1 // Copyright 2004 The Trustees of Indiana University.
2
3 // Use, modification and distribution is subject to the Boost Software
4 // License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
5 // http://www.boost.org/LICENSE_1_0.txt)
6
7 // Authors: Douglas Gregor
8 // Andrew Lumsdaine
9
10 #include <boost/graph/use_mpi.hpp>
11 #include <boost/config.hpp>
12 #include <boost/throw_exception.hpp>
13 #include <boost/serialization/vector.hpp>
14 #include <boost/graph/distributed/dehne_gotz_min_spanning_tree.hpp>
15 #include <boost/graph/distributed/mpi_process_group.hpp>
16 #include <boost/graph/distributed/vertex_list_adaptor.hpp>
17 #include <boost/graph/parallel/distribution.hpp>
18 #include <boost/test/minimal.hpp>
19 #include <boost/graph/distributed/adjacency_list.hpp>
20 #include <iostream>
21 #include <cstdlib>
22
23 #ifdef BOOST_NO_EXCEPTIONS
24 void
throw_exception(std::exception const & ex)25 boost::throw_exception(std::exception const& ex)
26 {
27 std::cout << ex.what() << std::endl;
28 abort();
29 }
30 #endif
31
32 using namespace boost;
33 using boost::graph::distributed::mpi_process_group;
34
35 template<typename Graph, typename WeightMap, typename InputIterator>
36 int
total_weight(const Graph & g,WeightMap weight_map,InputIterator first,InputIterator last)37 total_weight(const Graph& g, WeightMap weight_map,
38 InputIterator first, InputIterator last)
39 {
40 typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor;
41
42 int total_weight = 0;
43 while (first != last) {
44 total_weight += get(weight_map, *first);
45 if (process_id(g.process_group()) == 0) {
46 vertex_descriptor u = source(*first, g);
47 vertex_descriptor v = target(*first, g);
48 std::cout << "(" << g.distribution().global(owner(u), local(u))
49 << ", " << g.distribution().global(owner(v), local(v))
50 << ")\n";
51 }
52 ++first;
53 }
54
55 return total_weight;
56 }
57
58 void
test_distributed_dense_boruvka()59 test_distributed_dense_boruvka()
60 {
61 typedef adjacency_list<listS,
62 distributedS<mpi_process_group, vecS>,
63 undirectedS,
64 // Vertex properties
65 no_property,
66 // Edge properties
67 property<edge_weight_t, int> > Graph;
68
69 typedef graph_traits<Graph>::edge_descriptor edge_descriptor;
70
71 typedef std::pair<int, int> E;
72
73 const int num_nodes = 5;
74 E edge_array[] = { E(0, 2), E(1, 3), E(1, 4), E(2, 1), E(2, 3),
75 E(3, 4), E(4, 0), E(4, 1)
76 };
77 int weights[] = { 1, 1, 2, 7, 3, 1, 1, 1 };
78 std::size_t num_edges = sizeof(edge_array) / sizeof(E);
79
80 Graph g(edge_array, edge_array + num_edges, weights, num_nodes);
81
82 {
83 if (process_id(g.process_group()) == 0)
84 std::cerr << "--Dense Boruvka--\n";
85 typedef property_map<Graph, edge_weight_t>::type WeightMap;
86 WeightMap weight_map = get(edge_weight, g);
87
88 std::vector<edge_descriptor> mst_edges;
89 dense_boruvka_minimum_spanning_tree(make_vertex_list_adaptor(g),
90 weight_map,
91 std::back_inserter(mst_edges));
92 int w = total_weight(g, weight_map, mst_edges.begin(), mst_edges.end());
93 BOOST_CHECK(w == 4);
94 BOOST_CHECK(mst_edges.size() == 4);
95 }
96
97 {
98 if (process_id(g.process_group()) == 0)
99 std::cerr << "--Merge local MSTs--\n";
100 typedef property_map<Graph, edge_weight_t>::type WeightMap;
101 WeightMap weight_map = get(edge_weight, g);
102
103 std::vector<edge_descriptor> mst_edges;
104 merge_local_minimum_spanning_trees(make_vertex_list_adaptor(g), weight_map,
105 std::back_inserter(mst_edges));
106 if (process_id(g.process_group()) == 0) {
107 int w = total_weight(g, weight_map, mst_edges.begin(), mst_edges.end());
108 BOOST_CHECK(w == 4);
109 BOOST_CHECK(mst_edges.size() == 4);
110 }
111 }
112
113 {
114 if (process_id(g.process_group()) == 0)
115 std::cerr << "--Boruvka then Merge--\n";
116 typedef property_map<Graph, edge_weight_t>::type WeightMap;
117 WeightMap weight_map = get(edge_weight, g);
118
119 std::vector<edge_descriptor> mst_edges;
120 boruvka_then_merge(make_vertex_list_adaptor(g), weight_map,
121 std::back_inserter(mst_edges));
122 if (process_id(g.process_group()) == 0) {
123 int w = total_weight(g, weight_map, mst_edges.begin(), mst_edges.end());
124 BOOST_CHECK(w == 4);
125 BOOST_CHECK(mst_edges.size() == 4);
126 }
127 }
128
129 {
130 if (process_id(g.process_group()) == 0)
131 std::cerr << "--Boruvka mixed Merge--\n";
132 typedef property_map<Graph, edge_weight_t>::type WeightMap;
133 WeightMap weight_map = get(edge_weight, g);
134
135 std::vector<edge_descriptor> mst_edges;
136 boruvka_mixed_merge(make_vertex_list_adaptor(g), weight_map,
137 std::back_inserter(mst_edges));
138 if (process_id(g.process_group()) == 0) {
139 int w = total_weight(g, weight_map, mst_edges.begin(), mst_edges.end());
140 BOOST_CHECK(w == 4);
141 BOOST_CHECK(mst_edges.size() == 4);
142 }
143 }
144 }
145
test_main(int argc,char ** argv)146 int test_main(int argc, char** argv)
147 {
148 boost::mpi::environment env(argc, argv);
149 test_distributed_dense_boruvka();
150 return 0;
151 }
152