centroid_decomposition_example.cc File Reference

Story-driven demo of Centroid Decomposition dynamic nearest-center queries. More...

#include <Tree_Decomposition.H>
#include <tpl_graph.H>
#include <algorithm>
#include <array>
#include <cassert>
#include <format>
#include <iostream>
#include <limits>

Include dependency graph for centroid_decomposition_example.cc:

Go to the source code of this file.

Functions
int	main ()
	Demonstrates centroid-decomposition-based dynamic nearest-center queries on a fixed tree.

Detailed Description

Story-driven demo of Centroid Decomposition dynamic nearest-center queries.

Scenario: "Emergency Response Network"

Villages form a tree road network. We repeatedly:

• activate villages with emergency teams
• ask for the distance from a village to the nearest active team.

Centroid decomposition answers each operation in O(log n).

All per-node arrays are indexed by centroid/HLD integer IDs obtained via cd.id_of(node), not by insertion order, so the example is correct for any graph backend and insertion sequence.

Definition in file centroid_decomposition_example.cc.

Function Documentation

main()

int main

(

)

Demonstrates centroid-decomposition-based dynamic nearest-center queries on a fixed tree.

Builds a small tree of labeled "villages", constructs a Centroid_Decomposition and a Heavy_Light_Decomposition (used as an oracle for exact distances), and exercises:

• activation of centers (propagating distances to centroid ancestors),
• centroid-based nearest-center queries,
• brute-force verification of results via the HLD oracle.

The program prints diagnostic information (centroid root and ancestor chain), activates sample villages, compares centroid-query results against the brute-force oracle with assertions, and reports success when all checks pass.

Returns

int 0 on successful completion.

Definition at line 76 of file centroid_decomposition_example.cc.

References Aleph::Gen_Centroid_Decomposition< GT, SA >::centroid_root_id(), Aleph::Array< T >::create(), Aleph::divide_and_conquer_partition_dp(), Aleph::Gen_Centroid_Decomposition< GT, SA >::for_each_centroid_ancestor_id(), Aleph::Gen_Centroid_Decomposition< GT, SA >::id_of(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_arc(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_node(), k, and Aleph::Gen_Centroid_Decomposition< GT, SA >::size().