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 serialize(Archiver & ar,edge_base<Directed,Vertex> & e,const unsigned int)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 serialize(Archiver & ar,edge_desc_impl<Directed,Vertex> & e,const unsigned int)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 global_descriptorboost::detail::parallel::global_descriptor135 global_descriptor() : owner(), local() { } 136 global_descriptorboost::detail::parallel::global_descriptor137 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 generatorboost::detail::parallel::global_descriptor::generator154 generator() {} generatorboost::detail::parallel::global_descriptor::generator155 generator(processor_id_type owner) : owner(owner) {} 156 operator ()boost::detail::parallel::global_descriptor::generator157 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> serializeboost::detail::parallel::global_descriptor165 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> owner(const global_descriptor<LocalDescriptor> & v)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> local(const global_descriptor<LocalDescriptor> & v)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 operator ==(const global_descriptor<LocalDescriptor> & u,const global_descriptor<LocalDescriptor> & v)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 operator !=(const global_descriptor<LocalDescriptor> & u,const global_descriptor<LocalDescriptor> & v)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 operator <(const global_descriptor<LocalDescriptor> & u,const global_descriptor<LocalDescriptor> & v)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 operator <=(const global_descriptor<LocalDescriptor> & u,const global_descriptor<LocalDescriptor> & v)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 operator >(const global_descriptor<LocalDescriptor> & u,const global_descriptor<LocalDescriptor> & v)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 operator >=(const global_descriptor<LocalDescriptor> & u,const global_descriptor<LocalDescriptor> & v)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> get(global_descriptor_property_map<LocalDescriptor>,global_descriptor<LocalDescriptor> x)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 get(owner_property_map<LocalDescriptor>,global_descriptor<LocalDescriptor> x)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 get(local_descriptor_property_map<LocalDescriptor>,global_descriptor<LocalDescriptor> x)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 { stored_in_edgeboost::detail::parallel::stored_in_edge302 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 { edge_descriptorboost::detail::parallel::edge_descriptor318 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 ownerboost::detail::parallel::edge_descriptor324 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 out_generator()356 out_generator() : g(0) {} out_generator(const Graph & g)357 explicit out_generator(const Graph& g) : g(&g) {} 358 operator ()(argument_type e) const359 result_type operator()(argument_type e) const 360 { return map(e, directed_selector()); } 361 362 private: map(argument_type e,directedS) const363 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 map(argument_type e,bidirectionalS) const370 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 map(argument_type e,undirectedS) const377 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 in_generator()404 in_generator() : g(0) {} in_generator(const Graph & g)405 explicit in_generator(const Graph& g) : g(&g) {} 406 operator ()(argument_type e) const407 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 */ map(argument_type e,bidirectionalS) const415 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 */ map(argument_type e,undirectedS) const432 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> serializeboost::detail::parallel::edge_descriptor454 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 owner(const edge_descriptor<Edge> & e)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 local(const edge_descriptor<Edge> & e)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> get(edge_global_property_map<Edge>,const edge_descriptor<Edge> & e)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 get(edge_owner_property_map<Edge>,const edge_descriptor<Edge> & e)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 get(edge_local_property_map<Edge>,const edge_descriptor<Edge> & e)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 operator ==(const edge_descriptor<Edge> & e1,const edge_descriptor<Edge> & e2)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 operator !=(const edge_descriptor<Edge> & e1,const edge_descriptor<Edge> & e2)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 maybe_initialize_vertex_indices(IteratorPair p,VertexIndexMap to_index,read_write_property_map_tag)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 maybe_initialize_vertex_indices(IteratorPair p,VertexIndexMap to_index,readable_property_map_tag)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 maybe_initialize_vertex_indices(IteratorPair p,VertexIndexMap to_index)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 maybe_initialize_vertex_indices(IteratorPair p,::boost::detail::error_property_not_found)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 { msg_add_edge_databoost::detail::parallel::msg_add_edge_data696 msg_add_edge_data() { } 697 msg_add_edge_databoost::detail::parallel::msg_add_edge_data698 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> serializeboost::detail::parallel::msg_add_edge_data709 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: msg_add_edge_with_property_databoost::detail::parallel::msg_add_edge_with_property_data729 msg_add_edge_with_property_data() { } 730 msg_add_edge_with_property_databoost::detail::parallel::msg_add_edge_with_property_data731 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> serializeboost::detail::parallel::msg_add_edge_with_property_data738 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 remove_in_edge(typename Graph::edge_descriptor,Graph &,directedS)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 remove_in_edge(typename Graph::edge_descriptor e,Graph & g,bidirectionalS)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 remove_in_edge(typename Graph::edge_descriptor e,Graph & g,undirectedS)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> add_local_edge(typename Config::vertex_descriptor u,typename Config::vertex_descriptor v,const typename Config::edge_property_type & p,vec_adj_list_impl<Graph,Config,Base> & g_)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> add_local_edge(typename Config::vertex_descriptor u,typename Config::vertex_descriptor v,const typename Config::edge_property_type & p,boost::adj_list_impl<Graph,Config,Base> & g)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 msg_nonlocal_edge_databoost::detail::parallel::msg_nonlocal_edge_data1044 msg_nonlocal_edge_data() {} msg_nonlocal_edge_databoost::detail::parallel::msg_nonlocal_edge_data1045 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> serializeboost::detail::parallel::msg_nonlocal_edge_data1052 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; msg_remove_edge_databoost::detail::parallel::msg_remove_edge_data1062 msg_remove_edge_data() {} msg_remove_edge_databoost::detail::parallel::msg_remove_edge_data1063 explicit msg_remove_edge_data(edge_descriptor e) : e(e) {} 1064 1065 edge_descriptor e; 1066 1067 template<typename Archiver> serializeboost::detail::parallel::msg_remove_edge_data1068 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: adjacency_list(const ProcessGroup & pg=ProcessGroup ())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 adjacency_list(const ProcessGroup & pg,const base_distribution_type & distribution)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 adjacency_list(const GraphProperty & g,const ProcessGroup & pg=ProcessGroup ())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 adjacency_list(vertices_size_type n,const GraphProperty & p,const ProcessGroup & pg,const base_distribution_type & distribution)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 adjacency_list(vertices_size_type n,const ProcessGroup & pg,const base_distribution_type & distribution)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 adjacency_list(vertices_size_type n,const GraphProperty & p,const ProcessGroup & pg=ProcessGroup ())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 adjacency_list(vertices_size_type n,const ProcessGroup & pg=ProcessGroup ())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> adjacency_list(EdgeIterator first,EdgeIterator last,vertices_size_type n,const ProcessGroup & pg=ProcessGroup (),const GraphProperty & p=GraphProperty ())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> adjacency_list(EdgeIterator first,EdgeIterator last,EdgePropertyIterator ep_iter,vertices_size_type n,const ProcessGroup & pg=ProcessGroup (),const GraphProperty & p=GraphProperty ())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> adjacency_list(EdgeIterator first,EdgeIterator last,vertices_size_type n,const ProcessGroup & pg,const base_distribution_type & distribution,const GraphProperty & p=GraphProperty ())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> adjacency_list(EdgeIterator first,EdgeIterator last,EdgePropertyIterator ep_iter,vertices_size_type n,const ProcessGroup & pg,const base_distribution_type & distribution,const GraphProperty & p=GraphProperty ())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 ~adjacency_list()1653 ~adjacency_list() 1654 { 1655 synchronize(process_group_); 1656 } 1657 clear()1658 void clear() 1659 { 1660 base().clear(); 1661 local_edges_.clear(); 1662 named_graph_mixin::clearing_graph(); 1663 } 1664 swap(adjacency_list & other)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 null_vertex()1673 static vertex_descriptor null_vertex() 1674 { 1675 return vertex_descriptor(processor_id_type(0), 1676 inherited::null_vertex()); 1677 } 1678 base()1679 inherited& base() { return m_local_graph; } base() const1680 const inherited& base() const { return m_local_graph; } 1681 processor() const1682 processor_id_type processor() const { return process_id(process_group_); } process_group() const1683 process_group_type process_group() const { return process_group_.base(); } 1684 local_edges()1685 local_edge_list_type& local_edges() { return local_edges_; } local_edges() const1686 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 operator [](vertex_descriptor v)1694 vertex_bundled& operator[](vertex_descriptor v) 1695 { 1696 BOOST_ASSERT(v.owner == processor()); 1697 return base()[v.local]; 1698 } 1699 operator [](vertex_descriptor v) const1700 const vertex_bundled& operator[](vertex_descriptor v) const 1701 { 1702 BOOST_ASSERT(v.owner == processor()); 1703 return base()[v.local]; 1704 } 1705 operator [](edge_descriptor e)1706 edge_bundled& operator[](edge_descriptor e) 1707 { 1708 BOOST_ASSERT(e.owner() == processor()); 1709 return base()[e.local]; 1710 } 1711 operator [](edge_descriptor e) const1712 const edge_bundled& operator[](edge_descriptor e) const 1713 { 1714 BOOST_ASSERT(e.owner() == processor()); 1715 return base()[e.local]; 1716 } 1717 operator [](graph_bundle_t)1718 graph_bundled& operator[](graph_bundle_t) 1719 { return get_property(*this); } 1720 operator [](graph_bundle_t) const1721 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 request_in_neighbors(vertex_descriptor,VertexProcessorMap,directedS)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 request_in_neighbors(vertex_descriptor,VertexProcessorMap,undirectedS)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 clear_in_edges_local(vertex_descriptor v,directedS)1759 void clear_in_edges_local(vertex_descriptor v, directedS) {} clear_in_edges_local(vertex_descriptor v,undirectedS)1760 void clear_in_edges_local(vertex_descriptor v, undirectedS) {} 1761 clear_in_edges_local(vertex_descriptor v,bidirectionalS)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 remove_migrated_in_edges(vertex_descriptor,VertexProcessorMap,directedS)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 remove_migrated_in_edges(vertex_descriptor,VertexProcessorMap,undirectedS)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 build_vertex_property(const vertex_property_type & p)1836 build_vertex_property(const vertex_property_type& p) 1837 { return build_vertex_property(p, directed_selector()); } 1838 1839 base_vertex_property_type build_vertex_property(const vertex_property_type & p,directedS)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 build_vertex_property(const vertex_property_type & p,bidirectionalS)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 build_vertex_property(const vertex_property_type & p,undirectedS)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. build_edge_property(const edge_property_type & p)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 build_edge_property(const edge_property_type & p,directedS)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 build_edge_property(const edge_property_type & p,bidirectionalS)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 build_edge_property(const edge_property_type & p,undirectedS)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. split_edge_property(const base_edge_property_type & p)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 split_edge_property(const base_edge_property_type & p,directedS)1892 split_edge_property(const base_edge_property_type& p, directedS) 1893 { 1894 return p.m_base; 1895 } 1896 1897 edge_property_type split_edge_property(const base_edge_property_type & p,bidirectionalS)1898 split_edge_property(const base_edge_property_type& p, bidirectionalS) 1899 { 1900 return p.m_base; 1901 } 1902 1903 edge_property_type split_edge_property(const base_edge_property_type & p,undirectedS)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 send_remove_edge_request(edge_descriptor e)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 add_remote_edge(const msg_nonlocal_edge_data &,processor_id_type,directedS)2076 add_remote_edge(const msg_nonlocal_edge_data&, 2077 processor_id_type, directedS) 2078 { } 2079 2080 2081 /** 2082 * \overload 2083 */ 2084 void add_remote_edge(const msg_nonlocal_edge_data & data,processor_id_type other_proc,bidirectionalS)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 add_remote_edge(const msg_nonlocal_edge_data & data,processor_id_type other_proc,undirectedS)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 remove_local_edge(const msg_remove_edge_data &,processor_id_type,directedS)2116 remove_local_edge(const msg_remove_edge_data&, processor_id_type, 2117 directedS) 2118 { } 2119 2120 void remove_local_edge(const msg_remove_edge_data & data,processor_id_type other_proc,bidirectionalS)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 remove_local_edge(const msg_remove_edge_data & data,processor_id_type other_proc,undirectedS)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 remove_local_edge_from_list(vertex_descriptor,vertex_descriptor,directedS)2193 remove_local_edge_from_list(vertex_descriptor, vertex_descriptor, 2194 directedS) 2195 { 2196 } 2197 2198 void remove_local_edge_from_list(vertex_descriptor,vertex_descriptor,bidirectionalS)2199 remove_local_edge_from_list(vertex_descriptor, vertex_descriptor, 2200 bidirectionalS) 2201 { 2202 } 2203 2204 void remove_local_edge_from_list(vertex_descriptor src,vertex_descriptor tgt,undirectedS)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 lazy_add_vertex_with_propertyboost::PBGL_DISTRIB_ADJLIST_TYPE::lazy_add_vertex_with_property2246 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. lazy_add_vertex_with_propertyboost::PBGL_DISTRIB_ADJLIST_TYPE::lazy_add_vertex_with_property2253 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(). operator vertex_descriptorboost::PBGL_DISTRIB_ADJLIST_TYPE::lazy_add_vertex_with_property2265 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:: ~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:: commit() const2313 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 lazy_add_edgeboost::PBGL_DISTRIB_ADJLIST_TYPE::lazy_add_edge2351 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. lazy_add_edgeboost::PBGL_DISTRIB_ADJLIST_TYPE::lazy_add_edge2357 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(). operator std::pair<edge_descriptor,bool>boost::PBGL_DISTRIB_ADJLIST_TYPE::lazy_add_edge2369 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> ~lazy_add_edge()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> commit() const2417 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:: add_local_edge(const edge_property_type & property,directedS) const2438 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:: add_local_edge(const edge_property_type & property,bidirectionalS) const2464 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:: add_local_edge(const edge_property_type & property,undirectedS) const2498 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 lazy_add_edge_with_propertyboost::PBGL_DISTRIB_ADJLIST_TYPE::lazy_add_edge_with_property2550 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. lazy_add_edge_with_propertyboost::PBGL_DISTRIB_ADJLIST_TYPE::lazy_add_edge_with_property2558 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(). operator std::pair<edge_descriptor,bool>boost::PBGL_DISTRIB_ADJLIST_TYPE::lazy_add_edge_with_property2566 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:: ~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:: commit() const2606 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> vertices(const PBGL_DISTRIB_ADJLIST_TYPE & g)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 num_vertices(const PBGL_DISTRIB_ADJLIST_TYPE & g)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 source(const detail::parallel::edge_descriptor<Edge> & e,const PBGL_DISTRIB_ADJLIST_TYPE & g)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 target(const detail::parallel::edge_descriptor<Edge> & e,const PBGL_DISTRIB_ADJLIST_TYPE & g)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> out_edges(typename PBGL_DISTRIB_ADJLIST_TYPE::vertex_descriptor v,const PBGL_DISTRIB_ADJLIST_TYPE & g)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 out_degree(typename PBGL_DISTRIB_ADJLIST_TYPE::vertex_descriptor v,const PBGL_DISTRIB_ADJLIST_TYPE & g)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> in_edges(typename PBGL_DISTRIB_ADJLIST_TYPE_CONFIG (bidirectionalS)::vertex_descriptor v,const PBGL_DISTRIB_ADJLIST_TYPE_CONFIG (bidirectionalS)& g)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> in_edges(typename PBGL_DISTRIB_ADJLIST_TYPE_CONFIG (undirectedS)::vertex_descriptor v,const PBGL_DISTRIB_ADJLIST_TYPE_CONFIG (undirectedS)& g)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> PBGL_DISTRIB_ADJLIST_TYPE_CONFIG(bidirectionalS)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> PBGL_DISTRIB_ADJLIST_TYPE_CONFIG(undirectedS)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> PBGL_DISTRIB_ADJLIST_TYPE_CONFIG(undirectedS)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> PBGL_DISTRIB_ADJLIST_TYPE_CONFIG(bidirectionalS)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 num_edges(const PBGL_DISTRIB_ADJLIST_TYPE & g)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> PBGL_DISTRIB_ADJLIST_TYPE_CONFIG(undirectedS)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> edges(const PBGL_DISTRIB_ADJLIST_TYPE & g)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> edges(const PBGL_DISTRIB_ADJLIST_TYPE_CONFIG (undirectedS)& g)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 vertex(typename PBGL_DISTRIB_ADJLIST_TYPE::vertices_size_type n,const PBGL_DISTRIB_ADJLIST_TYPE & g)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 > edge(typename PBGL_DISTRIB_ADJLIST_TYPE_CONFIG (directedS)::vertex_descriptor u,typename PBGL_DISTRIB_ADJLIST_TYPE_CONFIG (directedS)::vertex_descriptor v,const PBGL_DISTRIB_ADJLIST_TYPE_CONFIG (directedS)& g)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 > edge(typename PBGL_DISTRIB_ADJLIST_TYPE::vertex_descriptor u,typename PBGL_DISTRIB_ADJLIST_TYPE::vertex_descriptor v,const PBGL_DISTRIB_ADJLIST_TYPE & g)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> adjacent_vertices(typename PBGL_DISTRIB_ADJLIST_TYPE::vertex_descriptor v,const PBGL_DISTRIB_ADJLIST_TYPE & g)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 add_edge(typename PBGL_DISTRIB_ADJLIST_TYPE::vertex_descriptor u,typename PBGL_DISTRIB_ADJLIST_TYPE::vertex_descriptor v,PBGL_DISTRIB_ADJLIST_TYPE & g)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 add_edge(typename PBGL_DISTRIB_ADJLIST_TYPE::vertex_descriptor u,typename PBGL_DISTRIB_ADJLIST_TYPE::vertex_descriptor v,typename PBGL_DISTRIB_ADJLIST_TYPE::edge_property_type const & p,PBGL_DISTRIB_ADJLIST_TYPE & g)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 remove_edge(typename PBGL_DISTRIB_ADJLIST_TYPE::edge_descriptor e,PBGL_DISTRIB_ADJLIST_TYPE & g)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 remove_edge(typename PBGL_DISTRIB_ADJLIST_TYPE::vertex_descriptor u,typename PBGL_DISTRIB_ADJLIST_TYPE::vertex_descriptor v,PBGL_DISTRIB_ADJLIST_TYPE & g)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 remove_edge(typename PBGL_DISTRIB_ADJLIST_TYPE::out_edge_iterator ei,PBGL_DISTRIB_ADJLIST_TYPE & g)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 remove_edge(typename PBGL_DISTRIB_ADJLIST_TYPE_CONFIG (directedS)::out_edge_iterator ei,PBGL_DISTRIB_ADJLIST_TYPE_CONFIG (directedS)& g)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 remove_out_edge_predicateboost::parallel::detail::remove_out_edge_predicate3090 remove_out_edge_predicate(Graph& g, Predicate& predicate) 3091 : g(g), predicate(predicate) { } 3092 operator ()boost::parallel::detail::remove_out_edge_predicate3093 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 remove_out_edge_if(typename PBGL_DISTRIB_ADJLIST_TYPE::vertex_descriptor u,Predicate predicate,PBGL_DISTRIB_ADJLIST_TYPE & g)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 remove_in_edge_predicateboost::parallel::detail::remove_in_edge_predicate3154 remove_in_edge_predicate(Graph& g, const Predicate& predicate) 3155 : g(g), predicate(predicate) { } 3156 3157 template<typename StoredEdge> operator ()boost::parallel::detail::remove_in_edge_predicate3158 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 remove_in_edge_if(typename PBGL_DISTRIB_ADJLIST_TYPE_CONFIG (bidirectionalS)::vertex_descriptor u,Predicate predicate,PBGL_DISTRIB_ADJLIST_TYPE_CONFIG (bidirectionalS)& g)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 remove_in_edge_if(typename PBGL_DISTRIB_ADJLIST_TYPE_CONFIG (undirectedS)::vertex_descriptor u,Predicate predicate,PBGL_DISTRIB_ADJLIST_TYPE_CONFIG (undirectedS)& g)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 remove_directed_edge_predicateboost::parallel::detail::remove_directed_edge_predicate3226 remove_directed_edge_predicate(Graph& g, const Predicate& predicate) 3227 : g(g), predicate(predicate) { } 3228 operator ()boost::parallel::detail::remove_directed_edge_predicate3229 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 remove_edge_if(Predicate predicate,PBGL_DISTRIB_ADJLIST_TYPE_CONFIG (directedS)& g)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 remove_edge_if(Predicate predicate,PBGL_DISTRIB_ADJLIST_TYPE_CONFIG (bidirectionalS)& g)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 remove_undirected_edge_predicateboost::parallel::detail::remove_undirected_edge_predicate3280 remove_undirected_edge_predicate(Graph& g, Predicate& predicate) 3281 : g(g), predicate(predicate) { } 3282 operator ()boost::parallel::detail::remove_undirected_edge_predicate3283 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 remove_edge_if(Predicate predicate,PBGL_DISTRIB_ADJLIST_TYPE_CONFIG (undirectedS)& g)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 operator ()boost::parallel::detail::always_true3323 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 clear_vertex(typename PBGL_DISTRIB_ADJLIST_TYPE_CONFIG (bidirectionalS)::vertex_descriptor u,PBGL_DISTRIB_ADJLIST_TYPE_CONFIG (bidirectionalS)& g)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 clear_vertex(typename PBGL_DISTRIB_ADJLIST_TYPE_CONFIG (undirectedS)::vertex_descriptor u,PBGL_DISTRIB_ADJLIST_TYPE_CONFIG (undirectedS)& g)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 clear_out_edges(typename PBGL_DISTRIB_ADJLIST_TYPE_CONFIG (directedS)::vertex_descriptor u,PBGL_DISTRIB_ADJLIST_TYPE_CONFIG (directedS)& g)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 clear_out_edges(typename PBGL_DISTRIB_ADJLIST_TYPE_CONFIG (bidirectionalS)::vertex_descriptor u,PBGL_DISTRIB_ADJLIST_TYPE_CONFIG (bidirectionalS)& g)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 clear_in_edges(typename PBGL_DISTRIB_ADJLIST_TYPE_CONFIG (bidirectionalS)::vertex_descriptor u,PBGL_DISTRIB_ADJLIST_TYPE_CONFIG (bidirectionalS)& g)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 add_vertex(PBGL_DISTRIB_ADJLIST_TYPE & g)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 add_vertex(typename PBGL_DISTRIB_ADJLIST_TYPE::vertex_property_type const & p,PBGL_DISTRIB_ADJLIST_TYPE & g)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 remove_vertex(typename PBGL_DISTRIB_ADJLIST_TYPE::vertex_descriptor u,PBGL_DISTRIB_ADJLIST_TYPE & g)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 get(Property p,PBGL_DISTRIB_ADJLIST_TYPE & g)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 get(Property p,const PBGL_DISTRIB_ADJLIST_TYPE & g)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 get(vertex_local_index_t,PBGL_DISTRIB_ADJLIST_TYPE & g)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 get(vertex_local_index_t,const PBGL_DISTRIB_ADJLIST_TYPE & g)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 get(vertex_global_t,const PBGL_DISTRIB_ADJLIST_TYPE & g)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 get(vertex_global_t,PBGL_DISTRIB_ADJLIST_TYPE & g)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 get(vertex_owner_t,PBGL_DISTRIB_ADJLIST_TYPE & g)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 get(vertex_owner_t,const PBGL_DISTRIB_ADJLIST_TYPE & g)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 get(vertex_owner_t,PBGL_DISTRIB_ADJLIST_TYPE &,typename PBGL_DISTRIB_ADJLIST_TYPE::vertex_descriptor v)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 get(vertex_owner_t,const PBGL_DISTRIB_ADJLIST_TYPE &,typename PBGL_DISTRIB_ADJLIST_TYPE::vertex_descriptor v)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 get(vertex_local_t,PBGL_DISTRIB_ADJLIST_TYPE & g)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 get(vertex_local_t,const PBGL_DISTRIB_ADJLIST_TYPE & g)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 get(vertex_local_t,PBGL_DISTRIB_ADJLIST_TYPE &,typename PBGL_DISTRIB_ADJLIST_TYPE::vertex_descriptor v)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 get(vertex_local_t,const PBGL_DISTRIB_ADJLIST_TYPE &,typename PBGL_DISTRIB_ADJLIST_TYPE::vertex_descriptor v)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 get(edge_global_t,const PBGL_DISTRIB_ADJLIST_TYPE & g)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 get(edge_global_t,PBGL_DISTRIB_ADJLIST_TYPE & g)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 get(edge_owner_t,PBGL_DISTRIB_ADJLIST_TYPE & g)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 get(edge_owner_t,const PBGL_DISTRIB_ADJLIST_TYPE & g)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 get(edge_local_t,PBGL_DISTRIB_ADJLIST_TYPE & g)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 get(edge_local_t,const PBGL_DISTRIB_ADJLIST_TYPE & g)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 get(Property p,const PBGL_DISTRIB_ADJLIST_TYPE & g,const Key & key)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 put(Property p,PBGL_DISTRIB_ADJLIST_TYPE & g,const Key & key,const Value & v)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 get(vertex_index_t vi,PBGL_DISTRIB_ADJLIST_TYPE & g)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 get(vertex_index_t vi,const PBGL_DISTRIB_ADJLIST_TYPE & g)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 get(T Bundle::* p,PBGL_DISTRIB_ADJLIST_TYPE & g)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 get(T Bundle::* p,const PBGL_DISTRIB_ADJLIST_TYPE & g)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> synchronize(const PBGL_DISTRIB_ADJLIST_TYPE & g)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 process_group(const PBGL_DISTRIB_ADJLIST_TYPE & g)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; operator ()boost::hash3960 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 operator ()boost::hash3974 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 3990