Centroid decomposition over a rooted tree represented as an Aleph graph. More...

#include <Tree_Decomposition.H>

Collaboration diagram for Aleph::Gen_Centroid_Decomposition< GT, SA >:

Public Types
using	Node = typename GT::Node

Public Member Functions
	Gen_Centroid_Decomposition (const GT &g, Node *root, SA sa=SA())
	Construct using an explicit root node.

	Gen_Centroid_Decomposition (const GT &g, SA sa=SA())
	Construct using the first graph node as root.

size_t	size () const noexcept

bool	is_empty () const noexcept

Node *	root () const noexcept

size_t	root_id () const noexcept

Node *	node_of (const size_t id) const

size_t	id_of (const Node *node) const

size_t	centroid_root_id () const noexcept
	Root centroid ID of the centroid tree (or `NONE` if empty).

Node *	centroid_root () const noexcept
	Root centroid node of the centroid tree (or `nullptr` if empty).

size_t	centroid_parent_id (const size_t id) const
	Parent centroid ID of `id` (or `NONE` if centroid root).

Node *	centroid_parent (const Node *node) const
	Parent centroid of `node` (or `nullptr` if centroid root).

size_t	centroid_level_of_id (const size_t id) const
	Level of centroid `id` in centroid tree (root level = 0).

size_t	centroid_level_of (const Node *node) const
	Level of centroid node in centroid tree (root level = 0).

size_t	max_centroid_level () const noexcept
	Maximum centroid-tree level.

size_t	centroid_path_length_of_id (const size_t id) const
	Number of centroid ancestors stored for node ID.

size_t	centroid_path_length_of (const Node *node) const
	Number of centroid ancestors stored for node.

const Array< size_t > &	centroid_ancestors_of_id (const size_t id) const
	Centroid ancestors of node ID from centroid root down to local centroid.

const Array< size_t > &	centroid_distances_of_id (const size_t id) const
	Distances to centroid ancestors (aligned with `centroid_ancestors_of_id`).

const Array< size_t > &	centroid_ancestors_of (const Node *node) const
	Centroid ancestors of node from centroid root down to local centroid.

const Array< size_t > &	centroid_distances_of (const Node *node) const
	Distances to centroid ancestors (aligned with `centroid_ancestors_of`).

bool	is_centroid_ancestor_id (const size_t ancestor, const size_t node) const
	True iff `ancestor` is in the centroid-ancestor chain of `node`.

size_t	distance_to_centroid_id (const size_t node, const size_t centroid) const
	Distance from node ID to a centroid ancestor ID.

template<class F >
void	for_each_centroid_ancestor_id (const size_t node, F &&f) const
	Visit each centroid ancestor of node ID.

template<class F >
void	for_each_centroid_ancestor (const Node *node, F &&f) const
	Visit each centroid ancestor of node.

Private Types
using	Topology = tree_decomposition_detail::Rooted_Tree_Topology< GT, SA >

Private Member Functions
void	ensure_not_empty (const char *where) const

void	init_storage ()

Array< size_t >	collect_component_nodes (const size_t start)

size_t	choose_centroid (const Array< size_t > &nodes)

void	append_centroid_annotations (const size_t centroid)

void	build_centroid_tree ()

Private Attributes
Topology	topology_

Array< char >	removed_

Array< size_t >	centroid_parent_

Array< size_t >	centroid_level_

size_t	centroid_root_ = NONE

Array< size_t >	local_parent_

Array< size_t >	local_subtree_

Array< Array< size_t > >	centroid_ancestors_

Array< Array< size_t > >	centroid_distances_

Static Private Attributes
static constexpr size_t	NONE = Topology::NONE

Detailed Description

template<class GT, class SA = Dft_Show_Arc<GT>>
class Aleph::Gen_Centroid_Decomposition< GT, SA >

Centroid decomposition over a rooted tree represented as an Aleph graph.

Decomposes a tree recursively by centroids, building a centroid tree.

For each original node u, the class stores:

centroid_ancestors_of_id(u)
centroid_distances_of_id(u)

where element k in both arrays corresponds to the same centroid ancestor.

Build complexity: O(n log n) Storage complexity: O(n log n)

Template Parameters

GT	Graph type.
SA	Arc filter type.

Definition at line 1023 of file Tree_Decomposition.H.

Member Typedef Documentation

◆ Node

template<class GT , class SA = Dft_Show_Arc<GT>>

