lal::detail::DMax::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
	Maximum projective arrangement of a rooted tree.

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::DMax::projective::AEF ( const graphs::rooted_tree & t )

nodiscardnoexcept

Maximum projective arrangement of a rooted tree.

This algorithm frst 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 [8].

Template Parameters

make_arrangement

Construct a maximum arrangement.

Parameters

t	Input tree.

Returns

A pair of cost and maximum linear arrangement.