Input description: A graph G, where each edge e=(i,j) has a capacity . A source node and sink node t.
Problem description: What is the maximum flow you can route from to t while respecting the capacity constraint of each edge?
Discussion: Applications of network flow go far beyond plumbing. Finding the most cost-effective way to ship goods between a set of factories and a set of stores defines a network flow problem, as do resource-allocation problems in communications networks and a variety of scheduling problems.
The real power of network flow is that a surprising variety of linear programming problems that arise in practice can be modeled as network flow problems, and that special-purpose network flow algorithms can solve such problems much faster than general-purpose linear programming methods. Several of the graph problems we have discussed in this book can be modeled as network flow, including bipartite matching, shortest path, and edge/vertex connectivity.
The key to exploiting this power is recognizing that your problem can be modeled as network flow. This is not easy, and it requires experience and study. My recommendation is to first construct a linear programming model for your problem and then compare it with the linear program for minimum-cost flow on a directed network G=(V,E). Let be a variable accounting for the flow from vertex i through edge j. The flow through edge j is constrained by its capacity, so
Further, at each nonsource or sink vertex, as much flow comes in as goes out, so
where we seek the assignment that minimizes
where is the cost of a unit of flow from i through j.
Special considerations include:
Linear programming will suffice for multicommodity flow if fractional flows are permitted. Unfortunately, multicommodity integral flow is NP-complete, even with only two commodities.
Network flow algorithms can be complicated, and significant engineering is required to optimize performance. Thus we strongly recommend that you use an existing code if possible, rather than implement your own. Excellent codes are available and are described below. The two primary classes of algorithms are:
Implementations: The highest-performance code available for solving maximum-flow in graphs is PRF [CG94], developed in the C language by Cherkassky and Goldberg. They report solving instances with over 250,000 vertices in under two minutes on a Sun Sparc-10 workstation. For minimum-cost max-flow, the highest-performance code available is CS [Gol92], capable of solving instances of over 30,000 vertices in a few minutes on Sun Sparc-2 workstations. Both of their codes are available by ftp for noncommercial use from http://www.neci.nj.nec.com/homepages/avg.html.
The First DIMACS Implementation Challenge on Network Flows and Matching [JM93] collected several implementations and generators for network flow, which can be obtained by anonymous ftp from dimacs.rutgers.edu in the directory pub/netflow/maxflow. These include:
Nijenhuis and Wilf [NW78] provide a Fortran implementation of Karzanov's algorithm for network flow. See Section . Fortran minimum-cost flow codes are given in [PGD82] and [KH80].
LEDA (see Section ) provides C++ implementations of maximum-flow and minimum-cost max-flow algorithms. It also provides an implementation of minimum cut.
Pascal implementations of max-flow and minimum-cost flow algorithms are provided in [SDK83]. Alternative Pascal max-flow implementations appear in [MS91]. For both codes, see Section .
Combinatorica [Ski90] provides a (slow) Mathematica implementation of network flow, with applications to connectivity testing and matching. See Section .
Notes: The definitive book on network flows and its applications is [AMO93]. Good expositions on preflow-push algorithms [GT88] include [CLR90]. Older augmenting path algorithms are discussed in [Eve79a, Man89, PS82]. Expositions on min-cost flow include [Law76, PS82, SDK83]. Expositions on the hardness of multicommodity flow [Ita78] include [Eve79a].
Conventional wisdom holds that network flow should be computable in O(nm) time, and there has been steady progress in lowering the time complexity. See [AMO93] for a history of algorithms for the problem. The fastest known general network flow algorithm runs in time [GT88]. Empirical studies of minimum-cost flow algorithms include [GKK74, Gol92].
Although network flow can be used to find minimum cut sets in graphs, faster algorithms are available, including [SW94] and [MR95].
Related Problems: Linear programming (see page ), matching (see page ), connectivity (see page ).