boost/graph/loop_erased_random_walk.hpp

0001 // Copyright 2010 The Trustees of Indiana University.
0002
0003 // Distributed under the Boost Software License, Version 1.0.
0004 // (See accompanying file LICENSE_1_0.txt or copy at
0005 // http://www.boost.org/LICENSE_1_0.txt)
0006
0007 //  Authors: Jeremiah Willcock
0008 //           Andrew Lumsdaine
0009
0010 #ifndef BOOST_GRAPH_LOOP_ERASED_RANDOM_WALK_HPP
0011 #define BOOST_GRAPH_LOOP_ERASED_RANDOM_WALK_HPP
0012
0013 #include <boost/graph/graph_traits.hpp>
0014 #include <boost/graph/properties.hpp>
0015 #include <boost/graph/random.hpp>
0016 #include <boost/next_prior.hpp>
0017 #include <vector>
0018 #include <boost/assert.hpp>
0019
0020 namespace boost
0021 {
0022
0023 struct BOOST_SYMBOL_VISIBLE loop_erased_random_walk_stuck
0024 : public std::exception
0025 {
0026     virtual ~loop_erased_random_walk_stuck() throw() {}
0027     inline virtual const char* what() const throw()
0028     {
0029         return "Loop-erased random walk found a vertex with no out-edges";
0030     }
0031 };
0032
0033 // Do a loop-erased random walk from vertex s to any vertex colored black (or
0034 // actually any color other than white or gray) in the color map.  The color
0035 // white is for vertices that are not part of the path, while gray is for
0036 // those that are on the path (for cycle detection).  The vector path is used
0037 // for temporary storage and as the result of the algorithm; while all
0038 // elements of the path except the last have their colors set to gray upon
0039 // return.  Vertex s must start off colored white.
0040 //
0041 // Useful references:
0042 // http://everything2.com/title/loop-erased+random+walk
0043 // Wikipedia page on "Loop-Erased Random Walk"
0044
0045 template < typename Graph, typename ColorMap, typename NextEdge >
0046 void loop_erased_random_walk(const Graph& g,
0047     typename boost::graph_traits< Graph >::vertex_descriptor s,
0048     NextEdge next_edge, ColorMap color,
0049     std::vector< typename boost::graph_traits< Graph >::vertex_descriptor >&
0050         path)
0051 {
0052     typedef typename boost::graph_traits< Graph >::vertex_descriptor
0053         vertex_descriptor;
0054     typedef
0055         typename boost::graph_traits< Graph >::edge_descriptor edge_descriptor;
0056     typedef typename boost::property_traits< ColorMap >::value_type color_t;
0057     typedef boost::color_traits< color_t > color_gen;
0058
0059     BOOST_ASSERT(get(color, s) == color_gen::white());
0060     path.clear();
0061     path.push_back(s);
0062     put(color, s, color_gen::gray());
0063     while (true)
0064     {
0065         edge_descriptor e = next_edge(s, g);
0066         vertex_descriptor t = target(e, g);
0067         color_t t_color = get(color, t);
0068         if (t_color == color_gen::white())
0069         {
0070             path.push_back(t);
0071             put(color, t, color_gen::gray());
0072             s = t;
0073         }
0074         else if (t_color == color_gen::gray())
0075         {
0076             // Found a loop; delete from path from the first occurrence of t to
0077             // the end, coloring vertices white.
0078             typename std::vector< vertex_descriptor >::iterator it
0079                 = std::find(path.begin(), path.end(), t);
0080             BOOST_ASSERT(it != path.end());
0081             ++it;
0082             for (typename std::vector< vertex_descriptor >::iterator j = it;
0083                  j != path.end(); ++j)
0084             {
0085                 put(color, *j, color_gen::white());
0086             }
0087             path.erase(it, path.end());
0088             s = t;
0089         }
0090         else
0091         {
0092             // Done
0093             path.push_back(t);
0094             break;
0095         }
0096     }
0097 }
0098
0099 template < typename Graph, typename Gen > class unweighted_random_out_edge_gen
0100 {
0101     Gen& gen;
0102
0103     typedef boost::graph_traits< Graph > gt;
0104
0105 public:
0106     unweighted_random_out_edge_gen(Gen& gen) : gen(gen) {}
0107
0108     typename gt::edge_descriptor operator()(
0109         typename gt::vertex_descriptor src, const Graph& g) const
0110     {
0111         if (out_degree(src, g) == 0)
0112             throw loop_erased_random_walk_stuck();
0113         return boost::random_out_edge(g, src, gen);
0114     }
0115 };
0116
0117 template < typename Graph, typename WeightMap, typename Gen >
0118 class weighted_random_out_edge_gen
0119 {
0120     WeightMap weight;
0121     Gen& gen;
0122
0123     typedef boost::graph_traits< Graph > gt;
0124
0125 public:
0126     weighted_random_out_edge_gen(const WeightMap& weight, Gen& gen)
0127     : weight(weight), gen(gen)
0128     {
0129     }
0130
0131     typename gt::edge_descriptor operator()(
0132         typename gt::vertex_descriptor src, const Graph& g) const
0133     {
0134         if (out_degree(src, g) == 0)
0135             throw loop_erased_random_walk_stuck();
0136         return boost::weighted_random_out_edge(g, src, weight, gen);
0137     }
0138 };
0139 }
0140
0141 #endif // BOOST_GRAPH_LOOP_ERASED_RANDOM_WALK_HPP