boost/graph/random_spanning_tree.hpp

0001 // Copyright 2010 The Trustees of Indiana University.
0002
0003 // Distributed under the Boost Software License, Version 1.0.
0004 // (See accompanying file LICENSE_1_0.txt or copy at
0005 // http://www.boost.org/LICENSE_1_0.txt)
0006
0007 //  Authors: Jeremiah Willcock
0008 //           Andrew Lumsdaine
0009
0010 #ifndef BOOST_GRAPH_RANDOM_SPANNING_TREE_HPP
0011 #define BOOST_GRAPH_RANDOM_SPANNING_TREE_HPP
0012
0013 #include <vector>
0014 #include <boost/assert.hpp>
0015 #include <boost/graph/loop_erased_random_walk.hpp>
0016 #include <boost/graph/random.hpp>
0017 #include <boost/graph/iteration_macros.hpp>
0018 #include <boost/property_map/property_map.hpp>
0019 #include <boost/config.hpp>
0020 #include <boost/graph/graph_traits.hpp>
0021 #include <boost/graph/graph_concepts.hpp>
0022 #include <boost/graph/properties.hpp>
0023 #include <boost/graph/named_function_params.hpp>
0024
0025 namespace boost
0026 {
0027
0028 namespace detail
0029 {
0030     // Use Wilson's algorithm (based on loop-free random walks) to generate a
0031     // random spanning tree.  The distribution of edges used is controlled by
0032     // the next_edge() function, so this version allows either weighted or
0033     // unweighted selection of trees.
0034     // Algorithm is from http://en.wikipedia.org/wiki/Uniform_spanning_tree
0035     template < typename Graph, typename PredMap, typename ColorMap,
0036         typename NextEdge >
0037     void random_spanning_tree_internal(const Graph& g,
0038         typename graph_traits< Graph >::vertex_descriptor s, PredMap pred,
0039         ColorMap color, NextEdge next_edge)
0040     {
0041         typedef
0042             typename graph_traits< Graph >::vertex_descriptor vertex_descriptor;
0043
0044         BOOST_ASSERT(num_vertices(g)
0045             >= 1); // g must also be undirected (or symmetric) and connected
0046
0047         typedef color_traits< typename property_traits< ColorMap >::value_type >
0048             color_gen;
0049         BGL_FORALL_VERTICES_T(v, g, Graph) put(color, v, color_gen::white());
0050
0051         std::vector< vertex_descriptor > path;
0052
0053         put(color, s, color_gen::black());
0054         put(pred, s, graph_traits< Graph >::null_vertex());
0055
0056         BGL_FORALL_VERTICES_T(v, g, Graph)
0057         {
0058             if (get(color, v) != color_gen::white())
0059                 continue;
0060             loop_erased_random_walk(g, v, next_edge, color, path);
0061             for (typename std::vector<
0062                      vertex_descriptor >::const_reverse_iterator i
0063                  = path.rbegin();
0064                  boost::next(i)
0065                  != (typename std::vector<
0066                      vertex_descriptor >::const_reverse_iterator)path.rend();
0067                  ++i)
0068             {
0069                 typename std::vector<
0070                     vertex_descriptor >::const_reverse_iterator j
0071                     = i;
0072                 ++j;
0073                 BOOST_ASSERT(get(color, *j) == color_gen::gray());
0074                 put(color, *j, color_gen::black());
0075                 put(pred, *j, *i);
0076             }
0077         }
0078     }
0079 }
0080
0081 // Compute a uniformly-distributed spanning tree on a graph.  Use Wilson's
0082 // algorithm:
0083 // @inproceedings{wilson96generating,
0084 //    author = {Wilson, David Bruce},
0085 //    title = {Generating random spanning trees more quickly than the cover
0086 //    time}, booktitle = {STOC '96: Proceedings of the twenty-eighth annual ACM
0087 //    symposium on Theory of computing}, year = {1996}, isbn = {0-89791-785-5},
0088 //    pages = {296--303},
0089 //    location = {Philadelphia, Pennsylvania, United States},
0090 //    doi = {http://doi.acm.org/10.1145/237814.237880},
0091 //    publisher = {ACM},
0092 //    address = {New York, NY, USA},
0093 //  }
0094 //
0095 template < typename Graph, typename Gen, typename PredMap, typename ColorMap >
0096 void random_spanning_tree(const Graph& g, Gen& gen,
0097     typename graph_traits< Graph >::vertex_descriptor root, PredMap pred,
0098     static_property_map< double >, ColorMap color)
0099 {
0100     unweighted_random_out_edge_gen< Graph, Gen > random_oe(gen);
0101     detail::random_spanning_tree_internal(g, root, pred, color, random_oe);
0102 }
0103
0104 // Compute a weight-distributed spanning tree on a graph.
0105 template < typename Graph, typename Gen, typename PredMap, typename WeightMap,
0106     typename ColorMap >
0107 void random_spanning_tree(const Graph& g, Gen& gen,
0108     typename graph_traits< Graph >::vertex_descriptor root, PredMap pred,
0109     WeightMap weight, ColorMap color)
0110 {
0111     weighted_random_out_edge_gen< Graph, WeightMap, Gen > random_oe(
0112         weight, gen);
0113     detail::random_spanning_tree_internal(g, root, pred, color, random_oe);
0114 }
0115
0116 template < typename Graph, typename Gen, typename P, typename T, typename R >
0117 void random_spanning_tree(
0118     const Graph& g, Gen& gen, const bgl_named_params< P, T, R >& params)
0119 {
0120     using namespace boost::graph::keywords;
0121     typedef bgl_named_params< P, T, R > params_type;
0122     BOOST_GRAPH_DECLARE_CONVERTED_PARAMETERS(params_type, params)
0123     typedef typename graph_traits< Graph >::vertex_descriptor vertex_descriptor;
0124     vertex_descriptor default_vertex = *vertices(g).first;
0125     vertex_descriptor start_vertex = arg_pack[_root_vertex | default_vertex];
0126     typename boost::parameter::binding< arg_pack_type,
0127         boost::graph::keywords::tag::predecessor_map >::type pred_map
0128         = arg_pack[_predecessor_map];
0129     static_property_map< double > default_weight_map(1.);
0130     typename boost::parameter::value_type< arg_pack_type,
0131         boost::graph::keywords::tag::weight_map,
0132         static_property_map< double > >::type e_w_map
0133         = arg_pack[_weight_map | default_weight_map];
0134     typename boost::detail::map_maker< Graph, arg_pack_type,
0135         boost::graph::keywords::tag::color_map,
0136         boost::default_color_type >::map_type c_map
0137         = boost::detail::make_color_map_from_arg_pack(g, arg_pack);
0138     random_spanning_tree(g, gen, start_vertex, pred_map, e_w_map, c_map);
0139 }
0140 }
0141
0142 #include <boost/graph/iteration_macros_undef.hpp>
0143
0144 #endif // BOOST_GRAPH_RANDOM_SPANNING_TREE_HPP