Heavy-Light Decomposition over a rooted tree represented as an Aleph graph. More...

#include <Tree_Decomposition.H>

Inheritance diagram for Aleph::Gen_Heavy_Light_Decomposition< GT, SA >:

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

Public Types
using	Node = typename GT::Node

using	Range = tree_decomposition_detail::Id_Range

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

	Gen_Heavy_Light_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	parent_id (const size_t id) const

Node *	parent_of (const Node *node) const

size_t	depth_of_id (const size_t id) const

size_t	depth_of (const Node *node) const

size_t	subtree_size_of_id (const size_t id) const

size_t	subtree_size_of (const Node *node) const

size_t	heavy_child_id (const size_t id) const

Node *	heavy_child (const Node *node) const

size_t	head_id (const size_t id) const

Node *	head_of (const Node *node) const

size_t	position_of_id (const size_t id) const

size_t	position_of (const Node *node) const

Range	subtree_range_id (const size_t id) const
	Base-array range of a full subtree (inclusive endpoints).

Range	subtree_range (const Node *node) const
	Base-array range of a full subtree (inclusive endpoints).

bool	is_ancestor_id (const size_t u, const size_t v) const
	True iff `u` is ancestor of `v` in the rooted tree.

bool	is_ancestor (const Node u, const Node v) const
	True iff `u` is ancestor of `v` in the rooted tree.

size_t	lca_id (size_t u, size_t v) const
	Lowest common ancestor in O(log n).

Node *	lca (const Node u, const Node v) const
	Lowest common ancestor in O(log n).

size_t	distance_id (const size_t u, const size_t v) const
	Distance (number of edges) between two node IDs.

size_t	distance (const Node u, const Node v) const
	Distance (number of edges) between two nodes.

template<class F >
void	for_each_path_segment_id (size_t u, size_t v, F &&visit) const
	Enumerate path segments from `u` to `v` in path order.

template<class F >
void	for_each_path_segment (const Node u, const Node v, F &&visit) const
	Enumerate path segments from `u` to `v` in path order.

template<class F >
void	for_each_path_segment_undirected_id (const size_t u, const size_t v, F &&visit) const
	Enumerate path segments ignoring direction.

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

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

void	build_decomposition ()

Private Attributes
Topology	topology_

Array< size_t >	parent_

Array< size_t >	depth_

Array< size_t >	subtree_size_

Array< size_t >	heavy_

Array< size_t >	head_

Array< size_t >	pos_

Array< size_t >	inv_pos_

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

Detailed Description

template<AlephGraph GT, ArcFilter< GT > SA = Dft_Show_Arc<GT>>
class Aleph::Gen_Heavy_Light_Decomposition< GT, SA >

Heavy-Light Decomposition over a rooted tree represented as an Aleph graph.

HLD decomposes each root-to-leaf path into heavy and light edges so that any path between two nodes can be split into O(log n) contiguous segments over a base array.

Build complexity: O(n) Path decomposition complexity: O(log n) segments

Template Parameters

GT	Graph type.
SA	Arc filter type.

Definition at line 394 of file Tree_Decomposition.H.

Member Typedef Documentation

◆ Node

template<AlephGraph GT, ArcFilter< GT > SA = Dft_Show_Arc<GT>>

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

Definition at line 397 of file Tree_Decomposition.H.

◆ Range

template<AlephGraph GT, ArcFilter< GT > SA = Dft_Show_Arc<GT>>

using Aleph::Gen_Heavy_Light_Decomposition< GT, SA >::Range = tree_decomposition_detail::Id_Range

Definition at line 398 of file Tree_Decomposition.H.

◆ Topology

template<AlephGraph GT, ArcFilter< GT > SA = Dft_Show_Arc<GT>>

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

private

Definition at line 401 of file Tree_Decomposition.H.

Constructor & Destructor Documentation

◆ Gen_Heavy_Light_Decomposition() [1/2]

template<AlephGraph GT, ArcFilter< GT > SA = Dft_Show_Arc<GT>>

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

inline

Construct using an explicit root node.

Parameters

