diff options
Diffstat (limited to 'src/boost/libs/graph_parallel/test')
30 files changed, 6703 insertions, 0 deletions
diff --git a/src/boost/libs/graph_parallel/test/Jamfile.v2 b/src/boost/libs/graph_parallel/test/Jamfile.v2 new file mode 100644 index 000000000..61bf16189 --- /dev/null +++ b/src/boost/libs/graph_parallel/test/Jamfile.v2 @@ -0,0 +1,47 @@ +# +# (C) Copyright 2005, 2006 Trustees of Indiana University +# (C) Copyright 2005 Douglas Gregor +# +# Distributed under 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.) + + +# use-project /boost/mpi : ../build ; + +project /boost/graph_parallel/test + : requirements <library>../build//boost_graph_parallel <library>../../system/build//boost_system ; + +import mpi : mpi-test ; + +if [ mpi.configured ] +{ +test-suite graph_parallel + : + [ mpi-test distributed_property_map_test : : : 2 ] + [ mpi-test distributed_queue_test : : : 2 ] + [ mpi-test process_group_serialization : : : 2 ] + [ mpi-test adjlist_build_test : : : 2 ] + [ mpi-test adjlist_redist_test : : : 2 ] + [ mpi-test adjlist_remove_test : : : 2 ] + [ mpi-test distributed_adjacency_list_test : : : 2 ] + [ mpi-test distributed_connected_components_test : : : 2 ] + [ mpi-test distributed_page_rank_test : : : 2 ] + [ mpi-test distributed_csr_test : : : 2 ] + [ mpi-test distributed_dfs_test : : : 2 ] + [ mpi-test distributed_graph_coloring_test : : : 2 ] + [ mpi-test distributed_mst_test : : : 2 ] + [ mpi-test distributed_strong_components_test : : : 2 ] + [ mpi-test hohberg_biconnected_components_test : : : 2 ] + [ mpi-test mesh_generator_test : : <testing.arg>"1000 1000 1 0" : 2 ] + [ mpi-test named_vertices_seq : : : 1 ] + [ mpi-test distributed_shortest_paths_test : : : 2 ] + [ mpi-test distributed_csr_algorithm_test : : : 1 ] + [ mpi-test distributed_betweenness_centrality_test : : : 2 ] + [ mpi-test distributed_dimacs_reader : : : 2 ] + [ mpi-test distributed_rmat_cc_ps : : : 2 ] + [ mpi-test distributed_rmat_cc : : : 2 ] + [ mpi-test distributed_rmat_pagerank : : : 2 ] + [ mpi-test distributed_st_connected_test : : : 2 ] + ; +} + diff --git a/src/boost/libs/graph_parallel/test/adjlist_build_test.cpp b/src/boost/libs/graph_parallel/test/adjlist_build_test.cpp new file mode 100644 index 000000000..87335a50a --- /dev/null +++ b/src/boost/libs/graph_parallel/test/adjlist_build_test.cpp @@ -0,0 +1,245 @@ +// 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; +} diff --git a/src/boost/libs/graph_parallel/test/adjlist_redist_test.cpp b/src/boost/libs/graph_parallel/test/adjlist_redist_test.cpp new file mode 100644 index 000000000..96a659ae5 --- /dev/null +++ b/src/boost/libs/graph_parallel/test/adjlist_redist_test.cpp @@ -0,0 +1,216 @@ +// Copyright (C) 2005, 2006 The Trustees of Indiana University. + +// 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) + +// Authors: Douglas Gregor +// Andrew Lumsdaine + +#include <boost/graph/use_mpi.hpp> +#include <boost/config.hpp> +#include <boost/throw_exception.hpp> +#include <boost/lexical_cast.hpp> +#include <boost/serialization/vector.hpp> +#include <boost/graph/distributed/adjacency_list.hpp> +#include <boost/graph/distributed/mpi_process_group.hpp> +#include <boost/random/linear_congruential.hpp> +#include <iostream> +#include <boost/property_map/property_map_iterator.hpp> +#include <boost/graph/distributed/dehne_gotz_min_spanning_tree.hpp> +#include <boost/graph/distributed/vertex_list_adaptor.hpp> +#include <boost/graph/erdos_renyi_generator.hpp> +#include <boost/graph/distributed/graphviz.hpp> +#include <sstream> +#include <string> +#include <boost/graph/iteration_macros.hpp> +#include <boost/test/minimal.hpp> + +#ifdef BOOST_NO_EXCEPTIONS +void +boost::throw_exception(std::exception const& ex) +{ + std::cout << ex.what() << std::endl; + abort(); +} +#endif + +using namespace boost; +using boost::graph::distributed::mpi_process_group; + +/**************************************************************************** + * Edge weight generator iterator * + ****************************************************************************/ +template<typename F> +class generator_iterator +{ +public: + typedef std::input_iterator_tag iterator_category; + typedef typename F::result_type value_type; + typedef const value_type& reference; + typedef const value_type* pointer; + typedef void difference_type; + + explicit generator_iterator(const F& f = F()) : f(f) { value = this->f(); } + + reference operator*() const { return value; } + pointer operator->() const { return &value; } + + generator_iterator& operator++() + { + value = f(); + return *this; + } + + generator_iterator operator++(int) + { + generator_iterator temp(*this); + ++(*this); + return temp; + } + + bool operator==(const generator_iterator& other) const + { return f == other.f; } + + bool operator!=(const generator_iterator& other) const + { return !(*this == other); } + +private: + F f; + value_type value; +}; + +template<typename F> +inline generator_iterator<F> make_generator_iterator(const F& f) +{ return generator_iterator<F>(f); } + +typedef minstd_rand RandomGenerator; + +template<typename Graph> +double get_mst_weight (const Graph& g) +{ + typedef typename graph_traits<Graph>::edge_descriptor edge_descriptor; + typename property_map<Graph, edge_weight_t>::const_type weight + = get(edge_weight, g); + + // Boruvka then merge test + std::vector<edge_descriptor> results; + graph::boruvka_then_merge(make_vertex_list_adaptor(g), weight, + std::back_inserter(results)); + if (process_id(g.process_group()) == 0) + return accumulate(make_property_map_iterator(weight, results.begin()), + make_property_map_iterator(weight, results.end()), + 0.0); + else + return 0.0; +} + +template<typename Graph> +void test_redistribution(int n, double p, int iterations, bool debug_output) +{ + RandomGenerator gen; + Graph g(erdos_renyi_iterator<RandomGenerator, Graph>(gen, n, p), + erdos_renyi_iterator<RandomGenerator, Graph>(), + make_generator_iterator(uniform_01<RandomGenerator>(gen)), + n); + + int iter = 0; + mpi_process_group pg = g.process_group(); + + // Set the names of the vertices to be the global index in the + // initial distribution. Then when we are debugging we'll be able to + // see how vertices have moved. + { + typedef typename property_map<Graph, vertex_index_t>::type VertexIndexMap; + typedef typename property_map<Graph, vertex_global_t>::type VertexGlobalMap; + typename property_map<Graph, vertex_name_t>::type name_map + = get(vertex_name, g); + + parallel::global_index_map<VertexIndexMap, VertexGlobalMap> + global_index(g.process_group(), num_vertices(g), + get(vertex_index, g), get(vertex_global, g)); + BGL_FORALL_VERTICES_T(v, g, Graph) + put(name_map, v, get(global_index, v)); + } + + if (debug_output) + write_graphviz("redist-0.dot", g, + make_label_writer(get(vertex_name, g)), + make_label_writer(get(edge_weight, g))); + + double mst_weight = get_mst_weight(g); + if (process_id(pg) == 0) + std::cout << "MST weight = " << mst_weight << std::endl; + + RandomGenerator nonsync_gen(process_id(pg) + gen()); + while (++iter <= iterations) { + typename property_map<Graph, vertex_rank_t>::type to_processor_map = + get(vertex_rank, g); + + // Randomly assign a new distribution + typename graph_traits<Graph>::vertex_iterator vi, vi_end; + for (boost::tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi) + put(to_processor_map, *vi, gen() % num_processes(pg)); + + if (process_id(pg) == 0) + std::cout << "Redistributing..."; + // Perform the actual redistribution + g.redistribute(to_processor_map); + + if (process_id(pg) == 0) + std::cout << " done." << std::endl; + + if (debug_output) { + std::ostringstream out; + out << "redist-" << iter << ".dot"; + write_graphviz(out.str().c_str(), g, + make_label_writer(get(vertex_name, g)), + make_label_writer(get(edge_weight, g))); + } + + // Check that the MST weight is unchanged + double new_mst_weight = get_mst_weight(g); + if (process_id(pg) == 0) { + std::cout << "MST weight = " << new_mst_weight << std::endl; + if (std::fabs(new_mst_weight - mst_weight) > 0.0001) + communicator(pg).abort(-1); } + } +} + +int test_main(int argc, char** argv) +{ + int n = 1000; + double p = 3e-3; + int iterations = 5; + bool debug_output = false; + + boost::mpi::environment env(argc, argv); + + if (argc > 1) n = lexical_cast<int>(argv[1]); + if (argc > 2) p = lexical_cast<double>(argv[2]); + if (argc > 3) iterations = lexical_cast<int>(argv[3]); + if (argc > 4) debug_output = true; + + typedef adjacency_list<listS, + distributedS<mpi_process_group, vecS>, + undirectedS, + // Vertex properties + property<vertex_name_t, std::size_t, + property<vertex_rank_t, int> >, + // Edge properties + property<edge_weight_t, double> > UnstableUDGraph; + typedef adjacency_list<listS, + distributedS<mpi_process_group, listS>, + undirectedS, + // Vertex properties + property<vertex_name_t, std::size_t, + property<vertex_rank_t, int, + property<vertex_index_t, std::size_t> > >, + // Edge properties + property<edge_weight_t, double> > StableUDGraph; + + test_redistribution<UnstableUDGraph>(n, p, iterations, debug_output); + test_redistribution<StableUDGraph>(n, p, iterations, debug_output); + + return 0; +} diff --git a/src/boost/libs/graph_parallel/test/adjlist_remove_test.cpp b/src/boost/libs/graph_parallel/test/adjlist_remove_test.cpp new file mode 100644 index 000000000..549c5195f --- /dev/null +++ b/src/boost/libs/graph_parallel/test/adjlist_remove_test.cpp @@ -0,0 +1,146 @@ +// Copyright 2004 The Trustees of Indiana University. + +// 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) + +// Authors: Douglas Gregor +// Andrew Lumsdaine + +#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/graph/parallel/distribution.hpp> +#include <iostream> +#include <cassert> +#include <boost/test/minimal.hpp> + +#ifdef BOOST_NO_EXCEPTIONS +void +boost::throw_exception(std::exception const& ex) +{ + std::cout << ex.what() << std::endl; + abort(); +} +#endif + +using namespace boost; +using boost::graph::distributed::mpi_process_group; + +void test_bidirectional_graph() +{ + typedef adjacency_list<listS, distributedS<mpi_process_group, vecS>, + bidirectionalS> Graph; + typedef graph_traits<Graph>::vertex_descriptor Vertex; + + typedef std::pair<std::size_t, std::size_t> E; + E edges[3] = { E(0,3), E(1,4), E(2,5) }; + + Graph g(&edges[0], &edges[0] + 3, 6); + assert(num_processes(g.process_group()) == 2); + + if (process_id(g.process_group()) == 0) + std::cerr << "Testing bidirectional graph edge removal..."; + synchronize(g.process_group()); + + graph_traits<Graph>::vertex_iterator vi = vertices(g).first; + Vertex u = *vi++; + Vertex v = *vi++; + Vertex w = *vi++; + BOOST_CHECK(vi == vertices(g).second); + + BOOST_CHECK((process_id(g.process_group()) == 0 && out_degree(u, g) == 1) + || (process_id(g.process_group()) == 1 && in_degree(u, g) == 1)); + + BOOST_CHECK((process_id(g.process_group()) == 0 && out_degree(v, g) == 1) + || (process_id(g.process_group()) == 1 && in_degree(v, g) == 1)); + + BOOST_CHECK((process_id(g.process_group()) == 0 && out_degree(w, g) == 1) + || (process_id(g.process_group()) == 1 && in_degree(w, g) == 1)); + + // Remove edges + if (process_id(g.process_group()) == 0) { + remove_edge(*out_edges(u, g).first, g); + remove_edge(*out_edges(w, g).first, g); + } else { + remove_edge(*in_edges(v, g).first, g); + remove_edge(*in_edges(w, g).first, g); + } + + synchronize(g); + + BOOST_CHECK(num_edges(g) == 0); + BOOST_CHECK(out_degree(u, g) == 0); + BOOST_CHECK(out_degree(v, g) == 0); + BOOST_CHECK(out_degree(w, g) == 0); + BOOST_CHECK(in_degree(u, g) == 0); + BOOST_CHECK(in_degree(v, g) == 0); + BOOST_CHECK(in_degree(w, g) == 0); + + if (process_id(g.process_group()) == 0) std::cerr << "OK.\n"; +} + +void test_undirected_graph() +{ + typedef adjacency_list<listS, distributedS<mpi_process_group, vecS>, + undirectedS> Graph; + typedef graph_traits<Graph>::vertex_descriptor Vertex; + typedef graph_traits<Graph>::edge_descriptor Edge; + + typedef std::pair<std::size_t, std::size_t> E; + E the_edges[3] = { E(0,3), E(1,4), E(2,5) }; + + Graph g(&the_edges[0], &the_edges[0] + 3, 6); + assert(num_processes(g.process_group()) == 2); + + if (process_id(g.process_group()) == 0) + std::cerr << "Testing undirected graph edge removal..."; + synchronize(g.process_group()); + + graph_traits<Graph>::vertex_iterator vi = vertices(g).first; + Vertex u = *vi++; + Vertex v = *vi++; + Vertex w = *vi++; + BOOST_CHECK(vi == vertices(g).second); + BOOST_CHECK(degree(u, g) == 1); + BOOST_CHECK(degree(v, g) == 1); + BOOST_CHECK(degree(w, g) == 1); + + // Remove edges + if (process_id(g.process_group()) == 0) { + BOOST_CHECK(num_edges(g) == 3); + remove_edge(*out_edges(u, g).first, g); + remove_edge(*out_edges(w, g).first, g); + } else { + BOOST_CHECK(num_edges(g) == 0); + remove_edge(*in_edges(v, g).first, g); + remove_edge(*in_edges(w, g).first, g); + } + + synchronize(g); + + if (num_edges(g) > 0) { + Edge e = *edges(g).first; + std::cerr << "#" << process_id(g.process_group()) << ": extra edge! (" + << local(source(e, g)) << "@" << owner(source(e, g)) + << ", " + << local(target(e, g)) << "@" << owner(target(e, g)) + << ")\n"; + } + + BOOST_CHECK(num_edges(g) == 0); + BOOST_CHECK(degree(u, g) == 0); + BOOST_CHECK(degree(v, g) == 0); + BOOST_CHECK(degree(w, g) == 0); + if (process_id(g.process_group()) == 0) std::cerr << "OK.\n"; +} + +int test_main(int argc, char** argv) +{ + boost::mpi::environment env(argc, argv); + test_bidirectional_graph(); + test_undirected_graph(); + return 0; +} diff --git a/src/boost/libs/graph_parallel/test/algorithm_performance.cpp b/src/boost/libs/graph_parallel/test/algorithm_performance.cpp new file mode 100644 index 000000000..c4973b41c --- /dev/null +++ b/src/boost/libs/graph_parallel/test/algorithm_performance.cpp @@ -0,0 +1,887 @@ +// Copyright 2004 The Trustees of Indiana University. + +// 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) + +// Authors: Nick Edmonds +// Andrew Lumsdaine + +// #define PBGL_ACCOUNTING + +#include <boost/graph/use_mpi.hpp> + +#include <boost/graph/distributed/compressed_sparse_row_graph.hpp> +#include <boost/graph/distributed/adjacency_list.hpp> + +#include <boost/graph/distributed/mpi_process_group.hpp> + +#include <boost/test/minimal.hpp> +#include <boost/random.hpp> +#include <boost/property_map/parallel/distributed_property_map.hpp> +#include <boost/graph/distributed/graphviz.hpp> +#include <boost/graph/iteration_macros.hpp> +#include <boost/graph/properties.hpp> + +#include <boost/graph/rmat_graph_generator.hpp> +#include <boost/graph/small_world_generator.hpp> +#include <boost/graph/erdos_renyi_generator.hpp> + +#include <boost/graph/distributed/connected_components.hpp> +#include <boost/graph/distributed/connected_components_parallel_search.hpp> +#include <boost/graph/distributed/betweenness_centrality.hpp> +#include <boost/graph/distributed/delta_stepping_shortest_paths.hpp> + +#include <time.h> +#include <sys/time.h> + +#include <iostream> +#include <iomanip> +#include <vector> +#include <stdint.h> + +// Edge distribution tags select a generator +struct rmat_edge_distribution_tag { }; +struct rmat_unique_edge_distribution_tag { }; + +using namespace boost; +using boost::graph::distributed::mpi_process_group; + +/**************************************************************************** + * Timing + ****************************************************************************/ +#ifndef PBGL_ACCOUNTING + +typedef double time_type; + +inline time_type get_time() +{ + timeval tp; + gettimeofday(&tp, 0); + return tp.tv_sec + tp.tv_usec / 1000000.0; +} + +std::string print_time(time_type t) +{ + std::ostringstream out; + out << std::setiosflags(std::ios::fixed) << std::setprecision(2) << t; + return out.str(); +} + +#endif // PBGL_ACCOUNTING + +/**************************************************************************** + * Edge weight generator iterator * + ****************************************************************************/ +template<typename F, typename RandomGenerator> +class generator_iterator +{ +public: + typedef std::input_iterator_tag iterator_category; + typedef typename F::result_type value_type; + typedef const value_type& reference; + typedef const value_type* pointer; + typedef void difference_type; + + explicit + generator_iterator(RandomGenerator& gen, const F& f = F()) + : f(f), gen(&gen) + { + value = this->f(gen); + } + + reference operator*() const { return value; } + pointer operator->() const { return &value; } + + generator_iterator& operator++() + { + value = f(*gen); + return *this; + } + + generator_iterator operator++(int) + { + generator_iterator temp(*this); + ++(*this); + return temp; + } + + bool operator==(const generator_iterator& other) const + { return f == other.f; } + + bool operator!=(const generator_iterator& other) const + { return !(*this == other); } + +private: + F f; + RandomGenerator* gen; + value_type value; +}; + +template<typename F, typename RandomGenerator> +inline generator_iterator<F, RandomGenerator> +make_generator_iterator( RandomGenerator& gen, const F& f) +{ return generator_iterator<F, RandomGenerator>(gen, f); } + +/**************************************************************************** + * Edge Property * + ****************************************************************************/ +typedef int weight_type; + +struct WeightedEdge { + WeightedEdge(weight_type weight = 0) : weight(weight) { } + + weight_type weight; + + template<typename Archiver> + void serialize(Archiver& ar, const unsigned int /*version*/) + { + ar & weight; + } +}; + +/**************************************************************************** + * Algorithm Tests * + ****************************************************************************/ +template <typename Graph> +void test_directed_sequential_algorithms(const Graph& g) +{ } + +template <typename Graph> +void test_undirected_sequential_algorithms(const Graph& g) +{ + std::vector<unsigned int> componentS(num_vertices(g)); + typedef iterator_property_map< + std::vector<unsigned int>::iterator, + typename property_map<Graph, vertex_index_t>::type> + ComponentMap; + ComponentMap component(componentS.begin(), get(vertex_index, g)); + + time_type start = get_time(); + unsigned int num_components = connected_components(g, component); + time_type end = get_time(); + + std::cerr << " Sequential connected Components time = " + << print_time(end - start) << " seconds.\n" + << " " << num_components << " components identified\n"; +} + +template <typename Graph, typename EdgeWeightMap> +void test_directed_csr_only_algorithms(const Graph& g, EdgeWeightMap weight, + typename graph_traits<Graph>::vertices_size_type num_sources, + typename property_traits<EdgeWeightMap>::value_type C) +{ + typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor; + typedef typename graph_traits<Graph>::vertex_iterator vertex_iterator; + typedef typename graph_traits<Graph>::vertices_size_type vertices_size_type; + typedef typename graph_traits<Graph>::edges_size_type edges_size_type; + + typedef typename boost::graph::parallel::process_group_type<Graph>::type + process_group_type; + + process_group_type pg = process_group(g); + typename process_group_type::process_id_type id = process_id(pg); + typename process_group_type::process_size_type p = num_processes(pg); + + vertices_size_type n = num_vertices(g); + n = boost::parallel::all_reduce(pg, n, std::plus<vertices_size_type>()); + + edges_size_type m = num_edges(g); + m = boost::parallel::all_reduce(pg, m, std::plus<edges_size_type>()); + + // + // Betweenness Centrality (Approximate) + // + queue<vertex_descriptor> delta_stepping_vertices; + + { + // Distributed Centrality Map + typedef typename property_map<Graph, vertex_index_t>::const_type IndexMap; + typedef iterator_property_map<std::vector<int>::iterator, IndexMap> CentralityMap; + + std::vector<int> centralityS(num_vertices(g), 0); + CentralityMap centrality(centralityS.begin(), get(vertex_index, g)); + + // Calculate number of vertices of degree 0 + vertices_size_type n0 = 0; + BGL_FORALL_VERTICES_T(v, g, Graph) { + if (out_degree(v, g) == 0) n0++; + } + n0 = boost::parallel::all_reduce(pg, n0, std::plus<vertices_size_type>()); + + queue<vertex_descriptor> sources; + + { + assert(num_sources >= p); // Don't feel like adding a special case for num_sources < p + + minstd_rand gen; + uniform_int<vertices_size_type> rand_vertex(0, num_vertices(g) - 1); + std::vector<vertex_descriptor> all_sources, local_sources; + vertices_size_type local_vertices = vertices_size_type(floor((double)num_sources / p)); + local_vertices += (id < (num_sources - (p * local_vertices)) ? 1 : 0); + + while (local_vertices > 0) { + vertex_iterator iter = vertices(g).first; + std::advance(iter, rand_vertex(gen)); + + if (out_degree(*iter, g) != 0 + && std::find(local_sources.begin(), local_sources.end(), *iter) == local_sources.end()) { + local_sources.push_back(*iter); + --local_vertices; + } + } + all_gather(pg, local_sources.begin(), local_sources.end(), all_sources); + std::sort(all_sources.begin(), all_sources.end()); + for (typename std::vector<vertex_descriptor>::iterator iter = all_sources.begin(); + iter != all_sources.end(); ++iter) { + sources.push(*iter); + delta_stepping_vertices.push(*iter); + } + } + + // NOTE: The delta below assumes uniform edge weight distribution + time_type start = get_time(); + brandes_betweenness_centrality(g, buffer(sources).weight_map(weight). + centrality_map(centrality).lookahead((m / n) * (C / 2))); + time_type end = get_time(); + + edges_size_type exactTEPs = edges_size_type(floor(7 * n* (n - n0) / (end - start))); + + if (id == 0) + std::cerr << " Betweenness Centrality Approximate (" << num_sources << " sources) = " + << print_time(end - start) << " (" << exactTEPs << " TEPs)\n"; + } + + // + // Delta stepping performance (to compare to SSSP inside BC + // + if (false) { + typedef typename property_map<Graph, vertex_index_t>::const_type IndexMap; + typedef iterator_property_map<std::vector<int>::iterator, IndexMap> DistanceMap; + + std::vector<int> distanceS(num_vertices(g), 0); + DistanceMap distance(distanceS.begin(), get(vertex_index, g)); + + while(!delta_stepping_vertices.empty()) { + + time_type start = get_time(); + delta_stepping_shortest_paths(g, delta_stepping_vertices.top(), dummy_property_map(), + distance, weight); + time_type end = get_time(); + + delta_stepping_vertices.pop(); + distance.reset(); + + if (id == 0) + std::cerr << " Delta-stepping shortest paths = " << print_time(end - start) + << std::endl; + } + } + +} + +template <typename Graph> +void test_directed_algorithms(const Graph& g) +{ +} + +template <typename Graph> +void test_undirected_algorithms(const Graph& g) +{ + typedef typename boost::graph::parallel::process_group_type<Graph>::type + process_group_type; + + process_group_type pg = process_group(g); + typename process_group_type::process_id_type id = process_id(pg); + typename process_group_type::process_size_type p = num_processes(pg); + + + // Connected Components + std::vector<unsigned int> local_components_vec(num_vertices(g)); + typedef iterator_property_map< + std::vector<unsigned int>::iterator, + typename property_map<Graph, vertex_index_t>::type> + ComponentMap; + ComponentMap component(local_components_vec.begin(), get(vertex_index, g)); + + int num_components; + + time_type start = get_time(); + num_components = connected_components(g, component); + time_type end = get_time(); + if (id == 0) + std::cerr << " Connected Components time = " << print_time(end - start) + << " seconds.\n" + << " " << num_components << " components identified\n"; + + start = get_time(); + num_components = boost::graph::distributed::connected_components_ps(g, component); + end = get_time(); + if (id == 0) + std::cerr << " Connected Components (parallel search) time = " + << print_time(end - start) << " seconds.\n" + << " " << num_components << " components identified\n"; +} + +/**************************************************************************** + * Graph Type Tests * + ****************************************************************************/ + +// TODO: Re-seed PRNG before sequential tests to get the same graph as the +// distributed case? + +// +// Compressed Sparse Row +// + +// R-MAT +template <typename ProcessGroup, typename RandomGenerator, typename Distribution> +void test_csr(const ProcessGroup& pg, RandomGenerator& gen, Distribution& distrib, + bool sequential_tests, size_t N, size_t M, size_t C, + double a, double b, double c, double d, size_t num_sources, + rmat_edge_distribution_tag) +{ + if (process_id(pg) == 0) + std::cerr << " R-MAT\n"; + + typedef compressed_sparse_row_graph<directedS, no_property, WeightedEdge, no_property, + distributedS<mpi_process_group> > Graph; + + Graph g(sorted_rmat_iterator<RandomGenerator, Graph>(gen, N, M, a, b, c, d), + sorted_rmat_iterator<RandomGenerator, Graph>(), + make_generator_iterator(gen, uniform_int<int>(1, C)), + N, pg, distrib); + + test_directed_algorithms(g); + test_directed_csr_only_algorithms(g, get(&WeightedEdge::weight, g), num_sources, C); + + if (sequential_tests && process_id(pg) == 0) { + typedef compressed_sparse_row_graph<directedS, no_property, WeightedEdge> + seqGraph; + + seqGraph sg(edges_are_sorted, + sorted_rmat_iterator<RandomGenerator, seqGraph>(gen, N, M, a, b, c, d), + sorted_rmat_iterator<RandomGenerator, seqGraph>(), + make_generator_iterator(gen, uniform_int<int>(1, C)), + N); + + test_directed_sequential_algorithms(sg); + } +} + +// R-MAT with unique edges +template <typename ProcessGroup, typename RandomGenerator, typename Distribution> +void test_csr(const ProcessGroup& pg, RandomGenerator& gen, Distribution& distrib, + bool sequential_tests, size_t N, size_t M, size_t C, + double a, double b, double c, double d, size_t num_sources, + rmat_unique_edge_distribution_tag) +{ + if (process_id(pg) == 0) + std::cerr << " R-MAT - unique\n"; + + typedef compressed_sparse_row_graph<directedS, no_property, WeightedEdge, no_property, + distributedS<mpi_process_group> > Graph; + + // Last boolean parameter makes R-MAT bidirectional + Graph g(sorted_unique_rmat_iterator<RandomGenerator, Graph>(gen, N, M, a, b, c, d), + sorted_unique_rmat_iterator<RandomGenerator, Graph>(), + make_generator_iterator(gen, uniform_int<int>(1, C)), + N, pg, distrib); + + test_directed_algorithms(g); + test_directed_csr_only_algorithms(g, get(&WeightedEdge::weight, g), num_sources, C); + + if (sequential_tests && process_id(pg) == 0) { + typedef compressed_sparse_row_graph<directedS, no_property, WeightedEdge> + seqGraph; + + seqGraph sg(edges_are_sorted, + sorted_unique_rmat_iterator<RandomGenerator, seqGraph>(gen, N, M, a, b, c, d), + sorted_unique_rmat_iterator<RandomGenerator, seqGraph>(), + make_generator_iterator(gen, uniform_int<int>(1, C)), + N); + + test_directed_sequential_algorithms(sg); + } +} + +// Erdos-Renyi +template <typename ProcessGroup, typename RandomGenerator, typename Distribution> +void test_csr(const ProcessGroup& pg, RandomGenerator& gen, Distribution& distrib, + bool sequential_tests, size_t N, size_t M, size_t C, size_t num_sources) +{ + if (process_id(pg) == 0) + std::cerr << " Erdos-Renyi\n"; + + double _p = static_cast<double>(M) / (N*N); + + typedef compressed_sparse_row_graph<directedS, no_property, WeightedEdge, no_property, + distributedS<mpi_process_group> > Graph; + + Graph g(sorted_erdos_renyi_iterator<RandomGenerator, Graph>(gen, N, _p/2), + sorted_erdos_renyi_iterator<RandomGenerator, Graph>(), + make_generator_iterator(gen, uniform_int<int>(1, C)), + N, pg, distrib); + + test_directed_algorithms(g); + test_directed_csr_only_algorithms(g, get(&WeightedEdge::weight, g), num_sources, C); + + if (sequential_tests && process_id(pg) == 0) { + typedef compressed_sparse_row_graph<directedS, no_property, WeightedEdge> + seqGraph; + + seqGraph sg(edges_are_sorted, + sorted_erdos_renyi_iterator<RandomGenerator, seqGraph>(gen, N, _p/2), + sorted_erdos_renyi_iterator<RandomGenerator, seqGraph>(), + make_generator_iterator(gen, uniform_int<int>(1, C)), + N); + + test_directed_sequential_algorithms(sg); + } +} + +// Small World +template <typename ProcessGroup, typename RandomGenerator, typename Distribution> +void test_csr(const ProcessGroup& pg, RandomGenerator& gen, Distribution& distrib, + bool sequential_tests, size_t N, size_t M, size_t C, double p, + size_t num_sources) +{ + if (process_id(pg) == 0) + std::cerr << " Small-World\n"; + + int k = M / N; + + typedef compressed_sparse_row_graph<directedS, no_property, WeightedEdge, no_property, + distributedS<mpi_process_group> > Graph; + + Graph g(small_world_iterator<RandomGenerator, Graph>(gen, N, k, p), + small_world_iterator<RandomGenerator, Graph>(), + make_generator_iterator(gen, uniform_int<int>(1, C)), + N, pg, distrib); + + test_directed_algorithms(g); + test_directed_csr_only_algorithms(g, get(&WeightedEdge::weight, g), num_sources, C); + + if (sequential_tests && process_id(pg) == 0) { + typedef compressed_sparse_row_graph<directedS, no_property, WeightedEdge> + seqGraph; + + seqGraph sg(edges_are_sorted, + small_world_iterator<RandomGenerator, seqGraph>(gen, N, k, p), + small_world_iterator<RandomGenerator, seqGraph>(), + make_generator_iterator(gen, uniform_int<int>(1, C)), + N); + + test_directed_sequential_algorithms(sg); + } +} + +// +// Adjacency List +// + +// R-MAT +template <typename ProcessGroup, typename RandomGenerator, typename Distribution> +void test_adjacency_list(const ProcessGroup& pg, RandomGenerator& gen, Distribution& distrib, + bool sequential_tests, size_t N, size_t M, size_t C, + double a, double b, double c, double d, + rmat_edge_distribution_tag) +{ + if (process_id(pg) == 0) + std::cerr << "R-MAT\n"; + + { + typedef adjacency_list<vecS, distributedS<mpi_process_group, vecS>, + directedS, no_property, WeightedEdge> Graph; + + Graph g(rmat_iterator<RandomGenerator, Graph>(gen, N, M, a, b, c, d), + rmat_iterator<RandomGenerator, Graph>(), + make_generator_iterator(gen, uniform_int<int>(1, C)), + N, pg, distrib); + + test_directed_algorithms(g); + } + + { + typedef adjacency_list<vecS, distributedS<mpi_process_group, vecS>, + undirectedS, no_property, WeightedEdge> Graph; + + Graph g(rmat_iterator<RandomGenerator, Graph>(gen, N, M, a, b, c, d), + rmat_iterator<RandomGenerator, Graph>(), + make_generator_iterator(gen, uniform_int<int>(1, C)), + N, pg, distrib); + + test_undirected_algorithms(g); + } + + if (sequential_tests && process_id(pg) == 0) { + { + typedef adjacency_list<vecS, vecS, directedS, no_property, property<edge_weight_t, int> > + seqGraph; + + seqGraph sg(rmat_iterator<RandomGenerator, seqGraph>(gen, N, M, a, b, c, d), + rmat_iterator<RandomGenerator, seqGraph>(), + make_generator_iterator(gen, uniform_int<int>(1, C)), + N); + + test_directed_sequential_algorithms(sg); + } + + { + typedef adjacency_list<vecS, vecS, undirectedS, no_property, property<edge_weight_t, int> > + seqGraph; + + seqGraph sg(rmat_iterator<RandomGenerator, seqGraph>(gen, N, M, a, b, c, d), + rmat_iterator<RandomGenerator, seqGraph>(), + make_generator_iterator(gen, uniform_int<int>(1, C)), + N); + + test_undirected_sequential_algorithms(sg); + } + } +} + +// R-MAT with unique edges +template <typename ProcessGroup, typename RandomGenerator, typename Distribution> +void test_adjacency_list(const ProcessGroup& pg, RandomGenerator& gen, Distribution& distrib, + bool sequential_tests, size_t N, size_t M, size_t C, + double a, double b, double c, double d, + rmat_unique_edge_distribution_tag) +{ + if (process_id(pg) == 0) + std::cerr << " R-MAT - unique\n"; + + { + typedef adjacency_list<vecS, distributedS<mpi_process_group, vecS>, + directedS, no_property, WeightedEdge> Graph; + + Graph g(sorted_unique_rmat_iterator<RandomGenerator, Graph>(gen, N, M, a, b, c, d), + sorted_unique_rmat_iterator<RandomGenerator, Graph>(), + make_generator_iterator(gen, uniform_int<int>(1, C)), + N, pg, distrib); + + test_directed_algorithms(g); + } + + { + typedef adjacency_list<vecS, distributedS<mpi_process_group, vecS>, + undirectedS, no_property, WeightedEdge> Graph; + + Graph g(sorted_unique_rmat_iterator<RandomGenerator, Graph>(gen, N, M, a, b, c, d), + sorted_unique_rmat_iterator<RandomGenerator, Graph>(), + make_generator_iterator(gen, uniform_int<int>(1, C)), + N, pg, distrib); + + test_undirected_algorithms(g); + } + + if (sequential_tests && process_id(pg) == 0) { + { + typedef adjacency_list<vecS, vecS, directedS, no_property, property<edge_weight_t, int> > + seqGraph; + + seqGraph sg(sorted_unique_rmat_iterator<RandomGenerator, seqGraph>(gen, N, M, a, b, c, d), + sorted_unique_rmat_iterator<RandomGenerator, seqGraph>(), + make_generator_iterator(gen, uniform_int<int>(1, C)), + N); + + test_directed_sequential_algorithms(sg); + } + + { + typedef adjacency_list<vecS, vecS, undirectedS, no_property, property<edge_weight_t, int> > + seqGraph; + + seqGraph sg(sorted_unique_rmat_iterator<RandomGenerator, seqGraph>(gen, N, M, a, b, c, d), + sorted_unique_rmat_iterator<RandomGenerator, seqGraph>(), + make_generator_iterator(gen, uniform_int<int>(1, C)), + N); + + test_undirected_sequential_algorithms(sg); + } + } +} + +// Erdos-Renyi +template <typename ProcessGroup, typename RandomGenerator, typename Distribution> +void test_adjacency_list(const ProcessGroup& pg, RandomGenerator& gen, Distribution& distrib, + bool sequential_tests, size_t N, size_t M, size_t C) +{ + if (process_id(pg) == 0) + std::cerr << " Erdos-Renyi\n"; + + double _p = static_cast<double>(M) / N*N; + + { + typedef adjacency_list<vecS, distributedS<mpi_process_group, vecS>, + directedS, no_property, WeightedEdge> Graph; + + Graph g(erdos_renyi_iterator<RandomGenerator, Graph>(gen, N, _p/2), + erdos_renyi_iterator<RandomGenerator, Graph>(), + make_generator_iterator(gen, uniform_int<int>(1, C)), + N, pg, distrib); + + test_directed_algorithms(g); + } + + { + typedef adjacency_list<vecS, distributedS<mpi_process_group, vecS>, + undirectedS, no_property, WeightedEdge> Graph; + + Graph g(erdos_renyi_iterator<RandomGenerator, Graph>(gen, N, _p/2), + erdos_renyi_iterator<RandomGenerator, Graph>(), + make_generator_iterator(gen, uniform_int<int>(1, C)), + N, pg, distrib); + + test_undirected_algorithms(g); + } + + if (sequential_tests && process_id(pg) == 0) { + { + typedef adjacency_list<vecS, vecS, directedS, no_property, property<edge_weight_t, int> > + seqGraph; + + seqGraph sg(erdos_renyi_iterator<RandomGenerator, seqGraph>(gen, N, _p/2), + erdos_renyi_iterator<RandomGenerator, seqGraph>(), + make_generator_iterator(gen, uniform_int<int>(1, C)), + N); + + test_directed_sequential_algorithms(sg); + } + + { + typedef adjacency_list<vecS, vecS, undirectedS, no_property, property<edge_weight_t, int> > + seqGraph; + + seqGraph sg(erdos_renyi_iterator<RandomGenerator, seqGraph>(gen, N, _p/2), + erdos_renyi_iterator<RandomGenerator, seqGraph>(), + make_generator_iterator(gen, uniform_int<int>(1, C)), + N); + + test_undirected_sequential_algorithms(sg); + } + } +} + +// Small World +template <typename ProcessGroup, typename RandomGenerator, typename Distribution> +void test_adjacency_list(const ProcessGroup& pg, RandomGenerator& gen, Distribution& distrib, + bool sequential_tests, size_t N, size_t M, size_t C, double p) +{ + if (process_id(pg) == 0) + std::cerr << " Small-World\n"; + + int k = M / N; + + { + typedef adjacency_list<vecS, distributedS<mpi_process_group, vecS>, + directedS, no_property, WeightedEdge> Graph; + + Graph g(small_world_iterator<RandomGenerator, Graph>(gen, N, k, p), + small_world_iterator<RandomGenerator, Graph>(), + make_generator_iterator(gen, uniform_int<int>(1, C)), + N, pg, distrib); + + test_directed_algorithms(g); + } + + { + typedef adjacency_list<vecS, distributedS<mpi_process_group, vecS>, + undirectedS, no_property, WeightedEdge> Graph; + + Graph g(small_world_iterator<RandomGenerator, Graph>(gen, N, k, p), + small_world_iterator<RandomGenerator, Graph>(), + make_generator_iterator(gen, uniform_int<int>(1, C)), + N, pg, distrib); + + test_undirected_algorithms(g); + } + + if (sequential_tests && process_id(pg) == 0) { + { + typedef adjacency_list<vecS, vecS, directedS, no_property, property<edge_weight_t, int> > + seqGraph; + + seqGraph sg(small_world_iterator<RandomGenerator, seqGraph>(gen, N, k, p), + small_world_iterator<RandomGenerator, seqGraph>(), + make_generator_iterator(gen, uniform_int<int>(1, C)), + N); + + test_directed_sequential_algorithms(sg); + } + + { + typedef adjacency_list<vecS, vecS, undirectedS, no_property, property<edge_weight_t, int> > + seqGraph; + + seqGraph sg(small_world_iterator<RandomGenerator, seqGraph>(gen, N, k, p), + small_world_iterator<RandomGenerator, seqGraph>(), + make_generator_iterator(gen, uniform_int<int>(1, C)), + N); + + test_undirected_sequential_algorithms(sg); + } + } +} + +void usage() +{ + std::cerr << "Algorithm Performance Test\n" + << "Usage : algorithm_performance [options]\n\n" + << "Options are:\n" + << "\t--vertices v\t\t\tNumber of vertices in the graph\n" + << "\t--edges v\t\t\tNumber of edges in the graph\n" + << "\t--seed s\t\t\tSeed for synchronized random number generator\n" + << "\t--max-weight miw\t\tMaximum integer edge weight\n" + << "\t--rewire-probability\t\tRewire-probabitility (p) for small-world graphs\n" + << "\t--dot\t\t\t\tEmit a dot file containing the graph\n" + << "\t--verify\t\t\tVerify result\n" + << "\t--degree-dist\t\t\tOutput degree distribution of graph\n" + << "\t--sequential-graph\t\tRun sequential graph tests\n" + << "\t--erdos-renyi\t\t\tRun tests on Erdos-Renyi graphs\n" + << "\t--small-world\t\t\tRun tests on Small World graphs\n" + << "\t--rmat\t\t\t\tRun tests on R-MAT graphs\n" + << "\t--rmat-unique\t\t\tRun tests on R-MAT graphs with no duplicate edges\n" + << "\t--csr <bool>\t\t\tRun tests using CSR graphs\n" + << "\t--adjacency-list <bool>\t\tRun tests using Adjacency List graphs\n"; +} + + +int test_main(int argc, char* argv[]) +{ + mpi::environment env(argc, argv); + + rand48 gen; + + // Default args + size_t n = 100, + m = 8*n, + c = 100, + num_sources = 32, + num_headers = 16 * 1024, + batch_buffer_size = 1024 * 1024; + uint64_t seed = 1; + bool emit_dot_file = false, + verify = false, + sequential_graph = false, + show_degree_dist = false, + erdos_renyi = false, + small_world = false, + rmat = false, + rmat_unique = false, + csr = false, + adj_list = false; + double p = 0.1, + rmat_a = 0.5, + rmat_b = 0.25, + rmat_c = 0.1, + rmat_d = 0.15; + + // Parse args + for (int i = 1; i < argc; ++i) { + std::string arg = argv[i]; + + if (arg == "--vertices") + n = boost::lexical_cast<size_t>( argv[i+1] ); + + if (arg == "--seed") + seed = boost::lexical_cast<uint64_t>( argv[i+1] ); + + if (arg == "--edges") + m = boost::lexical_cast<size_t>( argv[i+1] ); + + if (arg == "--max-weight") + c = boost::lexical_cast<int>( argv[i+1] ); + + if (arg == "--batch-buffer-size") { + batch_buffer_size = boost::lexical_cast<size_t>( argv[i+1] ); + num_headers = batch_buffer_size / 16; + num_headers = num_headers > 0 ? num_headers : 1; + } + + if (arg == "--rewire-probability") + p = boost::lexical_cast<double>( argv[i+1] ); + + if (arg == "--num-sources") + num_sources = boost::lexical_cast<size_t>( argv[i + 1] ); + + if (arg == "--erdos-renyi") + erdos_renyi = true; + + if (arg == "--small-world") + small_world = true; + + if (arg == "--rmat") + rmat = true; + + if (arg == "--rmat-unique") + rmat_unique = true; + + if (arg == "--dot") + emit_dot_file = true; + + if (arg == "--verify") + verify = true; + + if (arg == "--degree-dist") + show_degree_dist = true; + + if (arg == "--sequential-graph") + sequential_graph = true; + + if (arg == "--csr") + csr = std::string(argv[i+1]) == "true"; + + if (arg == "--adjacency-list") + adj_list = std::string(argv[i+1]) == "true"; + } + + mpi_process_group pg(num_headers, batch_buffer_size); + + if (argc == 1) { + if (process_id(pg) == 0) + usage(); + exit(-1); + } + + gen.seed(seed); + + parallel::variant_distribution<mpi_process_group> distrib + = parallel::block(pg, n); + + if (csr) { + if (process_id(pg) == 0) + std::cerr << "CSR Graph Tests\n"; + + if (erdos_renyi) + test_csr(pg, gen, distrib, sequential_graph, n, m, c, num_sources); + if (small_world) + test_csr(pg, gen, distrib, sequential_graph, n, m, c, p, num_sources); + if (rmat) + test_csr(pg, gen, distrib, sequential_graph, n, m, c, + rmat_a, rmat_b, rmat_c, rmat_d, num_sources, rmat_edge_distribution_tag()); + if (rmat_unique) + test_csr(pg, gen, distrib, sequential_graph, n, m, c, + rmat_a, rmat_b, rmat_c, rmat_d, num_sources, rmat_unique_edge_distribution_tag()); + } + + gen.seed(seed); // DEBUG + + if (adj_list) { + if (process_id(pg) == 0) + std::cerr << "Adjacency List Graph Tests\n"; + + if (erdos_renyi) + test_adjacency_list(pg, gen, distrib, sequential_graph, n, m, c); + if (small_world) + test_adjacency_list(pg, gen, distrib, sequential_graph, n, m, c, p); + if (rmat) + test_adjacency_list(pg, gen, distrib, sequential_graph, n, m, c, + rmat_a, rmat_b, rmat_c, rmat_d, rmat_edge_distribution_tag()); + if (rmat_unique) + test_adjacency_list(pg, gen, distrib, sequential_graph, n, m, c, + rmat_a, rmat_b, rmat_c, rmat_d, rmat_unique_edge_distribution_tag()); + } + + return 0; +} diff --git a/src/boost/libs/graph_parallel/test/distributed_adjacency_list_test.cpp b/src/boost/libs/graph_parallel/test/distributed_adjacency_list_test.cpp new file mode 100644 index 000000000..cc7ce8cf5 --- /dev/null +++ b/src/boost/libs/graph_parallel/test/distributed_adjacency_list_test.cpp @@ -0,0 +1,284 @@ +// Copyright (C) 2004-2008 The Trustees of Indiana University. + +// 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) + +// Authors: Douglas Gregor +// Andrew Lumsdaine + +#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/graph/distributed/local_subgraph.hpp> +#include <boost/graph/parallel/distribution.hpp> +#include <iostream> +#include <cassert> +#include <boost/test/minimal.hpp> + +#ifdef BOOST_NO_EXCEPTIONS +void +boost::throw_exception(std::exception const& ex) +{ + std::cout << ex.what() << std::endl; + abort(); +} +#endif + +using namespace boost; +using boost::graph::distributed::mpi_process_group; + +template<typename Graph> +struct never +{ + typedef typename graph_traits<Graph>::edge_descriptor argument_type; + typedef bool result_type; + + result_type operator()(argument_type) { return false; } +}; + +int test_main(int argc, char** argv) +{ + boost::mpi::environment env(argc, argv); + + mpi_process_group pg; + parallel::block dist(pg, 20); + + typedef adjacency_list<listS, distributedS<mpi_process_group, vecS>, + bidirectionalS> Graph1; + typedef adjacency_list<listS, distributedS<mpi_process_group, vecS>, + directedS> Graph2; + typedef adjacency_list<listS, distributedS<mpi_process_group, vecS>, + undirectedS> Graph3; + + if (num_processes(pg) > 20) return -1; + + if (process_id(pg) == 0) std::cout << "Graph 1------------------\n"; + + std::cout << "Processor #" << process_id(pg) << ": " + << dist.block_size(20) << " vertices." << std::endl; + { + Graph1 g1(20); + + // if (process_id(pg) == num_processes(pg)() - 1) + // add_vertex(g1); + + graph_traits<Graph1>::vertex_iterator v, v_end; + int counter = 0; + for (boost::tie(v, v_end) = vertices(g1); v != v_end; ++v) { + std::cout << "Processor #" << process_id(pg) << ": vertex " << ++counter + << std::endl; + + out_edges(*v, g1); + out_degree(*v, g1); + in_edges(*v, g1); + in_degree(*v, g1); + + graph_traits<Graph1>::vertex_descriptor other = *v; + other.owner = (other.owner + 1) % num_processes(pg); + other.local = 0; + add_edge(*v, other, g1); + + std::cout << "Adding edge from processor " << process_id(pg) + << " to processor " << other.owner << std::endl; + } + + synchronize(g1); + assert((std::size_t)std::distance(edges(g1).first, edges(g1).second) == num_vertices(g1)); + + if (num_vertices(g1) >= 2) { + graph_traits<Graph1>::vertex_iterator vi = vertices(g1).first; + graph_traits<Graph1>::vertex_descriptor u = *vi++; + graph_traits<Graph1>::vertex_descriptor v = *vi++; + add_edge(u, v, g1); + assert(out_degree(u, g1) == 2); + assert(in_degree(v, g1) == 1); + } + + int prior_processor = (process_id(pg) + num_processes(pg) - 1) + % num_processes(pg); + const int n = 20; + std::size_t vertices_in_prior = (n / num_processes(pg)) + + (n % num_processes(pg) > prior_processor? 1 : 0); + + graph_traits<Graph1>::vertex_descriptor u = *vertices(g1).first; + if (in_degree(u, g1) != vertices_in_prior) { + std::cout << "Processor #" << process_id(pg) << ": " << in_degree(u, g1) + << " vs. " << vertices_in_prior << std::endl; + } + assert(in_degree(u, g1) == vertices_in_prior); + std::cout << "Processor #" << process_id(pg) << ": " << num_edges(g1) + << " edges.\n"; + + local_subgraph<Graph1> local_g1(g1); + edges(local_g1); + vertices(local_g1); + if (num_vertices(local_g1) > 0) { + out_edges(*vertices(local_g1).first, local_g1); + in_edges(*vertices(local_g1).first, local_g1); + adjacent_vertices(*vertices(local_g1).first, local_g1); + if (false) { + remove_out_edge_if(*vertices(g1).first, never<Graph1>(), g1); + remove_in_edge_if(*vertices(g1).first, never<Graph1>(), g1); + clear_out_edges(*vertices(g1).first, g1); + clear_in_edges(*vertices(g1).first, g1); + clear_vertex(*vertices(g1).first, g1); + remove_vertex(*vertices(g1).first, g1); + } + } + remove_edge_if(never<Graph1>(), g1); + } + + + if (process_id(pg) == 0) std::cout << "Graph 2------------------\n"; + + { + Graph2 g2(20); + + if (process_id(pg) == num_processes(pg) - 1) + add_vertex(g2); + + graph_traits<Graph2>::vertex_iterator v, v_end; + int counter = 0; + for (boost::tie(v, v_end) = vertices(g2); v != v_end; ++v) { + std::cout << "Processor #" << process_id(pg) << ": vertex " << ++counter + << std::endl; + + out_edges(*v, g2); + } + + synchronize(g2); + + if (num_vertices(g2) >= 2) { + graph_traits<Graph2>::vertex_iterator vi = vertices(g2).first; + graph_traits<Graph2>::vertex_descriptor u = *vi++; + graph_traits<Graph2>::vertex_descriptor v = *vi++; + add_edge(u, v, g2); + assert(out_degree(u, g2) == 1); + assert(*adjacent_vertices(u, g2).first == v); + std::cout << "Processor #" << process_id(pg) << ": " << num_edges(g2) + << " edges.\n"; + assert(std::distance(edges(g2).first, edges(g2).second) == 1); + + } + synchronize(g2); + + local_subgraph<Graph2> local_g2(g2); + edges(local_g2); + vertices(local_g2); + if (num_vertices(local_g2) > 0) { + out_edges(*vertices(local_g2).first, local_g2); + adjacent_vertices(*vertices(local_g2).first, local_g2); + remove_out_edge_if(*vertices(g2).first, never<Graph2>(), g2); + clear_out_edges(*vertices(g2).first, g2); + remove_vertex(*vertices(g2).first, g2); + } + remove_edge_if(never<Graph2>(), g2); + } + + if (process_id(pg) == 0) std::cout << "Graph 3------------------\n"; + + { + Graph3 g3(20); + + // if (process_id(pg) == num_processes(pg) - 1) + // add_vertex(g3); + + graph_traits<Graph3>::vertex_iterator v, v_end; + int counter = 0; + for (boost::tie(v, v_end) = vertices(g3); v != v_end; ++v) { + std::cout << "Processor #" << process_id(pg) << ": vertex " << ++counter + << std::endl; + + out_edges(*v, g3); + out_degree(*v, g3); + in_edges(*v, g3); + in_degree(*v, g3); + } + + graph_traits<Graph3>::vertices_size_type added_edges = 0; + if (num_vertices(g3) >= 2) { + graph_traits<Graph3>::vertex_iterator vi = vertices(g3).first; + graph_traits<Graph3>::vertex_descriptor u = *vi++; + graph_traits<Graph3>::vertex_descriptor v = *vi++; + add_edge(u, v, g3); ++added_edges; + assert(out_degree(u, g3) == 1); + assert(in_degree(u, g3) == 1); + graph_traits<Graph3>::edge_descriptor e = *out_edges(u, g3).first; + assert(source(e, g3) == u); + assert(target(e, g3) == v); + e = *in_edges(u, g3).first; + assert(source(e, g3) == v); + assert(target(e, g3) == u); + assert(out_degree(v, g3) == 1); + assert(in_degree(v, g3) == 1); + e = *out_edges(v, g3).first; + assert(source(e, g3) == v); + assert(target(e, g3) == u); + e = *in_edges(v, g3).first; + assert(source(e, g3) == u); + assert(target(e, g3) == v); + + assert(*adjacent_vertices(u, g3).first == v); + assert(*adjacent_vertices(v, g3).first == u); + std::cout << "Processor #" << process_id(pg) << ": " << num_edges(g3) + << " edges.\n"; + } + + // Add some remote edges + for (boost::tie(v, v_end) = vertices(g3); v != v_end; ++v) { + graph_traits<Graph1>::vertex_descriptor other = *v; + other.owner = (other.owner + 1) % num_processes(pg); + other.local = 0; + add_edge(*v, other, g3); ++added_edges; + + std::cout << "Adding edge from processor " << process_id(pg) + << " to processor " << other.owner << std::endl; + } + + synchronize(g3); + assert(std::distance(edges(g3).first, edges(g3).second) == (ptrdiff_t)added_edges); + assert(num_edges(g3) == added_edges); + + // Verify the remote edges + if (num_vertices(g3) >= 2) { + graph_traits<Graph3>::vertex_iterator vi = vertices(g3).first; + graph_traits<Graph3>::vertex_descriptor u = *vi++; + + int prior_processor = (process_id(pg) + num_processes(pg) - 1) + % num_processes(pg); + const int n = 20; + graph_traits<Graph3>::vertices_size_type vertices_in_prior = (n / num_processes(pg)) + + (n % num_processes(pg) > prior_processor? 1 : 0); + if (in_degree(u, g3) != vertices_in_prior + 2) { + std::cerr << "#" << process_id(pg) << ": " << in_degree(u, g3) + << " != " << vertices_in_prior + 2 << std::endl; + } + + assert(in_degree(u, g3) == vertices_in_prior + 2); + assert(out_degree(u, g3) == vertices_in_prior + 2); + } + + local_subgraph<Graph3> local_g3(g3); + edges(local_g3); + vertices(local_g3); + if (num_vertices(local_g3) > 0) { + out_edges(*vertices(local_g3).first, local_g3); + in_edges(*vertices(local_g3).first, local_g3); + adjacent_vertices(*vertices(local_g3).first, local_g3); + remove_out_edge_if(*vertices(g3).first, never<Graph3>(), g3); + remove_in_edge_if(*vertices(g3).first, never<Graph3>(), g3); + if (false) { + // Removing an edge from two processes concurrently is not yet + // supported. + clear_vertex(*vertices(g3).first, g3); + remove_vertex(*vertices(g3).first, g3); + } + } + remove_edge_if(never<Graph3>(), g3); + } + + return 0; +} diff --git a/src/boost/libs/graph_parallel/test/distributed_betweenness_centrality_test.cpp b/src/boost/libs/graph_parallel/test/distributed_betweenness_centrality_test.cpp new file mode 100644 index 000000000..90c931432 --- /dev/null +++ b/src/boost/libs/graph_parallel/test/distributed_betweenness_centrality_test.cpp @@ -0,0 +1,295 @@ +// Copyright (C) 2006 The Trustees of Indiana University. + +// 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) + +// Authors: Nick Edmonds +// Andrew Lumsdaine + +#include <boost/graph/use_mpi.hpp> + +#define CSR + +#ifdef CSR +# include <boost/graph/distributed/compressed_sparse_row_graph.hpp> +#else +# include <boost/graph/distributed/adjacency_list.hpp> +#endif + +#include <boost/config.hpp> +#include <boost/throw_exception.hpp> +#include <boost/graph/distributed/mpi_process_group.hpp> +#include <boost/graph/distributed/concepts.hpp> +#include <boost/graph/erdos_renyi_generator.hpp> +#include <boost/graph/distributed/betweenness_centrality.hpp> +#include <boost/random/linear_congruential.hpp> +#include <boost/graph/graphviz.hpp> +#include <boost/property_map/vector_property_map.hpp> +#include <boost/test/minimal.hpp> + +#ifdef BOOST_NO_EXCEPTIONS +void +boost::throw_exception(std::exception const& ex) +{ + std::cout << ex.what() << std::endl; + abort(); +} +#endif + +/**************************************************************************** + * Edge weight generator iterator * + ****************************************************************************/ +template<typename F, typename RandomGenerator> +class generator_iterator +{ +public: + typedef std::input_iterator_tag iterator_category; + typedef typename F::result_type value_type; + typedef const value_type& reference; + typedef const value_type* pointer; + typedef void difference_type; + + explicit + generator_iterator(RandomGenerator& gen, const F& f = F()) + : f(f), gen(&gen) + { + value = this->f(gen); + } + + reference operator*() const { return value; } + pointer operator->() const { return &value; } + + generator_iterator& operator++() + { + value = f(*gen); + return *this; + } + + generator_iterator operator++(int) + { + generator_iterator temp(*this); + ++(*this); + return temp; + } + + bool operator==(const generator_iterator& other) const + { return f == other.f; } + + bool operator!=(const generator_iterator& other) const + { return !(*this == other); } + +private: + F f; + RandomGenerator* gen; + value_type value; +}; + +template<typename F, typename RandomGenerator> +inline generator_iterator<F, RandomGenerator> +make_generator_iterator( RandomGenerator& gen, const F& f) +{ return generator_iterator<F, RandomGenerator>(gen, f); } + +using namespace boost; +using boost::graph::distributed::mpi_process_group; + +typedef int weight_type; + +struct WeightedEdge { + WeightedEdge(weight_type weight = 0) : weight(weight) { } + + weight_type weight; + + template<typename Archiver> + void serialize(Archiver& ar, const unsigned int /*version*/) + { + ar & weight; + } +}; + +int test_main(int argc, char* argv[]) +{ + mpi::environment env(argc, argv); + +#ifdef CSR + typedef compressed_sparse_row_graph<directedS, no_property, WeightedEdge, + no_property, distributedS<mpi_process_group> > + Graph; + typedef compressed_sparse_row_graph<directedS, no_property, WeightedEdge> + seqGraph; +#else + typedef adjacency_list<vecS, + distributedS<mpi_process_group, vecS>, + directedS, + no_property, + property<edge_weight_t, int> > Graph; + + typedef adjacency_list<vecS, vecS, directedS, no_property, + property<edge_weight_t, int> > seqGraph; +#endif + + + typedef sorted_erdos_renyi_iterator<minstd_rand, Graph> ERIter; + + int n = 100; + double prob = 0.1; + int C = 3; + + minstd_rand gen; + + gen.seed(1); + + // NOTE: Weighted betweenness centrality only works with non-zero edge weights + + // Build graphs + Graph g(edges_are_sorted, ERIter(gen, n, prob), ERIter(), + make_generator_iterator(gen, uniform_int<int>(1, C)), + n); + + gen.seed(1); // Re-seed PRNG so we get the same graph + + seqGraph sg( +#ifdef CSR + edges_are_sorted, +#endif + ERIter(gen, n, prob), ERIter(), + make_generator_iterator(gen, uniform_int<int>(1, C)), + n); + + // Test Betweenness Centrality + typedef property_map<Graph, vertex_index_t>::const_type IndexMap; + typedef iterator_property_map<std::vector<int>::iterator, IndexMap> + CentralityMap; + + std::vector<int> centralityS(num_vertices(g), 0); + CentralityMap centrality(centralityS.begin(), get(vertex_index, g)); + + brandes_betweenness_centrality(g, centrality); + + std::vector<int> weightedCentralityS(num_vertices(g), 0); + CentralityMap weightedCentrality(weightedCentralityS.begin(), get(vertex_index, g)); + + brandes_betweenness_centrality(g, centrality_map(weightedCentrality). +#ifdef CSR + weight_map(get(&WeightedEdge::weight, g))); +#else + weight_map(get(edge_weight, g))); +#endif + + int g_cpd = central_point_dominance(g, centrality); + + // + // Non-distributed (embarassingly parallel) Betweenness Centrality + // + typedef boost::graph::parallel::process_group_type<Graph>::type + process_group_type; + + process_group_type pg = process_group(g); + + process_group_type::process_id_type id = process_id(pg); + process_group_type::process_size_type p = num_processes(pg); + + typedef property_map<seqGraph, vertex_index_t>::const_type seqIndexMap; + typedef iterator_property_map<std::vector<int>::iterator, seqIndexMap> seqCentralityMap; + + std::vector<int> nonDistributedCentralityS(num_vertices(sg), 0); + seqCentralityMap nonDistributedCentrality(nonDistributedCentralityS.begin(), get(vertex_index, sg)); + + std::vector<int> nonDistributedWeightedCentralityS(num_vertices(sg), 0); + seqCentralityMap nonDistributedWeightedCentrality(nonDistributedWeightedCentralityS.begin(), + get(vertex_index, sg)); + + non_distributed_brandes_betweenness_centrality(pg, sg, nonDistributedCentrality); + + non_distributed_brandes_betweenness_centrality(pg, sg, + centrality_map(nonDistributedWeightedCentrality). +#ifdef CSR + weight_map(get(&WeightedEdge::weight, sg))); +#else + weight_map(get(edge_weight, sg))); +#endif + + // + // Verify + // + std::vector<int> seqCentralityS(num_vertices(sg), 0); + seqCentralityMap seqCentrality(seqCentralityS.begin(), get(vertex_index, sg)); + + std::vector<int> seqWeightedCentralityS(num_vertices(sg), 0); + seqCentralityMap seqWeightedCentrality(seqWeightedCentralityS.begin(), get(vertex_index, sg)); + + brandes_betweenness_centrality(sg, seqCentrality); + + brandes_betweenness_centrality(sg, centrality_map(seqWeightedCentrality). +#ifdef CSR + weight_map(get(&WeightedEdge::weight, sg))); +#else + weight_map(get(edge_weight, sg))); +#endif + + int sg_cpd = central_point_dominance(sg, seqCentrality); + + // Verify exact betweenness centrality + // + // We're cheating when we map vertices in g to vertices in sg + // since we know that g is using the block distribution here + typedef property_map<Graph, vertex_owner_t>::const_type OwnerMap; + typedef property_map<Graph, vertex_local_t>::const_type LocalMap; + + OwnerMap owner = get(vertex_owner, g); + LocalMap local = get(vertex_local, g); + + bool passed = true; + + { + typedef graph_traits<Graph>::vertex_iterator vertex_iterator; + vertex_iterator v, v_end; + + for (boost::tie(v, v_end) = vertices(g); v != v_end; ++v) { + if (get(centrality, *v) != seqCentralityS[(n/p) * get(owner, *v) + get(local, *v)]) { + std::cerr << " " << id << ": Error - centrality of " << get(local, *v) << "@" << get(owner, *v) + << " does not match the sequential result (" << get(centrality, *v) << " vs. " + << seqCentralityS[(n/p) * get(owner, *v) + get(local, *v)] << ")\n"; + passed = false; + } + + if (get(weightedCentrality, *v) != seqWeightedCentralityS[(n/p) * get(owner, *v) + get(local, *v)]) { + std::cerr << " " << id << ": Error - weighted centrality of " << get(local, *v) << "@" << get(owner, *v) + << " does not match the sequential result (" << get(weightedCentrality, *v) << " vs. " + << seqWeightedCentralityS[(n/p) * get(owner, *v) + get(local, *v)] << ")\n"; + passed = false; + } + } + } + + if (id == 0) { + typedef graph_traits<seqGraph>::vertex_iterator vertex_iterator; + vertex_iterator v, v_end; + + for (boost::tie(v, v_end) = vertices(sg); v != v_end; ++v) { + if (get(seqCentrality, *v) != get(nonDistributedCentrality, *v)) { + std::cerr << " " << id << ": Error - non-distributed centrality of " << *v + << " does not match the sequential result (" << get(nonDistributedCentrality, *v) + << " vs. " << get(seqCentrality, *v) << ")\n"; + passed = false; + } + + if (get(seqWeightedCentrality, *v) != get(nonDistributedWeightedCentrality, *v)) { + std::cerr << " " << id << ": Error - non-distributed weighted centrality of " << *v + << " does not match the sequential result (" << get(nonDistributedWeightedCentrality, *v) + << " vs. " << get(seqCentrality, *v) << ")\n"; + passed = false; + } + } + } + + if (g_cpd != sg_cpd) { + passed = false; + std::cerr << "Central point dominance did not match the sequential result\n"; + } + + if (!passed) + MPI_Abort(MPI_COMM_WORLD, -1); + + return 0; +} diff --git a/src/boost/libs/graph_parallel/test/distributed_connected_components_test.cpp b/src/boost/libs/graph_parallel/test/distributed_connected_components_test.cpp new file mode 100644 index 000000000..e630bbb03 --- /dev/null +++ b/src/boost/libs/graph_parallel/test/distributed_connected_components_test.cpp @@ -0,0 +1,204 @@ +// Copyright (C) 2004-2006 The Trustees of Indiana University. + +// 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) + +// Authors: Douglas Gregor +// Andrew Lumsdaine + +#include <boost/graph/use_mpi.hpp> +#include <boost/config.hpp> +#include <boost/throw_exception.hpp> +#include <boost/serialization/vector.hpp> +#include <boost/graph/distributed/adjacency_list.hpp> +#include <boost/graph/connected_components.hpp> +#include <boost/graph/distributed/connected_components_parallel_search.hpp> +#include <boost/graph/random.hpp> +#include <boost/property_map/parallel/distributed_property_map.hpp> +#include <boost/graph/distributed/mpi_process_group.hpp> +#include <boost/graph/parallel/distribution.hpp> +#include <boost/graph/erdos_renyi_generator.hpp> +#include <boost/graph/distributed/graphviz.hpp> +#include <iostream> +#include <cstdlib> +#include <iomanip> +#include <boost/random.hpp> +#include <boost/test/minimal.hpp> + +#include <boost/graph/distributed/compressed_sparse_row_graph.hpp> +#include <boost/graph/rmat_graph_generator.hpp> + +#ifdef BOOST_NO_EXCEPTIONS +void +boost::throw_exception(std::exception const& ex) +{ + std::cout << ex.what() << std::endl; + abort(); +} +#endif + +using namespace boost; +using boost::graph::distributed::mpi_process_group; + +typedef double time_type; + +inline time_type get_time() +{ + return MPI_Wtime(); +} + +std::string print_time(time_type t) +{ + std::ostringstream out; + out << std::setiosflags(std::ios::fixed) << std::setprecision(2) << t; + return out.str(); +} + +template<typename T> +class map_lt +{ +public: + bool operator()() const { return false; } + bool operator()(T x, T y) const { return (owner(x) < owner(y) || (owner(x) == owner(y) && local(x) < local(y))); } +}; + +void +test_distributed_connected_components(int n, double _p, bool verify, bool emit_dot_file, int seed, bool parallel_search) +{ +// typedef adjacency_list<listS, +// distributedS<mpi_process_group, vecS>, +// undirectedS> Graph; + + typedef compressed_sparse_row_graph<directedS, no_property, no_property, no_property, + distributedS<mpi_process_group> > Graph; + + minstd_rand gen; + + gen.seed(seed); + + mpi_process_group pg; + parallel::variant_distribution<mpi_process_group> distrib + = parallel::block(pg, n); + + minstd_rand dist_gen; +#if 0 + if (false) { + distrib = parallel::random_distribution(pg, dist_gen, n); + } else if (true) { + distrib = parallel::oned_block_cyclic(pg, 13); + } +#endif + +// Graph g(erdos_renyi_iterator<minstd_rand, Graph>(gen, n, _p/2), +// erdos_renyi_iterator<minstd_rand, Graph>(), +// n, pg, distrib); + + int m = int(n * n * _p/2); + double a = 0.57, b = 0.19, c = 0.19, d = 0.05; + + // Last boolean parameter makes R-MAT bidirectional + Graph g(sorted_unique_rmat_iterator<minstd_rand, Graph>(gen, n, m, a, b, c, d, true), + sorted_unique_rmat_iterator<minstd_rand, Graph>(), + n, pg, distrib); + + synchronize(g); + + std::vector<int> local_components_vec(num_vertices(g)); + typedef iterator_property_map<std::vector<int>::iterator, property_map<Graph, vertex_index_t>::type> ComponentMap; + ComponentMap component(local_components_vec.begin(), get(vertex_index, g)); + + int num_components = 0; + + time_type start = get_time(); + if (parallel_search) { + num_components = connected_components_ps(g, component); + } else { + num_components = connected_components(g, component); + } + time_type end = get_time(); + if (process_id(g.process_group()) == 0) + std::cerr << "Connected Components time = " << print_time(end - start) << " seconds.\n" + << num_components << " components identified\n"; + + if ( verify ) + { + if ( process_id(g.process_group()) == 0 ) + { + component.set_max_ghost_cells(0); + for (int i = 0; i < n; ++i) + get(component, vertex(i, g)); + synchronize(component); + + // Check against the sequential version + typedef adjacency_list<listS, + vecS, + undirectedS, + // Vertex properties + no_property, + // Edge properties + no_property > Graph2; + + gen.seed(seed); + +// Graph2 g2(erdos_renyi_iterator<minstd_rand, Graph>(gen, n, _p/2), +// erdos_renyi_iterator<minstd_rand, Graph>(), +// n); + + Graph2 g2( sorted_unique_rmat_iterator<minstd_rand, Graph>(gen, n, m, a, b, c, d, true), + sorted_unique_rmat_iterator<minstd_rand, Graph>(), + n); + + std::vector<int> component2 (n); + int tmp; + tmp = connected_components(g2, make_iterator_property_map(component2.begin(), get(vertex_index, g2))); + std::cerr << "Verifier found " << tmp << " components" << std::endl; + + // Make sure components and component2 match + std::map<int, int> c2c; + int i; + // This fails if there are more components in 'component' than + // 'component2' because multiple components in 'component' may + // legitimately map to the same component number in 'component2'. + // We can either test the mapping in the opposite direction or + // just assert that the numbers of components found by both + // algorithms is the same + for ( i = 0; i < n; i++ ) + if ( c2c.find( get(component, vertex(i, g)) ) == c2c.end() ) + c2c[get(component, vertex(i, g))] = component2[i]; + else + if ( c2c[get(component, vertex(i, g))] != component2[i] ) + break; + + if ( i < n || num_components != tmp) { + printf("Unable to verify CC result...\n"); + } else + printf("Passed verification... %i connected components\n", + (int)c2c.size()); + } + else + { + synchronize(component); + } + if ( emit_dot_file ) + write_graphviz("cc.dot", g, paint_by_number(component)); + } +} + +int test_main(int argc, char* argv[]) +{ + mpi::environment env(argc, argv); + + if ( argc < 6 ) { + test_distributed_connected_components(10000, 0.001, true, false, 1, false); + test_distributed_connected_components(10000, 0.001, true, false, 1, true); + } + else + test_distributed_connected_components + (atoi(argv[1]), atof(argv[2]), + argv[3]==std::string("true"), argv[4]==std::string("true"), + argc == 6? 1 : atoi(argv[6]), + argv[5]==std::string("true")); + + return 0; +} diff --git a/src/boost/libs/graph_parallel/test/distributed_csr_algorithm_test.cpp b/src/boost/libs/graph_parallel/test/distributed_csr_algorithm_test.cpp new file mode 100644 index 000000000..0653cc912 --- /dev/null +++ b/src/boost/libs/graph_parallel/test/distributed_csr_algorithm_test.cpp @@ -0,0 +1,369 @@ +// Copyright (C) 2006 The Trustees of Indiana University. + +// 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) + +// Authors: Nick Edmonds +// Andrew Lumsdaine + +// A test of the distributed compressed sparse row graph type +#include <boost/graph/use_mpi.hpp> +#include <boost/config.hpp> +#include <boost/throw_exception.hpp> +#include <boost/graph/distributed/compressed_sparse_row_graph.hpp> +#include <boost/graph/distributed/mpi_process_group.hpp> +#include <boost/graph/distributed/concepts.hpp> + +#include <boost/graph/erdos_renyi_generator.hpp> +#include <boost/graph/small_world_generator.hpp> +#include <boost/graph/rmat_graph_generator.hpp> + +#include <boost/graph/breadth_first_search.hpp> +#include <boost/graph/depth_first_search.hpp> +#include <boost/graph/distributed/delta_stepping_shortest_paths.hpp> +#include <boost/graph/dijkstra_shortest_paths.hpp> +#include <boost/graph/distributed/page_rank.hpp> +#include <boost/graph/distributed/boman_et_al_graph_coloring.hpp> +#include <boost/graph/connected_components.hpp> +#include <boost/graph/strong_components.hpp> +#include <boost/graph/distributed/betweenness_centrality.hpp> +#include <boost/graph/distributed/dehne_gotz_min_spanning_tree.hpp> +#include <boost/graph/distributed/st_connected.hpp> + +#if 0 // Contains internal AdjList types not present in CSR graph +# include <boost/graph/distributed/connected_components_parallel_search.hpp> +#endif + +#include <boost/graph/distributed/vertex_list_adaptor.hpp> // Needed for MST + +#include <boost/random/linear_congruential.hpp> +#include <boost/graph/graphviz.hpp> +#include <boost/property_map/vector_property_map.hpp> +#include <boost/test/minimal.hpp> + +#ifdef BOOST_NO_EXCEPTIONS +void +boost::throw_exception(std::exception const& ex) +{ + std::cout << ex.what() << std::endl; + abort(); +} +#endif + + +/**************************************************************************** + * Edge weight generator iterator * + ****************************************************************************/ +template<typename F, typename RandomGenerator> +class generator_iterator +{ +public: + typedef std::input_iterator_tag iterator_category; + typedef typename F::result_type value_type; + typedef const value_type& reference; + typedef const value_type* pointer; + typedef void difference_type; + + explicit + generator_iterator(RandomGenerator& gen, const F& f = F()) + : f(f), gen(&gen) + { + value = this->f(gen); + } + + reference operator*() const { return value; } + pointer operator->() const { return &value; } + + generator_iterator& operator++() + { + value = f(*gen); + return *this; + } + + generator_iterator operator++(int) + { + generator_iterator temp(*this); + ++(*this); + return temp; + } + + bool operator==(const generator_iterator& other) const + { return f == other.f; } + + bool operator!=(const generator_iterator& other) const + { return !(*this == other); } + +private: + F f; + RandomGenerator* gen; + value_type value; +}; + +template<typename F, typename RandomGenerator> +inline generator_iterator<F, RandomGenerator> +make_generator_iterator( RandomGenerator& gen, const F& f) +{ return generator_iterator<F, RandomGenerator>(gen, f); } + + +/**************************************************************************** + * Printing DFS Visitor * + ****************************************************************************/ + +struct printing_dfs_visitor +{ + template<typename Vertex, typename Graph> + void initialize_vertex(Vertex v, const Graph& g) + { + vertex_event("initialize_vertex", v, g); + } + + template<typename Vertex, typename Graph> + void start_vertex(Vertex v, const Graph& g) + { + vertex_event("start_vertex", v, g); + } + + template<typename Vertex, typename Graph> + void discover_vertex(Vertex v, const Graph& g) + { + vertex_event("discover_vertex", v, g); + } + + template<typename Edge, typename Graph> + void examine_edge(Edge e, const Graph& g) + { + edge_event("examine_edge", e, g); + } + + template<typename Edge, typename Graph> + void tree_edge(Edge e, const Graph& g) + { + edge_event("tree_edge", e, g); + } + + template<typename Edge, typename Graph> + void back_edge(Edge e, const Graph& g) + { + edge_event("back_edge", e, g); + } + + template<typename Edge, typename Graph> + void forward_or_cross_edge(Edge e, const Graph& g) + { + edge_event("forward_or_cross_edge", e, g); + } + + template<typename Vertex, typename Graph> + void finish_vertex(Vertex v, const Graph& g) + { + vertex_event("finish_vertex", v, g); + } + +private: + template<typename Vertex, typename Graph> + void vertex_event(const char* name, Vertex v, const Graph& g) + { + std::cerr << "#" << process_id(g.process_group()) << ": " << name << "(" + << get_vertex_name(v, g) << ": " << local(v) << "@" << owner(v) + << ")\n"; + } + + template<typename Edge, typename Graph> + void edge_event(const char* name, Edge e, const Graph& g) + { + std::cerr << "#" << process_id(g.process_group()) << ": " << name << "(" + << get_vertex_name(source(e, g), g) << ": " + << local(source(e, g)) << "@" << owner(source(e, g)) << ", " + << get_vertex_name(target(e, g), g) << ": " + << local(target(e, g)) << "@" << owner(target(e, g)) << ")\n"; + } + +}; + +using namespace boost; +using boost::graph::distributed::mpi_process_group; + +typedef int weight_type; + +struct WeightedEdge { + WeightedEdge(weight_type weight = 0) : weight(weight) { } + + weight_type weight; + + template<typename Archiver> + void serialize(Archiver& ar, const unsigned int /*version*/) + { + ar & weight; + } +}; + +struct VertexProperties { + VertexProperties(int d = 0) + : distance(d) { } + + int distance; + + template<typename Archiver> + void serialize(Archiver& ar, const unsigned int /*version*/) + { + ar & distance; + } +}; + +int test_main(int argc, char* argv[]) +{ + mpi::environment env(argc, argv); + + typedef compressed_sparse_row_graph<directedS, VertexProperties, WeightedEdge, + no_property, distributedS<mpi_process_group> > + Digraph; + + // Make sure we can build graphs using common graph generators + typedef sorted_erdos_renyi_iterator<minstd_rand, Digraph> ERIter; + typedef small_world_iterator<minstd_rand, Digraph> SWIter; + typedef sorted_rmat_iterator<minstd_rand, Digraph> RMATIter; + + typedef graph_traits<Digraph>::edge_descriptor edge_descriptor; + + int n = 40; + int k = 3; + double prob = 0.1; + int C = 10; + double a = 0.5, b = 0.1, c = 0.25, d = 0.15; + int iterations = 50; + int num_colors = n / 10; + int lookahead = C / 10; + + minstd_rand gen; + + // Directed Graphs + Digraph g(ERIter(gen, n, prob), ERIter(), + make_generator_iterator(gen, uniform_int<int>(0, C)), + n); + Digraph g2(SWIter(gen, n, k, prob), SWIter(), n); + Digraph g3(RMATIter(gen, n, size_t(n*n*prob), a, b, c, d), RMATIter(), n); + + // Test BFS + breadth_first_search(g, vertex(0, g), visitor(bfs_visitor<>())); + + // Test SSSP Algorithms + graph::distributed::delta_stepping_shortest_paths(g, + vertex(0, g), + dummy_property_map(), + get(&VertexProperties::distance, g), + get(&WeightedEdge::weight, g)); + + dijkstra_shortest_paths(g, vertex(0, g), + distance_map(get(&VertexProperties::distance, g)). + weight_map(get(&WeightedEdge::weight, g))); + + dijkstra_shortest_paths(g, vertex(0, g), + distance_map(get(&VertexProperties::distance, g)). + weight_map(get(&WeightedEdge::weight, g)). + lookahead(lookahead)); + + // Test PageRank + using boost::graph::n_iterations; + + std::vector<double> ranks(num_vertices(g)); + + page_rank(g, + make_iterator_property_map(ranks.begin(), + get(boost::vertex_index, g)), + n_iterations(iterations), 0.85, vertex(0, g)); + + // Test Graph Coloring + typedef property_map<Digraph, vertex_index_t>::type vertex_index_map; + + std::vector<int> colors_vec(num_vertices(g)); + iterator_property_map<int*, vertex_index_map> color(&colors_vec[0], + get(vertex_index, g)); + + graph::boman_et_al_graph_coloring(g, color, num_colors); + + // Test DFS + // + // DFS requires an undirected graph, currently CSR graphs must be directed +#if 0 + std::vector<vertex_descriptor> parent(num_vertices(g)); + std::vector<vertex_descriptor> explore(num_vertices(g)); + + boost::graph::tsin_depth_first_visit + (g, + vertex(0, g), + printing_dfs_visitor(), + color, + make_iterator_property_map(parent.begin(), get(vertex_index, g)), + make_iterator_property_map(explore.begin(), get(vertex_index, g)), + get(vertex_index, g)); +#endif + + // Test S-T Connected + st_connected(g, vertex(0, g), vertex(1, g), color, get(vertex_owner, g)); + + // Test Connected Components + // + // CC requires an undirected graph, currently CSR graphs must be directed +#if 0 + std::vector<int> local_components_vec(num_vertices(g)); + typedef iterator_property_map<std::vector<int>::iterator, + vertex_index_map> ComponentMap; + ComponentMap component(local_components_vec.begin(), get(vertex_index, g)); + + assert(connected_components(g, component) == + connected_components_ps(g, component)); +#endif + + // Test Betweenness Centrality + // + // Betweenness Centrality is broken at the moment + typedef iterator_property_map<std::vector<int>::iterator, vertex_index_map> + CentralityMap; + + std::vector<int> centralityS(num_vertices(g), 0); + CentralityMap centrality(centralityS.begin(), get(vertex_index, g)); + + brandes_betweenness_centrality(g, centrality); + + // + // Test MST + // + std::vector<edge_descriptor> mst_edges; + + dense_boruvka_minimum_spanning_tree(make_vertex_list_adaptor(g), + get(&WeightedEdge::weight, g), + std::back_inserter(mst_edges)); + + mst_edges.clear(); + merge_local_minimum_spanning_trees(make_vertex_list_adaptor(g), + get(&WeightedEdge::weight, g), + std::back_inserter(mst_edges)); + + mst_edges.clear(); + boruvka_then_merge(make_vertex_list_adaptor(g), + get(&WeightedEdge::weight, g), + std::back_inserter(mst_edges)); + + mst_edges.clear(); + boruvka_mixed_merge(make_vertex_list_adaptor(g), + get(&WeightedEdge::weight, g), + std::back_inserter(mst_edges)); + + // Test Strong Components + // + // Can't build reverse graph of a CSR graph +#if 0 + std::vector<int> local_components_vec(num_vertices(g)); + typedef iterator_property_map<std::vector<int>::iterator, + vertex_index_map> ComponentMap; + ComponentMap component(local_components_vec.begin(), get(vertex_index, g)); + + int num_components = strong_components(g, component); +#endif + + std::ofstream out("dcsr.dot"); + write_graphviz(out, g); + + return 0; +} diff --git a/src/boost/libs/graph_parallel/test/distributed_csr_test.cpp b/src/boost/libs/graph_parallel/test/distributed_csr_test.cpp new file mode 100644 index 000000000..a6833ecbf --- /dev/null +++ b/src/boost/libs/graph_parallel/test/distributed_csr_test.cpp @@ -0,0 +1,103 @@ +// Copyright (C) 2006 The Trustees of Indiana University. + +// 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) + +// Authors: Douglas Gregor +// Andrew Lumsdaine + +// A test of the distributed compressed sparse row graph type +#include <boost/graph/use_mpi.hpp> +#include <boost/config.hpp> +#include <boost/throw_exception.hpp> +#include <boost/serialization/vector.hpp> +#include <boost/graph/distributed/compressed_sparse_row_graph.hpp> +#include <boost/graph/distributed/mpi_process_group.hpp> +#include <boost/graph/distributed/concepts.hpp> +#include <boost/graph/erdos_renyi_generator.hpp> +#include <boost/random/linear_congruential.hpp> +#include <boost/graph/breadth_first_search.hpp> +#include <boost/graph/graphviz.hpp> +#include <boost/property_map/vector_property_map.hpp> +#include <boost/test/minimal.hpp> + +#ifdef BOOST_NO_EXCEPTIONS +void +boost::throw_exception(std::exception const& ex) +{ + std::cout << ex.what() << std::endl; + abort(); +} +#endif + +using namespace boost; +using boost::graph::distributed::mpi_process_group; + +void concept_checks() +{ + typedef compressed_sparse_row_graph<directedS, no_property, no_property, no_property, + distributedS<mpi_process_group> > + Digraph; + typedef graph_traits<Digraph>::vertex_descriptor vertex_descriptor; + typedef graph_traits<Digraph>::edge_descriptor edge_descriptor; + + function_requires< GraphConcept<Digraph> >(); + function_requires< IncidenceGraphConcept<Digraph> >(); + function_requires< AdjacencyGraphConcept<Digraph> >(); + + function_requires< DistributedVertexListGraphConcept<Digraph> >(); + function_requires< DistributedEdgeListGraphConcept<Digraph> >(); + + function_requires< + ReadablePropertyGraphConcept<Digraph, vertex_descriptor, vertex_global_t> + >(); + function_requires< + ReadablePropertyGraphConcept<Digraph, vertex_descriptor, vertex_owner_t> + >(); + function_requires< + ReadablePropertyGraphConcept<Digraph, vertex_descriptor, vertex_local_t> + >(); + function_requires< + ReadablePropertyGraphConcept<Digraph, vertex_descriptor, vertex_index_t> + >(); + + function_requires< + ReadablePropertyGraphConcept<Digraph, edge_descriptor, edge_global_t> + >(); + + // DPG TBD: edge_owner, edge_local property maps + + function_requires< + ReadablePropertyGraphConcept<Digraph, edge_descriptor, edge_index_t> + >(); + + // Check default construction + Digraph g; +} + +int test_main(int argc, char* argv[]) +{ + mpi::environment env(argc, argv); + + concept_checks(); + + typedef compressed_sparse_row_graph<directedS, no_property, no_property, no_property, + distributedS<mpi_process_group> > + Digraph; + + // Build an Erdos-Renyi graph to test with + typedef sorted_erdos_renyi_iterator<minstd_rand, Digraph> ERIter; + + int n = 40; + double prob = 0.1; + + minstd_rand gen; + Digraph g(ERIter(gen, n, prob), ERIter(), n); + + breadth_first_search(g, vertex(0, g), visitor(bfs_visitor<>())); + + std::ofstream out("dcsr.dot"); + write_graphviz(out, g); + return 0; +} diff --git a/src/boost/libs/graph_parallel/test/distributed_dfs_test.cpp b/src/boost/libs/graph_parallel/test/distributed_dfs_test.cpp new file mode 100644 index 000000000..d21491b31 --- /dev/null +++ b/src/boost/libs/graph_parallel/test/distributed_dfs_test.cpp @@ -0,0 +1,167 @@ +//======================================================================= +// Copyright 2001 Jeremy G. Siek, Andrew Lumsdaine, Lie-Quan Lee, +// Copyright 2004 Douglas Gregor +// Copyright (C) 2006-2008 + +// Distributed under 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/serialization/vector.hpp> +#include <boost/graph/depth_first_search.hpp> +#include <boost/graph/distributed/mpi_process_group.hpp> +#include <boost/graph/distributed/adjacency_list.hpp> +#include <boost/test/minimal.hpp> +#include <iostream> + +#ifdef BOOST_NO_EXCEPTIONS +void +boost::throw_exception(std::exception const& ex) +{ + std::cout << ex.what() << std::endl; + abort(); +} +#endif + +using namespace boost; +using boost::graph::distributed::mpi_process_group; + +// Set up the vertex names +enum vertex_id_t { u, v, w, x, y, z, N }; +char vertex_names[] = { 'u', 'v', 'w', 'x', 'y', 'z' }; + +template<typename Vertex, typename Graph> +char get_vertex_name(Vertex v, const Graph& g) +{ + return vertex_names[g.distribution().global(owner(v), local(v))]; +} + +struct printing_dfs_visitor +{ + template<typename Vertex, typename Graph> + void initialize_vertex(Vertex v, const Graph& g) + { + vertex_event("initialize_vertex", v, g); + } + + template<typename Vertex, typename Graph> + void start_vertex(Vertex v, const Graph& g) + { + vertex_event("start_vertex", v, g); + } + + template<typename Vertex, typename Graph> + void discover_vertex(Vertex v, const Graph& g) + { + vertex_event("discover_vertex", v, g); + } + + template<typename Edge, typename Graph> + void examine_edge(Edge e, const Graph& g) + { + edge_event("examine_edge", e, g); + } + + template<typename Edge, typename Graph> + void tree_edge(Edge e, const Graph& g) + { + edge_event("tree_edge", e, g); + } + + template<typename Edge, typename Graph> + void back_edge(Edge e, const Graph& g) + { + edge_event("back_edge", e, g); + } + + template<typename Edge, typename Graph> + void forward_or_cross_edge(Edge e, const Graph& g) + { + edge_event("forward_or_cross_edge", e, g); + } + + template<typename Vertex, typename Graph> + void finish_vertex(Vertex v, const Graph& g) + { + vertex_event("finish_vertex", v, g); + } + +private: + template<typename Vertex, typename Graph> + void vertex_event(const char* name, Vertex v, const Graph& g) + { + std::cerr << "#" << process_id(g.process_group()) << ": " << name << "(" + << get_vertex_name(v, g) << ": " << local(v) << "@" << owner(v) + << ")\n"; + } + + template<typename Edge, typename Graph> + void edge_event(const char* name, Edge e, const Graph& g) + { + std::cerr << "#" << process_id(g.process_group()) << ": " << name << "(" + << get_vertex_name(source(e, g), g) << ": " + << local(source(e, g)) << "@" << owner(source(e, g)) << ", " + << get_vertex_name(target(e, g), g) << ": " + << local(target(e, g)) << "@" << owner(target(e, g)) << ")\n"; + } + +}; + +void +test_distributed_dfs() +{ + typedef adjacency_list<listS, + distributedS<mpi_process_group, vecS>, + undirectedS, + // Vertex properties + property<vertex_color_t, default_color_type> > + Graph; + typedef graph_traits<Graph>::vertex_descriptor vertex_descriptor; + + // Specify the edges in the graph + typedef std::pair<int, int> E; + E edge_array[] = { E(u, v), E(u, w), E(u, x), E(x, v), E(y, x), + E(v, y), E(w, y), E(w, z), E(z, z) }; + Graph g(edge_array, edge_array + sizeof(edge_array) / sizeof(E), N); + + std::vector<vertex_descriptor> parent(num_vertices(g)); + std::vector<vertex_descriptor> explore(num_vertices(g)); + + boost::graph::tsin_depth_first_visit + (g, + vertex(u, g), + printing_dfs_visitor(), + get(vertex_color, g), + make_iterator_property_map(parent.begin(), get(vertex_index, g)), + make_iterator_property_map(explore.begin(), get(vertex_index, g)), + get(vertex_index, g)); + +#if 0 + std::size_t correct_parents1[N] = {u, u, y, y, v, w}; + std::size_t correct_parents2[N] = {u, u, y, v, x, w}; +#endif + + for (std::size_t i = 0; i < N; ++i) { + vertex_descriptor v = vertex(i, g); + if (owner(v) == process_id(g.process_group())) { + std::cout << "parent(" << get_vertex_name(v, g) << ") = " + << get_vertex_name(parent[v.local], g) << std::endl; + + } + } + + if (false) { + depth_first_visit(g, vertex(u, g), printing_dfs_visitor()); + } +} + +int +test_main(int argc, char* argv[]) +{ + mpi::environment env(argc, argv); + test_distributed_dfs(); + return 0; +} diff --git a/src/boost/libs/graph_parallel/test/distributed_dimacs_reader.cpp b/src/boost/libs/graph_parallel/test/distributed_dimacs_reader.cpp new file mode 100644 index 000000000..a2e3cb7b4 --- /dev/null +++ b/src/boost/libs/graph_parallel/test/distributed_dimacs_reader.cpp @@ -0,0 +1,85 @@ +// Copyright (C) 2006 The Trustees of Indiana University. + +// 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) + +// Authors: Brian Barrett +// Nick Edmonds +// Andrew Lumsdaine + +#include <boost/graph/use_mpi.hpp> +#include <boost/config.hpp> +#include <boost/throw_exception.hpp> +#include <boost/graph/distributed/adjacency_list.hpp> +#include <boost/property_map/parallel/distributed_property_map.hpp> +#include <boost/graph/distributed/mpi_process_group.hpp> +#include <boost/graph/dimacs.hpp> +#include <boost/graph/graphviz.hpp> +#include <boost/test/minimal.hpp> + +#include <iostream> +#include <cstdlib> +#include <iomanip> +#include <fstream> + +#ifdef BOOST_NO_EXCEPTIONS +void +boost::throw_exception(std::exception const& ex) +{ + std::cout << ex.what() << std::endl; + abort(); +} +#endif + +using namespace boost; +using namespace boost::graph; +using boost::graph::distributed::mpi_process_group; + +typedef double time_type; + +inline time_type get_time() +{ + return MPI_Wtime(); +} + +std::string print_time(time_type t) +{ + std::ostringstream out; + out << std::setiosflags(std::ios::fixed) << std::setprecision(2) << t; + return out.str(); +} + +void +test_dimacs_reader(const char *filename) +{ + mpi_process_group pg; + + typedef adjacency_list<vecS, + distributedS<mpi_process_group, vecS>, + undirectedS> Graph; + + std::ifstream file(filename); + dimacs_basic_reader reader = dimacs_basic_reader(file, false); + dimacs_basic_reader end; + boost::parallel::variant_distribution<mpi_process_group> distrib = + boost::parallel::block(pg, reader.n_vertices()); + + Graph g(dimacs_edge_iterator<dimacs_basic_reader>(reader), + dimacs_edge_iterator<dimacs_basic_reader>(end), + reader.n_vertices(), pg, distrib);; + + // write_graphviz("reader.dot", g); +} + +int +test_main(int argc, char* argv[]) +{ + mpi::environment env(argc, argv); + + if (argc == 2) { + test_dimacs_reader(argv[1]); + } + + return 0; +} diff --git a/src/boost/libs/graph_parallel/test/distributed_graph_coloring_test.cpp b/src/boost/libs/graph_parallel/test/distributed_graph_coloring_test.cpp new file mode 100644 index 000000000..2b219c0a3 --- /dev/null +++ b/src/boost/libs/graph_parallel/test/distributed_graph_coloring_test.cpp @@ -0,0 +1,101 @@ +// Copyright (C) 2005, 2006 The Trustees of Indiana University. + +// 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) + +// Authors: Douglas Gregor +// Andrew Lumsdaine +#define PBGL_ACCOUNTING + +#include <boost/graph/use_mpi.hpp> +#include <boost/config.hpp> +#include <boost/throw_exception.hpp> +#include <boost/serialization/vector.hpp> +#include <boost/graph/distributed/boman_et_al_graph_coloring.hpp> +#include <boost/graph/distributed/mpi_process_group.hpp> +#include <boost/lexical_cast.hpp> +#include <boost/graph/parallel/distribution.hpp> +#include <boost/graph/erdos_renyi_generator.hpp> +#include <boost/graph/distributed/adjacency_list.hpp> +#include <boost/graph/graphviz.hpp> +#include <iostream> +#include <boost/random.hpp> +#include <boost/test/minimal.hpp> + +#ifdef BOOST_NO_EXCEPTIONS +void +boost::throw_exception(std::exception const& ex) +{ + std::cout << ex.what() << std::endl; + abort(); +} +#endif + +using namespace boost; +using boost::graph::distributed::mpi_process_group; + +void +test_distributed_graph_coloring(int n, double p, int s, + int seed, bool emit_dot_file) +{ + typedef adjacency_list<listS, + distributedS<mpi_process_group, vecS>, + undirectedS> Graph; + + typedef property_map<Graph, vertex_index_t>::type vertex_index_map; + + // Build a random number generator + minstd_rand gen; + gen.seed(seed); + + // Build a random graph + Graph g(erdos_renyi_iterator<minstd_rand, Graph>(gen, n, p), + erdos_renyi_iterator<minstd_rand, Graph>(), + n); + + // Set up color map + std::vector<int> colors_vec(num_vertices(g)); + iterator_property_map<int*, vertex_index_map> color(&colors_vec[0], + get(vertex_index, g)); + + // Run the graph coloring algorithm + graph::boman_et_al_graph_coloring(g, color, s); + + if (process_id(g.process_group()) == 0) { + graph::distributed::boman_et_al_graph_coloring_stats.print(std::cout); + } + + if ( emit_dot_file ) { + if ( process_id(g.process_group()) == 0 ) { + for (int i = 0; i < n; ++i) + get(color, vertex(i, g)); + synchronize(color); + } else { + synchronize(color); + } + + write_graphviz("coloring.dot", g, paint_by_number(color)); + } +} + +int test_main(int argc, char* argv[]) +{ + mpi::environment env(argc, argv); + + int n = 1000; + double p = 0.01; + int s = 100; + int seed = 1; + bool emit_dot_file = false; + + if (argc > 1) n = lexical_cast<int>(argv[1]); + if (argc > 2) p = lexical_cast<double>(argv[2]); + if (argc > 3) s = lexical_cast<int>(argv[3]); + if (argc > 4) seed = lexical_cast<int>(argv[4]); + if (argc > 5) emit_dot_file = lexical_cast<bool>(argv[5]); + + test_distributed_graph_coloring(n, p, s, seed, emit_dot_file); + + return 0; +} diff --git a/src/boost/libs/graph_parallel/test/distributed_mst_test.cpp b/src/boost/libs/graph_parallel/test/distributed_mst_test.cpp new file mode 100644 index 000000000..614116f60 --- /dev/null +++ b/src/boost/libs/graph_parallel/test/distributed_mst_test.cpp @@ -0,0 +1,151 @@ +// Copyright 2004 The Trustees of Indiana University. + +// 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) + +// Authors: Douglas Gregor +// Andrew Lumsdaine + +#include <boost/graph/use_mpi.hpp> +#include <boost/config.hpp> +#include <boost/throw_exception.hpp> +#include <boost/serialization/vector.hpp> +#include <boost/graph/distributed/dehne_gotz_min_spanning_tree.hpp> +#include <boost/graph/distributed/mpi_process_group.hpp> +#include <boost/graph/distributed/vertex_list_adaptor.hpp> +#include <boost/graph/parallel/distribution.hpp> +#include <boost/test/minimal.hpp> +#include <boost/graph/distributed/adjacency_list.hpp> +#include <iostream> +#include <cstdlib> + +#ifdef BOOST_NO_EXCEPTIONS +void +boost::throw_exception(std::exception const& ex) +{ + std::cout << ex.what() << std::endl; + abort(); +} +#endif + +using namespace boost; +using boost::graph::distributed::mpi_process_group; + +template<typename Graph, typename WeightMap, typename InputIterator> +int +total_weight(const Graph& g, WeightMap weight_map, + InputIterator first, InputIterator last) +{ + typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor; + + int total_weight = 0; + while (first != last) { + total_weight += get(weight_map, *first); + if (process_id(g.process_group()) == 0) { + vertex_descriptor u = source(*first, g); + vertex_descriptor v = target(*first, g); + std::cout << "(" << g.distribution().global(owner(u), local(u)) + << ", " << g.distribution().global(owner(v), local(v)) + << ")\n"; + } + ++first; + } + + return total_weight; +} + +void +test_distributed_dense_boruvka() +{ + typedef adjacency_list<listS, + distributedS<mpi_process_group, vecS>, + undirectedS, + // Vertex properties + no_property, + // Edge properties + property<edge_weight_t, int> > Graph; + + typedef graph_traits<Graph>::edge_descriptor edge_descriptor; + + typedef std::pair<int, int> E; + + const int num_nodes = 5; + E edge_array[] = { E(0, 2), E(1, 3), E(1, 4), E(2, 1), E(2, 3), + E(3, 4), E(4, 0), E(4, 1) + }; + int weights[] = { 1, 1, 2, 7, 3, 1, 1, 1 }; + std::size_t num_edges = sizeof(edge_array) / sizeof(E); + + Graph g(edge_array, edge_array + num_edges, weights, num_nodes); + + { + if (process_id(g.process_group()) == 0) + std::cerr << "--Dense Boruvka--\n"; + typedef property_map<Graph, edge_weight_t>::type WeightMap; + WeightMap weight_map = get(edge_weight, g); + + std::vector<edge_descriptor> mst_edges; + dense_boruvka_minimum_spanning_tree(make_vertex_list_adaptor(g), + weight_map, + std::back_inserter(mst_edges)); + int w = total_weight(g, weight_map, mst_edges.begin(), mst_edges.end()); + BOOST_CHECK(w == 4); + BOOST_CHECK(mst_edges.size() == 4); + } + + { + if (process_id(g.process_group()) == 0) + std::cerr << "--Merge local MSTs--\n"; + typedef property_map<Graph, edge_weight_t>::type WeightMap; + WeightMap weight_map = get(edge_weight, g); + + std::vector<edge_descriptor> mst_edges; + merge_local_minimum_spanning_trees(make_vertex_list_adaptor(g), weight_map, + std::back_inserter(mst_edges)); + if (process_id(g.process_group()) == 0) { + int w = total_weight(g, weight_map, mst_edges.begin(), mst_edges.end()); + BOOST_CHECK(w == 4); + BOOST_CHECK(mst_edges.size() == 4); + } + } + + { + if (process_id(g.process_group()) == 0) + std::cerr << "--Boruvka then Merge--\n"; + typedef property_map<Graph, edge_weight_t>::type WeightMap; + WeightMap weight_map = get(edge_weight, g); + + std::vector<edge_descriptor> mst_edges; + boruvka_then_merge(make_vertex_list_adaptor(g), weight_map, + std::back_inserter(mst_edges)); + if (process_id(g.process_group()) == 0) { + int w = total_weight(g, weight_map, mst_edges.begin(), mst_edges.end()); + BOOST_CHECK(w == 4); + BOOST_CHECK(mst_edges.size() == 4); + } + } + + { + if (process_id(g.process_group()) == 0) + std::cerr << "--Boruvka mixed Merge--\n"; + typedef property_map<Graph, edge_weight_t>::type WeightMap; + WeightMap weight_map = get(edge_weight, g); + + std::vector<edge_descriptor> mst_edges; + boruvka_mixed_merge(make_vertex_list_adaptor(g), weight_map, + std::back_inserter(mst_edges)); + if (process_id(g.process_group()) == 0) { + int w = total_weight(g, weight_map, mst_edges.begin(), mst_edges.end()); + BOOST_CHECK(w == 4); + BOOST_CHECK(mst_edges.size() == 4); + } + } +} + +int test_main(int argc, char** argv) +{ + boost::mpi::environment env(argc, argv); + test_distributed_dense_boruvka(); + return 0; +} diff --git a/src/boost/libs/graph_parallel/test/distributed_page_rank_test.cpp b/src/boost/libs/graph_parallel/test/distributed_page_rank_test.cpp new file mode 100644 index 000000000..d7b294574 --- /dev/null +++ b/src/boost/libs/graph_parallel/test/distributed_page_rank_test.cpp @@ -0,0 +1,110 @@ +// Copyright 2004 The Trustees of Indiana University. + +// 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) + +// Authors: Douglas Gregor +// Andrew Lumsdaine + +#include <boost/graph/use_mpi.hpp> +#include <boost/throw_exception.hpp> +#include <boost/serialization/vector.hpp> +#include <boost/graph/distributed/page_rank.hpp> +#include <boost/test/minimal.hpp> +#include <boost/graph/distributed/adjacency_list.hpp> +#include <boost/graph/distributed/mpi_process_group.hpp> +#include <boost/test/minimal.hpp> +#include <vector> +#include <iostream> +#include <stdlib.h> + +#ifdef BOOST_NO_EXCEPTIONS +void +boost::throw_exception(std::exception const& ex) +{ + std::cout << ex.what() << std::endl; + abort(); +} +#endif + +using namespace boost; +using boost::graph::distributed::mpi_process_group; + +bool close_to(double x, double y) +{ + double diff = x - y; + if (diff < 0) diff = -diff; + double base = (y == 0? x : y); + if (base != 0) return diff / base < 0.01; + else return true; +} + +// Make convenient labels for the vertices +enum vertex_id_t { A, B, C, D, N }; + +void test_distributed_page_rank(int iterations) +{ + using namespace boost::graph; + + // create a typedef for the Graph type + typedef adjacency_list<vecS, + distributedS<mpi_process_group, vecS>, + bidirectionalS + > Graph; + typedef graph_traits<Graph>::vertex_descriptor vertex_descriptor; + + // writing out the edges in the graph + typedef std::pair<int, int> Edge; + Edge edge_array[] = + { Edge(A,B), Edge(A,C), Edge(B,C), Edge(C,A), Edge(D,C) }; + const int num_edges = sizeof(edge_array)/sizeof(edge_array[0]); + + // declare a graph object + Graph g(edge_array, edge_array + num_edges, N); + + std::vector<double> ranks(num_vertices(g)); + + page_rank(g, + make_iterator_property_map(ranks.begin(), + get(boost::vertex_index, g)), + n_iterations(iterations), 0.85, N); + + double local_sum = 0.0; + for(unsigned int i = 0; i < num_vertices(g); ++i) { + std::cout << (char)('A' + g.distribution().global(i)) << " = " + << ranks[i] << std::endl; + local_sum += ranks[i]; + } + double sum=0.; + boost::mpi::reduce(communicator(g.process_group()), + local_sum, sum, std::plus<double>(), 0); + if (process_id(g.process_group()) == 0) { + std::cout << "Sum = " << sum << "\n\n"; + BOOST_CHECK(close_to(sum, 4)); // 1 when alpha=0 + } + + // double expected_ranks0[N] = {0.400009, 0.199993, 0.399998, 0.0}; + double expected_ranks[N] = {1.49011, 0.783296, 1.5766, 0.15}; + for (int i = 0; i < N; ++i) { + vertex_descriptor v = vertex(i, g); + if (v != Graph::null_vertex() + && owner(v) == process_id(g.process_group())) { + BOOST_CHECK(close_to(ranks[local(v)], expected_ranks[i])); + } + } +} + +int test_main(int argc, char* argv[]) +{ + mpi::environment env(argc, argv); + + int iterations = 50; + if (argc > 1) { + iterations = atoi(argv[1]); + } + + test_distributed_page_rank(iterations); + + return 0; +} diff --git a/src/boost/libs/graph_parallel/test/distributed_property_map_test.cpp b/src/boost/libs/graph_parallel/test/distributed_property_map_test.cpp new file mode 100644 index 000000000..6304fffa4 --- /dev/null +++ b/src/boost/libs/graph_parallel/test/distributed_property_map_test.cpp @@ -0,0 +1,356 @@ +// Copyright (C) 2004-2008 The Trustees of Indiana University. + +// 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) + +// Authors: Douglas Gregor +// Andrew Lumsdaine +#include <boost/graph/use_mpi.hpp> +#include <boost/config.hpp> +#include <boost/throw_exception.hpp> +#include <boost/graph/distributed/mpi_process_group.hpp> +#include <boost/property_map/property_map.hpp> +#include <boost/test/minimal.hpp> +#include <vector> +#include <string> +#include <boost/serialization/vector.hpp> +#include <boost/serialization/string.hpp> +#include <boost/serialization/utility.hpp> +#include <boost/lexical_cast.hpp> +#include <boost/graph/parallel/basic_reduce.hpp> + +#ifdef BOOST_NO_EXCEPTIONS +void +boost::throw_exception(std::exception const& ex) +{ + std::cout << ex.what() << std::endl; + abort(); +} +#endif + +using namespace boost; +using boost::graph::distributed::mpi_process_group; + +enum color_t { red, blue }; + +struct remote_key +{ + remote_key(int p = -1, std::size_t l = 0) : processor(p), local_key(l) {} + + int processor; + std::size_t local_key; + + template<typename Archiver> + void serialize(Archiver& ar, const unsigned int /*version*/) + { + ar & processor & local_key; + } +}; + +namespace boost { namespace mpi { + template<> struct is_mpi_datatype<remote_key> : mpl::true_ { }; +} } +BOOST_IS_BITWISE_SERIALIZABLE(remote_key) +BOOST_CLASS_IMPLEMENTATION(remote_key,object_serializable) +BOOST_CLASS_TRACKING(remote_key,track_never) + +namespace boost { + +template<> +struct hash<remote_key> +{ + std::size_t operator()(const remote_key& key) const + { + std::size_t hash = hash_value(key.processor); + hash_combine(hash, key.local_key); + return hash; + } +}; +} + +inline bool operator==(const remote_key& x, const remote_key& y) +{ return x.processor == y.processor && x.local_key == y.local_key; } + +struct remote_key_to_global +{ + typedef readable_property_map_tag category; + typedef remote_key key_type; + typedef std::pair<int, std::size_t> value_type; + typedef value_type reference; +}; + +inline std::pair<int, std::size_t> +get(remote_key_to_global, const remote_key& key) +{ + return std::make_pair(key.processor, key.local_key); +} + +template<typename T> +struct my_reduce : boost::parallel::basic_reduce<T> { + BOOST_STATIC_CONSTANT(bool, non_default_resolver = true); +}; + +void colored_test() +{ + mpi_process_group pg; + const int n = 500; + + color_t my_start_color = process_id(pg) % 2 == 0? ::red : ::blue; + int next_processor = (process_id(pg) + 1) % num_processes(pg); + color_t next_start_color = next_processor % 2 == 0? ::red : ::blue; + + // Initial color map: even-numbered processes are all red, + // odd-numbered processes are all blue. + std::vector<color_t> color_vec(n, my_start_color); + + typedef iterator_property_map<std::vector<color_t>::iterator, + identity_property_map> LocalPropertyMap; + LocalPropertyMap local_colors(color_vec.begin(), identity_property_map()); + + synchronize(pg); + + // Create the distributed property map + typedef boost::parallel::distributed_property_map<mpi_process_group, + remote_key_to_global, + LocalPropertyMap> ColorMap; + ColorMap colors(pg, remote_key_to_global(), local_colors); + colors.set_reduce(my_reduce<color_t>()); + + if (process_id(pg) == 0) std::cerr << "Checking local colors..."; + // check local processor colors + for (int i = 0; i < n; ++i) { + remote_key k(process_id(pg), i); + BOOST_CHECK(get(colors, k) == my_start_color); + } + + colors.set_consistency_model(boost::parallel::cm_bidirectional); + if (process_id(pg) == 0) std::cerr << "OK.\nChecking next processor's default colors..."; + // check next processor's colors + for (int i = 0; i < n; ++i) { + remote_key k(next_processor, i); + BOOST_CHECK(get(colors, k) == color_t()); + } + + if (process_id(pg) == 0) std::cerr << "OK.\nSynchronizing..."; + synchronize(pg); + + if (process_id(pg) == 0) std::cerr << "OK.\nChecking next processor's colors..."; + // check next processor's colors + for (int i = 0; i < n; ++i) { + remote_key k(next_processor, i); + BOOST_CHECK(get(colors, k) == next_start_color); + } + + if (process_id(pg) == 0) std::cerr << "OK.\nSynchronizing..."; + synchronize(pg); + + if (process_id(pg) == 0) std::cerr << "OK.\nChanging next processor's colors..."; + // change the next processor's colors + color_t next_finish_color = next_processor % 2 == 0? ::blue : ::red; + for (int i = 0; i < n; ++i) { + remote_key k(next_processor, i); + put(colors, k, next_finish_color); + } + + if (process_id(pg) == 0) std::cerr << "OK.\nSynchronizing..."; + synchronize(pg); + + if (process_id(pg) == 0) std::cerr << "OK.\nChecking changed colors..."; + // check our own colors + color_t my_finish_color = process_id(pg) % 2 == 0? ::blue : ::red; + for (int i = 0; i < n; ++i) { + remote_key k(process_id(pg), i); + BOOST_CHECK(get(colors, k) == my_finish_color); + } + + // check our neighbor's colors + if (process_id(pg) == 0) std::cerr << "OK.\nChecking changed colors on neighbor..."; + for (int i = 0; i < n; ++i) { + remote_key k(next_processor, i); + BOOST_CHECK(get(colors, k) == next_finish_color); + } + + synchronize(pg); + + if (process_id(pg) == 0) std::cerr << "OK.\n"; +} + +void bool_test() +{ + mpi_process_group pg; + const int n = 500; + + bool my_start_value = process_id(pg) % 2; + int next_processor = (process_id(pg) + 1) % num_processes(pg); + bool next_start_value = ((process_id(pg) + 1) % num_processes(pg)) % 2; + + // Initial color map: even-numbered processes are false, + // odd-numbered processes are true + std::vector<bool> bool_vec(n, my_start_value); + + typedef iterator_property_map<std::vector<bool>::iterator, + identity_property_map> LocalPropertyMap; + LocalPropertyMap local_values(bool_vec.begin(), identity_property_map()); + + synchronize(pg); + + // Create the distributed property map + typedef boost::parallel::distributed_property_map<mpi_process_group, + remote_key_to_global, + LocalPropertyMap> ValueMap; + ValueMap values(pg, remote_key_to_global(), local_values); + values.set_reduce(my_reduce<bool>()); + + if (process_id(pg) == 0) std::cerr << "Checking local values..."; + // check local processor values + for (int i = 0; i < n; ++i) { + remote_key k(process_id(pg), i); + BOOST_CHECK(get(values, k) == my_start_value); + } + + values.set_consistency_model(boost::parallel::cm_bidirectional); + if (process_id(pg) == 0) std::cerr << "OK.\nChecking next processor's default values..."; + // check next processor's values + for (int i = 0; i < n; ++i) { + remote_key k(next_processor, i); + BOOST_CHECK(get(values, k) == false); + } + + if (process_id(pg) == 0) std::cerr << "OK.\nSynchronizing..."; + synchronize(pg); + + if (process_id(pg) == 0) std::cerr << "OK.\nChecking next processor's values..."; + // check next processor's values + for (int i = 0; i < n; ++i) { + remote_key k(next_processor, i); + BOOST_CHECK(get(values, k) == next_start_value); + } + + if (process_id(pg) == 0) std::cerr << "OK.\nSynchronizing..."; + synchronize(pg); + + if (process_id(pg) == 0) std::cerr << "OK.\nChanging next processor's values..."; + // change the next processor's values + bool next_finish_value = next_processor % 2 == 0; + for (int i = 0; i < n; ++i) { + remote_key k(next_processor, i); + put(values, k, next_finish_value); + } + + if (process_id(pg) == 0) std::cerr << "OK.\nSynchronizing..."; + synchronize(pg); + + if (process_id(pg) == 0) std::cerr << "OK.\nChecking changed values..."; + // check our own values + bool my_finish_value = process_id(pg) % 2 == 0; + for (int i = 0; i < n; ++i) { + remote_key k(process_id(pg), i); + BOOST_CHECK(get(values, k) == my_finish_value); + } + + // check our neighbor's values + if (process_id(pg) == 0) std::cerr << "OK.\nChecking changed values on neighbor..."; + for (int i = 0; i < n; ++i) { + remote_key k(next_processor, i); + BOOST_CHECK(get(values, k) == next_finish_value); + } + + synchronize(pg); + + if (process_id(pg) == 0) std::cerr << "OK.\n"; +} + +void string_test() +{ + mpi_process_group pg; + const int n = 500; + + std::string my_start_string = lexical_cast<std::string>(process_id(pg)); + int next_processor = (process_id(pg) + 1) % num_processes(pg); + std::string next_start_string = lexical_cast<std::string>(next_processor); + + // Initial color map: even-numbered processes are false, + // odd-numbered processes are true + std::vector<std::string> string_vec(n, my_start_string); + + typedef iterator_property_map<std::vector<std::string>::iterator, + identity_property_map> LocalPropertyMap; + LocalPropertyMap local_strings(string_vec.begin(), identity_property_map()); + + synchronize(pg); + + // Create the distributed property map + typedef boost::parallel::distributed_property_map<mpi_process_group, + remote_key_to_global, + LocalPropertyMap> StringMap; + StringMap strings(pg, remote_key_to_global(), local_strings); + strings.set_reduce(my_reduce<std::string>()); + + if (process_id(pg) == 0) std::cerr << "Checking local strings..."; + // check local processor strings + for (int i = 0; i < n; ++i) { + remote_key k(process_id(pg), i); + BOOST_CHECK(get(strings, k) == my_start_string); + } + + strings.set_consistency_model(boost::parallel::cm_bidirectional); + if (process_id(pg) == 0) std::cerr << "OK.\nChecking next processor's default strings..."; + // check next processor's strings + for (int i = 0; i < n; ++i) { + remote_key k(next_processor, i); + BOOST_CHECK(get(strings, k) == (num_processes(pg) == 1 ? my_start_string : std::string())); + } + + if (process_id(pg) == 0) std::cerr << "OK.\nSynchronizing..."; + synchronize(pg); + + if (process_id(pg) == 0) std::cerr << "OK.\nChecking next processor's strings..."; + // check next processor's strings + for (int i = 0; i < n; ++i) { + remote_key k(next_processor, i); + BOOST_CHECK(get(strings, k) == next_start_string); + } + + if (process_id(pg) == 0) std::cerr << "OK.\nSynchronizing..."; + synchronize(pg); + + if (process_id(pg) == 0) std::cerr << "OK.\nChanging next processor's strings..."; + // change the next processor's strings + std::string next_finish_string = next_start_string + next_start_string; + for (int i = 0; i < n; ++i) { + remote_key k(next_processor, i); + put(strings, k, next_finish_string); + } + + if (process_id(pg) == 0) std::cerr << "OK.\nSynchronizing..."; + synchronize(pg); + + if (process_id(pg) == 0) std::cerr << "OK.\nChecking changed strings..."; + // check our own strings + std::string my_finish_string = my_start_string + my_start_string; + for (int i = 0; i < n; ++i) { + remote_key k(process_id(pg), i); + BOOST_CHECK(get(strings, k) == my_finish_string); + } + + // check our neighbor's strings + if (process_id(pg) == 0) std::cerr << "OK.\nChecking changed strings on neighbor..."; + for (int i = 0; i < n; ++i) { + remote_key k(next_processor, i); + BOOST_CHECK(get(strings, k) == next_finish_string); + } + + synchronize(pg); + + if (process_id(pg) == 0) std::cerr << "OK.\n"; +} + +int test_main(int argc, char** argv) +{ + boost::mpi::environment env(argc, argv); + colored_test(); + bool_test(); + string_test(); + return 0; +} diff --git a/src/boost/libs/graph_parallel/test/distributed_queue_test.cpp b/src/boost/libs/graph_parallel/test/distributed_queue_test.cpp new file mode 100644 index 000000000..5a3630384 --- /dev/null +++ b/src/boost/libs/graph_parallel/test/distributed_queue_test.cpp @@ -0,0 +1,116 @@ +// Copyright (C) 2004-2006 The Trustees of Indiana University. + +// 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) + +// Authors: Douglas Gregor +// Andrew Lumsdaine +#include <boost/graph/use_mpi.hpp> +#include <boost/config.hpp> +#include <boost/throw_exception.hpp> +#include <boost/serialization/vector.hpp> +#include <boost/graph/distributed/queue.hpp> +#include <boost/test/minimal.hpp> +#include <boost/graph/distributed/mpi_process_group.hpp> +#include <boost/pending/queue.hpp> +#include <boost/property_map/property_map.hpp> +#include <utility> +#include <iostream> + +#ifdef BOOST_NO_EXCEPTIONS +void +boost::throw_exception(std::exception const& ex) +{ + std::cout << ex.what() << std::endl; + abort(); +} +#endif + +using boost::graph::distributed::mpi_process_group; + +struct global_value +{ + global_value(int p = -1, std::size_t l = 0) : processor(p), value(l) {} + + int processor; + std::size_t value; + + template<typename Archiver> + void serialize(Archiver& ar, const unsigned int /*version*/) + { + ar & processor & value; + } +}; + +namespace boost { namespace mpi { + template<> struct is_mpi_datatype<global_value> : mpl::true_ { }; +} } // end namespace boost::mpi + +BOOST_IS_BITWISE_SERIALIZABLE(global_value) +BOOST_CLASS_IMPLEMENTATION(global_value,object_serializable) +BOOST_CLASS_TRACKING(global_value,track_never) + +inline bool operator==(const global_value& x, const global_value& y) +{ return x.processor == y.processor && x.value == y.value; } + +struct global_value_owner_map +{ + typedef int value_type; + typedef value_type reference; + typedef global_value key_type; + typedef boost::readable_property_map_tag category; +}; + +int get(global_value_owner_map, global_value k) +{ + return k.processor; +} + +void test_distributed_queue() +{ + mpi_process_group process_group; + + typedef boost::queue<global_value> local_queue_type; + + typedef boost::graph::distributed::distributed_queue<mpi_process_group, + global_value_owner_map, + local_queue_type> dist_queue_type; + + dist_queue_type Q(process_group, global_value_owner_map()); + + mpi_process_group::process_id_type id = process_id(process_group), + n = num_processes(process_group); + global_value v(0, 0); + + if (id == 0) { + std::cerr << "Should print level of each processor in a binary tree:\n"; + } + synchronize(process_group); + + if (id == n-1) Q.push(v); + while (!Q.empty()) { + v = Q.top(); Q.pop(); + + std::cerr << "#" << id << ": level = " << v.value << std::endl; + + int level_begin = 1; + for (std::size_t i = 0; i < v.value; ++i) level_begin *= 2; + int level_end = level_begin * 2; + BOOST_CHECK(level_begin <= (id + 1)); + BOOST_CHECK((id + 1) <= level_end); + + ++v.value; + v.processor = v.processor * 2 + 1; + if (v.processor < n) Q.push(v); + ++v.processor; + if (v.processor < n) Q.push(v); + } +} + +int test_main(int argc, char** argv) +{ + boost::mpi::environment env(argc, argv); + test_distributed_queue(); + return 0; +} diff --git a/src/boost/libs/graph_parallel/test/distributed_rmat_cc.cpp b/src/boost/libs/graph_parallel/test/distributed_rmat_cc.cpp new file mode 100644 index 000000000..606381753 --- /dev/null +++ b/src/boost/libs/graph_parallel/test/distributed_rmat_cc.cpp @@ -0,0 +1,118 @@ +// Copyright (C) 2006 The Trustees of Indiana University. + +// 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) + +// Authors: Brian Barrett +// Nick Edmonds +// Andrew Lumsdaine + +#include <boost/graph/use_mpi.hpp> +#include <boost/config.hpp> +#include <boost/throw_exception.hpp> +#include <boost/graph/distributed/adjacency_list.hpp> +#include <boost/property_map/parallel/distributed_property_map.hpp> +#include <boost/graph/distributed/mpi_process_group.hpp> +#include <boost/graph/distributed/concepts.hpp> +#include <boost/graph/distributed/connected_components_parallel_search.hpp> +#include <boost/graph/distributed/connected_components.hpp> +#include <boost/graph/rmat_graph_generator.hpp> +#include <boost/random/linear_congruential.hpp> +#include <boost/graph/graphviz.hpp> +#include <boost/property_map/vector_property_map.hpp> + +#include <iostream> +#include <cstdlib> +#include <iomanip> + +#ifdef BOOST_NO_EXCEPTIONS +void +boost::throw_exception(std::exception const& ex) +{ + std::cout << ex.what() << std::endl; + abort(); +} +#endif + +using namespace boost; +using boost::graph::distributed::mpi_process_group; + +typedef double time_type; + +inline time_type get_time() +{ + return MPI_Wtime(); +} + +std::string print_time(time_type t) +{ + std::ostringstream out; + out << std::setiosflags(std::ios::fixed) << std::setprecision(2) << t; + return out.str(); +} + +void +test_filtered_rmat_cc(int n, int m, double a, double b, double c, double d) +{ + mpi_process_group pg; + mpi_process_group::process_id_type id = process_id(pg); + + if (id == 0) printf("INFO: Params: n=%d, m=%d, a=%f, b=%f, c=%f, d=%f.\n", + n, m, a, b, c, d); + + parallel::variant_distribution<mpi_process_group> distrib + = parallel::block(pg, n); + + typedef adjacency_list<vecS, + distributedS<mpi_process_group, vecS>, + undirectedS> Graph; + + typedef keep_local_edges<parallel::variant_distribution<mpi_process_group>, + mpi_process_group::process_id_type> + EdgeFilter; + + typedef unique_rmat_iterator<rand48, Graph, EdgeFilter> + RMATIter; + + if (id == 0) printf("INFO: Generating graph.\n"); + + rand48 gen; + Graph g(RMATIter(gen, n, m, a, b, c, d, true, EdgeFilter(distrib, id)), + RMATIter(), n, pg, distrib); + + synchronize(g); + + if (id == 0) printf("INFO: Starting connected components.\n"); + + std::vector<int> local_components_vec(num_vertices(g)); + typedef iterator_property_map<std::vector<int>::iterator, property_map<Graph, vertex_index_t>::type> ComponentMap; + ComponentMap component(local_components_vec.begin(), get(vertex_index, g)); + + time_type start = get_time(); + int num_components = connected_components(g, component); + time_type end = get_time(); + + if (process_id(g.process_group()) == 0) { + std::cout << "INFO: Test Complete. components found = " << num_components + << ", time = " << print_time(end - start) << "s." << std::endl; + printf("RESULT: %d %d %d %f %f %f %f %f\n", + num_processes(pg), n, m, a, b, c, d, end - start); + } + +} + +int +main(int argc, char* argv[]) +{ + mpi::environment env(argc, argv); + + if (argc < 7) + test_filtered_rmat_cc(40, 200, 0.58, 0.19, 0.19, 0.04); + else + test_filtered_rmat_cc(atoi(argv[1]), atoi(argv[2]), + atof(argv[3]), atof(argv[4]), + atof(argv[5]), atof(argv[6])); + + return 0; +} diff --git a/src/boost/libs/graph_parallel/test/distributed_rmat_cc_ps.cpp b/src/boost/libs/graph_parallel/test/distributed_rmat_cc_ps.cpp new file mode 100644 index 000000000..020465c50 --- /dev/null +++ b/src/boost/libs/graph_parallel/test/distributed_rmat_cc_ps.cpp @@ -0,0 +1,117 @@ +// Copyright (C) 2006 The Trustees of Indiana University. + +// 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) + +// Authors: Brian Barrett +// Nick Edmonds +// Andrew Lumsdaine + +#include <boost/graph/use_mpi.hpp> +#include <boost/config.hpp> +#include <boost/throw_exception.hpp> +#include <boost/graph/distributed/adjacency_list.hpp> +#include <boost/property_map/parallel/distributed_property_map.hpp> +#include <boost/graph/distributed/mpi_process_group.hpp> +#include <boost/graph/distributed/concepts.hpp> +#include <boost/graph/distributed/connected_components_parallel_search.hpp> +#include <boost/graph/distributed/connected_components.hpp> +#include <boost/graph/rmat_graph_generator.hpp> +#include <boost/random/linear_congruential.hpp> +#include <boost/graph/graphviz.hpp> +#include <boost/property_map/vector_property_map.hpp> + +#include <iostream> +#include <cstdlib> +#include <iomanip> + +#ifdef BOOST_NO_EXCEPTIONS +void +boost::throw_exception(std::exception const& ex) +{ + std::cout << ex.what() << std::endl; + abort(); +} +#endif + +using namespace boost; +using boost::graph::distributed::mpi_process_group; + +typedef double time_type; + +inline time_type get_time() +{ + return MPI_Wtime(); +} + +std::string print_time(time_type t) +{ + std::ostringstream out; + out << std::setiosflags(std::ios::fixed) << std::setprecision(2) << t; + return out.str(); +} + +void +test_filtered_rmat_cc(int n, int m, double a, double b, double c, double d) +{ + mpi_process_group pg; + std::size_t id = process_id(pg); + + if (id == 0) printf("INFO: Params: n=%d, m=%d, a=%f, b=%f, c=%f, d=%f.\n", + n, m, a, b, c, d); + + typedef parallel::variant_distribution<mpi_process_group> Distribution; + Distribution distrib = parallel::block(pg, n); + + typedef adjacency_list<vecS, + distributedS<mpi_process_group, vecS>, + undirectedS> Graph; + + typedef scalable_rmat_iterator<mpi_process_group, Distribution, rand48, Graph> + RMATIter; + + if (id == 0) printf("INFO: Generating graph.\n"); + + rand48 gen; + time_type gen_start = get_time(); + Graph g(RMATIter(pg, distrib, gen, n, m, a, b, c, d, true), + RMATIter(), n, pg, distrib); + time_type gen_end = get_time(); + std::cout << "INFO: Graph Gen time: " << print_time(gen_end - gen_start) << std::endl; + + synchronize(g); + + if (id == 0) printf("INFO: Starting connected components.\n"); + + std::vector<int> local_components_vec(num_vertices(g)); + typedef iterator_property_map<std::vector<int>::iterator, property_map<Graph, vertex_index_t>::type> ComponentMap; + ComponentMap component(local_components_vec.begin(), get(vertex_index, g)); + + time_type start = get_time(); + int num_components = connected_components_ps(g, component); + time_type end = get_time(); + + if (process_id(g.process_group()) == 0) { + std::cout << "INFO: Test Complete. components found = " << num_components + << ", time = " << print_time(end - start) << "s." << std::endl; + printf("RESULT: %d %d %d %f %f %f %f %f\n", + num_processes(pg), n, m, a, b, c, d, end - start); + } + +} + +int +main(int argc, char* argv[]) +{ + mpi::environment env(argc, argv); + + if (argc < 7) + test_filtered_rmat_cc(40, 200, 0.58, 0.19, 0.19, 0.04); + else + test_filtered_rmat_cc(atoi(argv[1]), atoi(argv[2]), + atof(argv[3]), atof(argv[4]), + atof(argv[5]), atof(argv[6])); + + return 0; +} diff --git a/src/boost/libs/graph_parallel/test/distributed_rmat_pagerank.cpp b/src/boost/libs/graph_parallel/test/distributed_rmat_pagerank.cpp new file mode 100644 index 000000000..8700249e0 --- /dev/null +++ b/src/boost/libs/graph_parallel/test/distributed_rmat_pagerank.cpp @@ -0,0 +1,113 @@ +// Copyright (C) 2006 The Trustees of Indiana University. + +// 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) + +// Authors: Brian Barrett +// Nick Edmonds +// Andrew Lumsdaine + +#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/compressed_sparse_row_graph.hpp> +#include <boost/property_map/parallel/distributed_property_map.hpp> +#include <boost/graph/distributed/mpi_process_group.hpp> +#include <boost/graph/distributed/concepts.hpp> +#include <boost/graph/distributed/page_rank.hpp> +#include <boost/graph/rmat_graph_generator.hpp> +#include <boost/random/linear_congruential.hpp> +#include <boost/graph/graphviz.hpp> +#include <boost/property_map/vector_property_map.hpp> + +#include <iostream> +#include <cstdlib> +#include <iomanip> + +#ifdef BOOST_NO_EXCEPTIONS +void +boost::throw_exception(std::exception const& ex) +{ + std::cout << ex.what() << std::endl; + abort(); +} +#endif + +using namespace boost; +using boost::graph::distributed::mpi_process_group; + +typedef double time_type; + +inline time_type get_time() +{ + return MPI_Wtime(); +} + +std::string print_time(time_type t) +{ + std::ostringstream out; + out << std::setiosflags(std::ios::fixed) << std::setprecision(2) << t; + return out.str(); +} + +void +test_filtered_rmat_pagerank(int n, int m, double a, double b, double c, double d, int iters) +{ + mpi_process_group pg; + std::size_t id = process_id(pg); + + if (id == 0) printf("INFO: Params: n=%d, m=%d, a=%f, b=%f, c=%f, d=%f, iters=%d.\n", + n, m, a, b, c, d, iters); + + typedef parallel::variant_distribution<mpi_process_group> Distribution; + Distribution distrib = parallel::block(pg, n); + + typedef adjacency_list<vecS, + distributedS<mpi_process_group, vecS>, + bidirectionalS> Graph; + + typedef scalable_rmat_iterator<mpi_process_group, Distribution, rand48, Graph> + RMATIter; + + if (id == 0) printf("INFO: Generating graph.\n"); + + rand48 gen; + Graph g(RMATIter(pg, distrib, gen, n, m, a, b, c, d, true), + RMATIter(), n, pg, distrib); + + synchronize(g); + + if (id == 0) printf("INFO: Starting PageRank.\n"); + + std::vector<double> ranks(num_vertices(g)); + + time_type start = get_time(); + page_rank(g, make_iterator_property_map(ranks.begin(), get(boost::vertex_index, g)), + graph::n_iterations(iters), 0.85, n); + time_type end = get_time(); + + if (process_id(g.process_group()) == 0) { + std::cout << "INFO: Test Complete. time = " << + print_time(end - start) << "s." << std::endl; + printf("RESULT: %d %d %d %f %f %f %f %f\n", + num_processes(pg), n, m, a, b, c, d, end - start); + } + +} + +int +main(int argc, char* argv[]) +{ + mpi::environment env(argc, argv); + + if (argc < 8) + test_filtered_rmat_pagerank(40, 200, 0.58, 0.19, 0.19, 0.04, 10); + else + test_filtered_rmat_pagerank(atoi(argv[1]), atoi(argv[2]), atof(argv[3]), + atof(argv[4]), atof(argv[5]), atof(argv[6]), + atoi(argv[7])); + + return 0; +} diff --git a/src/boost/libs/graph_parallel/test/distributed_shortest_paths_test.cpp b/src/boost/libs/graph_parallel/test/distributed_shortest_paths_test.cpp new file mode 100644 index 000000000..fce4c255e --- /dev/null +++ b/src/boost/libs/graph_parallel/test/distributed_shortest_paths_test.cpp @@ -0,0 +1,214 @@ +// Copyright (C) 2005, 2006 The Trustees of Indiana University. + +// 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) + +// Authors: Douglas Gregor +// Andrew Lumsdaine +#define PBGL_ACCOUNTING + +#include <boost/graph/use_mpi.hpp> +#include <boost/config.hpp> +#include <boost/throw_exception.hpp> +#include <boost/graph/distributed/delta_stepping_shortest_paths.hpp> +#include <boost/graph/distributed/mpi_process_group.hpp> +#include <boost/lexical_cast.hpp> +#include <boost/graph/parallel/distribution.hpp> +#include <boost/graph/erdos_renyi_generator.hpp> +#include <boost/graph/distributed/adjacency_list.hpp> +#include <boost/graph/graphviz.hpp> +#include <boost/random.hpp> +#include <boost/test/minimal.hpp> +#include <boost/graph/iteration_macros.hpp> + +#include <iostream> +#include <iomanip> + +#ifdef BOOST_NO_EXCEPTIONS +void +boost::throw_exception(std::exception const& ex) +{ + std::cout << ex.what() << std::endl; + abort(); +} +#endif + +/**************************************************************************** + * Timing * + ****************************************************************************/ +typedef double time_type; + +inline time_type get_time() +{ + return MPI_Wtime(); +} + +std::string print_time(time_type t) +{ + std::ostringstream out; + out << std::setiosflags(std::ios::fixed) << std::setprecision(2) << t; + return out.str(); +} + +/**************************************************************************** + * Edge weight generator iterator * + ****************************************************************************/ +template<typename F, typename RandomGenerator> +class generator_iterator +{ +public: + typedef std::input_iterator_tag iterator_category; + typedef typename F::result_type value_type; + typedef const value_type& reference; + typedef const value_type* pointer; + typedef void difference_type; + + explicit + generator_iterator(RandomGenerator& gen, const F& f = F()) + : f(f), gen(&gen) + { + value = this->f(gen); + } + + reference operator*() const { return value; } + pointer operator->() const { return &value; } + + generator_iterator& operator++() + { + value = f(*gen); + return *this; + } + + generator_iterator operator++(int) + { + generator_iterator temp(*this); + ++(*this); + return temp; + } + + bool operator==(const generator_iterator& other) const + { return f == other.f; } + + bool operator!=(const generator_iterator& other) const + { return !(*this == other); } + +private: + F f; + RandomGenerator* gen; + value_type value; +}; + +template<typename F, typename RandomGenerator> +inline generator_iterator<F, RandomGenerator> +make_generator_iterator( RandomGenerator& gen, const F& f) +{ return generator_iterator<F, RandomGenerator>(gen, f); } + +/**************************************************************************** + * Verification * + ****************************************************************************/ +template <typename Graph, typename DistanceMap, typename WeightMap> +void +verify_shortest_paths(const Graph& g, DistanceMap distance, + const WeightMap& weight) { + + distance.set_max_ghost_cells(0); + + BGL_FORALL_VERTICES_T(v, g, Graph) { + BGL_FORALL_OUTEDGES_T(v, e, g, Graph) { + get(distance, target(e, g)); + } + } + + synchronize(process_group(g)); + + BGL_FORALL_VERTICES_T(v, g, Graph) { + BGL_FORALL_OUTEDGES_T(v, e, g, Graph) { + assert(get(distance, target(e, g)) <= + get(distance, source(e, g)) + get(weight, e)); + } + } +} + +using namespace boost; +using boost::graph::distributed::mpi_process_group; + +typedef int weight_type; + +struct WeightedEdge { + WeightedEdge(weight_type weight = 0) : weight(weight) { } + + weight_type weight; + + template<typename Archiver> + void serialize(Archiver& ar, const unsigned int /*version*/) + { + ar & weight; + } +}; + +struct VertexProperties { + VertexProperties(int d = 0) + : distance(d) { } + + int distance; + + template<typename Archiver> + void serialize(Archiver& ar, const unsigned int /*version*/) + { + ar & distance; + } +}; + +void +test_distributed_shortest_paths(int n, double p, int c, int seed) +{ + typedef adjacency_list<listS, + distributedS<mpi_process_group, vecS>, + undirectedS, + VertexProperties, + WeightedEdge> Graph; + + typedef graph_traits<Graph>::vertices_size_type vertices_size_type; + + // Build a random number generator + minstd_rand gen; + gen.seed(seed); + + // Build a random graph + Graph g(erdos_renyi_iterator<minstd_rand, Graph>(gen, n, p), + erdos_renyi_iterator<minstd_rand, Graph>(), + make_generator_iterator(gen, uniform_int<int>(0, c)), + n); + + uniform_int<vertices_size_type> rand_vertex(0, n); + + graph::distributed::delta_stepping_shortest_paths(g, + vertex(rand_vertex(gen), g), + dummy_property_map(), + get(&VertexProperties::distance, g), + get(&WeightedEdge::weight, g)); + + verify_shortest_paths(g, + get(&VertexProperties::distance, g), + get(&WeightedEdge::weight, g)); +} + +int test_main(int argc, char* argv[]) +{ + mpi::environment env(argc, argv); + + int n = 1000; + double p = 0.01; + int c = 100; + int seed = 1; + + if (argc > 1) n = lexical_cast<int>(argv[1]); + if (argc > 2) p = lexical_cast<double>(argv[2]); + if (argc > 3) c = lexical_cast<int>(argv[3]); + if (argc > 4) seed = lexical_cast<int>(argv[4]); + + test_distributed_shortest_paths(n, p, c, seed); + + return 0; +} diff --git a/src/boost/libs/graph_parallel/test/distributed_st_connected_test.cpp b/src/boost/libs/graph_parallel/test/distributed_st_connected_test.cpp new file mode 100644 index 000000000..a65f404f0 --- /dev/null +++ b/src/boost/libs/graph_parallel/test/distributed_st_connected_test.cpp @@ -0,0 +1,85 @@ +// Copyright (C) 2004-2006 The Trustees of Indiana University. + +// 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) + +// Authors: Nick Edmonds +// Andrew Lumsdaine + +#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/random.hpp> +#include <boost/property_map/parallel/distributed_property_map.hpp> +#include <boost/graph/distributed/mpi_process_group.hpp> +#include <boost/graph/distributed/st_connected.hpp> +#include <boost/graph/parallel/distribution.hpp> +#include <boost/graph/small_world_generator.hpp> +#include <iostream> +#include <cstdlib> +#include <iomanip> +#include <boost/random.hpp> +#include <boost/test/minimal.hpp> + +#ifdef BOOST_NO_EXCEPTIONS +void +boost::throw_exception(std::exception const& ex) +{ + std::cout << ex.what() << std::endl; + abort(); +} +#endif + +using namespace boost; +using boost::graph::distributed::mpi_process_group; + +// Set up the vertex names +enum vertex_id_t { u, v, w, x, y, z, N }; +char vertex_names[] = { 'u', 'v', 'w', 'x', 'y', 'z' }; + +void +test_distributed_st_connected() { + + typedef adjacency_list<listS, + distributedS<mpi_process_group, vecS>, + undirectedS, + // Vertex properties + property<vertex_color_t, default_color_type> > + Graph; + + // Specify the edges in the graph + { + typedef std::pair<int, int> E; + E edge_array[] = { E(u, u), E(u, v), E(u, w), E(v, w), E(x, y), + E(x, z), E(z, y), E(z, z) }; + Graph g(edge_array, edge_array + sizeof(edge_array) / sizeof(E), N); + + bool connected = st_connected(g, vertex(u, g), vertex(z, g), + get(vertex_color, g), get(vertex_owner, g)); + + assert(!connected); + } + + { + typedef std::pair<int, int> E; + E edge_array[] = { E(u, v), E(u, w), E(u, x), E(x, v), E(y, x), + E(v, y), E(w, y), E(w, z), E(z, z) }; + Graph g(edge_array, edge_array + sizeof(edge_array) / sizeof(E), N); + + bool connected = st_connected(g, vertex(u, g), vertex(z, g), + get(vertex_color, g), get(vertex_owner, g)); + + assert(connected); + } + + +} + +int test_main(int argc, char* argv[]) +{ + mpi::environment env(argc, argv); + test_distributed_st_connected(); + return 0; +} diff --git a/src/boost/libs/graph_parallel/test/distributed_strong_components_test.cpp b/src/boost/libs/graph_parallel/test/distributed_strong_components_test.cpp new file mode 100644 index 000000000..cbbd41b5a --- /dev/null +++ b/src/boost/libs/graph_parallel/test/distributed_strong_components_test.cpp @@ -0,0 +1,175 @@ +// Copyright (C) 2004-2008 The Trustees of Indiana University. + +// 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) + +// Authors: Nick Edmonds +// Douglas Gregor +// Andrew Lumsdaine + +// SCC won't work with CSR currently due to the way the reverse graph +// is constructed in the SCC algorithm + +#include <boost/graph/use_mpi.hpp> + +// #define CSR + +#ifdef CSR +# include <boost/graph/distributed/compressed_sparse_row_graph.hpp> +#else +# include <boost/graph/distributed/adjacency_list.hpp> +#endif + +#include <boost/config.hpp> +#include <boost/throw_exception.hpp> +#include <boost/graph/strong_components.hpp> +#include <boost/graph/random.hpp> +#include <boost/property_map/parallel/distributed_property_map.hpp> +#include <boost/graph/distributed/mpi_process_group.hpp> +#include <boost/graph/parallel/distribution.hpp> +#include <boost/graph/erdos_renyi_generator.hpp> +#include <boost/test/minimal.hpp> +#include <boost/graph/distributed/graphviz.hpp> +#include <iostream> +#include <cstdlib> +#include <iomanip> +#include <boost/random.hpp> +#include <boost/test/minimal.hpp> + +#ifdef BOOST_NO_EXCEPTIONS +void +boost::throw_exception(std::exception const& ex) +{ + std::cout << ex.what() << std::endl; + abort(); +} +#endif + +typedef double time_type; + +inline time_type get_time() +{ + return MPI_Wtime(); +} + +std::string print_time(time_type t) +{ + std::ostringstream out; + out << std::setiosflags(std::ios::fixed) << std::setprecision(2) << t; + return out.str(); +} + +using namespace boost; +using boost::graph::distributed::mpi_process_group; + +void +test_distributed_strong_components(int n, double _p, bool verify, bool emit_dot_file, int seed) +{ +#ifdef CSR + typedef compressed_sparse_row_graph<directedS, no_property, no_property, no_property, + distributedS<mpi_process_group> > Graph; +#else + typedef adjacency_list<listS, + distributedS<mpi_process_group, vecS>, + bidirectionalS > Graph; +#endif + + minstd_rand gen; + + gen.seed(seed); + + mpi_process_group pg; + parallel::variant_distribution<mpi_process_group> distrib + = parallel::block(pg, n); + +#ifdef CSR + Graph g(sorted_erdos_renyi_iterator<minstd_rand, Graph>(gen, n, _p/2), + sorted_erdos_renyi_iterator<minstd_rand, Graph>(), + n, pg, distrib); +#else + Graph g(erdos_renyi_iterator<minstd_rand, Graph>(gen, n, _p/2), + erdos_renyi_iterator<minstd_rand, Graph>(), + n, pg, distrib); +#endif + + synchronize(g); + + std::vector<int> local_components_vec(num_vertices(g)); + typedef iterator_property_map<std::vector<int>::iterator, property_map<Graph, vertex_index_t>::type> ComponentMap; + ComponentMap component(local_components_vec.begin(), get(vertex_index, g)); + + int num_components = 0; + + time_type start = get_time(); + num_components = strong_components(g, component); + time_type end = get_time(); + if (process_id(g.process_group()) == 0) + std::cerr << "Erdos-Reyni graph:\n" << n << " Vertices " << _p << " Edge probability " + << num_processes(pg) << " Processors\n" + << "Strong Components time = " << print_time(end - start) << " seconds.\n" + << num_components << " components identified\n"; + + + if ( verify ) + { + if ( process_id(g.process_group()) == 0 ) + { + for (int i = 0; i < n; ++i) + get(component, vertex(i, g)); + synchronize(component); + + // Check against the sequential version + typedef adjacency_list<listS, vecS, directedS> Graph2; + + gen.seed(seed); + + Graph2 g2(erdos_renyi_iterator<minstd_rand, Graph>(gen, n, _p/2), + erdos_renyi_iterator<minstd_rand, Graph>(), + n); + + std::vector<int> component2(n); + int seq_num_components = strong_components(g2, make_iterator_property_map(component2.begin(), get(vertex_index, g2))); + + assert(num_components == seq_num_components); + + // Make sure components and component2 match + std::map<int, int> c2c; + int i; + for ( i = 0; i < n; i++ ) + if ( c2c.find( get(component, vertex(i, g)) ) == c2c.end() ) + c2c[get(component, vertex(i, g))] = component2[i]; + else + if ( c2c[get(component, vertex(i, g))] != component2[i] ) + break; + + if ( i < n ) + std::cerr << "Unable to verify SCC result...\n"; + else + std::cerr << "Passed verification... " << seq_num_components << " strong components\n"; + } + else + { + synchronize(component); + } + if ( emit_dot_file ) + write_graphviz("scc.dot", g, paint_by_number(component)); + } +} + +int test_main(int argc, char* argv[]) +{ + mpi::environment env(argc, argv); + + if (argc == 1) + test_distributed_strong_components(10000, 0.0005, true, false, 1); + else if ( argc < 5 ) + std::cerr << "usage: test_distributed_strong_components <int num_vertices> <double p> <bool verify?> <bool emit_dotfile?> [seed]\n"; + else + test_distributed_strong_components + (atoi(argv[1]), atof(argv[2]), + argv[3]==std::string("true"), argv[4]==std::string("true"), + argc == 5? 1 : atoi(argv[5])); + + return 0; +} diff --git a/src/boost/libs/graph_parallel/test/hohberg_biconnected_components_test.cpp b/src/boost/libs/graph_parallel/test/hohberg_biconnected_components_test.cpp new file mode 100644 index 000000000..f0133300f --- /dev/null +++ b/src/boost/libs/graph_parallel/test/hohberg_biconnected_components_test.cpp @@ -0,0 +1,175 @@ +// Copyright (C) 2005-2008 The Trustees of Indiana University. + +// 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) + +// Authors: Douglas Gregor +// Andrew Lumsdaine +// +// Test of Hohberg's distributed biconnected components algorithm. +#include <boost/graph/use_mpi.hpp> +#include <boost/config.hpp> +#include <boost/throw_exception.hpp> +#include <boost/graph/distributed/hohberg_biconnected_components.hpp> +#include <boost/graph/distributed/mpi_process_group.hpp> +#include <boost/graph/distributed/adjacency_list.hpp> +#include <boost/test/minimal.hpp> + +#ifdef BOOST_NO_EXCEPTIONS +void +boost::throw_exception(std::exception const& ex) +{ + std::cout << ex.what() << std::endl; + abort(); +} +#endif + +using boost::graph::distributed::mpi_process_group; + +using namespace boost; + +template<typename Graph> +void check_components(const Graph& g, std::size_t num_comps) +{ + std::size_t not_mapped = (std::numeric_limits<std::size_t>::max)(); + std::vector<std::size_t> color_to_name(num_comps, not_mapped); + BGL_FORALL_EDGES_T(e, g, Graph) { + BOOST_CHECK(get(edge_color, g, e) < num_comps); + if (color_to_name[get(edge_color, g, e)] == not_mapped) + color_to_name[get(edge_color, g, e)] = get(edge_name, g, e); + BOOST_CHECK(color_to_name[get(edge_color,g,e)] == get(edge_name,g,e)); + + if (color_to_name[get(edge_color,g,e)] != get(edge_name,g,e)) { + for (std::size_t i = 0; i < color_to_name.size(); ++i) + std::cerr << color_to_name[i] << ' '; + + std::cerr << std::endl; + + std::cerr << color_to_name[get(edge_color,g,e)] << " != " + << get(edge_name,g,e) << " on edge " + << local(source(e, g)) << " -> " << local(target(e, g)) + << std::endl; + } + } +} + +template<typename Graph> +void +test_small_hohberg_biconnected_components(Graph& g, int n, int comps_expected, + bool single_component = true) +{ + using boost::graph::distributed::hohberg_biconnected_components; + + bool is_root = (process_id(process_group(g)) == 0); + + if (single_component) { + for (int i = 0; i < n; ++i) { + if (is_root) std::cerr << "Testing with leader = " << i << std::endl; + + // Scramble edge_color_map + BGL_FORALL_EDGES_T(e, g, Graph) + put(edge_color, g, e, 17); + + typename graph_traits<Graph>::vertex_descriptor leader = vertex(i, g); + int num_comps = + hohberg_biconnected_components(g, get(edge_color, g), &leader, + &leader + 1); + + BOOST_CHECK(num_comps == comps_expected); + check_components(g, num_comps); + } + } + + if (is_root) std::cerr << "Testing simple interface." << std::endl; + synchronize(g); + + // Scramble edge_color_map + int i = 0; + BGL_FORALL_EDGES_T(e, g, Graph) { + ++i; + put(edge_color, g, e, 17); + } + std::cerr << process_id(process_group(g)) << " has " + << i << " edges.\n"; + + int num_comps = hohberg_biconnected_components(g, get(edge_color, g)); + + BOOST_CHECK(num_comps == comps_expected); + check_components(g, num_comps); +} + +int test_main(int argc, char* argv[]) +{ + mpi::environment env(argc, argv); + + typedef adjacency_list<listS, + distributedS<mpi_process_group, vecS>, + undirectedS, + // Vertex properties + no_property, + // Edge properties + property<edge_name_t, std::size_t, + property<edge_color_t, std::size_t> > > Graph; + + typedef std::pair<int, int> E; + + { + // Example 1: A single component with 2 bicomponents + E edges_init[] = { E(0, 1), E(0, 2), E(1, 3), E(2, 4), E(3, 4), E(4, 5), + E(4, 6), E(5, 6) }; + const int m = sizeof(edges_init) / sizeof(E); + std::size_t expected_components[m] = { 0, 0, 0, 0, 0, 1, 1, 1 }; + const int n = 7; + Graph g(&edges_init[0], &edges_init[0] + m, &expected_components[0], n); + + int num_comps_expected = + *std::max_element(&expected_components[0], &expected_components[0] + m) + + 1; + + test_small_hohberg_biconnected_components(g, n, num_comps_expected); + } + + { + // Example 2: A single component with 4 bicomponents + E edges_init[] = { E(0, 1), E(1, 2), E(2, 0), E(2, 3), E(3, 4), E(4, 5), + E(5, 2), E(3, 6), E(6, 7), E(7, 8), E(8, 6) }; + const int m = sizeof(edges_init) / sizeof(E); + std::size_t expected_components[m] = { 0, 0, 0, 1, 1, 1, 1, 2, 3, 3, 3 }; + const int n = 9; + Graph g(&edges_init[0], &edges_init[0] + m, &expected_components[0], n); + + int num_comps_expected = + *std::max_element(&expected_components[0], &expected_components[0] + m) + + 1; + + test_small_hohberg_biconnected_components(g, n, num_comps_expected); + } + + { + // Example 3: Two components, 6 bicomponents + // This is just the concatenation of the two previous graphs. + E edges_init[] = { /* Example 1 graph */ + E(0, 1), E(0, 2), E(1, 3), E(2, 4), E(3, 4), E(4, 5), + E(4, 6), E(5, 6), + /* Example 2 graph */ + E(7, 8), E(8, 9), E(9, 7), E(9, 10), E(10, 11), + E(11, 12), E(12, 9), E(10, 13), E(13, 14), E(14, 15), + E(15, 13) }; + const int m = sizeof(edges_init) / sizeof(E); + std::size_t expected_components[m] = + { /* Example 1 */0, 0, 0, 0, 0, 1, 1, 1, + /* Example 2 */2, 2, 2, 3, 3, 3, 3, 4, 5, 5, 5 }; + const int n = 16; + Graph g(&edges_init[0], &edges_init[0] + m, &expected_components[0], n); + + int num_comps_expected = + *std::max_element(&expected_components[0], &expected_components[0] + m) + + 1; + + test_small_hohberg_biconnected_components(g, n, num_comps_expected, + false); + } + + return 0; +} diff --git a/src/boost/libs/graph_parallel/test/mesh_generator_test.cpp b/src/boost/libs/graph_parallel/test/mesh_generator_test.cpp new file mode 100644 index 000000000..160d1b504 --- /dev/null +++ b/src/boost/libs/graph_parallel/test/mesh_generator_test.cpp @@ -0,0 +1,133 @@ +// Copyright (C) 2004-2008 The Trustees of Indiana University. + +// 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) + +// Authors: Douglas Gregor +// Andrew Lumsdaine + +#include <boost/graph/use_mpi.hpp> +#include <boost/config.hpp> +#include <boost/throw_exception.hpp> +#include <boost/graph/mesh_graph_generator.hpp> +#include <boost/test/minimal.hpp> +#include <boost/graph/distributed/adjacency_list.hpp> +#include <boost/graph/distributed/mpi_process_group.hpp> +#include <boost/graph/distributed/graphviz.hpp> +#include <boost/graph/iteration_macros.hpp> +#include <iostream> +#include <sstream> +#include <iomanip> +#include <string> +#include <boost/test/minimal.hpp> + +#ifdef BOOST_NO_EXCEPTIONS +void +boost::throw_exception(std::exception const& ex) +{ + std::cout << ex.what() << std::endl; + abort(); +} +#endif + +using namespace boost; +using boost::graph::distributed::mpi_process_group; + +/**************************************************************************** + * Timing + ****************************************************************************/ +typedef double time_type; + +inline time_type get_time() +{ + return MPI_Wtime(); +} + +std::string print_time(time_type t) +{ + std::ostringstream out; + out << std::setiosflags(std::ios::fixed) << std::setprecision(2) << t; + return out.str(); +} + +/**************************************************************************** + * Edge weight generator iterator * + ****************************************************************************/ +template<typename F> +class generator_iterator +{ +public: + typedef std::input_iterator_tag iterator_category; + typedef typename F::result_type value_type; + typedef const value_type& reference; + typedef const value_type* pointer; + typedef void difference_type; + + explicit generator_iterator(const F& f = F()) : f(f) { value = this->f(); } + + reference operator*() const { return value; } + pointer operator->() const { return &value; } + + generator_iterator& operator++() + { + value = f(); + return *this; + } + + generator_iterator operator++(int) + { + generator_iterator temp(*this); + ++(*this); + return temp; + } + + bool operator==(const generator_iterator& other) const + { return f == other.f; } + + bool operator!=(const generator_iterator& other) const + { return !(*this == other); } + +private: + F f; + value_type value; +}; + +template<typename F> +inline generator_iterator<F> make_generator_iterator(const F& f) +{ return generator_iterator<F>(f); } + +int test_main(int argc, char* argv[]) +{ + mpi::environment env(argc, argv); + + if (argc < 5) { + std::cerr << "Usage: mesh_generator_test <x> <y> <toroidal> <emit dot file>\n"; + exit(-1); + } + + int x(atoi(argv[1])), y(atoi(argv[2])); + bool toroidal(argv[3] == std::string("true")); + bool emit_dot_file(argv[4] == std::string("true")); + + typedef adjacency_list<listS, + distributedS<mpi_process_group, vecS>, + undirectedS> Graph; + + Graph g(mesh_iterator<Graph>(x, y, toroidal), + mesh_iterator<Graph>(), + x*y); + + synchronize(g); + + BGL_FORALL_VERTICES(v, g, Graph) + if (toroidal) + assert(out_degree(v, g) == 4); + else + assert(out_degree(v, g) >= 2 && out_degree(v, g) <= 4); + + if ( emit_dot_file ) + write_graphviz("mesh.dot", g); + + return 0; +} diff --git a/src/boost/libs/graph_parallel/test/named_vertices_hash_test.cpp b/src/boost/libs/graph_parallel/test/named_vertices_hash_test.cpp new file mode 100644 index 000000000..c859a9a6e --- /dev/null +++ b/src/boost/libs/graph_parallel/test/named_vertices_hash_test.cpp @@ -0,0 +1,158 @@ +// Copyright (C) 2007-2008 The Trustees of Indiana University. + +// 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/mpl/print.hpp> +#include <boost/graph/distributed/adjacency_list.hpp> +#include <boost/graph/distributed/mpi_process_group.hpp> +#include <boost/graph/iteration_macros.hpp> +#include <boost/test/minimal.hpp> +#include <string> +#include <iostream> + +#ifdef BOOST_NO_EXCEPTIONS +void +boost::throw_exception(std::exception const& ex) +{ + std::cout << ex.what() << std::endl; + abort(); +} +#endif + +using namespace boost; +using boost::graph::distributed::mpi_process_group; + +/// City structure to be attached to each vertex +struct City { + City() {} + + City(const std::string& name, int population = -1) + : name(name), population(population) { } + + template<typename Archiver> + void serialize(Archiver& ar, const unsigned int /*version*/) + { + ar & name & population; + } + + std::string name; + int population; +}; + +/// Our distribution function +template<typename T> +struct named_vertices_hashed_distribution +{ + template<typename ProcessGroup> + named_vertices_hashed_distribution(const ProcessGroup& pg, + std::size_t /*num_vertices*/ = 0) + : n(num_processes(pg)) { } + + int operator()(const T& value) const + { + return hasher(value) % n; + } + + std::size_t n; + boost::hash<T> hasher; +}; + +typedef named_vertices_hashed_distribution<std::string> hasher_type; + +namespace boost { namespace graph { + +/// Use the City name as a key for indexing cities in a graph +template<> +struct internal_vertex_name<City> +{ + typedef multi_index::member<City, std::string, &City::name> type; +}; + +/// Allow the graph to build cities given only their names (filling in +/// the defaults for fields). +template<> +struct internal_vertex_constructor<City> +{ + typedef vertex_from_name<City> type; +}; + +// namespace distributed +// { +// /// Use the City name as the source for the distribution hasher +// /// +// /// This is currently needed in addition to the specification of this +// /// hasher functor as the 3rd template parameter to the distributedS +// /// template. +// template<> +// struct internal_vertex_name_distribution<City> +// { +// typedef named_vertices_hashed_distribution<std::string> type; +// }; +// } + +} } // end namespace boost::graph + +/// Our road map, where each of the vertices are cities +typedef boost::adjacency_list<vecS, + distributedS<mpi_process_group, vecS, hasher_type>, + bidirectionalS, City> RoadMap; +typedef graph_traits<RoadMap>::vertex_descriptor Vertex; + +int test_main(int argc, char** argv) +{ + boost::mpi::environment env(argc, argv); + + mpi_process_group pg; + RoadMap map; // (pg, hasher_type(pg)); + + int rank = process_id(pg); + bool i_am_root = rank == 0; + + /// Create vertices for Bloomington, Indianapolis, Chicago. Everyone will + /// try to do this, but only one of each vertex will be added. + Vertex bloomington = add_vertex(City("Bloomington", 69291), map); + Vertex chicago = add_vertex(City("Chicago", 9500000), map); + Vertex indianapolis = add_vertex(City("Indianapolis", 791926), map); + + BGL_FORALL_VERTICES(city, map, RoadMap) + std::cout << rank << ": " << map[city].name << ", population " + << map[city].population << std::endl; + + BOOST_CHECK(*find_vertex("Bloomington", map) == bloomington); + BOOST_CHECK(*find_vertex("Indianapolis", map) == indianapolis); + BOOST_CHECK(*find_vertex("Chicago", map) == chicago); + + if (i_am_root) { + add_edge(bloomington, "Indianapolis", map); + add_edge("Indianapolis", chicago, map); + add_edge("Indianapolis", "Cincinnati", map); + } + + synchronize(map); + + { + property_map<RoadMap, std::string City::*>::type + city_name = get(&City::name, map); + + BGL_FORALL_EDGES(road, map, RoadMap) + std::cout << rank << ": " << get(city_name, source(road, map)) << " -> " + << get(city_name, target(road, map)) << std::endl; + + synchronize(map); + } + + // Make sure the vertex for "Cincinnati" was created implicitly + Vertex cincinnati = *find_vertex("Cincinnati", map); + if (get(get(vertex_owner, map), cincinnati) + == process_id(map.process_group())) + BOOST_CHECK(map[cincinnati].population == -1); + + synchronize(map); + + return 0; +} diff --git a/src/boost/libs/graph_parallel/test/named_vertices_seq.cpp b/src/boost/libs/graph_parallel/test/named_vertices_seq.cpp new file mode 100644 index 000000000..219214c01 --- /dev/null +++ b/src/boost/libs/graph_parallel/test/named_vertices_seq.cpp @@ -0,0 +1,91 @@ +// Copyright (C) 2007-2008 The Trustees of Indiana University. + +// 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/test/minimal.hpp> +#include <boost/graph/adjacency_list.hpp> +#include <boost/graph/iteration_macros.hpp> +#include <string> +#include <iostream> + +#ifdef BOOST_NO_EXCEPTIONS +void +boost::throw_exception(std::exception const& ex) +{ + std::cout << ex.what() << std::endl; + abort(); +} +#endif + +using namespace boost; + +/// City structure to be attached to each vertex +struct City { + City() {} + + City(const std::string& name, int population = -1) + : name(name), population(population) { } + + std::string name; + int population; +}; + +namespace boost { namespace graph { + +/// Use the City name as a key for indexing cities in a graph +template<> +struct internal_vertex_name<City> +{ + typedef multi_index::member<City, std::string, &City::name> type; +}; + +/// Allow the graph to build cities given only their names (filling in +/// the defaults for fields). +template<> +struct internal_vertex_constructor<City> +{ + typedef vertex_from_name<City> type; +}; + +} } // end namespace boost::graph + +/// Our road map, where each of the vertices are cities +typedef adjacency_list<vecS, vecS, directedS, City> RoadMap; +typedef graph_traits<RoadMap>::vertex_descriptor Vertex; + +int test_main(int argc, char* argv[]) +{ + RoadMap map; + + /// Create vertices for Bloomington, Indianapolis, Chicago + Vertex bloomington = add_vertex(City("Bloomington", 69291), map); + Vertex indianapolis = add_vertex(City("Indianapolis", 791926), map); + Vertex chicago = add_vertex(City("Chicago", 9500000), map); + + BOOST_CHECK(add_vertex(City("Bloomington", 69291), map) == bloomington); + + BGL_FORALL_VERTICES(city, map, RoadMap) + std::cout << map[city].name << ", population " << map[city].population + << std::endl; + + BOOST_CHECK(*find_vertex("Bloomington", map) == bloomington); + BOOST_CHECK(*find_vertex("Indianapolis", map) == indianapolis); + BOOST_CHECK(*find_vertex("Chicago", map) == chicago); + + add_edge(bloomington, "Indianapolis", map); + add_edge("Indianapolis", chicago, map); + add_edge("Indianapolis", "Cincinnati", map); + + BGL_FORALL_EDGES(road, map, RoadMap) + std::cout << map[source(road, map)].name << " -> " + << map[target(road, map)].name << std::endl; + + BOOST_CHECK(map[*find_vertex("Cincinnati", map)].population == -1); + + return 0; +} diff --git a/src/boost/libs/graph_parallel/test/named_vertices_test.cpp b/src/boost/libs/graph_parallel/test/named_vertices_test.cpp new file mode 100644 index 000000000..a5d7b2732 --- /dev/null +++ b/src/boost/libs/graph_parallel/test/named_vertices_test.cpp @@ -0,0 +1,121 @@ +// Copyright (C) 2007 The Trustees of Indiana University. + +// 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/graph/iteration_macros.hpp> +#include <boost/test/minimal.hpp> +#include <string> +#include <iostream> + +#ifdef BOOST_NO_EXCEPTIONS +void +boost::throw_exception(std::exception const& ex) +{ + std::cout << ex.what() << std::endl; + abort(); +} +#endif + +using namespace boost; +using boost::graph::distributed::mpi_process_group; + +/// City structure to be attached to each vertex +struct City { + City() {} + + City(const std::string& name, int population = -1) + : name(name), population(population) { } + + template<typename Archiver> + void serialize(Archiver& ar, const unsigned int /*version*/) + { + ar & name & population; + } + + std::string name; + int population; +}; + +namespace boost { namespace graph { + +/// Use the City name as a key for indexing cities in a graph +template<> +struct internal_vertex_name<City> +{ + typedef multi_index::member<City, std::string, &City::name> type; +}; + +/// Allow the graph to build cities given only their names (filling in +/// the defaults for fields). +template<> +struct internal_vertex_constructor<City> +{ + typedef vertex_from_name<City> type; +}; + +} } // end namespace boost::graph + +/// Our road map, where each of the vertices are cities +typedef boost::adjacency_list<vecS, distributedS<mpi_process_group, vecS>, + bidirectionalS, City> RoadMap; +typedef graph_traits<RoadMap>::vertex_descriptor Vertex; + +int test_main(int argc, char** argv) +{ + boost::mpi::environment env(argc, argv); + + RoadMap map; + + int rank = process_id(mpi_process_group()); + bool i_am_root = rank == 0; + + /// Create vertices for Bloomington, Indianapolis, Chicago. Everyone will + /// try to do this, but only one of each vertex will be added. + Vertex bloomington = add_vertex(City("Bloomington", 69291), map); + Vertex chicago = add_vertex(City("Chicago", 9500000), map); + Vertex indianapolis = add_vertex(City("Indianapolis", 791926), map); + + BGL_FORALL_VERTICES(city, map, RoadMap) + std::cout << rank << ": " << map[city].name << ", population " + << map[city].population << std::endl; + + BOOST_CHECK(*find_vertex("Bloomington", map) == bloomington); + BOOST_CHECK(*find_vertex("Indianapolis", map) == indianapolis); + BOOST_CHECK(*find_vertex("Chicago", map) == chicago); + + if (i_am_root) { + add_edge(bloomington, "Indianapolis", map); + add_edge("Indianapolis", chicago, map); + add_edge("Indianapolis", "Cincinnati", map); + } + + synchronize(map); + + { + property_map<RoadMap, std::string City::*>::type + city_name = get(&City::name, map); + + BGL_FORALL_EDGES(road, map, RoadMap) + std::cout << rank << ": " << get(city_name, source(road, map)) << " -> " + << get(city_name, target(road, map)) << std::endl; + + synchronize(map); + } + + // Make sure the vertex for "Cincinnati" was created implicitly + Vertex cincinnati = *find_vertex("Cincinnati", map); + if (get(vertex_owner, map, cincinnati) + == process_id(map.process_group())) + BOOST_CHECK(map[cincinnati].population == -1); + + synchronize(map); + + return 0; +} diff --git a/src/boost/libs/graph_parallel/test/process_group_serialization.cpp b/src/boost/libs/graph_parallel/test/process_group_serialization.cpp new file mode 100644 index 000000000..807007510 --- /dev/null +++ b/src/boost/libs/graph_parallel/test/process_group_serialization.cpp @@ -0,0 +1,58 @@ +// Copyright (C) 2006 The Trustees of Indiana University. + +// 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) + +// Authors: Douglas Gregor +// Andrew Lumsdaine + +// FIXME: Including because of a missing header in the serialization library. +// Patch sent to list... +#include <cassert> + +#include <boost/graph/use_mpi.hpp> +#include <boost/config.hpp> +#include <boost/throw_exception.hpp> +#include <boost/serialization/list.hpp> +#include <boost/graph/distributed/mpi_process_group.hpp> +#include <boost/test/minimal.hpp> + +#ifdef BOOST_NO_EXCEPTIONS +void +boost::throw_exception(std::exception const& ex) +{ + std::cout << ex.what() << std::endl; + abort(); +} +#endif + +using boost::graph::distributed::mpi_process_group; + +int test_main(int argc, char** argv) +{ + boost::mpi::environment env(argc, argv); + + mpi_process_group pg; + + int seventeen = 17; + std::list<int> seventeens(17, 17); + + if (process_id(pg) == 0) { + send(pg, 1, 0, seventeen); + send(pg, 1, 1, seventeens); + } + synchronize(pg); + + if (process_id(pg) == 1) { + int value; + receive(pg, 0, 0, value); + BOOST_CHECK(seventeen == value); + + std::list<int> values; + receive(pg, 0, 1, values); + BOOST_CHECK(seventeens == values); + } + + return 0; +} diff --git a/src/boost/libs/graph_parallel/test/ssca.cpp b/src/boost/libs/graph_parallel/test/ssca.cpp new file mode 100644 index 000000000..0930e4d0f --- /dev/null +++ b/src/boost/libs/graph_parallel/test/ssca.cpp @@ -0,0 +1,1263 @@ +// Copyright 2004 The Trustees of Indiana University. + +// 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) + +// Authors: Nick Edmonds +// Andrew Lumsdaine + +#include <boost/graph/use_mpi.hpp> + +#define CSR + +#ifdef CSR +# include <boost/graph/distributed/compressed_sparse_row_graph.hpp> +#else +# include <boost/graph/distributed/adjacency_list.hpp> +#endif + +#include <boost/test/minimal.hpp> +#include <boost/graph/distributed/mpi_process_group.hpp> +#include <boost/graph/distributed/queue.hpp> + +#include <boost/graph/parallel/distribution.hpp> +#include <boost/lexical_cast.hpp> +#include <boost/bind.hpp> +#include <sys/time.h> +#include <time.h> + +#include <boost/random.hpp> +#include <boost/property_map/parallel/distributed_property_map.hpp> + +#include <boost/random/linear_congruential.hpp> + +#include <boost/graph/distributed/graphviz.hpp> +#include <boost/graph/graph_traits.hpp> +#include <boost/graph/iteration_macros.hpp> + +#include <boost/graph/parallel/algorithm.hpp> +#include <boost/graph/breadth_first_search.hpp> +#include <boost/pending/queue.hpp> + +#include <boost/graph/rmat_graph_generator.hpp> +#include <boost/graph/distributed/betweenness_centrality.hpp> +#include <boost/graph/distributed/filtered_graph.hpp> +#include <boost/graph/parallel/container_traits.hpp> + +#include <boost/graph/properties.hpp> + +#include <algorithm> +#include <vector> +#include <string> +#include <iostream> +#include <iomanip> +#include <fstream> +#include <string> +#include <sstream> +#include <stdint.h> + +using namespace boost; + +// #define DEBUG + +typedef rand48 RandomGenerator; + +/**************************************************************************** + * Timing + ****************************************************************************/ +#ifndef PBGL_ACCOUNTING + +typedef double time_type; + +inline time_type get_time() +{ + timeval tp; + gettimeofday(&tp, 0); + return tp.tv_sec + tp.tv_usec / 1000000.0; +} + +std::string print_time(time_type t) +{ + std::ostringstream out; + out << std::setiosflags(std::ios::fixed) << std::setprecision(2) << t; + return out.str(); +} + +#endif // PBGL_ACCOUNTING + +/**************************************************************************** + * Edge weight generator iterator * + ****************************************************************************/ +template<typename F, typename RandomGenerator> +class generator_iterator +{ +public: + typedef std::input_iterator_tag iterator_category; + typedef typename F::result_type value_type; + typedef const value_type& reference; + typedef const value_type* pointer; + typedef void difference_type; + + explicit + generator_iterator(RandomGenerator& gen, const F& f = F()) + : f(f), gen(&gen) + { + value = this->f(gen); + } + + reference operator*() const { return value; } + pointer operator->() const { return &value; } + + generator_iterator& operator++() + { + value = f(*gen); + return *this; + } + + generator_iterator operator++(int) + { + generator_iterator temp(*this); + ++(*this); + return temp; + } + + bool operator==(const generator_iterator& other) const + { return f == other.f; } + + bool operator!=(const generator_iterator& other) const + { return !(*this == other); } + +private: + F f; + RandomGenerator* gen; + value_type value; +}; + +template<typename F, typename RandomGenerator> +inline generator_iterator<F, RandomGenerator> +make_generator_iterator( RandomGenerator& gen, const F& f) +{ return generator_iterator<F, RandomGenerator>(gen, f); } + +template<typename Graph, typename DistanceMap, typename WeightMap, typename ColorMap> +struct ssca_visitor : bfs_visitor<> +{ + typedef typename property_traits<WeightMap>::value_type Weight; + typedef typename property_traits<ColorMap>::value_type ColorValue; + typedef color_traits<ColorValue> Color; + + ssca_visitor(DistanceMap& distance, const WeightMap& weight, ColorMap& color, + Weight max_) + : distance(distance), weight(weight), color(color), max_(max_) {} + + template<typename Edge> + void tree_edge(Edge e, const Graph& g) + { + int new_distance = get(weight, e) == (std::numeric_limits<Weight>::max)() ? + (std::numeric_limits<Weight>::max)() : get(distance, source(e, g)) + get(weight, e); + + put(distance, target(e, g), new_distance); + if (new_distance > max_) + put(color, target(e, g), Color::black()); + } + + private: + DistanceMap& distance; + const WeightMap& weight; + ColorMap& color; + Weight max_; +}; + +// Generate source vertices for approximate BC +template <typename Graph, typename Buffer> +void +generate_sources(const Graph& g, Buffer sources, + typename graph_traits<Graph>::vertices_size_type num_sources) +{ + typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor; + typedef typename graph_traits<Graph>::vertices_size_type vertices_size_type; + typedef typename graph_traits<Graph>::vertex_iterator vertex_iterator; + + typedef typename boost::graph::parallel::process_group_type<Graph>::type + process_group_type; + process_group_type pg = g.process_group(); + + typename process_group_type::process_id_type id = process_id(pg); + typename process_group_type::process_size_type p = num_processes(pg); + + // Don't feel like adding a special case for num_sources < p + assert(num_sources >= p); + + minstd_rand gen; + uniform_int<vertices_size_type> rand_vertex(0, num_vertices(g) - 1); + std::vector<vertex_descriptor> all_sources, local_sources; + vertices_size_type local_vertices = vertices_size_type(floor((double)num_sources / p)); + local_vertices += (id < (num_sources - (p * local_vertices)) ? 1 : 0); + + while (local_vertices > 0) { + vertex_iterator iter = vertices(g).first; + std::advance(iter, rand_vertex(gen)); + + if (out_degree(*iter, g) != 0 + && std::find(local_sources.begin(), local_sources.end(), *iter) == local_sources.end()) { + local_sources.push_back(*iter); + --local_vertices; + } + } + all_gather(pg, local_sources.begin(), local_sources.end(), all_sources); + std::sort(all_sources.begin(), all_sources.end()); + for (typename std::vector<vertex_descriptor>::iterator iter = all_sources.begin(); + iter != all_sources.end(); ++iter) + sources.push(*iter); +} + +// Kernel 2 - Classify large sets +template <typename Graph, typename WeightMap> +void classify_sets(const Graph& g, const WeightMap& weight_map, + std::vector<std::pair<typename graph_traits<Graph>::vertex_descriptor, + typename graph_traits<Graph>::vertex_descriptor> > & global_S) +{ + typedef typename boost::graph::parallel::process_group_type<Graph>::type + process_group_type; + process_group_type pg = g.process_group(); + + typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor; + std::vector<std::pair<vertex_descriptor, vertex_descriptor> > S; + + time_type start = get_time(); + +#ifdef CSR + typedef typename property_map<Graph, vertex_owner_t>::const_type OwnerMap; + typedef typename property_map<Graph, vertex_local_t>::const_type LocalMap; + OwnerMap owner = get(vertex_owner, g); + LocalMap local = get(vertex_local, g); +#endif + + int max_ = 0; + BGL_FORALL_EDGES_T(e, g, Graph) { +#ifdef CSR + if (get(owner, source(e, g)) == process_id(pg)) { +#endif + int w = get(weight_map, e); + if (w > max_) { + max_ = w; + S.clear(); + } + + if (w >= max_) + S.push_back(std::make_pair(source(e, g), target(e, g))); +#ifdef CSR + } +#endif + } + + int global_max = all_reduce(pg, max_, boost::parallel::maximum<int>()); + if (max_ < global_max) + S.clear(); + + global_S.clear(); + + all_gather(pg, S.begin(), S.end(), global_S); + + // This is probably unnecessary as long as the sets of edges owned by procs is disjoint + std::sort(global_S.begin(), global_S.end()); + std::unique(global_S.begin(), global_S.end()); + + synchronize(pg); + + time_type end = get_time(); + + if (process_id(pg) == 0) { + std::cerr << " Distributed Graph: " << print_time(end - start) << std::endl + << " Max int weight = " << global_max << std::endl; + } +} + +template <typename ProcessGroup, typename Graph, typename WeightMap, + typename EdgeVector> +void seq_classify_sets(const ProcessGroup& pg, const Graph& g, + const WeightMap& weight_map, EdgeVector& S) +{ + typedef typename graph_traits<Graph>::edge_descriptor edge_descriptor; + typedef typename property_traits<WeightMap>::value_type edge_weight_type; + + time_type start = get_time(); + + edge_weight_type max_ = 0; + BGL_FORALL_EDGES_T(e, g, Graph) { + edge_weight_type w = get(weight_map, e); + if (w > max_) { + max_ = w; + S.clear(); + } + + if (w >= max_) + S.push_back(e); + } + + synchronize(pg); + + time_type end = get_time(); + + if (process_id(pg) == 0) + std::cerr << " Non-Distributed Graph: " << print_time(end - start) << std::endl + << " Max int weight = " << max_ << std::endl; +} + +// Kernel 3 - Graph Extraction +template <typename Graph, typename OwnerMap, typename LocalMap, + typename WeightMap, typename DistanceMap, typename ColorMap, + typename EdgeVector> +void subgraph_extraction(Graph& g, const OwnerMap& owner, const LocalMap& local, + const WeightMap& weight_map, DistanceMap distances, + ColorMap color_map, const EdgeVector& S, + int subGraphEdgeLength) +{ + // Nick: I think turning the vertex black when the maximum distance is + // exceeded will prevent BFS from exploring beyond the subgraph. + // Unfortunately we can't run subgraph extraction in parallel + // because the subgraphs may overlap + + typedef typename property_traits<ColorMap>::value_type ColorValue; + typedef color_traits<ColorValue> Color; + + typedef typename graph_traits<Graph>::edge_descriptor edge_descriptor; + typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor; + + typedef typename boost::graph::parallel::process_group_type<Graph>::type + process_group_type; + + typedef boost::graph::distributed::distributed_queue<process_group_type, + OwnerMap, queue<vertex_descriptor> > queue_t; + + process_group_type pg = g.process_group(); + typename process_group_type::process_id_type id = process_id(pg); + + queue_t Q(pg, owner); + + EdgeVector sources(S.begin(), S.end()); + +#ifdef DEBUG + std::vector<std::vector<vertex_descriptor> > subgraphs; +#endif + + synchronize(pg); + + typedef typename std::vector<std::pair<vertex_descriptor, vertex_descriptor> >::iterator + source_iterator; + + time_type start = get_time(); + for (source_iterator iter = sources.begin(); iter != sources.end(); ++iter) { + // Reinitialize distance and color maps every BFS + BGL_FORALL_VERTICES_T(v, g, Graph) { + if (get(owner, v) == id) { + local_put(color_map, v, Color::white()); + local_put(distances, v, (std::numeric_limits<int>::max)()); + } + } + + vertex_descriptor u = iter->first, v = iter->second; + + local_put(distances, u, 0); + local_put(distances, v, 0); + + while (!Q.empty()) Q.pop(); + if (get(owner, u) == id) + Q.push(u); + + local_put(color_map, u, Color::gray()); + + breadth_first_search(g, v, Q, + ssca_visitor<Graph, DistanceMap, WeightMap, ColorMap> + (distances, weight_map, color_map, subGraphEdgeLength), + color_map); + + // At this point all vertices with distance > 0 in addition to the + // starting vertices compose the subgraph. +#ifdef DEBUG + subgraphs.push_back(std::vector<vertex_descriptor>()); + std::vector<vertex_descriptor>& subgraph = subgraphs.back(); + + BGL_FORALL_VERTICES_T(v, g, Graph) { + if (get(distances, v) < (std::numeric_limits<int>::max)()) + subgraph.push_back(v); + } +#endif + } + + synchronize(pg); + + time_type end = get_time(); + +#ifdef DEBUG + for (unsigned int i = 0; i < subgraphs.size(); i++) { + all_gather(pg, subgraphs[i].begin(), subgraphs[i].end(), subgraphs[i]); + std::sort(subgraphs[i].begin(), subgraphs[i].end()); + subgraphs[i].erase(std::unique(subgraphs[i].begin(), subgraphs[i].end()), + subgraphs[i].end()); + } + + if (process_id(pg) == 0) + for (int i = 0; abs(i) < subgraphs.size(); i++) { + std::cerr << "Subgraph " << i << " :\n"; + for (int j = 0; abs(j) < subgraphs[i].size(); j++) + std::cerr << " " << get(local, subgraphs[i][j]) << "@" + << get(owner, subgraphs[i][j]) << std::endl; + } +#endif + + if (process_id(pg) == 0) + std::cerr << " Distributed Graph: " << print_time(end - start) << std::endl; +} + +template <typename ProcessGroup, typename Graph, typename WeightMap, + typename DistanceMap, typename ColorMap, typename EdgeVector> +void seq_subgraph_extraction(const ProcessGroup& pg, const Graph& g, + const WeightMap& weight_map, DistanceMap distances, + ColorMap color_map, const EdgeVector& S, + int subGraphEdgeLength) +{ + // Nick: I think turning the vertex black when the maximum distance is + // exceeded will prevent BFS from exploring beyond the subgraph. + + using boost::graph::distributed::mpi_process_group; + + typedef typename property_traits<ColorMap>::value_type ColorValue; + typedef color_traits<ColorValue> Color; + + typedef typename graph_traits<Graph>::edge_descriptor edge_descriptor; + typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor; + + boost::queue<vertex_descriptor> Q; + + std::vector<edge_descriptor> sources(S.begin(), S.end()); + +#ifdef DEBUG + std::vector<std::vector<vertex_descriptor> > subgraphs; +#endif + + synchronize(pg); + + typedef ProcessGroup process_group_type; + + typename process_group_type::process_id_type id = process_id(pg); + typename process_group_type::process_size_type p = num_processes(pg); + + time_type start = get_time(); + + for (int i = id; i < sources.size(); i += p) { + + // Reinitialize distance and color maps every BFS + BGL_FORALL_VERTICES_T(v, g, Graph) { + put(color_map, v, Color::white()); + put(distances, v, (std::numeric_limits<int>::max)()); + } + + vertex_descriptor u = source(sources[i], g), + v = target(sources[i], g); + + put(distances, u, 0); + put(distances, v, 0); + + while (!Q.empty()) Q.pop(); + Q.push(u); + + put(color_map, u, Color::gray()); + + breadth_first_search(g, v, Q, + ssca_visitor<Graph, DistanceMap, WeightMap, ColorMap> + (distances, weight_map, color_map, subGraphEdgeLength), + color_map); + +#ifdef DEBUG + subgraphs.push_back(std::vector<vertex_descriptor>()); + std::vector<vertex_descriptor>& subgraph = subgraphs.back(); + + BGL_FORALL_VERTICES_T(v, g, Graph) { + if (get(distances, v) < (std::numeric_limits<int>::max)()) + subgraph.push_back(v); + } +#endif + } + + synchronize(pg); + + time_type end = get_time(); + +#ifdef DEBUG + std::vector<vertex_descriptor> ser_subgraphs; + + for (int i = 0; i < subgraphs.size(); ++i) { + for (int j = 0; j < subgraphs[i].size(); ++j) + ser_subgraphs.push_back(subgraphs[i][j]); + ser_subgraphs.push_back(graph_traits<Graph>::null_vertex()); + } + + all_gather(pg, ser_subgraphs.begin(), ser_subgraphs.end(), ser_subgraphs); + + int i = 0; + typename std::vector<vertex_descriptor>::iterator iter(ser_subgraphs.begin()); + + while (iter != ser_subgraphs.end()) { + std::cerr << "Subgraph " << i << " :\n"; + while (*iter != graph_traits<Graph>::null_vertex()) { + std::cerr << " " << *iter << std::endl; + ++iter; + } + ++i; + ++iter; + } +#endif + + if (process_id(pg) == 0) + std::cerr << " Non-Distributed Graph: " << print_time(end - start) << std::endl; +} + +template <typename ProcessGroup, typename Graph, typename CentralityMap> +void +extract_max_bc_vertices(const ProcessGroup& pg, const Graph& g, const CentralityMap& centrality, + std::vector<typename graph_traits<Graph>::vertex_descriptor>& max_bc_vec) +{ + using boost::graph::parallel::process_group; + using boost::parallel::all_gather; + using boost::parallel::all_reduce; + + // Find set of vertices with highest BC score + typedef typename property_traits<CentralityMap>::value_type centrality_type; + std::vector<centrality_type> max_bc_vertices; + centrality_type max_ = 0; + + max_bc_vec.clear(); + + BGL_FORALL_VERTICES_T(v, g, Graph) { + if (get(centrality, v) == max_) + max_bc_vec.push_back(v); + else if (get(centrality, v) > max_) { + max_ = get(centrality, v); + max_bc_vec.clear(); + max_bc_vec.push_back(v); + } + } + + centrality_type global_max = all_reduce(pg, max_, boost::parallel::minimum<int>()); + + if (global_max > max_) + max_bc_vec.clear(); + + all_gather(pg, max_bc_vec.begin(), max_bc_vec.end(), max_bc_vec); +} + + +// Function object to filter edges divisible by 8 +// EdgeWeightMap::value_type must be integral! +template <typename EdgeWeightMap> +struct edge_weight_not_divisible_by_eight { + typedef typename property_traits<EdgeWeightMap>::value_type weight_type; + + edge_weight_not_divisible_by_eight() { } + edge_weight_not_divisible_by_eight(EdgeWeightMap weight) : m_weight(weight) { } + template <typename Edge> + bool operator()(const Edge& e) const { + return (get(m_weight, e) & ((std::numeric_limits<weight_type>::max)() - 7)) != get(m_weight, e); + } + + EdgeWeightMap m_weight; +}; + +// +// Vertex and Edge properties +// +#ifdef CSR +typedef int weight_type; + +struct WeightedEdge { + WeightedEdge(weight_type weight = 0) : weight(weight) { } + + weight_type weight; +}; + +struct VertexProperties { + VertexProperties(int distance = 0, default_color_type color = white_color) + : distance(distance), color(color) { } + + int distance; + default_color_type color; +}; +#endif + +template <typename RandomGenerator, typename ProcessGroup, typename vertices_size_type, + typename edges_size_type> +void +run_non_distributed_graph_tests(RandomGenerator& gen, const ProcessGroup& pg, + vertices_size_type n, edges_size_type m, + std::size_t maxEdgeWeight, uint64_t seed, + int K4Alpha, double a, double b, double c, double d, + int subGraphEdgeLength, bool show_degree_dist, + bool full_bc, bool verify) +{ +#ifdef CSR + typedef compressed_sparse_row_graph<directedS, VertexProperties, WeightedEdge> + seqGraph; +#else + typedef adjacency_list<vecS, vecS, directedS, + // Vertex properties + property<vertex_distance_t, int, + property<vertex_color_t, default_color_type> >, + // Edge properties + property<edge_weight_t, int> > seqGraph; +#endif + + // Generate sequential graph for non_distributed betweenness centrality + // Reseed the PRNG to get the same graph + gen.seed(seed); + + synchronize(pg); + + time_type start = get_time(); + +#ifdef CSR + seqGraph sg(edges_are_sorted, + sorted_unique_rmat_iterator<RandomGenerator, seqGraph>(gen, n, m, a, b, c, d), + sorted_unique_rmat_iterator<RandomGenerator, seqGraph>(), + make_generator_iterator(gen, uniform_int<int>(0, maxEdgeWeight)), + n); +#else + seqGraph sg(unique_rmat_iterator<RandomGenerator, seqGraph>(gen, n, m, a, b, c, d), + unique_rmat_iterator<RandomGenerator, seqGraph>(), + make_generator_iterator(gen, uniform_int<int>(0, maxEdgeWeight)), + n); +#endif + + // Not strictly necessary to synchronize here, but it make sure that the + // time we measure is the time needed for all copies of the graph to be + // constructed + synchronize(pg); + + time_type end = get_time(); + + if (process_id(pg) == 0) + std::cerr<< "Kernel 1:\n" + << " Non-Distributed Graph: " << print_time(end - start) << std::endl; + + std::map<int, int> degree_dist; + if ( show_degree_dist ) { + BGL_FORALL_VERTICES_T(v, sg, seqGraph) { + degree_dist[out_degree(v, sg)]++; + } + + std::cerr << "Degree - Fraction of vertices of that degree\n"; + for (std::map<int, int>::iterator iter = degree_dist.begin(); + iter != degree_dist.end(); ++iter) + std::cerr << " " << iter->first << " - " << double(iter->second) / num_vertices(sg) << std::endl << std::endl; + } + + // + // Kernel 2 - Classify large sets + // + std::vector<graph_traits<seqGraph>::edge_descriptor> seqS; + + if (process_id(pg) == 0) + std::cerr << "Kernel 2:\n"; + + seq_classify_sets(pg, sg, +#ifdef CSR + get(&WeightedEdge::weight, sg), +#else + get(edge_weight, sg), +#endif + seqS); + + // + // Kernel 3 - Graph Extraction + // +#ifdef CSR + typedef weight_type weight_t; + weight_t unit_weight(1); +#else + int unit_weight(1);; +#endif + + if (process_id(pg) == 0) + std::cerr << "Kernel 3:\n"; + + seq_subgraph_extraction(pg, sg, +#ifdef CSR +// get(&WeightedEdge::weight, sg), + ref_property_map<graph_traits<seqGraph>::edge_descriptor, weight_t>(unit_weight), + get(&VertexProperties::distance, sg), + get(&VertexProperties::color, sg), +#else +// get(edge_weight, sg), + ref_property_map<graph_traits<seqGraph>::edge_descriptor, int>(unit_weight), + get(vertex_distance, sg), + get(vertex_color, sg), +#endif + seqS, subGraphEdgeLength); + +#ifdef CSR + typedef property_map<seqGraph, weight_type WeightedEdge::*>::type seqEdgeWeightMap; + edge_weight_not_divisible_by_eight<seqEdgeWeightMap> sg_filter(get(&WeightedEdge::weight, sg)); +#else + typedef property_map<seqGraph, edge_weight_t>::type seqEdgeWeightMap; + edge_weight_not_divisible_by_eight<seqEdgeWeightMap> sg_filter(get(edge_weight, sg)); +#endif + + typedef filtered_graph<const seqGraph, edge_weight_not_divisible_by_eight<seqEdgeWeightMap> > + filteredSeqGraph; + + filteredSeqGraph fsg(sg, sg_filter); + + std::vector<graph_traits<seqGraph>::vertex_descriptor> max_seq_bc_vec; + + // Non-Distributed Centrality Map + typedef property_map<seqGraph, vertex_index_t>::const_type seqIndexMap; + typedef iterator_property_map<std::vector<int>::iterator, seqIndexMap> seqCentralityMap; + + std::vector<int> non_distributed_centralityS(num_vertices(sg), 0); + seqCentralityMap non_distributed_centrality(non_distributed_centralityS.begin(), + get(vertex_index, sg)); + + vertices_size_type n0 = 0; + BGL_FORALL_VERTICES_T(v, fsg, filteredSeqGraph) { + if (out_degree(v, fsg) == 0) ++n0; + } + + if (process_id(pg) == 0) + std::cerr << "Kernel 4:\n"; + + // Run Betweenness Centrality + if (full_bc) { + + // Non-Distributed Graph BC + start = get_time(); + non_distributed_brandes_betweenness_centrality(pg, fsg, non_distributed_centrality); + extract_max_bc_vertices(pg, fsg, non_distributed_centrality, max_seq_bc_vec); + end = get_time(); + + edges_size_type nonDistributedExactTEPs = edges_size_type(floor(7 * n* (n - n0) / (end - start))); + + if (process_id(pg) == 0) + std::cerr << " non-Distributed Graph Exact = " << print_time(end - start) << " (" + << nonDistributedExactTEPs << " TEPs)\n"; + } + + // Non-Distributed Graph Approximate BC + std::vector<int> nonDistributedApproxCentralityS(num_vertices(sg), 0); + seqCentralityMap nonDistributedApproxCentrality(nonDistributedApproxCentralityS.begin(), + get(vertex_index, sg)); + + queue<typename graph_traits<filteredSeqGraph>::vertex_descriptor> sources; + { + minstd_rand gen; + uniform_int<vertices_size_type> rand_vertex(0, num_vertices(fsg) - 1); + int remaining_sources = floor(pow(2, K4Alpha)); + std::vector<typename graph_traits<filteredSeqGraph>::vertex_descriptor> temp_sources; + + while (remaining_sources > 0) { + typename graph_traits<filteredSeqGraph>::vertex_descriptor v = + vertex(rand_vertex(gen), fsg); + + if (out_degree(v, fsg) != 0 + && std::find(temp_sources.begin(), temp_sources.end(), v) == temp_sources.end()) { + temp_sources.push_back(v); + --remaining_sources; + } + } + + for (int i = 0; i < temp_sources.size(); ++i) + sources.push(temp_sources[i]); + } + + start = get_time(); + non_distributed_brandes_betweenness_centrality(pg, fsg, buffer(sources). + centrality_map(nonDistributedApproxCentrality)); + extract_max_bc_vertices(pg, fsg, nonDistributedApproxCentrality, max_seq_bc_vec); + end = get_time(); + + edges_size_type nonDistributedApproxTEPs = edges_size_type(floor(7 * n * pow(2, K4Alpha) / (end - start))); + + if (process_id(pg) == 0) + std::cerr << " Non-Distributed Graph Approximate (" << floor(pow(2, K4Alpha)) << " sources) = " + << print_time(end - start) << " (" << nonDistributedApproxTEPs << " TEPs)\n"; + + // Verify Correctness of Kernel 4 + if (full_bc && verify && process_id(pg) == 0) { + + std::vector<int> seq_centralityS(num_vertices(fsg), 0); + seqCentralityMap seq_centrality(seq_centralityS.begin(), get(vertex_index, fsg)); + + max_seq_bc_vec.clear(); + property_traits<seqCentralityMap>::value_type max_ = 0; + + start = get_time(); + brandes_betweenness_centrality(fsg, seq_centrality); + + typedef filtered_graph<const seqGraph, edge_weight_not_divisible_by_eight<seqEdgeWeightMap> > + filteredSeqGraph; + + BGL_FORALL_VERTICES_T(v, fsg, filteredSeqGraph ) { + if (get(seq_centrality, v) == max_) + max_seq_bc_vec.push_back(v); + else if (get(seq_centrality, v) > max_) { + max_ = get(seq_centrality, v); + max_seq_bc_vec.clear(); + max_seq_bc_vec.push_back(v); + } + } + + end = get_time(); + + edges_size_type sequentialTEPs = edges_size_type(floor(7 * n* (n - n0) / (end - start))); + + std::cerr << " Sequential = " << print_time(end - start) << " (" << sequentialTEPs << " TEPs)\n"; + + typename ProcessGroup::process_id_type id = process_id(pg); + typename ProcessGroup::process_size_type p = num_processes(pg); + + assert((double)n/p == floor((double)n/p)); + + std::cerr << "\nVerifying non-scalable betweenness centrality...\n"; + + { + bool passed = true; + + // Verify non-scalable betweenness centrality + BGL_FORALL_VERTICES_T(v, sg, seqGraph) { + if (get(non_distributed_centrality, v) != get(seq_centrality, v)) { + std::cerr << " " << id << ": Error - centrality of " << v + << " does not match the sequential result (" + << get(non_distributed_centrality, v) << " vs. " + << get(seq_centrality, v) << ")\n"; + passed = false; + } + } + + if (passed) + std::cerr << " PASSED\n"; + } + + } + +} + +template <typename RandomGenerator, typename ProcessGroup, typename vertices_size_type, + typename edges_size_type> +void +run_distributed_graph_tests(RandomGenerator& gen, const ProcessGroup& pg, + vertices_size_type n, edges_size_type m, + std::size_t maxEdgeWeight, uint64_t seed, + int K4Alpha, double a, double b, double c, double d, + int subGraphEdgeLength, bool show_degree_dist, + bool emit_dot_file, bool full_bc, bool verify) +{ +#ifdef CSR + typedef compressed_sparse_row_graph<directedS, VertexProperties, WeightedEdge, no_property, + distributedS<ProcessGroup> > Graph; +#else + typedef adjacency_list<vecS, + distributedS<ProcessGroup, vecS>, + directedS, + // Vertex properties + property<vertex_distance_t, int, + property<vertex_color_t, default_color_type> >, + // Edge properties + property<edge_weight_t, int> > Graph; +#endif + + gen.seed(seed); + + parallel::variant_distribution<ProcessGroup> distrib + = parallel::block(pg, n); + + typedef typename ProcessGroup::process_id_type process_id_type; + process_id_type id = process_id(pg); + + typedef typename property_map<Graph, vertex_owner_t>::const_type OwnerMap; + typedef typename property_map<Graph, vertex_local_t>::const_type LocalMap; + + typedef keep_local_edges<parallel::variant_distribution<ProcessGroup>, + process_id_type> + EdgeFilter; + + // + // Kernel 1 - Graph construction + // Nick: The benchmark specifies that we only have to time graph generation from + // edge tuples, the generator generates the edge tuples at graph construction + // time so we're timing some overhead in the random number generator, etc. + synchronize(pg); + + time_type start = get_time(); + +#ifdef CSR +// typedef sorted_unique_rmat_iterator<RandomGenerator, Graph, EdgeFilter> RMATIter; + typedef sorted_rmat_iterator<RandomGenerator, Graph, keep_all_edges> RMATIter; + + Graph g(//RMATIter(gen, n, m, a, b, c, d, false, true, EdgeFilter(distrib, id)), + RMATIter(gen, n, m, a, b, c, d, true, keep_all_edges()), + RMATIter(), + make_generator_iterator(gen, uniform_int<int>(0, maxEdgeWeight)), + n, pg, distrib); +#else + typedef unique_rmat_iterator<RandomGenerator, Graph, EdgeFilter> RMATIter; + Graph g(RMATIter(gen, n, m, a, b, c, d, true EdgeFilter(distrib, id)), + RMATIter(), + make_generator_iterator(gen, uniform_int<int>(0, maxEdgeWeight)), + n, pg, distrib); +#endif + + synchronize(pg); + + time_type end = get_time(); + + if (id == 0) + std::cerr<< "Kernel 1:\n" + << " Distributed Graph: " << print_time(end - start) << std::endl; + + if ( emit_dot_file ) + write_graphviz("ssca.dot", g); + + // + // Kernel 2 - Classify large sets + // + typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor; + std::vector<std::pair<vertex_descriptor, vertex_descriptor> > S; + + if (id == 0) + std::cerr << "Kernel 2:\n"; + + classify_sets(g, +#ifdef CSR + get(&WeightedEdge::weight, g), +#else + get(edge_weight, g), +#endif + S); + + // + // Kernel 3 - Graph Extraction + // + OwnerMap owner = get(vertex_owner, g); + LocalMap local = get(vertex_local, g); + + if (id == 0) + std::cerr << "Kernel 3:\n"; + +#ifdef CSR + typedef weight_type weight_t; + weight_t unit_weight(1); +#else + int unit_weight(1);; +#endif + + subgraph_extraction(g, owner, local, +#ifdef CSR +// get(&WeightedEdge::weight, g), + ref_property_map<typename graph_traits<Graph>::edge_descriptor, weight_t>(unit_weight), + get(&VertexProperties::distance, g), + get(&VertexProperties::color, g), +#else +// get(edge_weight, g), + ref_property_map<graph_traits<Graph>::edge_descriptor, int>(unit_weight), + get(vertex_distance, g), + get(vertex_color, g), +#endif + S, subGraphEdgeLength); + + // + // Kernel 4 - Betweenness Centrality + // + + // Filter edges with weights divisible by 8 +#ifdef CSR + typedef typename property_map<Graph, weight_type WeightedEdge::*>::type EdgeWeightMap; + edge_weight_not_divisible_by_eight<EdgeWeightMap> filter(get(&WeightedEdge::weight, g)); +#else + typedef typename property_map<Graph, edge_weight_t>::type EdgeWeightMap; + edge_weight_not_divisible_by_eight<EdgeWeightMap> filter(get(edge_weight, g)); +#endif + + typedef filtered_graph<const Graph, edge_weight_not_divisible_by_eight<EdgeWeightMap> > + filteredGraph; + filteredGraph fg(g, filter); + + // Vectors of max BC scores for all tests + std::vector<typename graph_traits<Graph>::vertex_descriptor> max_bc_vec; + + // Distributed Centrality Map + typedef typename property_map<Graph, vertex_index_t>::const_type IndexMap; + typedef iterator_property_map<std::vector<int>::iterator, IndexMap> CentralityMap; + + std::vector<int> centralityS(num_vertices(g), 0); + CentralityMap centrality(centralityS.begin(), get(vertex_index, g)); + + // Calculate number of vertices of degree 0 + vertices_size_type local_n0 = 0, n0; + BGL_FORALL_VERTICES_T(v, fg, filteredGraph) { + if (out_degree(v, g) == 0) local_n0++; + } + n0 = boost::parallel::all_reduce(pg, local_n0, std::plus<vertices_size_type>()); + + if (id == 0) + std::cerr << "Kernel 4:\n"; + + // Run Betweenness Centrality + if (full_bc) { + + // Distributed Graph Full BC + start = get_time(); + brandes_betweenness_centrality(fg, centrality); + extract_max_bc_vertices(pg, g, centrality, max_bc_vec); + end = get_time(); + + edges_size_type exactTEPs = edges_size_type(floor(7 * n* (n - n0) / (end - start))); + + if (id == 0) + std::cerr << " Exact = " << print_time(end - start) << " (" + << exactTEPs << " TEPs)\n"; + } + + // Distributed Graph Approximate BC + std::vector<int> approxCentralityS(num_vertices(g), 0); + CentralityMap approxCentrality(approxCentralityS.begin(), get(vertex_index, g)); + + queue<vertex_descriptor> sources; + generate_sources(g, sources, vertices_size_type(floor(pow(2, K4Alpha)))); + + start = get_time(); + brandes_betweenness_centrality(fg, buffer(sources).centrality_map(approxCentrality)); + extract_max_bc_vertices(pg, fg, approxCentrality, max_bc_vec); + end = get_time(); + + edges_size_type approxTEPs = edges_size_type(floor(7 * n * pow(2, K4Alpha) / (end - start))); + + if (id == 0) + std::cerr << " Approximate (" << floor(pow(2, K4Alpha)) << " sources) = " + << print_time(end - start) << " (" << approxTEPs << " TEPs)\n"; + + + // Verify Correctness of Kernel 4 + if (full_bc && verify && id == 0) { + + // Build non-distributed graph to verify against + typedef adjacency_list<vecS, vecS, directedS, + // Vertex properties + property<vertex_distance_t, int, + property<vertex_color_t, default_color_type> >, + // Edge properties + property<edge_weight_t, int> > seqGraph; + + gen.seed(seed); + +#ifdef CSR + seqGraph sg(sorted_unique_rmat_iterator<RandomGenerator, seqGraph>(gen, n, m, a, b, c, d), + sorted_unique_rmat_iterator<RandomGenerator, seqGraph>(), + make_generator_iterator(gen, uniform_int<int>(0, maxEdgeWeight)), + n); +#else + seqGraph sg(unique_rmat_iterator<RandomGenerator, seqGraph>(gen, n, m, a, b, c, d), + unique_rmat_iterator<RandomGenerator, seqGraph>(), + make_generator_iterator(gen, uniform_int<int>(0, maxEdgeWeight)), + n); +#endif + + typedef property_map<seqGraph, edge_weight_t>::type seqEdgeWeightMap; + edge_weight_not_divisible_by_eight<seqEdgeWeightMap> sg_filter(get(edge_weight, sg)); + + filtered_graph<const seqGraph, edge_weight_not_divisible_by_eight<seqEdgeWeightMap> > + fsg(sg, sg_filter); + + // Build sequential centrality map + typedef property_map<seqGraph, vertex_index_t>::const_type seqIndexMap; + typedef iterator_property_map<std::vector<int>::iterator, seqIndexMap> seqCentralityMap; + + std::vector<int> seq_centralityS(num_vertices(sg), 0); + seqCentralityMap seq_centrality(seq_centralityS.begin(), get(vertex_index, sg)); + + std::vector<graph_traits<seqGraph>::vertex_descriptor> max_seq_bc_vec; + + max_seq_bc_vec.clear(); + property_traits<seqCentralityMap>::value_type max_ = 0; + + start = get_time(); + brandes_betweenness_centrality(fsg, seq_centrality); + + typedef filtered_graph<const seqGraph, edge_weight_not_divisible_by_eight<seqEdgeWeightMap> > + filteredSeqGraph; + + BGL_FORALL_VERTICES_T(v, fsg, filteredSeqGraph ) { + if (get(seq_centrality, v) == max_) + max_seq_bc_vec.push_back(v); + else if (get(seq_centrality, v) > max_) { + max_ = get(seq_centrality, v); + max_seq_bc_vec.clear(); + max_seq_bc_vec.push_back(v); + } + } + + end = get_time(); + + edges_size_type sequentialTEPs = edges_size_type(floor(7 * n* (n - n0) / (end - start))); + + std::cerr << " Sequential = " << print_time(end - start) << " (" << sequentialTEPs << " TEPs)\n"; + + typename ProcessGroup::process_size_type p = num_processes(pg); + + assert((double)n/p == floor((double)n/p)); + + std::cerr << "\nVerifying betweenness centrality...\n"; + + { + bool passed = true; + + // Verify exact betweenness centrality + BGL_FORALL_VERTICES_T(v, g, Graph) { + if (get(centrality, v) != seq_centralityS[(n/p) * get(owner, v) + get(local, v)]) { + std::cerr << " " << id << ": Error - centrality of " << get(local, v) << "@" << get(owner, v) + << " does not match the sequential result (" << get(centrality, v) << " vs. " + << seq_centralityS[(n/p) * get(owner, v) + get(local, v)] << ")\n"; + passed = false; + } + } + + if (passed) + std::cerr << " PASSED\n"; + } + } +} + +void usage() +{ + std::cerr << "SSCA benchmark.\n\n" + << "Usage : ssca [options]\n\n" + << "Options are:\n" + << "\t--vertices v\t\t\tNumber of vertices in the graph\n" + << "\t--edges v\t\t\tNumber of edges in the graph\n" + << "\t--seed s\t\t\tSeed for synchronized random number generator\n" + << "\t--full-bc\t\t\tRun full (exact) Betweenness Centrality\n" + << "\t--max-weight miw\t\tMaximum integer edge weight\n" + << "\t--subgraph-edge-length sel\tEdge length of subgraphs to extract in Kernel 3\n" + << "\t--k4alpha k\t\t\tValue of K4Alpha in Kernel 4\n" + << "\t--scale s\t\t\tSCALE parameter for the SSCA benchmark (sets n, m, and C)\n" + << "\t--dot\t\t\t\tEmit a dot file containing the graph\n" + << "\t--verify\t\t\tVerify result\n" + << "\t--degree-dist\t\t\t Output degree distribution of graph\n" + << "\t--no-distributed-graph\t\tOmit distributed graph tests\n"; +} + +int test_main(int argc, char* argv[]) +{ + mpi::environment env(argc, argv); + + using boost::graph::distributed::mpi_process_group; + +#ifdef CSR + typedef compressed_sparse_row_graph<directedS, VertexProperties, WeightedEdge, no_property, + distributedS<mpi_process_group> > Graph; +#else + typedef adjacency_list<vecS, + distributedS<mpi_process_group, vecS>, + directedS, + // Vertex properties + property<vertex_distance_t, int, + property<vertex_color_t, default_color_type> >, + // Edge properties + property<edge_weight_t, int> > Graph; +#endif + + typedef graph_traits<Graph>::vertices_size_type vertices_size_type; + typedef graph_traits<Graph>::edges_size_type edges_size_type; + + RandomGenerator gen; + + // Default args + vertices_size_type n = 100; + edges_size_type m = 8*n; + uint64_t seed = 1; + int maxEdgeWeight = 100, + subGraphEdgeLength = 8, + K4Alpha = 0.5; + double a = 0.57, b = 0.19, c = 0.19, d = 0.05; + bool emit_dot_file = false, verify = false, full_bc = true, + distributed_graph = true, show_degree_dist = false, + non_distributed_graph = true; + + mpi_process_group pg; + + if (argc == 1) { + if (process_id(pg) == 0) + usage(); + exit(-1); + } + + // Parse args + for (int i = 1; i < argc; ++i) { + std::string arg = argv[i]; + + if (arg == "--vertices") + n = boost::lexical_cast<vertices_size_type>( argv[i+1] ); + + if (arg == "--seed") + seed = boost::lexical_cast<uint64_t>( argv[i+1] ); + + if (arg == "--full-bc") + full_bc = (argv[i+1]== "true"); + + if (arg == "--max-weight") + maxEdgeWeight = boost::lexical_cast<int>( argv[i+1] ); + + if (arg == "--subgraph-edge-length") + subGraphEdgeLength = boost::lexical_cast<int>( argv[i+1] ); + + if (arg == "--edges") + m = boost::lexical_cast<edges_size_type>( argv[i+1] ); + + if (arg == "--k4alpha") + K4Alpha = boost::lexical_cast<int>( argv[i+1] ); + + if (arg == "--dot") + emit_dot_file = true; + + if (arg == "--verify") + verify = true; + + if (arg == "--degree-dist") + show_degree_dist = true; + + if (arg == "--no-distributed-graph") + distributed_graph = false; + + if (arg == "--no-non-distributed-graph") + non_distributed_graph = false; + + if (arg == "--scale") { + vertices_size_type scale = boost::lexical_cast<vertices_size_type>( argv[i+1] ); + maxEdgeWeight = n = vertices_size_type(floor(pow(2, scale))); + m = 8 * n; + } + + if (arg == "--help") { + if (process_id(pg) == 0) + usage(); + exit(-1); + } + } + + if (non_distributed_graph) { + if (process_id(pg) == 0) + std::cerr << "Non-Distributed Graph Tests\n"; + + run_non_distributed_graph_tests(gen, pg, n, m, maxEdgeWeight, seed, K4Alpha, a, b, c, d, + subGraphEdgeLength, show_degree_dist, full_bc, verify); + } + + if (distributed_graph) { + if (process_id(pg) == 0) + std::cerr << "Distributed Graph Tests\n"; + + run_distributed_graph_tests(gen, pg, n, m, maxEdgeWeight, seed, K4Alpha, a, b, c, d, + subGraphEdgeLength, show_degree_dist, emit_dot_file, + full_bc, verify); + } + + return 0; +} |