The data structures used in the Branch and Bound algorithm. More...

#include "mst.h"

Classes
struct	SubProblem
	The struct used to represent a SubProblem or node of the Branch and Bound tree. More...

struct	Problem
	The struct used to represent the overall problem. More...

struct	SubProblemElem
	The element of the list of SubProblems. More...

struct	SubProblemsList
	The list of open SubProblems. More...

struct	SubProblemsListIterator
	The iterator of the list of SubProblems. More...

Typedefs
typedef enum BBNodeType	BBNodeType
	The labels used to identify the type of a SubProblem.

typedef enum ConstraintType	ConstraintType
	The enum used to identify the type of Edge constraints.

typedef struct SubProblem	SubProblem
	The struct used to represent a SubProblem or node of the Branch and Bound tree.

typedef struct Problem	Problem
	The struct used to represent the overall problem.

typedef struct SubProblemElem	SubProblemElem
	The element of the list of SubProblems.

typedef struct SubProblemsList	SubProblemsList
	The list of open SubProblems.

Enumerations
enum	BBNodeType { OPEN , CLOSED_NN , CLOSED_NN_HYBRID , CLOSED_BOUND , CLOSED_UNFEASIBLE , CLOSED_1TREE , CLOSED_SUBGRADIENT }
	The labels used to identify the type of a SubProblem. More...

enum	ConstraintType { NOTHING , MANDATORY , FORBIDDEN }
	The enum used to identify the type of Edge constraints. More...

Functions
void	new_SubProblemList (SubProblemsList *list)
	Create a new SubProblem List.

void	delete_SubProblemList (SubProblemsList *list)
	Delete a SubProblem List.

bool	is_SubProblemList_empty (SubProblemsList *list)
	Check if a SubProblem List is empty.

size_t	get_SubProblemList_size (SubProblemsList *list)
	Get the size of a SubProblem List.

void	add_elem_SubProblemList_bottom (SubProblemsList list, SubProblem element)
	Add a SubProblem to the bottom of a SubProblem List.

void	add_elem_SubProblemList_index (SubProblemsList list, SubProblem element, size_t index)
	Add a SubProblem at a specific index of a SubProblem List.

void	delete_SubProblemList_elem_index (SubProblemsList *list, size_t index)
	Remove a SubProblem from a specific index of a SubProblem List.

SubProblem *	get_SubProblemList_elem_index (SubProblemsList *list, size_t index)
	Get a SubProblem from a specific index of a SubProblem List.

SubProblemsListIterator *	create_SubProblemList_iterator (SubProblemsList *list)
	Create a new SubProblem List iterator on a SubProblem List.

bool	is_SubProblemList_iterator_valid (SubProblemsListIterator *iterator)
	Check if a SubProblem List iterator is valid.

SubProblem *	SubProblemList_iterator_get_next (SubProblemsListIterator *iterator)
	Get the next element of a SubProblem List iterator.

void	delete_SubProblemList_iterator (SubProblemsListIterator *iterator)
	Delete a SubProblem List iterator.

Detailed Description

The data structures used in the Branch and Bound algorithm.

Author: Lorenzo Sciandra

Header file that contains the core data structures used in the Branch and Bound algorithm. There are the data structures used to represent the problem, the sub-problems and the list of sub-problems.

Version: 1.0.0 @data 2024-05-1

Copyright: Copyright (c) 2024, license MIT

Repo: https://github.com/LorenzoSciandra/GraphConvolutionalBranchandBound

Definition in file b_and_b_data.h.

Typedef Documentation

◆ BBNodeType

typedef enum BBNodeType BBNodeType

The labels used to identify the type of a SubProblem.

◆ ConstraintType

typedef enum ConstraintType ConstraintType

The enum used to identify the type of Edge constraints.

◆ Problem

typedef struct Problem Problem

The struct used to represent the overall problem.

◆ SubProblem

typedef struct SubProblem SubProblem

The struct used to represent a SubProblem or node of the Branch and Bound tree.

◆ SubProblemElem

typedef struct SubProblemElem SubProblemElem

The element of the list of SubProblems.

◆ SubProblemsList

typedef struct SubProblemsList SubProblemsList

The list of open SubProblems.

Enumeration Type Documentation

◆ BBNodeType

enum BBNodeType

The labels used to identify the type of a SubProblem.

Enumerator
OPEN	The SubProblem is a feasible 1Tree, with a value lower than the best solution found so far.
CLOSED_NN	The SubProblem is a feasible 1Tree founded with the Nearest Neighbor algorithm, it is the first feasible solution found.
CLOSED_NN_HYBRID	The SubProblem is a feasible 1Tree founded with the Hybrid version of Nearest Neighbor algorithm, it is the first feasible solution found.
CLOSED_BOUND	The SubProblem is a feasible 1Tree, with a value greater than the best solution found so far.
CLOSED_UNFEASIBLE	The SubProblem is not a feasible 1Tree, and so discarded.
CLOSED_1TREE	The SubProblem is closed by calculating the 1Tree.
CLOSED_SUBGRADIENT	The SubProblem is closed in the subgradient algorithm, the ascending dual.