[in]	g	Graph containing the rooted tree.
[in]	root	Root node pointer.
[in]	sa	Arc filter.

Definition at line 552 of file Tree_Decomposition.H.

◆ Gen_Heavy_Light_Decomposition() [2/2]

template<AlephGraph GT, ArcFilter< GT > SA = Dft_Show_Arc<GT>>

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

inline

Construct using the first graph node as root.

Parameters

[in]	g	Graph containing the rooted tree.
[in]	sa	Arc filter.

Definition at line 563 of file Tree_Decomposition.H.

Member Function Documentation

◆ build_decomposition()

template<AlephGraph GT, ArcFilter< GT > SA = Dft_Show_Arc<GT>>

void Aleph::Gen_Heavy_Light_Decomposition< GT, SA >::build_decomposition ( )

inlineprivate

Definition at line 419 of file Tree_Decomposition.H.

◆ depth_of()

template<AlephGraph GT, ArcFilter< GT > SA = Dft_Show_Arc<GT>>

size_t Aleph::Gen_Heavy_Light_Decomposition< GT, SA >::depth_of ( const Node * node ) const

inline

Definition at line 603 of file Tree_Decomposition.H.

◆ depth_of_id()

template<AlephGraph GT, ArcFilter< GT > SA = Dft_Show_Arc<GT>>

size_t Aleph::Gen_Heavy_Light_Decomposition< GT, SA >::depth_of_id ( const size_t id ) const

inline

Definition at line 597 of file Tree_Decomposition.H.

◆ distance()

template<AlephGraph GT, ArcFilter< GT > SA = Dft_Show_Arc<GT>>

size_t Aleph::Gen_Heavy_Light_Decomposition< GT, SA >::distance	(	const Node *	u,
		const Node *	v
	)		const

inline

Distance (number of edges) between two nodes.

Definition at line 712 of file Tree_Decomposition.H.

◆ distance_id()

template<AlephGraph GT, ArcFilter< GT > SA = Dft_Show_Arc<GT>>

size_t Aleph::Gen_Heavy_Light_Decomposition< GT, SA >::distance_id	(	const size_t	u,
		const size_t	v
	)		const

inline

Distance (number of edges) between two node IDs.

Definition at line 705 of file Tree_Decomposition.H.

◆ ensure_not_empty()

template<AlephGraph GT, ArcFilter< GT > SA = Dft_Show_Arc<GT>>

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

inlineprivate

Definition at line 414 of file Tree_Decomposition.H.

References ah_domain_error_if, Aleph::blossom_maximum_cardinality_matching(), and Aleph::Gen_Heavy_Light_Decomposition< GT, SA >::is_empty().

◆ for_each_path_segment()

template<AlephGraph GT, ArcFilter< GT > SA = Dft_Show_Arc<GT>>

template<class F >

void Aleph::Gen_Heavy_Light_Decomposition< GT, SA >::for_each_path_segment	(	const Node *	u,
		const Node *	v,
		F &&	visit
	)		const

inline

Enumerate path segments from u to v in path order.

Definition at line 762 of file Tree_Decomposition.H.

References Aleph::blossom_maximum_cardinality_matching().

◆ for_each_path_segment_id()

template<AlephGraph GT, ArcFilter< GT > SA = Dft_Show_Arc<GT>>

template<class F >

void Aleph::Gen_Heavy_Light_Decomposition< GT, SA >::for_each_path_segment_id	(	size_t	u,
		size_t	v,
		F &&	visit
	)		const

inline

Enumerate path segments from u to v in path order.

The callback receives (l, r, reversed) where [l, r] is a contiguous segment in the HLD base array, and:

reversed == true means the path traverses that segment as r..l
reversed == false means the path traverses that segment as l..r

This is useful for non-commutative path folds where segment direction matters.

Definition at line 728 of file Tree_Decomposition.H.

References Aleph::blossom_maximum_cardinality_matching().

◆ for_each_path_segment_undirected_id()

template<AlephGraph GT, ArcFilter< GT > SA = Dft_Show_Arc<GT>>

template<class F >

