https://svn.boost.org/trac10/ticket/268 <pre class="wiki">I am trying to understand why the order in which I add edges to an adjacency_list graph has some effect on the connected components I get using incremental_components. Using the listing below, with Boost release 1.30.0 (also 1.31.0) with g++ 2.95 (cygwin) I get the following: &gt; g++ -I./boost_1_31_0 -o ok -ftemplate-depth-40 incremental-components-eg-bug.cpp &gt; ./ok rank[0] = 0 rank[1] = 0 rank[2] = 0 rank[3] = 1 rank[4] = 0 parent[0] = 3 parent[1] = 3 parent[2] = 3 parent[3] = 3 parent[4] = 3 component 0 contains: 4 3 2 1 0 This is what I expect. If I change the order in which I add edges to the graph, I get a different answer: &gt; g++ -I./boost_1_31_0 -DSHOWBUG -o bug -ftemplate- depth-40 incremental-components-eg-bug.cpp &gt; ./bug rank[0] = 0 rank[1] = 0 rank[2] = 1 rank[3] = 2 rank[4] = 0 parent[0] = 3 parent[1] = 2 parent[2] = 3 parent[3] = 3 parent[4] = 3 component 0 contains: 4 3 2 0 This is not what I expect. The single connected component has lost a vertex. But it should be the same graph, the only difference being the order in which I called add_edge(). Is this a bug or a misunderstanding on my part? Any advice would be appreciated... Jeff #include &lt;iostream&gt; #include &lt;vector&gt; #include &lt;algorithm&gt; #include &lt;utility&gt; #include &lt;boost/graph/adjacency_list.hpp&gt; #include &lt;boost/pending/disjoint_sets.hpp&gt; #include &lt;boost/graph/incremental_components.hpp&gt; int main(int, char *[]) { using namespace boost; // Create a graph typedef adjacency_list &lt; vecS, vecS, undirectedS &gt; Graph; typedef graph_traits &lt; Graph &gt;::vertex_descriptor Vertex; const int N = 5; Graph G(N); add_edge(0, 3, G); add_edge(0, 4, G); #ifndef SHOWBUG add_edge(1, 4, G); add_edge(1, 2, G); #else add_edge(1, 2, G); add_edge(1, 4, G); #endif // create the disjoint-sets object, which requires rank and parent vertex properties std::vector &lt; Vertex &gt; rank(num_vertices(G)); std::vector &lt; Vertex &gt; parent(num_vertices(G)); typedef graph_traits&lt;Graph&gt;::vertices_size_type* Rank; typedef Vertex* Parent; disjoint_sets &lt; Rank, Parent &gt; ds(&amp;rank[0], &amp;parent [0]); // determine the connected components, storing the results in the disjoint-sets object initialize_incremental_components(G, ds); incremental_components(G, ds); for (unsigned int i = 0; i &lt; rank.size(); ++i) { std::cout &lt;&lt; "rank[" &lt;&lt; i &lt;&lt; "] = " &lt;&lt; rank[i] &lt;&lt; std::endl; } for (unsigned int i = 0; i &lt; parent.size(); ++i) { std::cout &lt;&lt; "parent[" &lt;&lt; i &lt;&lt; "] = " &lt;&lt; parent[i] &lt;&lt; std::endl; } typedef component_index &lt; unsigned int &gt;Components; Components components(parent.begin(), parent.end()); for (Components::size_type i = 0; i &lt; components.size (); ++i) { std::cout &lt;&lt; "component " &lt;&lt; i &lt;&lt; " contains: "; for (Components::value_type::iterator j = components [i].begin(); j != components[i].end(); ++j) std::cout &lt;&lt; *j &lt;&lt; " "; std::cout &lt;&lt; std::endl; } return EXIT_SUCCESS; } </pre> en-us /htdocs/site/boost.png https://svn.boost.org/trac10/ticket/268 Trac 1.4.3 nobody Wed, 12 May 2004 17:21:18 GMT https://svn.boost.org/trac10/ticket/268#comment:2 https://svn.boost.org/trac10/ticket/268#comment:2 <ul> <li><strong>status</strong> <span class="trac-field-old">assigned</span> → <span class="trac-field-new">closed</span> </li> </ul> <pre class="wiki">Logged In: YES user_id=249098 This is actually not a bug. The problem is that, before using component_index to figure out what components exist, one needs to perform a "find_set" on each vertex to compress the representation. For instance, the example code does this: graph_traits&lt;Graph&gt;::vertex_iterator i,end; for (boost::tie(i, end) = vertices(G); i != end; ++i) cout &lt;&lt; "representative[" &lt;&lt; *i &lt;&lt; "] = " &lt;&lt; ds.find_set(*i) &lt;&lt; endl;; cout &lt;&lt; endl; Alternatively, one can use the "compress_sets" function in the disjoint sets data structure to do this more easily, e.g., ds.compress_sets(vertices(g).first, vertices(g).second); There is arguably a problem with the interface to incremental components because this is a subtle issue, but we should address that separately. </pre> Ticket