[Boost-users] [graph] incremental_components

From: Chris Weed (chrisweed_at_[hidden])
Date: 2006-10-29 22:26:14

Hi,
I am trying to use incremental connected components to find the
connected components of an image as I randomly add pixels to the
image. I calculate the number of components after each pixel is added.
This crashes part way through. Any help would be greatly appreciated.

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