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::AEF_BnB Class Reference

A Branch and Bound algorithm for the maximum sum of edge lengths. More...

#include <BnB.hpp>

Classes

class  indexer_edge
 A helper class to be able to store edges in m_E_p, m_E_ps, m_E_s. More...
 
struct  path_info
 Data related to paths in the tree. More...
 

Public Types

enum  process_end_result { did_not_reach_end = 0b00000000 , reached_end = 0b00000001 , found_max = 0b00000010 }
 Enumeration used in the function process_end. More...
 
typedef std::conditional_t< debug_BnB, bool, void > exe_result_type
 Result of the main function of the algorithm.
 

Public Member Functions

constexpr bool did_reach_end (const int at) const noexcept
 Returns true if at does not contain process_end_result::did_not_reach_end.
 
constexpr bool did_find_max (const int at) const noexcept
 Returns true if at contains process_end_result::found_max.
 
 AEF_BnB (const graphs::free_tree &t, const array< std::vector< node > > &leaves, const properties::bipartite_graph_coloring &colors, const uint64_t num_verts_blue, const uint64_t num_verts_red, const std::vector< properties::branchless_path > &paths_in_tree, const array< std::size_t > &node_to_path_idx, const array< std::vector< node > > &incident_antennas, const std::vector< std::vector< node > > &orbits, const array< std::size_t > &vertex_to_orbit) noexcept
 Constructor.
 
 ~AEF_BnB () noexcept=default
 Destructor.
 
void initialize (const std::pair< uint64_t, linear_arrangement > &initial_DMax) noexcept
 Initialize the Branch and Bound algorithm.
 
void exe (node first_node) noexcept
 Execute the algorithm starting at the given vertex.
 
bool has_valid_LV_prediction (node u) const noexcept
 Does vertex u have a valid prediction of level value?
 
bool is_node_a_trigger_of_LV (node u) const noexcept
 Did a propagation of level values start at vertex u?
 

Public Attributes

const graphs::free_treem_t
 Reference to the input free tree.
 
graphs::rooted_tree m_rt
 Temporary memory to store m_t as a rooted tree.
 
set_maximum_arrangements m_max_arrs
 Complete result of the algorithm.
 
linear_arrangement m_arr
 Partial result of the algorithm.
 
const uint64_t m_num_nodes_blue
 Number of blue vertices (m_vertex_colors).
 
const uint64_t m_num_nodes_red
 Number of red vertices (m_vertex_colors).
 
uint64_t m_num_assigned_nodes_blue
 Number of blue vertices that are assigned to the prefix of the arrangement (m_vertex_colors).
 
uint64_t m_num_assigned_nodes_red
 Number of red vertices that are assigned to the prefix of the arrangement (m_vertex_colors).
 
const std::vector< properties::branchless_path > & m_paths_in_tree
 All the branchless paths of the tree.
 
const array< std::size_t > & m_node_to_path_idx
 An index for each vertex that points to its path in m_paths_in_tree.
 
const std::vector< std::vector< node > > & m_orbits
 The set of vertex orbits of the tree.
 
const array< std::size_t > & m_node_to_orbit
 An index for each vertex that points to its vertex orbit in m_orbits.
 
array< uint64_t > m_degree_count
 Frequency of degrees among unassigned vertices.
 
array< uint64_t > m_num_assigned_neighbors
 Number of assigned neighbor vertices for each vertex.
 
array< uint64_t > m_num_unassigned_neighbors
 Number of unassigned neighbor vertices for each vertex.
 
set_array< nodem_border_nodes
 The set of border vertices.
 
sorting::countingsort::memory< nodem_sorting_memory
 Auxiliary memory to speed up the calculation of the upper bound.
 
array< path_infom_path_info
 Control of vertices to assign in the arrangement with a specific level value.
 
node m_first_node
 First vertex with which to start the algorithm.
 
array< char > m_is_node_assigned
 The set of assigned nodes.
 
set_array< edge, indexer_edgem_E_p
 The set of edges fully contained in the prefix.
 
set_array< edge, indexer_edgem_E_ps
 The set of edges with one endpoint in the prefix, the other in the suffix.
 
set_array< edge, indexer_edgem_E_s
 The set of edges fully contained in the suffix.
 
array< uint64_t > m_node_left_degree
 Directional left degree of each assigned vertex.
 
array< uint64_t > m_node_right_degree
 Directional right degree of each assigned vertex.
 
