ceph/src/boost/boost/graph/detail/compressed_sparse_row_struct.hpp

   1 // Copyright 2005-2009 The Trustees of Indiana University.
   2
   3 // Distributed under the Boost Software License, Version 1.0.
   4 // (See accompanying file LICENSE_1_0.txt or copy at
   5 // http://www.boost.org/LICENSE_1_0.txt)
   6
   7 //  Authors: Jeremiah Willcock
   8 //           Douglas Gregor
   9 //           Andrew Lumsdaine
  10
  11 // Compressed sparse row graph type internal structure
  12
  13 #ifndef BOOST_GRAPH_COMPRESSED_SPARSE_ROW_STRUCT_HPP
  14 #define BOOST_GRAPH_COMPRESSED_SPARSE_ROW_STRUCT_HPP
  15
  16 #ifndef BOOST_GRAPH_COMPRESSED_SPARSE_ROW_GRAPH_HPP
  17 #error This file should only be included from boost/graph/compressed_sparse_row_graph.hpp
  18 #endif
  19
  20 #include <vector>
  21 #include <utility>
  22 #include <algorithm>
  23 #include <climits>
  24 #include <boost/assert.hpp>
  25 #include <iterator>
  26 #if 0
  27 #include <iostream> // For some debugging code below
  28 #endif
  29 #include <boost/graph/graph_traits.hpp>
  30 #include <boost/graph/properties.hpp>
  31 #include <boost/graph/filtered_graph.hpp> // For keep_all
  32 #include <boost/graph/detail/indexed_properties.hpp>
  33 #include <boost/graph/detail/histogram_sort.hpp>
  34 #include <boost/graph/iteration_macros.hpp>
  35 #include <boost/iterator/counting_iterator.hpp>
  36 #include <boost/iterator/reverse_iterator.hpp>
  37 #include <boost/iterator/zip_iterator.hpp>
  38 #include <boost/iterator/transform_iterator.hpp>
  39 #include <boost/tuple/tuple.hpp>
  40 #include <boost/property_map/property_map.hpp>
  41 #include <boost/integer.hpp>
  42 #include <boost/iterator/iterator_facade.hpp>
  43 #include <boost/mpl/if.hpp>
  44 #include <boost/graph/graph_selectors.hpp>
  45 #include <boost/static_assert.hpp>
  46 #include <boost/functional/hash.hpp>
  47
  48 namespace boost {
  49
  50 namespace detail {
  51   // Forward declaration of CSR edge descriptor type, needed to pass to
  52   // indexed_edge_properties.
  53   template<typename Vertex, typename EdgeIndex>
  54   class csr_edge_descriptor;
  55
  56   // Add edge_index property map
  57   template<typename Vertex, typename EdgeIndex>
  58   struct csr_edge_index_map
  59   {
  60     typedef EdgeIndex                 value_type;
  61     typedef EdgeIndex                 reference;
  62     typedef csr_edge_descriptor<Vertex, EdgeIndex> key_type;
  63     typedef readable_property_map_tag category;
  64   };
  65
  66   template<typename Vertex, typename EdgeIndex>
  67   inline EdgeIndex
  68   get(const csr_edge_index_map<Vertex, EdgeIndex>&,
  69       const csr_edge_descriptor<Vertex, EdgeIndex>& key)
  70   {
  71     return key.idx;
  72   }
  73
  74   /** Compressed sparse row graph internal structure.
  75    *
  76    * Vertex and EdgeIndex should be unsigned integral types and should
  77    * specialize numeric_limits.
  78    */
  79   template <typename EdgeProperty,
  80             typename Vertex = std::size_t, typename EdgeIndex = Vertex>
  81   class compressed_sparse_row_structure :
  82     public detail::indexed_edge_properties<
  83              compressed_sparse_row_structure<EdgeProperty, Vertex, EdgeIndex>,
  84              EdgeProperty,
  85              csr_edge_descriptor<Vertex, EdgeIndex>,
  86              csr_edge_index_map<Vertex, EdgeIndex> > {
  87     public:
  88     typedef detail::indexed_edge_properties<
  89               compressed_sparse_row_structure<EdgeProperty, Vertex, EdgeIndex>,
  90               EdgeProperty,
  91               csr_edge_descriptor<Vertex, EdgeIndex>,
  92               csr_edge_index_map<Vertex, EdgeIndex> >
  93       inherited_edge_properties;
  94
  95     typedef Vertex vertices_size_type;
  96     typedef Vertex vertex_descriptor;
  97     typedef EdgeIndex edges_size_type;
  98
  99     static vertex_descriptor null_vertex() { return vertex_descriptor(-1); }
 100
 101     std::vector<EdgeIndex> m_rowstart;
 102     std::vector<Vertex> m_column;
 103
 104     compressed_sparse_row_structure(Vertex numverts = 0)
 105       : m_rowstart(numverts + 1, EdgeIndex(0)), m_column()
 106       {}
 107
 108     //  Rebuild graph from number of vertices and multi-pass unsorted list of
 109     //  edges (filtered using source_pred and mapped using global_to_local)
 110     template <typename MultiPassInputIterator, typename GlobalToLocal, typename SourcePred>
 111     void
 112     assign_unsorted_multi_pass_edges(MultiPassInputIterator edge_begin,
 113                                      MultiPassInputIterator edge_end,
 114                                      vertices_size_type numlocalverts,
 115                                      const GlobalToLocal& global_to_local,
 116                                      const SourcePred& source_pred) {
 117       m_rowstart.clear();
 118       m_rowstart.resize(numlocalverts + 1, 0);
 119       typedef std::pair<vertices_size_type, vertices_size_type> edge_type;
 120       typedef boost::transform_iterator<boost::graph::detail::project1st<edge_type>, MultiPassInputIterator> source_iterator;
 121       typedef boost::transform_iterator<boost::graph::detail::project2nd<edge_type>, MultiPassInputIterator> target_iterator;
 122       source_iterator sources_begin(edge_begin, boost::graph::detail::project1st<edge_type>());
 123       source_iterator sources_end(edge_end, boost::graph::detail::project1st<edge_type>());
 124       target_iterator targets_begin(edge_begin, boost::graph::detail::project2nd<edge_type>());
 125       target_iterator targets_end(edge_end, boost::graph::detail::project2nd<edge_type>());
 126
 127       boost::graph::detail::count_starts
 128         (sources_begin, sources_end, m_rowstart.begin(), numlocalverts,
 129          source_pred, boost::make_property_map_function(global_to_local));
 130
 131       m_column.resize(m_rowstart.back());
 132       inherited_edge_properties::resize(m_rowstart.back());
 133
 134       boost::graph::detail::histogram_sort
 135         (sources_begin, sources_end, m_rowstart.begin(), numlocalverts,
 136          targets_begin, m_column.begin(),
 137          source_pred, boost::make_property_map_function(global_to_local));
 138     }
 139
 140     //  Rebuild graph from number of vertices and multi-pass unsorted list of
 141     //  edges and their properties (filtered using source_pred and mapped using
 142     //  global_to_local)
 143     template <typename MultiPassInputIterator, typename EdgePropertyIterator, typename GlobalToLocal, typename SourcePred>
 144     void
 145     assign_unsorted_multi_pass_edges(MultiPassInputIterator edge_begin,
 146                                      MultiPassInputIterator edge_end,
 147                                      EdgePropertyIterator ep_iter,
 148                                      vertices_size_type numlocalverts,
 149                                      const GlobalToLocal& global_to_local,
 150                                      const SourcePred& source_pred) {
 151       m_rowstart.clear();
 152       m_rowstart.resize(numlocalverts + 1, 0);
 153       typedef std::pair<vertices_size_type, vertices_size_type> edge_type;
 154       typedef boost::transform_iterator<boost::graph::detail::project1st<edge_type>, MultiPassInputIterator> source_iterator;
 155       typedef boost::transform_iterator<boost::graph::detail::project2nd<edge_type>, MultiPassInputIterator> target_iterator;
 156       source_iterator sources_begin(edge_begin, boost::graph::detail::project1st<edge_type>());
 157       source_iterator sources_end(edge_end, boost::graph::detail::project1st<edge_type>());
 158       target_iterator targets_begin(edge_begin, boost::graph::detail::project2nd<edge_type>());
 159       target_iterator targets_end(edge_end, boost::graph::detail::project2nd<edge_type>());
 160
 161       boost::graph::detail::count_starts
 162         (sources_begin, sources_end, m_rowstart.begin(), numlocalverts,
 163          source_pred, boost::make_property_map_function(global_to_local));
 164
 165       m_column.resize(m_rowstart.back());
 166       inherited_edge_properties::resize(m_rowstart.back());
 167
 168       boost::graph::detail::histogram_sort
 169         (sources_begin, sources_end, m_rowstart.begin(), numlocalverts,
 170          targets_begin, m_column.begin(),
 171          ep_iter, inherited_edge_properties::begin(),
 172          source_pred, boost::make_property_map_function(global_to_local));
 173     }
 174
 175     //  Assign from number of vertices and sorted list of edges
 176     template<typename InputIterator, typename GlobalToLocal, typename SourcePred>
 177     void assign_from_sorted_edges(
 178            InputIterator edge_begin, InputIterator edge_end,
 179            const GlobalToLocal& global_to_local,
 180            const SourcePred& source_pred,
 181            vertices_size_type numlocalverts,
 182            edges_size_type numedges_or_zero) {
 183       m_column.clear();
 184       m_column.reserve(numedges_or_zero);
 185       m_rowstart.resize(numlocalverts + 1);
 186       EdgeIndex current_edge = 0;
 187       Vertex current_vertex_plus_one = 1;
 188       m_rowstart[0] = 0;
 189       for (InputIterator ei = edge_begin; ei != edge_end; ++ei) {
 190         if (!source_pred(ei->first)) continue;
 191         Vertex src = get(global_to_local, ei->first);
 192         Vertex tgt = ei->second;
 193         for (; current_vertex_plus_one != src + 1; ++current_vertex_plus_one)
 194           m_rowstart[current_vertex_plus_one] = current_edge;
 195         m_column.push_back(tgt);
 196         ++current_edge;
 197       }
 198
 199       // The remaining vertices have no edges
 200       for (; current_vertex_plus_one != numlocalverts + 1; ++current_vertex_plus_one)
 201         m_rowstart[current_vertex_plus_one] = current_edge;
 202
 203       // Default-construct properties for edges
 204       inherited_edge_properties::resize(m_column.size());
 205     }
 206
 207     //  Assign from number of vertices and sorted list of edges
 208     template<typename InputIterator, typename EdgePropertyIterator, typename GlobalToLocal, typename SourcePred>
 209     void assign_from_sorted_edges(
 210            InputIterator edge_begin, InputIterator edge_end,
 211            EdgePropertyIterator ep_iter,
 212            const GlobalToLocal& global_to_local,
 213            const SourcePred& source_pred,
 214            vertices_size_type numlocalverts,
 215            edges_size_type numedges_or_zero) {
 216       // Reserving storage in advance can save us lots of time and
 217       // memory, but it can only be done if we have forward iterators or
 218       // the user has supplied the number of edges.
 219       edges_size_type numedges = numedges_or_zero;
 220       if (numedges == 0) {
 221         numedges = boost::graph::detail::reserve_count_for_single_pass(edge_begin, edge_end);
 222       }
 223       m_column.clear();
 224       m_column.reserve(numedges_or_zero);
 225       inherited_edge_properties::clear();
 226       inherited_edge_properties::reserve(numedges_or_zero);
 227       m_rowstart.resize(numlocalverts + 1);
 228       EdgeIndex current_edge = 0;
 229       Vertex current_vertex_plus_one = 1;
 230       m_rowstart[0] = 0;
 231       for (InputIterator ei = edge_begin; ei != edge_end; ++ei, ++ep_iter) {
 232         if (!source_pred(ei->first)) continue;
 233         Vertex src = get(global_to_local, ei->first);
 234         Vertex tgt = ei->second;
 235         for (; current_vertex_plus_one != src + 1; ++current_vertex_plus_one)
 236           m_rowstart[current_vertex_plus_one] = current_edge;
 237         m_column.push_back(tgt);
 238         inherited_edge_properties::push_back(*ep_iter);
 239         ++current_edge;
 240       }
 241
 242       // The remaining vertices have no edges
 243       for (; current_vertex_plus_one != numlocalverts + 1; ++current_vertex_plus_one)
 244         m_rowstart[current_vertex_plus_one] = current_edge;
 245     }
 246
 247     // Replace graph with sources and targets given, sorting them in-place, and
 248     // using the given global-to-local property map to get local indices from
 249     // global ones in the two arrays.
 250     template <typename GlobalToLocal>
 251     void assign_sources_and_targets_global(std::vector<vertex_descriptor>& sources,
 252                                            std::vector<vertex_descriptor>& targets,
 253                                            vertices_size_type numverts,
 254                                            GlobalToLocal global_to_local) {
 255       BOOST_ASSERT (sources.size() == targets.size());
 256       // Do an in-place histogram sort (at least that's what I think it is) to
 257       // sort sources and targets
 258       m_rowstart.clear();
 259       m_rowstart.resize(numverts + 1);
 260       boost::graph::detail::count_starts
 261         (sources.begin(), sources.end(), m_rowstart.begin(), numverts,
 262          keep_all(), boost::make_property_map_function(global_to_local));
 263       boost::graph::detail::histogram_sort_inplace
 264         (sources.begin(), m_rowstart.begin(), numverts,
 265          targets.begin(), boost::make_property_map_function(global_to_local));
 266       // Now targets is the correct vector (properly sorted by source) for
 267       // m_column
 268       m_column.swap(targets);
 269       inherited_edge_properties::resize(m_rowstart.back());
 270     }
 271
 272     // Replace graph with sources and targets and edge properties given, sorting
 273     // them in-place, and using the given global-to-local property map to get
 274     // local indices from global ones in the two arrays.
 275     template <typename GlobalToLocal>
 276     void assign_sources_and_targets_global(std::vector<vertex_descriptor>& sources,
 277                                            std::vector<vertex_descriptor>& targets,
 278                                            std::vector<typename inherited_edge_properties::edge_bundled>& edge_props,
 279                                            vertices_size_type numverts,
 280                                            GlobalToLocal global_to_local) {
 281       BOOST_ASSERT (sources.size() == targets.size());
 282       BOOST_ASSERT (sources.size() == edge_props.size());
 283       // Do an in-place histogram sort (at least that's what I think it is) to
 284       // sort sources and targets
 285       m_rowstart.clear();
 286       m_rowstart.resize(numverts + 1);
 287       boost::graph::detail::count_starts
 288         (sources.begin(), sources.end(), m_rowstart.begin(), numverts,
 289          keep_all(), boost::make_property_map_function(global_to_local));
 290       boost::graph::detail::histogram_sort_inplace
 291         (sources.begin(), m_rowstart.begin(), numverts,
 292          targets.begin(), edge_props.begin(),
 293          boost::make_property_map_function(global_to_local));
 294       // Now targets is the correct vector (properly sorted by source) for
 295       // m_column, and edge_props for m_edge_properties
 296       m_column.swap(targets);
 297       this->m_edge_properties.swap(edge_props);
 298     }
 299
 300     // From any graph (slow and uses a lot of memory)
 301     //   Requires IncidenceGraph and a vertex index map
 302     //   Internal helper function
 303     //   Note that numedges must be doubled for undirected source graphs
 304     template<typename Graph, typename VertexIndexMap>
 305     void
 306     assign(const Graph& g, const VertexIndexMap& vi,
 307            vertices_size_type numverts, edges_size_type numedges)
 308     {
 309       m_rowstart.resize(numverts + 1);
 310       m_column.resize(numedges);
 311       inherited_edge_properties::resize(numedges);
 312       EdgeIndex current_edge = 0;
 313       typedef typename boost::graph_traits<Graph>::vertex_descriptor g_vertex;
 314       typedef typename boost::graph_traits<Graph>::out_edge_iterator
 315         g_out_edge_iter;
 316
 317       std::vector<g_vertex> ordered_verts_of_g(numverts);
 318       BGL_FORALL_VERTICES_T(v, g, Graph) {
 319         ordered_verts_of_g[get(vertex_index, g, v)] = v;
 320       }
 321       for (Vertex i = 0; i != numverts; ++i) {
 322         m_rowstart[i] = current_edge;
 323         g_vertex v = ordered_verts_of_g[i];
 324         g_out_edge_iter ei, ei_end;
 325         for (boost::tie(ei, ei_end) = out_edges(v, g); ei != ei_end; ++ei) {
 326           m_column[current_edge++] = get(vi, target(*ei, g));
 327         }
 328       }
 329       m_rowstart[numverts] = current_edge;
 330     }
 331
 332     // Add edges from a sorted (smallest sources first) range of pairs and edge
 333     // properties
 334     template <typename BidirectionalIteratorOrig, typename EPIterOrig,
 335               typename GlobalToLocal>
 336     void
 337     add_edges_sorted_internal(
 338         BidirectionalIteratorOrig first_sorted,
 339         BidirectionalIteratorOrig last_sorted,
 340         EPIterOrig ep_iter_sorted,
 341         const GlobalToLocal& global_to_local) {
 342       typedef boost::reverse_iterator<BidirectionalIteratorOrig> BidirectionalIterator;
 343       typedef boost::reverse_iterator<EPIterOrig> EPIter;
 344       // Flip sequence
 345       BidirectionalIterator first(last_sorted);
 346       BidirectionalIterator last(first_sorted);
 347       typedef Vertex vertex_num;
 348       typedef EdgeIndex edge_num;
 349       edge_num new_edge_count = std::distance(first, last);
 350
 351       EPIter ep_iter(ep_iter_sorted);
 352       std::advance(ep_iter, -(std::ptrdiff_t)new_edge_count);
 353       edge_num edges_added_before_i = new_edge_count; // Count increment to add to rowstarts
 354       m_column.resize(m_column.size() + new_edge_count);
 355       inherited_edge_properties::resize(inherited_edge_properties::size() + new_edge_count);
 356       BidirectionalIterator current_new_edge = first, prev_new_edge = first;
 357       EPIter current_new_edge_prop = ep_iter;
 358       for (vertex_num i_plus_1 = m_rowstart.size() - 1; i_plus_1 > 0; --i_plus_1) {
 359         vertex_num i = i_plus_1 - 1;
 360         prev_new_edge = current_new_edge;
 361         // edges_added_to_this_vertex = #mbrs of new_edges with first == i
 362         edge_num edges_added_to_this_vertex = 0;
 363         while (current_new_edge != last) {
 364           if (get(global_to_local, current_new_edge->first) != i) break;
 365           ++current_new_edge;
 366           ++current_new_edge_prop;
 367           ++edges_added_to_this_vertex;
 368         }
 369         edges_added_before_i -= edges_added_to_this_vertex;
 370         // Invariant: edges_added_before_i = #mbrs of new_edges with first < i
 371         edge_num old_rowstart = m_rowstart[i];
 372         edge_num new_rowstart = m_rowstart[i] + edges_added_before_i;
 373         edge_num old_degree = m_rowstart[i + 1] - m_rowstart[i];
 374         edge_num new_degree = old_degree + edges_added_to_this_vertex;
 375         // Move old edges forward (by #new_edges before this i) to make room
 376         // new_rowstart > old_rowstart, so use copy_backwards
 377         if (old_rowstart != new_rowstart) {
 378           std::copy_backward(m_column.begin() + old_rowstart,
 379                              m_column.begin() + old_rowstart + old_degree,
 380                              m_column.begin() + new_rowstart + old_degree);
 381           inherited_edge_properties::move_range(old_rowstart, old_rowstart + old_degree, new_rowstart);
 382         }
 383         // Add new edges (reversed because current_new_edge is a
 384         // const_reverse_iterator)
 385         BidirectionalIterator temp = current_new_edge;
 386         EPIter temp_prop = current_new_edge_prop;
 387         for (; temp != prev_new_edge; ++old_degree) {
 388           --temp;
 389           --temp_prop;
 390           m_column[new_rowstart + old_degree] = temp->second;
 391           inherited_edge_properties::write_by_index(new_rowstart + old_degree, *temp_prop);
 392         }
 393         m_rowstart[i + 1] = new_rowstart + new_degree;
 394         if (edges_added_before_i == 0) break; // No more edges inserted before this point
 395         // m_rowstart[i] will be fixed up on the next iteration (to avoid
 396         // changing the degree of vertex i - 1); the last iteration never changes
 397         // it (either because of the condition of the break or because
 398         // m_rowstart[0] is always 0)
 399       }
 400     }
 401
 402   };
 403
 404   template<typename Vertex, typename EdgeIndex>
 405   class csr_edge_descriptor
 406   {
 407    public:
 408     Vertex src;
 409     EdgeIndex idx;
 410
 411     csr_edge_descriptor(Vertex src, EdgeIndex idx): src(src), idx(idx) {}
 412     csr_edge_descriptor(): src(0), idx(0) {}
 413
 414     bool operator==(const csr_edge_descriptor& e) const {return idx == e.idx;}
 415     bool operator!=(const csr_edge_descriptor& e) const {return idx != e.idx;}
 416     bool operator<(const csr_edge_descriptor& e) const {return idx < e.idx;}
 417     bool operator>(const csr_edge_descriptor& e) const {return idx > e.idx;}
 418     bool operator<=(const csr_edge_descriptor& e) const {return idx <= e.idx;}
 419     bool operator>=(const csr_edge_descriptor& e) const {return idx >= e.idx;}
 420
 421     template<typename Archiver>
 422     void serialize(Archiver& ar, const unsigned int /*version*/)
 423     {
 424       ar & src & idx;
 425     }
 426   };
 427
 428   // Common out edge and edge iterators
 429   template<typename CSRGraph>
 430   class csr_out_edge_iterator
 431     : public iterator_facade<csr_out_edge_iterator<CSRGraph>,
 432                              typename CSRGraph::edge_descriptor,
 433                              std::random_access_iterator_tag,
 434                              const typename CSRGraph::edge_descriptor&,
 435                              typename int_t<CHAR_BIT * sizeof(typename CSRGraph::edges_size_type)>::fast>
 436   {
 437    public:
 438     typedef typename CSRGraph::edges_size_type EdgeIndex;
 439     typedef typename CSRGraph::edge_descriptor edge_descriptor;
 440     typedef typename int_t<CHAR_BIT * sizeof(EdgeIndex)>::fast difference_type;
 441
 442     csr_out_edge_iterator() {}
 443     // Implicit copy constructor OK
 444     explicit csr_out_edge_iterator(edge_descriptor edge) : m_edge(edge) { }
 445
 446    public: // GCC 4.2.1 doesn't like the private-and-friend thing
 447     // iterator_facade requirements
 448     const edge_descriptor& dereference() const { return m_edge; }
 449
 450     bool equal(const csr_out_edge_iterator& other) const
 451     { return m_edge == other.m_edge; }
 452
 453     void increment() { ++m_edge.idx; }
 454     void decrement() { --m_edge.idx; }
 455     void advance(difference_type n) { m_edge.idx += n; }
 456
 457     difference_type distance_to(const csr_out_edge_iterator& other) const
 458     { return other.m_edge.idx - m_edge.idx; }
 459
 460     edge_descriptor m_edge;
 461
 462     friend class boost::iterator_core_access;
 463   };
 464
 465   template<typename CSRGraph>
 466   class csr_edge_iterator
 467     : public iterator_facade<csr_edge_iterator<CSRGraph>,
 468                              typename CSRGraph::edge_descriptor,
 469                              boost::forward_traversal_tag,
 470                              typename CSRGraph::edge_descriptor>
 471   {
 472    private:
 473     typedef typename CSRGraph::edge_descriptor edge_descriptor;
 474     typedef typename CSRGraph::edges_size_type EdgeIndex;
 475
 476    public:
 477     csr_edge_iterator() : rowstart_array(0), current_edge(), end_of_this_vertex(0), total_num_edges(0) {}
 478
 479     csr_edge_iterator(const CSRGraph& graph,
 480                       edge_descriptor current_edge,
 481                       EdgeIndex end_of_this_vertex)
 482       : rowstart_array(&graph.m_forward.m_rowstart[0]),
 483         current_edge(current_edge),
 484         end_of_this_vertex(end_of_this_vertex),
 485         total_num_edges(num_edges(graph)) {}
 486
 487    public: // See above
 488     friend class boost::iterator_core_access;
 489
 490     edge_descriptor dereference() const {return current_edge;}
 491
 492     bool equal(const csr_edge_iterator& o) const {
 493       return current_edge == o.current_edge;
 494     }
 495
 496     void increment() {
 497       ++current_edge.idx;
 498       if (current_edge.idx == total_num_edges) return;
 499       while (current_edge.idx == end_of_this_vertex) {
 500         ++current_edge.src;
 501         end_of_this_vertex = rowstart_array[current_edge.src + 1];
 502       }
 503     }
 504
 505     const EdgeIndex* rowstart_array;
 506     edge_descriptor current_edge;
 507     EdgeIndex end_of_this_vertex;
 508     EdgeIndex total_num_edges;
 509   };
 510
 511   // Only for bidirectional graphs
 512   template<typename CSRGraph>
 513   class csr_in_edge_iterator
 514     : public iterator_facade<csr_in_edge_iterator<CSRGraph>,
 515                              typename CSRGraph::edge_descriptor,
 516                              boost::forward_traversal_tag,
 517                              typename CSRGraph::edge_descriptor>
 518   {
 519    public:
 520     typedef typename CSRGraph::edges_size_type EdgeIndex;
 521     typedef typename CSRGraph::edge_descriptor edge_descriptor;
 522
 523     csr_in_edge_iterator(): m_graph(0) {}
 524     // Implicit copy constructor OK
 525     csr_in_edge_iterator(const CSRGraph& graph,
 526                          EdgeIndex index_in_backward_graph)
 527       : m_index_in_backward_graph(index_in_backward_graph), m_graph(&graph) {}
 528
 529    public: // See above
 530     // iterator_facade requirements
 531     edge_descriptor dereference() const {
 532       return edge_descriptor(
 533                m_graph->m_backward.m_column[m_index_in_backward_graph],
 534                m_graph->m_backward.m_edge_properties[m_index_in_backward_graph]);
 535     }
 536
 537     bool equal(const csr_in_edge_iterator& other) const
 538     { return m_index_in_backward_graph == other.m_index_in_backward_graph; }
 539
 540     void increment() { ++m_index_in_backward_graph; }
 541     void decrement() { --m_index_in_backward_graph; }
 542     void advance(std::ptrdiff_t n) { m_index_in_backward_graph += n; }
 543
 544     std::ptrdiff_t distance_to(const csr_in_edge_iterator& other) const
 545     { return other.m_index_in_backward_graph - m_index_in_backward_graph; }
 546
 547     EdgeIndex m_index_in_backward_graph;
 548     const CSRGraph* m_graph;
 549
 550     friend class boost::iterator_core_access;
 551   };
 552
 553   template <typename A, typename B>
 554   struct transpose_pair {
 555     typedef std::pair<B, A> result_type;
 556     result_type operator()(const std::pair<A, B>& p) const {
 557       return result_type(p.second, p.first);
 558     }
 559   };
 560
 561   template <typename Iter>
 562   struct transpose_iterator_gen {
 563     typedef typename std::iterator_traits<Iter>::value_type vt;
 564     typedef typename vt::first_type first_type;
 565     typedef typename vt::second_type second_type;
 566     typedef transpose_pair<first_type, second_type> transpose;
 567     typedef boost::transform_iterator<transpose, Iter> type;
 568     static type make(Iter it) {
 569       return type(it, transpose());
 570     }
 571   };
 572
 573   template <typename Iter>
 574   typename transpose_iterator_gen<Iter>::type transpose_edges(Iter i) {
 575     return transpose_iterator_gen<Iter>::make(i);
 576   }
 577
 578   template<typename GraphT, typename VertexIndexMap>
 579   class edge_to_index_pair
 580   {
 581     typedef typename boost::graph_traits<GraphT>::vertices_size_type
 582       vertices_size_type;
 583     typedef typename boost::graph_traits<GraphT>::edge_descriptor edge_descriptor;
 584
 585    public:
 586     typedef std::pair<vertices_size_type, vertices_size_type> result_type;
 587
 588     edge_to_index_pair() : g(0), index() { }
 589     edge_to_index_pair(const GraphT& g, const VertexIndexMap& index)
 590       : g(&g), index(index)
 591     { }
 592
 593     result_type operator()(edge_descriptor e) const
 594     {
 595       return result_type(get(index, source(e, *g)), get(index, target(e, *g)));
 596     }
 597
 598    private:
 599     const GraphT* g;
 600     VertexIndexMap index;
 601   };
 602
 603   template<typename GraphT, typename VertexIndexMap>
 604   edge_to_index_pair<GraphT, VertexIndexMap>
 605   make_edge_to_index_pair(const GraphT& g, const VertexIndexMap& index)
 606   {
 607     return edge_to_index_pair<GraphT, VertexIndexMap>(g, index);
 608   }
 609
 610   template<typename GraphT>
 611   edge_to_index_pair
 612     <GraphT,
 613      typename boost::property_map<GraphT,boost::vertex_index_t>::const_type>
 614   make_edge_to_index_pair(const GraphT& g)
 615   {
 616     typedef typename boost::property_map<GraphT,
 617                                          boost::vertex_index_t>::const_type
 618       VertexIndexMap;
 619     return edge_to_index_pair<GraphT, VertexIndexMap>(g,
 620                                                      get(boost::vertex_index,
 621                                                          g));
 622   }
 623
 624   template<typename GraphT, typename VertexIndexMap, typename Iter>
 625   boost::transform_iterator<edge_to_index_pair<GraphT, VertexIndexMap>, Iter>
 626   make_edge_to_index_pair_iter(const GraphT& g, const VertexIndexMap& index,
 627                                Iter it) {
 628     return boost::transform_iterator<edge_to_index_pair<GraphT, VertexIndexMap>, Iter>(it, edge_to_index_pair<GraphT, VertexIndexMap>(g, index));
 629   }
 630
 631 } // namespace detail
 632
 633   template<typename Vertex, typename EdgeIndex>
 634   struct hash<detail::csr_edge_descriptor<Vertex, EdgeIndex> >
 635   {
 636     std::size_t operator()
 637                   (detail::csr_edge_descriptor<Vertex, EdgeIndex> const& x) const
 638     {
 639       std::size_t hash = hash_value(x.src);
 640       hash_combine(hash, x.idx);
 641       return hash;
 642     }
 643   };
 644
 645 } // namespace boost
 646
 647 #endif // BOOST_GRAPH_COMPRESSED_SPARSE_ROW_STRUCT_HPP