ceph/src/boost/libs/graph/doc/connected_components.html

   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 &lt;class VertexListGraph, class ComponentMap, class P, class T, class R&gt;
  28 typename property_traits&lt;ComponentMap&gt;::value_type
  29 connected_components(VertexListGraph&amp; G, ComponentMap comp,
  30     const bgl_named_params&lt;P, T, R&gt;&amp; 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&nbsp;[<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&amp; 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/doc/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/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
 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/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>
 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 &copy; 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>