Source code online books for professionals by professionals

Listing 10-2.  Counting Edge-Disjoint Paths Using Labeling Traversal to Find Augmenting Paths
from itertools import chain
 
def paths(G, s, t):                             # Edge-disjoint path count
    H, M, count = tr(G), set(), 0               # Transpose, matching, result
    while True:                                 # Until the function returns
        Q, P = {s}, {}                          # Traversal queue + tree
        while Q:                                # Discovered, unvisited
            u = Q.pop()                         # Get one
            if u == t:                          # Augmenting path!
                count += 1                      # That means one more path
                break                           # End the traversal
            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
        else:                                   # Didn't reach t?
            return count                        # We're done
        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
 
To make sure we’ve solved the problem, we still need to prove the converse, though—that there always will be 
an augmenting path as long as there is room for improvement. The easiest way of showing this is by using the idea 
of connectivity: how many edges must we remove to separate s from t (so that no path goes from s to t)? Any such set 
represents an s-t cut, a partitioning into two sets S and T, where S contains s and T contains t. We call the edges going 
from S to T a directed edge separator. We can then show that the following three statements are equivalent:
We have found 
•
k disjoint paths and there is an edge separator of size k.
We have found the maximum number of disjoint paths.
•
There are no augmenting paths.
•
What we primarily want to show is that the last two statements are equivalent, but sometimes it’s easier to go via 
a third statement, such as the first one in this case.
It’s pretty easy to see that the first implies the second. Let’s call the separator F. Any s-t path must have at least 
one edge in F, which means that the size of F is at least as great as the number of disjoint s-t paths. If the size of the 
separator is the same as the number of disjoint paths we’ve found, clearly we’ve reached the maximum.
Showing that the second statement implies the third is easily done by contradiction. Assume there is no room for 
improvement but that we still have an augmenting path. As discussed, this augmenting path could be used to improve 
the solution, so we have a contradiction.
The only thing left to prove is that the last statement implies the first, and this is where the whole connectivity 
idea pays off as a stepping stone. Imagine you’ve executed the algorithm until you’ve run out of augmenting paths. 
Let S be the set of nodes you reached in your last traversal, and let T be the remaining nodes. Clearly, this is an s-t cut. 
Consider the edges across this cut. Any forward edge from S to T must be part of one of your discovered disjoint paths. 
If it wasn’t, you would have followed it during your traversal. For the same reason, no edge from T to S can be part of 

---

ChApTeR 10 
■
 MATChINgs, CuTs, ANd Flows 
215
one of the paths, because you could have canceled it, thereby reaching T. In other words, all edges across from S to 
T belong to your disjoint paths, and because none of the edges in the other direction do, the forward edges must all 
belong to a path of their own, meaning that you have k disjoint paths and a separator of size k.
This may be a bit involved, but the intuition is that if we can’t find an augmenting path, there must be a 
bottleneck somewhere, and we must have filled it. No matter what we do, we can’t get more paths through this 
bottleneck, so the algorithm must have found the answer. (This result is a version of Menger’s theorem, and it is  
a special case of the max-flow min-cut theorem, which you’ll see in a bit.)
What’s the running time of all this, then? Each iteration consists of a relatively straightforward traversal from s, 
which has a running time of O(m), for m edges. Each round gives us another disjoint path, and there are clearly at most 
O(m), meaning that the running time is O(m
2
). Exercise 10-3 asks you to show that this is a tight bound in the worst case.
Note
 
■
   Menger’s theorem is another example of duality: The maximum number of edge-disjoint paths from s to t is 
equal to the minimum cut between s and t. This is a special case of the max-flow min-cut theorem, discussed later.
Maximum Flow
This is the central problem of the chapter. It forms a generalization of both the bipartite matching and the disjoint 
paths, and it is the mirror image of the minimum cut problem (next section). The only difference from the disjoint 
path case is that instead of setting the capacity for each edge to one, we let it be an arbitrary positive number. If the 
capacity is a positive integer, you could think of it as the number of paths that can pass through it. More generally, the 
metaphor here is some form of substance flowing through the network, from the source to the sink, and the capacity 
represents the limit for how many units can flow through a given edge. (You can think of this as a generalization of 
the engagement rings that were passed back and forth in the matching.) In general, the flow itself is an assignment 
of a number of flow units to each unit (that is, a function or mapping from edges to numbers), while the size or 
magnitude of the flow is the total amount pushed through the network. (This can be found by finding the net flow out 
of the source, for example.) Note that although flow networks are commonly defined as directed, you could find the 
maximum flow in an undirected network as well (Exercise 10-4).
Let’s see how we can solve this more general case. A naïve approach would be to simply split edges, just like 
the naïve extension of BFS in Chapter 9 (Figure 9-3). Now, though, we want to split them lengthwise, as shown in 
Figure 
10-3
. Just like BFS with serial dummy nodes gives you a good idea of how Dijkstra’s algorithm works, our 
augmenting path algorithm with parallel dummy nodes is very close to how the full Ford-Fulkerson algorithm for 
finding maximum flow works. As in the Dijkstra case, though, the actual algorithm can take care of greater chunks of 
flow in one go, meaning that the dummy node approach (which lets us saturate only one unit of capacity at a time) is 
hopelessly inefficient.