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