// Copyright 2005-2006 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 <iterator>

#include <boost/graph/graph_traits.hpp>

#include <boost/graph/properties.hpp>

#include <boost/graph/detail/indexed_properties.hpp>

#include <boost/iterator/counting_iterator.hpp>

#include <boost/integer.hpp>

#include <boost/iterator/iterator_facade.hpp>

#include <boost/mpl/if.hpp>

#include <boost/graph/graph_selectors.hpp>

#include <boost/static_assert.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;

/****************************************************************************

 * 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>

// Forward declaration of CSR edge descriptor type, needed to pass to

// indexed_edge_properties.

template<typename Vertex, typename EdgeIndex>

class csr_edge_descriptor;

/** Compressed sparse row graph.

 *

 * Vertex and EdgeIndex should be unsigned integral types and should

 * specialize numeric_limits.

 */

template<typename Directed = directedS, 

         typename VertexProperty = void,

         typename EdgeProperty = void,

         typename GraphProperty = no_property,

         typename Vertex = std::size_t,

         typename EdgeIndex = Vertex>

class compressed_sparse_row_graph

   : public detail::indexed_vertex_properties<BOOST_CSR_GRAPH_TYPE, VertexProperty,

                                              Vertex>,

     public detail::indexed_edge_properties<BOOST_CSR_GRAPH_TYPE, EdgeProperty,

                                            csr_edge_descriptor<Vertex,

                                                                EdgeIndex> >

