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 > get(const csr_edge_index_map<Vertex,EdgeIndex> &,const csr_edge_descriptor<Vertex,EdgeIndex> & key)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 null_vertex()97 static vertex_descriptor null_vertex() { return vertex_descriptor(-1); } 98 99 std::vector< EdgeIndex > m_rowstart; 100 std::vector< Vertex > m_column; 101 compressed_sparse_row_structure(Vertex numverts=0)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 > assign_unsorted_multi_pass_edges(MultiPassInputIterator edge_begin,MultiPassInputIterator edge_end,vertices_size_type numlocalverts,const GlobalToLocal & global_to_local,const SourcePred & source_pred)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 > assign_unsorted_multi_pass_edges(MultiPassInputIterator edge_begin,MultiPassInputIterator edge_end,EdgePropertyIterator ep_iter,vertices_size_type numlocalverts,const GlobalToLocal & global_to_local,const SourcePred & source_pred)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 > assign_from_sorted_edges(InputIterator edge_begin,InputIterator edge_end,const GlobalToLocal & global_to_local,const SourcePred & source_pred,vertices_size_type numlocalverts,edges_size_type numedges_or_zero)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 > assign_from_sorted_edges(InputIterator edge_begin,InputIterator edge_end,EdgePropertyIterator ep_iter,const GlobalToLocal & global_to_local,const SourcePred & source_pred,vertices_size_type numlocalverts,edges_size_type numedges_or_zero)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 > assign_sources_and_targets_global(std::vector<vertex_descriptor> & sources,std::vector<vertex_descriptor> & targets,vertices_size_type numverts,GlobalToLocal global_to_local)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 > assign_sources_and_targets_global(std::vector<vertex_descriptor> & sources,std::vector<vertex_descriptor> & targets,std::vector<typename inherited_edge_properties::edge_bundled> & edge_props,vertices_size_type numverts,GlobalToLocal global_to_local)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 > assign(const Graph & g,const VertexIndexMap & vi,vertices_size_type numverts,edges_size_type numedges)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 > add_edges_sorted_internal(BidirectionalIteratorOrig first_sorted,BidirectionalIteratorOrig last_sorted,EPIterOrig ep_iter_sorted,const GlobalToLocal & global_to_local)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 csr_edge_descriptor(Vertex src,EdgeIndex idx)459 csr_edge_descriptor(Vertex src, EdgeIndex idx) : src(src), idx(idx) {} csr_edge_descriptor()460 csr_edge_descriptor() : src(0), idx(0) {} 461 operator ==(const csr_edge_descriptor & e) const462 bool operator==(const csr_edge_descriptor& e) const 463 { 464 return idx == e.idx; 465 } operator !=(const csr_edge_descriptor & e) const466 bool operator!=(const csr_edge_descriptor& e) const 467 { 468 return idx != e.idx; 469 } operator <(const csr_edge_descriptor & e) const470 bool operator<(const csr_edge_descriptor& e) const 471 { 472 return idx < e.idx; 473 } operator >(const csr_edge_descriptor & e) const474 bool operator>(const csr_edge_descriptor& e) const 475 { 476 return idx > e.idx; 477 } operator <=(const csr_edge_descriptor & e) const478 bool operator<=(const csr_edge_descriptor& e) const 479 { 480 return idx <= e.idx; 481 } operator >=(const csr_edge_descriptor & e) const482 bool operator>=(const csr_edge_descriptor& e) const 483 { 484 return idx >= e.idx; 485 } 486 487 template < typename Archiver > serialize(Archiver & ar,const unsigned int)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 csr_out_edge_iterator()509 csr_out_edge_iterator() {} 510 // Implicit copy constructor OK csr_out_edge_iterator(edge_descriptor edge)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 dereference() const515 const edge_descriptor& dereference() const { return m_edge; } 516 equal(const csr_out_edge_iterator & other) const517 bool equal(const csr_out_edge_iterator& other) const 518 { 519 return m_edge == other.m_edge; 520 } 521 increment()522 void increment() { ++m_edge.idx; } decrement()523 void decrement() { --m_edge.idx; } advance(difference_type n)524 void advance(difference_type n) { m_edge.idx += n; } 525 distance_to(const csr_out_edge_iterator & other) const526 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: csr_edge_iterator()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 csr_edge_iterator(const CSRGraph & graph,edge_descriptor current_edge,EdgeIndex end_of_this_vertex)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 dereference() const567 edge_descriptor dereference() const { return current_edge; } 568 equal(const csr_edge_iterator & o) const569 bool equal(const csr_edge_iterator& o) const 570 { 571 return current_edge == o.current_edge; 572 } 573 increment()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 csr_in_edge_iterator()603 csr_in_edge_iterator() : m_graph(0) {} 604 // Implicit copy constructor OK csr_in_edge_iterator(const CSRGraph & graph,EdgeIndex index_in_backward_graph)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 dereference() const613 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 equal(const csr_in_edge_iterator & other) const621 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 increment()626 void increment() { ++m_index_in_backward_graph; } decrement()627 void decrement() { --m_index_in_backward_graph; } advance(std::ptrdiff_t n)628 void advance(std::ptrdiff_t n) { m_index_in_backward_graph += n; } 629 distance_to(const csr_in_edge_iterator & other) const630 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; operator ()boost::detail::transpose_pair644 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; makeboost::detail::transpose_iterator_gen657 static type make(Iter it) { return type(it, transpose()); } 658 }; 659 660 template < typename Iter > transpose_edges(Iter i)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 edge_to_index_pair()677 edge_to_index_pair() : g(0), index() {} edge_to_index_pair(const GraphT & g,const VertexIndexMap & index)678 edge_to_index_pair(const GraphT& g, const VertexIndexMap& index) 679 : g(&g), index(index) 680 { 681 } 682 operator ()(edge_descriptor e) const683 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 > make_edge_to_index_pair(const GraphT & g,const VertexIndexMap & index)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 > make_edge_to_index_pair(const GraphT & g)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 > make_edge_to_index_pair_iter(const GraphT & g,const VertexIndexMap & index,Iter it)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 { operator ()boost::hash729 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 741