123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160 |
- <HTML>
- <!--
- Copyright 2010 The Trustees of Indiana University.
-
- Distributed under the Boost Software License, Version 1.0.
- (See accompanying file LICENSE_1_0.txt or copy at
- http://www.boost.org/LICENSE_1_0.txt)
-
- Authors: Jeremiah Willcock
- Jeremy Siek (due to adaptation from depth_first_search.html)
- Andrew Lumsdaine
- -->
- <Head>
- <Title>Boost Graph Library: Random Spanning Tree</Title>
- <BODY BGCOLOR="#ffffff" LINK="#0000ee" TEXT="#000000" VLINK="#551a8b"
- ALINK="#ff0000">
- <IMG SRC="../../../boost.png"
- ALT="C++ Boost" width="277" height="86">
- <BR Clear>
- <TT>random_spanning_tree</TT>
- </H1>
- <P>
- <PRE>
- <i>// named parameter version</i>
- template <class Graph, class Gen, class class P, class T, class R>
- void random_spanning_tree(Graph& G,
- Gen& gen,
- const bgl_named_params<P, T, R>& params);
- <i>// non-named parameter versions</i>
- template <class Graph, class Gen, class PredMap, class WeightMap, class ColorMap>
- void random_spanning_tree(const Graph& g, Gen& gen, vertex_descriptor root,
- PredMap pred, WeightMap weight, ColorMap color);
- </PRE>
- <p>
- The <tt>random_spanning_tree()</tt> function generates a random spanning tree
- on a directed or undirected graph. The algorithm used is Wilson's algorithm (<a
- href="bibliography.html#wilson96generating">73</a>, based on <!-- (FIXME: add
- documentation for loop_erased_random_walk()) <a
- href="loop_erased_random_walk.html"> -->loop-erased random walks<!-- </a> -->. There must
- be a path from every non-root vertex of the graph to the root;
- the algorithm typically enters an infinite loop when
- given a graph that does not satisfy this property, but may also throw the
- exception <tt>loop_erased_random_walk_stuck</tt> if the search reaches a vertex
- with no outgoing edges. Both weighted and unweighted versions of
- <tt>random_spanning_tree()</tt> are
- implemented. In the unweighted version, all spanning trees are equally likely.
- In the weighted version, the probability of a particular spanning tree being
- selected is the product of its edge weights.
- In the non-named-parameter
- version of the algorithm, the unweighted version can be selected by passing an
- object of type <tt>static_property_map<double></tt> as the weight map.
- In the named-parameter version, leaving off the <tt>weight_map</tt> parameter
- has the same effect.
- </p>
- <H3>Where Defined</H3>
- <P>
- <a href="../../../boost/graph/random_spanning_tree.hpp"><TT>boost/graph/random_spanning_tree.hpp</TT></a>
- <h3>Parameters</h3>
- IN: <tt>const Graph& g</tt>
- <blockquote>
- An undirected graph. The graph type must
- be a model of <a href="./IncidenceGraph.html">Incidence Graph</a>
- and <a href="./VertexListGraph.html">Vertex List Graph</a>.<br>
- </blockquote>
- IN: <tt>Gen& gen</tt>
- <blockquote>
- A random number generator. The generator type must
- be a model of <a
- href="../../../doc/html/boost_random/reference.html#boost_random.reference.concepts.uniform_random_number_generator">Uniform
- Random Number Generator</a> or a pointer or reference to such a type.<br>
- </blockquote>
- <h3>Named Parameters</h3>
- IN: <tt>root_vertex(vertex_descriptor root)</tt>
- <blockquote>
- This parameter, whose type must be the vertex descriptor type of
- <tt>Graph</tt>, gives the root of the tree to be generated. The default is
- <tt>*vertices(g).first</tt>.<br>
- </blockquote>
- UTIL: <tt>color_map(ColorMap color)</tt>
- <blockquote>
- This is used by the algorithm to keep track of its progress through
- the graph. The type <tt>ColorMap</tt> must be a model of <a
- href="../../property_map/doc/ReadWritePropertyMap.html">Read/Write
- Property Map</a> and its key type must be the graph's vertex
- descriptor type and the value type of the color map must model
- <a href="./ColorValue.html">ColorValue</a>.<br>
- <b>Default:</b> a <tt>two_bit_color_map</tt> of size
- <tt>num_vertices(g)</tt> and using the <tt>i_map</tt> for the index
- map.<br>
- </blockquote>
- IN: <tt>vertex_index_map(VertexIndexMap i_map)</tt>
- <blockquote>
- This maps each vertex to an integer in the range <tt>[0,
- num_vertices(g))</tt>. This parameter is only necessary when the
- default color property map is used. The type <tt>VertexIndexMap</tt>
- must be a model of <a
- href="../../property_map/doc/ReadablePropertyMap.html">Readable Property
- Map</a>. The value type of the map must be an integer type. The
- vertex descriptor type of the graph needs to be usable as the key
- type of the map.<br>
- </blockquote>
- OUT: <tt>predecessor_map(PredMap pred)</tt>
- <blockquote>
- This map, on output, will contain the predecessor of each vertex in the graph
- in the spanning tree. The value
- <tt>graph_traits<Graph>::null_vertex()</tt> will be used as the
- predecessor of the root of the tree. The type <tt>PredMap</tt> must be a
- model of
- <a
- href="../../property_map/doc/ReadWritePropertyMap.html">Read/Write Property
- Map</a>. The key and value types of the map must both be the graph's vertex type.<br>
- </blockquote>
- IN: <tt>weight_map(WeightMap weight)</tt>
- <blockquote>
- This map contains the weight of each edge in the graph. The probability of
- any given spanning tree being produced as the result of the algorithm is
- proportional to the product of its edge weights. If the weight map is
- omitted, a default that gives an equal weight to each edge will be used; a
- faster algorithm that relies on constant weights will also be invoked.
- The type <tt>WeightMap</tt> must be a
- model of
- <a
- href="../../property_map/doc/ReadablePropertyMap.html">Readable Property
- Map</a>. The key type of the map must be the graph's edge type, and the value
- type must be a real number type (such as <tt>double</tt>).<br>
- </blockquote>
- <br>
- <HR>
- <TABLE>
- <TR valign=top>
- <TD nowrap>Copyright © 2000-2001</TD><TD>
- <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>)<br>
- <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>
- <A HREF="https://homes.cs.washington.edu/~al75">Andrew Lumsdaine</A>,
- Indiana University (<A
- HREF="mailto:lums@osl.iu.edu">lums@osl.iu.edu</A>)
- </TD></TR></TABLE>
- </BODY>
- </HTML>
|