]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | // Copyright (C) 2006 The Trustees of Indiana University. |
2 | ||
3 | // Use, modification and distribution is subject to the Boost Software | |
4 | // License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at | |
5 | // http://www.boost.org/LICENSE_1_0.txt) | |
6 | ||
7 | // Authors: Douglas Gregor | |
8 | // Jeremiah Willcock | |
9 | // Andrew Lumsdaine | |
10 | ||
11 | // Distributed compressed sparse row graph type | |
12 | ||
13 | #ifndef BOOST_GRAPH_DISTRIBUTED_CSR_HPP | |
14 | #define BOOST_GRAPH_DISTRIBUTED_CSR_HPP | |
15 | ||
16 | #ifndef BOOST_GRAPH_USE_MPI | |
17 | #error "Parallel BGL files should not be included unless <boost/graph/use_mpi.hpp> has been included" | |
18 | #endif | |
19 | ||
20 | #include <boost/assert.hpp> | |
21 | #include <boost/graph/compressed_sparse_row_graph.hpp> | |
22 | #include <boost/graph/distributed/selector.hpp> | |
23 | #include <boost/mpl/if.hpp> | |
24 | #include <boost/type_traits/is_same.hpp> | |
25 | #include <boost/graph/distributed/concepts.hpp> | |
26 | #include <boost/graph/parallel/properties.hpp> | |
27 | #include <boost/graph/parallel/distribution.hpp> | |
28 | #include <boost/property_map/parallel/local_property_map.hpp> | |
29 | #include <boost/property_map/parallel/distributed_property_map.hpp> | |
30 | ||
31 | namespace boost { | |
32 | ||
33 | // Distributed and sequential inplace ctors have the same signature so | |
34 | // we need a separate tag for distributed inplace ctors | |
35 | enum distributed_construct_inplace_from_sources_and_targets_t | |
36 | {distributed_construct_inplace_from_sources_and_targets}; | |
37 | ||
38 | // The number of bits we reserve for the processor ID. | |
39 | // DPG TBD: This is a hack. It will eventually be a run-time quantity. | |
40 | static const int processor_bits = 8; | |
41 | ||
42 | // Tag class for a distributed CSR graph | |
43 | struct distributed_csr_tag | |
44 | : public virtual distributed_graph_tag, | |
45 | public virtual distributed_vertex_list_graph_tag, | |
46 | public virtual distributed_edge_list_graph_tag, | |
47 | public virtual incidence_graph_tag, | |
48 | public virtual adjacency_graph_tag {}; | |
49 | ||
50 | template<typename VertexProperty, typename EdgeProperty, | |
51 | typename GraphProperty, typename ProcessGroup, typename InVertex, | |
52 | typename InDistribution, typename InEdgeIndex> | |
53 | class compressed_sparse_row_graph< | |
54 | directedS, VertexProperty, EdgeProperty, GraphProperty, | |
55 | distributedS<ProcessGroup, InVertex, InDistribution>, | |
56 | InEdgeIndex> | |
57 | { | |
58 | typedef compressed_sparse_row_graph self_type; | |
59 | ||
60 | private: | |
61 | /** | |
62 | * Determine the type used to represent vertices in the graph. If | |
63 | * the user has overridden the default, use the user's | |
64 | * parameter. Otherwise, fall back to std::size_t. | |
65 | */ | |
66 | typedef typename mpl::if_<is_same<InVertex, defaultS>, | |
67 | std::size_t, | |
68 | InVertex>::type Vertex; | |
69 | ||
70 | /** | |
71 | * Determine the type used to represent edges in the graph. If | |
72 | * the user has overridden the default (which is to be the same as | |
73 | * the distributed vertex selector type), use the user's | |
74 | * parameter. Otherwise, fall back to the value of @c Vertex. | |
75 | */ | |
76 | typedef typename mpl::if_<is_same<InEdgeIndex, | |
77 | distributedS<ProcessGroup, InVertex, | |
78 | InDistribution> >, | |
79 | Vertex, | |
80 | InEdgeIndex>::type EdgeIndex; | |
81 | ||
82 | public: | |
83 | /** | |
84 | * The type of the CSR graph that will be stored locally. | |
85 | */ | |
86 | typedef compressed_sparse_row_graph<directedS, VertexProperty, EdgeProperty, | |
87 | GraphProperty, Vertex, EdgeIndex> | |
88 | base_type; | |
89 | ||
90 | // ----------------------------------------------------------------- | |
91 | // Graph concept requirements | |
92 | typedef Vertex vertex_descriptor; | |
93 | typedef typename graph_traits<base_type>::edge_descriptor edge_descriptor; | |
94 | typedef directed_tag directed_category; | |
95 | typedef allow_parallel_edge_tag edge_parallel_category; | |
96 | typedef distributed_csr_tag traversal_category; | |
97 | static vertex_descriptor null_vertex(); | |
98 | ||
99 | // ----------------------------------------------------------------- | |
100 | // Distributed Vertex List Graph concept requirements | |
101 | typedef Vertex vertices_size_type; | |
102 | class vertex_iterator; | |
103 | ||
104 | // ----------------------------------------------------------------- | |
105 | // Distributed Edge List Graph concept requirements | |
106 | typedef EdgeIndex edges_size_type; | |
107 | class edge_iterator; | |
108 | ||
109 | // ----------------------------------------------------------------- | |
110 | // Incidence Graph concept requirements | |
111 | typedef typename graph_traits<base_type>::out_edge_iterator | |
112 | out_edge_iterator; | |
113 | typedef typename graph_traits<base_type>::degree_size_type | |
114 | degree_size_type; | |
115 | ||
116 | // ----------------------------------------------------------------- | |
117 | // Adjacency Graph concept requirements | |
118 | typedef typename graph_traits<base_type>::adjacency_iterator | |
119 | adjacency_iterator; | |
120 | ||
121 | // Note: This graph type does not model Bidirectional Graph. | |
122 | // However, this typedef is required to satisfy graph_traits. | |
123 | typedef void in_edge_iterator; | |
124 | ||
125 | // ----------------------------------------------------------------- | |
126 | // Distributed Container concept requirements | |
127 | typedef ProcessGroup process_group_type; | |
128 | typedef boost::parallel::variant_distribution<process_group_type, Vertex> | |
129 | distribution_type; | |
130 | ||
131 | // ----------------------------------------------------------------- | |
132 | // Workarounds | |
133 | // NOTE: This graph type does not have old-style graph properties. It only | |
134 | // accepts bundles. | |
135 | typedef no_property vertex_property_type; | |
136 | typedef no_property edge_property_type; | |
137 | typedef no_property graph_property_type; | |
138 | typedef typename mpl::if_<is_void<VertexProperty>, | |
139 | void****, | |
140 | VertexProperty>::type vertex_bundled; | |
141 | typedef typename mpl::if_<is_void<EdgeProperty>, | |
142 | void****, | |
143 | EdgeProperty>::type edge_bundled; | |
144 | typedef typename mpl::if_<is_void<GraphProperty>, | |
145 | void****, | |
146 | GraphProperty>::type graph_bundled; | |
147 | ||
148 | // ----------------------------------------------------------------- | |
149 | // Useful types | |
150 | typedef typename ProcessGroup::process_id_type process_id_type; | |
151 | ||
152 | // ----------------------------------------------------------------- | |
153 | // Graph constructors | |
154 | compressed_sparse_row_graph(const ProcessGroup& pg = ProcessGroup()) | |
155 | : m_process_group(pg), m_distribution(parallel::block(pg, 0)) {} | |
156 | ||
157 | compressed_sparse_row_graph(const GraphProperty& prop, | |
158 | const ProcessGroup& pg = ProcessGroup()) | |
159 | : m_process_group(pg), m_distribution(parallel::block(pg, 0)) {} | |
160 | ||
161 | compressed_sparse_row_graph(vertices_size_type numverts, | |
162 | const ProcessGroup& pg = ProcessGroup()) | |
163 | : m_process_group(pg), m_distribution(parallel::block(pg, 0)), | |
164 | m_base(numverts) | |
165 | {} | |
166 | ||
167 | compressed_sparse_row_graph(vertices_size_type numverts, | |
168 | const GraphProperty& prop, | |
169 | const ProcessGroup& pg = ProcessGroup()) | |
170 | : m_process_group(pg), m_distribution(parallel::block(pg, 0)), | |
171 | m_base(numverts) | |
172 | {} | |
173 | ||
174 | template <typename Distribution> | |
175 | compressed_sparse_row_graph(vertices_size_type numverts, | |
176 | const ProcessGroup& pg, | |
177 | const Distribution& dist) | |
178 | : m_process_group(pg), m_distribution(dist), m_base(numverts) {} | |
179 | ||
180 | template <typename Distribution> | |
181 | compressed_sparse_row_graph(vertices_size_type numverts, | |
182 | const GraphProperty& prop, | |
183 | const ProcessGroup& pg, | |
184 | const Distribution& dist) | |
185 | : m_process_group(pg), m_distribution(dist), m_base(numverts) {} | |
186 | ||
187 | template <typename InputIterator> | |
188 | compressed_sparse_row_graph(edges_are_unsorted_t, | |
189 | InputIterator edge_begin, InputIterator edge_end, | |
190 | vertices_size_type numverts, | |
191 | const ProcessGroup& pg = ProcessGroup(), | |
192 | const GraphProperty& prop = GraphProperty()); | |
193 | ||
194 | template <typename InputIterator, typename Distribution> | |
195 | compressed_sparse_row_graph(edges_are_unsorted_t, | |
196 | InputIterator edge_begin, InputIterator edge_end, | |
197 | vertices_size_type numverts, | |
198 | const ProcessGroup& pg, | |
199 | const Distribution& dist, | |
200 | const GraphProperty& prop = GraphProperty()); | |
201 | ||
202 | template <typename InputIterator, typename EdgePropertyIterator> | |
203 | compressed_sparse_row_graph(edges_are_unsorted_t, | |
204 | InputIterator edge_begin, InputIterator edge_end, | |
205 | EdgePropertyIterator ep_iter, | |
206 | vertices_size_type numverts, | |
207 | const ProcessGroup& pg = ProcessGroup(), | |
208 | const GraphProperty& prop = GraphProperty()); | |
209 | ||
210 | template <typename InputIterator, typename EdgePropertyIterator, | |
211 | typename Distribution> | |
212 | compressed_sparse_row_graph(edges_are_unsorted_t, | |
213 | InputIterator edge_begin, InputIterator edge_end, | |
214 | EdgePropertyIterator ep_iter, | |
215 | vertices_size_type numverts, | |
216 | const ProcessGroup& pg, | |
217 | const Distribution& dist, | |
218 | const GraphProperty& prop = GraphProperty()); | |
219 | ||
220 | template <typename InputIterator> | |
221 | compressed_sparse_row_graph(edges_are_sorted_t, | |
222 | InputIterator edge_begin, InputIterator edge_end, | |
223 | vertices_size_type numverts, | |
224 | edges_size_type numedges = 0, | |
225 | const ProcessGroup& pg = ProcessGroup(), | |
226 | const GraphProperty& prop = GraphProperty()); | |
227 | ||
228 | template <typename InputIterator, typename Distribution> | |
229 | compressed_sparse_row_graph(edges_are_sorted_t, | |
230 | InputIterator edge_begin, InputIterator edge_end, | |
231 | vertices_size_type numverts, | |
232 | const ProcessGroup& pg, | |
233 | const Distribution& dist, | |
234 | const GraphProperty& prop = GraphProperty()); | |
235 | ||
236 | template <typename InputIterator, typename EdgePropertyIterator> | |
237 | compressed_sparse_row_graph(edges_are_sorted_t, | |
238 | InputIterator edge_begin, InputIterator edge_end, | |
239 | EdgePropertyIterator ep_iter, | |
240 | vertices_size_type numverts, | |
241 | edges_size_type numedges = 0, | |
242 | const ProcessGroup& pg = ProcessGroup(), | |
243 | const GraphProperty& prop = GraphProperty()); | |
244 | ||
245 | template <typename InputIterator, typename EdgePropertyIterator, | |
246 | typename Distribution> | |
247 | compressed_sparse_row_graph(edges_are_sorted_t, | |
248 | InputIterator edge_begin, InputIterator edge_end, | |
249 | EdgePropertyIterator ep_iter, | |
250 | vertices_size_type numverts, | |
251 | const ProcessGroup& pg, | |
252 | const Distribution& dist, | |
253 | const GraphProperty& prop = GraphProperty()); | |
254 | ||
255 | template <typename MultiPassInputIterator> | |
256 | compressed_sparse_row_graph(edges_are_unsorted_multi_pass_t, | |
257 | MultiPassInputIterator edge_begin, | |
258 | MultiPassInputIterator edge_end, | |
259 | vertices_size_type numverts, | |
260 | const ProcessGroup& pg = ProcessGroup(), | |
261 | const GraphProperty& prop = GraphProperty()); | |
262 | ||
263 | template <typename MultiPassInputIterator, typename Distribution> | |
264 | compressed_sparse_row_graph(edges_are_unsorted_multi_pass_t, | |
265 | MultiPassInputIterator edge_begin, | |
266 | MultiPassInputIterator edge_end, | |
267 | vertices_size_type numverts, | |
268 | const ProcessGroup& pg, | |
269 | const Distribution& dist, | |
270 | const GraphProperty& prop = GraphProperty()); | |
271 | ||
272 | template <typename MultiPassInputIterator, typename EdgePropertyIterator> | |
273 | compressed_sparse_row_graph(edges_are_unsorted_multi_pass_t, | |
274 | MultiPassInputIterator edge_begin, | |
275 | MultiPassInputIterator edge_end, | |
276 | EdgePropertyIterator ep_iter, | |
277 | vertices_size_type numverts, | |
278 | const ProcessGroup& pg = ProcessGroup(), | |
279 | const GraphProperty& prop = GraphProperty()); | |
280 | ||
281 | template <typename MultiPassInputIterator, typename EdgePropertyIterator, | |
282 | typename Distribution> | |
283 | compressed_sparse_row_graph(edges_are_unsorted_multi_pass_t, | |
284 | MultiPassInputIterator edge_begin, | |
285 | MultiPassInputIterator edge_end, | |
286 | EdgePropertyIterator ep_iter, | |
287 | vertices_size_type numverts, | |
288 | const ProcessGroup& pg, | |
289 | const Distribution& dist, | |
290 | const GraphProperty& prop = GraphProperty()); | |
291 | ||
292 | template <typename Source> | |
293 | compressed_sparse_row_graph(distributed_construct_inplace_from_sources_and_targets_t, | |
294 | std::vector<Source>& sources, | |
295 | std::vector<vertex_descriptor>& targets, | |
296 | vertices_size_type numverts, | |
297 | const ProcessGroup& pg = ProcessGroup(), | |
298 | const GraphProperty& prop = GraphProperty()); | |
299 | ||
300 | template <typename Distribution, typename Source> | |
301 | compressed_sparse_row_graph(distributed_construct_inplace_from_sources_and_targets_t, | |
302 | std::vector<Source>& sources, | |
303 | std::vector<vertex_descriptor>& targets, | |
304 | vertices_size_type numverts, | |
305 | const ProcessGroup& pg, | |
306 | const Distribution& dist, | |
307 | const GraphProperty& prop = GraphProperty()); | |
308 | ||
309 | template <typename Source> | |
310 | compressed_sparse_row_graph(distributed_construct_inplace_from_sources_and_targets_t, | |
311 | std::vector<Source>& sources, | |
312 | std::vector<vertex_descriptor>& targets, | |
313 | std::vector<edge_bundled>& edge_props, | |
314 | vertices_size_type numverts, | |
315 | const ProcessGroup& pg = ProcessGroup(), | |
316 | const GraphProperty& prop = GraphProperty()); | |
317 | ||
318 | template <typename Distribution, typename Source> | |
319 | compressed_sparse_row_graph(distributed_construct_inplace_from_sources_and_targets_t, | |
320 | std::vector<Source>& sources, | |
321 | std::vector<vertex_descriptor>& targets, | |
322 | std::vector<edge_bundled>& edge_props, | |
323 | vertices_size_type numverts, | |
324 | const ProcessGroup& pg, | |
325 | const Distribution& dist, | |
326 | const GraphProperty& prop = GraphProperty()); | |
327 | ||
328 | template<typename InputIterator> | |
329 | compressed_sparse_row_graph(InputIterator edge_begin, InputIterator edge_end, | |
330 | vertices_size_type numverts, | |
331 | const ProcessGroup& pg = ProcessGroup(), | |
332 | const GraphProperty& prop = GraphProperty()); | |
333 | ||
334 | template<typename InputIterator, typename EdgePropertyIterator> | |
335 | compressed_sparse_row_graph(InputIterator edge_begin, InputIterator edge_end, | |
336 | EdgePropertyIterator ep_iter, | |
337 | vertices_size_type numverts, | |
338 | const ProcessGroup& pg = ProcessGroup(), | |
339 | const GraphProperty& prop = GraphProperty()); | |
340 | ||
341 | template<typename InputIterator, typename Distribution> | |
342 | compressed_sparse_row_graph(InputIterator edge_begin, InputIterator edge_end, | |
343 | vertices_size_type numverts, | |
344 | const ProcessGroup& pg, | |
345 | const Distribution& dist, | |
346 | const GraphProperty& prop = GraphProperty()); | |
347 | ||
348 | template<typename InputIterator, typename EdgePropertyIterator, | |
349 | typename Distribution> | |
350 | compressed_sparse_row_graph(InputIterator edge_begin, InputIterator edge_end, | |
351 | EdgePropertyIterator ep_iter, | |
352 | vertices_size_type numverts, | |
353 | const ProcessGroup& pg, | |
354 | const Distribution& dist, | |
355 | const GraphProperty& prop = GraphProperty()); | |
356 | ||
357 | base_type& base() { return m_base; } | |
358 | const base_type& base() const { return m_base; } | |
359 | ||
360 | process_group_type process_group() const { return m_process_group.base(); } | |
361 | ||
362 | distribution_type& distribution() { return m_distribution; } | |
363 | const distribution_type& distribution() const { return m_distribution; } | |
364 | ||
365 | // Directly access a vertex or edge bundle | |
366 | vertex_bundled& operator[](vertex_descriptor v) | |
367 | { | |
368 | return get(vertex_bundle, *this, v); | |
369 | } | |
370 | ||
371 | const vertex_bundled& operator[](vertex_descriptor v) const | |
372 | { | |
373 | return get(vertex_bundle, *this, v); | |
374 | } | |
375 | ||
376 | edge_bundled& operator[](edge_descriptor e) | |
377 | { | |
378 | return get(edge_bundle, *this, e); | |
379 | } | |
380 | ||
381 | const edge_bundled& operator[](edge_descriptor e) const | |
382 | { | |
383 | return get(edge_bundle, *this, e); | |
384 | } | |
385 | ||
386 | // Create a vertex descriptor from a process ID and a local index. | |
387 | vertex_descriptor | |
388 | make_vertex_descriptor(process_id_type p, vertex_descriptor v) const | |
389 | { | |
390 | vertex_descriptor vertex_local_index_bits = | |
391 | sizeof(vertex_descriptor) * CHAR_BIT - processor_bits; | |
392 | return v | ((vertex_descriptor)p << vertex_local_index_bits); | |
393 | } | |
394 | ||
395 | // Convert a local vertex descriptor into a global vertex descriptor | |
396 | vertex_descriptor local_to_global_vertex(vertex_descriptor v) const | |
397 | { | |
398 | return make_vertex_descriptor(process_id(m_process_group), v); | |
399 | } | |
400 | ||
401 | // Structural modification | |
402 | vertex_descriptor add_vertex() | |
403 | { | |
404 | typename graph_traits<base_type>::vertex_descriptor v | |
405 | = boost::add_vertex(m_base); | |
406 | ||
407 | return make_vertex_descriptor(process_id(m_process_group), v); | |
408 | } | |
409 | ||
410 | vertex_descriptor add_vertex(const vertex_bundled& p) | |
411 | { | |
412 | typename graph_traits<base_type>::vertex_descriptor v | |
413 | = boost::add_vertex(m_base, p); | |
414 | ||
415 | return make_vertex_descriptor(process_id(m_process_group), v); | |
416 | } | |
417 | ||
418 | vertex_descriptor add_vertices(vertices_size_type count) | |
419 | { | |
420 | typename graph_traits<base_type>::vertex_descriptor v | |
421 | = boost::add_vertices(count, m_base); | |
422 | ||
423 | return make_vertex_descriptor(process_id(m_process_group), v); | |
424 | } | |
425 | ||
426 | template <typename InputIterator> | |
427 | void | |
428 | add_edges(InputIterator first, InputIterator last) | |
429 | { boost::add_edges_global(first, last, get(vertex_local, *this), m_base); } | |
430 | ||
431 | template <typename InputIterator, typename EdgePropertyIterator> | |
432 | void | |
433 | add_edges(InputIterator first, InputIterator last, | |
434 | EdgePropertyIterator ep_iter, | |
435 | EdgePropertyIterator ep_iter_end) | |
436 | { boost::add_edges_global(first, last, ep_iter, ep_iter_end, | |
437 | get(vertex_local, *this), m_base); } | |
438 | ||
439 | template <typename InputIterator> | |
440 | void | |
441 | add_edges_sorted(InputIterator first, InputIterator last) | |
442 | { boost::add_edges_sorted_global(first, last, | |
443 | get(vertex_local, *this), m_base); } | |
444 | ||
445 | template <typename InputIterator, typename EdgePropertyIterator> | |
446 | void | |
447 | add_edges_sorted(InputIterator first_sorted, InputIterator last_sorted, | |
448 | EdgePropertyIterator ep_iter_sorted) | |
449 | { boost::add_edges_sorted_global(first_sorted, last_sorted, ep_iter_sorted, | |
450 | get(vertex_local, *this), m_base); } | |
451 | ||
452 | protected: | |
453 | ProcessGroup m_process_group; | |
454 | distribution_type m_distribution; | |
455 | base_type m_base; | |
456 | }; | |
457 | ||
458 | /** @brief Helper macro containing the template parameters for the | |
459 | * distributed CSR graph. | |
460 | * | |
461 | * This macro contains all of the template parameters needed for the | |
462 | * distributed compressed_sparse_row graph type. It is used to reduce | |
463 | * the amount of typing required to declare free functions for this | |
464 | * graph type. | |
465 | */ | |
466 | #define BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS \ | |
467 | typename VertexProperty, typename EdgeProperty, \ | |
468 | typename GraphProperty, typename ProcessGroup, typename InVertex, \ | |
469 | typename InDistribution, typename InEdgeIndex | |
470 | ||
471 | /** @brief Helper macro containing the typical instantiation of the | |
472 | * distributed CSR graph. | |
473 | * | |
474 | * This macro contains an instantiation of the distributed CSR graph | |
475 | * type using the typical template parameters names (e.g., those | |
476 | * provided by the macro @c | |
477 | * BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS). It is used to reduce | |
478 | * the amount of typing required to declare free functions for this | |
479 | * graph type. | |
480 | */ | |
481 | #define BOOST_DISTRIB_CSR_GRAPH_TYPE \ | |
482 | compressed_sparse_row_graph< \ | |
483 | directedS, VertexProperty, EdgeProperty, GraphProperty, \ | |
484 | distributedS<ProcessGroup, InVertex, InDistribution>, \ | |
485 | InEdgeIndex> | |
486 | ||
487 | // ----------------------------------------------------------------- | |
488 | // Graph concept operations | |
489 | template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS> | |
490 | inline typename BOOST_DISTRIB_CSR_GRAPH_TYPE::vertex_descriptor | |
491 | BOOST_DISTRIB_CSR_GRAPH_TYPE::null_vertex() | |
492 | { | |
493 | return graph_traits<base_type>::null_vertex(); | |
494 | } | |
495 | ||
496 | // ----------------------------------------------------------------- | |
497 | // Incidence Graph concept operations | |
498 | template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS> | |
499 | inline typename BOOST_DISTRIB_CSR_GRAPH_TYPE::vertex_descriptor | |
500 | source(typename BOOST_DISTRIB_CSR_GRAPH_TYPE::edge_descriptor e, | |
501 | const BOOST_DISTRIB_CSR_GRAPH_TYPE&) | |
502 | { return e.src; } | |
503 | ||
504 | template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS> | |
505 | inline typename BOOST_DISTRIB_CSR_GRAPH_TYPE::vertex_descriptor | |
506 | target(typename BOOST_DISTRIB_CSR_GRAPH_TYPE::edge_descriptor e, | |
507 | const BOOST_DISTRIB_CSR_GRAPH_TYPE& g) | |
508 | { return target(e, g.base()); } | |
509 | ||
510 | template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS> | |
511 | inline std::pair<typename BOOST_DISTRIB_CSR_GRAPH_TYPE::out_edge_iterator, | |
512 | typename BOOST_DISTRIB_CSR_GRAPH_TYPE::out_edge_iterator> | |
513 | out_edges(typename BOOST_DISTRIB_CSR_GRAPH_TYPE::vertex_descriptor u, | |
514 | const BOOST_DISTRIB_CSR_GRAPH_TYPE& g) | |
515 | { | |
516 | typedef typename BOOST_DISTRIB_CSR_GRAPH_TYPE::edges_size_type | |
517 | edges_size_type; | |
518 | typedef typename BOOST_DISTRIB_CSR_GRAPH_TYPE::edge_descriptor ed; | |
519 | typedef typename BOOST_DISTRIB_CSR_GRAPH_TYPE::out_edge_iterator it; | |
520 | edges_size_type u_local = get(vertex_local, g, u); | |
521 | edges_size_type u_row_start = g.base().m_forward.m_rowstart[u_local]; | |
522 | edges_size_type next_row_start = g.base().m_forward.m_rowstart[u_local + 1]; | |
523 | return std::make_pair(it(ed(u, u_row_start)), | |
524 | it(ed(u, (std::max)(u_row_start, next_row_start)))); | |
525 | } | |
526 | ||
527 | template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS> | |
528 | inline typename BOOST_DISTRIB_CSR_GRAPH_TYPE::degree_size_type | |
529 | out_degree(typename BOOST_DISTRIB_CSR_GRAPH_TYPE::vertex_descriptor u, | |
530 | const BOOST_DISTRIB_CSR_GRAPH_TYPE& g) | |
531 | { | |
532 | return out_degree(get(vertex_local, g, u), g.base()); | |
533 | } | |
534 | ||
535 | // ----------------------------------------------------------------- | |
536 | // DistributedGraph concept requirements | |
537 | template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS> | |
538 | void synchronize(const BOOST_DISTRIB_CSR_GRAPH_TYPE& g) | |
539 | { | |
540 | synchronize(g.process_group()); | |
541 | } | |
542 | ||
543 | template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS> | |
544 | ProcessGroup | |
545 | process_group(const BOOST_DISTRIB_CSR_GRAPH_TYPE& g) | |
546 | { return g.process_group(); } | |
547 | ||
548 | ||
549 | // ----------------------------------------------------------------- | |
550 | // Adjacency Graph concept requirements | |
551 | template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS> | |
552 | inline std::pair<typename BOOST_DISTRIB_CSR_GRAPH_TYPE::adjacency_iterator, | |
553 | typename BOOST_DISTRIB_CSR_GRAPH_TYPE::adjacency_iterator> | |
554 | adjacent_vertices(typename BOOST_DISTRIB_CSR_GRAPH_TYPE::vertex_descriptor u, | |
555 | const BOOST_DISTRIB_CSR_GRAPH_TYPE& g) | |
556 | { | |
557 | return adjacent_vertices(get(vertex_local, g, u), g.base()); | |
558 | } | |
559 | ||
560 | // ----------------------------------------------------------------- | |
561 | // Distributed Vertex List Graph concept operations | |
562 | template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS> | |
563 | class BOOST_DISTRIB_CSR_GRAPH_TYPE::vertex_iterator | |
564 | : public iterator_adaptor<vertex_iterator, | |
565 | counting_iterator<Vertex>, | |
566 | Vertex, | |
567 | random_access_traversal_tag, | |
568 | Vertex> | |
569 | { | |
570 | typedef iterator_adaptor<vertex_iterator, | |
571 | counting_iterator<Vertex>, | |
572 | Vertex, | |
573 | random_access_traversal_tag, | |
574 | Vertex> inherited; | |
575 | public: | |
576 | vertex_iterator() {} | |
577 | ||
578 | explicit vertex_iterator(Vertex v, const self_type* graph) | |
579 | : inherited(counting_iterator<Vertex>(v)), graph(graph) { } | |
580 | ||
581 | Vertex dereference() const | |
582 | { | |
583 | return graph->local_to_global_vertex(*(this->base_reference())); | |
584 | } | |
585 | ||
586 | friend class iterator_core_access; | |
587 | ||
588 | private: | |
589 | const self_type* graph; | |
590 | }; | |
591 | ||
592 | template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS> | |
593 | inline typename BOOST_DISTRIB_CSR_GRAPH_TYPE::degree_size_type | |
594 | num_vertices(const BOOST_DISTRIB_CSR_GRAPH_TYPE& g) | |
595 | { | |
596 | return num_vertices(g.base()); | |
597 | } | |
598 | ||
599 | template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS> | |
600 | inline std::pair<typename BOOST_DISTRIB_CSR_GRAPH_TYPE::vertex_iterator, | |
601 | typename BOOST_DISTRIB_CSR_GRAPH_TYPE::vertex_iterator> | |
602 | vertices(const BOOST_DISTRIB_CSR_GRAPH_TYPE& g) | |
603 | { | |
604 | typedef typename BOOST_DISTRIB_CSR_GRAPH_TYPE::vertex_iterator | |
605 | vertex_iterator; | |
606 | return std::make_pair(vertex_iterator(0, &g), | |
607 | vertex_iterator(num_vertices(g), &g)); | |
608 | } | |
609 | ||
610 | // ----------------------------------------------------------------- | |
611 | // Distributed Edge List Graph concept operations | |
612 | template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS> | |
613 | class BOOST_DISTRIB_CSR_GRAPH_TYPE::edge_iterator | |
614 | { | |
615 | public: | |
616 | typedef std::forward_iterator_tag iterator_category; | |
617 | typedef edge_descriptor value_type; | |
618 | ||
619 | typedef const edge_descriptor* pointer; | |
620 | ||
621 | typedef edge_descriptor reference; | |
622 | typedef typename int_t<CHAR_BIT * sizeof(EdgeIndex)>::fast difference_type; | |
623 | ||
624 | edge_iterator() : graph(0), current_edge(), end_of_this_vertex(0) {} | |
625 | ||
626 | edge_iterator(const compressed_sparse_row_graph& graph, | |
627 | edge_descriptor current_edge, | |
628 | EdgeIndex end_of_this_vertex) | |
629 | : graph(&graph), local_src(current_edge.src), current_edge(current_edge), | |
630 | end_of_this_vertex(end_of_this_vertex) | |
631 | { | |
632 | // The edge that comes in has a local source vertex. Make it global. | |
633 | current_edge.src = graph.local_to_global_vertex(current_edge.src); | |
634 | } | |
635 | ||
636 | // From InputIterator | |
637 | reference operator*() const { return current_edge; } | |
638 | pointer operator->() const { return ¤t_edge; } | |
639 | ||
640 | bool operator==(const edge_iterator& o) const { | |
641 | return current_edge == o.current_edge; | |
642 | } | |
643 | bool operator!=(const edge_iterator& o) const { | |
644 | return current_edge != o.current_edge; | |
645 | } | |
646 | ||
647 | edge_iterator& operator++() | |
648 | { | |
649 | ++current_edge.idx; | |
650 | while (current_edge.idx == end_of_this_vertex && local_src < num_vertices(*graph)-1) { | |
651 | ++local_src; | |
652 | current_edge.src = graph->local_to_global_vertex(local_src); | |
653 | end_of_this_vertex = graph->base().m_forward.m_rowstart[local_src + 1]; | |
654 | } | |
655 | return *this; | |
656 | } | |
657 | ||
658 | edge_iterator operator++(int) { | |
659 | edge_iterator temp = *this; | |
660 | ++*this; | |
661 | return temp; | |
662 | } | |
663 | ||
664 | private: | |
665 | const compressed_sparse_row_graph* graph; | |
666 | EdgeIndex local_src; | |
667 | edge_descriptor current_edge; | |
668 | EdgeIndex end_of_this_vertex; | |
669 | }; | |
670 | ||
671 | template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS> | |
672 | inline typename BOOST_DISTRIB_CSR_GRAPH_TYPE::edges_size_type | |
673 | num_edges(const BOOST_DISTRIB_CSR_GRAPH_TYPE& g) | |
674 | { | |
675 | return g.base().m_forward.m_column.size(); | |
676 | } | |
677 | ||
678 | template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS> | |
679 | std::pair<typename BOOST_DISTRIB_CSR_GRAPH_TYPE::edge_iterator, | |
680 | typename BOOST_DISTRIB_CSR_GRAPH_TYPE::edge_iterator> | |
681 | edges(const BOOST_DISTRIB_CSR_GRAPH_TYPE& g) | |
682 | { | |
683 | typedef typename BOOST_DISTRIB_CSR_GRAPH_TYPE::vertex_descriptor Vertex; | |
684 | typedef typename BOOST_DISTRIB_CSR_GRAPH_TYPE::edge_iterator ei; | |
685 | typedef typename BOOST_DISTRIB_CSR_GRAPH_TYPE::edge_descriptor edgedesc; | |
686 | if (g.base().m_forward.m_rowstart.size() == 1 || | |
687 | g.base().m_forward.m_column.empty()) { | |
688 | return std::make_pair(ei(), ei()); | |
689 | } else { | |
690 | // Find the first vertex that has outgoing edges | |
691 | Vertex src = 0; | |
692 | while (g.base().m_forward.m_rowstart[src + 1] == 0) ++src; | |
693 | return std::make_pair(ei(g, edgedesc(src, 0), g.base().m_forward.m_rowstart[src + 1]), | |
694 | ei(g, edgedesc(num_vertices(g), g.base().m_forward.m_column.size()), 0)); | |
695 | } | |
696 | } | |
697 | ||
698 | // ----------------------------------------------------------------- | |
699 | // Graph constructors | |
700 | ||
701 | // Returns true if a vertex belongs to a process according to a distribution | |
702 | template <typename OwnerMap, typename ProcessId> | |
703 | struct local_vertex { | |
704 | ||
705 | local_vertex(OwnerMap owner, ProcessId id) | |
706 | : owner(owner), id(id) {} | |
707 | ||
708 | template <typename Vertex> | |
709 | bool operator()(Vertex x) | |
710 | { return get(owner, x) == id; } | |
711 | ||
712 | template <typename Vertex> | |
713 | bool operator()(Vertex x) const | |
714 | { return get(owner, x) == id; } | |
715 | ||
716 | private: | |
717 | OwnerMap owner; | |
718 | ProcessId id; | |
719 | }; | |
720 | ||
721 | // Returns true if a vertex belongs to a process according to a distribution | |
722 | template <typename OwnerMap, typename ProcessId> | |
723 | struct local_edge { | |
724 | ||
725 | local_edge(OwnerMap owner, ProcessId id) | |
726 | : owner(owner), id(id) {} | |
727 | ||
728 | template <typename Vertex> | |
729 | bool operator()(std::pair<Vertex, Vertex>& x) | |
730 | { return get(owner, x.first) == id; } | |
731 | ||
732 | template <typename Vertex> | |
733 | bool operator()(const std::pair<Vertex, Vertex>& x) const | |
734 | { return get(owner, x.first) == id; } | |
735 | ||
736 | private: | |
737 | OwnerMap owner; | |
738 | ProcessId id; | |
739 | }; | |
740 | ||
741 | // Turns an index iterator into a vertex iterator | |
742 | template<typename IndexIterator, typename Graph> | |
743 | class index_to_vertex_iterator { | |
744 | ||
745 | public: | |
746 | typedef std::input_iterator_tag iterator_category; | |
747 | typedef typename graph_traits<Graph>::vertex_descriptor Vertex; | |
748 | typedef std::pair<Vertex, Vertex> value_type; | |
749 | typedef const value_type& reference; | |
750 | typedef const value_type* pointer; | |
751 | typedef void difference_type; | |
752 | ||
753 | index_to_vertex_iterator(IndexIterator index, | |
754 | const Graph& g) | |
755 | : index(index), g(g), current(to_edge(*index)) {} | |
756 | ||
757 | reference operator*() { current = to_edge(*index); return current; } | |
758 | pointer operator->() { current = to_edge(*index); return ¤t; } | |
759 | ||
760 | index_to_vertex_iterator& operator++() | |
761 | { | |
762 | ++index; | |
763 | return *this; | |
764 | } | |
765 | ||
766 | index_to_vertex_iterator operator++(int) | |
767 | { | |
768 | index_to_vertex_iterator temp(*this); | |
769 | ++(*this); | |
770 | return temp; | |
771 | } | |
772 | ||
773 | bool operator==(const index_to_vertex_iterator& other) const | |
774 | { return index == other.index; } | |
775 | ||
776 | bool operator!=(const index_to_vertex_iterator& other) const | |
777 | { return !(*this == other); } | |
778 | ||
779 | private: | |
780 | value_type to_edge(const typename std::iterator_traits<IndexIterator>::value_type& x) | |
781 | { return std::make_pair(vertex(x.first, g), vertex(x.second, g)); } | |
782 | ||
783 | IndexIterator index; | |
784 | const Graph& g; | |
785 | value_type current; | |
786 | }; | |
787 | ||
788 | template <typename Distribution, typename Graph> | |
789 | struct index_to_vertex_func { | |
790 | ||
791 | typedef typename boost::graph_traits<Graph>::vertex_descriptor vertex_descriptor; | |
792 | typedef typename boost::graph_traits<Graph>::vertices_size_type vertices_size_type; | |
793 | typedef std::pair<vertex_descriptor, vertex_descriptor> result_type; | |
794 | typedef std::pair<vertices_size_type, vertices_size_type> base_iterator_type; | |
795 | ||
796 | index_to_vertex_func(const Distribution& dist, const Graph& g) | |
797 | : dist(dist), g(g) {} | |
798 | ||
799 | ||
800 | result_type operator()(const base_iterator_type& p) const | |
801 | { | |
802 | return std::make_pair(vertex(p.first, g), vertex(p.second, g)); | |
803 | } | |
804 | ||
805 | private: | |
806 | const Distribution& dist; | |
807 | const Graph& g; | |
808 | }; | |
809 | ||
810 | // NGE: This method only works with iterators that have a difference_type, | |
811 | // the index_to_vertex_iterator class above is retained for compatibility | |
812 | // with BGL generators which have no difference_type | |
813 | template <typename IndexIterator, typename Distribution, typename Graph> | |
814 | boost::transform_iterator<index_to_vertex_func<Distribution, Graph>, IndexIterator> | |
815 | make_index_to_vertex_iterator(IndexIterator it, const Distribution& dist, | |
816 | const Graph& g) { | |
817 | return boost::make_transform_iterator( | |
818 | it, index_to_vertex_func<Distribution, Graph>(dist, g)); | |
819 | } | |
820 | ||
821 | // Forward declaration of csr_vertex_owner_map | |
822 | template<typename ProcessID, typename Key> class csr_vertex_owner_map; | |
823 | ||
824 | template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS> | |
825 | template<typename InputIterator> | |
826 | BOOST_DISTRIB_CSR_GRAPH_TYPE:: | |
827 | compressed_sparse_row_graph(edges_are_unsorted_t, | |
828 | InputIterator edge_begin, InputIterator edge_end, | |
829 | vertices_size_type numverts, | |
830 | const ProcessGroup& pg, | |
831 | const GraphProperty& prop) | |
832 | : m_process_group(pg), | |
833 | m_distribution(parallel::block(m_process_group, numverts)), | |
834 | m_base(edges_are_unsorted_global, | |
835 | index_to_vertex_iterator<InputIterator, BOOST_DISTRIB_CSR_GRAPH_TYPE>(edge_begin, *this), | |
836 | index_to_vertex_iterator<InputIterator, BOOST_DISTRIB_CSR_GRAPH_TYPE>(edge_end, *this), | |
837 | m_distribution.block_size(process_id(m_process_group), numverts), | |
838 | get(vertex_local, *this), | |
839 | local_vertex<csr_vertex_owner_map<process_id_type, vertex_descriptor>, | |
840 | process_id_type> (get(vertex_owner, *this), process_id(pg)), | |
841 | prop) | |
842 | { } | |
843 | ||
844 | template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS> | |
845 | template <typename InputIterator, typename Distribution> | |
846 | BOOST_DISTRIB_CSR_GRAPH_TYPE:: | |
847 | compressed_sparse_row_graph(edges_are_unsorted_t, | |
848 | InputIterator edge_begin, InputIterator edge_end, | |
849 | vertices_size_type numverts, | |
850 | const ProcessGroup& pg, | |
851 | const Distribution& dist, | |
852 | const GraphProperty& prop) | |
853 | : m_process_group(pg), | |
854 | m_distribution(dist), | |
855 | m_base(edges_are_unsorted_global, | |
856 | index_to_vertex_iterator<InputIterator, BOOST_DISTRIB_CSR_GRAPH_TYPE>(edge_begin, *this), | |
857 | index_to_vertex_iterator<InputIterator, BOOST_DISTRIB_CSR_GRAPH_TYPE>(edge_end, *this), | |
858 | m_distribution.block_size(process_id(m_process_group), numverts), | |
859 | get(vertex_local, *this), | |
860 | local_vertex<csr_vertex_owner_map<process_id_type, vertex_descriptor>, | |
861 | process_id_type> (get(vertex_owner, *this), process_id(pg)), | |
862 | prop) | |
863 | { } | |
864 | ||
865 | template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS> | |
866 | template<typename InputIterator, typename EdgePropertyIterator> | |
867 | BOOST_DISTRIB_CSR_GRAPH_TYPE:: | |
868 | compressed_sparse_row_graph(edges_are_unsorted_t, | |
869 | InputIterator edge_begin, InputIterator edge_end, | |
870 | EdgePropertyIterator ep_iter, | |
871 | vertices_size_type numverts, | |
872 | const ProcessGroup& pg, | |
873 | const GraphProperty& prop) | |
874 | : m_process_group(pg), | |
875 | m_distribution(parallel::block(m_process_group, numverts)), | |
876 | m_base(edges_are_unsorted_global, | |
877 | index_to_vertex_iterator<InputIterator, BOOST_DISTRIB_CSR_GRAPH_TYPE>(edge_begin, *this), | |
878 | index_to_vertex_iterator<InputIterator, BOOST_DISTRIB_CSR_GRAPH_TYPE>(edge_end, *this), | |
879 | ep_iter, | |
880 | m_distribution.block_size(process_id(m_process_group), numverts), | |
881 | get(vertex_local, *this), | |
882 | local_vertex<csr_vertex_owner_map<process_id_type, vertex_descriptor>, | |
883 | process_id_type> (get(vertex_owner, *this), process_id(pg)), | |
884 | prop) | |
885 | { } | |
886 | ||
887 | template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS> | |
888 | template <typename InputIterator, typename EdgePropertyIterator, | |
889 | typename Distribution> | |
890 | BOOST_DISTRIB_CSR_GRAPH_TYPE:: | |
891 | compressed_sparse_row_graph(edges_are_unsorted_t, | |
892 | InputIterator edge_begin, InputIterator edge_end, | |
893 | EdgePropertyIterator ep_iter, | |
894 | vertices_size_type numverts, | |
895 | const ProcessGroup& pg, | |
896 | const Distribution& dist, | |
897 | const GraphProperty& prop) | |
898 | : m_process_group(pg), | |
899 | m_distribution(dist), | |
900 | m_base(edges_are_unsorted_global, | |
901 | index_to_vertex_iterator<InputIterator, BOOST_DISTRIB_CSR_GRAPH_TYPE>(edge_begin, *this), | |
902 | index_to_vertex_iterator<InputIterator, BOOST_DISTRIB_CSR_GRAPH_TYPE>(edge_end, *this), | |
903 | ep_iter, | |
904 | m_distribution.block_size(process_id(m_process_group), numverts), | |
905 | get(vertex_local, *this), | |
906 | local_vertex<csr_vertex_owner_map<process_id_type, vertex_descriptor>, | |
907 | process_id_type> (get(vertex_owner, *this), process_id(pg)), | |
908 | prop) | |
909 | { } | |
910 | ||
911 | template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS> | |
912 | template<typename InputIterator> | |
913 | BOOST_DISTRIB_CSR_GRAPH_TYPE:: | |
914 | compressed_sparse_row_graph(edges_are_sorted_t, | |
915 | InputIterator edge_begin, InputIterator edge_end, | |
916 | vertices_size_type numverts, | |
917 | edges_size_type numedges, // This is not used as there is no appropriate BGL ctor | |
918 | const ProcessGroup& pg, | |
919 | const GraphProperty& prop) | |
920 | : m_process_group(pg), | |
921 | m_distribution(parallel::block(m_process_group, numverts)), | |
922 | m_base(edges_are_sorted_global, | |
923 | index_to_vertex_iterator<InputIterator, BOOST_DISTRIB_CSR_GRAPH_TYPE>(edge_begin, *this), | |
924 | index_to_vertex_iterator<InputIterator, BOOST_DISTRIB_CSR_GRAPH_TYPE>(edge_end, *this), | |
925 | get(vertex_local, *this), | |
926 | local_vertex<csr_vertex_owner_map<process_id_type, vertex_descriptor>, | |
927 | process_id_type> (get(vertex_owner, *this), process_id(pg)), | |
928 | m_distribution.block_size(process_id(m_process_group), numverts), | |
929 | prop) | |
930 | { } | |
931 | ||
932 | template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS> | |
933 | template <typename InputIterator, typename Distribution> | |
934 | BOOST_DISTRIB_CSR_GRAPH_TYPE:: | |
935 | compressed_sparse_row_graph(edges_are_sorted_t, | |
936 | InputIterator edge_begin, InputIterator edge_end, | |
937 | vertices_size_type numverts, | |
938 | const ProcessGroup& pg, | |
939 | const Distribution& dist, | |
940 | const GraphProperty& prop) | |
941 | : m_process_group(pg), | |
942 | m_distribution(dist), | |
943 | m_base(edges_are_sorted_global, | |
944 | index_to_vertex_iterator<InputIterator, BOOST_DISTRIB_CSR_GRAPH_TYPE>(edge_begin, *this), | |
945 | index_to_vertex_iterator<InputIterator, BOOST_DISTRIB_CSR_GRAPH_TYPE>(edge_end, *this), | |
946 | get(vertex_local, *this), | |
947 | local_vertex<csr_vertex_owner_map<process_id_type, vertex_descriptor>, | |
948 | process_id_type> (get(vertex_owner, *this), process_id(pg)), | |
949 | m_distribution.block_size(process_id(m_process_group), numverts), | |
950 | prop) | |
951 | { } | |
952 | ||
953 | template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS> | |
954 | template<typename InputIterator, typename EdgePropertyIterator> | |
955 | BOOST_DISTRIB_CSR_GRAPH_TYPE:: | |
956 | compressed_sparse_row_graph(edges_are_sorted_t, | |
957 | InputIterator edge_begin, InputIterator edge_end, | |
958 | EdgePropertyIterator ep_iter, | |
959 | vertices_size_type numverts, | |
960 | edges_size_type numedges, // This is not used as there is no appropriate BGL ctor | |
961 | const ProcessGroup& pg, | |
962 | const GraphProperty& prop) | |
963 | : m_process_group(pg), | |
964 | m_distribution(parallel::block(m_process_group, numverts)), | |
965 | m_base(edges_are_sorted_global, | |
966 | index_to_vertex_iterator<InputIterator, BOOST_DISTRIB_CSR_GRAPH_TYPE>(edge_begin, *this), | |
967 | index_to_vertex_iterator<InputIterator, BOOST_DISTRIB_CSR_GRAPH_TYPE>(edge_end, *this), | |
968 | ep_iter, | |
969 | get(vertex_local, *this), | |
970 | local_vertex<csr_vertex_owner_map<process_id_type, vertex_descriptor>, | |
971 | process_id_type> (get(vertex_owner, *this), process_id(pg)), | |
972 | m_distribution.block_size(process_id(m_process_group), numverts), | |
973 | prop) | |
974 | { } | |
975 | ||
976 | template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS> | |
977 | template<typename InputIterator, typename EdgePropertyIterator, | |
978 | typename Distribution> | |
979 | BOOST_DISTRIB_CSR_GRAPH_TYPE:: | |
980 | compressed_sparse_row_graph(edges_are_sorted_t, | |
981 | InputIterator edge_begin, InputIterator edge_end, | |
982 | EdgePropertyIterator ep_iter, | |
983 | vertices_size_type numverts, | |
984 | const ProcessGroup& pg, | |
985 | const Distribution& dist, | |
986 | const GraphProperty& prop) | |
987 | : m_process_group(pg), | |
988 | m_distribution(dist), | |
989 | m_base(edges_are_sorted_global, | |
990 | index_to_vertex_iterator<InputIterator, BOOST_DISTRIB_CSR_GRAPH_TYPE>(edge_begin, *this), | |
991 | index_to_vertex_iterator<InputIterator, BOOST_DISTRIB_CSR_GRAPH_TYPE>(edge_end, *this), | |
992 | ep_iter, | |
993 | get(vertex_local, *this), | |
994 | local_vertex<csr_vertex_owner_map<process_id_type, vertex_descriptor>, | |
995 | process_id_type> (get(vertex_owner, *this), process_id(pg)), | |
996 | m_distribution.block_size(process_id(m_process_group), numverts), | |
997 | prop) | |
998 | { } | |
999 | ||
1000 | template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS> | |
1001 | template<typename MultiPassInputIterator> | |
1002 | BOOST_DISTRIB_CSR_GRAPH_TYPE:: | |
1003 | compressed_sparse_row_graph(edges_are_unsorted_multi_pass_t, | |
1004 | MultiPassInputIterator edge_begin, | |
1005 | MultiPassInputIterator edge_end, | |
1006 | vertices_size_type numverts, | |
1007 | const ProcessGroup& pg, | |
1008 | const GraphProperty& prop) | |
1009 | : m_process_group(pg), | |
1010 | m_distribution(parallel::block(m_process_group, numverts)), | |
1011 | m_base(edges_are_unsorted_multi_pass_global, | |
1012 | make_index_to_vertex_iterator(edge_begin, parallel::block(m_process_group, numverts), *this), | |
1013 | make_index_to_vertex_iterator(edge_end, parallel::block(m_process_group, numverts), *this), | |
1014 | m_distribution.block_size(process_id(m_process_group), numverts), | |
1015 | get(vertex_local, *this), | |
1016 | local_vertex<csr_vertex_owner_map<process_id_type, vertex_descriptor>, | |
1017 | process_id_type> (get(vertex_owner, *this), process_id(pg)), | |
1018 | prop) | |
1019 | { } | |
1020 | ||
1021 | template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS> | |
1022 | template <typename MultiPassInputIterator, typename Distribution> | |
1023 | BOOST_DISTRIB_CSR_GRAPH_TYPE:: | |
1024 | compressed_sparse_row_graph(edges_are_unsorted_multi_pass_t, | |
1025 | MultiPassInputIterator edge_begin, | |
1026 | MultiPassInputIterator edge_end, | |
1027 | vertices_size_type numverts, | |
1028 | const ProcessGroup& pg, | |
1029 | const Distribution& dist, | |
1030 | const GraphProperty& prop) | |
1031 | : m_process_group(pg), | |
1032 | m_distribution(dist), | |
1033 | m_base(edges_are_unsorted_multi_pass_global, | |
1034 | make_index_to_vertex_iterator(edge_begin, parallel::block(m_process_group, numverts), *this), | |
1035 | make_index_to_vertex_iterator(edge_end, parallel::block(m_process_group, numverts), *this), | |
1036 | m_distribution.block_size(process_id(m_process_group), numverts), | |
1037 | get(vertex_local, *this), | |
1038 | local_vertex<csr_vertex_owner_map<process_id_type, vertex_descriptor>, | |
1039 | process_id_type> (get(vertex_owner, *this), process_id(pg)), | |
1040 | prop) | |
1041 | { } | |
1042 | ||
1043 | ||
1044 | template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS> | |
1045 | template<typename MultiPassInputIterator, typename EdgePropertyIterator> | |
1046 | BOOST_DISTRIB_CSR_GRAPH_TYPE:: | |
1047 | compressed_sparse_row_graph(edges_are_unsorted_multi_pass_t, | |
1048 | MultiPassInputIterator edge_begin, | |
1049 | MultiPassInputIterator edge_end, | |
1050 | EdgePropertyIterator ep_iter, | |
1051 | vertices_size_type numverts, | |
1052 | const ProcessGroup& pg, | |
1053 | const GraphProperty& prop) | |
1054 | : m_process_group(pg), | |
1055 | m_distribution(parallel::block(m_process_group, numverts)), | |
1056 | m_base(edges_are_unsorted_multi_pass_global, | |
1057 | make_index_to_vertex_iterator(edge_begin, parallel::block(m_process_group, numverts), *this), | |
1058 | make_index_to_vertex_iterator(edge_end, parallel::block(m_process_group, numverts), *this), | |
1059 | ep_iter, | |
1060 | m_distribution.block_size(process_id(m_process_group), numverts), | |
1061 | get(vertex_local, *this), | |
1062 | local_vertex<csr_vertex_owner_map<process_id_type, vertex_descriptor>, | |
1063 | process_id_type> (get(vertex_owner, *this), process_id(pg)), | |
1064 | prop) | |
1065 | { } | |
1066 | ||
1067 | template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS> | |
1068 | template <typename MultiPassInputIterator, typename EdgePropertyIterator, | |
1069 | typename Distribution> | |
1070 | BOOST_DISTRIB_CSR_GRAPH_TYPE:: | |
1071 | compressed_sparse_row_graph(edges_are_unsorted_multi_pass_t, | |
1072 | MultiPassInputIterator edge_begin, | |
1073 | MultiPassInputIterator edge_end, | |
1074 | EdgePropertyIterator ep_iter, | |
1075 | vertices_size_type numverts, | |
1076 | const ProcessGroup& pg, | |
1077 | const Distribution& dist, | |
1078 | const GraphProperty& prop) | |
1079 | : m_process_group(pg), | |
1080 | m_distribution(dist), | |
1081 | m_base(edges_are_unsorted_multi_pass_global, | |
1082 | make_index_to_vertex_iterator(edge_begin, parallel::block(m_process_group, numverts), *this), | |
1083 | make_index_to_vertex_iterator(edge_end, parallel::block(m_process_group, numverts), *this), | |
1084 | ep_iter, | |
1085 | m_distribution.block_size(process_id(m_process_group), numverts), | |
1086 | get(vertex_local, *this), | |
1087 | local_vertex<csr_vertex_owner_map<process_id_type, vertex_descriptor>, | |
1088 | process_id_type> (get(vertex_owner, *this), process_id(pg)), | |
1089 | prop) | |
1090 | { } | |
1091 | ||
1092 | template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS> | |
1093 | template<typename Source> | |
1094 | BOOST_DISTRIB_CSR_GRAPH_TYPE:: | |
1095 | compressed_sparse_row_graph(distributed_construct_inplace_from_sources_and_targets_t, | |
1096 | std::vector<Source>& sources, | |
1097 | std::vector<vertex_descriptor>& targets, | |
1098 | vertices_size_type numverts, | |
1099 | const ProcessGroup& pg, | |
1100 | const GraphProperty& prop) | |
1101 | : m_process_group(pg), | |
1102 | m_distribution(parallel::block(m_process_group, numverts)), | |
1103 | m_base(m_distribution.block_size(process_id(m_process_group), numverts)) | |
1104 | { | |
1105 | // Convert linear indices to global indices | |
1106 | for (edges_size_type i = 0; i < sources.size(); ++i) { | |
1107 | sources[i] = m_distribution.local(sources[i]); | |
1108 | targets[i] = make_vertex_descriptor(m_distribution(targets[i]), | |
1109 | m_distribution.local(targets[i])); | |
1110 | } | |
1111 | ||
1112 | m_base.assign_sources_and_targets_global( | |
1113 | sources, targets, m_distribution.block_size(process_id(m_process_group), numverts), | |
1114 | identity_property_map()); | |
1115 | ||
1116 | // TODO: set property on m_base? | |
1117 | } | |
1118 | ||
1119 | template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS> | |
1120 | template <typename Distribution, typename Source> | |
1121 | BOOST_DISTRIB_CSR_GRAPH_TYPE:: | |
1122 | compressed_sparse_row_graph(distributed_construct_inplace_from_sources_and_targets_t, | |
1123 | std::vector<Source>& sources, | |
1124 | std::vector<vertex_descriptor>& targets, | |
1125 | vertices_size_type numverts, | |
1126 | const ProcessGroup& pg, | |
1127 | const Distribution& dist, | |
1128 | const GraphProperty& prop) | |
1129 | : m_process_group(pg), | |
1130 | m_distribution(dist), | |
1131 | m_base(m_distribution.block_size(process_id(m_process_group), numverts)) | |
1132 | { | |
1133 | // Convert linear indices to global indices | |
1134 | for (edges_size_type i = 0; i < sources.size(); ++i) { | |
1135 | sources[i] = m_distribution.local(sources[i]); | |
1136 | targets[i] = make_vertex_descriptor(m_distribution(targets[i]), | |
1137 | m_distribution.local(targets[i])); | |
1138 | } | |
1139 | ||
1140 | m_base.assign_sources_and_targets_global( | |
1141 | sources, targets, m_distribution.block_size(process_id(m_process_group), numverts), | |
1142 | identity_property_map()); | |
1143 | ||
1144 | // TODO: set property on m_base? | |
1145 | } | |
1146 | ||
1147 | template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS> | |
1148 | template<typename Source> | |
1149 | BOOST_DISTRIB_CSR_GRAPH_TYPE:: | |
1150 | compressed_sparse_row_graph(distributed_construct_inplace_from_sources_and_targets_t, | |
1151 | std::vector<Source>& sources, | |
1152 | std::vector<vertex_descriptor>& targets, | |
1153 | std::vector<edge_bundled>& edge_props, | |
1154 | vertices_size_type numverts, | |
1155 | const ProcessGroup& pg, | |
1156 | const GraphProperty& prop) | |
1157 | : m_process_group(pg), | |
1158 | m_distribution(parallel::block(m_process_group, numverts)), | |
1159 | m_base(m_distribution.block_size(process_id(m_process_group), numverts)) | |
1160 | { | |
1161 | // Convert linear indices to global indices | |
1162 | for (edges_size_type i = 0; i < sources.size(); ++i) { | |
1163 | sources[i] = m_distribution.local(sources[i]); | |
1164 | targets[i] = make_vertex_descriptor(m_distribution(targets[i]), | |
1165 | m_distribution.local(targets[i])); | |
1166 | } | |
1167 | ||
1168 | m_base.assign_sources_and_targets_global( | |
1169 | sources, targets, edge_props, | |
1170 | m_distribution.block_size(process_id(m_process_group), numverts), | |
1171 | identity_property_map()); | |
1172 | ||
1173 | // TODO: set property on m_base? | |
1174 | } | |
1175 | ||
1176 | template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS> | |
1177 | template <typename Distribution, typename Source> | |
1178 | BOOST_DISTRIB_CSR_GRAPH_TYPE:: | |
1179 | compressed_sparse_row_graph(distributed_construct_inplace_from_sources_and_targets_t, | |
1180 | std::vector<Source>& sources, | |
1181 | std::vector<vertex_descriptor>& targets, | |
1182 | std::vector<edge_bundled>& edge_props, | |
1183 | vertices_size_type numverts, | |
1184 | const ProcessGroup& pg, | |
1185 | const Distribution& dist, | |
1186 | const GraphProperty& prop) | |
1187 | : m_process_group(pg), | |
1188 | m_distribution(dist), | |
1189 | m_base(m_distribution.block_size(process_id(m_process_group), numverts)) | |
1190 | { | |
1191 | // Convert linear indices to global indices | |
1192 | for (edges_size_type i = 0; i < sources.size(); ++i) { | |
1193 | sources[i] = m_distribution.local(sources[i]); | |
1194 | targets[i] = make_vertex_descriptor(m_distribution(targets[i]), | |
1195 | m_distribution.local(targets[i])); | |
1196 | } | |
1197 | ||
1198 | m_base.assign_sources_and_targets_global( | |
1199 | sources, targets, edge_props, | |
1200 | m_distribution.block_size(process_id(m_process_group), numverts), | |
1201 | identity_property_map()); | |
1202 | ||
1203 | // TODO: set property on m_base? | |
1204 | } | |
1205 | ||
1206 | // | |
1207 | // Old (untagged) ctors, these default to the unsorted sequential ctors | |
1208 | // | |
1209 | template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS> | |
1210 | template<typename InputIterator> | |
1211 | BOOST_DISTRIB_CSR_GRAPH_TYPE:: | |
1212 | compressed_sparse_row_graph(InputIterator edge_begin, InputIterator edge_end, | |
1213 | vertices_size_type numverts, | |
1214 | const ProcessGroup& pg, | |
1215 | const GraphProperty& prop) | |
1216 | : m_process_group(pg), | |
1217 | m_distribution(parallel::block(m_process_group, numverts)), | |
1218 | m_base(edges_are_unsorted_global, | |
1219 | index_to_vertex_iterator<InputIterator, BOOST_DISTRIB_CSR_GRAPH_TYPE>(edge_begin, *this), | |
1220 | index_to_vertex_iterator<InputIterator, BOOST_DISTRIB_CSR_GRAPH_TYPE>(edge_end, *this), | |
1221 | m_distribution.block_size(process_id(m_process_group), numverts), | |
1222 | get(vertex_local, *this), | |
1223 | local_vertex<csr_vertex_owner_map<process_id_type, vertex_descriptor>, | |
1224 | process_id_type> (get(vertex_owner, *this), process_id(pg)), | |
1225 | prop) | |
1226 | ||
1227 | { | |
1228 | } | |
1229 | ||
1230 | template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS> | |
1231 | template<typename InputIterator, typename EdgePropertyIterator> | |
1232 | BOOST_DISTRIB_CSR_GRAPH_TYPE:: | |
1233 | compressed_sparse_row_graph(InputIterator edge_begin, InputIterator edge_end, | |
1234 | EdgePropertyIterator ep_iter, | |
1235 | vertices_size_type numverts, | |
1236 | const ProcessGroup& pg, | |
1237 | const GraphProperty& prop) | |
1238 | : m_process_group(pg), | |
1239 | ||
1240 | m_distribution(parallel::block(m_process_group, numverts)), | |
1241 | m_base(edges_are_unsorted_global, | |
1242 | index_to_vertex_iterator<InputIterator, BOOST_DISTRIB_CSR_GRAPH_TYPE>(edge_begin, *this), | |
1243 | index_to_vertex_iterator<InputIterator, BOOST_DISTRIB_CSR_GRAPH_TYPE>(edge_end, *this), | |
1244 | ep_iter, | |
1245 | m_distribution.block_size(process_id(m_process_group), numverts), | |
1246 | get(vertex_local, *this), | |
1247 | local_vertex<csr_vertex_owner_map<process_id_type, vertex_descriptor>, | |
1248 | process_id_type> (get(vertex_owner, *this), process_id(pg)), | |
1249 | prop) | |
1250 | { | |
1251 | } | |
1252 | ||
1253 | template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS> | |
1254 | template<typename InputIterator, typename Distribution> | |
1255 | BOOST_DISTRIB_CSR_GRAPH_TYPE:: | |
1256 | compressed_sparse_row_graph(InputIterator edge_begin, InputIterator edge_end, | |
1257 | vertices_size_type numverts, | |
1258 | const ProcessGroup& pg, | |
1259 | const Distribution& dist, | |
1260 | const GraphProperty& prop) | |
1261 | : m_process_group(pg), | |
1262 | m_distribution(dist), | |
1263 | m_base(edges_are_unsorted_global, | |
1264 | index_to_vertex_iterator<InputIterator, BOOST_DISTRIB_CSR_GRAPH_TYPE>(edge_begin, *this), | |
1265 | index_to_vertex_iterator<InputIterator, BOOST_DISTRIB_CSR_GRAPH_TYPE>(edge_end, *this), | |
1266 | m_distribution.block_size(process_id(m_process_group), numverts), | |
1267 | get(vertex_local, *this), | |
1268 | local_vertex<csr_vertex_owner_map<process_id_type, vertex_descriptor>, | |
1269 | process_id_type> (get(vertex_owner, *this), process_id(pg)), | |
1270 | prop) | |
1271 | { | |
1272 | } | |
1273 | ||
1274 | template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS> | |
1275 | template<typename InputIterator, typename EdgePropertyIterator, | |
1276 | typename Distribution> | |
1277 | BOOST_DISTRIB_CSR_GRAPH_TYPE:: | |
1278 | compressed_sparse_row_graph(InputIterator edge_begin, InputIterator edge_end, | |
1279 | EdgePropertyIterator ep_iter, | |
1280 | vertices_size_type numverts, | |
1281 | const ProcessGroup& pg, | |
1282 | const Distribution& dist, | |
1283 | const GraphProperty& prop) | |
1284 | : m_process_group(pg), | |
1285 | m_distribution(dist), | |
1286 | m_base(edges_are_unsorted_global, | |
1287 | index_to_vertex_iterator<InputIterator, BOOST_DISTRIB_CSR_GRAPH_TYPE>(edge_begin, *this), | |
1288 | index_to_vertex_iterator<InputIterator, BOOST_DISTRIB_CSR_GRAPH_TYPE>(edge_end, *this), | |
1289 | m_distribution.block_size(process_id(m_process_group), numverts), | |
1290 | get(vertex_local, *this), | |
1291 | local_vertex<csr_vertex_owner_map<process_id_type, vertex_descriptor>, | |
1292 | process_id_type> (get(vertex_owner, *this), process_id(pg)), | |
1293 | prop) | |
1294 | { | |
1295 | } | |
1296 | ||
1297 | // ----------------------------------------------------------------- | |
1298 | // Vertex Global Property Map | |
1299 | template<typename ProcessID, typename Key> | |
1300 | class csr_vertex_global_map | |
1301 | { | |
1302 | public: | |
1303 | // ----------------------------------------------------------------- | |
1304 | // Readable Property Map concept requirements | |
1305 | typedef std::pair<ProcessID, Key> value_type; | |
1306 | typedef value_type reference; | |
1307 | typedef Key key_type; | |
1308 | typedef readable_property_map_tag category; | |
1309 | }; | |
1310 | ||
1311 | template<typename ProcessID, typename Key> | |
1312 | inline std::pair<ProcessID, Key> | |
1313 | get(csr_vertex_global_map<ProcessID, Key>, | |
1314 | typename csr_vertex_global_map<ProcessID, Key>::key_type k) | |
1315 | { | |
1316 | const int local_index_bits = sizeof(Key) * CHAR_BIT - processor_bits; | |
1317 | const Key local_index_mask = Key(-1) >> processor_bits; | |
1318 | ||
1319 | return std::pair<ProcessID, Key>(k >> local_index_bits, | |
1320 | k & local_index_mask); | |
1321 | } | |
1322 | ||
1323 | template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS> | |
1324 | class property_map<BOOST_DISTRIB_CSR_GRAPH_TYPE, vertex_global_t> | |
1325 | { | |
1326 | public: | |
1327 | typedef csr_vertex_global_map< | |
1328 | typename ProcessGroup::process_id_type, | |
1329 | typename BOOST_DISTRIB_CSR_GRAPH_TYPE::vertex_descriptor> type; | |
1330 | typedef type const_type; | |
1331 | }; | |
1332 | ||
1333 | template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS> | |
1334 | inline | |
1335 | typename property_map<BOOST_DISTRIB_CSR_GRAPH_TYPE, vertex_global_t>::type | |
1336 | get(vertex_global_t, BOOST_DISTRIB_CSR_GRAPH_TYPE& g) | |
1337 | { | |
1338 | typedef typename property_map<BOOST_DISTRIB_CSR_GRAPH_TYPE, vertex_global_t> | |
1339 | ::type result_type; | |
1340 | return result_type(); | |
1341 | } | |
1342 | ||
1343 | template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS> | |
1344 | inline | |
1345 | std::pair<typename ProcessGroup::process_id_type, | |
1346 | typename BOOST_DISTRIB_CSR_GRAPH_TYPE::vertex_descriptor> | |
1347 | get(vertex_global_t, BOOST_DISTRIB_CSR_GRAPH_TYPE& g, | |
1348 | typename BOOST_DISTRIB_CSR_GRAPH_TYPE::vertex_descriptor k) | |
1349 | { | |
1350 | return get(vertex_global, | |
1351 | const_cast<const BOOST_DISTRIB_CSR_GRAPH_TYPE&>(g), | |
1352 | k); | |
1353 | } | |
1354 | ||
1355 | template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS> | |
1356 | inline | |
1357 | typename property_map<BOOST_DISTRIB_CSR_GRAPH_TYPE, vertex_global_t>::const_type | |
1358 | get(vertex_global_t, const BOOST_DISTRIB_CSR_GRAPH_TYPE& g) | |
1359 | { | |
1360 | typedef typename property_map<BOOST_DISTRIB_CSR_GRAPH_TYPE, vertex_global_t> | |
1361 | ::const_type result_type; | |
1362 | return result_type(); | |
1363 | } | |
1364 | ||
1365 | template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS> | |
1366 | inline | |
1367 | std::pair<typename ProcessGroup::process_id_type, | |
1368 | typename BOOST_DISTRIB_CSR_GRAPH_TYPE::vertex_descriptor> | |
1369 | get(vertex_global_t, const BOOST_DISTRIB_CSR_GRAPH_TYPE& g, | |
1370 | typename BOOST_DISTRIB_CSR_GRAPH_TYPE::vertex_descriptor k) | |
1371 | { | |
1372 | typedef typename BOOST_DISTRIB_CSR_GRAPH_TYPE::vertex_descriptor | |
1373 | vertex_descriptor; | |
1374 | typedef std::pair<typename ProcessGroup::process_id_type, vertex_descriptor> | |
1375 | result_type; | |
1376 | const int local_index_bits = | |
1377 | sizeof(vertex_descriptor) * CHAR_BIT - processor_bits; | |
1378 | const vertex_descriptor local_index_mask = | |
1379 | vertex_descriptor(-1) >> processor_bits; | |
1380 | ||
1381 | return result_type(k >> local_index_bits, k & local_index_mask); | |
1382 | } | |
1383 | ||
1384 | // ----------------------------------------------------------------- | |
1385 | // Extra, common functions | |
1386 | template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS> | |
1387 | inline typename BOOST_DISTRIB_CSR_GRAPH_TYPE::vertex_descriptor | |
1388 | vertex(typename BOOST_DISTRIB_CSR_GRAPH_TYPE::vertices_size_type i, | |
1389 | const BOOST_DISTRIB_CSR_GRAPH_TYPE& g) | |
1390 | { | |
1391 | return g.make_vertex_descriptor(g.distribution()(i), | |
1392 | g.distribution().local(i)); | |
1393 | } | |
1394 | ||
1395 | // Unlike for an adjacency_matrix, edge_range and edge take lg(out_degree(i)) | |
1396 | // time | |
1397 | template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS> | |
1398 | inline std::pair<typename BOOST_DISTRIB_CSR_GRAPH_TYPE::out_edge_iterator, | |
1399 | typename BOOST_DISTRIB_CSR_GRAPH_TYPE::out_edge_iterator> | |
1400 | edge_range(typename BOOST_DISTRIB_CSR_GRAPH_TYPE::vertex_descriptor i, | |
1401 | typename BOOST_DISTRIB_CSR_GRAPH_TYPE::vertex_descriptor j, | |
1402 | const BOOST_DISTRIB_CSR_GRAPH_TYPE& g) | |
1403 | { | |
1404 | typedef typename BOOST_DISTRIB_CSR_GRAPH_TYPE::vertex_descriptor Vertex; | |
1405 | typedef typename BOOST_DISTRIB_CSR_GRAPH_TYPE::edges_size_type EdgeIndex; | |
1406 | typedef typename std::vector<Vertex>::const_iterator adj_iter; | |
1407 | typedef typename BOOST_DISTRIB_CSR_GRAPH_TYPE::out_edge_iterator out_edge_iter; | |
1408 | typedef typename BOOST_DISTRIB_CSR_GRAPH_TYPE::edge_descriptor edge_desc; | |
1409 | std::pair<adj_iter, adj_iter> raw_adjacencies = adjacent_vertices(i, g); | |
1410 | std::pair<adj_iter, adj_iter> adjacencies = | |
1411 | std::equal_range(raw_adjacencies.first, raw_adjacencies.second, j); | |
1412 | EdgeIndex idx_begin = adjacencies.first - g.base().m_forward.m_column.begin(); | |
1413 | EdgeIndex idx_end = adjacencies.second - g.base().m_forward.m_column.begin(); | |
1414 | return std::make_pair(out_edge_iter(edge_desc(i, idx_begin)), | |
1415 | out_edge_iter(edge_desc(i, idx_end))); | |
1416 | } | |
1417 | ||
1418 | template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS> | |
1419 | inline std::pair<typename BOOST_DISTRIB_CSR_GRAPH_TYPE::edge_descriptor, bool> | |
1420 | edge(typename BOOST_DISTRIB_CSR_GRAPH_TYPE::vertex_descriptor i, | |
1421 | typename BOOST_DISTRIB_CSR_GRAPH_TYPE::vertex_descriptor j, | |
1422 | const BOOST_DISTRIB_CSR_GRAPH_TYPE& g) | |
1423 | { | |
1424 | typedef typename BOOST_DISTRIB_CSR_GRAPH_TYPE::out_edge_iterator out_edge_iter; | |
1425 | std::pair<out_edge_iter, out_edge_iter> range = edge_range(i, j, g); | |
1426 | if (range.first == range.second) | |
1427 | return std::make_pair(typename BOOST_DISTRIB_CSR_GRAPH_TYPE::edge_descriptor(), | |
1428 | false); | |
1429 | else | |
1430 | return std::make_pair(*range.first, true); | |
1431 | } | |
1432 | ||
1433 | // A helper that turns requests for property maps for const graphs | |
1434 | // into property maps for non-const graphs. | |
1435 | template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS, typename Property> | |
1436 | class property_map<const BOOST_DISTRIB_CSR_GRAPH_TYPE, Property> | |
1437 | { | |
1438 | public: | |
1439 | typedef typename property_map<BOOST_DISTRIB_CSR_GRAPH_TYPE, Property> | |
1440 | ::const_type type; | |
1441 | typedef type const_type; | |
1442 | }; | |
1443 | ||
1444 | // ----------------------------------------------------------------- | |
1445 | // Structural modifiers | |
1446 | ||
1447 | #if 0 | |
1448 | template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS> | |
1449 | typename BOOST_DISTRIB_CSR_GRAPH_TYPE::vertex_descriptor | |
1450 | add_vertex(BOOST_DISTRIB_CSR_GRAPH_TYPE& g) | |
1451 | { return g.add_vertex(); } | |
1452 | ||
1453 | template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS> | |
1454 | typename BOOST_DISTRIB_CSR_GRAPH_TYPE::vertex_descriptor | |
1455 | add_vertex(const typename BOOST_DISTRIB_CSR_GRAPH_TYPE::vertex_bundled& p, | |
1456 | BOOST_DISTRIB_CSR_GRAPH_TYPE& g) | |
1457 | { return g.add_vertex(p); } | |
1458 | ||
1459 | template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS> | |
1460 | typename BOOST_DISTRIB_CSR_GRAPH_TYPE::vertex_descriptor | |
1461 | add_vertices(typename BOOST_DISTRIB_CSR_GRAPH_TYPE::vertices_size_type count, | |
1462 | BOOST_DISTRIB_CSR_GRAPH_TYPE& g) | |
1463 | { return g.add_vertices(count); } | |
1464 | ||
1465 | template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS, typename InputIterator> | |
1466 | void | |
1467 | add_edges(InputIterator first, InputIterator last, | |
1468 | BOOST_DISTRIB_CSR_GRAPH_TYPE& g) | |
1469 | { g.add_edges(first, last); } | |
1470 | ||
1471 | template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS, typename InputIterator, | |
1472 | typename EdgePropertyIterator> | |
1473 | void | |
1474 | add_edges(InputIterator first, InputIterator last, | |
1475 | EdgePropertyIterator ep_iter, | |
1476 | EdgePropertyIterator ep_iter_end, | |
1477 | BOOST_DISTRIB_CSR_GRAPH_TYPE& g) | |
1478 | { return g.add_edges(first, last, ep_iter, ep_iter_end); } | |
1479 | ||
1480 | template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS, typename InputIterator> | |
1481 | void | |
1482 | add_edges_sorted(InputIterator first, InputIterator last, | |
1483 | BOOST_DISTRIB_CSR_GRAPH_TYPE& g) | |
1484 | { return g.add_edges_sorted(first, last); } | |
1485 | ||
1486 | template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS, typename InputIterator, | |
1487 | typename EdgePropertyIterator> | |
1488 | void | |
1489 | add_edges_sorted(InputIterator first_sorted, InputIterator last_sorted, | |
1490 | EdgePropertyIterator ep_iter_sorted, | |
1491 | BOOST_DISTRIB_CSR_GRAPH_TYPE& g) | |
1492 | { g.add_edges_sorted(first_sorted, last_sorted, ep_iter_sorted); } | |
1493 | #endif | |
1494 | ||
1495 | // ----------------------------------------------------------------- | |
1496 | // Vertex Owner Property Map | |
1497 | template<typename ProcessID, typename Key> | |
1498 | class csr_vertex_owner_map | |
1499 | { | |
1500 | public: | |
1501 | // ----------------------------------------------------------------- | |
1502 | // Readable Property Map concept requirements | |
1503 | typedef ProcessID value_type; | |
1504 | typedef value_type reference; | |
1505 | typedef Key key_type; | |
1506 | typedef readable_property_map_tag category; | |
1507 | }; | |
1508 | ||
1509 | template<typename ProcessID, typename Key> | |
1510 | inline ProcessID | |
1511 | get(csr_vertex_owner_map<ProcessID, Key> pm, | |
1512 | typename csr_vertex_owner_map<ProcessID, Key>::key_type k) | |
1513 | { | |
1514 | const int local_index_bits = sizeof(Key) * CHAR_BIT - processor_bits; | |
1515 | return k >> local_index_bits; | |
1516 | } | |
1517 | ||
1518 | template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS> | |
1519 | class property_map<BOOST_DISTRIB_CSR_GRAPH_TYPE, vertex_owner_t> | |
1520 | { | |
1521 | public: | |
1522 | typedef csr_vertex_owner_map< | |
1523 | typename ProcessGroup::process_id_type, | |
1524 | typename BOOST_DISTRIB_CSR_GRAPH_TYPE::vertex_descriptor> type; | |
1525 | typedef type const_type; | |
1526 | }; | |
1527 | ||
1528 | template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS> | |
1529 | inline | |
1530 | typename property_map<BOOST_DISTRIB_CSR_GRAPH_TYPE, vertex_owner_t>::type | |
1531 | get(vertex_owner_t, BOOST_DISTRIB_CSR_GRAPH_TYPE& g) | |
1532 | { | |
1533 | typedef typename property_map<BOOST_DISTRIB_CSR_GRAPH_TYPE, vertex_owner_t> | |
1534 | ::type result_type; | |
1535 | return result_type(); | |
1536 | } | |
1537 | ||
1538 | template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS> | |
1539 | inline typename ProcessGroup::process_id_type | |
1540 | get(vertex_owner_t, BOOST_DISTRIB_CSR_GRAPH_TYPE& g, | |
1541 | typename BOOST_DISTRIB_CSR_GRAPH_TYPE::vertex_descriptor k) | |
1542 | { | |
1543 | return get(vertex_owner, | |
1544 | const_cast<const BOOST_DISTRIB_CSR_GRAPH_TYPE&>(g), | |
1545 | k); | |
1546 | } | |
1547 | ||
1548 | template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS> | |
1549 | inline | |
1550 | typename property_map<BOOST_DISTRIB_CSR_GRAPH_TYPE, vertex_owner_t>::const_type | |
1551 | get(vertex_owner_t, const BOOST_DISTRIB_CSR_GRAPH_TYPE& g) | |
1552 | { | |
1553 | typedef typename property_map<BOOST_DISTRIB_CSR_GRAPH_TYPE, vertex_owner_t> | |
1554 | ::const_type result_type; | |
1555 | return result_type(); | |
1556 | } | |
1557 | ||
1558 | template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS> | |
1559 | inline typename ProcessGroup::process_id_type | |
1560 | get(vertex_owner_t, const BOOST_DISTRIB_CSR_GRAPH_TYPE& g, | |
1561 | typename BOOST_DISTRIB_CSR_GRAPH_TYPE::vertex_descriptor k) | |
1562 | { | |
1563 | typedef typename BOOST_DISTRIB_CSR_GRAPH_TYPE::vertex_descriptor | |
1564 | vertex_descriptor; | |
1565 | const int local_index_bits = | |
1566 | sizeof(vertex_descriptor) * CHAR_BIT - processor_bits; | |
1567 | return k >> local_index_bits; | |
1568 | } | |
1569 | ||
1570 | // ----------------------------------------------------------------- | |
1571 | // Vertex Local Property Map | |
1572 | template<typename Key> | |
1573 | class csr_vertex_local_map | |
1574 | { | |
1575 | public: | |
1576 | // ----------------------------------------------------------------- | |
1577 | // Readable Property Map concept requirements | |
1578 | typedef Key value_type; | |
1579 | typedef value_type reference; | |
1580 | typedef Key key_type; | |
1581 | typedef readable_property_map_tag category; | |
1582 | }; | |
1583 | ||
1584 | template<typename Key> | |
1585 | inline Key | |
1586 | get(csr_vertex_local_map<Key> pm, | |
1587 | typename csr_vertex_local_map<Key>::key_type k) | |
1588 | { | |
1589 | const Key local_index_mask = Key(-1) >> processor_bits; | |
1590 | return k & local_index_mask; | |
1591 | } | |
1592 | ||
1593 | template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS> | |
1594 | class property_map<BOOST_DISTRIB_CSR_GRAPH_TYPE, vertex_local_t> | |
1595 | { | |
1596 | public: | |
1597 | typedef csr_vertex_local_map< | |
1598 | typename BOOST_DISTRIB_CSR_GRAPH_TYPE::vertex_descriptor> type; | |
1599 | typedef type const_type; | |
1600 | }; | |
1601 | ||
1602 | template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS> | |
1603 | inline | |
1604 | typename property_map<BOOST_DISTRIB_CSR_GRAPH_TYPE, vertex_local_t>::type | |
1605 | get(vertex_local_t, BOOST_DISTRIB_CSR_GRAPH_TYPE& g) | |
1606 | { | |
1607 | typedef typename property_map<BOOST_DISTRIB_CSR_GRAPH_TYPE, vertex_local_t> | |
1608 | ::type result_type; | |
1609 | return result_type(); | |
1610 | } | |
1611 | ||
1612 | template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS> | |
1613 | inline typename BOOST_DISTRIB_CSR_GRAPH_TYPE::vertex_descriptor | |
1614 | get(vertex_local_t, BOOST_DISTRIB_CSR_GRAPH_TYPE& g, | |
1615 | typename BOOST_DISTRIB_CSR_GRAPH_TYPE::vertex_descriptor k) | |
1616 | { | |
1617 | return get(vertex_local, | |
1618 | const_cast<const BOOST_DISTRIB_CSR_GRAPH_TYPE&>(g), | |
1619 | k); | |
1620 | } | |
1621 | ||
1622 | template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS> | |
1623 | inline | |
1624 | typename property_map<BOOST_DISTRIB_CSR_GRAPH_TYPE, vertex_local_t>::const_type | |
1625 | get(vertex_local_t, const BOOST_DISTRIB_CSR_GRAPH_TYPE& g) | |
1626 | { | |
1627 | typedef typename property_map<BOOST_DISTRIB_CSR_GRAPH_TYPE, vertex_local_t> | |
1628 | ::const_type result_type; | |
1629 | return result_type(); | |
1630 | } | |
1631 | ||
1632 | template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS> | |
1633 | inline typename BOOST_DISTRIB_CSR_GRAPH_TYPE::vertex_descriptor | |
1634 | get(vertex_local_t, const BOOST_DISTRIB_CSR_GRAPH_TYPE& g, | |
1635 | typename BOOST_DISTRIB_CSR_GRAPH_TYPE::vertex_descriptor k) | |
1636 | { | |
1637 | typedef typename BOOST_DISTRIB_CSR_GRAPH_TYPE::vertex_descriptor | |
1638 | vertex_descriptor; | |
1639 | const vertex_descriptor local_index_mask = | |
1640 | vertex_descriptor(-1) >> processor_bits; | |
1641 | return k & local_index_mask; | |
1642 | } | |
1643 | ||
1644 | // ----------------------------------------------------------------- | |
1645 | // Vertex Index Property Map | |
1646 | template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS> | |
1647 | class property_map<BOOST_DISTRIB_CSR_GRAPH_TYPE, vertex_index_t> | |
1648 | { | |
1649 | typedef typename property_map<BOOST_DISTRIB_CSR_GRAPH_TYPE, | |
1650 | vertex_global_t>::const_type | |
1651 | global_map; | |
1652 | typedef typename BOOST_DISTRIB_CSR_GRAPH_TYPE::process_group_type | |
1653 | process_group_type; | |
1654 | ||
1655 | typedef property_map<BOOST_DISTRIB_CSR_GRAPH_TYPE, vertex_local_t> local; | |
1656 | ||
1657 | public: | |
1658 | typedef local_property_map<process_group_type, | |
1659 | global_map, | |
1660 | typename local::type> type; | |
1661 | typedef local_property_map<process_group_type, | |
1662 | global_map, | |
1663 | typename local::const_type> const_type; | |
1664 | }; | |
1665 | ||
1666 | template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS> | |
1667 | inline | |
1668 | typename property_map<BOOST_DISTRIB_CSR_GRAPH_TYPE, vertex_index_t>::type | |
1669 | get(vertex_index_t, BOOST_DISTRIB_CSR_GRAPH_TYPE& g) | |
1670 | { | |
1671 | typedef typename property_map<BOOST_DISTRIB_CSR_GRAPH_TYPE, vertex_index_t> | |
1672 | ::type result_type; | |
1673 | ||
1674 | return result_type(g.process_group(), get(vertex_global, g), | |
1675 | get(vertex_local, g)); | |
1676 | } | |
1677 | ||
1678 | template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS> | |
1679 | inline typename BOOST_DISTRIB_CSR_GRAPH_TYPE::vertices_size_type | |
1680 | get(vertex_index_t, BOOST_DISTRIB_CSR_GRAPH_TYPE& g, | |
1681 | typename BOOST_DISTRIB_CSR_GRAPH_TYPE::vertex_descriptor k) | |
1682 | { | |
1683 | return get(vertex_local, g, k); | |
1684 | } | |
1685 | ||
1686 | template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS> | |
1687 | inline | |
1688 | typename property_map<BOOST_DISTRIB_CSR_GRAPH_TYPE, vertex_index_t>::const_type | |
1689 | get(vertex_index_t, const BOOST_DISTRIB_CSR_GRAPH_TYPE& g) | |
1690 | { | |
1691 | typedef typename property_map<BOOST_DISTRIB_CSR_GRAPH_TYPE, vertex_index_t> | |
1692 | ::const_type result_type; | |
1693 | return result_type(g.process_group(), get(vertex_global, g), | |
1694 | get(vertex_local, g)); | |
1695 | } | |
1696 | ||
1697 | template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS> | |
1698 | inline typename BOOST_DISTRIB_CSR_GRAPH_TYPE::vertices_size_type | |
1699 | get(vertex_index_t, const BOOST_DISTRIB_CSR_GRAPH_TYPE& g, | |
1700 | typename BOOST_DISTRIB_CSR_GRAPH_TYPE::vertex_descriptor k) | |
1701 | { | |
1702 | return get(vertex_local, g, k); | |
1703 | } | |
1704 | ||
1705 | // ----------------------------------------------------------------- | |
1706 | // Vertex Local Index Property Map | |
1707 | template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS> | |
1708 | class property_map<BOOST_DISTRIB_CSR_GRAPH_TYPE, vertex_local_index_t> | |
1709 | : public property_map<BOOST_DISTRIB_CSR_GRAPH_TYPE, vertex_local_t> { }; | |
1710 | ||
1711 | template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS> | |
1712 | inline | |
1713 | typename property_map<BOOST_DISTRIB_CSR_GRAPH_TYPE, vertex_local_index_t>::type | |
1714 | get(vertex_local_index_t, BOOST_DISTRIB_CSR_GRAPH_TYPE& g) | |
1715 | { | |
1716 | return get(vertex_local, g); | |
1717 | } | |
1718 | ||
1719 | template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS> | |
1720 | inline typename BOOST_DISTRIB_CSR_GRAPH_TYPE::vertices_size_type | |
1721 | get(vertex_local_index_t, BOOST_DISTRIB_CSR_GRAPH_TYPE& g, | |
1722 | typename BOOST_DISTRIB_CSR_GRAPH_TYPE::vertex_descriptor k) | |
1723 | { | |
1724 | return get(vertex_local, g, k); | |
1725 | } | |
1726 | ||
1727 | template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS> | |
1728 | inline | |
1729 | typename property_map<BOOST_DISTRIB_CSR_GRAPH_TYPE, vertex_local_index_t>::const_type | |
1730 | get(vertex_local_index_t, const BOOST_DISTRIB_CSR_GRAPH_TYPE& g) | |
1731 | { | |
1732 | return get(vertex_local, g); | |
1733 | } | |
1734 | ||
1735 | template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS> | |
1736 | inline typename BOOST_DISTRIB_CSR_GRAPH_TYPE::vertices_size_type | |
1737 | get(vertex_local_index_t, const BOOST_DISTRIB_CSR_GRAPH_TYPE& g, | |
1738 | typename BOOST_DISTRIB_CSR_GRAPH_TYPE::vertex_descriptor k) | |
1739 | { | |
1740 | return get(vertex_local, g, k); | |
1741 | } | |
1742 | ||
1743 | // ----------------------------------------------------------------- | |
1744 | // Edge Global Property Map | |
1745 | template<typename ProcessID, typename Vertex, typename EdgeIndex> | |
1746 | class csr_edge_global_map | |
1747 | { | |
1748 | public: | |
1749 | // ----------------------------------------------------------------- | |
1750 | // Readable Property Map concept requirements | |
1751 | typedef detail::csr_edge_descriptor<Vertex, EdgeIndex> key_type; | |
1752 | typedef std::pair<ProcessID, detail::csr_edge_descriptor<Vertex, EdgeIndex> > value_type; | |
1753 | typedef value_type reference; | |
1754 | typedef readable_property_map_tag category; | |
1755 | }; | |
1756 | ||
1757 | template<typename ProcessID, typename Vertex, typename EdgeIndex> | |
1758 | inline std::pair<ProcessID, detail::csr_edge_descriptor<Vertex, EdgeIndex> > | |
1759 | get(csr_edge_global_map<ProcessID, Vertex, EdgeIndex> pm, | |
1760 | typename csr_edge_global_map<ProcessID, Vertex, EdgeIndex>::key_type k) | |
1761 | { | |
1762 | const int local_index_bits = sizeof(Vertex) * CHAR_BIT - processor_bits; | |
1763 | const Vertex local_index_mask = Vertex(-1) >> processor_bits; | |
1764 | return std::pair<ProcessID, detail::csr_edge_descriptor<Vertex, EdgeIndex> > | |
1765 | ((k.src >> local_index_bits), | |
1766 | detail::csr_edge_descriptor<Vertex, EdgeIndex>(k.src & local_index_mask, k.idx)); | |
1767 | } | |
1768 | ||
1769 | template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS> | |
1770 | class property_map<BOOST_DISTRIB_CSR_GRAPH_TYPE, edge_global_t> | |
1771 | { | |
1772 | public: | |
1773 | typedef csr_edge_global_map< | |
1774 | typename ProcessGroup::process_id_type, | |
1775 | typename BOOST_DISTRIB_CSR_GRAPH_TYPE::vertex_descriptor, | |
1776 | typename BOOST_DISTRIB_CSR_GRAPH_TYPE::edges_size_type> type; | |
1777 | typedef type const_type; | |
1778 | }; | |
1779 | ||
1780 | template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS> | |
1781 | inline | |
1782 | typename property_map<BOOST_DISTRIB_CSR_GRAPH_TYPE, edge_global_t>::type | |
1783 | get(edge_global_t, BOOST_DISTRIB_CSR_GRAPH_TYPE& g) | |
1784 | { | |
1785 | typedef typename property_map<BOOST_DISTRIB_CSR_GRAPH_TYPE, edge_global_t> | |
1786 | ::type result_type; | |
1787 | return result_type(); | |
1788 | } | |
1789 | ||
1790 | template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS> | |
1791 | inline | |
1792 | std::pair<typename ProcessGroup::process_id_type, | |
1793 | typename BOOST_DISTRIB_CSR_GRAPH_TYPE::base_type::edge_descriptor> | |
1794 | get(edge_global_t, BOOST_DISTRIB_CSR_GRAPH_TYPE& g, | |
1795 | typename BOOST_DISTRIB_CSR_GRAPH_TYPE::edge_descriptor k) | |
1796 | { | |
1797 | return get(edge_global, | |
1798 | const_cast<const BOOST_DISTRIB_CSR_GRAPH_TYPE&>(g), | |
1799 | k); | |
1800 | } | |
1801 | ||
1802 | template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS> | |
1803 | inline | |
1804 | typename property_map<BOOST_DISTRIB_CSR_GRAPH_TYPE, edge_global_t>::const_type | |
1805 | get(edge_global_t, const BOOST_DISTRIB_CSR_GRAPH_TYPE& g) | |
1806 | { | |
1807 | typedef typename property_map<BOOST_DISTRIB_CSR_GRAPH_TYPE, edge_global_t> | |
1808 | ::const_type result_type; | |
1809 | return result_type(); | |
1810 | } | |
1811 | ||
1812 | template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS> | |
1813 | inline | |
1814 | std::pair<typename ProcessGroup::process_id_type, | |
1815 | typename BOOST_DISTRIB_CSR_GRAPH_TYPE::base_type::edge_descriptor> | |
1816 | get(edge_global_t, const BOOST_DISTRIB_CSR_GRAPH_TYPE& g, | |
1817 | typename BOOST_DISTRIB_CSR_GRAPH_TYPE::edge_descriptor k) | |
1818 | { | |
1819 | typedef typename BOOST_DISTRIB_CSR_GRAPH_TYPE::vertex_descriptor | |
1820 | vertex_descriptor; | |
1821 | ||
1822 | const int local_index_bits = | |
1823 | sizeof(vertex_descriptor) * CHAR_BIT - processor_bits; | |
1824 | const typename BOOST_DISTRIB_CSR_GRAPH_TYPE::edges_size_type local_index_mask = | |
1825 | typename BOOST_DISTRIB_CSR_GRAPH_TYPE::edges_size_type(-1) >> processor_bits; | |
1826 | ||
1827 | typedef std::pair<typename ProcessGroup::process_id_type, | |
1828 | typename BOOST_DISTRIB_CSR_GRAPH_TYPE::base_type::edge_descriptor> | |
1829 | result_type; | |
1830 | ||
1831 | return result_type(k.src >> local_index_bits, | |
1832 | typename BOOST_DISTRIB_CSR_GRAPH_TYPE::base_type::edge_descriptor | |
1833 | (k.src & local_index_mask, k.idx)); | |
1834 | } | |
1835 | ||
1836 | // ----------------------------------------------------------------- | |
1837 | // Edge Index Property Map | |
1838 | template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS> | |
1839 | class property_map<BOOST_DISTRIB_CSR_GRAPH_TYPE, edge_index_t> | |
1840 | { | |
1841 | typedef typename property_map<BOOST_DISTRIB_CSR_GRAPH_TYPE, edge_global_t> | |
1842 | ::type global_map; | |
1843 | ||
1844 | public: | |
1845 | typedef local_property_map< | |
1846 | typename BOOST_DISTRIB_CSR_GRAPH_TYPE::process_group_type, | |
1847 | global_map, | |
1848 | typename property_map<typename BOOST_DISTRIB_CSR_GRAPH_TYPE::base_type, edge_index_t>::type | |
1849 | > type; | |
1850 | typedef type const_type; | |
1851 | }; | |
1852 | ||
1853 | template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS> | |
1854 | inline | |
1855 | typename property_map<BOOST_DISTRIB_CSR_GRAPH_TYPE, edge_index_t>::type | |
1856 | get(edge_index_t, BOOST_DISTRIB_CSR_GRAPH_TYPE& g) | |
1857 | { | |
1858 | typedef typename property_map<BOOST_DISTRIB_CSR_GRAPH_TYPE, edge_index_t> | |
1859 | ::type result_type; | |
1860 | return result_type(g.process_group(), get(edge_global, g), | |
1861 | get(edge_index, g.base())); | |
1862 | } | |
1863 | ||
1864 | template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS> | |
1865 | inline typename BOOST_DISTRIB_CSR_GRAPH_TYPE::edges_size_type | |
1866 | get(edge_index_t, BOOST_DISTRIB_CSR_GRAPH_TYPE& g, | |
1867 | typename BOOST_DISTRIB_CSR_GRAPH_TYPE::edge_descriptor k) | |
1868 | { | |
1869 | return k.idx; | |
1870 | } | |
1871 | ||
1872 | template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS> | |
1873 | inline | |
1874 | typename property_map<BOOST_DISTRIB_CSR_GRAPH_TYPE, edge_index_t>::const_type | |
1875 | get(edge_index_t, const BOOST_DISTRIB_CSR_GRAPH_TYPE& g) | |
1876 | { | |
1877 | typedef typename property_map<BOOST_DISTRIB_CSR_GRAPH_TYPE, edge_index_t> | |
1878 | ::const_type result_type; | |
1879 | return result_type(g.process_group(), get(edge_global, g), | |
1880 | get(edge_index, g.base())); | |
1881 | } | |
1882 | ||
1883 | template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS> | |
1884 | inline typename BOOST_DISTRIB_CSR_GRAPH_TYPE::edges_size_type | |
1885 | get(edge_index_t, const BOOST_DISTRIB_CSR_GRAPH_TYPE& g, | |
1886 | typename BOOST_DISTRIB_CSR_GRAPH_TYPE::edge_descriptor k) | |
1887 | { | |
1888 | return k.idx; | |
1889 | } | |
1890 | ||
1891 | template <BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS, typename Tag> | |
1892 | class property_map<BOOST_DISTRIB_CSR_GRAPH_TYPE, Tag> { | |
1893 | typedef BOOST_DISTRIB_CSR_GRAPH_TYPE graph_type; | |
1894 | typedef typename graph_type::process_group_type process_group_type; | |
1895 | typedef typename graph_type::base_type base_graph_type; | |
1896 | typedef typename property_map<base_graph_type, Tag>::type | |
1897 | local_pmap; | |
1898 | typedef typename property_map<base_graph_type, Tag>::const_type | |
1899 | local_const_pmap; | |
1900 | ||
1901 | typedef graph_traits<graph_type> traits; | |
1902 | typedef typename graph_traits<base_graph_type>::vertex_descriptor local_vertex; | |
1903 | typedef typename property_traits<local_pmap>::key_type local_key_type; | |
1904 | ||
1905 | typedef typename property_traits<local_pmap>::value_type value_type; | |
1906 | ||
1907 | typedef typename property_map<graph_type, vertex_global_t>::const_type | |
1908 | vertex_global_map; | |
1909 | typedef typename property_map<graph_type, edge_global_t>::const_type | |
1910 | edge_global_map; | |
1911 | ||
1912 | typedef typename mpl::if_<is_same<typename detail::property_kind_from_graph<base_graph_type, Tag>::type, | |
1913 | vertex_property_tag>, | |
1914 | vertex_global_map, edge_global_map>::type | |
1915 | global_map; | |
1916 | ||
1917 | public: | |
1918 | typedef ::boost::parallel::distributed_property_map< | |
1919 | process_group_type, global_map, local_pmap> type; | |
1920 | ||
1921 | typedef ::boost::parallel::distributed_property_map< | |
1922 | process_group_type, global_map, local_const_pmap> const_type; | |
1923 | }; | |
1924 | ||
1925 | template <BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS, typename Tag> | |
1926 | typename property_map<BOOST_DISTRIB_CSR_GRAPH_TYPE, Tag>::type | |
1927 | get(Tag tag, BOOST_DISTRIB_CSR_GRAPH_TYPE& g) | |
1928 | { | |
1929 | typedef BOOST_DISTRIB_CSR_GRAPH_TYPE Graph; | |
1930 | typedef typename property_map<Graph, Tag>::type result_type; | |
1931 | typedef typename property_traits<result_type>::value_type value_type; | |
1932 | typedef typename property_reduce<Tag>::template apply<value_type> | |
1933 | reduce; | |
1934 | ||
1935 | typedef typename mpl::if_<is_same<typename detail::property_kind_from_graph<Graph, Tag>::type, | |
1936 | vertex_property_tag>, | |
1937 | vertex_global_t, edge_global_t>::type | |
1938 | global_map_t; | |
1939 | ||
1940 | return result_type(g.process_group(), get(global_map_t(), g), | |
1941 | get(tag, g.base()), reduce()); | |
1942 | } | |
1943 | ||
1944 | template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS, typename Tag> | |
1945 | typename property_map<BOOST_DISTRIB_CSR_GRAPH_TYPE, Tag>::const_type | |
1946 | get(Tag tag, const BOOST_DISTRIB_CSR_GRAPH_TYPE& g) | |
1947 | { | |
1948 | typedef BOOST_DISTRIB_CSR_GRAPH_TYPE Graph; | |
1949 | typedef typename property_map<Graph, Tag>::const_type result_type; | |
1950 | typedef typename property_traits<result_type>::value_type value_type; | |
1951 | typedef typename property_reduce<Tag>::template apply<value_type> | |
1952 | reduce; | |
1953 | ||
1954 | typedef typename property_traits<result_type>::key_type descriptor; | |
1955 | typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor; | |
1956 | typedef typename mpl::if_<is_same<descriptor, vertex_descriptor>, | |
1957 | vertex_global_t, edge_global_t>::type | |
1958 | global_map_t; | |
1959 | ||
1960 | return result_type(g.process_group(), get(global_map_t(), g), | |
1961 | get(tag, g.base()), reduce()); | |
1962 | } | |
1963 | ||
1964 | namespace mpi { | |
1965 | template<typename Vertex, typename EdgeIndex> | |
1966 | struct is_mpi_datatype<boost::detail::csr_edge_descriptor<Vertex, EdgeIndex> > | |
1967 | : mpl::true_ { }; | |
1968 | } | |
1969 | ||
1970 | namespace serialization { | |
1971 | template<typename Vertex, typename EdgeIndex> | |
1972 | struct is_bitwise_serializable<boost::detail::csr_edge_descriptor<Vertex, EdgeIndex> > | |
1973 | : mpl::true_ { }; | |
1974 | ||
1975 | template<typename Vertex, typename EdgeIndex> | |
1976 | struct implementation_level<boost::detail::csr_edge_descriptor<Vertex, EdgeIndex> > | |
1977 | : mpl::int_<object_serializable> {} ; | |
1978 | ||
1979 | template<typename Vertex, typename EdgeIndex> | |
1980 | struct tracking_level<boost::detail::csr_edge_descriptor<Vertex, EdgeIndex> > | |
1981 | : mpl::int_<track_never> {} ; | |
1982 | ||
1983 | } | |
1984 | ||
1985 | } // end namespace boost | |
1986 | ||
1987 | #endif // BOOST_GRAPH_DISTRIBUTED_CSR_HPP |