boost/graph/loop_erased_random_walk.hpp
// 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