From: Aaron Windsor (aaron.windsor_at_[hidden])
Date: 2006-11-18 23:45:09
On 11/17/06, Chris Weed <chrisweed_at_[hidden]> wrote:
> 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.
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)
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
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk