Chris@16: // Copyright 2005-2009 The Trustees of Indiana University.
Chris@16: 
Chris@16: // Distributed under the Boost Software License, Version 1.0.
Chris@16: // (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: Jeremiah Willcock
Chris@16: //           Douglas Gregor
Chris@16: //           Andrew Lumsdaine
Chris@16: 
Chris@16: // Compressed sparse row graph type
Chris@16: 
Chris@16: #ifndef BOOST_GRAPH_COMPRESSED_SPARSE_ROW_GRAPH_HPP
Chris@16: #define BOOST_GRAPH_COMPRESSED_SPARSE_ROW_GRAPH_HPP
Chris@16: 
Chris@16: #include <vector>
Chris@16: #include <utility>
Chris@16: #include <algorithm>
Chris@16: #include <climits>
Chris@16: #include <boost/assert.hpp>
Chris@16: #include <iterator>
Chris@16: #if 0
Chris@16: #include <iostream> // For some debugging code below
Chris@16: #endif
Chris@16: #include <boost/graph/graph_traits.hpp>
Chris@16: #include <boost/graph/properties.hpp>
Chris@16: #include <boost/graph/filtered_graph.hpp> // For keep_all
Chris@16: #include <boost/graph/detail/indexed_properties.hpp>
Chris@16: #include <boost/graph/detail/compressed_sparse_row_struct.hpp>
Chris@16: #include <boost/graph/iteration_macros.hpp>
Chris@16: #include <boost/iterator/counting_iterator.hpp>
Chris@16: #include <boost/iterator/reverse_iterator.hpp>
Chris@16: #include <boost/iterator/zip_iterator.hpp>
Chris@16: #include <boost/iterator/transform_iterator.hpp>
Chris@16: #include <boost/tuple/tuple.hpp>
Chris@16: #include <boost/property_map/property_map.hpp>
Chris@16: #include <boost/integer.hpp>
Chris@16: #include <boost/iterator/iterator_facade.hpp>
Chris@16: #include <boost/mpl/if.hpp>
Chris@16: #include <boost/utility/enable_if.hpp>
Chris@16: #include <boost/graph/graph_selectors.hpp>
Chris@16: #include <boost/graph/detail/is_distributed_selector.hpp>
Chris@16: #include <boost/graph/properties.hpp>
Chris@16: #include <boost/static_assert.hpp>
Chris@16: #include <boost/functional/hash.hpp>
Chris@16: #include <boost/next_prior.hpp>
Chris@16: #include <boost/property_map/transform_value_property_map.hpp>
Chris@16: #include <boost/mpl/print.hpp>
Chris@16: 
Chris@16: namespace boost {
Chris@16: 
Chris@16: // A tag type indicating that the graph in question is a compressed
Chris@16: // sparse row graph. This is an internal detail of the BGL.
Chris@16: struct csr_graph_tag;
Chris@16: 
Chris@16: // A type (edges_are_sorted_t) and a value (edges_are_sorted) used to indicate
Chris@16: // that the edge list passed into the CSR graph is already sorted by source
Chris@16: // vertex.
Chris@16: enum edges_are_sorted_t {edges_are_sorted};
Chris@16: 
Chris@16: // A type (edges_are_sorted_global_t) and a value (edges_are_sorted_global)
Chris@16: // used to indicate that the edge list passed into the CSR graph is already
Chris@16: // sorted by source vertex.
Chris@16: enum edges_are_sorted_global_t {edges_are_sorted_global};
Chris@16: 
Chris@16: // A type (edges_are_unsorted_t) and a value (edges_are_unsorted) used to
Chris@16: // indicate that the edge list passed into the CSR graph is not sorted by
Chris@16: // source vertex.  This version caches the edge information in memory, and thus
Chris@16: // requires only a single pass over the input data.
Chris@16: enum edges_are_unsorted_t {edges_are_unsorted};
Chris@16: 
Chris@16: // A type (edges_are_unsorted_multi_pass_t) and a value
Chris@16: // (edges_are_unsorted_multi_pass) used to indicate that the edge list passed
Chris@16: // into the CSR graph is not sorted by source vertex.  This version uses less
Chris@16: // memory but requires multi-pass capability on the iterators.
Chris@16: enum edges_are_unsorted_multi_pass_t {edges_are_unsorted_multi_pass};
Chris@16: 
Chris@16: // A type (edges_are_unsorted_multi_pass_global_t) and a value
Chris@16: // (edges_are_unsorted_multi_pass_global) used to indicate that the edge list
Chris@16: // passed into the CSR graph is not sorted by source vertex.  This version uses
Chris@16: // less memory but requires multi-pass capability on the iterators.  The
Chris@16: // global mapping and filtering is done here because it is often faster and it
Chris@16: // greatly simplifies handling of edge properties.
Chris@16: enum edges_are_unsorted_multi_pass_global_t {edges_are_unsorted_multi_pass_global};
Chris@16: 
Chris@16: // A type (construct_inplace_from_sources_and_targets_t) and a value
Chris@16: // (construct_inplace_from_sources_and_targets) used to indicate that mutable
Chris@16: // vectors of sources and targets (and possibly edge properties) are being used
Chris@16: // to construct the CSR graph.  These vectors are sorted in-place and then the
Chris@16: // targets and properties are swapped into the graph data structure.
Chris@16: enum construct_inplace_from_sources_and_targets_t {construct_inplace_from_sources_and_targets};
Chris@16: 
Chris@16: // A type (construct_inplace_from_sources_and_targets_global_t) and a value
Chris@16: // (construct_inplace_from_sources_and_targets_global) used to indicate that
Chris@16: // mutable vectors of sources and targets (and possibly edge properties) are
Chris@16: // being used to construct the CSR graph.  These vectors are sorted in-place
Chris@16: // and then the targets and properties are swapped into the graph data
Chris@16: // structure.  It is assumed that global indices (for distributed CSR) are
Chris@16: // used, and a map is required to convert those to local indices.  This
Chris@16: // constructor is intended for internal use by the various CSR graphs
Chris@16: // (sequential and distributed).
Chris@16: enum construct_inplace_from_sources_and_targets_global_t {construct_inplace_from_sources_and_targets_global};
Chris@16: 
Chris@16: // A type (edges_are_unsorted_global_t) and a value (edges_are_unsorted_global)
Chris@16: // used to indicate that the edge list passed into the CSR graph is not sorted
Chris@16: // by source vertex.  The data is also stored using global vertex indices, and
Chris@16: // must be filtered to choose only local vertices.  This constructor caches the
Chris@16: // edge information in memory, and thus requires only a single pass over the
Chris@16: // input data.  This constructor is intended for internal use by the
Chris@16: // distributed CSR constructors.
Chris@16: enum edges_are_unsorted_global_t {edges_are_unsorted_global};
Chris@16: 
Chris@16: /****************************************************************************
Chris@16:  * Local helper macros to reduce typing and clutter later on.               *
Chris@16:  ****************************************************************************/
Chris@16: #define BOOST_CSR_GRAPH_TEMPLATE_PARMS                                  \
Chris@16:   typename Directed, typename VertexProperty, typename EdgeProperty,    \
Chris@16:   typename GraphProperty, typename Vertex, typename EdgeIndex
Chris@16: #define BOOST_CSR_GRAPH_TYPE                                            \
Chris@16:    compressed_sparse_row_graph<Directed, VertexProperty, EdgeProperty,  \
Chris@16:                                GraphProperty, Vertex, EdgeIndex>
Chris@16: #define BOOST_DIR_CSR_GRAPH_TEMPLATE_PARMS                              \
Chris@16:   typename VertexProperty, typename EdgeProperty,                       \
Chris@16:   typename GraphProperty, typename Vertex, typename EdgeIndex
Chris@16: #define BOOST_DIR_CSR_GRAPH_TYPE                                        \
Chris@16:    compressed_sparse_row_graph<directedS, VertexProperty, EdgeProperty, \
Chris@16:                                GraphProperty, Vertex, EdgeIndex>
Chris@16: #define BOOST_BIDIR_CSR_GRAPH_TEMPLATE_PARMS                            \
Chris@16:   typename VertexProperty, typename EdgeProperty,                       \
Chris@16:   typename GraphProperty, typename Vertex, typename EdgeIndex
Chris@16: #define BOOST_BIDIR_CSR_GRAPH_TYPE                                      \
Chris@16:    compressed_sparse_row_graph<bidirectionalS, VertexProperty, EdgeProperty, \
Chris@16:                                GraphProperty, Vertex, EdgeIndex>
Chris@16: 
Chris@16: namespace detail {
Chris@16:   template <typename T>
Chris@16:   struct default_construct_iterator: public boost::iterator_facade<default_construct_iterator<T>, T, boost::random_access_traversal_tag, const T&> {
Chris@16:     typedef boost::iterator_facade<default_construct_iterator<T>, T, std::random_access_iterator_tag, const T&> base_type;
Chris@16:     T saved_value;
Chris@16:     const T& dereference() const {return saved_value;}
Chris@16:     bool equal(default_construct_iterator /*i*/) const {return true;}
Chris@16:     void increment() {}
Chris@16:     void decrement() {}
Chris@16:     void advance(typename base_type::difference_type) {}
Chris@16:     typename base_type::difference_type distance_to(default_construct_iterator) const {return 0;}
Chris@16:   };
Chris@16: 
Chris@16:   template <typename Less>
Chris@16:   struct compare_first {
Chris@16:     Less less;
Chris@16:     compare_first(Less less = Less()): less(less) {}
Chris@16:     template <typename Tuple>
Chris@16:     bool operator()(const Tuple& a, const Tuple& b) const {
Chris@16:       return less(a.template get<0>(), b.template get<0>());
Chris@16:     }
Chris@16:   };
Chris@16: 
Chris@16:   template <int N, typename Result>
Chris@16:   struct my_tuple_get_class {
Chris@16:     typedef const Result& result_type;
Chris@16:     template <typename Tuple>
Chris@16:     result_type operator()(const Tuple& t) const {
Chris@16:       return t.template get<N>();
Chris@16:     }
Chris@16:   };
Chris@16: }
Chris@16: 
Chris@16: /** Compressed sparse row graph.
Chris@16:  *
Chris@16:  * Vertex and EdgeIndex should be unsigned integral types and should
Chris@16:  * specialize numeric_limits.
Chris@16:  */
Chris@16: template<typename Directed = directedS,
Chris@16:          typename VertexProperty = no_property,
Chris@16:          typename EdgeProperty = no_property,
Chris@16:          typename GraphProperty = no_property,
Chris@16:          typename Vertex = std::size_t,
Chris@16:          typename EdgeIndex = Vertex>
Chris@16: class compressed_sparse_row_graph; // Not defined
Chris@16: 
Chris@16: template<typename VertexProperty,
Chris@16:          typename EdgeProperty,
Chris@16:          typename GraphProperty,
Chris@16:          typename Vertex,
Chris@16:          typename EdgeIndex>
Chris@16: class compressed_sparse_row_graph<directedS, VertexProperty, EdgeProperty, GraphProperty, Vertex, EdgeIndex>
Chris@16:    : public detail::indexed_vertex_properties<BOOST_DIR_CSR_GRAPH_TYPE,
Chris@16:                                               VertexProperty, Vertex, typed_identity_property_map<Vertex> >
Chris@16: {
Chris@16:  public:
Chris@16:   typedef detail::indexed_vertex_properties<compressed_sparse_row_graph,
Chris@16:                                             VertexProperty, Vertex, typed_identity_property_map<Vertex> >
Chris@16:     inherited_vertex_properties;
Chris@16: 
Chris@16:   // Some tests to prevent use of "void" is a property type (as was done in some test cases):
Chris@16:   BOOST_STATIC_ASSERT((!is_same<VertexProperty, void>::value));
Chris@16:   BOOST_STATIC_ASSERT((!is_same<EdgeProperty, void>::value));
Chris@16:   BOOST_STATIC_ASSERT((!is_same<GraphProperty, void>::value));
Chris@16: 
Chris@16:  public:
Chris@16:   // For Property Graph
Chris@16:   typedef GraphProperty graph_property_type;
Chris@16:   typedef typename lookup_one_property<GraphProperty, graph_bundle_t>::type graph_bundled;
Chris@16: 
Chris@16:   typedef detail::compressed_sparse_row_structure<EdgeProperty, Vertex, EdgeIndex> forward_type;
Chris@16: 
Chris@16:  public:
Chris@16:   /* At this time, the compressed sparse row graph can only be used to
Chris@16:    * create directed and bidirectional graphs. In the future,
Chris@16:    * undirected CSR graphs will also be supported.
Chris@16:    */
Chris@16:   // BOOST_STATIC_ASSERT((is_same<Directed, directedS>::value));
Chris@16: 
Chris@16:   // Concept requirements:
Chris@16:   // For Graph
Chris@16:   typedef Vertex vertex_descriptor;
Chris@16:   typedef detail::csr_edge_descriptor<Vertex, EdgeIndex> edge_descriptor;
Chris@16:   typedef directed_tag directed_category;
Chris@16:   typedef allow_parallel_edge_tag edge_parallel_category;
Chris@16: 
Chris@16:   class traversal_category: public incidence_graph_tag,
Chris@16:                             public adjacency_graph_tag,
Chris@16:                             public vertex_list_graph_tag,
Chris@16:                             public edge_list_graph_tag {};
Chris@16: 
Chris@16:   static vertex_descriptor null_vertex() { return vertex_descriptor(-1); }
Chris@16: 
Chris@16:   // For VertexListGraph
Chris@16:   typedef counting_iterator<Vertex> vertex_iterator;
Chris@16:   typedef Vertex vertices_size_type;
Chris@16: 
Chris@16:   // For EdgeListGraph
Chris@16:   typedef EdgeIndex edges_size_type;
Chris@16: 
Chris@16:   // For IncidenceGraph
Chris@16:   typedef detail::csr_out_edge_iterator<compressed_sparse_row_graph> out_edge_iterator;
Chris@16:   typedef EdgeIndex degree_size_type;
Chris@16: 
Chris@16:   // For AdjacencyGraph
Chris@16:   typedef typename std::vector<Vertex>::const_iterator adjacency_iterator;
Chris@16: 
Chris@16:   // For EdgeListGraph
Chris@16:   typedef detail::csr_edge_iterator<compressed_sparse_row_graph> edge_iterator;
Chris@16: 
Chris@16:   // For BidirectionalGraph (not implemented)
Chris@16:   typedef void in_edge_iterator;
Chris@16: 
Chris@16:   // For internal use
Chris@16:   typedef csr_graph_tag graph_tag;
Chris@16: 
Chris@16:   typedef typename forward_type::inherited_edge_properties::edge_bundled edge_bundled;
Chris@16:   typedef typename forward_type::inherited_edge_properties::edge_push_back_type edge_push_back_type;
Chris@16:   typedef typename forward_type::inherited_edge_properties::edge_property_type edge_property_type;
Chris@16: 
Chris@16:   // Constructors
Chris@16: 
Chris@16:   // Default constructor: an empty graph.
Chris@16:   compressed_sparse_row_graph(): m_property() {}
Chris@16: 
Chris@16:   //  With numverts vertices
Chris@16:   compressed_sparse_row_graph(vertices_size_type numverts)
Chris@16:     : inherited_vertex_properties(numverts), m_forward(numverts) {}
Chris@16: 
Chris@16:   //  From number of vertices and unsorted list of edges
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 GraphProperty& prop = GraphProperty())
Chris@16:     : inherited_vertex_properties(numverts), m_property(prop)
Chris@16:   {
Chris@16:     m_forward.assign_unsorted_multi_pass_edges(edge_begin, edge_end, numverts, typed_identity_property_map<vertices_size_type>(), keep_all());
Chris@16:   }
Chris@16: 
Chris@16:   //  From number of vertices and unsorted list of edges, plus edge properties
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 GraphProperty& prop = GraphProperty())
Chris@16:     : inherited_vertex_properties(numverts), m_forward(), m_property(prop)
Chris@16:   {
Chris@16:     m_forward.assign_unsorted_multi_pass_edges(edge_begin, edge_end, ep_iter, numverts, typed_identity_property_map<vertices_size_type>(), keep_all());
Chris@16:   }
Chris@16: 
Chris@16:   //  From number of vertices and unsorted list of edges, with filter and
Chris@16:   //  global-to-local map
Chris@16:   template <typename MultiPassInputIterator, typename GlobalToLocal, typename SourcePred>
Chris@16:   compressed_sparse_row_graph(edges_are_unsorted_multi_pass_global_t,
Chris@16:                               MultiPassInputIterator edge_begin,
Chris@16:                               MultiPassInputIterator edge_end,
Chris@16:                               vertices_size_type numlocalverts,
Chris@16:                               const GlobalToLocal& global_to_local,
Chris@16:                               const SourcePred& source_pred,
Chris@16:                               const GraphProperty& prop = GraphProperty())
Chris@16:     : inherited_vertex_properties(numlocalverts), m_forward(), m_property(prop)
Chris@16:   {
Chris@16:     m_forward.assign_unsorted_multi_pass_edges(edge_begin, edge_end, numlocalverts, global_to_local, source_pred);
Chris@16:   }
Chris@16: 
Chris@16:   //  From number of vertices and unsorted list of edges, plus edge properties,
Chris@16:   //  with filter and global-to-local map
Chris@16:   template <typename MultiPassInputIterator, typename EdgePropertyIterator, typename GlobalToLocal, typename SourcePred>
Chris@16:   compressed_sparse_row_graph(edges_are_unsorted_multi_pass_global_t,
Chris@16:                               MultiPassInputIterator edge_begin,
Chris@16:                               MultiPassInputIterator edge_end,
Chris@16:                               EdgePropertyIterator ep_iter,
Chris@16:                               vertices_size_type numlocalverts,
Chris@16:                               const GlobalToLocal& global_to_local,
Chris@16:                               const SourcePred& source_pred,
Chris@16:                               const GraphProperty& prop = GraphProperty())
Chris@16:     : inherited_vertex_properties(numlocalverts), m_forward(), m_property(prop)
Chris@16:   {
Chris@16:     m_forward.assign_unsorted_multi_pass_edges(edge_begin, edge_end, ep_iter, numlocalverts, global_to_local, source_pred);
Chris@16:   }
Chris@16: 
Chris@16:   //  From number of vertices and sorted list of edges (new interface)
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 GraphProperty& prop = GraphProperty())
Chris@16:     : m_property(prop)
Chris@16:   {
Chris@16:     m_forward.assign_from_sorted_edges(edge_begin, edge_end, typed_identity_property_map<vertices_size_type>(), keep_all(), numverts, numedges);
Chris@16:     inherited_vertex_properties::resize(numverts);
Chris@16:   }
Chris@16: 
Chris@16:   //  From number of vertices and sorted list of edges (new interface)
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 GraphProperty& prop = GraphProperty())
Chris@16:     : m_property(prop)
Chris@16:   {
Chris@16:     m_forward.assign_from_sorted_edges(edge_begin, edge_end, ep_iter, typed_identity_property_map<vertices_size_type>(), keep_all(), numverts, numedges);
Chris@16:     inherited_vertex_properties::resize(numverts);
Chris@16:   }
Chris@16: 
Chris@16:   //  From number of vertices and sorted list of edges, filtered and global (new interface)
Chris@16:   template<typename InputIterator, typename GlobalToLocal, typename SourcePred>
Chris@16:   compressed_sparse_row_graph(edges_are_sorted_global_t,
Chris@16:                               InputIterator edge_begin, InputIterator edge_end,
Chris@16:                               const GlobalToLocal& global_to_local,
Chris@16:                               const SourcePred& source_pred,
Chris@16:                               vertices_size_type numverts,
Chris@16:                               const GraphProperty& prop = GraphProperty())
Chris@16:     : m_property(prop)
Chris@16:   {
Chris@16:     m_forward.assign_from_sorted_edges(edge_begin, edge_end, global_to_local, source_pred, numverts, 0);
Chris@16:     inherited_vertex_properties::resize(numverts);
Chris@16:   }
Chris@16: 
Chris@16:   //  From number of vertices and sorted list of edges (new interface)
Chris@16:   template<typename InputIterator, typename EdgePropertyIterator, typename GlobalToLocal, typename SourcePred>
Chris@16:   compressed_sparse_row_graph(edges_are_sorted_global_t,
Chris@16:                               InputIterator edge_begin, InputIterator edge_end,
Chris@16:                               EdgePropertyIterator ep_iter,
Chris@16:                               const GlobalToLocal& global_to_local,
Chris@16:                               const SourcePred& source_pred,
Chris@16:                               vertices_size_type numverts,
Chris@16:                               const GraphProperty& prop = GraphProperty())
Chris@16:     : m_property(prop)
Chris@16:   {
Chris@16:     m_forward.assign_from_sorted_edges(edge_begin, edge_end, ep_iter, global_to_local, source_pred, numverts, 0);
Chris@16:     inherited_vertex_properties::resize(numverts);
Chris@16:   }
Chris@16: 
Chris@16:   //  From number of vertices and mutable vectors of sources and targets;
Chris@16:   //  vectors are returned with unspecified contents but are guaranteed not to
Chris@16:   //  share storage with the constructed graph.
Chris@16:   compressed_sparse_row_graph(construct_inplace_from_sources_and_targets_t,
Chris@16:                               std::vector<vertex_descriptor>& sources,
Chris@16:                               std::vector<vertex_descriptor>& targets,
Chris@16:                               vertices_size_type numverts,
Chris@16:                               const GraphProperty& prop = GraphProperty())
Chris@16:     : inherited_vertex_properties(numverts), m_property(prop)
Chris@16:   {
Chris@16:     m_forward.assign_sources_and_targets_global(sources, targets, numverts, boost::typed_identity_property_map<vertices_size_type>());
Chris@16:   }
Chris@16: 
Chris@16:   //  From number of vertices and mutable vectors of sources and targets,
Chris@16:   //  expressed with global vertex indices; vectors are returned with
Chris@16:   //  unspecified contents but are guaranteed not to share storage with the
Chris@16:   //  constructed graph.  This constructor should only be used by the
Chris@16:   //  distributed CSR graph.
Chris@16:   template <typename GlobalToLocal>
Chris@16:   compressed_sparse_row_graph(construct_inplace_from_sources_and_targets_global_t,
Chris@16:                               std::vector<vertex_descriptor>& sources,
Chris@16:                               std::vector<vertex_descriptor>& targets,
Chris@16:                               vertices_size_type numlocalverts,
Chris@16:                               GlobalToLocal global_to_local,
Chris@16:                               const GraphProperty& prop = GraphProperty())
Chris@16:     : inherited_vertex_properties(numlocalverts), m_property(prop)
Chris@16:   {
Chris@16:     m_forward.assign_sources_and_targets_global(sources, targets, numlocalverts, global_to_local);
Chris@16:   }
Chris@16: 
Chris@16:   //  From number of vertices and mutable vectors of sources, targets, and edge
Chris@16:   //  properties; vectors are returned with unspecified contents but are
Chris@16:   //  guaranteed not to share storage with the constructed graph.
Chris@16:   compressed_sparse_row_graph(construct_inplace_from_sources_and_targets_t,
Chris@16:                               std::vector<vertex_descriptor>& sources,
Chris@16:                               std::vector<vertex_descriptor>& targets,
Chris@16:                               std::vector<typename forward_type::inherited_edge_properties::edge_bundled>& edge_props,
Chris@16:                               vertices_size_type numverts,
Chris@16:                               const GraphProperty& prop = GraphProperty())
Chris@16:     : inherited_vertex_properties(numverts), m_property(prop)
Chris@16:   {
Chris@16:     m_forward.assign_sources_and_targets_global(sources, targets, edge_props, numverts, boost::typed_identity_property_map<vertices_size_type>());
Chris@16:   }
Chris@16: 
Chris@16:   //  From number of vertices and mutable vectors of sources and targets and
Chris@16:   //  edge properties, expressed with global vertex indices; vectors are
Chris@16:   //  returned with unspecified contents but are guaranteed not to share
Chris@16:   //  storage with the constructed graph.  This constructor should only be used
Chris@16:   //  by the distributed CSR graph.
Chris@16:   template <typename GlobalToLocal>
Chris@16:   compressed_sparse_row_graph(construct_inplace_from_sources_and_targets_global_t,
Chris@16:                               std::vector<vertex_descriptor>& sources,
Chris@16:                               std::vector<vertex_descriptor>& targets,
Chris@16:                               std::vector<typename forward_type::inherited_edge_properties::edge_bundled>& edge_props,
Chris@16:                               vertices_size_type numlocalverts,
Chris@16:                               GlobalToLocal global_to_local,
Chris@16:                               const GraphProperty& prop = GraphProperty())
Chris@16:     : inherited_vertex_properties(numlocalverts), m_property(prop)
Chris@16:   {
Chris@16:     m_forward.assign_sources_and_targets_global(sources, targets, edge_props, numlocalverts, global_to_local);
Chris@16:   }
Chris@16: 
Chris@16:   //  From number of vertices and single-pass range of unsorted edges.  Data is
Chris@16:   //  cached in coordinate form before creating the actual graph.
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 GraphProperty& prop = GraphProperty())
Chris@16:     : inherited_vertex_properties(numverts), m_property(prop)
Chris@16:   {
Chris@16:     std::vector<vertex_descriptor> sources, targets;
Chris@16:     boost::graph::detail::split_into_separate_coords
Chris@16:       (edge_begin, edge_end, sources, targets);
Chris@16:     m_forward.assign_sources_and_targets_global(sources, targets, numverts, boost::typed_identity_property_map<vertices_size_type>());
Chris@16:   }
Chris@16: 
Chris@16:   //  From number of vertices and single-pass range of unsorted edges and
Chris@16:   //  single-pass range of edge properties.  Data is cached in coordinate form
Chris@16:   //  before creating the actual graph.
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 GraphProperty& prop = GraphProperty())
Chris@16:     : inherited_vertex_properties(numverts), m_property(prop)
Chris@16:   {
Chris@16:     std::vector<vertex_descriptor> sources, targets;
Chris@16:     boost::graph::detail::split_into_separate_coords
Chris@16:       (edge_begin, edge_end, sources, targets);
Chris@16:     size_t numedges = sources.size();
Chris@16:     std::vector<typename forward_type::inherited_edge_properties::edge_bundled> edge_props(numedges);
Chris@16:     for (size_t i = 0; i < numedges; ++i) {
Chris@16:       edge_props[i] = *ep_iter++;
Chris@16:     }
Chris@16:     m_forward.assign_sources_and_targets_global(sources, targets, edge_props, numverts, boost::typed_identity_property_map<vertices_size_type>());
Chris@16:   }
Chris@16: 
Chris@16:   //  From number of vertices and single-pass range of unsorted edges.  Data is
Chris@16:   //  cached in coordinate form before creating the actual graph.  Edges are
Chris@16:   //  filtered and transformed for use in a distributed graph.
Chris@16:   template<typename InputIterator, typename GlobalToLocal, typename SourcePred>
Chris@16:   compressed_sparse_row_graph(edges_are_unsorted_global_t,
Chris@16:                               InputIterator edge_begin, InputIterator edge_end,
Chris@16:                               vertices_size_type numlocalverts,
Chris@16:                               GlobalToLocal global_to_local,
Chris@16:                               const SourcePred& source_pred,
Chris@16:                               const GraphProperty& prop = GraphProperty())
Chris@16:     : inherited_vertex_properties(numlocalverts), m_property(prop)
Chris@16:   {
Chris@16:     std::vector<vertex_descriptor> sources, targets;
Chris@16:     boost::graph::detail::split_into_separate_coords_filtered
Chris@16:       (edge_begin, edge_end, sources, targets, source_pred);
Chris@16:     m_forward.assign_sources_and_targets_global(sources, targets, numlocalverts, global_to_local);
Chris@16:   }
Chris@16: 
Chris@16:   //  From number of vertices and single-pass range of unsorted edges and
Chris@16:   //  single-pass range of edge properties.  Data is cached in coordinate form
Chris@16:   //  before creating the actual graph.  Edges are filtered and transformed for
Chris@16:   //  use in a distributed graph.
Chris@16:   template<typename InputIterator, typename EdgePropertyIterator,
Chris@16:            typename GlobalToLocal, typename SourcePred>
Chris@16:   compressed_sparse_row_graph(edges_are_unsorted_global_t,
Chris@16:                               InputIterator edge_begin, InputIterator edge_end,
Chris@16:                               EdgePropertyIterator ep_iter,
Chris@16:                               vertices_size_type numlocalverts,
Chris@16:                               GlobalToLocal global_to_local,
Chris@16:                               const SourcePred& source_pred,
Chris@16:                               const GraphProperty& prop = GraphProperty())
Chris@16:     : inherited_vertex_properties(numlocalverts), m_property(prop)
Chris@16:   {
Chris@16:     std::vector<vertex_descriptor> sources, targets;
Chris@16:     std::vector<edge_bundled> edge_props;
Chris@16:     boost::graph::detail::split_into_separate_coords_filtered
Chris@16:       (edge_begin, edge_end, ep_iter, sources, targets, edge_props, source_pred);
Chris@16:     m_forward.assign_sources_and_targets_global(sources, targets, edge_props, numlocalverts, global_to_local);
Chris@16:   }
Chris@16: 
Chris@16: 
Chris@16:   //   Requires IncidenceGraph and a vertex index map
Chris@16:   template<typename Graph, typename VertexIndexMap>
Chris@16:   compressed_sparse_row_graph(const Graph& g, const VertexIndexMap& vi,
Chris@16:                               vertices_size_type numverts,
Chris@16:                               edges_size_type numedges)
Chris@16:     : m_property()
Chris@16:   {
Chris@16:     assign(g, vi, numverts, numedges);
Chris@16:     inherited_vertex_properties::resize(numverts);
Chris@16:   }
Chris@16: 
Chris@16:   //   Requires VertexListGraph and EdgeListGraph
Chris@16:   template<typename Graph, typename VertexIndexMap>
Chris@16:   compressed_sparse_row_graph(const Graph& g, const VertexIndexMap& vi)
Chris@16:     : m_property()
Chris@16:   {
Chris@16:     typename graph_traits<Graph>::edges_size_type numedges = num_edges(g);
Chris@16:     if (is_same<typename graph_traits<Graph>::directed_category, undirectedS>::value) {
Chris@16:       numedges *= 2; // Double each edge (actual doubling done by out_edges function)
Chris@16:     }
Chris@16:     vertices_size_type numverts = num_vertices(g);
Chris@16:     assign(g, vi, numverts, numedges);
Chris@16:     inherited_vertex_properties::resize(numverts);
Chris@16:   }
Chris@16: 
Chris@16:   // Requires vertex index map plus requirements of previous constructor
Chris@16:   template<typename Graph>
Chris@16:   explicit compressed_sparse_row_graph(const Graph& g)
Chris@16:     : m_property()
Chris@16:   {
Chris@16:     typename graph_traits<Graph>::edges_size_type numedges = num_edges(g);
Chris@16:     if (is_same<typename graph_traits<Graph>::directed_category, undirectedS>::value) {
Chris@16:       numedges *= 2; // Double each edge (actual doubling done by out_edges function)
Chris@16:     }
Chris@16:     assign(g, get(vertex_index, g), num_vertices(g), numedges);
Chris@16:   }
Chris@16: 
Chris@16:   // From any graph (slow and uses a lot of memory)
Chris@16:   //   Requires IncidenceGraph and a vertex index map
Chris@16:   //   Internal helper function
Chris@16:   //   Note that numedges must be doubled for undirected source graphs
Chris@16:   template<typename Graph, typename VertexIndexMap>
Chris@16:   void
Chris@16:   assign(const Graph& g, const VertexIndexMap& vi,
Chris@16:          vertices_size_type numverts, edges_size_type numedges)
Chris@16:   {
Chris@16:     m_forward.assign(g, vi, numverts, numedges);
Chris@16:     inherited_vertex_properties::resize(numverts);
Chris@16:   }
Chris@16: 
Chris@16:   // Requires the above, plus VertexListGraph and EdgeListGraph
Chris@16:   template<typename Graph, typename VertexIndexMap>
Chris@16:   void assign(const Graph& g, const VertexIndexMap& vi)
Chris@16:   {
Chris@16:     typename graph_traits<Graph>::edges_size_type numedges = num_edges(g);
Chris@16:     if (is_same<typename graph_traits<Graph>::directed_category, undirectedS>::value) {
Chris@16:       numedges *= 2; // Double each edge (actual doubling done by out_edges function)
Chris@16:     }
Chris@16:     vertices_size_type numverts = num_vertices(g);
Chris@16:     m_forward.assign(g, vi, numverts, numedges);
Chris@16:     inherited_vertex_properties::resize(numverts);
Chris@16:   }
Chris@16: 
Chris@16:   // Requires the above, plus a vertex_index map.
Chris@16:   template<typename Graph>
Chris@16:   void assign(const Graph& g)
Chris@16:   {
Chris@16:     typename graph_traits<Graph>::edges_size_type numedges = num_edges(g);
Chris@16:     if (is_same<typename graph_traits<Graph>::directed_category, undirectedS>::value) {
Chris@16:       numedges *= 2; // Double each edge (actual doubling done by out_edges function)
Chris@16:     }
Chris@16:     vertices_size_type numverts = num_vertices(g);
Chris@16:     m_forward.assign(g, get(vertex_index, g), numverts, numedges);
Chris@16:     inherited_vertex_properties::resize(numverts);
Chris@16:   }
Chris@16: 
Chris@16:   // Add edges from a sorted (smallest sources first) range of pairs and edge
Chris@16:   // properties
Chris@16:   template <typename BidirectionalIteratorOrig, typename EPIterOrig,
Chris@16:             typename GlobalToLocal>
Chris@16:   void
Chris@16:   add_edges_sorted_internal(
Chris@16:       BidirectionalIteratorOrig first_sorted,
Chris@16:       BidirectionalIteratorOrig last_sorted,
Chris@16:       EPIterOrig ep_iter_sorted,
Chris@16:       const GlobalToLocal& global_to_local) {
Chris@16:     m_forward.add_edges_sorted_internal(first_sorted, last_sorted, ep_iter_sorted, global_to_local);
Chris@16:   }
Chris@16: 
Chris@16:   template <typename BidirectionalIteratorOrig, typename EPIterOrig>
Chris@16:   void
Chris@16:   add_edges_sorted_internal(
Chris@16:       BidirectionalIteratorOrig first_sorted,
Chris@16:       BidirectionalIteratorOrig last_sorted,
Chris@16:       EPIterOrig ep_iter_sorted)  {
Chris@16:     m_forward.add_edges_sorted_internal(first_sorted, last_sorted, ep_iter_sorted, typed_identity_property_map<vertices_size_type>());
Chris@16:   }
Chris@16: 
Chris@16:   // Add edges from a sorted (smallest sources first) range of pairs
Chris@16:   template <typename BidirectionalIteratorOrig>
Chris@16:   void
Chris@16:   add_edges_sorted_internal(
Chris@16:       BidirectionalIteratorOrig first_sorted,
Chris@16:       BidirectionalIteratorOrig last_sorted) {
Chris@16:     m_forward.add_edges_sorted_internal(first_sorted, last_sorted, detail::default_construct_iterator<edge_bundled>());
Chris@16:   }
Chris@16: 
Chris@16:   template <typename BidirectionalIteratorOrig, typename GlobalToLocal>
Chris@16:   void
Chris@16:   add_edges_sorted_internal_global(
Chris@16:       BidirectionalIteratorOrig first_sorted,
Chris@16:       BidirectionalIteratorOrig last_sorted,
Chris@16:       const GlobalToLocal& global_to_local) {
Chris@16:     m_forward.add_edges_sorted_internal(first_sorted, last_sorted, detail::default_construct_iterator<edge_bundled>(), global_to_local);
Chris@16:   }
Chris@16: 
Chris@16:   template <typename BidirectionalIteratorOrig, typename EPIterOrig,
Chris@16:             typename GlobalToLocal>
Chris@16:   void
Chris@16:   add_edges_sorted_internal_global(
Chris@16:       BidirectionalIteratorOrig first_sorted,
Chris@16:       BidirectionalIteratorOrig last_sorted,
Chris@16:       EPIterOrig ep_iter_sorted,
Chris@16:       const GlobalToLocal& global_to_local) {
Chris@16:     m_forward.add_edges_sorted_internal(first_sorted, last_sorted, ep_iter_sorted, global_to_local);
Chris@16:   }
Chris@16: 
Chris@16:   // Add edges from a range of (source, target) pairs that are unsorted
Chris@16:   template <typename InputIterator, typename GlobalToLocal>
Chris@16:   inline void
Chris@16:   add_edges_internal(InputIterator first, InputIterator last,
Chris@16:                      const GlobalToLocal& global_to_local) {
Chris@16:     typedef compressed_sparse_row_graph Graph;
Chris@16:     typedef typename boost::graph_traits<Graph>::vertex_descriptor vertex_t;
Chris@16:     typedef std::vector<std::pair<vertex_t, vertex_t> > edge_vector_t;
Chris@16:     edge_vector_t new_edges(first, last);
Chris@16:     if (new_edges.empty()) return;
Chris@16:     std::sort(new_edges.begin(), new_edges.end());
Chris@16:     this->add_edges_sorted_internal_global(new_edges.begin(), new_edges.end(), global_to_local);
Chris@16:   }
Chris@16: 
Chris@16:   template <typename InputIterator>
Chris@16:   inline void
Chris@16:   add_edges_internal(InputIterator first, InputIterator last) {
Chris@16:     this->add_edges_internal(first, last, typed_identity_property_map<vertices_size_type>());
Chris@16:   }
Chris@16: 
Chris@16:   // Add edges from a range of (source, target) pairs and edge properties that
Chris@16:   // are unsorted
Chris@16:   template <typename InputIterator, typename EPIterator, typename GlobalToLocal>
Chris@16:   inline void
Chris@16:   add_edges_internal(InputIterator first, InputIterator last,
Chris@16:                      EPIterator ep_iter, EPIterator ep_iter_end,
Chris@16:                      const GlobalToLocal& global_to_local) {
Chris@16:     typedef compressed_sparse_row_graph Graph;
Chris@16:     typedef typename boost::graph_traits<Graph>::vertex_descriptor vertex_t;
Chris@16:     typedef std::pair<vertex_t, vertex_t> vertex_pair;
Chris@16:     typedef std::vector<
Chris@16:               boost::tuple<vertex_pair,
Chris@16:                            edge_bundled> >
Chris@16:       edge_vector_t;
Chris@16:     edge_vector_t new_edges
Chris@16:       (boost::make_zip_iterator(boost::make_tuple(first, ep_iter)),
Chris@16:        boost::make_zip_iterator(boost::make_tuple(last, ep_iter_end)));
Chris@16:     if (new_edges.empty()) return;
Chris@16:     std::sort(new_edges.begin(), new_edges.end(),
Chris@16:               boost::detail::compare_first<
Chris@16:                 std::less<vertex_pair> >());
Chris@16:     m_forward.add_edges_sorted_internal
Chris@16:       (boost::make_transform_iterator(
Chris@16:          new_edges.begin(),
Chris@16:          boost::detail::my_tuple_get_class<0, vertex_pair>()),
Chris@16:        boost::make_transform_iterator(
Chris@16:          new_edges.end(),
Chris@16:          boost::detail::my_tuple_get_class<0, vertex_pair>()),
Chris@16:        boost::make_transform_iterator(
Chris@16:          new_edges.begin(),
Chris@16:          boost::detail::my_tuple_get_class
Chris@16:            <1, edge_bundled>()),
Chris@16:        global_to_local);
Chris@16:   }
Chris@16: 
Chris@16:   // Add edges from a range of (source, target) pairs and edge properties that
Chris@16:   // are unsorted
Chris@16:   template <typename InputIterator, typename EPIterator>
Chris@16:   inline void
Chris@16:   add_edges_internal(InputIterator first, InputIterator last,
Chris@16:                      EPIterator ep_iter, EPIterator ep_iter_end) {
Chris@16:     this->add_edges_internal(first, last, ep_iter, ep_iter_end, typed_identity_property_map<vertices_size_type>());
Chris@16:   }
Chris@16: 
Chris@16:   using inherited_vertex_properties::operator[];
Chris@16: 
Chris@16:   // Directly access a edge or edge bundle
Chris@16:   edge_push_back_type& operator[](const edge_descriptor& v)
Chris@16:   { return m_forward.m_edge_properties[get(edge_index, *this, v)]; }
Chris@16: 
Chris@16:   const edge_push_back_type& operator[](const edge_descriptor& v) const
Chris@16:   { return m_forward.m_edge_properties[get(edge_index, *this, v)]; }
Chris@16: 
Chris@16:   // Directly access a graph bundle
Chris@16:   graph_bundled& operator[](graph_bundle_t)
Chris@16:   { return get_property(*this); }
Chris@16: 
Chris@16:   const graph_bundled& operator[](graph_bundle_t) const
Chris@16:   { return get_property(*this); }
Chris@16: 
Chris@16:   // private: non-portable, requires friend templates
Chris@16:   inherited_vertex_properties&       vertex_properties()       {return *this;}
Chris@16:   const inherited_vertex_properties& vertex_properties() const {return *this;}
Chris@16:   typename forward_type::inherited_edge_properties&       edge_properties()       { return m_forward; }
Chris@16:   const typename forward_type::inherited_edge_properties& edge_properties() const { return m_forward; }
Chris@16: 
Chris@16:   forward_type m_forward;
Chris@16:   GraphProperty m_property;
Chris@16: };
Chris@16: 
Chris@16: template<typename VertexProperty,
Chris@16:          typename EdgeProperty,
Chris@16:          typename GraphProperty,
Chris@16:          typename Vertex,
Chris@16:          typename EdgeIndex>
Chris@16: class compressed_sparse_row_graph<bidirectionalS, VertexProperty, EdgeProperty, GraphProperty, Vertex, EdgeIndex>
Chris@16:    : public detail::indexed_vertex_properties<BOOST_BIDIR_CSR_GRAPH_TYPE,
Chris@16:                                               VertexProperty, Vertex, typed_identity_property_map<Vertex> >
Chris@16: {
Chris@16:  public:
Chris@16:   typedef detail::indexed_vertex_properties<compressed_sparse_row_graph,
Chris@16:                                             VertexProperty, Vertex, typed_identity_property_map<Vertex> >
Chris@16:     inherited_vertex_properties;
Chris@16: 
Chris@16:  public:
Chris@16:   // For Property Graph
Chris@16:   typedef GraphProperty graph_property_type;
Chris@16:   typedef typename lookup_one_property<GraphProperty, graph_bundle_t>::type graph_bundled;
Chris@16:   // typedef GraphProperty graph_property_type;
Chris@16: 
Chris@16:   typedef detail::compressed_sparse_row_structure<EdgeProperty, Vertex, EdgeIndex> forward_type;
Chris@16:   typedef EdgeIndex /* typename boost::mpl::if_c<boost::is_same<EdgeProperty, boost::no_property>, boost::no_property, EdgeIndex> */ backward_edge_property;
Chris@16:   typedef detail::compressed_sparse_row_structure<backward_edge_property, Vertex, EdgeIndex> backward_type;
Chris@16: 
Chris@16:  public:
Chris@16:   // Concept requirements:
Chris@16:   // For Graph
Chris@16:   typedef Vertex vertex_descriptor;
Chris@16:   typedef detail::csr_edge_descriptor<Vertex, EdgeIndex> edge_descriptor;
Chris@16:   typedef bidirectional_tag directed_category;
Chris@16:   typedef allow_parallel_edge_tag edge_parallel_category;
Chris@16: 
Chris@16:   class traversal_category: public bidirectional_graph_tag,
Chris@16:                             public adjacency_graph_tag,
Chris@16:                             public vertex_list_graph_tag,
Chris@16:                             public edge_list_graph_tag {};
Chris@16: 
Chris@16:   static vertex_descriptor null_vertex() { return vertex_descriptor(-1); }
Chris@16: 
Chris@16:   // For VertexListGraph
Chris@16:   typedef counting_iterator<Vertex> vertex_iterator;
Chris@16:   typedef Vertex vertices_size_type;
Chris@16: 
Chris@16:   // For EdgeListGraph
Chris@16:   typedef EdgeIndex edges_size_type;
Chris@16: 
Chris@16:   // For IncidenceGraph
Chris@16:   typedef detail::csr_out_edge_iterator<compressed_sparse_row_graph> out_edge_iterator;
Chris@16:   typedef EdgeIndex degree_size_type;
Chris@16: 
Chris@16:   // For AdjacencyGraph
Chris@16:   typedef typename std::vector<Vertex>::const_iterator adjacency_iterator;
Chris@16: 
Chris@16:   // For EdgeListGraph
Chris@16:   typedef detail::csr_edge_iterator<compressed_sparse_row_graph> edge_iterator;
Chris@16: 
Chris@16:   // For BidirectionalGraph (not implemented)
Chris@16:   typedef detail::csr_in_edge_iterator<compressed_sparse_row_graph> in_edge_iterator;
Chris@16: 
Chris@16:   // For internal use
Chris@16:   typedef csr_graph_tag graph_tag;
Chris@16: 
Chris@16:   typedef typename forward_type::inherited_edge_properties::edge_bundled edge_bundled;
Chris@16:   typedef typename forward_type::inherited_edge_properties::edge_push_back_type edge_push_back_type;
Chris@16:   typedef typename forward_type::inherited_edge_properties::edge_property_type edge_property_type;
Chris@16: 
Chris@16:   // Constructors
Chris@16: 
Chris@16:   // Default constructor: an empty graph.
Chris@16:   compressed_sparse_row_graph(): m_property() {}
Chris@16: 
Chris@16:   //  With numverts vertices
Chris@16:   compressed_sparse_row_graph(vertices_size_type numverts)
Chris@16:     : inherited_vertex_properties(numverts),
Chris@16:       m_forward(numverts), m_backward(numverts) {}
Chris@16: 
Chris@16:   private:
Chris@16: 
Chris@16:   void set_up_backward_property_links() {
Chris@16:     std::pair<edge_iterator, edge_iterator> e = edges(*this);
Chris@16:     m_backward.assign_unsorted_multi_pass_edges
Chris@16:       (detail::transpose_edges(
Chris@16:          detail::make_edge_to_index_pair_iter
Chris@16:            (*this, get(vertex_index, *this), e.first)),
Chris@16:        detail::transpose_edges(
Chris@16:          detail::make_edge_to_index_pair_iter
Chris@16:            (*this, get(vertex_index, *this), e.second)),
Chris@16:        boost::counting_iterator<EdgeIndex>(0),
Chris@16:        m_forward.m_rowstart.size() - 1,
Chris@16:        typed_identity_property_map<Vertex>(),
Chris@16:        keep_all());
Chris@16:   }
Chris@16: 
Chris@16:   public:
Chris@16: 
Chris@16:   //  From number of vertices and unsorted list of edges
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 GraphProperty& prop = GraphProperty())
Chris@16:     : inherited_vertex_properties(numverts), m_property(prop)
Chris@16:   {
Chris@16:     m_forward.assign_unsorted_multi_pass_edges(edge_begin, edge_end, numverts, typed_identity_property_map<Vertex>(), keep_all());
Chris@16:     set_up_backward_property_links();
Chris@16:   }
Chris@16: 
Chris@16:   //  From number of vertices and unsorted list of edges, plus edge properties
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 GraphProperty& prop = GraphProperty())
Chris@16:     : inherited_vertex_properties(numverts), m_forward(), m_property(prop)
Chris@16:   {
Chris@16:     m_forward.assign_unsorted_multi_pass_edges(edge_begin, edge_end, ep_iter, numverts, typed_identity_property_map<Vertex>(), keep_all());
Chris@16:     set_up_backward_property_links();
Chris@16:   }
Chris@16: 
Chris@16:   //  From number of vertices and unsorted list of edges, with filter and
Chris@16:   //  global-to-local map
Chris@16:   template <typename MultiPassInputIterator, typename GlobalToLocal, typename SourcePred>
Chris@16:   compressed_sparse_row_graph(edges_are_unsorted_multi_pass_global_t,
Chris@16:                               MultiPassInputIterator edge_begin,
Chris@16:                               MultiPassInputIterator edge_end,
Chris@16:                               vertices_size_type numlocalverts,
Chris@16:                               const GlobalToLocal& global_to_local,
Chris@16:                               const SourcePred& source_pred,
Chris@16:                               const GraphProperty& prop = GraphProperty())
Chris@16:     : inherited_vertex_properties(numlocalverts), m_forward(), m_property(prop)
Chris@16:   {
Chris@16:     m_forward.assign_unsorted_multi_pass_edges(edge_begin, edge_end, numlocalverts, global_to_local, source_pred);
Chris@16:     set_up_backward_property_links();
Chris@16:   }
Chris@16: 
Chris@16:   //  From number of vertices and unsorted list of edges, plus edge properties,
Chris@16:   //  with filter and global-to-local map
Chris@16:   template <typename MultiPassInputIterator, typename EdgePropertyIterator, typename GlobalToLocal, typename SourcePred>
Chris@16:   compressed_sparse_row_graph(edges_are_unsorted_multi_pass_global_t,
Chris@16:                               MultiPassInputIterator edge_begin,
Chris@16:                               MultiPassInputIterator edge_end,
Chris@16:                               EdgePropertyIterator ep_iter,
Chris@16:                               vertices_size_type numlocalverts,
Chris@16:                               const GlobalToLocal& global_to_local,
Chris@16:                               const SourcePred& source_pred,
Chris@16:                               const GraphProperty& prop = GraphProperty())
Chris@16:     : inherited_vertex_properties(numlocalverts), m_forward(), m_property(prop)
Chris@16:   {
Chris@16:     m_forward.assign_unsorted_multi_pass_edges(edge_begin, edge_end, ep_iter, numlocalverts, global_to_local, source_pred);
Chris@16:     set_up_backward_property_links();
Chris@16:   }
Chris@16: 
Chris@16:   //   Requires IncidenceGraph and a vertex index map
Chris@16:   template<typename Graph, typename VertexIndexMap>
Chris@16:   compressed_sparse_row_graph(const Graph& g, const VertexIndexMap& vi,
Chris@16:                               vertices_size_type numverts,
Chris@16:                               edges_size_type numedges)
Chris@16:     : m_property()
Chris@16:   {
Chris@16:     assign(g, vi, numverts, numedges);
Chris@16:     inherited_vertex_properties::resize(numverts);
Chris@16:   }
Chris@16: 
Chris@16:   //   Requires VertexListGraph and EdgeListGraph
Chris@16:   template<typename Graph, typename VertexIndexMap>
Chris@16:   compressed_sparse_row_graph(const Graph& g, const VertexIndexMap& vi)
Chris@16:     : m_property()
Chris@16:   {
Chris@16:     typename graph_traits<Graph>::edges_size_type numedges = num_edges(g);
Chris@16:     if (is_same<typename graph_traits<Graph>::directed_category, undirectedS>::value) {
Chris@16:       numedges *= 2; // Double each edge (actual doubling done by out_edges function)
Chris@16:     }
Chris@16:     vertices_size_type numverts = num_vertices(g);
Chris@16:     assign(g, vi, numverts, numedges);
Chris@16:     inherited_vertex_properties::resize(numverts);
Chris@16:   }
Chris@16: 
Chris@16:   // Requires vertex index map plus requirements of previous constructor
Chris@16:   template<typename Graph>
Chris@16:   explicit compressed_sparse_row_graph(const Graph& g)
Chris@16:     : m_property()
Chris@16:   {
Chris@16:     typename graph_traits<Graph>::edges_size_type numedges = num_edges(g);
Chris@16:     if (is_same<typename graph_traits<Graph>::directed_category, undirectedS>::value) {
Chris@16:       numedges *= 2; // Double each edge (actual doubling done by out_edges function)
Chris@16:     }
Chris@16:     assign(g, get(vertex_index, g), num_vertices(g), numedges);
Chris@16:   }
Chris@16: 
Chris@16:   // From any graph (slow and uses a lot of memory)
Chris@16:   //   Requires IncidenceGraph and a vertex index map
Chris@16:   //   Internal helper function
Chris@16:   //   Note that numedges must be doubled for undirected source graphs
Chris@16:   template<typename Graph, typename VertexIndexMap>
Chris@16:   void
Chris@16:   assign(const Graph& g, const VertexIndexMap& vi,
Chris@16:          vertices_size_type numverts, edges_size_type numedges)
Chris@16:   {
Chris@16:     m_forward.assign(g, vi, numverts, numedges);
Chris@16:     inherited_vertex_properties::resize(numverts);
Chris@16:     set_up_backward_property_links();
Chris@16:   }
Chris@16: 
Chris@16:   // Requires the above, plus VertexListGraph and EdgeListGraph
Chris@16:   template<typename Graph, typename VertexIndexMap>
Chris@16:   void assign(const Graph& g, const VertexIndexMap& vi)
Chris@16:   {
Chris@16:     typename graph_traits<Graph>::edges_size_type numedges = num_edges(g);
Chris@16:     if (is_same<typename graph_traits<Graph>::directed_category, undirectedS>::value) {
Chris@16:       numedges *= 2; // Double each edge (actual doubling done by out_edges function)
Chris@16:     }
Chris@16:     vertices_size_type numverts = num_vertices(g);
Chris@16:     m_forward.assign(g, vi, numverts, numedges);
Chris@16:     inherited_vertex_properties::resize(numverts);
Chris@16:     set_up_backward_property_links();
Chris@16:   }
Chris@16: 
Chris@16:   // Requires the above, plus a vertex_index map.
Chris@16:   template<typename Graph>
Chris@16:   void assign(const Graph& g)
Chris@16:   {
Chris@16:     typename graph_traits<Graph>::edges_size_type numedges = num_edges(g);
Chris@16:     if (is_same<typename graph_traits<Graph>::directed_category, undirectedS>::value) {
Chris@16:       numedges *= 2; // Double each edge (actual doubling done by out_edges function)
Chris@16:     }
Chris@16:     vertices_size_type numverts = num_vertices(g);
Chris@16:     m_forward.assign(g, get(vertex_index, g), numverts, numedges);
Chris@16:     inherited_vertex_properties::resize(numverts);
Chris@16:     set_up_backward_property_links();
Chris@16:   }
Chris@16: 
Chris@16:   using inherited_vertex_properties::operator[];
Chris@16: 
Chris@16:   // Directly access a edge or edge bundle
Chris@16:   edge_push_back_type& operator[](const edge_descriptor& v)
Chris@16:   { return m_forward.m_edge_properties[get(edge_index, *this, v)]; }
Chris@16: 
Chris@16:   const edge_push_back_type& operator[](const edge_descriptor& v) const
Chris@16:   { return m_forward.m_edge_properties[get(edge_index, *this, v)]; }
Chris@16: 
Chris@16:   // private: non-portable, requires friend templates
Chris@16:   inherited_vertex_properties&       vertex_properties()       {return *this;}
Chris@16:   const inherited_vertex_properties& vertex_properties() const {return *this;}
Chris@16:   typename forward_type::inherited_edge_properties&       edge_properties()       { return m_forward; }
Chris@16:   const typename forward_type::inherited_edge_properties& edge_properties() const { return m_forward; }
Chris@16: 
Chris@16:   forward_type m_forward;
Chris@16:   backward_type m_backward;
Chris@16:   GraphProperty m_property;
Chris@16: };
Chris@16: 
Chris@16: // Construction functions
Chris@16: template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
Chris@16: inline Vertex
Chris@16: add_vertex(BOOST_CSR_GRAPH_TYPE& g) {
Chris@16:   add_vertex(g, typename BOOST_CSR_GRAPH_TYPE::vertex_bundled());
Chris@16: }
Chris@16: 
Chris@16: template<BOOST_DIR_CSR_GRAPH_TEMPLATE_PARMS>
Chris@16: inline Vertex
Chris@16: add_vertex(BOOST_DIR_CSR_GRAPH_TYPE& g,
Chris@16:            typename BOOST_DIR_CSR_GRAPH_TYPE::vertex_bundled const& p) {
Chris@16:   Vertex old_num_verts_plus_one = g.m_forward.m_rowstart.size();
Chris@16:   g.m_forward.m_rowstart.push_back(g.m_forward.m_rowstart.back());
Chris@16:   g.vertex_properties().push_back(p);
Chris@16:   return old_num_verts_plus_one - 1;
Chris@16: }
Chris@16: 
Chris@16: template<BOOST_BIDIR_CSR_GRAPH_TEMPLATE_PARMS>
Chris@16: inline Vertex
Chris@16: add_vertex(BOOST_BIDIR_CSR_GRAPH_TYPE& g,
Chris@16:            typename BOOST_BIDIR_CSR_GRAPH_TYPE::vertex_bundled const& p) {
Chris@16:   Vertex old_num_verts_plus_one = g.m_forward.m_rowstart.size();
Chris@16:   g.m_forward.m_rowstart.push_back(g.m_forward.m_rowstart.back());
Chris@16:   g.m_backward.m_rowstart.push_back(g.m_backward.m_rowstart.back());
Chris@16:   g.vertex_properties().push_back(p);
Chris@16:   return old_num_verts_plus_one - 1;
Chris@16: }
Chris@16: 
Chris@16: template<BOOST_DIR_CSR_GRAPH_TEMPLATE_PARMS>
Chris@16: inline Vertex
Chris@16: add_vertices(typename BOOST_DIR_CSR_GRAPH_TYPE::vertices_size_type count, BOOST_DIR_CSR_GRAPH_TYPE& g) {
Chris@16:   Vertex old_num_verts_plus_one = g.m_forward.m_rowstart.size();
Chris@16:   EdgeIndex numedges = g.m_forward.m_rowstart.back();
Chris@16:   g.m_forward.m_rowstart.resize(old_num_verts_plus_one + count, numedges);
Chris@16:   g.vertex_properties().resize(num_vertices(g));
Chris@16:   return old_num_verts_plus_one - 1;
Chris@16: }
Chris@16: 
Chris@16:   // Add edges from a sorted (smallest sources first) range of pairs and edge
Chris@16:   // properties
Chris@16:   template <BOOST_DIR_CSR_GRAPH_TEMPLATE_PARMS, typename BidirectionalIteratorOrig,
Chris@16:             typename EPIterOrig>
Chris@16:   void
Chris@16:   add_edges_sorted(
Chris@16:       BidirectionalIteratorOrig first_sorted,
Chris@16:       BidirectionalIteratorOrig last_sorted,
Chris@16:       EPIterOrig ep_iter_sorted,
Chris@16:       BOOST_DIR_CSR_GRAPH_TYPE& g) {
Chris@16:     g.add_edges_sorted_internal(first_sorted, last_sorted, ep_iter_sorted);
Chris@16:   }
Chris@16: 
Chris@16:   // Add edges from a sorted (smallest sources first) range of pairs
Chris@16:   template <BOOST_DIR_CSR_GRAPH_TEMPLATE_PARMS, typename BidirectionalIteratorOrig>
Chris@16:   void
Chris@16:   add_edges_sorted(
Chris@16:       BidirectionalIteratorOrig first_sorted,
Chris@16:       BidirectionalIteratorOrig last_sorted,
Chris@16:       BOOST_DIR_CSR_GRAPH_TYPE& g) {
Chris@16:     g.add_edges_sorted_internal(first_sorted, last_sorted);
Chris@16:   }
Chris@16: 
Chris@16:   template <BOOST_DIR_CSR_GRAPH_TEMPLATE_PARMS, typename BidirectionalIteratorOrig,
Chris@16:             typename EPIterOrig, typename GlobalToLocal>
Chris@16:   void
Chris@16:   add_edges_sorted_global(
Chris@16:       BidirectionalIteratorOrig first_sorted,
Chris@16:       BidirectionalIteratorOrig last_sorted,
Chris@16:       EPIterOrig ep_iter_sorted,
Chris@16:       const GlobalToLocal& global_to_local,
Chris@16:       BOOST_DIR_CSR_GRAPH_TYPE& g) {
Chris@16:     g.add_edges_sorted_internal_global(first_sorted, last_sorted, ep_iter_sorted,
Chris@16:                                        global_to_local);
Chris@16:   }
Chris@16: 
Chris@16:   // Add edges from a sorted (smallest sources first) range of pairs
Chris@16:   template <BOOST_DIR_CSR_GRAPH_TEMPLATE_PARMS, typename BidirectionalIteratorOrig,
Chris@16:             typename GlobalToLocal>
Chris@16:   void
Chris@16:   add_edges_sorted_global(
Chris@16:       BidirectionalIteratorOrig first_sorted,
Chris@16:       BidirectionalIteratorOrig last_sorted,
Chris@16:       const GlobalToLocal& global_to_local,
Chris@16:       BOOST_DIR_CSR_GRAPH_TYPE& g) {
Chris@16:     g.add_edges_sorted_internal_global(first_sorted, last_sorted, global_to_local);
Chris@16:   }
Chris@16: 
Chris@16:   // Add edges from a range of (source, target) pairs that are unsorted
Chris@16:   template <BOOST_DIR_CSR_GRAPH_TEMPLATE_PARMS, typename InputIterator,
Chris@16:             typename GlobalToLocal>
Chris@16:   inline void
Chris@16:   add_edges_global(InputIterator first, InputIterator last,
Chris@16:                    const GlobalToLocal& global_to_local, BOOST_DIR_CSR_GRAPH_TYPE& g) {
Chris@16:     g.add_edges_internal(first, last, global_to_local);
Chris@16:   }
Chris@16: 
Chris@16:   // Add edges from a range of (source, target) pairs that are unsorted
Chris@16:   template <BOOST_DIR_CSR_GRAPH_TEMPLATE_PARMS, typename InputIterator>
Chris@16:   inline void
Chris@16:   add_edges(InputIterator first, InputIterator last, BOOST_DIR_CSR_GRAPH_TYPE& g) {
Chris@16:     g.add_edges_internal(first, last);
Chris@16:   }
Chris@16: 
Chris@16:   // Add edges from a range of (source, target) pairs and edge properties that
Chris@16:   // are unsorted
Chris@16:   template <BOOST_DIR_CSR_GRAPH_TEMPLATE_PARMS,
Chris@16:             typename InputIterator, typename EPIterator>
Chris@16:   inline void
Chris@16:   add_edges(InputIterator first, InputIterator last,
Chris@16:             EPIterator ep_iter, EPIterator ep_iter_end,
Chris@16:             BOOST_DIR_CSR_GRAPH_TYPE& g) {
Chris@16:     g.add_edges_internal(first, last, ep_iter, ep_iter_end);
Chris@16:   }
Chris@16: 
Chris@16:   template <BOOST_DIR_CSR_GRAPH_TEMPLATE_PARMS,
Chris@16:             typename InputIterator, typename EPIterator, typename GlobalToLocal>
Chris@16:   inline void
Chris@16:   add_edges_global(InputIterator first, InputIterator last,
Chris@16:             EPIterator ep_iter, EPIterator ep_iter_end,
Chris@16:             const GlobalToLocal& global_to_local,
Chris@16:             BOOST_DIR_CSR_GRAPH_TYPE& g) {
Chris@16:     g.add_edges_internal(first, last, ep_iter, ep_iter_end, global_to_local);
Chris@16:   }
Chris@16: 
Chris@16: // From VertexListGraph
Chris@16: template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
Chris@16: inline Vertex
Chris@16: num_vertices(const BOOST_CSR_GRAPH_TYPE& g) {
Chris@16:   return g.m_forward.m_rowstart.size() - 1;
Chris@16: }
Chris@16: 
Chris@16: template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
Chris@16: std::pair<counting_iterator<Vertex>, counting_iterator<Vertex> >
Chris@16: inline vertices(const BOOST_CSR_GRAPH_TYPE& g) {
Chris@16:   return std::make_pair(counting_iterator<Vertex>(0),
Chris@16:                         counting_iterator<Vertex>(num_vertices(g)));
Chris@16: }
Chris@16: 
Chris@16: // From IncidenceGraph
Chris@16: template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
Chris@16: inline Vertex
Chris@16: source(typename BOOST_CSR_GRAPH_TYPE::edge_descriptor e,
Chris@16:        const BOOST_CSR_GRAPH_TYPE&)
Chris@16: {
Chris@16:   return e.src;
Chris@16: }
Chris@16: 
Chris@16: template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
Chris@16: inline Vertex
Chris@16: target(typename BOOST_CSR_GRAPH_TYPE::edge_descriptor e,
Chris@16:        const BOOST_CSR_GRAPH_TYPE& g)
Chris@16: {
Chris@16:   return g.m_forward.m_column[e.idx];
Chris@16: }
Chris@16: 
Chris@16: template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
Chris@16: inline std::pair<typename BOOST_CSR_GRAPH_TYPE::out_edge_iterator,
Chris@16:                  typename BOOST_CSR_GRAPH_TYPE::out_edge_iterator>
Chris@16: out_edges(Vertex v, const BOOST_CSR_GRAPH_TYPE& g)
Chris@16: {
Chris@16:   typedef typename BOOST_CSR_GRAPH_TYPE::edge_descriptor ed;
Chris@16:   typedef typename BOOST_CSR_GRAPH_TYPE::out_edge_iterator it;
Chris@16:   EdgeIndex v_row_start = g.m_forward.m_rowstart[v];
Chris@16:   EdgeIndex next_row_start = g.m_forward.m_rowstart[v + 1];
Chris@16:   return std::make_pair(it(ed(v, v_row_start)),
Chris@16:                         it(ed(v, next_row_start)));
Chris@16: }
Chris@16: 
Chris@16: template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
Chris@16: inline EdgeIndex
Chris@16: out_degree(Vertex v, const BOOST_CSR_GRAPH_TYPE& g)
Chris@16: {
Chris@16:   EdgeIndex v_row_start = g.m_forward.m_rowstart[v];
Chris@16:   EdgeIndex next_row_start = g.m_forward.m_rowstart[v + 1];
Chris@16:   return next_row_start - v_row_start;
Chris@16: }
Chris@16: 
Chris@16: template<BOOST_BIDIR_CSR_GRAPH_TEMPLATE_PARMS>
Chris@16: inline std::pair<typename BOOST_BIDIR_CSR_GRAPH_TYPE::in_edge_iterator,
Chris@16:                  typename BOOST_BIDIR_CSR_GRAPH_TYPE::in_edge_iterator>
Chris@16: in_edges(Vertex v, const BOOST_BIDIR_CSR_GRAPH_TYPE& g)
Chris@16: {
Chris@16:   typedef typename BOOST_BIDIR_CSR_GRAPH_TYPE::in_edge_iterator it;
Chris@16:   EdgeIndex v_row_start = g.m_backward.m_rowstart[v];
Chris@16:   EdgeIndex next_row_start = g.m_backward.m_rowstart[v + 1];
Chris@16:   return std::make_pair(it(g, v_row_start),
Chris@16:                         it(g, next_row_start));
Chris@16: }
Chris@16: 
Chris@16: template<BOOST_BIDIR_CSR_GRAPH_TEMPLATE_PARMS>
Chris@16: inline EdgeIndex
Chris@16: in_degree(Vertex v, const BOOST_BIDIR_CSR_GRAPH_TYPE& g)
Chris@16: {
Chris@16:   EdgeIndex v_row_start = g.m_backward.m_rowstart[v];
Chris@16:   EdgeIndex next_row_start = g.m_backward.m_rowstart[v + 1];
Chris@16:   return next_row_start - v_row_start;
Chris@16: }
Chris@16: 
Chris@16: // From AdjacencyGraph
Chris@16: template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
Chris@16: inline std::pair<typename BOOST_CSR_GRAPH_TYPE::adjacency_iterator,
Chris@16:                  typename BOOST_CSR_GRAPH_TYPE::adjacency_iterator>
Chris@16: adjacent_vertices(Vertex v, const BOOST_CSR_GRAPH_TYPE& g)
Chris@16: {
Chris@16:   EdgeIndex v_row_start = g.m_forward.m_rowstart[v];
Chris@16:   EdgeIndex next_row_start = g.m_forward.m_rowstart[v + 1];
Chris@16:   return std::make_pair(g.m_forward.m_column.begin() + v_row_start,
Chris@16:                         g.m_forward.m_column.begin() + next_row_start);
Chris@16: }
Chris@16: 
Chris@16: // Extra, common functions
Chris@16: template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
Chris@16: inline typename graph_traits<BOOST_CSR_GRAPH_TYPE>::vertex_descriptor
Chris@16: vertex(typename graph_traits<BOOST_CSR_GRAPH_TYPE>::vertex_descriptor i,
Chris@16:        const BOOST_CSR_GRAPH_TYPE&)
Chris@16: {
Chris@16:   return i;
Chris@16: }
Chris@16: 
Chris@16: // edge() can be provided in linear time for the new interface
Chris@16: 
Chris@16: template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
Chris@16: inline std::pair<typename BOOST_CSR_GRAPH_TYPE::edge_descriptor, bool>
Chris@16: edge(Vertex i, Vertex j, const BOOST_CSR_GRAPH_TYPE& g)
Chris@16: {
Chris@16:   typedef typename BOOST_CSR_GRAPH_TYPE::out_edge_iterator out_edge_iter;
Chris@16:   std::pair<out_edge_iter, out_edge_iter> range = out_edges(i, g);
Chris@16:   for (; range.first != range.second; ++range.first) {
Chris@16:     if (target(*range.first, g) == j)
Chris@16:       return std::make_pair(*range.first, true);
Chris@16:   }
Chris@16:   return std::make_pair(typename BOOST_CSR_GRAPH_TYPE::edge_descriptor(),
Chris@16:                         false);
Chris@16: }
Chris@16: 
Chris@16: // Find an edge given its index in the graph
Chris@16: template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
Chris@16: inline typename BOOST_CSR_GRAPH_TYPE::edge_descriptor
Chris@16: edge_from_index(EdgeIndex idx, const BOOST_CSR_GRAPH_TYPE& g)
Chris@16: {
Chris@16:   typedef typename std::vector<EdgeIndex>::const_iterator row_start_iter;
Chris@16:   BOOST_ASSERT (idx < num_edges(g));
Chris@16:   row_start_iter src_plus_1 =
Chris@16:     std::upper_bound(g.m_forward.m_rowstart.begin(),
Chris@16:                      g.m_forward.m_rowstart.end(),
Chris@16:                      idx);
Chris@16:     // Get last source whose rowstart is at most idx
Chris@16:     // upper_bound returns this position plus 1
Chris@16:   Vertex src = (src_plus_1 - g.m_forward.m_rowstart.begin()) - 1;
Chris@16:   return typename BOOST_CSR_GRAPH_TYPE::edge_descriptor(src, idx);
Chris@16: }
Chris@16: 
Chris@16: template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
Chris@16: inline EdgeIndex
Chris@16: num_edges(const BOOST_CSR_GRAPH_TYPE& g)
Chris@16: {
Chris@16:   return g.m_forward.m_column.size();
Chris@16: }
Chris@16: 
Chris@16: template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
Chris@16: std::pair<typename BOOST_CSR_GRAPH_TYPE::edge_iterator,
Chris@16:           typename BOOST_CSR_GRAPH_TYPE::edge_iterator>
Chris@16: edges(const BOOST_CSR_GRAPH_TYPE& g)
Chris@16: {
Chris@16:   typedef typename BOOST_CSR_GRAPH_TYPE::edge_iterator ei;
Chris@16:   typedef typename BOOST_CSR_GRAPH_TYPE::edge_descriptor edgedesc;
Chris@16:   if (g.m_forward.m_rowstart.size() == 1 || g.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.m_forward.m_rowstart[src + 1] == 0) ++src;
Chris@16:     return std::make_pair(ei(g, edgedesc(src, 0), g.m_forward.m_rowstart[src + 1]),
Chris@16:                           ei(g, edgedesc(num_vertices(g), g.m_forward.m_column.size()), 0));
Chris@16:   }
Chris@16: }
Chris@16: 
Chris@16: // For Property Graph
Chris@16: 
Chris@16: // Graph properties
Chris@16: template<BOOST_CSR_GRAPH_TEMPLATE_PARMS, class Tag, class Value>
Chris@16: inline void
Chris@16: set_property(BOOST_CSR_GRAPH_TYPE& g, Tag tag, const Value& value)
Chris@16: {
Chris@16:   get_property_value(g.m_property, tag) = value;
Chris@16: }
Chris@16: 
Chris@16: template<BOOST_CSR_GRAPH_TEMPLATE_PARMS, class Tag>
Chris@16: inline
Chris@16: typename graph_property<BOOST_CSR_GRAPH_TYPE, Tag>::type&
Chris@16: get_property(BOOST_CSR_GRAPH_TYPE& g, Tag tag)
Chris@16: {
Chris@16:   return get_property_value(g.m_property, tag);
Chris@16: }
Chris@16: 
Chris@16: template<BOOST_CSR_GRAPH_TEMPLATE_PARMS, class Tag>
Chris@16: inline
Chris@16: const
Chris@16: typename graph_property<BOOST_CSR_GRAPH_TYPE, Tag>::type&
Chris@16: get_property(const BOOST_CSR_GRAPH_TYPE& g, Tag tag)
Chris@16: {
Chris@16:   return get_property_value(g.m_property, tag);
Chris@16: }
Chris@16: 
Chris@16: template <typename G, typename Tag, typename Kind>
Chris@16: struct csr_property_map_helper {};
Chris@16: // Kind == void for invalid property tags, so we can use that to SFINAE out
Chris@16: 
Chris@16: template <BOOST_CSR_GRAPH_TEMPLATE_PARMS, typename Tag>
Chris@16: struct csr_property_map_helper<BOOST_CSR_GRAPH_TYPE, Tag, vertex_property_tag> {
Chris@16:   typedef vertex_all_t all_tag;
Chris@16:   typedef typename property_traits<typename property_map<BOOST_CSR_GRAPH_TYPE, vertex_all_t>::type>::key_type key_type;
Chris@16:   typedef VertexProperty plist_type;
Chris@16:   typedef typename property_map<BOOST_CSR_GRAPH_TYPE, vertex_all_t>::type all_type;
Chris@16:   typedef typename property_map<BOOST_CSR_GRAPH_TYPE, vertex_all_t>::const_type all_const_type;
Chris@16:   typedef transform_value_property_map<detail::lookup_one_property_f<plist_type, Tag>, all_type> type;
Chris@16:   typedef transform_value_property_map<detail::lookup_one_property_f<const plist_type, Tag>, all_const_type> const_type;
Chris@16: };
Chris@16: 
Chris@16: template <BOOST_CSR_GRAPH_TEMPLATE_PARMS, typename Tag>
Chris@16: struct csr_property_map_helper<BOOST_CSR_GRAPH_TYPE, Tag, edge_property_tag> {
Chris@16:   typedef edge_all_t all_tag;
Chris@16:   typedef typename property_traits<typename property_map<BOOST_CSR_GRAPH_TYPE, edge_all_t>::type>::key_type key_type;
Chris@16:   typedef EdgeProperty plist_type;
Chris@16:   typedef typename property_map<BOOST_CSR_GRAPH_TYPE, edge_all_t>::type all_type;
Chris@16:   typedef typename property_map<BOOST_CSR_GRAPH_TYPE, edge_all_t>::const_type all_const_type;
Chris@16:   typedef transform_value_property_map<detail::lookup_one_property_f<plist_type, Tag>, all_type> type;
Chris@16:   typedef transform_value_property_map<detail::lookup_one_property_f<const plist_type, Tag>, all_const_type> const_type;
Chris@16: };
Chris@16: 
Chris@16: template <BOOST_CSR_GRAPH_TEMPLATE_PARMS, typename Tag>
Chris@16: struct csr_property_map_helper<BOOST_CSR_GRAPH_TYPE, Tag, graph_property_tag> {
Chris@16:   typedef graph_all_t all_tag;
Chris@16:   typedef BOOST_CSR_GRAPH_TYPE* key_type;
Chris@16:   typedef GraphProperty plist_type;
Chris@16:   typedef typename property_map<BOOST_CSR_GRAPH_TYPE, graph_all_t>::type all_type;
Chris@16:   typedef typename property_map<BOOST_CSR_GRAPH_TYPE, graph_all_t>::const_type all_const_type;
Chris@16:   typedef transform_value_property_map<detail::lookup_one_property_f<plist_type, Tag>, all_type> type;
Chris@16:   typedef transform_value_property_map<detail::lookup_one_property_f<const plist_type, Tag>, all_const_type> const_type;
Chris@16: };
Chris@16: 
Chris@16: // disable_if isn't truly necessary but required to avoid ambiguity with specializations below
Chris@16: template <BOOST_CSR_GRAPH_TEMPLATE_PARMS, typename Tag>
Chris@16: struct property_map<BOOST_CSR_GRAPH_TYPE, Tag, typename disable_if<detail::is_distributed_selector<Vertex> >::type>:
Chris@16:   csr_property_map_helper<
Chris@16:     BOOST_CSR_GRAPH_TYPE,
Chris@16:     Tag,
Chris@16:     typename detail::property_kind_from_graph<BOOST_CSR_GRAPH_TYPE, Tag>
Chris@16:                ::type> {};
Chris@16: 
Chris@16: template <BOOST_CSR_GRAPH_TEMPLATE_PARMS, typename Tag>
Chris@16: typename property_map<BOOST_CSR_GRAPH_TYPE, Tag>::type
Chris@16: get(Tag tag, BOOST_CSR_GRAPH_TYPE& g) {
Chris@16:   return typename property_map<BOOST_CSR_GRAPH_TYPE, Tag>::type(tag, get(typename property_map<BOOST_CSR_GRAPH_TYPE, Tag>::all_tag(), g));
Chris@16: }
Chris@16: 
Chris@16: template <BOOST_CSR_GRAPH_TEMPLATE_PARMS, typename Tag>
Chris@16: typename property_map<BOOST_CSR_GRAPH_TYPE, Tag>::const_type
Chris@16: get(Tag tag, const BOOST_CSR_GRAPH_TYPE& g) {
Chris@16:   return typename property_map<BOOST_CSR_GRAPH_TYPE, Tag>::const_type(tag, get(typename property_map<BOOST_CSR_GRAPH_TYPE, Tag>::all_tag(), g));
Chris@16: }
Chris@16: 
Chris@16: template <BOOST_CSR_GRAPH_TEMPLATE_PARMS, typename Tag>
Chris@16: typename property_traits<typename property_map<BOOST_CSR_GRAPH_TYPE, Tag>::type>::reference
Chris@16: get(Tag tag, BOOST_CSR_GRAPH_TYPE& g, typename property_map<BOOST_CSR_GRAPH_TYPE, Tag>::key_type k) {
Chris@16:   typedef typename property_map<BOOST_CSR_GRAPH_TYPE, Tag>::all_tag all_tag;
Chris@16:   typedef typename property_map<BOOST_CSR_GRAPH_TYPE, all_tag>::type outer_pm;
Chris@16:   return lookup_one_property<typename property_traits<outer_pm>::value_type, Tag>::lookup(get(all_tag(), g, k), tag);
Chris@16: }
Chris@16: 
Chris@16: template <BOOST_CSR_GRAPH_TEMPLATE_PARMS, typename Tag>
Chris@16: typename property_traits<typename property_map<BOOST_CSR_GRAPH_TYPE, Tag>::const_type>::reference
Chris@16: get(Tag tag, const BOOST_CSR_GRAPH_TYPE& g, typename property_map<BOOST_CSR_GRAPH_TYPE, Tag>::key_type k) {
Chris@16:   typedef typename property_map<BOOST_CSR_GRAPH_TYPE, Tag>::all_tag all_tag;
Chris@16:   typedef typename property_map<BOOST_CSR_GRAPH_TYPE, all_tag>::const_type outer_pm;
Chris@16:   return lookup_one_property<const typename property_traits<outer_pm>::value_type, Tag>::lookup(get(all_tag(), g, k), tag);
Chris@16: }
Chris@16: 
Chris@16: template <BOOST_CSR_GRAPH_TEMPLATE_PARMS, typename Tag>
Chris@16: void
Chris@16: put(Tag tag,
Chris@16:     BOOST_CSR_GRAPH_TYPE& g,
Chris@16:     typename property_map<BOOST_CSR_GRAPH_TYPE, Tag>::key_type k,
Chris@16:     typename lookup_one_property<typename property_map<BOOST_CSR_GRAPH_TYPE, Tag>::plist_type, Tag>::type val) {
Chris@16:   typedef typename property_map<BOOST_CSR_GRAPH_TYPE, Tag>::all_tag all_tag;
Chris@16:   lookup_one_property<typename property_map<BOOST_CSR_GRAPH_TYPE, Tag>::plist_type, Tag>::lookup(get(all_tag(), g, k), tag) = val;
Chris@16: }
Chris@16: 
Chris@16: template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
Chris@16: struct property_map<BOOST_CSR_GRAPH_TYPE, vertex_index_t, typename disable_if<detail::is_distributed_selector<Vertex> >::type>
Chris@16: {
Chris@16:   typedef typed_identity_property_map<Vertex> type;
Chris@16:   typedef type const_type;
Chris@16: };
Chris@16: 
Chris@16: template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
Chris@16: struct property_map<BOOST_CSR_GRAPH_TYPE, edge_index_t, typename disable_if<detail::is_distributed_selector<Vertex> >::type>
Chris@16: {
Chris@16:   typedef detail::csr_edge_index_map<Vertex, EdgeIndex> type;
Chris@16:   typedef type const_type;
Chris@16: };
Chris@16: 
Chris@16: template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
Chris@16: struct property_map<BOOST_CSR_GRAPH_TYPE, vertex_all_t, typename disable_if<detail::is_distributed_selector<Vertex> >::type>
Chris@16: {
Chris@16:   typedef typename BOOST_CSR_GRAPH_TYPE::inherited_vertex_properties::vertex_map_type type;
Chris@16:   typedef typename BOOST_CSR_GRAPH_TYPE::inherited_vertex_properties::const_vertex_map_type const_type;
Chris@16: };
Chris@16: 
Chris@16: template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
Chris@16: struct property_map<BOOST_CSR_GRAPH_TYPE, edge_all_t, typename disable_if<detail::is_distributed_selector<Vertex> >::type>
Chris@16: {
Chris@16:   typedef typename BOOST_CSR_GRAPH_TYPE::forward_type::inherited_edge_properties::edge_map_type type;
Chris@16:   typedef typename BOOST_CSR_GRAPH_TYPE::forward_type::inherited_edge_properties::const_edge_map_type const_type;
Chris@16: };
Chris@16: 
Chris@16: template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
Chris@16: struct property_map<BOOST_CSR_GRAPH_TYPE, graph_all_t, typename disable_if<detail::is_distributed_selector<Vertex> >::type>
Chris@16: {
Chris@16:   typedef boost::ref_property_map<BOOST_CSR_GRAPH_TYPE*, typename BOOST_CSR_GRAPH_TYPE::graph_property_type> type;
Chris@16:   typedef boost::ref_property_map<BOOST_CSR_GRAPH_TYPE*, const typename BOOST_CSR_GRAPH_TYPE::graph_property_type> const_type;
Chris@16: };
Chris@16: 
Chris@16: template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
Chris@16: inline typed_identity_property_map<Vertex>
Chris@16: get(vertex_index_t, const BOOST_CSR_GRAPH_TYPE&)
Chris@16: {
Chris@16:   return typed_identity_property_map<Vertex>();
Chris@16: }
Chris@16: 
Chris@16: template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
Chris@16: inline Vertex
Chris@16: get(vertex_index_t,
Chris@16:     const BOOST_CSR_GRAPH_TYPE&, Vertex v)
Chris@16: {
Chris@16:   return v;
Chris@16: }
Chris@16: 
Chris@16: template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
Chris@16: inline typed_identity_property_map<Vertex>
Chris@16: get(vertex_index_t, BOOST_CSR_GRAPH_TYPE&)
Chris@16: {
Chris@16:   return typed_identity_property_map<Vertex>();
Chris@16: }
Chris@16: 
Chris@16: template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
Chris@16: inline Vertex
Chris@16: get(vertex_index_t,
Chris@16:     BOOST_CSR_GRAPH_TYPE&, Vertex v)
Chris@16: {
Chris@16:   return v;
Chris@16: }
Chris@16: 
Chris@16: template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
Chris@16: inline typename property_map<BOOST_CSR_GRAPH_TYPE, edge_index_t>::const_type
Chris@16: get(edge_index_t, const BOOST_CSR_GRAPH_TYPE&)
Chris@16: {
Chris@16:   typedef typename property_map<BOOST_CSR_GRAPH_TYPE, edge_index_t>::const_type
Chris@16:     result_type;
Chris@16:   return result_type();
Chris@16: }
Chris@16: 
Chris@16: template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
Chris@16: inline EdgeIndex
Chris@16: get(edge_index_t, const BOOST_CSR_GRAPH_TYPE&,
Chris@16:     typename BOOST_CSR_GRAPH_TYPE::edge_descriptor e)
Chris@16: {
Chris@16:   return e.idx;
Chris@16: }
Chris@16: 
Chris@16: template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
Chris@16: inline typename property_map<BOOST_CSR_GRAPH_TYPE, edge_index_t>::const_type
Chris@16: get(edge_index_t, BOOST_CSR_GRAPH_TYPE&)
Chris@16: {
Chris@16:   typedef typename property_map<BOOST_CSR_GRAPH_TYPE, edge_index_t>::const_type
Chris@16:     result_type;
Chris@16:   return result_type();
Chris@16: }
Chris@16: 
Chris@16: template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
Chris@16: inline EdgeIndex
Chris@16: get(edge_index_t, BOOST_CSR_GRAPH_TYPE&,
Chris@16:     typename BOOST_CSR_GRAPH_TYPE::edge_descriptor e)
Chris@16: {
Chris@16:   return e.idx;
Chris@16: }
Chris@16: 
Chris@16: template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
Chris@16: inline typename property_map<BOOST_CSR_GRAPH_TYPE, vertex_all_t>::type
Chris@16: get(vertex_all_t, BOOST_CSR_GRAPH_TYPE& g)
Chris@16: {
Chris@16:   return g.get_vertex_bundle(get(vertex_index, g));
Chris@16: }
Chris@16: 
Chris@16: template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
Chris@16: inline typename property_map<BOOST_CSR_GRAPH_TYPE, vertex_all_t>::const_type
Chris@16: get(vertex_all_t, const BOOST_CSR_GRAPH_TYPE& g)
Chris@16: {
Chris@16:   return g.get_vertex_bundle(get(vertex_index, g));
Chris@16: }
Chris@16: 
Chris@16: template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
Chris@16: inline VertexProperty&
Chris@16: get(vertex_all_t,
Chris@16:     BOOST_CSR_GRAPH_TYPE& g, Vertex v)
Chris@16: {
Chris@16:   return get(vertex_all, g)[v];
Chris@16: }
Chris@16: 
Chris@16: template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
Chris@16: inline const VertexProperty&
Chris@16: get(vertex_all_t,
Chris@16:     const BOOST_CSR_GRAPH_TYPE& g, Vertex v)
Chris@16: {
Chris@16:   return get(vertex_all, g)[v];
Chris@16: }
Chris@16: 
Chris@16: template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
Chris@16: inline void
Chris@16: put(vertex_all_t,
Chris@16:     BOOST_CSR_GRAPH_TYPE& g,
Chris@16:     Vertex v,
Chris@16:     const VertexProperty& val)
Chris@16: {
Chris@16:   put(get(vertex_all, g), v, val);
Chris@16: }
Chris@16: 
Chris@16: template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
Chris@16: inline typename property_map<BOOST_CSR_GRAPH_TYPE, edge_all_t>::type
Chris@16: get(edge_all_t, BOOST_CSR_GRAPH_TYPE& g)
Chris@16: {
Chris@16:   return g.m_forward.get_edge_bundle(get(edge_index, g));
Chris@16: }
Chris@16: 
Chris@16: template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
Chris@16: inline typename property_map<BOOST_CSR_GRAPH_TYPE, edge_all_t>::const_type
Chris@16: get(edge_all_t, const BOOST_CSR_GRAPH_TYPE& g)
Chris@16: {
Chris@16:   return g.m_forward.get_edge_bundle(get(edge_index, g));
Chris@16: }
Chris@16: 
Chris@16: template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
Chris@16: inline EdgeProperty&
Chris@16: get(edge_all_t,
Chris@16:     BOOST_CSR_GRAPH_TYPE& g,
Chris@16:     const typename BOOST_CSR_GRAPH_TYPE::edge_descriptor& e)
Chris@16: {
Chris@16:   return get(edge_all, g)[e];
Chris@16: }
Chris@16: 
Chris@16: template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
Chris@16: inline const EdgeProperty&
Chris@16: get(edge_all_t,
Chris@16:     const BOOST_CSR_GRAPH_TYPE& g,
Chris@16:     const typename BOOST_CSR_GRAPH_TYPE::edge_descriptor& e)
Chris@16: {
Chris@16:   return get(edge_all, g)[e];
Chris@16: }
Chris@16: 
Chris@16: template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
Chris@16: inline void
Chris@16: put(edge_all_t,
Chris@16:     BOOST_CSR_GRAPH_TYPE& g,
Chris@16:     const typename BOOST_CSR_GRAPH_TYPE::edge_descriptor& e,
Chris@16:     const EdgeProperty& val)
Chris@16: {
Chris@16:   put(get(edge_all, g), e, val);
Chris@16: }
Chris@16: 
Chris@16: template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
Chris@16: inline typename property_map<BOOST_CSR_GRAPH_TYPE, graph_all_t>::type
Chris@16: get(graph_all_t, BOOST_CSR_GRAPH_TYPE& g)
Chris@16: {
Chris@16:   return typename property_map<BOOST_CSR_GRAPH_TYPE, graph_all_t>::type(g.m_property);
Chris@16: }
Chris@16: 
Chris@16: template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
Chris@16: inline typename property_map<BOOST_CSR_GRAPH_TYPE, graph_all_t>::const_type
Chris@16: get(graph_all_t, const BOOST_CSR_GRAPH_TYPE& g)
Chris@16: {
Chris@16:   return typename property_map<BOOST_CSR_GRAPH_TYPE, graph_all_t>::const_type(g.m_property);
Chris@16: }
Chris@16: 
Chris@16: template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
Chris@16: inline GraphProperty&
Chris@16: get(graph_all_t,
Chris@16:     BOOST_CSR_GRAPH_TYPE& g,
Chris@16:     BOOST_CSR_GRAPH_TYPE*)
Chris@16: {
Chris@16:   return g.m_property;
Chris@16: }
Chris@16: 
Chris@16: template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
Chris@16: inline const GraphProperty&
Chris@16: get(graph_all_t,
Chris@16:     const BOOST_CSR_GRAPH_TYPE& g,
Chris@16:     BOOST_CSR_GRAPH_TYPE*)
Chris@16: {
Chris@16:   return g.m_property;
Chris@16: }
Chris@16: 
Chris@16: template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
Chris@16: inline void
Chris@16: put(graph_all_t,
Chris@16:     BOOST_CSR_GRAPH_TYPE& g,
Chris@16:     BOOST_CSR_GRAPH_TYPE*,
Chris@16:     const GraphProperty& val)
Chris@16: {
Chris@16:   g.m_property = val;
Chris@16: }
Chris@16: 
Chris@16: #undef BOOST_CSR_GRAPH_TYPE
Chris@16: #undef BOOST_CSR_GRAPH_TEMPLATE_PARMS
Chris@16: #undef BOOST_DIR_CSR_GRAPH_TYPE
Chris@16: #undef BOOST_DIR_CSR_GRAPH_TEMPLATE_PARMS
Chris@16: #undef BOOST_BIDIR_CSR_GRAPH_TYPE
Chris@16: #undef BOOST_BIDIR_CSR_GRAPH_TEMPLATE_PARMS
Chris@16: 
Chris@16: } // end namespace boost
Chris@16: 
Chris@16: #endif // BOOST_GRAPH_COMPRESSED_SPARSE_ROW_GRAPH_HPP