Re: [Boost-users] [BGL] Question about push_relabel_max_flow

From: Doug Gregor (dgregor_at_[hidden])
Date: 2005-03-23 14:32:28

On Mar 22, 2005, at 4:36 AM, Matthias Linkenheil wrote:

> Doug Gregor schrieb:
>
>>
>> I'm not sure if the initialization of the graph is correct for the 
>> max-flow algorithms. For each edge (u, v) the graph needs an edge (v, 
>> u) such that the rev_edge map maps back and forth (okay so far) and 
>> the capacity of (v, u) is zero (I'm just quoting from the 
>> push_relabel_max_flow docs). However, it looks like the capacity of 
>> the reverse edge (called "e2" in the above snippets) is always set to 
>> cap_ptr->inv_cap, which is not necessarily zero. If I change the 
>> capacity of these reverse edges to 0, the example completes and gives 
>> a max_flow of 0 (with both max-flow algorithms). However, I don't 
>> have enough of an understanding of max-flow problems to know whether 
>> that is a reasonably answer or not :(
>>
>>     Doug
>>
>> _______________________________________________
>> Boost-users mailing list
>> Boost-users_at_[hidden]
>> http://lists.boost.org/mailman/listinfo.cgi/boost-users
>>
> Hello,
>
> you are right. I'm sorry because I read over this important condition 
> that the capacity of the reverse edge must be 0.
> But I'm a little bit surprised, that the edmunds_karp_max_flow 
> algorithm works also without these condition.

I'm actually a bit surprised that edmunds_karp_max_flow actually 
works... it's documented to require the same kind of input as 
push_relabel_max_flow, with reverse edges of zero capacity.

> My problem is that I need reverse edges in my graph, that have also 
> capacities different from zero.
> So I can't use the push_relabel_max_flow algorithm and the 
> edmunds_karp_max_flow algorithm is too slow.

I can't tell if the algorithms support parallel edges, but if they do 
you could start with your current graph (has edges in both directions) 
and then add reverse edges with capacity zero.

        Doug