Match as many left vertices to right vertices as possible, each used once. Add a source with a unit edge to every left vertex and a sink fed by every right vertex, keep the pairs as unit edges, and run max flow: each unit of flow is one matched pair, and each augmenting path is an alternating path that may re-pair earlier matches.
The code
Maximum Flow, in Python
def max_flow(cap, s, t, bfs):
flow = [[0] * n for _ in range(n)] # flow[v][u] == -flow[u][v]
total = 0
while True:
parent = bfs_path(s, t) if bfs else dfs_path(s, t) # residual(u, v) > 0 edges only
if parent[t] < 0: # t unreachable: no augmenting path
break
bottleneck = float("inf")
v = t
while v != s:
u = parent[v]
bottleneck = min(bottleneck, residual(u, v))
v = u
v = t
while v != s:
u = parent[v]
flow[u][v] += bottleneck
flow[v][u] -= bottleneck
v = u
total += bottleneck
return total
def residual(u, v):
return cap[u][v] - flow[u][v] # undoing flow on v->u counts as room on u->v
def min_cut(): # after max_flow
reachable = bfs_reachable(s) # S side: still reachable in the residual graph
return [(u, v) for u, v in edges if u in reachable and v not in reachable] # all saturated, summing to the flow
def bipartite_matching(left, right, pairs):
# s -> every left vertex, left -> right along the pairs, every right vertex -> t, all capacity 1
return max_flow(unit_network(left, right, pairs), s, t, bfs=True) # each path is an alternating path
def dinic(s, t):
total = 0
while True:
level = bfs_levels(s) # residual edges only, distance from s
if level[t] < 0: # t unreachable: done
return total
while True: # a blocking flow in this level graph
path = dfs_path(s, t, lambda u, v: level[v] == level[u] + 1 and residual(u, v) > 0)
if path is None: # no path left at these levels: next phase
break
amount = min(residual(u, v) for u, v in zip(path, path[1:]))
push(path, amount)
total += amount
# at most V phases: O(V^2 E)
Maximum Flow, in JavaScript
function maxFlow(cap, s, t, bfs) {
const flow = Array.from({ length: n }, () => new Array(n).fill(0)); // flow[v][u] == -flow[u][v]
let total = 0;
while (true) {
const parent = bfs ? bfsPath(s, t) : dfsPath(s, t); // residual(u, v) > 0 edges only
if (parent[t] < 0) break; // t unreachable: no augmenting path
let bottleneck = Infinity;
let v = t;
while (v !== s) {
const u = parent[v];
bottleneck = Math.min(bottleneck, residual(u, v));
v = u;
}
v = t;
while (v !== s) {
const u = parent[v];
flow[u][v] += bottleneck;
flow[v][u] -= bottleneck;
v = u;
}
total += bottleneck;
}
return total;
}
function residual(u, v) {
return cap[u][v] - flow[u][v]; // undoing flow on v->u counts as room on u->v
}
function minCut() { // after maxFlow
const reachable = bfsReachable(s); // S side: still reachable in the residual graph
return edges.filter(([u, v]) => reachable.has(u) && !reachable.has(v)); // all saturated, summing to the flow
}
function bipartiteMatching(left, right, pairs) {
// s -> every left vertex, left -> right along the pairs, every right vertex -> t, all capacity 1
return maxFlow(unitNetwork(left, right, pairs), s, t, true); // each path is an alternating path
}
function dinic(s, t) {
let total = 0;
while (true) {
const level = bfsLevels(s); // residual edges only, distance from s
if (level[t] < 0) return total; // t unreachable: done
while (true) { // a blocking flow in this level graph
const path = dfsPath(s, t, (u, v) => level[v] === level[u] + 1 && residual(u, v) > 0);
if (path == null) break; // no path left at these levels: next phase
const amount = Math.min(...path.slice(0, -1).map((u, i) => residual(u, path[i + 1])));
push(path, amount);
total += amount;
}
}
} // at most V phases: O(V^2 E)
Maximum Flow, in Kotlin
fun maxFlow(cap: Array<IntArray>, s: Int, t: Int, bfs: Boolean): Int {
val flow = Array(n) { IntArray(n) } // flow[v][u] == -flow[u][v]
var total = 0
while (true) {
val parent = if (bfs) bfsPath(s, t) else dfsPath(s, t) // residual(u, v) > 0 edges only
if (parent[t] < 0) break // t unreachable: no augmenting path
var bottleneck = Int.MAX_VALUE
var v = t
while (v != s) { val u = parent[v]; bottleneck = min(bottleneck, residual(u, v)); v = u }
v = t
while (v != s) { val u = parent[v]; flow[u][v] += bottleneck; flow[v][u] -= bottleneck; v = u }
total += bottleneck
}
return total
}
fun residual(u: Int, v: Int) = cap[u][v] - flow[u][v] // undoing flow on v->u counts as room on u->v
fun minCut(): List<Pair<Int, Int>> { // after maxFlow
val reachable = bfsReachable(s) // S side: still reachable in the residual graph
return edges.filter { (u, v) -> u in reachable && v !in reachable } // all saturated, summing to the flow
}
fun bipartiteMatching(left: Int, right: Int, pairs: List<Pair<Int, Int>>): Int {
// s -> every left vertex, left -> right along the pairs, every right vertex -> t, all capacity 1
return maxFlow(unitNetwork(left, right, pairs), s, t, bfs = true) // each path is an alternating path
}
fun dinic(s: Int, t: Int): Int {
var total = 0
while (true) {
val level = bfsLevels(s) // residual edges only, distance from s
if (level[t] < 0) return total // t unreachable: done
while (true) { // a blocking flow in this level graph
val path = dfsPath(s, t) { u, v -> level[v] == level[u] + 1 && residual(u, v) > 0 }
?: break // no path left at these levels: next phase
val amount = path.zipWithNext().minOf { (u, v) -> residual(u, v) }
push(path, amount); total += amount
}
}
} // at most V phases: O(V^2 E)