ceph/src/boost/boost/graph/loop_erased_random_walk.hpp

   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
  23 struct BOOST_SYMBOL_VISIBLE loop_erased_random_walk_stuck
  24 : public std::exception
  25 {
  26     virtual ~loop_erased_random_walk_stuck() throw() {}
  27     inline virtual const char* what() const throw()
  28     {
  29         return "Loop-erased random walk found a vertex with no out-edges";
  30     }
  31 };
  32
  33 // Do a loop-erased random walk from vertex s to any vertex colored black (or
  34 // actually any color other than white or gray) in the color map.  The color
  35 // white is for vertices that are not part of the path, while gray is for
  36 // those that are on the path (for cycle detection).  The vector path is used
  37 // for temporary storage and as the result of the algorithm; while all
  38 // elements of the path except the last have their colors set to gray upon
  39 // return.  Vertex s must start off colored white.
  40 //
  41 // Useful references:
  42 // http://everything2.com/title/loop-erased+random+walk
  43 // Wikipedia page on "Loop-Erased Random Walk"
  44
  45 template < typename Graph, typename ColorMap, typename NextEdge >
  46 void loop_erased_random_walk(const Graph& g,
  47     typename boost::graph_traits< Graph >::vertex_descriptor s,
  48     NextEdge next_edge, ColorMap color,
  49     std::vector< typename boost::graph_traits< Graph >::vertex_descriptor >&
  50         path)
  51 {
  52     typedef typename boost::graph_traits< Graph >::vertex_descriptor
  53         vertex_descriptor;
  54     typedef
  55         typename boost::graph_traits< Graph >::edge_descriptor edge_descriptor;
  56     typedef typename boost::property_traits< ColorMap >::value_type color_t;
  57     typedef boost::color_traits< color_t > color_gen;
  58
  59     BOOST_ASSERT(get(color, s) == color_gen::white());
  60     path.clear();
  61     path.push_back(s);
  62     put(color, s, color_gen::gray());
  63     while (true)
  64     {
  65         edge_descriptor e = next_edge(s, g);
  66         vertex_descriptor t = target(e, g);
  67         color_t t_color = get(color, t);
  68         if (t_color == color_gen::white())
  69         {
  70             path.push_back(t);
  71             put(color, t, color_gen::gray());
  72             s = t;
  73         }
  74         else if (t_color == color_gen::gray())
  75         {
  76             // Found a loop; delete from path from the first occurrence of t to
  77             // the end, coloring vertices white.
  78             typename std::vector< vertex_descriptor >::iterator it
  79                 = std::find(path.begin(), path.end(), t);
  80             BOOST_ASSERT(it != path.end());
  81             ++it;
  82             for (typename std::vector< vertex_descriptor >::iterator j = it;
  83                  j != path.end(); ++j)
  84             {
  85                 put(color, *j, color_gen::white());
  86             }
  87             path.erase(it, path.end());
  88             s = t;
  89         }
  90         else
  91         {
  92             // Done
  93             path.push_back(t);
  94             break;
  95         }
  96     }
  97 }
  98
  99 template < typename Graph, typename Gen > class unweighted_random_out_edge_gen
 100 {
 101     Gen& gen;
 102
 103     typedef boost::graph_traits< Graph > gt;
 104
 105 public:
 106     unweighted_random_out_edge_gen(Gen& gen) : gen(gen) {}
 107
 108     typename gt::edge_descriptor operator()(
 109         typename gt::vertex_descriptor src, const Graph& g) const
 110     {
 111         if (out_degree(src, g) == 0)
 112             throw loop_erased_random_walk_stuck();
 113         return boost::random_out_edge(g, src, gen);
 114     }
 115 };
 116
 117 template < typename Graph, typename WeightMap, typename Gen >
 118 class weighted_random_out_edge_gen
 119 {
 120     WeightMap weight;
 121     Gen& gen;
 122
 123     typedef boost::graph_traits< Graph > gt;
 124
 125 public:
 126     weighted_random_out_edge_gen(const WeightMap& weight, Gen& gen)
 127     : weight(weight), gen(gen)
 128     {
 129     }
 130
 131     typename gt::edge_descriptor operator()(
 132         typename gt::vertex_descriptor src, const Graph& g) const
 133     {
 134         if (out_degree(src, g) == 0)
 135             throw loop_erased_random_walk_stuck();
 136         return boost::weighted_random_out_edge(g, src, weight, gen);
 137     }
 138 };
 139 }
 140
 141 #endif // BOOST_GRAPH_LOOP_ERASED_RANDOM_WALK_HPP