EQ2EMu/EQ2/source/depends/boost_1_72_0/libs/graph_parallel/test/algorithm_performance.cpp

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