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 > |
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 | |
62 | int main(int, char**) |
63 | { |
64 | |
65 | boost::array< size_t, 2 > sizes = { .elems: { 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(graph: g), get(vertex_index, graph: g)); |
71 | shared_array_property_map< double, |
72 | property_map< graph_type, edge_index_t >::const_type > |
73 | weight(num_edges(graph: g), get(edge_index, graph: g)); |
74 | |
75 | BGL_FORALL_EDGES(e, g, graph_type) |
76 | { |
77 | put(pa: weight, k: e, v: (1. + get(edge_index, graph: g, edge: e)) / num_edges(graph: g)); |
78 | } |
79 | |
80 | boost::mt19937 gen; |
81 | random_spanning_tree(g, gen, params: predecessor_map(p: 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, params: predecessor_map(p: 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, params: predecessor_map(p: pred).weight_map(p: weight)); |
89 | // write_spanning_tree(g, pred, weight, "weight_random_st.dot"); |
90 | |
91 | return 0; |
92 | } |
93 | |