]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
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 | ||
92f5a8d4 | 22 | struct BOOST_SYMBOL_VISIBLE loop_erased_random_walk_stuck : public std::exception { |
7c673cae FG |
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 |