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

From: Matthias Linkenheil (m.linkenheil_at_[hidden])
Date: 2005-03-22 04:36:03

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.

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.

Thanks,

M. Linkenheil