ceph/src/boost/libs/graph_parallel/test/named_vertices_hash_test.cpp

   1 // Copyright (C) 2007-2008 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 #include <boost/graph/use_mpi.hpp>
   8 #include <boost/config.hpp>
   9 #include <boost/throw_exception.hpp>
  10 #include <boost/mpl/print.hpp>
  11 #include <boost/graph/distributed/adjacency_list.hpp>
  12 #include <boost/graph/distributed/mpi_process_group.hpp>
  13 #include <boost/graph/iteration_macros.hpp>
  14 #include <boost/core/lightweight_test.hpp>
  15 #include <string>
  16 #include <iostream>
  17
  18 #ifdef BOOST_NO_EXCEPTIONS
  19 void
  20 boost::throw_exception(std::exception const& ex)
  21 {
  22     std::cout << ex.what() << std::endl;
  23     abort();
  24 }
  25 #endif
  26
  27 using namespace boost;
  28 using boost::graph::distributed::mpi_process_group;
  29
  30 /// City structure to be attached to each vertex
  31 struct City {
  32   City() {}
  33
  34   City(const std::string& name, int population = -1)
  35     : name(name), population(population) { }
  36
  37   template<typename Archiver>
  38   void serialize(Archiver& ar, const unsigned int /*version*/)
  39   {
  40     ar & name & population;
  41   }
  42
  43   std::string name;
  44   int population;
  45 };
  46
  47 /// Our distribution function
  48 template<typename T>
  49 struct named_vertices_hashed_distribution
  50 {
  51   template<typename ProcessGroup>
  52   named_vertices_hashed_distribution(const ProcessGroup& pg,
  53         std::size_t /*num_vertices*/ = 0)
  54     : n(num_processes(pg)) { }
  55
  56   int operator()(const T& value) const
  57   {
  58     return hasher(value) % n;
  59   }
  60
  61   std::size_t n;
  62   boost::hash<T> hasher;
  63 };
  64
  65 typedef named_vertices_hashed_distribution<std::string> hasher_type;
  66
  67 namespace boost { namespace graph {
  68
  69 /// Use the City name as a key for indexing cities in a graph
  70 template<>
  71 struct internal_vertex_name<City>
  72 {
  73   typedef multi_index::member<City, std::string, &City::name> type;
  74 };
  75
  76 /// Allow the graph to build cities given only their names (filling in
  77 /// the defaults for fields).
  78 template<>
  79 struct internal_vertex_constructor<City>
  80 {
  81   typedef vertex_from_name<City> type;
  82 };
  83
  84 //   namespace distributed
  85 //   {
  86 //     /// Use the City name as the source for the distribution hasher
  87 //     ///
  88 //     /// This is currently needed in addition to the specification of this
  89 //     /// hasher functor as the 3rd template parameter to the distributedS
  90 //     /// template.
  91 //     template<>
  92 //     struct internal_vertex_name_distribution<City>
  93 //     {
  94 //       typedef named_vertices_hashed_distribution<std::string> type;
  95 //     };
  96 //   }
  97
  98 } } // end namespace boost::graph
  99
 100 /// Our road map, where each of the vertices are cities
 101 typedef boost::adjacency_list<vecS,
 102                        distributedS<mpi_process_group, vecS, hasher_type>,
 103                        bidirectionalS, City> RoadMap;
 104 typedef graph_traits<RoadMap>::vertex_descriptor Vertex;
 105
 106 int main(int argc, char** argv)
 107 {
 108   boost::mpi::environment env(argc, argv);
 109
 110   mpi_process_group pg;
 111   RoadMap map; // (pg, hasher_type(pg));
 112
 113   int rank = process_id(pg);
 114   bool i_am_root = rank == 0;
 115
 116   /// Create vertices for Bloomington, Indianapolis, Chicago. Everyone will
 117   /// try to do this, but only one of each vertex will be added.
 118   Vertex bloomington = add_vertex(City("Bloomington", 69291), map);
 119   Vertex chicago = add_vertex(City("Chicago", 9500000), map);
 120   Vertex indianapolis = add_vertex(City("Indianapolis", 791926), map);
 121
 122   BGL_FORALL_VERTICES(city, map, RoadMap)
 123     std::cout << rank << ": " << map[city].name << ", population "
 124               << map[city].population << std::endl;
 125
 126   BOOST_TEST(*find_vertex("Bloomington", map) == bloomington);
 127   BOOST_TEST(*find_vertex("Indianapolis", map) == indianapolis);
 128   BOOST_TEST(*find_vertex("Chicago", map) == chicago);
 129
 130   if (i_am_root) {
 131     add_edge(bloomington, "Indianapolis", map);
 132     add_edge("Indianapolis", chicago, map);
 133     add_edge("Indianapolis", "Cincinnati", map);
 134   }
 135
 136   synchronize(map);
 137
 138   {
 139     property_map<RoadMap, std::string City::*>::type
 140       city_name = get(&City::name, map);
 141
 142     BGL_FORALL_EDGES(road, map, RoadMap)
 143       std::cout << rank << ": " << get(city_name, source(road, map)) << " -> "
 144                 << get(city_name, target(road, map)) << std::endl;
 145
 146     synchronize(map);
 147   }
 148
 149   // Make sure the vertex for "Cincinnati" was created implicitly
 150   Vertex cincinnati = *find_vertex("Cincinnati", map);
 151   if (get(get(vertex_owner, map), cincinnati)
 152         == process_id(map.process_group()))
 153     BOOST_TEST(map[cincinnati].population == -1);
 154
 155   synchronize(map);
 156
 157   return boost::report_errors();
 158 }