Karp's minimum mean cycle algorithm in Python
Solves the minimum mean cycle problem in O(nm) time with a dynamic program over walk lengths.
- File
karp_minimum_mean_cycle.py, 57 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/karp-minimum-mean-cycle/. The authors are listed in prov/CDP661.jsonl.
from fractions import Fraction
def karp_minimum_mean_cycle(
n: int, arcs: list[tuple[int, int, int | Fraction]]
) -> tuple[Fraction, list[int]] | None:
"""Return (the minimum cycle mean, a cycle with that mean), or None if acyclic.
The directed graph has the vertices 0 .. n-1 and the arcs arcs[i] = (u, v, w), from
u to v with weight w (an int or a Fraction, of any sign); parallel arcs and
self-loops are allowed. The cycle is the list of its arc numbers in order.
D[k][v] is the least weight of a walk with exactly k arcs that ends at v and starts
anywhere. Time O(n (n + m)), extra space O(n^2).
"""
INF = None
dist: list[list[int | Fraction | None]] = [[0] * n] # @line L1
par: list[list[int]] = [[-1] * n]
for k in range(1, n + 1): # @line L2
cur: list[int | Fraction | None] = [INF] * n # @line L3
pk = [-1] * n
prev = dist[k - 1]
for a, (u, v, w) in enumerate(arcs): # @line L4
if prev[u] is not None:
d = prev[u] + w
if cur[v] is None or d < cur[v]: # @line L5
cur[v] = d
pk[v] = a
dist.append(cur)
par.append(pk)
best: Fraction | None = None # @line L6
best_v = -1
for v in range(n): # @line L7
dn = dist[n][v]
if dn is None:
continue
mu = max( # @line L8
Fraction(dn - dist[k][v], n - k) for k in range(n) if dist[k][v] is not None
)
if best is None or mu < best: # @line L9
best, best_v = mu, v
if best is None: # @line L10
return None
# L11: walk back from (n, best_v) and cut out the first repeated vertex
seen: dict[int, int] = {} # @line L11
walk_arcs: list[int] = []
v, k = best_v, n
while v not in seen:
seen[v] = len(walk_arcs)
a = par[k][v]
walk_arcs.append(a)
v, k = arcs[a][0], k - 1
cycle = walk_arcs[seen[v] :] # arcs in reverse order, from the repeat back
cycle.reverse()
return best, cycle # @line L12
test_karp_minimum_mean_cycle.py 83 lines
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/karp-minimum-mean-cycle/. The authors are listed in prov/CDP661.jsonl.
import itertools
import random
from fractions import Fraction
from karp_minimum_mean_cycle import karp_minimum_mean_cycle
def brute_min_mean(n, arcs):
"""Independent oracle: minimum of weight / length over all simple cycles."""
cheapest = {}
for u, v, w in arcs:
if (u, v) not in cheapest or w < cheapest[(u, v)]:
cheapest[(u, v)] = w
best = None
for k in range(1, n + 1):
for vs in itertools.combinations(range(n), k):
for rest in itertools.permutations(vs[1:]):
c = (vs[0],) + rest
pairs = [(c[i], c[(i + 1) % k]) for i in range(k)]
if all(p in cheapest for p in pairs):
mean = Fraction(sum(cheapest[p] for p in pairs), k)
best = mean if best is None or mean < best else best
return best
def check_cycle(arcs, cycle, mean) -> bool:
if not cycle:
return False
for i, a in enumerate(cycle):
if arcs[a][1] != arcs[cycle[(i + 1) % len(cycle)]][0]:
return False
heads = [arcs[a][1] for a in cycle]
if len(set(heads)) != len(heads):
return False
return Fraction(sum(arcs[a][2] for a in cycle), len(cycle)) == mean
EXAMPLE = [(0, 1, 2), (1, 0, 4), (1, 2, 1), (2, 3, 1), (3, 1, 4), (3, 0, 0)]
def test_example() -> None:
mean, cycle = karp_minimum_mean_cycle(4, EXAMPLE)
assert mean == Fraction(1)
assert check_cycle(EXAMPLE, cycle, mean)
assert cycle == [2, 3, 5, 0]
def test_small_cases() -> None:
assert karp_minimum_mean_cycle(0, []) is None
assert karp_minimum_mean_cycle(1, []) is None
assert karp_minimum_mean_cycle(1, [(0, 0, -3)]) == (Fraction(-3), [0])
assert karp_minimum_mean_cycle(3, [(0, 1, 5), (1, 2, -9)]) is None
# parallel arcs: the cheaper one is used
got = karp_minimum_mean_cycle(2, [(0, 1, 3), (0, 1, 1), (1, 0, 1)])
assert got is not None and got[0] == 1 and sorted(got[1]) == [1, 2]
# isolated vertices and a loop away from a 2-cycle
arcs = [(0, 1, 1), (1, 0, 1), (3, 3, 2)]
got = karp_minimum_mean_cycle(5, arcs)
assert got is not None and got[0] == 1 and sorted(got[1]) == [0, 1]
def test_fractions() -> None:
arcs = [(0, 1, Fraction(1, 3)), (1, 0, Fraction(1, 6))]
mean, cycle = karp_minimum_mean_cycle(2, arcs)
assert mean == Fraction(1, 4)
def test_random_against_brute_force() -> None:
rng = random.Random(1978)
for _ in range(700):
n = rng.randint(1, 6)
m = rng.randint(0, 12)
arcs = [(rng.randrange(n), rng.randrange(n), rng.randint(-5, 9)) for _ in range(m)]
want = brute_min_mean(n, arcs)
got = karp_minimum_mean_cycle(n, arcs)
if want is None:
assert got is None
else:
assert got is not None and got[0] == want
assert check_cycle(arcs, got[1], want)
What the next level needs
- the tests did not run in this build
Read the full page about Karp's minimum mean cycle algorithm