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