Lengauer-Tarjan algorithm in Python
Compute immediate dominators in near-linear time using DFS and path compression.
- File
lengauer_tarjan_algorithm.py, 97 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/lengauer-tarjan-algorithm/. The authors are listed in prov/206HCM.jsonl.
def _run(n: int, edges: list[tuple[int, int]], root: int) -> tuple[list[int], list[int]]:
if n < 1 or not 0 <= root < n:
raise ValueError("a flow graph needs n >= 1 vertices and a root in range")
succ: list[list[int]] = [[] for _ in range(n)]
pred: list[list[int]] = [[] for _ in range(n)]
for a, b in edges:
if not (0 <= a < n and 0 <= b < n):
raise ValueError("edge endpoint out of range")
succ[a].append(b)
pred[b].append(a)
# L1: iterative depth-first search; vertices are renamed by preorder number.
dfn = [-1] * n # @line L1
vertex = [root]
parent = [-1]
dfn[root] = 0
stack = [(root, 0)]
while stack:
v, i = stack[-1]
if i < len(succ[v]):
stack[-1] = (v, i + 1)
w = succ[v][i]
if dfn[w] == -1:
dfn[w] = len(vertex)
vertex.append(w)
parent.append(dfn[v])
stack.append((w, 0))
else:
stack.pop()
k = len(vertex)
preds = [[dfn[u] for u in pred[vertex[i]] if dfn[u] != -1] for i in range(k)]
semi = list(range(k)) # @line L2
label = list(range(k))
ancestor = [-1] * k
idom = [0] * k
bucket: list[list[int]] = [[] for _ in range(k)]
def evaluate(v: int) -> int:
if ancestor[v] == -1: # @line L12
return v
path = [] # @line L13
x = v
while ancestor[ancestor[x]] != -1: # @line L14
path.append(x)
x = ancestor[x]
for x in reversed(path): # @line L15
a = ancestor[x]
if semi[label[a]] < semi[label[x]]:
label[x] = label[a]
ancestor[x] = ancestor[a]
return label[v]
for w in range(k - 1, 0, -1): # @line L3
for v in preds[w]: # @line L4
u = evaluate(v) # @line L5
if semi[u] < semi[w]:
semi[w] = semi[u]
bucket[semi[w]].append(w) # @line L6
p = parent[w]
ancestor[w] = p
for v in bucket[p]: # @line L7
u = evaluate(v) # @line L8
idom[v] = u if semi[u] < semi[v] else p
bucket[p] = [] # @line L9
for w in range(1, k): # @line L10
if idom[w] != semi[w]: # @line L11
idom[w] = idom[idom[w]]
idom_out = [-1] * n
semi_out = [-1] * n
for w in range(1, k):
idom_out[vertex[w]] = vertex[idom[w]]
semi_out[vertex[w]] = vertex[semi[w]]
return idom_out, semi_out
def lengauer_tarjan(n: int, edges: list[tuple[int, int]], root: int = 0) -> list[int]:
"""Immediate dominators of a flow graph, by the simple Lengauer-Tarjan algorithm.
The graph is directed and unweighted, with vertices 0 .. n-1 (n >= 1) and
edges (a, b) meaning a -> b; self-loops and parallel edges are allowed.
Returns idom with idom[root] = -1 and idom[v] = -1 for every vertex that
root cannot reach. Time O(m log n), no recursion.
"""
return _run(n, edges, root)[0]
def semidominators(n: int, edges: list[tuple[int, int]], root: int = 0) -> list[int]:
"""Semidominators, as vertex labels, for the depth-first search that visits
successors in the order of the edge list; -1 for the root and unreachable
vertices."""
return _run(n, edges, root)[1]
test_lengauer_tarjan_algorithm.py 103 lines
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/lengauer-tarjan-algorithm/. The authors are listed in prov/206HCM.jsonl.
import random
import pytest
from lengauer_tarjan_algorithm import lengauer_tarjan, semidominators
EDGES = [(0, 1), (1, 2), (2, 3), (2, 4), (3, 4), (3, 7), (4, 5), (5, 6), (6, 3), (7, 8), (8, 6)]
def reach(n: int, succ: list[list[int]], root: int, banned: int) -> set[int]:
if banned == root:
return set()
seen = {root}
stack = [root]
while stack:
v = stack.pop()
for w in succ[v]:
if w != banned and w not in seen:
seen.add(w)
stack.append(w)
return seen
def brute_idom(n: int, edges: list[tuple[int, int]], root: int) -> list[int]:
succ: list[list[int]] = [[] for _ in range(n)]
for a, b in edges:
succ[a].append(b)
full = reach(n, succ, root, -1)
dom = {v: {v} for v in full}
for d in full:
r = reach(n, succ, root, d)
for v in full:
if v not in r:
dom[v].add(d)
out = [-1] * n
for v in full:
if v != root:
strict = dom[v] - {v}
out[v] = max(strict, key=lambda x: len(dom[x]))
return out
def test_page_example() -> None:
assert lengauer_tarjan(9, EDGES, 0) == [-1, 0, 1, 2, 2, 4, 2, 3, 7]
assert semidominators(9, EDGES, 0) == [-1, 0, 1, 2, 2, 4, 3, 3, 7]
def test_single_vertex() -> None:
assert lengauer_tarjan(1, [], 0) == [-1]
assert lengauer_tarjan(1, [(0, 0)], 0) == [-1]
def test_star_and_diamond() -> None:
n = 8
edges = [(0, v) for v in range(1, n)] + [(3, 4), (4, 5), (7, 1)]
assert lengauer_tarjan(n, edges, 0) == [-1] + [0] * (n - 1)
assert lengauer_tarjan(4, [(0, 1), (0, 2), (1, 3), (2, 3)], 0) == [-1, 0, 0, 0]
def test_unreachable_and_other_root() -> None:
edges = [(0, 1), (1, 2), (3, 2), (2, 0)]
assert lengauer_tarjan(4, edges, 0) == [-1, 0, 1, -1]
assert lengauer_tarjan(4, edges, 3) == [2, 0, 3, -1]
def test_long_paths() -> None:
n = 100_000
path = [(i, i + 1) for i in range(n - 1)]
assert lengauer_tarjan(n, path, 0) == [-1] + list(range(n - 1))
# back edges to the root and bypass edges around every vertex
idom = lengauer_tarjan(n, path + [(i, 0) for i in range(n)], 0)
assert idom == [-1] + list(range(n - 1))
idom = lengauer_tarjan(n, path + [(i, i + 2) for i in range(n - 2)], 0)
assert idom == [-1] + [0] * (n - 1)
# edges from the far end back to every vertex: EVAL climbs and compresses
# long forest paths, and the answer is still the path itself
idom = lengauer_tarjan(n, path + [(n - 1, i) for i in range(1, n - 1)], 0)
assert idom == [-1] + list(range(n - 1))
# the root also enters the far end of a long cycle: idom of the far end is 0
idom = lengauer_tarjan(n, path + [(0, n - 1), (n - 1, 1)], 0)
assert idom == [-1, 0] + list(range(1, n - 2)) + [0]
def test_bad_input() -> None:
with pytest.raises(ValueError):
lengauer_tarjan(0, [], 0)
with pytest.raises(ValueError):
lengauer_tarjan(2, [(0, 3)], 0)
with pytest.raises(ValueError):
lengauer_tarjan(2, [], 2)
def test_random_against_brute_force() -> None:
rng = random.Random(29)
for _ in range(800):
n = rng.randint(1, 12)
m = rng.randint(0, 3 * n)
edges = [(rng.randrange(n), rng.randrange(n)) for _ in range(m)]
root = rng.randrange(n)
assert lengauer_tarjan(n, edges, root) == brute_idom(n, edges, root)
What the next level needs
- the tests did not run in this build