LAL: Linear Arrangement Library 24.10.00
A library focused on algorithms on linear arrangements of graphs.
Loading...
Searching...
No Matches
BnB.hpp
1/*********************************************************************
2 *
3 * Linear Arrangement Library - A library that implements a collection
4 * algorithms for linear arrangments of graphs.
5 *
6 * Copyright (C) 2019 - 2024
7 *
8 * This file is part of Linear Arrangement Library. The full code is available
9 * at:
10 * https://github.com/LAL-project/linear-arrangement-library.git
11 *
12 * Linear Arrangement Library is free software: you can redistribute it
13 * and/or modify it under the terms of the GNU Affero General Public License
14 * as published by the Free Software Foundation, either version 3 of the
15 * License, or (at your option) any later version.
16 *
17 * Linear Arrangement Library is distributed in the hope that it will be
18 * useful, but WITHOUT ANY WARRANTY; without even the implied warranty of
19 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
20 * GNU Affero General Public License for more details.
21 *
22 * You should have received a copy of the GNU Affero General Public License
23 * along with Linear Arrangement Library. If not, see <http://www.gnu.org/licenses/>.
24 *
25 * Contact:
26 *
27 * LluĂ­s Alemany Puig (lluis.alemany.puig@upc.edu)
28 * LQMC (Quantitative, Mathematical, and Computational Linguisitcs)
29 * CQL (Complexity and Quantitative Linguistics Lab)
30 * Jordi Girona St 1-3, Campus Nord UPC, 08034 Barcelona. CATALONIA, SPAIN
31 * Webpage: https://cqllab.upc.edu/people/lalemany/
32 *
33 * Juan Luis Esteban (esteban@cs.upc.edu)
34 * LOGPROG: Logics and Programming Research Group
35 * Office 110, Omega building
36 * Jordi Girona St 1-3, Campus Nord UPC, 08034 Barcelona. CATALONIA, SPAIN
37 * Webpage: https://www.cs.upc.edu/~esteban/
38 *
39 * Ramon Ferrer i Cancho (rferrericancho@cs.upc.edu)
40 * LQMC (Quantitative, Mathematical, and Computational Linguisitcs)
41 * CQL (Complexity and Quantitative Linguistics Lab)
42 * Office 220, Omega building
43 * Jordi Girona St 1-3, Campus Nord UPC, 08034 Barcelona. CATALONIA, SPAIN
44 * Webpage: https://cqllab.upc.edu/people/rferrericancho/
45 *
46 ********************************************************************/
47
48#pragma once
49
50// lal includes
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>
60
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>
66
67#if defined __LAL_DEBUG_DMax_Unc_BnB
68#if !defined DEBUG
69#error("'__LAL_DEBUG_DMax_Unc_BnB' must be defined along with 'DEBUG'")
70#endif
71#endif
72
73namespace lal {
74namespace detail {
75namespace DMax {
76namespace unconstrained {
77
90class AEF_BnB {
91public:
93 static constexpr char VERTEX_ASSIGNED = 1;
95 static constexpr char VERTEX_UNASSIGNED = 0;
96
98 static constexpr bool debug_BnB =
99#if defined __LAL_DEBUG_DMax_Unc_BnB
100 true;
101#else
102 false;
103#endif
104
111 typedef std::conditional_t<debug_BnB, bool, void>
113
114public:
122 did_not_reach_end = 0b00000000,
124 reached_end = 0b00000001,
126 found_max = 0b00000010
127 };
128
130 [[nodiscard]] constexpr bool did_reach_end(const int at) const noexcept
131 { return at & process_end_result::reached_end; }
132
134 [[nodiscard]] constexpr bool did_find_max(const int at) const noexcept
135 { return at & process_end_result::found_max; }
136
137public:
142
156
157public:
175 const graphs::free_tree& t,
176 const array<std::vector<node>>& leaves,
177 // colors of vertices
179 const uint64_t num_verts_blue,
180 const uint64_t num_verts_red,
181 // paths
182 const std::vector<properties::branchless_path>& paths_in_tree,
183 const array<std::size_t>& node_to_path_idx,
184 const array<std::vector<node>>& incident_antennas,
185 // orbits
186 const std::vector<std::vector<node>>& orbits,
187 const array<std::size_t>& vertex_to_orbit
188 )
189 noexcept;
191 ~AEF_BnB() noexcept = default;
192
195 (const std::pair<uint64_t, linear_arrangement>& initial_DMax)
196 noexcept;
197
199 void exe(node first_node) noexcept;
200
201protected:
202
203 // -- constraints --
204
213 const node u, const int64_t level_u,
214 const node v, const int64_t level_v
215 ) const noexcept;
218 (const node u)
219 const noexcept;
222 (const node u, const int64_t level_u)
223 const noexcept;
226 (const node u, const int64_t level_u)
227 const noexcept;
230 (const node u, const int64_t level_u)
231 const noexcept;
232
242 [[nodiscard]] reason_discard discard_vertex(const node u, const position_t pos)
243 const noexcept;
244
245 // -- bounds --
246
248 [[nodiscard]] uint64_t upper_bound_generic
249 (const uint64_t D_p, const uint64_t D_ps_m, const position_t pos) noexcept;
250
253 (const uint64_t D_p, const uint64_t D_ps_m, const position_t pos) noexcept;
254
255 // -- state manipulation --
256
267 (const node u, const position_t pos, uint64_t& D_p, uint64_t& D_ps_m)
268 noexcept;
269
276 void recover_state(const position_t pos) noexcept;
277
278 // -- propagation of constraints -- //
279
282 (const node h, const node u) noexcept;
285 (const node u) noexcept;
288 (const node u) noexcept;
289
298 (const std::size_t path_idx, const LV_propagation_origin origin)
299 noexcept;
300
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;
310
314 (const std::size_t path_idx) noexcept;
318 (const std::size_t path_idx) noexcept;
321 (const node u) noexcept;
322
326 (const node u) noexcept;
327
331 (const node u) noexcept;
332
335 (const node u) noexcept;
336
337 // -- rollback constraints -- //
338
341 (const node u) noexcept;
342
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;
352
356 (const std::size_t path_idx) noexcept;
360 (const std::size_t path_idx) noexcept;
364 (const node u) noexcept;
365
369 (const node u) noexcept;
370
374 (const node u) noexcept;
377 (const node u) noexcept;
378
390 [[nodiscard]] int process_end(const uint64_t D, const position pos) noexcept;
391
392 // -- others --
393
395 [[nodiscard]] bool is_vertex_assigned(const node u) const noexcept {
397 }
398
400 [[nodiscard]] bool is_vertex_thistle(const node u) const noexcept {
401#if defined DEBUG
402 assert(is_vertex_assigned(u));
403#endif
404 return to_uint64(std::abs(m_node_level[u])) != m_t.get_degree(u);
405 }
406
408 [[nodiscard]] node leaf_parent(const node u) const noexcept {
409#if defined DEBUG
410 assert(m_t.get_degree(u) == 1);
411#endif
412 return m_t.get_neighbors(u)[0];
413 }
414
415 // -------------------------------------------------------------------------
416 // execute Branch and Bound for an independent set of vertices
417
418 /* Functions
419 * 'exe_independent_set'
420 * and
421 * 'exe_independent_set_leaves'
422 * do not call the 'update_state' functions since the construction of the
423 * arrangement is easy, final, and the information updated by the 'update_state'
424 * function is not needed anymore. Moreover, each call to 'update_state' requires
425 * a subsequent call to 'recover_state'.
426 *
427 * The value of D passed as parameter, 'D_p' is the sum of the lengths of all
428 * the edges whose both endpoints are assigned to the prefix of the arrangement
429 * before calling the function.
430 */
431
442 (const uint64_t D_p, position pos) noexcept;
443
454 (const uint64_t D_p, position pos) noexcept;
455
456 // -------------------------------------------------------------------------
457 // execute Branch and Bound for any tree
458
472 (const uint64_t D_p, const uint64_t D_ps_m, const position pos)
473 noexcept;
474
475private:
476 // -------------------------------------------------------------------------
477 // Tree-related data
478
480 const uint64_t m_n_nodes;
486 const uint64_t m_num_nodes_blue;
488 const uint64_t m_num_nodes_red;
494 const std::vector<properties::branchless_path>& m_paths_in_tree;
497 const array<std::vector<node>>& m_incident_antennas;
499 const std::vector<std::vector<node>>& m_orbits;
502
503 // -------------------------------------------------------------------------
504 // Data used for upper bounds
505
508
513
514 /* -------------------------- BORDER VERTICES -------------------------- */
515 // memory used to sort those vertices with some neighbor assigned.
516 // sorted by amount of assigned neighbors
517
522
523 /* -------------------------- BORDER VERTICES -------------------------- */
524
525 // -------------------------------------------------------------------------
526 // Algorithm control
527
537 struct path_info {
539 uint64_t num_thistles;
546
549 uint64_t min_pm_two;
552 uint64_t max_pm_two;
553
554 // number of vertices of level +-2 to assign to the arrangement
555 // known after the entire propagation of the path is complete
556 // (done only for antennas)
564 std::optional<uint64_t> nodes_p2_to_assign;
572 std::optional<uint64_t> nodes_m2_to_assign;
573 };
576
579
582
585 private:
586 std::size_t m_capacity;
587
588 public:
589 void init(std::size_t cap) noexcept {
590 m_capacity = cap;
591 }
592 [[nodiscard]] std::size_t operator()(const edge& p) const noexcept {
593 return p.first + p.second*m_capacity;
594 }
595 };
596
603
625
628
639
641 [[nodiscard]] bool has_valid_LV_prediction(node u) const noexcept
643
645 [[nodiscard]] bool is_node_a_trigger_of_LV(node u) const noexcept
647
648#if defined __LAL_DEBUG_DMax_Unc_BnB
649 // -------------------------------------------------------------------------
650 // Display of algorithm's data and progress
651
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)
667 noexcept;
668
669 // progress of algorithm
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); }
674#endif
675};
676
677} // -- namespace unconstrained
678} // -- namespace DMax
679} // -- namespace detail
680} // -- namespace lal
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 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
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