123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245 |
- // 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;
- }
|