Definition at line 22 of file b_and_b_data.h.

◆ ConstraintType

enum ConstraintType

The enum used to identify the type of Edge constraints.

Enumerator
NOTHING	The Edge has no constraints.
MANDATORY	The Edge is mandatory.
FORBIDDEN	The Edge is forbidden.

Definition at line 34 of file b_and_b_data.h.

Function Documentation

◆ add_elem_SubProblemList_bottom()

void add_elem_SubProblemList_bottom	(	SubProblemsList *	list,
		SubProblem *	element
	)

Add a SubProblem to the bottom of a SubProblem List.

Parameters

list	The SubProblem List to modify.
element	The SubProblem to add.

Definition at line 59 of file b_and_b_data.c.

◆ add_elem_SubProblemList_index()

void add_elem_SubProblemList_index	(	SubProblemsList *	list,
		SubProblem *	element,
		size_t	index
	)

Add a SubProblem at a specific index of a SubProblem List.

Parameters

list	The SubProblem List to modify.
element	The SubProblem to add.
index	The index where to add the SubProblem.

list is clearer way but it is already checked inside get_list_size

Definition at line 75 of file b_and_b_data.c.

◆ create_SubProblemList_iterator()

SubProblemsListIterator * create_SubProblemList_iterator ( SubProblemsList * list )

Create a new SubProblem List iterator on a SubProblem List.

Parameters

list	The SubProblem List to iterate.

Returns: the SubProblem List iterator.

Definition at line 159 of file b_and_b_data.c.

◆ delete_SubProblemList()

void delete_SubProblemList ( SubProblemsList * list )

Delete a SubProblem List.

Parameters

list	The SubProblem List to delete.

Definition at line 23 of file b_and_b_data.c.

◆ delete_SubProblemList_elem_index()

void delete_SubProblemList_elem_index	(	SubProblemsList *	list,
		size_t	index
	)

Remove a SubProblem from a specific index of a SubProblem List.

Parameters

list	The SubProblem List to modify.
index	The index of the SubProblem to remove.

Definition at line 113 of file b_and_b_data.c.

◆ delete_SubProblemList_iterator()

void delete_SubProblemList_iterator ( SubProblemsListIterator * iterator )

Delete a SubProblem List iterator.

Parameters

iterator The SubProblem List iterator.

Definition at line 198 of file b_and_b_data.c.

◆ get_SubProblemList_elem_index()

SubProblem * get_SubProblemList_elem_index	(	SubProblemsList *	list,
		size_t	index
	)

Get a SubProblem from a specific index of a SubProblem List.

Parameters

list	The SubProblem List to inspect.
index	The index of the SubProblem to get.

Returns: The SubProblem at the specified index.

Definition at line 146 of file b_and_b_data.c.

◆ get_SubProblemList_size()

size_t get_SubProblemList_size ( SubProblemsList * list )

Get the size of a SubProblem List.

Parameters

list	The SubProblem List to inspect.

Returns: The size of the SubProblem List.

Definition at line 54 of file b_and_b_data.c.

◆ is_SubProblemList_empty()

bool is_SubProblemList_empty ( SubProblemsList * list )

Check if a SubProblem List is empty.

Parameters

list	The SubProblem List to check.

Returns: True if the SubProblem List is empty, false otherwise.

Definition at line 39 of file b_and_b_data.c.

◆ is_SubProblemList_iterator_valid()

bool is_SubProblemList_iterator_valid ( SubProblemsListIterator * iterator )

Check if a SubProblem List iterator is valid.

An iterator is valid if it is not NULL and if the current element is not NULL.

Parameters

iterator The SubProblem List iterator to check.

Returns: True if the SubProblem List iterator is valid, false otherwise.

Definition at line 170 of file b_and_b_data.c.

◆ new_SubProblemList()

void new_SubProblemList ( SubProblemsList * list )

Create a new SubProblem List.

Parameters

list	The SubProblem List to create.

Definition at line 17 of file b_and_b_data.c.

◆ SubProblemList_iterator_get_next()

SubProblem * SubProblemList_iterator_get_next ( SubProblemsListIterator * iterator )

Get the next element of a SubProblem List iterator.

Parameters

iterator The SubProblem List iterator.

Returns: The next element of the List pointed by the iterator.

Definition at line 188 of file b_and_b_data.c.

Classes

Typedefs

Enumerations

Functions

Detailed Description

Typedef Documentation

◆ BBNodeType

◆ ConstraintType

◆ Problem

◆ SubProblem

◆ SubProblemElem

◆ SubProblemsList

Enumeration Type Documentation

◆ BBNodeType

◆ ConstraintType

Function Documentation

◆ add_elem_SubProblemList_bottom()

◆ add_elem_SubProblemList_index()

◆ create_SubProblemList_iterator()

◆ delete_SubProblemList()

◆ delete_SubProblemList_elem_index()

◆ delete_SubProblemList_iterator()

◆ get_SubProblemList_elem_index()

◆ get_SubProblemList_size()

◆ is_SubProblemList_empty()

◆ is_SubProblemList_iterator_valid()

◆ new_SubProblemList()

◆ SubProblemList_iterator_get_next()