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> 19disjoint_sets<Rank, Parent, FindCompress> 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 [<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<Rank, Parent, FindCompress> 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& x)</tt></td> 109 110 <td>Copy constructor.</td> 111 </tr> 112 113 <tr> 114 <td><tt>template <class Element><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 <class Element><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 <class Element><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 <class Element><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 <class ElementIterator><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 <class ElementIterator><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> 175disjoint_sets_with_storage<ID,InverseID,FindCompress> 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> 237disjoint_sets_with_storage(size_type n = 0, 238 ID id = ID(), 239 InverseID inv = InverseID()) 240</pre>Constructor. 241 <pre> 242template <class ElementIterator> 243void disjoint_sets_with_storage:: 244 normalize_sets(ElementIterator first, ElementIterator last) 245</pre>This rearranges the representatives such that the representative of 246each set is the element with the smallest ID.<br> 247 Postcondition: <tt>v >= 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> 254representative_with_path_halving<Parent> 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> 262Element 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> 269representative_with_full_path_compression<Parent> 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> 275Element 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 © 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> 310