using Aleph::Gen_Centroid_Decomposition< GT, SA >::Node = typename GT::Node

Definition at line 1026 of file Tree_Decomposition.H.

◆ Topology

template<class GT , class SA = Dft_Show_Arc<GT>>

using Aleph::Gen_Centroid_Decomposition< GT, SA >::Topology = tree_decomposition_detail::Rooted_Tree_Topology<GT, SA>

private

Definition at line 1029 of file Tree_Decomposition.H.

Constructor & Destructor Documentation

◆ Gen_Centroid_Decomposition() [1/2]

template<class GT , class SA = Dft_Show_Arc<GT>>

Aleph::Gen_Centroid_Decomposition< GT, SA >::Gen_Centroid_Decomposition	(	const GT &	g,
		Node *	root,
		SA	sa = `SA()`
	)

inline

Construct using an explicit root node.

Definition at line 1237 of file Tree_Decomposition.H.

◆ Gen_Centroid_Decomposition() [2/2]

template<class GT , class SA = Dft_Show_Arc<GT>>

Aleph::Gen_Centroid_Decomposition< GT, SA >::Gen_Centroid_Decomposition	(	const GT &	g,
		SA	sa = `SA()`
	)

inline

Construct using the first graph node as root.

Definition at line 1244 of file Tree_Decomposition.H.

Member Function Documentation

◆ append_centroid_annotations()

template<class GT , class SA = Dft_Show_Arc<GT>>

void Aleph::Gen_Centroid_Decomposition< GT, SA >::append_centroid_annotations ( const size_t centroid )

inlineprivate

Definition at line 1158 of file Tree_Decomposition.H.

References Aleph::tree_decomposition_detail::Rooted_Tree_Topology< GT, SA >::adjacency(), Aleph::Gen_Centroid_Decomposition< GT, SA >::centroid_ancestors_, Aleph::Gen_Centroid_Decomposition< GT, SA >::centroid_distances_, Aleph::divide_and_conquer_partition_dp(), Aleph::DynListStack< T >::is_empty(), Aleph::Gen_Centroid_Decomposition< GT, SA >::NONE, Aleph::DynListStack< T >::pop(), Aleph::DynListStack< T >::push(), Aleph::Gen_Centroid_Decomposition< GT, SA >::removed_, and Aleph::Gen_Centroid_Decomposition< GT, SA >::topology_.

Referenced by Aleph::Gen_Centroid_Decomposition< GT, SA >::build_centroid_tree().

◆ build_centroid_tree()

template<class GT , class SA = Dft_Show_Arc<GT>>

void Aleph::Gen_Centroid_Decomposition< GT, SA >::build_centroid_tree ( )

inlineprivate

Definition at line 1187 of file Tree_Decomposition.H.

◆ centroid_ancestors_of()

template<class GT , class SA = Dft_Show_Arc<GT>>

const Array< size_t > & Aleph::Gen_Centroid_Decomposition< GT, SA >::centroid_ancestors_of ( const Node * node ) const

inline

Centroid ancestors of node from centroid root down to local centroid.

Definition at line 1342 of file Tree_Decomposition.H.

◆ centroid_ancestors_of_id()

template<class GT , class SA = Dft_Show_Arc<GT>>

const Array< size_t > & Aleph::Gen_Centroid_Decomposition< GT, SA >::centroid_ancestors_of_id ( const size_t id ) const

inline

Centroid ancestors of node ID from centroid root down to local centroid.

Definition at line 1328 of file Tree_Decomposition.H.

Referenced by TYPED_TEST().

◆ centroid_distances_of()

template<class GT , class SA = Dft_Show_Arc<GT>>

const Array< size_t > & Aleph::Gen_Centroid_Decomposition< GT, SA >::centroid_distances_of ( const Node * node ) const

inline

Distances to centroid ancestors (aligned with centroid_ancestors_of).

Definition at line 1348 of file Tree_Decomposition.H.

◆ centroid_distances_of_id()

template<class GT , class SA = Dft_Show_Arc<GT>>

const Array< size_t > & Aleph::Gen_Centroid_Decomposition< GT, SA >::centroid_distances_of_id ( const size_t id ) const

inline

Distances to centroid ancestors (aligned with centroid_ancestors_of_id).

Definition at line 1335 of file Tree_Decomposition.H.

Referenced by TYPED_TEST().

◆ centroid_level_of()

