Source code online books for professionals by professionals

Listing 10-1.  Finding a Maximum Bipartite Matching Using Augmenting Paths
from itertools import chain
 
def match(G, X, Y):                             # Maximum bipartite matching
    H = tr(G)                                   # The transposed graph
    S, T, M = set(X), set(Y), set()             # Unmatched left/right + match
    while S:                                    # Still unmatched on the left?
        s = S.pop()                             # Get one
        Q, P = {s}, {}                          # Start a traversal from it
        while Q:                                # Discovered, unvisited
            u = Q.pop()                         # Visit one
            if u in T:                          # Finished augmenting path?
                T.remove(u)                     # u is now matched
                break                           # and our traversal is done
            forw = (v for v in G[u] if (u,v) not in M)  # Possible new edges
            back = (v for v in H[u] if (v,u) in M)      # Cancellations
            for v in chain(forw, back):         # Along out- and in-edges
                if v in P: continue             # Already visited? Ignore
                P[v] = u                        # Traversal predecessor
                Q.add(v)                        # New node discovered
        while u != s:                           # Augment: Backtrack to s
            u, v = P[u], u                      # Shift one step
            if v in G[u]:                       # Forward edge?
                M.add((u,v))                    # New edge
            else:                               # Backward edge?
                M.remove((v,u))                 # Cancellation
    return M                                    # Matching -- a set of edges
 
Note
 
■
   König’s theorem states that for bipartite graph, the dual of the maximum matching problem is the minimum 
vertex cover problem. In other words, the problems are equivalent.
Disjoint Paths
The augmenting path method for finding matchings can also be used for more general problems. The simplest 
generalization may be to count edge-disjoint paths instead of edges.
2
 Edge-disjoint paths can share nodes but not 
edges. In this more general setting, we no longer need to restrict ourselves to bipartite graphs. When we allow general 
directed graphs, however, we can freely specify where the paths are to start and end. The easiest (and most common) 
solution is to specify two special nodes, s and t, called the source and the sink. (Such a graph is often called an s-t 
graph, or an s-t-network.) We then require all paths to start in s and end in t (implicitly allowing the paths to share 
these two nodes). An important application of this problem is determining the edge connectivity of a network—how 
many edges can be removed (or “fail”) before the graph is disconnected (or, in this case, before s cannot reach t)?
Another application is finding communication paths on a multicore CPU. You may have lots of cores laid out in 
two dimensions, and because of the way communication works, it can be impossible to route two communication 
2
In some ways, this problem is similar to the path counting in Chapter 8. The main difference, however, is that in that case we 
counted all possible paths (such as in Pascal’s Triangle), which would usually entail lots of overlap—otherwise the memoization 
would be pointless. That overlap is not permitted here.

---

ChApTeR 10 
■
 MATChINgs, CuTs, ANd Flows 
213
channels through the same switching points. In these cases, finding a set of disjoint paths is critical. Note that these 
paths would probably be more naturally modeled as vertex-disjoint, rather than edge-disjoint. See Exercise 10-2 for 
more. Also, as long as you need to pair each source core with a specific sink core, you have a version of what’s called 
the multicommodity flow problem, which isn’t dealt with here. (See “If You’re Curious …” for some pointers.)
You could deal with multiple sources and sinks directly in the algorithm, just like in Listing 10-1. If each of these 
sources and sinks can be involved only in a single path and you don’t care which source is paired with which sink, it 
can be easier to reduce the problem to the single-source, single-sink case. You do this by adding s and t as new nodes 
and introduce edges from s to all of your sources and from all your sinks to t. The number of paths will be the same, 
and reconstructing the paths you were looking for requires only snipping off s and t again. This reduction, in fact, 
makes the maximum matching problem a special case of the disjoint paths problem. As you’ll see, the algorithms for 
solving the problems are also very similar.
Instead of thinking about complete paths, it would be useful to be able to look at smaller parts of the problem in 
isolation. We can do that by introducing two rules:
The number of paths going 
•
into any node except s or t must equal the number of paths going 
out of that node.
At most 
•
one path can go through any given edge.
Given these restrictions, we can use traversal to find paths from s to t. At some point, we can’t find any more paths 
without overlapping with some of those we already have. Once again, though, we can use the augmenting path idea 
from the previous section. See, for example, Figure 
10-2
. A first round of traversal has established one path from s to t 
via c and b. Now, any further progress seems blocked by this path—but the augmenting path idea lets us improve the 
solution by canceling the edge from c to b.