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

Functions
template<place r_place, bool make_arrangement>
uint64_t	arrange (const std::vector< std::vector< node_size > > &L, const node r, position ini, position fin, linear_arrangement &arr) noexcept
	Make a maximum projective arrangement using the sorted, rooted adjacency list L. More...

uint64_t	arrange_projective (uint64_t n, const std::vector< std::vector< node_size > > &L, node r, linear_arrangement &arr) noexcept
	Wrapper method for the recursive method arrange. More...

uint64_t	arrange_projective (uint64_t n, const std::vector< std::vector< node_size > > &L, node r) noexcept
	Wrapper method for the recursive method arrange. More...

Detailed Description

Utilities for the various maximum linear arrangement algorithms.

Functions useful to calculate the maximum sum of edge lengths.

Function Documentation

template<place r_place, bool make_arrangement>

uint64_t lal::detail::DMax_utils::arrange	(	const std::vector< std::vector< node_size > > &	L,
		const node	r,
		position	ini,
		position	fin,
		linear_arrangement &	arr
	)

noexcept

Make a maximum projective arrangement using the sorted, rooted adjacency list L.

Template Parameters

r_place	Position of node r with respect to its parent.
make_arrangement	Whether or not the arrangement is to be constructed.

Parameters

	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.
	r	The vertex root of the subtree whose interval is to be made
	ini	Left limit of the positions of the arrangement in which the tree has to be arranged. Note that the limits are included [ini,fin].
	fin	Right limit of the positions of the arrangement in which the tree has to be arranged. Note that the limits are included [ini,fin].
[out]	arr	the arrangement of the tree.

Returns: The sum of the length of the outgoing edges from vertex 'r' plus the length of the anchor of the edge from 'r' to its parent. Such length is defined as the number of vertices to the left of 'r' if 'r_place' is RIGHT_PLACE, or as the number of vertices to the right of 'r' if 'r_place' is LEFT_PLACE.

uint64_t lal::detail::DMax_utils::arrange_projective	(	uint64_t	n,
		const std::vector< std::vector< node_size > > &	L,
		node	r
	)

inlinenoexcept

Wrapper method for the recursive method arrange.

A call to this function is done when the goal is not to construct a linear arrangement, only to calculate its cost.

Parameters

n	Number of vertices.
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.
r	Root of the tree represented by L.

uint64_t lal::detail::DMax_utils::arrange_projective	(	uint64_t	n,
		const std::vector< std::vector< node_size > > &	L,
		node	r,
		linear_arrangement &	arr
	)

inlinenoexcept

Wrapper method for the recursive method arrange.

A call to this function is done when the goal is to construct a linear arrangement.

Parameters

	n	Number of vertices.
	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.
	r	Root of the tree represented by L.
[out]	arr	maximum projective linear arrangement.