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@lists.boost.org 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