Tree_Decomposition.H File Reference

Heavy-Light and Centroid decomposition on rooted trees represented as Aleph graphs. More...

#include <algorithm>
#include <concepts>
#include <cstddef>
#include <limits>
#include <type_traits>
#include <utility>
#include <ah-errors.H>
#include <ahFunction.H>
#include <tpl_array.H>
#include <tpl_dynListStack.H>
#include <tpl_dynMapOhash.H>
#include <tpl_dynMapTree.H>
#include <tpl_graph.H>
#include <tpl_segment_tree.H>

Include dependency graph for Tree_Decomposition.H:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Classes
struct	Aleph::tree_decomposition_detail::Id_Range
class	Aleph::tree_decomposition_detail::Rooted_Tree_Topology< GT, SA >
class	Aleph::Gen_Heavy_Light_Decomposition< GT, SA >
	Heavy-Light Decomposition over a rooted tree represented as an Aleph graph. More...
class	Aleph::Gen_HLD_Path_Query< GT, T, Op, SA >
	Segment-tree-powered path/subtree queries over an HLD layout. More...
class	Aleph::Gen_Centroid_Decomposition< GT, SA >
	Centroid decomposition over a rooted tree represented as an Aleph graph. More...

Namespaces
namespace	Aleph
	Main namespace for Aleph-w library functions.
namespace	Aleph::tree_decomposition_detail

Typedefs
template<class GT , class SA = Dft_Show_Arc<GT>>
using	Aleph::Heavy_Light_Decomposition = Gen_Heavy_Light_Decomposition< GT, SA >
	Convenience alias for heavy-light decomposition.
template<class GT , typename T = typename GT::Node::Node_Type, class Op = Aleph::plus<T>, class SA = Dft_Show_Arc<GT>>
using	Aleph::HLD_Path_Query = Gen_HLD_Path_Query< GT, T, Op, SA >
	Convenience alias for segment-tree-backed HLD queries.
template<class GT , class SA = Dft_Show_Arc<GT>>
using	Aleph::Centroid_Decomposition = Gen_Centroid_Decomposition< GT, SA >
	Convenience alias for centroid decomposition.

Detailed Description

Heavy-Light and Centroid decomposition on rooted trees represented as Aleph graphs.

This header provides two complementary tree decomposition engines:

1. Heavy-Light Decomposition (HLD)

   • Gen_Heavy_Light_Decomposition<GT, SA>
   • Gen_HLD_Path_Query<GT, T, Op, SA>

   HLD maps each tree node to a position in a base array. Any path query becomes a small number of contiguous segments (O(log n) segments), which can be aggregated with a range-query structure such as Gen_Segment_Tree.

2. Centroid Decomposition

   • Gen_Centroid_Decomposition<GT, SA>

   Centroid decomposition builds a centroid tree in O(n log n), exposing, for each node, its chain of centroid ancestors and the distance to each ancestor. This is ideal for dynamic nearest/farthest marked-node queries, distance-constrained updates, and other "niche but powerful" tree tricks.

Problem-oriented view

Use this header when your tree workload is one of these:

• Online path aggregates with node updates: many queries of the form query(path(u, v)) plus point updates. Typical examples: path risk score, path maintenance sum, path min/max.
• Online subtree aggregates with node updates: many queries of the form query(subtree(u)) plus point updates. Typical examples: total load/cost under a supervisor/rooted region.
• Distance to dynamic marked set (unweighted edge distance): repeatedly mark/activate nodes and query nearest/farthest/threshold distance from arbitrary nodes. Centroid chains are the natural primitive.

Which engine should you choose?

• Choose HLD when the central operation is an associative fold over tree paths/subtrees and you want a segment-tree style interface.
• Choose Centroid decomposition when the central operation is distance to a dynamic set of marked nodes.
• If you only need ancestor/LCA/distance queries, prefer LCA.H.
• If queries are fully offline and not monoidal, consider tpl_mo_on_trees.H.

Notes and limits

• Distances exposed by centroid annotations are measured in number of edges.
• Topology validation is strict and performed at construction time.
• For range updates on paths/subtrees, reuse HLD decomposition with a lazy segment tree policy.

Graph support

Both engines work on Aleph graph backends:

• List_Graph
• List_SGraph
• Array_Graph

and accept an optional arc filter SA to project a tree subgraph from a larger graph.

Validation guarantees

Construction validates that the filtered graph is a simple undirected tree:

• no self-loops
• no parallel edges
• exactly n-1 edges
• connected and acyclic

If validation fails, a domain error is raised with an explanatory message.

See also

tpl_segment_tree.H

LCA.H

Author

Leandro Rabindranath León

Definition in file Tree_Decomposition.H.