]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
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 | namespace detail { | |
28 | // Use Wilson's algorithm (based on loop-free random walks) to generate a | |
29 | // random spanning tree. The distribution of edges used is controlled by | |
30 | // the next_edge() function, so this version allows either weighted or | |
31 | // unweighted selection of trees. | |
32 | // Algorithm is from http://en.wikipedia.org/wiki/Uniform_spanning_tree | |
33 | template <typename Graph, typename PredMap, typename ColorMap, typename NextEdge> | |
34 | void random_spanning_tree_internal(const Graph& g, typename graph_traits<Graph>::vertex_descriptor s, PredMap pred, ColorMap color, NextEdge next_edge) { | |
35 | typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor; | |
36 | ||
37 | BOOST_ASSERT (num_vertices(g) >= 1); // g must also be undirected (or symmetric) and connected | |
38 | ||
39 | typedef color_traits<typename property_traits<ColorMap>::value_type> color_gen; | |
40 | BGL_FORALL_VERTICES_T(v, g, Graph) put(color, v, color_gen::white()); | |
41 | ||
42 | std::vector<vertex_descriptor> path; | |
43 | ||
44 | put(color, s, color_gen::black()); | |
45 | put(pred, s, graph_traits<Graph>::null_vertex()); | |
46 | ||
47 | BGL_FORALL_VERTICES_T(v, g, Graph) { | |
48 | if (get(color, v) != color_gen::white()) continue; | |
49 | loop_erased_random_walk(g, v, next_edge, color, path); | |
50 | for (typename std::vector<vertex_descriptor>::const_reverse_iterator i = path.rbegin(); | |
51 | boost::next(i) != | |
52 | (typename std::vector<vertex_descriptor>::const_reverse_iterator)path.rend(); | |
53 | ++i) { | |
54 | typename std::vector<vertex_descriptor>::const_reverse_iterator j = i; | |
55 | ++j; | |
56 | BOOST_ASSERT (get(color, *j) == color_gen::gray()); | |
57 | put(color, *j, color_gen::black()); | |
58 | put(pred, *j, *i); | |
59 | } | |
60 | } | |
61 | } | |
62 | } | |
63 | ||
64 | // Compute a uniformly-distributed spanning tree on a graph. Use Wilson's algorithm: | |
65 | // @inproceedings{wilson96generating, | |
66 | // author = {Wilson, David Bruce}, | |
67 | // title = {Generating random spanning trees more quickly than the cover time}, | |
68 | // booktitle = {STOC '96: Proceedings of the twenty-eighth annual ACM symposium on Theory of computing}, | |
69 | // year = {1996}, | |
70 | // isbn = {0-89791-785-5}, | |
71 | // pages = {296--303}, | |
72 | // location = {Philadelphia, Pennsylvania, United States}, | |
73 | // doi = {http://doi.acm.org/10.1145/237814.237880}, | |
74 | // publisher = {ACM}, | |
75 | // address = {New York, NY, USA}, | |
76 | // } | |
77 | // | |
78 | template <typename Graph, typename Gen, typename PredMap, typename ColorMap> | |
79 | void random_spanning_tree(const Graph& g, Gen& gen, typename graph_traits<Graph>::vertex_descriptor root, | |
80 | PredMap pred, static_property_map<double>, ColorMap color) { | |
81 | unweighted_random_out_edge_gen<Graph, Gen> random_oe(gen); | |
82 | detail::random_spanning_tree_internal(g, root, pred, color, random_oe); | |
83 | } | |
84 | ||
85 | // Compute a weight-distributed spanning tree on a graph. | |
86 | template <typename Graph, typename Gen, typename PredMap, typename WeightMap, typename ColorMap> | |
87 | void random_spanning_tree(const Graph& g, Gen& gen, typename graph_traits<Graph>::vertex_descriptor root, | |
88 | PredMap pred, WeightMap weight, ColorMap color) { | |
89 | weighted_random_out_edge_gen<Graph, WeightMap, Gen> random_oe(weight, gen); | |
90 | detail::random_spanning_tree_internal(g, root, pred, color, random_oe); | |
91 | } | |
92 | ||
93 | template <typename Graph, typename Gen, typename P, typename T, typename R> | |
94 | void random_spanning_tree(const Graph& g, Gen& gen, const bgl_named_params<P, T, R>& params) { | |
95 | using namespace boost::graph::keywords; | |
96 | typedef bgl_named_params<P, T, R> params_type; | |
97 | BOOST_GRAPH_DECLARE_CONVERTED_PARAMETERS(params_type, params) | |
98 | random_spanning_tree(g, | |
99 | gen, | |
100 | arg_pack[_root_vertex | *vertices(g).first], | |
101 | arg_pack[_predecessor_map], | |
102 | arg_pack[_weight_map | static_property_map<double>(1.)], | |
103 | boost::detail::make_color_map_from_arg_pack(g, arg_pack)); | |
104 | } | |
105 | } | |
106 | ||
107 | #include <boost/graph/iteration_macros_undef.hpp> | |
108 | ||
109 | #endif // BOOST_GRAPH_RANDOM_SPANNING_TREE_HPP |