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