template<class GT , class SA = Dft_Show_Arc<GT>>

size_t Aleph::Gen_Centroid_Decomposition< GT, SA >::centroid_level_of ( const Node * node ) const

inline

Level of centroid node in centroid tree (root level = 0).

Definition at line 1300 of file Tree_Decomposition.H.

◆ centroid_level_of_id()

template<class GT , class SA = Dft_Show_Arc<GT>>

size_t Aleph::Gen_Centroid_Decomposition< GT, SA >::centroid_level_of_id ( const size_t id ) const

inline

Level of centroid id in centroid tree (root level = 0).

Definition at line 1293 of file Tree_Decomposition.H.

Referenced by TYPED_TEST().

◆ centroid_parent()

template<class GT , class SA = Dft_Show_Arc<GT>>

Node * Aleph::Gen_Centroid_Decomposition< GT, SA >::centroid_parent ( const Node * node ) const

inline

Parent centroid of node (or nullptr if centroid root).

Definition at line 1286 of file Tree_Decomposition.H.

References Aleph::divide_and_conquer_partition_dp().

◆ centroid_parent_id()

template<class GT , class SA = Dft_Show_Arc<GT>>

size_t Aleph::Gen_Centroid_Decomposition< GT, SA >::centroid_parent_id ( const size_t id ) const

inline

Parent centroid ID of id (or NONE if centroid root).

Definition at line 1279 of file Tree_Decomposition.H.

Referenced by TYPED_TEST().

◆ centroid_path_length_of()

template<class GT , class SA = Dft_Show_Arc<GT>>

size_t Aleph::Gen_Centroid_Decomposition< GT, SA >::centroid_path_length_of ( const Node * node ) const

inline

Number of centroid ancestors stored for node.

Definition at line 1322 of file Tree_Decomposition.H.

◆ centroid_path_length_of_id()

template<class GT , class SA = Dft_Show_Arc<GT>>

size_t Aleph::Gen_Centroid_Decomposition< GT, SA >::centroid_path_length_of_id ( const size_t id ) const

inline

Number of centroid ancestors stored for node ID.

Definition at line 1315 of file Tree_Decomposition.H.

◆ centroid_root()

template<class GT , class SA = Dft_Show_Arc<GT>>

Node * Aleph::Gen_Centroid_Decomposition< GT, SA >::centroid_root ( ) const

inlinenoexcept

Root centroid node of the centroid tree (or nullptr if empty).

Definition at line 1273 of file Tree_Decomposition.H.

References Aleph::divide_and_conquer_partition_dp().

Referenced by TYPED_TEST(), TYPED_TEST(), and TYPED_TEST().

◆ centroid_root_id()

template<class GT , class SA = Dft_Show_Arc<GT>>

size_t Aleph::Gen_Centroid_Decomposition< GT, SA >::centroid_root_id ( ) const

inlinenoexcept

Root centroid ID of the centroid tree (or NONE if empty).

Definition at line 1267 of file Tree_Decomposition.H.

Referenced by main(), and TYPED_TEST().

◆ choose_centroid()

template<class GT , class SA = Dft_Show_Arc<GT>>

size_t Aleph::Gen_Centroid_Decomposition< GT, SA >::choose_centroid ( const Array< size_t > & nodes )

inlineprivate

Definition at line 1108 of file Tree_Decomposition.H.

References Aleph::tree_decomposition_detail::Rooted_Tree_Topology< GT, SA >::adjacency(), ah_runtime_error_unless, Aleph::divide_and_conquer_partition_dp(), Aleph::Gen_Centroid_Decomposition< GT, SA >::local_parent_, Aleph::Gen_Centroid_Decomposition< GT, SA >::local_subtree_, nodes, Aleph::Gen_Centroid_Decomposition< GT, SA >::removed_, Aleph::Gen_Centroid_Decomposition< GT, SA >::size(), and Aleph::Gen_Centroid_Decomposition< GT, SA >::topology_.

Referenced by Aleph::Gen_Centroid_Decomposition< GT, SA >::build_centroid_tree().

◆ collect_component_nodes()

template<class GT , class SA = Dft_Show_Arc<GT>>

Array< size_t > Aleph::Gen_Centroid_Decomposition< GT, SA >::collect_component_nodes ( const size_t start )

inlineprivate

Definition at line 1078 of file Tree_Decomposition.H.

