Chris@16: // Copyright 2005-2009 The Trustees of Indiana University.
Chris@16: 
Chris@16: // Distributed under the Boost Software License, Version 1.0.
Chris@16: // (See accompanying file LICENSE_1_0.txt or copy at
Chris@16: // http://www.boost.org/LICENSE_1_0.txt)
Chris@16: 
Chris@16: //  Authors: Jeremiah Willcock
Chris@16: //           Douglas Gregor
Chris@16: //           Andrew Lumsdaine
Chris@16: 
Chris@16: // Compressed sparse row graph type internal structure
Chris@16: 
Chris@16: #ifndef BOOST_GRAPH_COMPRESSED_SPARSE_ROW_STRUCT_HPP
Chris@16: #define BOOST_GRAPH_COMPRESSED_SPARSE_ROW_STRUCT_HPP
Chris@16: 
Chris@16: #ifndef BOOST_GRAPH_COMPRESSED_SPARSE_ROW_GRAPH_HPP
Chris@16: #error This file should only be included from boost/graph/compressed_sparse_row_graph.hpp
Chris@16: #endif
Chris@16: 
Chris@16: #include <vector>
Chris@16: #include <utility>
Chris@16: #include <algorithm>
Chris@16: #include <climits>
Chris@16: #include <boost/assert.hpp>
Chris@16: #include <iterator>
Chris@16: #if 0
Chris@16: #include <iostream> // For some debugging code below
Chris@16: #endif
Chris@16: #include <boost/graph/graph_traits.hpp>
Chris@16: #include <boost/graph/properties.hpp>
Chris@16: #include <boost/graph/filtered_graph.hpp> // For keep_all
Chris@16: #include <boost/graph/detail/indexed_properties.hpp>
Chris@16: #include <boost/graph/detail/histogram_sort.hpp>
Chris@16: #include <boost/graph/iteration_macros.hpp>
Chris@16: #include <boost/iterator/counting_iterator.hpp>
Chris@16: #include <boost/iterator/reverse_iterator.hpp>
Chris@16: #include <boost/iterator/zip_iterator.hpp>
Chris@16: #include <boost/iterator/transform_iterator.hpp>
Chris@16: #include <boost/tuple/tuple.hpp>
Chris@16: #include <boost/property_map/property_map.hpp>
Chris@16: #include <boost/integer.hpp>
Chris@16: #include <boost/iterator/iterator_facade.hpp>
Chris@16: #include <boost/mpl/if.hpp>
Chris@16: #include <boost/graph/graph_selectors.hpp>
Chris@16: #include <boost/static_assert.hpp>
Chris@16: #include <boost/functional/hash.hpp>
Chris@16: 
Chris@16: namespace boost {
Chris@16: 
Chris@16: namespace detail {
Chris@16:   // Forward declaration of CSR edge descriptor type, needed to pass to
Chris@16:   // indexed_edge_properties.
Chris@16:   template<typename Vertex, typename EdgeIndex>
Chris@16:   class csr_edge_descriptor;
Chris@16: 
Chris@16:   // Add edge_index property map
Chris@16:   template<typename Vertex, typename EdgeIndex>
Chris@16:   struct csr_edge_index_map
Chris@16:   {
Chris@16:     typedef EdgeIndex                 value_type;
Chris@16:     typedef EdgeIndex                 reference;
Chris@16:     typedef csr_edge_descriptor<Vertex, EdgeIndex> key_type;
Chris@16:     typedef readable_property_map_tag category;
Chris@16:   };
Chris@16: 
Chris@16:   template<typename Vertex, typename EdgeIndex>
Chris@16:   inline EdgeIndex
Chris@16:   get(const csr_edge_index_map<Vertex, EdgeIndex>&,
Chris@16:       const csr_edge_descriptor<Vertex, EdgeIndex>& key)
Chris@16:   {
Chris@16:     return key.idx;
Chris@16:   }
Chris@16: 
Chris@16:   /** Compressed sparse row graph internal structure.
Chris@16:    *
Chris@16:    * Vertex and EdgeIndex should be unsigned integral types and should
Chris@16:    * specialize numeric_limits.
Chris@16:    */
Chris@16:   template <typename EdgeProperty,
Chris@16:             typename Vertex = std::size_t, typename EdgeIndex = Vertex>
Chris@16:   class compressed_sparse_row_structure :
Chris@16:     public detail::indexed_edge_properties<
Chris@16:              compressed_sparse_row_structure<EdgeProperty, Vertex, EdgeIndex>,
Chris@16:              EdgeProperty,
Chris@16:              csr_edge_descriptor<Vertex, EdgeIndex>,
Chris@16:              csr_edge_index_map<Vertex, EdgeIndex> > {
Chris@16:     public:
Chris@16:     typedef detail::indexed_edge_properties<
Chris@16:               compressed_sparse_row_structure<EdgeProperty, Vertex, EdgeIndex>,
Chris@16:               EdgeProperty,
Chris@16:               csr_edge_descriptor<Vertex, EdgeIndex>,
Chris@16:               csr_edge_index_map<Vertex, EdgeIndex> >
Chris@16:       inherited_edge_properties;
Chris@16: 
Chris@16:     typedef Vertex vertices_size_type;
Chris@16:     typedef Vertex vertex_descriptor;
Chris@16:     typedef EdgeIndex edges_size_type;
Chris@16: 
Chris@16:     static vertex_descriptor null_vertex() { return vertex_descriptor(-1); }
Chris@16: 
Chris@16:     std::vector<EdgeIndex> m_rowstart;
Chris@16:     std::vector<Vertex> m_column;
Chris@16: 
Chris@16:     compressed_sparse_row_structure(Vertex numverts = 0)
Chris@16:       : m_rowstart(numverts + 1, EdgeIndex(0)), m_column()
Chris@16:       {}
Chris@16:     
Chris@16:     //  Rebuild graph from number of vertices and multi-pass unsorted list of
Chris@16:     //  edges (filtered using source_pred and mapped using global_to_local)
Chris@16:     template <typename MultiPassInputIterator, typename GlobalToLocal, typename SourcePred>
Chris@16:     void
Chris@16:     assign_unsorted_multi_pass_edges(MultiPassInputIterator edge_begin,
Chris@16:                                      MultiPassInputIterator edge_end,
Chris@16:                                      vertices_size_type numlocalverts,
Chris@16:                                      const GlobalToLocal& global_to_local,
Chris@16:                                      const SourcePred& source_pred) {
Chris@16:       m_rowstart.clear();
Chris@16:       m_rowstart.resize(numlocalverts + 1, 0);
Chris@16:       typedef std::pair<vertices_size_type, vertices_size_type> edge_type;
Chris@16:       typedef boost::transform_iterator<boost::graph::detail::project1st<edge_type>, MultiPassInputIterator> source_iterator;
Chris@16:       typedef boost::transform_iterator<boost::graph::detail::project2nd<edge_type>, MultiPassInputIterator> target_iterator;
Chris@16:       source_iterator sources_begin(edge_begin, boost::graph::detail::project1st<edge_type>());
Chris@16:       source_iterator sources_end(edge_end, boost::graph::detail::project1st<edge_type>());
Chris@16:       target_iterator targets_begin(edge_begin, boost::graph::detail::project2nd<edge_type>());
Chris@16:       target_iterator targets_end(edge_end, boost::graph::detail::project2nd<edge_type>());
Chris@16: 
Chris@16:       boost::graph::detail::count_starts
Chris@16:         (sources_begin, sources_end, m_rowstart.begin(), numlocalverts,
Chris@16:          source_pred, boost::make_property_map_function(global_to_local));
Chris@16: 
Chris@16:       m_column.resize(m_rowstart.back());
Chris@16:       inherited_edge_properties::resize(m_rowstart.back());
Chris@16: 
Chris@16:       boost::graph::detail::histogram_sort
Chris@16:         (sources_begin, sources_end, m_rowstart.begin(), numlocalverts,
Chris@16:          targets_begin, m_column.begin(),
Chris@16:          source_pred, boost::make_property_map_function(global_to_local));
Chris@16:     }
Chris@16: 
Chris@16:     //  Rebuild graph from number of vertices and multi-pass unsorted list of
Chris@16:     //  edges and their properties (filtered using source_pred and mapped using
Chris@16:     //  global_to_local)
Chris@16:     template <typename MultiPassInputIterator, typename EdgePropertyIterator, typename GlobalToLocal, typename SourcePred>
Chris@16:     void
Chris@16:     assign_unsorted_multi_pass_edges(MultiPassInputIterator edge_begin,
Chris@16:                                      MultiPassInputIterator edge_end,
Chris@16:                                      EdgePropertyIterator ep_iter,
Chris@16:                                      vertices_size_type numlocalverts,
Chris@16:                                      const GlobalToLocal& global_to_local,
Chris@16:                                      const SourcePred& source_pred) {
Chris@16:       m_rowstart.clear();
Chris@16:       m_rowstart.resize(numlocalverts + 1, 0);
Chris@16:       typedef std::pair<vertices_size_type, vertices_size_type> edge_type;
Chris@16:       typedef boost::transform_iterator<boost::graph::detail::project1st<edge_type>, MultiPassInputIterator> source_iterator;
Chris@16:       typedef boost::transform_iterator<boost::graph::detail::project2nd<edge_type>, MultiPassInputIterator> target_iterator;
Chris@16:       source_iterator sources_begin(edge_begin, boost::graph::detail::project1st<edge_type>());
Chris@16:       source_iterator sources_end(edge_end, boost::graph::detail::project1st<edge_type>());
Chris@16:       target_iterator targets_begin(edge_begin, boost::graph::detail::project2nd<edge_type>());
Chris@16:       target_iterator targets_end(edge_end, boost::graph::detail::project2nd<edge_type>());
Chris@16: 
Chris@16:       boost::graph::detail::count_starts
Chris@16:         (sources_begin, sources_end, m_rowstart.begin(), numlocalverts,
Chris@16:          source_pred, boost::make_property_map_function(global_to_local));
Chris@16: 
Chris@16:       m_column.resize(m_rowstart.back());
Chris@16:       inherited_edge_properties::resize(m_rowstart.back());
Chris@16: 
Chris@16:       boost::graph::detail::histogram_sort
Chris@16:         (sources_begin, sources_end, m_rowstart.begin(), numlocalverts,
Chris@16:          targets_begin, m_column.begin(),
Chris@16:          ep_iter, inherited_edge_properties::begin(),
Chris@16:          source_pred, boost::make_property_map_function(global_to_local));
Chris@16:     }
Chris@16: 
Chris@16:     //  Assign from number of vertices and sorted list of edges
Chris@16:     template<typename InputIterator, typename GlobalToLocal, typename SourcePred>
Chris@16:     void assign_from_sorted_edges(
Chris@16:            InputIterator edge_begin, InputIterator edge_end,
Chris@16:            const GlobalToLocal& global_to_local,
Chris@16:            const SourcePred& source_pred,
Chris@16:            vertices_size_type numlocalverts,
Chris@16:            edges_size_type numedges_or_zero) {
Chris@16:       m_column.clear();
Chris@16:       m_column.reserve(numedges_or_zero);
Chris@16:       m_rowstart.resize(numlocalverts + 1);
Chris@16:       EdgeIndex current_edge = 0;
Chris@16:       Vertex current_vertex_plus_one = 1;
Chris@16:       m_rowstart[0] = 0;
Chris@16:       for (InputIterator ei = edge_begin; ei != edge_end; ++ei) {
Chris@16:         if (!source_pred(ei->first)) continue;
Chris@16:         Vertex src = get(global_to_local, ei->first);
Chris@16:         Vertex tgt = ei->second;
Chris@16:         for (; current_vertex_plus_one != src + 1; ++current_vertex_plus_one)
Chris@16:           m_rowstart[current_vertex_plus_one] = current_edge;
Chris@16:         m_column.push_back(tgt);
Chris@16:         ++current_edge;
Chris@16:       }
Chris@16: 
Chris@16:       // The remaining vertices have no edges
Chris@16:       for (; current_vertex_plus_one != numlocalverts + 1; ++current_vertex_plus_one)
Chris@16:         m_rowstart[current_vertex_plus_one] = current_edge;
Chris@16: 
Chris@16:       // Default-construct properties for edges
Chris@16:       inherited_edge_properties::resize(m_column.size());
Chris@16:     }
Chris@16: 
Chris@16:     //  Assign from number of vertices and sorted list of edges
Chris@16:     template<typename InputIterator, typename EdgePropertyIterator, typename GlobalToLocal, typename SourcePred>
Chris@16:     void assign_from_sorted_edges(
Chris@16:            InputIterator edge_begin, InputIterator edge_end,
Chris@16:            EdgePropertyIterator ep_iter,
Chris@16:            const GlobalToLocal& global_to_local,
Chris@16:            const SourcePred& source_pred,
Chris@16:            vertices_size_type numlocalverts,
Chris@16:            edges_size_type numedges_or_zero) {
Chris@16:       // Reserving storage in advance can save us lots of time and
Chris@16:       // memory, but it can only be done if we have forward iterators or
Chris@16:       // the user has supplied the number of edges.
Chris@16:       edges_size_type numedges = numedges_or_zero;
Chris@16:       if (numedges == 0) {
Chris@16:         numedges = boost::graph::detail::reserve_count_for_single_pass(edge_begin, edge_end);
Chris@16:       }
Chris@16:       m_column.clear();
Chris@16:       m_column.reserve(numedges_or_zero);
Chris@16:       inherited_edge_properties::clear();
Chris@16:       inherited_edge_properties::reserve(numedges_or_zero);
Chris@16:       m_rowstart.resize(numlocalverts + 1);
Chris@16:       EdgeIndex current_edge = 0;
Chris@16:       Vertex current_vertex_plus_one = 1;
Chris@16:       m_rowstart[0] = 0;
Chris@16:       for (InputIterator ei = edge_begin; ei != edge_end; ++ei, ++ep_iter) {
Chris@16:         if (!source_pred(ei->first)) continue;
Chris@16:         Vertex src = get(global_to_local, ei->first);
Chris@16:         Vertex tgt = ei->second;
Chris@16:         for (; current_vertex_plus_one != src + 1; ++current_vertex_plus_one)
Chris@16:           m_rowstart[current_vertex_plus_one] = current_edge;
Chris@16:         m_column.push_back(tgt);
Chris@16:         inherited_edge_properties::push_back(*ep_iter);
Chris@16:         ++current_edge;
Chris@16:       }
Chris@16: 
Chris@16:       // The remaining vertices have no edges
Chris@16:       for (; current_vertex_plus_one != numlocalverts + 1; ++current_vertex_plus_one)
Chris@16:         m_rowstart[current_vertex_plus_one] = current_edge;
Chris@16:     }
Chris@16: 
Chris@16:     // Replace graph with sources and targets given, sorting them in-place, and
Chris@16:     // using the given global-to-local property map to get local indices from
Chris@16:     // global ones in the two arrays.
Chris@16:     template <typename GlobalToLocal>
Chris@16:     void assign_sources_and_targets_global(std::vector<vertex_descriptor>& sources,
Chris@16:                                            std::vector<vertex_descriptor>& targets,
Chris@16:                                            vertices_size_type numverts,
Chris@16:                                            GlobalToLocal global_to_local) {
Chris@16:       BOOST_ASSERT (sources.size() == targets.size());
Chris@16:       // Do an in-place histogram sort (at least that's what I think it is) to
Chris@16:       // sort sources and targets
Chris@16:       m_rowstart.clear();
Chris@16:       m_rowstart.resize(numverts + 1);
Chris@16:       boost::graph::detail::count_starts
Chris@16:         (sources.begin(), sources.end(), m_rowstart.begin(), numverts,
Chris@16:          keep_all(), boost::make_property_map_function(global_to_local));
Chris@16:       boost::graph::detail::histogram_sort_inplace
Chris@16:         (sources.begin(), m_rowstart.begin(), numverts,
Chris@16:          targets.begin(), boost::make_property_map_function(global_to_local));
Chris@16:       // Now targets is the correct vector (properly sorted by source) for
Chris@16:       // m_column
Chris@16:       m_column.swap(targets);
Chris@16:       inherited_edge_properties::resize(m_rowstart.back());
Chris@16:     }
Chris@16: 
Chris@16:     // Replace graph with sources and targets and edge properties given, sorting
Chris@16:     // them in-place, and using the given global-to-local property map to get
Chris@16:     // local indices from global ones in the two arrays.
Chris@16:     template <typename GlobalToLocal>
Chris@16:     void assign_sources_and_targets_global(std::vector<vertex_descriptor>& sources,
Chris@16:                                            std::vector<vertex_descriptor>& targets,
Chris@16:                                            std::vector<typename inherited_edge_properties::edge_bundled>& edge_props,
Chris@16:                                            vertices_size_type numverts,
Chris@16:                                            GlobalToLocal global_to_local) {
Chris@16:       BOOST_ASSERT (sources.size() == targets.size());
Chris@16:       BOOST_ASSERT (sources.size() == edge_props.size());
Chris@16:       // Do an in-place histogram sort (at least that's what I think it is) to
Chris@16:       // sort sources and targets
Chris@16:       m_rowstart.clear();
Chris@16:       m_rowstart.resize(numverts + 1);
Chris@16:       boost::graph::detail::count_starts
Chris@16:         (sources.begin(), sources.end(), m_rowstart.begin(), numverts,
Chris@16:          keep_all(), boost::make_property_map_function(global_to_local));
Chris@16:       boost::graph::detail::histogram_sort_inplace
Chris@16:         (sources.begin(), m_rowstart.begin(), numverts,
Chris@16:          targets.begin(), edge_props.begin(),
Chris@16:          boost::make_property_map_function(global_to_local));
Chris@16:       // Now targets is the correct vector (properly sorted by source) for
Chris@16:       // m_column, and edge_props for m_edge_properties
Chris@16:       m_column.swap(targets);
Chris@16:       this->m_edge_properties.swap(edge_props);
Chris@16:     }
Chris@16: 
Chris@16:     // From any graph (slow and uses a lot of memory)
Chris@16:     //   Requires IncidenceGraph and a vertex index map
Chris@16:     //   Internal helper function
Chris@16:     //   Note that numedges must be doubled for undirected source graphs
Chris@16:     template<typename Graph, typename VertexIndexMap>
Chris@16:     void
Chris@16:     assign(const Graph& g, const VertexIndexMap& vi,
Chris@16:            vertices_size_type numverts, edges_size_type numedges)
Chris@16:     {
Chris@16:       m_rowstart.resize(numverts + 1);
Chris@16:       m_column.resize(numedges);
Chris@16:       inherited_edge_properties::resize(numedges);
Chris@16:       EdgeIndex current_edge = 0;
Chris@16:       typedef typename boost::graph_traits<Graph>::vertex_descriptor g_vertex;
Chris@16:       typedef typename boost::graph_traits<Graph>::out_edge_iterator
Chris@16:         g_out_edge_iter;
Chris@16: 
Chris@16:       std::vector<g_vertex> ordered_verts_of_g(numverts);
Chris@16:       BGL_FORALL_VERTICES_T(v, g, Graph) {
Chris@16:         ordered_verts_of_g[get(vertex_index, g, v)] = v;
Chris@16:       }
Chris@16:       for (Vertex i = 0; i != numverts; ++i) {
Chris@16:         m_rowstart[i] = current_edge;
Chris@16:         g_vertex v = ordered_verts_of_g[i];
Chris@16:         g_out_edge_iter ei, ei_end;
Chris@16:         for (boost::tie(ei, ei_end) = out_edges(v, g); ei != ei_end; ++ei) {
Chris@16:           m_column[current_edge++] = get(vi, target(*ei, g));
Chris@16:         }
Chris@16:       }
Chris@16:       m_rowstart[numverts] = current_edge;
Chris@16:     }
Chris@16: 
Chris@16:     // Add edges from a sorted (smallest sources first) range of pairs and edge
Chris@16:     // properties
Chris@16:     template <typename BidirectionalIteratorOrig, typename EPIterOrig,
Chris@16:               typename GlobalToLocal>
Chris@16:     void
Chris@16:     add_edges_sorted_internal(
Chris@16:         BidirectionalIteratorOrig first_sorted,
Chris@16:         BidirectionalIteratorOrig last_sorted,
Chris@16:         EPIterOrig ep_iter_sorted,
Chris@16:         const GlobalToLocal& global_to_local) {
Chris@16:       typedef boost::reverse_iterator<BidirectionalIteratorOrig> BidirectionalIterator;
Chris@16:       typedef boost::reverse_iterator<EPIterOrig> EPIter;
Chris@16:       // Flip sequence
Chris@16:       BidirectionalIterator first(last_sorted);
Chris@16:       BidirectionalIterator last(first_sorted);
Chris@16:       typedef Vertex vertex_num;
Chris@16:       typedef EdgeIndex edge_num;
Chris@16:       edge_num new_edge_count = std::distance(first, last);
Chris@16: 
Chris@16:       EPIter ep_iter(ep_iter_sorted);
Chris@16:       std::advance(ep_iter, -(std::ptrdiff_t)new_edge_count);
Chris@16:       edge_num edges_added_before_i = new_edge_count; // Count increment to add to rowstarts
Chris@16:       m_column.resize(m_column.size() + new_edge_count);
Chris@16:       inherited_edge_properties::resize(inherited_edge_properties::size() + new_edge_count);
Chris@16:       BidirectionalIterator current_new_edge = first, prev_new_edge = first;
Chris@16:       EPIter current_new_edge_prop = ep_iter;
Chris@16:       for (vertex_num i_plus_1 = m_rowstart.size() - 1; i_plus_1 > 0; --i_plus_1) {
Chris@16:         vertex_num i = i_plus_1 - 1;
Chris@16:         prev_new_edge = current_new_edge;
Chris@16:         // edges_added_to_this_vertex = #mbrs of new_edges with first == i
Chris@16:         edge_num edges_added_to_this_vertex = 0;
Chris@16:         while (current_new_edge != last) {
Chris@16:           if (get(global_to_local, current_new_edge->first) != i) break;
Chris@16:           ++current_new_edge;
Chris@16:           ++current_new_edge_prop;
Chris@16:           ++edges_added_to_this_vertex;
Chris@16:         }
Chris@16:         edges_added_before_i -= edges_added_to_this_vertex;
Chris@16:         // Invariant: edges_added_before_i = #mbrs of new_edges with first < i
Chris@16:         edge_num old_rowstart = m_rowstart[i];
Chris@16:         edge_num new_rowstart = m_rowstart[i] + edges_added_before_i;
Chris@16:         edge_num old_degree = m_rowstart[i + 1] - m_rowstart[i];
Chris@16:         edge_num new_degree = old_degree + edges_added_to_this_vertex;
Chris@16:         // Move old edges forward (by #new_edges before this i) to make room
Chris@16:         // new_rowstart > old_rowstart, so use copy_backwards
Chris@16:         if (old_rowstart != new_rowstart) {
Chris@16:           std::copy_backward(m_column.begin() + old_rowstart,
Chris@16:                              m_column.begin() + old_rowstart + old_degree,
Chris@16:                              m_column.begin() + new_rowstart + old_degree);
Chris@16:           inherited_edge_properties::move_range(old_rowstart, old_rowstart + old_degree, new_rowstart);
Chris@16:         }
Chris@16:         // Add new edges (reversed because current_new_edge is a
Chris@16:         // const_reverse_iterator)
Chris@16:         BidirectionalIterator temp = current_new_edge;
Chris@16:         EPIter temp_prop = current_new_edge_prop;
Chris@16:         for (; temp != prev_new_edge; ++old_degree) {
Chris@16:           --temp;
Chris@16:           --temp_prop;
Chris@16:           m_column[new_rowstart + old_degree] = temp->second;
Chris@16:           inherited_edge_properties::write_by_index(new_rowstart + old_degree, *temp_prop);
Chris@16:         }
Chris@16:         m_rowstart[i + 1] = new_rowstart + new_degree;
Chris@16:         if (edges_added_before_i == 0) break; // No more edges inserted before this point
Chris@16:         // m_rowstart[i] will be fixed up on the next iteration (to avoid
Chris@16:         // changing the degree of vertex i - 1); the last iteration never changes
Chris@16:         // it (either because of the condition of the break or because
Chris@16:         // m_rowstart[0] is always 0)
Chris@16:       }
Chris@16:     }
Chris@16: 
Chris@16:   };
Chris@16: 
Chris@16:   template<typename Vertex, typename EdgeIndex>
Chris@16:   class csr_edge_descriptor
Chris@16:   {
Chris@16:    public:
Chris@16:     Vertex src;
Chris@16:     EdgeIndex idx;
Chris@16: 
Chris@16:     csr_edge_descriptor(Vertex src, EdgeIndex idx): src(src), idx(idx) {}
Chris@16:     csr_edge_descriptor(): src(0), idx(0) {}
Chris@16: 
Chris@16:     bool operator==(const csr_edge_descriptor& e) const {return idx == e.idx;}
Chris@16:     bool operator!=(const csr_edge_descriptor& e) const {return idx != e.idx;}
Chris@16:     bool operator<(const csr_edge_descriptor& e) const {return idx < e.idx;}
Chris@16:     bool operator>(const csr_edge_descriptor& e) const {return idx > e.idx;}
Chris@16:     bool operator<=(const csr_edge_descriptor& e) const {return idx <= e.idx;}
Chris@16:     bool operator>=(const csr_edge_descriptor& e) const {return idx >= e.idx;}
Chris@16: 
Chris@16:     template<typename Archiver>
Chris@16:     void serialize(Archiver& ar, const unsigned int /*version*/)
Chris@16:     {
Chris@16:       ar & src & idx;
Chris@16:     }
Chris@16:   };
Chris@16: 
Chris@16:   // Common out edge and edge iterators
Chris@16:   template<typename CSRGraph>
Chris@16:   class csr_out_edge_iterator
Chris@16:     : public iterator_facade<csr_out_edge_iterator<CSRGraph>,
Chris@16:                              typename CSRGraph::edge_descriptor,
Chris@16:                              std::random_access_iterator_tag,
Chris@16:                              const typename CSRGraph::edge_descriptor&,
Chris@16:                              typename int_t<CHAR_BIT * sizeof(typename CSRGraph::edges_size_type)>::fast>
Chris@16:   {
Chris@16:    public:
Chris@16:     typedef typename CSRGraph::edges_size_type EdgeIndex;
Chris@16:     typedef typename CSRGraph::edge_descriptor edge_descriptor;
Chris@16:     typedef typename int_t<CHAR_BIT * sizeof(EdgeIndex)>::fast difference_type;
Chris@16: 
Chris@16:     csr_out_edge_iterator() {}
Chris@16:     // Implicit copy constructor OK
Chris@16:     explicit csr_out_edge_iterator(edge_descriptor edge) : m_edge(edge) { }
Chris@16: 
Chris@16:    public: // GCC 4.2.1 doesn't like the private-and-friend thing
Chris@16:     // iterator_facade requirements
Chris@16:     const edge_descriptor& dereference() const { return m_edge; }
Chris@16: 
Chris@16:     bool equal(const csr_out_edge_iterator& other) const
Chris@16:     { return m_edge == other.m_edge; }
Chris@16: 
Chris@16:     void increment() { ++m_edge.idx; }
Chris@16:     void decrement() { --m_edge.idx; }
Chris@16:     void advance(difference_type n) { m_edge.idx += n; }
Chris@16: 
Chris@16:     difference_type distance_to(const csr_out_edge_iterator& other) const
Chris@16:     { return other.m_edge.idx - m_edge.idx; }
Chris@16: 
Chris@16:     edge_descriptor m_edge;
Chris@16: 
Chris@16:     friend class iterator_core_access;
Chris@16:   };
Chris@16: 
Chris@16:   template<typename CSRGraph>
Chris@16:   class csr_edge_iterator
Chris@16:     : public iterator_facade<csr_edge_iterator<CSRGraph>,
Chris@16:                              typename CSRGraph::edge_descriptor,
Chris@16:                              boost::forward_traversal_tag,
Chris@16:                              typename CSRGraph::edge_descriptor>
Chris@16:   {
Chris@16:    private:
Chris@16:     typedef typename CSRGraph::edge_descriptor edge_descriptor;
Chris@16:     typedef typename CSRGraph::edges_size_type EdgeIndex;
Chris@16: 
Chris@16:    public:
Chris@16:     csr_edge_iterator() : rowstart_array(0), current_edge(), end_of_this_vertex(0), total_num_edges(0) {}
Chris@16: 
Chris@16:     csr_edge_iterator(const CSRGraph& graph,
Chris@16:                       edge_descriptor current_edge,
Chris@16:                       EdgeIndex end_of_this_vertex)
Chris@16:       : rowstart_array(&graph.m_forward.m_rowstart[0]),
Chris@16:         current_edge(current_edge),
Chris@16:         end_of_this_vertex(end_of_this_vertex),
Chris@16:         total_num_edges(num_edges(graph)) {}
Chris@16: 
Chris@16:    public: // See above
Chris@16:     friend class boost::iterator_core_access;
Chris@16: 
Chris@16:     edge_descriptor dereference() const {return current_edge;}
Chris@16: 
Chris@16:     bool equal(const csr_edge_iterator& o) const {
Chris@16:       return current_edge == o.current_edge;
Chris@16:     }
Chris@16: 
Chris@16:     void increment() {
Chris@16:       ++current_edge.idx;
Chris@16:       if (current_edge.idx == total_num_edges) return;
Chris@16:       while (current_edge.idx == end_of_this_vertex) {
Chris@16:         ++current_edge.src;
Chris@16:         end_of_this_vertex = rowstart_array[current_edge.src + 1];
Chris@16:       }
Chris@16:     }
Chris@16: 
Chris@16:     const EdgeIndex* rowstart_array;
Chris@16:     edge_descriptor current_edge;
Chris@16:     EdgeIndex end_of_this_vertex;
Chris@16:     EdgeIndex total_num_edges;
Chris@16:   };
Chris@16: 
Chris@16:   // Only for bidirectional graphs
Chris@16:   template<typename CSRGraph>
Chris@16:   class csr_in_edge_iterator
Chris@16:     : public iterator_facade<csr_in_edge_iterator<CSRGraph>,
Chris@16:                              typename CSRGraph::edge_descriptor,
Chris@16:                              boost::forward_traversal_tag,
Chris@16:                              typename CSRGraph::edge_descriptor>
Chris@16:   {
Chris@16:    public:
Chris@16:     typedef typename CSRGraph::edges_size_type EdgeIndex;
Chris@16:     typedef typename CSRGraph::edge_descriptor edge_descriptor;
Chris@16: 
Chris@16:     csr_in_edge_iterator(): m_graph(0) {}
Chris@16:     // Implicit copy constructor OK
Chris@16:     csr_in_edge_iterator(const CSRGraph& graph,
Chris@16:                          EdgeIndex index_in_backward_graph)
Chris@16:       : m_index_in_backward_graph(index_in_backward_graph), m_graph(&graph) {}
Chris@16: 
Chris@16:    public: // See above
Chris@16:     // iterator_facade requirements
Chris@16:     edge_descriptor dereference() const {
Chris@16:       return edge_descriptor(
Chris@16:                m_graph->m_backward.m_column[m_index_in_backward_graph],
Chris@16:                m_graph->m_backward.m_edge_properties[m_index_in_backward_graph]);
Chris@16:     }
Chris@16: 
Chris@16:     bool equal(const csr_in_edge_iterator& other) const
Chris@16:     { return m_index_in_backward_graph == other.m_index_in_backward_graph; }
Chris@16: 
Chris@16:     void increment() { ++m_index_in_backward_graph; }
Chris@16:     void decrement() { --m_index_in_backward_graph; }
Chris@16:     void advance(std::ptrdiff_t n) { m_index_in_backward_graph += n; }
Chris@16: 
Chris@16:     std::ptrdiff_t distance_to(const csr_in_edge_iterator& other) const
Chris@16:     { return other.m_index_in_backward_graph - m_index_in_backward_graph; }
Chris@16: 
Chris@16:     EdgeIndex m_index_in_backward_graph;
Chris@16:     const CSRGraph* m_graph;
Chris@16: 
Chris@16:     friend class iterator_core_access;
Chris@16:   };
Chris@16: 
Chris@16:   template <typename A, typename B>
Chris@16:   struct transpose_pair {
Chris@16:     typedef std::pair<B, A> result_type;
Chris@16:     result_type operator()(const std::pair<A, B>& p) const {
Chris@16:       return result_type(p.second, p.first);
Chris@16:     }
Chris@16:   };
Chris@16: 
Chris@16:   template <typename Iter>
Chris@16:   struct transpose_iterator_gen {
Chris@16:     typedef typename std::iterator_traits<Iter>::value_type vt;
Chris@16:     typedef typename vt::first_type first_type;
Chris@16:     typedef typename vt::second_type second_type;
Chris@16:     typedef transpose_pair<first_type, second_type> transpose;
Chris@16:     typedef boost::transform_iterator<transpose, Iter> type;
Chris@16:     static type make(Iter it) {
Chris@16:       return type(it, transpose());
Chris@16:     }
Chris@16:   };
Chris@16: 
Chris@16:   template <typename Iter>
Chris@16:   typename transpose_iterator_gen<Iter>::type transpose_edges(Iter i) {
Chris@16:     return transpose_iterator_gen<Iter>::make(i);
Chris@16:   }
Chris@16: 
Chris@16:   template<typename GraphT, typename VertexIndexMap>
Chris@16:   class edge_to_index_pair
Chris@16:   {
Chris@16:     typedef typename boost::graph_traits<GraphT>::vertices_size_type
Chris@16:       vertices_size_type;
Chris@16:     typedef typename boost::graph_traits<GraphT>::edge_descriptor edge_descriptor;
Chris@16: 
Chris@16:    public:
Chris@16:     typedef std::pair<vertices_size_type, vertices_size_type> result_type;
Chris@16: 
Chris@16:     edge_to_index_pair() : g(0), index() { }
Chris@16:     edge_to_index_pair(const GraphT& g, const VertexIndexMap& index)
Chris@16:       : g(&g), index(index)
Chris@16:     { }
Chris@16: 
Chris@16:     result_type operator()(edge_descriptor e) const
Chris@16:     {
Chris@16:       return result_type(get(index, source(e, *g)), get(index, target(e, *g)));
Chris@16:     }
Chris@16: 
Chris@16:    private:
Chris@16:     const GraphT* g;
Chris@16:     VertexIndexMap index;
Chris@16:   };
Chris@16: 
Chris@16:   template<typename GraphT, typename VertexIndexMap>
Chris@16:   edge_to_index_pair<GraphT, VertexIndexMap>
Chris@16:   make_edge_to_index_pair(const GraphT& g, const VertexIndexMap& index)
Chris@16:   {
Chris@16:     return edge_to_index_pair<GraphT, VertexIndexMap>(g, index);
Chris@16:   }
Chris@16: 
Chris@16:   template<typename GraphT>
Chris@16:   edge_to_index_pair
Chris@16:     <GraphT,
Chris@16:      typename boost::property_map<GraphT,boost::vertex_index_t>::const_type>
Chris@16:   make_edge_to_index_pair(const GraphT& g)
Chris@16:   {
Chris@16:     typedef typename boost::property_map<GraphT,
Chris@16:                                          boost::vertex_index_t>::const_type
Chris@16:       VertexIndexMap;
Chris@16:     return edge_to_index_pair<GraphT, VertexIndexMap>(g,
Chris@16:                                                      get(boost::vertex_index,
Chris@16:                                                          g));
Chris@16:   }
Chris@16: 
Chris@16:   template<typename GraphT, typename VertexIndexMap, typename Iter>
Chris@16:   boost::transform_iterator<edge_to_index_pair<GraphT, VertexIndexMap>, Iter>
Chris@16:   make_edge_to_index_pair_iter(const GraphT& g, const VertexIndexMap& index,
Chris@16:                                Iter it) {
Chris@16:     return boost::transform_iterator<edge_to_index_pair<GraphT, VertexIndexMap>, Iter>(it, edge_to_index_pair<GraphT, VertexIndexMap>(g, index));
Chris@16:   }
Chris@16: 
Chris@16: } // namespace detail
Chris@16: 
Chris@16:   template<typename Vertex, typename EdgeIndex>
Chris@16:   struct hash<detail::csr_edge_descriptor<Vertex, EdgeIndex> >
Chris@16:   {
Chris@16:     std::size_t operator()
Chris@16:                   (detail::csr_edge_descriptor<Vertex, EdgeIndex> const& x) const
Chris@16:     {
Chris@16:       std::size_t hash = hash_value(x.src);
Chris@16:       hash_combine(hash, x.idx);
Chris@16:       return hash;
Chris@16:     }
Chris@16:   };
Chris@16: 
Chris@16: } // namespace boost
Chris@16: 
Chris@16: #endif // BOOST_GRAPH_COMPRESSED_SPARSE_ROW_STRUCT_HPP