Skip to content

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 ​

SyntaxDescription
centroidDecomposition(adj: usize[][])Decompose the tree adj into a centroid tree

Methods ​

MethodSignatureReturnsDescription
parentOf(v: usize)usize?Centroid-tree parent of v; absent for the global centroid root
depth(v: usize)usizeDepth of v in the centroid tree (root depth 0)

Complexity ​

OperationTime Complexity
constructionO(n), iterative per-component subtree sizing and centroid search
parentOf, depthO(1)
memoryO(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));  // 2

deep 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));  // 2

single 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));  // 0

namespace 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