Path cover by bipartite matching in Python
Minimum path cover of a DAG equals the vertex count minus a maximum matching in the split bipartite graph.
- File
path_cover_by_bipartite_matching.py, 70 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/path-cover-by-bipartite-matching/. The authors are listed in prov/775KP1.jsonl.
def path_cover_by_bipartite_matching(n: int, arcs: list[tuple[int, int]]) -> list[list[int]]:
"""Return a minimum set of vertex-disjoint paths that covers every vertex of a DAG.
Precondition: the directed graph with vertices 0 .. n-1 and arcs (u, v) is acyclic;
parallel arcs are allowed. Raises ValueError if it has a cycle (a self-loop
included). Each path is a list of vertices in arc order; the paths are sorted by
their first vertex. The number of paths is n minus a maximum matching of the split
graph, found by Kuhn's augmenting paths in O(n m) time and O(n + m) extra space.
"""
_check_acyclic(n, arcs)
adj: list[list[int]] = [[] for _ in range(n)] # @line L1
for u, v in arcs:
adj[u].append(v)
match_left: list[int | None] = [None] * n # @line L2
match_right: list[int | None] = [None] * n
for root in range(n): # @line L3
visited = [False] * n # @line L4
ptr = [0] * n
stack = [root] # @line L5
via: list[int] = []
while stack: # @line L6
u = stack[-1]
if ptr[u] == len(adj[u]): # @line L7
stack.pop()
if via:
via.pop()
continue
v = adj[u][ptr[u]] # @line L8
ptr[u] += 1
if visited[v]:
continue
visited[v] = True
via.append(v)
if match_right[v] is None: # @line L9
for x, y in zip(stack, via): # @line L10
match_left[x] = y
match_right[y] = x
break
stack.append(match_right[v]) # @line L11
paths: list[list[int]] = []
for s in range(n): # @line L12
if match_right[s] is None:
path = [s] # @line L13
while match_left[path[-1]] is not None:
path.append(match_left[path[-1]])
paths.append(path)
return paths # @line L14
def _check_acyclic(n: int, arcs: list[tuple[int, int]]) -> None:
indeg = [0] * n
out: list[list[int]] = [[] for _ in range(n)]
for u, v in arcs:
out[u].append(v)
indeg[v] += 1
queue = [v for v in range(n) if indeg[v] == 0]
seen = 0
while queue:
u = queue.pop()
seen += 1
for v in out[u]:
indeg[v] -= 1
if indeg[v] == 0:
queue.append(v)
if seen != n:
raise ValueError("the graph has a directed cycle")
test_path_cover_by_bipartite_matching.py 79 lines
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/path-cover-by-bipartite-matching/. The authors are listed in prov/775KP1.jsonl.
import random
import pytest
from path_cover_by_bipartite_matching import path_cover_by_bipartite_matching
def is_cover(n, arcs, paths) -> bool:
arcset = set(arcs)
seen = [v for p in paths for v in p]
if sorted(seen) != list(range(n)):
return False
return all((p[i], p[i + 1]) in arcset for p in paths for i in range(len(p) - 1))
def brute_min_cover(n, arcs) -> int:
"""Independent oracle: n minus the largest arc set with in- and out-degree at most 1."""
pairs = sorted(set(arcs))
best = 0
for mask in range(1 << len(pairs)):
outs, ins, size, ok = set(), set(), 0, True
for i, (u, v) in enumerate(pairs):
if mask >> i & 1:
if u in outs or v in ins:
ok = False
break
outs.add(u)
ins.add(v)
size += 1
if ok:
best = max(best, size)
return n - best
EXAMPLE = [(0, 1), (0, 2), (1, 3), (2, 3), (3, 4), (2, 5), (5, 6), (1, 5)]
def test_example() -> None:
paths = path_cover_by_bipartite_matching(7, EXAMPLE)
assert paths == [[0, 1, 5, 6], [2, 3, 4]]
def test_edge_cases() -> None:
assert path_cover_by_bipartite_matching(0, []) == []
assert path_cover_by_bipartite_matching(3, []) == [[0], [1], [2]]
assert path_cover_by_bipartite_matching(3, [(0, 1), (1, 2)]) == [[0, 1, 2]]
# a star: one path through the centre and the rest alone
assert len(path_cover_by_bipartite_matching(4, [(0, 1), (0, 2), (0, 3)])) == 3
# parallel arcs and an isolated vertex
assert path_cover_by_bipartite_matching(3, [(0, 1), (0, 1)]) == [[0, 1], [2]]
# a greedy choice 0->2 would need 3 paths; augmenting fixes it
paths = path_cover_by_bipartite_matching(4, [(0, 2), (0, 3), (1, 2)])
assert len(paths) == 2 and is_cover(4, [(0, 2), (0, 3), (1, 2)], paths)
def test_rejects_cycles() -> None:
with pytest.raises(ValueError):
path_cover_by_bipartite_matching(2, [(0, 1), (1, 0)])
with pytest.raises(ValueError):
path_cover_by_bipartite_matching(1, [(0, 0)])
def test_random_against_brute_force() -> None:
rng = random.Random(775)
for _ in range(800):
n = rng.randint(1, 7)
order = list(range(n))
rng.shuffle(order)
arcs = []
for _ in range(rng.randint(0, 11)):
i, j = sorted(rng.sample(range(n), 2)) if n >= 2 else (0, 0)
if i != j:
arcs.append((order[i], order[j]))
paths = path_cover_by_bipartite_matching(n, arcs)
assert is_cover(n, arcs, paths)
assert len(paths) == brute_min_cover(n, arcs)
What the next level needs
- the tests did not run in this build