Kuhn's algorithm in Python
Finds maximum bipartite matching by repeated DFS for augmenting paths, in O(VE) time.
- File
kuhn_algorithm.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/kuhn-algorithm/. The authors are listed in prov/H8SH4G.jsonl.
def kuhn_algorithm(n_left: int, n_right: int, adj: list[list[int]]) -> list[int | None]:
"""Maximum matching of a bipartite graph, unweighted, by Kuhn's algorithm.
The left side is 0 .. n_left-1 and the right side is 0 .. n_right-1;
adj[u] lists the right neighbours of the left vertex u (repeats are allowed).
Returns mate_left: mate_left[u] is the right mate of u, or None if u is exposed.
The number of edges of the matching is the count of entries that are not None.
One depth-first search per left vertex: O(n_left * (n + m)) time, O(n + m) space.
The search uses an explicit stack, so deep paths do not hit the recursion limit.
"""
if len(adj) != n_left:
raise ValueError("adj must have one list per left vertex")
mate_left: list[int | None] = [None] * n_left # @line L1
mate_right: list[int | None] = [None] * n_right
for u in range(n_left): # @line L2
visited = [False] * n_right # @line L3
_try(u, adj, mate_left, mate_right, visited) # @line L4
return mate_left # @line L5
def _try(
root: int,
adj: list[list[int]],
mate_left: list[int | None],
mate_right: list[int | None],
visited: list[bool],
) -> bool:
"""TRY(root) without recursion. A frame is [x, next index into adj[x], v that x waits on]."""
stack: list[list[int]] = [[root, 0, -1]]
while stack:
frame = stack[-1]
x, i = frame[0], frame[1]
if i == len(adj[x]): # @line L12: every neighbour failed, TRY(x) returns false
stack.pop()
continue
v = adj[x][i] # @line L6
frame[1] = i + 1
if visited[v]: # @line L7
continue
visited[v] = True # @line L8
w = mate_right[v]
if w is not None: # @line L9: call TRY(mate_right[v])
frame[2] = v
stack.append([w, 0, -1])
continue
# v is exposed: the path root .. x v is augmenting. Flip it along the stack.
for j in range(len(stack) - 1, -1, -1): # @line L10
y = stack[j][0]
target = v if j == len(stack) - 1 else stack[j][2]
mate_right[target] = y
mate_left[y] = target
return True # @line L11
return False
test_kuhn_algorithm.py 86 lines
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/kuhn-algorithm/. The authors are listed in prov/H8SH4G.jsonl.
import random
from kuhn_algorithm import kuhn_algorithm
def check_matching(n_left, n_right, adj, mate_left):
"""The result is a matching that uses only edges of the graph. Returns its size."""
used = set()
for u, v in enumerate(mate_left):
if v is None:
continue
assert v in adj[u]
assert v not in used
used.add(v)
return len(used)
def brute_nu(n_left, adj):
"""Oracle: the largest matching, by trying every choice for each left vertex."""
best = 0
def rec(u, used, size):
nonlocal best
if size + (n_left - u) <= best:
return
if u == n_left:
best = size
return
for v in set(adj[u]):
if v not in used:
rec(u + 1, used | {v}, size + 1)
rec(u + 1, used, size)
rec(0, frozenset(), 0)
return best
def test_example():
# left 1, 2, 3, 4 are 0..3; right a, b, c, d are 0..3
adj = [[0, 1], [0, 2], [0], [2, 3]]
mate = kuhn_algorithm(4, 4, adj)
assert mate == [1, 2, 0, 3]
def test_no_perfect_matching():
# left 2 and 3 both see only a: at most 3 of 4 left vertices can be matched
adj = [[0, 1], [0], [0], [2, 3]]
mate = kuhn_algorithm(4, 4, adj)
assert check_matching(4, 4, adj, mate) == 3
def test_empty_and_edgeless():
assert kuhn_algorithm(0, 0, []) == []
assert kuhn_algorithm(0, 5, []) == []
assert kuhn_algorithm(3, 0, [[], [], []]) == [None, None, None]
assert kuhn_algorithm(2, 2, [[], []]) == [None, None]
def test_complete_and_parallel_edges():
adj = [[0, 1, 2]] * 3
assert check_matching(3, 3, adj, kuhn_algorithm(3, 3, adj)) == 3
adj = [[0, 0, 0], [0, 0]]
assert check_matching(2, 1, adj, kuhn_algorithm(2, 1, adj)) == 1
def test_long_augmenting_path_no_recursion_limit():
# left j sees right j and j + 1 and takes j; the last left vertex sees only right 0,
# so its augmenting path runs through all n earlier left vertices
n = 3000
adj = [[j, j + 1] for j in range(n)] + [[0]]
mate = kuhn_algorithm(n + 1, n + 1, adj)
assert check_matching(n + 1, n + 1, adj, mate) == n + 1
assert mate[n] == 0 and mate[0] == 1 and mate[n - 1] == n
def test_random_against_brute_force():
rng = random.Random(4127)
for _ in range(600):
nl, nr = rng.randint(0, 7), rng.randint(0, 7)
p = rng.random()
adj = [[v for v in range(nr) if rng.random() < p] for _ in range(nl)]
mate = kuhn_algorithm(nl, nr, adj)
assert check_matching(nl, nr, adj, mate) == brute_nu(nl, adj)
What the next level needs
- the tests did not run in this build