| Report problems to ATLAS LXR Team (with time and IP address indicated) |
|
[ source navigation ] [ diff markup ] [ identifier search ] [ general search ] |
||||
|
||||||
| Links to LXR source navigation pages for stable releases | [ 12.*.* ] [ 13.*.* ] [ 14.*.* ] [ 15.*.* ] | |||||
001 // -*- c++ -*- 002 //======================================================================= 003 // Copyright 1997, 1998, 1999, 2000 University of Notre Dame. 004 // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek 005 // 006 // Distributed under the Boost Software License, Version 1.0. (See 007 // accompanying file LICENSE_1_0.txt or copy at 008 // http://www.boost.org/LICENSE_1_0.txt) 009 //======================================================================= 010 011 #ifndef BOOST_GRAPH_DETAIL_ADJACENCY_LIST_HPP 012 #define BOOST_GRAPH_DETAIL_ADJACENCY_LIST_HPP 013 014 #include <map> // for vertex_map in copy_impl 015 #include <boost/config.hpp> 016 #include <boost/detail/workaround.hpp> 017 #include <boost/operators.hpp> 018 #include <boost/property_map.hpp> 019 #include <boost/pending/integer_range.hpp> 020 #include <boost/graph/graph_traits.hpp> 021 #include <memory> 022 #include <algorithm> 023 #include <boost/limits.hpp> 024 025 #include <boost/iterator/iterator_adaptor.hpp> 026 027 #include <boost/pending/ct_if.hpp> 028 #include <boost/graph/graph_concepts.hpp> 029 #include <boost/pending/container_traits.hpp> 030 #include <boost/graph/detail/adj_list_edge_iterator.hpp> 031 #include <boost/graph/properties.hpp> 032 #include <boost/pending/property.hpp> 033 #include <boost/graph/adjacency_iterator.hpp> 034 #include <boost/static_assert.hpp> 035 036 // Symbol truncation problems with MSVC, trying to shorten names. 037 #define stored_edge se_ 038 #define stored_edge_property sep_ 039 #define stored_edge_iter sei_ 040 041 /* 042 Outline for this file: 043 044 out_edge_iterator and in_edge_iterator implementation 045 edge_iterator for undirected graph 046 stored edge types (these object live in the out-edge/in-edge lists) 047 directed edges helper class 048 directed graph helper class 049 undirected graph helper class 050 bidirectional graph helper class 051 bidirectional graph helper class (without edge properties) 052 bidirectional graph helper class (with edge properties) 053 adjacency_list helper class 054 adj_list_impl class 055 vec_adj_list_impl class 056 adj_list_gen class 057 vertex property map 058 edge property map 059 060 061 Note: it would be nice to merge some of the undirected and 062 bidirectional code... it is awful similar. 063 */ 064 065 066 namespace boost { 067 068 namespace detail { 069 070 template <typename DirectedS> 071 struct directed_category_traits { 072 typedef directed_tag directed_category; 073 }; 074 075 template <> 076 struct directed_category_traits<directedS> { 077 typedef directed_tag directed_category; 078 }; 079 template <> 080 struct directed_category_traits<undirectedS> { 081 typedef undirected_tag directed_category; 082 }; 083 template <> 084 struct directed_category_traits<bidirectionalS> { 085 typedef bidirectional_tag directed_category; 086 }; 087 088 template <class Vertex> 089 struct target_is { 090 target_is(const Vertex& v) : m_target(v) { } 091 template <class StoredEdge> 092 bool operator()(const StoredEdge& e) const { 093 return e.get_target() == m_target; 094 } 095 Vertex m_target; 096 }; 097 098 // O(E/V) 099 template <class EdgeList, class vertex_descriptor> 100 void erase_from_incidence_list(EdgeList& el, vertex_descriptor v, 101 allow_parallel_edge_tag) 102 { 103 boost::graph_detail::erase_if(el, detail::target_is<vertex_descriptor>(v)); 104 } 105 // O(log(E/V)) 106 template <class EdgeList, class vertex_descriptor> 107 void erase_from_incidence_list(EdgeList& el, vertex_descriptor v, 108 disallow_parallel_edge_tag) 109 { 110 typedef typename EdgeList::value_type StoredEdge; 111 el.erase(StoredEdge(v)); 112 } 113 114 //========================================================================= 115 // Out-Edge and In-Edge Iterator Implementation 116 117 template <class BaseIter, class VertexDescriptor, class EdgeDescriptor, class Difference> 118 struct out_edge_iter 119 : iterator_adaptor< 120 out_edge_iter<BaseIter, VertexDescriptor, EdgeDescriptor, Difference> 121 , BaseIter 122 , EdgeDescriptor 123 , use_default 124 , EdgeDescriptor 125 , Difference 126 > 127 { 128 typedef iterator_adaptor< 129 out_edge_iter<BaseIter, VertexDescriptor, EdgeDescriptor, Difference> 130 , BaseIter 131 , EdgeDescriptor 132 , use_default 133 , EdgeDescriptor 134 , Difference 135 > super_t; 136 137 inline out_edge_iter() { } 138 inline out_edge_iter(const BaseIter& i, const VertexDescriptor& src) 139 : super_t(i), m_src(src) { } 140 141 inline EdgeDescriptor 142 dereference() const 143 { 144 return EdgeDescriptor(m_src, (*this->base()).get_target(), 145 &(*this->base()).get_property()); 146 } 147 VertexDescriptor m_src; 148 }; 149 150 template <class BaseIter, class VertexDescriptor, class EdgeDescriptor, class Difference> 151 struct in_edge_iter 152 : iterator_adaptor< 153 in_edge_iter<BaseIter, VertexDescriptor, EdgeDescriptor, Difference> 154 , BaseIter 155 , EdgeDescriptor 156 , use_default 157 , EdgeDescriptor 158 , Difference 159 > 160 { 161 typedef iterator_adaptor< 162 in_edge_iter<BaseIter, VertexDescriptor, EdgeDescriptor, Difference> 163 , BaseIter 164 , EdgeDescriptor 165 , use_default 166 , EdgeDescriptor 167 , Difference 168 > super_t; 169 170 inline in_edge_iter() { } 171 inline in_edge_iter(const BaseIter& i, const VertexDescriptor& src) 172 : super_t(i), m_src(src) { } 173 174 inline EdgeDescriptor 175 dereference() const 176 { 177 return EdgeDescriptor((*this->base()).get_target(), m_src, 178 &this->base()->get_property()); 179 } 180 VertexDescriptor m_src; 181 }; 182 183 //========================================================================= 184 // Undirected Edge Iterator Implementation 185 186 template <class EdgeIter, class EdgeDescriptor, class Difference> 187 struct undirected_edge_iter 188 : iterator_adaptor< 189 undirected_edge_iter<EdgeIter, EdgeDescriptor, Difference> 190 , EdgeIter 191 , EdgeDescriptor 192 , use_default 193 , EdgeDescriptor 194 , Difference 195 > 196 { 197 typedef iterator_adaptor< 198 undirected_edge_iter<EdgeIter, EdgeDescriptor, Difference> 199 , EdgeIter 200 , EdgeDescriptor 201 , use_default 202 , EdgeDescriptor 203 , Difference 204 > super_t; 205 206 undirected_edge_iter() {} 207 208 explicit undirected_edge_iter(EdgeIter i) 209 : super_t(i) {} 210 211 inline EdgeDescriptor 212 dereference() const { 213 return EdgeDescriptor( 214 (*this->base()).m_source 215 , (*this->base()).m_target 216 , &this->base()->get_property()); 217 } 218 }; 219 220 //========================================================================= 221 // Edge Storage Types (stored in the out-edge/in-edge lists) 222 223 template <class Vertex> 224 class stored_edge 225 : public boost::equality_comparable1< stored_edge<Vertex>, 226 boost::less_than_comparable1< stored_edge<Vertex> > > 227 { 228 public: 229 typedef no_property property_type; 230 inline stored_edge() { } 231 inline stored_edge(Vertex target, const no_property& = no_property()) 232 : m_target(target) { } 233 // Need to write this explicitly so stored_edge_property can 234 // invoke Base::operator= (at least, for SGI MIPSPro compiler) 235 inline stored_edge& operator=(const stored_edge& x) { 236 m_target = x.m_target; 237 return *this; 238 } 239 inline Vertex& get_target() const { return m_target; } 240 inline const no_property& get_property() const { return s_prop; } 241 inline bool operator==(const stored_edge& x) const 242 { return m_target == x.get_target(); } 243 inline bool operator<(const stored_edge& x) const 244 { return m_target < x.get_target(); } 245 //protected: need to add hash<> as a friend 246 static no_property s_prop; 247 // Sometimes target not used as key in the set, and in that case 248 // it is ok to change the target. 249 mutable Vertex m_target; 250 }; 251 template <class Vertex> 252 no_property stored_edge<Vertex>::s_prop; 253 254 template <class Vertex, class Property> 255 class stored_edge_property : public stored_edge<Vertex> { 256 typedef stored_edge_property self; 257 typedef stored_edge<Vertex> Base; 258 public: 259 typedef Property property_type; 260 inline stored_edge_property() { } 261 inline stored_edge_property(Vertex target, 262 const Property& p = Property()) 263 : stored_edge<Vertex>(target), m_property(new Property(p)) { } 264 stored_edge_property(const self& x) 265 : Base(x), m_property(const_cast<self&>(x).m_property) { } 266 self& operator=(const self& x) { 267 Base::operator=(x); 268 m_property = const_cast<self&>(x).m_property; 269 return *this; 270 } 271 inline Property& get_property() { return *m_property; } 272 inline const Property& get_property() const { return *m_property; } 273 protected: 274 // Holding the property by-value causes edge-descriptor 275 // invalidation for add_edge() with EdgeList=vecS. Instead we 276 // hold a pointer to the property. std::auto_ptr is not 277 // a perfect fit for the job, but it is darn close. 278 std::auto_ptr<Property> m_property; 279 }; 280 281 282 template <class Vertex, class Iter, class Property> 283 class stored_edge_iter 284 : public stored_edge<Vertex> 285 { 286 public: 287 typedef Property property_type; 288 inline stored_edge_iter() { } 289 inline stored_edge_iter(Vertex v) 290 : stored_edge<Vertex>(v) { } 291 inline stored_edge_iter(Vertex v, Iter i, void* = 0) 292 : stored_edge<Vertex>(v), m_iter(i) { } 293 inline Property& get_property() { return m_iter->get_property(); } 294 inline const Property& get_property() const { 295 return m_iter->get_property(); 296 } 297 inline Iter get_iter() const { return m_iter; } 298 protected: 299 Iter m_iter; 300 }; 301 302 // For when the EdgeList is a std::vector. 303 // Want to make the iterator stable, so use an offset 304 // instead of an iterator into a std::vector 305 template <class Vertex, class EdgeVec, class Property> 306 class stored_ra_edge_iter 307 : public stored_edge<Vertex> 308 { 309 typedef typename EdgeVec::iterator Iter; 310 public: 311 typedef Property property_type; 312 inline stored_ra_edge_iter() { } 313 inline stored_ra_edge_iter(Vertex v, Iter i = Iter(), 314 EdgeVec* edge_vec = 0) 315 : stored_edge<Vertex>(v), m_i(i - edge_vec->begin()), m_vec(edge_vec){ } 316 inline Property& get_property() { return (*m_vec)[m_i].get_property(); } 317 inline const Property& get_property() const { 318 return (*m_vec)[m_i].get_property(); 319 } 320 inline Iter get_iter() const { return m_vec->begin() + m_i; } 321 protected: 322 std::size_t m_i; 323 EdgeVec* m_vec; 324 }; 325 326 } // namespace detail 327 328 template <class Tag, class Vertex, class Property> 329 const typename property_value<Property,Tag>::type& 330 get(Tag property_tag, 331 const detail::stored_edge_property<Vertex, Property>& e) 332 { 333 return get_property_value(e.get_property(), property_tag); 334 } 335 336 template <class Tag, class Vertex, class Iter, class Property> 337 const typename property_value<Property,Tag>::type& 338 get(Tag property_tag, 339 const detail::stored_edge_iter<Vertex, Iter, Property>& e) 340 { 341 return get_property_value(e.get_property(), property_tag); 342 } 343 344 template <class Tag, class Vertex, class EdgeVec, class Property> 345 const typename property_value<Property,Tag>::type& 346 get(Tag property_tag, 347 const detail::stored_ra_edge_iter<Vertex, EdgeVec, Property>& e) 348 { 349 return get_property_value(e.get_property(), property_tag); 350 } 351 352 //========================================================================= 353 // Directed Edges Helper Class 354 355 namespace detail { 356 357 // O(E/V) 358 template <class edge_descriptor, class EdgeList, class StoredProperty> 359 inline void 360 remove_directed_edge_dispatch(edge_descriptor, EdgeList& el, 361 StoredProperty& p) 362 { 363 for (typename EdgeList::iterator i = el.begin(); 364 i != el.end(); ++i) 365 if (&(*i).get_property() == &p) { 366 el.erase(i); 367 return; 368 } 369 } 370 371 template <class incidence_iterator, class EdgeList, class Predicate> 372 inline void 373 remove_directed_edge_if_dispatch(incidence_iterator first, 374 incidence_iterator last, 375 EdgeList& el, Predicate pred, 376 boost::allow_parallel_edge_tag) 377 { 378 // remove_if 379 while (first != last && !pred(*first)) 380 ++first; 381 incidence_iterator i = first; 382 if (first != last) 383 for (; i != last; ++i) 384 if (!pred(*i)) { 385 *first.base() = *i.base(); 386 ++first; 387 } 388 el.erase(first.base(), el.end()); 389 } 390 template <class incidence_iterator, class EdgeList, class Predicate> 391 inline void 392 remove_directed_edge_if_dispatch(incidence_iterator first, 393 incidence_iterator last, 394 EdgeList& el, 395 Predicate pred, 396 boost::disallow_parallel_edge_tag) 397 { 398 for (incidence_iterator next = first; 399 first != last; first = next) { 400 ++next; 401 if (pred(*first)) 402 el.erase( first.base() ); 403 } 404 } 405 406 template <class PropT, class Graph, class incidence_iterator, 407 class EdgeList, class Predicate> 408 inline void 409 undirected_remove_out_edge_if_dispatch(Graph& g, 410 incidence_iterator first, 411 incidence_iterator last, 412 EdgeList& el, Predicate pred, 413 boost::allow_parallel_edge_tag) 414 { 415 typedef typename Graph::global_edgelist_selector EdgeListS; 416 BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value)); 417 418 // remove_if 419 while (first != last && !pred(*first)) 420 ++first; 421 incidence_iterator i = first; 422 bool self_loop_removed = false; 423 if (first != last) 424 for (; i != last; ++i) { 425 if (self_loop_removed) { 426 /* With self loops, the descriptor will show up 427 * twice. The first time it will be removed, and now it 428 * will be skipped. 429 */ 430 self_loop_removed = false; 431 } 432 else if (!pred(*i)) { 433 *first.base() = *i.base(); 434 ++first; 435 } else { 436 if (source(*i, g) == target(*i, g)) self_loop_removed = true; 437 else { 438 // Remove the edge from the target 439 detail::remove_directed_edge_dispatch 440 (*i, 441 g.out_edge_list(target(*i, g)), 442 *(PropT*)(*i).get_property()); 443 } 444 445 // Erase the edge property 446 g.m_edges.erase( (*i.base()).get_iter() ); 447 } 448 } 449 el.erase(first.base(), el.end()); 450 } 451 template <class PropT, class Graph, class incidence_iterator, 452 class EdgeList, class Predicate> 453 inline void 454 undirected_remove_out_edge_if_dispatch(Graph& g, 455 incidence_iterator first, 456 incidence_iterator last, 457 EdgeList& el, 458 Predicate pred, 459 boost::disallow_parallel_edge_tag) 460 { 461 typedef typename Graph::global_edgelist_selector EdgeListS; 462 BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value)); 463 464 for (incidence_iterator next = first; 465 first != last; first = next) { 466 ++next; 467 if (pred(*first)) { 468 if (source(*first, g) != target(*first, g)) { 469 // Remove the edge from the target 470 detail::remove_directed_edge_dispatch 471 (*first, 472 g.out_edge_list(target(*first, g)), 473 *(PropT*)(*first).get_property()); 474 } 475 476 // Erase the edge property 477 g.m_edges.erase( (*first.base()).get_iter() ); 478 479 // Erase the edge in the source 480 el.erase( first.base() ); 481 } 482 } 483 } 484 485 // O(E/V) 486 template <class edge_descriptor, class EdgeList, class StoredProperty> 487 inline void 488 remove_directed_edge_dispatch(edge_descriptor e, EdgeList& el, 489 no_property&) 490 { 491 for (typename EdgeList::iterator i = el.begin(); 492 i != el.end(); ++i) 493 if ((*i).get_target() == e.m_target) { 494 el.erase(i); 495 return; 496 } 497 } 498 499 } // namespace detail 500 501 template <class Config> 502 struct directed_edges_helper { 503 504 // Placement of these overloaded remove_edge() functions 505 // inside the class avoids a VC++ bug. 506 507 // O(E/V) 508 inline void 509 remove_edge(typename Config::edge_descriptor e) 510 { 511 typedef typename Config::graph_type graph_type; 512 graph_type& g = static_cast<graph_type&>(*this); 513 typename Config::OutEdgeList& el = g.out_edge_list(source(e, g)); 514 typedef typename Config::OutEdgeList::value_type::property_type PType; 515 detail::remove_directed_edge_dispatch(e, el, 516 *(PType*)e.get_property()); 517 } 518 519 // O(1) 520 inline void 521 remove_edge(typename Config::out_edge_iterator iter) 522 { 523 typedef typename Config::graph_type graph_type; 524 graph_type& g = static_cast<graph_type&>(*this); 525 typename Config::edge_descriptor e = *iter; 526 typename Config::OutEdgeList& el = g.out_edge_list(source(e, g)); 527 el.erase(iter.base()); 528 } 529 530 }; 531 532 // O(1) 533 template <class Config> 534 inline std::pair<typename Config::edge_iterator, 535 typename Config::edge_iterator> 536 edges(const directed_edges_helper<Config>& g_) 537 { 538 typedef typename Config::graph_type graph_type; 539 typedef typename Config::edge_iterator edge_iterator; 540 const graph_type& cg = static_cast<const graph_type&>(g_); 541 graph_type& g = const_cast<graph_type&>(cg); 542 return std::make_pair( edge_iterator(g.vertex_set().begin(), 543 g.vertex_set().begin(), 544 g.vertex_set().end(), g), 545 edge_iterator(g.vertex_set().begin(), 546 g.vertex_set().end(), 547 g.vertex_set().end(), g) ); 548 } 549 550 //========================================================================= 551 // Directed Graph Helper Class 552 553 struct adj_list_dir_traversal_tag : 554 public virtual vertex_list_graph_tag, 555 public virtual incidence_graph_tag, 556 public virtual adjacency_graph_tag, 557 public virtual edge_list_graph_tag { }; 558 559 template <class Config> 560 struct directed_graph_helper 561 : public directed_edges_helper<Config> { 562 typedef typename Config::edge_descriptor edge_descriptor; 563 typedef adj_list_dir_traversal_tag traversal_category; 564 }; 565 566 // O(E/V) 567 template <class Config> 568 inline void 569 remove_edge(typename Config::vertex_descriptor u, 570 typename Config::vertex_descriptor v, 571 directed_graph_helper<Config>& g_) 572 { 573 typedef typename Config::graph_type graph_type; 574 typedef typename Config::edge_parallel_category Cat; 575 graph_type& g = static_cast<graph_type&>(g_); 576 detail::erase_from_incidence_list(g.out_edge_list(u), v, Cat()); 577 } 578 579 template <class Config, class Predicate> 580 inline void 581 remove_out_edge_if(typename Config::vertex_descriptor u, Predicate pred, 582 directed_graph_helper<Config>& g_) 583 { 584 typedef typename Config::graph_type graph_type; 585 graph_type& g = static_cast<graph_type&>(g_); 586 typename Config::out_edge_iterator first, last; 587 tie(first, last) = out_edges(u, g); 588 typedef typename Config::edge_parallel_category edge_parallel_category; 589 detail::remove_directed_edge_if_dispatch 590 (first, last, g.out_edge_list(u), pred, edge_parallel_category()); 591 } 592 593 template <class Config, class Predicate> 594 inline void 595 remove_edge_if(Predicate pred, directed_graph_helper<Config>& g_) 596 { 597 typedef typename Config::graph_type graph_type; 598 graph_type& g = static_cast<graph_type&>(g_); 599 600 typename Config::vertex_iterator vi, vi_end; 601 for (tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi) 602 remove_out_edge_if(*vi, pred, g); 603 } 604 605 template <class EdgeOrIter, class Config> 606 inline void 607 remove_edge(EdgeOrIter e_or_iter, directed_graph_helper<Config>& g_) 608 { 609 g_.remove_edge(e_or_iter); 610 } 611 612 // O(V + E) for allow_parallel_edges 613 // O(V * log(E/V)) for disallow_parallel_edges 614 template <class Config> 615 inline void 616 clear_vertex(typename Config::vertex_descriptor u, 617 directed_graph_helper<Config>& g_) 618 { 619 typedef typename Config::graph_type graph_type; 620 typedef typename Config::edge_parallel_category Cat; 621 graph_type& g = static_cast<graph_type&>(g_); 622 typename Config::vertex_iterator vi, viend; 623 for (boost::tie(vi, viend) = vertices(g); vi != viend; ++vi) 624 detail::erase_from_incidence_list(g.out_edge_list(*vi), u, Cat()); 625 g.out_edge_list(u).clear(); 626 // clear() should be a req of Sequence and AssociativeContainer, 627 // or maybe just Container 628 } 629 630 template <class Config> 631 inline void 632 clear_out_edges(typename Config::vertex_descriptor u, 633 directed_graph_helper<Config>& g_) 634 { 635 typedef typename Config::graph_type graph_type; 636 typedef typename Config::edge_parallel_category Cat; 637 graph_type& g = static_cast<graph_type&>(g_); 638 g.out_edge_list(u).clear(); 639 // clear() should be a req of Sequence and AssociativeContainer, 640 // or maybe just Container 641 } 642 643 // O(V), could do better... 644 template <class Config> 645 inline typename Config::edges_size_type 646 num_edges(const directed_graph_helper<Config>& g_) 647 { 648 typedef typename Config::graph_type graph_type; 649 const graph_type& g = static_cast<const graph_type&>(g_); 650 typename Config::edges_size_type num_e = 0; 651 typename Config::vertex_iterator vi, vi_end; 652 for (boost::tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi) 653 num_e += out_degree(*vi, g); 654 return num_e; 655 } 656 // O(1) for allow_parallel_edge_tag 657 // O(log(E/V)) for disallow_parallel_edge_tag 658 template <class Config> 659 inline std::pair<typename directed_graph_helper<Config>::edge_descriptor, bool> 660 add_edge(typename Config::vertex_descriptor u, 661 typename Config::vertex_descriptor v, 662 const typename Config::edge_property_type& p, 663 directed_graph_helper<Config>& g_) 664 { 665 typedef typename Config::edge_descriptor edge_descriptor; 666 typedef typename Config::graph_type graph_type; 667 typedef typename Config::StoredEdge StoredEdge; 668 graph_type& g = static_cast<graph_type&>(g_); 669 typename Config::OutEdgeList::iterator i; 670 bool inserted; 671 boost::tie(i, inserted) = boost::graph_detail::push(g.out_edge_list(u), 672 StoredEdge(v, p)); 673 return std::make_pair(edge_descriptor(u, v, &(*i).get_property()), 674 inserted); 675 } 676 // Did not use default argument here because that 677 // causes Visual C++ to get confused. 678 template <class Config> 679 inline std::pair<typename Config::edge_descriptor, bool> 680 add_edge(typename Config::vertex_descriptor u, 681 typename Config::vertex_descriptor v, 682 directed_graph_helper<Config>& g_) 683 { 684 typename Config::edge_property_type p; 685 return add_edge(u, v, p, g_); 686 } 687 //========================================================================= 688 // Undirected Graph Helper Class 689 690 template <class Config> 691 struct undirected_graph_helper; 692 693 struct undir_adj_list_traversal_tag : 694 public virtual vertex_list_graph_tag, 695 public virtual incidence_graph_tag, 696 public virtual adjacency_graph_tag, 697 public virtual edge_list_graph_tag, 698 public virtual bidirectional_graph_tag { }; 699 700 namespace detail { 701 702 // using class with specialization for dispatch is a VC++ workaround. 703 template <class StoredProperty> 704 struct remove_undirected_edge_dispatch { 705 706 // O(E/V) 707 template <class edge_descriptor, class Config> 708 static void 709 apply(edge_descriptor e, 710 undirected_graph_helper<Config>& g_, 711 StoredProperty& p) 712 { 713 typedef typename Config::global_edgelist_selector EdgeListS; 714 BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value)); 715 716 typedef typename Config::graph_type graph_type; 717 graph_type& g = static_cast<graph_type&>(g_); 718 719 typename Config::OutEdgeList& out_el = g.out_edge_list(source(e, g)); 720 typename Config::OutEdgeList::iterator out_i = out_el.begin(); 721 for (; out_i != out_el.end(); ++out_i) 722 if (&(*out_i).get_property() == &p) { 723 out_el.erase(out_i); 724 break; 725 } 726 typename Config::OutEdgeList& in_el = g.out_edge_list(target(e, g)); 727 typename Config::OutEdgeList::iterator in_i = in_el.begin(); 728 for (; in_i != in_el.end(); ++in_i) 729 if (&(*in_i).get_property() == &p) { 730 g.m_edges.erase((*in_i).get_iter()); 731 in_el.erase(in_i); 732 return; 733 } 734 } 735 }; 736 737 template <> 738 struct remove_undirected_edge_dispatch<no_property> { 739 // O(E/V) 740 template <class edge_descriptor, class Config> 741 static void 742 apply(edge_descriptor e, 743 undirected_graph_helper<Config>& g_, 744 no_property&) 745 { 746 typedef typename Config::global_edgelist_selector EdgeListS; 747 BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value)); 748 749 typedef typename Config::graph_type graph_type; 750 graph_type& g = static_cast<graph_type&>(g_); 751 no_property* p = (no_property*)e.get_property(); 752 typename Config::OutEdgeList& out_el = g.out_edge_list(source(e, g)); 753 typename Config::OutEdgeList::iterator out_i = out_el.begin(); 754 for (; out_i != out_el.end(); ++out_i) 755 if (&(*out_i).get_property() == p) { 756 out_el.erase(out_i); 757 break; 758 } 759 typename Config::OutEdgeList& in_el = g.out_edge_list(target(e, g)); 760 typename Config::OutEdgeList::iterator in_i = in_el.begin(); 761 for (; in_i != in_el.end(); ++in_i) 762 if (&(*in_i).get_property() == p) { 763 g.m_edges.erase((*in_i).get_iter()); 764 in_el.erase(in_i); 765 return; 766 } 767 } 768 }; 769 770 // O(E/V) 771 template <class Graph, class EdgeList, class Vertex> 772 inline void 773 remove_edge_and_property(Graph& g, EdgeList& el, Vertex v, 774 boost::allow_parallel_edge_tag cat) 775 { 776 typedef typename Graph::global_edgelist_selector EdgeListS; 777 BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value)); 778 779 typedef typename EdgeList::value_type StoredEdge; 780 typename EdgeList::iterator i = el.begin(), end = el.end(); 781 for (; i != end; ++i) 782 if ((*i).get_target() == v) 783 g.m_edges.erase((*i).get_iter()); 784 detail::erase_from_incidence_list(el, v, cat); 785 } 786 // O(log(E/V)) 787 template <class Graph, class EdgeList, class Vertex> 788 inline void 789 remove_edge_and_property(Graph& g, EdgeList& el, Vertex v, 790 boost::disallow_parallel_edge_tag) 791 { 792 typedef typename Graph::global_edgelist_selector EdgeListS; 793 BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value)); 794 795 typedef typename EdgeList::value_type StoredEdge; 796 typename EdgeList::iterator i = el.find(StoredEdge(v)), end = el.end(); 797 if (i != end) { 798 g.m_edges.erase((*i).get_iter()); 799 el.erase(i); 800 } 801 } 802 803 } // namespace detail 804 805 template <class Vertex, class EdgeProperty> 806 struct list_edge // short name due to VC++ truncation and linker problems 807 : public boost::detail::edge_base<boost::undirected_tag, Vertex> 808 { 809 typedef EdgeProperty property_type; 810 typedef boost::detail::edge_base<boost::undirected_tag, Vertex> Base; 811 list_edge(Vertex u, Vertex v, const EdgeProperty& p = EdgeProperty()) 812 : Base(u, v), m_property(p) { } 813 EdgeProperty& get_property() { return m_property; } 814 const EdgeProperty& get_property() const { return m_property; } 815 // the following methods should never be used, but are needed 816 // to make SGI MIPSpro C++ happy 817 list_edge() { } 818 bool operator==(const list_edge&) const { return false; } 819 bool operator<(const list_edge&) const { return false; } 820 EdgeProperty m_property; 821 }; 822 823 template <class Config> 824 struct undirected_graph_helper { 825 826 typedef undir_adj_list_traversal_tag traversal_category; 827 828 // Placement of these overloaded remove_edge() functions 829 // inside the class avoids a VC++ bug. 830 831 // O(E/V) 832 inline void 833 remove_edge(typename Config::edge_descriptor e) 834 { 835 typedef typename Config::global_edgelist_selector EdgeListS; 836 BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value)); 837 838 typedef typename Config::OutEdgeList::value_type::property_type PType; 839 detail::remove_undirected_edge_dispatch<PType>::apply 840 (e, *this, *(PType*)e.get_property()); 841 } 842 // O(E/V) 843 inline void 844 remove_edge(typename Config::out_edge_iterator iter) 845 { 846 this->remove_edge(*iter); 847 } 848 }; 849 850 // Had to make these non-members to avoid accidental instantiation 851 // on SGI MIPSpro C++ 852 template <class C> 853 inline typename C::InEdgeList& 854 in_edge_list(undirected_graph_helper<C>&, 855 typename C::vertex_descriptor v) 856 { 857 typename C::stored_vertex* sv = (typename C::stored_vertex*)v; 858 return sv->m_out_edges; 859 } 860 template <class C> 861 inline const typename C::InEdgeList& 862 in_edge_list(const undirected_graph_helper<C>&, 863 typename C::vertex_descriptor v) { 864 typename C::stored_vertex* sv = (typename C::stored_vertex*)v; 865 return sv->m_out_edges; 866 } 867 868 // O(E/V) 869 template <class EdgeOrIter, class Config> 870 inline void 871 remove_edge(EdgeOrIter e, undirected_graph_helper<Config>& g_) 872 { 873 typedef typename Config::global_edgelist_selector EdgeListS; 874 BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value)); 875 876 g_.remove_edge(e); 877 } 878 879 // O(E/V) or O(log(E/V)) 880 template <class Config> 881 void 882 remove_edge(typename Config::vertex_descriptor u, 883 typename Config::vertex_descriptor v, 884 undirected_graph_helper<Config>& g_) 885 { 886 typedef typename Config::global_edgelist_selector EdgeListS; 887 BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value)); 888 889 typedef typename Config::graph_type graph_type; 890 graph_type& g = static_cast<graph_type&>(g_); 891 typedef typename Config::edge_parallel_category Cat; 892 detail::remove_edge_and_property(g, g.out_edge_list(u), v, Cat()); 893 detail::erase_from_incidence_list(g.out_edge_list(v), u, Cat()); 894 } 895 896 template <class Config, class Predicate> 897 void 898 remove_out_edge_if(typename Config::vertex_descriptor u, Predicate pred, 899 undirected_graph_helper<Config>& g_) 900 { 901 typedef typename Config::global_edgelist_selector EdgeListS; 902 BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value)); 903 904 typedef typename Config::graph_type graph_type; 905 typedef typename Config::OutEdgeList::value_type::property_type PropT; 906 graph_type& g = static_cast<graph_type&>(g_); 907 typename Config::out_edge_iterator first, last; 908 tie(first, last) = out_edges(u, g); 909 typedef typename Config::edge_parallel_category Cat; 910 detail::undirected_remove_out_edge_if_dispatch<PropT> 911 (g, first, last, g.out_edge_list(u), pred, Cat()); 912 } 913 template <class Config, class Predicate> 914 void 915 remove_in_edge_if(typename Config::vertex_descriptor u, Predicate pred, 916 undirected_graph_helper<Config>& g_) 917 { 918 typedef typename Config::global_edgelist_selector EdgeListS; 919 BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value)); 920 921 remove_out_edge_if(u, pred, g_); 922 } 923 924 // O(E/V * E) or O(log(E/V) * E) 925 template <class Predicate, class Config> 926 void 927 remove_edge_if(Predicate pred, undirected_graph_helper<Config>& g_) 928 { 929 typedef typename Config::global_edgelist_selector EdgeListS; 930 BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value)); 931 932 typedef typename Config::graph_type graph_type; 933 graph_type& g = static_cast<graph_type&>(g_); 934 typename Config::edge_iterator ei, ei_end, next; 935 tie(ei, ei_end) = edges(g); 936 for (next = ei; ei != ei_end; ei = next) { 937 ++next; 938 if (pred(*ei)) 939 remove_edge(*ei, g); 940 } 941 } 942 943 // O(1) 944 template <class Config> 945 inline std::pair<typename Config::edge_iterator, 946 typename Config::edge_iterator> 947 edges(const undirected_graph_helper<Config>& g_) 948 { 949 typedef typename Config::graph_type graph_type; 950 typedef typename Config::edge_iterator edge_iterator; 951 const graph_type& cg = static_cast<const graph_type&>(g_); 952 graph_type& g = const_cast<graph_type&>(cg); 953 return std::make_pair( edge_iterator(g.m_edges.begin()), 954 edge_iterator(g.m_edges.end()) ); 955 } 956 // O(1) 957 template <class Config> 958 inline typename Config::edges_size_type 959 num_edges(const undirected_graph_helper<Config>& g_) 960 { 961 typedef typename Config::graph_type graph_type; 962 const graph_type& g = static_cast<const graph_type&>(g_); 963 return g.m_edges.size(); 964 } 965 // O(E/V * E/V) 966 template <class Config> 967 inline void 968 clear_vertex(typename Config::vertex_descriptor u, 969 undirected_graph_helper<Config>& g_) 970 { 971 typedef typename Config::global_edgelist_selector EdgeListS; 972 BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value)); 973 974 typedef typename Config::graph_type graph_type; 975 typedef typename Config::edge_parallel_category Cat; 976 graph_type& g = static_cast<graph_type&>(g_); 977 typename Config::OutEdgeList& el = g.out_edge_list(u); 978 typename Config::OutEdgeList::iterator 979 ei = el.begin(), ei_end = el.end(); 980 for (; ei != ei_end; ++ei) { 981 detail::erase_from_incidence_list 982 (g.out_edge_list((*ei).get_target()), u, Cat()); 983 g.m_edges.erase((*ei).get_iter()); 984 } 985 g.out_edge_list(u).clear(); 986 } 987 // O(1) for allow_parallel_edge_tag 988 // O(log(E/V)) for disallow_parallel_edge_tag 989 template <class Config> 990 inline std::pair<typename Config::edge_descriptor, bool> 991 add_edge(typename Config::vertex_descriptor u, 992 typename Config::vertex_descriptor v, 993 const typename Config::edge_property_type& p, 994 undirected_graph_helper<Config>& g_) 995 { 996 typedef typename Config::StoredEdge StoredEdge; 997 typedef typename Config::edge_descriptor edge_descriptor; 998 typedef typename Config::graph_type graph_type; 999 graph_type& g = static_cast<graph_type&>(g_); 1000 1001 bool inserted; 1002 typename Config::EdgeContainer::value_type e(u, v, p); 1003 typename Config::EdgeContainer::iterator p_iter 1004 = graph_detail::push(g.m_edges, e).first; 1005 1006 typename Config::OutEdgeList::iterator i; 1007 boost::tie(i, inserted) = boost::graph_detail::push(g.out_edge_list(u), 1008 StoredEdge(v, p_iter, &g.m_edges)); 1009 if (inserted) { 1010 boost::graph_detail::push(g.out_edge_list(v), StoredEdge(u, p_iter, &g.m_edges)); 1011 return std::make_pair(edge_descriptor(u, v, &p_iter->get_property()), 1012 true); 1013 } else { 1014 g.m_edges.erase(p_iter); 1015 return std::make_pair 1016 (edge_descriptor(u, v, &i->get_iter()->get_property()), false); 1017 } 1018 } 1019 template <class Config> 1020 inline std::pair<typename Config::edge_descriptor, bool> 1021 add_edge(typename Config::vertex_descriptor u, 1022 typename Config::vertex_descriptor v, 1023 undirected_graph_helper<Config>& g_) 1024 { 1025 typename Config::edge_property_type p; 1026 return add_edge(u, v, p, g_); 1027 } 1028 1029 // O(1) 1030 template <class Config> 1031 inline typename Config::degree_size_type 1032 degree(typename Config::vertex_descriptor u, 1033 const undirected_graph_helper<Config>& g_) 1034 { 1035 typedef typename Config::graph_type Graph; 1036 const Graph& g = static_cast<const Graph&>(g_); 1037 return out_degree(u, g); 1038 } 1039 1040 template <class Config> 1041 inline std::pair<typename Config::in_edge_iterator, 1042 typename Config::in_edge_iterator> 1043 in_edges(typename Config::vertex_descriptor u, 1044 const undirected_graph_helper<Config>& g_) 1045 { 1046 typedef typename Config::graph_type Graph; 1047 const Graph& cg = static_cast<const Graph&>(g_); 1048 Graph& g = const_cast<Graph&>(cg); 1049 typedef typename Config::in_edge_iterator in_edge_iterator; 1050 return 1051 std::make_pair(in_edge_iterator(g.out_edge_list(u).begin(), u), 1052 in_edge_iterator(g.out_edge_list(u).end(), u)); 1053 } 1054 1055 template <class Config> 1056 inline typename Config::degree_size_type 1057 in_degree(typename Config::vertex_descriptor u, 1058 const undirected_graph_helper<Config>& g_) 1059 { return degree(u, g_); } 1060 1061 //========================================================================= 1062 // Bidirectional Graph Helper Class 1063 1064 struct bidir_adj_list_traversal_tag : 1065 public virtual vertex_list_graph_tag, 1066 public virtual incidence_graph_tag, 1067 public virtual adjacency_graph_tag, 1068 public virtual edge_list_graph_tag, 1069 public virtual bidirectional_graph_tag { }; 1070 1071 template <class Config> 1072 struct bidirectional_graph_helper 1073 : public directed_edges_helper<Config> { 1074 typedef bidir_adj_list_traversal_tag traversal_category; 1075 }; 1076 1077 // Had to make these non-members to avoid accidental instantiation 1078 // on SGI MIPSpro C++ 1079 template <class C> 1080 inline typename C::InEdgeList& 1081 in_edge_list(bidirectional_graph_helper<C>&, 1082 typename C::vertex_descriptor v) 1083 { 1084 typename C::stored_vertex* sv = (typename C::stored_vertex*)v; 1085 return sv->m_in_edges; 1086 } 1087 template <class C> 1088 inline const typename C::InEdgeList& 1089 in_edge_list(const bidirectional_graph_helper<C>&, 1090 typename C::vertex_descriptor v) { 1091 typename C::stored_vertex* sv = (typename C::stored_vertex*)v; 1092 return sv->m_in_edges; 1093 } 1094 1095 template <class Predicate, class Config> 1096 inline void 1097 remove_edge_if(Predicate pred, bidirectional_graph_helper<Config>& g_) 1098 { 1099 typedef typename Config::global_edgelist_selector EdgeListS; 1100 BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value)); 1101 1102 typedef typename Config::graph_type graph_type; 1103 graph_type& g = static_cast<graph_type&>(g_); 1104 typename Config::edge_iterator ei, ei_end, next; 1105 tie(ei, ei_end) = edges(g); 1106 for (next = ei; ei != ei_end; ei = next) { 1107 ++next; 1108 if (pred(*ei)) 1109 remove_edge(*ei, g); 1110 } 1111 } 1112 1113 template <class Config> 1114 inline std::pair<typename Config::in_edge_iterator, 1115 typename Config::in_edge_iterator> 1116 in_edges(typename Config::vertex_descriptor u, 1117 const bidirectional_graph_helper<Config>& g_) 1118 { 1119 typedef typename Config::graph_type graph_type; 1120 const graph_type& cg = static_cast<const graph_type&>(g_); 1121 graph_type& g = const_cast<graph_type&>(cg); 1122 typedef typename Config::in_edge_iterator in_edge_iterator; 1123 return 1124 std::make_pair(in_edge_iterator(in_edge_list(g, u).begin(), u), 1125 in_edge_iterator(in_edge_list(g, u).end(), u)); 1126 } 1127 1128 // O(1) 1129 template <class Config> 1130 inline std::pair<typename Config::edge_iterator, 1131 typename Config::edge_iterator> 1132 edges(const bidirectional_graph_helper<Config>& g_) 1133 { 1134 typedef typename Config::graph_type graph_type; 1135 typedef typename Config::edge_iterator edge_iterator; 1136 const graph_type& cg = static_cast<const graph_type&>(g_); 1137 graph_type& g = const_cast<graph_type&>(cg); 1138 return std::make_pair( edge_iterator(g.m_edges.begin()), 1139 edge_iterator(g.m_edges.end()) ); 1140 } 1141 1142 //========================================================================= 1143 // Bidirectional Graph Helper Class (with edge properties) 1144 1145 1146 template <class Config> 1147 struct bidirectional_graph_helper_with_property 1148 : public bidirectional_graph_helper<Config> 1149 { 1150 typedef typename Config::graph_type graph_type; 1151 typedef typename Config::out_edge_iterator out_edge_iterator; 1152 1153 std::pair<out_edge_iterator, out_edge_iterator> 1154 get_parallel_edge_sublist(typename Config::edge_descriptor e, 1155 const graph_type& g, 1156 void*) 1157 { return out_edges(source(e, g), g); } 1158 1159 std::pair<out_edge_iterator, out_edge_iterator> 1160 get_parallel_edge_sublist(typename Config::edge_descriptor e, 1161 const graph_type& g, 1162 setS*) 1163 { return edge_range(source(e, g), target(e, g), g); } 1164 1165 std::pair<out_edge_iterator, out_edge_iterator> 1166 get_parallel_edge_sublist(typename Config::edge_descriptor e, 1167 const graph_type& g, 1168 multisetS*) 1169 { return edge_range(source(e, g), target(e, g), g); } 1170 1171 #if !defined BOOST_NO_HASH 1172 std::pair<out_edge_iterator, out_edge_iterator> 1173 get_parallel_edge_sublist(typename Config::edge_descriptor e, 1174 const graph_type& g, 1175 hash_setS*) 1176 { return edge_range(source(e, g), target(e, g), g); } 1177 #endif 1178 1179 // Placement of these overloaded remove_edge() functions 1180 // inside the class avoids a VC++ bug. 1181 1182 // O(E/V) or O(log(E/V)) 1183 void 1184 remove_edge(typename Config::edge_descriptor e) 1185 { 1186 typedef typename Config::global_edgelist_selector EdgeListS; 1187 BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value)); 1188 1189 graph_type& g = static_cast<graph_type&>(*this); 1190 1191 typedef typename Config::edgelist_selector OutEdgeListS; 1192 1193 std::pair<out_edge_iterator, out_edge_iterator> rng = 1194 get_parallel_edge_sublist(e, g, (OutEdgeListS*)(0)); 1195 rng.first = std::find(rng.first, rng.second, e); 1196 assert(rng.first != rng.second); 1197 remove_edge(rng.first); 1198 } 1199 1200 inline void 1201 remove_edge(typename Config::out_edge_iterator iter) 1202 { 1203 typedef typename Config::global_edgelist_selector EdgeListS; 1204 BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value)); 1205 1206 typedef typename Config::graph_type graph_type; 1207 graph_type& g = static_cast<graph_type&>(*this); 1208 typename Config::edge_descriptor e = *iter; 1209 typename Config::OutEdgeList& oel = g.out_edge_list(source(e, g)); 1210 typename Config::InEdgeList& iel = in_edge_list(g, target(e, g)); 1211 typedef typename Config::OutEdgeList::value_type::property_type PType; 1212 PType& p = *(PType*)e.get_property(); 1213 detail::remove_directed_edge_dispatch(*iter, iel, p); 1214 g.m_edges.erase(iter.base()->get_iter()); 1215 oel.erase(iter.base()); 1216 } 1217 }; 1218 1219 // O(E/V) for allow_parallel_edge_tag 1220 // O(log(E/V)) for disallow_parallel_edge_tag 1221 template <class Config> 1222 inline void 1223 remove_edge(typename Config::vertex_descriptor u, 1224 typename Config::vertex_descriptor v, 1225 bidirectional_graph_helper_with_property<Config>& g_) 1226 { 1227 typedef typename Config::global_edgelist_selector EdgeListS; 1228 BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value)); 1229 1230 typedef typename Config::graph_type graph_type; 1231 graph_type& g = static_cast<graph_type&>(g_); 1232 typedef typename Config::edge_parallel_category Cat; 1233 detail::remove_edge_and_property(g, g.out_edge_list(u), v, Cat()); 1234 detail::erase_from_incidence_list(in_edge_list(g, v), u, Cat()); 1235 } 1236 1237 // O(E/V) or O(log(E/V)) 1238 template <class EdgeOrIter, class Config> 1239 inline void 1240 remove_edge(EdgeOrIter e, 1241 bidirectional_graph_helper_with_property<Config>& g_) 1242 { 1243 typedef typename Config::global_edgelist_selector EdgeListS; 1244 BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value)); 1245 1246 g_.remove_edge(e); 1247 } 1248 1249 template <class Config, class Predicate> 1250 inline void 1251 remove_out_edge_if(typename Config::vertex_descriptor u, Predicate pred, 1252 bidirectional_graph_helper_with_property<Config>& g_) 1253 { 1254 typedef typename Config::global_edgelist_selector EdgeListS; 1255 BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value)); 1256 1257 typedef typename Config::graph_type graph_type; 1258 typedef typename Config::OutEdgeList::value_type::property_type PropT; 1259 graph_type& g = static_cast<graph_type&>(g_); 1260 1261 typedef typename Config::EdgeIter EdgeIter; 1262 typedef std::vector<EdgeIter> Garbage; 1263 Garbage garbage; 1264 1265 // First remove the edges from the targets' in-edge lists and 1266 // from the graph's edge set list. 1267 typename Config::out_edge_iterator out_i, out_end; 1268 for (tie(out_i, out_end) = out_edges(u, g); out_i != out_end; ++out_i) 1269 if (pred(*out_i)) { 1270 detail::remove_directed_edge_dispatch 1271 (*out_i, in_edge_list(g, target(*out_i, g)), 1272 *(PropT*)(*out_i).get_property()); 1273 // Put in garbage to delete later. Will need the properties 1274 // for the remove_if of the out-edges. 1275 garbage.push_back((*out_i.base()).get_iter()); 1276 } 1277 1278 // Now remove the edges from this out-edge list. 1279 typename Config::out_edge_iterator first, last; 1280 tie(first, last) = out_edges(u, g); 1281 typedef typename Config::edge_parallel_category Cat; 1282 detail::remove_directed_edge_if_dispatch 1283 (first, last, g.out_edge_list(u), pred, Cat()); 1284 1285 // Now delete the edge properties from the g.m_edges list 1286 for (typename Garbage::iterator i = garbage.begin(); 1287 i != garbage.end(); ++i) 1288 g.m_edges.erase(*i); 1289 } 1290 template <class Config, class Predicate> 1291 inline void 1292 remove_in_edge_if(typename Config::vertex_descriptor v, Predicate pred, 1293 bidirectional_graph_helper_with_property<Config>& g_) 1294 { 1295 typedef typename Config::global_edgelist_selector EdgeListS; 1296 BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value)); 1297 1298 typedef typename Config::graph_type graph_type; 1299 typedef typename Config::OutEdgeList::value_type::property_type PropT; 1300 graph_type& g = static_cast<graph_type&>(g_); 1301 1302 typedef typename Config::EdgeIter EdgeIter; 1303 typedef std::vector<EdgeIter> Garbage; 1304 Garbage garbage; 1305 1306 // First remove the edges from the sources' out-edge lists and 1307 // from the graph's edge set list. 1308 typename Config::in_edge_iterator in_i, in_end; 1309 for (tie(in_i, in_end) = in_edges(v, g); in_i != in_end; ++in_i) 1310 if (pred(*in_i)) { 1311 typename Config::vertex_descriptor u = source(*in_i, g); 1312 detail::remove_directed_edge_dispatch 1313 (*in_i, g.out_edge_list(u), *(PropT*)(*in_i).get_property()); 1314 // Put in garbage to delete later. Will need the properties 1315 // for the remove_if of the out-edges. 1316 garbage.push_back((*in_i.base()).get_iter()); 1317 } 1318 // Now remove the edges from this in-edge list. 1319 typename Config::in_edge_iterator first, last; 1320 tie(first, last) = in_edges(v, g); 1321 typedef typename Config::edge_parallel_category Cat; 1322 detail::remove_directed_edge_if_dispatch 1323 (first, last, in_edge_list(g, v), pred, Cat()); 1324 1325 // Now delete the edge properties from the g.m_edges list 1326 for (typename Garbage::iterator i = garbage.begin(); 1327 i != garbage.end(); ++i) 1328 g.m_edges.erase(*i); 1329 } 1330 1331 // O(1) 1332 template <class Config> 1333 inline typename Config::edges_size_type 1334 num_edges(const bidirectional_graph_helper_with_property<Config>& g_) 1335 { 1336 typedef typename Config::graph_type graph_type; 1337 const graph_type& g = static_cast<const graph_type&>(g_); 1338 return g.m_edges.size(); 1339 } 1340 // O(E/V * E/V) for allow_parallel_edge_tag 1341 // O(E/V * log(E/V)) for disallow_parallel_edge_tag 1342 template <class Config> 1343 inline void 1344 clear_vertex(typename Config::vertex_descriptor u, 1345 bidirectional_graph_helper_with_property<Config>& g_) 1346 { 1347 typedef typename Config::global_edgelist_selector EdgeListS; 1348 BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value)); 1349 1350 typedef typename Config::graph_type graph_type; 1351 typedef typename Config::edge_parallel_category Cat; 1352 graph_type& g = static_cast<graph_type&>(g_); 1353 typename Config::OutEdgeList& el = g.out_edge_list(u); 1354 typename Config::OutEdgeList::iterator 1355 ei = el.begin(), ei_end = el.end(); 1356 for (; ei != ei_end; ++ei) { 1357 detail::erase_from_incidence_list 1358 (in_edge_list(g, (*ei).get_target()), u, Cat()); 1359 g.m_edges.erase((*ei).get_iter()); 1360 } 1361 typename Config::InEdgeList& in_el = in_edge_list(g, u); 1362 typename Config::InEdgeList::iterator 1363 in_ei = in_el.begin(), in_ei_end = in_el.end(); 1364 for (; in_ei != in_ei_end; ++in_ei) { 1365 detail::erase_from_incidence_list 1366 (g.out_edge_list((*in_ei).get_target()), u, Cat()); 1367 g.m_edges.erase((*in_ei).get_iter()); 1368 } 1369 g.out_edge_list(u).clear(); 1370 in_edge_list(g, u).clear(); 1371 } 1372 1373 template <class Config> 1374 inline void 1375 clear_out_edges(typename Config::vertex_descriptor u, 1376 bidirectional_graph_helper_with_property<Config>& g_) 1377 { 1378 typedef typename Config::global_edgelist_selector EdgeListS; 1379 BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value)); 1380 1381 typedef typename Config::graph_type graph_type; 1382 typedef typename Config::edge_parallel_category Cat; 1383 graph_type& g = static_cast<graph_type&>(g_); 1384 typename Config::OutEdgeList& el = g.out_edge_list(u); 1385 typename Config::OutEdgeList::iterator 1386 ei = el.begin(), ei_end = el.end(); 1387 for (; ei != ei_end; ++ei) { 1388 detail::erase_from_incidence_list 1389 (in_edge_list(g, (*ei).get_target()), u, Cat()); 1390 g.m_edges.erase((*ei).get_iter()); 1391 } 1392 g.out_edge_list(u).clear(); 1393 } 1394 1395 template <class Config> 1396 inline void 1397 clear_in_edges(typename Config::vertex_descriptor u, 1398 bidirectional_graph_helper_with_property<Config>& g_) 1399 { 1400 typedef typename Config::global_edgelist_selector EdgeListS; 1401 BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value)); 1402 1403 typedef typename Config::graph_type graph_type; 1404 typedef typename Config::edge_parallel_category Cat; 1405 graph_type& g = static_cast<graph_type&>(g_); 1406 typename Config::InEdgeList& in_el = in_edge_list(g, u); 1407 typename Config::InEdgeList::iterator 1408 in_ei = in_el.begin(), in_ei_end = in_el.end(); 1409 for (; in_ei != in_ei_end; ++in_ei) { 1410 detail::erase_from_incidence_list 1411 (g.out_edge_list((*in_ei).get_target()), u, Cat()); 1412 g.m_edges.erase((*in_ei).get_iter()); 1413 } 1414 in_edge_list(g, u).clear(); 1415 } 1416 1417 // O(1) for allow_parallel_edge_tag 1418 // O(log(E/V)) for disallow_parallel_edge_tag 1419 template <class Config> 1420 inline std::pair<typename Config::edge_descriptor, bool> 1421 add_edge(typename Config::vertex_descriptor u, 1422 typename Config::vertex_descriptor v, 1423 const typename Config::edge_property_type& p, 1424 bidirectional_graph_helper_with_property<Config>& g_) 1425 { 1426 typedef typename Config::graph_type graph_type; 1427 graph_type& g = static_cast<graph_type&>(g_); 1428 typedef typename Config::edge_descriptor edge_descriptor; 1429 typedef typename Config::StoredEdge StoredEdge; 1430 bool inserted; 1431 typename Config::EdgeContainer::value_type e(u, v, p); 1432 typename Config::EdgeContainer::iterator p_iter 1433 = graph_detail::push(g.m_edges, e).first; 1434 typename Config::OutEdgeList::iterator i; 1435 boost::tie(i, inserted) = boost::graph_detail::push(g.out_edge_list(u), 1436 StoredEdge(v, p_iter, &g.m_edges)); 1437 if (inserted) { 1438 boost::graph_detail::push(in_edge_list(g, v), StoredEdge(u, p_iter, &g.m_edges)); 1439 return std::make_pair(edge_descriptor(u, v, &p_iter->m_property), 1440 true); 1441 } else { 1442 g.m_edges.erase(p_iter); 1443 return std::make_pair(edge_descriptor(u, v, 1444 &i->get_iter()->get_property()), 1445 false); 1446 } 1447 } 1448 1449 template <class Config> 1450 inline std::pair<typename Config::edge_descriptor, bool> 1451 add_edge(typename Config::vertex_descriptor u, 1452 typename Config::vertex_descriptor v, 1453 bidirectional_graph_helper_with_property<Config>& g_) 1454 { 1455 typename Config::edge_property_type p; 1456 return add_edge(u, v, p, g_); 1457 } 1458 // O(1) 1459 template <class Config> 1460 inline typename Config::degree_size_type 1461 degree(typename Config::vertex_descriptor u, 1462 const bidirectional_graph_helper_with_property<Config>& g_) 1463 { 1464 typedef typename Config::graph_type graph_type; 1465 const graph_type& g = static_cast<const graph_type&>(g_); 1466 return in_degree(u, g) + out_degree(u, g); 1467 } 1468 1469 //========================================================================= 1470 // Adjacency List Helper Class 1471 1472 template <class Config, class Base> 1473 struct adj_list_helper : public Base 1474 { 1475 typedef typename Config::graph_type AdjList; 1476 typedef typename Config::vertex_descriptor vertex_descriptor; 1477 typedef typename Config::edge_descriptor edge_descriptor; 1478 typedef typename Config::out_edge_iterator out_edge_iterator; 1479 typedef typename Config::in_edge_iterator in_edge_iterator; 1480 typedef typename Config::adjacency_iterator adjacency_iterator; 1481 typedef typename Config::inv_adjacency_iterator inv_adjacency_iterator; 1482 typedef typename Config::vertex_iterator vertex_iterator; 1483 typedef typename Config::edge_iterator edge_iterator; 1484 typedef typename Config::directed_category directed_category; 1485 typedef typename Config::edge_parallel_category edge_parallel_category; 1486 typedef typename Config::vertices_size_type vertices_size_type; 1487 typedef typename Config::edges_size_type edges_size_type; 1488 typedef typename Config::degree_size_type degree_size_type; 1489 typedef typename Config::StoredEdge StoredEdge; 1490 typedef typename Config::edge_property_type edge_property_type; 1491 1492 typedef typename Config::global_edgelist_selector 1493 global_edgelist_selector; 1494 1495 // protected: 1496 1497 // The edge_dispatch() functions should be static, but 1498 // Borland gets confused about constness. 1499 1500 // O(E/V) 1501 inline std::pair<edge_descriptor,bool> 1502 edge_dispatch(const AdjList& g, 1503 vertex_descriptor u, vertex_descriptor v, 1504 boost::allow_parallel_edge_tag) const 1505 { 1506 bool found; 1507 const typename Config::OutEdgeList& el = g.out_edge_list(u); 1508 typename Config::OutEdgeList::const_iterator 1509 i = std::find_if(el.begin(), el.end(), 1510 detail::target_is<vertex_descriptor>(v)); 1511 found = (i != g.out_edge_list(u).end()); 1512 if (found) 1513 return std::make_pair(edge_descriptor(u, v, &(*i).get_property()), 1514 true); 1515 else 1516 return std::make_pair(edge_descriptor(u, v, 0), false); 1517 } 1518 // O(log(E/V)) 1519 inline std::pair<edge_descriptor,bool> 1520 edge_dispatch(const AdjList& g, 1521 vertex_descriptor u, vertex_descriptor v, 1522 boost::disallow_parallel_edge_tag) const 1523 { 1524 bool found; 1525 /* According to the standard, this should be iterator, not const_iterator, 1526 but the VC++ std::set::find() const returns const_iterator. 1527 And since iterator should be convertible to const_iterator, the 1528 following should work everywhere. -Jeremy */ 1529 typename Config::OutEdgeList::const_iterator 1530 i = g.out_edge_list(u).find(StoredEdge(v)), 1531 end = g.out_edge_list(u).end(); 1532 found = (i != end); 1533 if (found) 1534 return std::make_pair(edge_descriptor(u, v, &(*i).get_property()), 1535 true); 1536 else 1537 return std::make_pair(edge_descriptor(u, v, 0), false); 1538 } 1539 }; 1540 1541 template <class Config, class Base> 1542 inline std::pair<typename Config::adjacency_iterator, 1543 typename Config::adjacency_iterator> 1544 adjacent_vertices(typename Config::vertex_descriptor u, 1545 const adj_list_helper<Config, Base>& g_) 1546 { 1547 typedef typename Config::graph_type AdjList; 1548 const AdjList& cg = static_cast<const AdjList&>(g_); 1549 AdjList& g = const_cast<AdjList&>(cg); 1550 typedef typename Config::adjacency_iterator adjacency_iterator; 1551 typename Config::out_edge_iterator first, last; 1552 boost::tie(first, last) = out_edges(u, g); 1553 return std::make_pair(adjacency_iterator(first, &g), 1554 adjacency_iterator(last, &g)); 1555 } 1556 template <class Config, class Base> 1557 inline std::pair<typename Config::inv_adjacency_iterator, 1558 typename Config::inv_adjacency_iterator> 1559 inv_adjacent_vertices(typename Config::vertex_descriptor u, 1560 const adj_list_helper<Config, Base>& g_) 1561 { 1562 typedef typename Config::graph_type AdjList; 1563 const AdjList& cg = static_cast<const AdjList&>(g_); 1564 AdjList& g = const_cast<AdjList&>(cg); 1565 typedef typename Config::inv_adjacency_iterator inv_adjacency_iterator; 1566 typename Config::in_edge_iterator first, last; 1567 boost::tie(first, last) = in_edges(u, g); 1568 return std::make_pair(inv_adjacency_iterator(first, &g), 1569 inv_adjacency_iterator(last, &g)); 1570 } 1571 template <class Config, class Base> 1572 inline std::pair<typename Config::out_edge_iterator, 1573 typename Config::out_edge_iterator> 1574 out_edges(typename Config::vertex_descriptor u, 1575 const adj_list_helper<Config, Base>& g_) 1576 { 1577 typedef typename Config::graph_type AdjList; 1578 typedef typename Config::out_edge_iterator out_edge_iterator; 1579 const AdjList& cg = static_cast<const AdjList&>(g_); 1580 AdjList& g = const_cast<AdjList&>(cg); 1581 return 1582 std::make_pair(out_edge_iterator(g.out_edge_list(u).begin(), u), 1583 out_edge_iterator(g.out_edge_list(u).end(), u)); 1584 } 1585 template <class Config, class Base> 1586 inline std::pair<typename Config::vertex_iterator, 1587 typename Config::vertex_iterator> 1588 vertices(const adj_list_helper<Config, Base>& g_) 1589 { 1590 typedef typename Config::graph_type AdjList; 1591 const AdjList& cg = static_cast<const AdjList&>(g_); 1592 AdjList& g = const_cast<AdjList&>(cg); 1593 return std::make_pair( g.vertex_set().begin(), g.vertex_set().end() ); 1594 } 1595 template <class Config, class Base> 1596 inline typename Config::vertices_size_type 1597 num_vertices(const adj_list_helper<Config, Base>& g_) 1598 { 1599 typedef typename Config::graph_type AdjList; 1600 const AdjList& g = static_cast<const AdjList&>(g_); 1601 return g.vertex_set().size(); 1602 } 1603 template <class Config, class Base> 1604 inline typename Config::degree_size_type 1605 out_degree(typename Config::vertex_descriptor u, 1606 const adj_list_helper<Config, Base>& g_) 1607 { 1608 typedef typename Config::graph_type AdjList; 1609 const AdjList& g = static_cast<const AdjList&>(g_); 1610 return g.out_edge_list(u).size(); 1611 } 1612 template <class Config, class Base> 1613 inline std::pair<typename Config::edge_descriptor, bool> 1614 edge(typename Config::vertex_descriptor u, 1615 typename Config::vertex_descriptor v, 1616 const adj_list_helper<Config, Base>& g_) 1617 { 1618 typedef typename Config::graph_type Graph; 1619 typedef typename Config::edge_parallel_category Cat; 1620 const Graph& g = static_cast<const Graph&>(g_); 1621 return g_.edge_dispatch(g, u, v, Cat()); 1622 } 1623 template <class Config, class Base> 1624 inline std::pair<typename Config::out_edge_iterator, 1625 typename Config::out_edge_iterator> 1626 edge_range(typename Config::vertex_descriptor u, 1627 typename Config::vertex_descriptor v, 1628 const adj_list_helper<Config, Base>& g_) 1629 { 1630 typedef typename Config::graph_type Graph; 1631 typedef typename Config::StoredEdge StoredEdge; 1632 const Graph& cg = static_cast<const Graph&>(g_); 1633 Graph& g = const_cast<Graph&>(cg); 1634 typedef typename Config::out_edge_iterator out_edge_iterator; 1635 typename Config::OutEdgeList& el = g.out_edge_list(u); 1636 typename Config::OutEdgeList::iterator first, last; 1637 typename Config::EdgeContainer fake_edge_container; 1638 tie(first, last) = 1639 std::equal_range(el.begin(), el.end(), 1640 StoredEdge(v, fake_edge_container.end(), 1641 &fake_edge_container)); 1642 return std::make_pair(out_edge_iterator(first, u), 1643 out_edge_iterator(last, u)); 1644 } 1645 1646 template <class Config> 1647 inline typename Config::degree_size_type 1648 in_degree(typename Config::vertex_descriptor u, 1649 const directed_edges_helper<Config>& g_) 1650 { 1651 typedef typename Config::graph_type Graph; 1652 const Graph& cg = static_cast<const Graph&>(g_); 1653 Graph& g = const_cast<Graph&>(cg); 1654 return in_edge_list(g, u).size(); 1655 } 1656 1657 namespace detail { 1658 template <class Config, class Base, class Property> 1659 inline 1660 typename boost::property_map<typename Config::graph_type, 1661 Property>::type 1662 get_dispatch(adj_list_helper<Config,Base>&, Property, 1663 boost::edge_property_tag) { 1664 typedef typename Config::graph_type Graph; 1665 typedef typename boost::property_map<Graph, Property>::type PA; 1666 return PA(); 1667 } 1668 template <class Config, class Base, class Property> 1669 inline 1670 typename boost::property_map<typename Config::graph_type, 1671 Property>::const_type 1672 get_dispatch(const adj_list_helper<Config,Base>&, Property, 1673 boost::edge_property_tag) { 1674 typedef typename Config::graph_type Graph; 1675 typedef typename boost::property_map<Graph, Property>::const_type PA; 1676 return PA(); 1677 } 1678 1679 template <class Config, class Base, class Property> 1680 inline 1681 typename boost::property_map<typename Config::graph_type, 1682 Property>::type 1683 get_dispatch(adj_list_helper<Config,Base>& g, Property, 1684 boost::vertex_property_tag) { 1685 typedef typename Config::graph_type Graph; 1686 typedef typename boost::property_map<Graph, Property>::type PA; 1687 return PA(&static_cast<Graph&>(g)); 1688 } 1689 template <class Config, class Base, class Property> 1690 inline 1691 typename boost::property_map<typename Config::graph_type, 1692 Property>::const_type 1693 get_dispatch(const adj_list_helper<Config, Base>& g, Property, 1694 boost::vertex_property_tag) { 1695 typedef typename Config::graph_type Graph; 1696 typedef typename boost::property_map<Graph, Property>::const_type PA; 1697 const Graph& cg = static_cast<const Graph&>(g); 1698 return PA(&cg); 1699 } 1700 1701 } // namespace detail 1702 1703 // Implementation of the PropertyGraph interface 1704 template <class Config, class Base, class Property> 1705 inline 1706 typename boost::property_map<typename Config::graph_type, Property>::type 1707 get(Property p, adj_list_helper<Config, Base>& g) { 1708 typedef typename property_kind<Property>::type Kind; 1709 return detail::get_dispatch(g, p, Kind()); 1710 } 1711 template <class Config, class Base, class Property> 1712 inline 1713 typename boost::property_map<typename Config::graph_type, 1714 Property>::const_type 1715 get(Property p, const adj_list_helper<Config, Base>& g) { 1716 typedef typename property_kind<Property>::type Kind; 1717 return detail::get_dispatch(g, p, Kind()); 1718 } 1719 1720 template <class Config, class Base, class Property, class Key> 1721 inline 1722 typename boost::property_traits< 1723 typename boost::property_map<typename Config::graph_type, 1724 Property>::type 1725 >::reference 1726 get(Property p, adj_list_helper<Config, Base>& g, const Key& key) { 1727 return get(get(p, g), key); 1728 } 1729 1730 template <class Config, class Base, class Property, class Key> 1731 inline 1732 typename boost::property_traits< 1733 typename boost::property_map<typename Config::graph_type, 1734 Property>::const_type 1735 >::reference 1736 get(Property p, const adj_list_helper<Config, Base>& g, const Key& key) { 1737 return get(get(p, g), key); 1738 } 1739 1740 template <class Config, class Base, class Property, class Key,class Value> 1741 inline void 1742 put(Property p, adj_list_helper<Config, Base>& g, 1743 const Key& key, const Value& value) 1744 { 1745 typedef typename Config::graph_type Graph; 1746 typedef typename boost::property_map<Graph, Property>::type Map; 1747 Map pmap = get(p, static_cast<Graph&>(g)); 1748 put(pmap, key, value); 1749 } 1750 1751 1752 //========================================================================= 1753 // Generalize Adjacency List Implementation 1754 1755 struct adj_list_tag { }; 1756 1757 template <class Derived, class Config, class Base> 1758 class adj_list_impl 1759 : public adj_list_helper<Config, Base> 1760 { 1761 typedef typename Config::OutEdgeList OutEdgeList; 1762 typedef typename Config::InEdgeList InEdgeList; 1763 typedef typename Config::StoredVertexList StoredVertexList; 1764 public: 1765 typedef typename Config::stored_vertex stored_vertex; 1766 typedef typename Config::EdgeContainer EdgeContainer; 1767 typedef typename Config::vertex_descriptor vertex_descriptor; 1768 typedef typename Config::edge_descriptor edge_descriptor; 1769 typedef typename Config::vertex_iterator vertex_iterator; 1770 typedef typename Config::edge_iterator edge_iterator; 1771 typedef typename Config::edge_parallel_category edge_parallel_category; 1772 typedef typename Config::vertices_size_type vertices_size_type; 1773 typedef typename Config::edges_size_type edges_size_type; 1774 typedef typename Config::degree_size_type degree_size_type; 1775 typedef typename Config::edge_property_type edge_property_type; 1776 typedef adj_list_tag graph_tag; 1777 1778 static vertex_descriptor null_vertex() 1779 { 1780 return 0; 1781 } 1782 1783 inline adj_list_impl() { } 1784 1785 inline adj_list_impl(const adj_list_impl& x) { 1786 copy_impl(x); 1787 } 1788 inline adj_list_impl& operator=(const adj_list_impl& x) { 1789 this->clear(); 1790 copy_impl(x); 1791 return *this; 1792 } 1793 inline void clear() { 1794 for (typename StoredVertexList::iterator i = m_vertices.begin(); 1795 i != m_vertices.end(); ++i) 1796 delete (stored_vertex*)*i; 1797 m_vertices.clear(); 1798 m_edges.clear(); 1799 } 1800 inline adj_list_impl(vertices_size_type num_vertices) { 1801 for (vertices_size_type i = 0; i < num_vertices; ++i) 1802 add_vertex(static_cast<Derived&>(*this)); 1803 } 1804 template <class EdgeIterator> 1805 inline adj_list_impl(vertices_size_type num_vertices, 1806 EdgeIterator first, EdgeIterator last) 1807 { 1808 vertex_descriptor* v = new vertex_descriptor[num_vertices]; 1809 for (vertices_size_type i = 0; i < num_vertices; ++i) 1810 v[i] = add_vertex(static_cast<Derived&>(*this)); 1811 1812 while (first != last) { 1813 add_edge(v[(*first).first], v[(*first).second], *this); 1814 ++first; 1815 } 1816 delete [] v; 1817 } 1818 template <class EdgeIterator, class EdgePropertyIterator> 1819 inline adj_list_impl(vertices_size_type num_vertices, 1820 EdgeIterator first, EdgeIterator last, 1821 EdgePropertyIterator ep_iter) 1822 { 1823 vertex_descriptor* v = new vertex_descriptor[num_vertices]; 1824 for (vertices_size_type i = 0; i < num_vertices; ++i) 1825 v[i] = add_vertex(static_cast<Derived&>(*this)); 1826 1827 while (first != last) { 1828 add_edge(v[(*first).first], v[(*first).second], *ep_iter, *this); 1829 ++first; 1830 ++ep_iter; 1831 } 1832 delete [] v; 1833 } 1834 ~adj_list_impl() { 1835 for (typename StoredVertexList::iterator i = m_vertices.begin(); 1836 i != m_vertices.end(); ++i) 1837 delete (stored_vertex*)*i; 1838 } 1839 // protected: 1840 inline OutEdgeList& out_edge_list(vertex_descriptor v) { 1841 stored_vertex* sv = (stored_vertex*)v; 1842 return sv->m_out_edges; 1843 } 1844 inline const OutEdgeList& out_edge_list(vertex_descriptor v) const { 1845 stored_vertex* sv = (stored_vertex*)v; 1846 return sv->m_out_edges; 1847 } 1848 inline StoredVertexList& vertex_set() { return m_vertices; } 1849 inline const StoredVertexList& vertex_set() const { return m_vertices; } 1850 1851 inline void copy_impl(const adj_list_impl& x_) 1852 { 1853 const Derived& x = static_cast<const Derived&>(x_); 1854 1855 // Would be better to have a constant time way to get from 1856 // vertices in x to the corresponding vertices in *this. 1857 std::map<stored_vertex*,stored_vertex*> vertex_map; 1858 1859 // Copy the stored vertex objects by adding each vertex 1860 // and copying its property object. 1861 vertex_iterator vi, vi_end; 1862 for (tie(vi, vi_end) = vertices(x); vi != vi_end; ++vi) { 1863 stored_vertex* v = (stored_vertex*)add_vertex(*this); 1864 v->m_property = ((stored_vertex*)*vi)->m_property; 1865 vertex_map[(stored_vertex*)*vi] = v; 1866 } 1867 // Copy the edges by adding each edge and copying its 1868 // property object. 1869 edge_iterator ei, ei_end; 1870 for (tie(ei, ei_end) = edges(x); ei != ei_end; ++ei) { 1871 edge_descriptor e; 1872 bool inserted; 1873 vertex_descriptor s = source(*ei,x), t = target(*ei,x); 1874 tie(e, inserted) = add_edge(vertex_map[(stored_vertex*)s], 1875 vertex_map[(stored_vertex*)t], *this); 1876 *((edge_property_type*)e.m_eproperty) 1877 = *((edge_property_type*)(*ei).m_eproperty); 1878 } 1879 } 1880 1881 1882 typename Config::EdgeContainer m_edges; 1883 StoredVertexList m_vertices; 1884 }; 1885 1886 // O(1) 1887 template <class Derived, class Config, class Base> 1888 inline typename Config::vertex_descriptor 1889 add_vertex(adj_list_impl<Derived, Config, Base>& g_) 1890 { 1891 Derived& g = static_cast<Derived&>(g_);