1 // Copyright (C) 2007 Trustees of Indiana University
2
3 // Authors: Douglas Gregor
4 // Andrew Lumsdaine
5
6 // Use, modification and distribution is subject to the Boost Software
7 // License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
8 // http://www.boost.org/LICENSE_1_0.txt)
9
10 // A test of the communicator that passes data around a ring and
11 // verifies that the same data makes it all the way. Should test all
12 // of the various kinds of data that can be sent (primitive types, POD
13 // types, serializable objects, etc.)
14 #include <boost/mpi/graph_communicator.hpp>
15 #include <boost/mpi/communicator.hpp>
16 #include <boost/mpi/environment.hpp>
17 #include <boost/graph/adjacency_list.hpp>
18 #include <boost/lexical_cast.hpp>
19 #include <boost/graph/erdos_renyi_generator.hpp>
20 #include <boost/random/linear_congruential.hpp>
21 #include <boost/graph/iteration_macros.hpp>
22 #include <boost/graph/isomorphism.hpp>
23 #include <algorithm> // for random_shuffle
24 #include <boost/serialization/vector.hpp>
25 #include <boost/mpi/collectives/broadcast.hpp>
26 #include <boost/config.hpp>
27
28 #define BOOST_TEST_MODULE mpi_graph_topology
29 #include <boost/test/included/unit_test.hpp>
30
31 #if defined(BOOST_NO_CXX98_RANDOM_SHUFFLE)
32
33 #include <random>
34
35 std::default_random_engine gen;
36
random_shuffle(RandomIt first,RandomIt last)37 template<typename RandomIt> void random_shuffle( RandomIt first, RandomIt last )
38 {
39 std::shuffle( first, last, gen );
40 }
41
42 #else
43
44 using std::random_shuffle;
45
46 #endif // #if defined(BOOST_NO_CXX98_RANDOM_SHUFFLE)
47
48
49 using boost::mpi::communicator;
50 using boost::mpi::graph_communicator;
51 using namespace boost;
52
BOOST_AUTO_TEST_CASE(graph_topology)53 BOOST_AUTO_TEST_CASE(graph_topology)
54 {
55 boost::function_requires< IncidenceGraphConcept<graph_communicator> >();
56 boost::function_requires< AdjacencyGraphConcept<graph_communicator> >();
57 boost::function_requires< VertexListGraphConcept<graph_communicator> >();
58 boost::function_requires< EdgeListGraphConcept<graph_communicator> >();
59
60 double prob = 0.1;
61
62 boost::mpi::environment env;
63 communicator world;
64
65 // Random number generator
66 minstd_rand gen;
67
68 // Build a random graph with as many vertices as there are processes
69 typedef adjacency_list<listS, vecS, bidirectionalS> Graph;
70 sorted_erdos_renyi_iterator<minstd_rand, Graph>
71 first(gen, world.size(), prob), last;
72 Graph graph(first, last, world.size());
73
74 // Display the original graph
75 if (world.rank() == 0) {
76 std::cout << "Original, random graph:\n";
77 BGL_FORALL_VERTICES(v, graph, Graph) {
78 BGL_FORALL_OUTEDGES(v, e, graph, Graph) {
79 std::cout << source(e, graph) << " -> " << target(e, graph)
80 << std::endl;
81 }
82 }
83 }
84
85 // Create an arbitrary mapping from vertices to integers
86 typedef property_map<Graph, vertex_index_t>::type GraphVertexIndexMap;
87 std::vector<int> graph_alt_index_vec(num_vertices(graph));
88 iterator_property_map<int*, GraphVertexIndexMap>
89 graph_alt_index(&graph_alt_index_vec[0], get(vertex_index, graph));
90
91 // Rank 0 will populate the alternative index vector
92 if (world.rank() == 0) {
93 int index = 0;
94 BGL_FORALL_VERTICES(v, graph, Graph)
95 put(graph_alt_index, v, index++);
96
97 ::random_shuffle(graph_alt_index_vec.begin(), graph_alt_index_vec.end());
98 }
99 broadcast(world, graph_alt_index_vec, 0);
100
101 // Display the original graph with the remapping
102 if (world.rank() == 0) {
103 std::cout << "Original, random graph with remapped vertex numbers:\n";
104 BGL_FORALL_VERTICES(v, graph, Graph) {
105 BGL_FORALL_OUTEDGES(v, e, graph, Graph) {
106 std::cout << get(graph_alt_index, source(e, graph)) << " -> "
107 << get(graph_alt_index, target(e, graph)) << std::endl;
108 }
109 }
110 }
111
112 // Create a communicator with a topology equivalent to the graph
113 graph_communicator graph_comm(world, graph, graph_alt_index, false);
114
115 // The communicator's topology should have the same number of
116 // vertices and edges and the original graph
117 BOOST_CHECK((int)num_vertices(graph) == num_vertices(graph_comm));
118 BOOST_CHECK((int)num_edges(graph) == num_edges(graph_comm));
119
120 // Display the communicator graph
121 if (graph_comm.rank() == 0) {
122 std::cout << "Communicator graph:\n";
123 BGL_FORALL_VERTICES(v, graph_comm, graph_communicator) {
124 BGL_FORALL_OUTEDGES(v, e, graph_comm, graph_communicator) {
125 std::cout << source(e, graph_comm) << " -> " << target(e, graph_comm)
126 << std::endl;
127 }
128 }
129
130 std::cout << "Communicator graph via edges():\n";
131 BGL_FORALL_EDGES(e, graph_comm, graph_communicator)
132 std::cout << source(e, graph_comm) << " -> " << target(e, graph_comm)
133 << std::endl;
134 }
135 (graph_comm.barrier)();
136
137 // Verify the isomorphism
138 if (graph_comm.rank() == 0)
139 std::cout << "Verifying isomorphism..." << std::endl;
140 BOOST_CHECK(verify_isomorphism(graph, graph_comm, graph_alt_index));
141 }
142