array< int64_t > m_node_level
 The level value of each assigned vertex.
 
array< uint64_t > m_cut_values
 Cuts in the arrangement.
 
array< int64_t > m_predicted_LV
 The set of predicted level values for all vertices of the tree.
 
array< LV_propagation_originm_predicted_LV__origin
 Origin of a propagation of level values.
 

Static Public Attributes

static constexpr char VERTEX_ASSIGNED = 1
 Value to indicate that a vertex is assigned to the arrangement.
 
static constexpr char VERTEX_UNASSIGNED = 0
 Value to indicate that a vertex is not assigned to the arrangement.
 
static constexpr bool debug_BnB
 Used to determine the result type of certain functions.
 

Protected Member Functions

reason_discard check_propagation_node_to_node (const node u, const int64_t level_u, const node v, const int64_t level_v) const noexcept
 Can the propagation from vertex u to vertex v fail?
 
reason_discard discard_node__degree_2__bridge__level_0 (const node u) const noexcept
 Can a vertex of a bridge be discarded when it is to be assigned with level 0?
 
reason_discard discard_node__degree_2__bridge__level_pm2 (const node u, const int64_t level_u) const noexcept
 Can a vertex of a bridge be discarded when it is to be assigned with level \(\pm2\)?
 
reason_discard discard_node_degree_2 (const node u, const int64_t level_u) const noexcept
 Can a vertex of degree 2 be discarded?
 
reason_discard discard_node_degree_3 (const node u, const int64_t level_u) const noexcept
 Can a vertex of degree 3 be discarded?
 
reason_discard discard_vertex (const node u, const position_t pos) const noexcept
 Function to discard a vertex as the next vertex to add to the arrangement.
 
uint64_t upper_bound_generic (const uint64_t D_p, const uint64_t D_ps_m, const position_t pos) noexcept
 Calculate a 'generic' upper bound.
 
next_action what_to_do_next (const uint64_t D_p, const uint64_t D_ps_m, const position_t pos) noexcept
 Decide what to do next according to the value of the upper bound.
 
void update_state (const node u, const position_t pos, uint64_t &D_p, uint64_t &D_ps_m) noexcept
 Update the internal state of the algorithm.
 
void recover_state (const position_t pos) noexcept
 Update the internal state of the algorithm.
 
void propagate_LV__antenna__from_hub (const node h, const node u) noexcept
 Propagate level values at an antenna, starting at its hub.
 
void propagate_LV__antenna__from_leaf (const node u) noexcept
 Propagate level values at an antenna, starting at its leaf.
 
void propagate_LV__antenna__from_internal (const node u) noexcept
 Propagate level values at an antenna, starting at an internal vertex.
 
propagation_result propagate_LV__bridge__check_lowest_can_be_predicted (const std::size_t path_idx, const LV_propagation_origin origin) noexcept
 In a bridge, predict the level value of the lowest lexicographic vertex.
 
void propagate_LV__bridge__from_hub__h2 (const std::size_t path_idx) noexcept
 Propagate level values at a bridge, starting at the second hub.
 
void propagate_LV__bridge__from_hub__h1 (const std::size_t path_idx) noexcept
 Propagate level values at a bridge, starting at the first hub.
 
propagation_result propagate_LV__bridge__from_hub (const node h, const std::size_t path_idx) noexcept
 Propagate level values at a bridge, starting at a hub h.
 
void propagate_LV__bridge__from_lowest__level_0__towards_h2 (const std::size_t path_idx) noexcept
 
void propagate_LV__bridge__from_lowest__level_0__towards_h1 (const std::size_t path_idx) noexcept
 
void propagate_LV__bridge__from_lowest__level_0 (const node u) noexcept
 Propagate level values at a bridge starting at the lowest lexicographic.
 
propagation_result propagate_LV__bridge__from_lowest__level_pm2 (const node u) noexcept
 
propagation_result propagate_LV__bridge__from_internal (const node u) noexcept
 
propagation_result propagate_constraints (const node u) noexcept
 Propagate level values starting at vertex u.
 
void roll_back_LV__antenna (const node u) noexcept
 Undo the propagation of level values at an antenna.
 
void roll_back_LV__bridge__from_hub__h2 (const std::size_t path_idx) noexcept
 Undo the propagation of level values at a bridge, starting at the second hub.
 
