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> 27template <class VertexListGraph, class ComponentMap, class P, class T, class R> 28typename property_traits<ComponentMap>::value_type 29connected_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> 36The <TT>connected_components()</TT> functions compute the connected 37components 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 39vertices that are all reachable from each other. If the connected 40components need to be maintained while a graph is growing the 41disjoint-set based approach of function <a 42href="./incremental_components.html"> 43<TT>incremental_components()</TT></a> is faster. For ``static'' graphs 44this DFS-based approach is faster [<A 45HREF="bibliography.html#clr90">8</A>]. 46 47<P> 48The output of the algorithm is recorded in the component property map 49<TT>comp</TT>, which will contain numbers giving the component number 50assigned to each vertex. The total number of components is the return 51value 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 61IN: <tt>const Graph& g</tt> 62<blockquote> 63An undirected graph. The graph type must be a model of <a 64href="VertexListGraph.html">Vertex List Graph</a> and <a 65href="IncidenceGraph.html">Incidence Graph</a>.<br> 66 67<b>Python</b>: The parameter is named <tt>graph</tt>. 68</blockquote> 69 70OUT: <tt>ComponentMap c</tt> 71<blockquote> 72The algorithm computes how many connected components are in the graph, 73and assigning each component an integer label. The algorithm then 74records which component each vertex in the graph belongs to by 75recording the component number in the component property map. The 76<tt>ComponentMap</tt> type must be a model of <a 77href="../../property_map/doc/WritablePropertyMap.html">Writable Property 78Map</a>. The value type should be an integer type, preferably the same 79as the <tt>vertices_size_type</tt> of the graph. The key type must be 80the 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 88UTIL: <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/doc/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/doc/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 106IN: <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/doc/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>adjacency_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> 130The 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> 138and <a href="./incremental_components.html"><tt>incremental_components()</tt></a> 139 140<H3>Example</H3> 141 142<P> 143The file <a 144href="../example/connected_components.cpp"><tt>examples/connected_components.cpp</tt></a> 145contains an example of calculating the connected components of an 146undirected graph. 147 148<br> 149<HR> 150<TABLE> 151<TR valign=top> 152<TD nowrap>Copyright © 2000-2001</TD><TD> 153<A HREF="http://www.boost.org/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> 158
