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
#include
#include <iostream>
#include <fstream>
#include
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
#include <iostream>
#include <vector>
#include <utility>
#include <string>
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#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 Traits;
typedef property VertexProperties;
typedef property > > EdgeProperties;
typedef adjacency_list 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::type vid = get(vertex_index, g);
property_map::type cap = get(edge_capacity, g);
property_map::type rev_edge = get(edge_reverse, g);
property_map::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 :"<> 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; mcap = 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;
}
