Planet
navi homePPSaboutscreenshotsdownloaddevelopmentforum

source: downloads/boost_1_34_1/libs/disjoint_sets/disjoint_sets.html @ 29

Last change on this file since 29 was 29, checked in by landauf, 17 years ago

updated boost from 1_33_1 to 1_34_1
File size: 9.5 KB
Line 
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&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/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/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/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>
175disjoint_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/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/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 &lt;class ElementIterator&gt;
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 &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>
254representative_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>
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&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>
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  "http://www.w3.org/Icons/valid-html401" 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="../../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>
Note: See TracBrowser for help on using the repository browser.