ceph/src/boost/libs/disjoint_sets/disjoint_sets.html

   1 <!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
   2
   3 <html>
   4 <head>
   5   <meta http-equiv="Content-Language" content="en-us">
   6   <meta http-equiv="Content-Type" content="text/html; charset=us-ascii">
   7
   8   <title>Boost Disjoint Sets</title>
   9 </head>
  10
  11 <body bgcolor="#FFFFFF" link="#0000EE" text="#000000" vlink="#551A8B" alink=
  12 "#FF0000">
  13   <img src="../../boost.png" alt="C++ Boost" width="277" height=
  14   "86"><br clear="none">
  15
  16   <h1><a name="sec:disjoint-sets" id="sec:disjoint-sets"></a> Disjoint
  17   Sets</h1>
  18   <pre>
  19 disjoint_sets&lt;Rank, Parent, FindCompress&gt;
  20 </pre>
  21
  22   <p>This is class that provides disjoint sets operations with <i>union by
  23   rank</i> and <i>path compression</i>. A disjoint-sets data structure
  24   maintains a collection <i>S = {S<sub>1</sub>, S<sub>2</sub>, ...,
  25   S<sub>k</sub>}</i> of disjoint sets. Each set is identified by a
  26   <i>representative</i> which is some member of of the set. Sets are
  27   represented by rooted trees which are encoded in the <tt>Parent</tt>
  28   property map. Two heuristics: "union by rank" and "path compression" are
  29   used to speed up the operations&nbsp;[<a href=
  30   "./bibliography.html#tarjan83:_data_struct_network_algo">1</a>, <a href=
  31   "./bibliography.html#clr90">2</a>].</p>
  32
  33   <h3>Where Defined</h3><a href=
  34   "../../boost/pending/disjoint_sets.hpp"><tt>boost/pending/disjoint_sets.hpp</tt></a>
  35
  36   <h3>Template Parameters</h3>
  37
  38   <table border summary="">
  39     <tr>
  40       <td><tt>Rank</tt></td>
  41
  42       <td>must be a model of <a href=
  43       "../property_map/doc/ReadWritePropertyMap.html">ReadWritePropertyMap</a>
  44       with an integer value type and a key type equal to the set's element
  45       type.</td>
  46     </tr>
  47
  48     <tr>
  49       <td><tt>Parent</tt></td>
  50
  51       <td>must be a model of <a href=
  52       "../property_map/doc/ReadWritePropertyMap.html">ReadWritePropertyMap</a>
  53       and the key and value type the same as the set's element type.</td>
  54     </tr>
  55
  56     <tr>
  57       <td><tt>FindCompress</tt></td>
  58
  59       <td>should be one of the find representative and path compress function
  60       objects.</td>
  61     </tr>
  62   </table>
  63
  64   <h3>Example</h3>
  65
  66   <p>A typical usage pattern for <tt>disjoint_sets</tt> can be seen in the
  67   <a href=
  68   "../graph/doc/kruskal_min_spanning_tree.html"><tt>kruskal_minimum_spanning_tree()</tt></a>
  69   algorithm. In this example, we call <tt>link()</tt> instead of
  70   <tt>union_set()</tt> because <tt>u</tt> and <tt>v</tt> were obtained from
  71   <tt>find_set()</tt> and therefore are already the representatives for their
  72   sets.</p>
  73   <pre>
  74   ...
  75   disjoint_sets&lt;Rank, Parent, FindCompress&gt; dsets(rank, p);
  76
  77   for (ui  = vertices(G).first; ui != vertices(G).second; ++ui)
  78     dsets.make_set(*ui);
  79   ...
  80   while ( !Q.empty() ) {
  81     e = Q.front();
  82     Q.pop();
  83     u = dsets.find_set(source(e));
  84     v = dsets.find_set(target(e));
  85     if ( u != v ) {
  86       *out++ = e;
  87       dsets.link(u, v);
  88     }
  89   }
  90 </pre>
  91
  92   <h3>Members</h3>
  93
  94   <table border summary="">
  95     <tr>
  96       <th>Member</th>
  97
  98       <th>Description</th>
  99     </tr>
 100
 101     <tr>
 102       <td><tt>disjoint_sets(Rank r, Parent p)</tt></td>
 103
 104       <td>Constructor.</td>
 105     </tr>
 106
 107     <tr>
 108       <td><tt>disjoint_sets(const disjoint_sets&amp; x)</tt></td>
 109
 110       <td>Copy constructor.</td>
 111     </tr>
 112
 113     <tr>
 114       <td><tt>template &lt;class Element&gt;<br>
 115       void make_set(Element x)</tt></td>
 116
 117       <td>Creates a singleton set containing Element <tt>x</tt>.</td>
 118     </tr>
 119
 120     <tr>
 121       <td><tt>template &lt;class Element&gt;<br>
 122       void link(Element x, Element y)</tt></td>
 123
 124       <td>Union the two sets <i>represented</i> by element <tt>x</tt> and
 125       <tt>y</tt>.</td>
 126     </tr>
 127
 128     <tr>
 129       <td><tt>template &lt;class Element&gt;<br>
 130       void union_set(Element x, Element y)</tt></td>
 131
 132       <td>Union the two sets that <i>contain</i> elements <tt>x</tt> and
 133       <tt>y</tt>. This is equivalent to
 134       <tt>link(find_set(x),find_set(y))</tt>.</td>
 135     </tr>
 136
 137     <tr>
 138       <td><tt>template &lt;class Element&gt;<br>
 139       Element find_set(Element x)</tt></td>
 140
 141       <td>Return the representative for the set containing element
 142       <tt>x</tt>.</td>
 143     </tr>
 144
 145     <tr>
 146       <td><tt>template &lt;class ElementIterator&gt;<br>
 147       std::size_t count_sets(ElementIterator first, ElementIterator
 148       last)</tt></td>
 149
 150       <td>Returns the number of disjoint sets.</td>
 151     </tr>
 152
 153     <tr>
 154       <td><tt>template &lt;class ElementIterator&gt;<br>
 155       void compress_sets(ElementIterator first, ElementIterator
 156       last)</tt></td>
 157
 158       <td>Flatten the parents tree so that the parent of every element is its
 159       representative.</td>
 160     </tr>
 161   </table>
 162
 163   <h3>Complexity</h3>
 164
 165   <p>The time complexity is <i>O(m alpha(m,n))</i>, where <i>alpha</i> is the
 166   inverse Ackermann's function, <i>m</i> is the number of disjoint-set
 167   operations (<tt>make_set()</tt>, <tt>find_set()</tt>, and <tt>link()</tt>
 168   and <i>n</i> is the number of elements. The <i>alpha</i> function grows
 169   very slowly, much more slowly than the <i>log</i> function.</p>
 170
 171   <h3>See Also</h3><a href=
 172   "../graph/doc/incremental_components.html"><tt>incremental_connected_components()</tt></a>
 173   <hr>
 174   <pre>
 175 disjoint_sets_with_storage&lt;ID,InverseID,FindCompress&gt;
 176 </pre>
 177
 178   <p>This class manages the storage for the rank and parent properties
 179   internally. The storage is in arrays, which are indexed by element ID,
 180   hence the requirement for the <tt>ID</tt> and <tt>InverseID</tt> functors.
 181   The rank and parent properties are initialized during construction so the
 182   each element is in a set by itself (so it is not necessary to initialize
 183   objects of this class with the <a href=
 184   "../graph/doc/incremental_components.html#sec:initialize-incremental-components">
 185   <tt>initialize_incremental_components()</tt></a> function). This class is
 186   especially useful when computing the (dynamic) connected components of an
 187   <tt>edge_list</tt> graph which does not provide a place to store vertex
 188   properties.</p>
 189
 190   <h3>Template Parameters</h3>
 191
 192   <table border summary="">
 193     <tr>
 194       <th>Parameter</th>
 195
 196       <th>Description</th>
 197
 198       <th>Default</th>
 199     </tr>
 200
 201     <tr>
 202       <td><tt>ID</tt></td>
 203
 204       <td>must be a model of <a href=
 205       "../property_map/doc/ReadablePropertyMap.html">ReadablePropertyMap</a> that
 206       maps elements to integers between zero 0 and N, the total number of
 207       elements in the sets.</td>
 208
 209       <td><tt>boost::identity_property_map</tt></td>
 210     </tr>
 211
 212     <tr>
 213       <td><tt>InverseID</tt></td>
 214
 215       <td>must be a model of <a href=
 216       "../property_map/doc/ReadablePropertyMap.html">ReadablePropertyMap</a> that
 217       maps integers to elements.</td>
 218
 219       <td><tt>boost::identity_property_map</tt></td>
 220     </tr>
 221
 222     <tr>
 223       <td><tt>FindCompress</tt></td>
 224
 225       <td>should be one of the find representative and path compress function
 226       objects.</td>
 227
 228       <td><tt>representative_with_full_path_compression</tt></td>
 229     </tr>
 230   </table>
 231
 232   <h3>Members</h3>
 233
 234   <p>This class has all of the members in <tt>disjoint_sets</tt> as well as
 235   the following members.</p>
 236   <pre>
 237 disjoint_sets_with_storage(size_type n = 0,
 238                            ID id = ID(),
 239                            InverseID inv = InverseID())
 240 </pre>Constructor.
 241   <pre>
 242 template &lt;class ElementIterator&gt;
 243 void disjoint_sets_with_storage::
 244   normalize_sets(ElementIterator first, ElementIterator last)
 245 </pre>This rearranges the representatives such that the representative of
 246 each set is the element with the smallest ID.<br>
 247   Postcondition: <tt>v &gt;= parent[v]</tt><br>
 248   Precondition: the disjoint sets structure must be compressed.<br>
 249   <hr>
 250
 251   <h2><a name="sec:representative-with-path-halving" id=
 252   "sec:representative-with-path-halving"></a></h2>
 253   <pre>
 254 representative_with_path_halving&lt;Parent&gt;
 255 </pre>
 256
 257   <p>This is a functor which finds the representative vertex for the same
 258   component as the element <tt>x</tt>. While traversing up the representative
 259   tree, the functor also applies the path halving technique to shorten the
 260   height of the tree.</p>
 261   <pre>
 262 Element operator()(Parent p, Element x)
 263 </pre>
 264   <hr>
 265
 266   <h2><a name="sec:representative-with-full-path-compression" id=
 267   "sec:representative-with-full-path-compression"></a><br></h2>
 268   <pre>
 269 representative_with_full_path_compression&lt;Parent&gt;
 270 </pre>
 271
 272   <p>This is a functor which finds the representative element for the set
 273   that element <tt>x</tt> belongs to.</p>
 274   <pre>
 275 Element operator()(Parent p, Element x)
 276 </pre>
 277
 278   <p><br></p>
 279   <hr>
 280
 281   <p><a href="http://validator.w3.org/check?uri=referer"><img border="0" src=
 282   "../../doc/images/valid-html401.png" alt="Valid HTML 4.01 Transitional"
 283   height="31" width="88"></a></p>
 284
 285   <p>Revised
 286   <!--webbot bot="Timestamp" s-type="EDITED" s-format="%d %B, %Y" startspan -->01
 287   December, 2006<!--webbot bot="Timestamp" endspan i-checksum="38508" --></p>
 288
 289   <table summary="">
 290     <tr valign="top">
 291       <td nowrap><i>Copyright &copy; 2000</i></td>
 292
 293       <td><i><a href="http://www.boost.org/people/jeremy_siek.htm">Jeremy Siek</a>, Univ.of
 294       Notre Dame (<a href="mailto:jsiek@lsc.nd.edu">jsiek@lsc.nd.edu</a>)<br>
 295       <a href="http://www.boost.org/people/liequan_lee.htm">Lie-Quan Lee</a>,
 296       Univ.of Notre Dame (<a href=
 297       "mailto:llee1@lsc.nd.edu">llee1@lsc.nd.edu</a>)<br>
 298       <a href="http://www.lsc.nd.edu/~lums">Andrew Lumsdaine</a>, Univ.of
 299       Notre Dame (<a href=
 300       "mailto:lums@lsc.nd.edu">lums@lsc.nd.edu</a>)</i></td>
 301     </tr>
 302   </table>
 303
 304   <p><i>Distributed under the Boost Software License, Version 1.0. (See
 305   accompanying file <a href="../../LICENSE_1_0.txt">LICENSE_1_0.txt</a> or
 306   copy at <a href=
 307   "http://www.boost.org/LICENSE_1_0.txt">http://www.boost.org/LICENSE_1_0.txt</a>)</i></p>
 308 </body>
 309 </html>