Planet
navi homePPSaboutscreenshotsdownloaddevelopmentforum

source: downloads/boost_1_33_1/libs/graph/doc/incremental_components.html @ 12

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

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