ceph/src/boost/libs/graph/doc/incremental_components.html

   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>
  33 This section describes a family of functions and classes that work
  34 together to calculate the connected components of an undirected graph.
  35 The algorithm used here is based on the disjoint-sets (fast
  36 union-find) data structure&nbsp;[<A
  37 HREF="bibliography.html#clr90">8</A>,<A
  38 HREF="bibliography.html#tarjan83:_data_struct_network_algo">27</A>]
  39 which is a good method to use for situations where the graph is
  40 growing (edges are being added) and the connected components
  41 information needs to be updated repeatedly. This method does not cover
  42 the situation where edges are both added and removed from the graph,
  43 hence it is called <b><i>incremental</i></b><a
  44 href="bibliography.html#eppstein97:dynamic_graph">[42]</a> (and not
  45 fully dynamic). The disjoint-sets class is described in Section <A
  46 HREF="../../disjoint_sets/disjoint_sets.html">Disjoint Sets</A>.
  47
  48 <P>
  49 The following five operations are the primary functions that you will
  50 use to calculate and maintain the connected components.  The objects
  51 used here are a graph <TT>g</TT>, a disjoint-sets structure <TT>ds</TT>,
  52 and 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>
  59 Basic 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>
  64 The 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>
  69 Extracts 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>
  74 Update 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>
  83 The time complexity for the whole process is <i>O(V + E
  84 alpha(E,V))</i> where <i>E</i> is the total number of edges in the
  85 graph (by the end of the process) and <i>V</i> is the number of
  86 vertices.  <i>alpha</i> is the inverse of Ackermann's function which
  87 has explosive recursively exponential growth. Therefore its inverse
  88 function grows <I>very</I> slowly. For all practical purposes
  89 <i>alpha(m,n) <= 4</i> which means the time complexity is only
  90 slightly larger than <i>O(V + E)</i>.
  91
  92 <P>
  93
  94 <H3>Example</H3>
  95
  96 <P>
  97 Maintain the connected components of a graph while adding edges using
  98 the disjoint-sets data structure. The full source code for this
  99 example can be found in <a
 100 href="../example/incremental_components.cpp"><TT>examples/incremental_components.cpp</TT></a>.
 101
 102 <P>
 103 <PRE class="code">
 104 using namespace boost;
 105
 106 int 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>
 202 template &lt;class VertexListGraph, class DisjointSets&gt;
 203 void initialize_incremental_components(VertexListGraph&amp; G, DisjointSets&amp; ds)
 204 </PRE>
 205
 206 <P>
 207 This prepares the disjoint-sets data structure for the incremental
 208 connected components algorithm by making each vertex in the graph a
 209 member 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>
 243 template &lt;class EdgeListGraph, class DisjointSets&gt;
 244 void incremental_components(EdgeListGraph&amp; g, DisjointSets&amp; ds)
 245 </PRE>
 246
 247 <P>
 248 This function calculates the connected components of the graph,
 249 embedding 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>
 291 template &lt;class Vertex, class DisjointSet&gt;
 292 bool same_component(Vertex u, Vertex v, DisjointSet&amp; ds)
 293 </PRE>
 294
 295 <P>
 296 This function determines whether <TT>u</TT> and <TT>v</TT> are in the same
 297 component.
 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>
 328 component_index&lt;Index&gt;
 329 </PRE>
 330
 331 <P>
 332 The <tt>component_index</tt> class provides an STL
 333 container-like view for the components of the graph. Each component is
 334 a container-like object, and access is provided via
 335 the <TT>operator[]</TT>.  A <TT>component_index</TT> object is
 336 initialized with the parents property in the disjoint-sets calculated
 337 from the <TT>incremental_components()</TT> function.  Optionally, a
 338 vertex -&gt; 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>
 363 The 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>
 370 Returns 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>
 378 Iterators 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>
 385 Returns 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>
 392 Returns an iterator past the end of the component indices (<tt>size()</tt>).
 393 </td>
 394 </tr>
 395
 396 <tr>
 397 <td><tt>std::pair&lt;component_iterator, component_iterator&gt; operator[size_type index] const</tt></td>
 398 <td>
 399 Returns 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 &copy; 2000-2001</TD><TD>
 410 <A HREF="http://www.boost.org/people/jeremy_siek.htm">Jeremy Siek</A>,
 411 Indiana University (<A
 412 HREF="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="http://www.osl.iu.edu/~lums">Andrew Lumsdaine</A>,
 415 Indiana University (<A
 416 HREF="mailto:lums@osl.iu.edu">lums@osl.iu.edu</A>)
 417 </TD></TR></TABLE>
 418
 419 </BODY>
 420 </HTML>