lal::detail::DMax::planar Namespace Reference

In planar arrangements. More...

Classes
struct	edge_size_sigma
	A tuple used to construct the sorted adjacency list. More...
struct	sorted_adjacency_list_info
	A piece of information within u's list. More...

Typedefs
typedef std::vector< std::vector< sorted_adjacency_list_info > >	sorted_adjacency_list
	Useful shorthand for a sorted adjacency list.

Enumerations
enum class	return_type_all_maxs { DMax_value_vertex_and_max_root , DMax_value_vertex , max_root }
	All return types as enumeration values. More...

Functions
sorted_adjacency_list	make_sorted_adjacency_list (const graphs::free_tree &t) noexcept
	Construct the for every vertex in the tree. .
template<return_type_all_maxs res_type>
conditional_list_t< bool_sequence< res_type==return_type_all_maxs::DMax_value_vertex_and_max_root, res_type==return_type_all_maxs::DMax_value_vertex, res_type==return_type_all_maxs::max_root >, type_sequence< std::pair< std::vector< uint64_t >, uint64_t >, std::vector< uint64_t >, uint64_t > >	all_max_sum_lengths_values (const graphs::free_tree &t) noexcept
	Maximum planar arrangement of a free tree.
template<bool make_arrangement>
std::conditional_t< make_arrangement, std::pair< uint64_t, linear_arrangement >, uint64_t >	AEF (const graphs::free_tree &t) noexcept
	Maximum planar arrangement of a free tree.

Detailed Description

In planar arrangements.

Enumeration Type Documentation

return_type_all_maxs

enum class lal::detail::DMax::planar::return_type_all_maxs

strong

All return types as enumeration values.

For function all_max_sum_lengths_values.

Enumerator
DMax_value_vertex_and_max_root	Return both the set of max projective values at every vertex and the vertex that maximizes the maximum projective.
DMax_value_vertex	Return only the max projective values for every vertex of the tree.
max_root	Return only a vertex that maximizes the maximum projective.

Function Documentation

AEF()

template<bool make_arrangement>

std::conditional_t< make_arrangement, std::pair< uint64_t, linear_arrangement >, uint64_t > lal::detail::DMax::planar::AEF ( const graphs::free_tree & t )

nodiscardnoexcept

Maximum planar arrangement of a free tree.

This algorithm calculates the maximum sum of edge lengths on every vertex and keeps track of the maximum. The calculation of DMax on every vertex is done in \(O(n)\) thanks to the adjacency list calculated by function make_sorted_adjacency_list.

This function calls all_max_sum_lengths_values, which implements the algorithm described in [8].

Template Parameters

make_arrangement

Construct a maximum arrangement.

Parameters

t	Input tree.

Returns

A pair of cost and maximum linear arrangement.

all_max_sum_lengths_values()

template<return_type_all_maxs res_type>

conditional_list_t< bool_sequence< res_type==return_type_all_maxs::DMax_value_vertex_and_max_root, res_type==return_type_all_maxs::DMax_value_vertex, res_type==return_type_all_maxs::max_root >, type_sequence< std::pair< std::vector< uint64_t >, uint64_t >, std::vector< uint64_t >, uint64_t > > lal::detail::DMax::planar::all_max_sum_lengths_values ( const graphs::free_tree & t )

nodiscardnoexcept

Maximum planar arrangement of a free tree.

This algorithm calculates the maximum sum of edge lengths on every vertex and keeps track of the maximum. The calculation of the maximum sum of edge lengths on every vertex is done in \(O(n)\) thanks to the adjacency list calculated by function make_sorted_adjacency_list.

This function implements the algorithm in [8].

Template Parameters

res_type

The type of result to return. See return_type_all_maxs for details.

Parameters

t	Input tree.

Returns

Depending of the value of res_type, a list of values, a p

make_sorted_adjacency_list()

sorted_adjacency_list lal::detail::DMax::planar::make_sorted_adjacency_list ( const graphs::free_tree & t )

inlinenodiscardnoexcept

Construct the for every vertex in the tree. .

Sorted adjacency list needed to calculate the maximum sum of edge legnths.

This adjacency list is needed in function all_max_sum_lengths_values.

Parameters

t	Input free tree.

Returns

The appropriate sorted adjacency list.