Stoer-Wagner algorithm in Python
Deterministic global min cut via repeated maximum-adjacency orderings and merging.
- File
stoer_wagner.py, 56 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/stoer-wagner/. The authors are listed in prov/M60CT8.jsonl.
def stoer_wagner(n: int, edges: list[tuple[int, int, float]]) -> tuple[float, set[int]]:
"""Global minimum cut of an undirected graph by the Stoer-Wagner algorithm.
Vertices are 0 .. n-1 with n >= 2, and edges (u, v, w) are undirected with
weight w >= 0, an integer or a real number. Parallel edges add up and
self-loops are ignored. Returns (value, S), where S is a nonempty proper
subset of the vertices whose cut has the least total weight. This is the
adjacency-matrix version, O(n^3) time and O(n^2) space.
"""
if n < 2:
raise ValueError("need at least two vertices")
w = [[0] * n for _ in range(n)]
for u, v, c in edges:
if c < 0:
raise ValueError("weights must be nonnegative")
if u != v:
w[u][v] += c
w[v][u] += c
group = [{v} for v in range(n)] # @line L1
alive = list(range(n))
best, best_set = None, set()
while len(alive) > 1: # @line L2
s, t, cut = minimum_cut_phase(w, alive) # @line L3
if best is None or cut < best: # @line L4
best, best_set = cut, set(group[t])
group[s] |= group[t] # @line L5
for v in alive:
w[s][v] += w[t][v]
w[v][s] = w[s][v]
w[s][s] = 0
alive.remove(t)
return best, best_set # @line L6
def minimum_cut_phase(w: list[list[float]], alive: list[int]) -> tuple[int, int, float]:
"""One maximum adjacency ordering of the alive vertices.
Returns (s, t, cut): the last two vertices of the ordering and the weight
of the edges between t and all other alive vertices, which is a minimum
s-t cut of the current graph.
"""
start = alive[0] # @line L7
key = {v: w[start][v] for v in alive if v != start}
order = [start]
last_key = 0
while key: # @line L8
z = max(key, key=lambda v: key[v]) # @line L9
last_key = key.pop(z)
order.append(z)
for v in key: # @line L10
key[v] += w[z][v]
return order[-2], order[-1], last_key # @line L11
test_stoer_wagner.py 78 lines
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/stoer-wagner/. The authors are listed in prov/M60CT8.jsonl.
import itertools
import random
from fractions import Fraction
import pytest
from stoer_wagner import stoer_wagner
# a, b, c, d, e, f = 0 .. 5: triangles abc and def with weight 2, joined by cd and be
EXAMPLE = [(0, 1, 2), (0, 2, 2), (1, 2, 2), (3, 4, 2), (3, 5, 2), (4, 5, 2), (2, 3, 1), (1, 4, 1)]
def cut_value(edges, side):
return sum(c for u, v, c in edges if (u in side) != (v in side))
def brute(n, edges):
"""Independent oracle: the least cut over all nonempty proper subsets holding vertex 0."""
best = None
for r in range(n - 1):
for extra in itertools.combinations(range(1, n), r):
c = cut_value(edges, {0, *extra})
best = c if best is None else min(best, c)
return best
def check(n, edges, value, side):
assert 0 < len(side) < n
assert cut_value(edges, side) == value
def test_example() -> None:
value, side = stoer_wagner(6, EXAMPLE)
assert value == 2
assert side in ({0, 1, 2}, {3, 4, 5})
check(6, EXAMPLE, value, side)
def test_two_vertices_and_parallel_edges() -> None:
assert stoer_wagner(2, [(0, 1, 3), (1, 0, 4)]) == (7, {1})
assert stoer_wagner(2, []) == (0, {1})
def test_disconnected_zero_weight_and_loops() -> None:
value, side = stoer_wagner(4, [(0, 1, 5), (2, 3, 5), (1, 2, 0), (0, 0, 9)])
assert value == 0
check(4, [(0, 1, 5), (2, 3, 5), (1, 2, 0)], value, side)
def test_cycle_and_real_weights() -> None:
cycle = [(i, (i + 1) % 6, 1) for i in range(6)]
assert stoer_wagner(6, cycle)[0] == 2
edges = [(0, 1, Fraction(1, 2)), (1, 2, Fraction(1, 3)), (2, 0, Fraction(1, 7)), (2, 3, Fraction(2, 5))]
value, side = stoer_wagner(4, edges)
assert value == brute(4, edges) == Fraction(2, 5)
check(4, edges, value, side)
def test_errors() -> None:
with pytest.raises(ValueError):
stoer_wagner(1, [])
with pytest.raises(ValueError):
stoer_wagner(2, [(0, 1, -1)])
def test_random_against_brute_force() -> None:
rng = random.Random(31337)
for _ in range(800):
n = rng.randint(2, 8)
m = rng.randint(0, 20)
edges = [(rng.randrange(n), rng.randrange(n), rng.choice([0, 1, 1, 2, 3, 7]))
for _ in range(m)]
value, side = stoer_wagner(n, edges)
assert value == brute(n, edges)
check(n, edges, value, side)
What the next level needs
- the tests did not run in this build