|
Boost : |
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;
}
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk