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 >
random_spanning_tree_internal(const Graph & g,typename graph_traits<Graph>::vertex_descriptor s,PredMap pred,ColorMap color,NextEdge next_edge)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 >
random_spanning_tree(const Graph & g,Gen & gen,typename graph_traits<Graph>::vertex_descriptor root,PredMap pred,static_property_map<double>,ColorMap color)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 >
random_spanning_tree(const Graph & g,Gen & gen,typename graph_traits<Graph>::vertex_descriptor root,PredMap pred,WeightMap weight,ColorMap color)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 >
random_spanning_tree(const Graph & g,Gen & gen,const bgl_named_params<P,T,R> & params)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
145