]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | // Copyright (C) 2004-2006 The Trustees of Indiana University. |
2 | // Copyright (C) 2007 Douglas Gregor | |
3 | ||
4 | // Use, modification and distribution is subject to the Boost Software | |
5 | // License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at | |
6 | // http://www.boost.org/LICENSE_1_0.txt) | |
7 | ||
8 | // Authors: Douglas Gregor | |
9 | // Andrew Lumsdaine | |
10 | ||
11 | #ifndef BOOST_GRAPH_DISTRIBUTED_ADJACENCY_LIST_HPP | |
12 | #define BOOST_GRAPH_DISTRIBUTED_ADJACENCY_LIST_HPP | |
13 | ||
14 | #ifndef BOOST_GRAPH_USE_MPI | |
15 | #error "Parallel BGL files should not be included unless <boost/graph/use_mpi.hpp> has been included" | |
16 | #endif | |
17 | ||
18 | #include <boost/graph/adjacency_list.hpp> | |
19 | #include <boost/graph/properties.hpp> | |
20 | #include <boost/graph/graph_traits.hpp> | |
21 | #include <boost/graph/iteration_macros.hpp> | |
22 | #include <boost/graph/distributed/concepts.hpp> | |
23 | #include <boost/iterator/transform_iterator.hpp> | |
24 | #include <boost/property_map/property_map.hpp> | |
25 | #include <boost/graph/adjacency_iterator.hpp> | |
26 | #include <boost/property_map/parallel/distributed_property_map.hpp> | |
27 | #include <boost/property_map/parallel/local_property_map.hpp> | |
28 | #include <boost/graph/parallel/detail/property_holders.hpp> | |
29 | #include <boost/mpl/if.hpp> | |
30 | #include <boost/type_traits/is_same.hpp> | |
31 | #include <boost/assert.hpp> | |
32 | #include <list> | |
33 | #include <algorithm> | |
34 | #include <boost/limits.hpp> | |
35 | #include <boost/graph/parallel/properties.hpp> | |
36 | #include <boost/graph/parallel/distribution.hpp> | |
37 | #include <boost/graph/parallel/algorithm.hpp> | |
38 | #include <boost/graph/distributed/selector.hpp> | |
39 | #include <boost/graph/parallel/process_group.hpp> | |
40 | #include <boost/pending/container_traits.hpp> | |
41 | ||
42 | // Callbacks | |
43 | #include <boost/function/function2.hpp> | |
44 | ||
45 | // Serialization | |
46 | #include <boost/serialization/base_object.hpp> | |
47 | #include <boost/mpi/datatype.hpp> | |
48 | #include <boost/pending/property_serialize.hpp> | |
49 | #include <boost/graph/distributed/unsafe_serialize.hpp> | |
50 | ||
51 | // Named vertices | |
52 | #include <boost/graph/distributed/named_graph.hpp> | |
53 | ||
54 | #include <boost/graph/distributed/shuffled_distribution.hpp> | |
55 | ||
56 | namespace boost { | |
57 | ||
58 | /// The type used to store an identifier that uniquely names a processor. | |
59 | // NGE: I doubt we'll be running on more than 32768 procs for the time being | |
60 | typedef /*int*/ short processor_id_type; | |
61 | ||
62 | // Tell which processor the target of an edge resides on (for | |
63 | // directed graphs) or which processor the other end point of the | |
64 | // edge resides on (for undirected graphs). | |
65 | enum edge_target_processor_id_t { edge_target_processor_id }; | |
66 | BOOST_INSTALL_PROPERTY(edge, target_processor_id); | |
67 | ||
68 | // For undirected graphs, tells whether the edge is locally owned. | |
69 | enum edge_locally_owned_t { edge_locally_owned }; | |
70 | BOOST_INSTALL_PROPERTY(edge, locally_owned); | |
71 | ||
72 | // For bidirectional graphs, stores the incoming edges. | |
73 | enum vertex_in_edges_t { vertex_in_edges }; | |
74 | BOOST_INSTALL_PROPERTY(vertex, in_edges); | |
75 | ||
76 | /// Tag class for directed, distributed adjacency list | |
77 | struct directed_distributed_adj_list_tag | |
78 | : public virtual distributed_graph_tag, | |
79 | public virtual distributed_vertex_list_graph_tag, | |
80 | public virtual distributed_edge_list_graph_tag, | |
81 | public virtual incidence_graph_tag, | |
82 | public virtual adjacency_graph_tag {}; | |
83 | ||
84 | /// Tag class for bidirectional, distributed adjacency list | |
85 | struct bidirectional_distributed_adj_list_tag | |
86 | : public virtual distributed_graph_tag, | |
87 | public virtual distributed_vertex_list_graph_tag, | |
88 | public virtual distributed_edge_list_graph_tag, | |
89 | public virtual incidence_graph_tag, | |
90 | public virtual adjacency_graph_tag, | |
91 | public virtual bidirectional_graph_tag {}; | |
92 | ||
93 | /// Tag class for undirected, distributed adjacency list | |
94 | struct undirected_distributed_adj_list_tag | |
95 | : public virtual distributed_graph_tag, | |
96 | public virtual distributed_vertex_list_graph_tag, | |
97 | public virtual distributed_edge_list_graph_tag, | |
98 | public virtual incidence_graph_tag, | |
99 | public virtual adjacency_graph_tag, | |
100 | public virtual bidirectional_graph_tag {}; | |
101 | ||
102 | namespace detail { | |
103 | template<typename Archiver, typename Directed, typename Vertex> | |
104 | void | |
105 | serialize(Archiver& ar, edge_base<Directed, Vertex>& e, | |
106 | const unsigned int /*version*/) | |
107 | { | |
108 | ar & unsafe_serialize(e.m_source) | |
109 | & unsafe_serialize(e.m_target); | |
110 | } | |
111 | ||
112 | template<typename Archiver, typename Directed, typename Vertex> | |
113 | void | |
114 | serialize(Archiver& ar, edge_desc_impl<Directed, Vertex>& e, | |
115 | const unsigned int /*version*/) | |
116 | { | |
117 | ar & boost::serialization::base_object<edge_base<Directed, Vertex> >(e) | |
118 | & unsafe_serialize(e.m_eproperty); | |
119 | } | |
120 | } | |
121 | ||
122 | namespace detail { namespace parallel { | |
123 | ||
124 | /** | |
125 | * A distributed vertex descriptor. These descriptors contain both | |
126 | * the ID of the processor that owns the vertex and a local vertex | |
127 | * descriptor that identifies the particular vertex for that | |
128 | * processor. | |
129 | */ | |
130 | template<typename LocalDescriptor> | |
131 | struct global_descriptor | |
132 | { | |
133 | typedef LocalDescriptor local_descriptor_type; | |
134 | ||
135 | global_descriptor() : owner(), local() { } | |
136 | ||
137 | global_descriptor(processor_id_type owner, LocalDescriptor local) | |
138 | : owner(owner), local(local) { } | |
139 | ||
140 | processor_id_type owner; | |
141 | LocalDescriptor local; | |
142 | ||
143 | /** | |
144 | * A function object that, given a processor ID, generates | |
145 | * distributed vertex descriptors from local vertex | |
146 | * descriptors. This function object is used by the | |
147 | * vertex_iterator of the distributed adjacency list. | |
148 | */ | |
149 | struct generator | |
150 | { | |
151 | typedef global_descriptor<LocalDescriptor> result_type; | |
152 | typedef LocalDescriptor argument_type; | |
153 | ||
154 | generator() {} | |
155 | generator(processor_id_type owner) : owner(owner) {} | |
156 | ||
157 | result_type operator()(argument_type v) const | |
158 | { return result_type(owner, v); } | |
159 | ||
160 | private: | |
161 | processor_id_type owner; | |
162 | }; | |
163 | ||
164 | template<typename Archiver> | |
165 | void serialize(Archiver& ar, const unsigned int /*version*/) | |
166 | { | |
167 | ar & owner & unsafe_serialize(local); | |
168 | } | |
169 | }; | |
170 | ||
171 | /// Determine the process that owns the given descriptor | |
172 | template<typename LocalDescriptor> | |
173 | inline processor_id_type owner(const global_descriptor<LocalDescriptor>& v) | |
174 | { return v.owner; } | |
175 | ||
176 | /// Determine the local portion of the given descriptor | |
177 | template<typename LocalDescriptor> | |
178 | inline LocalDescriptor local(const global_descriptor<LocalDescriptor>& v) | |
179 | { return v.local; } | |
180 | ||
181 | /// Compare distributed vertex descriptors for equality | |
182 | template<typename LocalDescriptor> | |
183 | inline bool | |
184 | operator==(const global_descriptor<LocalDescriptor>& u, | |
185 | const global_descriptor<LocalDescriptor>& v) | |
186 | { | |
187 | return u.owner == v.owner && u.local == v.local; | |
188 | } | |
189 | ||
190 | /// Compare distributed vertex descriptors for inequality | |
191 | template<typename LocalDescriptor> | |
192 | inline bool | |
193 | operator!=(const global_descriptor<LocalDescriptor>& u, | |
194 | const global_descriptor<LocalDescriptor>& v) | |
195 | { return !(u == v); } | |
196 | ||
197 | template<typename LocalDescriptor> | |
198 | inline bool | |
199 | operator<(const global_descriptor<LocalDescriptor>& u, | |
200 | const global_descriptor<LocalDescriptor>& v) | |
201 | { | |
202 | return (u.owner) < v.owner || (u.owner == v.owner && (u.local) < v.local); | |
203 | } | |
204 | ||
205 | template<typename LocalDescriptor> | |
206 | inline bool | |
207 | operator<=(const global_descriptor<LocalDescriptor>& u, | |
208 | const global_descriptor<LocalDescriptor>& v) | |
209 | { | |
210 | return u.owner <= v.owner || (u.owner == v.owner && u.local <= v.local); | |
211 | } | |
212 | ||
213 | template<typename LocalDescriptor> | |
214 | inline bool | |
215 | operator>(const global_descriptor<LocalDescriptor>& u, | |
216 | const global_descriptor<LocalDescriptor>& v) | |
217 | { | |
218 | return v < u; | |
219 | } | |
220 | ||
221 | template<typename LocalDescriptor> | |
222 | inline bool | |
223 | operator>=(const global_descriptor<LocalDescriptor>& u, | |
224 | const global_descriptor<LocalDescriptor>& v) | |
225 | { | |
226 | return v <= u; | |
227 | } | |
228 | ||
229 | // DPG TBD: Add <, <=, >=, > for global descriptors | |
230 | ||
231 | /** | |
232 | * A Readable Property Map that extracts a global descriptor pair | |
233 | * from a global_descriptor. | |
234 | */ | |
235 | template<typename LocalDescriptor> | |
236 | struct global_descriptor_property_map | |
237 | { | |
238 | typedef std::pair<processor_id_type, LocalDescriptor> value_type; | |
239 | typedef value_type reference; | |
240 | typedef global_descriptor<LocalDescriptor> key_type; | |
241 | typedef readable_property_map_tag category; | |
242 | }; | |
243 | ||
244 | template<typename LocalDescriptor> | |
245 | inline std::pair<processor_id_type, LocalDescriptor> | |
246 | get(global_descriptor_property_map<LocalDescriptor>, | |
247 | global_descriptor<LocalDescriptor> x) | |
248 | { | |
249 | return std::pair<processor_id_type, LocalDescriptor>(x.owner, x.local); | |
250 | } | |
251 | ||
252 | /** | |
253 | * A Readable Property Map that extracts the owner of a global | |
254 | * descriptor. | |
255 | */ | |
256 | template<typename LocalDescriptor> | |
257 | struct owner_property_map | |
258 | { | |
259 | typedef processor_id_type value_type; | |
260 | typedef value_type reference; | |
261 | typedef global_descriptor<LocalDescriptor> key_type; | |
262 | typedef readable_property_map_tag category; | |
263 | }; | |
264 | ||
265 | template<typename LocalDescriptor> | |
266 | inline processor_id_type | |
267 | get(owner_property_map<LocalDescriptor>, | |
268 | global_descriptor<LocalDescriptor> x) | |
269 | { | |
270 | return x.owner; | |
271 | } | |
272 | ||
273 | /** | |
274 | * A Readable Property Map that extracts the local descriptor from | |
275 | * a global descriptor. | |
276 | */ | |
277 | template<typename LocalDescriptor> | |
278 | struct local_descriptor_property_map | |
279 | { | |
280 | typedef LocalDescriptor value_type; | |
281 | typedef value_type reference; | |
282 | typedef global_descriptor<LocalDescriptor> key_type; | |
283 | typedef readable_property_map_tag category; | |
284 | }; | |
285 | ||
286 | template<typename LocalDescriptor> | |
287 | inline LocalDescriptor | |
288 | get(local_descriptor_property_map<LocalDescriptor>, | |
289 | global_descriptor<LocalDescriptor> x) | |
290 | { | |
291 | return x.local; | |
292 | } | |
293 | ||
294 | /** | |
295 | * Stores an incoming edge for a bidirectional distributed | |
296 | * adjacency list. The user does not see this type directly, | |
297 | * because it is just an implementation detail. | |
298 | */ | |
299 | template<typename Edge> | |
300 | struct stored_in_edge | |
301 | { | |
302 | stored_in_edge(processor_id_type sp, Edge e) | |
303 | : source_processor(sp), e(e) {} | |
304 | ||
305 | processor_id_type source_processor; | |
306 | Edge e; | |
307 | }; | |
308 | ||
309 | /** | |
310 | * A distributed edge descriptor. These descriptors contain the | |
311 | * underlying edge descriptor, the processor IDs for both the | |
312 | * source and the target of the edge, and a boolean flag that | |
313 | * indicates which of the processors actually owns the edge. | |
314 | */ | |
315 | template<typename Edge> | |
316 | struct edge_descriptor | |
317 | { | |
318 | edge_descriptor(processor_id_type sp = processor_id_type(), | |
319 | processor_id_type tp = processor_id_type(), | |
320 | bool owns = false, Edge ld = Edge()) | |
321 | : source_processor(sp), target_processor(tp), | |
322 | source_owns_edge(owns), local(ld) {} | |
323 | ||
324 | processor_id_type owner() const | |
325 | { | |
326 | return source_owns_edge? source_processor : target_processor; | |
327 | } | |
328 | ||
329 | /// The processor that the source vertex resides on | |
330 | processor_id_type source_processor; | |
331 | ||
332 | /// The processor that the target vertex resides on | |
333 | processor_id_type target_processor; | |
334 | ||
335 | /// True when the source processor owns the edge, false when the | |
336 | /// target processor owns the edge. | |
337 | bool source_owns_edge; | |
338 | ||
339 | /// The local edge descriptor. | |
340 | Edge local; | |
341 | ||
342 | /** | |
343 | * Function object that generates edge descriptors for the | |
344 | * out_edge_iterator of the given distributed adjacency list | |
345 | * from the edge descriptors of the underlying adjacency list. | |
346 | */ | |
347 | template<typename Graph> | |
348 | class out_generator | |
349 | { | |
350 | typedef typename Graph::directed_selector directed_selector; | |
351 | ||
352 | public: | |
353 | typedef edge_descriptor<Edge> result_type; | |
354 | typedef Edge argument_type; | |
355 | ||
356 | out_generator() : g(0) {} | |
357 | explicit out_generator(const Graph& g) : g(&g) {} | |
358 | ||
359 | result_type operator()(argument_type e) const | |
360 | { return map(e, directed_selector()); } | |
361 | ||
362 | private: | |
363 | result_type map(argument_type e, directedS) const | |
364 | { | |
365 | return result_type(g->processor(), | |
366 | get(edge_target_processor_id, g->base(), e), | |
367 | true, e); | |
368 | } | |
369 | ||
370 | result_type map(argument_type e, bidirectionalS) const | |
371 | { | |
372 | return result_type(g->processor(), | |
373 | get(edge_target_processor_id, g->base(), e), | |
374 | true, e); | |
375 | } | |
376 | ||
377 | result_type map(argument_type e, undirectedS) const | |
378 | { | |
379 | return result_type(g->processor(), | |
380 | get(edge_target_processor_id, g->base(), e), | |
381 | get(edge_locally_owned, g->base(), e), | |
382 | e); | |
383 | } | |
384 | ||
385 | const Graph* g; | |
386 | }; | |
387 | ||
388 | /** | |
389 | * Function object that generates edge descriptors for the | |
390 | * in_edge_iterator of the given distributed adjacency list | |
391 | * from the edge descriptors of the underlying adjacency list. | |
392 | */ | |
393 | template<typename Graph> | |
394 | class in_generator | |
395 | { | |
396 | typedef typename Graph::directed_selector DirectedS; | |
397 | ||
398 | public: | |
399 | typedef typename boost::mpl::if_<is_same<DirectedS, bidirectionalS>, | |
400 | stored_in_edge<Edge>, | |
401 | Edge>::type argument_type; | |
402 | typedef edge_descriptor<Edge> result_type; | |
403 | ||
404 | in_generator() : g(0) {} | |
405 | explicit in_generator(const Graph& g) : g(&g) {} | |
406 | ||
407 | result_type operator()(argument_type e) const | |
408 | { return map(e, DirectedS()); } | |
409 | ||
410 | private: | |
411 | /** | |
412 | * For a bidirectional graph, we just generate the appropriate | |
413 | * edge. No tricks. | |
414 | */ | |
415 | result_type map(argument_type e, bidirectionalS) const | |
416 | { | |
417 | return result_type(e.source_processor, | |
418 | g->processor(), | |
419 | true, | |
420 | e.e); | |
421 | } | |
422 | ||
423 | /** | |
424 | * For an undirected graph, we generate descriptors for the | |
425 | * incoming edges by swapping the source/target of the | |
426 | * underlying edge descriptor (a hack). The target processor | |
427 | * ID on the edge is actually the source processor for this | |
428 | * edge, and our processor is the target processor. If the | |
429 | * edge is locally owned, then it is owned by the target (us); | |
430 | * otherwise it is owned by the source. | |
431 | */ | |
432 | result_type map(argument_type e, undirectedS) const | |
433 | { | |
434 | typename Graph::local_edge_descriptor local_edge(e); | |
435 | // TBD: This is a very, VERY lame hack that takes advantage | |
436 | // of our knowledge of the internals of the BGL | |
437 | // adjacency_list. There should be a cleaner way to handle | |
438 | // this... | |
439 | using std::swap; | |
440 | swap(local_edge.m_source, local_edge.m_target); | |
441 | return result_type(get(edge_target_processor_id, g->base(), e), | |
442 | g->processor(), | |
443 | !get(edge_locally_owned, g->base(), e), | |
444 | local_edge); | |
445 | } | |
446 | ||
447 | const Graph* g; | |
448 | }; | |
449 | ||
450 | private: | |
451 | friend class boost::serialization::access; | |
452 | ||
453 | template<typename Archiver> | |
454 | void serialize(Archiver& ar, const unsigned int /*version*/) | |
455 | { | |
456 | ar | |
457 | & source_processor | |
458 | & target_processor | |
459 | & source_owns_edge | |
460 | & local; | |
461 | } | |
462 | }; | |
463 | ||
464 | /// Determine the process that owns this edge | |
465 | template<typename Edge> | |
466 | inline processor_id_type | |
467 | owner(const edge_descriptor<Edge>& e) | |
468 | { return e.source_owns_edge? e.source_processor : e.target_processor; } | |
469 | ||
470 | /// Determine the local descriptor for this edge. | |
471 | template<typename Edge> | |
472 | inline Edge | |
473 | local(const edge_descriptor<Edge>& e) | |
474 | { return e.local; } | |
475 | ||
476 | /** | |
477 | * A Readable Property Map that extracts the owner and local | |
478 | * descriptor of an edge descriptor. | |
479 | */ | |
480 | template<typename Edge> | |
481 | struct edge_global_property_map | |
482 | { | |
483 | typedef std::pair<processor_id_type, Edge> value_type; | |
484 | typedef value_type reference; | |
485 | typedef edge_descriptor<Edge> key_type; | |
486 | typedef readable_property_map_tag category; | |
487 | }; | |
488 | ||
489 | template<typename Edge> | |
490 | inline std::pair<processor_id_type, Edge> | |
491 | get(edge_global_property_map<Edge>, const edge_descriptor<Edge>& e) | |
492 | { | |
493 | typedef std::pair<processor_id_type, Edge> result_type; | |
494 | return result_type(e.source_owns_edge? e.source_processor | |
495 | /* target owns edge*/: e.target_processor, | |
496 | e.local); | |
497 | } | |
498 | ||
499 | /** | |
500 | * A Readable Property Map that extracts the owner of an edge | |
501 | * descriptor. | |
502 | */ | |
503 | template<typename Edge> | |
504 | struct edge_owner_property_map | |
505 | { | |
506 | typedef processor_id_type value_type; | |
507 | typedef value_type reference; | |
508 | typedef edge_descriptor<Edge> key_type; | |
509 | typedef readable_property_map_tag category; | |
510 | }; | |
511 | ||
512 | template<typename Edge> | |
513 | inline processor_id_type | |
514 | get(edge_owner_property_map<Edge>, const edge_descriptor<Edge>& e) | |
515 | { | |
516 | return e.source_owns_edge? e.source_processor : e.target_processor; | |
517 | } | |
518 | ||
519 | /** | |
520 | * A Readable Property Map that extracts the local descriptor from | |
521 | * an edge descriptor. | |
522 | */ | |
523 | template<typename Edge> | |
524 | struct edge_local_property_map | |
525 | { | |
526 | typedef Edge value_type; | |
527 | typedef value_type reference; | |
528 | typedef edge_descriptor<Edge> key_type; | |
529 | typedef readable_property_map_tag category; | |
530 | }; | |
531 | ||
532 | template<typename Edge> | |
533 | inline Edge | |
534 | get(edge_local_property_map<Edge>, | |
535 | const edge_descriptor<Edge>& e) | |
536 | { | |
537 | return e.local; | |
538 | } | |
539 | ||
540 | /** Compare distributed edge descriptors for equality. | |
541 | * | |
542 | * \todo need edge_descriptor to know if it is undirected so we | |
543 | * can compare both ways. | |
544 | */ | |
545 | template<typename Edge> | |
546 | inline bool | |
547 | operator==(const edge_descriptor<Edge>& e1, | |
548 | const edge_descriptor<Edge>& e2) | |
549 | { | |
550 | return (e1.source_processor == e2.source_processor | |
551 | && e1.target_processor == e2.target_processor | |
552 | && e1.local == e2.local); | |
553 | } | |
554 | ||
555 | /// Compare distributed edge descriptors for inequality. | |
556 | template<typename Edge> | |
557 | inline bool | |
558 | operator!=(const edge_descriptor<Edge>& e1, | |
559 | const edge_descriptor<Edge>& e2) | |
560 | { return !(e1 == e2); } | |
561 | ||
562 | /** | |
563 | * Configuration for the distributed adjacency list. We use this | |
564 | * parameter to store all of the configuration details for the | |
565 | * implementation of the distributed adjacency list, which allows us to | |
566 | * get at the distribution type in the maybe_named_graph. | |
567 | */ | |
568 | template<typename OutEdgeListS, typename ProcessGroup, | |
569 | typename InVertexListS, typename InDistribution, | |
570 | typename DirectedS, typename VertexProperty, | |
571 | typename EdgeProperty, typename GraphProperty, | |
572 | typename EdgeListS> | |
573 | struct adjacency_list_config | |
574 | { | |
575 | typedef typename mpl::if_<is_same<InVertexListS, defaultS>, | |
576 | vecS, InVertexListS>::type | |
577 | VertexListS; | |
578 | ||
579 | /// Introduce the target processor ID property for each edge | |
580 | typedef property<edge_target_processor_id_t, processor_id_type, | |
581 | EdgeProperty> edge_property_with_id; | |
582 | ||
583 | /// For undirected graphs, introduce the locally-owned property for edges | |
584 | typedef typename boost::mpl::if_<is_same<DirectedS, undirectedS>, | |
585 | property<edge_locally_owned_t, bool, | |
586 | edge_property_with_id>, | |
587 | edge_property_with_id>::type | |
588 | base_edge_property_type; | |
589 | ||
590 | /// The edge descriptor type for the local subgraph | |
591 | typedef typename adjacency_list_traits<OutEdgeListS, | |
592 | VertexListS, | |
593 | directedS>::edge_descriptor | |
594 | local_edge_descriptor; | |
595 | ||
596 | /// For bidirectional graphs, the type of an incoming stored edge | |
597 | typedef stored_in_edge<local_edge_descriptor> bidir_stored_edge; | |
598 | ||
599 | /// The container type that will store incoming edges for a | |
600 | /// bidirectional graph. | |
601 | typedef typename container_gen<EdgeListS, bidir_stored_edge>::type | |
602 | in_edge_list_type; | |
603 | ||
604 | // Bidirectional graphs have an extra vertex property to store | |
605 | // the incoming edges. | |
606 | typedef typename boost::mpl::if_<is_same<DirectedS, bidirectionalS>, | |
607 | property<vertex_in_edges_t, in_edge_list_type, | |
608 | VertexProperty>, | |
609 | VertexProperty>::type | |
610 | base_vertex_property_type; | |
611 | ||
612 | // The type of the distributed adjacency list | |
613 | typedef adjacency_list<OutEdgeListS, | |
614 | distributedS<ProcessGroup, | |
615 | VertexListS, | |
616 | InDistribution>, | |
617 | DirectedS, VertexProperty, EdgeProperty, | |
618 | GraphProperty, EdgeListS> | |
619 | graph_type; | |
620 | ||
621 | // The type of the underlying adjacency list implementation | |
622 | typedef adjacency_list<OutEdgeListS, VertexListS, directedS, | |
623 | base_vertex_property_type, | |
624 | base_edge_property_type, | |
625 | GraphProperty, | |
626 | EdgeListS> | |
627 | inherited; | |
628 | ||
629 | typedef InDistribution in_distribution_type; | |
630 | typedef typename inherited::vertices_size_type vertices_size_type; | |
631 | ||
632 | typedef typename ::boost::graph::distributed::select_distribution< | |
633 | in_distribution_type, VertexProperty, vertices_size_type, | |
634 | ProcessGroup>::type | |
635 | base_distribution_type; | |
636 | ||
637 | typedef ::boost::graph::distributed::shuffled_distribution< | |
638 | base_distribution_type> distribution_type; | |
639 | ||
640 | typedef VertexProperty vertex_property_type; | |
641 | typedef EdgeProperty edge_property_type; | |
642 | typedef ProcessGroup process_group_type; | |
643 | ||
644 | typedef VertexListS vertex_list_selector; | |
645 | typedef OutEdgeListS out_edge_list_selector; | |
646 | typedef DirectedS directed_selector; | |
647 | typedef GraphProperty graph_property_type; | |
648 | typedef EdgeListS edge_list_selector; | |
649 | }; | |
650 | ||
651 | // Maybe initialize the indices of each vertex | |
652 | template<typename IteratorPair, typename VertexIndexMap> | |
653 | void | |
654 | maybe_initialize_vertex_indices(IteratorPair p, VertexIndexMap to_index, | |
655 | read_write_property_map_tag) | |
656 | { | |
657 | typedef typename property_traits<VertexIndexMap>::value_type index_t; | |
658 | index_t next_index = 0; | |
659 | while (p.first != p.second) | |
660 | put(to_index, *p.first++, next_index++); | |
661 | } | |
662 | ||
663 | template<typename IteratorPair, typename VertexIndexMap> | |
664 | inline void | |
665 | maybe_initialize_vertex_indices(IteratorPair p, VertexIndexMap to_index, | |
666 | readable_property_map_tag) | |
667 | { | |
668 | // Do nothing | |
669 | } | |
670 | ||
671 | template<typename IteratorPair, typename VertexIndexMap> | |
672 | inline void | |
673 | maybe_initialize_vertex_indices(IteratorPair p, VertexIndexMap to_index) | |
674 | { | |
675 | typedef typename property_traits<VertexIndexMap>::category category; | |
676 | maybe_initialize_vertex_indices(p, to_index, category()); | |
677 | } | |
678 | ||
679 | template<typename IteratorPair> | |
680 | inline void | |
681 | maybe_initialize_vertex_indices(IteratorPair p, | |
682 | ::boost::detail::error_property_not_found) | |
683 | { } | |
684 | ||
685 | /*********************************************************************** | |
686 | * Message Payloads * | |
687 | ***********************************************************************/ | |
688 | ||
689 | /** | |
690 | * Data stored with a msg_add_edge message, which requests the | |
691 | * remote addition of an edge. | |
692 | */ | |
693 | template<typename Vertex, typename LocalVertex> | |
694 | struct msg_add_edge_data | |
695 | { | |
696 | msg_add_edge_data() { } | |
697 | ||
698 | msg_add_edge_data(Vertex source, Vertex target) | |
699 | : source(source.local), target(target) { } | |
700 | ||
701 | /// The source of the edge; the processor will be the | |
702 | /// receiving processor. | |
703 | LocalVertex source; | |
704 | ||
705 | /// The target of the edge. | |
706 | Vertex target; | |
707 | ||
708 | template<typename Archiver> | |
709 | void serialize(Archiver& ar, const unsigned int /*version*/) | |
710 | { | |
711 | ar & unsafe_serialize(source) & target; | |
712 | } | |
713 | }; | |
714 | ||
715 | /** | |
716 | * Like @c msg_add_edge_data, but also includes a user-specified | |
717 | * property value to be attached to the edge. | |
718 | */ | |
719 | template<typename Vertex, typename LocalVertex, typename EdgeProperty> | |
720 | struct msg_add_edge_with_property_data | |
721 | : msg_add_edge_data<Vertex, LocalVertex>, | |
722 | maybe_store_property<EdgeProperty> | |
723 | { | |
724 | private: | |
725 | typedef msg_add_edge_data<Vertex, LocalVertex> inherited_data; | |
726 | typedef maybe_store_property<EdgeProperty> inherited_property; | |
727 | ||
728 | public: | |
729 | msg_add_edge_with_property_data() { } | |
730 | ||
731 | msg_add_edge_with_property_data(Vertex source, | |
732 | Vertex target, | |
733 | const EdgeProperty& property) | |
734 | : inherited_data(source, target), | |
735 | inherited_property(property) { } | |
736 | ||
737 | template<typename Archiver> | |
738 | void serialize(Archiver& ar, const unsigned int /*version*/) | |
739 | { | |
740 | ar & boost::serialization::base_object<inherited_data>(*this) | |
741 | & boost::serialization::base_object<inherited_property>(*this); | |
742 | } | |
743 | }; | |
744 | ||
745 | //------------------------------------------------------------------------ | |
746 | // Distributed adjacency list property map details | |
747 | /** | |
748 | * Metafunction that extracts the given property from the given | |
749 | * distributed adjacency list type. This could be implemented much | |
750 | * more cleanly, but even newer versions of GCC (e.g., 3.2.3) | |
751 | * cannot properly handle partial specializations involving | |
752 | * enumerator types. | |
753 | */ | |
754 | template<typename Property> | |
755 | struct get_adj_list_pmap | |
756 | { | |
757 | template<typename Graph> | |
758 | struct apply | |
759 | { | |
760 | typedef Graph graph_type; | |
761 | typedef typename graph_type::process_group_type process_group_type; | |
762 | typedef typename graph_type::inherited base_graph_type; | |
763 | typedef typename property_map<base_graph_type, Property>::type | |
764 | local_pmap; | |
765 | typedef typename property_map<base_graph_type, Property>::const_type | |
766 | local_const_pmap; | |
767 | ||
768 | typedef graph_traits<graph_type> traits; | |
769 | typedef typename graph_type::local_vertex_descriptor local_vertex; | |
770 | typedef typename property_traits<local_pmap>::key_type local_key_type; | |
771 | ||
772 | typedef typename property_traits<local_pmap>::value_type value_type; | |
773 | ||
774 | typedef typename property_map<Graph, vertex_global_t>::const_type | |
775 | vertex_global_map; | |
776 | typedef typename property_map<Graph, edge_global_t>::const_type | |
777 | edge_global_map; | |
778 | ||
779 | typedef typename mpl::if_c<(is_same<local_key_type, | |
780 | local_vertex>::value), | |
781 | vertex_global_map, edge_global_map>::type | |
782 | global_map; | |
783 | ||
784 | public: | |
785 | typedef ::boost::parallel::distributed_property_map< | |
786 | process_group_type, global_map, local_pmap> type; | |
787 | ||
788 | typedef ::boost::parallel::distributed_property_map< | |
789 | process_group_type, global_map, local_const_pmap> const_type; | |
790 | }; | |
791 | }; | |
792 | ||
793 | /** | |
794 | * The local vertex index property map is actually a mapping from | |
795 | * the local vertex descriptors to vertex indices. | |
796 | */ | |
797 | template<> | |
798 | struct get_adj_list_pmap<vertex_local_index_t> | |
799 | { | |
800 | template<typename Graph> | |
801 | struct apply | |
802 | : ::boost::property_map<typename Graph::inherited, vertex_index_t> | |
803 | { }; | |
804 | }; | |
805 | ||
806 | /** | |
807 | * The vertex index property map maps from global descriptors | |
808 | * (e.g., the vertex descriptor of a distributed adjacency list) | |
809 | * to the underlying local index. It is not valid to use this | |
810 | * property map with nonlocal descriptors. | |
811 | */ | |
812 | template<> | |
813 | struct get_adj_list_pmap<vertex_index_t> | |
814 | { | |
815 | template<typename Graph> | |
816 | struct apply | |
817 | { | |
818 | private: | |
819 | typedef typename property_map<Graph, vertex_global_t>::const_type | |
820 | global_map; | |
821 | ||
822 | typedef property_map<typename Graph::inherited, vertex_index_t> local; | |
823 | ||
824 | public: | |
825 | typedef local_property_map<typename Graph::process_group_type, | |
826 | global_map, | |
827 | typename local::type> type; | |
828 | typedef local_property_map<typename Graph::process_group_type, | |
829 | global_map, | |
830 | typename local::const_type> const_type; | |
831 | }; | |
832 | }; | |
833 | ||
834 | /** | |
835 | * The vertex owner property map maps from vertex descriptors to | |
836 | * the processor that owns the vertex. | |
837 | */ | |
838 | template<> | |
839 | struct get_adj_list_pmap<vertex_global_t> | |
840 | { | |
841 | template<typename Graph> | |
842 | struct apply | |
843 | { | |
844 | private: | |
845 | typedef typename Graph::local_vertex_descriptor | |
846 | local_vertex_descriptor; | |
847 | public: | |
848 | typedef global_descriptor_property_map<local_vertex_descriptor> type; | |
849 | typedef type const_type; | |
850 | }; | |
851 | }; | |
852 | ||
853 | /** | |
854 | * The vertex owner property map maps from vertex descriptors to | |
855 | * the processor that owns the vertex. | |
856 | */ | |
857 | template<> | |
858 | struct get_adj_list_pmap<vertex_owner_t> | |
859 | { | |
860 | template<typename Graph> | |
861 | struct apply | |
862 | { | |
863 | private: | |
864 | typedef typename Graph::local_vertex_descriptor | |
865 | local_vertex_descriptor; | |
866 | public: | |
867 | typedef owner_property_map<local_vertex_descriptor> type; | |
868 | typedef type const_type; | |
869 | }; | |
870 | }; | |
871 | ||
872 | /** | |
873 | * The vertex local property map maps from vertex descriptors to | |
874 | * the local descriptor for that vertex. | |
875 | */ | |
876 | template<> | |
877 | struct get_adj_list_pmap<vertex_local_t> | |
878 | { | |
879 | template<typename Graph> | |
880 | struct apply | |
881 | { | |
882 | private: | |
883 | typedef typename Graph::local_vertex_descriptor | |
884 | local_vertex_descriptor; | |
885 | public: | |
886 | typedef local_descriptor_property_map<local_vertex_descriptor> type; | |
887 | typedef type const_type; | |
888 | }; | |
889 | }; | |
890 | ||
891 | /** | |
892 | * The edge global property map maps from edge descriptors to | |
893 | * a pair of the owning processor and local descriptor. | |
894 | */ | |
895 | template<> | |
896 | struct get_adj_list_pmap<edge_global_t> | |
897 | { | |
898 | template<typename Graph> | |
899 | struct apply | |
900 | { | |
901 | private: | |
902 | typedef typename Graph::local_edge_descriptor | |
903 | local_edge_descriptor; | |
904 | public: | |
905 | typedef edge_global_property_map<local_edge_descriptor> type; | |
906 | typedef type const_type; | |
907 | }; | |
908 | }; | |
909 | ||
910 | /** | |
911 | * The edge owner property map maps from edge descriptors to | |
912 | * the processor that owns the edge. | |
913 | */ | |
914 | template<> | |
915 | struct get_adj_list_pmap<edge_owner_t> | |
916 | { | |
917 | template<typename Graph> | |
918 | struct apply | |
919 | { | |
920 | private: | |
921 | typedef typename Graph::local_edge_descriptor | |
922 | local_edge_descriptor; | |
923 | public: | |
924 | typedef edge_owner_property_map<local_edge_descriptor> type; | |
925 | typedef type const_type; | |
926 | }; | |
927 | }; | |
928 | ||
929 | /** | |
930 | * The edge local property map maps from edge descriptors to | |
931 | * the local descriptor for that edge. | |
932 | */ | |
933 | template<> | |
934 | struct get_adj_list_pmap<edge_local_t> | |
935 | { | |
936 | template<typename Graph> | |
937 | struct apply | |
938 | { | |
939 | private: | |
940 | typedef typename Graph::local_edge_descriptor | |
941 | local_edge_descriptor; | |
942 | public: | |
943 | typedef edge_local_property_map<local_edge_descriptor> type; | |
944 | typedef type const_type; | |
945 | }; | |
946 | }; | |
947 | //------------------------------------------------------------------------ | |
948 | ||
949 | // Directed graphs do not have in edges, so this is a no-op | |
950 | template<typename Graph> | |
951 | inline void | |
952 | remove_in_edge(typename Graph::edge_descriptor, Graph&, directedS) | |
953 | { } | |
954 | ||
955 | // Bidirectional graphs have in edges stored in the | |
956 | // vertex_in_edges property. | |
957 | template<typename Graph> | |
958 | inline void | |
959 | remove_in_edge(typename Graph::edge_descriptor e, Graph& g, bidirectionalS) | |
960 | { | |
961 | typedef typename Graph::in_edge_list_type in_edge_list_type; | |
962 | in_edge_list_type& in_edges = | |
963 | get(vertex_in_edges, g.base())[target(e, g).local]; | |
964 | typename in_edge_list_type::iterator i = in_edges.begin(); | |
965 | while (i != in_edges.end() | |
966 | && !(i->source_processor == source(e, g).owner) | |
967 | && i->e == e.local) | |
968 | ++i; | |
969 | ||
970 | BOOST_ASSERT(i != in_edges.end()); | |
971 | in_edges.erase(i); | |
972 | } | |
973 | ||
974 | // Undirected graphs have in edges stored as normal edges. | |
975 | template<typename Graph> | |
976 | inline void | |
977 | remove_in_edge(typename Graph::edge_descriptor e, Graph& g, undirectedS) | |
978 | { | |
979 | typedef typename Graph::inherited base_type; | |
980 | typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor; | |
981 | ||
982 | // TBD: can we make this more efficient? | |
983 | // Removing edge (v, u). v is local | |
984 | base_type& bg = g.base(); | |
985 | vertex_descriptor u = source(e, g); | |
986 | vertex_descriptor v = target(e, g); | |
987 | if (v.owner != process_id(g.process_group())) { | |
988 | using std::swap; | |
989 | swap(u, v); | |
990 | } | |
991 | ||
992 | typename graph_traits<base_type>::out_edge_iterator ei, ei_end; | |
993 | for (boost::tie(ei, ei_end) = out_edges(v.local, bg); ei != ei_end; ++ei) | |
994 | { | |
995 | if (target(*ei, g.base()) == u.local | |
996 | // TBD: deal with parallel edges properly && *ei == e | |
997 | && get(edge_target_processor_id, bg, *ei) == u.owner) { | |
998 | remove_edge(ei, bg); | |
999 | return; | |
1000 | } | |
1001 | } | |
1002 | ||
1003 | if (v.owner == process_id(g.process_group())) { | |
1004 | ||
1005 | } | |
1006 | } | |
1007 | ||
1008 | //------------------------------------------------------------------------ | |
1009 | // Lazy addition of edges | |
1010 | ||
1011 | // Work around the fact that an adjacency_list with vecS vertex | |
1012 | // storage automatically adds edges when the descriptor is | |
1013 | // out-of-range. | |
1014 | template <class Graph, class Config, class Base> | |
1015 | inline std::pair<typename Config::edge_descriptor, bool> | |
1016 | add_local_edge(typename Config::vertex_descriptor u, | |
1017 | typename Config::vertex_descriptor v, | |
1018 | const typename Config::edge_property_type& p, | |
1019 | vec_adj_list_impl<Graph, Config, Base>& g_) | |
1020 | { | |
1021 | adj_list_helper<Config, Base>& g = g_; | |
1022 | return add_edge(u, v, p, g); | |
1023 | } | |
1024 | ||
1025 | template <class Graph, class Config, class Base> | |
1026 | inline std::pair<typename Config::edge_descriptor, bool> | |
1027 | add_local_edge(typename Config::vertex_descriptor u, | |
1028 | typename Config::vertex_descriptor v, | |
1029 | const typename Config::edge_property_type& p, | |
1030 | boost::adj_list_impl<Graph, Config, Base>& g) | |
1031 | { | |
1032 | return add_edge(u, v, p, g); | |
1033 | } | |
1034 | ||
1035 | template <class EdgeProperty,class EdgeDescriptor> | |
1036 | struct msg_nonlocal_edge_data | |
1037 | : public detail::parallel::maybe_store_property<EdgeProperty> | |
1038 | { | |
1039 | typedef EdgeProperty edge_property_type; | |
1040 | typedef EdgeDescriptor local_edge_descriptor; | |
1041 | typedef detail::parallel::maybe_store_property<edge_property_type> | |
1042 | inherited; | |
1043 | ||
1044 | msg_nonlocal_edge_data() {} | |
1045 | msg_nonlocal_edge_data(local_edge_descriptor e, | |
1046 | const edge_property_type& p) | |
1047 | : inherited(p), e(e) { } | |
1048 | ||
1049 | local_edge_descriptor e; | |
1050 | ||
1051 | template<typename Archiver> | |
1052 | void serialize(Archiver& ar, const unsigned int /*version*/) | |
1053 | { | |
1054 | ar & boost::serialization::base_object<inherited>(*this) & e; | |
1055 | } | |
1056 | }; | |
1057 | ||
1058 | template <class EdgeDescriptor> | |
1059 | struct msg_remove_edge_data | |
1060 | { | |
1061 | typedef EdgeDescriptor edge_descriptor; | |
1062 | msg_remove_edge_data() {} | |
1063 | explicit msg_remove_edge_data(edge_descriptor e) : e(e) {} | |
1064 | ||
1065 | edge_descriptor e; | |
1066 | ||
1067 | template<typename Archiver> | |
1068 | void serialize(Archiver& ar, const unsigned int /*version*/) | |
1069 | { | |
1070 | ar & e; | |
1071 | } | |
1072 | }; | |
1073 | ||
1074 | } } // end namespace detail::parallel | |
1075 | ||
1076 | /** | |
1077 | * Adjacency list traits for a distributed adjacency list. Contains | |
1078 | * the vertex and edge descriptors, the directed-ness, and the | |
1079 | * parallel edges typedefs. | |
1080 | */ | |
1081 | template<typename OutEdgeListS, typename ProcessGroup, | |
1082 | typename InVertexListS, typename InDistribution, typename DirectedS> | |
1083 | struct adjacency_list_traits<OutEdgeListS, | |
1084 | distributedS<ProcessGroup, | |
1085 | InVertexListS, | |
1086 | InDistribution>, | |
1087 | DirectedS> | |
1088 | { | |
1089 | private: | |
1090 | typedef typename mpl::if_<is_same<InVertexListS, defaultS>, | |
1091 | vecS, | |
1092 | InVertexListS>::type VertexListS; | |
1093 | ||
1094 | typedef adjacency_list_traits<OutEdgeListS, VertexListS, directedS> | |
1095 | base_type; | |
1096 | ||
1097 | public: | |
1098 | typedef typename base_type::vertex_descriptor local_vertex_descriptor; | |
1099 | typedef typename base_type::edge_descriptor local_edge_descriptor; | |
1100 | ||
1101 | typedef typename boost::mpl::if_<typename DirectedS::is_bidir_t, | |
1102 | bidirectional_tag, | |
1103 | typename boost::mpl::if_<typename DirectedS::is_directed_t, | |
1104 | directed_tag, undirected_tag | |
1105 | >::type | |
1106 | >::type directed_category; | |
1107 | ||
1108 | typedef typename parallel_edge_traits<OutEdgeListS>::type | |
1109 | edge_parallel_category; | |
1110 | ||
1111 | typedef detail::parallel::global_descriptor<local_vertex_descriptor> | |
1112 | vertex_descriptor; | |
1113 | ||
1114 | typedef detail::parallel::edge_descriptor<local_edge_descriptor> | |
1115 | edge_descriptor; | |
1116 | }; | |
1117 | ||
1118 | #define PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS \ | |
1119 | typename OutEdgeListS, typename ProcessGroup, typename InVertexListS, \ | |
1120 | typename InDistribution, typename DirectedS, typename VertexProperty, \ | |
1121 | typename EdgeProperty, typename GraphProperty, typename EdgeListS | |
1122 | ||
1123 | #define PBGL_DISTRIB_ADJLIST_TYPE \ | |
1124 | adjacency_list<OutEdgeListS, \ | |
1125 | distributedS<ProcessGroup, InVertexListS, InDistribution>, \ | |
1126 | DirectedS, VertexProperty, EdgeProperty, GraphProperty, \ | |
1127 | EdgeListS> | |
1128 | ||
1129 | #define PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS_CONFIG \ | |
1130 | typename OutEdgeListS, typename ProcessGroup, typename InVertexListS, \ | |
1131 | typename InDistribution, typename VertexProperty, \ | |
1132 | typename EdgeProperty, typename GraphProperty, typename EdgeListS | |
1133 | ||
1134 | #define PBGL_DISTRIB_ADJLIST_TYPE_CONFIG(directed) \ | |
1135 | adjacency_list<OutEdgeListS, \ | |
1136 | distributedS<ProcessGroup, InVertexListS, InDistribution>, \ | |
1137 | directed, VertexProperty, EdgeProperty, GraphProperty, \ | |
1138 | EdgeListS> | |
1139 | ||
1140 | /** A distributed adjacency list. | |
1141 | * | |
1142 | * This class template partial specialization defines a distributed | |
1143 | * (or "partitioned") adjacency list graph. The distributed | |
1144 | * adjacency list is similar to the standard Boost Graph Library | |
1145 | * adjacency list, which stores a list of vertices and for each | |
1146 | * verted the list of edges outgoing from the vertex (and, in some | |
1147 | * cases, also the edges incoming to the vertex). The distributed | |
1148 | * adjacency list differs in that it partitions the graph into | |
1149 | * several subgraphs that are then divided among different | |
1150 | * processors (or nodes within a cluster). The distributed adjacency | |
1151 | * list attempts to maintain a high degree of compatibility with the | |
1152 | * standard, non-distributed adjacency list. | |
1153 | * | |
1154 | * The graph is partitioned by vertex, with each processor storing | |
1155 | * all of the required information for a particular subset of the | |
1156 | * vertices, including vertex properties, outgoing edges, and (for | |
1157 | * bidirectional graphs) incoming edges. This information is | |
1158 | * accessible only on the processor that owns the vertex: for | |
1159 | * instance, if processor 0 owns vertex @c v, no other processor can | |
1160 | * directly access the properties of @c v or enumerate its outgoing | |
1161 | * edges. | |
1162 | * | |
1163 | * Edges in a graph may be entirely local (connecting two local | |
1164 | * vertices), but more often it is the case that edges are | |
1165 | * non-local, meaning that the two vertices they connect reside in | |
1166 | * different processes. Edge properties are stored with the | |
1167 | * originating vertex for directed and bidirectional graphs, and are | |
1168 | * therefore only accessible from the processor that owns the | |
1169 | * originating vertex. Other processors may query the source and | |
1170 | * target of the edge, but cannot access its properties. This is | |
1171 | * particularly interesting when accessing the incoming edges of a | |
1172 | * bidirectional graph, which are not guaranteed to be stored on the | |
1173 | * processor that is able to perform the iteration. For undirected | |
1174 | * graphs the situation is more complicated, since no vertex clearly | |
1175 | * owns the edges: the list of edges incident to a vertex may | |
1176 | * contain a mix of local and non-local edges. | |
1177 | * | |
1178 | * The distributed adjacency list is able to model several of the | |
1179 | * existing Graph concepts. It models the Graph concept because it | |
1180 | * exposes vertex and edge descriptors in the normal way; these | |
1181 | * descriptors model the GlobalDescriptor concept (because they have | |
1182 | * an owner and a local descriptor), and as such the distributed | |
1183 | * adjacency list models the DistributedGraph concept. The adjacency | |
1184 | * list also models the IncidenceGraph and AdjacencyGraph concepts, | |
1185 | * although this is only true so long as the domain of the valid | |
1186 | * expression arguments are restricted to vertices and edges stored | |
1187 | * locally. Likewise, bidirectional and undirected distributed | |
1188 | * adjacency lists model the BidirectionalGraph concept (vertex and | |
1189 | * edge domains must be respectived) and the distributed adjacency | |
1190 | * list models the MutableGraph concept (vertices and edges can only | |
1191 | * be added or removed locally). T he distributed adjacency list | |
1192 | * does not, however, model the VertexListGraph or EdgeListGraph | |
1193 | * concepts, because we can not efficiently enumerate all vertices | |
1194 | * or edges in the graph. Instead, the local subsets of vertices and | |
1195 | * edges can be enumerated (with the same syntax): the distributed | |
1196 | * adjacency list therefore models the DistributedVertexListGraph | |
1197 | * and DistributedEdgeListGraph concepts, because concurrent | |
1198 | * iteration over all of the vertices or edges stored on each | |
1199 | * processor will visit each vertex or edge. | |
1200 | * | |
1201 | * The distributed adjacency list is distinguished from the | |
1202 | * non-distributed version by the vertex list descriptor, which will | |
1203 | * be @c distributedS<ProcessGroup,VertexListS>. Here, | |
1204 | * the VertexListS type plays the same role as the VertexListS type | |
1205 | * in the non-distributed adjacency list: it allows one to select | |
1206 | * the data structure that will be used to store the local | |
1207 | * vertices. The ProcessGroup type, on the other hand, is unique to | |
1208 | * distributed data structures: it is the type that abstracts a | |
1209 | * group of cooperating processes, and it used for process | |
1210 | * identification, communication, and synchronization, among other | |
1211 | * things. Different process group types represent different | |
1212 | * communication mediums (e.g., MPI, PVM, TCP) or different models | |
1213 | * of communication (LogP, CGM, BSP, synchronous, etc.). This | |
1214 | * distributed adjacency list assumes a model based on non-blocking | |
1215 | * sends. | |
1216 | * | |
1217 | * Distribution of vertices across different processors is | |
1218 | * accomplished in two different ways. When initially constructing | |
1219 | * the graph, the user may provide a distribution object (that | |
1220 | * models the Distribution concept), which will determine the | |
1221 | * distribution of vertices to each process. Additionally, the @c | |
1222 | * add_vertex and @c add_edge operations add vertices or edges | |
1223 | * stored on the local processor. For @c add_edge, this is | |
1224 | * accomplished by requiring that the source vertex of the new edge | |
1225 | * be local to the process executing @c add_edge. | |
1226 | * | |
1227 | * Internal properties of a distributed adjacency list are | |
1228 | * accessible in the same manner as internal properties for a | |
1229 | * non-distributed adjacency list for local vertices or | |
1230 | * edges. Access to properties for remote vertices or edges occurs | |
1231 | * with the same syntax, but involve communication with the owner of | |
1232 | * the information: for more information, refer to class template | |
1233 | * @ref distributed_property_map, which manages distributed | |
1234 | * property maps. Note that the distributed property maps created | |
1235 | * for internal properties determine their reduction operation via | |
1236 | * the metafunction @ref property_reduce, which for the vast | |
1237 | * majority of uses is correct behavior. | |
1238 | * | |
1239 | * Communication among the processes coordinating on a particular | |
1240 | * distributed graph relies on non-blocking message passing along | |
1241 | * with synchronization. Local portions of the distributed graph may | |
1242 | * be modified concurrently, including the introduction of non-local | |
1243 | * edges, but prior to accessing the graph it is recommended that | |
1244 | * the @c synchronize free function be invoked on the graph to clear | |
1245 | * up any pending interprocess communication and modifications. All | |
1246 | * processes will then be released from the synchronization barrier | |
1247 | * concurrently. | |
1248 | * | |
1249 | * \todo Determine precisely what we should do with nonlocal edges | |
1250 | * in undirected graphs. Our parallelization of certain algorithms | |
1251 | * relies on the ability to access edge property maps immediately | |
1252 | * (e.g., edge_weight_t), so it may be necessary to duplicate the | |
1253 | * edge properties in both processes (but then we need some form of | |
1254 | * coherence protocol). | |
1255 | * | |
1256 | * \todo What does the user do if @c property_reduce doesn't do the | |
1257 | * right thing? | |
1258 | */ | |
1259 | template<typename OutEdgeListS, typename ProcessGroup, | |
1260 | typename InVertexListS, typename InDistribution, typename DirectedS, | |
1261 | typename VertexProperty, typename EdgeProperty, | |
1262 | typename GraphProperty, typename EdgeListS> | |
1263 | class adjacency_list<OutEdgeListS, | |
1264 | distributedS<ProcessGroup, | |
1265 | InVertexListS, | |
1266 | InDistribution>, | |
1267 | DirectedS, VertexProperty, | |
1268 | EdgeProperty, GraphProperty, EdgeListS> | |
1269 | : // Support for named vertices | |
1270 | public graph::distributed::maybe_named_graph< | |
1271 | adjacency_list<OutEdgeListS, | |
1272 | distributedS<ProcessGroup, | |
1273 | InVertexListS, | |
1274 | InDistribution>, | |
1275 | DirectedS, VertexProperty, | |
1276 | EdgeProperty, GraphProperty, EdgeListS>, | |
1277 | typename adjacency_list_traits<OutEdgeListS, | |
1278 | distributedS<ProcessGroup, | |
1279 | InVertexListS, | |
1280 | InDistribution>, | |
1281 | DirectedS>::vertex_descriptor, | |
1282 | typename adjacency_list_traits<OutEdgeListS, | |
1283 | distributedS<ProcessGroup, | |
1284 | InVertexListS, | |
1285 | InDistribution>, | |
1286 | DirectedS>::edge_descriptor, | |
1287 | detail::parallel::adjacency_list_config<OutEdgeListS, ProcessGroup, | |
1288 | InVertexListS, InDistribution, | |
1289 | DirectedS, VertexProperty, | |
1290 | EdgeProperty, GraphProperty, | |
1291 | EdgeListS> > | |
1292 | { | |
1293 | typedef detail::parallel::adjacency_list_config<OutEdgeListS, ProcessGroup, | |
1294 | InVertexListS, InDistribution, | |
1295 | DirectedS, VertexProperty, | |
1296 | EdgeProperty, GraphProperty, | |
1297 | EdgeListS> | |
1298 | config_type; | |
1299 | ||
1300 | typedef adjacency_list_traits<OutEdgeListS, | |
1301 | distributedS<ProcessGroup, | |
1302 | InVertexListS, | |
1303 | InDistribution>, | |
1304 | DirectedS> | |
1305 | traits_type; | |
1306 | ||
1307 | typedef typename DirectedS::is_directed_t is_directed; | |
1308 | ||
1309 | typedef EdgeListS edge_list_selector; | |
1310 | ||
1311 | public: | |
1312 | /// The container type that will store incoming edges for a | |
1313 | /// bidirectional graph. | |
1314 | typedef typename config_type::in_edge_list_type in_edge_list_type; | |
1315 | // typedef typename inherited::edge_descriptor edge_descriptor; | |
1316 | ||
1317 | /// The type of the underlying adjacency list implementation | |
1318 | typedef typename config_type::inherited inherited; | |
1319 | ||
1320 | /// The type of properties stored in the local subgraph | |
1321 | /// Bidirectional graphs have an extra vertex property to store | |
1322 | /// the incoming edges. | |
1323 | typedef typename inherited::vertex_property_type | |
1324 | base_vertex_property_type; | |
1325 | ||
1326 | /// The type of the distributed adjacency list (this type) | |
1327 | typedef typename config_type::graph_type graph_type; | |
1328 | ||
1329 | /// Expose graph components and graph category | |
1330 | typedef typename traits_type::local_vertex_descriptor | |
1331 | local_vertex_descriptor; | |
1332 | typedef typename traits_type::local_edge_descriptor | |
1333 | local_edge_descriptor; | |
1334 | typedef typename traits_type::vertex_descriptor vertex_descriptor; | |
1335 | typedef typename traits_type::edge_descriptor edge_descriptor; | |
1336 | ||
1337 | typedef typename traits_type::directed_category directed_category; | |
1338 | typedef typename inherited::edge_parallel_category | |
1339 | edge_parallel_category; | |
1340 | typedef typename inherited::graph_tag graph_tag; | |
1341 | ||
1342 | // Current implementation requires the ability to have parallel | |
1343 | // edges in the underlying adjacency_list. Which processor each | |
1344 | // edge refers to is attached as an internal property. TBD: | |
1345 | // remove this restriction, which may require some rewriting. | |
1346 | BOOST_STATIC_ASSERT((is_same<edge_parallel_category, | |
1347 | allow_parallel_edge_tag>::value)); | |
1348 | ||
1349 | /** Determine the graph traversal category. | |
1350 | * | |
1351 | * A directed distributed adjacency list models the Distributed | |
1352 | * Graph, Incidence Graph, and Adjacency Graph | |
1353 | * concepts. Bidirectional and undirected graphs also model the | |
1354 | * Bidirectional Graph concept. Note that when modeling these | |
1355 | * concepts the domains of certain operations (e.g., in_edges) | |
1356 | * are restricted; see the distributed adjacency_list | |
1357 | * documentation. | |
1358 | */ | |
1359 | typedef typename boost::mpl::if_< | |
1360 | is_same<DirectedS, directedS>, | |
1361 | directed_distributed_adj_list_tag, | |
1362 | typename boost::mpl::if_<is_same<DirectedS, bidirectionalS>, | |
1363 | bidirectional_distributed_adj_list_tag, | |
1364 | undirected_distributed_adj_list_tag>::type> | |
1365 | ::type traversal_category; | |
1366 | ||
1367 | typedef typename inherited::degree_size_type degree_size_type; | |
1368 | typedef typename inherited::vertices_size_type vertices_size_type; | |
1369 | typedef typename inherited::edges_size_type edges_size_type; | |
1370 | typedef VertexProperty vertex_property_type; | |
1371 | typedef EdgeProperty edge_property_type; | |
1372 | typedef typename inherited::graph_property_type graph_property_type; | |
1373 | typedef typename inherited::vertex_bundled vertex_bundled; | |
1374 | typedef typename inherited::edge_bundled edge_bundled; | |
1375 | typedef typename inherited::graph_bundled graph_bundled; | |
1376 | ||
1377 | typedef typename container_gen<edge_list_selector, edge_descriptor>::type | |
1378 | local_edge_list_type; | |
1379 | ||
1380 | private: | |
1381 | typedef typename boost::mpl::if_<is_same<DirectedS, bidirectionalS>, | |
1382 | typename in_edge_list_type::const_iterator, | |
1383 | typename inherited::out_edge_iterator>::type | |
1384 | base_in_edge_iterator; | |
1385 | ||
1386 | typedef typename inherited::out_edge_iterator base_out_edge_iterator; | |
1387 | typedef typename graph_traits<inherited>::edge_iterator | |
1388 | base_edge_iterator; | |
1389 | typedef typename inherited::edge_property_type base_edge_property_type; | |
1390 | ||
1391 | typedef typename local_edge_list_type::const_iterator | |
1392 | undirected_edge_iterator; | |
1393 | ||
1394 | typedef InDistribution in_distribution_type; | |
1395 | ||
1396 | typedef parallel::trigger_receive_context trigger_receive_context; | |
1397 | ||
1398 | public: | |
1399 | /// Iterator over the (local) vertices of the graph | |
1400 | typedef transform_iterator<typename vertex_descriptor::generator, | |
1401 | typename inherited::vertex_iterator> | |
1402 | vertex_iterator; | |
1403 | ||
1404 | /// Helper for out_edge_iterator | |
1405 | typedef typename edge_descriptor::template out_generator<adjacency_list> | |
1406 | out_edge_generator; | |
1407 | ||
1408 | /// Iterator over the outgoing edges of a vertex | |
1409 | typedef transform_iterator<out_edge_generator, | |
1410 | typename inherited::out_edge_iterator> | |
1411 | out_edge_iterator; | |
1412 | ||
1413 | /// Helper for in_edge_iterator | |
1414 | typedef typename edge_descriptor::template in_generator<adjacency_list> | |
1415 | in_edge_generator; | |
1416 | ||
1417 | /// Iterator over the incoming edges of a vertex | |
1418 | typedef transform_iterator<in_edge_generator, base_in_edge_iterator> | |
1419 | in_edge_iterator; | |
1420 | ||
1421 | /// Iterator over the neighbors of a vertex | |
1422 | typedef boost::adjacency_iterator< | |
1423 | adjacency_list, vertex_descriptor, out_edge_iterator, | |
1424 | typename detail::iterator_traits<base_out_edge_iterator> | |
1425 | ::difference_type> | |
1426 | adjacency_iterator; | |
1427 | ||
1428 | /// Iterator over the (local) edges in a graph | |
1429 | typedef typename boost::mpl::if_<is_same<DirectedS, undirectedS>, | |
1430 | undirected_edge_iterator, | |
1431 | transform_iterator<out_edge_generator, | |
1432 | base_edge_iterator> | |
1433 | >::type | |
1434 | edge_iterator; | |
1435 | ||
1436 | public: | |
1437 | /// The type of the mixin for named vertices | |
1438 | typedef graph::distributed::maybe_named_graph<graph_type, | |
1439 | vertex_descriptor, | |
1440 | edge_descriptor, | |
1441 | config_type> | |
1442 | named_graph_mixin; | |
1443 | ||
1444 | /// Process group used for communication | |
1445 | typedef ProcessGroup process_group_type; | |
1446 | ||
1447 | /// How to refer to a process | |
1448 | typedef typename process_group_type::process_id_type process_id_type; | |
1449 | ||
1450 | /// Whether this graph is directed, undirected, or bidirectional | |
1451 | typedef DirectedS directed_selector; | |
1452 | ||
1453 | // Structure used for the lazy addition of vertices | |
1454 | struct lazy_add_vertex_with_property; | |
1455 | friend struct lazy_add_vertex_with_property; | |
1456 | ||
1457 | // Structure used for the lazy addition of edges | |
1458 | struct lazy_add_edge; | |
1459 | friend struct lazy_add_edge; | |
1460 | ||
1461 | // Structure used for the lazy addition of edges with properties | |
1462 | struct lazy_add_edge_with_property; | |
1463 | friend struct lazy_add_edge_with_property; | |
1464 | ||
1465 | /// default_distribution_type is the type of the distribution used if the | |
1466 | /// user didn't specify an explicit one | |
1467 | typedef typename graph::distributed::select_distribution< | |
1468 | InDistribution, VertexProperty, vertices_size_type, | |
1469 | ProcessGroup>::default_type | |
1470 | default_distribution_type; | |
1471 | ||
1472 | /// distribution_type is the type of the distribution instance stored in | |
1473 | /// the maybe_named_graph base class | |
1474 | typedef typename graph::distributed::select_distribution< | |
1475 | InDistribution, VertexProperty, vertices_size_type, | |
1476 | ProcessGroup>::type | |
1477 | base_distribution_type; | |
1478 | ||
1479 | typedef graph::distributed::shuffled_distribution< | |
1480 | base_distribution_type> distribution_type; | |
1481 | ||
1482 | private: | |
1483 | // FIXME: the original adjacency_list contained this comment: | |
1484 | // Default copy constructor and copy assignment operators OK??? TBD | |
1485 | // but the adj_list_impl contained these declarations: | |
1486 | adjacency_list(const adjacency_list& other); | |
1487 | adjacency_list& operator=(const adjacency_list& other); | |
1488 | ||
1489 | public: | |
1490 | adjacency_list(const ProcessGroup& pg = ProcessGroup()) | |
1491 | : named_graph_mixin(pg, default_distribution_type(pg, 0)), | |
1492 | m_local_graph(GraphProperty()), | |
1493 | process_group_(pg, boost::parallel::attach_distributed_object()) | |
1494 | { | |
1495 | setup_triggers(); | |
1496 | } | |
1497 | ||
1498 | adjacency_list(const ProcessGroup& pg, | |
1499 | const base_distribution_type& distribution) | |
1500 | : named_graph_mixin(pg, distribution), | |
1501 | m_local_graph(GraphProperty()), | |
1502 | process_group_(pg, boost::parallel::attach_distributed_object()) | |
1503 | { | |
1504 | setup_triggers(); | |
1505 | } | |
1506 | ||
1507 | adjacency_list(const GraphProperty& g, | |
1508 | const ProcessGroup& pg = ProcessGroup()) | |
1509 | : named_graph_mixin(pg, default_distribution_type(pg, 0)), | |
1510 | m_local_graph(g), | |
1511 | process_group_(pg, boost::parallel::attach_distributed_object()) | |
1512 | { | |
1513 | setup_triggers(); | |
1514 | } | |
1515 | ||
1516 | adjacency_list(vertices_size_type n, | |
1517 | const GraphProperty& p, | |
1518 | const ProcessGroup& pg, | |
1519 | const base_distribution_type& distribution) | |
1520 | : named_graph_mixin(pg, distribution), | |
1521 | m_local_graph(distribution.block_size(process_id(pg), n), p), | |
1522 | process_group_(pg, boost::parallel::attach_distributed_object()) | |
1523 | { | |
1524 | setup_triggers(); | |
1525 | ||
1526 | detail::parallel::maybe_initialize_vertex_indices(vertices(base()), | |
1527 | get(vertex_index, base())); | |
1528 | } | |
1529 | ||
1530 | adjacency_list(vertices_size_type n, | |
1531 | const ProcessGroup& pg, | |
1532 | const base_distribution_type& distribution) | |
1533 | : named_graph_mixin(pg, distribution), | |
1534 | m_local_graph(distribution.block_size(process_id(pg), n), GraphProperty()), | |
1535 | process_group_(pg, boost::parallel::attach_distributed_object()) | |
1536 | { | |
1537 | setup_triggers(); | |
1538 | ||
1539 | detail::parallel::maybe_initialize_vertex_indices(vertices(base()), | |
1540 | get(vertex_index, base())); | |
1541 | } | |
1542 | ||
1543 | adjacency_list(vertices_size_type n, | |
1544 | const GraphProperty& p, | |
1545 | const ProcessGroup& pg = ProcessGroup()) | |
1546 | : named_graph_mixin(pg, default_distribution_type(pg, n)), | |
1547 | m_local_graph(this->distribution().block_size(process_id(pg), n), p), | |
1548 | process_group_(pg, boost::parallel::attach_distributed_object()) | |
1549 | { | |
1550 | setup_triggers(); | |
1551 | ||
1552 | detail::parallel::maybe_initialize_vertex_indices(vertices(base()), | |
1553 | get(vertex_index, base())); | |
1554 | } | |
1555 | ||
1556 | adjacency_list(vertices_size_type n, | |
1557 | const ProcessGroup& pg = ProcessGroup()) | |
1558 | : named_graph_mixin(pg, default_distribution_type(pg, n)), | |
1559 | m_local_graph(this->distribution().block_size(process_id(pg), n), | |
1560 | GraphProperty()), | |
1561 | process_group_(pg, boost::parallel::attach_distributed_object()) | |
1562 | { | |
1563 | setup_triggers(); | |
1564 | ||
1565 | detail::parallel::maybe_initialize_vertex_indices(vertices(base()), | |
1566 | get(vertex_index, base())); | |
1567 | } | |
1568 | ||
1569 | /* | |
1570 | * We assume that every processor sees the same list of edges, so | |
1571 | * they skip over any that don't originate from themselves. This | |
1572 | * means that programs switching between a local and a distributed | |
1573 | * graph will keep the same semantics. | |
1574 | */ | |
1575 | template <class EdgeIterator> | |
1576 | adjacency_list(EdgeIterator first, EdgeIterator last, | |
1577 | vertices_size_type n, | |
1578 | const ProcessGroup& pg = ProcessGroup(), | |
1579 | const GraphProperty& p = GraphProperty()) | |
1580 | : named_graph_mixin(pg, default_distribution_type(pg, n)), | |
1581 | m_local_graph(this->distribution().block_size(process_id(pg), n), p), | |
1582 | process_group_(pg, boost::parallel::attach_distributed_object()) | |
1583 | { | |
1584 | setup_triggers(); | |
1585 | ||
1586 | typedef typename config_type::VertexListS vertex_list_selector; | |
1587 | initialize(first, last, n, this->distribution(), vertex_list_selector()); | |
1588 | detail::parallel::maybe_initialize_vertex_indices(vertices(base()), | |
1589 | get(vertex_index, base())); | |
1590 | ||
1591 | } | |
1592 | ||
1593 | template <class EdgeIterator, class EdgePropertyIterator> | |
1594 | adjacency_list(EdgeIterator first, EdgeIterator last, | |
1595 | EdgePropertyIterator ep_iter, | |
1596 | vertices_size_type n, | |
1597 | const ProcessGroup& pg = ProcessGroup(), | |
1598 | const GraphProperty& p = GraphProperty()) | |
1599 | : named_graph_mixin(pg, default_distribution_type(pg, n)), | |
1600 | m_local_graph(this->distribution().block_size(process_id(pg), n), p), | |
1601 | process_group_(pg, boost::parallel::attach_distributed_object()) | |
1602 | { | |
1603 | setup_triggers(); | |
1604 | ||
1605 | typedef typename config_type::VertexListS vertex_list_selector; | |
1606 | initialize(first, last, ep_iter, n, this->distribution(), | |
1607 | vertex_list_selector()); | |
1608 | detail::parallel::maybe_initialize_vertex_indices(vertices(base()), | |
1609 | get(vertex_index, base())); | |
1610 | ||
1611 | } | |
1612 | ||
1613 | template <class EdgeIterator> | |
1614 | adjacency_list(EdgeIterator first, EdgeIterator last, | |
1615 | vertices_size_type n, | |
1616 | const ProcessGroup& pg, | |
1617 | const base_distribution_type& distribution, | |
1618 | const GraphProperty& p = GraphProperty()) | |
1619 | : named_graph_mixin(pg, distribution), | |
1620 | m_local_graph(distribution.block_size(process_id(pg), n), p), | |
1621 | process_group_(pg, boost::parallel::attach_distributed_object()) | |
1622 | { | |
1623 | setup_triggers(); | |
1624 | ||
1625 | typedef typename config_type::VertexListS vertex_list_selector; | |
1626 | initialize(first, last, n, this->distribution(), vertex_list_selector()); | |
1627 | detail::parallel::maybe_initialize_vertex_indices(vertices(base()), | |
1628 | get(vertex_index, base())); | |
1629 | ||
1630 | } | |
1631 | ||
1632 | template <class EdgeIterator, class EdgePropertyIterator> | |
1633 | adjacency_list(EdgeIterator first, EdgeIterator last, | |
1634 | EdgePropertyIterator ep_iter, | |
1635 | vertices_size_type n, | |
1636 | const ProcessGroup& pg, | |
1637 | const base_distribution_type& distribution, | |
1638 | const GraphProperty& p = GraphProperty()) | |
1639 | : named_graph_mixin(pg, distribution), | |
1640 | m_local_graph(this->distribution().block_size(process_id(pg), n), p), | |
1641 | process_group_(pg, boost::parallel::attach_distributed_object()) | |
1642 | { | |
1643 | setup_triggers(); | |
1644 | ||
1645 | typedef typename config_type::VertexListS vertex_list_selector; | |
1646 | initialize(first, last, ep_iter, n, distribution, | |
1647 | vertex_list_selector()); | |
1648 | detail::parallel::maybe_initialize_vertex_indices(vertices(base()), | |
1649 | get(vertex_index, base())); | |
1650 | ||
1651 | } | |
1652 | ||
1653 | ~adjacency_list() | |
1654 | { | |
1655 | synchronize(process_group_); | |
1656 | } | |
1657 | ||
1658 | void clear() | |
1659 | { | |
1660 | base().clear(); | |
1661 | local_edges_.clear(); | |
1662 | named_graph_mixin::clearing_graph(); | |
1663 | } | |
1664 | ||
1665 | void swap(adjacency_list& other) | |
1666 | { | |
1667 | using std::swap; | |
1668 | ||
1669 | base().swap(other); | |
1670 | swap(process_group_, other.process_group_); | |
1671 | } | |
1672 | ||
1673 | static vertex_descriptor null_vertex() | |
1674 | { | |
1675 | return vertex_descriptor(processor_id_type(0), | |
1676 | inherited::null_vertex()); | |
1677 | } | |
1678 | ||
1679 | inherited& base() { return m_local_graph; } | |
1680 | const inherited& base() const { return m_local_graph; } | |
1681 | ||
1682 | processor_id_type processor() const { return process_id(process_group_); } | |
1683 | process_group_type process_group() const { return process_group_.base(); } | |
1684 | ||
1685 | local_edge_list_type& local_edges() { return local_edges_; } | |
1686 | const local_edge_list_type& local_edges() const { return local_edges_; } | |
1687 | ||
1688 | // Redistribute the vertices of the graph by placing each vertex | |
1689 | // v on the processor get(vertex_to_processor, v). | |
1690 | template<typename VertexProcessorMap> | |
1691 | void redistribute(VertexProcessorMap vertex_to_processor); | |
1692 | ||
1693 | // Directly access a vertex or edge bundle | |
1694 | vertex_bundled& operator[](vertex_descriptor v) | |
1695 | { | |
1696 | BOOST_ASSERT(v.owner == processor()); | |
1697 | return base()[v.local]; | |
1698 | } | |
1699 | ||
1700 | const vertex_bundled& operator[](vertex_descriptor v) const | |
1701 | { | |
1702 | BOOST_ASSERT(v.owner == processor()); | |
1703 | return base()[v.local]; | |
1704 | } | |
1705 | ||
1706 | edge_bundled& operator[](edge_descriptor e) | |
1707 | { | |
1708 | BOOST_ASSERT(e.owner() == processor()); | |
1709 | return base()[e.local]; | |
1710 | } | |
1711 | ||
1712 | const edge_bundled& operator[](edge_descriptor e) const | |
1713 | { | |
1714 | BOOST_ASSERT(e.owner() == processor()); | |
1715 | return base()[e.local]; | |
1716 | } | |
1717 | ||
1718 | graph_bundled& operator[](graph_bundle_t) | |
1719 | { return get_property(*this); } | |
1720 | ||
1721 | graph_bundled const& operator[](graph_bundle_t) const | |
1722 | { return get_property(*this); } | |
1723 | ||
1724 | template<typename OStreamConstructibleArchive> | |
1725 | void save(std::string const& filename) const; | |
1726 | ||
1727 | template<typename IStreamConstructibleArchive> | |
1728 | void load(std::string const& filename); | |
1729 | ||
1730 | // Callback that will be invoked whenever a new vertex is added locally | |
1731 | boost::function<void(vertex_descriptor, adjacency_list&)> on_add_vertex; | |
1732 | ||
1733 | // Callback that will be invoked whenever a new edge is added locally | |
1734 | boost::function<void(edge_descriptor, adjacency_list&)> on_add_edge; | |
1735 | ||
1736 | private: | |
1737 | // Request vertex->processor mapping for neighbors <does nothing> | |
1738 | template<typename VertexProcessorMap> | |
1739 | void | |
1740 | request_in_neighbors(vertex_descriptor, | |
1741 | VertexProcessorMap, | |
1742 | directedS) { } | |
1743 | ||
1744 | // Request vertex->processor mapping for neighbors <does nothing> | |
1745 | template<typename VertexProcessorMap> | |
1746 | void | |
1747 | request_in_neighbors(vertex_descriptor, | |
1748 | VertexProcessorMap, | |
1749 | undirectedS) { } | |
1750 | ||
1751 | // Request vertex->processor mapping for neighbors | |
1752 | template<typename VertexProcessorMap> | |
1753 | void | |
1754 | request_in_neighbors(vertex_descriptor v, | |
1755 | VertexProcessorMap vertex_to_processor, | |
1756 | bidirectionalS); | |
1757 | ||
1758 | // Clear the list of in-edges, but don't tell the remote processor | |
1759 | void clear_in_edges_local(vertex_descriptor v, directedS) {} | |
1760 | void clear_in_edges_local(vertex_descriptor v, undirectedS) {} | |
1761 | ||
1762 | void clear_in_edges_local(vertex_descriptor v, bidirectionalS) | |
1763 | { get(vertex_in_edges, base())[v.local].clear(); } | |
1764 | ||
1765 | // Remove in-edges that have migrated <does nothing> | |
1766 | template<typename VertexProcessorMap> | |
1767 | void | |
1768 | remove_migrated_in_edges(vertex_descriptor, | |
1769 | VertexProcessorMap, | |
1770 | directedS) { } | |
1771 | ||
1772 | // Remove in-edges that have migrated <does nothing> | |
1773 | template<typename VertexProcessorMap> | |
1774 | void | |
1775 | remove_migrated_in_edges(vertex_descriptor, | |
1776 | VertexProcessorMap, | |
1777 | undirectedS) { } | |
1778 | ||
1779 | // Remove in-edges that have migrated | |
1780 | template<typename VertexProcessorMap> | |
1781 | void | |
1782 | remove_migrated_in_edges(vertex_descriptor v, | |
1783 | VertexProcessorMap vertex_to_processor, | |
1784 | bidirectionalS); | |
1785 | ||
1786 | // Initialize the graph with the given edge list and vertex | |
1787 | // distribution. This variation works only when | |
1788 | // VertexListS=vecS, and we know how to create remote vertex | |
1789 | // descriptors based solely on the distribution. | |
1790 | template<typename EdgeIterator> | |
1791 | void | |
1792 | initialize(EdgeIterator first, EdgeIterator last, | |
1793 | vertices_size_type, const base_distribution_type& distribution, | |
1794 | vecS); | |
1795 | ||
1796 | // Initialize the graph with the given edge list, edge | |
1797 | // properties, and vertex distribution. This variation works | |
1798 | // only when VertexListS=vecS, and we know how to create remote | |
1799 | // vertex descriptors based solely on the distribution. | |
1800 | template<typename EdgeIterator, typename EdgePropertyIterator> | |
1801 | void | |
1802 | initialize(EdgeIterator first, EdgeIterator last, | |
1803 | EdgePropertyIterator ep_iter, | |
1804 | vertices_size_type, const base_distribution_type& distribution, | |
1805 | vecS); | |
1806 | ||
1807 | // Initialize the graph with the given edge list, edge | |
1808 | // properties, and vertex distribution. | |
1809 | template<typename EdgeIterator, typename EdgePropertyIterator, | |
1810 | typename VertexListS> | |
1811 | void | |
1812 | initialize(EdgeIterator first, EdgeIterator last, | |
1813 | EdgePropertyIterator ep_iter, | |
1814 | vertices_size_type n, | |
1815 | const base_distribution_type& distribution, | |
1816 | VertexListS); | |
1817 | ||
1818 | // Initialize the graph with the given edge list and vertex | |
1819 | // distribution. This is nearly identical to the one below it, | |
1820 | // for which I should be flogged. However, this version does use | |
1821 | // slightly less memory than the version that accepts an edge | |
1822 | // property iterator. | |
1823 | template<typename EdgeIterator, typename VertexListS> | |
1824 | void | |
1825 | initialize(EdgeIterator first, EdgeIterator last, | |
1826 | vertices_size_type n, | |
1827 | const base_distribution_type& distribution, | |
1828 | VertexListS); | |
1829 | ||
1830 | public: | |
1831 | //--------------------------------------------------------------------- | |
1832 | // Build a vertex property instance for the underlying adjacency | |
1833 | // list from the given property instance of the type exposed to | |
1834 | // the user. | |
1835 | base_vertex_property_type | |
1836 | build_vertex_property(const vertex_property_type& p) | |
1837 | { return build_vertex_property(p, directed_selector()); } | |
1838 | ||
1839 | base_vertex_property_type | |
1840 | build_vertex_property(const vertex_property_type& p, directedS) | |
1841 | { | |
1842 | return base_vertex_property_type(p); | |
1843 | } | |
1844 | ||
1845 | base_vertex_property_type | |
1846 | build_vertex_property(const vertex_property_type& p, bidirectionalS) | |
1847 | { | |
1848 | return base_vertex_property_type(in_edge_list_type(), p); | |
1849 | } | |
1850 | ||
1851 | base_vertex_property_type | |
1852 | build_vertex_property(const vertex_property_type& p, undirectedS) | |
1853 | { | |
1854 | return base_vertex_property_type(p); | |
1855 | } | |
1856 | //--------------------------------------------------------------------- | |
1857 | ||
1858 | //--------------------------------------------------------------------- | |
1859 | // Build an edge property instance for the underlying adjacency | |
1860 | // list from the given property instance of the type exposed to | |
1861 | // the user. | |
1862 | base_edge_property_type build_edge_property(const edge_property_type& p) | |
1863 | { return build_edge_property(p, directed_selector()); } | |
1864 | ||
1865 | base_edge_property_type | |
1866 | build_edge_property(const edge_property_type& p, directedS) | |
1867 | { | |
1868 | return base_edge_property_type(0, p); | |
1869 | } | |
1870 | ||
1871 | base_edge_property_type | |
1872 | build_edge_property(const edge_property_type& p, bidirectionalS) | |
1873 | { | |
1874 | return base_edge_property_type(0, p); | |
1875 | } | |
1876 | ||
1877 | base_edge_property_type | |
1878 | build_edge_property(const edge_property_type& p, undirectedS) | |
1879 | { | |
1880 | typedef typename base_edge_property_type::next_type | |
1881 | edge_property_with_id; | |
1882 | return base_edge_property_type(true, edge_property_with_id(0, p)); | |
1883 | } | |
1884 | //--------------------------------------------------------------------- | |
1885 | ||
1886 | //--------------------------------------------------------------------- | |
1887 | // Opposite of above. | |
1888 | edge_property_type split_edge_property(const base_edge_property_type& p) | |
1889 | { return split_edge_property(p, directed_selector()); } | |
1890 | ||
1891 | edge_property_type | |
1892 | split_edge_property(const base_edge_property_type& p, directedS) | |
1893 | { | |
1894 | return p.m_base; | |
1895 | } | |
1896 | ||
1897 | edge_property_type | |
1898 | split_edge_property(const base_edge_property_type& p, bidirectionalS) | |
1899 | { | |
1900 | return p.m_base; | |
1901 | } | |
1902 | ||
1903 | edge_property_type | |
1904 | split_edge_property(const base_edge_property_type& p, undirectedS) | |
1905 | { | |
1906 | return p.m_base.m_base; | |
1907 | } | |
1908 | //--------------------------------------------------------------------- | |
1909 | ||
1910 | /** The set of messages that can be transmitted and received by | |
1911 | * a distributed adjacency list. This list will eventually be | |
1912 | * exhaustive, but is currently quite limited. | |
1913 | */ | |
1914 | enum { | |
1915 | /** | |
1916 | * Request to add or find a vertex with the given vertex | |
1917 | * property. The data will be a vertex_property_type | |
1918 | * structure. | |
1919 | */ | |
1920 | msg_add_vertex_with_property = 0, | |
1921 | ||
1922 | /** | |
1923 | * Request to add or find a vertex with the given vertex | |
1924 | * property, and request that the remote processor return the | |
1925 | * descriptor for the added/found edge. The data will be a | |
1926 | * vertex_property_type structure. | |
1927 | */ | |
1928 | msg_add_vertex_with_property_and_reply, | |
1929 | ||
1930 | /** | |
1931 | * Reply to a msg_add_vertex_* message, containing the local | |
1932 | * vertex descriptor that was added or found. | |
1933 | */ | |
1934 | msg_add_vertex_reply, | |
1935 | ||
1936 | /** | |
1937 | * Request to add an edge remotely. The data will be a | |
1938 | * msg_add_edge_data structure. | |
1939 | */ | |
1940 | msg_add_edge, | |
1941 | ||
1942 | /** | |
1943 | * Request to add an edge remotely. The data will be a | |
1944 | * msg_add_edge_with_property_data structure. | |
1945 | */ | |
1946 | msg_add_edge_with_property, | |
1947 | ||
1948 | /** | |
1949 | * Request to add an edge remotely and reply back with the | |
1950 | * edge descriptor. The data will be a | |
1951 | * msg_add_edge_data structure. | |
1952 | */ | |
1953 | msg_add_edge_with_reply, | |
1954 | ||
1955 | /** | |
1956 | * Request to add an edge remotely and reply back with the | |
1957 | * edge descriptor. The data will be a | |
1958 | * msg_add_edge_with_property_data structure. | |
1959 | */ | |
1960 | msg_add_edge_with_property_and_reply, | |
1961 | ||
1962 | /** | |
1963 | * Reply message responding to an @c msg_add_edge_with_reply | |
1964 | * or @c msg_add_edge_with_property_and_reply messages. The | |
1965 | * data will be a std::pair<edge_descriptor, bool>. | |
1966 | */ | |
1967 | msg_add_edge_reply, | |
1968 | ||
1969 | /** | |
1970 | * Indicates that a nonlocal edge has been created that should | |
1971 | * be added locally. Only valid for bidirectional and | |
1972 | * undirected graphs. The message carries a | |
1973 | * msg_nonlocal_edge_data structure. | |
1974 | */ | |
1975 | msg_nonlocal_edge, | |
1976 | ||
1977 | /** | |
1978 | * Indicates that a remote edge should be removed. This | |
1979 | * message does not exist for directedS graphs but may refer | |
1980 | * to either in-edges or out-edges for undirectedS graphs. | |
1981 | */ | |
1982 | msg_remove_edge, | |
1983 | ||
1984 | /** | |
1985 | * Indicates the number of vertices and edges that will be | |
1986 | * relocated from the source processor to the target | |
1987 | * processor. The data will be a pair<vertices_size_type, | |
1988 | * edges_size_type>. | |
1989 | */ | |
1990 | msg_num_relocated | |
1991 | }; | |
1992 | ||
1993 | typedef detail::parallel::msg_add_edge_data<vertex_descriptor, | |
1994 | local_vertex_descriptor> | |
1995 | msg_add_edge_data; | |
1996 | ||
1997 | typedef detail::parallel::msg_add_edge_with_property_data | |
1998 | <vertex_descriptor, local_vertex_descriptor, | |
1999 | edge_property_type> msg_add_edge_with_property_data; | |
2000 | ||
2001 | typedef boost::detail::parallel::msg_nonlocal_edge_data< | |
2002 | edge_property_type,local_edge_descriptor> msg_nonlocal_edge_data; | |
2003 | ||
2004 | typedef boost::detail::parallel::msg_remove_edge_data<edge_descriptor> | |
2005 | msg_remove_edge_data; | |
2006 | ||
2007 | void send_remove_edge_request(edge_descriptor e) | |
2008 | { | |
2009 | process_id_type dest = e.target_processor; | |
2010 | if (e.target_processor == process_id(process_group_)) | |
2011 | dest = e.source_processor; | |
2012 | send(process_group_, dest, msg_remove_edge, msg_remove_edge_data(e)); | |
2013 | } | |
2014 | ||
2015 | /// Process incoming messages. | |
2016 | void setup_triggers(); | |
2017 | ||
2018 | void | |
2019 | handle_add_vertex_with_property(int source, int tag, | |
2020 | const vertex_property_type&, | |
2021 | trigger_receive_context); | |
2022 | ||
2023 | local_vertex_descriptor | |
2024 | handle_add_vertex_with_property_and_reply(int source, int tag, | |
2025 | const vertex_property_type&, | |
2026 | trigger_receive_context); | |
2027 | ||
2028 | void | |
2029 | handle_add_edge(int source, int tag, const msg_add_edge_data& data, | |
2030 | trigger_receive_context); | |
2031 | ||
2032 | boost::parallel::detail::untracked_pair<edge_descriptor, bool> | |
2033 | handle_add_edge_with_reply(int source, int tag, | |
2034 | const msg_add_edge_data& data, | |
2035 | trigger_receive_context); | |
2036 | ||
2037 | void | |
2038 | handle_add_edge_with_property(int source, int tag, | |
2039 | const msg_add_edge_with_property_data&, | |
2040 | trigger_receive_context); | |
2041 | ||
2042 | boost::parallel::detail::untracked_pair<edge_descriptor, bool> | |
2043 | handle_add_edge_with_property_and_reply | |
2044 | (int source, int tag, const msg_add_edge_with_property_data&, | |
2045 | trigger_receive_context); | |
2046 | ||
2047 | void | |
2048 | handle_nonlocal_edge(int source, int tag, | |
2049 | const msg_nonlocal_edge_data& data, | |
2050 | trigger_receive_context); | |
2051 | ||
2052 | void | |
2053 | handle_remove_edge(int source, int tag, | |
2054 | const msg_remove_edge_data& data, | |
2055 | trigger_receive_context); | |
2056 | ||
2057 | protected: | |
2058 | /** Add an edge (locally) that was received from another | |
2059 | * processor. This operation is a no-op for directed graphs, | |
2060 | * because all edges reside on the local processor. For | |
2061 | * bidirectional graphs, this routine places the edge onto the | |
2062 | * list of incoming edges for the target vertex. For undirected | |
2063 | * graphs, the edge is placed along with all of the other edges | |
2064 | * for the target vertex, but it is marked as a non-local edge | |
2065 | * descriptor. | |
2066 | * | |
2067 | * \todo There is a potential problem here, where we could | |
2068 | * unintentionally allow duplicate edges in undirected graphs | |
2069 | * because the same edge is added on two different processors | |
2070 | * simultaneously. It's not an issue now, because we require | |
2071 | * that the graph allow parallel edges. Once we do support | |
2072 | * containers such as setS or hash_setS that disallow parallel | |
2073 | * edges we will need to deal with this. | |
2074 | */ | |
2075 | void | |
2076 | add_remote_edge(const msg_nonlocal_edge_data&, | |
2077 | processor_id_type, directedS) | |
2078 | { } | |
2079 | ||
2080 | ||
2081 | /** | |
2082 | * \overload | |
2083 | */ | |
2084 | void | |
2085 | add_remote_edge(const msg_nonlocal_edge_data& data, | |
2086 | processor_id_type other_proc, bidirectionalS) | |
2087 | { | |
2088 | typedef detail::parallel::stored_in_edge<local_edge_descriptor> stored_edge; | |
2089 | ||
2090 | stored_edge edge(other_proc, data.e); | |
2091 | local_vertex_descriptor v = target(data.e, base()); | |
2092 | boost::graph_detail::push(get(vertex_in_edges, base())[v], edge); | |
2093 | } | |
2094 | ||
2095 | /** | |
2096 | * \overload | |
2097 | */ | |
2098 | void | |
2099 | add_remote_edge(const msg_nonlocal_edge_data& data, | |
2100 | processor_id_type other_proc, undirectedS) | |
2101 | { | |
2102 | std::pair<local_edge_descriptor, bool> edge = | |
2103 | detail::parallel::add_local_edge(target(data.e, base()), | |
2104 | source(data.e, base()), | |
2105 | build_edge_property(data.get_property()), base()); | |
2106 | BOOST_ASSERT(edge.second); | |
2107 | put(edge_target_processor_id, base(), edge.first, other_proc); | |
2108 | ||
2109 | if (edge.second && on_add_edge) | |
2110 | on_add_edge(edge_descriptor(processor(), other_proc, false, | |
2111 | edge.first), | |
2112 | *this); | |
2113 | } | |
2114 | ||
2115 | void | |
2116 | remove_local_edge(const msg_remove_edge_data&, processor_id_type, | |
2117 | directedS) | |
2118 | { } | |
2119 | ||
2120 | void | |
2121 | remove_local_edge(const msg_remove_edge_data& data, | |
2122 | processor_id_type other_proc, bidirectionalS) | |
2123 | { | |
2124 | /* When the source is local, we first check if the edge still | |
2125 | * exists (it may have been deleted locally) and, if so, | |
2126 | * remove it locally. | |
2127 | */ | |
2128 | vertex_descriptor src = source(data.e, *this); | |
2129 | vertex_descriptor tgt = target(data.e, *this); | |
2130 | ||
2131 | if (src.owner == process_id(process_group_)) { | |
2132 | base_out_edge_iterator ei, ei_end; | |
2133 | for (boost::tie(ei, ei_end) = out_edges(src.local, base()); | |
2134 | ei != ei_end; ++ei) { | |
2135 | // TBD: can't check the descriptor here, because it could | |
2136 | // have changed if we're allowing the removal of | |
2137 | // edges. Egads! | |
2138 | if (tgt.local == target(*ei, base()) | |
2139 | && get(edge_target_processor_id, base(), *ei) == other_proc) | |
2140 | break; | |
2141 | } | |
2142 | ||
2143 | if (ei != ei_end) boost::remove_edge(ei, base()); | |
2144 | ||
2145 | remove_local_edge_from_list(src, tgt, undirectedS()); | |
2146 | } else { | |
2147 | BOOST_ASSERT(tgt.owner == process_id(process_group_)); | |
2148 | in_edge_list_type& in_edges = | |
2149 | get(vertex_in_edges, base())[tgt.local]; | |
2150 | typename in_edge_list_type::iterator ei; | |
2151 | for (ei = in_edges.begin(); ei != in_edges.end(); ++ei) { | |
2152 | if (src.local == source(ei->e, base()) | |
2153 | && src.owner == ei->source_processor) | |
2154 | break; | |
2155 | } | |
2156 | ||
2157 | if (ei != in_edges.end()) in_edges.erase(ei); | |
2158 | } | |
2159 | } | |
2160 | ||
2161 | void | |
2162 | remove_local_edge(const msg_remove_edge_data& data, | |
2163 | processor_id_type other_proc, undirectedS) | |
2164 | { | |
2165 | vertex_descriptor local_vertex = source(data.e, *this); | |
2166 | vertex_descriptor remote_vertex = target(data.e, *this); | |
2167 | if (remote_vertex.owner == process_id(process_group_)) { | |
2168 | using std::swap; | |
2169 | swap(local_vertex, remote_vertex); | |
2170 | } | |
2171 | ||
2172 | // Remove the edge from the out-edge list, if it is there | |
2173 | { | |
2174 | base_out_edge_iterator ei, ei_end; | |
2175 | for (boost::tie(ei, ei_end) = out_edges(local_vertex.local, base()); | |
2176 | ei != ei_end; ++ei) { | |
2177 | // TBD: can't check the descriptor here, because it could | |
2178 | // have changed if we're allowing the removal of | |
2179 | // edges. Egads! | |
2180 | if (remote_vertex.local == target(*ei, base()) | |
2181 | && get(edge_target_processor_id, base(), *ei) == other_proc) | |
2182 | break; | |
2183 | } | |
2184 | ||
2185 | if (ei != ei_end) boost::remove_edge(ei, base()); | |
2186 | } | |
2187 | ||
2188 | remove_local_edge_from_list(local_vertex, remote_vertex, undirectedS()); | |
2189 | } | |
2190 | ||
2191 | public: | |
2192 | void | |
2193 | remove_local_edge_from_list(vertex_descriptor, vertex_descriptor, | |
2194 | directedS) | |
2195 | { | |
2196 | } | |
2197 | ||
2198 | void | |
2199 | remove_local_edge_from_list(vertex_descriptor, vertex_descriptor, | |
2200 | bidirectionalS) | |
2201 | { | |
2202 | } | |
2203 | ||
2204 | void | |
2205 | remove_local_edge_from_list(vertex_descriptor src, vertex_descriptor tgt, | |
2206 | undirectedS) | |
2207 | { | |
2208 | // TBD: At some point we'll be able to improve the speed here | |
2209 | // because we'll know when the edge can't be in the local | |
2210 | // list. | |
2211 | { | |
2212 | typename local_edge_list_type::iterator ei; | |
2213 | for (ei = local_edges_.begin(); ei != local_edges_.end(); ++ei) { | |
2214 | if ((source(*ei, *this) == src | |
2215 | && target(*ei, *this) == tgt) | |
2216 | || (source(*ei, *this) == tgt | |
2217 | && target(*ei, *this) == src)) | |
2218 | break; | |
2219 | } | |
2220 | ||
2221 | if (ei != local_edges_.end()) local_edges_.erase(ei); | |
2222 | } | |
2223 | ||
2224 | } | |
2225 | ||
2226 | private: | |
2227 | /// The local subgraph | |
2228 | inherited m_local_graph; | |
2229 | ||
2230 | /// The process group through which this distributed graph | |
2231 | /// communicates. | |
2232 | process_group_type process_group_; | |
2233 | ||
2234 | // TBD: should only be available for undirected graphs, but for | |
2235 | // now it'll just be empty for directed and bidirectional | |
2236 | // graphs. | |
2237 | local_edge_list_type local_edges_; | |
2238 | }; | |
2239 | ||
2240 | //------------------------------------------------------------------------ | |
2241 | // Lazy addition of vertices | |
2242 | template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS> | |
2243 | struct PBGL_DISTRIB_ADJLIST_TYPE::lazy_add_vertex_with_property | |
2244 | { | |
2245 | /// Construct a lazy request to add a vertex | |
2246 | lazy_add_vertex_with_property(adjacency_list& self, | |
2247 | const vertex_property_type& property) | |
2248 | : self(self), property(property), committed(false) { } | |
2249 | ||
2250 | /// Copying a lazy_add_vertex_with_property transfers the | |
2251 | /// responsibility for adding the vertex to the newly-constructed | |
2252 | /// object. | |
2253 | lazy_add_vertex_with_property(const lazy_add_vertex_with_property& other) | |
2254 | : self(other.self), property(other.property), | |
2255 | committed(other.committed) | |
2256 | { | |
2257 | other.committed = true; | |
2258 | } | |
2259 | ||
2260 | /// If the vertex has not yet been added, add the vertex but don't | |
2261 | /// wait for a reply. | |
2262 | ~lazy_add_vertex_with_property(); | |
2263 | ||
2264 | /// Returns commit(). | |
2265 | operator vertex_descriptor() const { return commit(); } | |
2266 | ||
2267 | // Add the vertex. This operation will block if the vertex is | |
2268 | // being added remotely. | |
2269 | vertex_descriptor commit() const; | |
2270 | ||
2271 | protected: | |
2272 | adjacency_list& self; | |
2273 | vertex_property_type property; | |
2274 | mutable bool committed; | |
2275 | ||
2276 | private: | |
2277 | // No copy-assignment semantics | |
2278 | void operator=(lazy_add_vertex_with_property&); | |
2279 | }; | |
2280 | ||
2281 | template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS> | |
2282 | PBGL_DISTRIB_ADJLIST_TYPE::lazy_add_vertex_with_property:: | |
2283 | ~lazy_add_vertex_with_property() | |
2284 | { | |
2285 | /// If this vertex has already been created or will be created by | |
2286 | /// someone else, or if someone threw an exception, we will not | |
2287 | /// create the vertex now. | |
2288 | if (committed || std::uncaught_exception()) | |
2289 | return; | |
2290 | ||
2291 | committed = true; | |
2292 | ||
2293 | process_id_type owner | |
2294 | = static_cast<graph_type&>(self).owner_by_property(property); | |
2295 | if (owner == self.processor()) { | |
2296 | /// Add the vertex locally. | |
2297 | vertex_descriptor v(owner, | |
2298 | add_vertex(self.build_vertex_property(property), | |
2299 | self.base())); | |
2300 | if (self.on_add_vertex) | |
2301 | self.on_add_vertex(v, self); | |
2302 | } | |
2303 | else | |
2304 | /// Ask the owner of this new vertex to add the vertex. We | |
2305 | /// don't need a reply. | |
2306 | send(self.process_group_, owner, msg_add_vertex_with_property, | |
2307 | property); | |
2308 | } | |
2309 | ||
2310 | template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS> | |
2311 | typename PBGL_DISTRIB_ADJLIST_TYPE::vertex_descriptor | |
2312 | PBGL_DISTRIB_ADJLIST_TYPE::lazy_add_vertex_with_property:: | |
2313 | commit() const | |
2314 | { | |
2315 | BOOST_ASSERT(!this->committed); | |
2316 | this->committed = true; | |
2317 | ||
2318 | process_id_type owner | |
2319 | = static_cast<graph_type&>(self).owner_by_property(property); | |
2320 | local_vertex_descriptor local_v; | |
2321 | if (owner == self.processor()) | |
2322 | /// Add the vertex locally. | |
2323 | local_v = add_vertex(self.build_vertex_property(property), | |
2324 | self.base()); | |
2325 | else { | |
2326 | // Request that the remote process add the vertex immediately | |
2327 | send_oob_with_reply(self.process_group_, owner, | |
2328 | msg_add_vertex_with_property_and_reply, property, | |
2329 | local_v); | |
2330 | } | |
2331 | ||
2332 | vertex_descriptor v(owner, local_v); | |
2333 | if (self.on_add_vertex) | |
2334 | self.on_add_vertex(v, self); | |
2335 | ||
2336 | // Build the full vertex descriptor to return | |
2337 | return v; | |
2338 | } | |
2339 | ||
2340 | ||
2341 | /** | |
2342 | * Data structure returned from add_edge that will "lazily" add | |
2343 | * the edge, either when it is converted to a | |
2344 | * @c pair<edge_descriptor, bool> or when the most recent copy has | |
2345 | * been destroyed. | |
2346 | */ | |
2347 | template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS> | |
2348 | struct PBGL_DISTRIB_ADJLIST_TYPE::lazy_add_edge | |
2349 | { | |
2350 | /// Construct a lazy request to add an edge | |
2351 | lazy_add_edge(adjacency_list& self, | |
2352 | vertex_descriptor source, vertex_descriptor target) | |
2353 | : self(self), source(source), target(target), committed(false) { } | |
2354 | ||
2355 | /// Copying a lazy_add_edge transfers the responsibility for | |
2356 | /// adding the edge to the newly-constructed object. | |
2357 | lazy_add_edge(const lazy_add_edge& other) | |
2358 | : self(other.self), source(other.source), target(other.target), | |
2359 | committed(other.committed) | |
2360 | { | |
2361 | other.committed = true; | |
2362 | } | |
2363 | ||
2364 | /// If the edge has not yet been added, add the edge but don't | |
2365 | /// wait for a reply. | |
2366 | ~lazy_add_edge(); | |
2367 | ||
2368 | /// Returns commit(). | |
2369 | operator std::pair<edge_descriptor, bool>() const { return commit(); } | |
2370 | ||
2371 | // Add the edge. This operation will block if a remote edge is | |
2372 | // being added. | |
2373 | std::pair<edge_descriptor, bool> commit() const; | |
2374 | ||
2375 | protected: | |
2376 | std::pair<edge_descriptor, bool> | |
2377 | add_local_edge(const edge_property_type& property, directedS) const; | |
2378 | ||
2379 | std::pair<edge_descriptor, bool> | |
2380 | add_local_edge(const edge_property_type& property, bidirectionalS) const; | |
2381 | ||
2382 | std::pair<edge_descriptor, bool> | |
2383 | add_local_edge(const edge_property_type& property, undirectedS) const; | |
2384 | ||
2385 | adjacency_list& self; | |
2386 | vertex_descriptor source; | |
2387 | vertex_descriptor target; | |
2388 | mutable bool committed; | |
2389 | ||
2390 | private: | |
2391 | // No copy-assignment semantics | |
2392 | void operator=(lazy_add_edge&); | |
2393 | }; | |
2394 | ||
2395 | template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS> | |
2396 | PBGL_DISTRIB_ADJLIST_TYPE::lazy_add_edge::~lazy_add_edge() | |
2397 | { | |
2398 | /// If this edge has already been created or will be created by | |
2399 | /// someone else, or if someone threw an exception, we will not | |
2400 | /// create the edge now. | |
2401 | if (committed || std::uncaught_exception()) | |
2402 | return; | |
2403 | ||
2404 | committed = true; | |
2405 | ||
2406 | if (source.owner == self.processor()) | |
2407 | this->add_local_edge(edge_property_type(), DirectedS()); | |
2408 | else | |
2409 | // Request that the remote processor add an edge and, but | |
2410 | // don't wait for a reply. | |
2411 | send(self.process_group_, source.owner, msg_add_edge, | |
2412 | msg_add_edge_data(source, target)); | |
2413 | } | |
2414 | ||
2415 | template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS> | |
2416 | std::pair<typename PBGL_DISTRIB_ADJLIST_TYPE::edge_descriptor, bool> | |
2417 | PBGL_DISTRIB_ADJLIST_TYPE::lazy_add_edge::commit() const | |
2418 | { | |
2419 | BOOST_ASSERT(!committed); | |
2420 | committed = true; | |
2421 | ||
2422 | if (source.owner == self.processor()) | |
2423 | return this->add_local_edge(edge_property_type(), DirectedS()); | |
2424 | else { | |
2425 | // Request that the remote processor add an edge | |
2426 | boost::parallel::detail::untracked_pair<edge_descriptor, bool> result; | |
2427 | send_oob_with_reply(self.process_group_, source.owner, | |
2428 | msg_add_edge_with_reply, | |
2429 | msg_add_edge_data(source, target), result); | |
2430 | return result; | |
2431 | } | |
2432 | } | |
2433 | ||
2434 | // Add a local edge into a directed graph | |
2435 | template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS> | |
2436 | std::pair<typename PBGL_DISTRIB_ADJLIST_TYPE::edge_descriptor, bool> | |
2437 | PBGL_DISTRIB_ADJLIST_TYPE::lazy_add_edge:: | |
2438 | add_local_edge(const edge_property_type& property, directedS) const | |
2439 | { | |
2440 | // Add the edge to the local part of the graph | |
2441 | std::pair<local_edge_descriptor, bool> inserted = | |
2442 | detail::parallel::add_local_edge(source.local, target.local, | |
2443 | self.build_edge_property(property), | |
2444 | self.base()); | |
2445 | ||
2446 | if (inserted.second) | |
2447 | // Keep track of the owner of the target | |
2448 | put(edge_target_processor_id, self.base(), inserted.first, | |
2449 | target.owner); | |
2450 | ||
2451 | // Compose the edge descriptor and return the result | |
2452 | edge_descriptor e(source.owner, target.owner, true, inserted.first); | |
2453 | ||
2454 | // Trigger the on_add_edge event | |
2455 | if (inserted.second && self.on_add_edge) | |
2456 | self.on_add_edge(e, self); | |
2457 | ||
2458 | return std::pair<edge_descriptor, bool>(e, inserted.second); | |
2459 | } | |
2460 | ||
2461 | template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS> | |
2462 | std::pair<typename PBGL_DISTRIB_ADJLIST_TYPE::edge_descriptor, bool> | |
2463 | PBGL_DISTRIB_ADJLIST_TYPE::lazy_add_edge:: | |
2464 | add_local_edge(const edge_property_type& property, bidirectionalS) const | |
2465 | { | |
2466 | // Add the directed edge. | |
2467 | std::pair<edge_descriptor, bool> result | |
2468 | = this->add_local_edge(property, directedS()); | |
2469 | ||
2470 | if (result.second) { | |
2471 | if (target.owner == self.processor()) { | |
2472 | // Edge is local, so add the stored edge to the in_edges list | |
2473 | typedef detail::parallel::stored_in_edge<local_edge_descriptor> | |
2474 | stored_edge; | |
2475 | ||
2476 | stored_edge e(self.processor(), result.first.local); | |
2477 | boost::graph_detail::push(get(vertex_in_edges, | |
2478 | self.base())[target.local], e); | |
2479 | } | |
2480 | else { | |
2481 | // Edge is remote, so notify the target's owner that an edge | |
2482 | // has been added. | |
2483 | if (self.process_group_.trigger_context() == boost::parallel::trc_out_of_band) | |
2484 | send_oob(self.process_group_, target.owner, msg_nonlocal_edge, | |
2485 | msg_nonlocal_edge_data(result.first.local, property)); | |
2486 | else | |
2487 | send(self.process_group_, target.owner, msg_nonlocal_edge, | |
2488 | msg_nonlocal_edge_data(result.first.local, property)); | |
2489 | } | |
2490 | } | |
2491 | ||
2492 | return result; | |
2493 | } | |
2494 | ||
2495 | template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS> | |
2496 | std::pair<typename PBGL_DISTRIB_ADJLIST_TYPE::edge_descriptor, bool> | |
2497 | PBGL_DISTRIB_ADJLIST_TYPE::lazy_add_edge:: | |
2498 | add_local_edge(const edge_property_type& property, undirectedS) const | |
2499 | { | |
2500 | // Add the directed edge | |
2501 | std::pair<edge_descriptor, bool> result | |
2502 | = this->add_local_edge(property, directedS()); | |
2503 | ||
2504 | if (result.second) { | |
2505 | if (target.owner == self.processor()) { | |
2506 | // Edge is local, so add the new edge to the list | |
2507 | ||
2508 | // TODO: This is not what we want to do for an undirected | |
2509 | // edge, because we haven't linked the source and target's | |
2510 | // representations of those edges. | |
2511 | local_edge_descriptor return_edge = | |
2512 | detail::parallel::add_local_edge(target.local, source.local, | |
2513 | self.build_edge_property(property), | |
2514 | self.base()).first; | |
2515 | ||
2516 | put(edge_target_processor_id, self.base(), return_edge, | |
2517 | source.owner); | |
2518 | } | |
2519 | else { | |
2520 | // Edge is remote, so notify the target's owner that an edge | |
2521 | // has been added. | |
2522 | if (self.process_group_.trigger_context() == boost::parallel::trc_out_of_band) | |
2523 | send_oob(self.process_group_, target.owner, msg_nonlocal_edge, | |
2524 | msg_nonlocal_edge_data(result.first.local, property)); | |
2525 | else | |
2526 | send(self.process_group_, target.owner, msg_nonlocal_edge, | |
2527 | msg_nonlocal_edge_data(result.first.local, property)); | |
2528 | ||
2529 | } | |
2530 | ||
2531 | // Add this edge to the list of local edges | |
2532 | graph_detail::push(self.local_edges(), result.first); | |
2533 | } | |
2534 | ||
2535 | return result; | |
2536 | } | |
2537 | ||
2538 | ||
2539 | /** | |
2540 | * Data structure returned from add_edge that will "lazily" add | |
2541 | * the edge with its property, either when it is converted to a | |
2542 | * pair<edge_descriptor, bool> or when the most recent copy has | |
2543 | * been destroyed. | |
2544 | */ | |
2545 | template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS> | |
2546 | struct PBGL_DISTRIB_ADJLIST_TYPE::lazy_add_edge_with_property | |
2547 | : lazy_add_edge | |
2548 | { | |
2549 | /// Construct a lazy request to add an edge | |
2550 | lazy_add_edge_with_property(adjacency_list& self, | |
2551 | vertex_descriptor source, | |
2552 | vertex_descriptor target, | |
2553 | const edge_property_type& property) | |
2554 | : lazy_add_edge(self, source, target), property(property) { } | |
2555 | ||
2556 | /// Copying a lazy_add_edge transfers the responsibility for | |
2557 | /// adding the edge to the newly-constructed object. | |
2558 | lazy_add_edge_with_property(const lazy_add_edge& other) | |
2559 | : lazy_add_edge(other), property(other.property) { } | |
2560 | ||
2561 | /// If the edge has not yet been added, add the edge but don't | |
2562 | /// wait for a reply. | |
2563 | ~lazy_add_edge_with_property(); | |
2564 | ||
2565 | /// Returns commit(). | |
2566 | operator std::pair<edge_descriptor, bool>() const { return commit(); } | |
2567 | ||
2568 | // Add the edge. This operation will block if a remote edge is | |
2569 | // being added. | |
2570 | std::pair<edge_descriptor, bool> commit() const; | |
2571 | ||
2572 | private: | |
2573 | // No copy-assignment semantics | |
2574 | void operator=(lazy_add_edge_with_property&); | |
2575 | ||
2576 | edge_property_type property; | |
2577 | }; | |
2578 | ||
2579 | template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS> | |
2580 | PBGL_DISTRIB_ADJLIST_TYPE::lazy_add_edge_with_property:: | |
2581 | ~lazy_add_edge_with_property() | |
2582 | { | |
2583 | /// If this edge has already been created or will be created by | |
2584 | /// someone else, or if someone threw an exception, we will not | |
2585 | /// create the edge now. | |
2586 | if (this->committed || std::uncaught_exception()) | |
2587 | return; | |
2588 | ||
2589 | this->committed = true; | |
2590 | ||
2591 | if (this->source.owner == this->self.processor()) | |
2592 | // Add a local edge | |
2593 | this->add_local_edge(property, DirectedS()); | |
2594 | else | |
2595 | // Request that the remote processor add an edge and, but | |
2596 | // don't wait for a reply. | |
2597 | send(this->self.process_group_, this->source.owner, | |
2598 | msg_add_edge_with_property, | |
2599 | msg_add_edge_with_property_data(this->source, this->target, | |
2600 | property)); | |
2601 | } | |
2602 | ||
2603 | template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS> | |
2604 | std::pair<typename PBGL_DISTRIB_ADJLIST_TYPE::edge_descriptor, bool> | |
2605 | PBGL_DISTRIB_ADJLIST_TYPE::lazy_add_edge_with_property:: | |
2606 | commit() const | |
2607 | { | |
2608 | BOOST_ASSERT(!this->committed); | |
2609 | this->committed = true; | |
2610 | ||
2611 | if (this->source.owner == this->self.processor()) | |
2612 | // Add a local edge | |
2613 | return this->add_local_edge(property, DirectedS()); | |
2614 | else { | |
2615 | // Request that the remote processor add an edge | |
2616 | boost::parallel::detail::untracked_pair<edge_descriptor, bool> result; | |
2617 | send_oob_with_reply(this->self.process_group_, this->source.owner, | |
2618 | msg_add_edge_with_property_and_reply, | |
2619 | msg_add_edge_with_property_data(this->source, | |
2620 | this->target, | |
2621 | property), | |
2622 | result); | |
2623 | return result; | |
2624 | } | |
2625 | } | |
2626 | ||
2627 | ||
2628 | /** | |
2629 | * Returns the set of vertices local to this processor. Note that | |
2630 | * although this routine matches a valid expression of a | |
2631 | * VertexListGraph, it does not meet the semantic requirements of | |
2632 | * VertexListGraph because it returns only local vertices (not all | |
2633 | * vertices). | |
2634 | */ | |
2635 | template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS> | |
2636 | std::pair<typename PBGL_DISTRIB_ADJLIST_TYPE | |
2637 | ::vertex_iterator, | |
2638 | typename PBGL_DISTRIB_ADJLIST_TYPE | |
2639 | ::vertex_iterator> | |
2640 | vertices(const PBGL_DISTRIB_ADJLIST_TYPE& g) | |
2641 | { | |
2642 | typedef typename PBGL_DISTRIB_ADJLIST_TYPE | |
2643 | ::vertex_descriptor Vertex; | |
2644 | ||
2645 | typedef typename Vertex::generator generator; | |
2646 | ||
2647 | return std::make_pair(make_transform_iterator(vertices(g.base()).first, | |
2648 | generator(g.processor())), | |
2649 | make_transform_iterator(vertices(g.base()).second, | |
2650 | generator(g.processor()))); | |
2651 | } | |
2652 | ||
2653 | /** | |
2654 | * Returns the number of vertices local to this processor. Note that | |
2655 | * although this routine matches a valid expression of a | |
2656 | * VertexListGraph, it does not meet the semantic requirements of | |
2657 | * VertexListGraph because it returns only a count of local vertices | |
2658 | * (not all vertices). | |
2659 | */ | |
2660 | template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS> | |
2661 | typename PBGL_DISTRIB_ADJLIST_TYPE | |
2662 | ::vertices_size_type | |
2663 | num_vertices(const PBGL_DISTRIB_ADJLIST_TYPE& g) | |
2664 | { | |
2665 | return num_vertices(g.base()); | |
2666 | } | |
2667 | ||
2668 | /*************************************************************************** | |
2669 | * Implementation of Incidence Graph concept | |
2670 | ***************************************************************************/ | |
2671 | /** | |
2672 | * Returns the source of edge @param e in @param g. | |
2673 | */ | |
2674 | template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS, typename Edge> | |
2675 | typename PBGL_DISTRIB_ADJLIST_TYPE::vertex_descriptor | |
2676 | source(const detail::parallel::edge_descriptor<Edge>& e, | |
2677 | const PBGL_DISTRIB_ADJLIST_TYPE& g) | |
2678 | { | |
2679 | typedef typename PBGL_DISTRIB_ADJLIST_TYPE | |
2680 | ::vertex_descriptor Vertex; | |
2681 | return Vertex(e.source_processor, source(e.local, g.base())); | |
2682 | } | |
2683 | ||
2684 | /** | |
2685 | * Returns the target of edge @param e in @param g. | |
2686 | */ | |
2687 | template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS, typename Edge> | |
2688 | typename PBGL_DISTRIB_ADJLIST_TYPE::vertex_descriptor | |
2689 | target(const detail::parallel::edge_descriptor<Edge>& e, | |
2690 | const PBGL_DISTRIB_ADJLIST_TYPE& g) | |
2691 | { | |
2692 | typedef typename PBGL_DISTRIB_ADJLIST_TYPE | |
2693 | ::vertex_descriptor Vertex; | |
2694 | return Vertex(e.target_processor, target(e.local, g.base())); | |
2695 | } | |
2696 | ||
2697 | /** | |
2698 | * Return the set of edges outgoing from a particular vertex. The | |
2699 | * vertex @param v must be local to the processor executing this | |
2700 | * routine. | |
2701 | */ | |
2702 | template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS> | |
2703 | std::pair<typename PBGL_DISTRIB_ADJLIST_TYPE::out_edge_iterator, | |
2704 | typename PBGL_DISTRIB_ADJLIST_TYPE::out_edge_iterator> | |
2705 | out_edges(typename PBGL_DISTRIB_ADJLIST_TYPE::vertex_descriptor v, | |
2706 | const PBGL_DISTRIB_ADJLIST_TYPE& g) | |
2707 | { | |
2708 | BOOST_ASSERT(v.owner == g.processor()); | |
2709 | ||
2710 | typedef PBGL_DISTRIB_ADJLIST_TYPE impl; | |
2711 | typedef typename impl::out_edge_generator generator; | |
2712 | ||
2713 | return std::make_pair( | |
2714 | make_transform_iterator(out_edges(v.local, g.base()).first, | |
2715 | generator(g)), | |
2716 | make_transform_iterator(out_edges(v.local, g.base()).second, | |
2717 | generator(g))); | |
2718 | } | |
2719 | ||
2720 | /** | |
2721 | * Return the number of edges outgoing from a particular vertex. The | |
2722 | * vertex @param v must be local to the processor executing this | |
2723 | * routine. | |
2724 | */ | |
2725 | template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS> | |
2726 | typename PBGL_DISTRIB_ADJLIST_TYPE::degree_size_type | |
2727 | out_degree(typename PBGL_DISTRIB_ADJLIST_TYPE::vertex_descriptor v, | |
2728 | const PBGL_DISTRIB_ADJLIST_TYPE& g) | |
2729 | { | |
2730 | BOOST_ASSERT(v.owner == g.processor()); | |
2731 | ||
2732 | return out_degree(v.local, g.base()); | |
2733 | } | |
2734 | ||
2735 | /*************************************************************************** | |
2736 | * Implementation of Bidirectional Graph concept | |
2737 | ***************************************************************************/ | |
2738 | /** | |
2739 | * Returns the set of edges incoming to a particular vertex. The | |
2740 | * vertex @param v must be local to the processor executing this | |
2741 | * routine. | |
2742 | */ | |
2743 | template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS_CONFIG> | |
2744 | std::pair<typename PBGL_DISTRIB_ADJLIST_TYPE_CONFIG(bidirectionalS) | |
2745 | ::in_edge_iterator, | |
2746 | typename PBGL_DISTRIB_ADJLIST_TYPE_CONFIG(bidirectionalS) | |
2747 | ::in_edge_iterator> | |
2748 | in_edges(typename PBGL_DISTRIB_ADJLIST_TYPE_CONFIG(bidirectionalS) | |
2749 | ::vertex_descriptor v, | |
2750 | const PBGL_DISTRIB_ADJLIST_TYPE_CONFIG(bidirectionalS)& g) | |
2751 | { | |
2752 | BOOST_ASSERT(v.owner == g.processor()); | |
2753 | ||
2754 | typedef PBGL_DISTRIB_ADJLIST_TYPE_CONFIG(bidirectionalS) impl; | |
2755 | typedef typename impl::inherited base_graph_type; | |
2756 | typedef typename impl::in_edge_generator generator; | |
2757 | ||
2758 | ||
2759 | typename property_map<base_graph_type, vertex_in_edges_t>::const_type | |
2760 | in_edges = get(vertex_in_edges, g.base()); | |
2761 | ||
2762 | return std::make_pair(make_transform_iterator(in_edges[v.local].begin(), | |
2763 | generator(g)), | |
2764 | make_transform_iterator(in_edges[v.local].end(), | |
2765 | generator(g))); | |
2766 | } | |
2767 | ||
2768 | /** | |
2769 | * \overload | |
2770 | */ | |
2771 | template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS_CONFIG> | |
2772 | std::pair<typename PBGL_DISTRIB_ADJLIST_TYPE_CONFIG(undirectedS) | |
2773 | ::in_edge_iterator, | |
2774 | typename PBGL_DISTRIB_ADJLIST_TYPE_CONFIG(undirectedS) | |
2775 | ::in_edge_iterator> | |
2776 | in_edges(typename PBGL_DISTRIB_ADJLIST_TYPE_CONFIG(undirectedS) | |
2777 | ::vertex_descriptor v, | |
2778 | const PBGL_DISTRIB_ADJLIST_TYPE_CONFIG(undirectedS)& g) | |
2779 | { | |
2780 | BOOST_ASSERT(v.owner == g.processor()); | |
2781 | ||
2782 | typedef PBGL_DISTRIB_ADJLIST_TYPE_CONFIG(undirectedS) impl; | |
2783 | typedef typename impl::in_edge_generator generator; | |
2784 | ||
2785 | return std::make_pair( | |
2786 | make_transform_iterator(out_edges(v.local, g.base()).first, | |
2787 | generator(g)), | |
2788 | make_transform_iterator(out_edges(v.local, g.base()).second, | |
2789 | generator(g))); | |
2790 | } | |
2791 | ||
2792 | /** | |
2793 | * Returns the number of edges incoming to a particular vertex. The | |
2794 | * vertex @param v must be local to the processor executing this | |
2795 | * routine. | |
2796 | */ | |
2797 | template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS_CONFIG> | |
2798 | typename PBGL_DISTRIB_ADJLIST_TYPE_CONFIG(bidirectionalS)::degree_size_type | |
2799 | in_degree(typename PBGL_DISTRIB_ADJLIST_TYPE_CONFIG(bidirectionalS) | |
2800 | ::vertex_descriptor v, | |
2801 | const PBGL_DISTRIB_ADJLIST_TYPE_CONFIG(bidirectionalS)& g) | |
2802 | { | |
2803 | BOOST_ASSERT(v.owner == g.processor()); | |
2804 | ||
2805 | return get(vertex_in_edges, g.base())[v.local].size(); | |
2806 | } | |
2807 | ||
2808 | /** | |
2809 | * \overload | |
2810 | */ | |
2811 | template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS_CONFIG> | |
2812 | typename PBGL_DISTRIB_ADJLIST_TYPE_CONFIG(undirectedS)::degree_size_type | |
2813 | in_degree(typename PBGL_DISTRIB_ADJLIST_TYPE_CONFIG(undirectedS) | |
2814 | ::vertex_descriptor v, | |
2815 | const PBGL_DISTRIB_ADJLIST_TYPE_CONFIG(undirectedS)& g) | |
2816 | { | |
2817 | BOOST_ASSERT(v.owner == g.processor()); | |
2818 | ||
2819 | return out_degree(v.local, g.base()); | |
2820 | } | |
2821 | ||
2822 | /** | |
2823 | * Returns the number of edges incident on the given vertex. The | |
2824 | * vertex @param v must be local to the processor executing this | |
2825 | * routine. | |
2826 | */ | |
2827 | template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS_CONFIG> | |
2828 | typename PBGL_DISTRIB_ADJLIST_TYPE_CONFIG(undirectedS) | |
2829 | ::degree_size_type | |
2830 | degree(typename PBGL_DISTRIB_ADJLIST_TYPE_CONFIG(undirectedS) | |
2831 | ::vertex_descriptor v, | |
2832 | const PBGL_DISTRIB_ADJLIST_TYPE_CONFIG(undirectedS)& g) | |
2833 | { | |
2834 | BOOST_ASSERT(v.owner == g.processor()); | |
2835 | return out_degree(v.local, g.base()); | |
2836 | } | |
2837 | ||
2838 | /** | |
2839 | * \overload | |
2840 | */ | |
2841 | template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS_CONFIG> | |
2842 | typename PBGL_DISTRIB_ADJLIST_TYPE_CONFIG(bidirectionalS) | |
2843 | ::degree_size_type | |
2844 | degree(typename PBGL_DISTRIB_ADJLIST_TYPE_CONFIG(bidirectionalS) | |
2845 | ::vertex_descriptor v, | |
2846 | const PBGL_DISTRIB_ADJLIST_TYPE_CONFIG(bidirectionalS)& g) | |
2847 | { | |
2848 | BOOST_ASSERT(v.owner == g.processor()); | |
2849 | return out_degree(v, g) + in_degree(v, g); | |
2850 | } | |
2851 | ||
2852 | template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS> | |
2853 | typename PBGL_DISTRIB_ADJLIST_TYPE::edges_size_type | |
2854 | num_edges(const PBGL_DISTRIB_ADJLIST_TYPE& g) | |
2855 | { | |
2856 | return num_edges(g.base()); | |
2857 | } | |
2858 | ||
2859 | template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS_CONFIG> | |
2860 | typename PBGL_DISTRIB_ADJLIST_TYPE_CONFIG(undirectedS)::edges_size_type | |
2861 | num_edges(const PBGL_DISTRIB_ADJLIST_TYPE_CONFIG(undirectedS)& g) | |
2862 | { | |
2863 | return g.local_edges().size(); | |
2864 | } | |
2865 | ||
2866 | template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS> | |
2867 | std::pair< | |
2868 | typename PBGL_DISTRIB_ADJLIST_TYPE::edge_iterator, | |
2869 | typename PBGL_DISTRIB_ADJLIST_TYPE::edge_iterator> | |
2870 | edges(const PBGL_DISTRIB_ADJLIST_TYPE& g) | |
2871 | { | |
2872 | typedef PBGL_DISTRIB_ADJLIST_TYPE impl; | |
2873 | typedef typename impl::out_edge_generator generator; | |
2874 | ||
2875 | return std::make_pair(make_transform_iterator(edges(g.base()).first, | |
2876 | generator(g)), | |
2877 | make_transform_iterator(edges(g.base()).second, | |
2878 | generator(g))); | |
2879 | } | |
2880 | ||
2881 | template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS_CONFIG> | |
2882 | std::pair< | |
2883 | typename PBGL_DISTRIB_ADJLIST_TYPE_CONFIG(undirectedS)::edge_iterator, | |
2884 | typename PBGL_DISTRIB_ADJLIST_TYPE_CONFIG(undirectedS)::edge_iterator> | |
2885 | edges(const PBGL_DISTRIB_ADJLIST_TYPE_CONFIG(undirectedS)& g) | |
2886 | { | |
2887 | return std::make_pair(g.local_edges().begin(), g.local_edges().end()); | |
2888 | } | |
2889 | ||
2890 | template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS> | |
2891 | inline | |
2892 | typename PBGL_DISTRIB_ADJLIST_TYPE::vertex_descriptor | |
2893 | vertex(typename PBGL_DISTRIB_ADJLIST_TYPE::vertices_size_type n, | |
2894 | const PBGL_DISTRIB_ADJLIST_TYPE& g) | |
2895 | { | |
2896 | typedef typename PBGL_DISTRIB_ADJLIST_TYPE::vertex_descriptor | |
2897 | vertex_descriptor; | |
2898 | ||
2899 | return vertex_descriptor(g.distribution()(n), g.distribution().local(n)); | |
2900 | } | |
2901 | ||
2902 | /*************************************************************************** | |
2903 | * Access to particular edges | |
2904 | ***************************************************************************/ | |
2905 | template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS_CONFIG> | |
2906 | std::pair< | |
2907 | typename PBGL_DISTRIB_ADJLIST_TYPE_CONFIG(directedS)::edge_descriptor, | |
2908 | bool | |
2909 | > | |
2910 | edge(typename PBGL_DISTRIB_ADJLIST_TYPE_CONFIG(directedS)::vertex_descriptor u, | |
2911 | typename PBGL_DISTRIB_ADJLIST_TYPE_CONFIG(directedS)::vertex_descriptor v, | |
2912 | const PBGL_DISTRIB_ADJLIST_TYPE_CONFIG(directedS)& g) | |
2913 | { | |
2914 | typedef typename PBGL_DISTRIB_ADJLIST_TYPE_CONFIG(directedS) | |
2915 | ::edge_descriptor edge_descriptor; | |
2916 | ||
2917 | // For directed graphs, u must be local | |
2918 | BOOST_ASSERT(u.owner == process_id(g.process_group())); | |
2919 | ||
2920 | typename PBGL_DISTRIB_ADJLIST_TYPE_CONFIG(directedS) | |
2921 | ::out_edge_iterator ei, ei_end; | |
2922 | for (boost::tie(ei, ei_end) = out_edges(u, g); ei != ei_end; ++ei) { | |
2923 | if (target(*ei, g) == v) return std::make_pair(*ei, true); | |
2924 | } | |
2925 | return std::make_pair(edge_descriptor(), false); | |
2926 | } | |
2927 | ||
2928 | template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS> | |
2929 | std::pair< | |
2930 | typename PBGL_DISTRIB_ADJLIST_TYPE::edge_descriptor, | |
2931 | bool | |
2932 | > | |
2933 | edge(typename PBGL_DISTRIB_ADJLIST_TYPE::vertex_descriptor u, | |
2934 | typename PBGL_DISTRIB_ADJLIST_TYPE::vertex_descriptor v, | |
2935 | const PBGL_DISTRIB_ADJLIST_TYPE& g) | |
2936 | { | |
2937 | typedef typename PBGL_DISTRIB_ADJLIST_TYPE | |
2938 | ::edge_descriptor edge_descriptor; | |
2939 | ||
2940 | // For bidirectional and undirected graphs, u must be local or v | |
2941 | // must be local | |
2942 | if (u.owner == process_id(g.process_group())) { | |
2943 | typename PBGL_DISTRIB_ADJLIST_TYPE::out_edge_iterator ei, ei_end; | |
2944 | for (boost::tie(ei, ei_end) = out_edges(u, g); ei != ei_end; ++ei) { | |
2945 | if (target(*ei, g) == v) return std::make_pair(*ei, true); | |
2946 | } | |
2947 | return std::make_pair(edge_descriptor(), false); | |
2948 | } else if (v.owner == process_id(g.process_group())) { | |
2949 | typename PBGL_DISTRIB_ADJLIST_TYPE::in_edge_iterator ei, ei_end; | |
2950 | for (boost::tie(ei, ei_end) = in_edges(v, g); ei != ei_end; ++ei) { | |
2951 | if (source(*ei, g) == u) return std::make_pair(*ei, true); | |
2952 | } | |
2953 | return std::make_pair(edge_descriptor(), false); | |
2954 | } else { | |
2955 | BOOST_ASSERT(false); | |
2956 | abort(); | |
2957 | } | |
2958 | } | |
2959 | ||
2960 | #if 0 | |
2961 | // TBD: not yet supported | |
2962 | std::pair<out_edge_iterator, out_edge_iterator> | |
2963 | edge_range(vertex_descriptor u, vertex_descriptor v, | |
2964 | const adjacency_list& g); | |
2965 | #endif | |
2966 | ||
2967 | /*************************************************************************** | |
2968 | * Implementation of Adjacency Graph concept | |
2969 | ***************************************************************************/ | |
2970 | template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS> | |
2971 | std::pair<typename PBGL_DISTRIB_ADJLIST_TYPE::adjacency_iterator, | |
2972 | typename PBGL_DISTRIB_ADJLIST_TYPE::adjacency_iterator> | |
2973 | adjacent_vertices(typename PBGL_DISTRIB_ADJLIST_TYPE::vertex_descriptor v, | |
2974 | const PBGL_DISTRIB_ADJLIST_TYPE& g) | |
2975 | { | |
2976 | typedef typename PBGL_DISTRIB_ADJLIST_TYPE::adjacency_iterator iter; | |
2977 | return std::make_pair(iter(out_edges(v, g).first, &g), | |
2978 | iter(out_edges(v, g).second, &g)); | |
2979 | } | |
2980 | ||
2981 | /*************************************************************************** | |
2982 | * Implementation of Mutable Graph concept | |
2983 | ***************************************************************************/ | |
2984 | ||
2985 | /************************************************************************ | |
2986 | * add_edge | |
2987 | ************************************************************************/ | |
2988 | template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS> | |
2989 | typename PBGL_DISTRIB_ADJLIST_TYPE::lazy_add_edge | |
2990 | add_edge(typename PBGL_DISTRIB_ADJLIST_TYPE::vertex_descriptor u, | |
2991 | typename PBGL_DISTRIB_ADJLIST_TYPE::vertex_descriptor v, | |
2992 | PBGL_DISTRIB_ADJLIST_TYPE& g) | |
2993 | { | |
2994 | typedef typename PBGL_DISTRIB_ADJLIST_TYPE::lazy_add_edge lazy_add_edge; | |
2995 | ||
2996 | return lazy_add_edge(g, u, v); | |
2997 | } | |
2998 | ||
2999 | template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS> | |
3000 | typename PBGL_DISTRIB_ADJLIST_TYPE | |
3001 | ::lazy_add_edge_with_property | |
3002 | add_edge(typename PBGL_DISTRIB_ADJLIST_TYPE::vertex_descriptor u, | |
3003 | typename PBGL_DISTRIB_ADJLIST_TYPE::vertex_descriptor v, | |
3004 | typename PBGL_DISTRIB_ADJLIST_TYPE::edge_property_type const& p, | |
3005 | PBGL_DISTRIB_ADJLIST_TYPE& g) | |
3006 | { | |
3007 | typedef typename PBGL_DISTRIB_ADJLIST_TYPE | |
3008 | ::lazy_add_edge_with_property lazy_add_edge_with_property; | |
3009 | return lazy_add_edge_with_property(g, u, v, p); | |
3010 | } | |
3011 | ||
3012 | /************************************************************************ | |
3013 | * | |
3014 | * remove_edge | |
3015 | * | |
3016 | ************************************************************************/ | |
3017 | template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS> | |
3018 | void | |
3019 | remove_edge(typename PBGL_DISTRIB_ADJLIST_TYPE::edge_descriptor e, | |
3020 | PBGL_DISTRIB_ADJLIST_TYPE& g) | |
3021 | { | |
3022 | BOOST_ASSERT(source(e, g).owner == g.processor() | |
3023 | || target(e, g).owner == g.processor()); | |
3024 | ||
3025 | if (target(e, g).owner == g.processor()) | |
3026 | detail::parallel::remove_in_edge(e, g, DirectedS()); | |
3027 | if (source(e, g).owner == g.processor()) | |
3028 | remove_edge(e.local, g.base()); | |
3029 | ||
3030 | g.remove_local_edge_from_list(source(e, g), target(e, g), DirectedS()); | |
3031 | ||
3032 | if (source(e, g).owner != g.processor() | |
3033 | || (target(e, g).owner != g.processor() | |
3034 | && !(is_same<DirectedS, directedS>::value))) { | |
3035 | g.send_remove_edge_request(e); | |
3036 | } | |
3037 | } | |
3038 | ||
3039 | template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS> | |
3040 | void | |
3041 | remove_edge(typename PBGL_DISTRIB_ADJLIST_TYPE::vertex_descriptor u, | |
3042 | typename PBGL_DISTRIB_ADJLIST_TYPE::vertex_descriptor v, | |
3043 | PBGL_DISTRIB_ADJLIST_TYPE& g) | |
3044 | { | |
3045 | typedef typename PBGL_DISTRIB_ADJLIST_TYPE | |
3046 | ::edge_descriptor edge_descriptor; | |
3047 | std::pair<edge_descriptor, bool> the_edge = edge(u, v, g); | |
3048 | if (the_edge.second) remove_edge(the_edge.first, g); | |
3049 | } | |
3050 | ||
3051 | template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS> | |
3052 | inline void | |
3053 | remove_edge(typename PBGL_DISTRIB_ADJLIST_TYPE::out_edge_iterator ei, | |
3054 | PBGL_DISTRIB_ADJLIST_TYPE& g) | |
3055 | { | |
3056 | remove_edge(*ei, g); | |
3057 | } | |
3058 | ||
3059 | template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS_CONFIG> | |
3060 | inline void | |
3061 | remove_edge(typename PBGL_DISTRIB_ADJLIST_TYPE_CONFIG(directedS) | |
3062 | ::out_edge_iterator ei, | |
3063 | PBGL_DISTRIB_ADJLIST_TYPE_CONFIG(directedS)& g) | |
3064 | { | |
3065 | BOOST_ASSERT(source(*ei, g).owner == g.processor()); | |
3066 | remove_edge(ei->local, g.base()); | |
3067 | } | |
3068 | ||
3069 | /************************************************************************ | |
3070 | * | |
3071 | * remove_out_edge_if | |
3072 | * | |
3073 | ************************************************************************/ | |
3074 | namespace parallel { namespace detail { | |
3075 | /** | |
3076 | * Function object that applies the underlying predicate to | |
3077 | * determine if an out-edge should be removed. If so, either | |
3078 | * removes the incoming edge (if it is stored locally) or sends a | |
3079 | * message to the owner of the target requesting that it remove | |
3080 | * the edge. | |
3081 | */ | |
3082 | template<typename Graph, typename Predicate> | |
3083 | struct remove_out_edge_predicate | |
3084 | { | |
3085 | typedef typename graph_traits<Graph>::edge_descriptor edge_descriptor; | |
3086 | typedef typename Graph::local_edge_descriptor argument_type; | |
3087 | typedef typename Graph::directed_selector directed_selector; | |
3088 | typedef bool result_type; | |
3089 | ||
3090 | remove_out_edge_predicate(Graph& g, Predicate& predicate) | |
3091 | : g(g), predicate(predicate) { } | |
3092 | ||
3093 | bool operator()(const argument_type& le) | |
3094 | { | |
3095 | typedef typename edge_descriptor::template out_generator<Graph> | |
3096 | generator; | |
3097 | ||
3098 | edge_descriptor e = generator(g)(le); | |
3099 | ||
3100 | if (predicate(e)) { | |
3101 | if (source(e, g).owner != target(e, g).owner | |
3102 | && !(is_same<directed_selector, directedS>::value)) | |
3103 | g.send_remove_edge_request(e); | |
3104 | else | |
3105 | ::boost::detail::parallel::remove_in_edge(e, g, | |
3106 | directed_selector()); | |
3107 | ||
3108 | g.remove_local_edge_from_list(source(e, g), target(e, g), | |
3109 | directed_selector()); | |
3110 | return true; | |
3111 | } else return false; | |
3112 | } | |
3113 | ||
3114 | private: | |
3115 | Graph& g; | |
3116 | Predicate predicate; | |
3117 | }; | |
3118 | } } // end namespace parallel::detail | |
3119 | ||
3120 | template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS, typename Predicate> | |
3121 | inline void | |
3122 | remove_out_edge_if | |
3123 | (typename PBGL_DISTRIB_ADJLIST_TYPE::vertex_descriptor u, | |
3124 | Predicate predicate, | |
3125 | PBGL_DISTRIB_ADJLIST_TYPE& g) | |
3126 | { | |
3127 | typedef PBGL_DISTRIB_ADJLIST_TYPE Graph; | |
3128 | typedef parallel::detail::remove_out_edge_predicate<Graph, Predicate> | |
3129 | Pred; | |
3130 | ||
3131 | BOOST_ASSERT(u.owner == g.processor()); | |
3132 | remove_out_edge_if(u.local, Pred(g, predicate), g.base()); | |
3133 | } | |
3134 | ||
3135 | /************************************************************************ | |
3136 | * | |
3137 | * remove_in_edge_if | |
3138 | * | |
3139 | ************************************************************************/ | |
3140 | namespace parallel { namespace detail { | |
3141 | /** | |
3142 | * Function object that applies the underlying predicate to | |
3143 | * determine if an in-edge should be removed. If so, either | |
3144 | * removes the outgoing edge (if it is stored locally) or sends a | |
3145 | * message to the owner of the target requesting that it remove | |
3146 | * the edge. Only required for bidirectional graphs. | |
3147 | */ | |
3148 | template<typename Graph, typename Predicate> | |
3149 | struct remove_in_edge_predicate | |
3150 | { | |
3151 | typedef typename graph_traits<Graph>::edge_descriptor edge_descriptor; | |
3152 | typedef bool result_type; | |
3153 | ||
3154 | remove_in_edge_predicate(Graph& g, const Predicate& predicate) | |
3155 | : g(g), predicate(predicate) { } | |
3156 | ||
3157 | template<typename StoredEdge> | |
3158 | bool operator()(const StoredEdge& le) | |
3159 | { | |
3160 | typedef typename edge_descriptor::template in_generator<Graph> | |
3161 | generator; | |
3162 | ||
3163 | edge_descriptor e = generator(g)(le); | |
3164 | ||
3165 | if (predicate(e)) { | |
3166 | if (source(e, g).owner != target(e, g).owner) | |
3167 | g.send_remove_edge_request(e); | |
3168 | else | |
3169 | remove_edge(source(e, g).local, target(e, g).local, g.base()); | |
3170 | return true; | |
3171 | } else return false; | |
3172 | } | |
3173 | ||
3174 | private: | |
3175 | Graph& g; | |
3176 | Predicate predicate; | |
3177 | }; | |
3178 | } } // end namespace parallel::detail | |
3179 | ||
3180 | template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS_CONFIG, typename Predicate> | |
3181 | inline void | |
3182 | remove_in_edge_if | |
3183 | (typename PBGL_DISTRIB_ADJLIST_TYPE_CONFIG(bidirectionalS) | |
3184 | ::vertex_descriptor u, | |
3185 | Predicate predicate, | |
3186 | PBGL_DISTRIB_ADJLIST_TYPE_CONFIG(bidirectionalS)& g) | |
3187 | { | |
3188 | typedef PBGL_DISTRIB_ADJLIST_TYPE_CONFIG(bidirectionalS) Graph; | |
3189 | typedef parallel::detail::remove_in_edge_predicate<Graph, Predicate> | |
3190 | Pred; | |
3191 | ||
3192 | BOOST_ASSERT(u.owner == g.processor()); | |
3193 | graph_detail::erase_if(get(vertex_in_edges, g.base())[u.local], | |
3194 | Pred(g, predicate)); | |
3195 | } | |
3196 | ||
3197 | template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS_CONFIG, typename Predicate> | |
3198 | inline void | |
3199 | remove_in_edge_if | |
3200 | (typename PBGL_DISTRIB_ADJLIST_TYPE_CONFIG(undirectedS) | |
3201 | ::vertex_descriptor u, | |
3202 | Predicate predicate, | |
3203 | PBGL_DISTRIB_ADJLIST_TYPE_CONFIG(undirectedS)& g) | |
3204 | { | |
3205 | remove_out_edge_if(u, predicate, g); | |
3206 | } | |
3207 | ||
3208 | /************************************************************************ | |
3209 | * | |
3210 | * remove_edge_if | |
3211 | * | |
3212 | ************************************************************************/ | |
3213 | namespace parallel { namespace detail { | |
3214 | /** | |
3215 | * Function object that applies the underlying predicate to | |
3216 | * determine if a directed edge can be removed. This only applies | |
3217 | * to directed graphs. | |
3218 | */ | |
3219 | template<typename Graph, typename Predicate> | |
3220 | struct remove_directed_edge_predicate | |
3221 | { | |
3222 | typedef typename Graph::local_edge_descriptor argument_type; | |
3223 | typedef typename graph_traits<Graph>::edge_descriptor edge_descriptor; | |
3224 | typedef bool result_type; | |
3225 | ||
3226 | remove_directed_edge_predicate(Graph& g, const Predicate& predicate) | |
3227 | : g(g), predicate(predicate) { } | |
3228 | ||
3229 | bool operator()(const argument_type& le) | |
3230 | { | |
3231 | typedef typename edge_descriptor::template out_generator<Graph> | |
3232 | generator; | |
3233 | ||
3234 | edge_descriptor e = generator(g)(le); | |
3235 | return predicate(e); | |
3236 | } | |
3237 | ||
3238 | private: | |
3239 | Graph& g; | |
3240 | Predicate predicate; | |
3241 | }; | |
3242 | } } // end namespace parallel::detail | |
3243 | ||
3244 | template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS_CONFIG, typename Predicate> | |
3245 | inline void | |
3246 | remove_edge_if(Predicate predicate, | |
3247 | PBGL_DISTRIB_ADJLIST_TYPE_CONFIG(directedS)& g) | |
3248 | { | |
3249 | typedef PBGL_DISTRIB_ADJLIST_TYPE_CONFIG(directedS) Graph; | |
3250 | typedef parallel::detail::remove_directed_edge_predicate<Graph, | |
3251 | Predicate> Pred; | |
3252 | remove_edge_if(Pred(g, predicate), g.base()); | |
3253 | } | |
3254 | ||
3255 | template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS_CONFIG, typename Predicate> | |
3256 | inline void | |
3257 | remove_edge_if(Predicate predicate, | |
3258 | PBGL_DISTRIB_ADJLIST_TYPE_CONFIG(bidirectionalS)& g) | |
3259 | { | |
3260 | typedef PBGL_DISTRIB_ADJLIST_TYPE_CONFIG(bidirectionalS) Graph; | |
3261 | typedef parallel::detail::remove_out_edge_predicate<Graph, | |
3262 | Predicate> Pred; | |
3263 | remove_edge_if(Pred(g, predicate), g.base()); | |
3264 | } | |
3265 | ||
3266 | namespace parallel { namespace detail { | |
3267 | /** | |
3268 | * Function object that applies the underlying predicate to | |
3269 | * determine if an undirected edge should be removed. If so, | |
3270 | * removes the local edges associated with the edge and | |
3271 | * (potentially) sends a message to the remote processor that also | |
3272 | * is removing this edge. | |
3273 | */ | |
3274 | template<typename Graph, typename Predicate> | |
3275 | struct remove_undirected_edge_predicate | |
3276 | { | |
3277 | typedef typename graph_traits<Graph>::edge_descriptor argument_type; | |
3278 | typedef bool result_type; | |
3279 | ||
3280 | remove_undirected_edge_predicate(Graph& g, Predicate& predicate) | |
3281 | : g(g), predicate(predicate) { } | |
3282 | ||
3283 | bool operator()(const argument_type& e) | |
3284 | { | |
3285 | if (predicate(e)) { | |
3286 | if (source(e, g).owner != target(e, g).owner) | |
3287 | g.send_remove_edge_request(e); | |
3288 | if (target(e, g).owner == g.processor()) | |
3289 | ::boost::detail::parallel::remove_in_edge(e, g, undirectedS()); | |
3290 | if (source(e, g).owner == g.processor()) | |
3291 | remove_edge(e.local, g.base()); | |
3292 | return true; | |
3293 | } else return false; | |
3294 | } | |
3295 | ||
3296 | private: | |
3297 | Graph& g; | |
3298 | Predicate predicate; | |
3299 | }; | |
3300 | } } // end namespace parallel::detail | |
3301 | ||
3302 | template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS_CONFIG, typename Predicate> | |
3303 | inline void | |
3304 | remove_edge_if(Predicate predicate, | |
3305 | PBGL_DISTRIB_ADJLIST_TYPE_CONFIG(undirectedS)& g) | |
3306 | { | |
3307 | typedef PBGL_DISTRIB_ADJLIST_TYPE_CONFIG(undirectedS) Graph; | |
3308 | typedef parallel::detail::remove_undirected_edge_predicate<Graph, | |
3309 | Predicate> Pred; | |
3310 | graph_detail::erase_if(g.local_edges(), Pred(g, predicate)); | |
3311 | } | |
3312 | ||
3313 | /************************************************************************ | |
3314 | * | |
3315 | * clear_vertex | |
3316 | * | |
3317 | ************************************************************************/ | |
3318 | namespace parallel { namespace detail { | |
3319 | struct always_true | |
3320 | { | |
3321 | typedef bool result_type; | |
3322 | ||
3323 | template<typename T> bool operator()(const T&) const { return true; } | |
3324 | }; | |
3325 | } } // end namespace parallel::detail | |
3326 | ||
3327 | template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS_CONFIG> | |
3328 | void | |
3329 | clear_vertex | |
3330 | (typename PBGL_DISTRIB_ADJLIST_TYPE_CONFIG(bidirectionalS) | |
3331 | ::vertex_descriptor u, | |
3332 | PBGL_DISTRIB_ADJLIST_TYPE_CONFIG(bidirectionalS)& g) | |
3333 | { | |
3334 | clear_out_edges(u, g); | |
3335 | clear_in_edges(u, g); | |
3336 | } | |
3337 | ||
3338 | template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS_CONFIG> | |
3339 | void | |
3340 | clear_vertex | |
3341 | (typename PBGL_DISTRIB_ADJLIST_TYPE_CONFIG(undirectedS) | |
3342 | ::vertex_descriptor u, | |
3343 | PBGL_DISTRIB_ADJLIST_TYPE_CONFIG(undirectedS)& g) | |
3344 | { | |
3345 | remove_out_edge_if(u, parallel::detail::always_true(), g); | |
3346 | } | |
3347 | ||
3348 | /************************************************************************ | |
3349 | * | |
3350 | * clear_out_edges | |
3351 | * | |
3352 | ************************************************************************/ | |
3353 | template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS_CONFIG> | |
3354 | void | |
3355 | clear_out_edges | |
3356 | (typename PBGL_DISTRIB_ADJLIST_TYPE_CONFIG(directedS)::vertex_descriptor u, | |
3357 | PBGL_DISTRIB_ADJLIST_TYPE_CONFIG(directedS)& g) | |
3358 | { | |
3359 | BOOST_ASSERT(u.owner == g.processor()); | |
3360 | clear_out_edges(u.local, g.base()); | |
3361 | } | |
3362 | ||
3363 | template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS_CONFIG> | |
3364 | void | |
3365 | clear_out_edges | |
3366 | (typename PBGL_DISTRIB_ADJLIST_TYPE_CONFIG(bidirectionalS) | |
3367 | ::vertex_descriptor u, | |
3368 | PBGL_DISTRIB_ADJLIST_TYPE_CONFIG(bidirectionalS)& g) | |
3369 | { | |
3370 | remove_out_edge_if(u, parallel::detail::always_true(), g); | |
3371 | } | |
3372 | ||
3373 | /************************************************************************ | |
3374 | * | |
3375 | * clear_in_edges | |
3376 | * | |
3377 | ************************************************************************/ | |
3378 | template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS_CONFIG> | |
3379 | void | |
3380 | clear_in_edges | |
3381 | (typename PBGL_DISTRIB_ADJLIST_TYPE_CONFIG(bidirectionalS) | |
3382 | ::vertex_descriptor u, | |
3383 | PBGL_DISTRIB_ADJLIST_TYPE_CONFIG(bidirectionalS)& g) | |
3384 | { | |
3385 | remove_in_edge_if(u, parallel::detail::always_true(), g); | |
3386 | } | |
3387 | ||
3388 | /************************************************************************ | |
3389 | * | |
3390 | * add_vertex | |
3391 | * | |
3392 | ************************************************************************/ | |
3393 | template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS> | |
3394 | typename PBGL_DISTRIB_ADJLIST_TYPE::vertex_descriptor | |
3395 | add_vertex(PBGL_DISTRIB_ADJLIST_TYPE& g) | |
3396 | { | |
3397 | typedef PBGL_DISTRIB_ADJLIST_TYPE graph_type; | |
3398 | typename graph_type::vertex_property_type p; | |
3399 | return add_vertex(p, g); | |
3400 | } | |
3401 | ||
3402 | template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS> | |
3403 | typename PBGL_DISTRIB_ADJLIST_TYPE::lazy_add_vertex_with_property | |
3404 | add_vertex(typename PBGL_DISTRIB_ADJLIST_TYPE::vertex_property_type const& p, | |
3405 | PBGL_DISTRIB_ADJLIST_TYPE& g) | |
3406 | { | |
3407 | typedef typename PBGL_DISTRIB_ADJLIST_TYPE | |
3408 | ::lazy_add_vertex_with_property lazy_add_vertex; | |
3409 | return lazy_add_vertex(g, p); | |
3410 | } | |
3411 | ||
3412 | /************************************************************************ | |
3413 | * | |
3414 | * remove_vertex | |
3415 | * | |
3416 | ************************************************************************/ | |
3417 | template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS> | |
3418 | void | |
3419 | remove_vertex(typename PBGL_DISTRIB_ADJLIST_TYPE::vertex_descriptor u, | |
3420 | PBGL_DISTRIB_ADJLIST_TYPE& g) | |
3421 | { | |
3422 | typedef typename PBGL_DISTRIB_ADJLIST_TYPE::graph_type graph_type; | |
3423 | typedef typename graph_type::named_graph_mixin named_graph_mixin; | |
3424 | BOOST_ASSERT(u.owner == g.processor()); | |
3425 | static_cast<named_graph_mixin&>(static_cast<graph_type&>(g)) | |
3426 | .removing_vertex(u, boost::graph_detail::iterator_stability(g.base().m_vertices)); | |
3427 | g.distribution().clear(); | |
3428 | remove_vertex(u.local, g.base()); | |
3429 | } | |
3430 | ||
3431 | /*************************************************************************** | |
3432 | * Implementation of Property Graph concept | |
3433 | ***************************************************************************/ | |
3434 | template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS, typename Property> | |
3435 | struct property_map<PBGL_DISTRIB_ADJLIST_TYPE, Property> | |
3436 | : detail::parallel::get_adj_list_pmap<Property> | |
3437 | ::template apply<PBGL_DISTRIB_ADJLIST_TYPE> | |
3438 | { }; | |
3439 | ||
3440 | template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS, typename Property> | |
3441 | struct property_map<PBGL_DISTRIB_ADJLIST_TYPE const, Property> | |
3442 | : boost::detail::parallel::get_adj_list_pmap<Property> | |
3443 | // FIXME: in the original code the following was not const | |
3444 | ::template apply<PBGL_DISTRIB_ADJLIST_TYPE const> | |
3445 | { }; | |
3446 | ||
3447 | template<typename Property, PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS> | |
3448 | typename property_map<PBGL_DISTRIB_ADJLIST_TYPE, Property>::type | |
3449 | get(Property p, PBGL_DISTRIB_ADJLIST_TYPE& g) | |
3450 | { | |
3451 | typedef PBGL_DISTRIB_ADJLIST_TYPE Graph; | |
3452 | typedef typename property_map<Graph, Property>::type result_type; | |
3453 | typedef typename property_traits<result_type>::value_type value_type; | |
3454 | typedef typename property_reduce<Property>::template apply<value_type> | |
3455 | reduce; | |
3456 | ||
3457 | typedef typename property_traits<result_type>::key_type descriptor; | |
3458 | typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor; | |
3459 | typedef typename mpl::if_<is_same<descriptor, vertex_descriptor>, | |
3460 | vertex_global_t, edge_global_t>::type | |
3461 | global_map_t; | |
3462 | ||
3463 | return result_type(g.process_group(), get(global_map_t(), g), | |
3464 | get(p, g.base()), reduce()); | |
3465 | } | |
3466 | ||
3467 | template<typename Property, PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS> | |
3468 | typename property_map<PBGL_DISTRIB_ADJLIST_TYPE, Property>::const_type | |
3469 | get(Property p, const PBGL_DISTRIB_ADJLIST_TYPE& g) | |
3470 | { | |
3471 | typedef PBGL_DISTRIB_ADJLIST_TYPE Graph; | |
3472 | typedef typename property_map<Graph, Property>::const_type result_type; | |
3473 | typedef typename property_traits<result_type>::value_type value_type; | |
3474 | typedef typename property_reduce<Property>::template apply<value_type> | |
3475 | reduce; | |
3476 | ||
3477 | typedef typename property_traits<result_type>::key_type descriptor; | |
3478 | typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor; | |
3479 | typedef typename mpl::if_<is_same<descriptor, vertex_descriptor>, | |
3480 | vertex_global_t, edge_global_t>::type | |
3481 | global_map_t; | |
3482 | ||
3483 | return result_type(g.process_group(), get(global_map_t(), g), | |
3484 | get(p, g.base()), reduce()); | |
3485 | } | |
3486 | ||
3487 | template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS> | |
3488 | typename property_map<PBGL_DISTRIB_ADJLIST_TYPE, vertex_local_index_t>::type | |
3489 | get(vertex_local_index_t, PBGL_DISTRIB_ADJLIST_TYPE& g) | |
3490 | { | |
3491 | return get(vertex_local_index, g.base()); | |
3492 | } | |
3493 | ||
3494 | template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS> | |
3495 | typename property_map<PBGL_DISTRIB_ADJLIST_TYPE, | |
3496 | vertex_local_index_t>::const_type | |
3497 | get(vertex_local_index_t, const PBGL_DISTRIB_ADJLIST_TYPE& g) | |
3498 | { | |
3499 | return get(vertex_local_index, g.base()); | |
3500 | } | |
3501 | ||
3502 | template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS> | |
3503 | typename property_map<PBGL_DISTRIB_ADJLIST_TYPE, vertex_global_t>::const_type | |
3504 | get(vertex_global_t, const PBGL_DISTRIB_ADJLIST_TYPE& g) | |
3505 | { | |
3506 | typedef typename property_map< | |
3507 | PBGL_DISTRIB_ADJLIST_TYPE, | |
3508 | vertex_global_t>::const_type result_type; | |
3509 | return result_type(); | |
3510 | } | |
3511 | ||
3512 | template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS> | |
3513 | typename property_map<PBGL_DISTRIB_ADJLIST_TYPE, vertex_global_t>::const_type | |
3514 | get(vertex_global_t, PBGL_DISTRIB_ADJLIST_TYPE& g) | |
3515 | { | |
3516 | typedef typename property_map< | |
3517 | PBGL_DISTRIB_ADJLIST_TYPE, | |
3518 | vertex_global_t>::const_type result_type; | |
3519 | return result_type(); | |
3520 | } | |
3521 | ||
3522 | /// Retrieve a property map mapping from a vertex descriptor to its | |
3523 | /// owner. | |
3524 | template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS> | |
3525 | typename property_map<PBGL_DISTRIB_ADJLIST_TYPE, vertex_owner_t>::type | |
3526 | get(vertex_owner_t, PBGL_DISTRIB_ADJLIST_TYPE& g) | |
3527 | { | |
3528 | typedef typename property_map< | |
3529 | PBGL_DISTRIB_ADJLIST_TYPE, | |
3530 | vertex_owner_t>::type result_type; | |
3531 | return result_type(); | |
3532 | } | |
3533 | ||
3534 | /// Retrieve a property map mapping from a vertex descriptor to its | |
3535 | /// owner. | |
3536 | template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS> | |
3537 | typename property_map<PBGL_DISTRIB_ADJLIST_TYPE, vertex_owner_t>::const_type | |
3538 | get(vertex_owner_t, const PBGL_DISTRIB_ADJLIST_TYPE& g) | |
3539 | { | |
3540 | typedef typename property_map< | |
3541 | PBGL_DISTRIB_ADJLIST_TYPE, | |
3542 | vertex_owner_t>::const_type result_type; | |
3543 | return result_type(); | |
3544 | } | |
3545 | ||
3546 | /// Retrieve the owner of a vertex | |
3547 | template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS> | |
3548 | inline processor_id_type | |
3549 | get(vertex_owner_t, PBGL_DISTRIB_ADJLIST_TYPE&, | |
3550 | typename PBGL_DISTRIB_ADJLIST_TYPE::vertex_descriptor v) | |
3551 | { | |
3552 | return v.owner; | |
3553 | } | |
3554 | ||
3555 | /// Retrieve the owner of a vertex | |
3556 | template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS> | |
3557 | inline processor_id_type | |
3558 | get(vertex_owner_t, const PBGL_DISTRIB_ADJLIST_TYPE&, | |
3559 | typename PBGL_DISTRIB_ADJLIST_TYPE::vertex_descriptor v) | |
3560 | { | |
3561 | return v.owner; | |
3562 | } | |
3563 | ||
3564 | /// Retrieve a property map that maps from a vertex descriptor to | |
3565 | /// its local descriptor. | |
3566 | template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS> | |
3567 | typename property_map<PBGL_DISTRIB_ADJLIST_TYPE, vertex_local_t>::type | |
3568 | get(vertex_local_t, PBGL_DISTRIB_ADJLIST_TYPE& g) | |
3569 | { | |
3570 | typedef typename property_map< | |
3571 | PBGL_DISTRIB_ADJLIST_TYPE, | |
3572 | vertex_local_t>::type result_type; | |
3573 | return result_type(); | |
3574 | } | |
3575 | ||
3576 | /// Retrieve a property map that maps from a vertex descriptor to | |
3577 | /// its local descriptor. | |
3578 | template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS> | |
3579 | typename property_map<PBGL_DISTRIB_ADJLIST_TYPE, vertex_local_t>::const_type | |
3580 | get(vertex_local_t, const PBGL_DISTRIB_ADJLIST_TYPE& g) | |
3581 | { | |
3582 | typedef typename property_map< | |
3583 | PBGL_DISTRIB_ADJLIST_TYPE, | |
3584 | vertex_local_t>::const_type result_type; | |
3585 | return result_type(); | |
3586 | } | |
3587 | ||
3588 | /// Retrieve the local descriptor of a vertex | |
3589 | template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS> | |
3590 | inline typename PBGL_DISTRIB_ADJLIST_TYPE::local_vertex_descriptor | |
3591 | get(vertex_local_t, PBGL_DISTRIB_ADJLIST_TYPE&, | |
3592 | typename PBGL_DISTRIB_ADJLIST_TYPE::vertex_descriptor v) | |
3593 | { | |
3594 | return v.local; | |
3595 | } | |
3596 | ||
3597 | /// Retrieve the local descriptor of a vertex | |
3598 | template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS> | |
3599 | inline typename PBGL_DISTRIB_ADJLIST_TYPE::local_vertex_descriptor | |
3600 | get(vertex_local_t, const PBGL_DISTRIB_ADJLIST_TYPE&, | |
3601 | typename PBGL_DISTRIB_ADJLIST_TYPE::vertex_descriptor v) | |
3602 | { | |
3603 | return v.local; | |
3604 | } | |
3605 | ||
3606 | ||
3607 | template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS> | |
3608 | typename property_map<PBGL_DISTRIB_ADJLIST_TYPE, edge_global_t>::const_type | |
3609 | get(edge_global_t, const PBGL_DISTRIB_ADJLIST_TYPE& g) | |
3610 | { | |
3611 | typedef typename property_map< | |
3612 | PBGL_DISTRIB_ADJLIST_TYPE, | |
3613 | edge_global_t>::const_type result_type; | |
3614 | return result_type(); | |
3615 | } | |
3616 | ||
3617 | template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS> | |
3618 | typename property_map<PBGL_DISTRIB_ADJLIST_TYPE, edge_global_t>::const_type | |
3619 | get(edge_global_t, PBGL_DISTRIB_ADJLIST_TYPE& g) | |
3620 | { | |
3621 | typedef typename property_map< | |
3622 | PBGL_DISTRIB_ADJLIST_TYPE, | |
3623 | edge_global_t>::const_type result_type; | |
3624 | return result_type(); | |
3625 | } | |
3626 | ||
3627 | template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS> | |
3628 | typename property_map<PBGL_DISTRIB_ADJLIST_TYPE, edge_owner_t>::type | |
3629 | get(edge_owner_t, PBGL_DISTRIB_ADJLIST_TYPE& g) | |
3630 | { | |
3631 | typedef typename property_map< | |
3632 | PBGL_DISTRIB_ADJLIST_TYPE, | |
3633 | edge_owner_t>::type result_type; | |
3634 | return result_type(); | |
3635 | } | |
3636 | ||
3637 | template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS> | |
3638 | typename property_map<PBGL_DISTRIB_ADJLIST_TYPE, edge_owner_t>::const_type | |
3639 | get(edge_owner_t, const PBGL_DISTRIB_ADJLIST_TYPE& g) | |
3640 | { | |
3641 | typedef typename property_map< | |
3642 | PBGL_DISTRIB_ADJLIST_TYPE, | |
3643 | edge_owner_t>::const_type result_type; | |
3644 | return result_type(); | |
3645 | } | |
3646 | ||
3647 | template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS> | |
3648 | typename property_map<PBGL_DISTRIB_ADJLIST_TYPE, edge_local_t>::type | |
3649 | get(edge_local_t, PBGL_DISTRIB_ADJLIST_TYPE& g) | |
3650 | { | |
3651 | typedef typename property_map< | |
3652 | PBGL_DISTRIB_ADJLIST_TYPE, | |
3653 | edge_local_t>::type result_type; | |
3654 | return result_type(); | |
3655 | } | |
3656 | ||
3657 | template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS> | |
3658 | typename property_map<PBGL_DISTRIB_ADJLIST_TYPE, edge_local_t>::const_type | |
3659 | get(edge_local_t, const PBGL_DISTRIB_ADJLIST_TYPE& g) | |
3660 | { | |
3661 | typedef typename property_map< | |
3662 | PBGL_DISTRIB_ADJLIST_TYPE, | |
3663 | edge_local_t>::const_type result_type; | |
3664 | return result_type(); | |
3665 | } | |
3666 | ||
3667 | template<typename Property, PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS, | |
3668 | typename Key> | |
3669 | inline | |
3670 | typename property_traits<typename property_map< | |
3671 | PBGL_DISTRIB_ADJLIST_TYPE, Property>::const_type | |
3672 | >::value_type | |
3673 | get(Property p, const PBGL_DISTRIB_ADJLIST_TYPE& g, const Key& key) | |
3674 | { | |
3675 | if (owner(key) == process_id(g.process_group())) | |
3676 | return get(p, g.base(), local(key)); | |
3677 | else | |
3678 | BOOST_ASSERT(false); | |
3679 | } | |
3680 | ||
3681 | template<typename Property, PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS, | |
3682 | typename Key, typename Value> | |
3683 | void | |
3684 | put(Property p, PBGL_DISTRIB_ADJLIST_TYPE& g, const Key& key, const Value& v) | |
3685 | { | |
3686 | if (owner(key) == process_id(g.process_group())) | |
3687 | put(p, g.base(), local(key), v); | |
3688 | else | |
3689 | BOOST_ASSERT(false); | |
3690 | } | |
3691 | ||
3692 | template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS> | |
3693 | typename property_map<PBGL_DISTRIB_ADJLIST_TYPE, vertex_index_t>::type | |
3694 | get(vertex_index_t vi, PBGL_DISTRIB_ADJLIST_TYPE& g) | |
3695 | { | |
3696 | typedef PBGL_DISTRIB_ADJLIST_TYPE graph_type; | |
3697 | typedef typename property_map<graph_type, vertex_index_t>::type | |
3698 | result_type; | |
3699 | return result_type(g.process_group(), get(vertex_global, g), | |
3700 | get(vi, g.base())); | |
3701 | } | |
3702 | ||
3703 | template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS> | |
3704 | typename property_map<PBGL_DISTRIB_ADJLIST_TYPE, vertex_index_t>::const_type | |
3705 | get(vertex_index_t vi, const PBGL_DISTRIB_ADJLIST_TYPE& g) | |
3706 | { | |
3707 | typedef PBGL_DISTRIB_ADJLIST_TYPE graph_type; | |
3708 | typedef typename property_map<graph_type, vertex_index_t>::const_type | |
3709 | result_type; | |
3710 | return result_type(g.process_group(), get(vertex_global, g), | |
3711 | get(vi, g.base())); | |
3712 | } | |
3713 | ||
3714 | /*************************************************************************** | |
3715 | * Implementation of bundled properties | |
3716 | ***************************************************************************/ | |
3717 | template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS, typename T, typename Bundle> | |
3718 | struct property_map<PBGL_DISTRIB_ADJLIST_TYPE, T Bundle::*> | |
3719 | : detail::parallel::get_adj_list_pmap<T Bundle::*> | |
3720 | ::template apply<PBGL_DISTRIB_ADJLIST_TYPE> | |
3721 | { }; | |
3722 | ||
3723 | template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS, typename T, typename Bundle> | |
3724 | struct property_map<PBGL_DISTRIB_ADJLIST_TYPE const, T Bundle::*> | |
3725 | : detail::parallel::get_adj_list_pmap<T Bundle::*> | |
3726 | ::template apply<PBGL_DISTRIB_ADJLIST_TYPE const> | |
3727 | { }; | |
3728 | ||
3729 | template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS, typename T, typename Bundle> | |
3730 | typename property_map<PBGL_DISTRIB_ADJLIST_TYPE, T Bundle::*>::type | |
3731 | get(T Bundle::* p, PBGL_DISTRIB_ADJLIST_TYPE& g) | |
3732 | { | |
3733 | typedef PBGL_DISTRIB_ADJLIST_TYPE Graph; | |
3734 | typedef typename property_map<Graph, T Bundle::*>::type result_type; | |
3735 | typedef typename property_traits<result_type>::value_type value_type; | |
3736 | typedef typename property_reduce<T Bundle::*>::template apply<value_type> | |
3737 | reduce; | |
3738 | ||
3739 | typedef typename property_traits<result_type>::key_type descriptor; | |
3740 | typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor; | |
3741 | typedef typename mpl::if_<is_same<descriptor, vertex_descriptor>, | |
3742 | vertex_global_t, edge_global_t>::type | |
3743 | global_map_t; | |
3744 | ||
3745 | return result_type(g.process_group(), get(global_map_t(), g), | |
3746 | get(p, g.base()), reduce()); | |
3747 | } | |
3748 | ||
3749 | template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS, typename T, typename Bundle> | |
3750 | typename property_map<PBGL_DISTRIB_ADJLIST_TYPE, T Bundle::*>::const_type | |
3751 | get(T Bundle::* p, const PBGL_DISTRIB_ADJLIST_TYPE& g) | |
3752 | { | |
3753 | typedef PBGL_DISTRIB_ADJLIST_TYPE Graph; | |
3754 | typedef typename property_map<Graph, T Bundle::*>::const_type result_type; | |
3755 | typedef typename property_traits<result_type>::value_type value_type; | |
3756 | typedef typename property_reduce<T Bundle::*>::template apply<value_type> | |
3757 | reduce; | |
3758 | ||
3759 | typedef typename property_traits<result_type>::key_type descriptor; | |
3760 | typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor; | |
3761 | typedef typename mpl::if_<is_same<descriptor, vertex_descriptor>, | |
3762 | vertex_global_t, edge_global_t>::type | |
3763 | global_map_t; | |
3764 | ||
3765 | return result_type(g.process_group(), get(global_map_t(), g), | |
3766 | get(p, g.base()), reduce()); | |
3767 | } | |
3768 | ||
3769 | /*************************************************************************** | |
3770 | * Implementation of DistributedGraph concept | |
3771 | ***************************************************************************/ | |
3772 | template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS> | |
3773 | void synchronize(const PBGL_DISTRIB_ADJLIST_TYPE& g) | |
3774 | { | |
3775 | synchronize(g.process_group()); | |
3776 | } | |
3777 | ||
3778 | template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS> | |
3779 | ProcessGroup | |
3780 | process_group(const PBGL_DISTRIB_ADJLIST_TYPE& g) | |
3781 | { return g.process_group(); } | |
3782 | ||
3783 | /*************************************************************************** | |
3784 | * Specializations of is_mpi_datatype for Serializable entities | |
3785 | ***************************************************************************/ | |
3786 | namespace mpi { | |
3787 | template<typename Directed, typename Vertex> | |
3788 | struct is_mpi_datatype<boost::detail::edge_base<Directed, Vertex> > | |
3789 | : is_mpi_datatype<Vertex> { }; | |
3790 | ||
3791 | template<typename Directed, typename Vertex> | |
3792 | struct is_mpi_datatype<boost::detail::edge_desc_impl<Directed, Vertex> > | |
3793 | : is_mpi_datatype<boost::detail::edge_base<Directed, Vertex> > { }; | |
3794 | ||
3795 | template<typename LocalDescriptor> | |
3796 | struct is_mpi_datatype<boost::detail::parallel::global_descriptor<LocalDescriptor> > | |
3797 | : is_mpi_datatype<LocalDescriptor> { }; | |
3798 | ||
3799 | template<typename Edge> | |
3800 | struct is_mpi_datatype<boost::detail::parallel::edge_descriptor<Edge> > | |
3801 | : is_mpi_datatype<Edge> { }; | |
3802 | ||
3803 | template<typename Vertex, typename LocalVertex> | |
3804 | struct is_mpi_datatype<boost::detail::parallel:: | |
3805 | msg_add_edge_data<Vertex, LocalVertex> > | |
3806 | : is_mpi_datatype<Vertex> { }; | |
3807 | ||
3808 | template<typename Vertex, typename LocalVertex, typename EdgeProperty> | |
3809 | struct is_mpi_datatype<boost::detail::parallel:: | |
3810 | msg_add_edge_with_property_data<Vertex, | |
3811 | LocalVertex, | |
3812 | EdgeProperty> > | |
3813 | : mpl::and_<is_mpi_datatype<Vertex>, is_mpi_datatype<EdgeProperty> > { }; | |
3814 | ||
3815 | ||
3816 | template<typename EdgeProperty, typename EdgeDescriptor> | |
3817 | struct is_mpi_datatype<boost::detail::parallel::msg_nonlocal_edge_data< | |
3818 | EdgeProperty,EdgeDescriptor> > | |
3819 | : mpl::and_< | |
3820 | is_mpi_datatype<boost::detail::parallel::maybe_store_property< | |
3821 | EdgeProperty> >, | |
3822 | is_mpi_datatype<EdgeDescriptor> > | |
3823 | {}; | |
3824 | ||
3825 | template<typename EdgeDescriptor> | |
3826 | struct is_mpi_datatype< | |
3827 | boost::detail::parallel::msg_remove_edge_data<EdgeDescriptor> > | |
3828 | : is_mpi_datatype<EdgeDescriptor> {}; | |
3829 | } | |
3830 | ||
3831 | /*************************************************************************** | |
3832 | * Specializations of is_bitwise_serializable for Serializable entities | |
3833 | ***************************************************************************/ | |
3834 | namespace serialization { | |
3835 | template<typename Directed, typename Vertex> | |
3836 | struct is_bitwise_serializable<boost::detail::edge_base<Directed, Vertex> > | |
3837 | : is_bitwise_serializable<Vertex> { }; | |
3838 | ||
3839 | template<typename Directed, typename Vertex> | |
3840 | struct is_bitwise_serializable<boost::detail::edge_desc_impl<Directed, Vertex> > | |
3841 | : is_bitwise_serializable<boost::detail::edge_base<Directed, Vertex> > { }; | |
3842 | ||
3843 | template<typename LocalDescriptor> | |
3844 | struct is_bitwise_serializable<boost::detail::parallel::global_descriptor<LocalDescriptor> > | |
3845 | : is_bitwise_serializable<LocalDescriptor> { }; | |
3846 | ||
3847 | template<typename Edge> | |
3848 | struct is_bitwise_serializable<boost::detail::parallel::edge_descriptor<Edge> > | |
3849 | : is_bitwise_serializable<Edge> { }; | |
3850 | ||
3851 | template<typename Vertex, typename LocalVertex> | |
3852 | struct is_bitwise_serializable<boost::detail::parallel:: | |
3853 | msg_add_edge_data<Vertex, LocalVertex> > | |
3854 | : is_bitwise_serializable<Vertex> { }; | |
3855 | ||
3856 | template<typename Vertex, typename LocalVertex, typename EdgeProperty> | |
3857 | struct is_bitwise_serializable<boost::detail::parallel:: | |
3858 | msg_add_edge_with_property_data<Vertex, | |
3859 | LocalVertex, | |
3860 | EdgeProperty> > | |
3861 | : mpl::and_<is_bitwise_serializable<Vertex>, | |
3862 | is_bitwise_serializable<EdgeProperty> > { }; | |
3863 | ||
3864 | template<typename EdgeProperty, typename EdgeDescriptor> | |
3865 | struct is_bitwise_serializable<boost::detail::parallel::msg_nonlocal_edge_data< | |
3866 | EdgeProperty,EdgeDescriptor> > | |
3867 | : mpl::and_< | |
3868 | is_bitwise_serializable< | |
3869 | boost::detail::parallel::maybe_store_property<EdgeProperty> >, | |
3870 | is_bitwise_serializable<EdgeDescriptor> > | |
3871 | {}; | |
3872 | ||
3873 | template<typename EdgeDescriptor> | |
3874 | struct is_bitwise_serializable< | |
3875 | boost::detail::parallel::msg_remove_edge_data<EdgeDescriptor> > | |
3876 | : is_bitwise_serializable<EdgeDescriptor> {}; | |
3877 | ||
3878 | template<typename Directed, typename Vertex> | |
3879 | struct implementation_level<boost::detail::edge_base<Directed, Vertex> > | |
3880 | : mpl::int_<object_serializable> {}; | |
3881 | ||
3882 | template<typename Directed, typename Vertex> | |
3883 | struct implementation_level<boost::detail::edge_desc_impl<Directed, Vertex> > | |
3884 | : mpl::int_<object_serializable> {}; | |
3885 | ||
3886 | template<typename LocalDescriptor> | |
3887 | struct implementation_level<boost::detail::parallel::global_descriptor<LocalDescriptor> > | |
3888 | : mpl::int_<object_serializable> {}; | |
3889 | ||
3890 | template<typename Edge> | |
3891 | struct implementation_level<boost::detail::parallel::edge_descriptor<Edge> > | |
3892 | : mpl::int_<object_serializable> {}; | |
3893 | ||
3894 | template<typename Vertex, typename LocalVertex> | |
3895 | struct implementation_level<boost::detail::parallel:: | |
3896 | msg_add_edge_data<Vertex, LocalVertex> > | |
3897 | : mpl::int_<object_serializable> {}; | |
3898 | ||
3899 | template<typename Vertex, typename LocalVertex, typename EdgeProperty> | |
3900 | struct implementation_level<boost::detail::parallel:: | |
3901 | msg_add_edge_with_property_data<Vertex, | |
3902 | LocalVertex, | |
3903 | EdgeProperty> > | |
3904 | : mpl::int_<object_serializable> {}; | |
3905 | ||
3906 | template<typename EdgeProperty, typename EdgeDescriptor> | |
3907 | struct implementation_level<boost::detail::parallel::msg_nonlocal_edge_data< | |
3908 | EdgeProperty,EdgeDescriptor> > | |
3909 | : mpl::int_<object_serializable> {}; | |
3910 | ||
3911 | template<typename EdgeDescriptor> | |
3912 | struct implementation_level< | |
3913 | boost::detail::parallel::msg_remove_edge_data<EdgeDescriptor> > | |
3914 | : mpl::int_<object_serializable> {}; | |
3915 | ||
3916 | template<typename Directed, typename Vertex> | |
3917 | struct tracking_level<boost::detail::edge_base<Directed, Vertex> > | |
3918 | : mpl::int_<track_never> {}; | |
3919 | ||
3920 | template<typename Directed, typename Vertex> | |
3921 | struct tracking_level<boost::detail::edge_desc_impl<Directed, Vertex> > | |
3922 | : mpl::int_<track_never> {}; | |
3923 | ||
3924 | template<typename LocalDescriptor> | |
3925 | struct tracking_level<boost::detail::parallel::global_descriptor<LocalDescriptor> > | |
3926 | : mpl::int_<track_never> {}; | |
3927 | ||
3928 | template<typename Edge> | |
3929 | struct tracking_level<boost::detail::parallel::edge_descriptor<Edge> > | |
3930 | : mpl::int_<track_never> {}; | |
3931 | ||
3932 | template<typename Vertex, typename LocalVertex> | |
3933 | struct tracking_level<boost::detail::parallel:: | |
3934 | msg_add_edge_data<Vertex, LocalVertex> > | |
3935 | : mpl::int_<track_never> {}; | |
3936 | ||
3937 | template<typename Vertex, typename LocalVertex, typename EdgeProperty> | |
3938 | struct tracking_level<boost::detail::parallel:: | |
3939 | msg_add_edge_with_property_data<Vertex, | |
3940 | LocalVertex, | |
3941 | EdgeProperty> > | |
3942 | : mpl::int_<track_never> {}; | |
3943 | ||
3944 | template<typename EdgeProperty, typename EdgeDescriptor> | |
3945 | struct tracking_level<boost::detail::parallel::msg_nonlocal_edge_data< | |
3946 | EdgeProperty,EdgeDescriptor> > | |
3947 | : mpl::int_<track_never> {}; | |
3948 | ||
3949 | template<typename EdgeDescriptor> | |
3950 | struct tracking_level< | |
3951 | boost::detail::parallel::msg_remove_edge_data<EdgeDescriptor> > | |
3952 | : mpl::int_<track_never> {}; | |
3953 | } | |
3954 | ||
3955 | // Hash function for global descriptors | |
3956 | template<typename LocalDescriptor> | |
3957 | struct hash<detail::parallel::global_descriptor<LocalDescriptor> > | |
3958 | { | |
3959 | typedef detail::parallel::global_descriptor<LocalDescriptor> argument_type; | |
3960 | std::size_t operator()(argument_type const& x) const | |
3961 | { | |
3962 | std::size_t hash = hash_value(x.owner); | |
3963 | hash_combine(hash, x.local); | |
3964 | return hash; | |
3965 | } | |
3966 | }; | |
3967 | ||
3968 | // Hash function for parallel edge descriptors | |
3969 | template<typename Edge> | |
3970 | struct hash<detail::parallel::edge_descriptor<Edge> > | |
3971 | { | |
3972 | typedef detail::parallel::edge_descriptor<Edge> argument_type; | |
3973 | ||
3974 | std::size_t operator()(argument_type const& x) const | |
3975 | { | |
3976 | std::size_t hash = hash_value(x.owner()); | |
3977 | hash_combine(hash, x.local); | |
3978 | return hash; | |
3979 | } | |
3980 | }; | |
3981 | ||
3982 | } // end namespace boost | |
3983 | ||
3984 | #include <boost/graph/distributed/adjlist/handlers.hpp> | |
3985 | #include <boost/graph/distributed/adjlist/initialize.hpp> | |
3986 | #include <boost/graph/distributed/adjlist/redistribute.hpp> | |
3987 | #include <boost/graph/distributed/adjlist/serialization.hpp> | |
3988 | ||
3989 | #endif // BOOST_GRAPH_DISTRIBUTED_ADJACENCY_LIST_HPP |