Utilities for the various optimal linear arrangement algorithms. More...

Typedefs
typedef unsigned char	place
	Useful typedef to denote relative position.

typedef unsigned char	side
	Useful typedef to denote relative position.

Functions
static constexpr side	other_side (side s) noexcept
	Other side of a vertex. If s is RIGHT_SIDE, returns LEFT_SIDE.

static constexpr bool	is_even (uint64_t i) noexcept
	Is an integer number even?

template<sorting::sort_type type>
void	make_sorted_adjacency_list_rooted (const graphs::rooted_tree &t, std::vector< std::vector< node_size > > &L) noexcept
	Make a sorted, rooted adjacency list sorted according to the sizes of the subtrees of the input rooted tree t.

Variables
static constexpr place	PLACE_LEFT_OF = 0
	A vertex is to be placed to the left of a vertex.

static constexpr place	PLACE_RIGHT_OF = 1
	A vertex is to be placed to the right of a vertex.

static constexpr place	PLACE_NONE_OF = 2
	There is no vertex to use as reference to determine the side.

static constexpr side	RIGHT_SIDE = 0
	Right side of a vertex.

static constexpr side	LEFT_SIDE = 1
	Left side of a vertex.

static constexpr char	LEFT_ANCHOR = -1
	The tree is left-anchored.

static constexpr char	RIGHT_ANCHOR = 1
	The tree is right-anchored.

static constexpr char	NO_ANCHOR = 0
	The tree is not anchored.

static constexpr char	ANCHOR = 1
	The tree is anchored.

Detailed Description

Utilities for the various optimal linear arrangement algorithms.

Functions useful to calculate both the minimum and maximum sum of edge lengths.

Function Documentation

void lal::detail::Dopt_utils::make_sorted_adjacency_list_rooted	(	const graphs::rooted_tree &	t,
		std::vector< std::vector< node_size > > &	L )

noexcept

Make a sorted, rooted adjacency list sorted according to the sizes of the subtrees of the input rooted tree t.

Parameters

	t	Input rooted tree.
[out]	L	Adjacency list-like data structure. \(L[u]\) is a list of pairs \((v, n_u(v))\) where \(v\) is a neighbour of \(u\) and \(n_u(v)=\|V(T^u_v)\|\) is the size of the subtree \(T^u_v\) in vertices.

Precondition: Parameter L is initialized to have size n, the number of vertices of the tree.