Chris@16: // Copyright (C) 2006 The Trustees of Indiana University.
Chris@16: 
Chris@16: // Use, modification and distribution is subject to the Boost Software
Chris@16: // License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
Chris@16: // http://www.boost.org/LICENSE_1_0.txt)
Chris@16: 
Chris@16: //  Authors: Douglas Gregor
Chris@16: //           Jeremiah Willcock
Chris@16: //           Andrew Lumsdaine
Chris@16: 
Chris@16: // Distributed compressed sparse row graph type
Chris@16: 
Chris@16: #ifndef BOOST_GRAPH_DISTRIBUTED_CSR_HPP
Chris@16: #define BOOST_GRAPH_DISTRIBUTED_CSR_HPP
Chris@16: 
Chris@16: #ifndef BOOST_GRAPH_USE_MPI
Chris@16: #error "Parallel BGL files should not be included unless <boost/graph/use_mpi.hpp> has been included"
Chris@16: #endif
Chris@16: 
Chris@16: #include <boost/assert.hpp>
Chris@16: #include <boost/graph/compressed_sparse_row_graph.hpp>
Chris@16: #include <boost/graph/distributed/selector.hpp>
Chris@16: #include <boost/mpl/if.hpp>
Chris@16: #include <boost/type_traits/is_same.hpp>
Chris@16: #include <boost/graph/distributed/concepts.hpp>
Chris@16: #include <boost/graph/parallel/properties.hpp>
Chris@16: #include <boost/graph/parallel/distribution.hpp>
Chris@16: #include <boost/property_map/parallel/local_property_map.hpp>
Chris@16: #include <boost/property_map/parallel/distributed_property_map.hpp>
Chris@16: 
Chris@16: namespace boost {
Chris@16: 
Chris@16: // Distributed and sequential inplace ctors have the same signature so
Chris@16: // we need a separate tag for distributed inplace ctors
Chris@16: enum distributed_construct_inplace_from_sources_and_targets_t 
Chris@16:   {distributed_construct_inplace_from_sources_and_targets};
Chris@16: 
Chris@16: // The number of bits we reserve for the processor ID. 
Chris@16: // DPG TBD: This is a hack. It will eventually be a run-time quantity.
Chris@16: static const int processor_bits = 8;
Chris@16: 
Chris@16: // Tag class for a distributed CSR graph
Chris@16: struct distributed_csr_tag
Chris@16:   : public virtual distributed_graph_tag,
Chris@16:     public virtual distributed_vertex_list_graph_tag,
Chris@16:     public virtual distributed_edge_list_graph_tag,
Chris@16:     public virtual incidence_graph_tag,
Chris@16:     public virtual adjacency_graph_tag {};
Chris@16: 
Chris@16: template<typename VertexProperty, typename EdgeProperty,
Chris@16:          typename GraphProperty, typename ProcessGroup, typename InVertex,
Chris@16:          typename InDistribution, typename InEdgeIndex>
Chris@16: class compressed_sparse_row_graph<
Chris@16:          directedS, VertexProperty, EdgeProperty, GraphProperty,
Chris@16:          distributedS<ProcessGroup, InVertex, InDistribution>,
Chris@16:          InEdgeIndex>
Chris@16: {
Chris@16:   typedef compressed_sparse_row_graph self_type;
Chris@16: 
Chris@16:  private:
Chris@16:   /**
Chris@16:    *  Determine the type used to represent vertices in the graph. If
Chris@16:    *  the user has overridden the default, use the user's
Chris@16:    *  parameter. Otherwise, fall back to std::size_t.
Chris@16:    */
Chris@16:   typedef typename mpl::if_<is_same<InVertex, defaultS>,
Chris@16:                             std::size_t,
Chris@16:                             InVertex>::type Vertex;
Chris@16: 
Chris@16:   /**
Chris@16:    *  Determine the type used to represent edges in the graph. If
Chris@16:    *  the user has overridden the default (which is to be the same as
Chris@16:    *  the distributed vertex selector type), use the user's
Chris@16:    *  parameter. Otherwise, fall back to the value of @c Vertex.
Chris@16:    */
Chris@16:   typedef typename mpl::if_<is_same<InEdgeIndex,
Chris@16:                                     distributedS<ProcessGroup, InVertex,
Chris@16:                                                  InDistribution> >,
Chris@16:                             Vertex,
Chris@16:                             InEdgeIndex>::type EdgeIndex;
Chris@16: 
Chris@16:  public:
Chris@16:   /**
Chris@16:    * The type of the CSR graph that will be stored locally.
Chris@16:    */
Chris@16:   typedef compressed_sparse_row_graph<directedS, VertexProperty, EdgeProperty,
Chris@16:                                       GraphProperty, Vertex, EdgeIndex>
Chris@16:     base_type;
Chris@16: 
Chris@16:   // -----------------------------------------------------------------
Chris@16:   // Graph concept requirements
Chris@16:   typedef Vertex vertex_descriptor;
Chris@16:   typedef typename graph_traits<base_type>::edge_descriptor edge_descriptor;
Chris@16:   typedef directed_tag directed_category;
Chris@16:   typedef allow_parallel_edge_tag edge_parallel_category;
Chris@16:   typedef distributed_csr_tag traversal_category;
Chris@16:   static vertex_descriptor null_vertex();
Chris@16: 
Chris@16:   // -----------------------------------------------------------------
Chris@16:   // Distributed Vertex List Graph concept requirements
Chris@16:   typedef Vertex vertices_size_type;
Chris@16:   class vertex_iterator;
Chris@16: 
Chris@16:   // -----------------------------------------------------------------
Chris@16:   // Distributed Edge List Graph concept requirements
Chris@16:   typedef EdgeIndex edges_size_type;
Chris@16:   class edge_iterator;
Chris@16: 
Chris@16:   // -----------------------------------------------------------------
Chris@16:   // Incidence Graph concept requirements
Chris@16:   typedef typename graph_traits<base_type>::out_edge_iterator
Chris@16:     out_edge_iterator;
Chris@16:   typedef typename graph_traits<base_type>::degree_size_type
Chris@16:     degree_size_type;
Chris@16: 
Chris@16:   // -----------------------------------------------------------------
Chris@16:   // Adjacency Graph concept requirements
Chris@16:   typedef typename graph_traits<base_type>::adjacency_iterator
Chris@16:     adjacency_iterator;
Chris@16: 
Chris@16:   // Note: This graph type does not model Bidirectional Graph.
Chris@16:   // However, this typedef is required to satisfy graph_traits.
Chris@16:   typedef void in_edge_iterator;
Chris@16: 
Chris@16:   // -----------------------------------------------------------------
Chris@16:   // Distributed Container concept requirements
Chris@16:   typedef ProcessGroup process_group_type;
Chris@16:   typedef boost::parallel::variant_distribution<process_group_type, Vertex>
Chris@16:     distribution_type;
Chris@16: 
Chris@16:   // -----------------------------------------------------------------
Chris@16:   // Workarounds
Chris@16:   // NOTE: This graph type does not have old-style graph properties. It only
Chris@16:   // accepts bundles.
Chris@16:   typedef no_property vertex_property_type;
Chris@16:   typedef no_property edge_property_type;
Chris@16:   typedef no_property graph_property_type;
Chris@16:   typedef typename mpl::if_<is_void<VertexProperty>,
Chris@16:                             void****,
Chris@16:                             VertexProperty>::type vertex_bundled;
Chris@16:   typedef typename mpl::if_<is_void<EdgeProperty>,
Chris@16:                             void****,
Chris@16:                             EdgeProperty>::type edge_bundled;
Chris@16:   typedef typename mpl::if_<is_void<GraphProperty>,
Chris@16:                             void****,
Chris@16:                             GraphProperty>::type graph_bundled;
Chris@16: 
Chris@16:   // -----------------------------------------------------------------
Chris@16:   // Useful types
Chris@16:   typedef typename ProcessGroup::process_id_type process_id_type;
Chris@16: 
Chris@16:   // -----------------------------------------------------------------
Chris@16:   // Graph constructors
Chris@16:   compressed_sparse_row_graph(const ProcessGroup& pg = ProcessGroup())
Chris@16:     : m_process_group(pg), m_distribution(parallel::block(pg, 0)) {}
Chris@16: 
Chris@16:   compressed_sparse_row_graph(const GraphProperty& prop,
Chris@16:                               const ProcessGroup& pg = ProcessGroup())
Chris@16:     : m_process_group(pg), m_distribution(parallel::block(pg, 0)) {}
Chris@16: 
Chris@16:   compressed_sparse_row_graph(vertices_size_type numverts,
Chris@16:                               const ProcessGroup& pg = ProcessGroup())
Chris@16:     : m_process_group(pg), m_distribution(parallel::block(pg, 0)),
Chris@16:       m_base(numverts) 
Chris@16:   {}
Chris@16: 
Chris@16:   compressed_sparse_row_graph(vertices_size_type numverts,
Chris@16:                               const GraphProperty& prop,
Chris@16:                               const ProcessGroup& pg = ProcessGroup())
Chris@16:     : m_process_group(pg), m_distribution(parallel::block(pg, 0)),
Chris@16:       m_base(numverts) 
Chris@16:   {}
Chris@16: 
Chris@16:   template <typename Distribution>
Chris@16:   compressed_sparse_row_graph(vertices_size_type numverts,
Chris@16:                               const ProcessGroup& pg,
Chris@16:                               const Distribution& dist)
Chris@16:     : m_process_group(pg), m_distribution(dist), m_base(numverts) {}
Chris@16: 
Chris@16:   template <typename Distribution>
Chris@16:   compressed_sparse_row_graph(vertices_size_type numverts,
Chris@16:                               const GraphProperty& prop,
Chris@16:                               const ProcessGroup& pg,
Chris@16:                               const Distribution& dist)
Chris@16:     : m_process_group(pg), m_distribution(dist), m_base(numverts) {}
Chris@16: 
Chris@16:   template <typename InputIterator>
Chris@16:   compressed_sparse_row_graph(edges_are_unsorted_t,
Chris@16:                               InputIterator edge_begin, InputIterator edge_end,
Chris@16:                               vertices_size_type numverts,
Chris@16:                               const ProcessGroup& pg = ProcessGroup(),
Chris@16:                               const GraphProperty& prop = GraphProperty());
Chris@16: 
Chris@16:   template <typename InputIterator, typename Distribution>
Chris@16:   compressed_sparse_row_graph(edges_are_unsorted_t,
Chris@16:                               InputIterator edge_begin, InputIterator edge_end,
Chris@16:                               vertices_size_type numverts,
Chris@16:                               const ProcessGroup& pg,
Chris@16:                               const Distribution& dist,
Chris@16:                               const GraphProperty& prop = GraphProperty());
Chris@16: 
Chris@16:   template <typename InputIterator, typename EdgePropertyIterator>
Chris@16:   compressed_sparse_row_graph(edges_are_unsorted_t,
Chris@16:                               InputIterator edge_begin, InputIterator edge_end,
Chris@16:                               EdgePropertyIterator ep_iter,
Chris@16:                               vertices_size_type numverts,
Chris@16:                               const ProcessGroup& pg = ProcessGroup(),
Chris@16:                               const GraphProperty& prop = GraphProperty());
Chris@16: 
Chris@16:   template <typename InputIterator, typename EdgePropertyIterator,
Chris@16:             typename Distribution>
Chris@16:   compressed_sparse_row_graph(edges_are_unsorted_t,
Chris@16:                               InputIterator edge_begin, InputIterator edge_end,
Chris@16:                               EdgePropertyIterator ep_iter,
Chris@16:                               vertices_size_type numverts,
Chris@16:                               const ProcessGroup& pg,
Chris@16:                               const Distribution& dist,
Chris@16:                               const GraphProperty& prop = GraphProperty());
Chris@16: 
Chris@16:   template <typename InputIterator>
Chris@16:   compressed_sparse_row_graph(edges_are_sorted_t,
Chris@16:                               InputIterator edge_begin, InputIterator edge_end,
Chris@16:                               vertices_size_type numverts,
Chris@16:                               edges_size_type numedges = 0,
Chris@16:                               const ProcessGroup& pg = ProcessGroup(),
Chris@16:                               const GraphProperty& prop = GraphProperty());
Chris@16: 
Chris@16:   template <typename InputIterator, typename Distribution>
Chris@16:   compressed_sparse_row_graph(edges_are_sorted_t,
Chris@16:                               InputIterator edge_begin, InputIterator edge_end,
Chris@16:                               vertices_size_type numverts,
Chris@16:                               const ProcessGroup& pg,
Chris@16:                               const Distribution& dist,
Chris@16:                               const GraphProperty& prop = GraphProperty());
Chris@16: 
Chris@16:   template <typename InputIterator, typename EdgePropertyIterator>
Chris@16:   compressed_sparse_row_graph(edges_are_sorted_t,
Chris@16:                               InputIterator edge_begin, InputIterator edge_end,
Chris@16:                               EdgePropertyIterator ep_iter,
Chris@16:                               vertices_size_type numverts,
Chris@16:                               edges_size_type numedges = 0,
Chris@16:                               const ProcessGroup& pg = ProcessGroup(),
Chris@16:                               const GraphProperty& prop = GraphProperty());
Chris@16: 
Chris@16:   template <typename InputIterator, typename EdgePropertyIterator,
Chris@16:             typename Distribution>
Chris@16:   compressed_sparse_row_graph(edges_are_sorted_t,
Chris@16:                               InputIterator edge_begin, InputIterator edge_end,
Chris@16:                               EdgePropertyIterator ep_iter,
Chris@16:                               vertices_size_type numverts,
Chris@16:                               const ProcessGroup& pg,
Chris@16:                               const Distribution& dist,
Chris@16:                               const GraphProperty& prop = GraphProperty());
Chris@16: 
Chris@16:   template <typename MultiPassInputIterator>
Chris@16:   compressed_sparse_row_graph(edges_are_unsorted_multi_pass_t,
Chris@16:                               MultiPassInputIterator edge_begin, 
Chris@16:                               MultiPassInputIterator edge_end,
Chris@16:                               vertices_size_type numverts,
Chris@16:                               const ProcessGroup& pg = ProcessGroup(),
Chris@16:                               const GraphProperty& prop = GraphProperty());
Chris@16: 
Chris@16:   template <typename MultiPassInputIterator, typename Distribution>
Chris@16:   compressed_sparse_row_graph(edges_are_unsorted_multi_pass_t,
Chris@16:                               MultiPassInputIterator edge_begin, 
Chris@16:                               MultiPassInputIterator edge_end,
Chris@16:                               vertices_size_type numverts,
Chris@16:                               const ProcessGroup& pg,
Chris@16:                               const Distribution& dist,
Chris@16:                               const GraphProperty& prop = GraphProperty());
Chris@16: 
Chris@16:   template <typename MultiPassInputIterator, typename EdgePropertyIterator>
Chris@16:   compressed_sparse_row_graph(edges_are_unsorted_multi_pass_t,
Chris@16:                               MultiPassInputIterator edge_begin, 
Chris@16:                               MultiPassInputIterator edge_end,
Chris@16:                               EdgePropertyIterator ep_iter,
Chris@16:                               vertices_size_type numverts,
Chris@16:                               const ProcessGroup& pg = ProcessGroup(),
Chris@16:                               const GraphProperty& prop = GraphProperty());
Chris@16: 
Chris@16:   template <typename MultiPassInputIterator, typename EdgePropertyIterator,
Chris@16:             typename Distribution>
Chris@16:   compressed_sparse_row_graph(edges_are_unsorted_multi_pass_t,
Chris@16:                               MultiPassInputIterator edge_begin, 
Chris@16:                               MultiPassInputIterator edge_end,
Chris@16:                               EdgePropertyIterator ep_iter,
Chris@16:                               vertices_size_type numverts,
Chris@16:                               const ProcessGroup& pg,
Chris@16:                               const Distribution& dist,
Chris@16:                               const GraphProperty& prop = GraphProperty());
Chris@16: 
Chris@16:   template <typename Source>
Chris@16:   compressed_sparse_row_graph(distributed_construct_inplace_from_sources_and_targets_t,
Chris@16:                               std::vector<Source>& sources,
Chris@16:                               std::vector<vertex_descriptor>& targets,
Chris@16:                               vertices_size_type numverts,
Chris@16:                               const ProcessGroup& pg = ProcessGroup(),
Chris@16:                               const GraphProperty& prop = GraphProperty());
Chris@16: 
Chris@16:   template <typename Distribution, typename Source> 
Chris@16:   compressed_sparse_row_graph(distributed_construct_inplace_from_sources_and_targets_t,
Chris@16:                               std::vector<Source>& sources,
Chris@16:                               std::vector<vertex_descriptor>& targets,
Chris@16:                               vertices_size_type numverts,
Chris@16:                               const ProcessGroup& pg,
Chris@16:                               const Distribution& dist,
Chris@16:                               const GraphProperty& prop = GraphProperty());
Chris@16: 
Chris@16:   template <typename Source>
Chris@16:   compressed_sparse_row_graph(distributed_construct_inplace_from_sources_and_targets_t,
Chris@16:                               std::vector<Source>& sources,
Chris@16:                               std::vector<vertex_descriptor>& targets,
Chris@16:                               std::vector<edge_bundled>& edge_props,
Chris@16:                               vertices_size_type numverts,
Chris@16:                               const ProcessGroup& pg = ProcessGroup(),
Chris@16:                               const GraphProperty& prop = GraphProperty());
Chris@16: 
Chris@16:   template <typename Distribution, typename Source>
Chris@16:   compressed_sparse_row_graph(distributed_construct_inplace_from_sources_and_targets_t,
Chris@16:                               std::vector<Source>& sources,
Chris@16:                               std::vector<vertex_descriptor>& targets,
Chris@16:                               std::vector<edge_bundled>& edge_props,
Chris@16:                               vertices_size_type numverts,
Chris@16:                               const ProcessGroup& pg,
Chris@16:                               const Distribution& dist,
Chris@16:                               const GraphProperty& prop = GraphProperty());
Chris@16: 
Chris@16:   template<typename InputIterator>
Chris@16:   compressed_sparse_row_graph(InputIterator edge_begin, InputIterator edge_end,
Chris@16:                               vertices_size_type numverts,
Chris@16:                               const ProcessGroup& pg = ProcessGroup(),
Chris@16:                               const GraphProperty& prop = GraphProperty());
Chris@16: 
Chris@16:   template<typename InputIterator, typename EdgePropertyIterator>
Chris@16:   compressed_sparse_row_graph(InputIterator edge_begin, InputIterator edge_end,
Chris@16:                               EdgePropertyIterator ep_iter,
Chris@16:                               vertices_size_type numverts,
Chris@16:                               const ProcessGroup& pg = ProcessGroup(),
Chris@16:                               const GraphProperty& prop = GraphProperty());
Chris@16: 
Chris@16:   template<typename InputIterator, typename Distribution>
Chris@16:   compressed_sparse_row_graph(InputIterator edge_begin, InputIterator edge_end,
Chris@16:                               vertices_size_type numverts,
Chris@16:                               const ProcessGroup& pg,
Chris@16:                               const Distribution& dist,
Chris@16:                               const GraphProperty& prop = GraphProperty());
Chris@16: 
Chris@16:   template<typename InputIterator, typename EdgePropertyIterator, 
Chris@16:            typename Distribution>
Chris@16:   compressed_sparse_row_graph(InputIterator edge_begin, InputIterator edge_end,
Chris@16:                               EdgePropertyIterator ep_iter,
Chris@16:                               vertices_size_type numverts,
Chris@16:                               const ProcessGroup& pg,
Chris@16:                               const Distribution& dist,
Chris@16:                               const GraphProperty& prop = GraphProperty());
Chris@16: 
Chris@16:   base_type&       base()       { return m_base; }
Chris@16:   const base_type& base() const { return m_base; }
Chris@16: 
Chris@16:   process_group_type process_group() const { return m_process_group.base(); }
Chris@16: 
Chris@16:   distribution_type&       distribution()       { return m_distribution; }
Chris@16:   const distribution_type& distribution() const { return m_distribution; }
Chris@16: 
Chris@16:   // Directly access a vertex or edge bundle
Chris@16:   vertex_bundled& operator[](vertex_descriptor v)
Chris@16:   {
Chris@16:     return get(vertex_bundle, *this, v);
Chris@16:   }
Chris@16: 
Chris@16:   const vertex_bundled& operator[](vertex_descriptor v) const
Chris@16:   {
Chris@16:     return get(vertex_bundle, *this, v);
Chris@16:   }
Chris@16: 
Chris@16:   edge_bundled& operator[](edge_descriptor e)
Chris@16:   {
Chris@16:     return get(edge_bundle, *this, e);
Chris@16:   }
Chris@16: 
Chris@16:   const edge_bundled& operator[](edge_descriptor e) const
Chris@16:   {
Chris@16:     return get(edge_bundle, *this, e);
Chris@16:   }
Chris@16: 
Chris@16:   // Create a vertex descriptor from a process ID and a local index.
Chris@16:   vertex_descriptor 
Chris@16:   make_vertex_descriptor(process_id_type p, vertex_descriptor v) const
Chris@16:   {
Chris@16:     vertex_descriptor vertex_local_index_bits = 
Chris@16:       sizeof(vertex_descriptor) * CHAR_BIT - processor_bits;
Chris@16:     return v | ((vertex_descriptor)p << vertex_local_index_bits);
Chris@16:   }
Chris@16: 
Chris@16:   // Convert a local vertex descriptor into a global vertex descriptor
Chris@16:   vertex_descriptor local_to_global_vertex(vertex_descriptor v) const
Chris@16:   {
Chris@16:     return make_vertex_descriptor(process_id(m_process_group), v);
Chris@16:   }
Chris@16: 
Chris@16:   // Structural modification
Chris@16:   vertex_descriptor add_vertex()
Chris@16:   {
Chris@16:     typename graph_traits<base_type>::vertex_descriptor v 
Chris@16:       = boost::add_vertex(m_base);
Chris@16: 
Chris@16:     return make_vertex_descriptor(process_id(m_process_group), v);
Chris@16:   }
Chris@16: 
Chris@16:   vertex_descriptor add_vertex(const vertex_bundled& p)
Chris@16:   {
Chris@16:     typename graph_traits<base_type>::vertex_descriptor v 
Chris@16:       = boost::add_vertex(m_base, p);
Chris@16: 
Chris@16:     return make_vertex_descriptor(process_id(m_process_group), v);
Chris@16:   }
Chris@16: 
Chris@16:   vertex_descriptor add_vertices(vertices_size_type count)
Chris@16:   {
Chris@16:     typename graph_traits<base_type>::vertex_descriptor v 
Chris@16:       = boost::add_vertices(count, m_base);
Chris@16: 
Chris@16:     return make_vertex_descriptor(process_id(m_process_group), v);
Chris@16:   }
Chris@16: 
Chris@16:   template <typename InputIterator>
Chris@16:   void 
Chris@16:   add_edges(InputIterator first, InputIterator last)
Chris@16:   { boost::add_edges_global(first, last, get(vertex_local, *this), m_base); }
Chris@16: 
Chris@16:   template <typename InputIterator, typename EdgePropertyIterator>
Chris@16:   void 
Chris@16:   add_edges(InputIterator first, InputIterator last,
Chris@16:             EdgePropertyIterator ep_iter,
Chris@16:             EdgePropertyIterator ep_iter_end)
Chris@16:   { boost::add_edges_global(first, last, ep_iter, ep_iter_end, 
Chris@16:                             get(vertex_local, *this), m_base); }
Chris@16: 
Chris@16:   template <typename InputIterator>
Chris@16:   void 
Chris@16:   add_edges_sorted(InputIterator first, InputIterator last)
Chris@16:   { boost::add_edges_sorted_global(first, last, 
Chris@16:                                    get(vertex_local, *this), m_base); }
Chris@16: 
Chris@16:   template <typename InputIterator, typename EdgePropertyIterator>
Chris@16:   void 
Chris@16:   add_edges_sorted(InputIterator first_sorted, InputIterator last_sorted,
Chris@16:                    EdgePropertyIterator ep_iter_sorted)
Chris@16:   { boost::add_edges_sorted_global(first_sorted, last_sorted, ep_iter_sorted, 
Chris@16:                                    get(vertex_local, *this), m_base); }
Chris@16: 
Chris@16:  protected:
Chris@16:   ProcessGroup m_process_group;
Chris@16:   distribution_type m_distribution;
Chris@16:   base_type m_base;
Chris@16: };
Chris@16: 
Chris@16: /** @brief Helper macro containing the template parameters for the
Chris@16:  *   distributed CSR graph.
Chris@16:  *
Chris@16:  *  This macro contains all of the template parameters needed for the
Chris@16:  *  distributed compressed_sparse_row graph type. It is used to reduce
Chris@16:  *  the amount of typing required to declare free functions for this
Chris@16:  *  graph type.
Chris@16:  */
Chris@16: #define BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS                          \
Chris@16:   typename VertexProperty, typename EdgeProperty,    \
Chris@16:   typename GraphProperty, typename ProcessGroup, typename InVertex,     \
Chris@16:   typename InDistribution, typename InEdgeIndex
Chris@16: 
Chris@16: /** @brief Helper macro containing the typical instantiation of the
Chris@16:  *   distributed CSR graph.
Chris@16:  *
Chris@16:  *  This macro contains an instantiation of the distributed CSR graph
Chris@16:  *  type using the typical template parameters names (e.g., those
Chris@16:  *  provided by the macro @c
Chris@16:  *  BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS). It is used to reduce
Chris@16:  *  the amount of typing required to declare free functions for this
Chris@16:  *  graph type.
Chris@16:  */
Chris@16: #define BOOST_DISTRIB_CSR_GRAPH_TYPE                            \
Chris@16:   compressed_sparse_row_graph<                                  \
Chris@16:     directedS, VertexProperty, EdgeProperty, GraphProperty,      \
Chris@16:     distributedS<ProcessGroup, InVertex, InDistribution>,       \
Chris@16:     InEdgeIndex>
Chris@16: 
Chris@16: // -----------------------------------------------------------------
Chris@16: // Graph concept operations
Chris@16: template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS>
Chris@16: inline typename BOOST_DISTRIB_CSR_GRAPH_TYPE::vertex_descriptor
Chris@16: BOOST_DISTRIB_CSR_GRAPH_TYPE::null_vertex()
Chris@16: {
Chris@16:   return graph_traits<base_type>::null_vertex();
Chris@16: }
Chris@16: 
Chris@16: // -----------------------------------------------------------------
Chris@16: // Incidence Graph concept operations
Chris@16: template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS>
Chris@16: inline typename BOOST_DISTRIB_CSR_GRAPH_TYPE::vertex_descriptor
Chris@16: source(typename BOOST_DISTRIB_CSR_GRAPH_TYPE::edge_descriptor e,
Chris@16:        const BOOST_DISTRIB_CSR_GRAPH_TYPE&)
Chris@16: { return e.src; }
Chris@16: 
Chris@16: template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS>
Chris@16: inline typename BOOST_DISTRIB_CSR_GRAPH_TYPE::vertex_descriptor
Chris@16: target(typename BOOST_DISTRIB_CSR_GRAPH_TYPE::edge_descriptor e,
Chris@16:        const BOOST_DISTRIB_CSR_GRAPH_TYPE& g)
Chris@16: { return target(e, g.base()); }
Chris@16: 
Chris@16: template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS>
Chris@16: inline std::pair<typename BOOST_DISTRIB_CSR_GRAPH_TYPE::out_edge_iterator,
Chris@16:                  typename BOOST_DISTRIB_CSR_GRAPH_TYPE::out_edge_iterator>
Chris@16: out_edges(typename BOOST_DISTRIB_CSR_GRAPH_TYPE::vertex_descriptor u,
Chris@16:           const BOOST_DISTRIB_CSR_GRAPH_TYPE& g)
Chris@16: {
Chris@16:   typedef typename BOOST_DISTRIB_CSR_GRAPH_TYPE::edges_size_type
Chris@16:     edges_size_type;
Chris@16:   typedef typename BOOST_DISTRIB_CSR_GRAPH_TYPE::edge_descriptor ed;
Chris@16:   typedef typename BOOST_DISTRIB_CSR_GRAPH_TYPE::out_edge_iterator it;
Chris@16:   edges_size_type u_local = get(vertex_local, g, u);
Chris@16:   edges_size_type u_row_start = g.base().m_forward.m_rowstart[u_local];
Chris@16:   edges_size_type next_row_start = g.base().m_forward.m_rowstart[u_local + 1];
Chris@16:   return std::make_pair(it(ed(u, u_row_start)),
Chris@16:                         it(ed(u, (std::max)(u_row_start, next_row_start))));
Chris@16: }
Chris@16: 
Chris@16: template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS>
Chris@16: inline typename BOOST_DISTRIB_CSR_GRAPH_TYPE::degree_size_type
Chris@16: out_degree(typename BOOST_DISTRIB_CSR_GRAPH_TYPE::vertex_descriptor u,
Chris@16:            const BOOST_DISTRIB_CSR_GRAPH_TYPE& g)
Chris@16: {
Chris@16:   return out_degree(get(vertex_local, g, u), g.base());
Chris@16: }
Chris@16: 
Chris@16: // -----------------------------------------------------------------
Chris@16: // DistributedGraph concept requirements
Chris@16: template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS>
Chris@16: void synchronize(const BOOST_DISTRIB_CSR_GRAPH_TYPE& g)
Chris@16: {
Chris@16:   synchronize(g.process_group());
Chris@16: }
Chris@16: 
Chris@16: template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS> 
Chris@16: ProcessGroup
Chris@16: process_group(const BOOST_DISTRIB_CSR_GRAPH_TYPE& g)
Chris@16: { return g.process_group(); }
Chris@16: 
Chris@16: 
Chris@16: // -----------------------------------------------------------------
Chris@16: // Adjacency Graph concept requirements
Chris@16: template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS>
Chris@16: inline std::pair<typename BOOST_DISTRIB_CSR_GRAPH_TYPE::adjacency_iterator,
Chris@16:                  typename BOOST_DISTRIB_CSR_GRAPH_TYPE::adjacency_iterator>
Chris@16: adjacent_vertices(typename BOOST_DISTRIB_CSR_GRAPH_TYPE::vertex_descriptor u,
Chris@16:                   const BOOST_DISTRIB_CSR_GRAPH_TYPE& g)
Chris@16: {
Chris@16:   return adjacent_vertices(get(vertex_local, g, u), g.base());
Chris@16: }
Chris@16: 
Chris@16: // -----------------------------------------------------------------
Chris@16: // Distributed Vertex List Graph concept operations
Chris@16: template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS>
Chris@16: class BOOST_DISTRIB_CSR_GRAPH_TYPE::vertex_iterator
Chris@16:   : public iterator_adaptor<vertex_iterator,
Chris@16:                             counting_iterator<Vertex>,
Chris@16:                             Vertex,
Chris@16:                             random_access_traversal_tag,
Chris@16:                             Vertex>
Chris@16: {
Chris@16:   typedef iterator_adaptor<vertex_iterator,
Chris@16:                            counting_iterator<Vertex>,
Chris@16:                            Vertex,
Chris@16:                            random_access_traversal_tag,
Chris@16:                            Vertex> inherited;
Chris@16:  public:
Chris@16:   vertex_iterator() {}
Chris@16: 
Chris@16:   explicit vertex_iterator(Vertex v, const self_type* graph)
Chris@16:     : inherited(counting_iterator<Vertex>(v)), graph(graph) { }
Chris@16: 
Chris@16:   Vertex dereference() const
Chris@16:   {
Chris@16:     return graph->local_to_global_vertex(*(this->base_reference()));
Chris@16:   }
Chris@16: 
Chris@16:   friend class iterator_core_access;
Chris@16: 
Chris@16:  private:
Chris@16:   const self_type* graph;
Chris@16: };
Chris@16: 
Chris@16: template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS>
Chris@16: inline typename BOOST_DISTRIB_CSR_GRAPH_TYPE::degree_size_type
Chris@16: num_vertices(const BOOST_DISTRIB_CSR_GRAPH_TYPE& g)
Chris@16: {
Chris@16:   return num_vertices(g.base());
Chris@16: }
Chris@16: 
Chris@16: template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS>
Chris@16: inline std::pair<typename BOOST_DISTRIB_CSR_GRAPH_TYPE::vertex_iterator,
Chris@16:                  typename BOOST_DISTRIB_CSR_GRAPH_TYPE::vertex_iterator>
Chris@16: vertices(const BOOST_DISTRIB_CSR_GRAPH_TYPE& g)
Chris@16: {
Chris@16:   typedef typename BOOST_DISTRIB_CSR_GRAPH_TYPE::vertex_iterator
Chris@16:     vertex_iterator;
Chris@16:   return std::make_pair(vertex_iterator(0, &g),
Chris@16:                         vertex_iterator(num_vertices(g), &g));
Chris@16: }
Chris@16: 
Chris@16: // -----------------------------------------------------------------
Chris@16: // Distributed Edge List Graph concept operations
Chris@16: template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS>
Chris@16: class BOOST_DISTRIB_CSR_GRAPH_TYPE::edge_iterator
Chris@16: {
Chris@16:  public:
Chris@16:   typedef std::forward_iterator_tag iterator_category;
Chris@16:   typedef edge_descriptor value_type;
Chris@16: 
Chris@16:   typedef const edge_descriptor* pointer;
Chris@16: 
Chris@16:   typedef edge_descriptor reference;
Chris@16:   typedef typename int_t<CHAR_BIT * sizeof(EdgeIndex)>::fast difference_type;
Chris@16: 
Chris@16:   edge_iterator() : graph(0), current_edge(), end_of_this_vertex(0) {}
Chris@16: 
Chris@16:   edge_iterator(const compressed_sparse_row_graph& graph,
Chris@16:                 edge_descriptor current_edge,
Chris@16:                 EdgeIndex end_of_this_vertex)
Chris@16:     : graph(&graph), local_src(current_edge.src), current_edge(current_edge),
Chris@16:       end_of_this_vertex(end_of_this_vertex)
Chris@16:   {
Chris@16:     // The edge that comes in has a local source vertex. Make it global.
Chris@16:     current_edge.src = graph.local_to_global_vertex(current_edge.src);
Chris@16:   }
Chris@16: 
Chris@16:   // From InputIterator
Chris@16:   reference operator*() const { return current_edge; }
Chris@16:   pointer operator->() const { return &current_edge; }
Chris@16: 
Chris@16:   bool operator==(const edge_iterator& o) const {
Chris@16:     return current_edge == o.current_edge;
Chris@16:   }
Chris@16:   bool operator!=(const edge_iterator& o) const {
Chris@16:     return current_edge != o.current_edge;
Chris@16:   }
Chris@16: 
Chris@16:   edge_iterator& operator++()
Chris@16:   {
Chris@16:     ++current_edge.idx;
Chris@16:     while (current_edge.idx == end_of_this_vertex && local_src < num_vertices(*graph)-1) {
Chris@16:       ++local_src;
Chris@16:       current_edge.src = graph->local_to_global_vertex(local_src);
Chris@16:       end_of_this_vertex = graph->base().m_forward.m_rowstart[local_src + 1];
Chris@16:     }
Chris@16:     return *this;
Chris@16:   }
Chris@16: 
Chris@16:   edge_iterator operator++(int) {
Chris@16:     edge_iterator temp = *this;
Chris@16:     ++*this;
Chris@16:     return temp;
Chris@16:   }
Chris@16: 
Chris@16:  private:
Chris@16:   const compressed_sparse_row_graph* graph;
Chris@16:   EdgeIndex local_src;
Chris@16:   edge_descriptor current_edge;
Chris@16:   EdgeIndex end_of_this_vertex;
Chris@16: };
Chris@16: 
Chris@16: template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS>
Chris@16: inline typename BOOST_DISTRIB_CSR_GRAPH_TYPE::edges_size_type
Chris@16: num_edges(const BOOST_DISTRIB_CSR_GRAPH_TYPE& g)
Chris@16: {
Chris@16:   return g.base().m_forward.m_column.size();
Chris@16: }
Chris@16: 
Chris@16: template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS>
Chris@16: std::pair<typename BOOST_DISTRIB_CSR_GRAPH_TYPE::edge_iterator,
Chris@16:           typename BOOST_DISTRIB_CSR_GRAPH_TYPE::edge_iterator>
Chris@16: edges(const BOOST_DISTRIB_CSR_GRAPH_TYPE& g)
Chris@16: {
Chris@16:   typedef typename BOOST_DISTRIB_CSR_GRAPH_TYPE::vertex_descriptor Vertex;
Chris@16:   typedef typename BOOST_DISTRIB_CSR_GRAPH_TYPE::edge_iterator ei;
Chris@16:   typedef typename BOOST_DISTRIB_CSR_GRAPH_TYPE::edge_descriptor edgedesc;
Chris@16:   if (g.base().m_forward.m_rowstart.size() == 1 ||
Chris@16:       g.base().m_forward.m_column.empty()) {
Chris@16:     return std::make_pair(ei(), ei());
Chris@16:   } else {
Chris@16:     // Find the first vertex that has outgoing edges
Chris@16:     Vertex src = 0;
Chris@16:     while (g.base().m_forward.m_rowstart[src + 1] == 0) ++src;
Chris@16:     return std::make_pair(ei(g, edgedesc(src, 0), g.base().m_forward.m_rowstart[src + 1]),
Chris@16:                           ei(g, edgedesc(num_vertices(g), g.base().m_forward.m_column.size()), 0));
Chris@16:   }
Chris@16: }
Chris@16: 
Chris@16: // -----------------------------------------------------------------
Chris@16: // Graph constructors
Chris@16: 
Chris@16: // Returns true if a vertex belongs to a process according to a distribution
Chris@16: template <typename OwnerMap, typename ProcessId>
Chris@16: struct local_vertex {
Chris@16: 
Chris@16:   local_vertex(OwnerMap owner, ProcessId id) 
Chris@16:     : owner(owner), id(id) {}
Chris@16: 
Chris@16:   template <typename Vertex>
Chris@16:   bool operator()(Vertex x) 
Chris@16:   { return get(owner, x) == id; }
Chris@16: 
Chris@16:   template <typename Vertex>
Chris@16:   bool operator()(Vertex x) const
Chris@16:   { return get(owner, x) == id; }
Chris@16: 
Chris@16: private:
Chris@16:   OwnerMap owner;
Chris@16:   ProcessId id;
Chris@16: };
Chris@16: 
Chris@16: // Returns true if a vertex belongs to a process according to a distribution
Chris@16: template <typename OwnerMap, typename ProcessId>
Chris@16: struct local_edge {
Chris@16: 
Chris@16:   local_edge(OwnerMap owner, ProcessId id) 
Chris@16:     : owner(owner), id(id) {}
Chris@16: 
Chris@16:   template <typename Vertex>
Chris@16:   bool operator()(std::pair<Vertex, Vertex>& x) 
Chris@16:   { return get(owner, x.first) == id; }
Chris@16: 
Chris@16:   template <typename Vertex>
Chris@16:   bool operator()(const std::pair<Vertex, Vertex>& x) const
Chris@16:   { return get(owner, x.first) == id; }
Chris@16: 
Chris@16: private:
Chris@16:   OwnerMap owner;
Chris@16:   ProcessId id;
Chris@16: };
Chris@16: 
Chris@16: // Turns an index iterator into a vertex iterator
Chris@16: template<typename IndexIterator, typename Graph>
Chris@16: class index_to_vertex_iterator {
Chris@16:   
Chris@16: public:
Chris@16:   typedef std::input_iterator_tag iterator_category;
Chris@16:   typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
Chris@16:   typedef std::pair<Vertex, Vertex> value_type;
Chris@16:   typedef const value_type& reference;
Chris@16:   typedef const value_type* pointer;
Chris@16:   typedef void difference_type;
Chris@16: 
Chris@16:   index_to_vertex_iterator(IndexIterator index,
Chris@16:                            const Graph& g) 
Chris@16:     : index(index), g(g), current(to_edge(*index)) {}
Chris@16: 
Chris@16:   reference operator*() { current = to_edge(*index); return current; }
Chris@16:   pointer operator->() { current = to_edge(*index); return &current; }
Chris@16: 
Chris@16:   index_to_vertex_iterator& operator++()
Chris@16:   {
Chris@16:     ++index;
Chris@16:     return *this;
Chris@16:   }
Chris@16: 
Chris@16:   index_to_vertex_iterator operator++(int)
Chris@16:   {
Chris@16:     index_to_vertex_iterator temp(*this);
Chris@16:     ++(*this);
Chris@16:     return temp;
Chris@16:   }
Chris@16: 
Chris@16:   bool operator==(const index_to_vertex_iterator& other) const
Chris@16:   { return index == other.index; }
Chris@16:   
Chris@16:   bool operator!=(const index_to_vertex_iterator& other) const
Chris@16:   { return !(*this == other); }
Chris@16: 
Chris@16: private:
Chris@16:   value_type to_edge(const typename std::iterator_traits<IndexIterator>::value_type& x)
Chris@16:   { return std::make_pair(vertex(x.first, g), vertex(x.second, g)); }
Chris@16: 
Chris@16:   IndexIterator index;
Chris@16:   const Graph& g;  
Chris@16:   value_type current;
Chris@16: };
Chris@16: 
Chris@16: template <typename Distribution, typename Graph>
Chris@16: struct index_to_vertex_func {
Chris@16: 
Chris@16:   typedef typename boost::graph_traits<Graph>::vertex_descriptor vertex_descriptor;
Chris@16:   typedef typename boost::graph_traits<Graph>::vertices_size_type vertices_size_type;
Chris@16:   typedef std::pair<vertex_descriptor, vertex_descriptor> result_type;
Chris@16:   typedef std::pair<vertices_size_type, vertices_size_type> base_iterator_type;
Chris@16: 
Chris@16:   index_to_vertex_func(const Distribution& dist, const Graph& g)
Chris@16:     : dist(dist), g(g) {}
Chris@16: 
Chris@16: 
Chris@16:   result_type operator()(const base_iterator_type& p) const 
Chris@16:   {
Chris@16:     return std::make_pair(vertex(p.first, g), vertex(p.second, g));
Chris@16:   }
Chris@16: 
Chris@16: private:
Chris@16:   const Distribution& dist;
Chris@16:   const Graph& g;
Chris@16: };
Chris@16: 
Chris@16: // NGE: This method only works with iterators that have a difference_type,
Chris@16: // the index_to_vertex_iterator class above is retained for compatibility
Chris@16: // with BGL generators which have no difference_type
Chris@16: template <typename IndexIterator, typename Distribution, typename Graph>
Chris@16: boost::transform_iterator<index_to_vertex_func<Distribution, Graph>, IndexIterator>
Chris@16: make_index_to_vertex_iterator(IndexIterator it, const Distribution& dist, 
Chris@16:                               const Graph& g) {
Chris@16:   return boost::make_transform_iterator(
Chris@16:     it, index_to_vertex_func<Distribution, Graph>(dist, g));
Chris@16: }
Chris@16: 
Chris@16: // Forward declaration of csr_vertex_owner_map
Chris@16: template<typename ProcessID, typename Key> class csr_vertex_owner_map;
Chris@16: 
Chris@16: template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS>
Chris@16: template<typename InputIterator>
Chris@16: BOOST_DISTRIB_CSR_GRAPH_TYPE::
Chris@16: compressed_sparse_row_graph(edges_are_unsorted_t,
Chris@16:                             InputIterator edge_begin, InputIterator edge_end,
Chris@16:                             vertices_size_type numverts,
Chris@16:                             const ProcessGroup& pg,
Chris@16:                             const GraphProperty& prop)
Chris@16:   : m_process_group(pg),
Chris@16:     m_distribution(parallel::block(m_process_group, numverts)),
Chris@16:     m_base(edges_are_unsorted_global,
Chris@16:            index_to_vertex_iterator<InputIterator, BOOST_DISTRIB_CSR_GRAPH_TYPE>(edge_begin, *this),
Chris@16:            index_to_vertex_iterator<InputIterator, BOOST_DISTRIB_CSR_GRAPH_TYPE>(edge_end, *this),
Chris@16:            m_distribution.block_size(process_id(m_process_group), numverts),
Chris@16:            get(vertex_local, *this),
Chris@16:            local_vertex<csr_vertex_owner_map<process_id_type, vertex_descriptor>, 
Chris@16:                         process_id_type> (get(vertex_owner, *this), process_id(pg)),
Chris@16:            prop)
Chris@16: { }
Chris@16: 
Chris@16: template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS>
Chris@16: template <typename InputIterator, typename Distribution>
Chris@16: BOOST_DISTRIB_CSR_GRAPH_TYPE::
Chris@16: compressed_sparse_row_graph(edges_are_unsorted_t,
Chris@16:                             InputIterator edge_begin, InputIterator edge_end,
Chris@16:                             vertices_size_type numverts,
Chris@16:                             const ProcessGroup& pg,
Chris@16:                             const Distribution& dist,
Chris@16:                             const GraphProperty& prop)
Chris@16:   : m_process_group(pg),
Chris@16:     m_distribution(dist),
Chris@16:     m_base(edges_are_unsorted_global,
Chris@16:            index_to_vertex_iterator<InputIterator, BOOST_DISTRIB_CSR_GRAPH_TYPE>(edge_begin, *this),
Chris@16:            index_to_vertex_iterator<InputIterator, BOOST_DISTRIB_CSR_GRAPH_TYPE>(edge_end, *this),
Chris@16:            m_distribution.block_size(process_id(m_process_group), numverts),
Chris@16:            get(vertex_local, *this),
Chris@16:            local_vertex<csr_vertex_owner_map<process_id_type, vertex_descriptor>, 
Chris@16:                         process_id_type> (get(vertex_owner, *this), process_id(pg)),
Chris@16:            prop)
Chris@16: { }
Chris@16: 
Chris@16: template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS>
Chris@16: template<typename InputIterator, typename EdgePropertyIterator>
Chris@16: BOOST_DISTRIB_CSR_GRAPH_TYPE::
Chris@16: compressed_sparse_row_graph(edges_are_unsorted_t,
Chris@16:                             InputIterator edge_begin, InputIterator edge_end,
Chris@16:                             EdgePropertyIterator ep_iter,
Chris@16:                             vertices_size_type numverts,
Chris@16:                             const ProcessGroup& pg,
Chris@16:                             const GraphProperty& prop)
Chris@16:   : m_process_group(pg),
Chris@16:     m_distribution(parallel::block(m_process_group, numverts)),
Chris@16:     m_base(edges_are_unsorted_global,
Chris@16:            index_to_vertex_iterator<InputIterator, BOOST_DISTRIB_CSR_GRAPH_TYPE>(edge_begin, *this),
Chris@16:            index_to_vertex_iterator<InputIterator, BOOST_DISTRIB_CSR_GRAPH_TYPE>(edge_end, *this),
Chris@16:            ep_iter,
Chris@16:            m_distribution.block_size(process_id(m_process_group), numverts),
Chris@16:            get(vertex_local, *this),
Chris@16:            local_vertex<csr_vertex_owner_map<process_id_type, vertex_descriptor>, 
Chris@16:                         process_id_type> (get(vertex_owner, *this), process_id(pg)),
Chris@16:            prop)
Chris@16: { }
Chris@16: 
Chris@16: template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS>
Chris@16: template <typename InputIterator, typename EdgePropertyIterator,
Chris@16:           typename Distribution>
Chris@16: BOOST_DISTRIB_CSR_GRAPH_TYPE::
Chris@16: compressed_sparse_row_graph(edges_are_unsorted_t,
Chris@16:                             InputIterator edge_begin, InputIterator edge_end,
Chris@16:                             EdgePropertyIterator ep_iter,
Chris@16:                             vertices_size_type numverts,
Chris@16:                             const ProcessGroup& pg,
Chris@16:                             const Distribution& dist,
Chris@16:                             const GraphProperty& prop)
Chris@16:   : m_process_group(pg),
Chris@16:     m_distribution(dist),
Chris@16:     m_base(edges_are_unsorted_global,
Chris@16:            index_to_vertex_iterator<InputIterator, BOOST_DISTRIB_CSR_GRAPH_TYPE>(edge_begin, *this),
Chris@16:            index_to_vertex_iterator<InputIterator, BOOST_DISTRIB_CSR_GRAPH_TYPE>(edge_end, *this),
Chris@16:            ep_iter,
Chris@16:            m_distribution.block_size(process_id(m_process_group), numverts),
Chris@16:            get(vertex_local, *this),
Chris@16:            local_vertex<csr_vertex_owner_map<process_id_type, vertex_descriptor>, 
Chris@16:                         process_id_type> (get(vertex_owner, *this), process_id(pg)),
Chris@16:            prop)
Chris@16: { }
Chris@16: 
Chris@16: template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS>
Chris@16: template<typename InputIterator>
Chris@16: BOOST_DISTRIB_CSR_GRAPH_TYPE::
Chris@16: compressed_sparse_row_graph(edges_are_sorted_t,
Chris@16:                             InputIterator edge_begin, InputIterator edge_end,
Chris@16:                             vertices_size_type numverts,
Chris@16:                             edges_size_type numedges, // This is not used as there is no appropriate BGL ctor
Chris@16:                             const ProcessGroup& pg,
Chris@16:                             const GraphProperty& prop)
Chris@16:   : m_process_group(pg),
Chris@16:     m_distribution(parallel::block(m_process_group, numverts)),
Chris@16:     m_base(edges_are_sorted_global,
Chris@16:            index_to_vertex_iterator<InputIterator, BOOST_DISTRIB_CSR_GRAPH_TYPE>(edge_begin, *this),
Chris@16:            index_to_vertex_iterator<InputIterator, BOOST_DISTRIB_CSR_GRAPH_TYPE>(edge_end, *this),
Chris@16:            get(vertex_local, *this),
Chris@16:            local_vertex<csr_vertex_owner_map<process_id_type, vertex_descriptor>, 
Chris@16:                         process_id_type> (get(vertex_owner, *this), process_id(pg)),
Chris@16:            m_distribution.block_size(process_id(m_process_group), numverts),
Chris@16:            prop)
Chris@16: { }
Chris@16: 
Chris@16: template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS>
Chris@16: template <typename InputIterator, typename Distribution>
Chris@16: BOOST_DISTRIB_CSR_GRAPH_TYPE::
Chris@16: compressed_sparse_row_graph(edges_are_sorted_t,
Chris@16:                             InputIterator edge_begin, InputIterator edge_end,
Chris@16:                             vertices_size_type numverts,
Chris@16:                             const ProcessGroup& pg,
Chris@16:                             const Distribution& dist,
Chris@16:                             const GraphProperty& prop)
Chris@16:   : m_process_group(pg),
Chris@16:     m_distribution(dist),
Chris@16:     m_base(edges_are_sorted_global,
Chris@16:            index_to_vertex_iterator<InputIterator, BOOST_DISTRIB_CSR_GRAPH_TYPE>(edge_begin, *this),
Chris@16:            index_to_vertex_iterator<InputIterator, BOOST_DISTRIB_CSR_GRAPH_TYPE>(edge_end, *this),
Chris@16:            get(vertex_local, *this),
Chris@16:            local_vertex<csr_vertex_owner_map<process_id_type, vertex_descriptor>, 
Chris@16:                         process_id_type> (get(vertex_owner, *this), process_id(pg)),
Chris@16:            m_distribution.block_size(process_id(m_process_group), numverts),
Chris@16:            prop)
Chris@16: { }
Chris@16: 
Chris@16: template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS>
Chris@16: template<typename InputIterator, typename EdgePropertyIterator>
Chris@16: BOOST_DISTRIB_CSR_GRAPH_TYPE::
Chris@16: compressed_sparse_row_graph(edges_are_sorted_t,
Chris@16:                             InputIterator edge_begin, InputIterator edge_end,
Chris@16:                             EdgePropertyIterator ep_iter,
Chris@16:                             vertices_size_type numverts,
Chris@16:                             edges_size_type numedges, // This is not used as there is no appropriate BGL ctor
Chris@16:                             const ProcessGroup& pg,
Chris@16:                             const GraphProperty& prop)
Chris@16:   : m_process_group(pg),
Chris@16:     m_distribution(parallel::block(m_process_group, numverts)),
Chris@16:     m_base(edges_are_sorted_global,
Chris@16:            index_to_vertex_iterator<InputIterator, BOOST_DISTRIB_CSR_GRAPH_TYPE>(edge_begin, *this),
Chris@16:            index_to_vertex_iterator<InputIterator, BOOST_DISTRIB_CSR_GRAPH_TYPE>(edge_end, *this),
Chris@16:            ep_iter,
Chris@16:            get(vertex_local, *this),
Chris@16:            local_vertex<csr_vertex_owner_map<process_id_type, vertex_descriptor>, 
Chris@16:                         process_id_type> (get(vertex_owner, *this), process_id(pg)),
Chris@16:            m_distribution.block_size(process_id(m_process_group), numverts),
Chris@16:            prop)
Chris@16: { }
Chris@16: 
Chris@16: template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS>
Chris@16: template<typename InputIterator, typename EdgePropertyIterator,
Chris@16:          typename Distribution>
Chris@16: BOOST_DISTRIB_CSR_GRAPH_TYPE::
Chris@16: compressed_sparse_row_graph(edges_are_sorted_t,
Chris@16:                             InputIterator edge_begin, InputIterator edge_end,
Chris@16:                             EdgePropertyIterator ep_iter,
Chris@16:                             vertices_size_type numverts,
Chris@16:                             const ProcessGroup& pg,
Chris@16:                             const Distribution& dist,
Chris@16:                             const GraphProperty& prop)
Chris@16:   : m_process_group(pg),
Chris@16:     m_distribution(dist),
Chris@16:     m_base(edges_are_sorted_global,
Chris@16:            index_to_vertex_iterator<InputIterator, BOOST_DISTRIB_CSR_GRAPH_TYPE>(edge_begin, *this),
Chris@16:            index_to_vertex_iterator<InputIterator, BOOST_DISTRIB_CSR_GRAPH_TYPE>(edge_end, *this),
Chris@16:            ep_iter,
Chris@16:            get(vertex_local, *this),
Chris@16:            local_vertex<csr_vertex_owner_map<process_id_type, vertex_descriptor>, 
Chris@16:                         process_id_type> (get(vertex_owner, *this), process_id(pg)),
Chris@16:            m_distribution.block_size(process_id(m_process_group), numverts),
Chris@16:            prop)
Chris@16: { }
Chris@16: 
Chris@16: template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS>
Chris@16: template<typename MultiPassInputIterator>
Chris@16: BOOST_DISTRIB_CSR_GRAPH_TYPE::
Chris@16: compressed_sparse_row_graph(edges_are_unsorted_multi_pass_t,
Chris@16:                             MultiPassInputIterator edge_begin, 
Chris@16:                             MultiPassInputIterator edge_end,
Chris@16:                             vertices_size_type numverts,
Chris@16:                             const ProcessGroup& pg,
Chris@16:                             const GraphProperty& prop)
Chris@16:   : m_process_group(pg),
Chris@16:     m_distribution(parallel::block(m_process_group, numverts)),
Chris@16:     m_base(edges_are_unsorted_multi_pass_global,
Chris@16:            make_index_to_vertex_iterator(edge_begin, parallel::block(m_process_group, numverts), *this),
Chris@16:            make_index_to_vertex_iterator(edge_end, parallel::block(m_process_group, numverts), *this),
Chris@16:            m_distribution.block_size(process_id(m_process_group), numverts),
Chris@16:            get(vertex_local, *this),
Chris@16:            local_vertex<csr_vertex_owner_map<process_id_type, vertex_descriptor>, 
Chris@16:                         process_id_type> (get(vertex_owner, *this), process_id(pg)),
Chris@16:            prop)
Chris@16: { }
Chris@16: 
Chris@16: template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS>
Chris@16: template <typename MultiPassInputIterator, typename Distribution>
Chris@16: BOOST_DISTRIB_CSR_GRAPH_TYPE::
Chris@16: compressed_sparse_row_graph(edges_are_unsorted_multi_pass_t,
Chris@16:                             MultiPassInputIterator edge_begin, 
Chris@16:                             MultiPassInputIterator edge_end,
Chris@16:                             vertices_size_type numverts,
Chris@16:                             const ProcessGroup& pg,
Chris@16:                             const Distribution& dist,
Chris@16:                             const GraphProperty& prop)
Chris@16:   : m_process_group(pg),
Chris@16:     m_distribution(dist),
Chris@16:     m_base(edges_are_unsorted_multi_pass_global,
Chris@16:            make_index_to_vertex_iterator(edge_begin, parallel::block(m_process_group, numverts), *this),
Chris@16:            make_index_to_vertex_iterator(edge_end, parallel::block(m_process_group, numverts), *this),
Chris@16:            m_distribution.block_size(process_id(m_process_group), numverts),
Chris@16:            get(vertex_local, *this),
Chris@16:            local_vertex<csr_vertex_owner_map<process_id_type, vertex_descriptor>, 
Chris@16:                         process_id_type> (get(vertex_owner, *this), process_id(pg)),
Chris@16:            prop)
Chris@16: { }
Chris@16: 
Chris@16: 
Chris@16: template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS>
Chris@16: template<typename MultiPassInputIterator, typename EdgePropertyIterator>
Chris@16: BOOST_DISTRIB_CSR_GRAPH_TYPE::
Chris@16: compressed_sparse_row_graph(edges_are_unsorted_multi_pass_t,
Chris@16:                             MultiPassInputIterator edge_begin, 
Chris@16:                             MultiPassInputIterator edge_end,
Chris@16:                             EdgePropertyIterator ep_iter,
Chris@16:                             vertices_size_type numverts,
Chris@16:                             const ProcessGroup& pg,
Chris@16:                             const GraphProperty& prop)
Chris@16:   : m_process_group(pg),
Chris@16:     m_distribution(parallel::block(m_process_group, numverts)),
Chris@16:     m_base(edges_are_unsorted_multi_pass_global,
Chris@16:            make_index_to_vertex_iterator(edge_begin, parallel::block(m_process_group, numverts), *this),
Chris@16:            make_index_to_vertex_iterator(edge_end, parallel::block(m_process_group, numverts), *this),
Chris@16:            ep_iter,
Chris@16:            m_distribution.block_size(process_id(m_process_group), numverts),
Chris@16:            get(vertex_local, *this),
Chris@16:            local_vertex<csr_vertex_owner_map<process_id_type, vertex_descriptor>, 
Chris@16:                         process_id_type> (get(vertex_owner, *this), process_id(pg)),
Chris@16:            prop)
Chris@16: { }
Chris@16: 
Chris@16: template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS>
Chris@16: template <typename MultiPassInputIterator, typename EdgePropertyIterator,
Chris@16:           typename Distribution>
Chris@16: BOOST_DISTRIB_CSR_GRAPH_TYPE::
Chris@16: compressed_sparse_row_graph(edges_are_unsorted_multi_pass_t,
Chris@16:                             MultiPassInputIterator edge_begin, 
Chris@16:                             MultiPassInputIterator edge_end,
Chris@16:                             EdgePropertyIterator ep_iter,
Chris@16:                             vertices_size_type numverts,
Chris@16:                             const ProcessGroup& pg,
Chris@16:                             const Distribution& dist,
Chris@16:                             const GraphProperty& prop)
Chris@16:   : m_process_group(pg),
Chris@16:     m_distribution(dist),
Chris@16:     m_base(edges_are_unsorted_multi_pass_global,
Chris@16:            make_index_to_vertex_iterator(edge_begin, parallel::block(m_process_group, numverts), *this),
Chris@16:            make_index_to_vertex_iterator(edge_end, parallel::block(m_process_group, numverts), *this),
Chris@16:            ep_iter,
Chris@16:            m_distribution.block_size(process_id(m_process_group), numverts),
Chris@16:            get(vertex_local, *this),
Chris@16:            local_vertex<csr_vertex_owner_map<process_id_type, vertex_descriptor>, 
Chris@16:                         process_id_type> (get(vertex_owner, *this), process_id(pg)),
Chris@16:            prop)
Chris@16: { }
Chris@16: 
Chris@16: template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS>
Chris@16: template<typename Source>
Chris@16: BOOST_DISTRIB_CSR_GRAPH_TYPE::
Chris@16: compressed_sparse_row_graph(distributed_construct_inplace_from_sources_and_targets_t,
Chris@16:                             std::vector<Source>& sources,
Chris@16:                             std::vector<vertex_descriptor>& targets,
Chris@16:                             vertices_size_type numverts,
Chris@16:                             const ProcessGroup& pg,
Chris@16:                             const GraphProperty& prop)
Chris@16:   : m_process_group(pg),
Chris@16:     m_distribution(parallel::block(m_process_group, numverts)),
Chris@16:     m_base(m_distribution.block_size(process_id(m_process_group), numverts))
Chris@16: { 
Chris@16:   // Convert linear indices to global indices
Chris@16:   for (edges_size_type i = 0; i < sources.size(); ++i) {
Chris@16:     sources[i] = m_distribution.local(sources[i]);
Chris@16:     targets[i] = make_vertex_descriptor(m_distribution(targets[i]), 
Chris@16:                                         m_distribution.local(targets[i]));
Chris@16:   }
Chris@16: 
Chris@16:   m_base.assign_sources_and_targets_global(
Chris@16:     sources, targets, m_distribution.block_size(process_id(m_process_group), numverts),
Chris@16:     identity_property_map());
Chris@16: 
Chris@16:   // TODO: set property on m_base?
Chris@16: }
Chris@16: 
Chris@16: template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS>
Chris@16: template <typename Distribution, typename Source> 
Chris@16: BOOST_DISTRIB_CSR_GRAPH_TYPE::
Chris@16: compressed_sparse_row_graph(distributed_construct_inplace_from_sources_and_targets_t,
Chris@16:                             std::vector<Source>& sources,
Chris@16:                             std::vector<vertex_descriptor>& targets,
Chris@16:                             vertices_size_type numverts,
Chris@16:                             const ProcessGroup& pg,
Chris@16:                             const Distribution& dist,
Chris@16:                             const GraphProperty& prop)
Chris@16:   : m_process_group(pg),
Chris@16:     m_distribution(dist),
Chris@16:     m_base(m_distribution.block_size(process_id(m_process_group), numverts))
Chris@16: { 
Chris@16:   // Convert linear indices to global indices
Chris@16:   for (edges_size_type i = 0; i < sources.size(); ++i) {
Chris@16:     sources[i] = m_distribution.local(sources[i]);
Chris@16:     targets[i] = make_vertex_descriptor(m_distribution(targets[i]), 
Chris@16:                                         m_distribution.local(targets[i]));
Chris@16:   }
Chris@16: 
Chris@16:   m_base.assign_sources_and_targets_global(
Chris@16:     sources, targets, m_distribution.block_size(process_id(m_process_group), numverts),
Chris@16:     identity_property_map());
Chris@16: 
Chris@16:   // TODO: set property on m_base?
Chris@16: }
Chris@16: 
Chris@16: template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS>
Chris@16: template<typename Source>
Chris@16: BOOST_DISTRIB_CSR_GRAPH_TYPE::
Chris@16: compressed_sparse_row_graph(distributed_construct_inplace_from_sources_and_targets_t,
Chris@16:                             std::vector<Source>& sources,
Chris@16:                             std::vector<vertex_descriptor>& targets,
Chris@16:                             std::vector<edge_bundled>& edge_props,
Chris@16:                             vertices_size_type numverts,
Chris@16:                             const ProcessGroup& pg,
Chris@16:                             const GraphProperty& prop)
Chris@16:   : m_process_group(pg),
Chris@16:     m_distribution(parallel::block(m_process_group, numverts)),
Chris@16:     m_base(m_distribution.block_size(process_id(m_process_group), numverts))
Chris@16: { 
Chris@16:   // Convert linear indices to global indices
Chris@16:   for (edges_size_type i = 0; i < sources.size(); ++i) {
Chris@16:     sources[i] = m_distribution.local(sources[i]);
Chris@16:     targets[i] = make_vertex_descriptor(m_distribution(targets[i]), 
Chris@16:                                         m_distribution.local(targets[i]));
Chris@16:   }
Chris@16: 
Chris@16:   m_base.assign_sources_and_targets_global(
Chris@16:     sources, targets, edge_props, 
Chris@16:     m_distribution.block_size(process_id(m_process_group), numverts),
Chris@16:     identity_property_map());
Chris@16: 
Chris@16:   // TODO: set property on m_base?
Chris@16: }
Chris@16: 
Chris@16: template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS>
Chris@16: template <typename Distribution, typename Source> 
Chris@16: BOOST_DISTRIB_CSR_GRAPH_TYPE::
Chris@16: compressed_sparse_row_graph(distributed_construct_inplace_from_sources_and_targets_t,
Chris@16:                             std::vector<Source>& sources,
Chris@16:                             std::vector<vertex_descriptor>& targets,
Chris@16:                             std::vector<edge_bundled>& edge_props,
Chris@16:                             vertices_size_type numverts,
Chris@16:                             const ProcessGroup& pg,
Chris@16:                             const Distribution& dist,
Chris@16:                             const GraphProperty& prop)
Chris@16:   : m_process_group(pg),
Chris@16:     m_distribution(dist),
Chris@16:     m_base(m_distribution.block_size(process_id(m_process_group), numverts))
Chris@16: { 
Chris@16:   // Convert linear indices to global indices
Chris@16:   for (edges_size_type i = 0; i < sources.size(); ++i) {
Chris@16:     sources[i] = m_distribution.local(sources[i]);
Chris@16:     targets[i] = make_vertex_descriptor(m_distribution(targets[i]), 
Chris@16:                                         m_distribution.local(targets[i]));
Chris@16:   }
Chris@16: 
Chris@16:   m_base.assign_sources_and_targets_global(
Chris@16:     sources, targets, edge_props, 
Chris@16:     m_distribution.block_size(process_id(m_process_group), numverts),
Chris@16:     identity_property_map());
Chris@16: 
Chris@16:   // TODO: set property on m_base?
Chris@16: }
Chris@16: 
Chris@16: //
Chris@16: // Old (untagged) ctors, these default to the unsorted sequential ctors
Chris@16: //
Chris@16: template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS>
Chris@16: template<typename InputIterator>
Chris@16: BOOST_DISTRIB_CSR_GRAPH_TYPE::
Chris@16: compressed_sparse_row_graph(InputIterator edge_begin, InputIterator edge_end,
Chris@16:                             vertices_size_type numverts,
Chris@16:                             const ProcessGroup& pg,
Chris@16:                             const GraphProperty& prop)
Chris@16:   : m_process_group(pg),
Chris@16:     m_distribution(parallel::block(m_process_group, numverts)),
Chris@16:     m_base(edges_are_unsorted_global,
Chris@16:            index_to_vertex_iterator<InputIterator, BOOST_DISTRIB_CSR_GRAPH_TYPE>(edge_begin, *this),
Chris@16:            index_to_vertex_iterator<InputIterator, BOOST_DISTRIB_CSR_GRAPH_TYPE>(edge_end, *this),
Chris@16:            m_distribution.block_size(process_id(m_process_group), numverts),
Chris@16:            get(vertex_local, *this),
Chris@16:            local_vertex<csr_vertex_owner_map<process_id_type, vertex_descriptor>, 
Chris@16:                         process_id_type> (get(vertex_owner, *this), process_id(pg)),
Chris@16:            prop)
Chris@16:            
Chris@16: {
Chris@16: }
Chris@16: 
Chris@16: template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS>
Chris@16: template<typename InputIterator, typename EdgePropertyIterator>
Chris@16: BOOST_DISTRIB_CSR_GRAPH_TYPE::
Chris@16: compressed_sparse_row_graph(InputIterator edge_begin, InputIterator edge_end,
Chris@16:                             EdgePropertyIterator ep_iter,
Chris@16:                             vertices_size_type numverts,
Chris@16:                             const ProcessGroup& pg,
Chris@16:                             const GraphProperty& prop)
Chris@16:   : m_process_group(pg),
Chris@16: 
Chris@16:     m_distribution(parallel::block(m_process_group, numverts)),
Chris@16:     m_base(edges_are_unsorted_global,
Chris@16:            index_to_vertex_iterator<InputIterator, BOOST_DISTRIB_CSR_GRAPH_TYPE>(edge_begin, *this),
Chris@16:            index_to_vertex_iterator<InputIterator, BOOST_DISTRIB_CSR_GRAPH_TYPE>(edge_end, *this),
Chris@16:            ep_iter,
Chris@16:            m_distribution.block_size(process_id(m_process_group), numverts),
Chris@16:            get(vertex_local, *this),
Chris@16:            local_vertex<csr_vertex_owner_map<process_id_type, vertex_descriptor>, 
Chris@16:                         process_id_type> (get(vertex_owner, *this), process_id(pg)),
Chris@16:            prop)
Chris@16: {
Chris@16: }
Chris@16: 
Chris@16: template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS>
Chris@16: template<typename InputIterator, typename Distribution>
Chris@16: BOOST_DISTRIB_CSR_GRAPH_TYPE::
Chris@16: compressed_sparse_row_graph(InputIterator edge_begin, InputIterator edge_end,
Chris@16:                             vertices_size_type numverts,
Chris@16:                             const ProcessGroup& pg,
Chris@16:                             const Distribution& dist,
Chris@16:                             const GraphProperty& prop)
Chris@16:   : m_process_group(pg),
Chris@16:     m_distribution(dist),
Chris@16:     m_base(edges_are_unsorted_global,
Chris@16:            index_to_vertex_iterator<InputIterator, BOOST_DISTRIB_CSR_GRAPH_TYPE>(edge_begin, *this),
Chris@16:            index_to_vertex_iterator<InputIterator, BOOST_DISTRIB_CSR_GRAPH_TYPE>(edge_end, *this),
Chris@16:            m_distribution.block_size(process_id(m_process_group), numverts),
Chris@16:            get(vertex_local, *this),
Chris@16:            local_vertex<csr_vertex_owner_map<process_id_type, vertex_descriptor>, 
Chris@16:                         process_id_type> (get(vertex_owner, *this), process_id(pg)),
Chris@16:            prop)
Chris@16: {
Chris@16: }
Chris@16: 
Chris@16: template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS>
Chris@16: template<typename InputIterator, typename EdgePropertyIterator, 
Chris@16:          typename Distribution>
Chris@16: BOOST_DISTRIB_CSR_GRAPH_TYPE::
Chris@16: compressed_sparse_row_graph(InputIterator edge_begin, InputIterator edge_end,
Chris@16:                             EdgePropertyIterator ep_iter,
Chris@16:                             vertices_size_type numverts,
Chris@16:                             const ProcessGroup& pg,
Chris@16:                             const Distribution& dist,
Chris@16:                             const GraphProperty& prop)
Chris@16:   : m_process_group(pg),
Chris@16:     m_distribution(dist),
Chris@16:     m_base(edges_are_unsorted_global,
Chris@16:            index_to_vertex_iterator<InputIterator, BOOST_DISTRIB_CSR_GRAPH_TYPE>(edge_begin, *this),
Chris@16:            index_to_vertex_iterator<InputIterator, BOOST_DISTRIB_CSR_GRAPH_TYPE>(edge_end, *this),
Chris@16:            m_distribution.block_size(process_id(m_process_group), numverts),
Chris@16:            get(vertex_local, *this),
Chris@16:            local_vertex<csr_vertex_owner_map<process_id_type, vertex_descriptor>, 
Chris@16:                         process_id_type> (get(vertex_owner, *this), process_id(pg)),
Chris@16:            prop)
Chris@16: {
Chris@16: }
Chris@16: 
Chris@16: // -----------------------------------------------------------------
Chris@16: // Vertex Global Property Map
Chris@16: template<typename ProcessID, typename Key>
Chris@16: class csr_vertex_global_map
Chris@16: {
Chris@16:  public:
Chris@16:   // -----------------------------------------------------------------
Chris@16:   // Readable Property Map concept requirements
Chris@16:   typedef std::pair<ProcessID, Key> value_type;
Chris@16:   typedef value_type reference;
Chris@16:   typedef Key key_type;
Chris@16:   typedef readable_property_map_tag category;
Chris@16: };
Chris@16: 
Chris@16: template<typename ProcessID, typename Key>
Chris@16: inline std::pair<ProcessID, Key>
Chris@16: get(csr_vertex_global_map<ProcessID, Key>,
Chris@16:     typename csr_vertex_global_map<ProcessID, Key>::key_type k)
Chris@16: {
Chris@16:   const int local_index_bits = sizeof(Key) * CHAR_BIT - processor_bits;
Chris@16:   const Key local_index_mask = Key(-1) >> processor_bits;
Chris@16: 
Chris@16:   return std::pair<ProcessID, Key>(k >> local_index_bits,
Chris@16:                                    k & local_index_mask);
Chris@16: }
Chris@16: 
Chris@16: template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS>
Chris@16: class property_map<BOOST_DISTRIB_CSR_GRAPH_TYPE, vertex_global_t>
Chris@16: {
Chris@16:  public:
Chris@16:   typedef csr_vertex_global_map<
Chris@16:             typename ProcessGroup::process_id_type,
Chris@16:             typename BOOST_DISTRIB_CSR_GRAPH_TYPE::vertex_descriptor> type;
Chris@16:   typedef type const_type;
Chris@16: };
Chris@16: 
Chris@16: template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS>
Chris@16: inline
Chris@16: typename property_map<BOOST_DISTRIB_CSR_GRAPH_TYPE, vertex_global_t>::type
Chris@16: get(vertex_global_t, BOOST_DISTRIB_CSR_GRAPH_TYPE& g)
Chris@16: {
Chris@16:   typedef typename property_map<BOOST_DISTRIB_CSR_GRAPH_TYPE, vertex_global_t>
Chris@16:     ::type result_type;
Chris@16:   return result_type();
Chris@16: }
Chris@16: 
Chris@16: template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS>
Chris@16: inline
Chris@16: std::pair<typename ProcessGroup::process_id_type,
Chris@16:           typename BOOST_DISTRIB_CSR_GRAPH_TYPE::vertex_descriptor>
Chris@16: get(vertex_global_t, BOOST_DISTRIB_CSR_GRAPH_TYPE& g,
Chris@16:     typename BOOST_DISTRIB_CSR_GRAPH_TYPE::vertex_descriptor k)
Chris@16: {
Chris@16:   return get(vertex_global, 
Chris@16:              const_cast<const BOOST_DISTRIB_CSR_GRAPH_TYPE&>(g), 
Chris@16:              k);
Chris@16: }
Chris@16: 
Chris@16: template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS>
Chris@16: inline
Chris@16: typename property_map<BOOST_DISTRIB_CSR_GRAPH_TYPE, vertex_global_t>::const_type
Chris@16: get(vertex_global_t, const BOOST_DISTRIB_CSR_GRAPH_TYPE& g)
Chris@16: {
Chris@16:   typedef typename property_map<BOOST_DISTRIB_CSR_GRAPH_TYPE, vertex_global_t>
Chris@16:     ::const_type result_type;
Chris@16:   return result_type();
Chris@16: }
Chris@16: 
Chris@16: template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS>
Chris@16: inline
Chris@16: std::pair<typename ProcessGroup::process_id_type,
Chris@16:           typename BOOST_DISTRIB_CSR_GRAPH_TYPE::vertex_descriptor>
Chris@16: get(vertex_global_t, const BOOST_DISTRIB_CSR_GRAPH_TYPE& g,
Chris@16:     typename BOOST_DISTRIB_CSR_GRAPH_TYPE::vertex_descriptor k)
Chris@16: {
Chris@16:   typedef typename BOOST_DISTRIB_CSR_GRAPH_TYPE::vertex_descriptor
Chris@16:     vertex_descriptor;
Chris@16:   typedef std::pair<typename ProcessGroup::process_id_type, vertex_descriptor>
Chris@16:     result_type;
Chris@16:   const int local_index_bits = 
Chris@16:     sizeof(vertex_descriptor) * CHAR_BIT - processor_bits;
Chris@16:   const vertex_descriptor local_index_mask = 
Chris@16:     vertex_descriptor(-1) >> processor_bits;
Chris@16: 
Chris@16:   return result_type(k >> local_index_bits, k & local_index_mask);
Chris@16: }
Chris@16: 
Chris@16: // -----------------------------------------------------------------
Chris@16: // Extra, common functions
Chris@16: template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS>
Chris@16: inline typename BOOST_DISTRIB_CSR_GRAPH_TYPE::vertex_descriptor
Chris@16: vertex(typename BOOST_DISTRIB_CSR_GRAPH_TYPE::vertices_size_type i,
Chris@16:        const BOOST_DISTRIB_CSR_GRAPH_TYPE& g)
Chris@16: {
Chris@16:   return g.make_vertex_descriptor(g.distribution()(i), 
Chris@16:                                   g.distribution().local(i));
Chris@16: }
Chris@16: 
Chris@16: // Unlike for an adjacency_matrix, edge_range and edge take lg(out_degree(i))
Chris@16: // time
Chris@16: template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS>
Chris@16: inline std::pair<typename BOOST_DISTRIB_CSR_GRAPH_TYPE::out_edge_iterator,
Chris@16:                  typename BOOST_DISTRIB_CSR_GRAPH_TYPE::out_edge_iterator>
Chris@16: edge_range(typename BOOST_DISTRIB_CSR_GRAPH_TYPE::vertex_descriptor i,
Chris@16:            typename BOOST_DISTRIB_CSR_GRAPH_TYPE::vertex_descriptor j,
Chris@16:            const BOOST_DISTRIB_CSR_GRAPH_TYPE& g)
Chris@16: {
Chris@16:   typedef typename BOOST_DISTRIB_CSR_GRAPH_TYPE::vertex_descriptor Vertex;
Chris@16:   typedef typename BOOST_DISTRIB_CSR_GRAPH_TYPE::edges_size_type EdgeIndex;
Chris@16:   typedef typename std::vector<Vertex>::const_iterator adj_iter;
Chris@16:   typedef typename BOOST_DISTRIB_CSR_GRAPH_TYPE::out_edge_iterator out_edge_iter;
Chris@16:   typedef typename BOOST_DISTRIB_CSR_GRAPH_TYPE::edge_descriptor edge_desc;
Chris@16:   std::pair<adj_iter, adj_iter> raw_adjacencies = adjacent_vertices(i, g);
Chris@16:   std::pair<adj_iter, adj_iter> adjacencies =
Chris@16:     std::equal_range(raw_adjacencies.first, raw_adjacencies.second, j);
Chris@16:   EdgeIndex idx_begin = adjacencies.first - g.base().m_forward.m_column.begin();
Chris@16:   EdgeIndex idx_end = adjacencies.second - g.base().m_forward.m_column.begin();
Chris@16:   return std::make_pair(out_edge_iter(edge_desc(i, idx_begin)),
Chris@16:                         out_edge_iter(edge_desc(i, idx_end)));
Chris@16: }
Chris@16: 
Chris@16: template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS>
Chris@16: inline std::pair<typename BOOST_DISTRIB_CSR_GRAPH_TYPE::edge_descriptor, bool>
Chris@16: edge(typename BOOST_DISTRIB_CSR_GRAPH_TYPE::vertex_descriptor i,
Chris@16:      typename BOOST_DISTRIB_CSR_GRAPH_TYPE::vertex_descriptor j,
Chris@16:      const BOOST_DISTRIB_CSR_GRAPH_TYPE& g)
Chris@16: {
Chris@16:   typedef typename BOOST_DISTRIB_CSR_GRAPH_TYPE::out_edge_iterator out_edge_iter;
Chris@16:   std::pair<out_edge_iter, out_edge_iter> range = edge_range(i, j, g);
Chris@16:   if (range.first == range.second)
Chris@16:     return std::make_pair(typename BOOST_DISTRIB_CSR_GRAPH_TYPE::edge_descriptor(),
Chris@16:                           false);
Chris@16:   else
Chris@16:     return std::make_pair(*range.first, true);
Chris@16: }
Chris@16: 
Chris@16: // A helper that turns requests for property maps for const graphs
Chris@16: // into property maps for non-const graphs.
Chris@16: template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS, typename Property>
Chris@16: class property_map<const BOOST_DISTRIB_CSR_GRAPH_TYPE, Property>
Chris@16: {
Chris@16:  public:
Chris@16:   typedef typename property_map<BOOST_DISTRIB_CSR_GRAPH_TYPE, Property>
Chris@16:     ::const_type type;
Chris@16:   typedef type const_type;
Chris@16: };
Chris@16: 
Chris@16: // -----------------------------------------------------------------
Chris@16: // Structural modifiers
Chris@16: 
Chris@16: #if 0
Chris@16: template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS>
Chris@16: typename BOOST_DISTRIB_CSR_GRAPH_TYPE::vertex_descriptor
Chris@16: add_vertex(BOOST_DISTRIB_CSR_GRAPH_TYPE& g)
Chris@16: { return g.add_vertex(); }
Chris@16: 
Chris@16: template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS>
Chris@16: typename BOOST_DISTRIB_CSR_GRAPH_TYPE::vertex_descriptor
Chris@16: add_vertex(const typename BOOST_DISTRIB_CSR_GRAPH_TYPE::vertex_bundled& p, 
Chris@16:            BOOST_DISTRIB_CSR_GRAPH_TYPE& g)
Chris@16: { return g.add_vertex(p); }
Chris@16: 
Chris@16: template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS>
Chris@16: typename BOOST_DISTRIB_CSR_GRAPH_TYPE::vertex_descriptor
Chris@16: add_vertices(typename BOOST_DISTRIB_CSR_GRAPH_TYPE::vertices_size_type count, 
Chris@16:              BOOST_DISTRIB_CSR_GRAPH_TYPE& g)
Chris@16: { return g.add_vertices(count); }
Chris@16: 
Chris@16: template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS, typename InputIterator>
Chris@16: void 
Chris@16: add_edges(InputIterator first, InputIterator last,
Chris@16:           BOOST_DISTRIB_CSR_GRAPH_TYPE& g)
Chris@16: { g.add_edges(first, last); }
Chris@16: 
Chris@16: template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS, typename InputIterator, 
Chris@16:          typename EdgePropertyIterator>
Chris@16: void 
Chris@16: add_edges(InputIterator first, InputIterator last,
Chris@16:           EdgePropertyIterator ep_iter,
Chris@16:           EdgePropertyIterator ep_iter_end,
Chris@16:           BOOST_DISTRIB_CSR_GRAPH_TYPE& g)
Chris@16: { return g.add_edges(first, last, ep_iter, ep_iter_end); }
Chris@16: 
Chris@16: template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS, typename InputIterator>
Chris@16: void 
Chris@16: add_edges_sorted(InputIterator first, InputIterator last,
Chris@16:                  BOOST_DISTRIB_CSR_GRAPH_TYPE& g)
Chris@16: { return g.add_edges_sorted(first, last); }
Chris@16: 
Chris@16: template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS, typename InputIterator, 
Chris@16:          typename EdgePropertyIterator>
Chris@16: void 
Chris@16: add_edges_sorted(InputIterator first_sorted, InputIterator last_sorted,
Chris@16:                  EdgePropertyIterator ep_iter_sorted,
Chris@16:                  BOOST_DISTRIB_CSR_GRAPH_TYPE& g)
Chris@16: { g.add_edges_sorted(first_sorted, last_sorted, ep_iter_sorted); }
Chris@16: #endif
Chris@16: 
Chris@16: // -----------------------------------------------------------------
Chris@16: // Vertex Owner Property Map
Chris@16: template<typename ProcessID, typename Key>
Chris@16: class csr_vertex_owner_map
Chris@16: {
Chris@16:  public:
Chris@16:   // -----------------------------------------------------------------
Chris@16:   // Readable Property Map concept requirements
Chris@16:   typedef ProcessID value_type;
Chris@16:   typedef value_type reference;
Chris@16:   typedef Key key_type;
Chris@16:   typedef readable_property_map_tag category;
Chris@16: };
Chris@16: 
Chris@16: template<typename ProcessID, typename Key>
Chris@16: inline ProcessID
Chris@16: get(csr_vertex_owner_map<ProcessID, Key> pm,
Chris@16:     typename csr_vertex_owner_map<ProcessID, Key>::key_type k)
Chris@16: {
Chris@16:   const int local_index_bits = sizeof(Key) * CHAR_BIT - processor_bits;
Chris@16:   return k >> local_index_bits;
Chris@16: }
Chris@16: 
Chris@16: template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS>
Chris@16: class property_map<BOOST_DISTRIB_CSR_GRAPH_TYPE, vertex_owner_t>
Chris@16: {
Chris@16:  public:
Chris@16:   typedef csr_vertex_owner_map<
Chris@16:             typename ProcessGroup::process_id_type,
Chris@16:             typename BOOST_DISTRIB_CSR_GRAPH_TYPE::vertex_descriptor> type;
Chris@16:   typedef type const_type;
Chris@16: };
Chris@16: 
Chris@16: template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS>
Chris@16: inline
Chris@16: typename property_map<BOOST_DISTRIB_CSR_GRAPH_TYPE, vertex_owner_t>::type
Chris@16: get(vertex_owner_t, BOOST_DISTRIB_CSR_GRAPH_TYPE& g)
Chris@16: {
Chris@16:   typedef typename property_map<BOOST_DISTRIB_CSR_GRAPH_TYPE, vertex_owner_t>
Chris@16:     ::type result_type;
Chris@16:   return result_type();
Chris@16: }
Chris@16: 
Chris@16: template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS>
Chris@16: inline typename ProcessGroup::process_id_type
Chris@16: get(vertex_owner_t, BOOST_DISTRIB_CSR_GRAPH_TYPE& g,
Chris@16:     typename BOOST_DISTRIB_CSR_GRAPH_TYPE::vertex_descriptor k)
Chris@16: {
Chris@16:   return get(vertex_owner, 
Chris@16:              const_cast<const BOOST_DISTRIB_CSR_GRAPH_TYPE&>(g),
Chris@16:              k);
Chris@16: }
Chris@16: 
Chris@16: template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS>
Chris@16: inline
Chris@16: typename property_map<BOOST_DISTRIB_CSR_GRAPH_TYPE, vertex_owner_t>::const_type
Chris@16: get(vertex_owner_t, const BOOST_DISTRIB_CSR_GRAPH_TYPE& g)
Chris@16: {
Chris@16:   typedef typename property_map<BOOST_DISTRIB_CSR_GRAPH_TYPE, vertex_owner_t>
Chris@16:     ::const_type result_type;
Chris@16:   return result_type();
Chris@16: }
Chris@16: 
Chris@16: template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS>
Chris@16: inline typename ProcessGroup::process_id_type
Chris@16: get(vertex_owner_t, const BOOST_DISTRIB_CSR_GRAPH_TYPE& g,
Chris@16:     typename BOOST_DISTRIB_CSR_GRAPH_TYPE::vertex_descriptor k)
Chris@16: {
Chris@16:   typedef typename BOOST_DISTRIB_CSR_GRAPH_TYPE::vertex_descriptor
Chris@16:     vertex_descriptor;
Chris@16:   const int local_index_bits = 
Chris@16:     sizeof(vertex_descriptor) * CHAR_BIT - processor_bits;
Chris@16:   return k >> local_index_bits;
Chris@16: }
Chris@16: 
Chris@16: // -----------------------------------------------------------------
Chris@16: // Vertex Local Property Map
Chris@16: template<typename Key>
Chris@16: class csr_vertex_local_map
Chris@16: {
Chris@16:  public:
Chris@16:   // -----------------------------------------------------------------
Chris@16:   // Readable Property Map concept requirements
Chris@16:   typedef Key value_type;
Chris@16:   typedef value_type reference;
Chris@16:   typedef Key key_type;
Chris@16:   typedef readable_property_map_tag category;
Chris@16: };
Chris@16: 
Chris@16: template<typename Key>
Chris@16: inline Key
Chris@16: get(csr_vertex_local_map<Key> pm,
Chris@16:     typename csr_vertex_local_map<Key>::key_type k)
Chris@16: {
Chris@16:   const Key local_index_mask = Key(-1) >> processor_bits;
Chris@16:   return k & local_index_mask;
Chris@16: }
Chris@16: 
Chris@16: template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS>
Chris@16: class property_map<BOOST_DISTRIB_CSR_GRAPH_TYPE, vertex_local_t>
Chris@16: {
Chris@16:  public:
Chris@16:   typedef csr_vertex_local_map<
Chris@16:             typename BOOST_DISTRIB_CSR_GRAPH_TYPE::vertex_descriptor> type;
Chris@16:   typedef type const_type;
Chris@16: };
Chris@16: 
Chris@16: template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS>
Chris@16: inline
Chris@16: typename property_map<BOOST_DISTRIB_CSR_GRAPH_TYPE, vertex_local_t>::type
Chris@16: get(vertex_local_t, BOOST_DISTRIB_CSR_GRAPH_TYPE& g)
Chris@16: {
Chris@16:   typedef typename property_map<BOOST_DISTRIB_CSR_GRAPH_TYPE, vertex_local_t>
Chris@16:     ::type result_type;
Chris@16:   return result_type();
Chris@16: }
Chris@16: 
Chris@16: template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS>
Chris@16: inline typename BOOST_DISTRIB_CSR_GRAPH_TYPE::vertex_descriptor
Chris@16: get(vertex_local_t, BOOST_DISTRIB_CSR_GRAPH_TYPE& g,
Chris@16:     typename BOOST_DISTRIB_CSR_GRAPH_TYPE::vertex_descriptor k)
Chris@16: {
Chris@16:   return get(vertex_local, 
Chris@16:              const_cast<const BOOST_DISTRIB_CSR_GRAPH_TYPE&>(g),
Chris@16:              k);
Chris@16: }
Chris@16: 
Chris@16: template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS>
Chris@16: inline
Chris@16: typename property_map<BOOST_DISTRIB_CSR_GRAPH_TYPE, vertex_local_t>::const_type
Chris@16: get(vertex_local_t, const BOOST_DISTRIB_CSR_GRAPH_TYPE& g)
Chris@16: {
Chris@16:   typedef typename property_map<BOOST_DISTRIB_CSR_GRAPH_TYPE, vertex_local_t>
Chris@16:     ::const_type result_type;
Chris@16:   return result_type();
Chris@16: }
Chris@16: 
Chris@16: template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS>
Chris@16: inline typename BOOST_DISTRIB_CSR_GRAPH_TYPE::vertex_descriptor
Chris@16: get(vertex_local_t, const BOOST_DISTRIB_CSR_GRAPH_TYPE& g,
Chris@16:     typename BOOST_DISTRIB_CSR_GRAPH_TYPE::vertex_descriptor k)
Chris@16: {
Chris@16:   typedef typename BOOST_DISTRIB_CSR_GRAPH_TYPE::vertex_descriptor 
Chris@16:     vertex_descriptor;
Chris@16:   const vertex_descriptor local_index_mask = 
Chris@16:     vertex_descriptor(-1) >> processor_bits;
Chris@16:   return k & local_index_mask;
Chris@16: }
Chris@16: 
Chris@16: // -----------------------------------------------------------------
Chris@16: // Vertex Index Property Map
Chris@16: template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS>
Chris@16: class property_map<BOOST_DISTRIB_CSR_GRAPH_TYPE, vertex_index_t>
Chris@16: {
Chris@16:   typedef typename property_map<BOOST_DISTRIB_CSR_GRAPH_TYPE, 
Chris@16:                                 vertex_global_t>::const_type
Chris@16:     global_map;
Chris@16:   typedef typename BOOST_DISTRIB_CSR_GRAPH_TYPE::process_group_type
Chris@16:     process_group_type;
Chris@16: 
Chris@16:   typedef property_map<BOOST_DISTRIB_CSR_GRAPH_TYPE, vertex_local_t> local;
Chris@16: 
Chris@16: public:
Chris@16:   typedef local_property_map<process_group_type, 
Chris@16:                              global_map, 
Chris@16:                              typename local::type> type;
Chris@16:   typedef local_property_map<process_group_type, 
Chris@16:                              global_map, 
Chris@16:                              typename local::const_type> const_type;
Chris@16: };
Chris@16: 
Chris@16: template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS>
Chris@16: inline
Chris@16: typename property_map<BOOST_DISTRIB_CSR_GRAPH_TYPE, vertex_index_t>::type
Chris@16: get(vertex_index_t, BOOST_DISTRIB_CSR_GRAPH_TYPE& g)
Chris@16: {
Chris@16:   typedef typename property_map<BOOST_DISTRIB_CSR_GRAPH_TYPE, vertex_index_t>
Chris@16:     ::type result_type;
Chris@16: 
Chris@16:   return result_type(g.process_group(), get(vertex_global, g),
Chris@16:                      get(vertex_local, g));
Chris@16: }
Chris@16: 
Chris@16: template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS>
Chris@16: inline typename BOOST_DISTRIB_CSR_GRAPH_TYPE::vertices_size_type
Chris@16: get(vertex_index_t, BOOST_DISTRIB_CSR_GRAPH_TYPE& g,
Chris@16:     typename BOOST_DISTRIB_CSR_GRAPH_TYPE::vertex_descriptor k)
Chris@16: {
Chris@16:   return get(vertex_local, g, k);
Chris@16: }
Chris@16: 
Chris@16: template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS>
Chris@16: inline
Chris@16: typename property_map<BOOST_DISTRIB_CSR_GRAPH_TYPE, vertex_index_t>::const_type
Chris@16: get(vertex_index_t, const BOOST_DISTRIB_CSR_GRAPH_TYPE& g)
Chris@16: {
Chris@16:   typedef typename property_map<BOOST_DISTRIB_CSR_GRAPH_TYPE, vertex_index_t>
Chris@16:     ::const_type result_type;
Chris@16:   return result_type(g.process_group(), get(vertex_global, g),
Chris@16:                      get(vertex_local, g));
Chris@16: }
Chris@16: 
Chris@16: template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS>
Chris@16: inline typename BOOST_DISTRIB_CSR_GRAPH_TYPE::vertices_size_type
Chris@16: get(vertex_index_t, const BOOST_DISTRIB_CSR_GRAPH_TYPE& g,
Chris@16:     typename BOOST_DISTRIB_CSR_GRAPH_TYPE::vertex_descriptor k)
Chris@16: {
Chris@16:   return get(vertex_local, g, k);
Chris@16: }
Chris@16: 
Chris@16: // -----------------------------------------------------------------
Chris@16: // Vertex Local Index Property Map
Chris@16: template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS>
Chris@16: class property_map<BOOST_DISTRIB_CSR_GRAPH_TYPE, vertex_local_index_t>
Chris@16:   : public property_map<BOOST_DISTRIB_CSR_GRAPH_TYPE, vertex_local_t> { };
Chris@16: 
Chris@16: template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS>
Chris@16: inline
Chris@16: typename property_map<BOOST_DISTRIB_CSR_GRAPH_TYPE, vertex_local_index_t>::type
Chris@16: get(vertex_local_index_t, BOOST_DISTRIB_CSR_GRAPH_TYPE& g)
Chris@16: {
Chris@16:   return get(vertex_local, g);
Chris@16: }
Chris@16: 
Chris@16: template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS>
Chris@16: inline typename BOOST_DISTRIB_CSR_GRAPH_TYPE::vertices_size_type
Chris@16: get(vertex_local_index_t, BOOST_DISTRIB_CSR_GRAPH_TYPE& g,
Chris@16:     typename BOOST_DISTRIB_CSR_GRAPH_TYPE::vertex_descriptor k)
Chris@16: {
Chris@16:   return get(vertex_local, g, k);
Chris@16: }
Chris@16: 
Chris@16: template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS>
Chris@16: inline
Chris@16: typename property_map<BOOST_DISTRIB_CSR_GRAPH_TYPE, vertex_local_index_t>::const_type
Chris@16: get(vertex_local_index_t, const BOOST_DISTRIB_CSR_GRAPH_TYPE& g)
Chris@16: {
Chris@16:   return get(vertex_local, g);
Chris@16: }
Chris@16: 
Chris@16: template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS>
Chris@16: inline typename BOOST_DISTRIB_CSR_GRAPH_TYPE::vertices_size_type
Chris@16: get(vertex_local_index_t, const BOOST_DISTRIB_CSR_GRAPH_TYPE& g,
Chris@16:     typename BOOST_DISTRIB_CSR_GRAPH_TYPE::vertex_descriptor k)
Chris@16: {
Chris@16:   return get(vertex_local, g, k);
Chris@16: }
Chris@16: 
Chris@16: // -----------------------------------------------------------------
Chris@16: // Edge Global Property Map
Chris@16: template<typename ProcessID, typename Vertex, typename EdgeIndex>
Chris@16: class csr_edge_global_map
Chris@16: {
Chris@16:  public:
Chris@16:   // -----------------------------------------------------------------
Chris@16:   // Readable Property Map concept requirements
Chris@16:   typedef detail::csr_edge_descriptor<Vertex, EdgeIndex> key_type;
Chris@16:   typedef std::pair<ProcessID, detail::csr_edge_descriptor<Vertex, EdgeIndex> > value_type;
Chris@16:   typedef value_type reference;
Chris@16:   typedef readable_property_map_tag category;
Chris@16: };
Chris@16: 
Chris@16: template<typename ProcessID, typename Vertex, typename EdgeIndex>
Chris@16: inline std::pair<ProcessID, detail::csr_edge_descriptor<Vertex, EdgeIndex> >
Chris@16: get(csr_edge_global_map<ProcessID, Vertex, EdgeIndex> pm,
Chris@16:     typename csr_edge_global_map<ProcessID, Vertex, EdgeIndex>::key_type k)
Chris@16: {
Chris@16:   const int local_index_bits = sizeof(Vertex) * CHAR_BIT - processor_bits;
Chris@16:   const Vertex local_index_mask = Vertex(-1) >> processor_bits;
Chris@16:   return std::pair<ProcessID, detail::csr_edge_descriptor<Vertex, EdgeIndex> >
Chris@16:            ((k.src >> local_index_bits),
Chris@16:             detail::csr_edge_descriptor<Vertex, EdgeIndex>(k.src & local_index_mask, k.idx));
Chris@16: }
Chris@16: 
Chris@16: template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS>
Chris@16: class property_map<BOOST_DISTRIB_CSR_GRAPH_TYPE, edge_global_t>
Chris@16: {
Chris@16:  public:
Chris@16:   typedef csr_edge_global_map<
Chris@16:             typename ProcessGroup::process_id_type,
Chris@16:             typename BOOST_DISTRIB_CSR_GRAPH_TYPE::vertex_descriptor,
Chris@16:             typename BOOST_DISTRIB_CSR_GRAPH_TYPE::edges_size_type> type;
Chris@16:   typedef type const_type;
Chris@16: };
Chris@16: 
Chris@16: template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS>
Chris@16: inline
Chris@16: typename property_map<BOOST_DISTRIB_CSR_GRAPH_TYPE, edge_global_t>::type
Chris@16: get(edge_global_t, BOOST_DISTRIB_CSR_GRAPH_TYPE& g)
Chris@16: {
Chris@16:   typedef typename property_map<BOOST_DISTRIB_CSR_GRAPH_TYPE, edge_global_t>
Chris@16:     ::type result_type;
Chris@16:   return result_type();
Chris@16: }
Chris@16: 
Chris@16: template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS>
Chris@16: inline
Chris@16: std::pair<typename ProcessGroup::process_id_type,
Chris@16:           typename BOOST_DISTRIB_CSR_GRAPH_TYPE::base_type::edge_descriptor>
Chris@16: get(edge_global_t, BOOST_DISTRIB_CSR_GRAPH_TYPE& g,
Chris@16:     typename BOOST_DISTRIB_CSR_GRAPH_TYPE::edge_descriptor k)
Chris@16: {
Chris@16:   return get(edge_global, 
Chris@16:              const_cast<const BOOST_DISTRIB_CSR_GRAPH_TYPE&>(g),
Chris@16:              k);
Chris@16: }
Chris@16: 
Chris@16: template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS>
Chris@16: inline
Chris@16: typename property_map<BOOST_DISTRIB_CSR_GRAPH_TYPE, edge_global_t>::const_type
Chris@16: get(edge_global_t, const BOOST_DISTRIB_CSR_GRAPH_TYPE& g)
Chris@16: {
Chris@16:   typedef typename property_map<BOOST_DISTRIB_CSR_GRAPH_TYPE, edge_global_t>
Chris@16:     ::const_type result_type;
Chris@16:   return result_type();
Chris@16: }
Chris@16: 
Chris@16: template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS>
Chris@16: inline
Chris@16: std::pair<typename ProcessGroup::process_id_type,
Chris@16:           typename BOOST_DISTRIB_CSR_GRAPH_TYPE::base_type::edge_descriptor>
Chris@16: get(edge_global_t, const BOOST_DISTRIB_CSR_GRAPH_TYPE& g,
Chris@16:     typename BOOST_DISTRIB_CSR_GRAPH_TYPE::edge_descriptor k)
Chris@16: {
Chris@16:   typedef typename BOOST_DISTRIB_CSR_GRAPH_TYPE::vertex_descriptor
Chris@16:     vertex_descriptor;
Chris@16: 
Chris@16:   const int local_index_bits = 
Chris@16:     sizeof(vertex_descriptor) * CHAR_BIT - processor_bits;
Chris@16:   const typename BOOST_DISTRIB_CSR_GRAPH_TYPE::edges_size_type local_index_mask =
Chris@16:     typename BOOST_DISTRIB_CSR_GRAPH_TYPE::edges_size_type(-1) >> processor_bits;
Chris@16:   
Chris@16:   typedef std::pair<typename ProcessGroup::process_id_type,
Chris@16:                     typename BOOST_DISTRIB_CSR_GRAPH_TYPE::base_type::edge_descriptor>
Chris@16:     result_type;
Chris@16: 
Chris@16:   return result_type(k.src >> local_index_bits,
Chris@16:                      typename BOOST_DISTRIB_CSR_GRAPH_TYPE::base_type::edge_descriptor
Chris@16:                        (k.src & local_index_mask, k.idx));
Chris@16: }
Chris@16: 
Chris@16: // -----------------------------------------------------------------
Chris@16: // Edge Index Property Map
Chris@16: template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS>
Chris@16: class property_map<BOOST_DISTRIB_CSR_GRAPH_TYPE, edge_index_t>
Chris@16: {
Chris@16:    typedef typename property_map<BOOST_DISTRIB_CSR_GRAPH_TYPE, edge_global_t>
Chris@16:     ::type global_map;
Chris@16: 
Chris@16:  public:
Chris@16:   typedef local_property_map<
Chris@16:             typename BOOST_DISTRIB_CSR_GRAPH_TYPE::process_group_type,
Chris@16:             global_map,
Chris@16:             typename property_map<typename BOOST_DISTRIB_CSR_GRAPH_TYPE::base_type, edge_index_t>::type
Chris@16:           > type;
Chris@16:   typedef type const_type;
Chris@16: };
Chris@16: 
Chris@16: template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS>
Chris@16: inline
Chris@16: typename property_map<BOOST_DISTRIB_CSR_GRAPH_TYPE, edge_index_t>::type
Chris@16: get(edge_index_t, BOOST_DISTRIB_CSR_GRAPH_TYPE& g)
Chris@16: {
Chris@16:   typedef typename property_map<BOOST_DISTRIB_CSR_GRAPH_TYPE, edge_index_t>
Chris@16:     ::type result_type;
Chris@16:   return result_type(g.process_group(), get(edge_global, g),
Chris@16:                      get(edge_index, g.base()));
Chris@16: }
Chris@16: 
Chris@16: template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS>
Chris@16: inline typename BOOST_DISTRIB_CSR_GRAPH_TYPE::edges_size_type
Chris@16: get(edge_index_t, BOOST_DISTRIB_CSR_GRAPH_TYPE& g,
Chris@16:     typename BOOST_DISTRIB_CSR_GRAPH_TYPE::edge_descriptor k)
Chris@16: {
Chris@16:   return k.idx;
Chris@16: }
Chris@16: 
Chris@16: template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS>
Chris@16: inline
Chris@16: typename property_map<BOOST_DISTRIB_CSR_GRAPH_TYPE, edge_index_t>::const_type
Chris@16: get(edge_index_t, const BOOST_DISTRIB_CSR_GRAPH_TYPE& g)
Chris@16: {
Chris@16:   typedef typename property_map<BOOST_DISTRIB_CSR_GRAPH_TYPE, edge_index_t>
Chris@16:     ::const_type result_type;
Chris@16:   return result_type(g.process_group(), get(edge_global, g),
Chris@16:                      get(edge_index, g.base()));
Chris@16: }
Chris@16: 
Chris@16: template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS>
Chris@16: inline typename BOOST_DISTRIB_CSR_GRAPH_TYPE::edges_size_type
Chris@16: get(edge_index_t, const BOOST_DISTRIB_CSR_GRAPH_TYPE& g,
Chris@16:     typename BOOST_DISTRIB_CSR_GRAPH_TYPE::edge_descriptor k)
Chris@16: {
Chris@16:   return k.idx;
Chris@16: }
Chris@16: 
Chris@16: template <BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS, typename Tag>
Chris@16: class property_map<BOOST_DISTRIB_CSR_GRAPH_TYPE, Tag> {
Chris@16:   typedef BOOST_DISTRIB_CSR_GRAPH_TYPE graph_type;
Chris@16:   typedef typename graph_type::process_group_type process_group_type;
Chris@16:   typedef typename graph_type::base_type base_graph_type;
Chris@16:   typedef typename property_map<base_graph_type, Tag>::type
Chris@16:     local_pmap;
Chris@16:   typedef typename property_map<base_graph_type, Tag>::const_type
Chris@16:     local_const_pmap;
Chris@16: 
Chris@16:   typedef graph_traits<graph_type> traits;
Chris@16:   typedef typename graph_traits<base_graph_type>::vertex_descriptor local_vertex;
Chris@16:   typedef typename property_traits<local_pmap>::key_type local_key_type;
Chris@16: 
Chris@16:   typedef typename property_traits<local_pmap>::value_type value_type;
Chris@16: 
Chris@16:   typedef typename property_map<graph_type, vertex_global_t>::const_type
Chris@16:     vertex_global_map;
Chris@16:   typedef typename property_map<graph_type, edge_global_t>::const_type
Chris@16:     edge_global_map;
Chris@16: 
Chris@16:   typedef typename mpl::if_<is_same<typename detail::property_kind_from_graph<base_graph_type, Tag>::type,
Chris@16:                                     vertex_property_tag>,
Chris@16:                             vertex_global_map, edge_global_map>::type
Chris@16:     global_map;
Chris@16: 
Chris@16: public:
Chris@16:   typedef ::boost::parallel::distributed_property_map<
Chris@16:             process_group_type, global_map, local_pmap> type;
Chris@16: 
Chris@16:   typedef ::boost::parallel::distributed_property_map<
Chris@16:             process_group_type, global_map, local_const_pmap> const_type;
Chris@16: };
Chris@16: 
Chris@16: template <BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS, typename Tag>
Chris@16: typename property_map<BOOST_DISTRIB_CSR_GRAPH_TYPE, Tag>::type
Chris@16: get(Tag tag, BOOST_DISTRIB_CSR_GRAPH_TYPE& g)
Chris@16: {
Chris@16:   typedef BOOST_DISTRIB_CSR_GRAPH_TYPE Graph;
Chris@16:   typedef typename property_map<Graph, Tag>::type result_type;
Chris@16:   typedef typename property_traits<result_type>::value_type value_type;
Chris@16:   typedef typename property_reduce<Tag>::template apply<value_type>
Chris@16:     reduce;
Chris@16: 
Chris@16:   typedef typename mpl::if_<is_same<typename detail::property_kind_from_graph<Graph, Tag>::type,
Chris@16:                                     vertex_property_tag>,
Chris@16:                             vertex_global_t, edge_global_t>::type
Chris@16:     global_map_t;
Chris@16: 
Chris@16:   return result_type(g.process_group(), get(global_map_t(), g),
Chris@16:                      get(tag, g.base()), reduce());
Chris@16: }
Chris@16: 
Chris@16: template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS, typename Tag>
Chris@16: typename property_map<BOOST_DISTRIB_CSR_GRAPH_TYPE, Tag>::const_type
Chris@16: get(Tag tag, const BOOST_DISTRIB_CSR_GRAPH_TYPE& g)
Chris@16: {
Chris@16:   typedef BOOST_DISTRIB_CSR_GRAPH_TYPE Graph;
Chris@16:   typedef typename property_map<Graph, Tag>::const_type result_type;
Chris@16:   typedef typename property_traits<result_type>::value_type value_type;
Chris@16:   typedef typename property_reduce<Tag>::template apply<value_type>
Chris@16:     reduce;
Chris@16: 
Chris@16:   typedef typename property_traits<result_type>::key_type descriptor;
Chris@16:   typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor;
Chris@16:   typedef typename mpl::if_<is_same<descriptor, vertex_descriptor>,
Chris@16:                             vertex_global_t, edge_global_t>::type
Chris@16:     global_map_t;
Chris@16: 
Chris@16:   return result_type(g.process_group(), get(global_map_t(), g),
Chris@16:                      get(tag, g.base()), reduce());
Chris@16: }
Chris@16: 
Chris@16: namespace mpi {
Chris@16:   template<typename Vertex, typename EdgeIndex>
Chris@16:   struct is_mpi_datatype<boost::detail::csr_edge_descriptor<Vertex, EdgeIndex> >
Chris@16:     : mpl::true_ { };
Chris@16: }
Chris@16: 
Chris@16: namespace serialization {
Chris@16:   template<typename Vertex, typename EdgeIndex>
Chris@16:   struct is_bitwise_serializable<boost::detail::csr_edge_descriptor<Vertex, EdgeIndex> >
Chris@16:     : mpl::true_ { };
Chris@16: 
Chris@16:   template<typename Vertex, typename EdgeIndex>
Chris@16:   struct implementation_level<boost::detail::csr_edge_descriptor<Vertex, EdgeIndex> >
Chris@16:    : mpl::int_<object_serializable> {} ;
Chris@16: 
Chris@16:   template<typename Vertex, typename EdgeIndex>
Chris@16:   struct tracking_level<boost::detail::csr_edge_descriptor<Vertex, EdgeIndex> >
Chris@16:    : mpl::int_<track_never> {} ;
Chris@16: 
Chris@16: }
Chris@16: 
Chris@16: } // end namespace boost
Chris@16: 
Chris@16: #endif // BOOST_GRAPH_DISTRIBUTED_CSR_HPP