[boost] [graph] incremental_components bug

From: Chris Weed (chrisweed_at_[hidden])
Date: 2006-11-17 23:52:18

Hi,
I have submitted this once before, and I didn't get any response.

I am trying to use incremental connected components to find the
connected components of an image as I randomly add pixels to the
image. The graph is updated by adding edges between the added pixel
and it's four neighbors (2,3 neighbors on the image edges).
I calculate the number of components after each pixel is added.
This crashes when I try to create the component_index at line 70 on
windows using vc-8.0.
Any help would be greatly appreciated.
This code works when I use regular connected_components.
Thanks,
Chris

#include <boost/graph/graph_utility.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/pending/disjoint_sets.hpp>
#include <boost/graph/incremental_components.hpp>
#include <algorithm>
#include <numeric>
#include <boost/multi_array.hpp>

int main()
{

 // Image size
 size_t width = 100;
 size_t height = 100;

 // Create vector of randomized indices
 std::vector<size_t> indices(width*height,1);
 indices[0] = 0;
 std::partial_sum(indices.begin(),indices.end(),indices.begin());
 std::random_shuffle(indices.begin(),indices.end());

 // Create image which holds which pixels were stored by their linear index
 boost::multi_array<size_t,2> added_pixels(boost::extents[height][width]);
 for(size_t i=0;i<height;++i)
 for(size_t j=0;j<width;++j)
   added_pixels[i][j] = 0;

 using namespace boost;
 typedef adjacency_list<vecS,vecS,undirectedS> Graph;
 typedef graph_traits<Graph>::vertex_descriptor Vertex;
 typedef graph_traits<Graph>::vertices_size_type size_type;
 Graph G(indices.size());

 std::vector<size_type> rank(num_vertices(G));
 std::vector<Vertex> parent(num_vertices(G));
 typedef size_type* Rank;
 typedef Vertex* Parent;
 disjoint_sets<Rank,Parent> ds(&rank[0],&parent[0]);
 initialize_incremental_components(G,ds);
 incremental_components(G,ds);

 // Loop over indices and add pixels to image, and edges to graph
 std::vector<size_t>::iterator b_iter = indices.begin();
 for(;b_iter!=indices.end();++b_iter)
 {
   size_t r = (*b_iter)/width;
   size_t c = (*b_iter)%width;
   size_t j = *b_iter;
   added_pixels[r][c] = j;
   if(r>0 && added_pixels[r-1][c])
   {
     add_edge(j,added_pixels[r-1][c],G);
     ds.union_set(j,added_pixels[r-1][c]);
   }
   if(r<(height-1) && added_pixels[r+1][c])
   {
     add_edge(j,added_pixels[r+1][c],G);
     ds.union_set(j,added_pixels[r+1][c]);
   }
   if(c>0 && added_pixels[r][c-1])
   {
     add_edge(j,added_pixels[r][c-1],G);
     ds.union_set(j,added_pixels[r][c-1]);
   }
   if(c<(width-1) && added_pixels[r][c+1])
   {
     add_edge(j,added_pixels[r][c+1],G);
     ds.union_set(j,added_pixels[r][c+1]);
   }
   // After each pixel is added and connected, compute the number of cc's
   typedef component_index<unsigned int> Components;
   Components comp(parent.begin(),parent.end());
   std::cout <<  comp.size() << std::endl;
 }

 return 0;
}