[graph] incremental_components bug
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; }
On 11/17/06, Chris Weed <chrisweed@gmail.com> wrote:
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.
Hi Chris, I was able to replicate the crash under gcc as well. Unfortunately, this looks like a bug in the component_index implementation. The disjoint sets data structure used by the incremental connected components algorithm is arranged as a forest of trees. To figure out what set a node is in, you just follow parent links in whatever tree that node belongs to until you reach the root of that tree, and the root serves as a canonical element for that set. To union two sets together, you set the root of one tree to point to the root of the other tree as its parent. An important optimization to this data structure is performed every time you do a find_set(v): after finding the canonical element in v's set, all of the parent pointers on the path from v to the canonical element in v's tree are reset to point directly to v. So, the trees tend to get flattened out as find_set operations are performed. The reason I'm going into all of this background is that there's a certain point in the component_index construction that seems to assume that the disjoint sets are all completely flat (lines 66-70 of graph/detail/incremental_components.hpp.) Until I can put a patch together, you can work around this by flattening out the tree "manually" by calling ds.find_set(v) on each vertex in the graph before you construct the component_index. If I add the following lines to your code directly before you create the index your code runs fine: graph_traits<Graph>::vertex_iterator vi, vi_end; for(tie(vi,vi_end) = vertices(G); vi != vi_end; ++vi) ds.find_set(*vi); But the above loop (as well as the construction of the component_index) takes linear time in the number of vertices in the graph, and you're using it just to figure out the number of components in the graph. There's an easier way of doing this: just keep a running total (starting with num_components = num_vertices.) You can detect when the number of components is going to decrease by one by calling find_set on each of the vertices you're about to call union_set on - if the vertices are in different sets, decrease the number of components. Regards, Aaron
On 11/18/06, Aaron Windsor <aaron.windsor@gmail.com> wrote:
On 11/17/06, Chris Weed <chrisweed@gmail.com> wrote:
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.
Hi Chris,
I was able to replicate the crash under gcc as well. Unfortunately, this looks like a bug in the component_index implementation.
The disjoint sets data structure used by the incremental connected components algorithm is arranged as a forest of trees. To figure out what set a node is in, you just follow parent links in whatever tree that node belongs to until you reach the root of that tree, and the root serves as a canonical element for that set. To union two sets together, you set the root of one tree to point to the root of the other tree as its parent. An important optimization to this data structure is performed every time you do a find_set(v): after finding the canonical element in v's set, all of the parent pointers on the path from v to the canonical element in v's tree are reset to point directly to v. So, the trees tend to get flattened out as find_set operations are performed.
The reason I'm going into all of this background is that there's a certain point in the component_index construction that seems to assume that the disjoint sets are all completely flat (lines 66-70 of graph/detail/incremental_components.hpp.) Until I can put a patch together, you can work around this by flattening out the tree "manually" by calling ds.find_set(v) on each vertex in the graph before you construct the component_index. If I add the following lines to your code directly before you create the index your code runs fine:
graph_traits<Graph>::vertex_iterator vi, vi_end; for(tie(vi,vi_end) = vertices(G); vi != vi_end; ++vi) ds.find_set(*vi);
But the above loop (as well as the construction of the component_index) takes linear time in the number of vertices in the graph, and you're using it just to figure out the number of components in the graph. There's an easier way of doing this: just keep a running total (starting with num_components = num_vertices.) You can detect when the number of components is going to decrease by one by calling find_set on each of the vertices you're about to call union_set on - if the vertices are in different sets, decrease the number of components.
Hi Aaron, Thanks for the information. I realize my example isn't particularly useful or efficient. It was just a sample program to localize the problem. However, I think your hack should fix my algorithm, until this code is patched. Thanks again, Chris
participants (2)
-
Aaron Windsor -
Chris Weed