51#include <lal/basic_types.hpp>
52#include <lal/graphs/free_tree.hpp>
53#include <lal/graphs/rooted_tree.hpp>
54#include <lal/properties/branchless_path.hpp>
55#include <lal/properties/bipartite_graph_coloring.hpp>
56#include <lal/detail/array.hpp>
57#include <lal/detail/set_array.hpp>
58#include <lal/detail/macros/basic_convert.hpp>
59#include <lal/detail/sorting/counting_sort.hpp>
61#include <lal/detail/linarr/D/DMax/unconstrained/branch_and_bound/AEF/set_maximum_arrangements.hpp>
62#include <lal/detail/linarr/D/DMax/unconstrained/branch_and_bound/AEF/reason_discard.hpp>
63#include <lal/detail/linarr/D/DMax/unconstrained/branch_and_bound/AEF/next_action.hpp>
64#include <lal/detail/linarr/D/DMax/unconstrained/branch_and_bound/AEF/level_value_propagation_origin.hpp>
65#include <lal/detail/linarr/D/DMax/unconstrained/branch_and_bound/AEF/propagation_result.hpp>
67#if defined __LAL_DEBUG_DMax_Unc_BnB
69#error("'__LAL_DEBUG_DMax_Unc_BnB' must be defined along with 'DEBUG'")
76namespace unconstrained {
99#if defined __LAL_DEBUG_DMax_Unc_BnB
111 typedef std::conditional_t<debug_BnB, bool, void>
176 const array<std::vector<node>>& leaves,
179 const uint64_t num_verts_blue,
180 const uint64_t num_verts_red,
182 const std::vector<properties::branchless_path>& paths_in_tree,
184 const array<std::vector<node>>& incident_antennas,
186 const std::vector<std::vector<node>>& orbits,
213 const
node u, const int64_t level_u,
214 const
node v, const int64_t level_v
222 (const
node u, const int64_t level_u)
226 (const
node u, const int64_t level_u)
230 (const
node u, const int64_t level_u)
249 (const uint64_t D_p, const uint64_t D_ps_m, const
position_t pos) noexcept;
253 (const uint64_t D_p, const uint64_t D_ps_m, const
position_t pos) noexcept;
267 (const
node u, const
position_t pos, uint64_t& D_p, uint64_t& D_ps_m)
282 (const
node h, const
node u) noexcept;
285 (const
node u) noexcept;
288 (const
node u) noexcept;
303 (const std::
size_t path_idx) noexcept;
306 (const std::
size_t path_idx) noexcept;
309 (const
node h, const std::
size_t path_idx) noexcept;
314 (const std::
size_t path_idx) noexcept;
318 (const std::
size_t path_idx) noexcept;
321 (const
node u) noexcept;
326 (const
node u) noexcept;
331 (const
node u) noexcept;
335 (const
node u) noexcept;
341 (const
node u) noexcept;
345 (const std::
size_t path_idx) noexcept;
348 (const std::
size_t path_idx) noexcept;
351 (const
node h, const std::
size_t path_idx) noexcept;
356 (const std::
size_t path_idx) noexcept;
360 (const std::
size_t path_idx) noexcept;
364 (const
node u) noexcept;
369 (const
node u) noexcept;
374 (const
node u) noexcept;
377 (const
node u) noexcept;
442 (
const uint64_t D_p,
position pos)
noexcept;
454 (
const uint64_t D_p,
position pos)
noexcept;
472 (
const uint64_t D_p,
const uint64_t D_ps_m,
const position pos)
586 std::size_t m_capacity;
589 void init(std::size_t cap)
noexcept {
592 [[nodiscard]] std::size_t operator()(
const edge& p)
const noexcept {
593 return p.first + p.second*m_capacity;
648#if defined __LAL_DEBUG_DMax_Unc_BnB
652 void output_edge_list() const noexcept;
653 void output_arrangement() const noexcept;
654 void output_invarr(const
position p) const noexcept;
655 void output_degree_sequence(const
position p) const noexcept;
656 void output_left_degree_sequence(const
position p) const noexcept;
657 void output_right_degree_sequence(const
position p) const noexcept;
658 void output_level_sequence(const
position p) const noexcept;
659 void output_cut_signature(const
position p) const noexcept;
660 void output_num_assigned_neighbors() const noexcept;
661 void output_num_unassigned_neighbors() const noexcept;
662 void output_border_nodes() const noexcept;
663 void output_predicted_level_values() const noexcept;
664 void output_path_info() const noexcept;
665 void display_all_info
666 (const uint64_t D_p, const uint64_t D_ps_m, const
position pos)
670 std::
string m_tabstr;
671 const std::
string& tab() const noexcept {
return m_tabstr; }
672 void push_tab(
const std::string& add =
"| ") noexcept { m_tabstr += add; }
673 void pop_tab() noexcept { m_tabstr = m_tabstr.substr(0, m_tabstr.length() - 4); }
A helper class to be able to store edges in m_E_p, m_E_ps, m_E_s.
Definition BnB.hpp:584
A Branch and Bound algorithm for the maximum sum of edge lengths.
Definition BnB.hpp:90
void roll_back_LV__bridge__from_lowest__level_0__towards_h2(const std::size_t path_idx) noexcept
linear_arrangement m_arr
Partial result of the algorithm.
Definition BnB.hpp:155
set_array< edge, indexer_edge > m_E_ps
The set of edges with one endpoint in the prefix, the other in the suffix.
Definition BnB.hpp:600
int process_end(const uint64_t D, const position pos) noexcept
Take action at the end of the recursion.
set_array< edge, indexer_edge > m_E_p
The set of edges fully contained in the prefix.
Definition BnB.hpp:598
exe_result_type exe_independent_set(const uint64_t D_p, position pos) noexcept
Finish constructing the arrangement.
array< uint64_t > m_node_left_degree
Directional left degree of each assigned vertex.
Definition BnB.hpp:610
~AEF_BnB() noexcept=default
Destructor.
set_array< node > m_border_nodes
The set of border vertices.
Definition BnB.hpp:519
array< int64_t > m_predicted_LV
The set of predicted level values for all vertices of the tree.
Definition BnB.hpp:630
const graphs::free_tree & m_t
Reference to the input free tree.
Definition BnB.hpp:139
propagation_result propagate_LV__bridge__from_lowest__level_pm2(const node u) noexcept
array< path_info > m_path_info
Control of vertices to assign in the arrangement with a specific level value.
Definition BnB.hpp:575
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 propagate_LV__antenna__from_internal(const node u) noexcept
Propagate level values at an antenna, starting at an internal vertex.
static constexpr char VERTEX_ASSIGNED
Value to indicate that a vertex is assigned to the arrangement.
Definition BnB.hpp:93
array< LV_propagation_origin > m_predicted_LV__origin
Origin of a propagation of level values.
Definition BnB.hpp:638
reason_discard discard_node_degree_3(const node u, const int64_t level_u) const noexcept
Can a vertex of degree 3 be discarded?
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 roll_back_LV__antenna(const node u) noexcept
Undo the propagation of level values at an antenna.
bool has_valid_LV_prediction(node u) const noexcept
Does vertex u have a valid prediction of level value?
Definition BnB.hpp:641
uint64_t m_num_assigned_nodes_blue
Number of blue vertices that are assigned to the prefix of the arrangement (m_vertex_colors).
Definition BnB.hpp:490
array< char > m_is_node_assigned
The set of assigned nodes.
Definition BnB.hpp:581
uint64_t m_num_assigned_nodes_red
Number of red vertices that are assigned to the prefix of the arrangement (m_vertex_colors).
Definition BnB.hpp:492
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 propagate_LV__bridge__from_lowest__level_0__towards_h1(const std::size_t path_idx) noexcept
void roll_back_LV__bridge__from_internal(const node u) noexcept
process_end_result
Enumeration used in the function process_end.
Definition BnB.hpp:120
@ found_max
Algorithm reached found a new maximum.
Definition BnB.hpp:126
@ did_not_reach_end
Algorithm did not completely construct the arrangement.
Definition BnB.hpp:122
@ reached_end
Algorithm reached the end of the arrangement.
Definition BnB.hpp:124
array< uint64_t > m_cut_values
Cuts in the arrangement.
Definition BnB.hpp:627
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.
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?
array< uint64_t > m_num_unassigned_neighbors
Number of unassigned neighbor vertices for each vertex.
Definition BnB.hpp:512
propagation_result propagate_constraints(const node u) noexcept
Propagate level values starting at vertex u.
bool is_vertex_assigned(const node u) const noexcept
Is vertex u assigned to the prefix of the arrangement?
Definition BnB.hpp:395
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.
const uint64_t m_num_nodes_blue
Number of blue vertices (m_vertex_colors).
Definition BnB.hpp:486
void initialize(const std::pair< uint64_t, linear_arrangement > &initial_DMax) noexcept
Initialize the Branch and Bound algorithm.
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.
const uint64_t m_n_nodes
Number of nodes.
Definition BnB.hpp:480
std::conditional_t< debug_BnB, bool, void > exe_result_type
Result of the main function of the algorithm.
Definition BnB.hpp:112
constexpr bool did_reach_end(const int at) const noexcept
Returns true if at does not contain process_end_result::did_not_reach_end.
Definition BnB.hpp:130
sorting::countingsort::memory< node > m_sorting_memory
Auxiliary memory to speed up the calculation of the upper bound.
Definition BnB.hpp:521
array< int64_t > m_node_level
The level value of each assigned vertex.
Definition BnB.hpp:624
graphs::rooted_tree m_rt
Temporary memory to store m_t as a rooted tree.
Definition BnB.hpp:141
void roll_back_LV__bridge__from_lowest__level_0__towards_h1(const std::size_t path_idx) noexcept
void propagate_LV__antenna__from_leaf(const node u) noexcept
Propagate level values at an antenna, starting at its leaf.
set_maximum_arrangements m_max_arrs
Complete result of the algorithm.
Definition BnB.hpp:149
node leaf_parent(const node u) const noexcept
Return the only parent of the leaf u.
Definition BnB.hpp:408
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 ?
static constexpr bool debug_BnB
Used to determine the result type of certain functions.
Definition BnB.hpp:98
propagation_result propagate_LV__bridge__from_internal(const node u) noexcept
const uint64_t m_num_nodes_red
Number of red vertices (m_vertex_colors).
Definition BnB.hpp:488
void recover_state(const position_t pos) noexcept
Update the internal state of the algorithm.
void propagate_LV__bridge__from_lowest__level_0(const node u) noexcept
Propagate level values at a bridge starting at the lowest lexicographic.
set_array< edge, indexer_edge > m_E_s
The set of edges fully contained in the suffix.
Definition BnB.hpp:602
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.
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?
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_lowest__level_0__towards_h2(const std::size_t path_idx) noexcept
const array< std::vector< node > > & m_leaves
Set of leaves per vertex.
Definition BnB.hpp:482
bool is_node_a_trigger_of_LV(node u) const noexcept
Did a propagation of level values start at vertex u?
Definition BnB.hpp:645
const std::vector< properties::branchless_path > & m_paths_in_tree
All the branchless paths of the tree.
Definition BnB.hpp:494
void roll_back_LV__bridge__from_lowest__level_pm2(const node u) noexcept
node m_first_node
First vertex with which to start the algorithm.
Definition BnB.hpp:578
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.
constexpr bool did_find_max(const int at) const noexcept
Returns true if at contains process_end_result::found_max.
Definition BnB.hpp:134
exe_result_type exe_independent_set_leaves(const uint64_t D_p, position pos) noexcept
Finish constructing the arrangement.
array< uint64_t > m_node_right_degree
Directional right degree of each assigned vertex.
Definition BnB.hpp:617
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.
reason_discard discard_node_degree_2(const node u, const int64_t level_u) const noexcept
Can a vertex of degree 2 be discarded?
void exe(node first_node) noexcept
Execute the algorithm starting at the given 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.
array< uint64_t > m_num_assigned_neighbors
Number of assigned neighbor vertices for each vertex.
Definition BnB.hpp:510
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.
const std::vector< std::vector< node > > & m_orbits
The set of vertex orbits of the tree.
Definition BnB.hpp:499
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.
Definition BnB.hpp:496
void propagate_LV__antenna__from_hub(const node h, const node u) noexcept
Propagate level values at an antenna, starting at its hub.
static constexpr char VERTEX_UNASSIGNED
Value to indicate that a vertex is not assigned to the arrangement.
Definition BnB.hpp:95
void roll_back_constraints(const node u) noexcept
Undo the propagation of level values at a vertex u.
array< uint64_t > m_degree_count
Frequency of degrees among unassigned vertices.
Definition BnB.hpp:507
const array< std::size_t > & m_node_to_orbit
An index for each vertex that points to its vertex orbit in m_orbits.
Definition BnB.hpp:501
void roll_back_LV__bridge__from_lowest__level_0(const node u) noexcept
bool is_vertex_thistle(const node u) const noexcept
Is vertex u a thistle vertex?
Definition BnB.hpp:400
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.
Set of maximum arrangements up to isomorphism.
Definition set_maximum_arrangements.hpp:70
A set-like data structure implemented with an array.
Definition set_array.hpp:105
Free tree graph class.
Definition free_tree.hpp:60
Rooted tree graph class.
Definition rooted_tree.hpp:109
uint64_t get_degree(const node u) const noexcept
Returns the number of neighbors of u.
Definition undirected_graph.hpp:384
const neighbourhood & get_neighbors(const node u) const noexcept
Returns the neighbourhood of node u.
Definition undirected_graph.hpp:372
Linear arrangement of vertices.
Definition linear_arrangement.hpp:103
A class to represent a coloring of the vertices of a bipartite graph.
Definition bipartite_graph_coloring.hpp:60
reason_discard
The many different reasons to not assign a vertex to the arrangement.
Definition reason_discard.hpp:67
next_action
What should be done after checking the upper bound?
Definition next_action.hpp:67
LV_propagation_origin
Origin of the propagation of level value.
Definition level_value_propagation_origin.hpp:67
@ self
This indicates the origin of the propagation.
propagation_result
The possible results of the propagation of level values.
Definition propagation_result.hpp:67
constexpr uint64_t to_uint64(const T &t) noexcept
Conversion to uint64_t.
Definition basic_convert.hpp:52
Main namespace of the library.
Definition basic_types.hpp:48
std::pair< node, node > edge
See Edge page for further details.
Definition basic_types.hpp:56
uint64_t position
Node's position type.
Definition basic_types.hpp:53
uint64_t node
Node type. See Node / Vertex page for further details.
Definition basic_types.hpp:51
Data related to paths in the tree.
Definition BnB.hpp:537
uint64_t num_assigned_nodes_p2
Number of vertices in the path assigned to the arrangement with level +2.
Definition BnB.hpp:543
uint64_t min_pm_two
Definition BnB.hpp:549
uint64_t num_assigned_nodes_m2
Number of vertices in the path assigned to the arrangement with level -2.
Definition BnB.hpp:545
std::optional< uint64_t > nodes_p2_to_assign
Number of vertices of this path to be assigned with level +2 in the arrangement.
Definition BnB.hpp:564
uint64_t num_thistles
Number of thistle vertices in the path (assigned to the arrangement).
Definition BnB.hpp:539
uint64_t max_pm_two
Definition BnB.hpp:552
std::optional< uint64_t > nodes_m2_to_assign
Number of vertices of this path to be assigned with level -2 in the arrangement.
Definition BnB.hpp:572
uint64_t num_assigned_nodes
Number of vertices in the path assigned to the arrangement.
Definition BnB.hpp:541
Wrapper of a C array for automatic deallocation of memory.
Definition array.hpp:59
Memory used for the counting sort algorithm.
Definition counting_sort.hpp:72
Typesafe position type.
Definition basic_types.hpp:244