1 // Copyright (C) 2005, 2006 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/lexical_cast.hpp>
14 #include <boost/serialization/vector.hpp>
15 #include <boost/graph/distributed/adjacency_list.hpp>
16 #include <boost/graph/distributed/mpi_process_group.hpp>
17 #include <boost/random/linear_congruential.hpp>
18 #include <iostream>
19 #include <boost/property_map/property_map_iterator.hpp>
20 #include <boost/graph/distributed/dehne_gotz_min_spanning_tree.hpp>
21 #include <boost/graph/distributed/vertex_list_adaptor.hpp>
22 #include <boost/graph/erdos_renyi_generator.hpp>
23 #include <boost/graph/distributed/graphviz.hpp>
24 #include <sstream>
25 #include <string>
26 #include <boost/graph/iteration_macros.hpp>
27 #include <boost/test/minimal.hpp>
28
29 #ifdef BOOST_NO_EXCEPTIONS
30 void
throw_exception(std::exception const & ex)31 boost::throw_exception(std::exception const& ex)
32 {
33 std::cout << ex.what() << std::endl;
34 abort();
35 }
36 #endif
37
38 using namespace boost;
39 using boost::graph::distributed::mpi_process_group;
40
41 /****************************************************************************
42 * Edge weight generator iterator *
43 ****************************************************************************/
44 template<typename F>
45 class generator_iterator
46 {
47 public:
48 typedef std::input_iterator_tag iterator_category;
49 typedef typename F::result_type value_type;
50 typedef const value_type& reference;
51 typedef const value_type* pointer;
52 typedef void difference_type;
53
generator_iterator(const F & f=F ())54 explicit generator_iterator(const F& f = F()) : f(f) { value = this->f(); }
55
operator *() const56 reference operator*() const { return value; }
operator ->() const57 pointer operator->() const { return &value; }
58
operator ++()59 generator_iterator& operator++()
60 {
61 value = f();
62 return *this;
63 }
64
operator ++(int)65 generator_iterator operator++(int)
66 {
67 generator_iterator temp(*this);
68 ++(*this);
69 return temp;
70 }
71
operator ==(const generator_iterator & other) const72 bool operator==(const generator_iterator& other) const
73 { return f == other.f; }
74
operator !=(const generator_iterator & other) const75 bool operator!=(const generator_iterator& other) const
76 { return !(*this == other); }
77
78 private:
79 F f;
80 value_type value;
81 };
82
83 template<typename F>
make_generator_iterator(const F & f)84 inline generator_iterator<F> make_generator_iterator(const F& f)
85 { return generator_iterator<F>(f); }
86
87 typedef minstd_rand RandomGenerator;
88
89 template<typename Graph>
get_mst_weight(const Graph & g)90 double get_mst_weight (const Graph& g)
91 {
92 typedef typename graph_traits<Graph>::edge_descriptor edge_descriptor;
93 typename property_map<Graph, edge_weight_t>::const_type weight
94 = get(edge_weight, g);
95
96 // Boruvka then merge test
97 std::vector<edge_descriptor> results;
98 graph::boruvka_then_merge(make_vertex_list_adaptor(g), weight,
99 std::back_inserter(results));
100 if (process_id(g.process_group()) == 0)
101 return accumulate(make_property_map_iterator(weight, results.begin()),
102 make_property_map_iterator(weight, results.end()),
103 0.0);
104 else
105 return 0.0;
106 }
107
108 template<typename Graph>
test_redistribution(int n,double p,int iterations,bool debug_output)109 void test_redistribution(int n, double p, int iterations, bool debug_output)
110 {
111 RandomGenerator gen;
112 Graph g(erdos_renyi_iterator<RandomGenerator, Graph>(gen, n, p),
113 erdos_renyi_iterator<RandomGenerator, Graph>(),
114 make_generator_iterator(uniform_01<RandomGenerator>(gen)),
115 n);
116
117 int iter = 0;
118 mpi_process_group pg = g.process_group();
119
120 // Set the names of the vertices to be the global index in the
121 // initial distribution. Then when we are debugging we'll be able to
122 // see how vertices have moved.
123 {
124 typedef typename property_map<Graph, vertex_index_t>::type VertexIndexMap;
125 typedef typename property_map<Graph, vertex_global_t>::type VertexGlobalMap;
126 typename property_map<Graph, vertex_name_t>::type name_map
127 = get(vertex_name, g);
128
129 parallel::global_index_map<VertexIndexMap, VertexGlobalMap>
130 global_index(g.process_group(), num_vertices(g),
131 get(vertex_index, g), get(vertex_global, g));
132 BGL_FORALL_VERTICES_T(v, g, Graph)
133 put(name_map, v, get(global_index, v));
134 }
135
136 if (debug_output)
137 write_graphviz("redist-0.dot", g,
138 make_label_writer(get(vertex_name, g)),
139 make_label_writer(get(edge_weight, g)));
140
141 double mst_weight = get_mst_weight(g);
142 if (process_id(pg) == 0)
143 std::cout << "MST weight = " << mst_weight << std::endl;
144
145 RandomGenerator nonsync_gen(process_id(pg) + gen());
146 while (++iter <= iterations) {
147 typename property_map<Graph, vertex_rank_t>::type to_processor_map =
148 get(vertex_rank, g);
149
150 // Randomly assign a new distribution
151 typename graph_traits<Graph>::vertex_iterator vi, vi_end;
152 for (boost::tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi)
153 put(to_processor_map, *vi, gen() % num_processes(pg));
154
155 if (process_id(pg) == 0)
156 std::cout << "Redistributing...";
157 // Perform the actual redistribution
158 g.redistribute(to_processor_map);
159
160 if (process_id(pg) == 0)
161 std::cout << " done." << std::endl;
162
163 if (debug_output) {
164 std::ostringstream out;
165 out << "redist-" << iter << ".dot";
166 write_graphviz(out.str().c_str(), g,
167 make_label_writer(get(vertex_name, g)),
168 make_label_writer(get(edge_weight, g)));
169 }
170
171 // Check that the MST weight is unchanged
172 double new_mst_weight = get_mst_weight(g);
173 if (process_id(pg) == 0) {
174 std::cout << "MST weight = " << new_mst_weight << std::endl;
175 if (std::fabs(new_mst_weight - mst_weight) > 0.0001)
176 communicator(pg).abort(-1); }
177 }
178 }
179
test_main(int argc,char ** argv)180 int test_main(int argc, char** argv)
181 {
182 int n = 1000;
183 double p = 3e-3;
184 int iterations = 5;
185 bool debug_output = false;
186
187 boost::mpi::environment env(argc, argv);
188
189 if (argc > 1) n = lexical_cast<int>(argv[1]);
190 if (argc > 2) p = lexical_cast<double>(argv[2]);
191 if (argc > 3) iterations = lexical_cast<int>(argv[3]);
192 if (argc > 4) debug_output = true;
193
194 typedef adjacency_list<listS,
195 distributedS<mpi_process_group, vecS>,
196 undirectedS,
197 // Vertex properties
198 property<vertex_name_t, std::size_t,
199 property<vertex_rank_t, int> >,
200 // Edge properties
201 property<edge_weight_t, double> > UnstableUDGraph;
202 typedef adjacency_list<listS,
203 distributedS<mpi_process_group, listS>,
204 undirectedS,
205 // Vertex properties
206 property<vertex_name_t, std::size_t,
207 property<vertex_rank_t, int,
208 property<vertex_index_t, std::size_t> > >,
209 // Edge properties
210 property<edge_weight_t, double> > StableUDGraph;
211
212 test_redistribution<UnstableUDGraph>(n, p, iterations, debug_output);
213 test_redistribution<StableUDGraph>(n, p, iterations, debug_output);
214
215 return 0;
216 }
217