[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 <stdlib.h> #include <stdio.h> #include <iostream> #include <fstream> #include <math.h> using namespace std; struct cap_typ{ double cap; double inv_cap; }; const x_size = 6; const y_size = 6; struct grey_values_typ{ int grey_value_base; int grey_value_neighb; }; class intensity { public: int picture [x_size][y_size]; intensity(void); struct cap_typ get_cap_right(int base, int right); struct cap_typ get_cap_below(int base, int below); ~intensity(void); private: struct grey_values_typ *g_ptr; struct cap_typ *c_ptr; struct grey_values_typ *gr_va_ptr; struct grey_values_typ get_grey_values_right(int base, int right); struct grey_values_typ get_grey_values_below(int base, int below); double get_capacity(int grey_value_p, int grey_value_q); }; #include <boost/config.hpp> #include <iostream> #include <vector> #include <utility> #include <string> #include <boost/graph/adjacency_list.hpp> #include <boost/property_map.hpp> #include <boost/graph/edmunds_karp_max_flow.hpp> #include <boost/graph/push_relabel_max_flow.hpp> #include <boost/graph/filtered_graph.hpp> #include <boost/graph/graph_utility.hpp> #include <boost/graph/breadth_first_search.hpp> #include <boost/graph/visitors.hpp> #include <stdlib.h> #include <stdio.h> #include "intensity.h" /***************************************************************************************/ int main(int , char* []) { using namespace boost; using namespace std; intensity myintensity; int node_nr = 0; int below = 0; int right = 0; int matrix_counter = 0; bool in1, in2; struct cap_typ *cap_ptr; cap_ptr = new struct cap_typ; typedef adjacency_list_traits<vecS, vecS, directedS> Traits; typedef property<vertex_index_t, int> VertexProperties; typedef property<edge_capacity_t, double, property<edge_residual_capacity_t, double, property<edge_reverse_t, Traits::edge_descriptor> > > EdgeProperties; typedef adjacency_list<vecS, vecS, directedS, VertexProperties, EdgeProperties > Graph; typedef graph_traits<Graph>::edge_descriptor edge_descriptor; typedef graph_traits<Graph>::vertex_descriptor vertex_descriptor; const int V = x_size*y_size; Graph g(V); property_map<Graph, vertex_index_t>::type vid = get(vertex_index, g); property_map<Graph, edge_capacity_t>::type cap = get(edge_capacity, g); property_map<Graph, edge_reverse_t>::type rev_edge = get(edge_reverse, g); property_map<Graph, edge_residual_capacity_t >::type res_cap = get(edge_residual_capacity, g); edge_descriptor e1, e2; matrix_counter = 0; while (matrix_counter < ((x_size*y_size)-x_size-1)){ for (int spalten_counter = 0; spalten_counter <= (x_size-2); ++spalten_counter){ node_nr = matrix_counter; right = matrix_counter + 1; below = matrix_counter + x_size; *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; } *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; } ++matrix_counter; } matrix_counter = (x_size-1); for (int zeilen_counter = 0; zeilen_counter <= (y_size-2); ++zeilen_counter){ node_nr = matrix_counter; below = matrix_counter + x_size; *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 + x_size; } graph_traits<Graph>::vertex_iterator i, end; graph_traits<Graph>::out_edge_iterator ei1, edge_end; for (boost::tie(i,end) = vertices(g); i != end; ++i) { cout << vid[*i] << " "; for (boost::tie(ei1,edge_end) = out_edges(*i, g); ei1 != edge_end; ++ei1) cout << " --" << cap[*ei1] << "--> " << vid[target(*ei1, g)] << " "; cout << endl; } graph_traits<Graph>::vertex_descriptor s, t; s = vertex(0 , g); t = vertex(28 , g); //double flow = edmunds_karp_max_flow(g, s, t); double flow = push_relabel_max_flow(g, s, t); cout<<"max flow :"<<flow<<endl; char h; cout<<"end"<<endl; cin >> h; return 0; } When using the push_relabel_max_flow algorithm on a 2D grid graph an access violation in push_relabel_max_flow.hpp line 554 occurs. #include "intensity.h" intensity::intensity(void) { g_ptr = new struct grey_values_typ; c_ptr = new struct cap_typ; gr_va_ptr = new struct grey_values_typ; for (int m=0; m<y_size; ++m){ for (int n=0; n<x_size; ++n){ if (m <= (y_size/2)-1) picture [n][m] = 255; else picture [n][m] = 0; } } } struct cap_typ intensity::get_cap_right(int base, int right) { *gr_va_ptr=get_grey_values_right(base, right); c_ptr->cap = get_capacity(gr_va_ptr->grey_value_base, gr_va_ptr->grey_value_neighb); c_ptr->inv_cap = get_capacity(gr_va_ptr->grey_value_neighb, gr_va_ptr->grey_value_base); return *c_ptr; } struct cap_typ intensity::get_cap_below(int base, int below) { *gr_va_ptr=get_grey_values_below(base, below); c_ptr->cap = get_capacity(gr_va_ptr->grey_value_base, gr_va_ptr->grey_value_neighb); c_ptr->inv_cap = get_capacity(gr_va_ptr->grey_value_neighb, gr_va_ptr->grey_value_base); return *c_ptr; } struct grey_values_typ intensity::get_grey_values_right(int base, int right){ int xPos; int yPos; int xPos_hilfsvar; xPos = base % x_size; yPos = base / y_size; xPos_hilfsvar = xPos; g_ptr->grey_value_base = picture[xPos][yPos]; ++xPos_hilfsvar; g_ptr->grey_value_neighb = picture[xPos_hilfsvar][yPos]; return *g_ptr; } struct grey_values_typ intensity::get_grey_values_below(int base, int below){ int xPos; int yPos; int yPos_hilfsvar; xPos = base % x_size; yPos = base / y_size; yPos_hilfsvar = yPos; g_ptr->grey_value_base = picture[xPos][yPos]; ++yPos_hilfsvar; g_ptr->grey_value_neighb = picture[xPos][yPos_hilfsvar]; return *g_ptr; } double intensity::get_capacity(int grey_value_p, int grey_value_q){ const sigma = 1; const k = 1; return k * exp(-(pow((grey_value_q - grey_value_p), 2)/pow(sigma, 2))); } intensity::~intensity(void) { delete g_ptr; delete c_ptr; delete gr_va_ptr; }
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<char,'8','9','.','4','5'> eightyninepointfourfive; typedef mpl::vector_c<char,'2','4','.','1','1'> twentyfourpointoneone; typedef mpl::vector<eightyninepointfourfive, twentyfourpointoneone> floatseq; // idea 2 template<int INTEGRAL, int DECIMAL> struct float_ : mpl::pair<mpl::integral_c<int, INTEGRAL>, mpl::integral_c<int, DECIMAL> > { }; typedef mpl::vector<float_<89, 45>, float_<24,11> > floataspairseq; typedef float_<89,45>::first the89part; typedef float_<89,45>::second the45part; // end ideas What do you think of these ideas? I am assuming that there must be other solutions and perhaps these are not the best. Wanted to bounce these of the list for comments. Thanks in advance. Regards, Bruce
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