Network Flow

  

 

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:

• What if all my costs are identical? - Simpler and faster algorithms exist for solving the simple (as opposed to min-cost) maximum flow problem. This problem arises in many applications, including connectivity and bipartite matching.
• What if all arc capacities are identical, either 0 or 1? - Faster algorithms exist for 0-1 network flows. See the references for details.
• What if I have multiple sources and/or sinks? -     Such problems can be handled by modifying the network to create a vertex to serve as a super-source that feeds all the sources and a super-sink that drains all the sinks.
• What if I have multiple types of material moving through the network? -   In modeling a telecommunications network, every message has a given source and destination. Each destination needs to receive exactly those calls sent to it, not a given quantity of communication from arbitrary places. This can be modeled as a multicommodity flow problem, where each call defines a different commodity and we seek to satisfy all demands without exceeding the total capacity of any edge.

  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:

• Augmenting path methods -   These algorithms repeatedly find a path of positive capacity from source to sink and add it to the flow. It can be shown that the flow through a network of rational capacities is optimal if and only if it contains no augmenting path, and since each augmentation adds to the flow, we will eventually find the maximum. The difference between network flow algorithms is in how they select the augmenting path. If we are not careful, each augmenting path will add but a little to the total flow, and so the algorithm might take a long time to converge.
• Preflow-push methods -   These algorithms push flows from one vertex to another, ignoring until the end the constraint that the in-flow must equal the out-flow at each vertex. Preflow-push methods prove faster than augmenting path methods, essentially because multiple paths can be augmented simultaneously. These algorithms are the method of choice and are implemented in the best codes described below.

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:

• A preflow-push network flow implementation in C by Edward Rothberg. It took under a second on a test graph of 500 nodes and 4,000 edges, but over an hour with 5,000 nodes and 40,000 edges.
• An implementation of eleven network flow variants in C, including the older Dinic and Karzanov algorithms by Richard Anderson and Joao Setubal. On an instance of 8,000 vertices and 12,000 edges, all options finished within two seconds.    

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 ).