1 // Copyright (C) 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: Nick Edmonds
8 // Andrew Lumsdaine
9
10 // A test of the distributed compressed sparse row graph type
11 #include <boost/graph/use_mpi.hpp>
12 #include <boost/config.hpp>
13 #include <boost/throw_exception.hpp>
14 #include <boost/graph/distributed/compressed_sparse_row_graph.hpp>
15 #include <boost/graph/distributed/mpi_process_group.hpp>
16 #include <boost/graph/distributed/concepts.hpp>
17
18 #include <boost/graph/erdos_renyi_generator.hpp>
19 #include <boost/graph/small_world_generator.hpp>
20 #include <boost/graph/rmat_graph_generator.hpp>
21
22 #include <boost/graph/breadth_first_search.hpp>
23 #include <boost/graph/depth_first_search.hpp>
24 #include <boost/graph/distributed/delta_stepping_shortest_paths.hpp>
25 #include <boost/graph/dijkstra_shortest_paths.hpp>
26 #include <boost/graph/distributed/page_rank.hpp>
27 #include <boost/graph/distributed/boman_et_al_graph_coloring.hpp>
28 #include <boost/graph/connected_components.hpp>
29 #include <boost/graph/strong_components.hpp>
30 #include <boost/graph/distributed/betweenness_centrality.hpp>
31 #include <boost/graph/distributed/dehne_gotz_min_spanning_tree.hpp>
32 #include <boost/graph/distributed/st_connected.hpp>
33
34 #if 0 // Contains internal AdjList types not present in CSR graph
35 # include <boost/graph/distributed/connected_components_parallel_search.hpp>
36 #endif
37
38 #include <boost/graph/distributed/vertex_list_adaptor.hpp> // Needed for MST
39
40 #include <boost/random/linear_congruential.hpp>
41 #include <boost/graph/graphviz.hpp>
42 #include <boost/property_map/vector_property_map.hpp>
43 #include <boost/test/minimal.hpp>
44
45 #ifdef BOOST_NO_EXCEPTIONS
46 void
throw_exception(std::exception const & ex)47 boost::throw_exception(std::exception const& ex)
48 {
49 std::cout << ex.what() << std::endl;
50 abort();
51 }
52 #endif
53
54
55 /****************************************************************************
56 * Edge weight generator iterator *
57 ****************************************************************************/
58 template<typename F, typename RandomGenerator>
59 class generator_iterator
60 {
61 public:
62 typedef std::input_iterator_tag iterator_category;
63 typedef typename F::result_type value_type;
64 typedef const value_type& reference;
65 typedef const value_type* pointer;
66 typedef void difference_type;
67
68 explicit
generator_iterator(RandomGenerator & gen,const F & f=F ())69 generator_iterator(RandomGenerator& gen, const F& f = F())
70 : f(f), gen(&gen)
71 {
72 value = this->f(gen);
73 }
74
operator *() const75 reference operator*() const { return value; }
operator ->() const76 pointer operator->() const { return &value; }
77
operator ++()78 generator_iterator& operator++()
79 {
80 value = f(*gen);
81 return *this;
82 }
83
operator ++(int)84 generator_iterator operator++(int)
85 {
86 generator_iterator temp(*this);
87 ++(*this);
88 return temp;
89 }
90
operator ==(const generator_iterator & other) const91 bool operator==(const generator_iterator& other) const
92 { return f == other.f; }
93
operator !=(const generator_iterator & other) const94 bool operator!=(const generator_iterator& other) const
95 { return !(*this == other); }
96
97 private:
98 F f;
99 RandomGenerator* gen;
100 value_type value;
101 };
102
103 template<typename F, typename RandomGenerator>
104 inline generator_iterator<F, RandomGenerator>
make_generator_iterator(RandomGenerator & gen,const F & f)105 make_generator_iterator( RandomGenerator& gen, const F& f)
106 { return generator_iterator<F, RandomGenerator>(gen, f); }
107
108
109 /****************************************************************************
110 * Printing DFS Visitor *
111 ****************************************************************************/
112
113 struct printing_dfs_visitor
114 {
115 template<typename Vertex, typename Graph>
initialize_vertexprinting_dfs_visitor116 void initialize_vertex(Vertex v, const Graph& g)
117 {
118 vertex_event("initialize_vertex", v, g);
119 }
120
121 template<typename Vertex, typename Graph>
start_vertexprinting_dfs_visitor122 void start_vertex(Vertex v, const Graph& g)
123 {
124 vertex_event("start_vertex", v, g);
125 }
126
127 template<typename Vertex, typename Graph>
discover_vertexprinting_dfs_visitor128 void discover_vertex(Vertex v, const Graph& g)
129 {
130 vertex_event("discover_vertex", v, g);
131 }
132
133 template<typename Edge, typename Graph>
examine_edgeprinting_dfs_visitor134 void examine_edge(Edge e, const Graph& g)
135 {
136 edge_event("examine_edge", e, g);
137 }
138
139 template<typename Edge, typename Graph>
tree_edgeprinting_dfs_visitor140 void tree_edge(Edge e, const Graph& g)
141 {
142 edge_event("tree_edge", e, g);
143 }
144
145 template<typename Edge, typename Graph>
back_edgeprinting_dfs_visitor146 void back_edge(Edge e, const Graph& g)
147 {
148 edge_event("back_edge", e, g);
149 }
150
151 template<typename Edge, typename Graph>
forward_or_cross_edgeprinting_dfs_visitor152 void forward_or_cross_edge(Edge e, const Graph& g)
153 {
154 edge_event("forward_or_cross_edge", e, g);
155 }
156
157 template<typename Vertex, typename Graph>
finish_vertexprinting_dfs_visitor158 void finish_vertex(Vertex v, const Graph& g)
159 {
160 vertex_event("finish_vertex", v, g);
161 }
162
163 private:
164 template<typename Vertex, typename Graph>
vertex_eventprinting_dfs_visitor165 void vertex_event(const char* name, Vertex v, const Graph& g)
166 {
167 std::cerr << "#" << process_id(g.process_group()) << ": " << name << "("
168 << get_vertex_name(v, g) << ": " << local(v) << "@" << owner(v)
169 << ")\n";
170 }
171
172 template<typename Edge, typename Graph>
edge_eventprinting_dfs_visitor173 void edge_event(const char* name, Edge e, const Graph& g)
174 {
175 std::cerr << "#" << process_id(g.process_group()) << ": " << name << "("
176 << get_vertex_name(source(e, g), g) << ": "
177 << local(source(e, g)) << "@" << owner(source(e, g)) << ", "
178 << get_vertex_name(target(e, g), g) << ": "
179 << local(target(e, g)) << "@" << owner(target(e, g)) << ")\n";
180 }
181
182 };
183
184 using namespace boost;
185 using boost::graph::distributed::mpi_process_group;
186
187 typedef int weight_type;
188
189 struct WeightedEdge {
WeightedEdgeWeightedEdge190 WeightedEdge(weight_type weight = 0) : weight(weight) { }
191
192 weight_type weight;
193
194 template<typename Archiver>
serializeWeightedEdge195 void serialize(Archiver& ar, const unsigned int /*version*/)
196 {
197 ar & weight;
198 }
199 };
200
201 struct VertexProperties {
VertexPropertiesVertexProperties202 VertexProperties(int d = 0)
203 : distance(d) { }
204
205 int distance;
206
207 template<typename Archiver>
serializeVertexProperties208 void serialize(Archiver& ar, const unsigned int /*version*/)
209 {
210 ar & distance;
211 }
212 };
213
test_main(int argc,char * argv[])214 int test_main(int argc, char* argv[])
215 {
216 mpi::environment env(argc, argv);
217
218 typedef compressed_sparse_row_graph<directedS, VertexProperties, WeightedEdge,
219 no_property, distributedS<mpi_process_group> >
220 Digraph;
221
222 // Make sure we can build graphs using common graph generators
223 typedef sorted_erdos_renyi_iterator<minstd_rand, Digraph> ERIter;
224 typedef small_world_iterator<minstd_rand, Digraph> SWIter;
225 typedef sorted_rmat_iterator<minstd_rand, Digraph> RMATIter;
226
227 typedef graph_traits<Digraph>::edge_descriptor edge_descriptor;
228
229 int n = 40;
230 int k = 3;
231 double prob = 0.1;
232 int C = 10;
233 double a = 0.5, b = 0.1, c = 0.25, d = 0.15;
234 int iterations = 50;
235 int num_colors = n / 10;
236 int lookahead = C / 10;
237
238 minstd_rand gen;
239
240 // Directed Graphs
241 Digraph g(ERIter(gen, n, prob), ERIter(),
242 make_generator_iterator(gen, uniform_int<int>(0, C)),
243 n);
244 Digraph g2(SWIter(gen, n, k, prob), SWIter(), n);
245 Digraph g3(RMATIter(gen, n, size_t(n*n*prob), a, b, c, d), RMATIter(), n);
246
247 // Test BFS
248 breadth_first_search(g, vertex(0, g), visitor(bfs_visitor<>()));
249
250 // Test SSSP Algorithms
251 graph::distributed::delta_stepping_shortest_paths(g,
252 vertex(0, g),
253 dummy_property_map(),
254 get(&VertexProperties::distance, g),
255 get(&WeightedEdge::weight, g));
256
257 dijkstra_shortest_paths(g, vertex(0, g),
258 distance_map(get(&VertexProperties::distance, g)).
259 weight_map(get(&WeightedEdge::weight, g)));
260
261 dijkstra_shortest_paths(g, vertex(0, g),
262 distance_map(get(&VertexProperties::distance, g)).
263 weight_map(get(&WeightedEdge::weight, g)).
264 lookahead(lookahead));
265
266 // Test PageRank
267 using boost::graph::n_iterations;
268
269 std::vector<double> ranks(num_vertices(g));
270
271 page_rank(g,
272 make_iterator_property_map(ranks.begin(),
273 get(boost::vertex_index, g)),
274 n_iterations(iterations), 0.85, vertex(0, g));
275
276 // Test Graph Coloring
277 typedef property_map<Digraph, vertex_index_t>::type vertex_index_map;
278
279 std::vector<int> colors_vec(num_vertices(g));
280 iterator_property_map<int*, vertex_index_map> color(&colors_vec[0],
281 get(vertex_index, g));
282
283 graph::boman_et_al_graph_coloring(g, color, num_colors);
284
285 // Test DFS
286 //
287 // DFS requires an undirected graph, currently CSR graphs must be directed
288 #if 0
289 std::vector<vertex_descriptor> parent(num_vertices(g));
290 std::vector<vertex_descriptor> explore(num_vertices(g));
291
292 boost::graph::tsin_depth_first_visit
293 (g,
294 vertex(0, g),
295 printing_dfs_visitor(),
296 color,
297 make_iterator_property_map(parent.begin(), get(vertex_index, g)),
298 make_iterator_property_map(explore.begin(), get(vertex_index, g)),
299 get(vertex_index, g));
300 #endif
301
302 // Test S-T Connected
303 st_connected(g, vertex(0, g), vertex(1, g), color, get(vertex_owner, g));
304
305 // Test Connected Components
306 //
307 // CC requires an undirected graph, currently CSR graphs must be directed
308 #if 0
309 std::vector<int> local_components_vec(num_vertices(g));
310 typedef iterator_property_map<std::vector<int>::iterator,
311 vertex_index_map> ComponentMap;
312 ComponentMap component(local_components_vec.begin(), get(vertex_index, g));
313
314 assert(connected_components(g, component) ==
315 connected_components_ps(g, component));
316 #endif
317
318 // Test Betweenness Centrality
319 //
320 // Betweenness Centrality is broken at the moment
321 typedef iterator_property_map<std::vector<int>::iterator, vertex_index_map>
322 CentralityMap;
323
324 std::vector<int> centralityS(num_vertices(g), 0);
325 CentralityMap centrality(centralityS.begin(), get(vertex_index, g));
326
327 brandes_betweenness_centrality(g, centrality);
328
329 //
330 // Test MST
331 //
332 std::vector<edge_descriptor> mst_edges;
333
334 dense_boruvka_minimum_spanning_tree(make_vertex_list_adaptor(g),
335 get(&WeightedEdge::weight, g),
336 std::back_inserter(mst_edges));
337
338 mst_edges.clear();
339 merge_local_minimum_spanning_trees(make_vertex_list_adaptor(g),
340 get(&WeightedEdge::weight, g),
341 std::back_inserter(mst_edges));
342
343 mst_edges.clear();
344 boruvka_then_merge(make_vertex_list_adaptor(g),
345 get(&WeightedEdge::weight, g),
346 std::back_inserter(mst_edges));
347
348 mst_edges.clear();
349 boruvka_mixed_merge(make_vertex_list_adaptor(g),
350 get(&WeightedEdge::weight, g),
351 std::back_inserter(mst_edges));
352
353 // Test Strong Components
354 //
355 // Can't build reverse graph of a CSR graph
356 #if 0
357 std::vector<int> local_components_vec(num_vertices(g));
358 typedef iterator_property_map<std::vector<int>::iterator,
359 vertex_index_map> ComponentMap;
360 ComponentMap component(local_components_vec.begin(), get(vertex_index, g));
361
362 int num_components = strong_components(g, component);
363 #endif
364
365 std::ofstream out("dcsr.dot");
366 write_graphviz(out, g);
367
368 return 0;
369 }
370