void Aleph::Gen_Heavy_Light_Decomposition< GT, SA >::for_each_path_segment_undirected_id	(	const size_t	u,
		const size_t	v,
		F &&	visit
	)		const

inline

Enumerate path segments ignoring direction.

Useful when the query operation is commutative.

Definition at line 772 of file Tree_Decomposition.H.

References Aleph::blossom_maximum_cardinality_matching(), l, and r.

◆ head_id()

template<AlephGraph GT, ArcFilter< GT > SA = Dft_Show_Arc<GT>>

size_t Aleph::Gen_Heavy_Light_Decomposition< GT, SA >::head_id ( const size_t id ) const

inline

Definition at line 631 of file Tree_Decomposition.H.

◆ head_of()

template<AlephGraph GT, ArcFilter< GT > SA = Dft_Show_Arc<GT>>

Node * Aleph::Gen_Heavy_Light_Decomposition< GT, SA >::head_of ( const Node * node ) const

inline

Definition at line 637 of file Tree_Decomposition.H.

◆ heavy_child()

template<AlephGraph GT, ArcFilter< GT > SA = Dft_Show_Arc<GT>>

Node * Aleph::Gen_Heavy_Light_Decomposition< GT, SA >::heavy_child ( const Node * node ) const

inline

Definition at line 625 of file Tree_Decomposition.H.

References Aleph::blossom_maximum_cardinality_matching().

◆ heavy_child_id()

template<AlephGraph GT, ArcFilter< GT > SA = Dft_Show_Arc<GT>>

size_t Aleph::Gen_Heavy_Light_Decomposition< GT, SA >::heavy_child_id ( const size_t id ) const

inline

Definition at line 619 of file Tree_Decomposition.H.

◆ id_of()

template<AlephGraph GT, ArcFilter< GT > SA = Dft_Show_Arc<GT>>

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

inline

Definition at line 580 of file Tree_Decomposition.H.

◆ is_ancestor()

template<AlephGraph GT, ArcFilter< GT > SA = Dft_Show_Arc<GT>>

bool Aleph::Gen_Heavy_Light_Decomposition< GT, SA >::is_ancestor	(	const Node *	u,
		const Node *	v
	)		const

inline

True iff u is ancestor of v in the rooted tree.

Definition at line 677 of file Tree_Decomposition.H.

◆ is_ancestor_id()

template<AlephGraph GT, ArcFilter< GT > SA = Dft_Show_Arc<GT>>

bool Aleph::Gen_Heavy_Light_Decomposition< GT, SA >::is_ancestor_id	(	const size_t	u,
		const size_t	v
	)		const

inline

True iff u is ancestor of v in the rooted tree.

Definition at line 669 of file Tree_Decomposition.H.

References Aleph::and, Aleph::blossom_maximum_cardinality_matching(), and r.

◆ is_empty()

template<AlephGraph GT, ArcFilter< GT > SA = Dft_Show_Arc<GT>>

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

inlinenoexcept

Definition at line 570 of file Tree_Decomposition.H.

Referenced by Aleph::Gen_Heavy_Light_Decomposition< GT, SA >::ensure_not_empty().

◆ lca()

template<AlephGraph GT, ArcFilter< GT > SA = Dft_Show_Arc<GT>>

Node * Aleph::Gen_Heavy_Light_Decomposition< GT, SA >::lca	(	const Node *	u,
		const Node *	v
	)		const

inline

Lowest common ancestor in O(log n).

Definition at line 699 of file Tree_Decomposition.H.

◆ lca_id()

template<AlephGraph GT, ArcFilter< GT > SA = Dft_Show_Arc<GT>>

size_t Aleph::Gen_Heavy_Light_Decomposition< GT, SA >::lca_id	(	size_t	u,
		size_t	v
	)		const

inline

Lowest common ancestor in O(log n).

Definition at line 683 of file Tree_Decomposition.H.

◆ node_of()

template<AlephGraph GT, ArcFilter< GT > SA = Dft_Show_Arc<GT>>

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

inline

Definition at line 575 of file Tree_Decomposition.H.

