142 lines
4.7 KiB
C++
142 lines
4.7 KiB
C++
// 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));
|
|
}
|