Tree center by leaf peeling in Python
Repeatedly delete all leaves; the last one or two remaining nodes are the center.
- File
tree_center_leaf_peeling.py, 36 lines- Level
- I0 not checked yet
- Toolchain
- Python 3.14, pytest 9
- Test framework
- pytest
- Run the tests
python3 -m pytest
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/tree-center-leaf-peeling/. The authors are listed in prov/R9M66X.jsonl.
def tree_center(n: int, edges: list[tuple[int, int]]) -> tuple[list[int], int]:
"""Return (centre, rounds) of a free, unweighted tree on the vertices 0 .. n-1.
The centre is the sorted list of the one or two vertices of smallest
eccentricity. rounds is the number of peeling rounds; the radius is rounds
when the centre has one vertex and rounds + 1 when it has two (for n >= 2).
Precondition: n >= 1 and edges are the n - 1 edges of a tree.
Time and extra space Theta(n); no recursion.
"""
if n <= 2: # @line L1
return list(range(n)), 0
adj: list[list[int]] = [[] for _ in range(n)]
for u, v in edges:
adj[u].append(v)
adj[v].append(u)
deg = [len(a) for a in adj] # @line L2
leaves = [v for v in range(n) if deg[v] == 1] # @line L3
left = n
rounds = 0
while left > 2: # @line L4
left -= len(leaves) # @line L5
rounds += 1
nxt: list[int] = [] # @line L6
for u in leaves: # @line L7
deg[u] = 0 # @line L8
for v in adj[u]: # @line L9
if deg[v] > 0:
deg[v] -= 1 # @line L10
if deg[v] == 1: # @line L11
nxt.append(v)
leaves = nxt # @line L12
return sorted(leaves), rounds # @line L13
test_tree_center_leaf_peeling.py 72 lines
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/tree-center-leaf-peeling/. The authors are listed in prov/R9M66X.jsonl.
import random
from collections import deque
from tree_center_leaf_peeling import tree_center
def eccentricities(n: int, edges: list[tuple[int, int]]) -> list[int]:
adj: list[list[int]] = [[] for _ in range(n)]
for u, v in edges:
adj[u].append(v)
adj[v].append(u)
out = []
for s in range(n):
dist = [-1] * n
dist[s] = 0
q = deque([s])
while q:
u = q.popleft()
for v in adj[u]:
if dist[v] < 0:
dist[v] = dist[u] + 1
q.append(v)
out.append(max(dist))
return out
def check(n: int, edges: list[tuple[int, int]]) -> None:
ecc = eccentricities(n, edges)
rad = min(ecc)
centre, rounds = tree_center(n, edges)
assert centre == [v for v in range(n) if ecc[v] == rad]
if n >= 2:
assert rad == (rounds if len(centre) == 1 else rounds + 1)
diameter = max(ecc)
assert diameter == 2 * rounds + len(centre) - 1
def test_example() -> None:
edges = [(0, 1), (0, 2), (1, 3), (1, 4), (2, 5), (4, 6), (4, 7)]
assert tree_center(8, edges) == ([0, 1], 2)
def test_small() -> None:
assert tree_center(1, []) == ([0], 0)
assert tree_center(2, [(0, 1)]) == ([0, 1], 0)
assert tree_center(3, [(0, 1), (1, 2)]) == ([1], 1)
def test_star() -> None:
n = 40
assert tree_center(n, [(0, i) for i in range(1, n)]) == ([0], 1)
assert tree_center(n, [(n - 1, i) for i in range(n - 1)]) == ([n - 1], 1)
def test_path_long() -> None:
n = 100_000
edges = [(i, i + 1) for i in range(n - 1)]
assert tree_center(n, edges) == ([n // 2 - 1, n // 2], n // 2 - 1)
assert tree_center(n + 1, edges + [(n - 1, n)]) == ([n // 2], n // 2)
def test_random_against_brute_force() -> None:
rng = random.Random(5150)
for _ in range(700):
n = rng.randint(1, 30)
perm = list(range(n))
rng.shuffle(perm)
edges = [(perm[i], perm[rng.randrange(i)]) for i in range(1, n)]
check(n, edges)
What the next level needs
- the tests did not run in this build