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
24using namespace boost;
25using namespace std;
26
27typedef grid_graph< 2 > graph_type;
28typedef graph_traits< graph_type > gt;
29
30template < typename Graph, typename PredMap, typename WeightMap >
31void 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
62int 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

source code of boost/libs/graph/test/random_spanning_tree_test.cpp