Itai-Rodeh girth algorithm in Python
Computes the girth of an undirected unweighted graph, and a shortest cycle, by one breadth-first search from every vertex in O(n(n + m)) time.
- File
itai_rodeh_girth_algorithm.py, 60 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/itai-rodeh-girth-algorithm/. The authors are listed in prov/SX075V.jsonl.
from collections import deque
def itai_rodeh_girth_algorithm(
n: int, edges: list[tuple[int, int]]
) -> tuple[list[int], list[int]] | None:
"""Return a shortest cycle of an undirected graph, or None if it is a forest.
The graph has the vertices 0 .. n-1 and the undirected edges edges[i] = (u, v),
numbered by i; self-loops, parallel edges and isolated vertices are allowed. The
result (vs, es) has len(vs) == len(es) == girth, and es[i] joins vs[i] to
vs[(i + 1) % girth]. One breadth-first search runs from every vertex.
Time O(n (n + m)), extra space O(n + m).
"""
inc: list[list[tuple[int, int]]] = [[] for _ in range(n)]
for e, (u, v) in enumerate(edges):
inc[u].append((e, v))
inc[v].append((e, u)) # a loop appears twice at its vertex
def search(r: int, record: bool) -> tuple[list[int], list[int], list[int]]:
nonlocal best, found
dist = [-1] * n # @line L3
pv = [-1] * n
pe = [-1] * n
dist[r] = 0
queue = deque([r])
while queue: # @line L4
u = queue.popleft() # @line L5
for e, v in inc[u]: # @line L6
if dist[v] < 0: # @line L7
dist[v] = dist[u] + 1
pv[v], pe[v] = u, e
queue.append(v)
elif record and e != pe[u] and dist[u] + dist[v] + 1 < best: # @line L8
best = dist[u] + dist[v] + 1 # @line L9
found = (r, e, u, v)
return dist, pv, pe
best = n + 1 # @line L1
found = (-1, -1, -1, -1)
for r in range(n): # @line L2
search(r, True)
if found[0] < 0: # @line L10
return None
r, e, a, b = found
dist, pv, pe = search(r, False) # @line L11
left_v, left_e, right_v, right_e = [a], [], [b], []
while a != b: # climb to the lowest common ancestor
if dist[a] >= dist[b]:
left_e.append(pe[a])
a = pv[a]
left_v.append(a)
else:
right_e.append(pe[b])
b = pv[b]
right_v.append(b)
return left_v[::-1] + right_v[:-1], left_e[::-1] + [e] + right_e # @line L12
test_itai_rodeh_girth_algorithm.py 101 lines
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/itai-rodeh-girth-algorithm/. The authors are listed in prov/SX075V.jsonl.
import random
from collections import deque
from itai_rodeh_girth_algorithm import itai_rodeh_girth_algorithm
def girth_oracle(n, edges):
"""Independent oracle: the shortest cycle through edge e = (u, v) has length
1 + dist(u, v) in the graph without e; a loop is a cycle of length 1."""
best = None
for f, (u, v) in enumerate(edges):
if u == v:
c = 1
else:
dist = {u: 0}
q = deque([u])
while q:
x = q.popleft()
for g, (a, b) in enumerate(edges):
if g == f or x not in (a, b):
continue
y = b if x == a else a
if y not in dist:
dist[y] = dist[x] + 1
q.append(y)
if v not in dist:
continue
c = dist[v] + 1
best = c if best is None or c < best else best
return best
def is_cycle(edges, res) -> bool:
vs, es = res
k = len(vs)
if k == 0 or len(es) != k or len(set(vs)) != k or len(set(es)) != k:
return False
for i in range(k):
a, b = vs[i], vs[(i + 1) % k]
if edges[es[i]] not in ((a, b), (b, a)):
return False
return True
EXAMPLE = [(0, 1), (1, 2), (2, 3), (3, 4), (4, 0), (4, 5), (5, 6), (6, 3)]
def test_example() -> None:
res = itai_rodeh_girth_algorithm(8, EXAMPLE)
assert res is not None and is_cycle(EXAMPLE, res)
assert len(res[0]) == 4 and sorted(res[0]) == [3, 4, 5, 6]
def test_small_cases() -> None:
assert itai_rodeh_girth_algorithm(0, []) is None
assert itai_rodeh_girth_algorithm(1, []) is None
assert itai_rodeh_girth_algorithm(1, [(0, 0)]) == ([0], [0])
assert itai_rodeh_girth_algorithm(2, [(0, 1), (1, 0)]) == ([0, 1], [1, 0])
assert itai_rodeh_girth_algorithm(3, [(0, 1), (1, 2), (2, 0)]) is not None
# trees and forests, with isolated vertices
assert itai_rodeh_girth_algorithm(6, [(0, 1), (1, 2), (1, 3), (4, 5)]) is None
# a loop away from a triangle wins
edges = [(0, 1), (1, 2), (2, 0), (3, 3)]
assert itai_rodeh_girth_algorithm(4, edges) == ([3], [3])
def test_petersen() -> None:
outer = [(i, (i + 1) % 5) for i in range(5)]
spokes = [(i, i + 5) for i in range(5)]
inner = [(5 + i, 5 + (i + 2) % 5) for i in range(5)]
edges = outer + spokes + inner
res = itai_rodeh_girth_algorithm(10, edges)
assert res is not None and is_cycle(edges, res) and len(res[0]) == 5
def test_long_cycle() -> None:
n = 400
edges = [(i, (i + 1) % n) for i in range(n)]
res = itai_rodeh_girth_algorithm(n, edges)
assert res is not None and len(res[0]) == n and is_cycle(edges, res)
def test_random_against_oracle() -> None:
rng = random.Random(1978)
for trial in range(700):
n = rng.randint(1, 8)
m = rng.randint(0, 11)
edges = []
for _ in range(m):
u = rng.randrange(n)
v = u if rng.random() < 0.05 else rng.randrange(n)
edges.append((u, v))
want = girth_oracle(n, edges)
got = itai_rodeh_girth_algorithm(n, edges)
if want is None:
assert got is None
else:
assert got is not None and is_cycle(edges, got) and len(got[0]) == want
What the next level needs
- the tests did not run in this build