{

  typedef detail::indexed_vertex_properties<compressed_sparse_row_graph,

                                            VertexProperty, Vertex>

    inherited_vertex_properties;

  typedef detail::indexed_edge_properties<BOOST_CSR_GRAPH_TYPE, EdgeProperty,

                                          csr_edge_descriptor<Vertex, EdgeIndex> >

    inherited_edge_properties;

 public:

  // For Property Graph

  typedef GraphProperty graph_property_type;

 protected:

  template<typename InputIterator>

  void

  maybe_reserve_edge_list_storage(InputIterator, InputIterator,

                                  std::input_iterator_tag)

  {

    // Do nothing: we have no idea how much storage to reserve.

  }

  template<typename InputIterator>

  void

  maybe_reserve_edge_list_storage(InputIterator first, InputIterator last,

                                  std::forward_iterator_tag)

  {

    using std::distance;

    typename std::iterator_traits<InputIterator>::difference_type n =

      distance(first, last);

    m_column.reserve(n);

    inherited_edge_properties::reserve(n);

  }

 public:

  /* At this time, the compressed sparse row graph can only be used to

   * create a directed graph. In the future, bidirectional and

   * undirected CSR graphs will also be supported.

   */

  BOOST_STATIC_ASSERT((is_same<Directed, directedS>::value));

  // Concept requirements:

  // For Graph

  typedef Vertex vertex_descriptor;

  typedef 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

  class out_edge_iterator;

  typedef EdgeIndex degree_size_type;

  // For AdjacencyGraph

  typedef typename std::vector<Vertex>::const_iterator adjacency_iterator;

  // For EdgeListGraph

  class edge_iterator;

  // For BidirectionalGraph (not implemented)

  typedef void in_edge_iterator;

  // For internal use

  typedef csr_graph_tag graph_tag;

  // Constructors

  // Default constructor: an empty graph.

  compressed_sparse_row_graph()

    : m_rowstart(1, EdgeIndex(0)), m_column(0), m_property(),

      m_last_source(0) {}

  //  From number of vertices and sorted list of edges

  template<typename InputIterator>

  compressed_sparse_row_graph(InputIterator edge_begin, InputIterator edge_end,

                              vertices_size_type numverts,

                              edges_size_type numedges = 0,

                              const GraphProperty& prop = GraphProperty())

    : inherited_vertex_properties(numverts), m_rowstart(numverts + 1),

      m_column(0), m_property(prop), m_last_source(numverts)

  {

    // Reserving storage in advance can save us lots of time and

    // memory, but it can only be done if we have forward iterators or

    // the user has supplied the number of edges.

    if (numedges == 0) {

      typedef typename std::iterator_traits<InputIterator>::iterator_category

        category;

      maybe_reserve_edge_list_storage(edge_begin, edge_end, category());

    } else {

      m_column.reserve(numedges);

    }

    EdgeIndex current_edge = 0;

    Vertex current_vertex_plus_one = 1;

    m_rowstart[0] = 0;

    for (InputIterator ei = edge_begin; ei != edge_end; ++ei) {

      Vertex src = ei->first;

      Vertex tgt = ei->second;

      for (; current_vertex_plus_one != src + 1; ++current_vertex_plus_one)

        m_rowstart[current_vertex_plus_one] = current_edge;

      m_column.push_back(tgt);

      ++current_edge;

    }

    // The remaining vertices have no edges

    for (; current_vertex_plus_one != numverts + 1; ++current_vertex_plus_one)

      m_rowstart[current_vertex_plus_one] = current_edge;

    // Default-construct properties for edges

    inherited_edge_properties::resize(m_column.size());

  }

  //  From number of vertices and sorted list of edges

  template<typename InputIterator, typename EdgePropertyIterator>

  compressed_sparse_row_graph(InputIterator edge_begin, InputIterator edge_end,

                              EdgePropertyIterator ep_iter,

                              vertices_size_type numverts,

                              edges_size_type numedges = 0,

                              const GraphProperty& prop = GraphProperty())

    : inherited_vertex_properties(numverts), m_rowstart(numverts + 1),

      m_column(0), m_property(prop), m_last_source(numverts)

  {

    // Reserving storage in advance can save us lots of time and

    // memory, but it can only be done if we have forward iterators or

    // the user has supplied the number of edges.

    if (numedges == 0) {

      typedef typename std::iterator_traits<InputIterator>::iterator_category

        category;

      maybe_reserve_edge_list_storage(edge_begin, edge_end, category());

    } else {

      m_column.reserve(numedges);

    }

    EdgeIndex current_edge = 0;

    Vertex current_vertex_plus_one = 1;

    m_rowstart[0] = 0;

    for (InputIterator ei = edge_begin; ei != edge_end; ++ei, ++ep_iter) {

      Vertex src = ei->first;

      Vertex tgt = ei->second;

      for (; current_vertex_plus_one != src + 1; ++current_vertex_plus_one)

        m_rowstart[current_vertex_plus_one] = current_edge;

      m_column.push_back(tgt);

      inherited_edge_properties::push_back(*ep_iter);

      ++current_edge;

    }

    // The remaining vertices have no edges

    for (; current_vertex_plus_one != numverts + 1; ++current_vertex_plus_one)

      m_rowstart[current_vertex_plus_one] = current_edge;

  }

  //   Requires IncidenceGraph, a vertex index map, and a vertex(n, g) function

  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(), m_last_source(0)

  {

    assign(g, vi, numverts, numedges);

  }

  //   Requires VertexListGraph and EdgeListGraph

  template<typename Graph, typename VertexIndexMap>

  compressed_sparse_row_graph(const Graph& g, const VertexIndexMap& vi)

    : m_property(), m_last_source(0)

  {

    assign(g, vi, num_vertices(g), num_edges(g));

  }

  // Requires vertex index map plus requirements of previous constructor

  template<typename Graph>

  explicit compressed_sparse_row_graph(const Graph& g)

    : m_property(), m_last_source(0)

  {

    assign(g, get(vertex_index, g), num_vertices(g), num_edges(g));

  }

  // From any graph (slow and uses a lot of memory)

  //   Requires IncidenceGraph, a vertex index map, and a vertex(n, g) function

  //   Internal helper function

  template<typename Graph, typename VertexIndexMap>

  void

  assign(const Graph& g, const VertexIndexMap& vi,

         vertices_size_type numverts, edges_size_type numedges)

  {

    inherited_vertex_properties::resize(numverts);

    m_rowstart.resize(numverts + 1);

    m_column.resize(numedges);

    EdgeIndex current_edge = 0;

    typedef typename boost::graph_traits<Graph>::vertex_descriptor g_vertex;

    typedef typename boost::graph_traits<Graph>::edge_descriptor g_edge;

    typedef typename boost::graph_traits<Graph>::out_edge_iterator

      g_out_edge_iter;

    for (Vertex i = 0; i != numverts; ++i) {

      m_rowstart[i] = current_edge;

      g_vertex v = vertex(i, g);

      EdgeIndex num_edges_before_this_vertex = current_edge;

      g_out_edge_iter ei, ei_end;

      for (tie(ei, ei_end) = out_edges(v, g); ei != ei_end; ++ei) {

        m_column[current_edge++] = get(vi, target(*ei, g));

      }

      std::sort(m_column.begin() + num_edges_before_this_vertex,

                m_column.begin() + current_edge);

    }

    m_rowstart[numverts] = current_edge;

    m_last_source = numverts;

  }

  // Requires the above, plus VertexListGraph and EdgeListGraph

  template<typename Graph, typename VertexIndexMap>

  void assign(const Graph& g, const VertexIndexMap& vi)

  {

    assign(g, vi, num_vertices(g), num_edges(g));

  }

  // Requires the above, plus a vertex_index map.

  template<typename Graph>

  void assign(const Graph& g)

  {

    assign(g, get(vertex_index, g), num_vertices(g), num_edges(g));

  }

  using inherited_vertex_properties::operator[];

  using inherited_edge_properties::operator[];

  // private: non-portable, requires friend templates

  inherited_vertex_properties&       vertex_properties()       {return *this;}

  const inherited_vertex_properties& vertex_properties() const {return *this;}

  inherited_edge_properties&       edge_properties()       { return *this; }

  const inherited_edge_properties& edge_properties() const { return *this; }

  std::vector<EdgeIndex> m_rowstart;

  std::vector<Vertex> m_column;

  GraphProperty m_property;

  Vertex m_last_source; // Last source of added edge, plus one

};

