graph/distributed/vertex_list_adaptor.hpp

0001 // Copyright (C) 2004-2006 The Trustees of Indiana University.
0002
0003 // Use, modification and distribution is subject to the Boost Software
0004 // License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
0005 // http://www.boost.org/LICENSE_1_0.txt)
0006
0007 //  Authors: Douglas Gregor
0008 //           Andrew Lumsdaine
0009
0010 #ifndef BOOST_VERTEX_LIST_ADAPTOR_HPP
0011 #define BOOST_VERTEX_LIST_ADAPTOR_HPP
0012
0013 #ifndef BOOST_GRAPH_USE_MPI
0014 #error "Parallel BGL files should not be included unless <boost/graph/use_mpi.hpp> has been included"
0015 #endif
0016
0017 #include <boost/graph/graph_traits.hpp>
0018 #include <vector>
0019 #include <boost/shared_ptr.hpp>
0020 #include <boost/property_map/property_map.hpp>
0021 #include <boost/property_map/parallel/parallel_property_maps.hpp>
0022 #include <boost/graph/parallel/algorithm.hpp>
0023 #include <boost/graph/parallel/container_traits.hpp>
0024 #include <boost/property_map/vector_property_map.hpp>
0025
0026 namespace boost { namespace graph {
0027
0028 // --------------------------------------------------------------------------
0029 // Global index map built from a distribution
0030 // --------------------------------------------------------------------------
0031 template<typename Distribution, typename OwnerPropertyMap,
0032          typename LocalPropertyMap>
0033 class distribution_global_index_map
0034 {
0035  public:
0036   typedef std::size_t value_type;
0037   typedef value_type reference;
0038   typedef typename property_traits<OwnerPropertyMap>::key_type key_type;
0039   typedef readable_property_map_tag category;
0040
0041   distribution_global_index_map(const Distribution& distribution,
0042                                 const OwnerPropertyMap& owner,
0043                                 const LocalPropertyMap& local)
0044     : distribution_(distribution), owner(owner), local(local) { }
0045
0046   Distribution distribution_;
0047   OwnerPropertyMap owner;
0048   LocalPropertyMap local;
0049 };
0050
0051 template<typename Distribution, typename OwnerPropertyMap,
0052          typename LocalPropertyMap>
0053 inline
0054 typename distribution_global_index_map<Distribution, OwnerPropertyMap,
0055                                        LocalPropertyMap>::value_type
0056 get(const distribution_global_index_map<Distribution, OwnerPropertyMap,
0057                                         LocalPropertyMap>& p,
0058     typename distribution_global_index_map<Distribution, OwnerPropertyMap,
0059                                            LocalPropertyMap>::key_type x)
0060 {
0061   using boost::get;
0062   return p.distribution_.global(get(p.owner, x), get(p.local, x));
0063 }
0064
0065 template<typename Graph, typename Distribution>
0066 inline
0067 distribution_global_index_map<
0068   Distribution,
0069   typename property_map<Graph, vertex_owner_t>::const_type,
0070   typename property_map<Graph, vertex_local_t>::const_type>
0071 make_distribution_global_index_map(const Graph& g, const Distribution& d)
0072 {
0073   typedef distribution_global_index_map<
0074             Distribution,
0075             typename property_map<Graph, vertex_owner_t>::const_type,
0076             typename property_map<Graph, vertex_local_t>::const_type>
0077     result_type;
0078   return result_type(d, get(vertex_owner, g), get(vertex_local, g));
0079 }
0080
0081 // --------------------------------------------------------------------------
0082 // Global index map built from a distributed index map and list of vertices
0083 // --------------------------------------------------------------------------
0084 template<typename IndexMap>
0085 class stored_global_index_map : public IndexMap
0086 {
0087  public:
0088   typedef readable_property_map_tag category;
0089
0090   stored_global_index_map(const IndexMap& index_map) : IndexMap(index_map) {
0091     // When we have a global index, we need to always have the indices
0092     // of every key we've seen
0093     this->set_max_ghost_cells(0);
0094   }
0095 };
0096
0097 // --------------------------------------------------------------------------
0098 // Global index map support code
0099 // --------------------------------------------------------------------------
0100 namespace detail {
0101   template<typename PropertyMap, typename ForwardIterator>
0102   inline void
0103   initialize_global_index_map(const PropertyMap&,
0104                               ForwardIterator, ForwardIterator)
0105   { }
0106
0107   template<typename IndexMap, typename ForwardIterator>
0108   void
0109   initialize_global_index_map(stored_global_index_map<IndexMap>& p,
0110                               ForwardIterator first, ForwardIterator last)
0111   {
0112     using std::distance;
0113
0114     typedef typename property_traits<IndexMap>::value_type size_t;
0115
0116     size_t n = distance(first, last);
0117     for (size_t i = 0; i < n; ++i, ++first) local_put(p, *first, i);
0118   }
0119 }
0120
0121 // --------------------------------------------------------------------------
0122 // Adapts a Distributed Vertex List Graph to a Vertex List Graph
0123 // --------------------------------------------------------------------------
0124 template<typename Graph, typename GlobalIndexMap>
0125 class vertex_list_adaptor : public graph_traits<Graph>
0126 {
0127   typedef graph_traits<Graph> inherited;
0128
0129   typedef typename inherited::traversal_category base_traversal_category;
0130
0131  public:
0132   typedef typename inherited::vertex_descriptor vertex_descriptor;
0133   typedef typename std::vector<vertex_descriptor>::iterator vertex_iterator;
0134   typedef typename std::vector<vertex_descriptor>::size_type
0135     vertices_size_type;
0136
0137   struct traversal_category
0138     : public virtual base_traversal_category,
0139       public virtual vertex_list_graph_tag {};
0140
0141   vertex_list_adaptor(const Graph& g,
0142                       const GlobalIndexMap& index_map = GlobalIndexMap())
0143     : g(&g), index_map(index_map)
0144   {
0145     using boost::vertices;
0146
0147     all_vertices_.reset(new std::vector<vertex_descriptor>());
0148     all_gather(process_group(), vertices(g).first, vertices(g).second,
0149                *all_vertices_);
0150     detail::initialize_global_index_map(this->index_map,
0151                                         all_vertices_->begin(),
0152                                         all_vertices_->end());
0153   }
0154
0155   const Graph& base() const { return *g; }
0156
0157   // --------------------------------------------------------------------------
0158   // Distributed Container
0159   // --------------------------------------------------------------------------
0160   typedef typename boost::graph::parallel::process_group_type<Graph>::type
0161     process_group_type;
0162
0163   process_group_type process_group() const
0164   {
0165     using boost::graph::parallel::process_group;
0166     return process_group(*g);
0167   }
0168
0169   std::pair<vertex_iterator, vertex_iterator> vertices() const
0170   { return std::make_pair(all_vertices_->begin(), all_vertices_->end()); }
0171
0172   vertices_size_type num_vertices() const { return all_vertices_->size(); }
0173
0174   GlobalIndexMap get_index_map() const { return index_map; }
0175
0176  private:
0177   const Graph* g;
0178   GlobalIndexMap index_map;
0179   shared_ptr<std::vector<vertex_descriptor> > all_vertices_;
0180 };
0181
0182 template<typename Graph, typename GlobalIndexMap>
0183 inline vertex_list_adaptor<Graph, GlobalIndexMap>
0184 make_vertex_list_adaptor(const Graph& g, const GlobalIndexMap& index_map)
0185 { return vertex_list_adaptor<Graph, GlobalIndexMap>(g, index_map); }
0186
0187 namespace detail {
0188   template<typename Graph>
0189   class default_global_index_map
0190   {
0191     typedef typename graph_traits<Graph>::vertices_size_type value_type;
0192     typedef typename property_map<Graph, vertex_index_t>::const_type local_map;
0193
0194   public:
0195     typedef vector_property_map<value_type, local_map> distributed_map;
0196     typedef stored_global_index_map<distributed_map> type;
0197   };
0198 }
0199
0200 template<typename Graph>
0201 inline
0202 vertex_list_adaptor<Graph,
0203                     typename detail::default_global_index_map<Graph>::type>
0204 make_vertex_list_adaptor(const Graph& g)
0205 {
0206   typedef typename detail::default_global_index_map<Graph>::type
0207     GlobalIndexMap;
0208   typedef typename detail::default_global_index_map<Graph>::distributed_map
0209     DistributedMap;
0210   typedef vertex_list_adaptor<Graph, GlobalIndexMap> result_type;
0211   return result_type(g,
0212                      GlobalIndexMap(DistributedMap(num_vertices(g),
0213                                                    get(vertex_index, g))));
0214 }
0215
0216 // --------------------------------------------------------------------------
0217 // Incidence Graph
0218 // --------------------------------------------------------------------------
0219 template<typename Graph, typename GlobalIndexMap>
0220 inline typename vertex_list_adaptor<Graph, GlobalIndexMap>::vertex_descriptor
0221 source(typename vertex_list_adaptor<Graph, GlobalIndexMap>::edge_descriptor e,
0222        const vertex_list_adaptor<Graph, GlobalIndexMap>& g)
0223 { return source(e, g.base()); }
0224
0225 template<typename Graph, typename GlobalIndexMap>
0226 inline typename vertex_list_adaptor<Graph, GlobalIndexMap>::vertex_descriptor
0227 target(typename vertex_list_adaptor<Graph, GlobalIndexMap>::edge_descriptor e,
0228        const vertex_list_adaptor<Graph, GlobalIndexMap>& g)
0229 { return target(e, g.base()); }
0230
0231 template<typename Graph, typename GlobalIndexMap>
0232 inline
0233 std::pair<typename vertex_list_adaptor<Graph, GlobalIndexMap>::out_edge_iterator,
0234           typename vertex_list_adaptor<Graph, GlobalIndexMap>::out_edge_iterator>
0235 out_edges(typename vertex_list_adaptor<Graph, GlobalIndexMap>::vertex_descriptor v,
0236           const vertex_list_adaptor<Graph, GlobalIndexMap>& g)
0237 { return out_edges(v, g.base()); }
0238
0239 template<typename Graph, typename GlobalIndexMap>
0240 inline typename vertex_list_adaptor<Graph, GlobalIndexMap>::degree_size_type
0241 out_degree(typename vertex_list_adaptor<Graph, GlobalIndexMap>::vertex_descriptor v,
0242           const vertex_list_adaptor<Graph, GlobalIndexMap>& g)
0243 { return out_degree(v, g.base()); }
0244
0245 // --------------------------------------------------------------------------
0246 // Bidirectional Graph
0247 // --------------------------------------------------------------------------
0248 template<typename Graph, typename GlobalIndexMap>
0249 inline
0250 std::pair<typename vertex_list_adaptor<Graph, GlobalIndexMap>::in_edge_iterator,
0251           typename vertex_list_adaptor<Graph, GlobalIndexMap>::in_edge_iterator>
0252 in_edges(typename vertex_list_adaptor<Graph, GlobalIndexMap>::vertex_descriptor v,
0253          const vertex_list_adaptor<Graph, GlobalIndexMap>& g)
0254 { return in_edges(v, g.base()); }
0255
0256 template<typename Graph, typename GlobalIndexMap>
0257 inline typename vertex_list_adaptor<Graph, GlobalIndexMap>::degree_size_type
0258 in_degree(typename vertex_list_adaptor<Graph, GlobalIndexMap>::vertex_descriptor v,
0259           const vertex_list_adaptor<Graph, GlobalIndexMap>& g)
0260 { return in_degree(v, g.base()); }
0261
0262 template<typename Graph, typename GlobalIndexMap>
0263 inline typename vertex_list_adaptor<Graph, GlobalIndexMap>::degree_size_type
0264 degree(typename vertex_list_adaptor<Graph, GlobalIndexMap>::vertex_descriptor v,
0265        const vertex_list_adaptor<Graph, GlobalIndexMap>& g)
0266 { return degree(v, g.base()); }
0267
0268 // --------------------------------------------------------------------------
0269 // Adjacency Graph
0270 // --------------------------------------------------------------------------
0271 template<typename Graph, typename GlobalIndexMap>
0272 inline
0273 std::pair<typename vertex_list_adaptor<Graph, GlobalIndexMap>::adjacency_iterator,
0274           typename vertex_list_adaptor<Graph, GlobalIndexMap>::adjacency_iterator>
0275 adjacent_vertices(typename vertex_list_adaptor<Graph, GlobalIndexMap>::vertex_descriptor v,
0276                   const vertex_list_adaptor<Graph, GlobalIndexMap>& g)
0277 { return adjacent_vertices(v, g.base()); }
0278
0279
0280 // --------------------------------------------------------------------------
0281 // Vertex List Graph
0282 // --------------------------------------------------------------------------
0283 template<typename Graph, typename GlobalIndexMap>
0284 inline
0285 std::pair<typename vertex_list_adaptor<Graph, GlobalIndexMap>::vertex_iterator,
0286           typename vertex_list_adaptor<Graph, GlobalIndexMap>::vertex_iterator>
0287 vertices(const vertex_list_adaptor<Graph, GlobalIndexMap>& g)
0288 { return g.vertices(); }
0289
0290 template<typename Graph, typename GlobalIndexMap>
0291 inline
0292 typename vertex_list_adaptor<Graph, GlobalIndexMap>::vertices_size_type
0293 num_vertices(const vertex_list_adaptor<Graph, GlobalIndexMap>& g)
0294 { return g.num_vertices(); }
0295
0296 // --------------------------------------------------------------------------
0297 // Edge List Graph
0298 // --------------------------------------------------------------------------
0299 template<typename Graph, typename GlobalIndexMap>
0300 inline
0301 std::pair<typename vertex_list_adaptor<Graph, GlobalIndexMap>::edge_iterator,
0302           typename vertex_list_adaptor<Graph, GlobalIndexMap>::edge_iterator>
0303 edges(const vertex_list_adaptor<Graph, GlobalIndexMap>& g)
0304 { return edges(g.base()); }
0305
0306 template<typename Graph, typename GlobalIndexMap>
0307 inline
0308 typename vertex_list_adaptor<Graph, GlobalIndexMap>::edges_size_type
0309 num_edges(const vertex_list_adaptor<Graph, GlobalIndexMap>& g)
0310 { return num_edges(g.base()); }
0311
0312 // --------------------------------------------------------------------------
0313 // Property Graph
0314 // --------------------------------------------------------------------------
0315 template<typename PropertyTag, typename Graph, typename GlobalIndexMap>
0316 inline typename property_map<Graph, PropertyTag>::type
0317 get(PropertyTag p, vertex_list_adaptor<Graph, GlobalIndexMap>& g)
0318 { return get(p, g.base()); }
0319
0320 template<typename PropertyTag, typename Graph, typename GlobalIndexMap>
0321 inline typename property_map<Graph, PropertyTag>::const_type
0322 get(PropertyTag p, const vertex_list_adaptor<Graph, GlobalIndexMap>& g)
0323 { return get(p, g.base()); }
0324
0325 template<typename PropertyTag, typename Graph, typename GlobalIndexMap>
0326 inline typename property_traits<
0327                   typename property_map<Graph, PropertyTag>::type
0328                 >::value_type
0329 get(PropertyTag p, const vertex_list_adaptor<Graph, GlobalIndexMap>& g,
0330     typename property_traits<
0331                typename property_map<Graph, PropertyTag>::type
0332              >::key_type const& x)
0333 { return get(p, g.base(), x); }
0334
0335 template<typename PropertyTag, typename Graph, typename GlobalIndexMap>
0336 inline void
0337 put(PropertyTag p, vertex_list_adaptor<Graph, GlobalIndexMap>& g,
0338     typename property_traits<
0339                typename property_map<Graph, PropertyTag>::type
0340              >::key_type const& x,
0341     typename property_traits<
0342                typename property_map<Graph, PropertyTag>::type
0343              >::value_type const& v)
0344 { return put(p, g.base(), x, v); }
0345
0346 // --------------------------------------------------------------------------
0347 // Property Graph: vertex_index property
0348 // --------------------------------------------------------------------------
0349 template<typename Graph, typename GlobalIndexMap>
0350 inline GlobalIndexMap
0351 get(vertex_index_t, const vertex_list_adaptor<Graph, GlobalIndexMap>& g)
0352 { return g.get_index_map(); }
0353
0354 template<typename Graph, typename GlobalIndexMap>
0355 inline typename vertex_list_adaptor<Graph, GlobalIndexMap>::vertices_size_type
0356 get(vertex_index_t, const vertex_list_adaptor<Graph, GlobalIndexMap>& g,
0357     typename vertex_list_adaptor<Graph, GlobalIndexMap>::vertex_descriptor x)
0358 { return get(g.get_index_map(), x); }
0359
0360 // --------------------------------------------------------------------------
0361 // Adjacency Matrix Graph
0362 // --------------------------------------------------------------------------
0363 template<typename Graph, typename GlobalIndexMap>
0364 std::pair<typename vertex_list_adaptor<Graph, GlobalIndexMap>::edge_descriptor,
0365           bool>
0366 edge(typename vertex_list_adaptor<Graph, GlobalIndexMap>::vertex_descriptor u,
0367      typename vertex_list_adaptor<Graph, GlobalIndexMap>::vertex_descriptor v,
0368      vertex_list_adaptor<Graph, GlobalIndexMap>& g)
0369 { return edge(u, v, g.base()); }
0370
0371 } } // end namespace boost::graph
0372
0373 namespace boost {
0374
0375 // --------------------------------------------------------------------------
0376 // Property Graph: vertex_index property
0377 // --------------------------------------------------------------------------
0378 template<typename Graph, typename GlobalIndexMap>
0379 class property_map<vertex_index_t,
0380                    graph::vertex_list_adaptor<Graph, GlobalIndexMap> >
0381 {
0382 public:
0383   typedef GlobalIndexMap type;
0384   typedef type const_type;
0385 };
0386
0387 template<typename Graph, typename GlobalIndexMap>
0388 class property_map<vertex_index_t,
0389                    const graph::vertex_list_adaptor<Graph, GlobalIndexMap> >
0390 {
0391 public:
0392   typedef GlobalIndexMap type;
0393   typedef type const_type;
0394 };
0395
0396 using graph::distribution_global_index_map;
0397 using graph::make_distribution_global_index_map;
0398 using graph::stored_global_index_map;
0399 using graph::make_vertex_list_adaptor;
0400 using graph::vertex_list_adaptor;
0401
0402 } // end namespace boost
0403
0404 #endif // BOOST_VERTEX_LIST_ADAPTOR_HPP