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