References Aleph::tree_decomposition_detail::Rooted_Tree_Topology< GT, SA >::adjacency(), Aleph::divide_and_conquer_partition_dp(), Aleph::DynListStack< T >::is_empty(), Aleph::Gen_Centroid_Decomposition< GT, SA >::local_parent_, nodes, Aleph::Gen_Centroid_Decomposition< GT, SA >::NONE, Aleph::DynListStack< T >::pop(), Aleph::DynListStack< T >::push(), Aleph::Gen_Centroid_Decomposition< GT, SA >::removed_, Aleph::Gen_Centroid_Decomposition< GT, SA >::size(), and Aleph::Gen_Centroid_Decomposition< GT, SA >::topology_.

Referenced by Aleph::Gen_Centroid_Decomposition< GT, SA >::build_centroid_tree().

◆ distance_to_centroid_id()

template<class GT , class SA = Dft_Show_Arc<GT>>

size_t Aleph::Gen_Centroid_Decomposition< GT, SA >::distance_to_centroid_id	(	const size_t	node,
		const size_t	centroid
	)		const

inline

Distance from node ID to a centroid ancestor ID.

Returns NONE if centroid is not in node's centroid-ancestor chain.

Definition at line 1372 of file Tree_Decomposition.H.

References Aleph::divide_and_conquer_partition_dp().

◆ ensure_not_empty()

template<class GT , class SA = Dft_Show_Arc<GT>>

void Aleph::Gen_Centroid_Decomposition< GT, SA >::ensure_not_empty ( const char * where ) const

inlineprivate

Definition at line 1045 of file Tree_Decomposition.H.

References ah_domain_error_if, Aleph::divide_and_conquer_partition_dp(), and Aleph::Gen_Centroid_Decomposition< GT, SA >::is_empty().

◆ for_each_centroid_ancestor()

template<class GT , class SA = Dft_Show_Arc<GT>>

template<class F >

void Aleph::Gen_Centroid_Decomposition< GT, SA >::for_each_centroid_ancestor	(	const Node *	node,
		F &&	f
	)		const

inline

Visit each centroid ancestor of node.

Callback signature: f(centroid_id, distance, index).

Definition at line 1413 of file Tree_Decomposition.H.

◆ for_each_centroid_ancestor_id()

template<class GT , class SA = Dft_Show_Arc<GT>>

template<class F >

void Aleph::Gen_Centroid_Decomposition< GT, SA >::for_each_centroid_ancestor_id	(	const size_t	node,
		F &&	f
	)		const

inline

Visit each centroid ancestor of node ID.

Callback signature: f(centroid_id, distance, index).

Definition at line 1393 of file Tree_Decomposition.H.

References ah_runtime_error_unless, and Aleph::divide_and_conquer_partition_dp().

Referenced by main(), TYPED_TEST(), and TYPED_TEST().

◆ id_of()

template<class GT , class SA = Dft_Show_Arc<GT>>

size_t Aleph::Gen_Centroid_Decomposition< GT, SA >::id_of ( const Node * node ) const

inline

Definition at line 1261 of file Tree_Decomposition.H.

Referenced by main(), and TYPED_TEST().

◆ init_storage()

template<class GT , class SA = Dft_Show_Arc<GT>>

void Aleph::Gen_Centroid_Decomposition< GT, SA >::init_storage ( )

inlineprivate

Definition at line 1050 of file Tree_Decomposition.H.

Referenced by Aleph::Gen_Centroid_Decomposition< GT, SA >::build_centroid_tree().

◆ is_centroid_ancestor_id()

template<class GT , class SA = Dft_Show_Arc<GT>>

bool Aleph::Gen_Centroid_Decomposition< GT, SA >::is_centroid_ancestor_id	(	const size_t	ancestor,
		const size_t	node
	)		const

inline

True iff ancestor is in the centroid-ancestor chain of node.

Definition at line 1354 of file Tree_Decomposition.H.

References Aleph::divide_and_conquer_partition_dp().

◆ is_empty()

template<class GT , class SA = Dft_Show_Arc<GT>>

bool Aleph::Gen_Centroid_Decomposition< GT, SA >::is_empty ( ) const

inlinenoexcept

Definition at line 1251 of file Tree_Decomposition.H.

Referenced by Aleph::Gen_Centroid_Decomposition< GT, SA >::ensure_not_empty(), Aleph::Gen_Centroid_Decomposition< GT, SA >::init_storage(), and TYPED_TEST().

