888 lines
30 KiB
C++
888 lines
30 KiB
C++
// 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;
|
|
}
|