libs/graph_parallel/test/distributed_betweenness_centrality_test.cpp

   1 // Copyright (C) 2006 The Trustees of Indiana University.
   2
   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)
   6
   7 //  Authors: Nick Edmonds
   8 //           Andrew Lumsdaine
   9
  10 #include <boost/graph/use_mpi.hpp>
  11
  12 #define CSR
  13
  14 #ifdef CSR
  15 #  include <boost/graph/distributed/compressed_sparse_row_graph.hpp>
  16 #else
  17 #  include <boost/graph/distributed/adjacency_list.hpp>
  18 #endif
  19
  20 #include <boost/config.hpp>
  21 #include <boost/throw_exception.hpp>
  22 #include <boost/graph/distributed/mpi_process_group.hpp>
  23 #include <boost/graph/distributed/concepts.hpp>
  24 #include <boost/graph/erdos_renyi_generator.hpp>
  25 #include <boost/graph/distributed/betweenness_centrality.hpp>
  26 #include <boost/random/linear_congruential.hpp>
  27 #include <boost/graph/graphviz.hpp>
  28 #include <boost/property_map/vector_property_map.hpp>
  29 #include <boost/test/minimal.hpp>
  30
  31 #ifdef BOOST_NO_EXCEPTIONS
  32 void
  33 boost::throw_exception(std::exception const& ex)
  34 {
  35     std::cout << ex.what() << std::endl;
  36     abort();
  37 }
  38 #endif
  39
  40 /****************************************************************************
  41  * Edge weight generator iterator                                           *
  42  ****************************************************************************/
  43 template<typename F, typename RandomGenerator>
  44 class generator_iterator
  45 {
  46 public:
  47   typedef std::input_iterator_tag iterator_category;
  48   typedef typename F::result_type value_type;
  49   typedef const value_type&       reference;
  50   typedef const value_type*       pointer;
  51   typedef void                    difference_type;
  52
  53   explicit
  54   generator_iterator(RandomGenerator& gen, const F& f = F())
  55     : f(f), gen(&gen)
  56   {
  57     value = this->f(gen);
  58   }
  59
  60   reference operator*() const  { return value; }
  61   pointer   operator->() const { return &value; }
  62
  63   generator_iterator& operator++()
  64   {
  65     value = f(*gen);
  66     return *this;
  67   }
  68
  69   generator_iterator operator++(int)
  70   {
  71     generator_iterator temp(*this);
  72     ++(*this);
  73     return temp;
  74   }
  75
  76   bool operator==(const generator_iterator& other) const
  77   { return f == other.f; }
  78
  79   bool operator!=(const generator_iterator& other) const
  80   { return !(*this == other); }
  81
  82 private:
  83   F f;
  84   RandomGenerator* gen;
  85   value_type value;
  86 };
  87
  88 template<typename F, typename RandomGenerator>
  89 inline generator_iterator<F, RandomGenerator>
  90 make_generator_iterator( RandomGenerator& gen, const F& f)
  91 { return generator_iterator<F, RandomGenerator>(gen, f); }
  92
  93 using namespace boost;
  94 using boost::graph::distributed::mpi_process_group;
  95
  96 typedef int weight_type;
  97
  98 struct WeightedEdge {
  99   WeightedEdge(weight_type weight = 0) : weight(weight) { }
 100
 101   weight_type weight;
 102
 103   template<typename Archiver>
 104   void serialize(Archiver& ar, const unsigned int /*version*/)
 105   {
 106     ar & weight;
 107   }
 108 };
 109
 110 int test_main(int argc, char* argv[])
 111 {
 112   mpi::environment env(argc, argv);
 113
 114 #ifdef CSR
 115   typedef compressed_sparse_row_graph<directedS, no_property, WeightedEdge,
 116                                       no_property, distributedS<mpi_process_group> >
 117     Graph;
 118   typedef compressed_sparse_row_graph<directedS, no_property, WeightedEdge>
 119     seqGraph;
 120 #else
 121   typedef adjacency_list<vecS,
 122                          distributedS<mpi_process_group, vecS>,
 123                          directedS,
 124                          no_property,
 125                          property<edge_weight_t, int> > Graph;
 126
 127   typedef adjacency_list<vecS, vecS, directedS, no_property,
 128                          property<edge_weight_t, int> > seqGraph;
 129 #endif
 130
 131
 132   typedef sorted_erdos_renyi_iterator<minstd_rand, Graph> ERIter;
 133
 134   int n = 100;
 135   double prob = 0.1;
 136   int C = 3;
 137
 138   minstd_rand gen;
 139
 140   gen.seed(1);
 141
 142   // NOTE: Weighted betweenness centrality only works with non-zero edge weights
 143
 144   // Build graphs
 145   Graph g(edges_are_sorted, ERIter(gen, n, prob), ERIter(),
 146           make_generator_iterator(gen, uniform_int<int>(1, C)),
 147           n);
 148
 149   gen.seed(1);  // Re-seed PRNG so we get the same graph
 150
 151   seqGraph sg(
 152 #ifdef CSR
 153               edges_are_sorted,
 154 #endif
 155               ERIter(gen, n, prob), ERIter(),
 156               make_generator_iterator(gen, uniform_int<int>(1, C)),
 157               n);
 158
 159   // Test Betweenness Centrality
 160   typedef property_map<Graph, vertex_index_t>::const_type IndexMap;
 161   typedef iterator_property_map<std::vector<int>::iterator, IndexMap>
 162     CentralityMap;
 163
 164   std::vector<int> centralityS(num_vertices(g), 0);
 165   CentralityMap centrality(centralityS.begin(), get(vertex_index, g));
 166
 167   brandes_betweenness_centrality(g, centrality);
 168
 169   std::vector<int> weightedCentralityS(num_vertices(g), 0);
 170   CentralityMap weightedCentrality(weightedCentralityS.begin(), get(vertex_index, g));
 171
 172   brandes_betweenness_centrality(g, centrality_map(weightedCentrality).
 173 #ifdef CSR
 174                                  weight_map(get(&WeightedEdge::weight, g)));
 175 #else
 176                                  weight_map(get(edge_weight, g)));
 177 #endif
 178
 179   int g_cpd = central_point_dominance(g, centrality);
 180
 181   //
 182   //  Non-distributed (embarassingly parallel) Betweenness Centrality
 183   //
 184   typedef boost::graph::parallel::process_group_type<Graph>::type
 185     process_group_type;
 186
 187   process_group_type pg = process_group(g);
 188
 189   process_group_type::process_id_type id = process_id(pg);
 190   process_group_type::process_size_type p = num_processes(pg);
 191
 192   typedef property_map<seqGraph, vertex_index_t>::const_type seqIndexMap;
 193   typedef iterator_property_map<std::vector<int>::iterator, seqIndexMap> seqCentralityMap;
 194
 195   std::vector<int> nonDistributedCentralityS(num_vertices(sg), 0);
 196   seqCentralityMap nonDistributedCentrality(nonDistributedCentralityS.begin(), get(vertex_index, sg));
 197
 198   std::vector<int> nonDistributedWeightedCentralityS(num_vertices(sg), 0);
 199   seqCentralityMap nonDistributedWeightedCentrality(nonDistributedWeightedCentralityS.begin(),
 200                                                     get(vertex_index, sg));
 201
 202   non_distributed_brandes_betweenness_centrality(pg, sg, nonDistributedCentrality);
 203
 204   non_distributed_brandes_betweenness_centrality(pg, sg,
 205                                                  centrality_map(nonDistributedWeightedCentrality).
 206 #ifdef CSR
 207                                                  weight_map(get(&WeightedEdge::weight, sg)));
 208 #else
 209                                                  weight_map(get(edge_weight, sg)));
 210 #endif
 211
 212   //
 213   // Verify
 214   //
 215   std::vector<int> seqCentralityS(num_vertices(sg), 0);
 216   seqCentralityMap seqCentrality(seqCentralityS.begin(), get(vertex_index, sg));
 217
 218   std::vector<int> seqWeightedCentralityS(num_vertices(sg), 0);
 219   seqCentralityMap seqWeightedCentrality(seqWeightedCentralityS.begin(), get(vertex_index, sg));
 220
 221   brandes_betweenness_centrality(sg, seqCentrality);
 222
 223   brandes_betweenness_centrality(sg, centrality_map(seqWeightedCentrality).
 224 #ifdef CSR
 225                                  weight_map(get(&WeightedEdge::weight, sg)));
 226 #else
 227                                  weight_map(get(edge_weight, sg)));
 228 #endif
 229
 230   int sg_cpd = central_point_dominance(sg, seqCentrality);
 231
 232   // Verify exact betweenness centrality
 233   //
 234   // We're cheating when we map vertices in g to vertices in sg
 235   // since we know that g is using the block distribution here
 236   typedef property_map<Graph, vertex_owner_t>::const_type OwnerMap;
 237   typedef property_map<Graph, vertex_local_t>::const_type LocalMap;
 238
 239   OwnerMap owner = get(vertex_owner, g);
 240   LocalMap local = get(vertex_local, g);
 241
 242   bool passed = true;
 243
 244   {
 245     typedef graph_traits<Graph>::vertex_iterator vertex_iterator;
 246     vertex_iterator v, v_end;
 247
 248     for (boost::tie(v, v_end) = vertices(g); v != v_end; ++v) {
 249       if (get(centrality, *v) != seqCentralityS[(n/p) * get(owner, *v) + get(local, *v)]) {
 250         std::cerr << "  " << id << ": Error - centrality of " << get(local, *v) << "@" << get(owner, *v)
 251                   << " does not match the sequential result (" << get(centrality, *v) << " vs. "
 252                   << seqCentralityS[(n/p) * get(owner, *v) + get(local, *v)] << ")\n";
 253         passed = false;
 254       }
 255
 256       if (get(weightedCentrality, *v) != seqWeightedCentralityS[(n/p) * get(owner, *v) + get(local, *v)]) {
 257         std::cerr << "  " << id << ": Error - weighted centrality of " << get(local, *v) << "@" << get(owner, *v)
 258                   << " does not match the sequential result (" << get(weightedCentrality, *v) << " vs. "
 259                   << seqWeightedCentralityS[(n/p) * get(owner, *v) + get(local, *v)] << ")\n";
 260         passed = false;
 261       }
 262     }
 263   }
 264
 265   if (id == 0) {
 266     typedef graph_traits<seqGraph>::vertex_iterator vertex_iterator;
 267     vertex_iterator v, v_end;
 268
 269     for (boost::tie(v, v_end) = vertices(sg); v != v_end; ++v) {
 270       if (get(seqCentrality, *v) != get(nonDistributedCentrality, *v)) {
 271         std::cerr << "  " << id << ": Error - non-distributed centrality of " << *v
 272                   << " does not match the sequential result (" << get(nonDistributedCentrality, *v)
 273                   << " vs. " << get(seqCentrality, *v) << ")\n";
 274         passed = false;
 275       }
 276
 277       if (get(seqWeightedCentrality, *v) != get(nonDistributedWeightedCentrality, *v)) {
 278         std::cerr << "  " << id << ": Error - non-distributed weighted centrality of " << *v
 279                   << " does not match the sequential result (" << get(nonDistributedWeightedCentrality, *v)
 280                   << " vs. " << get(seqCentrality, *v) << ")\n";
 281         passed = false;
 282       }
 283     }
 284   }
 285
 286   if (g_cpd != sg_cpd) {
 287     passed = false;
 288     std::cerr << "Central point dominance did not match the sequential result\n";
 289   }
 290
 291   if (!passed)
 292     MPI_Abort(MPI_COMM_WORLD, -1);
 293
 294   return 0;
 295 }