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

   1 <HTML>
   2 <!--
   3      Copyright (c) Jeremy Siek 2000
   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: Kruskal Minimum Spanning Tree</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><A NAME="sec:kruskal">
  20 <img src="figs/python.gif" alt="(Python)"/>
  21 <TT>kruskal_minimum_spanning_tree</TT>
  22 </H1>
  23
  24 <PRE>
  25 template &lt;class Graph, class OutputIterator, class P, class T, class R&gt;
  26 OutputIterator
  27 kruskal_minimum_spanning_tree(Graph&amp; g, OutputIterator tree_edges,
  28     const bgl_named_params&lt;P, T, R&gt;&amp; params = <i>all defaults</i>);
  29 </PRE>
  30
  31 <P>
  32 The <tt>kruskal_minimum_spanning_tree()</tt> function find a minimum
  33 spanning tree (MST) in an undirected graph with weighted edges. A MST is a
  34 set of edges that connects all the vertices in the graph where the
  35 total weight of the edges in the tree is minimized.  For more details,
  36 see section <a
  37 href="graph_theory_review.html#sec:minimum-spanning-tree">Minimum
  38 Spanning Tree Problem</a>.  The edges in the MST are output to the
  39 <tt>tree_edges</tt> output iterator.  This function uses Kruskal's
  40 algorithm to compute the MST&nbsp;[<A
  41 HREF="bibliography.html#kruskal56">18</A>,<A
  42 HREF="bibliography.html#clr90">8</A>,<A
  43 HREF="bibliography.html#tarjan83:_data_struct_network_algo">27</A>,<A
  44 HREF="bibliography.html#graham85">15</A>].
  45 </p>
  46 <p>
  47 Kruskal's algorithm starts with each vertex in a tree by itself, and
  48 with no edges in the minimum spanning tree <i>T</i>. The algorithm
  49 then examines each edge in the graph in order of increasing edge
  50 weight. If an edge connects two vertices in different trees the
  51 algorithm merges the two trees into a single tree and adds the edge to
  52 <i>T</i>. We use the ``union by rank'' and ``path compression''
  53 heuristics to provide fast implementations of the disjoint set
  54 operations (<tt>MAKE-SET</tt>, <tt>FIND-SET</tt>, and
  55 <tt>UNION-SET</tt>).  The algorithm is as follows:
  56 </p>
  57
  58 <pre>
  59 KRUSKAL-MST(<i>G</i>, <i>w</i>)
  60   <i>T := &Oslash;</i>
  61   <b>for</b> each vertex <i>u in V</i>
  62     MAKE-SET(<i>DS</i>, <i>u</i>)
  63   <b>end for</b>
  64   <b>for</b> each edge <i>(u,v) in E</i> in order of nondecreasing weight
  65     <b>if</b> FIND-SET(<i>DS</i>, <i>u</i>) != FIND-SET(<i>DS</i>, <i>v</i>)
  66       UNION-SET(<i>DS</i>, <i>u</i>, <i>v</i>)
  67       <i>T := T U {(u,v)}</i>
  68   <b>end for</b>
  69   <b>return</b> <i>T</i>
  70 </pre>
  71
  72
  73 <H3>Where Defined</H3>
  74
  75 <P>
  76 <a href="../../../boost/graph/kruskal_min_spanning_tree.hpp"><TT>boost/graph/kruskal_min_spanning_tree.hpp</TT></a>
  77
  78 <P>
  79
  80 <h3>Parameters</h3>
  81
  82 IN: <tt>const Graph&amp; g</tt>
  83 <blockquote>
  84   An undirected graph. The graph type must be a model of
  85   <a href="./VertexListGraph.html">Vertex List Graph</a>
  86   and <a href="./EdgeListGraph.html">Edge List Graph</a>.<br>
  87
  88   <b>Python</b>: The parameter is named <tt>graph</tt>.
  89 </blockquote>
  90
  91 IN: <tt>OutputIterator spanning_tree_edges</tt>
  92 <blockquote>
  93    The edges of the minimum spanning tree are output to this <a
  94    href="http://www.sgi.com/tech/stl/OutputIterator.html">Output
  95    Iterator</a>.<br>
  96
  97    <b>Python</b>: This parameter is not used in Python. Instead, a
  98    Python <tt>list</tt> containing all of the spanning tree edges is
  99    returned.
 100 </blockquote>
 101
 102
 103 <h3>Named Parameters</h3>
 104
 105 IN: <tt>weight_map(WeightMap w_map)</tt>
 106 <blockquote>
 107 The weight or ``length'' of
 108   each edge in the graph.  The <tt>WeightMap</tt> type must be a model
 109   of <a href="../../property_map/doc/ReadablePropertyMap.html">Readable
 110   Property Map</a> and its value type must be <a
 111   href="http://www.sgi.com/tech/stl/LessThanComparable.html">Less Than
 112   Comparable</a>. The key type of this map needs to be the graph's
 113   edge descriptor type.<br>
 114   <b>Default:</b> <tt>get(edge_weight, g)</tt><br>
 115   <b>Python</b>: Must be an <tt>edge_double_map</tt> for the graph.<br>
 116   <b>Python default</b>: <tt>graph.get_edge_double_map("weight")</tt>
 117 </blockquote>
 118
 119 UTIL: <tt>rank_map(RankMap r_map)</tt>
 120 <blockquote>
 121   This is used by the disjoint sets data structure.
 122   The type <tt>RankMap</tt> must be a model of <a
 123   href="../../property_map/doc/ReadWritePropertyMap.html">Read/Write
 124   Property Map</a>. The vertex descriptor type of the graph needs to
 125   be usable as the key type of the rank map. The value type of the
 126   rank map must be an integer type.<br>
 127   <b>Default:</b> an <a
 128   href="../../property_map/doc/iterator_property_map.html">
 129   <tt>iterator_property_map</tt></a> created from a
 130   <tt>std::vector</tt> of the integers of size
 131   <tt>num_vertices(g)</tt> and using the <tt>i_map</tt> for the index
 132   map.<br>
 133
 134   <b>Python</b>: Unsupported parameter.
 135 </blockquote>
 136
 137 UTIL: <tt>predecessor_map(PredecessorMap p_map)</tt>
 138 <blockquote>
 139   This is used by the disjoint sets data structure, and is <b>not</b>
 140   used for storing predecessors in the spanning tree.  The predecessors
 141   of the spanning tree can be obtained from the spanning tree edges
 142   output. The type <tt>PredecessorMap</tt> must be a model of <a
 143   href="../../property_map/doc/ReadWritePropertyMap.html">Read/Write
 144   Property Map</a>. The key type value types of the predecessor map
 145   must be the vertex descriptor type of the graph. <br>
 146   <b>Default:</b> an <a
 147   href="../../property_map/doc/iterator_property_map.html">
 148   <tt>iterator_property_map</tt></a> created from a
 149   <tt>std::vector</tt> of vertex descriptors of size
 150   <tt>num_vertices(g)</tt> and using the <tt>i_map</tt> for the index
 151   map.<br>
 152
 153   <b>Python</b>: Unsupported parameter.
 154 </blockquote>
 155
 156 IN: <tt>vertex_index_map(VertexIndexMap i_map)</tt>
 157 <blockquote>
 158   This maps each vertex to an integer in the range <tt>[0,
 159   num_vertices(g))</tt>. This is only necessary if the default is used
 160   for the rank or predecessor maps. The type <tt>VertexIndexMap</tt>
 161   must be a model of <a
 162   href="../../property_map/doc/ReadablePropertyMap.html">Readable Property
 163   Map</a>. The value type of the map must be an integer type. The
 164   vertex descriptor type of the graph needs to be usable as the key
 165   type of the map.<br>
 166   <b>Default:</b> <tt>get(vertex_index, g)</tt>
 167     Note: if you use this default, make sure your graph has
 168     an internal <tt>vertex_index</tt> property. For example,
 169     <tt>adjacency_list</tt> with <tt>VertexList=listS</tt> does
 170     not have an internal <tt>vertex_index</tt> property.
 171    <br>
 172
 173   <b>Python</b>: Unsupported parameter.
 174 </blockquote>
 175
 176
 177 <H3>Complexity</H3>
 178
 179 <P>
 180 The time complexity is <i>O(E log E)</i>
 181
 182 <H3>Example</H3>
 183
 184 <P>
 185 The file <a
 186 href="../example/kruskal-example.cpp"><TT>examples/kruskal-example.cpp</TT></a>
 187 contains an example of using Kruskal's algorithm.
 188
 189
 190 <br>
 191 <HR>
 192 <TABLE>
 193 <TR valign=top>
 194 <TD nowrap>Copyright &copy; 2000-2001</TD><TD>
 195 <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>)
 196 </TD></TR></TABLE>
 197
 198 </BODY>
 199 </HTML>