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

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

Typedefs
typedef lal::detail::data_array< node_size >	ordering
	Typedef for a useful type.

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

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 [11] 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, node  one_node, position  start, linear_arrangement &  mla, uint64_t &  cost  )

noexcept

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

For further details, see [11].

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 ( uint64_t  n, const ordering &  ord  )

noexcept

Calculate \(p\).

See [11] 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 ( uint64_t  n, const ordering &  ord  )

noexcept

Calculate \(q\).

See [11] 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, node  u  )

noexcept

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

See [11] for further details.

Parameters

t	Input free tree.
u	Vertex.

Returns

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

get_P()

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

noexcept

Calculate \(P\).

See [11] 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()

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

noexcept

Calculate \(Q\).

See [11] 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\).