[Matrix-SIG] ANN: Network maximum flow module

Aaron Watters aaron@cs.rutgers.edu
Fri, 12 Jun 1998 10:36:41 -0400


ANNOUNCE MPM.py Network Maximum flow algorithm implementation

  GO: http://www.pythonpros.com/arw/MPM/

MPM.py provides a Python based implementation of the
MPM network maximum-flow algorithm from

V.M. Malhotra, M. Pramodh-Kumar and S.N. Maheshwari
"An O(V**3) algorithm for finding maximum flows in networks"
Information Processing Letters, 7 (1978), 277-278.

The module is implemented in Python.
The MPM algorithm is one of the better algorithms for finding network
maximum flows.

This module will certainly be easy to use and fast enough for network
flow maximization problems with thousands of nodes and edges.

For example:
============

A simple motivating example may be stolen from

A Quantitative Approach to Management
Levin, Ruben, and Stinson
McGraw Hill, 1986. p.542

There are a number of freeways connected by intersections
(interchanges).  Each of the freeways has a maximum number of
cars that can pass across it per hour in each direction (and
for some "one way" freeways the capacity in one direction is
zero).  We number the intersections 1 through 6 and depict the
freeways as "arcs" between the intersections:

   6      0
(1)--------(2)
 | \        | \
 |  \5      |  \4
 |3  \      |7  \
 |    \     |    \
 |     \    |     \
 |      \9  |2     \5
 |0      \  |       \
 |  5  3  \ |  5  4  \
(4)--------(3)-------(5)
  \                  /
   \                /2
    \7             /
     \            /
      \          /
       \        /
        \0     /0
         \    /
          \  /
           (6)

Furthermore we make the somewhat artificial assumption that
the only "exits" from the freeway system are at intersection 6
(the sink) and the only "onramps" are at intersection 1 (the source)
<b>and no rest stops are permitted!</b>
Above

    6     0
(1)---------(2)

Indicates that intersection 1 is connected by a freeway
to intersection 2 and the maximum cars-per-hour from 1 to 2
is 6000 and the maximum from 2 to 1 is 0.

The network maximum flow problem is to determine the maximum
flow assignment for a network.  In the above network we want to
determine
the maximal number of cars per hour that can pass across the network
(without stopping) entering at intersection 1 and leaving at
intersection 6.

Using MPM.py this model may be encoded and maximized as follows:

def test2():
    D = {}
    # 6000 cars/hour can travel from intersection 1 to intersection 2
    D[1,2] = 6000
    D[1,3] = 5000
    D[1,4] = 3000
    D[2,3] = 7000 #capacities from intersection 2
    D[2,5] = 4000
    D[3,2] = 2000 #capacities from intersection 3
    D[3,1] = 9000
    D[3,2] = 2000
    D[3,4] = 3000
    D[3,5] = 5000
    D[4,3] = 5000 #capacities from intersection 4
    D[4,6] = 7000
    D[5,3] = 4000 #capacities from intersection 5
    D[5,6] = 2000
    (total, flow, net) = maxflow(source=1, sink=6, capacities=D)
    print "maximum at", total, "cars per hour"
    print "travelling"
    edges = flow.keys()
    edges.sort()
    for edge in edges:
        (i1, i2) = edge
        fl = flow[edge]
        if fl>0:
           print fl, "cars from intersection", i1, "to", i2

When executed the function prints

maximum at 8000 cars per hour
travelling
5000 cars from intersection 1 to 3
3000 cars from intersection 1 to 4
3000 cars from intersection 3 to 4
2000 cars from intersection 3 to 5
6000 cars from intersection 4 to 6
2000 cars from intersection 5 to 6

Thus the following flow assignment maximizes conservative flow
on the network:

     0   0
(1)--------(2)
 | \        | \
 |  \5      |  \0
 |3  \      |0  \
 |    \     |    \
 |     \    |     \
 |      \0  |0     \0
 |0      \  |       \
 |  0  3  \ |  2  0  \
(4)--------(3)-------(5)
  \                  /
   \                /
    \6             /2
     \            /
      \          /
       \        /
        \0     /0
         \    /
          \  /
           (6)

Please look at http://www.pythonpros.com/arw/MPM for
more information and downloads.

   -- Aaron Watters
===
"To repeat that, this time a little more slowly..." -Wilf