centroidDecomposition
centroidDecomposition(adj: usize[][]): Centroid builds the centroid decomposition over the undirected tree described by the adjacency list adj, where adj[v] holds the neighbors of vertex v. The returned Centroid is an owned handle of tyrus:algorithm; every vertex of the input tree becomes a node of the centroid tree, and removing a centroid splits each component into child components of depth at most half its size. It exposes parentOf(v), which returns the centroid-tree parent of v as usize? (the global centroid root has none), and depth(v), the depth of v in the centroid tree (root depth 0).
Construction
| Syntax | Description |
|---|---|
centroidDecomposition(adj: usize[][]) | Decompose the tree adj into a centroid tree |
Methods
| Method | Signature | Returns | Description |
|---|---|---|---|
parentOf | (v: usize) | usize? | Centroid-tree parent of v; absent for the global centroid root |
depth | (v: usize) | usize | Depth of v in the centroid tree (root depth 0) |
Complexity
| Operation | Time Complexity |
|---|---|
| construction | O(n), iterative per-component subtree sizing and centroid search |
parentOf, depth | O(1) |
| memory | O(n) |
Examples
balanced tree
tyrus
import { centroidDecomposition } from "tyrus:algorithm";
const adj: usize[][] = [[1, 2], [0, 3, 4], [0, 5, 6], [1], [1], [2], [2]];
const ct = centroidDecomposition(adj);
print(ct.parentOf(0) ?? 0); // 0 (no parent, global centroid)
print(ct.depth(0)); // 0
print(ct.parentOf(3) ?? 0); // 1
print(ct.depth(3)); // 2
print(ct.parentOf(5) ?? 0); // 2
print(ct.depth(5)); // 2deep path
tyrus
import { centroidDecomposition } from "tyrus:algorithm";
const path: usize[][] = [[1], [0, 2], [1, 3], [2, 4], [3, 5], [4]];
const ct = centroidDecomposition(path);
print(ct.parentOf(2) ?? 0); // 0 (no parent, global centroid)
print(ct.depth(2)); // 0
print(ct.parentOf(0) ?? 0); // 1
print(ct.depth(0)); // 2single vertex
tyrus
import { centroidDecomposition } from "tyrus:algorithm";
const single: usize[][] = [[]];
const ct = centroidDecomposition(single);
print(ct.parentOf(0) ?? 0); // 0 (no parent)
print(ct.depth(0)); // 0namespace import
tyrus
import * as alg from "tyrus:algorithm";
const ct = alg.centroidDecomposition([[1], [0, 2], [1]]);
print(ct.parentOf(1) ?? 0); // 0 (no parent)
print(ct.depth(0)); // 1