Adding upstream version 16.2.11+ds.upstream/16.2.11+dsupstream

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

1 files changed, 1263 insertions, 0 deletions

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