◆ max_centroid_level()

template<class GT , class SA = Dft_Show_Arc<GT>>

size_t Aleph::Gen_Centroid_Decomposition< GT, SA >::max_centroid_level ( ) const

inlinenoexcept

Maximum centroid-tree level.

Definition at line 1306 of file Tree_Decomposition.H.

References Aleph::divide_and_conquer_partition_dp(), and Aleph::size().

◆ node_of()

template<class GT , class SA = Dft_Show_Arc<GT>>

Node * Aleph::Gen_Centroid_Decomposition< GT, SA >::node_of ( const size_t id ) const

inline

Definition at line 1256 of file Tree_Decomposition.H.

◆ root()

template<class GT , class SA = Dft_Show_Arc<GT>>

Node * Aleph::Gen_Centroid_Decomposition< GT, SA >::root ( ) const

inlinenoexcept

Definition at line 1253 of file Tree_Decomposition.H.

◆ root_id()

template<class GT , class SA = Dft_Show_Arc<GT>>

size_t Aleph::Gen_Centroid_Decomposition< GT, SA >::root_id ( ) const

inlinenoexcept

Definition at line 1254 of file Tree_Decomposition.H.

◆ size()

template<class GT , class SA = Dft_Show_Arc<GT>>

size_t Aleph::Gen_Centroid_Decomposition< GT, SA >::size ( ) const

inlinenoexcept

Definition at line 1250 of file Tree_Decomposition.H.

Referenced by Aleph::Gen_Centroid_Decomposition< GT, SA >::build_centroid_tree(), Aleph::Gen_Centroid_Decomposition< GT, SA >::choose_centroid(), Aleph::Gen_Centroid_Decomposition< GT, SA >::collect_component_nodes(), Aleph::Gen_Centroid_Decomposition< GT, SA >::init_storage(), main(), TYPED_TEST(), TYPED_TEST(), and TYPED_TEST().

Member Data Documentation

◆ centroid_ancestors_

template<class GT , class SA = Dft_Show_Arc<GT>>

Array<Array<size_t> > Aleph::Gen_Centroid_Decomposition< GT, SA >::centroid_ancestors_

private

Definition at line 1042 of file Tree_Decomposition.H.

Referenced by Aleph::Gen_Centroid_Decomposition< GT, SA >::append_centroid_annotations(), and Aleph::Gen_Centroid_Decomposition< GT, SA >::init_storage().

◆ centroid_distances_

template<class GT , class SA = Dft_Show_Arc<GT>>

Array<Array<size_t> > Aleph::Gen_Centroid_Decomposition< GT, SA >::centroid_distances_

private

Definition at line 1043 of file Tree_Decomposition.H.

Referenced by Aleph::Gen_Centroid_Decomposition< GT, SA >::append_centroid_annotations(), and Aleph::Gen_Centroid_Decomposition< GT, SA >::init_storage().

◆ centroid_level_

template<class GT , class SA = Dft_Show_Arc<GT>>

Array<size_t> Aleph::Gen_Centroid_Decomposition< GT, SA >::centroid_level_

private

Definition at line 1036 of file Tree_Decomposition.H.

Referenced by Aleph::Gen_Centroid_Decomposition< GT, SA >::build_centroid_tree(), and Aleph::Gen_Centroid_Decomposition< GT, SA >::init_storage().

◆ centroid_parent_

template<class GT , class SA = Dft_Show_Arc<GT>>

Array<size_t> Aleph::Gen_Centroid_Decomposition< GT, SA >::centroid_parent_

private

Definition at line 1035 of file Tree_Decomposition.H.

Referenced by Aleph::Gen_Centroid_Decomposition< GT, SA >::build_centroid_tree(), and Aleph::Gen_Centroid_Decomposition< GT, SA >::init_storage().

◆ centroid_root_

template<class GT , class SA = Dft_Show_Arc<GT>>

size_t Aleph::Gen_Centroid_Decomposition< GT, SA >::centroid_root_ = NONE

private

Definition at line 1037 of file Tree_Decomposition.H.

Referenced by Aleph::Gen_Centroid_Decomposition< GT, SA >::build_centroid_tree(), and Aleph::Gen_Centroid_Decomposition< GT, SA >::init_storage().

◆ local_parent_

template<class GT , class SA = Dft_Show_Arc<GT>>

Array<size_t> Aleph::Gen_Centroid_Decomposition< GT, SA >::local_parent_

