lal::detail::DMax::unconstrained Namespace Reference

In unconstrained arrangements. More...

Classes
class	AEF_BnB
	A Branch and Bound algorithm for the maximum sum of edge lengths. More...
class	set_maximum_arrangements
	Set of maximum arrangements up to isomorphism. More...

Enumerations
enum class	LV_propagation_origin : int8_t {   antenna_leaf , antenna_internal , antenna_hub , bridge_hub_1 ,   bridge_hub_2 , bridge_lowest_pm2 , bridge_lowest_0 , bridge_internal_left ,   bridge_internal_right , self , none }
	Origin of the propagation of level value. More...
enum class	next_action : int8_t { bound , continue_normally , continue_independent_set , continue_independent_set_leaves }
	What should be done after checking the upper bound? More...
enum class	propagation_result : int8_t { success , conflict_LV_propagation , conflict_LV_emulated_propagation , __last_item }
	The possible results of the propagation of level values. More...
enum class	reason_discard : int8_t {   none , will_produce_bipartite_arrangement , node_of_antenna_as_thistle , thistle_in_bridge_is_not_the_lowest ,   hub_disallows_placement_of_antennas , placement_is_in_conflict_with_level_prediction , level_signature_will_not_be_nonincreasing , missing_entire_path ,   missing_degree1 , missing_degree2_lp2 , missing_degree2_lm2 , adjacent_vertices_with_equal_level_value ,   node_disallows_placement_of_neighbors , placement_fails_level_propagation , largest_cut_below_minimum , nodes_of_equal_level_disobey_lexicographic_order ,   node_leaves_disobey_lexicographic_order , roots_of_isomorphic_subtrees_disobey_lexicographic_order , __last_item }
	The many different reasons to not assign a vertex to the arrangement. More...

Detailed Description

In unconstrained arrangements.

Enumeration Type Documentation

LV_propagation_origin

enum class lal::detail::DMax::unconstrained::LV_propagation_origin : int8_t

strong

Origin of the propagation of level value.

This is used in lal::detail::DMax::unconstrained::AEF_BnB to keep track the origin of each propagation of level values.

Enumerator
antenna_leaf	Propagation started at the leaf of an antenna.
antenna_internal	Propagation started at an internal vertex of an antenna.
antenna_hub	Propagation started at the hub of an antenna.
bridge_hub_1	Propagation started at the first hub of a bridge.
bridge_hub_2	Propagation started at the second hub of a bridge.
bridge_lowest_pm2	Propagation started at the lowest lexicographic vertex of a bridge. The level value of this vertex is \(\pm2\).
bridge_lowest_0	Propagation started at the lowest lexicographic vertex of a bridge. The level value of this vertex is \(0\).
bridge_internal_left	Propagation started at an internal vertex of a bridge. This vertex is to the left of the lowest lexicographic vertex in the bridge.
bridge_internal_right	Propagation started at an internal vertex of a bridge. This vertex is to the right of the lowest lexicographic vertex in the bridge.
self	This indicates the origin of the propagation.
none	Null value.

next_action

enum class lal::detail::DMax::unconstrained::next_action : int8_t

strong

What should be done after checking the upper bound?

This is used in lal::detail::DMax::unconstrained::AEF_BnB to decide what to do after the upper bound was calculated.

Enumerator
bound	Bound the exploration (Bound).
continue_normally	Continue the exploration normally (Branch)
continue_independent_set	Finish the exploration. In this case, the remaining vertices to assign make up an independent set in which not all vertices have degree 1.
continue_independent_set_leaves	Finish the exploration. In this case, the remaining vertices to assign make up an independent set in which all vertices have degree 1.

propagation_result

enum class lal::detail::DMax::unconstrained::propagation_result : int8_t

strong

The possible results of the propagation of level values.

This is used in lal::detail::DMax::unconstrained::AEF_BnB when propagating level values. See also lal::detail::DMax::unconstrained::LV_propagation_origin.

Enumerator
success	The propagation did not fail.
conflict_LV_propagation	There was a conflict while propagating the level value.
conflict_LV_emulated_propagation	There was a conflict when emulating the propagation of level value.
__last_item	Null value. This is used only for debugging.

reason_discard

enum class lal::detail::DMax::unconstrained::reason_discard : int8_t

strong

The many different reasons to not assign a vertex to the arrangement.

This is used in lal::detail::DMax::unconstrained::AEF_BnB before deciding whether or not a vertex should be arranged at the next empty position.

Enumerator
none	No reason to discard. Use the vertex.
will_produce_bipartite_arrangement	Placing the vertex will produce a bipartite arrangement.
node_of_antenna_as_thistle	Placing this vertex will produce a thistle located at an antenna.
thistle_in_bridge_is_not_the_lowest	This vertex wants to be a thistle (and could be one) but it is not the lowest vertex (in the lexicographic order) among the vertices of the bridge.
hub_disallows_placement_of_antennas	A hub vertex has a level value that does not allow an optimal placement of some of the antennas incident to it.
placement_is_in_conflict_with_level_prediction	The level prediction made will not be met.
level_signature_will_not_be_nonincreasing	If the vertex is placed then the level signature will not be non-increasing – breaks Nurse's properties.
missing_entire_path	If the vertex is placed then none of the vertices (of degree <= 2) of some path will be allowed to be placed in the arrangement.
missing_degree1	If the vertex is placed then some leaf will be misplaced (thus breaking the non-increasing order of level values).
missing_degree2_lp2	If the vertex is placed then some degree-2 vertex will be misplaced (with level value +2), thus breaking the non-increasing order of level values.
missing_degree2_lm2	If the vertex is placed then some degree-2 vertex will be misplaced (with level value -2), thus breaking the non-increasing order of level values.
adjacent_vertices_with_equal_level_value	If the vertex is placed then it will have the same level value as one of its neighbor vertices (in the graph) – breaks Nurse's properties.
node_disallows_placement_of_neighbors	Placing this vertex prevents the construction of a maximum arrangement since the placement of its remaining neighbors will not satisfy (1) non-increasing level sequence, (2) neighbors may have the same level value.
placement_fails_level_propagation	Placing this vertex (of |level|=2) will surely fail level value propagation, thus eventually breaking one of Nurse's properties.
largest_cut_below_minimum	The largest cut is below the lower bound for the maximum cut value.
nodes_of_equal_level_disobey_lexicographic_order	The vertices in the same level value interval in the arrangement are not sorted by lexicographic order.
node_leaves_disobey_lexicographic_order	The leaves attached to the same vertex are not arranged so that they appear (from left to right) in the lexicographic order.
roots_of_isomorphic_subtrees_disobey_lexicographic_order	The vertices that are root of isomorphic subtrees are not arranged so that they appear (from left to right) in the lexicographic order.
__last_item	Null value.