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
50 namespace 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.
54 struct 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.
59 enum 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.
64 enum 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.
70 enum 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.
76 enum 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.
84 enum 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.
91 enum 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).
102 enum 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.
111 enum 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
135 namespace 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;
dereferenceboost::detail::default_construct_iterator140 const T& dereference() const {return saved_value;}
equalboost::detail::default_construct_iterator141 bool equal(default_construct_iterator /*i*/) const {return true;}
incrementboost::detail::default_construct_iterator142 void increment() {}
decrementboost::detail::default_construct_iterator143 void decrement() {}
advanceboost::detail::default_construct_iterator144 void advance(typename base_type::difference_type) {}
distance_toboost::detail::default_construct_iterator145 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;
compare_firstboost::detail::compare_first151 compare_first(Less less = Less()): less(less) {}
152 template <typename Tuple>
operator ()boost::detail::compare_first153 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>
operator ()boost::detail::my_tuple_get_class162 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 */
173 template<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>
179 class compressed_sparse_row_graph; // Not defined
180
181 template<typename VertexProperty,
182 typename EdgeProperty,
183 typename GraphProperty,
184 typename Vertex,
185 typename EdgeIndex>
186 class 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
null_vertex()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.
compressed_sparse_row_graph()258 compressed_sparse_row_graph(): m_property() {}
259
260 // With numverts vertices
compressed_sparse_row_graph(vertices_size_type numverts)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>
compressed_sparse_row_graph(edges_are_unsorted_multi_pass_t,MultiPassInputIterator edge_begin,MultiPassInputIterator edge_end,vertices_size_type numverts,const GraphProperty & prop=GraphProperty ())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>
compressed_sparse_row_graph(edges_are_unsorted_multi_pass_t,MultiPassInputIterator edge_begin,MultiPassInputIterator edge_end,EdgePropertyIterator ep_iter,vertices_size_type numverts,const GraphProperty & prop=GraphProperty ())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>
compressed_sparse_row_graph(edges_are_unsorted_multi_pass_global_t,MultiPassInputIterator edge_begin,MultiPassInputIterator edge_end,vertices_size_type numlocalverts,const GlobalToLocal & global_to_local,const SourcePred & source_pred,const GraphProperty & prop=GraphProperty ())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>
compressed_sparse_row_graph(edges_are_unsorted_multi_pass_global_t,MultiPassInputIterator edge_begin,MultiPassInputIterator edge_end,EdgePropertyIterator ep_iter,vertices_size_type numlocalverts,const GlobalToLocal & global_to_local,const SourcePred & source_pred,const GraphProperty & prop=GraphProperty ())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>
compressed_sparse_row_graph(edges_are_sorted_t,InputIterator edge_begin,InputIterator edge_end,vertices_size_type numverts,edges_size_type numedges=0,const GraphProperty & prop=GraphProperty ())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>
compressed_sparse_row_graph(edges_are_sorted_t,InputIterator edge_begin,InputIterator edge_end,EdgePropertyIterator ep_iter,vertices_size_type numverts,edges_size_type numedges=0,const GraphProperty & prop=GraphProperty ())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>
compressed_sparse_row_graph(edges_are_sorted_global_t,InputIterator edge_begin,InputIterator edge_end,const GlobalToLocal & global_to_local,const SourcePred & source_pred,vertices_size_type numverts,const GraphProperty & prop=GraphProperty ())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>
compressed_sparse_row_graph(edges_are_sorted_global_t,InputIterator edge_begin,InputIterator edge_end,EdgePropertyIterator ep_iter,const GlobalToLocal & global_to_local,const SourcePred & source_pred,vertices_size_type numverts,const GraphProperty & prop=GraphProperty ())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.
compressed_sparse_row_graph(construct_inplace_from_sources_and_targets_t,std::vector<vertex_descriptor> & sources,std::vector<vertex_descriptor> & targets,vertices_size_type numverts,const GraphProperty & prop=GraphProperty ())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>
compressed_sparse_row_graph(construct_inplace_from_sources_and_targets_global_t,std::vector<vertex_descriptor> & sources,std::vector<vertex_descriptor> & targets,vertices_size_type numlocalverts,GlobalToLocal global_to_local,const GraphProperty & prop=GraphProperty ())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.
compressed_sparse_row_graph(construct_inplace_from_sources_and_targets_t,std::vector<vertex_descriptor> & sources,std::vector<vertex_descriptor> & targets,std::vector<typename forward_type::inherited_edge_properties::edge_bundled> & edge_props,vertices_size_type numverts,const GraphProperty & prop=GraphProperty ())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>
compressed_sparse_row_graph(construct_inplace_from_sources_and_targets_global_t,std::vector<vertex_descriptor> & sources,std::vector<vertex_descriptor> & targets,std::vector<typename forward_type::inherited_edge_properties::edge_bundled> & edge_props,vertices_size_type numlocalverts,GlobalToLocal global_to_local,const GraphProperty & prop=GraphProperty ())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>
compressed_sparse_row_graph(edges_are_unsorted_t,InputIterator edge_begin,InputIterator edge_end,vertices_size_type numverts,const GraphProperty & prop=GraphProperty ())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>
compressed_sparse_row_graph(edges_are_unsorted_t,InputIterator edge_begin,InputIterator edge_end,EdgePropertyIterator ep_iter,vertices_size_type numverts,const GraphProperty & prop=GraphProperty ())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>
compressed_sparse_row_graph(edges_are_unsorted_global_t,InputIterator edge_begin,InputIterator edge_end,vertices_size_type numlocalverts,GlobalToLocal global_to_local,const SourcePred & source_pred,const GraphProperty & prop=GraphProperty ())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>
compressed_sparse_row_graph(edges_are_unsorted_global_t,InputIterator edge_begin,InputIterator edge_end,EdgePropertyIterator ep_iter,vertices_size_type numlocalverts,GlobalToLocal global_to_local,const SourcePred & source_pred,const GraphProperty & prop=GraphProperty ())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>
compressed_sparse_row_graph(const Graph & g,const VertexIndexMap & vi,vertices_size_type numverts,edges_size_type numedges)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>
compressed_sparse_row_graph(const Graph & g,const VertexIndexMap & vi)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>
compressed_sparse_row_graph(const Graph & g)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
assign(const Graph & g,const VertexIndexMap & vi,vertices_size_type numverts,edges_size_type numedges)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>
assign(const Graph & g,const VertexIndexMap & vi)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>
assign(const Graph & g)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
add_edges_sorted_internal(BidirectionalIteratorOrig first_sorted,BidirectionalIteratorOrig last_sorted,EPIterOrig ep_iter_sorted,const GlobalToLocal & global_to_local)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
add_edges_sorted_internal(BidirectionalIteratorOrig first_sorted,BidirectionalIteratorOrig last_sorted,EPIterOrig ep_iter_sorted)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
add_edges_sorted_internal(BidirectionalIteratorOrig first_sorted,BidirectionalIteratorOrig last_sorted)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
add_edges_sorted_internal_global(BidirectionalIteratorOrig first_sorted,BidirectionalIteratorOrig last_sorted,const GlobalToLocal & global_to_local)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
add_edges_sorted_internal_global(BidirectionalIteratorOrig first_sorted,BidirectionalIteratorOrig last_sorted,EPIterOrig ep_iter_sorted,const GlobalToLocal & global_to_local)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
add_edges_internal(InputIterator first,InputIterator last,const GlobalToLocal & global_to_local)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
add_edges_internal(InputIterator first,InputIterator last)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
add_edges_internal(InputIterator first,InputIterator last,EPIterator ep_iter,EPIterator ep_iter_end,const GlobalToLocal & global_to_local)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
add_edges_internal(InputIterator first,InputIterator last,EPIterator ep_iter,EPIterator ep_iter_end)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
operator [](const edge_descriptor & v)710 edge_push_back_type& operator[](const edge_descriptor& v)
711 { return m_forward.m_edge_properties[get(edge_index, *this, v)]; }
712
operator [](const edge_descriptor & v) const713 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
operator [](graph_bundle_t)717 graph_bundled& operator[](graph_bundle_t)
718 { return get_property(*this); }
719
operator [](graph_bundle_t) const720 const graph_bundled& operator[](graph_bundle_t) const
721 { return get_property(*this); }
722
723 // private: non-portable, requires friend templates
vertex_properties()724 inherited_vertex_properties& vertex_properties() {return *this;}
vertex_properties() const725 const inherited_vertex_properties& vertex_properties() const {return *this;}
edge_properties()726 typename forward_type::inherited_edge_properties& edge_properties() { return m_forward; }
edge_properties() const727 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
733 template<typename VertexProperty,
734 typename EdgeProperty,
735 typename GraphProperty,
736 typename Vertex,
737 typename EdgeIndex>
738 class 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
null_vertex()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.
compressed_sparse_row_graph()802 compressed_sparse_row_graph(): m_property() {}
803
804 // With numverts vertices
compressed_sparse_row_graph(vertices_size_type numverts)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
set_up_backward_property_links()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>
compressed_sparse_row_graph(edges_are_unsorted_multi_pass_t,MultiPassInputIterator edge_begin,MultiPassInputIterator edge_end,vertices_size_type numverts,const GraphProperty & prop=GraphProperty ())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>
compressed_sparse_row_graph(edges_are_unsorted_multi_pass_t,MultiPassInputIterator edge_begin,MultiPassInputIterator edge_end,EdgePropertyIterator ep_iter,vertices_size_type numverts,const GraphProperty & prop=GraphProperty ())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>
compressed_sparse_row_graph(edges_are_unsorted_multi_pass_global_t,MultiPassInputIterator edge_begin,MultiPassInputIterator edge_end,vertices_size_type numlocalverts,const GlobalToLocal & global_to_local,const SourcePred & source_pred,const GraphProperty & prop=GraphProperty ())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>
compressed_sparse_row_graph(edges_are_unsorted_multi_pass_global_t,MultiPassInputIterator edge_begin,MultiPassInputIterator edge_end,EdgePropertyIterator ep_iter,vertices_size_type numlocalverts,const GlobalToLocal & global_to_local,const SourcePred & source_pred,const GraphProperty & prop=GraphProperty ())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>
compressed_sparse_row_graph(const Graph & g,const VertexIndexMap & vi,vertices_size_type numverts,edges_size_type numedges)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>
compressed_sparse_row_graph(const Graph & g,const VertexIndexMap & vi)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>
compressed_sparse_row_graph(const Graph & g)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
assign(const Graph & g,const VertexIndexMap & vi,vertices_size_type numverts,edges_size_type numedges)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>
assign(const Graph & g,const VertexIndexMap & vi)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>
assign(const Graph & g)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
operator [](const edge_descriptor & v)970 edge_push_back_type& operator[](const edge_descriptor& v)
971 { return m_forward.m_edge_properties[get(edge_index, *this, v)]; }
972
operator [](const edge_descriptor & v) const973 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
vertex_properties()977 inherited_vertex_properties& vertex_properties() {return *this;}
vertex_properties() const978 const inherited_vertex_properties& vertex_properties() const {return *this;}
edge_properties()979 typename forward_type::inherited_edge_properties& edge_properties() { return m_forward; }
edge_properties() const980 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
988 template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
989 inline Vertex
add_vertex(BOOST_CSR_GRAPH_TYPE & g)990 add_vertex(BOOST_CSR_GRAPH_TYPE& g) {
991 add_vertex(g, typename BOOST_CSR_GRAPH_TYPE::vertex_bundled());
992 }
993
994 template<BOOST_DIR_CSR_GRAPH_TEMPLATE_PARMS>
995 inline Vertex
add_vertex(BOOST_DIR_CSR_GRAPH_TYPE & g,typename BOOST_DIR_CSR_GRAPH_TYPE::vertex_bundled const & p)996 add_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
1004 template<BOOST_BIDIR_CSR_GRAPH_TEMPLATE_PARMS>
1005 inline Vertex
add_vertex(BOOST_BIDIR_CSR_GRAPH_TYPE & g,typename BOOST_BIDIR_CSR_GRAPH_TYPE::vertex_bundled const & p)1006 add_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
1015 template<BOOST_DIR_CSR_GRAPH_TEMPLATE_PARMS>
1016 inline Vertex
add_vertices(typename BOOST_DIR_CSR_GRAPH_TYPE::vertices_size_type count,BOOST_DIR_CSR_GRAPH_TYPE & g)1017 add_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
add_edges_sorted(BidirectionalIteratorOrig first_sorted,BidirectionalIteratorOrig last_sorted,EPIterOrig ep_iter_sorted,BOOST_DIR_CSR_GRAPH_TYPE & g)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
add_edges_sorted(BidirectionalIteratorOrig first_sorted,BidirectionalIteratorOrig last_sorted,BOOST_DIR_CSR_GRAPH_TYPE & g)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
add_edges_sorted_global(BidirectionalIteratorOrig first_sorted,BidirectionalIteratorOrig last_sorted,EPIterOrig ep_iter_sorted,const GlobalToLocal & global_to_local,BOOST_DIR_CSR_GRAPH_TYPE & g)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
add_edges_sorted_global(BidirectionalIteratorOrig first_sorted,BidirectionalIteratorOrig last_sorted,const GlobalToLocal & global_to_local,BOOST_DIR_CSR_GRAPH_TYPE & g)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
add_edges_global(InputIterator first,InputIterator last,const GlobalToLocal & global_to_local,BOOST_DIR_CSR_GRAPH_TYPE & g)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
add_edges(InputIterator first,InputIterator last,BOOST_DIR_CSR_GRAPH_TYPE & g)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
add_edges(InputIterator first,InputIterator last,EPIterator ep_iter,EPIterator ep_iter_end,BOOST_DIR_CSR_GRAPH_TYPE & g)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
add_edges_global(InputIterator first,InputIterator last,EPIterator ep_iter,EPIterator ep_iter_end,const GlobalToLocal & global_to_local,BOOST_DIR_CSR_GRAPH_TYPE & g)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
1111 template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
1112 inline Vertex
num_vertices(const BOOST_CSR_GRAPH_TYPE & g)1113 num_vertices(const BOOST_CSR_GRAPH_TYPE& g) {
1114 return g.m_forward.m_rowstart.size() - 1;
1115 }
1116
1117 template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
1118 std::pair<counting_iterator<Vertex>, counting_iterator<Vertex> >
vertices(const BOOST_CSR_GRAPH_TYPE & g)1119 inline 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
1125 template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
1126 inline Vertex
source(typename BOOST_CSR_GRAPH_TYPE::edge_descriptor e,const BOOST_CSR_GRAPH_TYPE &)1127 source(typename BOOST_CSR_GRAPH_TYPE::edge_descriptor e,
1128 const BOOST_CSR_GRAPH_TYPE&)
1129 {
1130 return e.src;
1131 }
1132
1133 template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
1134 inline Vertex
target(typename BOOST_CSR_GRAPH_TYPE::edge_descriptor e,const BOOST_CSR_GRAPH_TYPE & g)1135 target(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
1141 template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
1142 inline std::pair<typename BOOST_CSR_GRAPH_TYPE::out_edge_iterator,
1143 typename BOOST_CSR_GRAPH_TYPE::out_edge_iterator>
out_edges(Vertex v,const BOOST_CSR_GRAPH_TYPE & g)1144 out_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
1154 template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
1155 inline EdgeIndex
out_degree(Vertex v,const BOOST_CSR_GRAPH_TYPE & g)1156 out_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
1163 template<BOOST_BIDIR_CSR_GRAPH_TEMPLATE_PARMS>
1164 inline std::pair<typename BOOST_BIDIR_CSR_GRAPH_TYPE::in_edge_iterator,
1165 typename BOOST_BIDIR_CSR_GRAPH_TYPE::in_edge_iterator>
in_edges(Vertex v,const BOOST_BIDIR_CSR_GRAPH_TYPE & g)1166 in_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
1175 template<BOOST_BIDIR_CSR_GRAPH_TEMPLATE_PARMS>
1176 inline EdgeIndex
in_degree(Vertex v,const BOOST_BIDIR_CSR_GRAPH_TYPE & g)1177 in_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
1185 template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
1186 inline std::pair<typename BOOST_CSR_GRAPH_TYPE::adjacency_iterator,
1187 typename BOOST_CSR_GRAPH_TYPE::adjacency_iterator>
adjacent_vertices(Vertex v,const BOOST_CSR_GRAPH_TYPE & g)1188 adjacent_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
1197 template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
1198 inline typename graph_traits<BOOST_CSR_GRAPH_TYPE>::vertex_descriptor
vertex(typename graph_traits<BOOST_CSR_GRAPH_TYPE>::vertex_descriptor i,const BOOST_CSR_GRAPH_TYPE &)1199 vertex(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
1207 template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
1208 inline std::pair<typename BOOST_CSR_GRAPH_TYPE::edge_descriptor, bool>
edge(Vertex i,Vertex j,const BOOST_CSR_GRAPH_TYPE & g)1209 edge(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
1222 template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
1223 inline typename BOOST_CSR_GRAPH_TYPE::edge_descriptor
edge_from_index(EdgeIndex idx,const BOOST_CSR_GRAPH_TYPE & g)1224 edge_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
1238 template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
1239 inline EdgeIndex
num_edges(const BOOST_CSR_GRAPH_TYPE & g)1240 num_edges(const BOOST_CSR_GRAPH_TYPE& g)
1241 {
1242 return g.m_forward.m_column.size();
1243 }
1244
1245 template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
1246 std::pair<typename BOOST_CSR_GRAPH_TYPE::edge_iterator,
1247 typename BOOST_CSR_GRAPH_TYPE::edge_iterator>
edges(const BOOST_CSR_GRAPH_TYPE & g)1248 edges(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
1266 template<BOOST_CSR_GRAPH_TEMPLATE_PARMS, class Tag, class Value>
1267 inline void
set_property(BOOST_CSR_GRAPH_TYPE & g,Tag tag,const Value & value)1268 set_property(BOOST_CSR_GRAPH_TYPE& g, Tag tag, const Value& value)
1269 {
1270 get_property_value(g.m_property, tag) = value;
1271 }
1272
1273 template<BOOST_CSR_GRAPH_TEMPLATE_PARMS, class Tag>
1274 inline
1275 typename graph_property<BOOST_CSR_GRAPH_TYPE, Tag>::type&
get_property(BOOST_CSR_GRAPH_TYPE & g,Tag tag)1276 get_property(BOOST_CSR_GRAPH_TYPE& g, Tag tag)
1277 {
1278 return get_property_value(g.m_property, tag);
1279 }
1280
1281 template<BOOST_CSR_GRAPH_TEMPLATE_PARMS, class Tag>
1282 inline
1283 const
1284 typename graph_property<BOOST_CSR_GRAPH_TYPE, Tag>::type&
get_property(const BOOST_CSR_GRAPH_TYPE & g,Tag tag)1285 get_property(const BOOST_CSR_GRAPH_TYPE& g, Tag tag)
1286 {
1287 return get_property_value(g.m_property, tag);
1288 }
1289
1290 template <typename G, typename Tag, typename Kind>
1291 struct csr_property_map_helper {};
1292 // Kind == void for invalid property tags, so we can use that to SFINAE out
1293
1294 template <BOOST_CSR_GRAPH_TEMPLATE_PARMS, typename Tag>
1295 struct 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
1305 template <BOOST_CSR_GRAPH_TEMPLATE_PARMS, typename Tag>
1306 struct 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
1316 template <BOOST_CSR_GRAPH_TEMPLATE_PARMS, typename Tag>
1317 struct 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
1328 template <BOOST_CSR_GRAPH_TEMPLATE_PARMS, typename Tag>
1329 struct 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
1336 template <BOOST_CSR_GRAPH_TEMPLATE_PARMS, typename Tag>
1337 typename property_map<BOOST_CSR_GRAPH_TYPE, Tag>::type
get(Tag tag,BOOST_CSR_GRAPH_TYPE & g)1338 get(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
1342 template <BOOST_CSR_GRAPH_TEMPLATE_PARMS, typename Tag>
1343 typename property_map<BOOST_CSR_GRAPH_TYPE, Tag>::const_type
get(Tag tag,const BOOST_CSR_GRAPH_TYPE & g)1344 get(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
1348 template <BOOST_CSR_GRAPH_TEMPLATE_PARMS, typename Tag>
1349 typename property_traits<typename property_map<BOOST_CSR_GRAPH_TYPE, Tag>::type>::reference
get(Tag tag,BOOST_CSR_GRAPH_TYPE & g,typename property_map<BOOST_CSR_GRAPH_TYPE,Tag>::key_type k)1350 get(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
1356 template <BOOST_CSR_GRAPH_TEMPLATE_PARMS, typename Tag>
1357 typename property_traits<typename property_map<BOOST_CSR_GRAPH_TYPE, Tag>::const_type>::reference
get(Tag tag,const BOOST_CSR_GRAPH_TYPE & g,typename property_map<BOOST_CSR_GRAPH_TYPE,Tag>::key_type k)1358 get(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
1364 template <BOOST_CSR_GRAPH_TEMPLATE_PARMS, typename Tag>
1365 void
put(Tag tag,BOOST_CSR_GRAPH_TYPE & g,typename property_map<BOOST_CSR_GRAPH_TYPE,Tag>::key_type k,typename lookup_one_property<typename property_map<BOOST_CSR_GRAPH_TYPE,Tag>::plist_type,Tag>::type val)1366 put(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
1374 template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
1375 struct 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
1381 template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
1382 struct 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
1388 template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
1389 struct 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
1395 template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
1396 struct 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
1402 template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
1403 struct 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
1409 template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
1410 inline typed_identity_property_map<Vertex>
get(vertex_index_t,const BOOST_CSR_GRAPH_TYPE &)1411 get(vertex_index_t, const BOOST_CSR_GRAPH_TYPE&)
1412 {
1413 return typed_identity_property_map<Vertex>();
1414 }
1415
1416 template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
1417 inline Vertex
get(vertex_index_t,const BOOST_CSR_GRAPH_TYPE &,Vertex v)1418 get(vertex_index_t,
1419 const BOOST_CSR_GRAPH_TYPE&, Vertex v)
1420 {
1421 return v;
1422 }
1423
1424 template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
1425 inline typed_identity_property_map<Vertex>
get(vertex_index_t,BOOST_CSR_GRAPH_TYPE &)1426 get(vertex_index_t, BOOST_CSR_GRAPH_TYPE&)
1427 {
1428 return typed_identity_property_map<Vertex>();
1429 }
1430
1431 template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
1432 inline Vertex
get(vertex_index_t,BOOST_CSR_GRAPH_TYPE &,Vertex v)1433 get(vertex_index_t,
1434 BOOST_CSR_GRAPH_TYPE&, Vertex v)
1435 {
1436 return v;
1437 }
1438
1439 template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
1440 inline typename property_map<BOOST_CSR_GRAPH_TYPE, edge_index_t>::const_type
get(edge_index_t,const BOOST_CSR_GRAPH_TYPE &)1441 get(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
1448 template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
1449 inline EdgeIndex
get(edge_index_t,const BOOST_CSR_GRAPH_TYPE &,typename BOOST_CSR_GRAPH_TYPE::edge_descriptor e)1450 get(edge_index_t, const BOOST_CSR_GRAPH_TYPE&,
1451 typename BOOST_CSR_GRAPH_TYPE::edge_descriptor e)
1452 {
1453 return e.idx;
1454 }
1455
1456 template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
1457 inline typename property_map<BOOST_CSR_GRAPH_TYPE, edge_index_t>::const_type
get(edge_index_t,BOOST_CSR_GRAPH_TYPE &)1458 get(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
1465 template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
1466 inline EdgeIndex
get(edge_index_t,BOOST_CSR_GRAPH_TYPE &,typename BOOST_CSR_GRAPH_TYPE::edge_descriptor e)1467 get(edge_index_t, BOOST_CSR_GRAPH_TYPE&,
1468 typename BOOST_CSR_GRAPH_TYPE::edge_descriptor e)
1469 {
1470 return e.idx;
1471 }
1472
1473 template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
1474 inline typename property_map<BOOST_CSR_GRAPH_TYPE, vertex_all_t>::type
get(vertex_all_t,BOOST_CSR_GRAPH_TYPE & g)1475 get(vertex_all_t, BOOST_CSR_GRAPH_TYPE& g)
1476 {
1477 return g.get_vertex_bundle(get(vertex_index, g));
1478 }
1479
1480 template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
1481 inline typename property_map<BOOST_CSR_GRAPH_TYPE, vertex_all_t>::const_type
get(vertex_all_t,const BOOST_CSR_GRAPH_TYPE & g)1482 get(vertex_all_t, const BOOST_CSR_GRAPH_TYPE& g)
1483 {
1484 return g.get_vertex_bundle(get(vertex_index, g));
1485 }
1486
1487 template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
1488 inline VertexProperty&
get(vertex_all_t,BOOST_CSR_GRAPH_TYPE & g,Vertex v)1489 get(vertex_all_t,
1490 BOOST_CSR_GRAPH_TYPE& g, Vertex v)
1491 {
1492 return get(vertex_all, g)[v];
1493 }
1494
1495 template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
1496 inline const VertexProperty&
get(vertex_all_t,const BOOST_CSR_GRAPH_TYPE & g,Vertex v)1497 get(vertex_all_t,
1498 const BOOST_CSR_GRAPH_TYPE& g, Vertex v)
1499 {
1500 return get(vertex_all, g)[v];
1501 }
1502
1503 template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
1504 inline void
put(vertex_all_t,BOOST_CSR_GRAPH_TYPE & g,Vertex v,const VertexProperty & val)1505 put(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
1513 template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
1514 inline typename property_map<BOOST_CSR_GRAPH_TYPE, edge_all_t>::type
get(edge_all_t,BOOST_CSR_GRAPH_TYPE & g)1515 get(edge_all_t, BOOST_CSR_GRAPH_TYPE& g)
1516 {
1517 return g.m_forward.get_edge_bundle(get(edge_index, g));
1518 }
1519
1520 template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
1521 inline typename property_map<BOOST_CSR_GRAPH_TYPE, edge_all_t>::const_type
get(edge_all_t,const BOOST_CSR_GRAPH_TYPE & g)1522 get(edge_all_t, const BOOST_CSR_GRAPH_TYPE& g)
1523 {
1524 return g.m_forward.get_edge_bundle(get(edge_index, g));
1525 }
1526
1527 template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
1528 inline EdgeProperty&
get(edge_all_t,BOOST_CSR_GRAPH_TYPE & g,const typename BOOST_CSR_GRAPH_TYPE::edge_descriptor & e)1529 get(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
1536 template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
1537 inline const EdgeProperty&
get(edge_all_t,const BOOST_CSR_GRAPH_TYPE & g,const typename BOOST_CSR_GRAPH_TYPE::edge_descriptor & e)1538 get(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
1545 template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
1546 inline void
put(edge_all_t,BOOST_CSR_GRAPH_TYPE & g,const typename BOOST_CSR_GRAPH_TYPE::edge_descriptor & e,const EdgeProperty & val)1547 put(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
1555 template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
1556 inline typename property_map<BOOST_CSR_GRAPH_TYPE, graph_all_t>::type
get(graph_all_t,BOOST_CSR_GRAPH_TYPE & g)1557 get(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
1562 template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
1563 inline typename property_map<BOOST_CSR_GRAPH_TYPE, graph_all_t>::const_type
get(graph_all_t,const BOOST_CSR_GRAPH_TYPE & g)1564 get(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
1569 template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
1570 inline GraphProperty&
get(graph_all_t,BOOST_CSR_GRAPH_TYPE & g,BOOST_CSR_GRAPH_TYPE *)1571 get(graph_all_t,
1572 BOOST_CSR_GRAPH_TYPE& g,
1573 BOOST_CSR_GRAPH_TYPE*)
1574 {
1575 return g.m_property;
1576 }
1577
1578 template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
1579 inline const GraphProperty&
get(graph_all_t,const BOOST_CSR_GRAPH_TYPE & g,BOOST_CSR_GRAPH_TYPE *)1580 get(graph_all_t,
1581 const BOOST_CSR_GRAPH_TYPE& g,
1582 BOOST_CSR_GRAPH_TYPE*)
1583 {
1584 return g.m_property;
1585 }
1586
1587 template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
1588 inline void
put(graph_all_t,BOOST_CSR_GRAPH_TYPE & g,BOOST_CSR_GRAPH_TYPE *,const GraphProperty & val)1589 put(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