Algorithms for caterpillar trees. More...

Enumerations
enum	result { distance , distance_vertices , distance_structure }
	What is to be calculated when finding the maximum spanning caterpillar. More...

Functions
template<class tree_t >
node	find_farthest_vertex (const tree_t &t, const node start_at, BFS< tree_t > &bfs, array< uint64_t > &num_vertices_in_path, array< uint64_t > &weight) noexcept
	Find the farthest vertex from start_at in the tree.

template<result ret_type, class tree_t , std::enable_if_t< std::is_base_of_v< graphs::tree, tree_t >, bool > = true>
conditional_list_t< bool_sequence< ret_type==result::distance, ret_type==result::distance_vertices, ret_type==result::distance_structure >, type_sequence< uint64_t, std::tuple< uint64_t, std::vector< char > >, std::tuple< uint64_t, std::vector< node >, std::vector< char > > > >	max_subtree (const tree_t &t) noexcept
	Calculate the maximum spanning caterpillar of a tree.

Detailed Description

Algorithms for caterpillar trees.

Enumeration Type Documentation

◆ result

enum lal::detail::maximum_subtrees::caterpillar::result

What is to be calculated when finding the maximum spanning caterpillar.

Enumerator

distance

Only the caterpillar distance.

distance_vertices

Caterpillar distance plus caterpillar structure's nodes.

The only vector represents the set of nodes that belong to the caterpillar in the form of a bitset.

distance_structure

Caterpillar distance plus the caterpillar's structure.

The second vector contains the caterpillar backbone in the form of an "ordered" path. It is guaranteed that the path starts at the first vertex and finishes at the last vertex of the second vector.

The third vector represents the set of nodes that belong to the caterpillar in the form of a bitset.

Function Documentation

◆ find_farthest_vertex()

template<class tree_t >

node lal::detail::maximum_subtrees::caterpillar::find_farthest_vertex	(	const tree_t &	t,
		const node	start_at,
		BFS< tree_t > &	bfs,
		array< uint64_t > &	num_vertices_in_path,
		array< uint64_t > &	weight )

nodiscardnoexcept

Find the farthest vertex from start_at in the tree.

Distance is defined as the number of vertices in the path plus the number of vertices neighbouring the path.

Template Parameters

tree_t Type of tree.

Parameters

t	Input tree.
start_at	Starting vertex.
bfs	Traversal object.
num_vertices_in_path	Function memory.
weight	Function memory.

Returns: The farthest vertex from start_at

◆ max_subtree()

template<result ret_type, class tree_t , std::enable_if_t< std::is_base_of_v< graphs::tree, tree_t >, bool > = true>

conditional_list_t< bool_sequence< ret_type==result::distance, ret_type==result::distance_vertices, ret_type==result::distance_structure >, type_sequence< uint64_t, std::tuple< uint64_t, std::vector< char > >, std::tuple< uint64_t, std::vector< node >, std::vector< char > > > > lal::detail::maximum_subtrees::caterpillar::max_subtree ( const tree_t & t )

nodiscardnoexcept

Calculate the maximum spanning caterpillar of a tree.