| // Copyright 2010 The Trustees of Indiana University. |
| |
| // Distributed under the Boost Software License, Version 1.0. |
| // (See accompanying file LICENSE_1_0.txt or copy at |
| // http://www.boost.org/LICENSE_1_0.txt) |
| |
| // Authors: Jeremiah Willcock |
| // Andrew Lumsdaine |
| |
| #ifndef BOOST_GRAPH_LOOP_ERASED_RANDOM_WALK_HPP |
| #define BOOST_GRAPH_LOOP_ERASED_RANDOM_WALK_HPP |
| |
| #include <boost/graph/graph_traits.hpp> |
| #include <boost/graph/properties.hpp> |
| #include <boost/graph/random.hpp> |
| #include <boost/next_prior.hpp> |
| #include <vector> |
| #include <cassert> |
| |
| namespace boost { |
| |
| struct loop_erased_random_walk_stuck : public std::exception { |
| virtual ~loop_erased_random_walk_stuck() throw() {} |
| inline virtual const char* what() const throw() { |
| return "Loop-erased random walk found a vertex with no out-edges"; |
| } |
| }; |
| |
| // Do a loop-erased random walk from vertex s to any vertex colored black (or |
| // actually any color other than white or gray) in the color map. The color |
| // white is for vertices that are not part of the path, while gray is for |
| // those that are on the path (for cycle detection). The vector path is used |
| // for temporary storage and as the result of the algorithm; while all |
| // elements of the path except the last have their colors set to gray upon |
| // return. Vertex s must start off colored white. |
| // |
| // Useful references: |
| // http://everything2.com/title/loop-erased+random+walk |
| // Wikipedia page on "Loop-Erased Random Walk" |
| |
| template <typename Graph, typename ColorMap, typename NextEdge> |
| void 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 |
| ) { |
| typedef typename boost::graph_traits<Graph>::vertex_descriptor vertex_descriptor; |
| typedef typename boost::graph_traits<Graph>::edge_descriptor edge_descriptor; |
| typedef typename boost::property_traits<ColorMap>::value_type color_t; |
| typedef boost::color_traits<color_t> color_gen; |
| |
| assert (get(color, s) == color_gen::white()); |
| path.clear(); |
| path.push_back(s); |
| put(color, s, color_gen::gray()); |
| while (true) { |
| edge_descriptor e = next_edge(s, g); |
| vertex_descriptor t = target(e, g); |
| color_t t_color = get(color, t); |
| if (t_color == color_gen::white()) { |
| path.push_back(t); |
| put(color, t, color_gen::gray()); |
| s = t; |
| } else if (t_color == color_gen::gray()) { |
| // Found a loop; delete from path from the first occurrence of t to the |
| // end, coloring vertices white. |
| typename std::vector<vertex_descriptor>::iterator it = std::find(path.begin(), path.end(), t); |
| assert (it != path.end()); |
| ++it; |
| for (typename std::vector<vertex_descriptor>::iterator j = it; j != path.end(); ++j) { |
| put(color, *j, color_gen::white()); |
| } |
| path.erase(it, path.end()); |
| s = t; |
| } else { |
| // Done |
| path.push_back(t); |
| break; |
| } |
| } |
| } |
| |
| template <typename Graph, typename Gen> |
| class unweighted_random_out_edge_gen { |
| Gen& gen; |
| |
| typedef boost::graph_traits<Graph> gt; |
| |
| public: |
| unweighted_random_out_edge_gen(Gen& gen): gen(gen) {} |
| |
| typename gt::edge_descriptor |
| operator()(typename gt::vertex_descriptor src, const Graph& g) const { |
| if (out_degree(src, g) == 0) throw loop_erased_random_walk_stuck(); |
| return boost::random_out_edge(g, src, gen); |
| } |
| }; |
| |
| template <typename Graph, typename WeightMap, typename Gen> |
| class weighted_random_out_edge_gen { |
| WeightMap weight; |
| Gen& gen; |
| |
| typedef boost::graph_traits<Graph> gt; |
| |
| public: |
| weighted_random_out_edge_gen(const WeightMap& weight, Gen& gen): weight(weight), gen(gen) {} |
| |
| typename gt::edge_descriptor |
| operator()(typename gt::vertex_descriptor src, const Graph& g) const { |
| if (out_degree(src, g) == 0) throw loop_erased_random_walk_stuck(); |
| return boost::weighted_random_out_edge(g, src, weight, gen); |
| } |
| }; |
| } |
| |
| #endif // BOOST_GRAPH_LOOP_ERASED_RANDOM_WALK_HPP |