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_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.

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

typedef std::conditional_t<debug_BnB, bool, void> lal::detail::DMax::unconstrained::AEF_BnB::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

enum lal::detail::DMax::unconstrained::AEF_BnB::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

t	Input tree.
leaves	Set of leaves per vertex.
colors	Bipartite coloring of the tree.
num_verts_blue	Number of blue vertices.
num_verts_red	Number of red vertices.
paths_in_tree	All the branchless paths in the tree.
node_to_path_idx	An index for each vertex pointing to the branchless path it belongs.
incident_antennas	For every vertex u, this contains the list of the first nodes in all incident antennas
orbits	The set of vertex orbits of the tree.
vertex_to_orbit	An 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

u	Vertex to test.
pos	Position 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_p	The 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_m	The 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'.
pos	Position 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_p	Sum of the lengths of the edges contained inside the prefix.
pos	Position 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_p	Sum of the lengths of the edges contained inside the prefix.
pos	Position 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

D	Cost of the arrangement.
pos	Position 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

pos	Position 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

u	Next vertex in the arrangement.
pos	Next position.
D_p	Sum of edge lengths of edges in the prefix.
D_ps_m	Sum 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:

• lal/detail/linarr/D/DMax/unconstrained/branch_and_bound/AEF/BnB.hpp