1 // Copyright 2004 The Trustees of Indiana University.
3 // Use, modification and distribution is subject to the Boost Software
4 // License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
5 // http://www.boost.org/LICENSE_1_0.txt)
7 // Authors: Nick Edmonds
10 #include <boost/graph/use_mpi.hpp>
15 # include <boost/graph/distributed/compressed_sparse_row_graph.hpp>
17 # include <boost/graph/distributed/adjacency_list.hpp>
20 #include <boost/core/lightweight_test.hpp>
21 #include <boost/graph/distributed/mpi_process_group.hpp>
22 #include <boost/graph/distributed/queue.hpp>
24 #include <boost/graph/parallel/distribution.hpp>
25 #include <boost/lexical_cast.hpp>
26 #include <boost/bind.hpp>
30 #include <boost/random.hpp>
31 #include <boost/property_map/parallel/distributed_property_map.hpp>
33 #include <boost/random/linear_congruential.hpp>
35 #include <boost/graph/distributed/graphviz.hpp>
36 #include <boost/graph/graph_traits.hpp>
37 #include <boost/graph/iteration_macros.hpp>
39 #include <boost/graph/parallel/algorithm.hpp>
40 #include <boost/graph/breadth_first_search.hpp>
41 #include <boost/pending/queue.hpp>
43 #include <boost/graph/rmat_graph_generator.hpp>
44 #include <boost/graph/distributed/betweenness_centrality.hpp>
45 #include <boost/graph/distributed/filtered_graph.hpp>
46 #include <boost/graph/parallel/container_traits.hpp>
48 #include <boost/graph/properties.hpp>
60 using namespace boost
;
64 typedef rand48 RandomGenerator
;
66 /****************************************************************************
68 ****************************************************************************/
69 #ifndef PBGL_ACCOUNTING
71 typedef double time_type
;
73 inline time_type
get_time()
77 return tp
.tv_sec
+ tp
.tv_usec
/ 1000000.0;
80 std::string
print_time(time_type t
)
82 std::ostringstream out
;
83 out
<< std::setiosflags(std::ios::fixed
) << std::setprecision(2) << t
;
87 #endif // PBGL_ACCOUNTING
89 /****************************************************************************
90 * Edge weight generator iterator *
91 ****************************************************************************/
92 template<typename F
, typename RandomGenerator
>
93 class generator_iterator
96 typedef std::input_iterator_tag iterator_category
;
97 typedef typename
F::result_type value_type
;
98 typedef const value_type
& reference
;
99 typedef const value_type
* pointer
;
100 typedef void difference_type
;
103 generator_iterator(RandomGenerator
& gen
, const F
& f
= F())
106 value
= this->f(gen
);
109 reference
operator*() const { return value
; }
110 pointer
operator->() const { return &value
; }
112 generator_iterator
& operator++()
118 generator_iterator
operator++(int)
120 generator_iterator
temp(*this);
125 bool operator==(const generator_iterator
& other
) const
126 { return f
== other
.f
; }
128 bool operator!=(const generator_iterator
& other
) const
129 { return !(*this == other
); }
133 RandomGenerator
* gen
;
137 template<typename F
, typename RandomGenerator
>
138 inline generator_iterator
<F
, RandomGenerator
>
139 make_generator_iterator( RandomGenerator
& gen
, const F
& f
)
140 { return generator_iterator
<F
, RandomGenerator
>(gen
, f
); }
142 template<typename Graph
, typename DistanceMap
, typename WeightMap
, typename ColorMap
>
143 struct ssca_visitor
: bfs_visitor
<>
145 typedef typename property_traits
<WeightMap
>::value_type Weight
;
146 typedef typename property_traits
<ColorMap
>::value_type ColorValue
;
147 typedef color_traits
<ColorValue
> Color
;
149 ssca_visitor(DistanceMap
& distance
, const WeightMap
& weight
, ColorMap
& color
,
151 : distance(distance
), weight(weight
), color(color
), max_(max_
) {}
153 template<typename Edge
>
154 void tree_edge(Edge e
, const Graph
& g
)
156 int new_distance
= get(weight
, e
) == (std::numeric_limits
<Weight
>::max
)() ?
157 (std::numeric_limits
<Weight
>::max
)() : get(distance
, source(e
, g
)) + get(weight
, e
);
159 put(distance
, target(e
, g
), new_distance
);
160 if (new_distance
> max_
)
161 put(color
, target(e
, g
), Color::black());
165 DistanceMap
& distance
;
166 const WeightMap
& weight
;
171 // Generate source vertices for approximate BC
172 template <typename Graph
, typename Buffer
>
174 generate_sources(const Graph
& g
, Buffer sources
,
175 typename graph_traits
<Graph
>::vertices_size_type num_sources
)
177 typedef typename graph_traits
<Graph
>::vertex_descriptor vertex_descriptor
;
178 typedef typename graph_traits
<Graph
>::vertices_size_type vertices_size_type
;
179 typedef typename graph_traits
<Graph
>::vertex_iterator vertex_iterator
;
181 typedef typename
boost::graph::parallel::process_group_type
<Graph
>::type
183 process_group_type pg
= g
.process_group();
185 typename
process_group_type::process_id_type id
= process_id(pg
);
186 typename
process_group_type::process_size_type p
= num_processes(pg
);
188 // Don't feel like adding a special case for num_sources < p
189 assert(num_sources
>= p
);
192 uniform_int
<vertices_size_type
> rand_vertex(0, num_vertices(g
) - 1);
193 std::vector
<vertex_descriptor
> all_sources
, local_sources
;
194 vertices_size_type local_vertices
= vertices_size_type(floor((double)num_sources
/ p
));
195 local_vertices
+= (id
< (num_sources
- (p
* local_vertices
)) ? 1 : 0);
197 while (local_vertices
> 0) {
198 vertex_iterator iter
= vertices(g
).first
;
199 std::advance(iter
, rand_vertex(gen
));
201 if (out_degree(*iter
, g
) != 0
202 && std::find(local_sources
.begin(), local_sources
.end(), *iter
) == local_sources
.end()) {
203 local_sources
.push_back(*iter
);
207 all_gather(pg
, local_sources
.begin(), local_sources
.end(), all_sources
);
208 std::sort(all_sources
.begin(), all_sources
.end());
209 for (typename
std::vector
<vertex_descriptor
>::iterator iter
= all_sources
.begin();
210 iter
!= all_sources
.end(); ++iter
)
214 // Kernel 2 - Classify large sets
215 template <typename Graph
, typename WeightMap
>
216 void classify_sets(const Graph
& g
, const WeightMap
& weight_map
,
217 std::vector
<std::pair
<typename graph_traits
<Graph
>::vertex_descriptor
,
218 typename graph_traits
<Graph
>::vertex_descriptor
> > & global_S
)
220 typedef typename
boost::graph::parallel::process_group_type
<Graph
>::type
222 process_group_type pg
= g
.process_group();
224 typedef typename graph_traits
<Graph
>::vertex_descriptor vertex_descriptor
;
225 std::vector
<std::pair
<vertex_descriptor
, vertex_descriptor
> > S
;
227 time_type start
= get_time();
230 typedef typename property_map
<Graph
, vertex_owner_t
>::const_type OwnerMap
;
231 typedef typename property_map
<Graph
, vertex_local_t
>::const_type LocalMap
;
232 OwnerMap owner
= get(vertex_owner
, g
);
233 LocalMap local
= get(vertex_local
, g
);
237 BGL_FORALL_EDGES_T(e
, g
, Graph
) {
239 if (get(owner
, source(e
, g
)) == process_id(pg
)) {
241 int w
= get(weight_map
, e
);
248 S
.push_back(std::make_pair(source(e
, g
), target(e
, g
)));
254 int global_max
= all_reduce(pg
, max_
, boost::parallel::maximum
<int>());
255 if (max_
< global_max
)
260 all_gather(pg
, S
.begin(), S
.end(), global_S
);
262 // This is probably unnecessary as long as the sets of edges owned by procs is disjoint
263 std::sort(global_S
.begin(), global_S
.end());
264 std::unique(global_S
.begin(), global_S
.end());
268 time_type end
= get_time();
270 if (process_id(pg
) == 0) {
271 std::cerr
<< " Distributed Graph: " << print_time(end
- start
) << std::endl
272 << " Max int weight = " << global_max
<< std::endl
;
276 template <typename ProcessGroup
, typename Graph
, typename WeightMap
,
278 void seq_classify_sets(const ProcessGroup
& pg
, const Graph
& g
,
279 const WeightMap
& weight_map
, EdgeVector
& S
)
281 typedef typename graph_traits
<Graph
>::edge_descriptor edge_descriptor
;
282 typedef typename property_traits
<WeightMap
>::value_type edge_weight_type
;
284 time_type start
= get_time();
286 edge_weight_type max_
= 0;
287 BGL_FORALL_EDGES_T(e
, g
, Graph
) {
288 edge_weight_type w
= get(weight_map
, e
);
300 time_type end
= get_time();
302 if (process_id(pg
) == 0)
303 std::cerr
<< " Non-Distributed Graph: " << print_time(end
- start
) << std::endl
304 << " Max int weight = " << max_
<< std::endl
;
307 // Kernel 3 - Graph Extraction
308 template <typename Graph
, typename OwnerMap
, typename LocalMap
,
309 typename WeightMap
, typename DistanceMap
, typename ColorMap
,
311 void subgraph_extraction(Graph
& g
, const OwnerMap
& owner
, const LocalMap
& local
,
312 const WeightMap
& weight_map
, DistanceMap distances
,
313 ColorMap color_map
, const EdgeVector
& S
,
314 int subGraphEdgeLength
)
316 // Nick: I think turning the vertex black when the maximum distance is
317 // exceeded will prevent BFS from exploring beyond the subgraph.
318 // Unfortunately we can't run subgraph extraction in parallel
319 // because the subgraphs may overlap
321 typedef typename property_traits
<ColorMap
>::value_type ColorValue
;
322 typedef color_traits
<ColorValue
> Color
;
324 typedef typename graph_traits
<Graph
>::edge_descriptor edge_descriptor
;
325 typedef typename graph_traits
<Graph
>::vertex_descriptor vertex_descriptor
;
327 typedef typename
boost::graph::parallel::process_group_type
<Graph
>::type
330 typedef boost::graph::distributed::distributed_queue
<process_group_type
,
331 OwnerMap
, queue
<vertex_descriptor
> > queue_t
;
333 process_group_type pg
= g
.process_group();
334 typename
process_group_type::process_id_type id
= process_id(pg
);
336 queue_t
Q(pg
, owner
);
338 EdgeVector
sources(S
.begin(), S
.end());
341 std::vector
<std::vector
<vertex_descriptor
> > subgraphs
;
346 typedef typename
std::vector
<std::pair
<vertex_descriptor
, vertex_descriptor
> >::iterator
349 time_type start
= get_time();
350 for (source_iterator iter
= sources
.begin(); iter
!= sources
.end(); ++iter
) {
351 // Reinitialize distance and color maps every BFS
352 BGL_FORALL_VERTICES_T(v
, g
, Graph
) {
353 if (get(owner
, v
) == id
) {
354 local_put(color_map
, v
, Color::white());
355 local_put(distances
, v
, (std::numeric_limits
<int>::max
)());
359 vertex_descriptor u
= iter
->first
, v
= iter
->second
;
361 local_put(distances
, u
, 0);
362 local_put(distances
, v
, 0);
364 while (!Q
.empty()) Q
.pop();
365 if (get(owner
, u
) == id
)
368 local_put(color_map
, u
, Color::gray());
370 breadth_first_search(g
, v
, Q
,
371 ssca_visitor
<Graph
, DistanceMap
, WeightMap
, ColorMap
>
372 (distances
, weight_map
, color_map
, subGraphEdgeLength
),
375 // At this point all vertices with distance > 0 in addition to the
376 // starting vertices compose the subgraph.
378 subgraphs
.push_back(std::vector
<vertex_descriptor
>());
379 std::vector
<vertex_descriptor
>& subgraph
= subgraphs
.back();
381 BGL_FORALL_VERTICES_T(v
, g
, Graph
) {
382 if (get(distances
, v
) < (std::numeric_limits
<int>::max
)())
383 subgraph
.push_back(v
);
390 time_type end
= get_time();
393 for (unsigned int i
= 0; i
< subgraphs
.size(); i
++) {
394 all_gather(pg
, subgraphs
[i
].begin(), subgraphs
[i
].end(), subgraphs
[i
]);
395 std::sort(subgraphs
[i
].begin(), subgraphs
[i
].end());
396 subgraphs
[i
].erase(std::unique(subgraphs
[i
].begin(), subgraphs
[i
].end()),
400 if (process_id(pg
) == 0)
401 for (int i
= 0; abs(i
) < subgraphs
.size(); i
++) {
402 std::cerr
<< "Subgraph " << i
<< " :\n";
403 for (int j
= 0; abs(j
) < subgraphs
[i
].size(); j
++)
404 std::cerr
<< " " << get(local
, subgraphs
[i
][j
]) << "@"
405 << get(owner
, subgraphs
[i
][j
]) << std::endl
;
409 if (process_id(pg
) == 0)
410 std::cerr
<< " Distributed Graph: " << print_time(end
- start
) << std::endl
;
413 template <typename ProcessGroup
, typename Graph
, typename WeightMap
,
414 typename DistanceMap
, typename ColorMap
, typename EdgeVector
>
415 void seq_subgraph_extraction(const ProcessGroup
& pg
, const Graph
& g
,
416 const WeightMap
& weight_map
, DistanceMap distances
,
417 ColorMap color_map
, const EdgeVector
& S
,
418 int subGraphEdgeLength
)
420 // Nick: I think turning the vertex black when the maximum distance is
421 // exceeded will prevent BFS from exploring beyond the subgraph.
423 using boost::graph::distributed::mpi_process_group
;
425 typedef typename property_traits
<ColorMap
>::value_type ColorValue
;
426 typedef color_traits
<ColorValue
> Color
;
428 typedef typename graph_traits
<Graph
>::edge_descriptor edge_descriptor
;
429 typedef typename graph_traits
<Graph
>::vertex_descriptor vertex_descriptor
;
431 boost::queue
<vertex_descriptor
> Q
;
433 std::vector
<edge_descriptor
> sources(S
.begin(), S
.end());
436 std::vector
<std::vector
<vertex_descriptor
> > subgraphs
;
441 typedef ProcessGroup process_group_type
;
443 typename
process_group_type::process_id_type id
= process_id(pg
);
444 typename
process_group_type::process_size_type p
= num_processes(pg
);
446 time_type start
= get_time();
448 for (int i
= id
; i
< sources
.size(); i
+= p
) {
450 // Reinitialize distance and color maps every BFS
451 BGL_FORALL_VERTICES_T(v
, g
, Graph
) {
452 put(color_map
, v
, Color::white());
453 put(distances
, v
, (std::numeric_limits
<int>::max
)());
456 vertex_descriptor u
= source(sources
[i
], g
),
457 v
= target(sources
[i
], g
);
459 put(distances
, u
, 0);
460 put(distances
, v
, 0);
462 while (!Q
.empty()) Q
.pop();
465 put(color_map
, u
, Color::gray());
467 breadth_first_search(g
, v
, Q
,
468 ssca_visitor
<Graph
, DistanceMap
, WeightMap
, ColorMap
>
469 (distances
, weight_map
, color_map
, subGraphEdgeLength
),
473 subgraphs
.push_back(std::vector
<vertex_descriptor
>());
474 std::vector
<vertex_descriptor
>& subgraph
= subgraphs
.back();
476 BGL_FORALL_VERTICES_T(v
, g
, Graph
) {
477 if (get(distances
, v
) < (std::numeric_limits
<int>::max
)())
478 subgraph
.push_back(v
);
485 time_type end
= get_time();
488 std::vector
<vertex_descriptor
> ser_subgraphs
;
490 for (int i
= 0; i
< subgraphs
.size(); ++i
) {
491 for (int j
= 0; j
< subgraphs
[i
].size(); ++j
)
492 ser_subgraphs
.push_back(subgraphs
[i
][j
]);
493 ser_subgraphs
.push_back(graph_traits
<Graph
>::null_vertex());
496 all_gather(pg
, ser_subgraphs
.begin(), ser_subgraphs
.end(), ser_subgraphs
);
499 typename
std::vector
<vertex_descriptor
>::iterator
iter(ser_subgraphs
.begin());
501 while (iter
!= ser_subgraphs
.end()) {
502 std::cerr
<< "Subgraph " << i
<< " :\n";
503 while (*iter
!= graph_traits
<Graph
>::null_vertex()) {
504 std::cerr
<< " " << *iter
<< std::endl
;
512 if (process_id(pg
) == 0)
513 std::cerr
<< " Non-Distributed Graph: " << print_time(end
- start
) << std::endl
;
516 template <typename ProcessGroup
, typename Graph
, typename CentralityMap
>
518 extract_max_bc_vertices(const ProcessGroup
& pg
, const Graph
& g
, const CentralityMap
& centrality
,
519 std::vector
<typename graph_traits
<Graph
>::vertex_descriptor
>& max_bc_vec
)
521 using boost::graph::parallel::process_group
;
522 using boost::parallel::all_gather
;
523 using boost::parallel::all_reduce
;
525 // Find set of vertices with highest BC score
526 typedef typename property_traits
<CentralityMap
>::value_type centrality_type
;
527 std::vector
<centrality_type
> max_bc_vertices
;
528 centrality_type max_
= 0;
532 BGL_FORALL_VERTICES_T(v
, g
, Graph
) {
533 if (get(centrality
, v
) == max_
)
534 max_bc_vec
.push_back(v
);
535 else if (get(centrality
, v
) > max_
) {
536 max_
= get(centrality
, v
);
538 max_bc_vec
.push_back(v
);
542 centrality_type global_max
= all_reduce(pg
, max_
, boost::parallel::minimum
<int>());
544 if (global_max
> max_
)
547 all_gather(pg
, max_bc_vec
.begin(), max_bc_vec
.end(), max_bc_vec
);
551 // Function object to filter edges divisible by 8
552 // EdgeWeightMap::value_type must be integral!
553 template <typename EdgeWeightMap
>
554 struct edge_weight_not_divisible_by_eight
{
555 typedef typename property_traits
<EdgeWeightMap
>::value_type weight_type
;
557 edge_weight_not_divisible_by_eight() { }
558 edge_weight_not_divisible_by_eight(EdgeWeightMap weight
) : m_weight(weight
) { }
559 template <typename Edge
>
560 bool operator()(const Edge
& e
) const {
561 return (get(m_weight
, e
) & ((std::numeric_limits
<weight_type
>::max
)() - 7)) != get(m_weight
, e
);
564 EdgeWeightMap m_weight
;
568 // Vertex and Edge properties
571 typedef int weight_type
;
573 struct WeightedEdge
{
574 WeightedEdge(weight_type weight
= 0) : weight(weight
) { }
579 struct VertexProperties
{
580 VertexProperties(int distance
= 0, default_color_type color
= white_color
)
581 : distance(distance
), color(color
) { }
584 default_color_type color
;
588 template <typename RandomGenerator
, typename ProcessGroup
, typename vertices_size_type
,
589 typename edges_size_type
>
591 run_non_distributed_graph_tests(RandomGenerator
& gen
, const ProcessGroup
& pg
,
592 vertices_size_type n
, edges_size_type m
,
593 std::size_t maxEdgeWeight
, uint64_t seed
,
594 int K4Alpha
, double a
, double b
, double c
, double d
,
595 int subGraphEdgeLength
, bool show_degree_dist
,
596 bool full_bc
, bool verify
)
599 typedef compressed_sparse_row_graph
<directedS
, VertexProperties
, WeightedEdge
>
602 typedef adjacency_list
<vecS
, vecS
, directedS
,
604 property
<vertex_distance_t
, int,
605 property
<vertex_color_t
, default_color_type
> >,
607 property
<edge_weight_t
, int> > seqGraph
;
610 // Generate sequential graph for non_distributed betweenness centrality
611 // Reseed the PRNG to get the same graph
616 time_type start
= get_time();
619 seqGraph
sg(edges_are_sorted
,
620 sorted_unique_rmat_iterator
<RandomGenerator
, seqGraph
>(gen
, n
, m
, a
, b
, c
, d
),
621 sorted_unique_rmat_iterator
<RandomGenerator
, seqGraph
>(),
622 make_generator_iterator(gen
, uniform_int
<int>(0, maxEdgeWeight
)),
625 seqGraph
sg(unique_rmat_iterator
<RandomGenerator
, seqGraph
>(gen
, n
, m
, a
, b
, c
, d
),
626 unique_rmat_iterator
<RandomGenerator
, seqGraph
>(),
627 make_generator_iterator(gen
, uniform_int
<int>(0, maxEdgeWeight
)),
631 // Not strictly necessary to synchronize here, but it make sure that the
632 // time we measure is the time needed for all copies of the graph to be
636 time_type end
= get_time();
638 if (process_id(pg
) == 0)
639 std::cerr
<< "Kernel 1:\n"
640 << " Non-Distributed Graph: " << print_time(end
- start
) << std::endl
;
642 std::map
<int, int> degree_dist
;
643 if ( show_degree_dist
) {
644 BGL_FORALL_VERTICES_T(v
, sg
, seqGraph
) {
645 degree_dist
[out_degree(v
, sg
)]++;
648 std::cerr
<< "Degree - Fraction of vertices of that degree\n";
649 for (std::map
<int, int>::iterator iter
= degree_dist
.begin();
650 iter
!= degree_dist
.end(); ++iter
)
651 std::cerr
<< " " << iter
->first
<< " - " << double(iter
->second
) / num_vertices(sg
) << std::endl
<< std::endl
;
655 // Kernel 2 - Classify large sets
657 std::vector
<graph_traits
<seqGraph
>::edge_descriptor
> seqS
;
659 if (process_id(pg
) == 0)
660 std::cerr
<< "Kernel 2:\n";
662 seq_classify_sets(pg
, sg
,
664 get(&WeightedEdge::weight
, sg
),
666 get(edge_weight
, sg
),
671 // Kernel 3 - Graph Extraction
674 typedef weight_type weight_t
;
675 weight_t
unit_weight(1);
680 if (process_id(pg
) == 0)
681 std::cerr
<< "Kernel 3:\n";
683 seq_subgraph_extraction(pg
, sg
,
685 // get(&WeightedEdge::weight, sg),
686 ref_property_map
<graph_traits
<seqGraph
>::edge_descriptor
, weight_t
>(unit_weight
),
687 get(&VertexProperties::distance
, sg
),
688 get(&VertexProperties::color
, sg
),
690 // get(edge_weight, sg),
691 ref_property_map
<graph_traits
<seqGraph
>::edge_descriptor
, int>(unit_weight
),
692 get(vertex_distance
, sg
),
693 get(vertex_color
, sg
),
695 seqS
, subGraphEdgeLength
);
698 typedef property_map
<seqGraph
, weight_type
WeightedEdge::*>::type seqEdgeWeightMap
;
699 edge_weight_not_divisible_by_eight
<seqEdgeWeightMap
> sg_filter(get(&WeightedEdge::weight
, sg
));
701 typedef property_map
<seqGraph
, edge_weight_t
>::type seqEdgeWeightMap
;
702 edge_weight_not_divisible_by_eight
<seqEdgeWeightMap
> sg_filter(get(edge_weight
, sg
));
705 typedef filtered_graph
<const seqGraph
, edge_weight_not_divisible_by_eight
<seqEdgeWeightMap
> >
708 filteredSeqGraph
fsg(sg
, sg_filter
);
710 std::vector
<graph_traits
<seqGraph
>::vertex_descriptor
> max_seq_bc_vec
;
712 // Non-Distributed Centrality Map
713 typedef property_map
<seqGraph
, vertex_index_t
>::const_type seqIndexMap
;
714 typedef iterator_property_map
<std::vector
<int>::iterator
, seqIndexMap
> seqCentralityMap
;
716 std::vector
<int> non_distributed_centralityS(num_vertices(sg
), 0);
717 seqCentralityMap
non_distributed_centrality(non_distributed_centralityS
.begin(),
718 get(vertex_index
, sg
));
720 vertices_size_type n0
= 0;
721 BGL_FORALL_VERTICES_T(v
, fsg
, filteredSeqGraph
) {
722 if (out_degree(v
, fsg
) == 0) ++n0
;
725 if (process_id(pg
) == 0)
726 std::cerr
<< "Kernel 4:\n";
728 // Run Betweenness Centrality
731 // Non-Distributed Graph BC
733 non_distributed_brandes_betweenness_centrality(pg
, fsg
, non_distributed_centrality
);
734 extract_max_bc_vertices(pg
, fsg
, non_distributed_centrality
, max_seq_bc_vec
);
737 edges_size_type nonDistributedExactTEPs
= edges_size_type(floor(7 * n
* (n
- n0
) / (end
- start
)));
739 if (process_id(pg
) == 0)
740 std::cerr
<< " non-Distributed Graph Exact = " << print_time(end
- start
) << " ("
741 << nonDistributedExactTEPs
<< " TEPs)\n";
744 // Non-Distributed Graph Approximate BC
745 std::vector
<int> nonDistributedApproxCentralityS(num_vertices(sg
), 0);
746 seqCentralityMap
nonDistributedApproxCentrality(nonDistributedApproxCentralityS
.begin(),
747 get(vertex_index
, sg
));
749 queue
<typename graph_traits
<filteredSeqGraph
>::vertex_descriptor
> sources
;
752 uniform_int
<vertices_size_type
> rand_vertex(0, num_vertices(fsg
) - 1);
753 int remaining_sources
= floor(pow(2, K4Alpha
));
754 std::vector
<typename graph_traits
<filteredSeqGraph
>::vertex_descriptor
> temp_sources
;
756 while (remaining_sources
> 0) {
757 typename graph_traits
<filteredSeqGraph
>::vertex_descriptor v
=
758 vertex(rand_vertex(gen
), fsg
);
760 if (out_degree(v
, fsg
) != 0
761 && std::find(temp_sources
.begin(), temp_sources
.end(), v
) == temp_sources
.end()) {
762 temp_sources
.push_back(v
);
767 for (int i
= 0; i
< temp_sources
.size(); ++i
)
768 sources
.push(temp_sources
[i
]);
772 non_distributed_brandes_betweenness_centrality(pg
, fsg
, buffer(sources
).
773 centrality_map(nonDistributedApproxCentrality
));
774 extract_max_bc_vertices(pg
, fsg
, nonDistributedApproxCentrality
, max_seq_bc_vec
);
777 edges_size_type nonDistributedApproxTEPs
= edges_size_type(floor(7 * n
* pow(2, K4Alpha
) / (end
- start
)));
779 if (process_id(pg
) == 0)
780 std::cerr
<< " Non-Distributed Graph Approximate (" << floor(pow(2, K4Alpha
)) << " sources) = "
781 << print_time(end
- start
) << " (" << nonDistributedApproxTEPs
<< " TEPs)\n";
783 // Verify Correctness of Kernel 4
784 if (full_bc
&& verify
&& process_id(pg
) == 0) {
786 std::vector
<int> seq_centralityS(num_vertices(fsg
), 0);
787 seqCentralityMap
seq_centrality(seq_centralityS
.begin(), get(vertex_index
, fsg
));
789 max_seq_bc_vec
.clear();
790 property_traits
<seqCentralityMap
>::value_type max_
= 0;
793 brandes_betweenness_centrality(fsg
, seq_centrality
);
795 typedef filtered_graph
<const seqGraph
, edge_weight_not_divisible_by_eight
<seqEdgeWeightMap
> >
798 BGL_FORALL_VERTICES_T(v
, fsg
, filteredSeqGraph
) {
799 if (get(seq_centrality
, v
) == max_
)
800 max_seq_bc_vec
.push_back(v
);
801 else if (get(seq_centrality
, v
) > max_
) {
802 max_
= get(seq_centrality
, v
);
803 max_seq_bc_vec
.clear();
804 max_seq_bc_vec
.push_back(v
);
810 edges_size_type sequentialTEPs
= edges_size_type(floor(7 * n
* (n
- n0
) / (end
- start
)));
812 std::cerr
<< " Sequential = " << print_time(end
- start
) << " (" << sequentialTEPs
<< " TEPs)\n";
814 typename
ProcessGroup::process_id_type id
= process_id(pg
);
815 typename
ProcessGroup::process_size_type p
= num_processes(pg
);
817 assert((double)n
/p
== floor((double)n
/p
));
819 std::cerr
<< "\nVerifying non-scalable betweenness centrality...\n";
824 // Verify non-scalable betweenness centrality
825 BGL_FORALL_VERTICES_T(v
, sg
, seqGraph
) {
826 if (get(non_distributed_centrality
, v
) != get(seq_centrality
, v
)) {
827 std::cerr
<< " " << id
<< ": Error - centrality of " << v
828 << " does not match the sequential result ("
829 << get(non_distributed_centrality
, v
) << " vs. "
830 << get(seq_centrality
, v
) << ")\n";
836 std::cerr
<< " PASSED\n";
843 template <typename RandomGenerator
, typename ProcessGroup
, typename vertices_size_type
,
844 typename edges_size_type
>
846 run_distributed_graph_tests(RandomGenerator
& gen
, const ProcessGroup
& pg
,
847 vertices_size_type n
, edges_size_type m
,
848 std::size_t maxEdgeWeight
, uint64_t seed
,
849 int K4Alpha
, double a
, double b
, double c
, double d
,
850 int subGraphEdgeLength
, bool show_degree_dist
,
851 bool emit_dot_file
, bool full_bc
, bool verify
)
854 typedef compressed_sparse_row_graph
<directedS
, VertexProperties
, WeightedEdge
, no_property
,
855 distributedS
<ProcessGroup
> > Graph
;
857 typedef adjacency_list
<vecS
,
858 distributedS
<ProcessGroup
, vecS
>,
861 property
<vertex_distance_t
, int,
862 property
<vertex_color_t
, default_color_type
> >,
864 property
<edge_weight_t
, int> > Graph
;
869 parallel::variant_distribution
<ProcessGroup
> distrib
870 = parallel::block(pg
, n
);
872 typedef typename
ProcessGroup::process_id_type process_id_type
;
873 process_id_type id
= process_id(pg
);
875 typedef typename property_map
<Graph
, vertex_owner_t
>::const_type OwnerMap
;
876 typedef typename property_map
<Graph
, vertex_local_t
>::const_type LocalMap
;
878 typedef keep_local_edges
<parallel::variant_distribution
<ProcessGroup
>,
883 // Kernel 1 - Graph construction
884 // Nick: The benchmark specifies that we only have to time graph generation from
885 // edge tuples, the generator generates the edge tuples at graph construction
886 // time so we're timing some overhead in the random number generator, etc.
889 time_type start
= get_time();
892 // typedef sorted_unique_rmat_iterator<RandomGenerator, Graph, EdgeFilter> RMATIter;
893 typedef sorted_rmat_iterator
<RandomGenerator
, Graph
, keep_all_edges
> RMATIter
;
895 Graph
g(//RMATIter(gen, n, m, a, b, c, d, false, true, EdgeFilter(distrib, id)),
896 RMATIter(gen
, n
, m
, a
, b
, c
, d
, true, keep_all_edges()),
898 make_generator_iterator(gen
, uniform_int
<int>(0, maxEdgeWeight
)),
901 typedef unique_rmat_iterator
<RandomGenerator
, Graph
, EdgeFilter
> RMATIter
;
902 Graph
g(RMATIter(gen
, n
, m
, a
, b
, c
, d
, true EdgeFilter(distrib
, id
)),
904 make_generator_iterator(gen
, uniform_int
<int>(0, maxEdgeWeight
)),
910 time_type end
= get_time();
913 std::cerr
<< "Kernel 1:\n"
914 << " Distributed Graph: " << print_time(end
- start
) << std::endl
;
917 write_graphviz("ssca.dot", g
);
920 // Kernel 2 - Classify large sets
922 typedef typename graph_traits
<Graph
>::vertex_descriptor vertex_descriptor
;
923 std::vector
<std::pair
<vertex_descriptor
, vertex_descriptor
> > S
;
926 std::cerr
<< "Kernel 2:\n";
930 get(&WeightedEdge::weight
, g
),
937 // Kernel 3 - Graph Extraction
939 OwnerMap owner
= get(vertex_owner
, g
);
940 LocalMap local
= get(vertex_local
, g
);
943 std::cerr
<< "Kernel 3:\n";
946 typedef weight_type weight_t
;
947 weight_t
unit_weight(1);
952 subgraph_extraction(g
, owner
, local
,
954 // get(&WeightedEdge::weight, g),
955 ref_property_map
<typename graph_traits
<Graph
>::edge_descriptor
, weight_t
>(unit_weight
),
956 get(&VertexProperties::distance
, g
),
957 get(&VertexProperties::color
, g
),
959 // get(edge_weight, g),
960 ref_property_map
<graph_traits
<Graph
>::edge_descriptor
, int>(unit_weight
),
961 get(vertex_distance
, g
),
962 get(vertex_color
, g
),
964 S
, subGraphEdgeLength
);
967 // Kernel 4 - Betweenness Centrality
970 // Filter edges with weights divisible by 8
972 typedef typename property_map
<Graph
, weight_type
WeightedEdge::*>::type EdgeWeightMap
;
973 edge_weight_not_divisible_by_eight
<EdgeWeightMap
> filter(get(&WeightedEdge::weight
, g
));
975 typedef typename property_map
<Graph
, edge_weight_t
>::type EdgeWeightMap
;
976 edge_weight_not_divisible_by_eight
<EdgeWeightMap
> filter(get(edge_weight
, g
));
979 typedef filtered_graph
<const Graph
, edge_weight_not_divisible_by_eight
<EdgeWeightMap
> >
981 filteredGraph
fg(g
, filter
);
983 // Vectors of max BC scores for all tests
984 std::vector
<typename graph_traits
<Graph
>::vertex_descriptor
> max_bc_vec
;
986 // Distributed Centrality Map
987 typedef typename property_map
<Graph
, vertex_index_t
>::const_type IndexMap
;
988 typedef iterator_property_map
<std::vector
<int>::iterator
, IndexMap
> CentralityMap
;
990 std::vector
<int> centralityS(num_vertices(g
), 0);
991 CentralityMap
centrality(centralityS
.begin(), get(vertex_index
, g
));
993 // Calculate number of vertices of degree 0
994 vertices_size_type local_n0
= 0, n0
;
995 BGL_FORALL_VERTICES_T(v
, fg
, filteredGraph
) {
996 if (out_degree(v
, g
) == 0) local_n0
++;
998 n0
= boost::parallel::all_reduce(pg
, local_n0
, std::plus
<vertices_size_type
>());
1001 std::cerr
<< "Kernel 4:\n";
1003 // Run Betweenness Centrality
1006 // Distributed Graph Full BC
1008 brandes_betweenness_centrality(fg
, centrality
);
1009 extract_max_bc_vertices(pg
, g
, centrality
, max_bc_vec
);
1012 edges_size_type exactTEPs
= edges_size_type(floor(7 * n
* (n
- n0
) / (end
- start
)));
1015 std::cerr
<< " Exact = " << print_time(end
- start
) << " ("
1016 << exactTEPs
<< " TEPs)\n";
1019 // Distributed Graph Approximate BC
1020 std::vector
<int> approxCentralityS(num_vertices(g
), 0);
1021 CentralityMap
approxCentrality(approxCentralityS
.begin(), get(vertex_index
, g
));
1023 queue
<vertex_descriptor
> sources
;
1024 generate_sources(g
, sources
, vertices_size_type(floor(pow(2, K4Alpha
))));
1027 brandes_betweenness_centrality(fg
, buffer(sources
).centrality_map(approxCentrality
));
1028 extract_max_bc_vertices(pg
, fg
, approxCentrality
, max_bc_vec
);
1031 edges_size_type approxTEPs
= edges_size_type(floor(7 * n
* pow(2, K4Alpha
) / (end
- start
)));
1034 std::cerr
<< " Approximate (" << floor(pow(2, K4Alpha
)) << " sources) = "
1035 << print_time(end
- start
) << " (" << approxTEPs
<< " TEPs)\n";
1038 // Verify Correctness of Kernel 4
1039 if (full_bc
&& verify
&& id
== 0) {
1041 // Build non-distributed graph to verify against
1042 typedef adjacency_list
<vecS
, vecS
, directedS
,
1043 // Vertex properties
1044 property
<vertex_distance_t
, int,
1045 property
<vertex_color_t
, default_color_type
> >,
1047 property
<edge_weight_t
, int> > seqGraph
;
1052 seqGraph
sg(sorted_unique_rmat_iterator
<RandomGenerator
, seqGraph
>(gen
, n
, m
, a
, b
, c
, d
),
1053 sorted_unique_rmat_iterator
<RandomGenerator
, seqGraph
>(),
1054 make_generator_iterator(gen
, uniform_int
<int>(0, maxEdgeWeight
)),
1057 seqGraph
sg(unique_rmat_iterator
<RandomGenerator
, seqGraph
>(gen
, n
, m
, a
, b
, c
, d
),
1058 unique_rmat_iterator
<RandomGenerator
, seqGraph
>(),
1059 make_generator_iterator(gen
, uniform_int
<int>(0, maxEdgeWeight
)),
1063 typedef property_map
<seqGraph
, edge_weight_t
>::type seqEdgeWeightMap
;
1064 edge_weight_not_divisible_by_eight
<seqEdgeWeightMap
> sg_filter(get(edge_weight
, sg
));
1066 filtered_graph
<const seqGraph
, edge_weight_not_divisible_by_eight
<seqEdgeWeightMap
> >
1069 // Build sequential centrality map
1070 typedef property_map
<seqGraph
, vertex_index_t
>::const_type seqIndexMap
;
1071 typedef iterator_property_map
<std::vector
<int>::iterator
, seqIndexMap
> seqCentralityMap
;
1073 std::vector
<int> seq_centralityS(num_vertices(sg
), 0);
1074 seqCentralityMap
seq_centrality(seq_centralityS
.begin(), get(vertex_index
, sg
));
1076 std::vector
<graph_traits
<seqGraph
>::vertex_descriptor
> max_seq_bc_vec
;
1078 max_seq_bc_vec
.clear();
1079 property_traits
<seqCentralityMap
>::value_type max_
= 0;
1082 brandes_betweenness_centrality(fsg
, seq_centrality
);
1084 typedef filtered_graph
<const seqGraph
, edge_weight_not_divisible_by_eight
<seqEdgeWeightMap
> >
1087 BGL_FORALL_VERTICES_T(v
, fsg
, filteredSeqGraph
) {
1088 if (get(seq_centrality
, v
) == max_
)
1089 max_seq_bc_vec
.push_back(v
);
1090 else if (get(seq_centrality
, v
) > max_
) {
1091 max_
= get(seq_centrality
, v
);
1092 max_seq_bc_vec
.clear();
1093 max_seq_bc_vec
.push_back(v
);
1099 edges_size_type sequentialTEPs
= edges_size_type(floor(7 * n
* (n
- n0
) / (end
- start
)));
1101 std::cerr
<< " Sequential = " << print_time(end
- start
) << " (" << sequentialTEPs
<< " TEPs)\n";
1103 typename
ProcessGroup::process_size_type p
= num_processes(pg
);
1105 assert((double)n
/p
== floor((double)n
/p
));
1107 std::cerr
<< "\nVerifying betweenness centrality...\n";
1112 // Verify exact betweenness centrality
1113 BGL_FORALL_VERTICES_T(v
, g
, Graph
) {
1114 if (get(centrality
, v
) != seq_centralityS
[(n
/p
) * get(owner
, v
) + get(local
, v
)]) {
1115 std::cerr
<< " " << id
<< ": Error - centrality of " << get(local
, v
) << "@" << get(owner
, v
)
1116 << " does not match the sequential result (" << get(centrality
, v
) << " vs. "
1117 << seq_centralityS
[(n
/p
) * get(owner
, v
) + get(local
, v
)] << ")\n";
1123 std::cerr
<< " PASSED\n";
1130 std::cerr
<< "SSCA benchmark.\n\n"
1131 << "Usage : ssca [options]\n\n"
1133 << "\t--vertices v\t\t\tNumber of vertices in the graph\n"
1134 << "\t--edges v\t\t\tNumber of edges in the graph\n"
1135 << "\t--seed s\t\t\tSeed for synchronized random number generator\n"
1136 << "\t--full-bc\t\t\tRun full (exact) Betweenness Centrality\n"
1137 << "\t--max-weight miw\t\tMaximum integer edge weight\n"
1138 << "\t--subgraph-edge-length sel\tEdge length of subgraphs to extract in Kernel 3\n"
1139 << "\t--k4alpha k\t\t\tValue of K4Alpha in Kernel 4\n"
1140 << "\t--scale s\t\t\tSCALE parameter for the SSCA benchmark (sets n, m, and C)\n"
1141 << "\t--dot\t\t\t\tEmit a dot file containing the graph\n"
1142 << "\t--verify\t\t\tVerify result\n"
1143 << "\t--degree-dist\t\t\t Output degree distribution of graph\n"
1144 << "\t--no-distributed-graph\t\tOmit distributed graph tests\n";
1147 int main(int argc
, char* argv
[])
1149 mpi::environment
env(argc
, argv
);
1151 using boost::graph::distributed::mpi_process_group
;
1154 typedef compressed_sparse_row_graph
<directedS
, VertexProperties
, WeightedEdge
, no_property
,
1155 distributedS
<mpi_process_group
> > Graph
;
1157 typedef adjacency_list
<vecS
,
1158 distributedS
<mpi_process_group
, vecS
>,
1160 // Vertex properties
1161 property
<vertex_distance_t
, int,
1162 property
<vertex_color_t
, default_color_type
> >,
1164 property
<edge_weight_t
, int> > Graph
;
1167 typedef graph_traits
<Graph
>::vertices_size_type vertices_size_type
;
1168 typedef graph_traits
<Graph
>::edges_size_type edges_size_type
;
1170 RandomGenerator gen
;
1173 vertices_size_type n
= 100;
1174 edges_size_type m
= 8*n
;
1176 int maxEdgeWeight
= 100,
1177 subGraphEdgeLength
= 8,
1179 double a
= 0.57, b
= 0.19, c
= 0.19, d
= 0.05;
1180 bool emit_dot_file
= false, verify
= false, full_bc
= true,
1181 distributed_graph
= true, show_degree_dist
= false,
1182 non_distributed_graph
= true;
1184 mpi_process_group pg
;
1187 if (process_id(pg
) == 0)
1193 for (int i
= 1; i
< argc
; ++i
) {
1194 std::string arg
= argv
[i
];
1196 if (arg
== "--vertices")
1197 n
= boost::lexical_cast
<vertices_size_type
>( argv
[i
+1] );
1199 if (arg
== "--seed")
1200 seed
= boost::lexical_cast
<uint64_t>( argv
[i
+1] );
1202 if (arg
== "--full-bc")
1203 full_bc
= (argv
[i
+1]== "true");
1205 if (arg
== "--max-weight")
1206 maxEdgeWeight
= boost::lexical_cast
<int>( argv
[i
+1] );
1208 if (arg
== "--subgraph-edge-length")
1209 subGraphEdgeLength
= boost::lexical_cast
<int>( argv
[i
+1] );
1211 if (arg
== "--edges")
1212 m
= boost::lexical_cast
<edges_size_type
>( argv
[i
+1] );
1214 if (arg
== "--k4alpha")
1215 K4Alpha
= boost::lexical_cast
<int>( argv
[i
+1] );
1218 emit_dot_file
= true;
1220 if (arg
== "--verify")
1223 if (arg
== "--degree-dist")
1224 show_degree_dist
= true;
1226 if (arg
== "--no-distributed-graph")
1227 distributed_graph
= false;
1229 if (arg
== "--no-non-distributed-graph")
1230 non_distributed_graph
= false;
1232 if (arg
== "--scale") {
1233 vertices_size_type scale
= boost::lexical_cast
<vertices_size_type
>( argv
[i
+1] );
1234 maxEdgeWeight
= n
= vertices_size_type(floor(pow(2, scale
)));
1238 if (arg
== "--help") {
1239 if (process_id(pg
) == 0)
1245 if (non_distributed_graph
) {
1246 if (process_id(pg
) == 0)
1247 std::cerr
<< "Non-Distributed Graph Tests\n";
1249 run_non_distributed_graph_tests(gen
, pg
, n
, m
, maxEdgeWeight
, seed
, K4Alpha
, a
, b
, c
, d
,
1250 subGraphEdgeLength
, show_degree_dist
, full_bc
, verify
);
1253 if (distributed_graph
) {
1254 if (process_id(pg
) == 0)
1255 std::cerr
<< "Distributed Graph Tests\n";
1257 run_distributed_graph_tests(gen
, pg
, n
, m
, maxEdgeWeight
, seed
, K4Alpha
, a
, b
, c
, d
,
1258 subGraphEdgeLength
, show_degree_dist
, emit_dot_file
,
1262 return boost::report_errors();