Title: How to get different maximum matchings
Tags: algorithm;language-agnostic;graph-theory;bipartite
Question: I have a large bipartite graph and I can find a maximum matching quickly using Hopcroft-Karp. But what I would really like is a few hundred different maximum matchings for the same graph. How can I get those?
Here is an example small bipartite graph with a maximum matching shown.
Similar graphs can be made with:
import igraph as ig
from scipy.sparse import random, find
from scipy import stats
from numpy.random import default_rng
import numpy as np
from igraph import Graph, plot
np.random.seed(7)
rng = default_rng()
rvs = stats.poisson(2).rvs
S = random(20, 20, density=0.35, random_state=rng, data_rvs=rvs)
triples = [*zip(*find(S))]
edges = [(triple[0], triple[1]+20) for triple in triples]
print(edges)
types = [0]*20+[1]*20
g = Graph.Bipartite(types, edges)
matching = g.maximum_bipartite_matching()
layout = g.layout_bipartite()
visual_style={}
visual_style[&quot;vertex_size&quot;] = 10
visual_style[&quot;bbox&quot;] = (600,300)
plot(g, bbox=(600, 200), layout=g.layout_bipartite(), vertex_size=20, vertex_label=range(g.vcount()),
vertex_color=&quot;lightblue&quot;, edge_width=[5 if e.target == matching.match_of(e.source) else 1.0 for e in g.es], edge_color=[&quot;red&quot; if e.target == matching.match_of(e.source) else &quot;black&quot; for e in g.es]
Comment: You give example code using Python but did not tag this with Python. Are you looking for an answer specifically in Python or not? If Python only then please add the tag [tag:python] , if not then please add the tag [tag:lalanguage-agnostic]. Thanks.

Here is the accepted answer: There’s an enumeration algorithm due to Fukuda and Matsui (“Finding all the perfect matchings in bipartite graphs”), (pdf) which was improved for non-sparse graphs by Uno (“Algorithms for enumerating all perfect,
maximum and maximal matchings in bipartite graphs”) at the cost of more implementation complexity.
Given the graph G, we find a matching M (e.g., with Hopcroft–Karp) to
pass along with G to the root of a recursive enumeration procedure. On
input (G, M), if M is empty, then the procedure yields M. Otherwise, the
procedure chooses an arbitrary e ∈ M. A maximum matching in G either
contains e or not. To enumerate the matchings that contain e, delete e’s
endpoints from G to obtain G′, delete e from M to obtain M′, make a
recursive call for (G′, M′), and add e to all of the matchings returned.
To enumerate the matchings that don’t contain e, delete e from G to
obtain G′′ and look for an augmenting path with respect to (G′′, M′). If
we find a new maximum matching M′′ thereby, recur on (G′′, M′′).
With Python you can implement this procedure using generators and then
grab as many matchings as you like.
def augment_bipartite_matching(g, m, u_cover=None, v_cover=None):
level = set(g)
level.difference_update(m.values())
u_parent = {u: None for u in level}
v_parent = {}
while level:
next_level = set()
for u in level:
for v in g[u]:
if v in v_parent:
continue
v_parent[v] = u
if v not in m:
while v is not None:
u = v_parent[v]
m[v] = u
v = u_parent[u]
return True
if m[v] not in u_parent:
u_parent[m[v]] = v
next_level.add(m[v])
level = next_level
if u_cover is not None:
u_cover.update(g)
u_cover.difference_update(u_parent)
if v_cover is not None:
v_cover.update(v_parent)
return False
def max_bipartite_matching_and_min_vertex_cover(g):
m = {}
u_cover = set()
v_cover = set()
while augment_bipartite_matching(g, m, u_cover, v_cover):
pass
return m, u_cover, v_cover
def max_bipartite_matchings(g, m):
if not m:
yield {}
return
m_prime = m.copy()
v, u = m_prime.popitem()
g_prime = {w: g[w] - {v} for w in g if w != u}
for m in max_bipartite_matchings(g_prime, m_prime):
assert v not in m
m[v] = u
yield m
g_prime_prime = {w: g[w] - {v} if w == u else g[w] for w in g}
if augment_bipartite_matching(g_prime_prime, m_prime):
yield from max_bipartite_matchings(g_prime_prime, m_prime)
# Test code
import itertools
import random
def erdos_renyi_random_bipartite_graph(n_u, n_v, p):
return {u: {v for v in range(n_v) if random.random() < p} for u in range(n_u)}
def is_bipartite_matching(g, m):
for v, u in m.items():
if u not in g or v not in g[u]:
return False
return len(set(m.values())) == len(m)
def is_bipartite_vertex_cover(g, u_cover, v_cover):
for u in g:
if u in u_cover:
continue
for v in g[u]:
if v not in v_cover:
return False
return True
def is_max_bipartite_matching(g, m, u_cover, v_cover):
return (
is_bipartite_matching(g, m)
and is_bipartite_vertex_cover(g, u_cover, v_cover)
and len(m) == len(u_cover) + len(v_cover)
def brute_force_count_bipartite_matchings(g, k):
g_edges = [(v, u) for u in g for v in g[u]]
count = 0
for m_edges in itertools.combinations(g_edges, k):
m = dict(m_edges)
if len(m) == k and is_bipartite_matching(g, m):
count += 1
return count
def test():
g = erdos_renyi_random_bipartite_graph(7, 7, 0.35)
m, u_cover, v_cover = max_bipartite_matching_and_min_vertex_cover(g)
assert is_max_bipartite_matching(g, m, u_cover, v_cover)
count = 0
for m_prime in max_bipartite_matchings(g, m):
assert is_bipartite_matching(g, m_prime)
assert len(m_prime) == len(m)
count += 1
assert brute_force_count_bipartite_matchings(g, len(m)) == count
for i in range(100):
test()


{'source': 'StackExchangeDataset', 'subset': 'stackoverflow.com', 'metadata': {'AnswerCount': 1, 'CommentCount': 1, 'ContentLicense': 'CC BY-SA 4.0', 'CreationDate': '2022:00:04/09/22', 'FavoriteCount': 2.0, 'PostTypeId': 1, 'Tags': '<algorithm><language-agnostic><graph-theory><bipartite>', 'Title': 'How to get different maximum matchings', 'ViewCount': 197, 'id': 71807022, 'user_AboutMe': None, 'user_AccountId': 24849695.0, 'user_DisplayName': 'byteful', 'user_Reputation': 169.0, 'user_Views': 41.0, 'user_id': 18726774.0}}