◆ parent_id()

template<AlephGraph GT, ArcFilter< GT > SA = Dft_Show_Arc<GT>>

size_t Aleph::Gen_Heavy_Light_Decomposition< GT, SA >::parent_id ( const size_t id ) const

inline

Definition at line 585 of file Tree_Decomposition.H.

◆ parent_of()

template<AlephGraph GT, ArcFilter< GT > SA = Dft_Show_Arc<GT>>

Node * Aleph::Gen_Heavy_Light_Decomposition< GT, SA >::parent_of ( const Node * node ) const

inline

Definition at line 591 of file Tree_Decomposition.H.

◆ position_of()

template<AlephGraph GT, ArcFilter< GT > SA = Dft_Show_Arc<GT>>

size_t Aleph::Gen_Heavy_Light_Decomposition< GT, SA >::position_of ( const Node * node ) const

inline

Definition at line 648 of file Tree_Decomposition.H.

◆ position_of_id()

template<AlephGraph GT, ArcFilter< GT > SA = Dft_Show_Arc<GT>>

size_t Aleph::Gen_Heavy_Light_Decomposition< GT, SA >::position_of_id ( const size_t id ) const

inline

Definition at line 642 of file Tree_Decomposition.H.

◆ root()

template<AlephGraph GT, ArcFilter< GT > SA = Dft_Show_Arc<GT>>

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

inlinenoexcept

Definition at line 572 of file Tree_Decomposition.H.

◆ root_id()

template<AlephGraph GT, ArcFilter< GT > SA = Dft_Show_Arc<GT>>

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

inlinenoexcept

Definition at line 573 of file Tree_Decomposition.H.

Referenced by Aleph::Gen_Heavy_Light_Decomposition< GT, SA >::build_decomposition().

◆ size()

template<AlephGraph GT, ArcFilter< GT > SA = Dft_Show_Arc<GT>>

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

inlinenoexcept

Definition at line 569 of file Tree_Decomposition.H.

Referenced by Aleph::Gen_Heavy_Light_Decomposition< GT, SA >::build_decomposition().

◆ subtree_range()

template<AlephGraph GT, ArcFilter< GT > SA = Dft_Show_Arc<GT>>

Range Aleph::Gen_Heavy_Light_Decomposition< GT, SA >::subtree_range ( const Node * node ) const

inline

Base-array range of a full subtree (inclusive endpoints).

Definition at line 663 of file Tree_Decomposition.H.

◆ subtree_range_id()

template<AlephGraph GT, ArcFilter< GT > SA = Dft_Show_Arc<GT>>

Range Aleph::Gen_Heavy_Light_Decomposition< GT, SA >::subtree_range_id ( const size_t id ) const

inline

Base-array range of a full subtree (inclusive endpoints).

Definition at line 654 of file Tree_Decomposition.H.

References l, and r.

◆ subtree_size_of()

template<AlephGraph GT, ArcFilter< GT > SA = Dft_Show_Arc<GT>>

size_t Aleph::Gen_Heavy_Light_Decomposition< GT, SA >::subtree_size_of ( const Node * node ) const

inline

Definition at line 614 of file Tree_Decomposition.H.

◆ subtree_size_of_id()

template<AlephGraph GT, ArcFilter< GT > SA = Dft_Show_Arc<GT>>

size_t Aleph::Gen_Heavy_Light_Decomposition< GT, SA >::subtree_size_of_id ( const size_t id ) const

inline

Definition at line 608 of file Tree_Decomposition.H.

Member Data Documentation

◆ depth_

template<AlephGraph GT, ArcFilter< GT > SA = Dft_Show_Arc<GT>>

Array<size_t> Aleph::Gen_Heavy_Light_Decomposition< GT, SA >::depth_

private

Definition at line 407 of file Tree_Decomposition.H.

Referenced by Aleph::Gen_Heavy_Light_Decomposition< GT, SA >::build_decomposition().

◆ head_

template<AlephGraph GT, ArcFilter< GT > SA = Dft_Show_Arc<GT>>

