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

From: Aaron Windsor (aaron.windsor_at_[hidden])
Date: 2007-10-08 07:59:28

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