Planet
navi homePPSaboutscreenshotsdownloaddevelopmentforum

source: downloads/boost_1_34_1/libs/graph/doc/incremental_components.html @ 45

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

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