|
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?
|
|
|
const graphs::free_tree & | m_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< node > | m_border_nodes |
| The set of border vertices.
|
|
sorting::countingsort::memory< node > | m_sorting_memory |
| Auxiliary memory to speed up the calculation of the upper bound.
|
|
array< path_info > | m_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_edge > | m_E_p |
| The set of edges fully contained in the prefix.
|
|
set_array< edge, indexer_edge > | m_E_ps |
| The set of edges with one endpoint in the prefix, the other in the suffix.
|
|
set_array< edge, indexer_edge > | m_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_origin > | m_predicted_LV__origin |
| Origin of a propagation of level values.
|
|
|
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.
|
|
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,