[BGL] Question about push_relabel_max_flow
Hello, I used the edmunds_karp_max_flow algorithm in my project and it worked fine. Then I changed it to the push_relabel_max_flow algorithm but it doesn't work. I get an access violation at line 562 in the push_relabel_max_flow.hpp . Have anyone an idea where the problem could be? Line 558 - line 565 of push_relabel_max_flow.hpp : // do the bottom u = bos; ai = out_edges(u, g).first; while (excess_flow[u] > 0) { if (capacity[*ai] == 0 && is_residual_edge(*ai)) push_flow(*ai); ++ai; } Thanks, Matthias
On Feb 25, 2005, at 4:50 AM, Matthias Linkenheil wrote:
Hello,
I used the edmunds_karp_max_flow algorithm in my project and it worked fine. Then I changed it to the push_relabel_max_flow algorithm but it doesn't work. I get an access violation at line 562 in the push_relabel_max_flow.hpp .
Have anyone an idea where the problem could be?
Line 558 - line 565 of push_relabel_max_flow.hpp : // do the bottom u = bos; ai = out_edges(u, g).first; while (excess_flow[u] > 0) { if (capacity[*ai] == 0 && is_residual_edge(*ai)) push_flow(*ai); ++ai; }
That's an odd bit of code... "ai" is never checked against the end iterator (out_edges(u, g).second). Could you put in "assert(ai != out_edges(u, g).second);" as the first line of the while loop, to see if that's what's happening? Doug
Hi, okay, "ai" is not checked against the end iterator because the assert function is called. I don't know how to fix this problem so that the max flow result is right. Suggestions are welcome? Thanks, Matthias Linkenheil Doug Gregor schrieb:
On Feb 25, 2005, at 4:50 AM, Matthias Linkenheil wrote:
Hello,
I used the edmunds_karp_max_flow algorithm in my project and it worked fine. Then I changed it to the push_relabel_max_flow algorithm but it doesn't work. I get an access violation at line 562 in the push_relabel_max_flow.hpp .
Have anyone an idea where the problem could be?
Line 558 - line 565 of push_relabel_max_flow.hpp : // do the bottom u = bos; ai = out_edges(u, g).first; while (excess_flow[u] > 0) { if (capacity[*ai] == 0 && is_residual_edge(*ai)) push_flow(*ai); ++ai; }
That's an odd bit of code... "ai" is never checked against the end iterator (out_edges(u, g).second). Could you put in "assert(ai != out_edges(u, g).second);" as the first line of the while loop, to see if that's what's happening?
Doug
_______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
On Mar 10, 2005, at 12:09 PM, Matthias Linkenheil wrote:
okay, "ai" is not checked against the end iterator because the assert function is called. I don't know how to fix this problem so that the max flow result is right.
Suggestions are welcome?
Do you happen to have a graph that illustrates the problem? I'm not very familiar with the algorithm itself, so a failing test case would really help us debug it. I've submitted a Sourceforge bug report to track progress on this problem. Doug
Douglas Gregor schrieb:
On Mar 10, 2005, at 12:09 PM, Matthias Linkenheil wrote:
okay, "ai" is not checked against the end iterator because the assert function is called. I don't know how to fix this problem so that the max flow result is right.
Suggestions are welcome?
Do you happen to have a graph that illustrates the problem? I'm not very familiar with the algorithm itself, so a failing test case would really help us debug it. I've submitted a Sourceforge bug report to track progress on this problem.
Doug
_______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
Hello,
I used a 2D grid graph, when the access violation in the
push_relabel_max_flow algorithm occurs.
A failing test case is attached to this mail.
Perhaps it could help to debug this problem.
Regards,
M. Linkenheil
#pragma once
#include
On Mar 18, 2005, at 8:10 AM, Matthias Linkenheil wrote:
tie(e1, in1) = add_edge(vertex(node_nr, g), vertex(right, g), g); tie(e2, in2) = add_edge(vertex(right, g), vertex(node_nr, g), g); if (in1 && in2){ cap[e1] = cap_ptr->cap; cap[e2] = cap_ptr->inv_cap; rev_edge[e1] = e2; rev_edge[e2] = e1; }
*cap_ptr=myintensity.get_cap_below(node_nr, below);
tie(e1, in1) = add_edge(vertex(node_nr, g), vertex(below, g), g); tie(e2, in2) = add_edge(vertex(below, g), vertex(node_nr, g), g); if (in1 && in2){ cap[e1] = cap_ptr->cap; cap[e2] = cap_ptr->inv_cap; rev_edge[e1] = e2; rev_edge[e2] = e1; } ++matrix_counter; } ++matrix_counter; } matrix_counter = ((x_size*y_size)-x_size); for (int spalten_counter = 0; spalten_counter <= (x_size-2); ++spalten_counter){ node_nr = matrix_counter; right = matrix_counter + 1;
*cap_ptr=myintensity.get_cap_right(node_nr, right);
tie(e1, in1) = add_edge(vertex(node_nr, g), vertex(right, g), g); tie(e2, in2) = add_edge(vertex(right, g), vertex(node_nr, g), g); if (in1 && in2){ cap[e1] = cap_ptr->cap; cap[e2] = cap_ptr->inv_cap; rev_edge[e1] = e2; rev_edge[e2] = e1; }
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
Hello,
I need to create a sequence of float values that the user can put in at
compile time. Since floats cannot be used as template params I am
assuming I cannot use vector_c in any way.
My plan was to have the user input the initial float values as
mpl::vector<char> and then convert the chars to string and then the
string to float when I needed to use it at runtime. My other idea was
to make a struct that inherited from mpl::pair and have the first part
be the integral part and the second part be the decimal part and again,
construct the float from that.
So the two ideas look something like:
// idea 1 - a bit odd but need to get around C++ on this one
typedef mpl::vector_c
Bruce Trask writes:
I need to create a sequence of float values that the user can put in at compile time. Since floats cannot be used as template params I am assuming I cannot use vector_c in any way.
Correct.
My plan was to have the user input the initial float values as mpl::vector<char> and then convert the chars to string and then the string to float when I needed to use it at runtime.
From a user standpoint, this one sounds somewhat painful.
My other idea was to make a struct that inherited from mpl::pair and have the first part be the integral part and the second part be the decimal part and again, construct the float from that.
Been there, please see http://article.gmane.org/gmane.comp.lib.boost.devel/103064.
So the two ideas look something like:
[snip code]
What do you think of these ideas?
I am assuming that there must be other solutions and perhaps these are not the best.
I think "the best" here heavily depends on the particular details of your application for the whole thing. For instance, if you need compile-time arithmetics on these, the "decimal" representation would probably be the easiest one to build a prototype for. On the other hand, if expect your users to enter a lot of these numbers, you might want to reconsider at least the interface part -- et cetera. Be sure to check Cromwell Enage's work on the subject: http://thread.gmane.org/gmane.comp.lib.boost.devel/103302. HTH, -- Aleksey Gurtovoy MetaCommunications Engineering
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
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
participants (5)
-
Aleksey Gurtovoy -
Bruce Trask -
Doug Gregor -
Douglas Gregor -
Matthias Linkenheil