...one of the most highly
regarded and expertly designed C++ library projects in the
world.

— Herb Sutter and Andrei
Alexandrescu, C++
Coding Standards

// named parameter versiontemplate <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);// non-named parameter versionstemplate <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);

The `random_spanning_tree()` function generates a random spanning tree
on a directed or undirected graph. The algorithm used is Wilson's algorithm (73), based on loop-erased random walks. 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 `loop_erased_random_walk_stuck` if the search reaches a vertex
with no outgoing edges. Both weighted and unweighted versions of
`random_spanning_tree()` 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 `static_property_map<double>` as the weight map.
In the named-parameter version, leaving off the `weight_map` parameter
has the same effect.

`boost/graph/random_spanning_tree.hpp`

An undirected graph. The graph type must be a model of Incidence Graph and Vertex List Graph.IN:

A random number generator. The generator type must be a model of Uniform Random Number Generator or a pointer or reference to such a type.

This parameter, whose type must be the vertex descriptor type ofUTIL:Graph, gives the root of the tree to be generated. The default is*vertices(g).first.

This is used by the algorithm to keep track of its progress through the graph. The typeIN:ColorMapmust be a model of Read/Write Property Map and its key type must be the graph's vertex descriptor type and the value type of the color map must model ColorValue.

Default:atwo_bit_color_mapof sizenum_vertices(g)and using thei_mapfor the index map.

This maps each vertex to an integer in the rangeOUT:[0, num_vertices(g)). This parameter is only necessary when the default color property map is used. The typeVertexIndexMapmust be a model of Readable Property Map. 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.

This map, on output, will contain the predecessor of each vertex in the graph in the spanning tree. The valueIN:graph_traits<Graph>::null_vertex()will be used as the predecessor of the root of the tree. The typePredMapmust be a model of Read/Write Property Map. The key and value types of the map must both be the graph's vertex type.

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 typeWeightMapmust be a model of Readable Property Map. The key type of the map must be the graph's edge type, and the value type must be a real number type (such asdouble).

Copyright © 2000-2001 |
Jeremy Siek,
Indiana University (jsiek@osl.iu.edu) Lie-Quan Lee, Indiana University (llee@cs.indiana.edu) Andrew Lumsdaine, Indiana University (lums@osl.iu.edu) |