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; |
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 | */ |
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 | |
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 | |
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 | |
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 |
988 | template<BOOST_CSR_GRAPH_TEMPLATE_PARMS> |
989 | inline Vertex |
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 |
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 |
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 |
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 |
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 |
1111 | template<BOOST_CSR_GRAPH_TEMPLATE_PARMS> |
1112 | inline Vertex |
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> > |
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 |
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 |
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> |
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 |
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> |
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 |
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> |
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 |
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> |
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 |
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 |
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> |
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 |
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& |
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& |
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 |
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 |
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 |
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 |
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 |
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> |
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 |
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> |
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 |
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 |
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 |
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 |
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 |
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 |
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 |
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& |
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& |
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 |
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 |
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 |
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& |
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& |
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 |
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 |
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 |
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& |
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& |
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 |
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 | |