246 lines
7.9 KiB
C++
246 lines
7.9 KiB
C++
// Copyright (C) 2007 Douglas Gregor
|
|
|
|
// 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)
|
|
|
|
#include <boost/graph/use_mpi.hpp>
|
|
#include <boost/config.hpp>
|
|
#include <boost/throw_exception.hpp>
|
|
#include <boost/graph/distributed/adjacency_list.hpp>
|
|
#include <boost/graph/distributed/mpi_process_group.hpp>
|
|
#include <boost/test/minimal.hpp>
|
|
#include <boost/random/linear_congruential.hpp>
|
|
#include <boost/graph/erdos_renyi_generator.hpp>
|
|
#include <boost/lexical_cast.hpp>
|
|
#include <ctime>
|
|
|
|
using namespace boost;
|
|
using boost::graph::distributed::mpi_process_group;
|
|
|
|
#ifdef BOOST_NO_EXCEPTIONS
|
|
void
|
|
boost::throw_exception(std::exception const& ex)
|
|
{
|
|
std::cout << ex.what() << std::endl;
|
|
abort();
|
|
}
|
|
#endif
|
|
|
|
|
|
int test_main(int argc, char** argv)
|
|
{
|
|
boost::mpi::environment env(argc, argv);
|
|
|
|
int n = 10000;
|
|
double p = 3e-3;
|
|
int seed = std::time(0);
|
|
int immediate_response_percent = 10;
|
|
|
|
if (argc > 1) n = lexical_cast<int>(argv[1]);
|
|
if (argc > 2) p = lexical_cast<double>(argv[2]);
|
|
if (argc > 3) seed = lexical_cast<int>(argv[3]);
|
|
|
|
typedef adjacency_list<listS,
|
|
distributedS<mpi_process_group, vecS>,
|
|
bidirectionalS> Graph;
|
|
|
|
mpi_process_group pg;
|
|
int rank = process_id(pg);
|
|
int numprocs = num_processes(pg);
|
|
bool i_am_root = rank == 0;
|
|
|
|
// broadcast the seed
|
|
broadcast(pg, seed, 0);
|
|
|
|
// Random number generator
|
|
minstd_rand gen;
|
|
minstd_rand require_response_gen;
|
|
|
|
if (i_am_root) {
|
|
std::cout << "n = " << n << ", p = " << p << ", seed = " << seed
|
|
<< "\nBuilding graph with the iterator constructor... ";
|
|
std::cout.flush();
|
|
}
|
|
|
|
// Build a graph using the iterator constructor, where each of the
|
|
// processors has exactly the same information.
|
|
gen.seed(seed);
|
|
Graph g1(erdos_renyi_iterator<minstd_rand, Graph>(gen, n, p),
|
|
erdos_renyi_iterator<minstd_rand, Graph>(),
|
|
n, pg, Graph::graph_property_type());
|
|
// NGE: Grrr, the default graph property is needed to resolve an
|
|
// ambiguous overload in the adjaceny list constructor
|
|
|
|
// Build another, identical graph using add_edge
|
|
if (i_am_root) {
|
|
std::cout << "done.\nBuilding graph with add_edge from the root...";
|
|
std::cout.flush();
|
|
}
|
|
|
|
gen.seed(seed);
|
|
require_response_gen.seed(1);
|
|
Graph g2(n, pg);
|
|
if (i_am_root) {
|
|
// The root will add all of the edges, some percentage of which
|
|
// will require an immediate response from the owner of the edge.
|
|
for (erdos_renyi_iterator<minstd_rand, Graph> first(gen, n, p), last;
|
|
first != last; ++first) {
|
|
Graph::lazy_add_edge lazy
|
|
= add_edge(vertex(first->first, g2), vertex(first->second, g2), g2);
|
|
|
|
if ((int)require_response_gen() % 100 < immediate_response_percent) {
|
|
// Send out-of-band to require a response
|
|
std::pair<graph_traits<Graph>::edge_descriptor, bool> result(lazy);
|
|
BOOST_CHECK(source(result.first, g2) == vertex(first->first, g2));
|
|
BOOST_CHECK(target(result.first, g2) == vertex(first->second, g2));
|
|
}
|
|
}
|
|
}
|
|
|
|
if (i_am_root) {
|
|
std::cout << "synchronizing...";
|
|
std::cout.flush();
|
|
}
|
|
|
|
synchronize(g2);
|
|
|
|
// Verify that the two graphs are indeed identical.
|
|
if (i_am_root) {
|
|
std::cout << "done.\nVerifying graphs...";
|
|
std::cout.flush();
|
|
}
|
|
|
|
// Check the number of vertices
|
|
if (num_vertices(g1) != num_vertices(g2)) {
|
|
std::cerr << g1.processor() << ": g1 has " << num_vertices(g1)
|
|
<< " vertices, g2 has " << num_vertices(g2) << " vertices.\n";
|
|
communicator(pg).abort(-1);
|
|
}
|
|
|
|
// Check the number of edges
|
|
if (num_edges(g1) != num_edges(g2)) {
|
|
std::cerr << g1.processor() << ": g1 has " << num_edges(g1)
|
|
<< " edges, g2 has " << num_edges(g2) << " edges.\n";
|
|
communicator(pg).abort(-1);
|
|
}
|
|
|
|
// Check the in-degree and out-degree of each vertex
|
|
graph_traits<Graph>::vertex_iterator vfirst1, vlast1, vfirst2, vlast2;
|
|
boost::tie(vfirst1, vlast1) = vertices(g1);
|
|
boost::tie(vfirst2, vlast2) = vertices(g2);
|
|
for(; vfirst1 != vlast1 && vfirst2 != vlast2; ++vfirst1, ++vfirst2) {
|
|
if (out_degree(*vfirst1, g1) != out_degree(*vfirst2, g2)) {
|
|
std::cerr << g1.processor() << ": out-degree mismatch ("
|
|
<< out_degree(*vfirst1, g1) << " vs. "
|
|
<< out_degree(*vfirst2, g2) << ").\n";
|
|
communicator(pg).abort(-1);
|
|
}
|
|
|
|
if (in_degree(*vfirst1, g1) != in_degree(*vfirst2, g2)) {
|
|
std::cerr << g1.processor() << ": in-degree mismatch ("
|
|
<< in_degree(*vfirst1, g1) << " vs. "
|
|
<< in_degree(*vfirst2, g2) << ").\n";
|
|
communicator(pg).abort(-1);
|
|
}
|
|
}
|
|
|
|
// TODO: Check the actual edge targets
|
|
|
|
// Build another, identical graph using add_edge
|
|
if (i_am_root) {
|
|
std::cout << "done.\nBuilding graph with add_edge from everywhere...";
|
|
std::cout.flush();
|
|
}
|
|
|
|
gen.seed(seed);
|
|
require_response_gen.seed(1);
|
|
Graph g3(n, pg);
|
|
|
|
{
|
|
// Each processor will take a chunk of incoming edges and add
|
|
// them. Some percentage of the edge additions will require an
|
|
// immediate response from the owner of the edge. This should
|
|
// create a lot of traffic when building the graph, but should
|
|
// produce a graph identical to the other graphs.
|
|
typedef graph_traits<Graph>::edges_size_type edges_size_type;
|
|
|
|
erdos_renyi_iterator<minstd_rand, Graph> first(gen, n, p);
|
|
edges_size_type chunk_size = edges_size_type(p*n*n)/numprocs;
|
|
edges_size_type start = chunk_size * rank;
|
|
edges_size_type remaining_edges =
|
|
(rank < numprocs - 1? chunk_size
|
|
: edges_size_type(p*n*n) - start);
|
|
|
|
// Spin the generator to the first edge we're responsible for
|
|
for (; start; ++first, --start) ;
|
|
|
|
for (; remaining_edges; --remaining_edges, ++first) {
|
|
Graph::lazy_add_edge lazy
|
|
= add_edge(vertex(first->first, g3), vertex(first->second, g3), g3);
|
|
|
|
if ((int)require_response_gen() % 100 < immediate_response_percent) {
|
|
// Send out-of-band to require a response
|
|
std::pair<graph_traits<Graph>::edge_descriptor, bool> result(lazy);
|
|
BOOST_CHECK(source(result.first, g3) == vertex(first->first, g3));
|
|
BOOST_CHECK(target(result.first, g3) == vertex(first->second, g3));
|
|
}
|
|
}
|
|
}
|
|
|
|
if (i_am_root) {
|
|
std::cout << "synchronizing...";
|
|
std::cout.flush();
|
|
}
|
|
|
|
synchronize(g3);
|
|
|
|
// Verify that the two graphs are indeed identical.
|
|
if (i_am_root) {
|
|
std::cout << "done.\nVerifying graphs...";
|
|
std::cout.flush();
|
|
}
|
|
|
|
// Check the number of vertices
|
|
if (num_vertices(g1) != num_vertices(g3)) {
|
|
std::cerr << g1.processor() << ": g1 has " << num_vertices(g1)
|
|
<< " vertices, g3 has " << num_vertices(g3) << " vertices.\n";
|
|
communicator(pg).abort(-1);
|
|
}
|
|
|
|
// Check the number of edges
|
|
if (num_edges(g1) != num_edges(g3)) {
|
|
std::cerr << g1.processor() << ": g1 has " << num_edges(g1)
|
|
<< " edges, g3 has " << num_edges(g3) << " edges.\n";
|
|
communicator(pg).abort(-1);
|
|
}
|
|
|
|
// Check the in-degree and out-degree of each vertex
|
|
boost::tie(vfirst1, vlast1) = vertices(g1);
|
|
boost::tie(vfirst2, vlast2) = vertices(g3);
|
|
for(; vfirst1 != vlast1 && vfirst2 != vlast2; ++vfirst1, ++vfirst2) {
|
|
if (out_degree(*vfirst1, g1) != out_degree(*vfirst2, g3)) {
|
|
std::cerr << g1.processor() << ": out-degree mismatch ("
|
|
<< out_degree(*vfirst1, g1) << " vs. "
|
|
<< out_degree(*vfirst2, g3) << ").\n";
|
|
communicator(pg).abort(-1);
|
|
}
|
|
|
|
if (in_degree(*vfirst1, g1) != in_degree(*vfirst2, g3)) {
|
|
std::cerr << g1.processor() << ": in-degree mismatch ("
|
|
<< in_degree(*vfirst1, g1) << " vs. "
|
|
<< in_degree(*vfirst2, g3) << ").\n";
|
|
communicator(pg).abort(-1);
|
|
}
|
|
}
|
|
|
|
// TODO: Check the actual edge targets
|
|
|
|
if (i_am_root) {
|
|
std::cout << "done.\n";
|
|
std::cout.flush();
|
|
}
|
|
|
|
return 0;
|
|
}
|