Aleph::Gen_Heavy_Light_Decomposition< GT, SA > Class Template Reference

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<class GT, class 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 392 of file Tree_Decomposition.H.

Member Typedef Documentation

Node

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

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

Definition at line 395 of file Tree_Decomposition.H.

Range

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

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

Definition at line 396 of file Tree_Decomposition.H.

Topology

template<class GT , class 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 399 of file Tree_Decomposition.H.

Constructor & Destructor Documentation

Gen_Heavy_Light_Decomposition() [1/2]

template<class GT , class 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 550 of file Tree_Decomposition.H.

Gen_Heavy_Light_Decomposition() [2/2]

template<class GT , class 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 561 of file Tree_Decomposition.H.

Member Function Documentation

build_decomposition()

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

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

inlineprivate

Definition at line 417 of file Tree_Decomposition.H.

References Aleph::tree_decomposition_detail::Rooted_Tree_Topology< GT, SA >::adjacency(), ah_domain_error_if, Aleph::and, Aleph::Array< T >::append(), Aleph::Array< T >::create(), Aleph::Gen_Heavy_Light_Decomposition< GT, SA >::depth_, Aleph::divide_and_conquer_partition_dp(), Aleph::Gen_Heavy_Light_Decomposition< GT, SA >::head_, Aleph::Gen_Heavy_Light_Decomposition< GT, SA >::heavy_, Aleph::Gen_Heavy_Light_Decomposition< GT, SA >::inv_pos_, Aleph::DynListStack< T >::is_empty(), Aleph::Gen_Heavy_Light_Decomposition< GT, SA >::NONE, Aleph::Gen_Heavy_Light_Decomposition< GT, SA >::parent_, Aleph::DynListStack< T >::pop(), Aleph::Gen_Heavy_Light_Decomposition< GT, SA >::pos_, Aleph::DynListStack< T >::push(), Aleph::Array< T >::reserve(), Aleph::tree_decomposition_detail::Rooted_Tree_Topology< GT, SA >::root_id(), Aleph::Gen_Heavy_Light_Decomposition< GT, SA >::root_id(), Aleph::Array< T >::size(), Aleph::Gen_Heavy_Light_Decomposition< GT, SA >::size(), Aleph::Gen_Heavy_Light_Decomposition< GT, SA >::subtree_size_, Aleph::DynListStack< T >::top(), and Aleph::Gen_Heavy_Light_Decomposition< GT, SA >::topology_.

depth_of()

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

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

inline

Definition at line 601 of file Tree_Decomposition.H.

depth_of_id()

template<class GT , class 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 595 of file Tree_Decomposition.H.

distance()

template<class GT , class 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 710 of file Tree_Decomposition.H.

distance_id()

template<class GT , class 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 703 of file Tree_Decomposition.H.

ensure_not_empty()

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

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

inlineprivate

Definition at line 412 of file Tree_Decomposition.H.

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

for_each_path_segment()

template<class GT , class 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 760 of file Tree_Decomposition.H.

References Aleph::divide_and_conquer_partition_dp().

for_each_path_segment_id()

template<class GT , class 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 726 of file Tree_Decomposition.H.

References Aleph::divide_and_conquer_partition_dp().

for_each_path_segment_undirected_id()

template<class GT , class 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 770 of file Tree_Decomposition.H.

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

head_id()

template<class GT , class 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 629 of file Tree_Decomposition.H.

head_of()

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

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

inline

Definition at line 635 of file Tree_Decomposition.H.

heavy_child()

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

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

inline

Definition at line 623 of file Tree_Decomposition.H.

References Aleph::divide_and_conquer_partition_dp().

heavy_child_id()

template<class GT , class 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 617 of file Tree_Decomposition.H.

id_of()

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

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

inline

Definition at line 578 of file Tree_Decomposition.H.

is_ancestor()

template<class GT , class 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 675 of file Tree_Decomposition.H.

is_ancestor_id()

template<class GT , class 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 667 of file Tree_Decomposition.H.

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

is_empty()

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

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

inlinenoexcept

Definition at line 568 of file Tree_Decomposition.H.

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

lca()

template<class GT , class 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 697 of file Tree_Decomposition.H.

lca_id()

template<class GT , class 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 681 of file Tree_Decomposition.H.

node_of()

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

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

inline

Definition at line 573 of file Tree_Decomposition.H.

parent_id()

template<class GT , class 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 583 of file Tree_Decomposition.H.

parent_of()

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

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

inline

Definition at line 589 of file Tree_Decomposition.H.

References Aleph::divide_and_conquer_partition_dp().

position_of()

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

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

inline

Definition at line 646 of file Tree_Decomposition.H.

position_of_id()

template<class GT , class 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 640 of file Tree_Decomposition.H.

root()

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

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

inlinenoexcept

Definition at line 570 of file Tree_Decomposition.H.

root_id()

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

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

inlinenoexcept

Definition at line 571 of file Tree_Decomposition.H.

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

size()

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

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

inlinenoexcept

Definition at line 567 of file Tree_Decomposition.H.

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

subtree_range()

template<class GT , class 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 661 of file Tree_Decomposition.H.

subtree_range_id()

template<class GT , class 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 652 of file Tree_Decomposition.H.

References l, and r.

subtree_size_of()

template<class GT , class 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 612 of file Tree_Decomposition.H.

subtree_size_of_id()

template<class GT , class 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 606 of file Tree_Decomposition.H.

Member Data Documentation

depth_

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

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

private

Definition at line 405 of file Tree_Decomposition.H.

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

head_

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

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

private

Definition at line 408 of file Tree_Decomposition.H.

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

heavy_

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

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

private

Definition at line 407 of file Tree_Decomposition.H.

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

inv_pos_

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

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

private

Definition at line 410 of file Tree_Decomposition.H.

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

NONE

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

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

staticconstexprprivate

Definition at line 400 of file Tree_Decomposition.H.

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

parent_

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

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

private

Definition at line 404 of file Tree_Decomposition.H.

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

pos_

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

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

private

Definition at line 409 of file Tree_Decomposition.H.

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

subtree_size_

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

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

private

Definition at line 406 of file Tree_Decomposition.H.

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

topology_

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

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

private

Definition at line 402 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