Reingold-Tilford rooted tree layout in Python
Lays out a rooted tree by placing subtrees side by side at minimum separation and centering each parent above its children.
- File
reingold_tilford_layout.py, 83 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/reingold-tilford-layout/. The authors are listed in prov/NB9NJR.jsonl.
"""Reingold-Tilford layout of an ordered rooted tree.
The tree has the vertices 0..n-1 and is given by children lists, in
order from left to right. It is rooted and not weighted. Each vertex gets
y = its depth and an x coordinate (a Fraction), so that two neighbours on
the same level are at least `sep` apart and each parent is centred over
its first and last child. Contours are kept as lists, deepest level first,
with a shift, so each merge costs the height of the lower of the two parts.
"""
from fractions import Fraction
def layout(children, root=0, sep=1):
n = len(children)
order = []
stack = [root]
while stack: # preorder without recursion
v = stack.pop()
order.append(v)
stack.extend(reversed(children[v]))
rel = [Fraction(0)] * n # x of v minus x of its parent
left = [None] * n # left contour: [list, shift]; level i is list[-1-i] + shift
right = [None] * n
for v in reversed(order): # @line L1
kids = children[v]
if not kids: # @line L2
left[v] = [[Fraction(0)], Fraction(0)]
right[v] = [[Fraction(0)], Fraction(0)]
continue
c1 = kids[0]
fl, fr = left[c1], right[c1] # @line L3
off = {c1: Fraction(0)}
for c in kids[1:]: # @line L4
cl, cr = left[c], right[c]
hf, hc = len(fr[0]), len(cl[0])
d = None
for i in range(min(hf, hc)): # @line L5
gap = fr[0][hf - 1 - i] + fr[1] - (cl[0][hc - 1 - i] + cl[1])
if d is None or gap > d:
d = gap
d += sep # @line L6
off[c] = d
# @line L7: merge the left contours, then the right contours
if hc > len(fl[0]):
hl = len(fl[0])
for i in range(hl):
cl[0][hc - 1 - i] = fl[0][hl - 1 - i] + fl[1] - (cl[1] + d)
fl = [cl[0], cl[1] + d]
if hf > hc:
for i in range(hc):
fr[0][hf - 1 - i] = cr[0][hc - 1 - i] + cr[1] + d - fr[1]
else:
fr = [cr[0], cr[1] + d]
m = off[kids[-1]] / 2 # @line L8
for c in kids: # @line L9
rel[c] = off[c] - m
fl[1] -= m # @line L10
fl[0].append(-fl[1])
fr[1] -= m
fr[0].append(-fr[1])
left[v], right[v] = fl, fr
x = [Fraction(0)] * n
y = [0] * n
for v in order: # @line L11
for c in children[v]:
x[c] = x[v] + rel[c]
y[c] = y[v] + 1 # @line L12
return x, y # @line L13
def children_from_parents(parent):
"""Children lists in increasing order, and the root, from a parent array."""
ch = [[] for _ in parent]
root = 0
for v, p in enumerate(parent):
if p < 0:
root = v
else:
ch[p].append(v)
return ch, root
test_reingold_tilford_layout.py 99 lines
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/reingold-tilford-layout/. The authors are listed in prov/NB9NJR.jsonl.
import random
import unittest
from fractions import Fraction
from reingold_tilford_layout import children_from_parents, layout
def oracle(children, root, sep):
"""Slow layout by the same rule: whole subtrees, not contours, O(n^2)."""
order = []
stack = [root]
while stack:
v = stack.pop()
order.append(v)
stack.extend(reversed(children[v]))
pos = {} # v -> dict of (u -> (x relative to v, depth below v))
for v in reversed(order):
placed = {}
offs = []
for c in children[v]:
sub = pos.pop(c)
if not placed:
d = Fraction(0)
else:
d = None
for u, (xu, du) in placed.items():
for w, (xw, dw) in sub.items():
if du == dw and (d is None or xu - xw + sep > d):
d = xu - xw + sep
offs.append(d)
for w, (xw, dw) in sub.items():
placed[w] = (xw + d, dw)
m = (offs[0] + offs[-1]) / 2 if offs else Fraction(0)
cur = {v: (Fraction(0), 0)}
for u, (xu, du) in placed.items():
cur[u] = (xu - m, du + 1)
pos[v] = cur
res = pos[root]
n = len(children)
return [res[v][0] for v in range(n)], [res[v][1] for v in range(n)]
def random_parents(n, rng):
return [-1] + [rng.randrange(v) for v in range(1, n)]
class TestReingoldTilford(unittest.TestCase):
def test_page_example(self):
ch, r = children_from_parents([-1, 0, 0, 1, 1, 2, 4, 4])
x, y = layout(ch, r, sep=2)
h = Fraction(1, 2)
self.assertEqual(x, [0, -3 * h, 3 * h, -5 * h, -h, 3 * h, -3 * h, h])
self.assertEqual(y, [0, 1, 1, 2, 2, 2, 3, 3])
def test_single_vertex(self):
self.assertEqual(layout([[]]), ([0], [0]))
def test_path(self):
n = 100000
ch = [[v + 1] for v in range(n - 1)] + [[]]
x, y = layout(ch)
self.assertTrue(all(v == 0 for v in x))
self.assertEqual(y, list(range(n)))
def test_star(self):
n = 7
ch = [list(range(1, n))] + [[] for _ in range(n - 1)]
x, y = layout(ch, sep=1)
self.assertEqual(x, [0] + [Fraction(k) - Fraction(n - 2, 2) for k in range(n - 1)])
self.assertEqual(y, [0] + [1] * (n - 1))
def test_random_against_oracle(self):
rng = random.Random(20260412)
for _ in range(600):
n = rng.randint(1, 30)
ch, r = children_from_parents(random_parents(n, rng))
sep = rng.choice([1, 2, 3])
got = layout(ch, r, sep)
self.assertEqual(got, oracle(ch, r, sep))
x, y = got
# neighbours on a level keep the order and the separation
levels = {}
stack = [r]
while stack:
v = stack.pop()
levels.setdefault(y[v], []).append(v)
stack.extend(reversed(ch[v]))
for row in levels.values():
for a, b in zip(row, row[1:]):
self.assertGreaterEqual(x[b] - x[a], sep)
for v in range(n):
if ch[v]:
self.assertEqual(x[v], (x[ch[v][0]] + x[ch[v][-1]]) / 2)
if __name__ == "__main__":
unittest.main()
What the next level needs
- the tests did not run in this build
Read the full page about Reingold-Tilford rooted tree layout