/
bipartite_matching.py
42 lines (34 loc) · 1.24 KB
/
bipartite_matching.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""\
Bipartie maximum matching
jill-jenn vie et christoph durr - 2014-2018
"""
__all__ = ["max_bipartite_matching"]
# snip{
def augment(u, bigraph, visit, timestamp, match):
""" find augmenting path starting from u, by recursive DFS """
for v in bigraph[u]:
if visit[v] < timestamp:
visit[v] = timestamp
if match[v] is None or augment(match[v], bigraph,
visit, timestamp, match):
match[v] = u # found an augmenting path
return True
return False
def max_bipartite_matching(bigraph):
"""Bipartie maximum matching
:param bigraph: adjacency list, index = vertex in U,
value = neighbor list in V
:comment: U and V can have different cardinalities
:returns: matching list, match[v] == u iff (u, v) in matching
:complexity: `O(|V|*|E|)`
"""
nU = len(bigraph) # nU = cardinality of U, nV = card. of V
nV = max(max(adjlist, default=-1) for adjlist in bigraph) + 1
match = [None] * nV
visit = [-1] * nV # timestamp of last visit
for u in range(nU):
augment(u, bigraph, visit, u, match)
return match
# snip}