NETWORK FLOWS HELP          Wed Aug  7 23:35:32 EDT 2002

A network flow problem can be reduced to the problem of
finding a shortest path with non-zero flow.  Alterna-
tively it can be reduced to the dynamic programming
problem of finding a path with maximum flow.

A flow network is a directed graph in which every arrow
is labeled with a capacity, and we are asked to find the
maximum amount of fluid (or whatever) that can flow from
a given source vertex to a given destination vertex,
assuming each arrow is a uni-directional pipe whose 
capacity is the maximum fluid flow on that pipe.  See
the Maximum Flow chapter of Cormen, Leiserson, and
Rivest or the Advanced Combinatorial Algorithms chapter
of Atallah.

The simpler algorithms find an path flow P from source
to destination and subtract P from the original flow
network N to get a residual flow network R.  P is a
path from source to destination each of whose edges has
positive, non-zero capacity in N.  The flow of P is the
minimum capacity of all P's edges.  It is this flow that
must be subtracted from the capacities of N, for each
edge in P, to get the capacities of R.  R and N are then
related, in that every flow FR of R that obeys R's cap-
acity restrictions is related to a flow FN of N that
obeys N's capacity restrictions with the FN equal to
FR plus the flow of P.

The path flow P is called an `augmenting path' because
the maximum flow of N is the sum of P and the maximum
flow of R.

One iterates the above algorithm until the residual
network has no remaining path with non-zero flow.
There is then an easy lemma saying that the maximum
flow of this residual network is zero.  It follows that
the maximum flow of the original network is the sum of
all the augmenting paths found by the iterations.

Some cleverness is required in computing residual net-
works.  If the original network has capacities Cxy from
vertex x to vertex y, and Cyx from vertex y to vertex x,
and if the path being subtracted has flow f > 0 from x
to y, then the residual network has capacities Cxy-f
from x to y and Cyx+f from y to x.  Even if Cyx was 
originally 0, and there was no explicit arrow from y to
x.  This is because a flow of f from y to x in the
residual network can be obtained by reducing the flow
subtracted out of the original network to 0.

The hard part of all this is finding the right augment-
ing paths.  A sloppy algorithm can find paths that have
too little flow, and the require too many iterations.
E.g., consider the network:



          1,000,000,001        1,000,000,000
       +-----------------> C ----------------> +
       |                   |                   |
       |                   |                   |
       |      2,000,000,000|                   |
       |                   |                   |
       |                   v                   |
       |                   D                   |
       |                   |                   v
       B                   |2                  G
       |                   v                   ^
       |                   E                   |
       |                  ^ |                  |
       |                  | |                  |
       |     2,000,000,000| |2                 |
       |                  | |                  |
       |                  | |                  |
       |  1,000,000,000   | v  1,000,000,000   |
       + ----------------> F ------------------+


Here the problem is to find the maximum flow from B to
G.  A depth first search that prefers the arrow of
greatest capacity and does not revisit vertices would
find the path B->C->D->E->F->G in the first iteration,
which only has a flow of 2, and then find the path
B->F->E->D->C->G in the second iteration, which only has
the flow of 2, and then repeat these two iterations over
and over.  There would be about a billion iterations in
all.  But if the first iteration found B->C->G and the
second B->F->G, the algorithm would complete in just two
iterations.

The easiest good algorithm for finding augmenting paths
is to just find a shortest augmenting path.  The number
of augmenting paths that must be found can be shown to
be O(|E| |V|), where |E| is the number of edges and |V|
is the number of vertices in the original flow network.

A slightly better solution is to find an augmenting
path with maximum flow.  Calculating the maximum flow
of any path from source to destination is an easy
dynamic programming problem (see help file on dynamic
programming).  It can be shown that the number of
maximum flow augmenting paths that must be found is at
most O(|E| log C) where |E| is the number of edges and
C is the maximum capacity of any edge in the original
flow network.




File:		network_flows
Author:		Bob Walton <walton@deas.harvard.edu>
Date:		See top of file.

The authors have placed this file in the public domain;
they make no warranty and accept no liability for this
file.

RCS Info (may not be true date or author):

    $Author: hc3 $
    $Date: 2002/08/08 03:37:08 $
    $RCSfile: network_flows,v $
    $Revision: 1.6 $