]> git.proxmox.com Git - ceph.git/blame - ceph/src/boost/libs/graph/doc/incremental_components.html
projects / ceph.git / blame
? search:
summary | shortlog | log | commit | commitdiff | tree
blob | blame (incremental) | history | HEAD
bump version to 12.2.2-pve1
[ceph.git] / ceph / src / boost / libs / graph / doc / incremental_components.html
CommitLineData
7c673cae
FG		 1<HTML>
2<!--
3 Copyright (c) Jeremy Siek, Lie-Quan Lee, and Andrew Lumsdaine 2000
4
5 Distributed under the Boost Software License, Version 1.0.
6 (See accompanying file LICENSE_1_0.txt or copy at
7 http://www.boost.org/LICENSE_1_0.txt)
8 -->
9<Head>
10<Title>Boost Graph Library: Incremental Connected Components</Title>
11<style type="text/css">
12 <!--
13 .code
14 {
15 border-left-style: groove;
16 border-left-width: 1px;
17 padding-left: 2em;
18 }
19
20 -->
21</style>
22
23<BODY BGCOLOR="#ffffff" LINK="#0000ee" TEXT="#000000" VLINK="#551a8b"
24 ALINK="#ff0000">
25<IMG SRC="../../../boost.png"
26 ALT="C++ Boost" width="277" height="86">
27
28<BR Clear>
29
30<H1>Incremental Connected Components</H1>
31
32<P>
33This section describes a family of functions and classes that work
34together to calculate the connected components of an undirected graph.
35The algorithm used here is based on the disjoint-sets (fast
36union-find) data structure&nbsp;[<A
37HREF="bibliography.html#clr90">8</A>,<A
38HREF="bibliography.html#tarjan83:_data_struct_network_algo">27</A>]
39which is a good method to use for situations where the graph is
40growing (edges are being added) and the connected components
41information needs to be updated repeatedly. This method does not cover
42the situation where edges are both added and removed from the graph,
43hence it is called <b><i>incremental</i></b><a
44href="bibliography.html#eppstein97:dynamic_graph">[42]</a> (and not
45fully dynamic). The disjoint-sets class is described in Section <A
46HREF="../../disjoint_sets/disjoint_sets.html">Disjoint Sets</A>.
47
48<P>
49The following five operations are the primary functions that you will
50use to calculate and maintain the connected components. The objects
51used here are a graph <TT>g</TT>, a disjoint-sets structure <TT>ds</TT>,
52and vertices <TT>u</TT> and <TT>v</TT>.
53
54<P>
55
56<UL>
57<LI><TT>initialize_incremental_components(g, ds)</TT>
58<BR>
59Basic initialization of the disjoint-sets structure. Each
60 vertex in the graph <TT>g</TT> is in its own set.
61</LI>
62<LI><TT>incremental_components(g, ds)</TT>
63<BR>
64The connected components are calculated based on the edges in the graph
65 <TT>g</TT> and the information is embedded in <TT>ds</TT>.
66</LI>
67<LI><TT>ds.find_set(v)</TT>
68<BR>
69Extracts the component information for vertex <TT>v</TT> from the
70 disjoint-sets.
71</LI>
72<LI><TT>ds.union_set(u, v)</TT>
73<BR>
74Update the disjoint-sets structure when edge <i>(u,v)</i> is added to the graph.
75</LI>
76</UL>
77
78<P>
79
80<H3>Complexity</H3>
81
82<P>
83The time complexity for the whole process is <i>O(V + E
84alpha(E,V))</i> where <i>E</i> is the total number of edges in the
85graph (by the end of the process) and <i>V</i> is the number of
86vertices. <i>alpha</i> is the inverse of Ackermann's function which
87has explosive recursively exponential growth. Therefore its inverse
88function grows <I>very</I> slowly. For all practical purposes
89<i>alpha(m,n) <= 4</i> which means the time complexity is only
90slightly larger than <i>O(V + E)</i>.
91
92<P>
93
94<H3>Example</H3>
95
96<P>
97Maintain the connected components of a graph while adding edges using
98the disjoint-sets data structure. The full source code for this
99example can be found in <a
100href="../example/incremental_components.cpp"><TT>examples/incremental_components.cpp</TT></a>.
101
102<P>
103<PRE class="code">
104using namespace boost;
105
106int main(int argc, char* argv[])
107{
108 typedef adjacency_list <vecS, vecS, undirectedS> Graph;
109 typedef graph_traits<Graph>::vertex_descriptor Vertex;
110 typedef graph_traits<Graph>::vertices_size_type VertexIndex;
111
112 const int VERTEX_COUNT = 6;
113 Graph graph(VERTEX_COUNT);
114
115 std::vector<VertexIndex> rank(num_vertices(graph));
116 std::vector<Vertex> parent(num_vertices(graph));
117
118 typedef VertexIndex* Rank;
119 typedef Vertex* Parent;
120
121 disjoint_sets<Rank, Parent> ds(&rank[0], &parent[0]);
122
123 initialize_incremental_components(graph, ds);
124 incremental_components(graph, ds);
125
126 graph_traits<Graph>::edge_descriptor edge;
127 bool flag;
128
129 boost::tie(edge, flag) = add_edge(0, 1, graph);
130 ds.union_set(0,1);
131
132 boost::tie(edge, flag) = add_edge(1, 4, graph);
133 ds.union_set(1,4);
134
135 boost::tie(edge, flag) = add_edge(4, 0, graph);
136 ds.union_set(4,0);
137
138 boost::tie(edge, flag) = add_edge(2, 5, graph);
139 ds.union_set(2,5);
140
141 std::cout << "An undirected graph:" << std::endl;
142 print_graph(graph, get(boost::vertex_index, graph));
143 std::cout << std::endl;
144
145 BOOST_FOREACH(Vertex current_vertex, vertices(graph)) {
146 std::cout << "representative[" << current_vertex << "] = " <<
147 ds.find_set(current_vertex) << std::endl;
148 }
149
150 std::cout << std::endl;
151
152 typedef component_index<VertexIndex> Components;
153
154 // NOTE: Because we're using vecS for the graph type, we're
155 // effectively using identity_property_map for a vertex index map.
156 // If we were to use listS instead, the index map would need to be
157 // explicity passed to the component_index constructor.
158 Components components(parent.begin(), parent.end());
159
160 // Iterate through the component indices
161 BOOST_FOREACH(VertexIndex current_index, components) {
162 std::cout << "component " << current_index << " contains: ";
163
164 // Iterate through the child vertex indices for [current_index]
165 BOOST_FOREACH(VertexIndex child_index,
166 components[current_index]) {
167 std::cout << child_index << " ";
168 }
169
170 std::cout << std::endl;
171 }
172
173 return (0);
174}
175</PRE>
176
177<P>
178<hr>
179<p>
180
181<H2><A NAME="sec:initialize-incremental-components"></A>
182<TT>initialize_incremental_components</TT>
183</H2>
184
185<P>
186<DIV ALIGN="left">
187<TABLE CELLPADDING=3 border>
188<TR><TH ALIGN="LEFT"><B>Graphs:</B></TH>
189<TD ALIGN="LEFT">undirected</TD>
190</TR>
191<TR><TH ALIGN="LEFT"><B>Properties:</B></TH>
192<TD ALIGN="LEFT">rank, parent (in disjoint-sets)</TD>
193</TR>
194<TR><TH ALIGN="LEFT"><B>Complexity:</B></TH>
195<TD></TD>
196</TR>
197</TABLE>
198</DIV>
199
200<P>
201<PRE>
202template &lt;class VertexListGraph, class DisjointSets&gt;
203void initialize_incremental_components(VertexListGraph&amp; G, DisjointSets&amp; ds)
204</PRE>
205
206<P>
207This prepares the disjoint-sets data structure for the incremental
208connected components algorithm by making each vertex in the graph a
209member of its own component (or set).
210
211<P>
212
213<H3>Where Defined</H3>
214
215<P>
216<a href="../../../boost/graph/incremental_components.hpp"><TT>boost/graph/incremental_components.hpp</TT></a>
217
218<p>
219<hr>
220<P>
221
222<H2><A NAME="sec:incremental-components"></A>
223<TT>incremental_components</TT>
224</H2>
225
226<P>
227<DIV ALIGN="left">
228<TABLE CELLPADDING=3 border>
229<TR><TH ALIGN="LEFT"><B>Graphs:</B></TH>
230<TD ALIGN="LEFT">undirected</TD>
231</TR>
232<TR><TH ALIGN="LEFT"><B>Properties:</B></TH>
233<TD ALIGN="LEFT">rank, parent (in disjoint-sets)</TD>
234</TR>
235<TR><TH ALIGN="LEFT"><B>Complexity:</B></TH>
236<TD ALIGN="LEFT"><i>O(E)</i></TD>
237</TR>
238</TABLE>
239</DIV>
240
241<p>
242<PRE>
243template &lt;class EdgeListGraph, class DisjointSets&gt;
244void incremental_components(EdgeListGraph&amp; g, DisjointSets&amp; ds)
245</PRE>
246
247<P>
248This function calculates the connected components of the graph,
249embedding the results in the disjoint-sets data structure.
250
251<P>
252
253<H3>Where Defined</H3>
254
255<P>
256<a href="../../../boost/graph/incremental_components.hpp"><TT>boost/graph/incremental_components.hpp</TT></a>
257
258<P>
259
260<H3>Requirements on Types</H3>
261
262<P>
263
264<UL>
265<LI>The graph type must be a model of <a href="./EdgeListGraph.html">EdgeListGraph</a>.
266</LI>
267</UL>
268
269<P>
270<hr>
271<p>
272
273<H2><A NAME="sec:same-component">
274<TT>same_component</TT></A>
275</H2>
276
277<P>
278<DIV ALIGN="left">
279<TABLE CELLPADDING=3 border>
280<TR><TH ALIGN="LEFT"><B>Properties:</B></TH>
281<TD ALIGN="LEFT">rank, parent (in disjoint-sets)</TD>
282</TR>
283<TR><TH ALIGN="LEFT"><B>Complexity:</B></TH>
284<TD ALIGN="LEFT"><i>O(alpha(E,V))</i></TD>
285</TR>
286</TABLE>
287</DIV>
288
289<P>
290<PRE>
291template &lt;class Vertex, class DisjointSet&gt;
292bool same_component(Vertex u, Vertex v, DisjointSet&amp; ds)
293</PRE>
294
295<P>
296This function determines whether <TT>u</TT> and <TT>v</TT> are in the same
297component.
298
299<P>
300
301<H3>Where Defined</H3>
302
303<P>
304<a href="../../../boost/graph/incremental_components.hpp"><TT>boost/graph/incremental_components.hpp</TT></a>
305
306<P>
307
308<H3>Requirements on Types</H3>
309
310<P>
311
312<UL>
313<LI><TT>Vertex</TT> must be compatible with the rank and parent
314 property maps of the <TT>DisjointSets</TT> data structure.
315</LI>
316</UL>
317
318<P>
319<hr>
320<p>
321
322<H2><A NAME="sec:component-index"></A>
323<TT>component_index</TT>
324</H2>
325
326<p>
327<PRE>
328component_index&lt;Index&gt;
329</PRE>
330
331<P>
332The <tt>component_index</tt> class provides an STL
333container-like view for the components of the graph. Each component is
334a container-like object, and access is provided via
335the <TT>operator[]</TT>. A <TT>component_index</TT> object is
336initialized with the parents property in the disjoint-sets calculated
337from the <TT>incremental_components()</TT> function. Optionally, a
338vertex -&gt; index property map is passed in
339(<tt>identity_property_map</tt> is used by default).
340
341<P>
342
343<H3>Where Defined</H3>
344
345<P>
346<a href="../../../boost/graph/incremental_components.hpp"><TT>boost/graph/incremental_components.hpp</TT></a>
347
348<P>
349
350<H3>Members</H3>
351
352<P>
353
354<table border>
355
356<tr>
357<th>Member</th> <th>Description</th>
358</tr>
359
360<tr>
361<td><tt>value_type/size_type</tt></td>
362<td>
363The type for a component index (same as <tt>Index</tt>).
364</td>
365</tr>
366
367<tr>
368<td><tt>size_type size()</tt></td>
369<td>
370Returns the number of components in the graph.
371</td>
372</tr>
373
374
375<tr>
376<td><tt>iterator/const_iterator</tt></td>
377<td>
378Iterators used to traverse the available component indices [0 to <tt>size()</tt>).
379</td>
380</tr>
381
382<tr>
383<td><tt>iterator begin() const</tt></td>
384<td>
385Returns an iterator at the start of the component indices (0).
386</td>
387</tr>
388
389<tr>
390<td><tt>iterator end() const</tt></td>
391<td>
392Returns an iterator past the end of the component indices (<tt>size()</tt>).
393</td>
394</tr>
395
396<tr>
397<td><tt>std::pair&lt;component_iterator, component_iterator&gt; operator[size_type index] const</tt></td>
398<td>
399Returns a pair of iterators for the component at <tt>index</tt> where <tt>index</tt> is in [0, <tt>size()</tt>).
400</td>
401</tr>
402
403</table>
404
405<br>
406<HR>
407<TABLE>
408<TR valign=top>
409<TD nowrap>Copyright &copy; 2000-2001</TD><TD>
410<A HREF="http://www.boost.org/people/jeremy_siek.htm">Jeremy Siek</A>,
411Indiana University (<A
412HREF="mailto:jsiek@osl.iu.edu">jsiek@osl.iu.edu</A>)<br>
413<A HREF="http://www.boost.org/people/liequan_lee.htm">Lie-Quan Lee</A>, Indiana University (<A HREF="mailto:llee@cs.indiana.edu">llee@cs.indiana.edu</A>)<br>
414<A HREF="http://www.osl.iu.edu/~lums">Andrew Lumsdaine</A>,
415Indiana University (<A
416HREF="mailto:lums@osl.iu.edu">lums@osl.iu.edu</A>)
417</TD></TR></TABLE>
418
419</BODY>
420</HTML>
Ceph