Source code online books for professionals by professionals

n
 represent the rows of the matrix, and let y
1
, …, y
m
 represent the columns. Also add a source s and a sink 
s. Give every row an in-edge from s, representing the row sums, and every column an out-edge to t, representing the 
column sums. Also, add an edge from every row to every column, representing the matrix elements. Every edge e then 
represents a real value r. Set l(e) = floor(r) and u(e) = ceil(r). A feasible flow from s to t with respect to l and u will 
give us exactly what we need—a consistent matrix rounding. (Do you see how?)
Summary
This chapter deals with a single core problem, finding maximum flows in flow networks, as well as specialized versions, 
such as maximum bipartite matching and finding edge-disjoint paths. You also saw how the minimum cut problem 
is the dual of the maximum flow problem, giving us two solutions for the price of one. Solving the minimum cost flow 
problem is also a close relative, requiring only that we switch the traversal method, using a shortest-path algorithm to 
find the cheapest augmenting path. The general idea underlying all of the solutions is that of iterative improvement, 
repeatedly finding an augmenting path that will let us improve the solution. This is the general Ford-Fulkerson 
method, which does not guarantee polynomial running time in general (or even termination, if you’re using irrational 
capacities). Finding the augmenting path with the fewest number of edges, using BFS, is called the Edmonds-Karp 
algorithm and solves this problem nicely. (Note that this approach cannot be used in the min-cost case because there 
we have to find the shortest path with respect to the capacities, not the edge counts.) The max-flow problem and its 
relative are flexible and apply to quite a lot of problems. The challenge becomes finding the suitable reductions.
If You’re Curious …
There is a truly vast amount of material out there on flow algorithm of various kinds. For example, there’s Dinic’s 
algorithm, which is a very close relative of the Edmonds-Karp algorithm (it actually predates it, and uses the same basic 
principles), with some tricks that improves the running time a bit. Or you have the push-relabel algorithm, which in most 
cases (except for sparse graphs) is faster than Edmonds-Karp. For the bipartite matching case, you have the Hopcroft-
Karp algorithm, which improves on the running time by performing multiple simultaneous traversals. For min-cost 
bipartite matching, there is also the well-known Hungarian algorithm, as well as more recent heuristic algorithms that 
really fly, such as the cost scaling algorithm (CSA) of Goldberg and Kennedy. And if you want to dig into the foundations 
of augmenting paths, perhaps you’d like to read Berge’s original paper, “Two Theorems in Graph Theory”?
There are more advanced flow problems, as well, involving lower bounds on edge flow, or so-called circulations, 
without sources or sinks. And there’s the multicommodity flow problem, for which there are no efficient special-
purpose algorithms (you need to solve it with a technique known as linear programming). And you have the matching 
problem—even the min-cost version—for general graphs. The algorithms for that are quite a bit more complex than 
the ones in this chapter.
A first stop for some gory details about flows might be a textbook such as Introduction to Algorithms by Cormen 
et al. (see the “References” section in Chapter 1), but if you’d like more breadth, as well as lots of example applications, 
I recommend Network Flows: Theory, Algorithms, and Applications by Ahuja, Magnanti, and Orlin. You may also want 
to check out the seminal work Flows in Networks, by Ford and Fulkerson.
Exercises
10-1. In some applications, such as when routing communication through switching points, it can be useful to let 
the nodes have capacities, instead of (or in addition to) the edges. How would you reduce this kind of problem to the 
standard max-flow problem?
10-2. How would you find vertex-disjoint paths?
10-3. Show that the worst-case running time of the augmenting path algorithm for finding disjoint paths is Q(m
2
), 
where m is the number of edges in the graph.
10-4. How would you find flow in an undirected network?

---

ChApTeR 10 
■
 MATChINgs, CuTs, ANd Flows 
225
10-5. Implement a wrapper-object that looks like a graph but that dynamically reflects the residual network of an 
underlying flow network with a changing flow. Implement some of the flow algorithms in this chapter using plain 
implementations of the traversal algorithms to find augmenting paths.
10-6. How would you reduce the flow problem (finding a flow of a given magnitude) to the max-flow problem?
10-7. Implement a solution to the min-cost flow problem using Dijkstra’s algorithm and weight adjustments.
10-8. In Exercise 4-3, you were inviting friends to a party and wanted to ensure that each guest knew at least k others 
there. You’ve realized that things are a bit more complicated. You like some friends more than others, represented by 
a real-valued compatibility, possibly negative. You also know that many of the guests will attend only if certain other 
guests attend (though the feelings need not be mutual). How would you select a feasible subset of potential guests that 
maximizes the sum of your compatibility to them? (You might also want to consider guests who won’t come if certain 
others do. That’s a bit harder, though—take a look at Exercise 11-19.)
10-9. In Chapter 4, four grumpy moviegoers were trying to figure out their seating arrangements. Part of the problem was 
that none of them would switch seats unless they could get their favorite. Let’s say they were slightly less grumpy and were 
willing to switch places as required to get the best solution. Now, an optimal solution could be found by just adding edges 
to free seats until you run out. Use a reduction to the bipartite matching algorithm in this chapter to show that this is so.
10-10. You’re having a team building seminar for n people, and you’re doing two exercises. In both exercises, you 
want to partition crowd into groups of k, and you want to make sure that no one in the second round is in the same 
group as someone they were in a group with in the first round. How could you solve this with maximum flow? 
(Assume that n is divisible by k.)
10-11. You’ve been hired by an interplanetary passenger transport service (or, less imaginatively, an airline) to analyze 
one of its flight. The spaceship lands on planets 1…n in order and can pick up or drop off passengers at each stop. You 
know how many passengers want to go from planet every i to every other planet j, as well as the fare for each such trip. 
Design an algorithm to maximize the profit for the entire trip. (This problem is based on Application 9.4 in Network 
Flows, by Ahuja et al.)
References
Ahuja, R. K., Magnanti, T. L., and Orlin, J. B. (1993). Network Flows: Theory, Algorithms, and Applications. Prentice Hall.
Berge, C. (1957). Two theorems in graph theory. Proceedings of the National Academy of Sciences of the United States of 
America 43(9):842–844. 
http://www.pnas.org/content/43/9/842.full.pdf
.
Busacker, R. G., Coffin, S. A., and Gowen, P. J. (1962). Three general network flow problems and their solutions.  
Staff Paper RAC-SP-183, Research Analysis Corporation, Operations Logistics Division.  
http://handle.dtic.mil/100.2/AD296365
.
Ford, L. R. and Fulkerson, D. R. (1957). A simple algorithm for finding maximal network flows and an application to 
the hitchcock problem. Canadian Journal of Mathematics, 9:210–218. 
http://smc.math.ca/cjm/v9/p210
.
Ford, L. R. and Fulkerson, D. R. (1962). Flows in networks. Technical Report R-375-PR, RAND Corporation.  
http://www.rand.org/pubs/reports/R375
.
Jungnickel, D. (2007). Graphs, Networks and Algorithms, third edition. Springer.
Goh, C. J. and Yang, X. Q. (2002). Duality in Optimization and Variational Inequalities. Optimization Theory and 
Applications. Taylor & Francis.
Goldberg, A. V. and Kennedy, R. (1995). An efficient cost scaling algorithm for the assignment problem. Mathematical 
Programming, 71:153–178. 
http://theory.stanford.edu/~robert/papers/csa.ps
.
Schwartz, B. L. (1966). Possible winners in partially completed tournaments. SIAM Review, 8(3):302–308.  
http://jstor.org/pss/2028206
.

---

227