1// Copyright 2010 The Trustees of Indiana University.
2
3// Distributed under the Boost Software License, Version 1.0.
4// (See accompanying file LICENSE_1_0.txt or copy at
5// http://www.boost.org/LICENSE_1_0.txt)
6
7// Authors: Jeremiah Willcock
8// Andrew Lumsdaine
9
10#ifndef BOOST_GRAPH_LOOP_ERASED_RANDOM_WALK_HPP
11#define BOOST_GRAPH_LOOP_ERASED_RANDOM_WALK_HPP
12
13#include <boost/graph/graph_traits.hpp>
14#include <boost/graph/properties.hpp>
15#include <boost/graph/random.hpp>
16#include <boost/next_prior.hpp>
17#include <vector>
18#include <boost/assert.hpp>
19
20namespace boost {
21
22 struct loop_erased_random_walk_stuck : public std::exception {
23 virtual ~loop_erased_random_walk_stuck() throw() {}
24 inline virtual const char* what() const throw() {
25 return "Loop-erased random walk found a vertex with no out-edges";
26 }
27 };
28
29 // Do a loop-erased random walk from vertex s to any vertex colored black (or
30 // actually any color other than white or gray) in the color map. The color
31 // white is for vertices that are not part of the path, while gray is for
32 // those that are on the path (for cycle detection). The vector path is used
33 // for temporary storage and as the result of the algorithm; while all
34 // elements of the path except the last have their colors set to gray upon
35 // return. Vertex s must start off colored white.
36 //
37 // Useful references:
38 // http://everything2.com/title/loop-erased+random+walk
39 // Wikipedia page on "Loop-Erased Random Walk"
40
41 template <typename Graph, typename ColorMap, typename NextEdge>
42 void loop_erased_random_walk(
43 const Graph& g,
44 typename boost::graph_traits<Graph>::vertex_descriptor s,
45 NextEdge next_edge,
46 ColorMap color,
47 std::vector<typename boost::graph_traits<Graph>::vertex_descriptor>& path
48 ) {
49 typedef typename boost::graph_traits<Graph>::vertex_descriptor vertex_descriptor;
50 typedef typename boost::graph_traits<Graph>::edge_descriptor edge_descriptor;
51 typedef typename boost::property_traits<ColorMap>::value_type color_t;
52 typedef boost::color_traits<color_t> color_gen;
53
54 BOOST_ASSERT (get(color, s) == color_gen::white());
55 path.clear();
56 path.push_back(s);
57 put(color, s, color_gen::gray());
58 while (true) {
59 edge_descriptor e = next_edge(s, g);
60 vertex_descriptor t = target(e, g);
61 color_t t_color = get(color, t);
62 if (t_color == color_gen::white()) {
63 path.push_back(t);
64 put(color, t, color_gen::gray());
65 s = t;
66 } else if (t_color == color_gen::gray()) {
67 // Found a loop; delete from path from the first occurrence of t to the
68 // end, coloring vertices white.
69 typename std::vector<vertex_descriptor>::iterator it = std::find(path.begin(), path.end(), t);
70 BOOST_ASSERT (it != path.end());
71 ++it;
72 for (typename std::vector<vertex_descriptor>::iterator j = it; j != path.end(); ++j) {
73 put(color, *j, color_gen::white());
74 }
75 path.erase(it, path.end());
76 s = t;
77 } else {
78 // Done
79 path.push_back(t);
80 break;
81 }
82 }
83 }
84
85 template <typename Graph, typename Gen>
86 class unweighted_random_out_edge_gen {
87 Gen& gen;
88
89 typedef boost::graph_traits<Graph> gt;
90
91 public:
92 unweighted_random_out_edge_gen(Gen& gen): gen(gen) {}
93
94 typename gt::edge_descriptor
95 operator()(typename gt::vertex_descriptor src, const Graph& g) const {
96 if (out_degree(src, g) == 0) throw loop_erased_random_walk_stuck();
97 return boost::random_out_edge(g, src, gen);
98 }
99 };
100
101 template <typename Graph, typename WeightMap, typename Gen>
102 class weighted_random_out_edge_gen {
103 WeightMap weight;
104 Gen& gen;
105
106 typedef boost::graph_traits<Graph> gt;
107
108 public:
109 weighted_random_out_edge_gen(const WeightMap& weight, Gen& gen): weight(weight), gen(gen) {}
110
111 typename gt::edge_descriptor
112 operator()(typename gt::vertex_descriptor src, const Graph& g) const {
113 if (out_degree(src, g) == 0) throw loop_erased_random_walk_stuck();
114 return boost::weighted_random_out_edge(g, src, weight, gen);
115 }
116 };
117}
118
119#endif // BOOST_GRAPH_LOOP_ERASED_RANDOM_WALK_HPP
120

source code of boost/boost/graph/loop_erased_random_walk.hpp