This documentation is being rewritten. If something looks off, please cross-check with the Boost 1.91.0 Boost.Graph docs and open an issue.

random_spanning_tree

Generates a random spanning tree on a directed or undirected graph.

Complexity: Expected O(tau) (unweighted), where tau is the mean hitting time
Defined in: <boost/graph/random_spanning_tree.hpp>

Example

#include <iostream>
#include <vector>
#include <random>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/random_spanning_tree.hpp>

int main() {
    using Graph = boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS>;
    using Vertex = boost::graph_traits<Graph>::vertex_descriptor;
    Graph g(5);
    boost::add_edge(0, 1, g); boost::add_edge(0, 2, g);
    boost::add_edge(1, 2, g); boost::add_edge(1, 3, g);
    boost::add_edge(2, 3, g); boost::add_edge(3, 4, g);
    boost::add_edge(2, 4, g);

    std::vector<Vertex> pred(num_vertices(g));
    std::vector<boost::default_color_type> color(num_vertices(g));
    std::mt19937 gen(42); // fixed seed for deterministic output
    boost::random_spanning_tree(g, gen, Vertex{0},
        boost::make_iterator_property_map(pred.begin(), get(boost::vertex_index, g)),
        boost::static_property_map<double>(1.0),
        boost::make_iterator_property_map(color.begin(), get(boost::vertex_index, g)));

    std::cout << "Random spanning tree edges:\n";
    for (Vertex v = 0; v < num_vertices(g); ++v) {
        if (pred[v] != boost::graph_traits<Graph>::null_vertex() && pred[v] != v)
            std::cout << "  " << pred[v] << " - " << v << "\n";
    }
}
Random spanning tree edges:
  2 - 1
  0 - 2
  4 - 3
  2 - 4

(1) Positional version

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);
Direction Parameter Description

IN

const Graph& g

A directed or undirected graph. The graph type must be a model of Incidence Graph and Vertex List Graph.

IN

Gen& gen

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.

IN

vertex_descriptor root

The root of the spanning tree to be generated.

OUT

PredMap pred

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

IN

WeightMap weight

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. The unweighted version can be selected by passing an object of type static_property_map<double> as the weight map. The type WeightMap must 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 as double).

UTIL

ColorMap color

This is used by the algorithm to keep track of its progress through the graph. The type ColorMap must 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.

(2) Named parameter version

template <class Graph, class Gen,
          class P, class T, class R>
void random_spanning_tree(Graph& G, Gen& gen,
    const bgl_named_params<P, T, R>& params);
Direction Parameter Description

IN

Graph& G

A directed or undirected graph. The graph type must be a model of Incidence Graph and Vertex List Graph.

IN

Gen& gen

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.

IN

root_vertex(vertex_descriptor root)

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

UTIL

color_map(ColorMap color)

This is used by the algorithm to keep track of its progress through the graph. The type ColorMap must 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: a two_bit_color_map of size num_vertices(g) and using the i_map for the index map.

IN

vertex_index_map(VertexIndexMap i_map)

This maps each vertex to an integer in the range [0, num_vertices(g)). This parameter is only necessary when the default color property map is used. The type VertexIndexMap must 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.

OUT

predecessor_map(PredMap pred)

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

IN

weight_map(WeightMap weight)

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 WeightMap must 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 as double).

Description

The random_spanning_tree() function generates a random spanning tree on a directed or undirected graph. The algorithm used is Wilson’s algorithm (67), 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.

Notes

The loop_erased_random_walk_stuck exception is thrown when the random walk reaches a vertex with no outgoing edges and thus cannot continue. This typically indicates that the graph does not have a path from every vertex to the root.

Edit this Page