Re: [Boost-users] [BGL] maximum flow through push_relabel_max_flow

10 Oct 2007


      On 10/8/07, "Alejandro M. Aragón"  wrote:
...
Aaron Windsor wrote:
...
On 10/7/07, "Alejandro M. Aragón"  wrote:
...
Aaron Windsor wrote:
...
On 10/7/07, "Alejandro M. Aragón"  wrote:
...
Hello all,
I've been working with the Edmunds & Karp maximum flow algorithm in the
BGL for some time without any problems. However, I realized that I could
do better in time complexity by moving to the push_relabel_max_flow
algorithm so I gave it a try. I've been trying to figure out what the
problem with my code is for the entire day without success. I was
wondering if someone could tell me what is my mistake.
It is a very simple problem, four vertices, four edges, the result from
the algorithm should be two:
2--------1
    |        |
    |        |
    |        |
    0--------3
Source is 0, target is 1, all edges have unit capacity. The code is:
<snip>
...
...
...
Hi Alejandro,
...
From the output above, it looks like the input graph does have max
flow 0 between vertices 0 and 1. The only edges with non-zero capacity
are (0,2), (0,3), (1,2) and (1,3), so there isn't even a path with
non-zero capacity between 0 and 1. If you want a graph with flow 2
between vertices 0 and 1, you would need to give capacity 1 to (0,2),
(0,3), (2,1), and (3,1). So, it looks like it's a problem in
translating between the two graph types you're using.
Regards,
Aaron
Oh, I see. Thanks Aaron for replying. Well, the thing is that I'm
translating the graph from an undirected graph. Now I understand that it
previously worked with the Edumnds & Karp algorithm because both
capacities are assigned a unit value. I don't really have a way to
determine the right direction of the edges. Is there a work around this
so I can still use the algorithm with lower complexity? If not I guess
that I better use the old code... =/
I don't know enough about your problem to suggest a workaround. For
instance, why can you not just start with the directed graph in the
first place? If you know at some point the correct capacities and
directions of the edges, there should be a way to construct a graph
that's usable without going through an intermediary undirected graph
and losing all of that information.
Also, in the example you gave, if you just allowed all edges to have
unit capacity, you would have gotten a max flow of 2 from vertex 0 to
vertex 1 - but maybe you're not just dealing with unit capacity graphs
in general.
Regards,
Aaron
Well, I tried that in the beginning but I got a segmentation fault at
the point of the call to the push_relabel_max_flow algorithm. Then I
read in the documentation that I have to assign a zero capacity to the
reverse edge and then I had no more segmentation faults. If I could
assign a unit capacity to all edges, even reverse edges as I do in the
Edmunds & Karp algorithm, that would be perfect. Is this segmentation
fault a bug in the algorithm?
About the directed graph, my problem is basically to find the direction
of the flow so I cannot assign directions a priori.
You're right - the documentation does say that reverse edges need to
have 0 capacity for the Push-Relabel algorithm. Stephan Diederich
added a nice implementation of Kolmogorov's algorithm for max flow to
the BGL recently - in tests, it was shown to be comparable to the
push-relabel algorithm and even outperformed it in some cases. It also
has the advantage of not restricting reverse edges to 0 capacity. It's
going to be released in Boost 1.35, but you could pull it from our
subversion repository now if you'd like.

Regards,
Aaron