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
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
|
// 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 BOOST_SYMBOL_VISIBLE 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
|
