Subject: Re: [Boost-users] [BGL] Question about push_relabel_max_flow
From: Matthias Linkenheil <[email-masked]>
To: [email-masked]
Date: Fri, 18 Mar 2005 13:10:21 +0000

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

}
_______________________________________________
Boost-users mailing list
[email-masked]
http://lists.boost.org/mailman/listinfo.cgi/boost-users