| 1 | <HTML> |
|---|
| 2 | <!-- |
|---|
| 3 | -- Copyright (c) Jeremy Siek 2000-2001 |
|---|
| 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. Jeremy Siek makes 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: 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 | |
|---|
| 23 | <H1> |
|---|
| 24 | <A NAME="sec:connected-components"> |
|---|
| 25 | <img src="figs/python.gif" alt="(Python)"/> |
|---|
| 26 | <TT>connected_components</TT></A> |
|---|
| 27 | </H1> |
|---|
| 28 | |
|---|
| 29 | <PRE> |
|---|
| 30 | <i>// named parameter version</i> |
|---|
| 31 | template <class VertexListGraph, class ComponentMap, class P, class T, class R> |
|---|
| 32 | typename property_traits<ComponentMap>::value_type |
|---|
| 33 | connected_components(VertexListGraph& G, ComponentMap comp, |
|---|
| 34 | const bgl_named_params<P, T, R>& params = <i>all defaults</i>); |
|---|
| 35 | |
|---|
| 36 | <i>// there is not a non-named parameter version of this function</i> |
|---|
| 37 | </PRE> |
|---|
| 38 | |
|---|
| 39 | <P> |
|---|
| 40 | The <TT>connected_components()</TT> functions compute the connected |
|---|
| 41 | components of an undirected graph using a DFS-based approach. A |
|---|
| 42 | <b><I>connected component</I></b> of an undirected graph is a set of |
|---|
| 43 | vertices that are all reachable from each other. If the connected |
|---|
| 44 | components need to be maintained while a graph is growing the |
|---|
| 45 | disjoint-set based approach of function <a |
|---|
| 46 | href="./incremental_components.html"> |
|---|
| 47 | <TT>incremental_components()</TT></a> is faster. For ``static'' graphs |
|---|
| 48 | this DFS-based approach is faster [<A |
|---|
| 49 | HREF="bibliography.html#clr90">8</A>]. |
|---|
| 50 | |
|---|
| 51 | <P> |
|---|
| 52 | The output of the algorithm is recorded in the component property map |
|---|
| 53 | <TT>comp</TT>, which will contain numbers giving the component number |
|---|
| 54 | assigned to each vertex. The total number of components is the return |
|---|
| 55 | value of the function. |
|---|
| 56 | |
|---|
| 57 | <H3>Where Defined</H3> |
|---|
| 58 | |
|---|
| 59 | <P> |
|---|
| 60 | <a href="../../../boost/graph/connected_components.hpp"><TT>boost/graph/connected_components.hpp</TT></a> |
|---|
| 61 | |
|---|
| 62 | |
|---|
| 63 | <h3>Parameters</h3> |
|---|
| 64 | |
|---|
| 65 | IN: <tt>const Graph& g</tt> |
|---|
| 66 | <blockquote> |
|---|
| 67 | An undirected graph. The graph type must be a model of <a |
|---|
| 68 | href="VertexListGraph.html">Vertex List Graph</a> and <a |
|---|
| 69 | href="IncidenceGraph.html">Incidence Graph</a>.<br> |
|---|
| 70 | |
|---|
| 71 | <b>Python</b>: The parameter is named <tt>graph</tt>. |
|---|
| 72 | </blockquote> |
|---|
| 73 | |
|---|
| 74 | OUT: <tt>ComponentMap c</tt> |
|---|
| 75 | <blockquote> |
|---|
| 76 | The algorithm computes how many connected components are in the graph, |
|---|
| 77 | and assigning each component an integer label. The algorithm then |
|---|
| 78 | records which component each vertex in the graph belongs to by |
|---|
| 79 | recording the component number in the component property map. The |
|---|
| 80 | <tt>ComponentMap</tt> type must be a model of <a |
|---|
| 81 | href="../../property_map/WritablePropertyMap.html">Writable Property |
|---|
| 82 | Map</a>. The value type shouch be an integer type, preferably the same |
|---|
| 83 | as the <tt>vertices_size_type</tt> of the graph. The key type must be |
|---|
| 84 | the graph's vertex descriptor type.<br> |
|---|
| 85 | |
|---|
| 86 | <b>Python</b>: Must be an <tt>vertex_int_map</tt> for the graph.<br> |
|---|
| 87 | <b>Python default</b>: <tt>graph.get_vertex_int_map("component")</tt> |
|---|
| 88 | </blockquote> |
|---|
| 89 | |
|---|
| 90 | <h3>Named Parameters</h3> |
|---|
| 91 | |
|---|
| 92 | UTIL: <tt>color_map(ColorMap color)</tt> |
|---|
| 93 | <blockquote> |
|---|
| 94 | This is used by the algorithm to keep track of its progress through |
|---|
| 95 | the graph. The type <tt>ColorMap</tt> must be a model of <a |
|---|
| 96 | href="../../property_map/ReadWritePropertyMap.html">Read/Write |
|---|
| 97 | Property Map</a> and its key type must be the graph's vertex |
|---|
| 98 | descriptor type and the value type of the color map must model |
|---|
| 99 | <a href="./ColorValue.html">ColorValue</a>.<br> |
|---|
| 100 | <b>Default:</b> an <a |
|---|
| 101 | href="../../property_map/iterator_property_map.html"> |
|---|
| 102 | </tt>iterator_property_map</tt></a> created from a |
|---|
| 103 | <tt>std::vector</tt> of <tt>default_color_type</tt> of size |
|---|
| 104 | <tt>num_vertices(g)</tt> and using the <tt>i_map</tt> for the index |
|---|
| 105 | map.<br> |
|---|
| 106 | <b>Python</b>: The color map must be a <tt>vertex_color_map</tt> for |
|---|
| 107 | the graph. |
|---|
| 108 | </blockquote> |
|---|
| 109 | |
|---|
| 110 | IN: <tt>vertex_index_map(VertexIndexMap i_map)</tt> |
|---|
| 111 | <blockquote> |
|---|
| 112 | This maps each vertex to an integer in the range <tt>[0, |
|---|
| 113 | num_vertices(g))</tt>. This parameter is only necessary when the |
|---|
| 114 | default color property map is used. The type <tt>VertexIndexMap</tt> |
|---|
| 115 | must be a model of <a |
|---|
| 116 | href="../../property_map/ReadablePropertyMap.html">Readable Property |
|---|
| 117 | Map</a>. The value type of the map must be an integer type. The |
|---|
| 118 | vertex descriptor type of the graph needs to be usable as the key |
|---|
| 119 | type of the map.<br> |
|---|
| 120 | |
|---|
| 121 | <b>Default:</b> <tt>get(vertex_index, g)</tt><br> |
|---|
| 122 | <b>Python</b>: Unsupported parameter. |
|---|
| 123 | </blockquote> |
|---|
| 124 | |
|---|
| 125 | |
|---|
| 126 | <H3>Complexity</H3> |
|---|
| 127 | |
|---|
| 128 | <P> |
|---|
| 129 | The time complexity for the connected components algorithm is also |
|---|
| 130 | <i>O(V + E)</i>. |
|---|
| 131 | |
|---|
| 132 | <P> |
|---|
| 133 | |
|---|
| 134 | <h3>See Also</h3> |
|---|
| 135 | |
|---|
| 136 | <a href="./strong_components.html"><tt>strong_components()</tt></a> |
|---|
| 137 | and <a href="./incremental_components.html"><tt>incremental_components()</tt></a> |
|---|
| 138 | |
|---|
| 139 | <H3>Example</H3> |
|---|
| 140 | |
|---|
| 141 | <P> |
|---|
| 142 | The file <a |
|---|
| 143 | href="../example/connected_components.cpp"><tt>examples/connected_components.cpp</tt></a> |
|---|
| 144 | contains an example of calculating the connected components of an |
|---|
| 145 | undirected graph. |
|---|
| 146 | |
|---|
| 147 | <br> |
|---|
| 148 | <HR> |
|---|
| 149 | <TABLE> |
|---|
| 150 | <TR valign=top> |
|---|
| 151 | <TD nowrap>Copyright © 2000-2001</TD><TD> |
|---|
| 152 | <A HREF="../../../people/jeremy_siek.htm">Jeremy Siek</A>, Indiana University (<A HREF="mailto:jsiek@osl.iu.edu">jsiek@osl.iu.edu</A>) |
|---|
| 153 | </TD></TR></TABLE> |
|---|
| 154 | |
|---|
| 155 | </BODY> |
|---|
| 156 | </HTML> |
|---|