Array<size_t> Aleph::Gen_Heavy_Light_Decomposition< GT, SA >::head_

private

Definition at line 410 of file Tree_Decomposition.H.

Referenced by Aleph::Gen_Heavy_Light_Decomposition< GT, SA >::build_decomposition().

◆ heavy_

template<AlephGraph GT, ArcFilter< GT > SA = Dft_Show_Arc<GT>>

Array<size_t> Aleph::Gen_Heavy_Light_Decomposition< GT, SA >::heavy_

private

Definition at line 409 of file Tree_Decomposition.H.

Referenced by Aleph::Gen_Heavy_Light_Decomposition< GT, SA >::build_decomposition().

◆ inv_pos_

template<AlephGraph GT, ArcFilter< GT > SA = Dft_Show_Arc<GT>>

Array<size_t> Aleph::Gen_Heavy_Light_Decomposition< GT, SA >::inv_pos_

private

Definition at line 412 of file Tree_Decomposition.H.

Referenced by Aleph::Gen_Heavy_Light_Decomposition< GT, SA >::build_decomposition().

◆ NONE

template<AlephGraph GT, ArcFilter< GT > SA = Dft_Show_Arc<GT>>

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

staticconstexprprivate

Definition at line 402 of file Tree_Decomposition.H.

Referenced by Aleph::Gen_Heavy_Light_Decomposition< GT, SA >::build_decomposition().

◆ parent_

template<AlephGraph GT, ArcFilter< GT > SA = Dft_Show_Arc<GT>>

Array<size_t> Aleph::Gen_Heavy_Light_Decomposition< GT, SA >::parent_

private

Definition at line 406 of file Tree_Decomposition.H.

Referenced by Aleph::Gen_Heavy_Light_Decomposition< GT, SA >::build_decomposition().

◆ pos_

template<AlephGraph GT, ArcFilter< GT > SA = Dft_Show_Arc<GT>>

Array<size_t> Aleph::Gen_Heavy_Light_Decomposition< GT, SA >::pos_

private

Definition at line 411 of file Tree_Decomposition.H.

Referenced by Aleph::Gen_Heavy_Light_Decomposition< GT, SA >::build_decomposition().

◆ subtree_size_

template<AlephGraph GT, ArcFilter< GT > SA = Dft_Show_Arc<GT>>

Array<size_t> Aleph::Gen_Heavy_Light_Decomposition< GT, SA >::subtree_size_

private

Definition at line 408 of file Tree_Decomposition.H.

Referenced by Aleph::Gen_Heavy_Light_Decomposition< GT, SA >::build_decomposition().

◆ topology_

template<AlephGraph GT, ArcFilter< GT > SA = Dft_Show_Arc<GT>>

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

private

Definition at line 404 of file Tree_Decomposition.H.

Referenced by Aleph::Gen_Heavy_Light_Decomposition< GT, SA >::build_decomposition().

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

◆ Range

◆ Topology

Constructor & Destructor Documentation

◆ Gen_Heavy_Light_Decomposition() [1/2]

◆ Gen_Heavy_Light_Decomposition() [2/2]

Member Function Documentation

◆ build_decomposition()

◆ depth_of()

◆ depth_of_id()

◆ distance()

◆ distance_id()

◆ ensure_not_empty()

◆ for_each_path_segment()

◆ for_each_path_segment_id()

◆ for_each_path_segment_undirected_id()

◆ head_id()

◆ head_of()

◆ heavy_child()

◆ heavy_child_id()

◆ id_of()

◆ is_ancestor()

◆ is_ancestor_id()

◆ is_empty()

◆ lca()

◆ lca_id()

◆ node_of()

◆ parent_id()

◆ parent_of()

◆ position_of()

◆ position_of_id()

◆ root()

◆ root_id()

◆ size()

◆ subtree_range()

◆ subtree_range_id()

◆ subtree_size_of()

◆ subtree_size_of_id()

Member Data Documentation

◆ depth_

◆ head_

◆ heavy_

◆ inv_pos_

◆ NONE

◆ parent_

◆ pos_

◆ subtree_size_

◆ topology_