Karger's algorithm in Python
Randomly contract edges until two vertices remain; repeat to find a min cut with high probability.
- File
karger_min_cut.py, 59 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/karger-min-cut/. The authors are listed in prov/981JCR.jsonl.
import random
def _find(parent: list[int], x: int) -> int:
"""Root of x in the union-find forest, with path halving."""
while parent[x] != x:
parent[x] = parent[parent[x]]
x = parent[x]
return x
def contract(n: int, edges: list[tuple[int, int]], rng: random.Random) -> tuple[set[int], int]:
"""One run of random contraction on an undirected multigraph.
Vertices are 0 .. n-1 with n >= 2; edges is a list of pairs, where a
repeated pair is a parallel edge and a pair (v, v) is a self-loop that is
ignored. Returns (S, k): S is the side of the final cut that holds vertex 0,
and k is the number of edges with one end in S and one end outside it.
Time O(m alpha(n)) after an O(m) shuffle.
"""
parent = list(range(n)) # @line L6
comps = n
order = list(edges) # @line L7
rng.shuffle(order)
for u, v in order: # @line L8
if comps <= 2:
break
ru, rv = _find(parent, u), _find(parent, v)
if ru != rv: # @line L9
parent[ru] = rv
comps -= 1
root = _find(parent, 0) # @line L10
side = {x for x in range(n) if _find(parent, x) == root}
k = sum(1 for u, v in edges if (u in side) != (v in side)) # @line L11
return side, k # @line L12
def karger_min_cut(n: int, edges: list[tuple[int, int]], trials: int,
rng: random.Random | None = None) -> tuple[int, set[int]]:
"""Karger's algorithm: the best cut found by `trials` runs of contract.
The graph is undirected and unweighted (parallel edges count separately).
Returns (k, S) where S holds vertex 0 and k is the number of edges that
cross S. The value k is always a real cut value, so k >= the minimum cut;
it equals the minimum with probability at least 1 - (1 - 2/(n(n-1)))^trials.
Requires n >= 2 and trials >= 1. Time O(trials * m alpha(n)).
"""
if n < 2 or trials < 1:
raise ValueError("need n >= 2 and trials >= 1")
rng = rng or random.Random()
best, best_side = -1, set() # @line L1
for _ in range(trials): # @line L2
side, k = contract(n, edges, rng) # @line L3
if best < 0 or k < best: # @line L4
best, best_side = k, side
return best, best_side # @line L5
test_karger_min_cut.py 73 lines
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/karger-min-cut/. The authors are listed in prov/981JCR.jsonl.
import itertools
import math
import random
from karger_min_cut import contract, karger_min_cut
# two triangles with doubled edges, joined by c-d and b-e (a..f = 0..5)
EXAMPLE = [(0, 1), (0, 1), (0, 2), (0, 2), (1, 2), (1, 2),
(3, 4), (3, 4), (3, 5), (3, 5), (4, 5), (4, 5),
(2, 3), (1, 4)]
def brute(n, edges):
"""Independent oracle: the minimum over all 2^(n-1) - 1 cuts that hold vertex 0."""
best = None
for r in range(0, n - 1):
for rest in itertools.combinations(range(1, n), r):
s = {0, *rest}
k = sum(1 for u, v in edges if (u in s) != (v in s))
best = k if best is None else min(best, k)
return best
def cut_of(edges, s):
return sum(1 for u, v in edges if (u in s) != (v in s))
def test_example() -> None:
k, s = karger_min_cut(6, EXAMPLE, 200, random.Random(1))
assert k == 2 and s == {0, 1, 2}
def test_one_run_is_always_a_cut() -> None:
rng = random.Random(7)
for _ in range(200):
s, k = contract(6, EXAMPLE, rng)
assert 0 in s and 0 < len(s) < 6
assert k == cut_of(EXAMPLE, s) and k >= 2
def test_success_rate_meets_the_bound() -> None:
rng = random.Random(11)
runs = 3000
hits = sum(1 for _ in range(runs) if contract(6, EXAMPLE, rng)[1] == 2)
assert hits / runs >= 2 / (6 * 5)
def test_disconnected_and_two_vertices() -> None:
k, s = karger_min_cut(4, [(0, 1), (2, 3)], 1, random.Random(3))
assert k == 0 and s == {0, 1}
assert karger_min_cut(3, [], 1, random.Random(3))[0] == 0
assert karger_min_cut(2, [(0, 1), (0, 1), (0, 1)], 1, random.Random(3)) == (3, {0})
assert karger_min_cut(2, [(0, 0), (1, 1)], 1, random.Random(3)) == (0, {0})
def test_self_loops_are_ignored() -> None:
edges = [(0, 0), (0, 1), (1, 2), (2, 2), (2, 0), (2, 3)]
assert karger_min_cut(4, edges, 50, random.Random(5))[0] == 1
def test_random_against_brute_force() -> None:
rng = random.Random(2024)
for _ in range(500):
n = rng.randint(2, 7)
m = rng.randint(0, 14)
edges = [(rng.randrange(n), rng.randrange(n)) for _ in range(m)]
trials = math.ceil(n * (n - 1) / 2 * math.log(1e6))
k, s = karger_min_cut(n, edges, trials, rng)
assert k == cut_of(edges, s)
assert k == brute(n, edges)
What the next level needs
- the tests did not run in this build