76 lines
2.0 KiB
Python
76 lines
2.0 KiB
Python
import random
|
|
from hopcroft_karp import max_bipartite_matching
|
|
|
|
|
|
def kuhn(adj, n_left, n_right):
|
|
match_r = [-1] * n_right
|
|
|
|
def try_k(u, seen):
|
|
for v in adj[u]:
|
|
if seen[v]:
|
|
continue
|
|
seen[v] = True
|
|
if match_r[v] == -1 or try_k(match_r[v], seen):
|
|
match_r[v] = u
|
|
return True
|
|
return False
|
|
|
|
size = 0
|
|
for u in range(n_left):
|
|
seen = [False] * n_right
|
|
if try_k(u, seen):
|
|
size += 1
|
|
return size
|
|
|
|
|
|
def test_random():
|
|
rng = random.Random(42)
|
|
for _ in range(2000):
|
|
nL = rng.randint(0, 8)
|
|
nR = rng.randint(0, 8)
|
|
m = rng.randint(0, nL * nR if nL and nR else 0)
|
|
edges = []
|
|
seen = set()
|
|
for _ in range(m):
|
|
u = rng.randrange(nL) if nL else 0
|
|
v = rng.randrange(nR) if nR else 0
|
|
if (u, v) not in seen:
|
|
seen.add((u, v))
|
|
edges.append((u, v))
|
|
adj = [[] for _ in range(nL)]
|
|
for u, v in edges:
|
|
adj[u].append(v)
|
|
# shuffle adjacency order to stress
|
|
for u in range(nL):
|
|
rng.shuffle(adj[u])
|
|
size, ml, mr = max_bipartite_matching(adj, nL, nR)
|
|
ref = kuhn(adj, nL, nR)
|
|
assert size == ref, (size, ref, adj)
|
|
# verify matching consistency
|
|
assert all(ml[u] == -1 or mr[ml[u]] == u for u in range(nL))
|
|
assert sum(1 for u in range(nL) if ml[u] != -1) == size
|
|
|
|
|
|
def test_empty():
|
|
size, ml, mr = max_bipartite_matching([], 0, 0)
|
|
assert size == 0 and ml == [] and mr == []
|
|
|
|
|
|
def test_complete():
|
|
n = 5
|
|
adj = [[v for v in range(n)] for _ in range(n)]
|
|
size, _, _ = max_bipartite_matching(adj, n, n)
|
|
assert size == n
|
|
|
|
|
|
def test_no_edges():
|
|
adj = [[] for _ in range(4)]
|
|
size, _, _ = max_bipartite_matching(adj, 4, 4)
|
|
assert size == 0
|
|
|
|
|
|
def test_duplicates():
|
|
adj = [[0, 0, 1], [1]]
|
|
size, _, _ = max_bipartite_matching(adj, 2, 2)
|
|
assert size == 2
|