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