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
20 namespace boost
21 {
22
23 struct BOOST_SYMBOL_VISIBLE loop_erased_random_walk_stuck
24 : public std::exception
25 {
~loop_erased_random_walk_stuckboost::loop_erased_random_walk_stuck26 virtual ~loop_erased_random_walk_stuck() throw() {}
whatboost::loop_erased_random_walk_stuck27 inline virtual const char* what() const throw()
28 {
29 return "Loop-erased random walk found a vertex with no out-edges";
30 }
31 };
32
33 // Do a loop-erased random walk from vertex s to any vertex colored black (or
34 // actually any color other than white or gray) in the color map. The color
35 // white is for vertices that are not part of the path, while gray is for
36 // those that are on the path (for cycle detection). The vector path is used
37 // for temporary storage and as the result of the algorithm; while all
38 // elements of the path except the last have their colors set to gray upon
39 // return. Vertex s must start off colored white.
40 //
41 // Useful references:
42 // http://everything2.com/title/loop-erased+random+walk
43 // Wikipedia page on "Loop-Erased Random Walk"
44
45 template < typename Graph, typename ColorMap, typename NextEdge >
loop_erased_random_walk(const Graph & g,typename boost::graph_traits<Graph>::vertex_descriptor s,NextEdge next_edge,ColorMap color,std::vector<typename boost::graph_traits<Graph>::vertex_descriptor> & path)46 void loop_erased_random_walk(const Graph& g,
47 typename boost::graph_traits< Graph >::vertex_descriptor s,
48 NextEdge next_edge, ColorMap color,
49 std::vector< typename boost::graph_traits< Graph >::vertex_descriptor >&
50 path)
51 {
52 typedef typename boost::graph_traits< Graph >::vertex_descriptor
53 vertex_descriptor;
54 typedef
55 typename boost::graph_traits< Graph >::edge_descriptor edge_descriptor;
56 typedef typename boost::property_traits< ColorMap >::value_type color_t;
57 typedef boost::color_traits< color_t > color_gen;
58
59 BOOST_ASSERT(get(color, s) == color_gen::white());
60 path.clear();
61 path.push_back(s);
62 put(color, s, color_gen::gray());
63 while (true)
64 {
65 edge_descriptor e = next_edge(s, g);
66 vertex_descriptor t = target(e, g);
67 color_t t_color = get(color, t);
68 if (t_color == color_gen::white())
69 {
70 path.push_back(t);
71 put(color, t, color_gen::gray());
72 s = t;
73 }
74 else if (t_color == color_gen::gray())
75 {
76 // Found a loop; delete from path from the first occurrence of t to
77 // the end, coloring vertices white.
78 typename std::vector< vertex_descriptor >::iterator it
79 = std::find(path.begin(), path.end(), t);
80 BOOST_ASSERT(it != path.end());
81 ++it;
82 for (typename std::vector< vertex_descriptor >::iterator j = it;
83 j != path.end(); ++j)
84 {
85 put(color, *j, color_gen::white());
86 }
87 path.erase(it, path.end());
88 s = t;
89 }
90 else
91 {
92 // Done
93 path.push_back(t);
94 break;
95 }
96 }
97 }
98
99 template < typename Graph, typename Gen > class unweighted_random_out_edge_gen
100 {
101 Gen& gen;
102
103 typedef boost::graph_traits< Graph > gt;
104
105 public:
unweighted_random_out_edge_gen(Gen & gen)106 unweighted_random_out_edge_gen(Gen& gen) : gen(gen) {}
107
operator ()(typename gt::vertex_descriptor src,const Graph & g) const108 typename gt::edge_descriptor operator()(
109 typename gt::vertex_descriptor src, const Graph& g) const
110 {
111 if (out_degree(src, g) == 0)
112 throw loop_erased_random_walk_stuck();
113 return boost::random_out_edge(g, src, gen);
114 }
115 };
116
117 template < typename Graph, typename WeightMap, typename Gen >
118 class weighted_random_out_edge_gen
119 {
120 WeightMap weight;
121 Gen& gen;
122
123 typedef boost::graph_traits< Graph > gt;
124
125 public:
weighted_random_out_edge_gen(const WeightMap & weight,Gen & gen)126 weighted_random_out_edge_gen(const WeightMap& weight, Gen& gen)
127 : weight(weight), gen(gen)
128 {
129 }
130
operator ()(typename gt::vertex_descriptor src,const Graph & g) const131 typename gt::edge_descriptor operator()(
132 typename gt::vertex_descriptor src, const Graph& g) const
133 {
134 if (out_degree(src, g) == 0)
135 throw loop_erased_random_walk_stuck();
136 return boost::weighted_random_out_edge(g, src, weight, gen);
137 }
138 };
139 }
140
141 #endif // BOOST_GRAPH_LOOP_ERASED_RANDOM_WALK_HPP
142