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
12
13#ifndef BOOST_GRAPH_COMPRESSED_SPARSE_ROW_GRAPH_HPP
14#define BOOST_GRAPH_COMPRESSED_SPARSE_ROW_GRAPH_HPP
15
16#include <vector>
17#include <utility>
18#include <algorithm>
19#include <climits>
20#include <boost/assert.hpp>
21#include <iterator>
22#if 0
23#include <iostream> // For some debugging code below
24#endif
25#include <boost/graph/graph_traits.hpp>
26#include <boost/graph/properties.hpp>
27#include <boost/graph/filtered_graph.hpp> // For keep_all
28#include <boost/graph/detail/indexed_properties.hpp>
29#include <boost/graph/detail/compressed_sparse_row_struct.hpp>
30#include <boost/graph/iteration_macros.hpp>
31#include <boost/iterator/counting_iterator.hpp>
32#include <boost/iterator/reverse_iterator.hpp>
33#include <boost/iterator/zip_iterator.hpp>
34#include <boost/iterator/transform_iterator.hpp>
35#include <boost/tuple/tuple.hpp>
36#include <boost/property_map/property_map.hpp>
37#include <boost/integer.hpp>
38#include <boost/iterator/iterator_facade.hpp>
39#include <boost/mpl/if.hpp>
40#include <boost/utility/enable_if.hpp>
41#include <boost/graph/graph_selectors.hpp>
42#include <boost/graph/detail/is_distributed_selector.hpp>
43#include <boost/graph/properties.hpp>
44#include <boost/static_assert.hpp>
45#include <boost/functional/hash.hpp>
46#include <boost/next_prior.hpp>
47#include <boost/property_map/transform_value_property_map.hpp>
48#include <boost/mpl/print.hpp>
49
50namespace boost {
51
52// A tag type indicating that the graph in question is a compressed
53// sparse row graph. This is an internal detail of the BGL.
54struct csr_graph_tag;
55
56// A type (edges_are_sorted_t) and a value (edges_are_sorted) used to indicate
57// that the edge list passed into the CSR graph is already sorted by source
58// vertex.
59enum edges_are_sorted_t {edges_are_sorted};
60
61// A type (edges_are_sorted_global_t) and a value (edges_are_sorted_global)
62// used to indicate that the edge list passed into the CSR graph is already
63// sorted by source vertex.
64enum edges_are_sorted_global_t {edges_are_sorted_global};
65
66// A type (edges_are_unsorted_t) and a value (edges_are_unsorted) used to
67// indicate that the edge list passed into the CSR graph is not sorted by
68// source vertex. This version caches the edge information in memory, and thus
69// requires only a single pass over the input data.
70enum edges_are_unsorted_t {edges_are_unsorted};
71
72// A type (edges_are_unsorted_multi_pass_t) and a value
73// (edges_are_unsorted_multi_pass) used to indicate that the edge list passed
74// into the CSR graph is not sorted by source vertex. This version uses less
75// memory but requires multi-pass capability on the iterators.
76enum edges_are_unsorted_multi_pass_t {edges_are_unsorted_multi_pass};
77
78// A type (edges_are_unsorted_multi_pass_global_t) and a value
79// (edges_are_unsorted_multi_pass_global) used to indicate that the edge list
80// passed into the CSR graph is not sorted by source vertex. This version uses
81// less memory but requires multi-pass capability on the iterators. The
82// global mapping and filtering is done here because it is often faster and it
83// greatly simplifies handling of edge properties.
84enum edges_are_unsorted_multi_pass_global_t {edges_are_unsorted_multi_pass_global};
85
86// A type (construct_inplace_from_sources_and_targets_t) and a value
87// (construct_inplace_from_sources_and_targets) used to indicate that mutable
88// vectors of sources and targets (and possibly edge properties) are being used
89// to construct the CSR graph. These vectors are sorted in-place and then the
90// targets and properties are swapped into the graph data structure.
91enum construct_inplace_from_sources_and_targets_t {construct_inplace_from_sources_and_targets};
92
93// A type (construct_inplace_from_sources_and_targets_global_t) and a value
94// (construct_inplace_from_sources_and_targets_global) used to indicate that
95// mutable vectors of sources and targets (and possibly edge properties) are
96// being used to construct the CSR graph. These vectors are sorted in-place
97// and then the targets and properties are swapped into the graph data
98// structure. It is assumed that global indices (for distributed CSR) are
99// used, and a map is required to convert those to local indices. This
100// constructor is intended for internal use by the various CSR graphs
101// (sequential and distributed).
102enum construct_inplace_from_sources_and_targets_global_t {construct_inplace_from_sources_and_targets_global};
103
104// A type (edges_are_unsorted_global_t) and a value (edges_are_unsorted_global)
105// used to indicate that the edge list passed into the CSR graph is not sorted
106// by source vertex. The data is also stored using global vertex indices, and
107// must be filtered to choose only local vertices. This constructor caches the
108// edge information in memory, and thus requires only a single pass over the
109// input data. This constructor is intended for internal use by the
110// distributed CSR constructors.
111enum edges_are_unsorted_global_t {edges_are_unsorted_global};
112
113/****************************************************************************
114 * Local helper macros to reduce typing and clutter later on. *
115 ****************************************************************************/
116#define BOOST_CSR_GRAPH_TEMPLATE_PARMS \
117 typename Directed, typename VertexProperty, typename EdgeProperty, \
118 typename GraphProperty, typename Vertex, typename EdgeIndex
119#define BOOST_CSR_GRAPH_TYPE \
120 compressed_sparse_row_graph<Directed, VertexProperty, EdgeProperty, \
121 GraphProperty, Vertex, EdgeIndex>
122#define BOOST_DIR_CSR_GRAPH_TEMPLATE_PARMS \
123 typename VertexProperty, typename EdgeProperty, \
124 typename GraphProperty, typename Vertex, typename EdgeIndex
125#define BOOST_DIR_CSR_GRAPH_TYPE \
126 compressed_sparse_row_graph<directedS, VertexProperty, EdgeProperty, \
127 GraphProperty, Vertex, EdgeIndex>
128#define BOOST_BIDIR_CSR_GRAPH_TEMPLATE_PARMS \
129 typename VertexProperty, typename EdgeProperty, \
130 typename GraphProperty, typename Vertex, typename EdgeIndex
131#define BOOST_BIDIR_CSR_GRAPH_TYPE \
132 compressed_sparse_row_graph<bidirectionalS, VertexProperty, EdgeProperty, \
133 GraphProperty, Vertex, EdgeIndex>
134
135namespace detail {
136 template <typename T>
137 struct default_construct_iterator: public boost::iterator_facade<default_construct_iterator<T>, T, boost::random_access_traversal_tag, const T&> {
138 typedef boost::iterator_facade<default_construct_iterator<T>, T, std::random_access_iterator_tag, const T&> base_type;
139 T saved_value;
140 const T& dereference() const {return saved_value;}
141 bool equal(default_construct_iterator /*i*/) const {return true;}
142 void increment() {}
143 void decrement() {}
144 void advance(typename base_type::difference_type) {}
145 typename base_type::difference_type distance_to(default_construct_iterator) const {return 0;}
146 };
147
148 template <typename Less>
149 struct compare_first {
150 Less less;
151 compare_first(Less less = Less()): less(less) {}
152 template <typename Tuple>
153 bool operator()(const Tuple& a, const Tuple& b) const {
154 return less(a.template get<0>(), b.template get<0>());
155 }
156 };
157
158 template <int N, typename Result>
159 struct my_tuple_get_class {
160 typedef const Result& result_type;
161 template <typename Tuple>
162 result_type operator()(const Tuple& t) const {
163 return t.template get<N>();
164 }
165 };
166}
167
168/** Compressed sparse row graph.
169 *
170 * Vertex and EdgeIndex should be unsigned integral types and should
171 * specialize numeric_limits.
172 */
173template<typename Directed = directedS,
174 typename VertexProperty = no_property,
175 typename EdgeProperty = no_property,
176 typename GraphProperty = no_property,
177 typename Vertex = std::size_t,
178 typename EdgeIndex = Vertex>
179class compressed_sparse_row_graph; // Not defined
180
181template<typename VertexProperty,
182 typename EdgeProperty,
183 typename GraphProperty,
184 typename Vertex,
185 typename EdgeIndex>
186class compressed_sparse_row_graph<directedS, VertexProperty, EdgeProperty, GraphProperty, Vertex, EdgeIndex>
187 : public detail::indexed_vertex_properties<BOOST_DIR_CSR_GRAPH_TYPE,
188 VertexProperty, Vertex, typed_identity_property_map<Vertex> >
189{
190 public:
191 typedef detail::indexed_vertex_properties<compressed_sparse_row_graph,
192 VertexProperty, Vertex, typed_identity_property_map<Vertex> >
193 inherited_vertex_properties;
194
195 // Some tests to prevent use of "void" is a property type (as was done in some test cases):
196 BOOST_STATIC_ASSERT((!is_same<VertexProperty, void>::value));
197 BOOST_STATIC_ASSERT((!is_same<EdgeProperty, void>::value));
198 BOOST_STATIC_ASSERT((!is_same<GraphProperty, void>::value));
199
200 public:
201 // For Property Graph
202 typedef GraphProperty graph_property_type;
203 typedef typename lookup_one_property<GraphProperty, graph_bundle_t>::type graph_bundled;
204
205 typedef detail::compressed_sparse_row_structure<EdgeProperty, Vertex, EdgeIndex> forward_type;
206
207 public:
208 /* At this time, the compressed sparse row graph can only be used to
209 * create directed and bidirectional graphs. In the future,
210 * undirected CSR graphs will also be supported.
211 */
212 // BOOST_STATIC_ASSERT((is_same<Directed, directedS>::value));
213
214 // Concept requirements:
215 // For Graph
216 typedef Vertex vertex_descriptor;
217 typedef detail::csr_edge_descriptor<Vertex, EdgeIndex> edge_descriptor;
218 typedef directed_tag directed_category;
219 typedef allow_parallel_edge_tag edge_parallel_category;
220
221 class traversal_category: public incidence_graph_tag,
222 public adjacency_graph_tag,
223 public vertex_list_graph_tag,
224 public edge_list_graph_tag {};
225
226 static vertex_descriptor null_vertex() { return vertex_descriptor(-1); }
227
228 // For VertexListGraph
229 typedef counting_iterator<Vertex> vertex_iterator;
230 typedef Vertex vertices_size_type;
231
232 // For EdgeListGraph
233 typedef EdgeIndex edges_size_type;
234
235 // For IncidenceGraph
236 typedef detail::csr_out_edge_iterator<compressed_sparse_row_graph> out_edge_iterator;
237 typedef EdgeIndex degree_size_type;
238
239 // For AdjacencyGraph
240 typedef typename std::vector<Vertex>::const_iterator adjacency_iterator;
241
242 // For EdgeListGraph
243 typedef detail::csr_edge_iterator<compressed_sparse_row_graph> edge_iterator;
244
245 // For BidirectionalGraph (not implemented)
246 typedef void in_edge_iterator;
247
248 // For internal use
249 typedef csr_graph_tag graph_tag;
250
251 typedef typename forward_type::inherited_edge_properties::edge_bundled edge_bundled;
252 typedef typename forward_type::inherited_edge_properties::edge_push_back_type edge_push_back_type;
253 typedef typename forward_type::inherited_edge_properties::edge_property_type edge_property_type;
254
255 // Constructors
256
257 // Default constructor: an empty graph.
258 compressed_sparse_row_graph(): m_property() {}
259
260 // With numverts vertices
261 compressed_sparse_row_graph(vertices_size_type numverts)
262 : inherited_vertex_properties(numverts), m_forward(numverts) {}
263
264 // From number of vertices and unsorted list of edges
265 template <typename MultiPassInputIterator>
266 compressed_sparse_row_graph(edges_are_unsorted_multi_pass_t,
267 MultiPassInputIterator edge_begin,
268 MultiPassInputIterator edge_end,
269 vertices_size_type numverts,
270 const GraphProperty& prop = GraphProperty())
271 : inherited_vertex_properties(numverts), m_property(prop)
272 {
273 m_forward.assign_unsorted_multi_pass_edges(edge_begin, edge_end, numverts, typed_identity_property_map<vertices_size_type>(), keep_all());
274 }
275
276 // From number of vertices and unsorted list of edges, plus edge properties
277 template <typename MultiPassInputIterator, typename EdgePropertyIterator>
278 compressed_sparse_row_graph(edges_are_unsorted_multi_pass_t,
279 MultiPassInputIterator edge_begin,
280 MultiPassInputIterator edge_end,
281 EdgePropertyIterator ep_iter,
282 vertices_size_type numverts,
283 const GraphProperty& prop = GraphProperty())
284 : inherited_vertex_properties(numverts), m_forward(), m_property(prop)
285 {
286 m_forward.assign_unsorted_multi_pass_edges(edge_begin, edge_end, ep_iter, numverts, typed_identity_property_map<vertices_size_type>(), keep_all());
287 }
288
289 // From number of vertices and unsorted list of edges, with filter and
290 // global-to-local map
291 template <typename MultiPassInputIterator, typename GlobalToLocal, typename SourcePred>
292 compressed_sparse_row_graph(edges_are_unsorted_multi_pass_global_t,
293 MultiPassInputIterator edge_begin,
294 MultiPassInputIterator edge_end,
295 vertices_size_type numlocalverts,
296 const GlobalToLocal& global_to_local,
297 const SourcePred& source_pred,
298 const GraphProperty& prop = GraphProperty())
299 : inherited_vertex_properties(numlocalverts), m_forward(), m_property(prop)
300 {
301 m_forward.assign_unsorted_multi_pass_edges(edge_begin, edge_end, numlocalverts, global_to_local, source_pred);
302 }
303
304 // From number of vertices and unsorted list of edges, plus edge properties,
305 // with filter and global-to-local map
306 template <typename MultiPassInputIterator, typename EdgePropertyIterator, typename GlobalToLocal, typename SourcePred>
307 compressed_sparse_row_graph(edges_are_unsorted_multi_pass_global_t,
308 MultiPassInputIterator edge_begin,
309 MultiPassInputIterator edge_end,
310 EdgePropertyIterator ep_iter,
311 vertices_size_type numlocalverts,
312 const GlobalToLocal& global_to_local,
313 const SourcePred& source_pred,
314 const GraphProperty& prop = GraphProperty())
315 : inherited_vertex_properties(numlocalverts), m_forward(), m_property(prop)
316 {
317 m_forward.assign_unsorted_multi_pass_edges(edge_begin, edge_end, ep_iter, numlocalverts, global_to_local, source_pred);
318 }
319
320 // From number of vertices and sorted list of edges (new interface)
321 template<typename InputIterator>
322 compressed_sparse_row_graph(edges_are_sorted_t,
323 InputIterator edge_begin, InputIterator edge_end,
324 vertices_size_type numverts,
325 edges_size_type numedges = 0,
326 const GraphProperty& prop = GraphProperty())
327 : m_property(prop)
328 {
329 m_forward.assign_from_sorted_edges(edge_begin, edge_end, typed_identity_property_map<vertices_size_type>(), keep_all(), numverts, numedges);
330 inherited_vertex_properties::resize(numverts);
331 }
332
333 // From number of vertices and sorted list of edges (new interface)
334 template<typename InputIterator, typename EdgePropertyIterator>
335 compressed_sparse_row_graph(edges_are_sorted_t,
336 InputIterator edge_begin, InputIterator edge_end,
337 EdgePropertyIterator ep_iter,
338 vertices_size_type numverts,
339 edges_size_type numedges = 0,
340 const GraphProperty& prop = GraphProperty())
341 : m_property(prop)
342 {
343 m_forward.assign_from_sorted_edges(edge_begin, edge_end, ep_iter, typed_identity_property_map<vertices_size_type>(), keep_all(), numverts, numedges);
344 inherited_vertex_properties::resize(numverts);
345 }
346
347 // From number of vertices and sorted list of edges, filtered and global (new interface)
348 template<typename InputIterator, typename GlobalToLocal, typename SourcePred>
349 compressed_sparse_row_graph(edges_are_sorted_global_t,
350 InputIterator edge_begin, InputIterator edge_end,
351 const GlobalToLocal& global_to_local,
352 const SourcePred& source_pred,
353 vertices_size_type numverts,
354 const GraphProperty& prop = GraphProperty())
355 : m_property(prop)
356 {
357 m_forward.assign_from_sorted_edges(edge_begin, edge_end, global_to_local, source_pred, numverts, 0);
358 inherited_vertex_properties::resize(numverts);
359 }
360
361 // From number of vertices and sorted list of edges (new interface)
362 template<typename InputIterator, typename EdgePropertyIterator, typename GlobalToLocal, typename SourcePred>
363 compressed_sparse_row_graph(edges_are_sorted_global_t,
364 InputIterator edge_begin, InputIterator edge_end,
365 EdgePropertyIterator ep_iter,
366 const GlobalToLocal& global_to_local,
367 const SourcePred& source_pred,
368 vertices_size_type numverts,
369 const GraphProperty& prop = GraphProperty())
370 : m_property(prop)
371 {
372 m_forward.assign_from_sorted_edges(edge_begin, edge_end, ep_iter, global_to_local, source_pred, numverts, 0);
373 inherited_vertex_properties::resize(numverts);
374 }
375
376 // From number of vertices and mutable vectors of sources and targets;
377 // vectors are returned with unspecified contents but are guaranteed not to
378 // share storage with the constructed graph.
379 compressed_sparse_row_graph(construct_inplace_from_sources_and_targets_t,
380 std::vector<vertex_descriptor>& sources,
381 std::vector<vertex_descriptor>& targets,
382 vertices_size_type numverts,
383 const GraphProperty& prop = GraphProperty())
384 : inherited_vertex_properties(numverts), m_property(prop)
385 {
386 m_forward.assign_sources_and_targets_global(sources, targets, numverts, boost::typed_identity_property_map<vertices_size_type>());
387 }
388
389 // From number of vertices and mutable vectors of sources and targets,
390 // expressed with global vertex indices; vectors are returned with
391 // unspecified contents but are guaranteed not to share storage with the
392 // constructed graph. This constructor should only be used by the
393 // distributed CSR graph.
394 template <typename GlobalToLocal>
395 compressed_sparse_row_graph(construct_inplace_from_sources_and_targets_global_t,
396 std::vector<vertex_descriptor>& sources,
397 std::vector<vertex_descriptor>& targets,
398 vertices_size_type numlocalverts,
399 GlobalToLocal global_to_local,
400 const GraphProperty& prop = GraphProperty())
401 : inherited_vertex_properties(numlocalverts), m_property(prop)
402 {
403 m_forward.assign_sources_and_targets_global(sources, targets, numlocalverts, global_to_local);
404 }
405
406 // From number of vertices and mutable vectors of sources, targets, and edge
407 // properties; vectors are returned with unspecified contents but are
408 // guaranteed not to share storage with the constructed graph.
409 compressed_sparse_row_graph(construct_inplace_from_sources_and_targets_t,
410 std::vector<vertex_descriptor>& sources,
411 std::vector<vertex_descriptor>& targets,
412 std::vector<typename forward_type::inherited_edge_properties::edge_bundled>& edge_props,
413 vertices_size_type numverts,
414 const GraphProperty& prop = GraphProperty())
415 : inherited_vertex_properties(numverts), m_property(prop)
416 {
417 m_forward.assign_sources_and_targets_global(sources, targets, edge_props, numverts, boost::typed_identity_property_map<vertices_size_type>());
418 }
419
420 // From number of vertices and mutable vectors of sources and targets and
421 // edge properties, expressed with global vertex indices; vectors are
422 // returned with unspecified contents but are guaranteed not to share
423 // storage with the constructed graph. This constructor should only be used
424 // by the distributed CSR graph.
425 template <typename GlobalToLocal>
426 compressed_sparse_row_graph(construct_inplace_from_sources_and_targets_global_t,
427 std::vector<vertex_descriptor>& sources,
428 std::vector<vertex_descriptor>& targets,
429 std::vector<typename forward_type::inherited_edge_properties::edge_bundled>& edge_props,
430 vertices_size_type numlocalverts,
431 GlobalToLocal global_to_local,
432 const GraphProperty& prop = GraphProperty())
433 : inherited_vertex_properties(numlocalverts), m_property(prop)
434 {
435 m_forward.assign_sources_and_targets_global(sources, targets, edge_props, numlocalverts, global_to_local);
436 }
437
438 // From number of vertices and single-pass range of unsorted edges. Data is
439 // cached in coordinate form before creating the actual graph.
440 template<typename InputIterator>
441 compressed_sparse_row_graph(edges_are_unsorted_t,
442 InputIterator edge_begin, InputIterator edge_end,
443 vertices_size_type numverts,
444 const GraphProperty& prop = GraphProperty())
445 : inherited_vertex_properties(numverts), m_property(prop)
446 {
447 std::vector<vertex_descriptor> sources, targets;
448 boost::graph::detail::split_into_separate_coords
449 (edge_begin, edge_end, sources, targets);
450 m_forward.assign_sources_and_targets_global(sources, targets, numverts, boost::typed_identity_property_map<vertices_size_type>());
451 }
452
453 // From number of vertices and single-pass range of unsorted edges and
454 // single-pass range of edge properties. Data is cached in coordinate form
455 // before creating the actual graph.
456 template<typename InputIterator, typename EdgePropertyIterator>
457 compressed_sparse_row_graph(edges_are_unsorted_t,
458 InputIterator edge_begin, InputIterator edge_end,
459 EdgePropertyIterator ep_iter,
460 vertices_size_type numverts,
461 const GraphProperty& prop = GraphProperty())
462 : inherited_vertex_properties(numverts), m_property(prop)
463 {
464 std::vector<vertex_descriptor> sources, targets;
465 boost::graph::detail::split_into_separate_coords
466 (edge_begin, edge_end, sources, targets);
467 size_t numedges = sources.size();
468 std::vector<typename forward_type::inherited_edge_properties::edge_bundled> edge_props(numedges);
469 for (size_t i = 0; i < numedges; ++i) {
470 edge_props[i] = *ep_iter++;
471 }
472 m_forward.assign_sources_and_targets_global(sources, targets, edge_props, numverts, boost::typed_identity_property_map<vertices_size_type>());
473 }
474
475 // From number of vertices and single-pass range of unsorted edges. Data is
476 // cached in coordinate form before creating the actual graph. Edges are
477 // filtered and transformed for use in a distributed graph.
478 template<typename InputIterator, typename GlobalToLocal, typename SourcePred>
479 compressed_sparse_row_graph(edges_are_unsorted_global_t,
480 InputIterator edge_begin, InputIterator edge_end,
481 vertices_size_type numlocalverts,
482 GlobalToLocal global_to_local,
483 const SourcePred& source_pred,
484 const GraphProperty& prop = GraphProperty())
485 : inherited_vertex_properties(numlocalverts), m_property(prop)
486 {
487 std::vector<vertex_descriptor> sources, targets;
488 boost::graph::detail::split_into_separate_coords_filtered
489 (edge_begin, edge_end, sources, targets, source_pred);
490 m_forward.assign_sources_and_targets_global(sources, targets, numlocalverts, global_to_local);
491 }
492
493 // From number of vertices and single-pass range of unsorted edges and
494 // single-pass range of edge properties. Data is cached in coordinate form
495 // before creating the actual graph. Edges are filtered and transformed for
496 // use in a distributed graph.
497 template<typename InputIterator, typename EdgePropertyIterator,
498 typename GlobalToLocal, typename SourcePred>
499 compressed_sparse_row_graph(edges_are_unsorted_global_t,
500 InputIterator edge_begin, InputIterator edge_end,
501 EdgePropertyIterator ep_iter,
502 vertices_size_type numlocalverts,
503 GlobalToLocal global_to_local,
504 const SourcePred& source_pred,
505 const GraphProperty& prop = GraphProperty())
506 : inherited_vertex_properties(numlocalverts), m_property(prop)
507 {
508 std::vector<vertex_descriptor> sources, targets;
509 std::vector<edge_bundled> edge_props;
510 boost::graph::detail::split_into_separate_coords_filtered
511 (edge_begin, edge_end, ep_iter, sources, targets, edge_props, source_pred);
512 m_forward.assign_sources_and_targets_global(sources, targets, edge_props, numlocalverts, global_to_local);
513 }
514
515
516 // Requires IncidenceGraph and a vertex index map
517 template<typename Graph, typename VertexIndexMap>
518 compressed_sparse_row_graph(const Graph& g, const VertexIndexMap& vi,
519 vertices_size_type numverts,
520 edges_size_type numedges)
521 : m_property()
522 {
523 assign(g, vi, numverts, numedges);
524 inherited_vertex_properties::resize(numverts);
525 }
526
527 // Requires VertexListGraph and EdgeListGraph
528 template<typename Graph, typename VertexIndexMap>
529 compressed_sparse_row_graph(const Graph& g, const VertexIndexMap& vi)
530 : m_property()
531 {
532 typename graph_traits<Graph>::edges_size_type numedges = num_edges(g);
533 if (is_same<typename graph_traits<Graph>::directed_category, undirectedS>::value) {
534 numedges *= 2; // Double each edge (actual doubling done by out_edges function)
535 }
536 vertices_size_type numverts = num_vertices(g);
537 assign(g, vi, numverts, numedges);
538 inherited_vertex_properties::resize(numverts);
539 }
540
541 // Requires vertex index map plus requirements of previous constructor
542 template<typename Graph>
543 explicit compressed_sparse_row_graph(const Graph& g)
544 : m_property()
545 {
546 typename graph_traits<Graph>::edges_size_type numedges = num_edges(g);
547 if (is_same<typename graph_traits<Graph>::directed_category, undirectedS>::value) {
548 numedges *= 2; // Double each edge (actual doubling done by out_edges function)
549 }
550 assign(g, get(vertex_index, g), num_vertices(g), numedges);
551 }
552
553 // From any graph (slow and uses a lot of memory)
554 // Requires IncidenceGraph and a vertex index map
555 // Internal helper function
556 // Note that numedges must be doubled for undirected source graphs
557 template<typename Graph, typename VertexIndexMap>
558 void
559 assign(const Graph& g, const VertexIndexMap& vi,
560 vertices_size_type numverts, edges_size_type numedges)
561 {
562 m_forward.assign(g, vi, numverts, numedges);
563 inherited_vertex_properties::resize(numverts);
564 }
565
566 // Requires the above, plus VertexListGraph and EdgeListGraph
567 template<typename Graph, typename VertexIndexMap>
568 void assign(const Graph& g, const VertexIndexMap& vi)
569 {
570 typename graph_traits<Graph>::edges_size_type numedges = num_edges(g);
571 if (is_same<typename graph_traits<Graph>::directed_category, undirectedS>::value) {
572 numedges *= 2; // Double each edge (actual doubling done by out_edges function)
573 }
574 vertices_size_type numverts = num_vertices(g);
575 m_forward.assign(g, vi, numverts, numedges);
576 inherited_vertex_properties::resize(numverts);
577 }
578
579 // Requires the above, plus a vertex_index map.
580 template<typename Graph>
581 void assign(const Graph& g)
582 {
583 typename graph_traits<Graph>::edges_size_type numedges = num_edges(g);
584 if (is_same<typename graph_traits<Graph>::directed_category, undirectedS>::value) {
585 numedges *= 2; // Double each edge (actual doubling done by out_edges function)
586 }
587 vertices_size_type numverts = num_vertices(g);
588 m_forward.assign(g, get(vertex_index, g), numverts, numedges);
589 inherited_vertex_properties::resize(numverts);
590 }
591
592 // Add edges from a sorted (smallest sources first) range of pairs and edge
593 // properties
594 template <typename BidirectionalIteratorOrig, typename EPIterOrig,
595 typename GlobalToLocal>
596 void
597 add_edges_sorted_internal(
598 BidirectionalIteratorOrig first_sorted,
599 BidirectionalIteratorOrig last_sorted,
600 EPIterOrig ep_iter_sorted,
601 const GlobalToLocal& global_to_local) {
602 m_forward.add_edges_sorted_internal(first_sorted, last_sorted, ep_iter_sorted, global_to_local);
603 }
604
605 template <typename BidirectionalIteratorOrig, typename EPIterOrig>
606 void
607 add_edges_sorted_internal(
608 BidirectionalIteratorOrig first_sorted,
609 BidirectionalIteratorOrig last_sorted,
610 EPIterOrig ep_iter_sorted) {
611 m_forward.add_edges_sorted_internal(first_sorted, last_sorted, ep_iter_sorted, typed_identity_property_map<vertices_size_type>());
612 }
613
614 // Add edges from a sorted (smallest sources first) range of pairs
615 template <typename BidirectionalIteratorOrig>
616 void
617 add_edges_sorted_internal(
618 BidirectionalIteratorOrig first_sorted,
619 BidirectionalIteratorOrig last_sorted) {
620 m_forward.add_edges_sorted_internal(first_sorted, last_sorted, detail::default_construct_iterator<edge_bundled>());
621 }
622
623 template <typename BidirectionalIteratorOrig, typename GlobalToLocal>
624 void
625 add_edges_sorted_internal_global(
626 BidirectionalIteratorOrig first_sorted,
627 BidirectionalIteratorOrig last_sorted,
628 const GlobalToLocal& global_to_local) {
629 m_forward.add_edges_sorted_internal(first_sorted, last_sorted, detail::default_construct_iterator<edge_bundled>(), global_to_local);
630 }
631
632 template <typename BidirectionalIteratorOrig, typename EPIterOrig,
633 typename GlobalToLocal>
634 void
635 add_edges_sorted_internal_global(
636 BidirectionalIteratorOrig first_sorted,
637 BidirectionalIteratorOrig last_sorted,
638 EPIterOrig ep_iter_sorted,
639 const GlobalToLocal& global_to_local) {
640 m_forward.add_edges_sorted_internal(first_sorted, last_sorted, ep_iter_sorted, global_to_local);
641 }
642
643 // Add edges from a range of (source, target) pairs that are unsorted
644 template <typename InputIterator, typename GlobalToLocal>
645 inline void
646 add_edges_internal(InputIterator first, InputIterator last,
647 const GlobalToLocal& global_to_local) {
648 typedef compressed_sparse_row_graph Graph;
649 typedef typename boost::graph_traits<Graph>::vertex_descriptor vertex_t;
650 typedef std::vector<std::pair<vertex_t, vertex_t> > edge_vector_t;
651 edge_vector_t new_edges(first, last);
652 if (new_edges.empty()) return;
653 std::sort(new_edges.begin(), new_edges.end());
654 this->add_edges_sorted_internal_global(new_edges.begin(), new_edges.end(), global_to_local);
655 }
656
657 template <typename InputIterator>
658 inline void
659 add_edges_internal(InputIterator first, InputIterator last) {
660 this->add_edges_internal(first, last, typed_identity_property_map<vertices_size_type>());
661 }
662
663 // Add edges from a range of (source, target) pairs and edge properties that
664 // are unsorted
665 template <typename InputIterator, typename EPIterator, typename GlobalToLocal>
666 inline void
667 add_edges_internal(InputIterator first, InputIterator last,
668 EPIterator ep_iter, EPIterator ep_iter_end,
669 const GlobalToLocal& global_to_local) {
670 typedef compressed_sparse_row_graph Graph;
671 typedef typename boost::graph_traits<Graph>::vertex_descriptor vertex_t;
672 typedef std::pair<vertex_t, vertex_t> vertex_pair;
673 typedef std::vector<
674 boost::tuple<vertex_pair,
675 edge_bundled> >
676 edge_vector_t;
677 edge_vector_t new_edges
678 (boost::make_zip_iterator(boost::make_tuple(first, ep_iter)),
679 boost::make_zip_iterator(boost::make_tuple(last, ep_iter_end)));
680 if (new_edges.empty()) return;
681 std::sort(new_edges.begin(), new_edges.end(),
682 boost::detail::compare_first<
683 std::less<vertex_pair> >());
684 m_forward.add_edges_sorted_internal
685 (boost::make_transform_iterator(
686 new_edges.begin(),
687 boost::detail::my_tuple_get_class<0, vertex_pair>()),
688 boost::make_transform_iterator(
689 new_edges.end(),
690 boost::detail::my_tuple_get_class<0, vertex_pair>()),
691 boost::make_transform_iterator(
692 new_edges.begin(),
693 boost::detail::my_tuple_get_class
694 <1, edge_bundled>()),
695 global_to_local);
696 }
697
698 // Add edges from a range of (source, target) pairs and edge properties that
699 // are unsorted
700 template <typename InputIterator, typename EPIterator>
701 inline void
702 add_edges_internal(InputIterator first, InputIterator last,
703 EPIterator ep_iter, EPIterator ep_iter_end) {
704 this->add_edges_internal(first, last, ep_iter, ep_iter_end, typed_identity_property_map<vertices_size_type>());
705 }
706
707 using inherited_vertex_properties::operator[];
708
709 // Directly access a edge or edge bundle
710 edge_push_back_type& operator[](const edge_descriptor& v)
711 { return m_forward.m_edge_properties[get(edge_index, *this, v)]; }
712
713 const edge_push_back_type& operator[](const edge_descriptor& v) const
714 { return m_forward.m_edge_properties[get(edge_index, *this, v)]; }
715
716 // Directly access a graph bundle
717 graph_bundled& operator[](graph_bundle_t)
718 { return get_property(*this); }
719
720 const graph_bundled& operator[](graph_bundle_t) const
721 { return get_property(*this); }
722
723 // private: non-portable, requires friend templates
724 inherited_vertex_properties& vertex_properties() {return *this;}
725 const inherited_vertex_properties& vertex_properties() const {return *this;}
726 typename forward_type::inherited_edge_properties& edge_properties() { return m_forward; }
727 const typename forward_type::inherited_edge_properties& edge_properties() const { return m_forward; }
728
729 forward_type m_forward;
730 GraphProperty m_property;
731};
732
733template<typename VertexProperty,
734 typename EdgeProperty,
735 typename GraphProperty,
736 typename Vertex,
737 typename EdgeIndex>
738class compressed_sparse_row_graph<bidirectionalS, VertexProperty, EdgeProperty, GraphProperty, Vertex, EdgeIndex>
739 : public detail::indexed_vertex_properties<BOOST_BIDIR_CSR_GRAPH_TYPE,
740 VertexProperty, Vertex, typed_identity_property_map<Vertex> >
741{
742 public:
743 typedef detail::indexed_vertex_properties<compressed_sparse_row_graph,
744 VertexProperty, Vertex, typed_identity_property_map<Vertex> >
745 inherited_vertex_properties;
746
747 public:
748 // For Property Graph
749 typedef GraphProperty graph_property_type;
750 typedef typename lookup_one_property<GraphProperty, graph_bundle_t>::type graph_bundled;
751 // typedef GraphProperty graph_property_type;
752
753 typedef detail::compressed_sparse_row_structure<EdgeProperty, Vertex, EdgeIndex> forward_type;
754 typedef EdgeIndex /* typename boost::mpl::if_c<boost::is_same<EdgeProperty, boost::no_property>, boost::no_property, EdgeIndex> */ backward_edge_property;
755 typedef detail::compressed_sparse_row_structure<backward_edge_property, Vertex, EdgeIndex> backward_type;
756
757 public:
758 // Concept requirements:
759 // For Graph
760 typedef Vertex vertex_descriptor;
761 typedef detail::csr_edge_descriptor<Vertex, EdgeIndex> edge_descriptor;
762 typedef bidirectional_tag directed_category;
763 typedef allow_parallel_edge_tag edge_parallel_category;
764
765 class traversal_category: public bidirectional_graph_tag,
766 public adjacency_graph_tag,
767 public vertex_list_graph_tag,
768 public edge_list_graph_tag {};
769
770 static vertex_descriptor null_vertex() { return vertex_descriptor(-1); }
771
772 // For VertexListGraph
773 typedef counting_iterator<Vertex> vertex_iterator;
774 typedef Vertex vertices_size_type;
775
776 // For EdgeListGraph
777 typedef EdgeIndex edges_size_type;
778
779 // For IncidenceGraph
780 typedef detail::csr_out_edge_iterator<compressed_sparse_row_graph> out_edge_iterator;
781 typedef EdgeIndex degree_size_type;
782
783 // For AdjacencyGraph
784 typedef typename std::vector<Vertex>::const_iterator adjacency_iterator;
785
786 // For EdgeListGraph
787 typedef detail::csr_edge_iterator<compressed_sparse_row_graph> edge_iterator;
788
789 // For BidirectionalGraph (not implemented)
790 typedef detail::csr_in_edge_iterator<compressed_sparse_row_graph> in_edge_iterator;
791
792 // For internal use
793 typedef csr_graph_tag graph_tag;
794
795 typedef typename forward_type::inherited_edge_properties::edge_bundled edge_bundled;
796 typedef typename forward_type::inherited_edge_properties::edge_push_back_type edge_push_back_type;
797 typedef typename forward_type::inherited_edge_properties::edge_property_type edge_property_type;
798
799 // Constructors
800
801 // Default constructor: an empty graph.
802 compressed_sparse_row_graph(): m_property() {}
803
804 // With numverts vertices
805 compressed_sparse_row_graph(vertices_size_type numverts)
806 : inherited_vertex_properties(numverts),
807 m_forward(numverts), m_backward(numverts) {}
808
809 private:
810
811 void set_up_backward_property_links() {
812 std::pair<edge_iterator, edge_iterator> e = edges(*this);
813 m_backward.assign_unsorted_multi_pass_edges
814 (detail::transpose_edges(
815 detail::make_edge_to_index_pair_iter
816 (*this, get(vertex_index, *this), e.first)),
817 detail::transpose_edges(
818 detail::make_edge_to_index_pair_iter
819 (*this, get(vertex_index, *this), e.second)),
820 boost::counting_iterator<EdgeIndex>(0),
821 m_forward.m_rowstart.size() - 1,
822 typed_identity_property_map<Vertex>(),
823 keep_all());
824 }
825
826 public:
827
828 // From number of vertices and unsorted list of edges
829 template <typename MultiPassInputIterator>
830 compressed_sparse_row_graph(edges_are_unsorted_multi_pass_t,
831 MultiPassInputIterator edge_begin,
832 MultiPassInputIterator edge_end,
833 vertices_size_type numverts,
834 const GraphProperty& prop = GraphProperty())
835 : inherited_vertex_properties(numverts), m_property(prop)
836 {
837 m_forward.assign_unsorted_multi_pass_edges(edge_begin, edge_end, numverts, typed_identity_property_map<Vertex>(), keep_all());
838 set_up_backward_property_links();
839 }
840
841 // From number of vertices and unsorted list of edges, plus edge properties
842 template <typename MultiPassInputIterator, typename EdgePropertyIterator>
843 compressed_sparse_row_graph(edges_are_unsorted_multi_pass_t,
844 MultiPassInputIterator edge_begin,
845 MultiPassInputIterator edge_end,
846 EdgePropertyIterator ep_iter,
847 vertices_size_type numverts,
848 const GraphProperty& prop = GraphProperty())
849 : inherited_vertex_properties(numverts), m_forward(), m_property(prop)
850 {
851 m_forward.assign_unsorted_multi_pass_edges(edge_begin, edge_end, ep_iter, numverts, typed_identity_property_map<Vertex>(), keep_all());
852 set_up_backward_property_links();
853 }
854
855 // From number of vertices and unsorted list of edges, with filter and
856 // global-to-local map
857 template <typename MultiPassInputIterator, typename GlobalToLocal, typename SourcePred>
858 compressed_sparse_row_graph(edges_are_unsorted_multi_pass_global_t,
859 MultiPassInputIterator edge_begin,
860 MultiPassInputIterator edge_end,
861 vertices_size_type numlocalverts,
862 const GlobalToLocal& global_to_local,
863 const SourcePred& source_pred,
864 const GraphProperty& prop = GraphProperty())
865 : inherited_vertex_properties(numlocalverts), m_forward(), m_property(prop)
866 {
867 m_forward.assign_unsorted_multi_pass_edges(edge_begin, edge_end, numlocalverts, global_to_local, source_pred);
868 set_up_backward_property_links();
869 }
870
871 // From number of vertices and unsorted list of edges, plus edge properties,
872 // with filter and global-to-local map
873 template <typename MultiPassInputIterator, typename EdgePropertyIterator, typename GlobalToLocal, typename SourcePred>
874 compressed_sparse_row_graph(edges_are_unsorted_multi_pass_global_t,
875 MultiPassInputIterator edge_begin,
876 MultiPassInputIterator edge_end,
877 EdgePropertyIterator ep_iter,
878 vertices_size_type numlocalverts,
879 const GlobalToLocal& global_to_local,
880 const SourcePred& source_pred,
881 const GraphProperty& prop = GraphProperty())
882 : inherited_vertex_properties(numlocalverts), m_forward(), m_property(prop)
883 {
884 m_forward.assign_unsorted_multi_pass_edges(edge_begin, edge_end, ep_iter, numlocalverts, global_to_local, source_pred);
885 set_up_backward_property_links();
886 }
887
888 // Requires IncidenceGraph and a vertex index map
889 template<typename Graph, typename VertexIndexMap>
890 compressed_sparse_row_graph(const Graph& g, const VertexIndexMap& vi,
891 vertices_size_type numverts,
892 edges_size_type numedges)
893 : m_property()
894 {
895 assign(g, vi, numverts, numedges);
896 inherited_vertex_properties::resize(numverts);
897 }
898
899 // Requires VertexListGraph and EdgeListGraph
900 template<typename Graph, typename VertexIndexMap>
901 compressed_sparse_row_graph(const Graph& g, const VertexIndexMap& vi)
902 : m_property()
903 {
904 typename graph_traits<Graph>::edges_size_type numedges = num_edges(g);
905 if (is_same<typename graph_traits<Graph>::directed_category, undirectedS>::value) {
906 numedges *= 2; // Double each edge (actual doubling done by out_edges function)
907 }
908 vertices_size_type numverts = num_vertices(g);
909 assign(g, vi, numverts, numedges);
910 inherited_vertex_properties::resize(numverts);
911 }
912
913 // Requires vertex index map plus requirements of previous constructor
914 template<typename Graph>
915 explicit compressed_sparse_row_graph(const Graph& g)
916 : m_property()
917 {
918 typename graph_traits<Graph>::edges_size_type numedges = num_edges(g);
919 if (is_same<typename graph_traits<Graph>::directed_category, undirectedS>::value) {
920 numedges *= 2; // Double each edge (actual doubling done by out_edges function)
921 }
922 assign(g, get(vertex_index, g), num_vertices(g), numedges);
923 }
924
925 // From any graph (slow and uses a lot of memory)
926 // Requires IncidenceGraph and a vertex index map
927 // Internal helper function
928 // Note that numedges must be doubled for undirected source graphs
929 template<typename Graph, typename VertexIndexMap>
930 void
931 assign(const Graph& g, const VertexIndexMap& vi,
932 vertices_size_type numverts, edges_size_type numedges)
933 {
934 m_forward.assign(g, vi, numverts, numedges);
935 inherited_vertex_properties::resize(numverts);
936 set_up_backward_property_links();
937 }
938
939 // Requires the above, plus VertexListGraph and EdgeListGraph
940 template<typename Graph, typename VertexIndexMap>
941 void assign(const Graph& g, const VertexIndexMap& vi)
942 {
943 typename graph_traits<Graph>::edges_size_type numedges = num_edges(g);
944 if (is_same<typename graph_traits<Graph>::directed_category, undirectedS>::value) {
945 numedges *= 2; // Double each edge (actual doubling done by out_edges function)
946 }
947 vertices_size_type numverts = num_vertices(g);
948 m_forward.assign(g, vi, numverts, numedges);
949 inherited_vertex_properties::resize(numverts);
950 set_up_backward_property_links();
951 }
952
953 // Requires the above, plus a vertex_index map.
954 template<typename Graph>
955 void assign(const Graph& g)
956 {
957 typename graph_traits<Graph>::edges_size_type numedges = num_edges(g);
958 if (is_same<typename graph_traits<Graph>::directed_category, undirectedS>::value) {
959 numedges *= 2; // Double each edge (actual doubling done by out_edges function)
960 }
961 vertices_size_type numverts = num_vertices(g);
962 m_forward.assign(g, get(vertex_index, g), numverts, numedges);
963 inherited_vertex_properties::resize(numverts);
964 set_up_backward_property_links();
965 }
966
967 using inherited_vertex_properties::operator[];
968
969 // Directly access a edge or edge bundle
970 edge_push_back_type& operator[](const edge_descriptor& v)
971 { return m_forward.m_edge_properties[get(edge_index, *this, v)]; }
972
973 const edge_push_back_type& operator[](const edge_descriptor& v) const
974 { return m_forward.m_edge_properties[get(edge_index, *this, v)]; }
975
976 // private: non-portable, requires friend templates
977 inherited_vertex_properties& vertex_properties() {return *this;}
978 const inherited_vertex_properties& vertex_properties() const {return *this;}
979 typename forward_type::inherited_edge_properties& edge_properties() { return m_forward; }
980 const typename forward_type::inherited_edge_properties& edge_properties() const { return m_forward; }
981
982 forward_type m_forward;
983 backward_type m_backward;
984 GraphProperty m_property;
985};
986
987// Construction functions
988template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
989inline Vertex
990add_vertex(BOOST_CSR_GRAPH_TYPE& g) {
991 add_vertex(g, typename BOOST_CSR_GRAPH_TYPE::vertex_bundled());
992}
993
994template<BOOST_DIR_CSR_GRAPH_TEMPLATE_PARMS>
995inline Vertex
996add_vertex(BOOST_DIR_CSR_GRAPH_TYPE& g,
997 typename BOOST_DIR_CSR_GRAPH_TYPE::vertex_bundled const& p) {
998 Vertex old_num_verts_plus_one = g.m_forward.m_rowstart.size();
999 g.m_forward.m_rowstart.push_back(g.m_forward.m_rowstart.back());
1000 g.vertex_properties().push_back(p);
1001 return old_num_verts_plus_one - 1;
1002}
1003
1004template<BOOST_BIDIR_CSR_GRAPH_TEMPLATE_PARMS>
1005inline Vertex
1006add_vertex(BOOST_BIDIR_CSR_GRAPH_TYPE& g,
1007 typename BOOST_BIDIR_CSR_GRAPH_TYPE::vertex_bundled const& p) {
1008 Vertex old_num_verts_plus_one = g.m_forward.m_rowstart.size();
1009 g.m_forward.m_rowstart.push_back(g.m_forward.m_rowstart.back());
1010 g.m_backward.m_rowstart.push_back(g.m_backward.m_rowstart.back());
1011 g.vertex_properties().push_back(p);
1012 return old_num_verts_plus_one - 1;
1013}
1014
1015template<BOOST_DIR_CSR_GRAPH_TEMPLATE_PARMS>
1016inline Vertex
1017add_vertices(typename BOOST_DIR_CSR_GRAPH_TYPE::vertices_size_type count, BOOST_DIR_CSR_GRAPH_TYPE& g) {
1018 Vertex old_num_verts_plus_one = g.m_forward.m_rowstart.size();
1019 EdgeIndex numedges = g.m_forward.m_rowstart.back();
1020 g.m_forward.m_rowstart.resize(old_num_verts_plus_one + count, numedges);
1021 g.vertex_properties().resize(num_vertices(g));
1022 return old_num_verts_plus_one - 1;
1023}
1024
1025 // Add edges from a sorted (smallest sources first) range of pairs and edge
1026 // properties
1027 template <BOOST_DIR_CSR_GRAPH_TEMPLATE_PARMS, typename BidirectionalIteratorOrig,
1028 typename EPIterOrig>
1029 void
1030 add_edges_sorted(
1031 BidirectionalIteratorOrig first_sorted,
1032 BidirectionalIteratorOrig last_sorted,
1033 EPIterOrig ep_iter_sorted,
1034 BOOST_DIR_CSR_GRAPH_TYPE& g) {
1035 g.add_edges_sorted_internal(first_sorted, last_sorted, ep_iter_sorted);
1036 }
1037
1038 // Add edges from a sorted (smallest sources first) range of pairs
1039 template <BOOST_DIR_CSR_GRAPH_TEMPLATE_PARMS, typename BidirectionalIteratorOrig>
1040 void
1041 add_edges_sorted(
1042 BidirectionalIteratorOrig first_sorted,
1043 BidirectionalIteratorOrig last_sorted,
1044 BOOST_DIR_CSR_GRAPH_TYPE& g) {
1045 g.add_edges_sorted_internal(first_sorted, last_sorted);
1046 }
1047
1048 template <BOOST_DIR_CSR_GRAPH_TEMPLATE_PARMS, typename BidirectionalIteratorOrig,
1049 typename EPIterOrig, typename GlobalToLocal>
1050 void
1051 add_edges_sorted_global(
1052 BidirectionalIteratorOrig first_sorted,
1053 BidirectionalIteratorOrig last_sorted,
1054 EPIterOrig ep_iter_sorted,
1055 const GlobalToLocal& global_to_local,
1056 BOOST_DIR_CSR_GRAPH_TYPE& g) {
1057 g.add_edges_sorted_internal_global(first_sorted, last_sorted, ep_iter_sorted,
1058 global_to_local);
1059 }
1060
1061 // Add edges from a sorted (smallest sources first) range of pairs
1062 template <BOOST_DIR_CSR_GRAPH_TEMPLATE_PARMS, typename BidirectionalIteratorOrig,
1063 typename GlobalToLocal>
1064 void
1065 add_edges_sorted_global(
1066 BidirectionalIteratorOrig first_sorted,
1067 BidirectionalIteratorOrig last_sorted,
1068 const GlobalToLocal& global_to_local,
1069 BOOST_DIR_CSR_GRAPH_TYPE& g) {
1070 g.add_edges_sorted_internal_global(first_sorted, last_sorted, global_to_local);
1071 }
1072
1073 // Add edges from a range of (source, target) pairs that are unsorted
1074 template <BOOST_DIR_CSR_GRAPH_TEMPLATE_PARMS, typename InputIterator,
1075 typename GlobalToLocal>
1076 inline void
1077 add_edges_global(InputIterator first, InputIterator last,
1078 const GlobalToLocal& global_to_local, BOOST_DIR_CSR_GRAPH_TYPE& g) {
1079 g.add_edges_internal(first, last, global_to_local);
1080 }
1081
1082 // Add edges from a range of (source, target) pairs that are unsorted
1083 template <BOOST_DIR_CSR_GRAPH_TEMPLATE_PARMS, typename InputIterator>
1084 inline void
1085 add_edges(InputIterator first, InputIterator last, BOOST_DIR_CSR_GRAPH_TYPE& g) {
1086 g.add_edges_internal(first, last);
1087 }
1088
1089 // Add edges from a range of (source, target) pairs and edge properties that
1090 // are unsorted
1091 template <BOOST_DIR_CSR_GRAPH_TEMPLATE_PARMS,
1092 typename InputIterator, typename EPIterator>
1093 inline void
1094 add_edges(InputIterator first, InputIterator last,
1095 EPIterator ep_iter, EPIterator ep_iter_end,
1096 BOOST_DIR_CSR_GRAPH_TYPE& g) {
1097 g.add_edges_internal(first, last, ep_iter, ep_iter_end);
1098 }
1099
1100 template <BOOST_DIR_CSR_GRAPH_TEMPLATE_PARMS,
1101 typename InputIterator, typename EPIterator, typename GlobalToLocal>
1102 inline void
1103 add_edges_global(InputIterator first, InputIterator last,
1104 EPIterator ep_iter, EPIterator ep_iter_end,
1105 const GlobalToLocal& global_to_local,
1106 BOOST_DIR_CSR_GRAPH_TYPE& g) {
1107 g.add_edges_internal(first, last, ep_iter, ep_iter_end, global_to_local);
1108 }
1109
1110// From VertexListGraph
1111template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
1112inline Vertex
1113num_vertices(const BOOST_CSR_GRAPH_TYPE& g) {
1114 return g.m_forward.m_rowstart.size() - 1;
1115}
1116
1117template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
1118std::pair<counting_iterator<Vertex>, counting_iterator<Vertex> >
1119inline vertices(const BOOST_CSR_GRAPH_TYPE& g) {
1120 return std::make_pair(counting_iterator<Vertex>(0),
1121 counting_iterator<Vertex>(num_vertices(g)));
1122}
1123
1124// From IncidenceGraph
1125template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
1126inline Vertex
1127source(typename BOOST_CSR_GRAPH_TYPE::edge_descriptor e,
1128 const BOOST_CSR_GRAPH_TYPE&)
1129{
1130 return e.src;
1131}
1132
1133template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
1134inline Vertex
1135target(typename BOOST_CSR_GRAPH_TYPE::edge_descriptor e,
1136 const BOOST_CSR_GRAPH_TYPE& g)
1137{
1138 return g.m_forward.m_column[e.idx];
1139}
1140
1141template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
1142inline std::pair<typename BOOST_CSR_GRAPH_TYPE::out_edge_iterator,
1143 typename BOOST_CSR_GRAPH_TYPE::out_edge_iterator>
1144out_edges(Vertex v, const BOOST_CSR_GRAPH_TYPE& g)
1145{
1146 typedef typename BOOST_CSR_GRAPH_TYPE::edge_descriptor ed;
1147 typedef typename BOOST_CSR_GRAPH_TYPE::out_edge_iterator it;
1148 EdgeIndex v_row_start = g.m_forward.m_rowstart[v];
1149 EdgeIndex next_row_start = g.m_forward.m_rowstart[v + 1];
1150 return std::make_pair(it(ed(v, v_row_start)),
1151 it(ed(v, next_row_start)));
1152}
1153
1154template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
1155inline EdgeIndex
1156out_degree(Vertex v, const BOOST_CSR_GRAPH_TYPE& g)
1157{
1158 EdgeIndex v_row_start = g.m_forward.m_rowstart[v];
1159 EdgeIndex next_row_start = g.m_forward.m_rowstart[v + 1];
1160 return next_row_start - v_row_start;
1161}
1162
1163template<BOOST_BIDIR_CSR_GRAPH_TEMPLATE_PARMS>
1164inline std::pair<typename BOOST_BIDIR_CSR_GRAPH_TYPE::in_edge_iterator,
1165 typename BOOST_BIDIR_CSR_GRAPH_TYPE::in_edge_iterator>
1166in_edges(Vertex v, const BOOST_BIDIR_CSR_GRAPH_TYPE& g)
1167{
1168 typedef typename BOOST_BIDIR_CSR_GRAPH_TYPE::in_edge_iterator it;
1169 EdgeIndex v_row_start = g.m_backward.m_rowstart[v];
1170 EdgeIndex next_row_start = g.m_backward.m_rowstart[v + 1];
1171 return std::make_pair(it(g, v_row_start),
1172 it(g, next_row_start));
1173}
1174
1175template<BOOST_BIDIR_CSR_GRAPH_TEMPLATE_PARMS>
1176inline EdgeIndex
1177in_degree(Vertex v, const BOOST_BIDIR_CSR_GRAPH_TYPE& g)
1178{
1179 EdgeIndex v_row_start = g.m_backward.m_rowstart[v];
1180 EdgeIndex next_row_start = g.m_backward.m_rowstart[v + 1];
1181 return next_row_start - v_row_start;
1182}
1183
1184// From AdjacencyGraph
1185template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
1186inline std::pair<typename BOOST_CSR_GRAPH_TYPE::adjacency_iterator,
1187 typename BOOST_CSR_GRAPH_TYPE::adjacency_iterator>
1188adjacent_vertices(Vertex v, const BOOST_CSR_GRAPH_TYPE& g)
1189{
1190 EdgeIndex v_row_start = g.m_forward.m_rowstart[v];
1191 EdgeIndex next_row_start = g.m_forward.m_rowstart[v + 1];
1192 return std::make_pair(g.m_forward.m_column.begin() + v_row_start,
1193 g.m_forward.m_column.begin() + next_row_start);
1194}
1195
1196// Extra, common functions
1197template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
1198inline typename graph_traits<BOOST_CSR_GRAPH_TYPE>::vertex_descriptor
1199vertex(typename graph_traits<BOOST_CSR_GRAPH_TYPE>::vertex_descriptor i,
1200 const BOOST_CSR_GRAPH_TYPE&)
1201{
1202 return i;
1203}
1204
1205// edge() can be provided in linear time for the new interface
1206
1207template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
1208inline std::pair<typename BOOST_CSR_GRAPH_TYPE::edge_descriptor, bool>
1209edge(Vertex i, Vertex j, const BOOST_CSR_GRAPH_TYPE& g)
1210{
1211 typedef typename BOOST_CSR_GRAPH_TYPE::out_edge_iterator out_edge_iter;
1212 std::pair<out_edge_iter, out_edge_iter> range = out_edges(i, g);
1213 for (; range.first != range.second; ++range.first) {
1214 if (target(*range.first, g) == j)
1215 return std::make_pair(*range.first, true);
1216 }
1217 return std::make_pair(typename BOOST_CSR_GRAPH_TYPE::edge_descriptor(),
1218 false);
1219}
1220
1221// Find an edge given its index in the graph
1222template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
1223inline typename BOOST_CSR_GRAPH_TYPE::edge_descriptor
1224edge_from_index(EdgeIndex idx, const BOOST_CSR_GRAPH_TYPE& g)
1225{
1226 typedef typename std::vector<EdgeIndex>::const_iterator row_start_iter;
1227 BOOST_ASSERT (idx < num_edges(g));
1228 row_start_iter src_plus_1 =
1229 std::upper_bound(g.m_forward.m_rowstart.begin(),
1230 g.m_forward.m_rowstart.end(),
1231 idx);
1232 // Get last source whose rowstart is at most idx
1233 // upper_bound returns this position plus 1
1234 Vertex src = (src_plus_1 - g.m_forward.m_rowstart.begin()) - 1;
1235 return typename BOOST_CSR_GRAPH_TYPE::edge_descriptor(src, idx);
1236}
1237
1238template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
1239inline EdgeIndex
1240num_edges(const BOOST_CSR_GRAPH_TYPE& g)
1241{
1242 return g.m_forward.m_column.size();
1243}
1244
1245template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
1246std::pair<typename BOOST_CSR_GRAPH_TYPE::edge_iterator,
1247 typename BOOST_CSR_GRAPH_TYPE::edge_iterator>
1248edges(const BOOST_CSR_GRAPH_TYPE& g)
1249{
1250 typedef typename BOOST_CSR_GRAPH_TYPE::edge_iterator ei;
1251 typedef typename BOOST_CSR_GRAPH_TYPE::edge_descriptor edgedesc;
1252 if (g.m_forward.m_rowstart.size() == 1 || g.m_forward.m_column.empty()) {
1253 return std::make_pair(ei(), ei());
1254 } else {
1255 // Find the first vertex that has outgoing edges
1256 Vertex src = 0;
1257 while (g.m_forward.m_rowstart[src + 1] == 0) ++src;
1258 return std::make_pair(ei(g, edgedesc(src, 0), g.m_forward.m_rowstart[src + 1]),
1259 ei(g, edgedesc(num_vertices(g), g.m_forward.m_column.size()), 0));
1260 }
1261}
1262
1263// For Property Graph
1264
1265// Graph properties
1266template<BOOST_CSR_GRAPH_TEMPLATE_PARMS, class Tag, class Value>
1267inline void
1268set_property(BOOST_CSR_GRAPH_TYPE& g, Tag tag, const Value& value)
1269{
1270 get_property_value(g.m_property, tag) = value;
1271}
1272
1273template<BOOST_CSR_GRAPH_TEMPLATE_PARMS, class Tag>
1274inline
1275typename graph_property<BOOST_CSR_GRAPH_TYPE, Tag>::type&
1276get_property(BOOST_CSR_GRAPH_TYPE& g, Tag tag)
1277{
1278 return get_property_value(g.m_property, tag);
1279}
1280
1281template<BOOST_CSR_GRAPH_TEMPLATE_PARMS, class Tag>
1282inline
1283const
1284typename graph_property<BOOST_CSR_GRAPH_TYPE, Tag>::type&
1285get_property(const BOOST_CSR_GRAPH_TYPE& g, Tag tag)
1286{
1287 return get_property_value(g.m_property, tag);
1288}
1289
1290template <typename G, typename Tag, typename Kind>
1291struct csr_property_map_helper {};
1292// Kind == void for invalid property tags, so we can use that to SFINAE out
1293
1294template <BOOST_CSR_GRAPH_TEMPLATE_PARMS, typename Tag>
1295struct csr_property_map_helper<BOOST_CSR_GRAPH_TYPE, Tag, vertex_property_tag> {
1296 typedef vertex_all_t all_tag;
1297 typedef typename property_traits<typename property_map<BOOST_CSR_GRAPH_TYPE, vertex_all_t>::type>::key_type key_type;
1298 typedef VertexProperty plist_type;
1299 typedef typename property_map<BOOST_CSR_GRAPH_TYPE, vertex_all_t>::type all_type;
1300 typedef typename property_map<BOOST_CSR_GRAPH_TYPE, vertex_all_t>::const_type all_const_type;
1301 typedef transform_value_property_map<detail::lookup_one_property_f<plist_type, Tag>, all_type> type;
1302 typedef transform_value_property_map<detail::lookup_one_property_f<const plist_type, Tag>, all_const_type> const_type;
1303};
1304
1305template <BOOST_CSR_GRAPH_TEMPLATE_PARMS, typename Tag>
1306struct csr_property_map_helper<BOOST_CSR_GRAPH_TYPE, Tag, edge_property_tag> {
1307 typedef edge_all_t all_tag;
1308 typedef typename property_traits<typename property_map<BOOST_CSR_GRAPH_TYPE, edge_all_t>::type>::key_type key_type;
1309 typedef EdgeProperty plist_type;
1310 typedef typename property_map<BOOST_CSR_GRAPH_TYPE, edge_all_t>::type all_type;
1311 typedef typename property_map<BOOST_CSR_GRAPH_TYPE, edge_all_t>::const_type all_const_type;
1312 typedef transform_value_property_map<detail::lookup_one_property_f<plist_type, Tag>, all_type> type;
1313 typedef transform_value_property_map<detail::lookup_one_property_f<const plist_type, Tag>, all_const_type> const_type;
1314};
1315
1316template <BOOST_CSR_GRAPH_TEMPLATE_PARMS, typename Tag>
1317struct csr_property_map_helper<BOOST_CSR_GRAPH_TYPE, Tag, graph_property_tag> {
1318 typedef graph_all_t all_tag;
1319 typedef BOOST_CSR_GRAPH_TYPE* key_type;
1320 typedef GraphProperty plist_type;
1321 typedef typename property_map<BOOST_CSR_GRAPH_TYPE, graph_all_t>::type all_type;
1322 typedef typename property_map<BOOST_CSR_GRAPH_TYPE, graph_all_t>::const_type all_const_type;
1323 typedef transform_value_property_map<detail::lookup_one_property_f<plist_type, Tag>, all_type> type;
1324 typedef transform_value_property_map<detail::lookup_one_property_f<const plist_type, Tag>, all_const_type> const_type;
1325};
1326
1327// disable_if isn't truly necessary but required to avoid ambiguity with specializations below
1328template <BOOST_CSR_GRAPH_TEMPLATE_PARMS, typename Tag>
1329struct property_map<BOOST_CSR_GRAPH_TYPE, Tag, typename disable_if<detail::is_distributed_selector<Vertex> >::type>:
1330 csr_property_map_helper<
1331 BOOST_CSR_GRAPH_TYPE,
1332 Tag,
1333 typename detail::property_kind_from_graph<BOOST_CSR_GRAPH_TYPE, Tag>
1334 ::type> {};
1335
1336template <BOOST_CSR_GRAPH_TEMPLATE_PARMS, typename Tag>
1337typename property_map<BOOST_CSR_GRAPH_TYPE, Tag>::type
1338get(Tag tag, BOOST_CSR_GRAPH_TYPE& g) {
1339 return typename property_map<BOOST_CSR_GRAPH_TYPE, Tag>::type(tag, get(typename property_map<BOOST_CSR_GRAPH_TYPE, Tag>::all_tag(), g));
1340}
1341
1342template <BOOST_CSR_GRAPH_TEMPLATE_PARMS, typename Tag>
1343typename property_map<BOOST_CSR_GRAPH_TYPE, Tag>::const_type
1344get(Tag tag, const BOOST_CSR_GRAPH_TYPE& g) {
1345 return typename property_map<BOOST_CSR_GRAPH_TYPE, Tag>::const_type(tag, get(typename property_map<BOOST_CSR_GRAPH_TYPE, Tag>::all_tag(), g));
1346}
1347
1348template <BOOST_CSR_GRAPH_TEMPLATE_PARMS, typename Tag>
1349typename property_traits<typename property_map<BOOST_CSR_GRAPH_TYPE, Tag>::type>::reference
1350get(Tag tag, BOOST_CSR_GRAPH_TYPE& g, typename property_map<BOOST_CSR_GRAPH_TYPE, Tag>::key_type k) {
1351 typedef typename property_map<BOOST_CSR_GRAPH_TYPE, Tag>::all_tag all_tag;
1352 typedef typename property_map<BOOST_CSR_GRAPH_TYPE, all_tag>::type outer_pm;
1353 return lookup_one_property<typename property_traits<outer_pm>::value_type, Tag>::lookup(get(all_tag(), g, k), tag);
1354}
1355
1356template <BOOST_CSR_GRAPH_TEMPLATE_PARMS, typename Tag>
1357typename property_traits<typename property_map<BOOST_CSR_GRAPH_TYPE, Tag>::const_type>::reference
1358get(Tag tag, const BOOST_CSR_GRAPH_TYPE& g, typename property_map<BOOST_CSR_GRAPH_TYPE, Tag>::key_type k) {
1359 typedef typename property_map<BOOST_CSR_GRAPH_TYPE, Tag>::all_tag all_tag;
1360 typedef typename property_map<BOOST_CSR_GRAPH_TYPE, all_tag>::const_type outer_pm;
1361 return lookup_one_property<const typename property_traits<outer_pm>::value_type, Tag>::lookup(get(all_tag(), g, k), tag);
1362}
1363
1364template <BOOST_CSR_GRAPH_TEMPLATE_PARMS, typename Tag>
1365void
1366put(Tag tag,
1367 BOOST_CSR_GRAPH_TYPE& g,
1368 typename property_map<BOOST_CSR_GRAPH_TYPE, Tag>::key_type k,
1369 typename lookup_one_property<typename property_map<BOOST_CSR_GRAPH_TYPE, Tag>::plist_type, Tag>::type val) {
1370 typedef typename property_map<BOOST_CSR_GRAPH_TYPE, Tag>::all_tag all_tag;
1371 lookup_one_property<typename property_map<BOOST_CSR_GRAPH_TYPE, Tag>::plist_type, Tag>::lookup(get(all_tag(), g, k), tag) = val;
1372}
1373
1374template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
1375struct property_map<BOOST_CSR_GRAPH_TYPE, vertex_index_t, typename disable_if<detail::is_distributed_selector<Vertex> >::type>
1376{
1377 typedef typed_identity_property_map<Vertex> type;
1378 typedef type const_type;
1379};
1380
1381template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
1382struct property_map<BOOST_CSR_GRAPH_TYPE, edge_index_t, typename disable_if<detail::is_distributed_selector<Vertex> >::type>
1383{
1384 typedef detail::csr_edge_index_map<Vertex, EdgeIndex> type;
1385 typedef type const_type;
1386};
1387
1388template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
1389struct property_map<BOOST_CSR_GRAPH_TYPE, vertex_all_t, typename disable_if<detail::is_distributed_selector<Vertex> >::type>
1390{
1391 typedef typename BOOST_CSR_GRAPH_TYPE::inherited_vertex_properties::vertex_map_type type;
1392 typedef typename BOOST_CSR_GRAPH_TYPE::inherited_vertex_properties::const_vertex_map_type const_type;
1393};
1394
1395template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
1396struct property_map<BOOST_CSR_GRAPH_TYPE, edge_all_t, typename disable_if<detail::is_distributed_selector<Vertex> >::type>
1397{
1398 typedef typename BOOST_CSR_GRAPH_TYPE::forward_type::inherited_edge_properties::edge_map_type type;
1399 typedef typename BOOST_CSR_GRAPH_TYPE::forward_type::inherited_edge_properties::const_edge_map_type const_type;
1400};
1401
1402template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
1403struct property_map<BOOST_CSR_GRAPH_TYPE, graph_all_t, typename disable_if<detail::is_distributed_selector<Vertex> >::type>
1404{
1405 typedef boost::ref_property_map<BOOST_CSR_GRAPH_TYPE*, typename BOOST_CSR_GRAPH_TYPE::graph_property_type> type;
1406 typedef boost::ref_property_map<BOOST_CSR_GRAPH_TYPE*, const typename BOOST_CSR_GRAPH_TYPE::graph_property_type> const_type;
1407};
1408
1409template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
1410inline typed_identity_property_map<Vertex>
1411get(vertex_index_t, const BOOST_CSR_GRAPH_TYPE&)
1412{
1413 return typed_identity_property_map<Vertex>();
1414}
1415
1416template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
1417inline Vertex
1418get(vertex_index_t,
1419 const BOOST_CSR_GRAPH_TYPE&, Vertex v)
1420{
1421 return v;
1422}
1423
1424template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
1425inline typed_identity_property_map<Vertex>
1426get(vertex_index_t, BOOST_CSR_GRAPH_TYPE&)
1427{
1428 return typed_identity_property_map<Vertex>();
1429}
1430
1431template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
1432inline Vertex
1433get(vertex_index_t,
1434 BOOST_CSR_GRAPH_TYPE&, Vertex v)
1435{
1436 return v;
1437}
1438
1439template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
1440inline typename property_map<BOOST_CSR_GRAPH_TYPE, edge_index_t>::const_type
1441get(edge_index_t, const BOOST_CSR_GRAPH_TYPE&)
1442{
1443 typedef typename property_map<BOOST_CSR_GRAPH_TYPE, edge_index_t>::const_type
1444 result_type;
1445 return result_type();
1446}
1447
1448template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
1449inline EdgeIndex
1450get(edge_index_t, const BOOST_CSR_GRAPH_TYPE&,
1451 typename BOOST_CSR_GRAPH_TYPE::edge_descriptor e)
1452{
1453 return e.idx;
1454}
1455
1456template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
1457inline typename property_map<BOOST_CSR_GRAPH_TYPE, edge_index_t>::const_type
1458get(edge_index_t, BOOST_CSR_GRAPH_TYPE&)
1459{
1460 typedef typename property_map<BOOST_CSR_GRAPH_TYPE, edge_index_t>::const_type
1461 result_type;
1462 return result_type();
1463}
1464
1465template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
1466inline EdgeIndex
1467get(edge_index_t, BOOST_CSR_GRAPH_TYPE&,
1468 typename BOOST_CSR_GRAPH_TYPE::edge_descriptor e)
1469{
1470 return e.idx;
1471}
1472
1473template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
1474inline typename property_map<BOOST_CSR_GRAPH_TYPE, vertex_all_t>::type
1475get(vertex_all_t, BOOST_CSR_GRAPH_TYPE& g)
1476{
1477 return g.get_vertex_bundle(get(vertex_index, g));
1478}
1479
1480template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
1481inline typename property_map<BOOST_CSR_GRAPH_TYPE, vertex_all_t>::const_type
1482get(vertex_all_t, const BOOST_CSR_GRAPH_TYPE& g)
1483{
1484 return g.get_vertex_bundle(get(vertex_index, g));
1485}
1486
1487template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
1488inline VertexProperty&
1489get(vertex_all_t,
1490 BOOST_CSR_GRAPH_TYPE& g, Vertex v)
1491{
1492 return get(vertex_all, g)[v];
1493}
1494
1495template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
1496inline const VertexProperty&
1497get(vertex_all_t,
1498 const BOOST_CSR_GRAPH_TYPE& g, Vertex v)
1499{
1500 return get(vertex_all, g)[v];
1501}
1502
1503template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
1504inline void
1505put(vertex_all_t,
1506 BOOST_CSR_GRAPH_TYPE& g,
1507 Vertex v,
1508 const VertexProperty& val)
1509{
1510 put(get(vertex_all, g), v, val);
1511}
1512
1513template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
1514inline typename property_map<BOOST_CSR_GRAPH_TYPE, edge_all_t>::type
1515get(edge_all_t, BOOST_CSR_GRAPH_TYPE& g)
1516{
1517 return g.m_forward.get_edge_bundle(get(edge_index, g));
1518}
1519
1520template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
1521inline typename property_map<BOOST_CSR_GRAPH_TYPE, edge_all_t>::const_type
1522get(edge_all_t, const BOOST_CSR_GRAPH_TYPE& g)
1523{
1524 return g.m_forward.get_edge_bundle(get(edge_index, g));
1525}
1526
1527template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
1528inline EdgeProperty&
1529get(edge_all_t,
1530 BOOST_CSR_GRAPH_TYPE& g,
1531 const typename BOOST_CSR_GRAPH_TYPE::edge_descriptor& e)
1532{
1533 return get(edge_all, g)[e];
1534}
1535
1536template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
1537inline const EdgeProperty&
1538get(edge_all_t,
1539 const BOOST_CSR_GRAPH_TYPE& g,
1540 const typename BOOST_CSR_GRAPH_TYPE::edge_descriptor& e)
1541{
1542 return get(edge_all, g)[e];
1543}
1544
1545template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
1546inline void
1547put(edge_all_t,
1548 BOOST_CSR_GRAPH_TYPE& g,
1549 const typename BOOST_CSR_GRAPH_TYPE::edge_descriptor& e,
1550 const EdgeProperty& val)
1551{
1552 put(get(edge_all, g), e, val);
1553}
1554
1555template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
1556inline typename property_map<BOOST_CSR_GRAPH_TYPE, graph_all_t>::type
1557get(graph_all_t, BOOST_CSR_GRAPH_TYPE& g)
1558{
1559 return typename property_map<BOOST_CSR_GRAPH_TYPE, graph_all_t>::type(g.m_property);
1560}
1561
1562template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
1563inline typename property_map<BOOST_CSR_GRAPH_TYPE, graph_all_t>::const_type
1564get(graph_all_t, const BOOST_CSR_GRAPH_TYPE& g)
1565{
1566 return typename property_map<BOOST_CSR_GRAPH_TYPE, graph_all_t>::const_type(g.m_property);
1567}
1568
1569template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
1570inline GraphProperty&
1571get(graph_all_t,
1572 BOOST_CSR_GRAPH_TYPE& g,
1573 BOOST_CSR_GRAPH_TYPE*)
1574{
1575 return g.m_property;
1576}
1577
1578template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
1579inline const GraphProperty&
1580get(graph_all_t,
1581 const BOOST_CSR_GRAPH_TYPE& g,
1582 BOOST_CSR_GRAPH_TYPE*)
1583{
1584 return g.m_property;
1585}
1586
1587template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
1588inline void
1589put(graph_all_t,
1590 BOOST_CSR_GRAPH_TYPE& g,
1591 BOOST_CSR_GRAPH_TYPE*,
1592 const GraphProperty& val)
1593{
1594 g.m_property = val;
1595}
1596
1597#undef BOOST_CSR_GRAPH_TYPE
1598#undef BOOST_CSR_GRAPH_TEMPLATE_PARMS
1599#undef BOOST_DIR_CSR_GRAPH_TYPE
1600#undef BOOST_DIR_CSR_GRAPH_TEMPLATE_PARMS
1601#undef BOOST_BIDIR_CSR_GRAPH_TYPE
1602#undef BOOST_BIDIR_CSR_GRAPH_TEMPLATE_PARMS
1603
1604} // end namespace boost
1605
1606#endif // BOOST_GRAPH_COMPRESSED_SPARSE_ROW_GRAPH_HPP
1607

source code of boost/boost/graph/compressed_sparse_row_graph.hpp