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

   1 <HTML>
   2 <!--
   3      Copyright 2010 The Trustees of Indiana University.
   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       Authors: Jeremiah Willcock
  10                Jeremy Siek (due to adaptation from depth_first_search.html)
  11                Andrew Lumsdaine
  12   -->
  13 <Head>
  14 <Title>Boost Graph Library: Random Spanning Tree</Title>
  15 <BODY BGCOLOR="#ffffff" LINK="#0000ee" TEXT="#000000" VLINK="#551a8b"
  16         ALINK="#ff0000">
  17 <IMG SRC="../../../boost.png"
  18      ALT="C++ Boost" width="277" height="86">
  19
  20 <BR Clear>
  21
  22 <TT>random_spanning_tree</TT>
  23 </H1>
  24
  25 <P>
  26 <PRE>
  27 <i>// named parameter version</i>
  28 template &lt;class Graph, class Gen, class class P, class T, class R&gt;
  29 void random_spanning_tree(Graph&amp; G,
  30   Gen&amp; gen,
  31   const bgl_named_params&lt;P, T, R&gt;&amp; params);
  32
  33 <i>// non-named parameter versions</i>
  34 template &lt;class Graph, class Gen, class PredMap, class WeightMap, class ColorMap&gt;
  35 void random_spanning_tree(const Graph&amp; g, Gen&amp; gen, vertex_descriptor root,
  36   PredMap pred, WeightMap weight, ColorMap color);
  37 </PRE>
  38
  39 <p>
  40 The <tt>random_spanning_tree()</tt> function generates a random spanning tree
  41 on a directed or undirected graph.  The algorithm used is Wilson's algorithm (<a
  42 href="bibliography.html#wilson96generating">73</a>, based on <!-- (FIXME: add
  43 documentation for loop_erased_random_walk()) <a
  44 href="loop_erased_random_walk.html"> -->loop-erased random walks<!-- </a> -->.  There must
  45 be a path from every non-root vertex of the graph to the root;
  46 the algorithm typically enters an infinite loop when
  47 given a graph that does not satisfy this property, but may also throw the
  48 exception <tt>loop_erased_random_walk_stuck</tt> if the search reaches a vertex
  49 with no outgoing edges.  Both weighted and unweighted versions of
  50 <tt>random_spanning_tree()</tt> are
  51 implemented.  In the unweighted version, all spanning trees are equally likely.
  52 In the weighted version, the probability of a particular spanning tree being
  53 selected is the product of its edge weights.
  54 In the non-named-parameter
  55 version of the algorithm, the unweighted version can be selected by passing an
  56 object of type <tt>static_property_map&lt;double&gt;</tt> as the weight map.
  57 In the named-parameter version, leaving off the <tt>weight_map</tt> parameter
  58 has the same effect.
  59 </p>
  60
  61 <H3>Where Defined</H3>
  62
  63 <P>
  64 <a href="../../../boost/graph/random_spanning_tree.hpp"><TT>boost/graph/random_spanning_tree.hpp</TT></a>
  65
  66 <h3>Parameters</h3>
  67
  68 IN: <tt>const Graph&amp; g</tt>
  69 <blockquote>
  70   An undirected graph. The graph type must
  71   be a model of <a href="./IncidenceGraph.html">Incidence Graph</a>
  72   and <a href="./VertexListGraph.html">Vertex List Graph</a>.<br>
  73 </blockquote>
  74
  75 IN: <tt>Gen&amp; gen</tt>
  76 <blockquote>
  77   A random number generator. The generator type must
  78   be a model of <a
  79   href="../../../doc/html/boost_random/reference.html#boost_random.reference.concepts.uniform_random_number_generator">Uniform
  80   Random Number Generator</a> or a pointer or reference to such a type.<br>
  81 </blockquote>
  82
  83
  84 <h3>Named Parameters</h3>
  85
  86 IN: <tt>root_vertex(vertex_descriptor root)</tt>
  87 <blockquote>
  88   This parameter, whose type must be the vertex descriptor type of
  89   <tt>Graph</tt>, gives the root of the tree to be generated.  The default is
  90   <tt>*vertices(g).first</tt>.<br>
  91 </blockquote>
  92
  93 UTIL: <tt>color_map(ColorMap color)</tt>
  94 <blockquote>
  95   This is used by the algorithm to keep track of its progress through
  96   the graph. The type <tt>ColorMap</tt> must be a model of <a
  97   href="../../property_map/doc/ReadWritePropertyMap.html">Read/Write
  98   Property Map</a> and its key type must be the graph's vertex
  99   descriptor type and the value type of the color map must model
 100   <a href="./ColorValue.html">ColorValue</a>.<br>
 101   <b>Default:</b> a <tt>two_bit_color_map</tt> of size
 102   <tt>num_vertices(g)</tt> and using the <tt>i_map</tt> for the index
 103   map.<br>
 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 </blockquote>
 117
 118 OUT: <tt>predecessor_map(PredMap pred)</tt>
 119 <blockquote>
 120   This map, on output, will contain the predecessor of each vertex in the graph
 121   in the spanning tree.  The value
 122   <tt>graph_traits&lt;Graph&gt;::null_vertex()</tt> will be used as the
 123   predecessor of the root of the tree.  The type <tt>PredMap</tt> must be a
 124   model of
 125   <a
 126   href="../../property_map/doc/ReadWritePropertyMap.html">Read/Write Property
 127   Map</a>. The key and value types of the map must both be the graph's vertex type.<br>
 128 </blockquote>
 129
 130 IN: <tt>weight_map(WeightMap weight)</tt>
 131 <blockquote>
 132   This map contains the weight of each edge in the graph.  The probability of
 133   any given spanning tree being produced as the result of the algorithm is
 134   proportional to the product of its edge weights.  If the weight map is
 135   omitted, a default that gives an equal weight to each edge will be used; a
 136   faster algorithm that relies on constant weights will also be invoked.
 137   The type <tt>WeightMap</tt> must be a
 138   model of
 139   <a
 140   href="../../property_map/doc/ReadablePropertyMap.html">Readable Property
 141   Map</a>. The key type of the map must be the graph's edge type, and the value
 142   type must be a real number type (such as <tt>double</tt>).<br>
 143 </blockquote>
 144
 145 <br>
 146 <HR>
 147 <TABLE>
 148 <TR valign=top>
 149 <TD nowrap>Copyright &copy; 2000-2001</TD><TD>
 150 <A HREF="http://www.boost.org/people/jeremy_siek.htm">Jeremy Siek</A>,
 151 Indiana University (<A
 152 HREF="mailto:jsiek@osl.iu.edu">jsiek@osl.iu.edu</A>)<br>
 153 <A HREF="http://www.boost.org/people/liequan_lee.htm">Lie-Quan Lee</A>, Indiana University (<A HREF="mailto:llee@cs.indiana.edu">llee@cs.indiana.edu</A>)<br>
 154 <A HREF="http://www.osl.iu.edu/~lums">Andrew Lumsdaine</A>,
 155 Indiana University (<A
 156 HREF="mailto:lums@osl.iu.edu">lums@osl.iu.edu</A>)
 157 </TD></TR></TABLE>
 158
 159 </BODY>
 160 </HTML>