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. 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