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> 28template <class Graph, class Gen, class class P, class T, class R> 29void random_spanning_tree(Graph& G, 30 Gen& gen, 31 const bgl_named_params<P, T, R>& params); 32 33<i>// non-named parameter versions</i> 34template <class Graph, class Gen, class PredMap, class WeightMap, class ColorMap> 35void random_spanning_tree(const Graph& g, Gen& gen, vertex_descriptor root, 36 PredMap pred, WeightMap weight, ColorMap color); 37</PRE> 38 39<p> 40The <tt>random_spanning_tree()</tt> function generates a random spanning tree 41on a directed or undirected graph. The algorithm used is Wilson's algorithm (<a 42href="bibliography.html#wilson96generating">73</a>, based on <!-- (FIXME: add 43documentation for loop_erased_random_walk()) <a 44href="loop_erased_random_walk.html"> -->loop-erased random walks<!-- </a> -->. There must 45be a path from every non-root vertex of the graph to the root; 46the algorithm typically enters an infinite loop when 47given a graph that does not satisfy this property, but may also throw the 48exception <tt>loop_erased_random_walk_stuck</tt> if the search reaches a vertex 49with no outgoing edges. Both weighted and unweighted versions of 50<tt>random_spanning_tree()</tt> are 51implemented. In the unweighted version, all spanning trees are equally likely. 52In the weighted version, the probability of a particular spanning tree being 53selected is the product of its edge weights. 54In the non-named-parameter 55version of the algorithm, the unweighted version can be selected by passing an 56object of type <tt>static_property_map<double></tt> as the weight map. 57In the named-parameter version, leaving off the <tt>weight_map</tt> parameter 58has 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 68IN: <tt>const Graph& 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 75IN: <tt>Gen& 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 86IN: <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 93UTIL: <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 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</blockquote> 117 118OUT: <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<Graph>::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 130IN: <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 © 2000-2001</TD><TD> 150<A HREF="http://www.boost.org/people/jeremy_siek.htm">Jeremy Siek</A>, 151Indiana University (<A 152HREF="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="https://homes.cs.washington.edu/~al75">Andrew Lumsdaine</A>, 155Indiana University (<A 156HREF="mailto:lums@osl.iu.edu">lums@osl.iu.edu</A>) 157</TD></TR></TABLE> 158 159</BODY> 160</HTML> 161