template<typename Vertex, typename EdgeIndex>

class csr_edge_descriptor

{

 public:

  Vertex src;

  EdgeIndex idx;

  csr_edge_descriptor(Vertex src, EdgeIndex idx): src(src), idx(idx) {}

  csr_edge_descriptor(): src(0), idx(0) {}

  bool operator==(const csr_edge_descriptor& e) const {return idx == e.idx;}

  bool operator!=(const csr_edge_descriptor& e) const {return idx != e.idx;}

  bool operator<(const csr_edge_descriptor& e) const {return idx < e.idx;}

  bool operator>(const csr_edge_descriptor& e) const {return idx > e.idx;}

  bool operator<=(const csr_edge_descriptor& e) const {return idx <= e.idx;}

  bool operator>=(const csr_edge_descriptor& e) const {return idx >= e.idx;}

};

// Construction functions

template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>

inline Vertex

add_vertex(BOOST_CSR_GRAPH_TYPE& g) {

  Vertex old_num_verts_plus_one = g.m_rowstart.size();

  g.m_rowstart.push_back(EdgeIndex(0));

  return old_num_verts_plus_one - 1;

}

template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>

inline Vertex

add_vertices(typename BOOST_CSR_GRAPH_TYPE::vertices_size_type count, BOOST_CSR_GRAPH_TYPE& g) {

  Vertex old_num_verts_plus_one = g.m_rowstart.size();

  g.m_rowstart.resize(old_num_verts_plus_one + count, EdgeIndex(0));

  return old_num_verts_plus_one - 1;

}

// This function requires that (src, tgt) be lexicographically at least as

// large as the largest edge in the graph so far

template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>

inline typename BOOST_CSR_GRAPH_TYPE::edge_descriptor

add_edge(Vertex src, Vertex tgt, BOOST_CSR_GRAPH_TYPE& g) {

  assert ((g.m_last_source == 0 || src >= g.m_last_source - 1) &&

          src < num_vertices(g));

  EdgeIndex num_edges_orig = g.m_column.size();

  for (; g.m_last_source <= src; ++g.m_last_source)

    g.m_rowstart[g.m_last_source] = num_edges_orig;

  g.m_rowstart[src + 1] = num_edges_orig + 1;

  g.m_column.push_back(tgt);

  typedef typename BOOST_CSR_GRAPH_TYPE::edge_push_back_type push_back_type;

  g.edge_properties().push_back(push_back_type());

  return typename BOOST_CSR_GRAPH_TYPE::edge_descriptor(src, num_edges_orig);

}

