lal::detail::Dmin::unconstrained::Chung Namespace Reference

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

Typedefs
typedef array< node_size >	ordering
	Typedef for a useful type.

Functions
std::optional< uint64_t >	calculate_q (const uint64_t n, const ordering &ord) noexcept
	Calculate \(q\).
std::optional< uint64_t >	calculate_p (const uint64_t n, const ordering &ord) noexcept
	Calculate \(p\).
array< uint64_t >	get_P (const uint64_t p, uint64_t i) noexcept
	Calculate \(P\).
array< uint64_t >	get_Q (const uint64_t q, const uint64_t i) noexcept
	Calculate \(Q\).
ordering	get_ordering (const graphs::free_tree &t, const node u) noexcept
	Sort the children of u in the rooted tree \(T^u\).
template<char root, bool make_arrangement>
void	calculate_mla (graphs::free_tree &t, const node one_node, const position start, linear_arrangement &mla, uint64_t &cost) noexcept
	Calculate a minimum linear arrangment using Fan Chung's algorithm.

Detailed Description

Functions for Chung's minimum linear arrangement algorithm.

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

Function Documentation

calculate_mla()

template<char root, bool make_arrangement>

void lal::detail::Dmin::unconstrained::Chung::calculate_mla ( graphs::free_tree & t, const node one_node, const position start, linear_arrangement & mla, uint64_t & cost )

noexcept

Calculate a minimum linear arrangment using Fan Chung's algorithm.

For further details, see [15].

Template Parameters

root	Is the call to this function with a root?
make_arrangement	Whether or not the arrangement should be constructed.

Parameters

	t	Input free tree.
	one_node	Root or anchor.
	start	Starting position of the minLA of the current tree.
[out]	mla	A minimum arrangement.
[out]	cost	The cost of the minimum arrangement.

calculate_p()

std::optional< uint64_t > lal::detail::Dmin::unconstrained::Chung::calculate_p ( const uint64_t n, const ordering & ord )

nodiscardnoexcept

Calculate \(p\).

See [15] for details.

Parameters

n	Number of vertices
ord	Ordering of the children with respect to a node.

Returns

Returns the value of \(p\).

calculate_q()

std::optional< uint64_t > lal::detail::Dmin::unconstrained::Chung::calculate_q ( const uint64_t n, const ordering & ord )

nodiscardnoexcept

Calculate \(q\).

See [15] for details.

Parameters

n	Number of vertices
ord	Ordering of the children with respect to a node.

Returns

Returns the value of \(q\).

get_ordering()

ordering lal::detail::Dmin::unconstrained::Chung::get_ordering ( const graphs::free_tree & t, const node u )

nodiscardnoexcept

Sort the children of u in the rooted tree \(T^u\).

See [15] for further details.

Parameters

t	Input free tree.
u	Vertex.

Returns

Returns the children of u sorted in non-increasing order.

get_P()

array< uint64_t > lal::detail::Dmin::unconstrained::Chung::get_P ( const uint64_t p, uint64_t i )

nodiscardnoexcept

Calculate \(P\).

See [15] for details.

Parameters

p	See lal::detail::Dmin::unconstrained::Chung::calculate_p.
i	Index of the i-th children in the ordering.

Returns

Returns the value of \(P\).

get_Q()

array< uint64_t > lal::detail::Dmin::unconstrained::Chung::get_Q ( const uint64_t q, const uint64_t i )

nodiscardnoexcept

Calculate \(Q\).

See [15] for details.

Parameters

q	See lal::detail::Dmin::unconstrained::Chung::calculate_q.
i	Index of the i-th children in the ordering.

Returns

Returns the value of \(Q\).