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