Re: Push relabel modification to show used paths (maxflow problem)

From: Glenn C. Rhoads (gcrhoads_at_yahoo.com)
Date: 11/14/04 

Date: 14 Nov 2004 14:59:58 -0800

soundman@gmx.de (Mirko Knoll) wrote in message news:<89c5c392.0411120122.22fe1a91@posting.google.com>...
> I'm currently trying to implement Goldberg's push relabel algorithm
> (PRF from http://www.avglab.com/andrew/soft.html) into our
> environment. But there are some points where I need advice:
>
> - how do I have to modify the algorithm to get the actual paths found
> and not only the flow ?

Regardless of the max-flow algorithm used, you can convert the flow
values on the arcs into flows on paths as follows. Start at your
source node s. Keeping following arcs with a positive flow out of
the current node until you reach your destination node (since the
flow is maximum, you won't run into a cycle). Now you have one path.
Let fmin be the minimum flow among the arcs on the path. Reduce the
flow value along every arc on the path by fmin. Now find the next
path on the resulting network in exactly the same way. Repeat until
you've taken care of all the flow going out of your source.

> - is it suitable to use the highest-level push relabel algorithm even
> for a unit capacity network with about 400 nodes and 2000 Edges ?

For unit capacity networks, there are algorithms with a better
time complexity. The best I know of is a hybrid algorithm that
does the shortest augmenting path algorithm until the flow value
is "close" to the solution, and then finishes it off with a
generic augmenting path algorithm. I don't know how much of a
difference this is likely to make on a 400 node, 2000 edge graph.

Relevant Pages