| <HTML> |
| <!-- |
| Copyright (c) Jeremy Siek, Lie-Quan Lee, and Andrew Lumsdaine 2000 |
| |
| Distributed under the Boost Software License, Version 1.0. |
| (See accompanying file LICENSE_1_0.txt or copy at |
| http://www.boost.org/LICENSE_1_0.txt) |
| --> |
| <Head> |
| <Title>Boost Graph Library: Incremental Connected Components</Title> |
| <style type="text/css"> |
| <!-- |
| .code |
| { |
| border-left-style: groove; |
| border-left-width: 1px; |
| padding-left: 2em; |
| } |
| |
| --> |
| </style> |
| |
| <BODY BGCOLOR="#ffffff" LINK="#0000ee" TEXT="#000000" VLINK="#551a8b" |
| ALINK="#ff0000"> |
| <IMG SRC="../../../boost.png" |
| ALT="C++ Boost" width="277" height="86"> |
| |
| <BR Clear> |
| |
| <H1>Incremental Connected Components</H1> |
| |
| <P> |
| This section describes a family of functions and classes that work |
| together to calculate the connected components of an undirected graph. |
| The algorithm used here is based on the disjoint-sets (fast |
| union-find) data structure [<A |
| HREF="bibliography.html#clr90">8</A>,<A |
| HREF="bibliography.html#tarjan83:_data_struct_network_algo">27</A>] |
| which is a good method to use for situations where the graph is |
| growing (edges are being added) and the connected components |
| information needs to be updated repeatedly. This method does not cover |
| the situation where edges are both added and removed from the graph, |
| hence it is called <b><i>incremental</i></b><a |
| href="bibliography.html#eppstein97:dynamic_graph">[42]</a> (and not |
| fully dynamic). The disjoint-sets class is described in Section <A |
| HREF="../../disjoint_sets/disjoint_sets.html">Disjoint Sets</A>. |
| |
| <P> |
| The following five operations are the primary functions that you will |
| use to calculate and maintain the connected components. The objects |
| used here are a graph <TT>g</TT>, a disjoint-sets structure <TT>ds</TT>, |
| and vertices <TT>u</TT> and <TT>v</TT>. |
| |
| <P> |
| |
| <UL> |
| <LI><TT>initialize_incremental_components(g, ds)</TT> |
| <BR> |
| Basic initialization of the disjoint-sets structure. Each |
| vertex in the graph <TT>g</TT> is in its own set. |
| </LI> |
| <LI><TT>incremental_components(g, ds)</TT> |
| <BR> |
| The connected components are calculated based on the edges in the graph |
| <TT>g</TT> and the information is embedded in <TT>ds</TT>. |
| </LI> |
| <LI><TT>ds.find_set(v)</TT> |
| <BR> |
| Extracts the component information for vertex <TT>v</TT> from the |
| disjoint-sets. |
| </LI> |
| <LI><TT>ds.union_set(u, v)</TT> |
| <BR> |
| Update the disjoint-sets structure when edge <i>(u,v)</i> is added to the graph. |
| </LI> |
| </UL> |
| |
| <P> |
| |
| <H3>Complexity</H3> |
| |
| <P> |
| The time complexity for the whole process is <i>O(V + E |
| alpha(E,V))</i> where <i>E</i> is the total number of edges in the |
| graph (by the end of the process) and <i>V</i> is the number of |
| vertices. <i>alpha</i> is the inverse of Ackermann's function which |
| has explosive recursively exponential growth. Therefore its inverse |
| function grows <I>very</I> slowly. For all practical purposes |
| <i>alpha(m,n) <= 4</i> which means the time complexity is only |
| slightly larger than <i>O(V + E)</i>. |
| |
| <P> |
| |
| <H3>Example</H3> |
| |
| <P> |
| Maintain the connected components of a graph while adding edges using |
| the disjoint-sets data structure. The full source code for this |
| example can be found in <a |
| href="../example/incremental_components.cpp"><TT>examples/incremental_components.cpp</TT></a>. |
| |
| <P> |
| <PRE class="code"> |
| using namespace boost; |
| |
| int main(int argc, char* argv[]) |
| { |
| typedef adjacency_list <vecS, vecS, undirectedS> Graph; |
| typedef graph_traits<Graph>::vertex_descriptor Vertex; |
| typedef graph_traits<Graph>::vertices_size_type VertexIndex; |
| |
| const int VERTEX_COUNT = 6; |
| Graph graph(VERTEX_COUNT); |
| |
| std::vector<VertexIndex> rank(num_vertices(graph)); |
| std::vector<Vertex> parent(num_vertices(graph)); |
| |
| typedef VertexIndex* Rank; |
| typedef Vertex* Parent; |
| |
| disjoint_sets<Rank, Parent> ds(&rank[0], &parent[0]); |
| |
| initialize_incremental_components(graph, ds); |
| incremental_components(graph, ds); |
| |
| graph_traits<Graph>::edge_descriptor edge; |
| bool flag; |
| |
| boost::tie(edge, flag) = add_edge(0, 1, graph); |
| ds.union_set(0,1); |
| |
| boost::tie(edge, flag) = add_edge(1, 4, graph); |
| ds.union_set(1,4); |
| |
| boost::tie(edge, flag) = add_edge(4, 0, graph); |
| ds.union_set(4,0); |
| |
| boost::tie(edge, flag) = add_edge(2, 5, graph); |
| ds.union_set(2,5); |
| |
| std::cout << "An undirected graph:" << std::endl; |
| print_graph(graph, get(boost::vertex_index, graph)); |
| std::cout << std::endl; |
| |
| BOOST_FOREACH(Vertex current_vertex, vertices(graph)) { |
| std::cout << "representative[" << current_vertex << "] = " << |
| ds.find_set(current_vertex) << std::endl; |
| } |
| |
| std::cout << std::endl; |
| |
| typedef component_index<VertexIndex> Components; |
| |
| // NOTE: Because we're using vecS for the graph type, we're |
| // effectively using identity_property_map for a vertex index map. |
| // If we were to use listS instead, the index map would need to be |
| // explicity passed to the component_index constructor. |
| Components components(parent.begin(), parent.end()); |
| |
| // Iterate through the component indices |
| BOOST_FOREACH(VertexIndex current_index, components) { |
| std::cout << "component " << current_index << " contains: "; |
| |
| // Iterate through the child vertex indices for [current_index] |
| BOOST_FOREACH(VertexIndex child_index, |
| components[current_index]) { |
| std::cout << child_index << " "; |
| } |
| |
| std::cout << std::endl; |
| } |
| |
| return (0); |
| } |
| </PRE> |
| |
| <P> |
| <hr> |
| <p> |
| |
| <H2><A NAME="sec:initialize-incremental-components"></A> |
| <TT>initialize_incremental_components</TT> |
| </H2> |
| |
| <P> |
| <DIV ALIGN="left"> |
| <TABLE CELLPADDING=3 border> |
| <TR><TH ALIGN="LEFT"><B>Graphs:</B></TH> |
| <TD ALIGN="LEFT">undirected</TD> |
| </TR> |
| <TR><TH ALIGN="LEFT"><B>Properties:</B></TH> |
| <TD ALIGN="LEFT">rank, parent (in disjoint-sets)</TD> |
| </TR> |
| <TR><TH ALIGN="LEFT"><B>Complexity:</B></TH> |
| <TD></TD> |
| </TR> |
| </TABLE> |
| </DIV> |
| |
| <P> |
| <PRE> |
| template <class VertexListGraph, class DisjointSets> |
| void initialize_incremental_components(VertexListGraph& G, DisjointSets& ds) |
| </PRE> |
| |
| <P> |
| This prepares the disjoint-sets data structure for the incremental |
| connected components algorithm by making each vertex in the graph a |
| member of its own component (or set). |
| |
| <P> |
| |
| <H3>Where Defined</H3> |
| |
| <P> |
| <a href="../../../boost/graph/incremental_components.hpp"><TT>boost/graph/incremental_components.hpp</TT></a> |
| |
| <p> |
| <hr> |
| <P> |
| |
| <H2><A NAME="sec:incremental-components"></A> |
| <TT>incremental_components</TT> |
| </H2> |
| |
| <P> |
| <DIV ALIGN="left"> |
| <TABLE CELLPADDING=3 border> |
| <TR><TH ALIGN="LEFT"><B>Graphs:</B></TH> |
| <TD ALIGN="LEFT">undirected</TD> |
| </TR> |
| <TR><TH ALIGN="LEFT"><B>Properties:</B></TH> |
| <TD ALIGN="LEFT">rank, parent (in disjoint-sets)</TD> |
| </TR> |
| <TR><TH ALIGN="LEFT"><B>Complexity:</B></TH> |
| <TD ALIGN="LEFT"><i>O(E)</i></TD> |
| </TR> |
| </TABLE> |
| </DIV> |
| |
| <p> |
| <PRE> |
| template <class EdgeListGraph, class DisjointSets> |
| void incremental_components(EdgeListGraph& g, DisjointSets& ds) |
| </PRE> |
| |
| <P> |
| This function calculates the connected components of the graph, |
| embedding the results in the disjoint-sets data structure. |
| |
| <P> |
| |
| <H3>Where Defined</H3> |
| |
| <P> |
| <a href="../../../boost/graph/incremental_components.hpp"><TT>boost/graph/incremental_components.hpp</TT></a> |
| |
| <P> |
| |
| <H3>Requirements on Types</H3> |
| |
| <P> |
| |
| <UL> |
| <LI>The graph type must be a model of <a href="./EdgeListGraph.html">EdgeListGraph</a>. |
| </LI> |
| </UL> |
| |
| <P> |
| <hr> |
| <p> |
| |
| <H2><A NAME="sec:same-component"> |
| <TT>same_component</TT></A> |
| </H2> |
| |
| <P> |
| <DIV ALIGN="left"> |
| <TABLE CELLPADDING=3 border> |
| <TR><TH ALIGN="LEFT"><B>Properties:</B></TH> |
| <TD ALIGN="LEFT">rank, parent (in disjoint-sets)</TD> |
| </TR> |
| <TR><TH ALIGN="LEFT"><B>Complexity:</B></TH> |
| <TD ALIGN="LEFT"><i>O(alpha(E,V))</i></TD> |
| </TR> |
| </TABLE> |
| </DIV> |
| |
| <P> |
| <PRE> |
| template <class Vertex, class DisjointSet> |
| bool same_component(Vertex u, Vertex v, DisjointSet& ds) |
| </PRE> |
| |
| <P> |
| This function determines whether <TT>u</TT> and <TT>v</TT> are in the same |
| component. |
| |
| <P> |
| |
| <H3>Where Defined</H3> |
| |
| <P> |
| <a href="../../../boost/graph/incremental_components.hpp"><TT>boost/graph/incremental_components.hpp</TT></a> |
| |
| <P> |
| |
| <H3>Requirements on Types</H3> |
| |
| <P> |
| |
| <UL> |
| <LI><TT>Vertex</TT> must be compatible with the rank and parent |
| property maps of the <TT>DisjointSets</TT> data structure. |
| </LI> |
| </UL> |
| |
| <P> |
| <hr> |
| <p> |
| |
| <H2><A NAME="sec:component-index"></A> |
| <TT>component_index</TT> |
| </H2> |
| |
| <p> |
| <PRE> |
| component_index<Index> |
| </PRE> |
| |
| <P> |
| The <tt>component_index</tt> class provides an STL |
| container-like view for the components of the graph. Each component is |
| a container-like object, and access is provided via |
| the <TT>operator[]</TT>. A <TT>component_index</TT> object is |
| initialized with the parents property in the disjoint-sets calculated |
| from the <TT>incremental_components()</TT> function. Optionally, a |
| vertex -> index property map is passed in |
| (<tt>identity_property_map</tt> is used by default). |
| |
| <P> |
| |
| <H3>Where Defined</H3> |
| |
| <P> |
| <a href="../../../boost/graph/incremental_components.hpp"><TT>boost/graph/incremental_components.hpp</TT></a> |
| |
| <P> |
| |
| <H3>Members</H3> |
| |
| <P> |
| |
| <table border> |
| |
| <tr> |
| <th>Member</th> <th>Description</th> |
| </tr> |
| |
| <tr> |
| <td><tt>value_type/size_type</tt></td> |
| <td> |
| The type for a component index (same as <tt>Index</tt>). |
| </td> |
| </tr> |
| |
| <tr> |
| <td><tt>size_type size()</tt></td> |
| <td> |
| Returns the number of components in the graph. |
| </td> |
| </tr> |
| |
| |
| <tr> |
| <td><tt>iterator/const_iterator</tt></td> |
| <td> |
| Iterators used to traverse the available component indices [0 to <tt>size()</tt>). |
| </td> |
| </tr> |
| |
| <tr> |
| <td><tt>iterator begin() const</tt></td> |
| <td> |
| Returns an iterator at the start of the component indices (0). |
| </td> |
| </tr> |
| |
| <tr> |
| <td><tt>iterator end() const</tt></td> |
| <td> |
| Returns an iterator past the end of the component indices (<tt>size()</tt>). |
| </td> |
| </tr> |
| |
| <tr> |
| <td><tt>std::pair<component_iterator, component_iterator> operator[size_type index] const</tt></td> |
| <td> |
| Returns a pair of iterators for the component at <tt>index</tt> where <tt>index</tt> is in [0, <tt>size()</tt>). |
| </td> |
| </tr> |
| |
| </table> |
| |
| <br> |
| <HR> |
| <TABLE> |
| <TR valign=top> |
| <TD nowrap>Copyright © 2000-2001</TD><TD> |
| <A HREF="http://www.boost.org/people/jeremy_siek.htm">Jeremy Siek</A>, |
| Indiana University (<A |
| HREF="mailto:jsiek@osl.iu.edu">jsiek@osl.iu.edu</A>)<br> |
| <A HREF="http://www.boost.org/people/liequan_lee.htm">Lie-Quan Lee</A>, Indiana University (<A HREF="mailto:llee@cs.indiana.edu">llee@cs.indiana.edu</A>)<br> |
| <A HREF="http://www.osl.iu.edu/~lums">Andrew Lumsdaine</A>, |
| Indiana University (<A |
| HREF="mailto:lums@osl.iu.edu">lums@osl.iu.edu</A>) |
| </TD></TR></TABLE> |
| |
| </BODY> |
| </HTML> |