void roll_back_LV__bridge__from_hub__h1 (const std::size_t path_idx) noexcept
 Undo the propagation of level values at a bridge, starting at the first hub.
 
void roll_back_LV__bridge__from_hub (const node h, const std::size_t path_idx) noexcept
 Undo the propagation of level values at a bridge.
 
void roll_back_LV__bridge__from_lowest__level_0__towards_h2 (const std::size_t path_idx) noexcept
 
void roll_back_LV__bridge__from_lowest__level_0__towards_h1 (const std::size_t path_idx) noexcept
 
void roll_back_LV__bridge__from_lowest__level_0 (const node u) noexcept
 
void roll_back_LV__bridge__from_lowest__level_pm2 (const node u) noexcept
 
void roll_back_LV__bridge__from_internal (const node u) noexcept
 
void roll_back_constraints (const node u) noexcept
 Undo the propagation of level values at a vertex u.
 
int process_end (const uint64_t D, const position pos) noexcept
 Take action at the end of the recursion.
 
bool is_vertex_assigned (const node u) const noexcept
 Is vertex u assigned to the prefix of the arrangement?
 
bool is_vertex_thistle (const node u) const noexcept
 Is vertex u a thistle vertex?
 
node leaf_parent (const node u) const noexcept
 Return the only parent of the leaf u.
 
exe_result_type exe_independent_set (const uint64_t D_p, position pos) noexcept
 Finish constructing the arrangement.
 
exe_result_type exe_independent_set_leaves (const uint64_t D_p, position pos) noexcept
 Finish constructing the arrangement.
 
exe_result_type exe (const uint64_t D_p, const uint64_t D_ps_m, const position pos) noexcept
 Execute the Branch and Bound algorithm.
 

Properties

 :bipartite_graph_coloring& m_vertex_colors
 Bipartite coloring of the tree.
 

Private Attributes

const uint64_t m_n_nodes
 Number of nodes.
 
const array< std::vector< node > > & m_leaves
 Set of leaves per vertex.
 

Detailed Description

A Branch and Bound algorithm for the maximum sum of edge lengths.

Readers are urged to read [7] for the full details of the inner workings of the algorithm.

In many of the parameters of the functions of this class we find the names:

  • D_p: this is the sum of edge lengths of the edges contained entirely in the prefix of the arrangement.
  • D_ps_m: this is the sum of edge lengths of the parts over the prefix of the arrangement of the edges partially contained in the prefix,

Member Typedef Documentation

◆ exe_result_type

Result of the main function of the algorithm.

If debug_BnB is true, then the function is to return a Boolean value that indicates if it found a maxium arrangement.

Member Enumeration Documentation

◆ process_end_result

Enumeration used in the function process_end.

These values are used as flags!

Enumerator
did_not_reach_end 

Algorithm did not completely construct the arrangement.

reached_end 

Algorithm reached the end of the arrangement.

found_max 

Algorithm reached found a new maximum.

Constructor & Destructor Documentation

◆ AEF_BnB()

lal::detail::DMax::unconstrained::AEF_BnB::AEF_BnB ( const graphs::free_tree & t,
const array< std::vector< node > > & leaves,
const properties::bipartite_graph_coloring & colors,
const uint64_t num_verts_blue,
const uint64_t num_verts_red,
const std::vector< properties::branchless_path > & paths_in_tree,
const array< std::size_t > & node_to_path_idx,
const array< std::vector< node > > & incident_antennas,
const std::vector< std::vector< node > > & orbits,
const array< std::size_t > & vertex_to_orbit )
noexcept

Constructor.

Parameters
tInput tree.
leavesSet of leaves per vertex.
colorsBipartite coloring of the tree.
num_verts_blueNumber of blue vertices.
num_verts_redNumber of red vertices.
paths_in_treeAll the branchless paths in the tree.
node_to_path_idxAn index for each vertex pointing to the branchless path it belongs.
incident_antennasFor every vertex u, this contains the list of the first nodes in all incident antennas
orbitsThe set of vertex orbits of the tree.
vertex_to_orbitAn index for each vertex pointing to the vertex orbit it belongs.

Member Function Documentation

◆ check_propagation_node_to_node()

reason_discard lal::detail::DMax::unconstrained::AEF_BnB::check_propagation_node_to_node ( const node u,
const int64_t level_u,
const node v,
const int64_t level_v ) const
nodiscardprotectednoexcept

