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

From: Aaron Windsor (aaron.windsor_at_[hidden])
Date: 2007-10-10 08:35:06

On 10/8/07, "Alejandro M. Aragón" <aaragon2_at_[hidden]> wrote:
> Aaron Windsor wrote:
> > On 10/7/07, "Alejandro M. Aragón" <aaragon2_at_[hidden]> wrote:
> >> Aaron Windsor wrote:
> >>> On 10/7/07, "Alejandro M. Aragón" <aaragon2_at_[hidden]> 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