1<HTML> 2<!-- 3 Copyright (c) Jeremy Siek, Lie-Quan Lee, and Andrew Lumsdaine 2000 4 5 Distributed under the Boost Software License, Version 1.0. 6 (See accompanying file LICENSE_1_0.txt or copy at 7 http://www.boost.org/LICENSE_1_0.txt) 8 --> 9<Head> 10<Title>Boost Graph Library: Incremental Connected Components</Title> 11<style type="text/css"> 12 <!-- 13 .code 14 { 15 border-left-style: groove; 16 border-left-width: 1px; 17 padding-left: 2em; 18 } 19 20 --> 21</style> 22 23<BODY BGCOLOR="#ffffff" LINK="#0000ee" TEXT="#000000" VLINK="#551a8b" 24 ALINK="#ff0000"> 25<IMG SRC="../../../boost.png" 26 ALT="C++ Boost" width="277" height="86"> 27 28<BR Clear> 29 30<H1>Incremental Connected Components</H1> 31 32<P> 33This section describes a family of functions and classes that work 34together to calculate the connected components of an undirected graph. 35The algorithm used here is based on the disjoint-sets (fast 36union-find) data structure [<A 37HREF="bibliography.html#clr90">8</A>,<A 38HREF="bibliography.html#tarjan83:_data_struct_network_algo">27</A>] 39which is a good method to use for situations where the graph is 40growing (edges are being added) and the connected components 41information needs to be updated repeatedly. This method does not cover 42the situation where edges are both added and removed from the graph, 43hence it is called <b><i>incremental</i></b><a 44href="bibliography.html#eppstein97:dynamic_graph">[42]</a> (and not 45fully dynamic). The disjoint-sets class is described in Section <A 46HREF="../../disjoint_sets/disjoint_sets.html">Disjoint Sets</A>. 47 48<P> 49The following five operations are the primary functions that you will 50use to calculate and maintain the connected components. The objects 51used here are a graph <TT>g</TT>, a disjoint-sets structure <TT>ds</TT>, 52and vertices <TT>u</TT> and <TT>v</TT>. 53 54<P> 55 56<UL> 57<LI><TT>initialize_incremental_components(g, ds)</TT> 58<BR> 59Basic initialization of the disjoint-sets structure. Each 60 vertex in the graph <TT>g</TT> is in its own set. 61</LI> 62<LI><TT>incremental_components(g, ds)</TT> 63<BR> 64The connected components are calculated based on the edges in the graph 65 <TT>g</TT> and the information is embedded in <TT>ds</TT>. 66</LI> 67<LI><TT>ds.find_set(v)</TT> 68<BR> 69Extracts the component information for vertex <TT>v</TT> from the 70 disjoint-sets. 71</LI> 72<LI><TT>ds.union_set(u, v)</TT> 73<BR> 74Update the disjoint-sets structure when edge <i>(u,v)</i> is added to the graph. 75</LI> 76</UL> 77 78<P> 79 80<H3>Complexity</H3> 81 82<P> 83The time complexity for the whole process is <i>O(V + E 84alpha(E,V))</i> where <i>E</i> is the total number of edges in the 85graph (by the end of the process) and <i>V</i> is the number of 86vertices. <i>alpha</i> is the inverse of Ackermann's function which 87has explosive recursively exponential growth. Therefore its inverse 88function grows <I>very</I> slowly. For all practical purposes 89<i>alpha(m,n) <= 4</i> which means the time complexity is only 90slightly larger than <i>O(V + E)</i>. 91 92<P> 93 94<H3>Example</H3> 95 96<P> 97Maintain the connected components of a graph while adding edges using 98the disjoint-sets data structure. The full source code for this 99example can be found in <a 100href="../example/incremental_components.cpp"><TT>examples/incremental_components.cpp</TT></a>. 101 102<P> 103<PRE class="code"> 104using namespace boost; 105 106int main(int argc, char* argv[]) 107{ 108 typedef adjacency_list <vecS, vecS, undirectedS> Graph; 109 typedef graph_traits<Graph>::vertex_descriptor Vertex; 110 typedef graph_traits<Graph>::vertices_size_type VertexIndex; 111 112 const int VERTEX_COUNT = 6; 113 Graph graph(VERTEX_COUNT); 114 115 std::vector<VertexIndex> rank(num_vertices(graph)); 116 std::vector<Vertex> parent(num_vertices(graph)); 117 118 typedef VertexIndex* Rank; 119 typedef Vertex* Parent; 120 121 disjoint_sets<Rank, Parent> ds(&rank[0], &parent[0]); 122 123 initialize_incremental_components(graph, ds); 124 incremental_components(graph, ds); 125 126 graph_traits<Graph>::edge_descriptor edge; 127 bool flag; 128 129 boost::tie(edge, flag) = add_edge(0, 1, graph); 130 ds.union_set(0,1); 131 132 boost::tie(edge, flag) = add_edge(1, 4, graph); 133 ds.union_set(1,4); 134 135 boost::tie(edge, flag) = add_edge(4, 0, graph); 136 ds.union_set(4,0); 137 138 boost::tie(edge, flag) = add_edge(2, 5, graph); 139 ds.union_set(2,5); 140 141 std::cout << "An undirected graph:" << std::endl; 142 print_graph(graph, get(boost::vertex_index, graph)); 143 std::cout << std::endl; 144 145 BOOST_FOREACH(Vertex current_vertex, vertices(graph)) { 146 std::cout << "representative[" << current_vertex << "] = " << 147 ds.find_set(current_vertex) << std::endl; 148 } 149 150 std::cout << std::endl; 151 152 typedef component_index<VertexIndex> Components; 153 154 // NOTE: Because we're using vecS for the graph type, we're 155 // effectively using identity_property_map for a vertex index map. 156 // If we were to use listS instead, the index map would need to be 157 // explicity passed to the component_index constructor. 158 Components components(parent.begin(), parent.end()); 159 160 // Iterate through the component indices 161 BOOST_FOREACH(VertexIndex current_index, components) { 162 std::cout << "component " << current_index << " contains: "; 163 164 // Iterate through the child vertex indices for [current_index] 165 BOOST_FOREACH(VertexIndex child_index, 166 components[current_index]) { 167 std::cout << child_index << " "; 168 } 169 170 std::cout << std::endl; 171 } 172 173 return (0); 174} 175</PRE> 176 177<P> 178<hr> 179<p> 180 181<H2><A NAME="sec:initialize-incremental-components"></A> 182<TT>initialize_incremental_components</TT> 183</H2> 184 185<P> 186<DIV ALIGN="left"> 187<TABLE CELLPADDING=3 border> 188<TR><TH ALIGN="LEFT"><B>Graphs:</B></TH> 189<TD ALIGN="LEFT">undirected</TD> 190</TR> 191<TR><TH ALIGN="LEFT"><B>Properties:</B></TH> 192<TD ALIGN="LEFT">rank, parent (in disjoint-sets)</TD> 193</TR> 194<TR><TH ALIGN="LEFT"><B>Complexity:</B></TH> 195<TD></TD> 196</TR> 197</TABLE> 198</DIV> 199 200<P> 201<PRE> 202template <class VertexListGraph, class DisjointSets> 203void initialize_incremental_components(VertexListGraph& G, DisjointSets& ds) 204</PRE> 205 206<P> 207This prepares the disjoint-sets data structure for the incremental 208connected components algorithm by making each vertex in the graph a 209member of its own component (or set). 210 211<P> 212 213<H3>Where Defined</H3> 214 215<P> 216<a href="../../../boost/graph/incremental_components.hpp"><TT>boost/graph/incremental_components.hpp</TT></a> 217 218<p> 219<hr> 220<P> 221 222<H2><A NAME="sec:incremental-components"></A> 223<TT>incremental_components</TT> 224</H2> 225 226<P> 227<DIV ALIGN="left"> 228<TABLE CELLPADDING=3 border> 229<TR><TH ALIGN="LEFT"><B>Graphs:</B></TH> 230<TD ALIGN="LEFT">undirected</TD> 231</TR> 232<TR><TH ALIGN="LEFT"><B>Properties:</B></TH> 233<TD ALIGN="LEFT">rank, parent (in disjoint-sets)</TD> 234</TR> 235<TR><TH ALIGN="LEFT"><B>Complexity:</B></TH> 236<TD ALIGN="LEFT"><i>O(E)</i></TD> 237</TR> 238</TABLE> 239</DIV> 240 241<p> 242<PRE> 243template <class EdgeListGraph, class DisjointSets> 244void incremental_components(EdgeListGraph& g, DisjointSets& ds) 245</PRE> 246 247<P> 248This function calculates the connected components of the graph, 249embedding the results in the disjoint-sets data structure. 250 251<P> 252 253<H3>Where Defined</H3> 254 255<P> 256<a href="../../../boost/graph/incremental_components.hpp"><TT>boost/graph/incremental_components.hpp</TT></a> 257 258<P> 259 260<H3>Requirements on Types</H3> 261 262<P> 263 264<UL> 265<LI>The graph type must be a model of <a href="./EdgeListGraph.html">EdgeListGraph</a>. 266</LI> 267</UL> 268 269<P> 270<hr> 271<p> 272 273<H2><A NAME="sec:same-component"> 274<TT>same_component</TT></A> 275</H2> 276 277<P> 278<DIV ALIGN="left"> 279<TABLE CELLPADDING=3 border> 280<TR><TH ALIGN="LEFT"><B>Properties:</B></TH> 281<TD ALIGN="LEFT">rank, parent (in disjoint-sets)</TD> 282</TR> 283<TR><TH ALIGN="LEFT"><B>Complexity:</B></TH> 284<TD ALIGN="LEFT"><i>O(alpha(E,V))</i></TD> 285</TR> 286</TABLE> 287</DIV> 288 289<P> 290<PRE> 291template <class Vertex, class DisjointSet> 292bool same_component(Vertex u, Vertex v, DisjointSet& ds) 293</PRE> 294 295<P> 296This function determines whether <TT>u</TT> and <TT>v</TT> are in the same 297component. 298 299<P> 300 301<H3>Where Defined</H3> 302 303<P> 304<a href="../../../boost/graph/incremental_components.hpp"><TT>boost/graph/incremental_components.hpp</TT></a> 305 306<P> 307 308<H3>Requirements on Types</H3> 309 310<P> 311 312<UL> 313<LI><TT>Vertex</TT> must be compatible with the rank and parent 314 property maps of the <TT>DisjointSets</TT> data structure. 315</LI> 316</UL> 317 318<P> 319<hr> 320<p> 321 322<H2><A NAME="sec:component-index"></A> 323<TT>component_index</TT> 324</H2> 325 326<p> 327<PRE> 328component_index<Index> 329</PRE> 330 331<P> 332The <tt>component_index</tt> class provides an STL 333container-like view for the components of the graph. Each component is 334a container-like object, and access is provided via 335the <TT>operator[]</TT>. A <TT>component_index</TT> object is 336initialized with the parents property in the disjoint-sets calculated 337from the <TT>incremental_components()</TT> function. Optionally, a 338vertex -> index property map is passed in 339(<tt>identity_property_map</tt> is used by default). 340 341<P> 342 343<H3>Where Defined</H3> 344 345<P> 346<a href="../../../boost/graph/incremental_components.hpp"><TT>boost/graph/incremental_components.hpp</TT></a> 347 348<P> 349 350<H3>Members</H3> 351 352<P> 353 354<table border> 355 356<tr> 357<th>Member</th> <th>Description</th> 358</tr> 359 360<tr> 361<td><tt>value_type/size_type</tt></td> 362<td> 363The type for a component index (same as <tt>Index</tt>). 364</td> 365</tr> 366 367<tr> 368<td><tt>size_type size()</tt></td> 369<td> 370Returns the number of components in the graph. 371</td> 372</tr> 373 374 375<tr> 376<td><tt>iterator/const_iterator</tt></td> 377<td> 378Iterators used to traverse the available component indices [0 to <tt>size()</tt>). 379</td> 380</tr> 381 382<tr> 383<td><tt>iterator begin() const</tt></td> 384<td> 385Returns an iterator at the start of the component indices (0). 386</td> 387</tr> 388 389<tr> 390<td><tt>iterator end() const</tt></td> 391<td> 392Returns an iterator past the end of the component indices (<tt>size()</tt>). 393</td> 394</tr> 395 396<tr> 397<td><tt>std::pair<component_iterator, component_iterator> operator[size_type index] const</tt></td> 398<td> 399Returns a pair of iterators for the component at <tt>index</tt> where <tt>index</tt> is in [0, <tt>size()</tt>). 400</td> 401</tr> 402 403</table> 404 405<br> 406<HR> 407<TABLE> 408<TR valign=top> 409<TD nowrap>Copyright © 2000-2001</TD><TD> 410<A HREF="http://www.boost.org/people/jeremy_siek.htm">Jeremy Siek</A>, 411Indiana University (<A 412HREF="mailto:jsiek@osl.iu.edu">jsiek@osl.iu.edu</A>)<br> 413<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> 414<A HREF="https://homes.cs.washington.edu/~al75">Andrew Lumsdaine</A>, 415Indiana University (<A 416HREF="mailto:lums@osl.iu.edu">lums@osl.iu.edu</A>) 417</TD></TR></TABLE> 418 419</BODY> 420</HTML> 421
