File: loop_erased_random_walk.hpp

package info (click to toggle)
boost1.62 1.62.0+dfsg-4
  • links: PTS, VCS
  • area: main
  • in suites: stretch
  • size: 686,420 kB
  • sloc: cpp: 2,609,004; xml: 972,558; ansic: 53,674; python: 32,437; sh: 8,829; asm: 3,071; cs: 2,121; makefile: 964; perl: 859; yacc: 472; php: 132; ruby: 94; f90: 55; sql: 13; csh: 6
file content (119 lines) | stat: -rw-r--r-- 4,218 bytes parent folder | download | duplicates (11)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
// 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 <boost/assert.hpp>

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;
    
    BOOST_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);
        BOOST_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