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