Online bridge finding in Python
Algorithm that maintains the bridges of a graph while edges are added, using union-find and a spanning forest with path compression.
- File
online_bridge_finding.py, 124 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/online-bridge-finding/. The authors are listed in prov/6AA8GQ.jsonl.
"""Online bridge finding: the bridges of a graph under edge insertions.
The 2-edge-connected components are kept in a union-find. Contracting them
turns each connected component into a tree (the bridge tree), stored by parent
pointers between component representatives. A second union-find keeps the
connected components. An edge between two trees links them, after rerooting
the smaller one; an edge inside one tree closes a cycle, and every bridge on
the tree path between its ends stops being a bridge. Insertions only;
deterministic; O(m log n) total time for m insertions, up to an alpha factor.
"""
class OnlineBridges:
def __init__(self, n: int) -> None:
self.n = n
self.par = [-1] * n # bridge-tree parent (any vertex of the parent 2ECC)
self.ecc = list(range(n)) # union-find of 2-edge-connected components
self.ecc_size = [1] * n
self.cc = list(range(n)) # union-find of connected components
self.cc_size = [1] * n
self.bridges = 0
self._mark = [0] * n
self._stamp = 0
def find_2ecc(self, v: int) -> int:
root = v
while self.ecc[root] != root:
root = self.ecc[root]
while self.ecc[v] != root:
self.ecc[v], v = root, self.ecc[v]
return root
def find_cc(self, v: int) -> int:
v = self.find_2ecc(v)
root = v
while self.cc[root] != root:
root = self.cc[root]
while self.cc[v] != root:
self.cc[v], v = root, self.cc[v]
return root
def _parent(self, v: int) -> int:
p = self.par[v]
return -1 if p == -1 else self.find_2ecc(p)
def _reroot(self, v: int) -> None:
"""Make the 2ECC v the root of its bridge tree."""
old = self.find_cc(v)
size = self.cc_size[old]
root = v
child = -1
while v != -1:
p = self._parent(v) # @line L9
self.par[v] = child
self.cc[v] = root
child = v
v = p
self.cc[old] = root
self.cc[root] = root
self.cc_size[root] = size
def _merge_path(self, a: int, b: int) -> None:
"""a and b are 2ECCs in one tree; merge the tree path between them."""
self._stamp += 1
path_a: list[int] = []
path_b: list[int] = []
lca = -1
while lca == -1: # @line L7
if a != -1:
if self._mark[a] == self._stamp:
lca = a
break
self._mark[a] = self._stamp
path_a.append(a)
a = self._parent(a)
if b != -1:
if self._mark[b] == self._stamp:
lca = b
break
self._mark[b] = self._stamp
path_b.append(b)
b = self._parent(b)
up = self.par[lca] # the bridge above the merged component stays
rep = lca
for path in (path_a, path_b):
for v in path:
if v == lca:
break
if self.ecc_size[v] > self.ecc_size[rep]:
v, rep = rep, v
self.ecc[v] = rep # @line L8
self.ecc_size[rep] += self.ecc_size[v]
self.bridges -= 1
self.par[rep] = up
def add_edge(self, a: int, b: int) -> None:
a, b = self.find_2ecc(a), self.find_2ecc(b) # @line L1
if a == b:
return
ca, cb = self.find_cc(a), self.find_cc(b) # @line L2
if ca != cb:
self.bridges += 1 # @line L3
if self.cc_size[ca] > self.cc_size[cb]:
a, b, ca, cb = b, a, cb, ca # @line L4
self._reroot(a) # @line L5
self.par[a] = b
self.cc[a] = b
self.cc_size[cb] += self.cc_size[a]
else:
self._merge_path(a, b) # @line L6
def two_edge_connected(self, u: int, v: int) -> bool:
return self.find_2ecc(u) == self.find_2ecc(v)
def connected(self, u: int, v: int) -> bool:
return self.find_cc(u) == self.find_cc(v)
def is_bridge(self, u: int, v: int) -> bool:
"""For an inserted edge {u, v}: is it currently a bridge?"""
a, b = self.find_2ecc(u), self.find_2ecc(v)
return a != b
test_online_bridge_finding.py 96 lines
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/online-bridge-finding/. The authors are listed in prov/6AA8GQ.jsonl.
import random
from online_bridge_finding import OnlineBridges
def _static(n: int, edges: list[tuple[int, int]]) -> tuple[int, list[int], list[int]]:
"""Bridges by an iterative low-link DFS; returns (count, 2ECC labels, CC labels)."""
adj: list[list[tuple[int, int]]] = [[] for _ in range(n)]
for i, (u, v) in enumerate(edges):
adj[u].append((v, i))
adj[v].append((u, i))
tin = [-1] * n
low = [0] * n
is_bridge = [False] * len(edges)
timer = 0
for s in range(n):
if tin[s] != -1:
continue
tin[s] = low[s] = timer
timer += 1
stack = [(s, -1, 0)]
while stack:
v, pe, i = stack.pop()
if i < len(adj[v]):
stack.append((v, pe, i + 1))
w, e = adj[v][i]
if e == pe:
continue
if tin[w] == -1:
tin[w] = low[w] = timer
timer += 1
stack.append((w, e, 0))
else:
low[v] = min(low[v], tin[w])
elif pe != -1:
u = edges[pe][0] if edges[pe][1] == v else edges[pe][1]
low[u] = min(low[u], low[v])
if low[v] > tin[u]:
is_bridge[pe] = True
def label(skip_bridges: bool) -> list[int]:
lab = [-1] * n
for s in range(n):
if lab[s] == -1:
lab[s] = s
st = [s]
while st:
x = st.pop()
for y, e in adj[x]:
if lab[y] == -1 and not (skip_bridges and is_bridge[e]):
lab[y] = s
st.append(y)
return lab
return sum(is_bridge), label(True), label(False)
def test_example() -> None:
g = OnlineBridges(7)
counts = []
for u, v in [(0, 1), (1, 2), (2, 3), (3, 4), (1, 5), (5, 6), (4, 2), (6, 0), (3, 3), (0, 1)]:
g.add_edge(u, v)
counts.append(g.bridges)
assert counts == [1, 2, 3, 4, 5, 6, 4, 1, 1, 1]
assert g.is_bridge(2, 1) and not g.is_bridge(0, 6)
def test_random_against_static() -> None:
rng = random.Random(99)
for _ in range(500):
n = rng.randint(1, 9)
g = OnlineBridges(n)
edges: list[tuple[int, int]] = []
for _ in range(rng.randint(0, 14)):
u, v = rng.randrange(n), rng.randrange(n)
g.add_edge(u, v)
edges.append((u, v))
cnt, ecc, cc = _static(n, edges)
assert g.bridges == cnt
for a in range(n):
for b in range(n):
assert g.two_edge_connected(a, b) == (ecc[a] == ecc[b])
assert g.connected(a, b) == (cc[a] == cc[b])
def test_long_path_then_cycle() -> None:
n = 20000
g = OnlineBridges(n)
for i in range(n - 1):
g.add_edge(i, i + 1)
assert g.bridges == n - 1
g.add_edge(0, n - 1)
assert g.bridges == 0
What the next level needs
- the tests did not run in this build