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