ceph/src/boost/boost/graph/distributed/vertex_list_adaptor.hpp

   1 // Copyright (C) 2004-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: Douglas Gregor
   8 //           Andrew Lumsdaine
   9
  10 #ifndef BOOST_VERTEX_LIST_ADAPTOR_HPP
  11 #define BOOST_VERTEX_LIST_ADAPTOR_HPP
  12
  13 #ifndef BOOST_GRAPH_USE_MPI
  14 #error "Parallel BGL files should not be included unless <boost/graph/use_mpi.hpp> has been included"
  15 #endif
  16
  17 #include <boost/graph/graph_traits.hpp>
  18 #include <vector>
  19 #include <boost/shared_ptr.hpp>
  20 #include <boost/property_map/property_map.hpp>
  21 #include <boost/graph/parallel/algorithm.hpp>
  22 #include <boost/graph/parallel/container_traits.hpp>
  23 #include <boost/property_map/vector_property_map.hpp>
  24
  25 namespace boost { namespace graph {
  26
  27 // --------------------------------------------------------------------------
  28 // Global index map built from a distribution
  29 // --------------------------------------------------------------------------
  30 template<typename Distribution, typename OwnerPropertyMap,
  31          typename LocalPropertyMap>
  32 class distribution_global_index_map
  33 {
  34  public:
  35   typedef std::size_t value_type;
  36   typedef value_type reference;
  37   typedef typename property_traits<OwnerPropertyMap>::key_type key_type;
  38   typedef readable_property_map_tag category;
  39
  40   distribution_global_index_map(const Distribution& distribution,
  41                                 const OwnerPropertyMap& owner,
  42                                 const LocalPropertyMap& local)
  43     : distribution_(distribution), owner(owner), local(local) { }
  44
  45   Distribution distribution_;
  46   OwnerPropertyMap owner;
  47   LocalPropertyMap local;
  48 };
  49
  50 template<typename Distribution, typename OwnerPropertyMap,
  51          typename LocalPropertyMap>
  52 inline
  53 typename distribution_global_index_map<Distribution, OwnerPropertyMap,
  54                                        LocalPropertyMap>::value_type
  55 get(const distribution_global_index_map<Distribution, OwnerPropertyMap,
  56                                         LocalPropertyMap>& p,
  57     typename distribution_global_index_map<Distribution, OwnerPropertyMap,
  58                                            LocalPropertyMap>::key_type x)
  59 {
  60   using boost::get;
  61   return p.distribution_.global(get(p.owner, x), get(p.local, x));
  62 }
  63
  64 template<typename Graph, typename Distribution>
  65 inline
  66 distribution_global_index_map<
  67   Distribution,
  68   typename property_map<Graph, vertex_owner_t>::const_type,
  69   typename property_map<Graph, vertex_local_t>::const_type>
  70 make_distribution_global_index_map(const Graph& g, const Distribution& d)
  71 {
  72   typedef distribution_global_index_map<
  73             Distribution,
  74             typename property_map<Graph, vertex_owner_t>::const_type,
  75             typename property_map<Graph, vertex_local_t>::const_type>
  76     result_type;
  77   return result_type(d, get(vertex_owner, g), get(vertex_local, g));
  78 }
  79
  80 // --------------------------------------------------------------------------
  81 // Global index map built from a distributed index map and list of vertices
  82 // --------------------------------------------------------------------------
  83 template<typename IndexMap>
  84 class stored_global_index_map : public IndexMap
  85 {
  86  public:
  87   typedef readable_property_map_tag category;
  88
  89   stored_global_index_map(const IndexMap& index_map) : IndexMap(index_map) {
  90     // When we have a global index, we need to always have the indices
  91     // of every key we've seen
  92     this->set_max_ghost_cells(0);
  93   }
  94 };
  95
  96 // --------------------------------------------------------------------------
  97 // Global index map support code
  98 // --------------------------------------------------------------------------
  99 namespace detail {
 100   template<typename PropertyMap, typename ForwardIterator>
 101   inline void
 102   initialize_global_index_map(const PropertyMap&,
 103                               ForwardIterator, ForwardIterator)
 104   { }
 105
 106   template<typename IndexMap, typename ForwardIterator>
 107   void
 108   initialize_global_index_map(stored_global_index_map<IndexMap>& p,
 109                               ForwardIterator first, ForwardIterator last)
 110   {
 111     using std::distance;
 112
 113     typedef typename property_traits<IndexMap>::value_type size_t;
 114
 115     size_t n = distance(first, last);
 116     for (size_t i = 0; i < n; ++i, ++first) local_put(p, *first, i);
 117   }
 118 }
 119
 120 // --------------------------------------------------------------------------
 121 // Adapts a Distributed Vertex List Graph to a Vertex List Graph
 122 // --------------------------------------------------------------------------
 123 template<typename Graph, typename GlobalIndexMap>
 124 class vertex_list_adaptor : public graph_traits<Graph>
 125 {
 126   typedef graph_traits<Graph> inherited;
 127
 128   typedef typename inherited::traversal_category base_traversal_category;
 129
 130  public:
 131   typedef typename inherited::vertex_descriptor vertex_descriptor;
 132   typedef typename std::vector<vertex_descriptor>::iterator vertex_iterator;
 133   typedef typename std::vector<vertex_descriptor>::size_type
 134     vertices_size_type;
 135
 136   struct traversal_category
 137     : public virtual base_traversal_category,
 138       public virtual vertex_list_graph_tag {};
 139
 140   vertex_list_adaptor(const Graph& g,
 141                       const GlobalIndexMap& index_map = GlobalIndexMap())
 142     : g(&g), index_map(index_map)
 143   {
 144     using boost::vertices;
 145
 146     all_vertices_.reset(new std::vector<vertex_descriptor>());
 147     all_gather(process_group(), vertices(g).first, vertices(g).second,
 148                *all_vertices_);
 149     detail::initialize_global_index_map(this->index_map,
 150                                         all_vertices_->begin(),
 151                                         all_vertices_->end());
 152   }
 153
 154   const Graph& base() const { return *g; }
 155
 156   // --------------------------------------------------------------------------
 157   // Distributed Container
 158   // --------------------------------------------------------------------------
 159   typedef typename boost::graph::parallel::process_group_type<Graph>::type
 160     process_group_type;
 161
 162   process_group_type process_group() const
 163   {
 164     using boost::graph::parallel::process_group;
 165     return process_group(*g);
 166   }
 167
 168   std::pair<vertex_iterator, vertex_iterator> vertices() const
 169   { return std::make_pair(all_vertices_->begin(), all_vertices_->end()); }
 170
 171   vertices_size_type num_vertices() const { return all_vertices_->size(); }
 172
 173   GlobalIndexMap get_index_map() const { return index_map; }
 174
 175  private:
 176   const Graph* g;
 177   GlobalIndexMap index_map;
 178   shared_ptr<std::vector<vertex_descriptor> > all_vertices_;
 179 };
 180
 181 template<typename Graph, typename GlobalIndexMap>
 182 inline vertex_list_adaptor<Graph, GlobalIndexMap>
 183 make_vertex_list_adaptor(const Graph& g, const GlobalIndexMap& index_map)
 184 { return vertex_list_adaptor<Graph, GlobalIndexMap>(g, index_map); }
 185
 186 namespace detail {
 187   template<typename Graph>
 188   class default_global_index_map
 189   {
 190     typedef typename graph_traits<Graph>::vertices_size_type value_type;
 191     typedef typename property_map<Graph, vertex_index_t>::const_type local_map;
 192
 193   public:
 194     typedef vector_property_map<value_type, local_map> distributed_map;
 195     typedef stored_global_index_map<distributed_map> type;
 196   };
 197 }
 198
 199 template<typename Graph>
 200 inline
 201 vertex_list_adaptor<Graph,
 202                     typename detail::default_global_index_map<Graph>::type>
 203 make_vertex_list_adaptor(const Graph& g)
 204 {
 205   typedef typename detail::default_global_index_map<Graph>::type
 206     GlobalIndexMap;
 207   typedef typename detail::default_global_index_map<Graph>::distributed_map
 208     DistributedMap;
 209   typedef vertex_list_adaptor<Graph, GlobalIndexMap> result_type;
 210   return result_type(g,
 211                      GlobalIndexMap(DistributedMap(num_vertices(g),
 212                                                    get(vertex_index, g))));
 213 }
 214
 215 // --------------------------------------------------------------------------
 216 // Incidence Graph
 217 // --------------------------------------------------------------------------
 218 template<typename Graph, typename GlobalIndexMap>
 219 inline typename vertex_list_adaptor<Graph, GlobalIndexMap>::vertex_descriptor
 220 source(typename vertex_list_adaptor<Graph, GlobalIndexMap>::edge_descriptor e,
 221        const vertex_list_adaptor<Graph, GlobalIndexMap>& g)
 222 { return source(e, g.base()); }
 223
 224 template<typename Graph, typename GlobalIndexMap>
 225 inline typename vertex_list_adaptor<Graph, GlobalIndexMap>::vertex_descriptor
 226 target(typename vertex_list_adaptor<Graph, GlobalIndexMap>::edge_descriptor e,
 227        const vertex_list_adaptor<Graph, GlobalIndexMap>& g)
 228 { return target(e, g.base()); }
 229
 230 template<typename Graph, typename GlobalIndexMap>
 231 inline
 232 std::pair<typename vertex_list_adaptor<Graph, GlobalIndexMap>::out_edge_iterator,
 233           typename vertex_list_adaptor<Graph, GlobalIndexMap>::out_edge_iterator>
 234 out_edges(typename vertex_list_adaptor<Graph, GlobalIndexMap>::vertex_descriptor v,
 235           const vertex_list_adaptor<Graph, GlobalIndexMap>& g)
 236 { return out_edges(v, g.base()); }
 237
 238 template<typename Graph, typename GlobalIndexMap>
 239 inline typename vertex_list_adaptor<Graph, GlobalIndexMap>::degree_size_type
 240 out_degree(typename vertex_list_adaptor<Graph, GlobalIndexMap>::vertex_descriptor v,
 241           const vertex_list_adaptor<Graph, GlobalIndexMap>& g)
 242 { return out_degree(v, g.base()); }
 243
 244 // --------------------------------------------------------------------------
 245 // Bidirectional Graph
 246 // --------------------------------------------------------------------------
 247 template<typename Graph, typename GlobalIndexMap>
 248 inline
 249 std::pair<typename vertex_list_adaptor<Graph, GlobalIndexMap>::in_edge_iterator,
 250           typename vertex_list_adaptor<Graph, GlobalIndexMap>::in_edge_iterator>
 251 in_edges(typename vertex_list_adaptor<Graph, GlobalIndexMap>::vertex_descriptor v,
 252          const vertex_list_adaptor<Graph, GlobalIndexMap>& g)
 253 { return in_edges(v, g.base()); }
 254
 255 template<typename Graph, typename GlobalIndexMap>
 256 inline typename vertex_list_adaptor<Graph, GlobalIndexMap>::degree_size_type
 257 in_degree(typename vertex_list_adaptor<Graph, GlobalIndexMap>::vertex_descriptor v,
 258           const vertex_list_adaptor<Graph, GlobalIndexMap>& g)
 259 { return in_degree(v, g.base()); }
 260
 261 template<typename Graph, typename GlobalIndexMap>
 262 inline typename vertex_list_adaptor<Graph, GlobalIndexMap>::degree_size_type
 263 degree(typename vertex_list_adaptor<Graph, GlobalIndexMap>::vertex_descriptor v,
 264        const vertex_list_adaptor<Graph, GlobalIndexMap>& g)
 265 { return degree(v, g.base()); }
 266
 267 // --------------------------------------------------------------------------
 268 // Adjacency Graph
 269 // --------------------------------------------------------------------------
 270 template<typename Graph, typename GlobalIndexMap>
 271 inline
 272 std::pair<typename vertex_list_adaptor<Graph, GlobalIndexMap>::adjacency_iterator,
 273           typename vertex_list_adaptor<Graph, GlobalIndexMap>::adjacency_iterator>
 274 adjacent_vertices(typename vertex_list_adaptor<Graph, GlobalIndexMap>::vertex_descriptor v,
 275                   const vertex_list_adaptor<Graph, GlobalIndexMap>& g)
 276 { return adjacent_vertices(v, g.base()); }
 277
 278
 279 // --------------------------------------------------------------------------
 280 // Vertex List Graph
 281 // --------------------------------------------------------------------------
 282 template<typename Graph, typename GlobalIndexMap>
 283 inline
 284 std::pair<typename vertex_list_adaptor<Graph, GlobalIndexMap>::vertex_iterator,
 285           typename vertex_list_adaptor<Graph, GlobalIndexMap>::vertex_iterator>
 286 vertices(const vertex_list_adaptor<Graph, GlobalIndexMap>& g)
 287 { return g.vertices(); }
 288
 289 template<typename Graph, typename GlobalIndexMap>
 290 inline
 291 typename vertex_list_adaptor<Graph, GlobalIndexMap>::vertices_size_type
 292 num_vertices(const vertex_list_adaptor<Graph, GlobalIndexMap>& g)
 293 { return g.num_vertices(); }
 294
 295 // --------------------------------------------------------------------------
 296 // Edge List Graph
 297 // --------------------------------------------------------------------------
 298 template<typename Graph, typename GlobalIndexMap>
 299 inline
 300 std::pair<typename vertex_list_adaptor<Graph, GlobalIndexMap>::edge_iterator,
 301           typename vertex_list_adaptor<Graph, GlobalIndexMap>::edge_iterator>
 302 edges(const vertex_list_adaptor<Graph, GlobalIndexMap>& g)
 303 { return edges(g.base()); }
 304
 305 template<typename Graph, typename GlobalIndexMap>
 306 inline
 307 typename vertex_list_adaptor<Graph, GlobalIndexMap>::edges_size_type
 308 num_edges(const vertex_list_adaptor<Graph, GlobalIndexMap>& g)
 309 { return num_edges(g.base()); }
 310
 311 // --------------------------------------------------------------------------
 312 // Property Graph
 313 // --------------------------------------------------------------------------
 314 template<typename PropertyTag, typename Graph, typename GlobalIndexMap>
 315 inline typename property_map<Graph, PropertyTag>::type
 316 get(PropertyTag p, vertex_list_adaptor<Graph, GlobalIndexMap>& g)
 317 { return get(p, g.base()); }
 318
 319 template<typename PropertyTag, typename Graph, typename GlobalIndexMap>
 320 inline typename property_map<Graph, PropertyTag>::const_type
 321 get(PropertyTag p, const vertex_list_adaptor<Graph, GlobalIndexMap>& g)
 322 { return get(p, g.base()); }
 323
 324 template<typename PropertyTag, typename Graph, typename GlobalIndexMap>
 325 inline typename property_traits<
 326                   typename property_map<Graph, PropertyTag>::type
 327                 >::value_type
 328 get(PropertyTag p, const vertex_list_adaptor<Graph, GlobalIndexMap>& g,
 329     typename property_traits<
 330                typename property_map<Graph, PropertyTag>::type
 331              >::key_type const& x)
 332 { return get(p, g.base(), x); }
 333
 334 template<typename PropertyTag, typename Graph, typename GlobalIndexMap>
 335 inline void
 336 put(PropertyTag p, vertex_list_adaptor<Graph, GlobalIndexMap>& g,
 337     typename property_traits<
 338                typename property_map<Graph, PropertyTag>::type
 339              >::key_type const& x,
 340     typename property_traits<
 341                typename property_map<Graph, PropertyTag>::type
 342              >::value_type const& v)
 343 { return put(p, g.base(), x, v); }
 344
 345 // --------------------------------------------------------------------------
 346 // Property Graph: vertex_index property
 347 // --------------------------------------------------------------------------
 348 template<typename Graph, typename GlobalIndexMap>
 349 inline GlobalIndexMap
 350 get(vertex_index_t, const vertex_list_adaptor<Graph, GlobalIndexMap>& g)
 351 { return g.get_index_map(); }
 352
 353 template<typename Graph, typename GlobalIndexMap>
 354 inline typename vertex_list_adaptor<Graph, GlobalIndexMap>::vertices_size_type
 355 get(vertex_index_t, const vertex_list_adaptor<Graph, GlobalIndexMap>& g,
 356     typename vertex_list_adaptor<Graph, GlobalIndexMap>::vertex_descriptor x)
 357 { return get(g.get_index_map(), x); }
 358
 359 // --------------------------------------------------------------------------
 360 // Adjacency Matrix Graph
 361 // --------------------------------------------------------------------------
 362 template<typename Graph, typename GlobalIndexMap>
 363 std::pair<typename vertex_list_adaptor<Graph, GlobalIndexMap>::edge_descriptor,
 364           bool>
 365 edge(typename vertex_list_adaptor<Graph, GlobalIndexMap>::vertex_descriptor u,
 366      typename vertex_list_adaptor<Graph, GlobalIndexMap>::vertex_descriptor v,
 367      vertex_list_adaptor<Graph, GlobalIndexMap>& g)
 368 { return edge(u, v, g.base()); }
 369
 370 } } // end namespace boost::graph
 371
 372 namespace boost {
 373
 374 // --------------------------------------------------------------------------
 375 // Property Graph: vertex_index property
 376 // --------------------------------------------------------------------------
 377 template<typename Graph, typename GlobalIndexMap>
 378 class property_map<vertex_index_t,
 379                    graph::vertex_list_adaptor<Graph, GlobalIndexMap> >
 380 {
 381 public:
 382   typedef GlobalIndexMap type;
 383   typedef type const_type;
 384 };
 385
 386 template<typename Graph, typename GlobalIndexMap>
 387 class property_map<vertex_index_t,
 388                    const graph::vertex_list_adaptor<Graph, GlobalIndexMap> >
 389 {
 390 public:
 391   typedef GlobalIndexMap type;
 392   typedef type const_type;
 393 };
 394
 395 using graph::distribution_global_index_map;
 396 using graph::make_distribution_global_index_map;
 397 using graph::stored_global_index_map;
 398 using graph::make_vertex_list_adaptor;
 399 using graph::vertex_list_adaptor;
 400
 401 } // end namespace boost
 402
 403 #endif // BOOST_VERTEX_LIST_ADAPTOR_HPP