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 | 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 | |