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