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 #include <boost/graph/random_spanning_tree.hpp>
11 #include <boost/graph/grid_graph.hpp>
12 #include <boost/array.hpp>
13 #include <boost/random.hpp>
14 #include <boost/property_map/shared_array_property_map.hpp>
15 #include <boost/property_map/dynamic_property_map.hpp>
16 #include <boost/graph/graphviz.hpp>
17 #include <boost/lexical_cast.hpp>
18 #include <boost/graph/property_maps/constant_property_map.hpp>
19 #include <string>
20 #include <iostream>
21 #include <fstream>
22 #include <boost/graph/iteration_macros.hpp>
23
24 using namespace boost;
25 using namespace std;
26
27 typedef grid_graph< 2 > graph_type;
28 typedef graph_traits< graph_type > gt;
29
30 template < typename Graph, typename PredMap, typename WeightMap >
write_spanning_tree(const Graph & g,PredMap pred,WeightMap weight,string filename)31 void write_spanning_tree(
32 const Graph& g, PredMap pred, WeightMap weight, string filename)
33 {
34 shared_array_property_map< string,
35 typename property_map< Graph, edge_index_t >::const_type >
36 edge_style(num_edges(g), get(edge_index, g));
37 shared_array_property_map< string,
38 typename property_map< Graph, vertex_index_t >::const_type >
39 vertex_pos(num_vertices(g), get(vertex_index, g));
40 BGL_FORALL_EDGES_T(e, g, Graph)
41 {
42 put(edge_style, e,
43 (get(pred, target(e, g)) == source(e, g)
44 || get(pred, source(e, g)) == target(e, g))
45 ? "bold"
46 : "dotted");
47 }
48 BGL_FORALL_VERTICES_T(v, g, Graph)
49 {
50 put(vertex_pos, v,
51 lexical_cast< string >(v[0]) + "," + lexical_cast< string >(v[1]));
52 }
53 dynamic_properties dp;
54 dp.property("style", edge_style);
55 dp.property("pos", vertex_pos);
56 dp.property("len", weight);
57 dp.property("node_id", get(vertex_index, g));
58 ofstream out(filename.c_str());
59 write_graphviz_dp(out, g, dp);
60 }
61
main(int,char **)62 int main(int, char**)
63 {
64
65 boost::array< size_t, 2 > sizes = { { 5, 5 } };
66 graph_type g(sizes);
67
68 shared_array_property_map< gt::vertex_descriptor,
69 property_map< graph_type, vertex_index_t >::const_type >
70 pred(num_vertices(g), get(vertex_index, g));
71 shared_array_property_map< double,
72 property_map< graph_type, edge_index_t >::const_type >
73 weight(num_edges(g), get(edge_index, g));
74
75 BGL_FORALL_EDGES(e, g, graph_type)
76 {
77 put(weight, e, (1. + get(edge_index, g, e)) / num_edges(g));
78 }
79
80 boost::mt19937 gen;
81 random_spanning_tree(g, gen, predecessor_map(pred));
82 // write_spanning_tree(g, pred, constant_property_map<gt::edge_descriptor,
83 // double>(1.), "unweight_random_st.dot");
84 random_spanning_tree(g, gen, predecessor_map(pred));
85 // write_spanning_tree(g, pred, constant_property_map<gt::edge_descriptor,
86 // double>(1.), "unweight_random_st2.dot");
87
88 random_spanning_tree(g, gen, predecessor_map(pred).weight_map(weight));
89 // write_spanning_tree(g, pred, weight, "weight_random_st.dot");
90
91 return 0;
92 }
93