// This function requires that (src, tgt) be lexicographically at least as

// large as the largest edge in the graph so far

template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>

inline typename BOOST_CSR_GRAPH_TYPE::edge_descriptor

add_edge(Vertex src, Vertex tgt,

         typename BOOST_CSR_GRAPH_TYPE::edge_bundled const& p,

         BOOST_CSR_GRAPH_TYPE& g) {

  assert ((g.m_last_source == 0 || src >= g.m_last_source - 1) &&

          src < num_vertices(g));

  EdgeIndex num_edges_orig = g.m_column.size();

  for (; g.m_last_source <= src; ++g.m_last_source)

    g.m_rowstart[g.m_last_source] = num_edges_orig;

  g.m_rowstart[src + 1] = num_edges_orig + 1;

  g.m_column.push_back(tgt);

  g.edge_properties().push_back(p);

  return typename BOOST_CSR_GRAPH_TYPE::edge_descriptor(src, num_edges_orig);

}

// From VertexListGraph

template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>

inline Vertex

num_vertices(const BOOST_CSR_GRAPH_TYPE& g) {

  return g.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>

class BOOST_CSR_GRAPH_TYPE::out_edge_iterator

  : public iterator_facade<typename BOOST_CSR_GRAPH_TYPE::out_edge_iterator,

                           typename BOOST_CSR_GRAPH_TYPE::edge_descriptor,

                           std::random_access_iterator_tag,

                           const typename BOOST_CSR_GRAPH_TYPE::edge_descriptor&,

                           typename int_t<CHAR_BIT * sizeof(EdgeIndex)>::fast>

{

 public:

  typedef typename int_t<CHAR_BIT * sizeof(EdgeIndex)>::fast difference_type;

  out_edge_iterator() {}

  // Implicit copy constructor OK

  explicit out_edge_iterator(edge_descriptor edge) : m_edge(edge) { }

 private:

  // iterator_facade requirements

  const edge_descriptor& dereference() const { return m_edge; }

  bool equal(const out_edge_iterator& other) const

  { return m_edge == other.m_edge; }

  void increment() { ++m_edge.idx; }

  void decrement() { ++m_edge.idx; }

  void advance(difference_type n) { m_edge.idx += n; }

  difference_type distance_to(const out_edge_iterator& other) const

  { return other.m_edge.idx - m_edge.idx; }

  edge_descriptor m_edge;

  friend class iterator_core_access;

};

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_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_rowstart[v];

  EdgeIndex next_row_start = g.m_rowstart[v + 1];

  return std::make_pair(it(ed(v, v_row_start)),

                        it(ed(v, (std::max)(v_row_start, 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_rowstart[v];

  EdgeIndex next_row_start = g.m_rowstart[v + 1];

  return (std::max)(v_row_start, 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_rowstart[v];

  EdgeIndex next_row_start = g.m_rowstart[v + 1];

  return std::make_pair(g.m_column.begin() + v_row_start,

                        g.m_column.begin() +

                                (std::max)(v_row_start, 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;

}

// Unlike for an adjacency_matrix, edge_range and edge take lg(out_degree(i))

// time

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>

edge_range(Vertex i, Vertex j, const BOOST_CSR_GRAPH_TYPE& g)

{

  typedef typename std::vector<Vertex>::const_iterator adj_iter;

  typedef typename BOOST_CSR_GRAPH_TYPE::out_edge_iterator out_edge_iter;

  typedef typename BOOST_CSR_GRAPH_TYPE::edge_descriptor edge_desc;

  std::pair<adj_iter, adj_iter> raw_adjacencies = adjacent_vertices(i, g);

  std::pair<adj_iter, adj_iter> adjacencies =

    std::equal_range(raw_adjacencies.first, raw_adjacencies.second, j);

  EdgeIndex idx_begin = adjacencies.first - g.m_column.begin();

  EdgeIndex idx_end = adjacencies.second - g.m_column.begin();

  return std::make_pair(out_edge_iter(edge_desc(i, idx_begin)),

                        out_edge_iter(edge_desc(i, idx_end)));

}

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)

{