"""BipartiteMatching.py
Hopcroft-Karp bipartite maximum-cardinality matching and maximum
independent set for bipartite graphs.
D. Eppstein, April 2002.
"""
from StrongConnectivity import StronglyConnectedComponents
def matching(graph):
"""
Find maximum cardinality matching of a bipartite graph (U,V,E).
The input format is a dictionary mapping members of U to lists
of their neighbors in V. The output is a triple (M,A,B) where M is a
dictionary mapping members of V to their matches in U, A is the part
of the maximum independent set in U, and B is the part of the MIS in V.
The same object may occur in both U and V, and is treated as two
distinct vertices if this happens.
"""
# initialize greedy matching (redundant, but faster than full search)
matching = {}
for u in graph:
for v in graph[u]:
if v not in matching:
matching[v] = u
break
while True:
# structure residual graph into layers
# pred[u] gives the neighbor in the previous layer for u in U
# preds[v] gives a list of neighbors in the previous layer for v in V
# unmatched gives a list of unmatched vertices in final layer of V,
# and is also used as a flag value for pred[u] when u is in the first layer
preds = {}
unmatched = []
pred = {u:unmatched for u in graph}
for v in matching:
del pred[matching[v]]
layer = list(pred)
# repeatedly extend layering structure by another pair of layers
while layer and not unmatched:
newLayer = {}
for u in layer:
for v in graph[u]:
if v not in preds:
newLayer.setdefault(v,[]).append(u)
layer = []
for v in newLayer:
preds[v] = newLayer[v]
if v in matching:
layer.append(matching[v])
pred[matching[v]] = v
else:
unmatched.append(v)
# did we finish layering without finding any alternating paths?
if not unmatched:
unlayered = {}
for u in graph:
for v in graph[u]:
if v not in preds:
unlayered[v] = None
return (matching,list(pred),list(unlayered))
# recursively search backward through layers to find alternating paths
# recursion returns true if found path, false otherwise
def recurse(v):
if v in preds:
L = preds[v]
del preds[v]
for u in L:
if u in pred:
pu = pred[u]
del pred[u]
if pu is unmatched or recurse(pu):
matching[v] = u
return True
return False
for v in unmatched: recurse(v)
def imperfections(graph):
"""
Find edges that do not belong to any perfect matching of G.
The input format is the same as for matching(), and the output
is a subgraph of the input graph in the same format.
For each edge v->w in the output subgraph, imperfections[v][w]
is itself a subgraph of the input, induced by a set of
vertices that must be matched to each other, including w but
not including v.
"""
M,A,B = matching(graph)
if len(M) != len(graph):
return graph # whole graph is imperfect
orientation = {}
for v in graph:
orientation[v,True]=[]
for w in graph[v]:
if M[w] == v:
orientation[w,False]=[(v,True)]
else:
orientation[v,True].append((w,False))
components = {}
for C in StronglyConnectedComponents(orientation):
induced = {v:{w for w,bit2 in C[v,bit]} for v,bit in C if bit}
for v,bit in C:
if not bit: # don't forget the matched edges!
induced.setdefault(M[v],set()).add(v)
for v in C:
components[v] = induced
imperfections = {}
for v in graph:
imperfections[v] = {w:components[w,False] for w in graph[v]
if M[w] != v and
components[v,True] != components[w,False]}
return imperfections