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 get(const csr_edge_index_map<Vertex,EdgeIndex> &,const csr_edge_descriptor<Vertex,EdgeIndex> & key)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 null_vertex()99 static vertex_descriptor null_vertex() { return vertex_descriptor(-1); } 100 101 std::vector<EdgeIndex> m_rowstart; 102 std::vector<Vertex> m_column; 103 compressed_sparse_row_structure(Vertex numverts=0)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 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 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 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)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> 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)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> 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)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> assign_sources_and_targets_global(std::vector<vertex_descriptor> & sources,std::vector<vertex_descriptor> & targets,vertices_size_type numverts,GlobalToLocal global_to_local)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> 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)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 assign(const Graph & g,const VertexIndexMap & vi,vertices_size_type numverts,edges_size_type numedges)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 add_edges_sorted_internal(BidirectionalIteratorOrig first_sorted,BidirectionalIteratorOrig last_sorted,EPIterOrig ep_iter_sorted,const GlobalToLocal & global_to_local)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 csr_edge_descriptor(Vertex src,EdgeIndex idx)411 csr_edge_descriptor(Vertex src, EdgeIndex idx): src(src), idx(idx) {} csr_edge_descriptor()412 csr_edge_descriptor(): src(0), idx(0) {} 413 operator ==(const csr_edge_descriptor & e) const414 bool operator==(const csr_edge_descriptor& e) const {return idx == e.idx;} operator !=(const csr_edge_descriptor & e) const415 bool operator!=(const csr_edge_descriptor& e) const {return idx != e.idx;} operator <(const csr_edge_descriptor & e) const416 bool operator<(const csr_edge_descriptor& e) const {return idx < e.idx;} operator >(const csr_edge_descriptor & e) const417 bool operator>(const csr_edge_descriptor& e) const {return idx > e.idx;} operator <=(const csr_edge_descriptor & e) const418 bool operator<=(const csr_edge_descriptor& e) const {return idx <= e.idx;} operator >=(const csr_edge_descriptor & e) const419 bool operator>=(const csr_edge_descriptor& e) const {return idx >= e.idx;} 420 421 template<typename Archiver> serialize(Archiver & ar,const unsigned int)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 csr_out_edge_iterator()442 csr_out_edge_iterator() {} 443 // Implicit copy constructor OK csr_out_edge_iterator(edge_descriptor edge)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 dereference() const448 const edge_descriptor& dereference() const { return m_edge; } 449 equal(const csr_out_edge_iterator & other) const450 bool equal(const csr_out_edge_iterator& other) const 451 { return m_edge == other.m_edge; } 452 increment()453 void increment() { ++m_edge.idx; } decrement()454 void decrement() { --m_edge.idx; } advance(difference_type n)455 void advance(difference_type n) { m_edge.idx += n; } 456 distance_to(const csr_out_edge_iterator & other) const457 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 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: csr_edge_iterator()477 csr_edge_iterator() : rowstart_array(0), current_edge(), end_of_this_vertex(0), total_num_edges(0) {} 478 csr_edge_iterator(const CSRGraph & graph,edge_descriptor current_edge,EdgeIndex end_of_this_vertex)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 dereference() const490 edge_descriptor dereference() const {return current_edge;} 491 equal(const csr_edge_iterator & o) const492 bool equal(const csr_edge_iterator& o) const { 493 return current_edge == o.current_edge; 494 } 495 increment()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 csr_in_edge_iterator()523 csr_in_edge_iterator(): m_graph(0) {} 524 // Implicit copy constructor OK csr_in_edge_iterator(const CSRGraph & graph,EdgeIndex index_in_backward_graph)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 dereference() const531 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 equal(const csr_in_edge_iterator & other) const537 bool equal(const csr_in_edge_iterator& other) const 538 { return m_index_in_backward_graph == other.m_index_in_backward_graph; } 539 increment()540 void increment() { ++m_index_in_backward_graph; } decrement()541 void decrement() { --m_index_in_backward_graph; } advance(std::ptrdiff_t n)542 void advance(std::ptrdiff_t n) { m_index_in_backward_graph += n; } 543 distance_to(const csr_in_edge_iterator & other) const544 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 iterator_core_access; 551 }; 552 553 template <typename A, typename B> 554 struct transpose_pair { 555 typedef std::pair<B, A> result_type; operator ()boost::detail::transpose_pair556 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; makeboost::detail::transpose_iterator_gen568 static type make(Iter it) { 569 return type(it, transpose()); 570 } 571 }; 572 573 template <typename Iter> transpose_edges(Iter i)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 edge_to_index_pair()588 edge_to_index_pair() : g(0), index() { } edge_to_index_pair(const GraphT & g,const VertexIndexMap & index)589 edge_to_index_pair(const GraphT& g, const VertexIndexMap& index) 590 : g(&g), index(index) 591 { } 592 operator ()(edge_descriptor e) const593 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> make_edge_to_index_pair(const GraphT & g,const VertexIndexMap & index)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> make_edge_to_index_pair(const GraphT & g)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> make_edge_to_index_pair_iter(const GraphT & g,const VertexIndexMap & index,Iter it)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 { operator ()boost::hash636 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 648