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

From: Alejandro M. Aragón (aaragon2_at_[hidden])
Date: 2007-10-08 10:42:44

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.

a²