private

Definition at line 1039 of file Tree_Decomposition.H.

Referenced by Aleph::Gen_Centroid_Decomposition< GT, SA >::choose_centroid(), Aleph::Gen_Centroid_Decomposition< GT, SA >::collect_component_nodes(), and Aleph::Gen_Centroid_Decomposition< GT, SA >::init_storage().

◆ local_subtree_

template<class GT , class SA = Dft_Show_Arc<GT>>

Array<size_t> Aleph::Gen_Centroid_Decomposition< GT, SA >::local_subtree_

private

Definition at line 1040 of file Tree_Decomposition.H.

Referenced by Aleph::Gen_Centroid_Decomposition< GT, SA >::choose_centroid(), and Aleph::Gen_Centroid_Decomposition< GT, SA >::init_storage().

◆ NONE

template<class GT , class SA = Dft_Show_Arc<GT>>

constexpr size_t Aleph::Gen_Centroid_Decomposition< GT, SA >::NONE = Topology::NONE

staticconstexprprivate

Definition at line 1030 of file Tree_Decomposition.H.

Referenced by Aleph::Gen_Centroid_Decomposition< GT, SA >::append_centroid_annotations(), Aleph::Gen_Centroid_Decomposition< GT, SA >::build_centroid_tree(), Aleph::Gen_Centroid_Decomposition< GT, SA >::collect_component_nodes(), and Aleph::Gen_Centroid_Decomposition< GT, SA >::init_storage().

◆ removed_

template<class GT , class SA = Dft_Show_Arc<GT>>

Array<char> Aleph::Gen_Centroid_Decomposition< GT, SA >::removed_

private

Definition at line 1034 of file Tree_Decomposition.H.

Referenced by Aleph::Gen_Centroid_Decomposition< GT, SA >::append_centroid_annotations(), Aleph::Gen_Centroid_Decomposition< GT, SA >::build_centroid_tree(), Aleph::Gen_Centroid_Decomposition< GT, SA >::choose_centroid(), Aleph::Gen_Centroid_Decomposition< GT, SA >::collect_component_nodes(), and Aleph::Gen_Centroid_Decomposition< GT, SA >::init_storage().

◆ topology_

template<class GT , class SA = Dft_Show_Arc<GT>>

Topology Aleph::Gen_Centroid_Decomposition< GT, SA >::topology_

private

Definition at line 1032 of file Tree_Decomposition.H.

Referenced by Aleph::Gen_Centroid_Decomposition< GT, SA >::append_centroid_annotations(), Aleph::Gen_Centroid_Decomposition< GT, SA >::build_centroid_tree(), Aleph::Gen_Centroid_Decomposition< GT, SA >::choose_centroid(), and Aleph::Gen_Centroid_Decomposition< GT, SA >::collect_component_nodes().

The documentation for this class was generated from the following file:

Tree_Decomposition.H

Public Types

Public Member Functions

Private Types

Private Member Functions

Private Attributes

Static Private Attributes

Detailed Description

Member Typedef Documentation

◆ Node

◆ Topology

Constructor & Destructor Documentation

◆ Gen_Centroid_Decomposition() [1/2]

◆ Gen_Centroid_Decomposition() [2/2]

Member Function Documentation

◆ append_centroid_annotations()

◆ build_centroid_tree()

◆ centroid_ancestors_of()

◆ centroid_ancestors_of_id()

◆ centroid_distances_of()

◆ centroid_distances_of_id()

◆ centroid_level_of()

◆ centroid_level_of_id()

◆ centroid_parent()

◆ centroid_parent_id()

◆ centroid_path_length_of()

◆ centroid_path_length_of_id()

◆ centroid_root()

◆ centroid_root_id()

◆ choose_centroid()

◆ collect_component_nodes()

◆ distance_to_centroid_id()

◆ ensure_not_empty()

◆ for_each_centroid_ancestor()

◆ for_each_centroid_ancestor_id()

◆ id_of()

◆ init_storage()

◆ is_centroid_ancestor_id()

◆ is_empty()

◆ max_centroid_level()

◆ node_of()

◆ root()

◆ root_id()

◆ size()

Member Data Documentation

◆ centroid_ancestors_

◆ centroid_distances_

◆ centroid_level_

◆ centroid_parent_

◆ centroid_root_

◆ local_parent_

◆ local_subtree_

◆ NONE

◆ removed_

◆ topology_