Re: [boost] [graph] incremental_components bug

From: Chris Weed (chrisweed_at_[hidden])
Date: 2006-11-19 15:11:19

On 11/18/06, Aaron Windsor <aaron.windsor_at_[hidden]> wrote:
> On 11/17/06, Chris Weed <chrisweed_at_[hidden]> 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