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