ceph/src/boost/boost/graph/random_spanning_tree.hpp

   1 // Copyright 2010 The Trustees of Indiana University.
   2
   3 // Distributed under the Boost Software License, Version 1.0.
   4 // (See accompanying file LICENSE_1_0.txt or copy at
   5 // http://www.boost.org/LICENSE_1_0.txt)
   6
   7 //  Authors: Jeremiah Willcock
   8 //           Andrew Lumsdaine
   9
  10 #ifndef BOOST_GRAPH_RANDOM_SPANNING_TREE_HPP
  11 #define BOOST_GRAPH_RANDOM_SPANNING_TREE_HPP
  12
  13 #include <vector>
  14 #include <boost/assert.hpp>
  15 #include <boost/graph/loop_erased_random_walk.hpp>
  16 #include <boost/graph/random.hpp>
  17 #include <boost/graph/iteration_macros.hpp>
  18 #include <boost/property_map/property_map.hpp>
  19 #include <boost/config.hpp>
  20 #include <boost/graph/graph_traits.hpp>
  21 #include <boost/graph/graph_concepts.hpp>
  22 #include <boost/graph/properties.hpp>
  23 #include <boost/graph/named_function_params.hpp>
  24
  25 namespace boost
  26 {
  27
  28 namespace detail
  29 {
  30     // Use Wilson's algorithm (based on loop-free random walks) to generate a
  31     // random spanning tree.  The distribution of edges used is controlled by
  32     // the next_edge() function, so this version allows either weighted or
  33     // unweighted selection of trees.
  34     // Algorithm is from http://en.wikipedia.org/wiki/Uniform_spanning_tree
  35     template < typename Graph, typename PredMap, typename ColorMap,
  36         typename NextEdge >
  37     void random_spanning_tree_internal(const Graph& g,
  38         typename graph_traits< Graph >::vertex_descriptor s, PredMap pred,
  39         ColorMap color, NextEdge next_edge)
  40     {
  41         typedef
  42             typename graph_traits< Graph >::vertex_descriptor vertex_descriptor;
  43
  44         BOOST_ASSERT(num_vertices(g)
  45             >= 1); // g must also be undirected (or symmetric) and connected
  46
  47         typedef color_traits< typename property_traits< ColorMap >::value_type >
  48             color_gen;
  49         BGL_FORALL_VERTICES_T(v, g, Graph) put(color, v, color_gen::white());
  50
  51         std::vector< vertex_descriptor > path;
  52
  53         put(color, s, color_gen::black());
  54         put(pred, s, graph_traits< Graph >::null_vertex());
  55
  56         BGL_FORALL_VERTICES_T(v, g, Graph)
  57         {
  58             if (get(color, v) != color_gen::white())
  59                 continue;
  60             loop_erased_random_walk(g, v, next_edge, color, path);
  61             for (typename std::vector<
  62                      vertex_descriptor >::const_reverse_iterator i
  63                  = path.rbegin();
  64                  boost::next(i)
  65                  != (typename std::vector<
  66                      vertex_descriptor >::const_reverse_iterator)path.rend();
  67                  ++i)
  68             {
  69                 typename std::vector<
  70                     vertex_descriptor >::const_reverse_iterator j
  71                     = i;
  72                 ++j;
  73                 BOOST_ASSERT(get(color, *j) == color_gen::gray());
  74                 put(color, *j, color_gen::black());
  75                 put(pred, *j, *i);
  76             }
  77         }
  78     }
  79 }
  80
  81 // Compute a uniformly-distributed spanning tree on a graph.  Use Wilson's
  82 // algorithm:
  83 // @inproceedings{wilson96generating,
  84 //    author = {Wilson, David Bruce},
  85 //    title = {Generating random spanning trees more quickly than the cover
  86 //    time}, booktitle = {STOC '96: Proceedings of the twenty-eighth annual ACM
  87 //    symposium on Theory of computing}, year = {1996}, isbn = {0-89791-785-5},
  88 //    pages = {296--303},
  89 //    location = {Philadelphia, Pennsylvania, United States},
  90 //    doi = {http://doi.acm.org/10.1145/237814.237880},
  91 //    publisher = {ACM},
  92 //    address = {New York, NY, USA},
  93 //  }
  94 //
  95 template < typename Graph, typename Gen, typename PredMap, typename ColorMap >
  96 void random_spanning_tree(const Graph& g, Gen& gen,
  97     typename graph_traits< Graph >::vertex_descriptor root, PredMap pred,
  98     static_property_map< double >, ColorMap color)
  99 {
 100     unweighted_random_out_edge_gen< Graph, Gen > random_oe(gen);
 101     detail::random_spanning_tree_internal(g, root, pred, color, random_oe);
 102 }
 103
 104 // Compute a weight-distributed spanning tree on a graph.
 105 template < typename Graph, typename Gen, typename PredMap, typename WeightMap,
 106     typename ColorMap >
 107 void random_spanning_tree(const Graph& g, Gen& gen,
 108     typename graph_traits< Graph >::vertex_descriptor root, PredMap pred,
 109     WeightMap weight, ColorMap color)
 110 {
 111     weighted_random_out_edge_gen< Graph, WeightMap, Gen > random_oe(
 112         weight, gen);
 113     detail::random_spanning_tree_internal(g, root, pred, color, random_oe);
 114 }
 115
 116 template < typename Graph, typename Gen, typename P, typename T, typename R >
 117 void random_spanning_tree(
 118     const Graph& g, Gen& gen, const bgl_named_params< P, T, R >& params)
 119 {
 120     using namespace boost::graph::keywords;
 121     typedef bgl_named_params< P, T, R > params_type;
 122     BOOST_GRAPH_DECLARE_CONVERTED_PARAMETERS(params_type, params)
 123     typedef typename graph_traits< Graph >::vertex_descriptor vertex_descriptor;
 124     vertex_descriptor default_vertex = *vertices(g).first;
 125     vertex_descriptor start_vertex = arg_pack[_root_vertex | default_vertex];
 126     typename boost::parameter::binding< arg_pack_type,
 127         boost::graph::keywords::tag::predecessor_map >::type pred_map
 128         = arg_pack[_predecessor_map];
 129     static_property_map< double > default_weight_map(1.);
 130     typename boost::parameter::value_type< arg_pack_type,
 131         boost::graph::keywords::tag::weight_map,
 132         static_property_map< double > >::type e_w_map
 133         = arg_pack[_weight_map | default_weight_map];
 134     typename boost::detail::map_maker< Graph, arg_pack_type,
 135         boost::graph::keywords::tag::color_map,
 136         boost::default_color_type >::map_type c_map
 137         = boost::detail::make_color_map_from_arg_pack(g, arg_pack);
 138     random_spanning_tree(g, gen, start_vertex, pred_map, e_w_map, c_map);
 139 }
 140 }
 141
 142 #include <boost/graph/iteration_macros_undef.hpp>
 143
 144 #endif // BOOST_GRAPH_RANDOM_SPANNING_TREE_HPP