graph/distributed/compressed_sparse_row_graph.hpp

0001 // Copyright (C) 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 //           Jeremiah Willcock
0009 //           Andrew Lumsdaine
0010
0011 // Distributed compressed sparse row graph type
0012
0013 #ifndef BOOST_GRAPH_DISTRIBUTED_CSR_HPP
0014 #define BOOST_GRAPH_DISTRIBUTED_CSR_HPP
0015
0016 #ifndef BOOST_GRAPH_USE_MPI
0017 #error "Parallel BGL files should not be included unless <boost/graph/use_mpi.hpp> has been included"
0018 #endif
0019
0020 #include <boost/assert.hpp>
0021 #include <boost/graph/compressed_sparse_row_graph.hpp>
0022 #include <boost/graph/distributed/selector.hpp>
0023 #include <boost/mpl/if.hpp>
0024 #include <boost/type_traits/is_same.hpp>
0025 #include <boost/graph/distributed/concepts.hpp>
0026 #include <boost/graph/parallel/properties.hpp>
0027 #include <boost/graph/parallel/distribution.hpp>
0028 #include <boost/property_map/parallel/local_property_map.hpp>
0029 #include <boost/property_map/parallel/distributed_property_map.hpp>
0030
0031 namespace boost {
0032
0033 // Distributed and sequential inplace ctors have the same signature so
0034 // we need a separate tag for distributed inplace ctors
0035 enum distributed_construct_inplace_from_sources_and_targets_t
0036   {distributed_construct_inplace_from_sources_and_targets};
0037
0038 // The number of bits we reserve for the processor ID.
0039 // DPG TBD: This is a hack. It will eventually be a run-time quantity.
0040 static const int processor_bits = 8;
0041
0042 // Tag class for a distributed CSR graph
0043 struct distributed_csr_tag
0044   : public virtual distributed_graph_tag,
0045     public virtual distributed_vertex_list_graph_tag,
0046     public virtual distributed_edge_list_graph_tag,
0047     public virtual incidence_graph_tag,
0048     public virtual adjacency_graph_tag {};
0049
0050 template<typename VertexProperty, typename EdgeProperty,
0051          typename GraphProperty, typename ProcessGroup, typename InVertex,
0052          typename InDistribution, typename InEdgeIndex>
0053 class compressed_sparse_row_graph<
0054          directedS, VertexProperty, EdgeProperty, GraphProperty,
0055          distributedS<ProcessGroup, InVertex, InDistribution>,
0056          InEdgeIndex>
0057 {
0058   typedef compressed_sparse_row_graph self_type;
0059
0060  private:
0061   /**
0062    *  Determine the type used to represent vertices in the graph. If
0063    *  the user has overridden the default, use the user's
0064    *  parameter. Otherwise, fall back to std::size_t.
0065    */
0066   typedef typename mpl::if_<is_same<InVertex, defaultS>,
0067                             std::size_t,
0068                             InVertex>::type Vertex;
0069
0070   /**
0071    *  Determine the type used to represent edges in the graph. If
0072    *  the user has overridden the default (which is to be the same as
0073    *  the distributed vertex selector type), use the user's
0074    *  parameter. Otherwise, fall back to the value of @c Vertex.
0075    */
0076   typedef typename mpl::if_<is_same<InEdgeIndex,
0077                                     distributedS<ProcessGroup, InVertex,
0078                                                  InDistribution> >,
0079                             Vertex,
0080                             InEdgeIndex>::type EdgeIndex;
0081
0082  public:
0083   /**
0084    * The type of the CSR graph that will be stored locally.
0085    */
0086   typedef compressed_sparse_row_graph<directedS, VertexProperty, EdgeProperty,
0087                                       GraphProperty, Vertex, EdgeIndex>
0088     base_type;
0089
0090   // -----------------------------------------------------------------
0091   // Graph concept requirements
0092   typedef Vertex vertex_descriptor;
0093   typedef typename graph_traits<base_type>::edge_descriptor edge_descriptor;
0094   typedef directed_tag directed_category;
0095   typedef allow_parallel_edge_tag edge_parallel_category;
0096   typedef distributed_csr_tag traversal_category;
0097   static vertex_descriptor null_vertex();
0098
0099   // -----------------------------------------------------------------
0100   // Distributed Vertex List Graph concept requirements
0101   typedef Vertex vertices_size_type;
0102   class vertex_iterator;
0103
0104   // -----------------------------------------------------------------
0105   // Distributed Edge List Graph concept requirements
0106   typedef EdgeIndex edges_size_type;
0107   class edge_iterator;
0108
0109   // -----------------------------------------------------------------
0110   // Incidence Graph concept requirements
0111   typedef typename graph_traits<base_type>::out_edge_iterator
0112     out_edge_iterator;
0113   typedef typename graph_traits<base_type>::degree_size_type
0114     degree_size_type;
0115
0116   // -----------------------------------------------------------------
0117   // Adjacency Graph concept requirements
0118   typedef typename graph_traits<base_type>::adjacency_iterator
0119     adjacency_iterator;
0120
0121   // Note: This graph type does not model Bidirectional Graph.
0122   // However, this typedef is required to satisfy graph_traits.
0123   typedef void in_edge_iterator;
0124
0125   // -----------------------------------------------------------------
0126   // Distributed Container concept requirements
0127   typedef ProcessGroup process_group_type;
0128   typedef boost::parallel::variant_distribution<process_group_type, Vertex>
0129     distribution_type;
0130
0131   // -----------------------------------------------------------------
0132   // Workarounds
0133   // NOTE: This graph type does not have old-style graph properties. It only
0134   // accepts bundles.
0135   typedef no_property vertex_property_type;
0136   typedef no_property edge_property_type;
0137   typedef no_property graph_property_type;
0138   typedef typename mpl::if_<is_void<VertexProperty>,
0139                             void****,
0140                             VertexProperty>::type vertex_bundled;
0141   typedef typename mpl::if_<is_void<EdgeProperty>,
0142                             void****,
0143                             EdgeProperty>::type edge_bundled;
0144   typedef typename mpl::if_<is_void<GraphProperty>,
0145                             void****,
0146                             GraphProperty>::type graph_bundled;
0147
0148   // -----------------------------------------------------------------
0149   // Useful types
0150   typedef typename ProcessGroup::process_id_type process_id_type;
0151
0152   // -----------------------------------------------------------------
0153   // Graph constructors
0154   compressed_sparse_row_graph(const ProcessGroup& pg = ProcessGroup())
0155     : m_process_group(pg), m_distribution(parallel::block(pg, 0)) {}
0156
0157   compressed_sparse_row_graph(const GraphProperty& prop,
0158                               const ProcessGroup& pg = ProcessGroup())
0159     : m_process_group(pg), m_distribution(parallel::block(pg, 0)) {}
0160
0161   compressed_sparse_row_graph(vertices_size_type numverts,
0162                               const ProcessGroup& pg = ProcessGroup())
0163     : m_process_group(pg), m_distribution(parallel::block(pg, 0)),
0164       m_base(numverts)
0165   {}
0166
0167   compressed_sparse_row_graph(vertices_size_type numverts,
0168                               const GraphProperty& prop,
0169                               const ProcessGroup& pg = ProcessGroup())
0170     : m_process_group(pg), m_distribution(parallel::block(pg, 0)),
0171       m_base(numverts)
0172   {}
0173
0174   template <typename Distribution>
0175   compressed_sparse_row_graph(vertices_size_type numverts,
0176                               const ProcessGroup& pg,
0177                               const Distribution& dist)
0178     : m_process_group(pg), m_distribution(dist), m_base(numverts) {}
0179
0180   template <typename Distribution>
0181   compressed_sparse_row_graph(vertices_size_type numverts,
0182                               const GraphProperty& prop,
0183                               const ProcessGroup& pg,
0184                               const Distribution& dist)
0185     : m_process_group(pg), m_distribution(dist), m_base(numverts) {}
0186
0187   template <typename InputIterator>
0188   compressed_sparse_row_graph(edges_are_unsorted_t,
0189                               InputIterator edge_begin, InputIterator edge_end,
0190                               vertices_size_type numverts,
0191                               const ProcessGroup& pg = ProcessGroup(),
0192                               const GraphProperty& prop = GraphProperty());
0193
0194   template <typename InputIterator, typename Distribution>
0195   compressed_sparse_row_graph(edges_are_unsorted_t,
0196                               InputIterator edge_begin, InputIterator edge_end,
0197                               vertices_size_type numverts,
0198                               const ProcessGroup& pg,
0199                               const Distribution& dist,
0200                               const GraphProperty& prop = GraphProperty());
0201
0202   template <typename InputIterator, typename EdgePropertyIterator>
0203   compressed_sparse_row_graph(edges_are_unsorted_t,
0204                               InputIterator edge_begin, InputIterator edge_end,
0205                               EdgePropertyIterator ep_iter,
0206                               vertices_size_type numverts,
0207                               const ProcessGroup& pg = ProcessGroup(),
0208                               const GraphProperty& prop = GraphProperty());
0209
0210   template <typename InputIterator, typename EdgePropertyIterator,
0211             typename Distribution>
0212   compressed_sparse_row_graph(edges_are_unsorted_t,
0213                               InputIterator edge_begin, InputIterator edge_end,
0214                               EdgePropertyIterator ep_iter,
0215                               vertices_size_type numverts,
0216                               const ProcessGroup& pg,
0217                               const Distribution& dist,
0218                               const GraphProperty& prop = GraphProperty());
0219
0220   template <typename InputIterator>
0221   compressed_sparse_row_graph(edges_are_sorted_t,
0222                               InputIterator edge_begin, InputIterator edge_end,
0223                               vertices_size_type numverts,
0224                               edges_size_type numedges = 0,
0225                               const ProcessGroup& pg = ProcessGroup(),
0226                               const GraphProperty& prop = GraphProperty());
0227
0228   template <typename InputIterator, typename Distribution>
0229   compressed_sparse_row_graph(edges_are_sorted_t,
0230                               InputIterator edge_begin, InputIterator edge_end,
0231                               vertices_size_type numverts,
0232                               const ProcessGroup& pg,
0233                               const Distribution& dist,
0234                               const GraphProperty& prop = GraphProperty());
0235
0236   template <typename InputIterator, typename EdgePropertyIterator>
0237   compressed_sparse_row_graph(edges_are_sorted_t,
0238                               InputIterator edge_begin, InputIterator edge_end,
0239                               EdgePropertyIterator ep_iter,
0240                               vertices_size_type numverts,
0241                               edges_size_type numedges = 0,
0242                               const ProcessGroup& pg = ProcessGroup(),
0243                               const GraphProperty& prop = GraphProperty());
0244
0245   template <typename InputIterator, typename EdgePropertyIterator,
0246             typename Distribution>
0247   compressed_sparse_row_graph(edges_are_sorted_t,
0248                               InputIterator edge_begin, InputIterator edge_end,
0249                               EdgePropertyIterator ep_iter,
0250                               vertices_size_type numverts,
0251                               const ProcessGroup& pg,
0252                               const Distribution& dist,
0253                               const GraphProperty& prop = GraphProperty());
0254
0255   template <typename MultiPassInputIterator>
0256   compressed_sparse_row_graph(edges_are_unsorted_multi_pass_t,
0257                               MultiPassInputIterator edge_begin,
0258                               MultiPassInputIterator edge_end,
0259                               vertices_size_type numverts,
0260                               const ProcessGroup& pg = ProcessGroup(),
0261                               const GraphProperty& prop = GraphProperty());
0262
0263   template <typename MultiPassInputIterator, typename Distribution>
0264   compressed_sparse_row_graph(edges_are_unsorted_multi_pass_t,
0265                               MultiPassInputIterator edge_begin,
0266                               MultiPassInputIterator edge_end,
0267                               vertices_size_type numverts,
0268                               const ProcessGroup& pg,
0269                               const Distribution& dist,
0270                               const GraphProperty& prop = GraphProperty());
0271
0272   template <typename MultiPassInputIterator, typename EdgePropertyIterator>
0273   compressed_sparse_row_graph(edges_are_unsorted_multi_pass_t,
0274                               MultiPassInputIterator edge_begin,
0275                               MultiPassInputIterator edge_end,
0276                               EdgePropertyIterator ep_iter,
0277                               vertices_size_type numverts,
0278                               const ProcessGroup& pg = ProcessGroup(),
0279                               const GraphProperty& prop = GraphProperty());
0280
0281   template <typename MultiPassInputIterator, typename EdgePropertyIterator,
0282             typename Distribution>
0283   compressed_sparse_row_graph(edges_are_unsorted_multi_pass_t,
0284                               MultiPassInputIterator edge_begin,
0285                               MultiPassInputIterator edge_end,
0286                               EdgePropertyIterator ep_iter,
0287                               vertices_size_type numverts,
0288                               const ProcessGroup& pg,
0289                               const Distribution& dist,
0290                               const GraphProperty& prop = GraphProperty());
0291
0292   template <typename Source>
0293   compressed_sparse_row_graph(distributed_construct_inplace_from_sources_and_targets_t,
0294                               std::vector<Source>& sources,
0295                               std::vector<vertex_descriptor>& targets,
0296                               vertices_size_type numverts,
0297                               const ProcessGroup& pg = ProcessGroup(),
0298                               const GraphProperty& prop = GraphProperty());
0299
0300   template <typename Distribution, typename Source>
0301   compressed_sparse_row_graph(distributed_construct_inplace_from_sources_and_targets_t,
0302                               std::vector<Source>& sources,
0303                               std::vector<vertex_descriptor>& targets,
0304                               vertices_size_type numverts,
0305                               const ProcessGroup& pg,
0306                               const Distribution& dist,
0307                               const GraphProperty& prop = GraphProperty());
0308
0309   template <typename Source>
0310   compressed_sparse_row_graph(distributed_construct_inplace_from_sources_and_targets_t,
0311                               std::vector<Source>& sources,
0312                               std::vector<vertex_descriptor>& targets,
0313                               std::vector<edge_bundled>& edge_props,
0314                               vertices_size_type numverts,
0315                               const ProcessGroup& pg = ProcessGroup(),
0316                               const GraphProperty& prop = GraphProperty());
0317
0318   template <typename Distribution, typename Source>
0319   compressed_sparse_row_graph(distributed_construct_inplace_from_sources_and_targets_t,
0320                               std::vector<Source>& sources,
0321                               std::vector<vertex_descriptor>& targets,
0322                               std::vector<edge_bundled>& edge_props,
0323                               vertices_size_type numverts,
0324                               const ProcessGroup& pg,
0325                               const Distribution& dist,
0326                               const GraphProperty& prop = GraphProperty());
0327
0328   template<typename InputIterator>
0329   compressed_sparse_row_graph(InputIterator edge_begin, InputIterator edge_end,
0330                               vertices_size_type numverts,
0331                               const ProcessGroup& pg = ProcessGroup(),
0332                               const GraphProperty& prop = GraphProperty());
0333
0334   template<typename InputIterator, typename EdgePropertyIterator>
0335   compressed_sparse_row_graph(InputIterator edge_begin, InputIterator edge_end,
0336                               EdgePropertyIterator ep_iter,
0337                               vertices_size_type numverts,
0338                               const ProcessGroup& pg = ProcessGroup(),
0339                               const GraphProperty& prop = GraphProperty());
0340
0341   template<typename InputIterator, typename Distribution>
0342   compressed_sparse_row_graph(InputIterator edge_begin, InputIterator edge_end,
0343                               vertices_size_type numverts,
0344                               const ProcessGroup& pg,
0345                               const Distribution& dist,
0346                               const GraphProperty& prop = GraphProperty());
0347
0348   template<typename InputIterator, typename EdgePropertyIterator,
0349            typename Distribution>
0350   compressed_sparse_row_graph(InputIterator edge_begin, InputIterator edge_end,
0351                               EdgePropertyIterator ep_iter,
0352                               vertices_size_type numverts,
0353                               const ProcessGroup& pg,
0354                               const Distribution& dist,
0355                               const GraphProperty& prop = GraphProperty());
0356
0357   base_type&       base()       { return m_base; }
0358   const base_type& base() const { return m_base; }
0359
0360   process_group_type process_group() const { return m_process_group.base(); }
0361
0362   distribution_type&       distribution()       { return m_distribution; }
0363   const distribution_type& distribution() const { return m_distribution; }
0364
0365   // Directly access a vertex or edge bundle
0366   vertex_bundled& operator[](vertex_descriptor v)
0367   {
0368     return get(vertex_bundle, *this, v);
0369   }
0370
0371   const vertex_bundled& operator[](vertex_descriptor v) const
0372   {
0373     return get(vertex_bundle, *this, v);
0374   }
0375
0376   edge_bundled& operator[](edge_descriptor e)
0377   {
0378     return get(edge_bundle, *this, e);
0379   }
0380
0381   const edge_bundled& operator[](edge_descriptor e) const
0382   {
0383     return get(edge_bundle, *this, e);
0384   }
0385
0386   // Create a vertex descriptor from a process ID and a local index.
0387   vertex_descriptor
0388   make_vertex_descriptor(process_id_type p, vertex_descriptor v) const
0389   {
0390     vertex_descriptor vertex_local_index_bits =
0391       sizeof(vertex_descriptor) * CHAR_BIT - processor_bits;
0392     return v | ((vertex_descriptor)p << vertex_local_index_bits);
0393   }
0394
0395   // Convert a local vertex descriptor into a global vertex descriptor
0396   vertex_descriptor local_to_global_vertex(vertex_descriptor v) const
0397   {
0398     return make_vertex_descriptor(process_id(m_process_group), v);
0399   }
0400
0401   // Structural modification
0402   vertex_descriptor add_vertex()
0403   {
0404     typename graph_traits<base_type>::vertex_descriptor v
0405       = boost::add_vertex(m_base);
0406
0407     return make_vertex_descriptor(process_id(m_process_group), v);
0408   }
0409
0410   vertex_descriptor add_vertex(const vertex_bundled& p)
0411   {
0412     typename graph_traits<base_type>::vertex_descriptor v
0413       = boost::add_vertex(m_base, p);
0414
0415     return make_vertex_descriptor(process_id(m_process_group), v);
0416   }
0417
0418   vertex_descriptor add_vertices(vertices_size_type count)
0419   {
0420     typename graph_traits<base_type>::vertex_descriptor v
0421       = boost::add_vertices(count, m_base);
0422
0423     return make_vertex_descriptor(process_id(m_process_group), v);
0424   }
0425
0426   template <typename InputIterator>
0427   void
0428   add_edges(InputIterator first, InputIterator last)
0429   { boost::add_edges_global(first, last, get(vertex_local, *this), m_base); }
0430
0431   template <typename InputIterator, typename EdgePropertyIterator>
0432   void
0433   add_edges(InputIterator first, InputIterator last,
0434             EdgePropertyIterator ep_iter,
0435             EdgePropertyIterator ep_iter_end)
0436   { boost::add_edges_global(first, last, ep_iter, ep_iter_end,
0437                             get(vertex_local, *this), m_base); }
0438
0439   template <typename InputIterator>
0440   void
0441   add_edges_sorted(InputIterator first, InputIterator last)
0442   { boost::add_edges_sorted_global(first, last,
0443                                    get(vertex_local, *this), m_base); }
0444
0445   template <typename InputIterator, typename EdgePropertyIterator>
0446   void
0447   add_edges_sorted(InputIterator first_sorted, InputIterator last_sorted,
0448                    EdgePropertyIterator ep_iter_sorted)
0449   { boost::add_edges_sorted_global(first_sorted, last_sorted, ep_iter_sorted,
0450                                    get(vertex_local, *this), m_base); }
0451
0452  protected:
0453   ProcessGroup m_process_group;
0454   distribution_type m_distribution;
0455   base_type m_base;
0456 };
0457
0458 /** @brief Helper macro containing the template parameters for the
0459  *   distributed CSR graph.
0460  *
0461  *  This macro contains all of the template parameters needed for the
0462  *  distributed compressed_sparse_row graph type. It is used to reduce
0463  *  the amount of typing required to declare free functions for this
0464  *  graph type.
0465  */
0466 #define BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS                          \
0467   typename VertexProperty, typename EdgeProperty,    \
0468   typename GraphProperty, typename ProcessGroup, typename InVertex,     \
0469   typename InDistribution, typename InEdgeIndex
0470
0471 /** @brief Helper macro containing the typical instantiation of the
0472  *   distributed CSR graph.
0473  *
0474  *  This macro contains an instantiation of the distributed CSR graph
0475  *  type using the typical template parameters names (e.g., those
0476  *  provided by the macro @c
0477  *  BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS). It is used to reduce
0478  *  the amount of typing required to declare free functions for this
0479  *  graph type.
0480  */
0481 #define BOOST_DISTRIB_CSR_GRAPH_TYPE                            \
0482   compressed_sparse_row_graph<                                  \
0483     directedS, VertexProperty, EdgeProperty, GraphProperty,      \
0484     distributedS<ProcessGroup, InVertex, InDistribution>,       \
0485     InEdgeIndex>
0486
0487 // -----------------------------------------------------------------
0488 // Graph concept operations
0489 template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS>
0490 inline typename BOOST_DISTRIB_CSR_GRAPH_TYPE::vertex_descriptor
0491 BOOST_DISTRIB_CSR_GRAPH_TYPE::null_vertex()
0492 {
0493   return graph_traits<base_type>::null_vertex();
0494 }
0495
0496 // -----------------------------------------------------------------
0497 // Incidence Graph concept operations
0498 template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS>
0499 inline typename BOOST_DISTRIB_CSR_GRAPH_TYPE::vertex_descriptor
0500 source(typename BOOST_DISTRIB_CSR_GRAPH_TYPE::edge_descriptor e,
0501        const BOOST_DISTRIB_CSR_GRAPH_TYPE&)
0502 { return e.src; }
0503
0504 template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS>
0505 inline typename BOOST_DISTRIB_CSR_GRAPH_TYPE::vertex_descriptor
0506 target(typename BOOST_DISTRIB_CSR_GRAPH_TYPE::edge_descriptor e,
0507        const BOOST_DISTRIB_CSR_GRAPH_TYPE& g)
0508 { return target(e, g.base()); }
0509
0510 template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS>
0511 inline std::pair<typename BOOST_DISTRIB_CSR_GRAPH_TYPE::out_edge_iterator,
0512                  typename BOOST_DISTRIB_CSR_GRAPH_TYPE::out_edge_iterator>
0513 out_edges(typename BOOST_DISTRIB_CSR_GRAPH_TYPE::vertex_descriptor u,
0514           const BOOST_DISTRIB_CSR_GRAPH_TYPE& g)
0515 {
0516   typedef typename BOOST_DISTRIB_CSR_GRAPH_TYPE::edges_size_type
0517     edges_size_type;
0518   typedef typename BOOST_DISTRIB_CSR_GRAPH_TYPE::edge_descriptor ed;
0519   typedef typename BOOST_DISTRIB_CSR_GRAPH_TYPE::out_edge_iterator it;
0520   edges_size_type u_local = get(vertex_local, g, u);
0521   edges_size_type u_row_start = g.base().m_forward.m_rowstart[u_local];
0522   edges_size_type next_row_start = g.base().m_forward.m_rowstart[u_local + 1];
0523   return std::make_pair(it(ed(u, u_row_start)),
0524                         it(ed(u, (std::max)(u_row_start, next_row_start))));
0525 }
0526
0527 template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS>
0528 inline typename BOOST_DISTRIB_CSR_GRAPH_TYPE::degree_size_type
0529 out_degree(typename BOOST_DISTRIB_CSR_GRAPH_TYPE::vertex_descriptor u,
0530            const BOOST_DISTRIB_CSR_GRAPH_TYPE& g)
0531 {
0532   return out_degree(get(vertex_local, g, u), g.base());
0533 }
0534
0535 // -----------------------------------------------------------------
0536 // DistributedGraph concept requirements
0537 template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS>
0538 void synchronize(const BOOST_DISTRIB_CSR_GRAPH_TYPE& g)
0539 {
0540   synchronize(g.process_group());
0541 }
0542
0543 template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS>
0544 ProcessGroup
0545 process_group(const BOOST_DISTRIB_CSR_GRAPH_TYPE& g)
0546 { return g.process_group(); }
0547
0548
0549 // -----------------------------------------------------------------
0550 // Adjacency Graph concept requirements
0551 template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS>
0552 inline std::pair<typename BOOST_DISTRIB_CSR_GRAPH_TYPE::adjacency_iterator,
0553                  typename BOOST_DISTRIB_CSR_GRAPH_TYPE::adjacency_iterator>
0554 adjacent_vertices(typename BOOST_DISTRIB_CSR_GRAPH_TYPE::vertex_descriptor u,
0555                   const BOOST_DISTRIB_CSR_GRAPH_TYPE& g)
0556 {
0557   return adjacent_vertices(get(vertex_local, g, u), g.base());
0558 }
0559
0560 // -----------------------------------------------------------------
0561 // Distributed Vertex List Graph concept operations
0562 template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS>
0563 class BOOST_DISTRIB_CSR_GRAPH_TYPE::vertex_iterator
0564   : public iterator_adaptor<vertex_iterator,
0565                             counting_iterator<Vertex>,
0566                             Vertex,
0567                             random_access_traversal_tag,
0568                             Vertex>
0569 {
0570   typedef iterator_adaptor<vertex_iterator,
0571                            counting_iterator<Vertex>,
0572                            Vertex,
0573                            random_access_traversal_tag,
0574                            Vertex> inherited;
0575  public:
0576   vertex_iterator() {}
0577
0578   explicit vertex_iterator(Vertex v, const self_type* graph)
0579     : inherited(counting_iterator<Vertex>(v)), graph(graph) { }
0580
0581   Vertex dereference() const
0582   {
0583     return graph->local_to_global_vertex(*(this->base_reference()));
0584   }
0585
0586   friend class iterator_core_access;
0587
0588  private:
0589   const self_type* graph;
0590 };
0591
0592 template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS>
0593 inline typename BOOST_DISTRIB_CSR_GRAPH_TYPE::degree_size_type
0594 num_vertices(const BOOST_DISTRIB_CSR_GRAPH_TYPE& g)
0595 {
0596   return num_vertices(g.base());
0597 }
0598
0599 template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS>
0600 inline std::pair<typename BOOST_DISTRIB_CSR_GRAPH_TYPE::vertex_iterator,
0601                  typename BOOST_DISTRIB_CSR_GRAPH_TYPE::vertex_iterator>
0602 vertices(const BOOST_DISTRIB_CSR_GRAPH_TYPE& g)
0603 {
0604   typedef typename BOOST_DISTRIB_CSR_GRAPH_TYPE::vertex_iterator
0605     vertex_iterator;
0606   return std::make_pair(vertex_iterator(0, &g),
0607                         vertex_iterator(num_vertices(g), &g));
0608 }
0609
0610 // -----------------------------------------------------------------
0611 // Distributed Edge List Graph concept operations
0612 template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS>
0613 class BOOST_DISTRIB_CSR_GRAPH_TYPE::edge_iterator
0614 {
0615  public:
0616   typedef std::forward_iterator_tag iterator_category;
0617   typedef edge_descriptor value_type;
0618
0619   typedef const edge_descriptor* pointer;
0620
0621   typedef edge_descriptor reference;
0622   typedef typename int_t<CHAR_BIT * sizeof(EdgeIndex)>::fast difference_type;
0623
0624   edge_iterator() : graph(0), current_edge(), end_of_this_vertex(0) {}
0625
0626   edge_iterator(const compressed_sparse_row_graph& graph,
0627                 edge_descriptor current_edge,
0628                 EdgeIndex end_of_this_vertex)
0629     : graph(&graph), local_src(current_edge.src), current_edge(current_edge),
0630       end_of_this_vertex(end_of_this_vertex)
0631   {
0632     // The edge that comes in has a local source vertex. Make it global.
0633     current_edge.src = graph.local_to_global_vertex(current_edge.src);
0634   }
0635
0636   // From InputIterator
0637   reference operator*() const { return current_edge; }
0638   pointer operator->() const { return &current_edge; }
0639
0640   bool operator==(const edge_iterator& o) const {
0641     return current_edge == o.current_edge;
0642   }
0643   bool operator!=(const edge_iterator& o) const {
0644     return current_edge != o.current_edge;
0645   }
0646
0647   edge_iterator& operator++()
0648   {
0649     ++current_edge.idx;
0650     while (current_edge.idx == end_of_this_vertex && local_src < num_vertices(*graph)-1) {
0651       ++local_src;
0652       current_edge.src = graph->local_to_global_vertex(local_src);
0653       end_of_this_vertex = graph->base().m_forward.m_rowstart[local_src + 1];
0654     }
0655     return *this;
0656   }
0657
0658   edge_iterator operator++(int) {
0659     edge_iterator temp = *this;
0660     ++*this;
0661     return temp;
0662   }
0663
0664  private:
0665   const compressed_sparse_row_graph* graph;
0666   EdgeIndex local_src;
0667   edge_descriptor current_edge;
0668   EdgeIndex end_of_this_vertex;
0669 };
0670
0671 template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS>
0672 inline typename BOOST_DISTRIB_CSR_GRAPH_TYPE::edges_size_type
0673 num_edges(const BOOST_DISTRIB_CSR_GRAPH_TYPE& g)
0674 {
0675   return g.base().m_forward.m_column.size();
0676 }
0677
0678 template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS>
0679 std::pair<typename BOOST_DISTRIB_CSR_GRAPH_TYPE::edge_iterator,
0680           typename BOOST_DISTRIB_CSR_GRAPH_TYPE::edge_iterator>
0681 edges(const BOOST_DISTRIB_CSR_GRAPH_TYPE& g)
0682 {
0683   typedef typename BOOST_DISTRIB_CSR_GRAPH_TYPE::vertex_descriptor Vertex;
0684   typedef typename BOOST_DISTRIB_CSR_GRAPH_TYPE::edge_iterator ei;
0685   typedef typename BOOST_DISTRIB_CSR_GRAPH_TYPE::edge_descriptor edgedesc;
0686   if (g.base().m_forward.m_rowstart.size() == 1 ||
0687       g.base().m_forward.m_column.empty()) {
0688     return std::make_pair(ei(), ei());
0689   } else {
0690     // Find the first vertex that has outgoing edges
0691     Vertex src = 0;
0692     while (g.base().m_forward.m_rowstart[src + 1] == 0) ++src;
0693     return std::make_pair(ei(g, edgedesc(src, 0), g.base().m_forward.m_rowstart[src + 1]),
0694                           ei(g, edgedesc(num_vertices(g), g.base().m_forward.m_column.size()), 0));
0695   }
0696 }
0697
0698 // -----------------------------------------------------------------
0699 // Graph constructors
0700
0701 // Returns true if a vertex belongs to a process according to a distribution
0702 template <typename OwnerMap, typename ProcessId>
0703 struct local_vertex {
0704
0705   local_vertex(OwnerMap owner, ProcessId id)
0706     : owner(owner), id(id) {}
0707
0708   template <typename Vertex>
0709   bool operator()(Vertex x)
0710   { return get(owner, x) == id; }
0711
0712   template <typename Vertex>
0713   bool operator()(Vertex x) const
0714   { return get(owner, x) == id; }
0715
0716 private:
0717   OwnerMap owner;
0718   ProcessId id;
0719 };
0720
0721 // Returns true if a vertex belongs to a process according to a distribution
0722 template <typename OwnerMap, typename ProcessId>
0723 struct local_edge {
0724
0725   local_edge(OwnerMap owner, ProcessId id)
0726     : owner(owner), id(id) {}
0727
0728   template <typename Vertex>
0729   bool operator()(std::pair<Vertex, Vertex>& x)
0730   { return get(owner, x.first) == id; }
0731
0732   template <typename Vertex>
0733   bool operator()(const std::pair<Vertex, Vertex>& x) const
0734   { return get(owner, x.first) == id; }
0735
0736 private:
0737   OwnerMap owner;
0738   ProcessId id;
0739 };
0740
0741 // Turns an index iterator into a vertex iterator
0742 template<typename IndexIterator, typename Graph>
0743 class index_to_vertex_iterator {
0744
0745 public:
0746   typedef std::input_iterator_tag iterator_category;
0747   typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
0748   typedef std::pair<Vertex, Vertex> value_type;
0749   typedef const value_type& reference;
0750   typedef const value_type* pointer;
0751   typedef void difference_type;
0752
0753   index_to_vertex_iterator(IndexIterator index,
0754                            const Graph& g)
0755     : index(index), g(g), current(to_edge(*index)) {}
0756
0757   reference operator*() { current = to_edge(*index); return current; }
0758   pointer operator->() { current = to_edge(*index); return &current; }
0759
0760   index_to_vertex_iterator& operator++()
0761   {
0762     ++index;
0763     return *this;
0764   }
0765
0766   index_to_vertex_iterator operator++(int)
0767   {
0768     index_to_vertex_iterator temp(*this);
0769     ++(*this);
0770     return temp;
0771   }
0772
0773   bool operator==(const index_to_vertex_iterator& other) const
0774   { return index == other.index; }
0775
0776   bool operator!=(const index_to_vertex_iterator& other) const
0777   { return !(*this == other); }
0778
0779 private:
0780   value_type to_edge(const typename std::iterator_traits<IndexIterator>::value_type& x)
0781   { return std::make_pair(vertex(x.first, g), vertex(x.second, g)); }
0782
0783   IndexIterator index;
0784   const Graph& g;
0785   value_type current;
0786 };
0787
0788 template <typename Distribution, typename Graph>
0789 struct index_to_vertex_func {
0790
0791   typedef typename boost::graph_traits<Graph>::vertex_descriptor vertex_descriptor;
0792   typedef typename boost::graph_traits<Graph>::vertices_size_type vertices_size_type;
0793   typedef std::pair<vertex_descriptor, vertex_descriptor> result_type;
0794   typedef std::pair<vertices_size_type, vertices_size_type> base_iterator_type;
0795
0796   index_to_vertex_func(const Distribution& dist, const Graph& g)
0797     : dist(dist), g(g) {}
0798
0799
0800   result_type operator()(const base_iterator_type& p) const
0801   {
0802     return std::make_pair(vertex(p.first, g), vertex(p.second, g));
0803   }
0804
0805 private:
0806   const Distribution& dist;
0807   const Graph& g;
0808 };
0809
0810 // NGE: This method only works with iterators that have a difference_type,
0811 // the index_to_vertex_iterator class above is retained for compatibility
0812 // with BGL generators which have no difference_type
0813 template <typename IndexIterator, typename Distribution, typename Graph>
0814 boost::transform_iterator<index_to_vertex_func<Distribution, Graph>, IndexIterator>
0815 make_index_to_vertex_iterator(IndexIterator it, const Distribution& dist,
0816                               const Graph& g) {
0817   return boost::make_transform_iterator(
0818     it, index_to_vertex_func<Distribution, Graph>(dist, g));
0819 }
0820
0821 // Forward declaration of csr_vertex_owner_map
0822 template<typename ProcessID, typename Key> class csr_vertex_owner_map;
0823
0824 template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS>
0825 template<typename InputIterator>
0826 BOOST_DISTRIB_CSR_GRAPH_TYPE::
0827 compressed_sparse_row_graph(edges_are_unsorted_t,
0828                             InputIterator edge_begin, InputIterator edge_end,
0829                             vertices_size_type numverts,
0830                             const ProcessGroup& pg,
0831                             const GraphProperty& prop)
0832   : m_process_group(pg),
0833     m_distribution(parallel::block(m_process_group, numverts)),
0834     m_base(edges_are_unsorted_global,
0835            index_to_vertex_iterator<InputIterator, BOOST_DISTRIB_CSR_GRAPH_TYPE>(edge_begin, *this),
0836            index_to_vertex_iterator<InputIterator, BOOST_DISTRIB_CSR_GRAPH_TYPE>(edge_end, *this),
0837            m_distribution.block_size(process_id(m_process_group), numverts),
0838            get(vertex_local, *this),
0839            local_vertex<csr_vertex_owner_map<process_id_type, vertex_descriptor>,
0840                         process_id_type> (get(vertex_owner, *this), process_id(pg)),
0841            prop)
0842 { }
0843
0844 template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS>
0845 template <typename InputIterator, typename Distribution>
0846 BOOST_DISTRIB_CSR_GRAPH_TYPE::
0847 compressed_sparse_row_graph(edges_are_unsorted_t,
0848                             InputIterator edge_begin, InputIterator edge_end,
0849                             vertices_size_type numverts,
0850                             const ProcessGroup& pg,
0851                             const Distribution& dist,
0852                             const GraphProperty& prop)
0853   : m_process_group(pg),
0854     m_distribution(dist),
0855     m_base(edges_are_unsorted_global,
0856            index_to_vertex_iterator<InputIterator, BOOST_DISTRIB_CSR_GRAPH_TYPE>(edge_begin, *this),
0857            index_to_vertex_iterator<InputIterator, BOOST_DISTRIB_CSR_GRAPH_TYPE>(edge_end, *this),
0858            m_distribution.block_size(process_id(m_process_group), numverts),
0859            get(vertex_local, *this),
0860            local_vertex<csr_vertex_owner_map<process_id_type, vertex_descriptor>,
0861                         process_id_type> (get(vertex_owner, *this), process_id(pg)),
0862            prop)
0863 { }
0864
0865 template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS>
0866 template<typename InputIterator, typename EdgePropertyIterator>
0867 BOOST_DISTRIB_CSR_GRAPH_TYPE::
0868 compressed_sparse_row_graph(edges_are_unsorted_t,
0869                             InputIterator edge_begin, InputIterator edge_end,
0870                             EdgePropertyIterator ep_iter,
0871                             vertices_size_type numverts,
0872                             const ProcessGroup& pg,
0873                             const GraphProperty& prop)
0874   : m_process_group(pg),
0875     m_distribution(parallel::block(m_process_group, numverts)),
0876     m_base(edges_are_unsorted_global,
0877            index_to_vertex_iterator<InputIterator, BOOST_DISTRIB_CSR_GRAPH_TYPE>(edge_begin, *this),
0878            index_to_vertex_iterator<InputIterator, BOOST_DISTRIB_CSR_GRAPH_TYPE>(edge_end, *this),
0879            ep_iter,
0880            m_distribution.block_size(process_id(m_process_group), numverts),
0881            get(vertex_local, *this),
0882            local_vertex<csr_vertex_owner_map<process_id_type, vertex_descriptor>,
0883                         process_id_type> (get(vertex_owner, *this), process_id(pg)),
0884            prop)
0885 { }
0886
0887 template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS>
0888 template <typename InputIterator, typename EdgePropertyIterator,
0889           typename Distribution>
0890 BOOST_DISTRIB_CSR_GRAPH_TYPE::
0891 compressed_sparse_row_graph(edges_are_unsorted_t,
0892                             InputIterator edge_begin, InputIterator edge_end,
0893                             EdgePropertyIterator ep_iter,
0894                             vertices_size_type numverts,
0895                             const ProcessGroup& pg,
0896                             const Distribution& dist,
0897                             const GraphProperty& prop)
0898   : m_process_group(pg),
0899     m_distribution(dist),
0900     m_base(edges_are_unsorted_global,
0901            index_to_vertex_iterator<InputIterator, BOOST_DISTRIB_CSR_GRAPH_TYPE>(edge_begin, *this),
0902            index_to_vertex_iterator<InputIterator, BOOST_DISTRIB_CSR_GRAPH_TYPE>(edge_end, *this),
0903            ep_iter,
0904            m_distribution.block_size(process_id(m_process_group), numverts),
0905            get(vertex_local, *this),
0906            local_vertex<csr_vertex_owner_map<process_id_type, vertex_descriptor>,
0907                         process_id_type> (get(vertex_owner, *this), process_id(pg)),
0908            prop)
0909 { }
0910
0911 template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS>
0912 template<typename InputIterator>
0913 BOOST_DISTRIB_CSR_GRAPH_TYPE::
0914 compressed_sparse_row_graph(edges_are_sorted_t,
0915                             InputIterator edge_begin, InputIterator edge_end,
0916                             vertices_size_type numverts,
0917                             edges_size_type numedges, // This is not used as there is no appropriate BGL ctor
0918                             const ProcessGroup& pg,
0919                             const GraphProperty& prop)
0920   : m_process_group(pg),
0921     m_distribution(parallel::block(m_process_group, numverts)),
0922     m_base(edges_are_sorted_global,
0923            index_to_vertex_iterator<InputIterator, BOOST_DISTRIB_CSR_GRAPH_TYPE>(edge_begin, *this),
0924            index_to_vertex_iterator<InputIterator, BOOST_DISTRIB_CSR_GRAPH_TYPE>(edge_end, *this),
0925            get(vertex_local, *this),
0926            local_vertex<csr_vertex_owner_map<process_id_type, vertex_descriptor>,
0927                         process_id_type> (get(vertex_owner, *this), process_id(pg)),
0928            m_distribution.block_size(process_id(m_process_group), numverts),
0929            prop)
0930 { }
0931
0932 template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS>
0933 template <typename InputIterator, typename Distribution>
0934 BOOST_DISTRIB_CSR_GRAPH_TYPE::
0935 compressed_sparse_row_graph(edges_are_sorted_t,
0936                             InputIterator edge_begin, InputIterator edge_end,
0937                             vertices_size_type numverts,
0938                             const ProcessGroup& pg,
0939                             const Distribution& dist,
0940                             const GraphProperty& prop)
0941   : m_process_group(pg),
0942     m_distribution(dist),
0943     m_base(edges_are_sorted_global,
0944            index_to_vertex_iterator<InputIterator, BOOST_DISTRIB_CSR_GRAPH_TYPE>(edge_begin, *this),
0945            index_to_vertex_iterator<InputIterator, BOOST_DISTRIB_CSR_GRAPH_TYPE>(edge_end, *this),
0946            get(vertex_local, *this),
0947            local_vertex<csr_vertex_owner_map<process_id_type, vertex_descriptor>,
0948                         process_id_type> (get(vertex_owner, *this), process_id(pg)),
0949            m_distribution.block_size(process_id(m_process_group), numverts),
0950            prop)
0951 { }
0952
0953 template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS>
0954 template<typename InputIterator, typename EdgePropertyIterator>
0955 BOOST_DISTRIB_CSR_GRAPH_TYPE::
0956 compressed_sparse_row_graph(edges_are_sorted_t,
0957                             InputIterator edge_begin, InputIterator edge_end,
0958                             EdgePropertyIterator ep_iter,
0959                             vertices_size_type numverts,
0960                             edges_size_type numedges, // This is not used as there is no appropriate BGL ctor
0961                             const ProcessGroup& pg,
0962                             const GraphProperty& prop)
0963   : m_process_group(pg),
0964     m_distribution(parallel::block(m_process_group, numverts)),
0965     m_base(edges_are_sorted_global,
0966            index_to_vertex_iterator<InputIterator, BOOST_DISTRIB_CSR_GRAPH_TYPE>(edge_begin, *this),
0967            index_to_vertex_iterator<InputIterator, BOOST_DISTRIB_CSR_GRAPH_TYPE>(edge_end, *this),
0968            ep_iter,
0969            get(vertex_local, *this),
0970            local_vertex<csr_vertex_owner_map<process_id_type, vertex_descriptor>,
0971                         process_id_type> (get(vertex_owner, *this), process_id(pg)),
0972            m_distribution.block_size(process_id(m_process_group), numverts),
0973            prop)
0974 { }
0975
0976 template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS>
0977 template<typename InputIterator, typename EdgePropertyIterator,
0978          typename Distribution>
0979 BOOST_DISTRIB_CSR_GRAPH_TYPE::
0980 compressed_sparse_row_graph(edges_are_sorted_t,
0981                             InputIterator edge_begin, InputIterator edge_end,
0982                             EdgePropertyIterator ep_iter,
0983                             vertices_size_type numverts,
0984                             const ProcessGroup& pg,
0985                             const Distribution& dist,
0986                             const GraphProperty& prop)
0987   : m_process_group(pg),
0988     m_distribution(dist),
0989     m_base(edges_are_sorted_global,
0990            index_to_vertex_iterator<InputIterator, BOOST_DISTRIB_CSR_GRAPH_TYPE>(edge_begin, *this),
0991            index_to_vertex_iterator<InputIterator, BOOST_DISTRIB_CSR_GRAPH_TYPE>(edge_end, *this),
0992            ep_iter,
0993            get(vertex_local, *this),
0994            local_vertex<csr_vertex_owner_map<process_id_type, vertex_descriptor>,
0995                         process_id_type> (get(vertex_owner, *this), process_id(pg)),
0996            m_distribution.block_size(process_id(m_process_group), numverts),
0997            prop)
0998 { }
0999
1000 template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS>
1001 template<typename MultiPassInputIterator>
1002 BOOST_DISTRIB_CSR_GRAPH_TYPE::
1003 compressed_sparse_row_graph(edges_are_unsorted_multi_pass_t,
1004                             MultiPassInputIterator edge_begin,
1005                             MultiPassInputIterator edge_end,
1006                             vertices_size_type numverts,
1007                             const ProcessGroup& pg,
1008                             const GraphProperty& prop)
1009   : m_process_group(pg),
1010     m_distribution(parallel::block(m_process_group, numverts)),
1011     m_base(edges_are_unsorted_multi_pass_global,
1012            make_index_to_vertex_iterator(edge_begin, parallel::block(m_process_group, numverts), *this),
1013            make_index_to_vertex_iterator(edge_end, parallel::block(m_process_group, numverts), *this),
1014            m_distribution.block_size(process_id(m_process_group), numverts),
1015            get(vertex_local, *this),
1016            local_vertex<csr_vertex_owner_map<process_id_type, vertex_descriptor>,
1017                         process_id_type> (get(vertex_owner, *this), process_id(pg)),
1018            prop)
1019 { }
1020
1021 template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS>
1022 template <typename MultiPassInputIterator, typename Distribution>
1023 BOOST_DISTRIB_CSR_GRAPH_TYPE::
1024 compressed_sparse_row_graph(edges_are_unsorted_multi_pass_t,
1025                             MultiPassInputIterator edge_begin,
1026                             MultiPassInputIterator edge_end,
1027                             vertices_size_type numverts,
1028                             const ProcessGroup& pg,
1029                             const Distribution& dist,
1030                             const GraphProperty& prop)
1031   : m_process_group(pg),
1032     m_distribution(dist),
1033     m_base(edges_are_unsorted_multi_pass_global,
1034            make_index_to_vertex_iterator(edge_begin, parallel::block(m_process_group, numverts), *this),
1035            make_index_to_vertex_iterator(edge_end, parallel::block(m_process_group, numverts), *this),
1036            m_distribution.block_size(process_id(m_process_group), numverts),
1037            get(vertex_local, *this),
1038            local_vertex<csr_vertex_owner_map<process_id_type, vertex_descriptor>,
1039                         process_id_type> (get(vertex_owner, *this), process_id(pg)),
1040            prop)
1041 { }
1042
1043
1044 template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS>
1045 template<typename MultiPassInputIterator, typename EdgePropertyIterator>
1046 BOOST_DISTRIB_CSR_GRAPH_TYPE::
1047 compressed_sparse_row_graph(edges_are_unsorted_multi_pass_t,
1048                             MultiPassInputIterator edge_begin,
1049                             MultiPassInputIterator edge_end,
1050                             EdgePropertyIterator ep_iter,
1051                             vertices_size_type numverts,
1052                             const ProcessGroup& pg,
1053                             const GraphProperty& prop)
1054   : m_process_group(pg),
1055     m_distribution(parallel::block(m_process_group, numverts)),
1056     m_base(edges_are_unsorted_multi_pass_global,
1057            make_index_to_vertex_iterator(edge_begin, parallel::block(m_process_group, numverts), *this),
1058            make_index_to_vertex_iterator(edge_end, parallel::block(m_process_group, numverts), *this),
1059            ep_iter,
1060            m_distribution.block_size(process_id(m_process_group), numverts),
1061            get(vertex_local, *this),
1062            local_vertex<csr_vertex_owner_map<process_id_type, vertex_descriptor>,
1063                         process_id_type> (get(vertex_owner, *this), process_id(pg)),
1064            prop)
1065 { }
1066
1067 template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS>
1068 template <typename MultiPassInputIterator, typename EdgePropertyIterator,
1069           typename Distribution>
1070 BOOST_DISTRIB_CSR_GRAPH_TYPE::
1071 compressed_sparse_row_graph(edges_are_unsorted_multi_pass_t,
1072                             MultiPassInputIterator edge_begin,
1073                             MultiPassInputIterator edge_end,
1074                             EdgePropertyIterator ep_iter,
1075                             vertices_size_type numverts,
1076                             const ProcessGroup& pg,
1077                             const Distribution& dist,
1078                             const GraphProperty& prop)
1079   : m_process_group(pg),
1080     m_distribution(dist),
1081     m_base(edges_are_unsorted_multi_pass_global,
1082            make_index_to_vertex_iterator(edge_begin, parallel::block(m_process_group, numverts), *this),
1083            make_index_to_vertex_iterator(edge_end, parallel::block(m_process_group, numverts), *this),
1084            ep_iter,
1085            m_distribution.block_size(process_id(m_process_group), numverts),
1086            get(vertex_local, *this),
1087            local_vertex<csr_vertex_owner_map<process_id_type, vertex_descriptor>,
1088                         process_id_type> (get(vertex_owner, *this), process_id(pg)),
1089            prop)
1090 { }
1091
1092 template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS>
1093 template<typename Source>
1094 BOOST_DISTRIB_CSR_GRAPH_TYPE::
1095 compressed_sparse_row_graph(distributed_construct_inplace_from_sources_and_targets_t,
1096                             std::vector<Source>& sources,
1097                             std::vector<vertex_descriptor>& targets,
1098                             vertices_size_type numverts,
1099                             const ProcessGroup& pg,
1100                             const GraphProperty& prop)
1101   : m_process_group(pg),
1102     m_distribution(parallel::block(m_process_group, numverts)),
1103     m_base(m_distribution.block_size(process_id(m_process_group), numverts))
1104 {
1105   // Convert linear indices to global indices
1106   for (edges_size_type i = 0; i < sources.size(); ++i) {
1107     sources[i] = m_distribution.local(sources[i]);
1108     targets[i] = make_vertex_descriptor(m_distribution(targets[i]),
1109                                         m_distribution.local(targets[i]));
1110   }
1111
1112   m_base.assign_sources_and_targets_global(
1113     sources, targets, m_distribution.block_size(process_id(m_process_group), numverts),
1114     identity_property_map());
1115
1116   // TODO: set property on m_base?
1117 }
1118
1119 template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS>
1120 template <typename Distribution, typename Source>
1121 BOOST_DISTRIB_CSR_GRAPH_TYPE::
1122 compressed_sparse_row_graph(distributed_construct_inplace_from_sources_and_targets_t,
1123                             std::vector<Source>& sources,
1124                             std::vector<vertex_descriptor>& targets,
1125                             vertices_size_type numverts,
1126                             const ProcessGroup& pg,
1127                             const Distribution& dist,
1128                             const GraphProperty& prop)
1129   : m_process_group(pg),
1130     m_distribution(dist),
1131     m_base(m_distribution.block_size(process_id(m_process_group), numverts))
1132 {
1133   // Convert linear indices to global indices
1134   for (edges_size_type i = 0; i < sources.size(); ++i) {
1135     sources[i] = m_distribution.local(sources[i]);
1136     targets[i] = make_vertex_descriptor(m_distribution(targets[i]),
1137                                         m_distribution.local(targets[i]));
1138   }
1139
1140   m_base.assign_sources_and_targets_global(
1141     sources, targets, m_distribution.block_size(process_id(m_process_group), numverts),
1142     identity_property_map());
1143
1144   // TODO: set property on m_base?
1145 }
1146
1147 template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS>
1148 template<typename Source>
1149 BOOST_DISTRIB_CSR_GRAPH_TYPE::
1150 compressed_sparse_row_graph(distributed_construct_inplace_from_sources_and_targets_t,
1151                             std::vector<Source>& sources,
1152                             std::vector<vertex_descriptor>& targets,
1153                             std::vector<edge_bundled>& edge_props,
1154                             vertices_size_type numverts,
1155                             const ProcessGroup& pg,
1156                             const GraphProperty& prop)
1157   : m_process_group(pg),
1158     m_distribution(parallel::block(m_process_group, numverts)),
1159     m_base(m_distribution.block_size(process_id(m_process_group), numverts))
1160 {
1161   // Convert linear indices to global indices
1162   for (edges_size_type i = 0; i < sources.size(); ++i) {
1163     sources[i] = m_distribution.local(sources[i]);
1164     targets[i] = make_vertex_descriptor(m_distribution(targets[i]),
1165                                         m_distribution.local(targets[i]));
1166   }
1167
1168   m_base.assign_sources_and_targets_global(
1169     sources, targets, edge_props,
1170     m_distribution.block_size(process_id(m_process_group), numverts),
1171     identity_property_map());
1172
1173   // TODO: set property on m_base?
1174 }
1175
1176 template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS>
1177 template <typename Distribution, typename Source>
1178 BOOST_DISTRIB_CSR_GRAPH_TYPE::
1179 compressed_sparse_row_graph(distributed_construct_inplace_from_sources_and_targets_t,
1180                             std::vector<Source>& sources,
1181                             std::vector<vertex_descriptor>& targets,
1182                             std::vector<edge_bundled>& edge_props,
1183                             vertices_size_type numverts,
1184                             const ProcessGroup& pg,
1185                             const Distribution& dist,
1186                             const GraphProperty& prop)
1187   : m_process_group(pg),
1188     m_distribution(dist),
1189     m_base(m_distribution.block_size(process_id(m_process_group), numverts))
1190 {
1191   // Convert linear indices to global indices
1192   for (edges_size_type i = 0; i < sources.size(); ++i) {
1193     sources[i] = m_distribution.local(sources[i]);
1194     targets[i] = make_vertex_descriptor(m_distribution(targets[i]),
1195                                         m_distribution.local(targets[i]));
1196   }
1197
1198   m_base.assign_sources_and_targets_global(
1199     sources, targets, edge_props,
1200     m_distribution.block_size(process_id(m_process_group), numverts),
1201     identity_property_map());
1202
1203   // TODO: set property on m_base?
1204 }
1205
1206 //
1207 // Old (untagged) ctors, these default to the unsorted sequential ctors
1208 //
1209 template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS>
1210 template<typename InputIterator>
1211 BOOST_DISTRIB_CSR_GRAPH_TYPE::
1212 compressed_sparse_row_graph(InputIterator edge_begin, InputIterator edge_end,
1213                             vertices_size_type numverts,
1214                             const ProcessGroup& pg,
1215                             const GraphProperty& prop)
1216   : m_process_group(pg),
1217     m_distribution(parallel::block(m_process_group, numverts)),
1218     m_base(edges_are_unsorted_global,
1219            index_to_vertex_iterator<InputIterator, BOOST_DISTRIB_CSR_GRAPH_TYPE>(edge_begin, *this),
1220            index_to_vertex_iterator<InputIterator, BOOST_DISTRIB_CSR_GRAPH_TYPE>(edge_end, *this),
1221            m_distribution.block_size(process_id(m_process_group), numverts),
1222            get(vertex_local, *this),
1223            local_vertex<csr_vertex_owner_map<process_id_type, vertex_descriptor>,
1224                         process_id_type> (get(vertex_owner, *this), process_id(pg)),
1225            prop)
1226
1227 {
1228 }
1229
1230 template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS>
1231 template<typename InputIterator, typename EdgePropertyIterator>
1232 BOOST_DISTRIB_CSR_GRAPH_TYPE::
1233 compressed_sparse_row_graph(InputIterator edge_begin, InputIterator edge_end,
1234                             EdgePropertyIterator ep_iter,
1235                             vertices_size_type numverts,
1236                             const ProcessGroup& pg,
1237                             const GraphProperty& prop)
1238   : m_process_group(pg),
1239
1240     m_distribution(parallel::block(m_process_group, numverts)),
1241     m_base(edges_are_unsorted_global,
1242            index_to_vertex_iterator<InputIterator, BOOST_DISTRIB_CSR_GRAPH_TYPE>(edge_begin, *this),
1243            index_to_vertex_iterator<InputIterator, BOOST_DISTRIB_CSR_GRAPH_TYPE>(edge_end, *this),
1244            ep_iter,
1245            m_distribution.block_size(process_id(m_process_group), numverts),
1246            get(vertex_local, *this),
1247            local_vertex<csr_vertex_owner_map<process_id_type, vertex_descriptor>,
1248                         process_id_type> (get(vertex_owner, *this), process_id(pg)),
1249            prop)
1250 {
1251 }
1252
1253 template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS>
1254 template<typename InputIterator, typename Distribution>
1255 BOOST_DISTRIB_CSR_GRAPH_TYPE::
1256 compressed_sparse_row_graph(InputIterator edge_begin, InputIterator edge_end,
1257                             vertices_size_type numverts,
1258                             const ProcessGroup& pg,
1259                             const Distribution& dist,
1260                             const GraphProperty& prop)
1261   : m_process_group(pg),
1262     m_distribution(dist),
1263     m_base(edges_are_unsorted_global,
1264            index_to_vertex_iterator<InputIterator, BOOST_DISTRIB_CSR_GRAPH_TYPE>(edge_begin, *this),
1265            index_to_vertex_iterator<InputIterator, BOOST_DISTRIB_CSR_GRAPH_TYPE>(edge_end, *this),
1266            m_distribution.block_size(process_id(m_process_group), numverts),
1267            get(vertex_local, *this),
1268            local_vertex<csr_vertex_owner_map<process_id_type, vertex_descriptor>,
1269                         process_id_type> (get(vertex_owner, *this), process_id(pg)),
1270            prop)
1271 {
1272 }
1273
1274 template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS>
1275 template<typename InputIterator, typename EdgePropertyIterator,
1276          typename Distribution>
1277 BOOST_DISTRIB_CSR_GRAPH_TYPE::
1278 compressed_sparse_row_graph(InputIterator edge_begin, InputIterator edge_end,
1279                             EdgePropertyIterator ep_iter,
1280                             vertices_size_type numverts,
1281                             const ProcessGroup& pg,
1282                             const Distribution& dist,
1283                             const GraphProperty& prop)
1284   : m_process_group(pg),
1285     m_distribution(dist),
1286     m_base(edges_are_unsorted_global,
1287            index_to_vertex_iterator<InputIterator, BOOST_DISTRIB_CSR_GRAPH_TYPE>(edge_begin, *this),
1288            index_to_vertex_iterator<InputIterator, BOOST_DISTRIB_CSR_GRAPH_TYPE>(edge_end, *this),
1289            m_distribution.block_size(process_id(m_process_group), numverts),
1290            get(vertex_local, *this),
1291            local_vertex<csr_vertex_owner_map<process_id_type, vertex_descriptor>,
1292                         process_id_type> (get(vertex_owner, *this), process_id(pg)),
1293            prop)
1294 {
1295 }
1296
1297 // -----------------------------------------------------------------
1298 // Vertex Global Property Map
1299 template<typename ProcessID, typename Key>
1300 class csr_vertex_global_map
1301 {
1302  public:
1303   // -----------------------------------------------------------------
1304   // Readable Property Map concept requirements
1305   typedef std::pair<ProcessID, Key> value_type;
1306   typedef value_type reference;
1307   typedef Key key_type;
1308   typedef readable_property_map_tag category;
1309 };
1310
1311 template<typename ProcessID, typename Key>
1312 inline std::pair<ProcessID, Key>
1313 get(csr_vertex_global_map<ProcessID, Key>,
1314     typename csr_vertex_global_map<ProcessID, Key>::key_type k)
1315 {
1316   const int local_index_bits = sizeof(Key) * CHAR_BIT - processor_bits;
1317   const Key local_index_mask = Key(-1) >> processor_bits;
1318
1319   return std::pair<ProcessID, Key>(k >> local_index_bits,
1320                                    k & local_index_mask);
1321 }
1322
1323 template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS>
1324 class property_map<BOOST_DISTRIB_CSR_GRAPH_TYPE, vertex_global_t>
1325 {
1326  public:
1327   typedef csr_vertex_global_map<
1328             typename ProcessGroup::process_id_type,
1329             typename BOOST_DISTRIB_CSR_GRAPH_TYPE::vertex_descriptor> type;
1330   typedef type const_type;
1331 };
1332
1333 template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS>
1334 inline
1335 typename property_map<BOOST_DISTRIB_CSR_GRAPH_TYPE, vertex_global_t>::type
1336 get(vertex_global_t, BOOST_DISTRIB_CSR_GRAPH_TYPE& g)
1337 {
1338   typedef typename property_map<BOOST_DISTRIB_CSR_GRAPH_TYPE, vertex_global_t>
1339     ::type result_type;
1340   return result_type();
1341 }
1342
1343 template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS>
1344 inline
1345 std::pair<typename ProcessGroup::process_id_type,
1346           typename BOOST_DISTRIB_CSR_GRAPH_TYPE::vertex_descriptor>
1347 get(vertex_global_t, BOOST_DISTRIB_CSR_GRAPH_TYPE& g,
1348     typename BOOST_DISTRIB_CSR_GRAPH_TYPE::vertex_descriptor k)
1349 {
1350   return get(vertex_global,
1351              const_cast<const BOOST_DISTRIB_CSR_GRAPH_TYPE&>(g),
1352              k);
1353 }
1354
1355 template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS>
1356 inline
1357 typename property_map<BOOST_DISTRIB_CSR_GRAPH_TYPE, vertex_global_t>::const_type
1358 get(vertex_global_t, const BOOST_DISTRIB_CSR_GRAPH_TYPE& g)
1359 {
1360   typedef typename property_map<BOOST_DISTRIB_CSR_GRAPH_TYPE, vertex_global_t>
1361     ::const_type result_type;
1362   return result_type();
1363 }
1364
1365 template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS>
1366 inline
1367 std::pair<typename ProcessGroup::process_id_type,
1368           typename BOOST_DISTRIB_CSR_GRAPH_TYPE::vertex_descriptor>
1369 get(vertex_global_t, const BOOST_DISTRIB_CSR_GRAPH_TYPE& g,
1370     typename BOOST_DISTRIB_CSR_GRAPH_TYPE::vertex_descriptor k)
1371 {
1372   typedef typename BOOST_DISTRIB_CSR_GRAPH_TYPE::vertex_descriptor
1373     vertex_descriptor;
1374   typedef std::pair<typename ProcessGroup::process_id_type, vertex_descriptor>
1375     result_type;
1376   const int local_index_bits =
1377     sizeof(vertex_descriptor) * CHAR_BIT - processor_bits;
1378   const vertex_descriptor local_index_mask =
1379     vertex_descriptor(-1) >> processor_bits;
1380
1381   return result_type(k >> local_index_bits, k & local_index_mask);
1382 }
1383
1384 // -----------------------------------------------------------------
1385 // Extra, common functions
1386 template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS>
1387 inline typename BOOST_DISTRIB_CSR_GRAPH_TYPE::vertex_descriptor
1388 vertex(typename BOOST_DISTRIB_CSR_GRAPH_TYPE::vertices_size_type i,
1389        const BOOST_DISTRIB_CSR_GRAPH_TYPE& g)
1390 {
1391   return g.make_vertex_descriptor(g.distribution()(i),
1392                                   g.distribution().local(i));
1393 }
1394
1395 // Unlike for an adjacency_matrix, edge_range and edge take lg(out_degree(i))
1396 // time
1397 template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS>
1398 inline std::pair<typename BOOST_DISTRIB_CSR_GRAPH_TYPE::out_edge_iterator,
1399                  typename BOOST_DISTRIB_CSR_GRAPH_TYPE::out_edge_iterator>
1400 edge_range(typename BOOST_DISTRIB_CSR_GRAPH_TYPE::vertex_descriptor i,
1401            typename BOOST_DISTRIB_CSR_GRAPH_TYPE::vertex_descriptor j,
1402            const BOOST_DISTRIB_CSR_GRAPH_TYPE& g)
1403 {
1404   typedef typename BOOST_DISTRIB_CSR_GRAPH_TYPE::vertex_descriptor Vertex;
1405   typedef typename BOOST_DISTRIB_CSR_GRAPH_TYPE::edges_size_type EdgeIndex;
1406   typedef typename std::vector<Vertex>::const_iterator adj_iter;
1407   typedef typename BOOST_DISTRIB_CSR_GRAPH_TYPE::out_edge_iterator out_edge_iter;
1408   typedef typename BOOST_DISTRIB_CSR_GRAPH_TYPE::edge_descriptor edge_desc;
1409   std::pair<adj_iter, adj_iter> raw_adjacencies = adjacent_vertices(i, g);
1410   std::pair<adj_iter, adj_iter> adjacencies =
1411     std::equal_range(raw_adjacencies.first, raw_adjacencies.second, j);
1412   EdgeIndex idx_begin = adjacencies.first - g.base().m_forward.m_column.begin();
1413   EdgeIndex idx_end = adjacencies.second - g.base().m_forward.m_column.begin();
1414   return std::make_pair(out_edge_iter(edge_desc(i, idx_begin)),
1415                         out_edge_iter(edge_desc(i, idx_end)));
1416 }
1417
1418 template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS>
1419 inline std::pair<typename BOOST_DISTRIB_CSR_GRAPH_TYPE::edge_descriptor, bool>
1420 edge(typename BOOST_DISTRIB_CSR_GRAPH_TYPE::vertex_descriptor i,
1421      typename BOOST_DISTRIB_CSR_GRAPH_TYPE::vertex_descriptor j,
1422      const BOOST_DISTRIB_CSR_GRAPH_TYPE& g)
1423 {
1424   typedef typename BOOST_DISTRIB_CSR_GRAPH_TYPE::out_edge_iterator out_edge_iter;
1425   std::pair<out_edge_iter, out_edge_iter> range = edge_range(i, j, g);
1426   if (range.first == range.second)
1427     return std::make_pair(typename BOOST_DISTRIB_CSR_GRAPH_TYPE::edge_descriptor(),
1428                           false);
1429   else
1430     return std::make_pair(*range.first, true);
1431 }
1432
1433 // A helper that turns requests for property maps for const graphs
1434 // into property maps for non-const graphs.
1435 template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS, typename Property>
1436 class property_map<const BOOST_DISTRIB_CSR_GRAPH_TYPE, Property>
1437 {
1438  public:
1439   typedef typename property_map<BOOST_DISTRIB_CSR_GRAPH_TYPE, Property>
1440     ::const_type type;
1441   typedef type const_type;
1442 };
1443
1444 // -----------------------------------------------------------------
1445 // Structural modifiers
1446
1447 #if 0
1448 template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS>
1449 typename BOOST_DISTRIB_CSR_GRAPH_TYPE::vertex_descriptor
1450 add_vertex(BOOST_DISTRIB_CSR_GRAPH_TYPE& g)
1451 { return g.add_vertex(); }
1452
1453 template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS>
1454 typename BOOST_DISTRIB_CSR_GRAPH_TYPE::vertex_descriptor
1455 add_vertex(const typename BOOST_DISTRIB_CSR_GRAPH_TYPE::vertex_bundled& p,
1456            BOOST_DISTRIB_CSR_GRAPH_TYPE& g)
1457 { return g.add_vertex(p); }
1458
1459 template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS>
1460 typename BOOST_DISTRIB_CSR_GRAPH_TYPE::vertex_descriptor
1461 add_vertices(typename BOOST_DISTRIB_CSR_GRAPH_TYPE::vertices_size_type count,
1462              BOOST_DISTRIB_CSR_GRAPH_TYPE& g)
1463 { return g.add_vertices(count); }
1464
1465 template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS, typename InputIterator>
1466 void
1467 add_edges(InputIterator first, InputIterator last,
1468           BOOST_DISTRIB_CSR_GRAPH_TYPE& g)
1469 { g.add_edges(first, last); }
1470
1471 template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS, typename InputIterator,
1472          typename EdgePropertyIterator>
1473 void
1474 add_edges(InputIterator first, InputIterator last,
1475           EdgePropertyIterator ep_iter,
1476           EdgePropertyIterator ep_iter_end,
1477           BOOST_DISTRIB_CSR_GRAPH_TYPE& g)
1478 { return g.add_edges(first, last, ep_iter, ep_iter_end); }
1479
1480 template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS, typename InputIterator>
1481 void
1482 add_edges_sorted(InputIterator first, InputIterator last,
1483                  BOOST_DISTRIB_CSR_GRAPH_TYPE& g)
1484 { return g.add_edges_sorted(first, last); }
1485
1486 template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS, typename InputIterator,
1487          typename EdgePropertyIterator>
1488 void
1489 add_edges_sorted(InputIterator first_sorted, InputIterator last_sorted,
1490                  EdgePropertyIterator ep_iter_sorted,
1491                  BOOST_DISTRIB_CSR_GRAPH_TYPE& g)
1492 { g.add_edges_sorted(first_sorted, last_sorted, ep_iter_sorted); }
1493 #endif
1494
1495 // -----------------------------------------------------------------
1496 // Vertex Owner Property Map
1497 template<typename ProcessID, typename Key>
1498 class csr_vertex_owner_map
1499 {
1500  public:
1501   // -----------------------------------------------------------------
1502   // Readable Property Map concept requirements
1503   typedef ProcessID value_type;
1504   typedef value_type reference;
1505   typedef Key key_type;
1506   typedef readable_property_map_tag category;
1507 };
1508
1509 template<typename ProcessID, typename Key>
1510 inline ProcessID
1511 get(csr_vertex_owner_map<ProcessID, Key> pm,
1512     typename csr_vertex_owner_map<ProcessID, Key>::key_type k)
1513 {
1514   const int local_index_bits = sizeof(Key) * CHAR_BIT - processor_bits;
1515   return k >> local_index_bits;
1516 }
1517
1518 template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS>
1519 class property_map<BOOST_DISTRIB_CSR_GRAPH_TYPE, vertex_owner_t>
1520 {
1521  public:
1522   typedef csr_vertex_owner_map<
1523             typename ProcessGroup::process_id_type,
1524             typename BOOST_DISTRIB_CSR_GRAPH_TYPE::vertex_descriptor> type;
1525   typedef type const_type;
1526 };
1527
1528 template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS>
1529 inline
1530 typename property_map<BOOST_DISTRIB_CSR_GRAPH_TYPE, vertex_owner_t>::type
1531 get(vertex_owner_t, BOOST_DISTRIB_CSR_GRAPH_TYPE& g)
1532 {
1533   typedef typename property_map<BOOST_DISTRIB_CSR_GRAPH_TYPE, vertex_owner_t>
1534     ::type result_type;
1535   return result_type();
1536 }
1537
1538 template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS>
1539 inline typename ProcessGroup::process_id_type
1540 get(vertex_owner_t, BOOST_DISTRIB_CSR_GRAPH_TYPE& g,
1541     typename BOOST_DISTRIB_CSR_GRAPH_TYPE::vertex_descriptor k)
1542 {
1543   return get(vertex_owner,
1544              const_cast<const BOOST_DISTRIB_CSR_GRAPH_TYPE&>(g),
1545              k);
1546 }
1547
1548 template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS>
1549 inline
1550 typename property_map<BOOST_DISTRIB_CSR_GRAPH_TYPE, vertex_owner_t>::const_type
1551 get(vertex_owner_t, const BOOST_DISTRIB_CSR_GRAPH_TYPE& g)
1552 {
1553   typedef typename property_map<BOOST_DISTRIB_CSR_GRAPH_TYPE, vertex_owner_t>
1554     ::const_type result_type;
1555   return result_type();
1556 }
1557
1558 template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS>
1559 inline typename ProcessGroup::process_id_type
1560 get(vertex_owner_t, const BOOST_DISTRIB_CSR_GRAPH_TYPE& g,
1561     typename BOOST_DISTRIB_CSR_GRAPH_TYPE::vertex_descriptor k)
1562 {
1563   typedef typename BOOST_DISTRIB_CSR_GRAPH_TYPE::vertex_descriptor
1564     vertex_descriptor;
1565   const int local_index_bits =
1566     sizeof(vertex_descriptor) * CHAR_BIT - processor_bits;
1567   return k >> local_index_bits;
1568 }
1569
1570 // -----------------------------------------------------------------
1571 // Vertex Local Property Map
1572 template<typename Key>
1573 class csr_vertex_local_map
1574 {
1575  public:
1576   // -----------------------------------------------------------------
1577   // Readable Property Map concept requirements
1578   typedef Key value_type;
1579   typedef value_type reference;
1580   typedef Key key_type;
1581   typedef readable_property_map_tag category;
1582 };
1583
1584 template<typename Key>
1585 inline Key
1586 get(csr_vertex_local_map<Key> pm,
1587     typename csr_vertex_local_map<Key>::key_type k)
1588 {
1589   const Key local_index_mask = Key(-1) >> processor_bits;
1590   return k & local_index_mask;
1591 }
1592
1593 template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS>
1594 class property_map<BOOST_DISTRIB_CSR_GRAPH_TYPE, vertex_local_t>
1595 {
1596  public:
1597   typedef csr_vertex_local_map<
1598             typename BOOST_DISTRIB_CSR_GRAPH_TYPE::vertex_descriptor> type;
1599   typedef type const_type;
1600 };
1601
1602 template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS>
1603 inline
1604 typename property_map<BOOST_DISTRIB_CSR_GRAPH_TYPE, vertex_local_t>::type
1605 get(vertex_local_t, BOOST_DISTRIB_CSR_GRAPH_TYPE& g)
1606 {
1607   typedef typename property_map<BOOST_DISTRIB_CSR_GRAPH_TYPE, vertex_local_t>
1608     ::type result_type;
1609   return result_type();
1610 }
1611
1612 template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS>
1613 inline typename BOOST_DISTRIB_CSR_GRAPH_TYPE::vertex_descriptor
1614 get(vertex_local_t, BOOST_DISTRIB_CSR_GRAPH_TYPE& g,
1615     typename BOOST_DISTRIB_CSR_GRAPH_TYPE::vertex_descriptor k)
1616 {
1617   return get(vertex_local,
1618              const_cast<const BOOST_DISTRIB_CSR_GRAPH_TYPE&>(g),
1619              k);
1620 }
1621
1622 template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS>
1623 inline
1624 typename property_map<BOOST_DISTRIB_CSR_GRAPH_TYPE, vertex_local_t>::const_type
1625 get(vertex_local_t, const BOOST_DISTRIB_CSR_GRAPH_TYPE& g)
1626 {
1627   typedef typename property_map<BOOST_DISTRIB_CSR_GRAPH_TYPE, vertex_local_t>
1628     ::const_type result_type;
1629   return result_type();
1630 }
1631
1632 template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS>
1633 inline typename BOOST_DISTRIB_CSR_GRAPH_TYPE::vertex_descriptor
1634 get(vertex_local_t, const BOOST_DISTRIB_CSR_GRAPH_TYPE& g,
1635     typename BOOST_DISTRIB_CSR_GRAPH_TYPE::vertex_descriptor k)
1636 {
1637   typedef typename BOOST_DISTRIB_CSR_GRAPH_TYPE::vertex_descriptor
1638     vertex_descriptor;
1639   const vertex_descriptor local_index_mask =
1640     vertex_descriptor(-1) >> processor_bits;
1641   return k & local_index_mask;
1642 }
1643
1644 // -----------------------------------------------------------------
1645 // Vertex Index Property Map
1646 template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS>
1647 class property_map<BOOST_DISTRIB_CSR_GRAPH_TYPE, vertex_index_t>
1648 {
1649   typedef typename property_map<BOOST_DISTRIB_CSR_GRAPH_TYPE,
1650                                 vertex_global_t>::const_type
1651     global_map;
1652   typedef typename BOOST_DISTRIB_CSR_GRAPH_TYPE::process_group_type
1653     process_group_type;
1654
1655   typedef property_map<BOOST_DISTRIB_CSR_GRAPH_TYPE, vertex_local_t> local;
1656
1657 public:
1658   typedef local_property_map<process_group_type,
1659                              global_map,
1660                              typename local::type> type;
1661   typedef local_property_map<process_group_type,
1662                              global_map,
1663                              typename local::const_type> const_type;
1664 };
1665
1666 template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS>
1667 inline
1668 typename property_map<BOOST_DISTRIB_CSR_GRAPH_TYPE, vertex_index_t>::type
1669 get(vertex_index_t, BOOST_DISTRIB_CSR_GRAPH_TYPE& g)
1670 {
1671   typedef typename property_map<BOOST_DISTRIB_CSR_GRAPH_TYPE, vertex_index_t>
1672     ::type result_type;
1673
1674   return result_type(g.process_group(), get(vertex_global, g),
1675                      get(vertex_local, g));
1676 }
1677
1678 template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS>
1679 inline typename BOOST_DISTRIB_CSR_GRAPH_TYPE::vertices_size_type
1680 get(vertex_index_t, BOOST_DISTRIB_CSR_GRAPH_TYPE& g,
1681     typename BOOST_DISTRIB_CSR_GRAPH_TYPE::vertex_descriptor k)
1682 {
1683   return get(vertex_local, g, k);
1684 }
1685
1686 template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS>
1687 inline
1688 typename property_map<BOOST_DISTRIB_CSR_GRAPH_TYPE, vertex_index_t>::const_type
1689 get(vertex_index_t, const BOOST_DISTRIB_CSR_GRAPH_TYPE& g)
1690 {
1691   typedef typename property_map<BOOST_DISTRIB_CSR_GRAPH_TYPE, vertex_index_t>
1692     ::const_type result_type;
1693   return result_type(g.process_group(), get(vertex_global, g),
1694                      get(vertex_local, g));
1695 }
1696
1697 template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS>
1698 inline typename BOOST_DISTRIB_CSR_GRAPH_TYPE::vertices_size_type
1699 get(vertex_index_t, const BOOST_DISTRIB_CSR_GRAPH_TYPE& g,
1700     typename BOOST_DISTRIB_CSR_GRAPH_TYPE::vertex_descriptor k)
1701 {
1702   return get(vertex_local, g, k);
1703 }
1704
1705 // -----------------------------------------------------------------
1706 // Vertex Local Index Property Map
1707 template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS>
1708 class property_map<BOOST_DISTRIB_CSR_GRAPH_TYPE, vertex_local_index_t>
1709   : public property_map<BOOST_DISTRIB_CSR_GRAPH_TYPE, vertex_local_t> { };
1710
1711 template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS>
1712 inline
1713 typename property_map<BOOST_DISTRIB_CSR_GRAPH_TYPE, vertex_local_index_t>::type
1714 get(vertex_local_index_t, BOOST_DISTRIB_CSR_GRAPH_TYPE& g)
1715 {
1716   return get(vertex_local, g);
1717 }
1718
1719 template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS>
1720 inline typename BOOST_DISTRIB_CSR_GRAPH_TYPE::vertices_size_type
1721 get(vertex_local_index_t, BOOST_DISTRIB_CSR_GRAPH_TYPE& g,
1722     typename BOOST_DISTRIB_CSR_GRAPH_TYPE::vertex_descriptor k)
1723 {
1724   return get(vertex_local, g, k);
1725 }
1726
1727 template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS>
1728 inline
1729 typename property_map<BOOST_DISTRIB_CSR_GRAPH_TYPE, vertex_local_index_t>::const_type
1730 get(vertex_local_index_t, const BOOST_DISTRIB_CSR_GRAPH_TYPE& g)
1731 {
1732   return get(vertex_local, g);
1733 }
1734
1735 template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS>
1736 inline typename BOOST_DISTRIB_CSR_GRAPH_TYPE::vertices_size_type
1737 get(vertex_local_index_t, const BOOST_DISTRIB_CSR_GRAPH_TYPE& g,
1738     typename BOOST_DISTRIB_CSR_GRAPH_TYPE::vertex_descriptor k)
1739 {
1740   return get(vertex_local, g, k);
1741 }
1742
1743 // -----------------------------------------------------------------
1744 // Edge Global Property Map
1745 template<typename ProcessID, typename Vertex, typename EdgeIndex>
1746 class csr_edge_global_map
1747 {
1748  public:
1749   // -----------------------------------------------------------------
1750   // Readable Property Map concept requirements
1751   typedef detail::csr_edge_descriptor<Vertex, EdgeIndex> key_type;
1752   typedef std::pair<ProcessID, detail::csr_edge_descriptor<Vertex, EdgeIndex> > value_type;
1753   typedef value_type reference;
1754   typedef readable_property_map_tag category;
1755 };
1756
1757 template<typename ProcessID, typename Vertex, typename EdgeIndex>
1758 inline std::pair<ProcessID, detail::csr_edge_descriptor<Vertex, EdgeIndex> >
1759 get(csr_edge_global_map<ProcessID, Vertex, EdgeIndex> pm,
1760     typename csr_edge_global_map<ProcessID, Vertex, EdgeIndex>::key_type k)
1761 {
1762   const int local_index_bits = sizeof(Vertex) * CHAR_BIT - processor_bits;
1763   const Vertex local_index_mask = Vertex(-1) >> processor_bits;
1764   return std::pair<ProcessID, detail::csr_edge_descriptor<Vertex, EdgeIndex> >
1765            ((k.src >> local_index_bits),
1766             detail::csr_edge_descriptor<Vertex, EdgeIndex>(k.src & local_index_mask, k.idx));
1767 }
1768
1769 template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS>
1770 class property_map<BOOST_DISTRIB_CSR_GRAPH_TYPE, edge_global_t>
1771 {
1772  public:
1773   typedef csr_edge_global_map<
1774             typename ProcessGroup::process_id_type,
1775             typename BOOST_DISTRIB_CSR_GRAPH_TYPE::vertex_descriptor,
1776             typename BOOST_DISTRIB_CSR_GRAPH_TYPE::edges_size_type> type;
1777   typedef type const_type;
1778 };
1779
1780 template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS>
1781 inline
1782 typename property_map<BOOST_DISTRIB_CSR_GRAPH_TYPE, edge_global_t>::type
1783 get(edge_global_t, BOOST_DISTRIB_CSR_GRAPH_TYPE& g)
1784 {
1785   typedef typename property_map<BOOST_DISTRIB_CSR_GRAPH_TYPE, edge_global_t>
1786     ::type result_type;
1787   return result_type();
1788 }
1789
1790 template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS>
1791 inline
1792 std::pair<typename ProcessGroup::process_id_type,
1793           typename BOOST_DISTRIB_CSR_GRAPH_TYPE::base_type::edge_descriptor>
1794 get(edge_global_t, BOOST_DISTRIB_CSR_GRAPH_TYPE& g,
1795     typename BOOST_DISTRIB_CSR_GRAPH_TYPE::edge_descriptor k)
1796 {
1797   return get(edge_global,
1798              const_cast<const BOOST_DISTRIB_CSR_GRAPH_TYPE&>(g),
1799              k);
1800 }
1801
1802 template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS>
1803 inline
1804 typename property_map<BOOST_DISTRIB_CSR_GRAPH_TYPE, edge_global_t>::const_type
1805 get(edge_global_t, const BOOST_DISTRIB_CSR_GRAPH_TYPE& g)
1806 {
1807   typedef typename property_map<BOOST_DISTRIB_CSR_GRAPH_TYPE, edge_global_t>
1808     ::const_type result_type;
1809   return result_type();
1810 }
1811
1812 template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS>
1813 inline
1814 std::pair<typename ProcessGroup::process_id_type,
1815           typename BOOST_DISTRIB_CSR_GRAPH_TYPE::base_type::edge_descriptor>
1816 get(edge_global_t, const BOOST_DISTRIB_CSR_GRAPH_TYPE& g,
1817     typename BOOST_DISTRIB_CSR_GRAPH_TYPE::edge_descriptor k)
1818 {
1819   typedef typename BOOST_DISTRIB_CSR_GRAPH_TYPE::vertex_descriptor
1820     vertex_descriptor;
1821
1822   const int local_index_bits =
1823     sizeof(vertex_descriptor) * CHAR_BIT - processor_bits;
1824   const typename BOOST_DISTRIB_CSR_GRAPH_TYPE::edges_size_type local_index_mask =
1825     typename BOOST_DISTRIB_CSR_GRAPH_TYPE::edges_size_type(-1) >> processor_bits;
1826
1827   typedef std::pair<typename ProcessGroup::process_id_type,
1828                     typename BOOST_DISTRIB_CSR_GRAPH_TYPE::base_type::edge_descriptor>
1829     result_type;
1830
1831   return result_type(k.src >> local_index_bits,
1832                      typename BOOST_DISTRIB_CSR_GRAPH_TYPE::base_type::edge_descriptor
1833                        (k.src & local_index_mask, k.idx));
1834 }
1835
1836 // -----------------------------------------------------------------
1837 // Edge Index Property Map
1838 template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS>
1839 class property_map<BOOST_DISTRIB_CSR_GRAPH_TYPE, edge_index_t>
1840 {
1841    typedef typename property_map<BOOST_DISTRIB_CSR_GRAPH_TYPE, edge_global_t>
1842     ::type global_map;
1843
1844  public:
1845   typedef local_property_map<
1846             typename BOOST_DISTRIB_CSR_GRAPH_TYPE::process_group_type,
1847             global_map,
1848             typename property_map<typename BOOST_DISTRIB_CSR_GRAPH_TYPE::base_type, edge_index_t>::type
1849           > type;
1850   typedef type const_type;
1851 };
1852
1853 template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS>
1854 inline
1855 typename property_map<BOOST_DISTRIB_CSR_GRAPH_TYPE, edge_index_t>::type
1856 get(edge_index_t, BOOST_DISTRIB_CSR_GRAPH_TYPE& g)
1857 {
1858   typedef typename property_map<BOOST_DISTRIB_CSR_GRAPH_TYPE, edge_index_t>
1859     ::type result_type;
1860   return result_type(g.process_group(), get(edge_global, g),
1861                      get(edge_index, g.base()));
1862 }
1863
1864 template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS>
1865 inline typename BOOST_DISTRIB_CSR_GRAPH_TYPE::edges_size_type
1866 get(edge_index_t, BOOST_DISTRIB_CSR_GRAPH_TYPE& g,
1867     typename BOOST_DISTRIB_CSR_GRAPH_TYPE::edge_descriptor k)
1868 {
1869   return k.idx;
1870 }
1871
1872 template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS>
1873 inline
1874 typename property_map<BOOST_DISTRIB_CSR_GRAPH_TYPE, edge_index_t>::const_type
1875 get(edge_index_t, const BOOST_DISTRIB_CSR_GRAPH_TYPE& g)
1876 {
1877   typedef typename property_map<BOOST_DISTRIB_CSR_GRAPH_TYPE, edge_index_t>
1878     ::const_type result_type;
1879   return result_type(g.process_group(), get(edge_global, g),
1880                      get(edge_index, g.base()));
1881 }
1882
1883 template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS>
1884 inline typename BOOST_DISTRIB_CSR_GRAPH_TYPE::edges_size_type
1885 get(edge_index_t, const BOOST_DISTRIB_CSR_GRAPH_TYPE& g,
1886     typename BOOST_DISTRIB_CSR_GRAPH_TYPE::edge_descriptor k)
1887 {
1888   return k.idx;
1889 }
1890
1891 template <BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS, typename Tag>
1892 class property_map<BOOST_DISTRIB_CSR_GRAPH_TYPE, Tag> {
1893   typedef BOOST_DISTRIB_CSR_GRAPH_TYPE graph_type;
1894   typedef typename graph_type::process_group_type process_group_type;
1895   typedef typename graph_type::base_type base_graph_type;
1896   typedef typename property_map<base_graph_type, Tag>::type
1897     local_pmap;
1898   typedef typename property_map<base_graph_type, Tag>::const_type
1899     local_const_pmap;
1900
1901   typedef graph_traits<graph_type> traits;
1902   typedef typename graph_traits<base_graph_type>::vertex_descriptor local_vertex;
1903   typedef typename property_traits<local_pmap>::key_type local_key_type;
1904
1905   typedef typename property_traits<local_pmap>::value_type value_type;
1906
1907   typedef typename property_map<graph_type, vertex_global_t>::const_type
1908     vertex_global_map;
1909   typedef typename property_map<graph_type, edge_global_t>::const_type
1910     edge_global_map;
1911
1912   typedef typename mpl::if_<is_same<typename detail::property_kind_from_graph<base_graph_type, Tag>::type,
1913                                     vertex_property_tag>,
1914                             vertex_global_map, edge_global_map>::type
1915     global_map;
1916
1917 public:
1918   typedef ::boost::parallel::distributed_property_map<
1919             process_group_type, global_map, local_pmap> type;
1920
1921   typedef ::boost::parallel::distributed_property_map<
1922             process_group_type, global_map, local_const_pmap> const_type;
1923 };
1924
1925 template <BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS, typename Tag>
1926 typename property_map<BOOST_DISTRIB_CSR_GRAPH_TYPE, Tag>::type
1927 get(Tag tag, BOOST_DISTRIB_CSR_GRAPH_TYPE& g)
1928 {
1929   typedef BOOST_DISTRIB_CSR_GRAPH_TYPE Graph;
1930   typedef typename property_map<Graph, Tag>::type result_type;
1931   typedef typename property_traits<result_type>::value_type value_type;
1932   typedef typename property_reduce<Tag>::template apply<value_type>
1933     reduce;
1934
1935   typedef typename mpl::if_<is_same<typename detail::property_kind_from_graph<Graph, Tag>::type,
1936                                     vertex_property_tag>,
1937                             vertex_global_t, edge_global_t>::type
1938     global_map_t;
1939
1940   return result_type(g.process_group(), get(global_map_t(), g),
1941                      get(tag, g.base()), reduce());
1942 }
1943
1944 template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS, typename Tag>
1945 typename property_map<BOOST_DISTRIB_CSR_GRAPH_TYPE, Tag>::const_type
1946 get(Tag tag, const BOOST_DISTRIB_CSR_GRAPH_TYPE& g)
1947 {
1948   typedef BOOST_DISTRIB_CSR_GRAPH_TYPE Graph;
1949   typedef typename property_map<Graph, Tag>::const_type result_type;
1950   typedef typename property_traits<result_type>::value_type value_type;
1951   typedef typename property_reduce<Tag>::template apply<value_type>
1952     reduce;
1953
1954   typedef typename property_traits<result_type>::key_type descriptor;
1955   typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor;
1956   typedef typename mpl::if_<is_same<descriptor, vertex_descriptor>,
1957                             vertex_global_t, edge_global_t>::type
1958     global_map_t;
1959
1960   return result_type(g.process_group(), get(global_map_t(), g),
1961                      get(tag, g.base()), reduce());
1962 }
1963
1964 namespace mpi {
1965   template<typename Vertex, typename EdgeIndex>
1966   struct is_mpi_datatype<boost::detail::csr_edge_descriptor<Vertex, EdgeIndex> >
1967     : mpl::true_ { };
1968 }
1969
1970 namespace serialization {
1971   template<typename Vertex, typename EdgeIndex>
1972   struct is_bitwise_serializable<boost::detail::csr_edge_descriptor<Vertex, EdgeIndex> >
1973     : mpl::true_ { };
1974
1975   template<typename Vertex, typename EdgeIndex>
1976   struct implementation_level<boost::detail::csr_edge_descriptor<Vertex, EdgeIndex> >
1977    : mpl::int_<object_serializable> {} ;
1978
1979   template<typename Vertex, typename EdgeIndex>
1980   struct tracking_level<boost::detail::csr_edge_descriptor<Vertex, EdgeIndex> >
1981    : mpl::int_<track_never> {} ;
1982
1983 }
1984
1985 } // end namespace boost
1986
1987 #endif // BOOST_GRAPH_DISTRIBUTED_CSR_HPP