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

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

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

Detailed Description

Utilities for the various maximum linear arrangement algorithms.

Functions useful to calculate the maximum sum of edge lengths.

Function Documentation

template<Dopt_utils::place r_place, bool make_arrangement>

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

nodiscardnoexcept

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.

template<bool make_arrangement>

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

inlinenodiscardnoexcept

Wrapper method for the recursive method arrange.

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

Template Parameters

make_arrangement Should the arrangement be constructed?

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.