ceph/src/boost/libs/graph/doc/prim_minimum_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: Prim 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
  20 <H1><A NAME="sec:prim"></A>
  21 <img src="figs/python.gif" alt="(Python)"/>
  22 <TT>prim_minimum_spanning_tree</TT>
  23 </H1>
  24
  25 <P>
  26 <PRE>
  27 <i>// named parameter version</i>
  28 template &lt;class Graph, class PredMap, class P, class T, class R&gt;
  29 void prim_minimum_spanning_tree(const Graph&amp; g, PredMap p_map,
  30   const bgl_named_params&lt;P, T, R&gt;&amp; params)
  31
  32 <i>// non-named parameter version</i>
  33 template &lt;class Graph, class DijkstraVisitor,
  34           class PredecessorMap, class DistanceMap,
  35           class WeightMap, class IndexMap&gt;
  36 void prim_minimum_spanning_tree(const Graph&amp; g,
  37    typename graph_traits&lt;Graph&gt;::vertex_descriptor s,
  38    PredecessorMap predecessor, DistanceMap distance, WeightMap weight,
  39    IndexMap index_map, DijkstraVisitor vis)
  40 </PRE>
  41
  42 <P>
  43 This is Prim's algorithm&nbsp;[<A
  44 HREF="bibliography.html#prim57:_short">25</A>,<A
  45 HREF="bibliography.html#clr90">8</A>,<A
  46 HREF="bibliography.html#tarjan83:_data_struct_network_algo">27</A>,<A
  47 HREF="bibliography.html#graham85">15</A>] for solving the minimum
  48 spanning tree problem for an undirected graph with weighted edges. A
  49 MST is a set of edges that connects all the vertices in the graph
  50 where the total weight of the edges in the tree is minimized.  See
  51 Section <A
  52 HREF="graph_theory_review.html#sec:minimum-spanning-tree">Minimum
  53 Spanning Tree Problem</A> for more details. The implementation is
  54 simply a call to <a
  55 href="./dijkstra_shortest_paths.html"><TT>dijkstra_shortest_paths()</TT></a>
  56 with the appropriate choice of comparison and combine functors.
  57 The pseudo-code for Prim's algorithm is listed below.
  58 The algorithm as implemented in Boost.Graph does not produce correct results on
  59 graphs with parallel edges.
  60 </p>
  61
  62 <table>
  63 <tr>
  64 <td valign="top">
  65 <pre>
  66 PRIM-MST(<i>G</i>, <i>s</i>, <i>w</i>)
  67   <b>for</b> each vertex <i>u</i> <i>in</i> <i>V[G]</i>
  68     <i>color[u] :=</i> WHITE
  69     <i>d[u] :=</i> <i>infinity</i>
  70   <b>end for</b>
  71   <i>color[s] :=</i> GRAY
  72   <i>d[s] := 0</i>
  73   ENQUEUE(<i>PQ</i>, <i>s</i>)
  74   <i>p[s] := s</i>
  75   <b>while</b> (<i>PQ != &Oslash;</i>)
  76     <i>u :=</i> DEQUEUE(<i>PQ</i>)
  77     <b>for</b> each <i>v in Adj[u]</i>
  78       <b>if</b> (<i>w(u,v) < d[v]</i>)
  79         <i>d[v] := w(u,v)</i>
  80         <i>p[v] := u</i>
  81         <b>if</b> (<i>color[v] = </i> WHITE)
  82           ENQUEUE(<i>PQ</i>, <i>v</i>)
  83           <i>color[v] :=</i> GRAY
  84         <b>else if</b> (<i>color[v] = </i> GRAY)
  85           UPDATE(<i>PQ</i>, <i>v</i>)
  86       <b>else</b>
  87         do nothing
  88     <b>end for</b>
  89     <i>color[u] :=</i> BLACK
  90   <b>end while</b>
  91   <b>return</b> (<i>p</i>, <i>d</i>)
  92 </pre>
  93 </td>
  94 <td valign="top">
  95 <pre>
  96
  97 initialize vertex <i>u</i>
  98
  99
 100
 101 start vertex <i>s</i>
 102 discover vertex <i>s</i>
 103
 104
 105 examine vertex <i>u</i>
 106 examining edge <i>(u,v)</i>
 107
 108 edge <i>(u,v)</i> relaxed
 109
 110
 111 discover vertex <i>v</i>
 112
 113
 114
 115
 116 edge <i>(u,v)</i> not relaxed
 117
 118 finish <i>u</i>
 119 </pre>
 120 </tr>
 121 </table>
 122
 123
 124 <H3>Where Defined</H3>
 125
 126 <P>
 127 <a href="../../../boost/graph/prim_minimum_spanning_tree.hpp"><TT>boost/graph/prim_minimum_spanning_tree.hpp</TT></a>
 128
 129 <P>
 130
 131 <h3>Parameters</h3>
 132
 133 IN: <tt>const Graph&amp; g</tt>
 134 <blockquote>
 135   An undirected graph. The type <tt>Graph</tt> must be a
 136   model of <a href="./VertexListGraph.html">Vertex List Graph</a>
 137   and <a href="./IncidenceGraph.html">Incidence Graph</a>.  It should not
 138   contain parallel edges.<br>
 139
 140   <b>Python</b>: The parameter is named <tt>graph</tt>.
 141 </blockquote>
 142
 143 OUT: <tt>PredecessorMap p_map</tt>
 144 <blockquote>
 145   The predecessor map records the edges in the minimum spanning
 146   tree. Upon completion of the algorithm, the edges
 147   <i>(p[u],u)</i> for all <i>u in V</i> are in the minimum spanning
 148   tree. If <i>p[u] = u</i> then <i>u</i> is either the root of the
 149   tree or is a vertex that is not reachable from the root.
 150   The <tt>PredecessorMap</tt> type must be a <a
 151   href="../../property_map/doc/ReadWritePropertyMap.html">Read/Write
 152   Property Map</a>
 153   with key and vertex types the same as the vertex descriptor type
 154   of the graph.<br>
 155
 156   <b>Python</b>: Must be a <tt>vertex_vertex_map</tt> for the graph.<br>
 157 </blockquote>
 158
 159 <h3>Named Parameters</h3>
 160
 161 IN: <tt>root_vertex(vertex_descriptor r)</tt>
 162 <blockquote>
 163   The vertex that will be the root of the minimum spanning tree.
 164   The choice of the root vertex is arbitrary.<br>
 165   <b>Default:</b> <tt>*vertices(g).first</tt>
 166 </blockquote>
 167
 168 IN: <tt>weight_map(WeightMap w_map)</tt>
 169 <blockquote>
 170   The weight or ``length'' of each edge in the graph.
 171   The type <tt>WeightMap</tt> must be a model of
 172   <a href="../../property_map/doc/ReadablePropertyMap.html">Readable Property Map</a>. The edge descriptor type of
 173   the graph needs to be usable as the key type for the weight
 174   map. The value type for the map must be
 175   the same as the value type of the distance map, and that type must be <a
 176     href="http://www.sgi.com/tech/stl/LessThanComparable.html">Less Than
 177       Comparable</a>.<br>
 178   <b>Default:</b>  <tt>get(edge_weight, g)</tt><br>
 179   <b>Python</b>: Must be an <tt>edge_double_map</tt> for the graph.<br>
 180   <b>Python default</b>: <tt>graph.get_edge_double_map("weight")</tt>
 181 </blockquote>
 182
 183 IN: <tt>vertex_index_map(VertexIndexMap i_map)</tt>
 184 <blockquote>
 185   This maps each vertex to an integer in the range <tt>[0,
 186     num_vertices(g))</tt>. This is necessary for efficient updates of the
 187   heap data structure when an edge is relaxed.  The type
 188   <tt>VertexIndexMap</tt> must be a model of
 189   <a href="../../property_map/doc/ReadablePropertyMap.html">Readable Property Map</a>. The value type of the map must be an
 190   integer type. The vertex descriptor type of the graph needs to be
 191   usable as the key type of the map.<br>
 192   <b>Default:</b> <tt>get(vertex_index, g)</tt>
 193     Note: if you use this default, make sure your graph has
 194     an internal <tt>vertex_index</tt> property. For example,
 195     <tt>adjacency_list</tt> with <tt>VertexList=listS</tt> does
 196     not have an internal <tt>vertex_index</tt> property.
 197    <br>
 198   <b>Python</b>: Unsupported parameter.
 199 </blockquote>
 200
 201 UTIL/OUT: <tt>distance_map(DistanceMap d_map)</tt>
 202 <blockquote>
 203   The weight of the spanning tree edge into each
 204   vertex in the graph <tt>g</tt> is recorded in this property map, with edges
 205   directed away from the spanning tree root.
 206   The type <tt>DistanceMap</tt> must be a model of <a
 207   href="../../property_map/doc/ReadWritePropertyMap.html">Read/Write
 208   Property Map</a>. The vertex descriptor type of the
 209   graph needs to be usable as the key type of the distance map, and the value
 210   type needs to be the same as the value type of the <tt>weight_map</tt>
 211   argument.<br>
 212   <b>Default:</b> <a href="../../property_map/doc/iterator_property_map.html">
 213   <tt>iterator_property_map</tt></a> created from a
 214   <tt>std::vector</tt> of the <tt>WeightMap</tt>'s value type of size
 215   <tt>num_vertices(g)</tt> and using the <tt>i_map</tt> for the index
 216   map.<br>
 217
 218   <b>Python</b>: Must be a <tt>vertex_double_map</tt> for the graph.<br>
 219 </blockquote>
 220
 221 UTIL/OUT: <tt>color_map(ColorMap c_map)</tt>
 222 <blockquote>
 223   This is used during the execution of the algorithm to mark the
 224   vertices. The vertices start out white and become gray when they are
 225   inserted in the queue. They then turn black when they are removed
 226   from the queue. At the end of the algorithm, vertices reachable from
 227   the source vertex will have been colored black. All other vertices
 228   will still be white. The type <tt>ColorMap</tt> must be a model of
 229   <a href="../../property_map/doc/ReadWritePropertyMap.html">Read/Write
 230   Property Map</a>. A vertex descriptor must be usable as the key type
 231   of the map, and the value type of the map must be a model of
 232   <a href="./ColorValue.html">Color Value</a>.<br>
 233   <b>Default:</b> an <a
 234   href="../../property_map/doc/iterator_property_map.html">
 235   <tt>iterator_property_map</tt></a> created from a <tt>std::vector</tt>
 236   of <tt>default_color_type</tt> of size <tt>num_vertices(g)</tt> and
 237   using the <tt>i_map</tt> for the index map.<br>
 238
 239   <b>Python</b>: The color map must be a <tt>vertex_color_map</tt> for
 240   the graph.
 241 </blockquote>
 242
 243 OUT: <tt>visitor(DijkstraVisitor v)</tt>
 244 <blockquote>
 245   Use this to specify actions that you would like to happen
 246   during certain event points within the algorithm.
 247   The type <tt>DijkstraVisitor</tt> must be a model of the
 248   <a href="./DijkstraVisitor.html">Dijkstra Visitor</a> concept.
 249   The visitor object is passed by value <a
 250   href="#1">[1]</a>.<br>
 251   <b>Default:</b> <tt>dijkstra_visitor&lt;null_visitor&gt;</tt><br>
 252
 253   <b>Python</b>: The parameter should be an object that derives from
 254   the <a
 255   href="DijkstraVisitor.html#python"><tt>DijkstraVisitor</tt></a> type
 256   of the graph.
 257 </blockquote>
 258
 259 <H3>Complexity</H3>
 260
 261 <P>
 262 The time complexity is <i>O(E log V)</i>.
 263
 264 <P>
 265
 266 <H3>Example</H3>
 267
 268 <P>
 269 The file <a
 270 href="../example/prim-example.cpp"><TT>examples/prim-example.cpp</TT></a>
 271 contains an example of using Prim's algorithm.
 272
 273
 274 <h3>Notes</h3>
 275
 276 <p><a name="1">[1]</a>
 277   Since the visitor parameter is passed by value, if your visitor
 278   contains state then any changes to the state during the algorithm
 279   will be made to a copy of the visitor object, not the visitor object
 280   passed in. Therefore you may want the visitor to hold this state by
 281   pointer or reference.
 282
 283 <br>
 284 <HR>
 285 <TABLE>
 286 <TR valign=top>
 287 <TD nowrap>Copyright &copy; 2000-2001</TD><TD>
 288 <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>)
 289 </TD></TR></TABLE>
 290
 291 </BODY>
 292 </HTML>