Loop-Erased Random Walk

Performs a random walk from vertex s until it reaches a vertex that is already colored (not white) in the color map. Whenever the walk revisits a vertex already on the current path (creating a cycle), the cycle is erased and the walk continues from where the cycle started.

This is the building block for Wilson’s algorithm for generating uniformly random spanning trees. It is used internally by random_spanning_tree.

Example

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

int main() {
    using namespace boost;
    using Graph = adjacency_list<vecS, vecS, directedS>;
    using Vertex = graph_traits<Graph>::vertex_descriptor;

    Graph g(5);
    add_edge(0, 1, g);
    add_edge(1, 2, g);
    add_edge(2, 3, g);
    add_edge(3, 4, g);
    add_edge(1, 3, g);  // shortcut

    std::mt19937 gen(42);
    auto next_edge = [&](Vertex v, const Graph& gr) {
        auto range = out_edges(v, gr);
        auto n = std::distance(range.first, range.second);
        std::advance(range.first, gen() % n);
        return *range.first;
    };

    std::vector<default_color_type> colors(num_vertices(g), white_color);
    colors[4] = black_color;  // target

    std::vector<Vertex> path;
    loop_erased_random_walk(g, vertex(0, g), next_edge,
        make_iterator_property_map(colors.begin(), get(vertex_index, g)),
        path);

    std::cout << "Path from 0 to 4: ";
    for (auto v : path) { std::cout << v << " "; }
    std::cout << "\n";
}

Path from 0 to 4: 0 1 3 4

Complexity: depends on graph structure, expected O(V) per walk on many graphs
Defined in: <boost/graph/loop_erased_random_walk.hpp>

Synopsis

template <typename Graph, typename ColorMap, typename NextEdge>
void loop_erased_random_walk(
    const Graph& g,
    typename graph_traits<Graph>::vertex_descriptor s,
    NextEdge next_edge,
    ColorMap color,
    std::vector<typename graph_traits<Graph>::vertex_descriptor>& path);

Direction Parameter Description

Direction	Parameter	Description
IN	`const Graph& g`	Must model IncidenceGraph.
IN	`vertex_descriptor s`	Starting vertex. Must be colored white.
IN	`NextEdge next_edge`	Callable `(vertex_descriptor, Graph) → edge_descriptor` that selects the next edge to follow. Typically uses a random generator.
IN/OUT	`ColorMap color`	White = unvisited, gray = on current path, black (or other) = target. The walk stops when it reaches a non-white, non-gray vertex.
OUT	`path`	Receives the loop-erased path from `s` to the target vertex.

const Graph& g

Must model IncidenceGraph.

vertex_descriptor s

Starting vertex. Must be colored white.

NextEdge next_edge

Callable (vertex_descriptor, Graph) → edge_descriptor that selects the next edge to follow. Typically uses a random generator.

IN/OUT

ColorMap color

White = unvisited, gray = on current path, black (or other) = target. The walk stops when it reaches a non-white, non-gray vertex.

OUT

path

Receives the loop-erased path from s to the target vertex.

Throws

loop_erased_random_walk_stuck if the walk reaches a vertex with no out-edges.

NextEdge helpers

The header also provides two ready-made NextEdge functors that satisfy the callable signature expected by loop_erased_random_walk:

template <typename Graph, typename Gen>
class unweighted_random_out_edge_gen {
public:
    explicit unweighted_random_out_edge_gen(Gen& gen);

    typename graph_traits<Graph>::edge_descriptor
    operator()(typename graph_traits<Graph>::vertex_descriptor src,
               const Graph& g) const;
};

template <typename Graph, typename WeightMap, typename Gen>
class weighted_random_out_edge_gen {
public:
    weighted_random_out_edge_gen(const WeightMap& weight, Gen& gen);

    typename graph_traits<Graph>::edge_descriptor
    operator()(typename graph_traits<Graph>::vertex_descriptor src,
               const Graph& g) const;
};

unweighted_random_out_edge_gen picks an out-edge uniformly at random via boost::random_out_edge(g, src, gen).

weighted_random_out_edge_gen picks an out-edge with probability proportional to its weight via boost::weighted_random_out_edge(g, src, weight, gen).

Both throw loop_erased_random_walk_stuck if out_degree(src, g) == 0.

loop_erased_random_walk_stuck (exception)

struct loop_erased_random_walk_stuck : public std::exception {
    virtual const char* what() const throw();
};

Thrown when the walk encounters a vertex with no outgoing edges, which makes the algorithm unable to continue.

Edit this Page