Can the propagation from vertex u to vertex v fail?

This is only checked for pairs of vertices connected by a propagation path (any pair of vertices in an antenna, or pairs of vertices in a bridge where both are on the same side of its lowest lexicographic).

◆ discard_vertex()

reason_discard lal::detail::DMax::unconstrained::AEF_BnB::discard_vertex ( const node u,
const position_t pos ) const
nodiscardprotectednoexcept

Function to discard a vertex as the next vertex to add to the arrangement.

This function implements symmetry breaking constraints, optimality constraints, ... For details see code, or the paper [7].

Parameters
uVertex to test.
posPosition where the vertex is to be placed at.
Returns
Whether or not the vertex is to be discarded at this stage.

◆ exe()

exe_result_type lal::detail::DMax::unconstrained::AEF_BnB::exe ( const uint64_t D_p,
const uint64_t D_ps_m,
const position pos )
protectednoexcept

Execute the Branch and Bound algorithm.

The algorithm will add vertices starting at position 'pos'.

Parameters
D_pThe sum of the lengths of the edges in E_p, that is, the set of edges where both endpoints are assigned to the prefix.
D_ps_mThe sum of the partial length of the edges in E_ps, from the vertex assigned to the prefix to the border that separates the prefix and the suffix (between positions 'pos-1' and 'pos'), calculated as the length of the edge as if it ended at position 'pos'.
posPosition where to place the next vertex.

◆ exe_independent_set()

exe_result_type lal::detail::DMax::unconstrained::AEF_BnB::exe_independent_set ( const uint64_t D_p,
position pos )
protectednoexcept

Finish constructing the arrangement.

Under the assumption that the unassigned vertices make up an independent set.

Parameters
D_pSum of the lengths of the edges contained inside the prefix.
posPosition where to continue building the arrangement from.
Returns
Whether or not the algorithm found a new maximum arrangement.

◆ exe_independent_set_leaves()

exe_result_type lal::detail::DMax::unconstrained::AEF_BnB::exe_independent_set_leaves ( const uint64_t D_p,
position pos )
protectednoexcept

Finish constructing the arrangement.

Under the assumption that the unassigned vertices make up an independent set, and that all remaining vertices are leaves.

Parameters
D_pSum of the lengths of the edges contained inside the prefix.
posPosition where to continue building the arrangement from.
Returns
Whether or not the algorithm found a new maximum arrangement.

◆ process_end()

int lal::detail::DMax::unconstrained::AEF_BnB::process_end ( const uint64_t D,
const position pos )
nodiscardprotectednoexcept

Take action at the end of the recursion.

The algorithm has finished the construction of a linear arrangement and it's time to add it to the set of maximum arrangements.

Parameters
DCost of the arrangement.
posPosition to place the next vertex (it equals the number of vertices in this function).
Returns
Whether the recursion actually constructed the arrangement. The values returned are a combination of the values in process_end_result.

◆ propagate_LV__bridge__check_lowest_can_be_predicted()

propagation_result lal::detail::DMax::unconstrained::AEF_BnB::propagate_LV__bridge__check_lowest_can_be_predicted ( const std::size_t path_idx,
const LV_propagation_origin origin )
nodiscardprotectednoexcept

In a bridge, predict the level value of the lowest lexicographic vertex.

Checks if, after several propagations on the bridge, the level value of the lowest lexicographic vertex can be predicted, and assigns one when appropriate. This check can fail.

◆ propagate_LV__bridge__from_internal()

propagation_result lal::detail::DMax::unconstrained::AEF_BnB::propagate_LV__bridge__from_internal ( const node u)
nodiscardprotectednoexcept

Propagate level values at a bridge starting at an internal vertex that is not the lowest lexicographic.

◆ propagate_LV__bridge__from_lowest__level_0__towards_h1()

void lal::detail::DMax::unconstrained::AEF_BnB::propagate_LV__bridge__from_lowest__level_0__towards_h1 ( const std::size_t path_idx)
protectednoexcept

Propagate level values at a bridge starting at the lowest lexicographic with level value \(\pm 2\) towards the first hub.

◆ propagate_LV__bridge__from_lowest__level_0__towards_h2()

void lal::detail::DMax::unconstrained::AEF_BnB::propagate_LV__bridge__from_lowest__level_0__towards_h2 ( const std::size_t path_idx)
protectednoexcept

