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

Functions
template<bool make_arrangement>
uint64_t	arrange (const std::vector< std::vector< node_size > > &L, const node r, const place r_place, position ini, position fin, linear_arrangement &arr) noexcept
	Make a minimum 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 of the same name. More...

template<bool make_arrangement>
uint64_t	embed_branch (const std::vector< std::vector< node_size > > &L, node v, int64_t base, int64_t dir, data_array< int64_t > &rel_pos) noexcept
	Embed a tree's branch. More...

template<bool make_arrangement>
uint64_t	embed (const std::vector< std::vector< node_size > > &L, const node r, linear_arrangement &arr) noexcept
	Embed a tree's branch. More...

Detailed Description

Utilities for the various minimum linear arrangement algorithms.

Functions useful to calculate the minimum sum of edge lengths.

Function Documentation

◆ arrange()

template<bool make_arrangement>

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

noexcept

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

The full details of this algorithm can be found in [7].

Template Parameters

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
	r_place	Where, respect to its parent, node 'r' has been placed in the arrangement. Possible values: PLACE_LEFT_OF, PLACE_RIGHT_OF, PLACE_NONE_OF. The latter value is only valid for the root of the whole tree.
	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.

Precondition: L is sorted decreasingly.

◆ arrange_projective() [1/2]

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

inlinenoexcept

Wrapper method for the recursive method of the same name.

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.

Returns: The cost of a minimum projective linear arrangement.

Precondition: L is sorted decreasingly.

◆ arrange_projective() [2/2]

uint64_t lal::detail::Dmin_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	Minimum projective linear arrangement.

Returns: The cost of a minimum projective linear arrangement.

Precondition: L is sorted decreasingly.

◆ embed()

template<bool make_arrangement>

uint64_t lal::detail::Dmin_utils::embed	(	const std::vector< std::vector< node_size > > &	L,
		const node	r,
		linear_arrangement &	arr
	)

noexcept

Embed a tree's branch.

Implementation of procedure 'embed' as defined by Hochberg and Stallmann in [24] and with the correction in [7].

Template Parameters

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 used to construct L.
[out]	arr	The optimal arrangement.

Returns: The cost of a minimum linear arrangement of the corresponding branch.

Precondition: L is sorted decreasingly.

◆ embed_branch()

template<bool make_arrangement>

uint64_t lal::detail::Dmin_utils::embed_branch	(	const std::vector< std::vector< node_size > > &	L,
		node	v,
		int64_t	base,
		int64_t	dir,
		data_array< int64_t > &	rel_pos
	)

noexcept

Embed a tree's branch.

Implementation of procedure 'embed' as defined by Hochberg and Stallmann in [24] and with the correction in [7].

Template Parameters

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.
	v	The current branch of the tree to be arranged.
	base	The displacement for the starting position of the subtree arrangement
	dir	Whether or not v is to the left or to the right of its parent
[out]	rel_pos	the displacement from the root of all nodes of the subtree

Returns: The cost of a minimum linear arrangement of the corresponding branch.

Precondition: L is sorted decreasingly.