compressed_sparse_row_graph.hpp

support vector clustering for vc++

// 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) {