ceph/src/boost/libs/graph_parallel/include/boost/graph/distributed/compressed_sparse_row_graph.hpp

   1 // Copyright (C) 2006 The Trustees of Indiana University.
   2
   3 // Use, modification and distribution is subject to the Boost Software
   4 // License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
   5 // http://www.boost.org/LICENSE_1_0.txt)
   6
   7 //  Authors: Douglas Gregor
   8 //           Jeremiah Willcock
   9 //           Andrew Lumsdaine
  10
  11 // Distributed compressed sparse row graph type
  12
  13 #ifndef BOOST_GRAPH_DISTRIBUTED_CSR_HPP
  14 #define BOOST_GRAPH_DISTRIBUTED_CSR_HPP
  15
  16 #ifndef BOOST_GRAPH_USE_MPI
  17 #error "Parallel BGL files should not be included unless <boost/graph/use_mpi.hpp> has been included"
  18 #endif
  19
  20 #include <boost/assert.hpp>
  21 #include <boost/graph/compressed_sparse_row_graph.hpp>
  22 #include <boost/graph/distributed/selector.hpp>
  23 #include <boost/mpl/if.hpp>
  24 #include <boost/type_traits/is_same.hpp>
  25 #include <boost/graph/distributed/concepts.hpp>
  26 #include <boost/graph/parallel/properties.hpp>
  27 #include <boost/graph/parallel/distribution.hpp>
  28 #include <boost/property_map/parallel/local_property_map.hpp>
  29 #include <boost/property_map/parallel/distributed_property_map.hpp>
  30
  31 namespace boost {
  32
  33 // Distributed and sequential inplace ctors have the same signature so
  34 // we need a separate tag for distributed inplace ctors
  35 enum distributed_construct_inplace_from_sources_and_targets_t
  36   {distributed_construct_inplace_from_sources_and_targets};
  37
  38 // The number of bits we reserve for the processor ID.
  39 // DPG TBD: This is a hack. It will eventually be a run-time quantity.
  40 static const int processor_bits = 8;
  41
  42 // Tag class for a distributed CSR graph
  43 struct distributed_csr_tag
  44   : public virtual distributed_graph_tag,
  45     public virtual distributed_vertex_list_graph_tag,
  46     public virtual distributed_edge_list_graph_tag,
  47     public virtual incidence_graph_tag,
  48     public virtual adjacency_graph_tag {};
  49
  50 template<typename VertexProperty, typename EdgeProperty,
  51          typename GraphProperty, typename ProcessGroup, typename InVertex,
  52          typename InDistribution, typename InEdgeIndex>
  53 class compressed_sparse_row_graph<
  54          directedS, VertexProperty, EdgeProperty, GraphProperty,
  55          distributedS<ProcessGroup, InVertex, InDistribution>,
  56          InEdgeIndex>
  57 {
  58   typedef compressed_sparse_row_graph self_type;
  59
  60  private:
  61   /**
  62    *  Determine the type used to represent vertices in the graph. If
  63    *  the user has overridden the default, use the user's
  64    *  parameter. Otherwise, fall back to std::size_t.
  65    */
  66   typedef typename mpl::if_<is_same<InVertex, defaultS>,
  67                             std::size_t,
  68                             InVertex>::type Vertex;
  69
  70   /**
  71    *  Determine the type used to represent edges in the graph. If
  72    *  the user has overridden the default (which is to be the same as
  73    *  the distributed vertex selector type), use the user's
  74    *  parameter. Otherwise, fall back to the value of @c Vertex.
  75    */
  76   typedef typename mpl::if_<is_same<InEdgeIndex,
  77                                     distributedS<ProcessGroup, InVertex,
  78                                                  InDistribution> >,
  79                             Vertex,
  80                             InEdgeIndex>::type EdgeIndex;
  81
  82  public:
  83   /**
  84    * The type of the CSR graph that will be stored locally.
  85    */
  86   typedef compressed_sparse_row_graph<directedS, VertexProperty, EdgeProperty,
  87                                       GraphProperty, Vertex, EdgeIndex>
  88     base_type;
  89
  90   // -----------------------------------------------------------------
  91   // Graph concept requirements
  92   typedef Vertex vertex_descriptor;
  93   typedef typename graph_traits<base_type>::edge_descriptor edge_descriptor;
  94   typedef directed_tag directed_category;
  95   typedef allow_parallel_edge_tag edge_parallel_category;
  96   typedef distributed_csr_tag traversal_category;
  97   static vertex_descriptor null_vertex();
  98
  99   // -----------------------------------------------------------------
 100   // Distributed Vertex List Graph concept requirements
 101   typedef Vertex vertices_size_type;
 102   class vertex_iterator;
 103
 104   // -----------------------------------------------------------------
 105   // Distributed Edge List Graph concept requirements
 106   typedef EdgeIndex edges_size_type;
 107   class edge_iterator;
 108
 109   // -----------------------------------------------------------------
 110   // Incidence Graph concept requirements
 111   typedef typename graph_traits<base_type>::out_edge_iterator
 112     out_edge_iterator;
 113   typedef typename graph_traits<base_type>::degree_size_type
 114     degree_size_type;
 115
 116   // -----------------------------------------------------------------
 117   // Adjacency Graph concept requirements
 118   typedef typename graph_traits<base_type>::adjacency_iterator
 119     adjacency_iterator;
 120
 121   // Note: This graph type does not model Bidirectional Graph.
 122   // However, this typedef is required to satisfy graph_traits.
 123   typedef void in_edge_iterator;
 124
 125   // -----------------------------------------------------------------
 126   // Distributed Container concept requirements
 127   typedef ProcessGroup process_group_type;
 128   typedef boost::parallel::variant_distribution<process_group_type, Vertex>
 129     distribution_type;
 130
 131   // -----------------------------------------------------------------
 132   // Workarounds
 133   // NOTE: This graph type does not have old-style graph properties. It only
 134   // accepts bundles.
 135   typedef no_property vertex_property_type;
 136   typedef no_property edge_property_type;
 137   typedef no_property graph_property_type;
 138   typedef typename mpl::if_<is_void<VertexProperty>,
 139                             void****,
 140                             VertexProperty>::type vertex_bundled;
 141   typedef typename mpl::if_<is_void<EdgeProperty>,
 142                             void****,
 143                             EdgeProperty>::type edge_bundled;
 144   typedef typename mpl::if_<is_void<GraphProperty>,
 145                             void****,
 146                             GraphProperty>::type graph_bundled;
 147
 148   // -----------------------------------------------------------------
 149   // Useful types
 150   typedef typename ProcessGroup::process_id_type process_id_type;
 151
 152   // -----------------------------------------------------------------
 153   // Graph constructors
 154   compressed_sparse_row_graph(const ProcessGroup& pg = ProcessGroup())
 155     : m_process_group(pg), m_distribution(parallel::block(pg, 0)) {}
 156
 157   compressed_sparse_row_graph(const GraphProperty& prop,
 158                               const ProcessGroup& pg = ProcessGroup())
 159     : m_process_group(pg), m_distribution(parallel::block(pg, 0)) {}
 160
 161   compressed_sparse_row_graph(vertices_size_type numverts,
 162                               const ProcessGroup& pg = ProcessGroup())
 163     : m_process_group(pg), m_distribution(parallel::block(pg, 0)),
 164       m_base(numverts)
 165   {}
 166
 167   compressed_sparse_row_graph(vertices_size_type numverts,
 168                               const GraphProperty& prop,
 169                               const ProcessGroup& pg = ProcessGroup())
 170     : m_process_group(pg), m_distribution(parallel::block(pg, 0)),
 171       m_base(numverts)
 172   {}
 173
 174   template <typename Distribution>
 175   compressed_sparse_row_graph(vertices_size_type numverts,
 176                               const ProcessGroup& pg,
 177                               const Distribution& dist)
 178     : m_process_group(pg), m_distribution(dist), m_base(numverts) {}
 179
 180   template <typename Distribution>
 181   compressed_sparse_row_graph(vertices_size_type numverts,
 182                               const GraphProperty& prop,
 183                               const ProcessGroup& pg,
 184                               const Distribution& dist)
 185     : m_process_group(pg), m_distribution(dist), m_base(numverts) {}
 186
 187   template <typename InputIterator>
 188   compressed_sparse_row_graph(edges_are_unsorted_t,
 189                               InputIterator edge_begin, InputIterator edge_end,
 190                               vertices_size_type numverts,
 191                               const ProcessGroup& pg = ProcessGroup(),
 192                               const GraphProperty& prop = GraphProperty());
 193
 194   template <typename InputIterator, typename Distribution>
 195   compressed_sparse_row_graph(edges_are_unsorted_t,
 196                               InputIterator edge_begin, InputIterator edge_end,
 197                               vertices_size_type numverts,
 198                               const ProcessGroup& pg,
 199                               const Distribution& dist,
 200                               const GraphProperty& prop = GraphProperty());
 201
 202   template <typename InputIterator, typename EdgePropertyIterator>
 203   compressed_sparse_row_graph(edges_are_unsorted_t,
 204                               InputIterator edge_begin, InputIterator edge_end,
 205                               EdgePropertyIterator ep_iter,
 206                               vertices_size_type numverts,
 207                               const ProcessGroup& pg = ProcessGroup(),
 208                               const GraphProperty& prop = GraphProperty());
 209
 210   template <typename InputIterator, typename EdgePropertyIterator,
 211             typename Distribution>
 212   compressed_sparse_row_graph(edges_are_unsorted_t,
 213                               InputIterator edge_begin, InputIterator edge_end,
 214                               EdgePropertyIterator ep_iter,
 215                               vertices_size_type numverts,
 216                               const ProcessGroup& pg,
 217                               const Distribution& dist,
 218                               const GraphProperty& prop = GraphProperty());
 219
 220   template <typename InputIterator>
 221   compressed_sparse_row_graph(edges_are_sorted_t,
 222                               InputIterator edge_begin, InputIterator edge_end,
 223                               vertices_size_type numverts,
 224                               edges_size_type numedges = 0,
 225                               const ProcessGroup& pg = ProcessGroup(),
 226                               const GraphProperty& prop = GraphProperty());
 227
 228   template <typename InputIterator, typename Distribution>
 229   compressed_sparse_row_graph(edges_are_sorted_t,
 230                               InputIterator edge_begin, InputIterator edge_end,
 231                               vertices_size_type numverts,
 232                               const ProcessGroup& pg,
 233                               const Distribution& dist,
 234                               const GraphProperty& prop = GraphProperty());
 235
 236   template <typename InputIterator, typename EdgePropertyIterator>
 237   compressed_sparse_row_graph(edges_are_sorted_t,
 238                               InputIterator edge_begin, InputIterator edge_end,
 239                               EdgePropertyIterator ep_iter,
 240                               vertices_size_type numverts,
 241                               edges_size_type numedges = 0,
 242                               const ProcessGroup& pg = ProcessGroup(),
 243                               const GraphProperty& prop = GraphProperty());
 244
 245   template <typename InputIterator, typename EdgePropertyIterator,
 246             typename Distribution>
 247   compressed_sparse_row_graph(edges_are_sorted_t,
 248                               InputIterator edge_begin, InputIterator edge_end,
 249                               EdgePropertyIterator ep_iter,
 250                               vertices_size_type numverts,
 251                               const ProcessGroup& pg,
 252                               const Distribution& dist,
 253                               const GraphProperty& prop = GraphProperty());
 254
 255   template <typename MultiPassInputIterator>
 256   compressed_sparse_row_graph(edges_are_unsorted_multi_pass_t,
 257                               MultiPassInputIterator edge_begin,
 258                               MultiPassInputIterator edge_end,
 259                               vertices_size_type numverts,
 260                               const ProcessGroup& pg = ProcessGroup(),
 261                               const GraphProperty& prop = GraphProperty());
 262
 263   template <typename MultiPassInputIterator, typename Distribution>
 264   compressed_sparse_row_graph(edges_are_unsorted_multi_pass_t,
 265                               MultiPassInputIterator edge_begin,
 266                               MultiPassInputIterator edge_end,
 267                               vertices_size_type numverts,
 268                               const ProcessGroup& pg,
 269                               const Distribution& dist,
 270                               const GraphProperty& prop = GraphProperty());
 271
 272   template <typename MultiPassInputIterator, typename EdgePropertyIterator>
 273   compressed_sparse_row_graph(edges_are_unsorted_multi_pass_t,
 274                               MultiPassInputIterator edge_begin,
 275                               MultiPassInputIterator edge_end,
 276                               EdgePropertyIterator ep_iter,
 277                               vertices_size_type numverts,
 278                               const ProcessGroup& pg = ProcessGroup(),
 279                               const GraphProperty& prop = GraphProperty());
 280
 281   template <typename MultiPassInputIterator, typename EdgePropertyIterator,
 282             typename Distribution>
 283   compressed_sparse_row_graph(edges_are_unsorted_multi_pass_t,
 284                               MultiPassInputIterator edge_begin,
 285                               MultiPassInputIterator edge_end,
 286                               EdgePropertyIterator ep_iter,
 287                               vertices_size_type numverts,
 288                               const ProcessGroup& pg,
 289                               const Distribution& dist,
 290                               const GraphProperty& prop = GraphProperty());
 291
 292   template <typename Source>
 293   compressed_sparse_row_graph(distributed_construct_inplace_from_sources_and_targets_t,
 294                               std::vector<Source>& sources,
 295                               std::vector<vertex_descriptor>& targets,
 296                               vertices_size_type numverts,
 297                               const ProcessGroup& pg = ProcessGroup(),
 298                               const GraphProperty& prop = GraphProperty());
 299
 300   template <typename Distribution, typename Source>
 301   compressed_sparse_row_graph(distributed_construct_inplace_from_sources_and_targets_t,
 302                               std::vector<Source>& sources,
 303                               std::vector<vertex_descriptor>& targets,
 304                               vertices_size_type numverts,
 305                               const ProcessGroup& pg,
 306                               const Distribution& dist,
 307                               const GraphProperty& prop = GraphProperty());
 308
 309   template <typename Source>
 310   compressed_sparse_row_graph(distributed_construct_inplace_from_sources_and_targets_t,
 311                               std::vector<Source>& sources,
 312                               std::vector<vertex_descriptor>& targets,
 313                               std::vector<edge_bundled>& edge_props,
 314                               vertices_size_type numverts,
 315                               const ProcessGroup& pg = ProcessGroup(),
 316                               const GraphProperty& prop = GraphProperty());
 317
 318   template <typename Distribution, typename Source>
 319   compressed_sparse_row_graph(distributed_construct_inplace_from_sources_and_targets_t,
 320                               std::vector<Source>& sources,
 321                               std::vector<vertex_descriptor>& targets,
 322                               std::vector<edge_bundled>& edge_props,
 323                               vertices_size_type numverts,
 324                               const ProcessGroup& pg,
 325                               const Distribution& dist,
 326                               const GraphProperty& prop = GraphProperty());
 327
 328   template<typename InputIterator>
 329   compressed_sparse_row_graph(InputIterator edge_begin, InputIterator edge_end,
 330                               vertices_size_type numverts,
 331                               const ProcessGroup& pg = ProcessGroup(),
 332                               const GraphProperty& prop = GraphProperty());
 333
 334   template<typename InputIterator, typename EdgePropertyIterator>
 335   compressed_sparse_row_graph(InputIterator edge_begin, InputIterator edge_end,
 336                               EdgePropertyIterator ep_iter,
 337                               vertices_size_type numverts,
 338                               const ProcessGroup& pg = ProcessGroup(),
 339                               const GraphProperty& prop = GraphProperty());
 340
 341   template<typename InputIterator, typename Distribution>
 342   compressed_sparse_row_graph(InputIterator edge_begin, InputIterator edge_end,
 343                               vertices_size_type numverts,
 344                               const ProcessGroup& pg,
 345                               const Distribution& dist,
 346                               const GraphProperty& prop = GraphProperty());
 347
 348   template<typename InputIterator, typename EdgePropertyIterator,
 349            typename Distribution>
 350   compressed_sparse_row_graph(InputIterator edge_begin, InputIterator edge_end,
 351                               EdgePropertyIterator ep_iter,
 352                               vertices_size_type numverts,
 353                               const ProcessGroup& pg,
 354                               const Distribution& dist,
 355                               const GraphProperty& prop = GraphProperty());
 356
 357   base_type&       base()       { return m_base; }
 358   const base_type& base() const { return m_base; }
 359
 360   process_group_type process_group() const { return m_process_group.base(); }
 361
 362   distribution_type&       distribution()       { return m_distribution; }
 363   const distribution_type& distribution() const { return m_distribution; }
 364
 365   // Directly access a vertex or edge bundle
 366   vertex_bundled& operator[](vertex_descriptor v)
 367   {
 368     return get(vertex_bundle, *this, v);
 369   }
 370
 371   const vertex_bundled& operator[](vertex_descriptor v) const
 372   {
 373     return get(vertex_bundle, *this, v);
 374   }
 375
 376   edge_bundled& operator[](edge_descriptor e)
 377   {
 378     return get(edge_bundle, *this, e);
 379   }
 380
 381   const edge_bundled& operator[](edge_descriptor e) const
 382   {
 383     return get(edge_bundle, *this, e);
 384   }
 385
 386   // Create a vertex descriptor from a process ID and a local index.
 387   vertex_descriptor
 388   make_vertex_descriptor(process_id_type p, vertex_descriptor v) const
 389   {
 390     vertex_descriptor vertex_local_index_bits =
 391       sizeof(vertex_descriptor) * CHAR_BIT - processor_bits;
 392     return v | ((vertex_descriptor)p << vertex_local_index_bits);
 393   }
 394
 395   // Convert a local vertex descriptor into a global vertex descriptor
 396   vertex_descriptor local_to_global_vertex(vertex_descriptor v) const
 397   {
 398     return make_vertex_descriptor(process_id(m_process_group), v);
 399   }
 400
 401   // Structural modification
 402   vertex_descriptor add_vertex()
 403   {
 404     typename graph_traits<base_type>::vertex_descriptor v
 405       = boost::add_vertex(m_base);
 406
 407     return make_vertex_descriptor(process_id(m_process_group), v);
 408   }
 409
 410   vertex_descriptor add_vertex(const vertex_bundled& p)
 411   {
 412     typename graph_traits<base_type>::vertex_descriptor v
 413       = boost::add_vertex(m_base, p);
 414
 415     return make_vertex_descriptor(process_id(m_process_group), v);
 416   }
 417
 418   vertex_descriptor add_vertices(vertices_size_type count)
 419   {
 420     typename graph_traits<base_type>::vertex_descriptor v
 421       = boost::add_vertices(count, m_base);
 422
 423     return make_vertex_descriptor(process_id(m_process_group), v);
 424   }
 425
 426   template <typename InputIterator>
 427   void
 428   add_edges(InputIterator first, InputIterator last)
 429   { boost::add_edges_global(first, last, get(vertex_local, *this), m_base); }
 430
 431   template <typename InputIterator, typename EdgePropertyIterator>
 432   void
 433   add_edges(InputIterator first, InputIterator last,
 434             EdgePropertyIterator ep_iter,
 435             EdgePropertyIterator ep_iter_end)
 436   { boost::add_edges_global(first, last, ep_iter, ep_iter_end,
 437                             get(vertex_local, *this), m_base); }
 438
 439   template <typename InputIterator>
 440   void
 441   add_edges_sorted(InputIterator first, InputIterator last)
 442   { boost::add_edges_sorted_global(first, last,
 443                                    get(vertex_local, *this), m_base); }
 444
 445   template <typename InputIterator, typename EdgePropertyIterator>
 446   void
 447   add_edges_sorted(InputIterator first_sorted, InputIterator last_sorted,
 448                    EdgePropertyIterator ep_iter_sorted)
 449   { boost::add_edges_sorted_global(first_sorted, last_sorted, ep_iter_sorted,
 450                                    get(vertex_local, *this), m_base); }
 451
 452  protected:
 453   ProcessGroup m_process_group;
 454   distribution_type m_distribution;
 455   base_type m_base;
 456 };
 457
 458 /** @brief Helper macro containing the template parameters for the
 459  *   distributed CSR graph.
 460  *
 461  *  This macro contains all of the template parameters needed for the
 462  *  distributed compressed_sparse_row graph type. It is used to reduce
 463  *  the amount of typing required to declare free functions for this
 464  *  graph type.
 465  */
 466 #define BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS                          \
 467   typename VertexProperty, typename EdgeProperty,    \
 468   typename GraphProperty, typename ProcessGroup, typename InVertex,     \
 469   typename InDistribution, typename InEdgeIndex
 470
 471 /** @brief Helper macro containing the typical instantiation of the
 472  *   distributed CSR graph.
 473  *
 474  *  This macro contains an instantiation of the distributed CSR graph
 475  *  type using the typical template parameters names (e.g., those
 476  *  provided by the macro @c
 477  *  BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS). It is used to reduce
 478  *  the amount of typing required to declare free functions for this
 479  *  graph type.
 480  */
 481 #define BOOST_DISTRIB_CSR_GRAPH_TYPE                            \
 482   compressed_sparse_row_graph<                                  \
 483     directedS, VertexProperty, EdgeProperty, GraphProperty,      \
 484     distributedS<ProcessGroup, InVertex, InDistribution>,       \
 485     InEdgeIndex>
 486
 487 // -----------------------------------------------------------------
 488 // Graph concept operations
 489 template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS>
 490 inline typename BOOST_DISTRIB_CSR_GRAPH_TYPE::vertex_descriptor
 491 BOOST_DISTRIB_CSR_GRAPH_TYPE::null_vertex()
 492 {
 493   return graph_traits<base_type>::null_vertex();
 494 }
 495
 496 // -----------------------------------------------------------------
 497 // Incidence Graph concept operations
 498 template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS>
 499 inline typename BOOST_DISTRIB_CSR_GRAPH_TYPE::vertex_descriptor
 500 source(typename BOOST_DISTRIB_CSR_GRAPH_TYPE::edge_descriptor e,
 501        const BOOST_DISTRIB_CSR_GRAPH_TYPE&)
 502 { return e.src; }
 503
 504 template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS>
 505 inline typename BOOST_DISTRIB_CSR_GRAPH_TYPE::vertex_descriptor
 506 target(typename BOOST_DISTRIB_CSR_GRAPH_TYPE::edge_descriptor e,
 507        const BOOST_DISTRIB_CSR_GRAPH_TYPE& g)
 508 { return target(e, g.base()); }
 509
 510 template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS>
 511 inline std::pair<typename BOOST_DISTRIB_CSR_GRAPH_TYPE::out_edge_iterator,
 512                  typename BOOST_DISTRIB_CSR_GRAPH_TYPE::out_edge_iterator>
 513 out_edges(typename BOOST_DISTRIB_CSR_GRAPH_TYPE::vertex_descriptor u,
 514           const BOOST_DISTRIB_CSR_GRAPH_TYPE& g)
 515 {
 516   typedef typename BOOST_DISTRIB_CSR_GRAPH_TYPE::edges_size_type
 517     edges_size_type;
 518   typedef typename BOOST_DISTRIB_CSR_GRAPH_TYPE::edge_descriptor ed;
 519   typedef typename BOOST_DISTRIB_CSR_GRAPH_TYPE::out_edge_iterator it;
 520   edges_size_type u_local = get(vertex_local, g, u);
 521   edges_size_type u_row_start = g.base().m_forward.m_rowstart[u_local];
 522   edges_size_type next_row_start = g.base().m_forward.m_rowstart[u_local + 1];
 523   return std::make_pair(it(ed(u, u_row_start)),
 524                         it(ed(u, (std::max)(u_row_start, next_row_start))));
 525 }
 526
 527 template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS>
 528 inline typename BOOST_DISTRIB_CSR_GRAPH_TYPE::degree_size_type
 529 out_degree(typename BOOST_DISTRIB_CSR_GRAPH_TYPE::vertex_descriptor u,
 530            const BOOST_DISTRIB_CSR_GRAPH_TYPE& g)
 531 {
 532   return out_degree(get(vertex_local, g, u), g.base());
 533 }
 534
 535 // -----------------------------------------------------------------
 536 // DistributedGraph concept requirements
 537 template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS>
 538 void synchronize(const BOOST_DISTRIB_CSR_GRAPH_TYPE& g)
 539 {
 540   synchronize(g.process_group());
 541 }
 542
 543 template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS>
 544 ProcessGroup
 545 process_group(const BOOST_DISTRIB_CSR_GRAPH_TYPE& g)
 546 { return g.process_group(); }
 547
 548
 549 // -----------------------------------------------------------------
 550 // Adjacency Graph concept requirements
 551 template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS>
 552 inline std::pair<typename BOOST_DISTRIB_CSR_GRAPH_TYPE::adjacency_iterator,
 553                  typename BOOST_DISTRIB_CSR_GRAPH_TYPE::adjacency_iterator>
 554 adjacent_vertices(typename BOOST_DISTRIB_CSR_GRAPH_TYPE::vertex_descriptor u,
 555                   const BOOST_DISTRIB_CSR_GRAPH_TYPE& g)
 556 {
 557   return adjacent_vertices(get(vertex_local, g, u), g.base());
 558 }
 559
 560 // -----------------------------------------------------------------
 561 // Distributed Vertex List Graph concept operations
 562 template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS>
 563 class BOOST_DISTRIB_CSR_GRAPH_TYPE::vertex_iterator
 564   : public iterator_adaptor<vertex_iterator,
 565                             counting_iterator<Vertex>,
 566                             Vertex,
 567                             random_access_traversal_tag,
 568                             Vertex>
 569 {
 570   typedef iterator_adaptor<vertex_iterator,
 571                            counting_iterator<Vertex>,
 572                            Vertex,
 573                            random_access_traversal_tag,
 574                            Vertex> inherited;
 575  public:
 576   vertex_iterator() {}
 577
 578   explicit vertex_iterator(Vertex v, const self_type* graph)
 579     : inherited(counting_iterator<Vertex>(v)), graph(graph) { }
 580
 581   Vertex dereference() const
 582   {
 583     return graph->local_to_global_vertex(*(this->base_reference()));
 584   }
 585
 586   friend class iterator_core_access;
 587
 588  private:
 589   const self_type* graph;
 590 };
 591
 592 template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS>
 593 inline typename BOOST_DISTRIB_CSR_GRAPH_TYPE::degree_size_type
 594 num_vertices(const BOOST_DISTRIB_CSR_GRAPH_TYPE& g)
 595 {
 596   return num_vertices(g.base());
 597 }
 598
 599 template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS>
 600 inline std::pair<typename BOOST_DISTRIB_CSR_GRAPH_TYPE::vertex_iterator,
 601                  typename BOOST_DISTRIB_CSR_GRAPH_TYPE::vertex_iterator>
 602 vertices(const BOOST_DISTRIB_CSR_GRAPH_TYPE& g)
 603 {
 604   typedef typename BOOST_DISTRIB_CSR_GRAPH_TYPE::vertex_iterator
 605     vertex_iterator;
 606   return std::make_pair(vertex_iterator(0, &g),
 607                         vertex_iterator(num_vertices(g), &g));
 608 }
 609
 610 // -----------------------------------------------------------------
 611 // Distributed Edge List Graph concept operations
 612 template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS>
 613 class BOOST_DISTRIB_CSR_GRAPH_TYPE::edge_iterator
 614 {
 615  public:
 616   typedef std::forward_iterator_tag iterator_category;
 617   typedef edge_descriptor value_type;
 618
 619   typedef const edge_descriptor* pointer;
 620
 621   typedef edge_descriptor reference;
 622   typedef typename int_t<CHAR_BIT * sizeof(EdgeIndex)>::fast difference_type;
 623
 624   edge_iterator() : graph(0), current_edge(), end_of_this_vertex(0) {}
 625
 626   edge_iterator(const compressed_sparse_row_graph& graph,
 627                 edge_descriptor current_edge,
 628                 EdgeIndex end_of_this_vertex)
 629     : graph(&graph), local_src(current_edge.src), current_edge(current_edge),
 630       end_of_this_vertex(end_of_this_vertex)
 631   {
 632     // The edge that comes in has a local source vertex. Make it global.
 633     current_edge.src = graph.local_to_global_vertex(current_edge.src);
 634   }
 635
 636   // From InputIterator
 637   reference operator*() const { return current_edge; }
 638   pointer operator->() const { return &current_edge; }
 639
 640   bool operator==(const edge_iterator& o) const {
 641     return current_edge == o.current_edge;
 642   }
 643   bool operator!=(const edge_iterator& o) const {
 644     return current_edge != o.current_edge;
 645   }
 646
 647   edge_iterator& operator++()
 648   {
 649     ++current_edge.idx;
 650     while (current_edge.idx == end_of_this_vertex && local_src < num_vertices(*graph)-1) {
 651       ++local_src;
 652       current_edge.src = graph->local_to_global_vertex(local_src);
 653       end_of_this_vertex = graph->base().m_forward.m_rowstart[local_src + 1];
 654     }
 655     return *this;
 656   }
 657
 658   edge_iterator operator++(int) {
 659     edge_iterator temp = *this;
 660     ++*this;
 661     return temp;
 662   }
 663
 664  private:
 665   const compressed_sparse_row_graph* graph;
 666   EdgeIndex local_src;
 667   edge_descriptor current_edge;
 668   EdgeIndex end_of_this_vertex;
 669 };
 670
 671 template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS>
 672 inline typename BOOST_DISTRIB_CSR_GRAPH_TYPE::edges_size_type
 673 num_edges(const BOOST_DISTRIB_CSR_GRAPH_TYPE& g)
 674 {
 675   return g.base().m_forward.m_column.size();
 676 }
 677
 678 template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS>
 679 std::pair<typename BOOST_DISTRIB_CSR_GRAPH_TYPE::edge_iterator,
 680           typename BOOST_DISTRIB_CSR_GRAPH_TYPE::edge_iterator>
 681 edges(const BOOST_DISTRIB_CSR_GRAPH_TYPE& g)
 682 {
 683   typedef typename BOOST_DISTRIB_CSR_GRAPH_TYPE::vertex_descriptor Vertex;
 684   typedef typename BOOST_DISTRIB_CSR_GRAPH_TYPE::edge_iterator ei;
 685   typedef typename BOOST_DISTRIB_CSR_GRAPH_TYPE::edge_descriptor edgedesc;
 686   if (g.base().m_forward.m_rowstart.size() == 1 ||
 687       g.base().m_forward.m_column.empty()) {
 688     return std::make_pair(ei(), ei());
 689   } else {
 690     // Find the first vertex that has outgoing edges
 691     Vertex src = 0;
 692     while (g.base().m_forward.m_rowstart[src + 1] == 0) ++src;
 693     return std::make_pair(ei(g, edgedesc(src, 0), g.base().m_forward.m_rowstart[src + 1]),
 694                           ei(g, edgedesc(num_vertices(g), g.base().m_forward.m_column.size()), 0));
 695   }
 696 }
 697
 698 // -----------------------------------------------------------------
 699 // Graph constructors
 700
 701 // Returns true if a vertex belongs to a process according to a distribution
 702 template <typename OwnerMap, typename ProcessId>
 703 struct local_vertex {
 704
 705   local_vertex(OwnerMap owner, ProcessId id)
 706     : owner(owner), id(id) {}
 707
 708   template <typename Vertex>
 709   bool operator()(Vertex x)
 710   { return get(owner, x) == id; }
 711
 712   template <typename Vertex>
 713   bool operator()(Vertex x) const
 714   { return get(owner, x) == id; }
 715
 716 private:
 717   OwnerMap owner;
 718   ProcessId id;
 719 };
 720
 721 // Returns true if a vertex belongs to a process according to a distribution
 722 template <typename OwnerMap, typename ProcessId>
 723 struct local_edge {
 724
 725   local_edge(OwnerMap owner, ProcessId id)
 726     : owner(owner), id(id) {}
 727
 728   template <typename Vertex>
 729   bool operator()(std::pair<Vertex, Vertex>& x)
 730   { return get(owner, x.first) == id; }
 731
 732   template <typename Vertex>
 733   bool operator()(const std::pair<Vertex, Vertex>& x) const
 734   { return get(owner, x.first) == id; }
 735
 736 private:
 737   OwnerMap owner;
 738   ProcessId id;
 739 };
 740
 741 // Turns an index iterator into a vertex iterator
 742 template<typename IndexIterator, typename Graph>
 743 class index_to_vertex_iterator {
 744
 745 public:
 746   typedef std::input_iterator_tag iterator_category;
 747   typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
 748   typedef std::pair<Vertex, Vertex> value_type;
 749   typedef const value_type& reference;
 750   typedef const value_type* pointer;
 751   typedef void difference_type;
 752
 753   index_to_vertex_iterator(IndexIterator index,
 754                            const Graph& g)
 755     : index(index), g(g), current(to_edge(*index)) {}
 756
 757   reference operator*() { current = to_edge(*index); return current; }
 758   pointer operator->() { current = to_edge(*index); return &current; }
 759
 760   index_to_vertex_iterator& operator++()
 761   {
 762     ++index;
 763     return *this;
 764   }
 765
 766   index_to_vertex_iterator operator++(int)
 767   {
 768     index_to_vertex_iterator temp(*this);
 769     ++(*this);
 770     return temp;
 771   }
 772
 773   bool operator==(const index_to_vertex_iterator& other) const
 774   { return index == other.index; }
 775
 776   bool operator!=(const index_to_vertex_iterator& other) const
 777   { return !(*this == other); }
 778
 779 private:
 780   value_type to_edge(const typename std::iterator_traits<IndexIterator>::value_type& x)
 781   { return std::make_pair(vertex(x.first, g), vertex(x.second, g)); }
 782
 783   IndexIterator index;
 784   const Graph& g;
 785   value_type current;
 786 };
 787
 788 template <typename Distribution, typename Graph>
 789 struct index_to_vertex_func {
 790
 791   typedef typename boost::graph_traits<Graph>::vertex_descriptor vertex_descriptor;
 792   typedef typename boost::graph_traits<Graph>::vertices_size_type vertices_size_type;
 793   typedef std::pair<vertex_descriptor, vertex_descriptor> result_type;
 794   typedef std::pair<vertices_size_type, vertices_size_type> base_iterator_type;
 795
 796   index_to_vertex_func(const Distribution& dist, const Graph& g)
 797     : dist(dist), g(g) {}
 798
 799
 800   result_type operator()(const base_iterator_type& p) const
 801   {
 802     return std::make_pair(vertex(p.first, g), vertex(p.second, g));
 803   }
 804
 805 private:
 806   const Distribution& dist;
 807   const Graph& g;
 808 };
 809
 810 // NGE: This method only works with iterators that have a difference_type,
 811 // the index_to_vertex_iterator class above is retained for compatibility
 812 // with BGL generators which have no difference_type
 813 template <typename IndexIterator, typename Distribution, typename Graph>
 814 boost::transform_iterator<index_to_vertex_func<Distribution, Graph>, IndexIterator>
 815 make_index_to_vertex_iterator(IndexIterator it, const Distribution& dist,
 816                               const Graph& g) {
 817   return boost::make_transform_iterator(
 818     it, index_to_vertex_func<Distribution, Graph>(dist, g));
 819 }
 820
 821 // Forward declaration of csr_vertex_owner_map
 822 template<typename ProcessID, typename Key> class csr_vertex_owner_map;
 823
 824 template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS>
 825 template<typename InputIterator>
 826 BOOST_DISTRIB_CSR_GRAPH_TYPE::
 827 compressed_sparse_row_graph(edges_are_unsorted_t,
 828                             InputIterator edge_begin, InputIterator edge_end,
 829                             vertices_size_type numverts,
 830                             const ProcessGroup& pg,
 831                             const GraphProperty& prop)
 832   : m_process_group(pg),
 833     m_distribution(parallel::block(m_process_group, numverts)),
 834     m_base(edges_are_unsorted_global,
 835            index_to_vertex_iterator<InputIterator, BOOST_DISTRIB_CSR_GRAPH_TYPE>(edge_begin, *this),
 836            index_to_vertex_iterator<InputIterator, BOOST_DISTRIB_CSR_GRAPH_TYPE>(edge_end, *this),
 837            m_distribution.block_size(process_id(m_process_group), numverts),
 838            get(vertex_local, *this),
 839            local_vertex<csr_vertex_owner_map<process_id_type, vertex_descriptor>,
 840                         process_id_type> (get(vertex_owner, *this), process_id(pg)),
 841            prop)
 842 { }
 843
 844 template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS>
 845 template <typename InputIterator, typename Distribution>
 846 BOOST_DISTRIB_CSR_GRAPH_TYPE::
 847 compressed_sparse_row_graph(edges_are_unsorted_t,
 848                             InputIterator edge_begin, InputIterator edge_end,
 849                             vertices_size_type numverts,
 850                             const ProcessGroup& pg,
 851                             const Distribution& dist,
 852                             const GraphProperty& prop)
 853   : m_process_group(pg),
 854     m_distribution(dist),
 855     m_base(edges_are_unsorted_global,
 856            index_to_vertex_iterator<InputIterator, BOOST_DISTRIB_CSR_GRAPH_TYPE>(edge_begin, *this),
 857            index_to_vertex_iterator<InputIterator, BOOST_DISTRIB_CSR_GRAPH_TYPE>(edge_end, *this),
 858            m_distribution.block_size(process_id(m_process_group), numverts),
 859            get(vertex_local, *this),
 860            local_vertex<csr_vertex_owner_map<process_id_type, vertex_descriptor>,
 861                         process_id_type> (get(vertex_owner, *this), process_id(pg)),
 862            prop)
 863 { }
 864
 865 template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS>
 866 template<typename InputIterator, typename EdgePropertyIterator>
 867 BOOST_DISTRIB_CSR_GRAPH_TYPE::
 868 compressed_sparse_row_graph(edges_are_unsorted_t,
 869                             InputIterator edge_begin, InputIterator edge_end,
 870                             EdgePropertyIterator ep_iter,
 871                             vertices_size_type numverts,
 872                             const ProcessGroup& pg,
 873                             const GraphProperty& prop)
 874   : m_process_group(pg),
 875     m_distribution(parallel::block(m_process_group, numverts)),
 876     m_base(edges_are_unsorted_global,
 877            index_to_vertex_iterator<InputIterator, BOOST_DISTRIB_CSR_GRAPH_TYPE>(edge_begin, *this),
 878            index_to_vertex_iterator<InputIterator, BOOST_DISTRIB_CSR_GRAPH_TYPE>(edge_end, *this),
 879            ep_iter,
 880            m_distribution.block_size(process_id(m_process_group), numverts),
 881            get(vertex_local, *this),
 882            local_vertex<csr_vertex_owner_map<process_id_type, vertex_descriptor>,
 883                         process_id_type> (get(vertex_owner, *this), process_id(pg)),
 884            prop)
 885 { }
 886
 887 template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS>
 888 template <typename InputIterator, typename EdgePropertyIterator,
 889           typename Distribution>
 890 BOOST_DISTRIB_CSR_GRAPH_TYPE::
 891 compressed_sparse_row_graph(edges_are_unsorted_t,
 892                             InputIterator edge_begin, InputIterator edge_end,
 893                             EdgePropertyIterator ep_iter,
 894                             vertices_size_type numverts,
 895                             const ProcessGroup& pg,
 896                             const Distribution& dist,
 897                             const GraphProperty& prop)
 898   : m_process_group(pg),
 899     m_distribution(dist),
 900     m_base(edges_are_unsorted_global,
 901            index_to_vertex_iterator<InputIterator, BOOST_DISTRIB_CSR_GRAPH_TYPE>(edge_begin, *this),
 902            index_to_vertex_iterator<InputIterator, BOOST_DISTRIB_CSR_GRAPH_TYPE>(edge_end, *this),
 903            ep_iter,
 904            m_distribution.block_size(process_id(m_process_group), numverts),
 905            get(vertex_local, *this),
 906            local_vertex<csr_vertex_owner_map<process_id_type, vertex_descriptor>,
 907                         process_id_type> (get(vertex_owner, *this), process_id(pg)),
 908            prop)
 909 { }
 910
 911 template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS>
 912 template<typename InputIterator>
 913 BOOST_DISTRIB_CSR_GRAPH_TYPE::
 914 compressed_sparse_row_graph(edges_are_sorted_t,
 915                             InputIterator edge_begin, InputIterator edge_end,
 916                             vertices_size_type numverts,
 917                             edges_size_type numedges, // This is not used as there is no appropriate BGL ctor
 918                             const ProcessGroup& pg,
 919                             const GraphProperty& prop)
 920   : m_process_group(pg),
 921     m_distribution(parallel::block(m_process_group, numverts)),
 922     m_base(edges_are_sorted_global,
 923            index_to_vertex_iterator<InputIterator, BOOST_DISTRIB_CSR_GRAPH_TYPE>(edge_begin, *this),
 924            index_to_vertex_iterator<InputIterator, BOOST_DISTRIB_CSR_GRAPH_TYPE>(edge_end, *this),
 925            get(vertex_local, *this),
 926            local_vertex<csr_vertex_owner_map<process_id_type, vertex_descriptor>,
 927                         process_id_type> (get(vertex_owner, *this), process_id(pg)),
 928            m_distribution.block_size(process_id(m_process_group), numverts),
 929            prop)
 930 { }
 931
 932 template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS>
 933 template <typename InputIterator, typename Distribution>
 934 BOOST_DISTRIB_CSR_GRAPH_TYPE::
 935 compressed_sparse_row_graph(edges_are_sorted_t,
 936                             InputIterator edge_begin, InputIterator edge_end,
 937                             vertices_size_type numverts,
 938                             const ProcessGroup& pg,
 939                             const Distribution& dist,
 940                             const GraphProperty& prop)
 941   : m_process_group(pg),
 942     m_distribution(dist),
 943     m_base(edges_are_sorted_global,
 944            index_to_vertex_iterator<InputIterator, BOOST_DISTRIB_CSR_GRAPH_TYPE>(edge_begin, *this),
 945            index_to_vertex_iterator<InputIterator, BOOST_DISTRIB_CSR_GRAPH_TYPE>(edge_end, *this),
 946            get(vertex_local, *this),
 947            local_vertex<csr_vertex_owner_map<process_id_type, vertex_descriptor>,
 948                         process_id_type> (get(vertex_owner, *this), process_id(pg)),
 949            m_distribution.block_size(process_id(m_process_group), numverts),
 950            prop)
 951 { }
 952
 953 template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS>
 954 template<typename InputIterator, typename EdgePropertyIterator>
 955 BOOST_DISTRIB_CSR_GRAPH_TYPE::
 956 compressed_sparse_row_graph(edges_are_sorted_t,
 957                             InputIterator edge_begin, InputIterator edge_end,
 958                             EdgePropertyIterator ep_iter,
 959                             vertices_size_type numverts,
 960                             edges_size_type numedges, // This is not used as there is no appropriate BGL ctor
 961                             const ProcessGroup& pg,
 962                             const GraphProperty& prop)
 963   : m_process_group(pg),
 964     m_distribution(parallel::block(m_process_group, numverts)),
 965     m_base(edges_are_sorted_global,
 966            index_to_vertex_iterator<InputIterator, BOOST_DISTRIB_CSR_GRAPH_TYPE>(edge_begin, *this),
 967            index_to_vertex_iterator<InputIterator, BOOST_DISTRIB_CSR_GRAPH_TYPE>(edge_end, *this),
 968            ep_iter,
 969            get(vertex_local, *this),
 970            local_vertex<csr_vertex_owner_map<process_id_type, vertex_descriptor>,
 971                         process_id_type> (get(vertex_owner, *this), process_id(pg)),
 972            m_distribution.block_size(process_id(m_process_group), numverts),
 973            prop)
 974 { }
 975
 976 template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS>
 977 template<typename InputIterator, typename EdgePropertyIterator,
 978          typename Distribution>
 979 BOOST_DISTRIB_CSR_GRAPH_TYPE::
 980 compressed_sparse_row_graph(edges_are_sorted_t,
 981                             InputIterator edge_begin, InputIterator edge_end,
 982                             EdgePropertyIterator ep_iter,
 983                             vertices_size_type numverts,
 984                             const ProcessGroup& pg,
 985                             const Distribution& dist,
 986                             const GraphProperty& prop)
 987   : m_process_group(pg),
 988     m_distribution(dist),
 989     m_base(edges_are_sorted_global,
 990            index_to_vertex_iterator<InputIterator, BOOST_DISTRIB_CSR_GRAPH_TYPE>(edge_begin, *this),
 991            index_to_vertex_iterator<InputIterator, BOOST_DISTRIB_CSR_GRAPH_TYPE>(edge_end, *this),
 992            ep_iter,
 993            get(vertex_local, *this),
 994            local_vertex<csr_vertex_owner_map<process_id_type, vertex_descriptor>,
 995                         process_id_type> (get(vertex_owner, *this), process_id(pg)),
 996            m_distribution.block_size(process_id(m_process_group), numverts),
 997            prop)
 998 { }
 999
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