// 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_RANDOM_SPANNING_TREE_HPP #define BOOST_GRAPH_RANDOM_SPANNING_TREE_HPP #include <vector> #include <boost/assert.hpp> #include <boost/graph/loop_erased_random_walk.hpp> #include <boost/graph/random.hpp> #include <boost/graph/iteration_macros.hpp> #include <boost/property_map/property_map.hpp> #include <boost/config.hpp> #include <boost/graph/graph_traits.hpp> #include <boost/graph/graph_concepts.hpp> #include <boost/graph/properties.hpp> #include <boost/graph/named_function_params.hpp> namespace boost { namespace detail { // Use Wilson's algorithm (based on loop-free random walks) to generate a // random spanning tree. The distribution of edges used is controlled by // the next_edge() function, so this version allows either weighted or // unweighted selection of trees. // Algorithm is from http://en.wikipedia.org/wiki/Uniform_spanning_tree template <typename Graph, typename PredMap, typename ColorMap, typename NextEdge> void random_spanning_tree_internal(const Graph& g, typename graph_traits<Graph>::vertex_descriptor s, PredMap pred, ColorMap color, NextEdge next_edge) { typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor; BOOST_ASSERT (num_vertices(g) >= 1); // g must also be undirected (or symmetric) and connected typedef color_traits<typename property_traits<ColorMap>::value_type> color_gen; BGL_FORALL_VERTICES_T(v, g, Graph) put(color, v, color_gen::white()); std::vector<vertex_descriptor> path; put(color, s, color_gen::black()); put(pred, s, graph_traits<Graph>::null_vertex()); BGL_FORALL_VERTICES_T(v, g, Graph) { if (get(color, v) != color_gen::white()) continue; loop_erased_random_walk(g, v, next_edge, color, path); for (typename std::vector<vertex_descriptor>::const_reverse_iterator i = path.rbegin(); boost::next(i) != (typename std::vector<vertex_descriptor>::const_reverse_iterator)path.rend(); ++i) { typename std::vector<vertex_descriptor>::const_reverse_iterator j = i; ++j; BOOST_ASSERT (get(color, *j) == color_gen::gray()); put(color, *j, color_gen::black()); put(pred, *j, *i); } } } } // Compute a uniformly-distributed spanning tree on a graph. Use Wilson's algorithm: // @inproceedings{wilson96generating, // author = {Wilson, David Bruce}, // title = {Generating random spanning trees more quickly than the cover time}, // booktitle = {STOC '96: Proceedings of the twenty-eighth annual ACM symposium on Theory of computing}, // year = {1996}, // isbn = {0-89791-785-5}, // pages = {296--303}, // location = {Philadelphia, Pennsylvania, United States}, // doi = {http://doi.acm.org/10.1145/237814.237880}, // publisher = {ACM}, // address = {New York, NY, USA}, // } // template <typename Graph, typename Gen, typename PredMap, typename ColorMap> void random_spanning_tree(const Graph& g, Gen& gen, typename graph_traits<Graph>::vertex_descriptor root, PredMap pred, static_property_map<double>, ColorMap color) { unweighted_random_out_edge_gen<Graph, Gen> random_oe(gen); detail::random_spanning_tree_internal(g, root, pred, color, random_oe); } // Compute a weight-distributed spanning tree on a graph. template <typename Graph, typename Gen, typename PredMap, typename WeightMap, typename ColorMap> void random_spanning_tree(const Graph& g, Gen& gen, typename graph_traits<Graph>::vertex_descriptor root, PredMap pred, WeightMap weight, ColorMap color) { weighted_random_out_edge_gen<Graph, WeightMap, Gen> random_oe(weight, gen); detail::random_spanning_tree_internal(g, root, pred, color, random_oe); } template <typename Graph, typename Gen, typename P, typename T, typename R> void random_spanning_tree(const Graph& g, Gen& gen, const bgl_named_params<P, T, R>& params) { using namespace boost::graph::keywords; typedef bgl_named_params<P, T, R> params_type; BOOST_GRAPH_DECLARE_CONVERTED_PARAMETERS(params_type, params) random_spanning_tree(g, gen, arg_pack[_root_vertex | *vertices(g).first], arg_pack[_predecessor_map], arg_pack[_weight_map | static_property_map<double>(1.)], boost::detail::make_color_map_from_arg_pack(g, arg_pack)); } } #include <boost/graph/iteration_macros_undef.hpp> #endif // BOOST_GRAPH_RANDOM_SPANNING_TREE_HPP