Re: [Boost-users] [BGL] Question about push_relabel_max_flow

From: Matthias Linkenheil (m.linkenheil_at_[hidden])
Date: 2005-03-18 08:10:25

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_at_[hidden]
> 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;

}