lal::detail::Dmin::projective Namespace Reference

In projective arrangements. More...

Functions
template<bool make_arrangement>
std::conditional_t< make_arrangement, std::pair< uint64_t, linear_arrangement >, uint64_t >	AEF (const graphs::rooted_tree &t) noexcept
	Minimum projective arrangement of a rooted tree. More...
template<bool make_arrangement>
std::conditional_t< make_arrangement, std::pair< uint64_t, linear_arrangement >, uint64_t >	HS (const graphs::rooted_tree &t) noexcept
	Minimum projective arrangement of a rooted tree. More...

Detailed Description

In projective arrangements.

Function Documentation

AEF()

template<bool make_arrangement>

std::conditional_t< make_arrangement, std::pair< uint64_t, linear_arrangement >, uint64_t > lal::detail::Dmin::projective::AEF ( const graphs::rooted_tree &  t )

noexcept

Minimum projective arrangement of a rooted tree.

This function first constructs the sorted adjacency matrix rooted at the tree's root. Then, it arranges the tree so that there are no edge crossings and the root vertex is not covered. Such arrangement is done using a interval-based algorithm.

This function implements the algorithm in [7].

Template Parameters

make_arrangement

Construct a maximum arrangement.

Parameters

t	Input tree.

Returns

A pair of cost and minimum linear arrangement.

HS()

template<bool make_arrangement>

std::conditional_t< make_arrangement, std::pair< uint64_t, linear_arrangement >, uint64_t > lal::detail::Dmin::projective::HS ( const graphs::rooted_tree &  t )

noexcept

Minimum projective arrangement of a rooted tree.

This algorithm first constructs the sorted adjacency matrix rooted at the tree's root. Then, it arranges the tree so that there are no edge crossings and the root vertex is not covered. Such arrangement is done using a displacement-based algorithm.

This function implements the algorithm following the description in [7], i.e., this algorithm uses the approach first described by Hochberg and Stallmann in [24] using the correction in [7].

Template Parameters

make_arrangement

Construct a maximum arrangement.

Parameters

t	Input tree.

Returns

A pair of cost and minimum linear arrangement.