Planet
navi homePPSaboutscreenshotsdownloaddevelopmentforum

source: downloads/boost_1_33_1/libs/disjoint_sets/disjoint_sets.html @ 12

Last change on this file since 12 was 12, checked in by landauf, 18 years ago

added boost
File size: 8.6 KB
Line 
1<HTML>
2<!--
3  -- Copyright (c) Jeremy Siek, Lie-Quan Lee, and Andrew Lumsdaine 2000
4  --
5  -- Permission to use, copy, modify, distribute and sell this software
6  -- and its documentation for any purpose is hereby granted without fee,
7  -- provided that the above copyright notice appears in all copies and
8  -- that both that copyright notice and this permission notice appear
9  -- in supporting documentation.  We make no
10  -- representations about the suitability of this software for any
11  -- purpose.  It is provided "as is" without express or implied warranty.
12  -->
13<Head>
14<Title>Boost Disjoint Sets</Title>
15<BODY BGCOLOR="#ffffff" LINK="#0000ee" TEXT="#000000" VLINK="#551a8b" 
16        ALINK="#ff0000"> 
17<IMG SRC="../../boost.png" 
18     ALT="C++ Boost" width="277" height="86"> 
19
20<BR Clear>
21
22
23<H1><A NAME="sec:disjoint-sets"></A>
24Disjoint Sets
25</H1>
26
27<P>
28
29<H2>
30</h2>
31<PRE>
32disjoint_sets&lt;Rank, Parent, FindCompress&gt;
33</PRE>
34
35<P>
36This is class that provides disjoint sets operations with <I>union by
37rank</I> and <I>path compression</I>. A disjoint-sets data structure
38maintains a collection <i>S = {S<sub>1</sub>, S<sub>2</sub>, ...,
39S<sub>k</sub>}</i> of disjoint sets. Each set is identified by a
40<I>representative</I> which is some member of of the set. Sets are
41represented by rooted trees which are encoded in the <TT>Parent</TT>
42property map. Two heuristics: &quot;union by rank&quot; and
43&quot;path compression&quot; are used to speed up the
44operations&nbsp;[<a
45href="./bibliography.html#tarjan83:_data_struct_network_algo">1</a>, <a
46href="./bibliography.html#clr90">2</a>].
47
48<P>
49
50<h3>Where Defined</h3>
51
52<a href="../../boost/pending/disjoint_sets.hpp"><tt>boost/disjoint_sets.hpp</tt></a>
53
54<H3>Template Parameters</H3>
55
56<P>
57<TABLE border>
58<TR><TD><TT>Rank</TT></TD> <TD>must be a model of <a
59href="../property_map/ReadWritePropertyMap.html">ReadWritePropertyMap</a>
60with an integer value type and a key type equal to the set's element
61type.</TD>
62</TR>
63<TR><TD><TT>Parent</TT></TD> <TD>must be a model of <a
64href="../property_map/ReadWritePropertyMap.html">ReadWritePropertyMap</a>
65and the key and value type the same as the set's element type.</TD>
66</TR>
67<TR><TD><TT>FindCompress</TT></TD>
68<TD>should be one of the find representative and
69   path compress function objects.</TD>
70</TR>
71</TABLE>
72<P>
73
74<H3>Example</H3>
75
76<P>
77A typical usage pattern for <TT>disjoint_sets</TT> can be seen in the
78<a
79href="../graph/doc/kruskal_min_spanning_tree.html"><TT>kruskal_minimum_spanning_tree()</TT></a>
80algorithm.  In this example, we call <TT>link()</TT> instead of
81<TT>union_set()</TT> because <TT>u</TT> and <TT>v</TT> were obtained
82from <TT>find_set()</TT> and therefore are already the representatives
83for their sets.
84
85<P>
86<PRE>
87  ...
88  disjoint_sets&lt;Rank, Parent, FindCompress&gt; dsets(rank, p);
89 
90  for (ui  = vertices(G).first; ui != vertices(G).second; ++ui)
91    dsets.make_set(*ui);
92  ...
93  while ( !Q.empty() ) {
94    e = Q.front();
95    Q.pop();
96    u = dsets.find_set(source(e));
97    v = dsets.find_set(target(e));
98    if ( u != v ) {
99      *out++ = e;
100      dsets.link(u, v);
101    }
102  }
103</PRE>
104
105<P>
106
107<H3>Members</H3>
108
109<P>
110
111<table border>
112<tr>
113<th>Member</th><th>Description</th>
114</tr>
115
116<tr> 
117<td><tt>
118disjoint_sets(Rank r, Parent p)
119</tt></td>
120<td>
121Constructor.
122</td>
123</tr>
124
125<tr>
126<td><tt>
127disjoint_sets(const disjoint_sets&amp; x)
128</tt></td>
129<td>
130Copy constructor.
131</td>
132</tr>
133
134<tr>
135<td><tt>
136template &lt;class Element&gt;<br>
137void make_set(Element x)
138</tt></td>
139<td>
140Creates a singleton set containing Element <TT>x</TT>.
141</td>
142</tr>
143
144<tr>
145<td><tt>
146template &lt;class Element&gt;<br>
147void link(Element x, Element y)
148</tt></td>
149<td>
150Union the two sets <I>represented</I> by element <TT>x</TT> and <TT>y</TT>.
151</td>
152</tr>
153
154<tr>
155<td><tt>
156template &lt;class Element&gt;<br>
157void union_set(Element x, Element y)
158</tt></td>
159<td>
160Union the two sets that <I>contain</I> elements <TT>x</TT> and <TT>y</TT>.
161This is equivalent to <TT>link(find_set(x),find_set(y))</TT>.
162</td>
163</tr>
164
165<tr>
166<td><tt>
167template &lt;class Element&gt;<br>
168Element find_set(Element x)
169</tt></td>
170<td>
171Return the representative for the set containing element <TT>x</TT>.
172</td>
173</tr>
174
175<tr>
176<td><tt>
177template &lt;class ElementIterator&gt;<br>
178std::size_t count_sets(ElementIterator first, ElementIterator last)
179</tt></td>
180<td>
181Returns the number of disjoint sets.
182</td>
183</tr>
184
185<tr>
186<td><tt>
187template &lt;class ElementIterator&gt;<br>
188void compress_sets(ElementIterator first, ElementIterator last)
189</tt></td>
190<td>
191Flatten the parents tree so that the parent of every element is
192its representative.
193</td>
194</tr>
195
196</table>
197
198<p>
199
200<H3>Complexity</H3>
201
202<P>
203The time complexity is <i>O(m alpha(m,n))</i>, where <i>alpha</i> is
204the inverse Ackermann's function, <i>m</i> is the number of
205disjoint-set operations (<TT>make_set()</TT>, <TT>find_set()</TT>, and
206<TT>link()</TT> and <i>n</i> is the number of elements. The
207<i>alpha</i> function grows very slowly, much more slowly than the
208<i>log</i> function.
209
210<P>
211
212<h3>See Also</h3>
213
214<a href="../graph/doc/incremental_components.html"><tt>incremental_connected_components()</tt></a>
215
216
217<hr>
218
219<H2>
220</h2>
221<PRE>
222disjoint_sets_with_storage&lt;ID,InverseID,FindCompress&gt;
223</PRE>
224
225<P>
226This class manages the storage for the rank and parent properties
227internally. The storage is in arrays, which are indexed by element ID,
228hence the requirement for the <TT>ID</TT> and <TT>InverseID</TT>
229functors.  The rank and parent properties are initialized during
230construction so the each element is in a set by itself (so it is not
231necessary to initialize objects of this class with the <a
232href="../graph/doc/incremental_components.html#sec:initialize-incremental-components"><TT>initialize_incremental_components()</TT></a>
233function). This class is especially useful when computing the
234(dynamic) connected components of an <TT>edge_list</TT> graph which
235does not provide a place to store vertex properties.
236
237<P>
238
239<H3>Template Parameters</H3>
240
241<TABLE border>
242<TR>
243<th>Parameter</th><th>Description</th><th>Default</th>
244</tr>
245
246<TR>
247<TD><TT>ID</TT></TD>
248<TD>must be a model of <a href="../property_map/ReadablePropertyMap.html">ReadablePropertyMap</a>
249 that maps elements to integers between zero 0 and N, the total
250 number of elements in the sets.</TD>
251<TD><TT>boost::identity_property_map</TT></TD>
252</TR>
253
254<TR>
255<TD><TT>InverseID</TT></TD>
256<TD>must be a model of <a href="../property_map/ReadablePropertyMap.html">ReadablePropertyMap</a> that maps integers to elements.</TD>
257<TD><TT>boost::identity_property_map</TT></TD>
258</TR>
259
260<TR><TD><TT>FindCompress</TT></TD>
261<TD>should be one of the find representative and
262   path compress function objects.</TD>
263<TD><TT>representative_with_full_path_compression</TT></TD>
264</TR>
265
266</TABLE>
267<P>
268
269<H3>Members</H3>
270
271<P>
272This class has all of the members in <TT>disjoint_sets</TT> as well as
273the following members.
274
275<P>
276 
277<P> <P>
278 <PRE>
279disjoint_sets_with_storage(size_type n = 0,
280                           ID id = ID(),
281                           InverseID inv = InverseID())
282</PRE>
283Constructor.
284<P>
285
286<P> <P>
287 <PRE>
288template &lt;class ElementIterator&gt;
289void disjoint_sets_with_storage::
290  normalize_sets(ElementIterator first, ElementIterator last)
291</PRE>
292This rearranges the representatives such that the representative
293of each set is the element with the smallest ID. 
294<BR>
295Postcondition: <TT>v &gt;= parent[v]</TT> 
296<BR>
297Precondition: the disjoint sets structure must be compressed.
298<BR>
299<P>
300 
301<P>
302
303
304
305
306<hr>
307
308<H2><A NAME="sec:representative-with-path-halving"></A>
309</h2>
310<PRE>
311representative_with_path_halving&lt;Parent&gt;
312</PRE>
313
314<P>
315This is a functor which finds the representative vertex for the same
316component as the element <TT>x</TT>. While traversing up the
317representative tree, the functor also applies the path halving
318technique to shorten the height of the tree.
319
320<P>
321 
322<P> <PRE>
323Element operator()(Parent p, Element x)
324</PRE> 
325<P>
326
327
328
329<hr>
330
331<H2>
332<A NAME="sec:representative-with-full-path-compression"></A>
333<BR>
334</h2>
335<PRE>
336representative_with_full_path_compression&lt;Parent&gt;
337</PRE>
338
339<P>
340This is a functor which finds the representative element for the set
341that element <TT>x</TT> belongs to.
342
343<P>
344 
345<P> <PRE>
346Element operator()(Parent p, Element x)
347</PRE> 
348<P>
349
350<P>
351
352
353<br>
354<HR>
355<TABLE>
356<TR valign=top>
357<TD nowrap>Copyright &copy 2000</TD><TD>
358<a HREF="../../people/jeremy_siek.htm">Jeremy Siek</a>,
359Univ.of Notre Dame (<A
360HREF="mailto:jsiek@lsc.nd.edu">jsiek@lsc.nd.edu</A>)<br>
361<A HREF="http://www.boost.org/people/liequan_lee.htm">Lie-Quan Lee</A>, Univ.of Notre Dame (<A HREF="mailto:llee1@lsc.nd.edu">llee1@lsc.nd.edu</A>)<br>
362<A HREF=http://www.lsc.nd.edu/~lums>Andrew Lumsdaine</A>,
363Univ.of Notre Dame (<A
364HREF="mailto:lums@lsc.nd.edu">lums@lsc.nd.edu</A>)
365</TD></TR></TABLE>
366
367</BODY>
368</HTML> 
Note: See TracBrowser for help on using the repository browser.