Functions for Shiloach's minimum linear arrangement algorithm. More...

Functions
template<char anchored>
uint64_t	calculate_p_alpha (const uint64_t n, const ordering &ord, uint64_t &s_0, uint64_t &s_1) noexcept
	Calculate \(p_{\alpha}\). More...

template<char alpha, bool make_arrangement>
void	calculate_mla (graphs::free_tree &t, node root_or_anchor, position start, position end, linear_arrangement &mla, uint64_t &cost) noexcept
	Calculate a minimum linear arrangment using Shiloach's algorithm. More...

Detailed Description

Functions for Shiloach's minimum linear arrangement algorithm.

Namespace that holds function for Shiloach's algorithm for the minimum linear arrangement problem. See [34] for further details.

Function Documentation

template<char alpha, bool make_arrangement>

void lal::detail::Dmin::unconstrained::Shiloach::calculate_mla	(	graphs::free_tree &	t,
		node	root_or_anchor,
		position	start,
		position	end,
		linear_arrangement &	mla,
		uint64_t &	cost
	)

noexcept

Calculate a minimum linear arrangment using Shiloach's algorithm.

For further details, see [34].

Template Parameters

alpha	indicates whether the connected component of 't' is rooted or anchored.
make_arrangement	Whether or not the arrangement should be constructed.

Parameters

	t	input forest a single connected component of which has to be arranged.
	root_or_anchor	node used as a reference to the said connected component. Its value is within [1,n]
	start	position where to start placing the vertices (the leftmost position in the mla for the subtree).
	end	position where to end placing the vertices (the rightmost position int the mla for the subtree).
[out]	mla	A minimum arrangement.
[out]	cost	The cost of the minimum arrangement.

template<char anchored>

uint64_t lal::detail::Dmin::unconstrained::Shiloach::calculate_p_alpha	(	const uint64_t	n,
		const ordering &	ord,
		uint64_t &	s_0,
		uint64_t &	s_1
	)

noexcept

Calculate \(p_{\alpha}\).

See [34] for details.

Template Parameters

anchored Is the tree anchored?

Parameters

n	Number of vertices of the tree.
ord	Ordering of the children of a vertex in non-increasing order.
s_0	Value \(s_0\).
s_1	Value \(s_1\).