Hopcroft-Tarjan biconnectivity algorithm in Python
One DFS computes low-points and yields articulation points, bridges and blocks in linear time.
- File
hopcroft_tarjan_biconnectivity.py, 77 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/hopcroft-tarjan-biconnectivity/. The authors are listed in prov/B1ZMBY.jsonl.
def biconnectivity(
n: int, edges: list[tuple[int, int]]
) -> tuple[list[int], list[int], list[list[int]]]:
"""Find the articulation points, the bridges and the blocks of an undirected graph.
Precondition: the vertices are 0 .. n-1 and edges[i] = (u, v) is the edge with id i.
Parallel edges and loops are allowed, and the graph need not be connected.
Returns (aps, bridges, blocks): the sorted articulation points, the sorted ids of
the bridges, and the blocks as sorted lists of edge ids, in the order of output
(loops first, then the order in which the search closes the blocks).
Time O(n + m), extra space O(n + m). The depth-first search uses an explicit stack
of (vertex, id of the tree edge into it, next index) frames, not recursion.
"""
adj: list[list[tuple[int, int]]] = [[] for _ in range(n)]
blocks: list[list[int]] = []
for i, (u, v) in enumerate(edges):
if u == v:
blocks.append([i]) # @line L2
else:
adj[u].append((v, i))
adj[v].append((u, i))
d = [0] * n # @line L1
low = [0] * n
t = 0
estack: list[int] = []
is_ap = [False] * n
bridges: list[int] = []
for r in range(n): # @line L3
if d[r]:
continue
children = 0
t += 1 # @line L5: VISIT(r, nil) starts
d[r] = low[r] = t
frames = [(r, -1, 0)]
while frames:
u, p, k = frames[-1]
if k < len(adj[u]): # @line L6
frames[-1] = (u, p, k + 1)
v, e = adj[u][k]
if e == p: # the tree edge into u, by id
continue
if d[v] == 0: # @line L7
estack.append(e) # @line L8
if u == r:
children += 1
t += 1 # @line L5: VISIT(v, e) starts
d[v] = low[v] = t
frames.append((v, e, 0))
elif d[v] < d[u]: # @line L14
estack.append(e) # @line L15
low[u] = min(low[u], d[v])
continue
frames.pop() # VISIT(u, p) returns to its caller
if not frames:
break
w = frames[-1][0] # the parent of u; p is the tree edge {w, u}
low[w] = min(low[w], low[u]) # @line L9
if low[u] >= d[w]: # @line L10
block = [] # @line L11
while True:
x = estack.pop()
block.append(x)
if x == p:
break
blocks.append(sorted(block))
if w != r: # @line L12
is_ap[w] = True
if low[u] > d[w]: # @line L13
bridges.append(p)
if children >= 2: # @line L4
is_ap[r] = True
aps = [v for v in range(n) if is_ap[v]]
return aps, sorted(bridges), blocks
test_hopcroft_tarjan_biconnectivity.py 124 lines
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/hopcroft-tarjan-biconnectivity/. The authors are listed in prov/B1ZMBY.jsonl.
import random
from hopcroft_tarjan_biconnectivity import biconnectivity
def count_components(n: int, alive: list[bool], edges: list[tuple[int, int]]) -> int:
parent = list(range(n))
def find(x: int) -> int:
while parent[x] != x:
parent[x] = parent[parent[x]]
x = parent[x]
return x
for u, v in edges:
if alive[u] and alive[v]:
parent[find(u)] = find(v)
return len({find(v) for v in range(n) if alive[v]})
def oracle(n: int, edges: list[tuple[int, int]]):
"""Articulation points and bridges by removal; blocks by Menger on the subdivision."""
every = [True] * n
c = count_components(n, every, edges)
aps = []
for v in range(n):
alive = [x != v for x in range(n)]
if count_components(n, alive, edges) > c:
aps.append(v)
bridges = [
i
for i, (u, v) in enumerate(edges)
if u != v and count_components(n, every, edges[:i] + edges[i + 1 :]) > c
]
# Subdivide edge i by the vertex n + i. Two non-loop edges i, j lie on a common
# cycle iff n + i and n + j are joined after the removal of any one other vertex.
m = len(edges)
sub = []
for i, (u, v) in enumerate(edges):
if u != v:
sub += [(u, n + i), (n + i, v)]
big = n + m
real = [i for i in range(m) if edges[i][0] != edges[i][1]]
label = {i: i for i in range(m)}
def joined(a: int, b: int, cut: int) -> bool:
alive = [x != cut for x in range(big)]
parent = list(range(big))
def find(x: int) -> int:
while parent[x] != x:
x = parent[x]
return x
for x, y in sub:
if alive[x] and alive[y]:
parent[find(x)] = find(y)
return find(a) == find(b)
for a in real:
for b in real:
if a < b and all(
joined(n + a, n + b, x) for x in range(-1, big) if x not in (n + a, n + b)
):
la, lb = label[a], label[b]
for k in label:
if label[k] == lb:
label[k] = la
groups: dict[int, list[int]] = {}
for i in range(m):
groups.setdefault(label[i], []).append(i)
blocks = sorted(sorted(g) for g in groups.values())
return aps, bridges, blocks
def check(n: int, edges: list[tuple[int, int]]) -> None:
aps, bridges, blocks = biconnectivity(n, edges)
want_aps, want_bridges, want_blocks = oracle(n, edges)
assert aps == want_aps
assert bridges == want_bridges
assert sorted(blocks) == want_blocks
def test_example() -> None:
edges = [(0, 1), (0, 1), (1, 2), (2, 0), (2, 3), (3, 4), (4, 5), (5, 3), (5, 6), (6, 6)]
aps, bridges, blocks = biconnectivity(7, edges)
assert aps == [2, 3, 5]
assert bridges == [4, 8]
assert blocks == [[9], [8], [5, 6, 7], [4], [0, 1, 2, 3]]
check(7, edges)
def test_edges() -> None:
assert biconnectivity(0, []) == ([], [], [])
assert biconnectivity(1, []) == ([], [], [])
assert biconnectivity(1, [(0, 0), (0, 0)]) == ([], [], [[0], [1]])
assert biconnectivity(2, [(0, 1)]) == ([], [0], [[0]])
assert biconnectivity(2, [(0, 1), (1, 0)]) == ([], [], [[0, 1]])
assert biconnectivity(3, [(0, 1), (1, 2)]) == ([1], [0, 1], [[1], [0]])
star = [(0, i) for i in range(1, 5)]
assert biconnectivity(5, star)[0] == [0]
bowtie = [(0, 1), (1, 2), (2, 0), (0, 3), (3, 4), (4, 0)]
assert biconnectivity(5, bowtie)[0] == [0]
check(4, [(1, 2), (2, 3), (3, 1)])
def test_long_path() -> None:
n = 20000
edges = [(i, i + 1) for i in range(n - 1)]
aps, bridges, blocks = biconnectivity(n, edges)
assert aps == list(range(1, n - 1))
assert bridges == list(range(n - 1)) and len(blocks) == n - 1
def test_random() -> None:
rng = random.Random(1973)
for _ in range(600):
n = rng.randint(1, 7)
m = rng.randint(0, 10)
edges = [(rng.randrange(n), rng.randrange(n)) for _ in range(m)]
check(n, edges)
What the next level needs
- the tests did not run in this build
Read the full page about Hopcroft-Tarjan biconnectivity algorithm