lal::detail::Dopt_utils Namespace Reference

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
template<typename sort_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. More...

Variables
constexpr char	LEFT_ANCHOR = -1
	The tree is left-anchored.
constexpr char	RIGHT_ANCHOR = 1
	The tree is right-anchored.
constexpr char	NO_ANCHOR = 0
	The tree is not anchored.
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

make_sorted_adjacency_list_rooted()

template<typename sort_type >

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 initialised to have size n, the number of vertices of the tree.