LAL: Linear Arrangement Library 24.10.00
A library focused on algorithms on linear arrangements of graphs.
Loading...
Searching...
No Matches
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

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

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

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

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.