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; }