Welcome, guest | Sign In | My Account | Store | Cart

Takes as input a bipartite graph in a variation of Guido van Rossum's dictionary-of-lists format, and outputs both a maximum matching (largest possible set of nonadjacent edges) and a maximum independent set (largest possible set of nonadjacent vertices). The running time in the worst case is O(E sqrt(V)) but for many graphs it runs faster due to doing fewer than the worst case number of iterations.

Python, 74 lines
 ``` 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 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74``` ```# Hopcroft-Karp bipartite max-cardinality matching and max independent set # David Eppstein, UC Irvine, 27 Apr 2002 def bipartiteMatch(graph): '''Find maximum cardinality matching of a bipartite graph (U,V,E). The input format is a dictionary mapping members of U to a list 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 1: # 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 = dict([(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 1 return 0 for v in unmatched: recurse(v) ```

Example from Cormen, Leiserson, and Rivest, section 27.3: <pre> bipartiteMatch({ 0:[0], 1:[0,2], 2:[1,2,3], 3:[2], 4:[2] }) </pre> There are other bipartite matching algorithms available with similar performance but this one is relatively simple and not bad in practice.

One situation where this problem comes up is in partitioning a rectilinear polygon into a minimum number of rectangles: one can do this by finding a maximum set of non-crossing horizontal and vertical diagonals that connect pairs of concave corners of the polygon, and this is a maximum independent set problem in a bipartite graph representing the crossings between diagonals. However in this application the matching algorithm can be sped up by replacing the adjacency lists with more complicated data structures -- see Imai and Asano, SIAM J. Computing 15(2):478-494, 1986.

 Created by David Eppstein on Sat, 27 Apr 2002 (PSF)

### Required Modules

• (none specified)