Propagate level values at a bridge starting at the lowest lexicographic with level value \(\pm 2\) towards the second hub.

◆ propagate_LV__bridge__from_lowest__level_pm2()

propagation_result lal::detail::DMax::unconstrained::AEF_BnB::propagate_LV__bridge__from_lowest__level_pm2 ( const node u)
nodiscardprotectednoexcept

Propagate level values at a bridge starting at the lowest lexicographic with level value \(0\).

◆ recover_state()

void lal::detail::DMax::unconstrained::AEF_BnB::recover_state ( const position_t pos)
protectednoexcept

Update the internal state of the algorithm.

Assuming that the vertex at position pos will be removed.

Parameters
posPosition to remove the vertex from.

◆ roll_back_LV__bridge__from_internal()

void lal::detail::DMax::unconstrained::AEF_BnB::roll_back_LV__bridge__from_internal ( const node u)
protectednoexcept

Undo the propagation of level values at a bridge, starting at an internal vertex.

◆ roll_back_LV__bridge__from_lowest__level_0()

void lal::detail::DMax::unconstrained::AEF_BnB::roll_back_LV__bridge__from_lowest__level_0 ( const node u)
protectednoexcept

Undo the propagation of level values at a bridge, starting at the lowest lexicographic of level value \(0\).

◆ roll_back_LV__bridge__from_lowest__level_0__towards_h1()

void lal::detail::DMax::unconstrained::AEF_BnB::roll_back_LV__bridge__from_lowest__level_0__towards_h1 ( const std::size_t path_idx)
protectednoexcept

Undo the propagation of level values at a bridge, starting at the lowest lexicographic of level value \(0\) towards the first hub.

◆ roll_back_LV__bridge__from_lowest__level_0__towards_h2()

void lal::detail::DMax::unconstrained::AEF_BnB::roll_back_LV__bridge__from_lowest__level_0__towards_h2 ( const std::size_t path_idx)
protectednoexcept

Undo the propagation of level values at a bridge, starting at the lowest lexicographic of level value \(0\) towards the second hub.

◆ roll_back_LV__bridge__from_lowest__level_pm2()

void lal::detail::DMax::unconstrained::AEF_BnB::roll_back_LV__bridge__from_lowest__level_pm2 ( const node u)
protectednoexcept

Undo the propagation of level values at a bridge, starting at the lowest lexicographic of level value \(\pm2\).

◆ update_state()

void lal::detail::DMax::unconstrained::AEF_BnB::update_state ( const node u,
const position_t pos,
uint64_t & D_p,
uint64_t & D_ps_m )
protectednoexcept

Update the internal state of the algorithm.

Assuming that vertex u will be placed at position pos.

Parameters
uNext vertex in the arrangement.
posNext position.
D_pSum of edge lengths of edges in the prefix.
D_ps_mSum of edge lengths of edges partially in the prefix.

Member Data Documentation

◆ m_arr

linear_arrangement lal::detail::DMax::unconstrained::AEF_BnB::m_arr

Partial result of the algorithm.

This arrangement is built from left to right, adding vertices one by one.

◆ m_max_arrs

set_maximum_arrangements lal::detail::DMax::unconstrained::AEF_BnB::m_max_arrs

Complete result of the algorithm.

The entire set of maximum arrangements we can make starting at the given vertex.

◆ m_node_left_degree

array<uint64_t> lal::detail::DMax::unconstrained::AEF_BnB::m_node_left_degree

Directional left degree of each assigned vertex.

This data is only valid for a vertex u when is_vertex_assigned returns true for u.

◆ m_node_level

array<int64_t> lal::detail::DMax::unconstrained::AEF_BnB::m_node_level

The level value of each assigned vertex.

This data is only valid for a vertex u when is_vertex_assigned returns true for u.

◆ m_node_right_degree

array<uint64_t> lal::detail::DMax::unconstrained::AEF_BnB::m_node_right_degree

Directional right degree of each assigned vertex.

This data is only valid for a vertex u when is_vertex_assigned returns true for u.

◆ m_predicted_LV__origin

array<LV_propagation_origin> lal::detail::DMax::unconstrained::AEF_BnB::m_predicted_LV__origin

Origin of a propagation of level values.

For each vertex u, information of the origin of the propagation of level values that went through u. Notice that u may be the origin of the propagation (see lal::detail::DMax::unconstrained::LV_propagation_origin::self).


The documentation for this class was generated from the following file: