graph/detail/compressed_sparse_row_struct.hpp

0001 // Copyright 2005-2009 The Trustees of Indiana University.
0002
0003 // Distributed under the Boost Software License, Version 1.0.
0004 // (See accompanying file LICENSE_1_0.txt or copy at
0005 // http://www.boost.org/LICENSE_1_0.txt)
0006
0007 //  Authors: Jeremiah Willcock
0008 //           Douglas Gregor
0009 //           Andrew Lumsdaine
0010
0011 // Compressed sparse row graph type internal structure
0012
0013 #ifndef BOOST_GRAPH_COMPRESSED_SPARSE_ROW_STRUCT_HPP
0014 #define BOOST_GRAPH_COMPRESSED_SPARSE_ROW_STRUCT_HPP
0015
0016 #ifndef BOOST_GRAPH_COMPRESSED_SPARSE_ROW_GRAPH_HPP
0017 #error This file should only be included from boost/graph/compressed_sparse_row_graph.hpp
0018 #endif
0019
0020 #include <vector>
0021 #include <utility>
0022 #include <algorithm>
0023 #include <climits>
0024 #include <boost/assert.hpp>
0025 #include <iterator>
0026 #if 0
0027 #include <iostream> // For some debugging code below
0028 #endif
0029 #include <boost/graph/graph_traits.hpp>
0030 #include <boost/graph/properties.hpp>
0031 #include <boost/graph/filtered_graph.hpp> // For keep_all
0032 #include <boost/graph/detail/indexed_properties.hpp>
0033 #include <boost/graph/detail/histogram_sort.hpp>
0034 #include <boost/graph/iteration_macros.hpp>
0035 #include <boost/iterator/counting_iterator.hpp>
0036 #include <boost/iterator/reverse_iterator.hpp>
0037 #include <boost/iterator/zip_iterator.hpp>
0038 #include <boost/iterator/transform_iterator.hpp>
0039 #include <boost/tuple/tuple.hpp>
0040 #include <boost/property_map/property_map.hpp>
0041 #include <boost/integer.hpp>
0042 #include <boost/iterator/iterator_facade.hpp>
0043 #include <boost/mpl/if.hpp>
0044 #include <boost/graph/graph_selectors.hpp>
0045 #include <boost/static_assert.hpp>
0046 #include <boost/functional/hash.hpp>
0047
0048 namespace boost
0049 {
0050
0051 namespace detail
0052 {
0053     // Forward declaration of CSR edge descriptor type, needed to pass to
0054     // indexed_edge_properties.
0055     template < typename Vertex, typename EdgeIndex > class csr_edge_descriptor;
0056
0057     // Add edge_index property map
0058     template < typename Vertex, typename EdgeIndex > struct csr_edge_index_map
0059     {
0060         typedef EdgeIndex value_type;
0061         typedef EdgeIndex reference;
0062         typedef csr_edge_descriptor< Vertex, EdgeIndex > key_type;
0063         typedef readable_property_map_tag category;
0064     };
0065
0066     template < typename Vertex, typename EdgeIndex >
0067     inline EdgeIndex get(const csr_edge_index_map< Vertex, EdgeIndex >&,
0068         const csr_edge_descriptor< Vertex, EdgeIndex >& key)
0069     {
0070         return key.idx;
0071     }
0072
0073     /** Compressed sparse row graph internal structure.
0074      *
0075      * Vertex and EdgeIndex should be unsigned integral types and should
0076      * specialize numeric_limits.
0077      */
0078     template < typename EdgeProperty, typename Vertex = std::size_t,
0079         typename EdgeIndex = Vertex >
0080     class compressed_sparse_row_structure
0081     : public detail::indexed_edge_properties<
0082           compressed_sparse_row_structure< EdgeProperty, Vertex, EdgeIndex >,
0083           EdgeProperty, csr_edge_descriptor< Vertex, EdgeIndex >,
0084           csr_edge_index_map< Vertex, EdgeIndex > >
0085     {
0086     public:
0087         typedef detail::indexed_edge_properties<
0088             compressed_sparse_row_structure< EdgeProperty, Vertex, EdgeIndex >,
0089             EdgeProperty, csr_edge_descriptor< Vertex, EdgeIndex >,
0090             csr_edge_index_map< Vertex, EdgeIndex > >
0091             inherited_edge_properties;
0092
0093         typedef Vertex vertices_size_type;
0094         typedef Vertex vertex_descriptor;
0095         typedef EdgeIndex edges_size_type;
0096
0097         static vertex_descriptor null_vertex() { return vertex_descriptor(-1); }
0098
0099         std::vector< EdgeIndex > m_rowstart;
0100         std::vector< Vertex > m_column;
0101
0102         compressed_sparse_row_structure(Vertex numverts = 0)
0103         : m_rowstart(numverts + 1, EdgeIndex(0)), m_column()
0104         {
0105         }
0106
0107         //  Rebuild graph from number of vertices and multi-pass unsorted list
0108         //  of edges (filtered using source_pred and mapped using
0109         //  global_to_local)
0110         template < typename MultiPassInputIterator, typename GlobalToLocal,
0111             typename SourcePred >
0112         void assign_unsorted_multi_pass_edges(MultiPassInputIterator edge_begin,
0113             MultiPassInputIterator edge_end, vertices_size_type numlocalverts,
0114             const GlobalToLocal& global_to_local, const SourcePred& source_pred)
0115         {
0116             m_rowstart.clear();
0117             m_rowstart.resize(numlocalverts + 1, 0);
0118             typedef std::pair< vertices_size_type, vertices_size_type >
0119                 edge_type;
0120             typedef boost::transform_iterator<
0121                 boost::graph::detail::project1st< edge_type >,
0122                 MultiPassInputIterator >
0123                 source_iterator;
0124             typedef boost::transform_iterator<
0125                 boost::graph::detail::project2nd< edge_type >,
0126                 MultiPassInputIterator >
0127                 target_iterator;
0128             source_iterator sources_begin(
0129                 edge_begin, boost::graph::detail::project1st< edge_type >());
0130             source_iterator sources_end(
0131                 edge_end, boost::graph::detail::project1st< edge_type >());
0132             target_iterator targets_begin(
0133                 edge_begin, boost::graph::detail::project2nd< edge_type >());
0134             target_iterator targets_end(
0135                 edge_end, boost::graph::detail::project2nd< edge_type >());
0136
0137             boost::graph::detail::count_starts(sources_begin, sources_end,
0138                 m_rowstart.begin(), numlocalverts, source_pred,
0139                 boost::make_property_map_function(global_to_local));
0140
0141             m_column.resize(m_rowstart.back());
0142             inherited_edge_properties::resize(m_rowstart.back());
0143
0144             boost::graph::detail::histogram_sort(sources_begin, sources_end,
0145                 m_rowstart.begin(), numlocalverts, targets_begin,
0146                 m_column.begin(), source_pred,
0147                 boost::make_property_map_function(global_to_local));
0148         }
0149
0150         //  Rebuild graph from number of vertices and multi-pass unsorted list
0151         //  of edges and their properties (filtered using source_pred and mapped
0152         //  using global_to_local)
0153         template < typename MultiPassInputIterator,
0154             typename EdgePropertyIterator, typename GlobalToLocal,
0155             typename SourcePred >
0156         void assign_unsorted_multi_pass_edges(MultiPassInputIterator edge_begin,
0157             MultiPassInputIterator edge_end, EdgePropertyIterator ep_iter,
0158             vertices_size_type numlocalverts,
0159             const GlobalToLocal& global_to_local, const SourcePred& source_pred)
0160         {
0161             m_rowstart.clear();
0162             m_rowstart.resize(numlocalverts + 1, 0);
0163             typedef std::pair< vertices_size_type, vertices_size_type >
0164                 edge_type;
0165             typedef boost::transform_iterator<
0166                 boost::graph::detail::project1st< edge_type >,
0167                 MultiPassInputIterator >
0168                 source_iterator;
0169             typedef boost::transform_iterator<
0170                 boost::graph::detail::project2nd< edge_type >,
0171                 MultiPassInputIterator >
0172                 target_iterator;
0173             source_iterator sources_begin(
0174                 edge_begin, boost::graph::detail::project1st< edge_type >());
0175             source_iterator sources_end(
0176                 edge_end, boost::graph::detail::project1st< edge_type >());
0177             target_iterator targets_begin(
0178                 edge_begin, boost::graph::detail::project2nd< edge_type >());
0179             target_iterator targets_end(
0180                 edge_end, boost::graph::detail::project2nd< edge_type >());
0181
0182             boost::graph::detail::count_starts(sources_begin, sources_end,
0183                 m_rowstart.begin(), numlocalverts, source_pred,
0184                 boost::make_property_map_function(global_to_local));
0185
0186             m_column.resize(m_rowstart.back());
0187             inherited_edge_properties::resize(m_rowstart.back());
0188
0189             boost::graph::detail::histogram_sort(sources_begin, sources_end,
0190                 m_rowstart.begin(), numlocalverts, targets_begin,
0191                 m_column.begin(), ep_iter, inherited_edge_properties::begin(),
0192                 source_pred,
0193                 boost::make_property_map_function(global_to_local));
0194         }
0195
0196         //  Assign from number of vertices and sorted list of edges
0197         template < typename InputIterator, typename GlobalToLocal,
0198             typename SourcePred >
0199         void assign_from_sorted_edges(InputIterator edge_begin,
0200             InputIterator edge_end, const GlobalToLocal& global_to_local,
0201             const SourcePred& source_pred, vertices_size_type numlocalverts,
0202             edges_size_type numedges_or_zero)
0203         {
0204             m_column.clear();
0205             m_column.reserve(numedges_or_zero);
0206             m_rowstart.resize(numlocalverts + 1);
0207             EdgeIndex current_edge = 0;
0208             Vertex current_vertex_plus_one = 1;
0209             m_rowstart[0] = 0;
0210             for (InputIterator ei = edge_begin; ei != edge_end; ++ei)
0211             {
0212                 if (!source_pred(ei->first))
0213                     continue;
0214                 Vertex src = get(global_to_local, ei->first);
0215                 Vertex tgt = ei->second;
0216                 for (; current_vertex_plus_one != src + 1;
0217                      ++current_vertex_plus_one)
0218                     m_rowstart[current_vertex_plus_one] = current_edge;
0219                 m_column.push_back(tgt);
0220                 ++current_edge;
0221             }
0222
0223             // The remaining vertices have no edges
0224             for (; current_vertex_plus_one != numlocalverts + 1;
0225                  ++current_vertex_plus_one)
0226                 m_rowstart[current_vertex_plus_one] = current_edge;
0227
0228             // Default-construct properties for edges
0229             inherited_edge_properties::resize(m_column.size());
0230         }
0231
0232         //  Assign from number of vertices and sorted list of edges
0233         template < typename InputIterator, typename EdgePropertyIterator,
0234             typename GlobalToLocal, typename SourcePred >
0235         void assign_from_sorted_edges(InputIterator edge_begin,
0236             InputIterator edge_end, EdgePropertyIterator ep_iter,
0237             const GlobalToLocal& global_to_local, const SourcePred& source_pred,
0238             vertices_size_type numlocalverts, edges_size_type numedges_or_zero)
0239         {
0240             // Reserving storage in advance can save us lots of time and
0241             // memory, but it can only be done if we have forward iterators or
0242             // the user has supplied the number of edges.
0243             edges_size_type numedges = numedges_or_zero;
0244             if (numedges == 0)
0245             {
0246                 numedges = boost::graph::detail::reserve_count_for_single_pass(
0247                     edge_begin, edge_end);
0248             }
0249             m_column.clear();
0250             m_column.reserve(numedges_or_zero);
0251             inherited_edge_properties::clear();
0252             inherited_edge_properties::reserve(numedges_or_zero);
0253             m_rowstart.resize(numlocalverts + 1);
0254             EdgeIndex current_edge = 0;
0255             Vertex current_vertex_plus_one = 1;
0256             m_rowstart[0] = 0;
0257             for (InputIterator ei = edge_begin; ei != edge_end; ++ei, ++ep_iter)
0258             {
0259                 if (!source_pred(ei->first))
0260                     continue;
0261                 Vertex src = get(global_to_local, ei->first);
0262                 Vertex tgt = ei->second;
0263                 for (; current_vertex_plus_one != src + 1;
0264                      ++current_vertex_plus_one)
0265                     m_rowstart[current_vertex_plus_one] = current_edge;
0266                 m_column.push_back(tgt);
0267                 inherited_edge_properties::push_back(*ep_iter);
0268                 ++current_edge;
0269             }
0270
0271             // The remaining vertices have no edges
0272             for (; current_vertex_plus_one != numlocalverts + 1;
0273                  ++current_vertex_plus_one)
0274                 m_rowstart[current_vertex_plus_one] = current_edge;
0275         }
0276
0277         // Replace graph with sources and targets given, sorting them in-place,
0278         // and using the given global-to-local property map to get local indices
0279         // from global ones in the two arrays.
0280         template < typename GlobalToLocal >
0281         void assign_sources_and_targets_global(
0282             std::vector< vertex_descriptor >& sources,
0283             std::vector< vertex_descriptor >& targets,
0284             vertices_size_type numverts, GlobalToLocal global_to_local)
0285         {
0286             BOOST_ASSERT(sources.size() == targets.size());
0287             // Do an in-place histogram sort (at least that's what I think it
0288             // is) to sort sources and targets
0289             m_rowstart.clear();
0290             m_rowstart.resize(numverts + 1);
0291             boost::graph::detail::count_starts(sources.begin(), sources.end(),
0292                 m_rowstart.begin(), numverts, keep_all(),
0293                 boost::make_property_map_function(global_to_local));
0294             boost::graph::detail::histogram_sort_inplace(sources.begin(),
0295                 m_rowstart.begin(), numverts, targets.begin(),
0296                 boost::make_property_map_function(global_to_local));
0297             // Now targets is the correct vector (properly sorted by source) for
0298             // m_column
0299             m_column.swap(targets);
0300             inherited_edge_properties::resize(m_rowstart.back());
0301         }
0302
0303         // Replace graph with sources and targets and edge properties given,
0304         // sorting them in-place, and using the given global-to-local property
0305         // map to get local indices from global ones in the two arrays.
0306         template < typename GlobalToLocal >
0307         void assign_sources_and_targets_global(
0308             std::vector< vertex_descriptor >& sources,
0309             std::vector< vertex_descriptor >& targets,
0310             std::vector< typename inherited_edge_properties::edge_bundled >&
0311                 edge_props,
0312             vertices_size_type numverts, GlobalToLocal global_to_local)
0313         {
0314             BOOST_ASSERT(sources.size() == targets.size());
0315             BOOST_ASSERT(sources.size() == edge_props.size());
0316             // Do an in-place histogram sort (at least that's what I think it
0317             // is) to sort sources and targets
0318             m_rowstart.clear();
0319             m_rowstart.resize(numverts + 1);
0320             boost::graph::detail::count_starts(sources.begin(), sources.end(),
0321                 m_rowstart.begin(), numverts, keep_all(),
0322                 boost::make_property_map_function(global_to_local));
0323             boost::graph::detail::histogram_sort_inplace(sources.begin(),
0324                 m_rowstart.begin(), numverts, targets.begin(),
0325                 edge_props.begin(),
0326                 boost::make_property_map_function(global_to_local));
0327             // Now targets is the correct vector (properly sorted by source) for
0328             // m_column, and edge_props for m_edge_properties
0329             m_column.swap(targets);
0330             this->m_edge_properties.swap(edge_props);
0331         }
0332
0333         // From any graph (slow and uses a lot of memory)
0334         //   Requires IncidenceGraph and a vertex index map
0335         //   Internal helper function
0336         //   Note that numedges must be doubled for undirected source graphs
0337         template < typename Graph, typename VertexIndexMap >
0338         void assign(const Graph& g, const VertexIndexMap& vi,
0339             vertices_size_type numverts, edges_size_type numedges)
0340         {
0341             m_rowstart.resize(numverts + 1);
0342             m_column.resize(numedges);
0343             inherited_edge_properties::resize(numedges);
0344             EdgeIndex current_edge = 0;
0345             typedef typename boost::graph_traits< Graph >::vertex_descriptor
0346                 g_vertex;
0347             typedef typename boost::graph_traits< Graph >::out_edge_iterator
0348                 g_out_edge_iter;
0349
0350             std::vector< g_vertex > ordered_verts_of_g(numverts);
0351             BGL_FORALL_VERTICES_T(v, g, Graph)
0352             {
0353                 ordered_verts_of_g[get(vertex_index, g, v)] = v;
0354             }
0355             for (Vertex i = 0; i != numverts; ++i)
0356             {
0357                 m_rowstart[i] = current_edge;
0358                 g_vertex v = ordered_verts_of_g[i];
0359                 g_out_edge_iter ei, ei_end;
0360                 for (boost::tie(ei, ei_end) = out_edges(v, g); ei != ei_end;
0361                      ++ei)
0362                 {
0363                     m_column[current_edge++] = get(vi, target(*ei, g));
0364                 }
0365             }
0366             m_rowstart[numverts] = current_edge;
0367         }
0368
0369         // Add edges from a sorted (smallest sources first) range of pairs and
0370         // edge properties
0371         template < typename BidirectionalIteratorOrig, typename EPIterOrig,
0372             typename GlobalToLocal >
0373         void add_edges_sorted_internal(BidirectionalIteratorOrig first_sorted,
0374             BidirectionalIteratorOrig last_sorted, EPIterOrig ep_iter_sorted,
0375             const GlobalToLocal& global_to_local)
0376         {
0377             typedef boost::reverse_iterator< BidirectionalIteratorOrig >
0378                 BidirectionalIterator;
0379             typedef boost::reverse_iterator< EPIterOrig > EPIter;
0380             // Flip sequence
0381             BidirectionalIterator first(last_sorted);
0382             BidirectionalIterator last(first_sorted);
0383             typedef Vertex vertex_num;
0384             typedef EdgeIndex edge_num;
0385             edge_num new_edge_count = std::distance(first, last);
0386
0387             EPIter ep_iter(ep_iter_sorted);
0388             std::advance(ep_iter, -(std::ptrdiff_t)new_edge_count);
0389             edge_num edges_added_before_i
0390                 = new_edge_count; // Count increment to add to rowstarts
0391             m_column.resize(m_column.size() + new_edge_count);
0392             inherited_edge_properties::resize(
0393                 inherited_edge_properties::size() + new_edge_count);
0394             BidirectionalIterator current_new_edge = first,
0395                                   prev_new_edge = first;
0396             EPIter current_new_edge_prop = ep_iter;
0397             for (vertex_num i_plus_1 = m_rowstart.size() - 1; i_plus_1 > 0;
0398                  --i_plus_1)
0399             {
0400                 vertex_num i = i_plus_1 - 1;
0401                 prev_new_edge = current_new_edge;
0402                 // edges_added_to_this_vertex = #mbrs of new_edges with first ==
0403                 // i
0404                 edge_num edges_added_to_this_vertex = 0;
0405                 while (current_new_edge != last)
0406                 {
0407                     if (get(global_to_local, current_new_edge->first) != i)
0408                         break;
0409                     ++current_new_edge;
0410                     ++current_new_edge_prop;
0411                     ++edges_added_to_this_vertex;
0412                 }
0413                 edges_added_before_i -= edges_added_to_this_vertex;
0414                 // Invariant: edges_added_before_i = #mbrs of new_edges with
0415                 // first < i
0416                 edge_num old_rowstart = m_rowstart[i];
0417                 edge_num new_rowstart = m_rowstart[i] + edges_added_before_i;
0418                 edge_num old_degree = m_rowstart[i + 1] - m_rowstart[i];
0419                 edge_num new_degree = old_degree + edges_added_to_this_vertex;
0420                 // Move old edges forward (by #new_edges before this i) to make
0421                 // room new_rowstart > old_rowstart, so use copy_backwards
0422                 if (old_rowstart != new_rowstart)
0423                 {
0424                     std::copy_backward(m_column.begin() + old_rowstart,
0425                         m_column.begin() + old_rowstart + old_degree,
0426                         m_column.begin() + new_rowstart + old_degree);
0427                     inherited_edge_properties::move_range(
0428                         old_rowstart, old_rowstart + old_degree, new_rowstart);
0429                 }
0430                 // Add new edges (reversed because current_new_edge is a
0431                 // const_reverse_iterator)
0432                 BidirectionalIterator temp = current_new_edge;
0433                 EPIter temp_prop = current_new_edge_prop;
0434                 for (; temp != prev_new_edge; ++old_degree)
0435                 {
0436                     --temp;
0437                     --temp_prop;
0438                     m_column[new_rowstart + old_degree] = temp->second;
0439                     inherited_edge_properties::write_by_index(
0440                         new_rowstart + old_degree, *temp_prop);
0441                 }
0442                 m_rowstart[i + 1] = new_rowstart + new_degree;
0443                 if (edges_added_before_i == 0)
0444                     break; // No more edges inserted before this point
0445                 // m_rowstart[i] will be fixed up on the next iteration (to
0446                 // avoid changing the degree of vertex i - 1); the last
0447                 // iteration never changes it (either because of the condition
0448                 // of the break or because m_rowstart[0] is always 0)
0449             }
0450         }
0451     };
0452
0453     template < typename Vertex, typename EdgeIndex > class csr_edge_descriptor
0454     {
0455     public:
0456         Vertex src;
0457         EdgeIndex idx;
0458
0459         csr_edge_descriptor(Vertex src, EdgeIndex idx) : src(src), idx(idx) {}
0460         csr_edge_descriptor() : src(0), idx(0) {}
0461
0462         bool operator==(const csr_edge_descriptor& e) const
0463         {
0464             return idx == e.idx;
0465         }
0466         bool operator!=(const csr_edge_descriptor& e) const
0467         {
0468             return idx != e.idx;
0469         }
0470         bool operator<(const csr_edge_descriptor& e) const
0471         {
0472             return idx < e.idx;
0473         }
0474         bool operator>(const csr_edge_descriptor& e) const
0475         {
0476             return idx > e.idx;
0477         }
0478         bool operator<=(const csr_edge_descriptor& e) const
0479         {
0480             return idx <= e.idx;
0481         }
0482         bool operator>=(const csr_edge_descriptor& e) const
0483         {
0484             return idx >= e.idx;
0485         }
0486
0487         template < typename Archiver >
0488         void serialize(Archiver& ar, const unsigned int /*version*/)
0489         {
0490             ar& src& idx;
0491         }
0492     };
0493
0494     // Common out edge and edge iterators
0495     template < typename CSRGraph >
0496     class csr_out_edge_iterator
0497     : public iterator_facade< csr_out_edge_iterator< CSRGraph >,
0498           typename CSRGraph::edge_descriptor, std::random_access_iterator_tag,
0499           const typename CSRGraph::edge_descriptor&,
0500           typename int_t< CHAR_BIT
0501               * sizeof(typename CSRGraph::edges_size_type) >::fast >
0502     {
0503     public:
0504         typedef typename CSRGraph::edges_size_type EdgeIndex;
0505         typedef typename CSRGraph::edge_descriptor edge_descriptor;
0506         typedef typename int_t< CHAR_BIT * sizeof(EdgeIndex) >::fast
0507             difference_type;
0508
0509         csr_out_edge_iterator() {}
0510         // Implicit copy constructor OK
0511         explicit csr_out_edge_iterator(edge_descriptor edge) : m_edge(edge) {}
0512
0513     public: // GCC 4.2.1 doesn't like the private-and-friend thing
0514         // iterator_facade requirements
0515         const edge_descriptor& dereference() const { return m_edge; }
0516
0517         bool equal(const csr_out_edge_iterator& other) const
0518         {
0519             return m_edge == other.m_edge;
0520         }
0521
0522         void increment() { ++m_edge.idx; }
0523         void decrement() { --m_edge.idx; }
0524         void advance(difference_type n) { m_edge.idx += n; }
0525
0526         difference_type distance_to(const csr_out_edge_iterator& other) const
0527         {
0528             return other.m_edge.idx - m_edge.idx;
0529         }
0530
0531         edge_descriptor m_edge;
0532
0533         friend class boost::iterator_core_access;
0534     };
0535
0536     template < typename CSRGraph >
0537     class csr_edge_iterator
0538     : public iterator_facade< csr_edge_iterator< CSRGraph >,
0539           typename CSRGraph::edge_descriptor, boost::forward_traversal_tag,
0540           typename CSRGraph::edge_descriptor >
0541     {
0542     private:
0543         typedef typename CSRGraph::edge_descriptor edge_descriptor;
0544         typedef typename CSRGraph::edges_size_type EdgeIndex;
0545
0546     public:
0547         csr_edge_iterator()
0548         : rowstart_array(0)
0549         , current_edge()
0550         , end_of_this_vertex(0)
0551         , total_num_edges(0)
0552         {
0553         }
0554
0555         csr_edge_iterator(const CSRGraph& graph, edge_descriptor current_edge,
0556             EdgeIndex end_of_this_vertex)
0557         : rowstart_array(&graph.m_forward.m_rowstart[0])
0558         , current_edge(current_edge)
0559         , end_of_this_vertex(end_of_this_vertex)
0560         , total_num_edges(num_edges(graph))
0561         {
0562         }
0563
0564     public: // See above
0565         friend class boost::iterator_core_access;
0566
0567         edge_descriptor dereference() const { return current_edge; }
0568
0569         bool equal(const csr_edge_iterator& o) const
0570         {
0571             return current_edge == o.current_edge;
0572         }
0573
0574         void increment()
0575         {
0576             ++current_edge.idx;
0577             if (current_edge.idx == total_num_edges)
0578                 return;
0579             while (current_edge.idx == end_of_this_vertex)
0580             {
0581                 ++current_edge.src;
0582                 end_of_this_vertex = rowstart_array[current_edge.src + 1];
0583             }
0584         }
0585
0586         const EdgeIndex* rowstart_array;
0587         edge_descriptor current_edge;
0588         EdgeIndex end_of_this_vertex;
0589         EdgeIndex total_num_edges;
0590     };
0591
0592     // Only for bidirectional graphs
0593     template < typename CSRGraph >
0594     class csr_in_edge_iterator
0595     : public iterator_facade< csr_in_edge_iterator< CSRGraph >,
0596           typename CSRGraph::edge_descriptor, boost::forward_traversal_tag,
0597           typename CSRGraph::edge_descriptor >
0598     {
0599     public:
0600         typedef typename CSRGraph::edges_size_type EdgeIndex;
0601         typedef typename CSRGraph::edge_descriptor edge_descriptor;
0602
0603         csr_in_edge_iterator() : m_graph(0) {}
0604         // Implicit copy constructor OK
0605         csr_in_edge_iterator(
0606             const CSRGraph& graph, EdgeIndex index_in_backward_graph)
0607         : m_index_in_backward_graph(index_in_backward_graph), m_graph(&graph)
0608         {
0609         }
0610
0611     public: // See above
0612         // iterator_facade requirements
0613         edge_descriptor dereference() const
0614         {
0615             return edge_descriptor(
0616                 m_graph->m_backward.m_column[m_index_in_backward_graph],
0617                 m_graph->m_backward
0618                     .m_edge_properties[m_index_in_backward_graph]);
0619         }
0620
0621         bool equal(const csr_in_edge_iterator& other) const
0622         {
0623             return m_index_in_backward_graph == other.m_index_in_backward_graph;
0624         }
0625
0626         void increment() { ++m_index_in_backward_graph; }
0627         void decrement() { --m_index_in_backward_graph; }
0628         void advance(std::ptrdiff_t n) { m_index_in_backward_graph += n; }
0629
0630         std::ptrdiff_t distance_to(const csr_in_edge_iterator& other) const
0631         {
0632             return other.m_index_in_backward_graph - m_index_in_backward_graph;
0633         }
0634
0635         EdgeIndex m_index_in_backward_graph;
0636         const CSRGraph* m_graph;
0637
0638         friend class boost::iterator_core_access;
0639     };
0640
0641     template < typename A, typename B > struct transpose_pair
0642     {
0643         typedef std::pair< B, A > result_type;
0644         result_type operator()(const std::pair< A, B >& p) const
0645         {
0646             return result_type(p.second, p.first);
0647         }
0648     };
0649
0650     template < typename Iter > struct transpose_iterator_gen
0651     {
0652         typedef typename std::iterator_traits< Iter >::value_type vt;
0653         typedef typename vt::first_type first_type;
0654         typedef typename vt::second_type second_type;
0655         typedef transpose_pair< first_type, second_type > transpose;
0656         typedef boost::transform_iterator< transpose, Iter > type;
0657         static type make(Iter it) { return type(it, transpose()); }
0658     };
0659
0660     template < typename Iter >
0661     typename transpose_iterator_gen< Iter >::type transpose_edges(Iter i)
0662     {
0663         return transpose_iterator_gen< Iter >::make(i);
0664     }
0665
0666     template < typename GraphT, typename VertexIndexMap >
0667     class edge_to_index_pair
0668     {
0669         typedef typename boost::graph_traits< GraphT >::vertices_size_type
0670             vertices_size_type;
0671         typedef typename boost::graph_traits< GraphT >::edge_descriptor
0672             edge_descriptor;
0673
0674     public:
0675         typedef std::pair< vertices_size_type, vertices_size_type > result_type;
0676
0677         edge_to_index_pair() : g(0), index() {}
0678         edge_to_index_pair(const GraphT& g, const VertexIndexMap& index)
0679         : g(&g), index(index)
0680         {
0681         }
0682
0683         result_type operator()(edge_descriptor e) const
0684         {
0685             return result_type(
0686                 get(index, source(e, *g)), get(index, target(e, *g)));
0687         }
0688
0689     private:
0690         const GraphT* g;
0691         VertexIndexMap index;
0692     };
0693
0694     template < typename GraphT, typename VertexIndexMap >
0695     edge_to_index_pair< GraphT, VertexIndexMap > make_edge_to_index_pair(
0696         const GraphT& g, const VertexIndexMap& index)
0697     {
0698         return edge_to_index_pair< GraphT, VertexIndexMap >(g, index);
0699     }
0700
0701     template < typename GraphT >
0702     edge_to_index_pair< GraphT,
0703         typename boost::property_map< GraphT,
0704             boost::vertex_index_t >::const_type >
0705     make_edge_to_index_pair(const GraphT& g)
0706     {
0707         typedef typename boost::property_map< GraphT,
0708             boost::vertex_index_t >::const_type VertexIndexMap;
0709         return edge_to_index_pair< GraphT, VertexIndexMap >(
0710             g, get(boost::vertex_index, g));
0711     }
0712
0713     template < typename GraphT, typename VertexIndexMap, typename Iter >
0714     boost::transform_iterator< edge_to_index_pair< GraphT, VertexIndexMap >,
0715         Iter >
0716     make_edge_to_index_pair_iter(
0717         const GraphT& g, const VertexIndexMap& index, Iter it)
0718     {
0719         return boost::transform_iterator<
0720             edge_to_index_pair< GraphT, VertexIndexMap >, Iter >(
0721             it, edge_to_index_pair< GraphT, VertexIndexMap >(g, index));
0722     }
0723
0724 } // namespace detail
0725
0726 template < typename Vertex, typename EdgeIndex >
0727 struct hash< detail::csr_edge_descriptor< Vertex, EdgeIndex > >
0728 {
0729     std::size_t operator()(
0730         detail::csr_edge_descriptor< Vertex, EdgeIndex > const& x) const
0731     {
0732         std::size_t hash = hash_value(x.src);
0733         hash_combine(hash, x.idx);
0734         return hash;
0735     }
0736 };
0737
0738 } // namespace boost
0739
0740 #endif // BOOST_GRAPH_COMPRESSED_SPARSE_ROW_STRUCT_HPP