1 // -*- c++ -*- 2 //======================================================================= 3 // Copyright 1997, 1998, 1999, 2000 University of Notre Dame. 4 // Copyright 2010 Thomas Claveirole 5 // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek, Thomas Claveirole 6 // 7 // Distributed under the Boost Software License, Version 1.0. (See 8 // accompanying file LICENSE_1_0.txt or copy at 9 // http://www.boost.org/LICENSE_1_0.txt) 10 //======================================================================= 11 12 #ifndef BOOST_GRAPH_DETAIL_ADJACENCY_LIST_HPP 13 #define BOOST_GRAPH_DETAIL_ADJACENCY_LIST_HPP 14 15 #include <map> // for vertex_map in copy_impl 16 #include <boost/config.hpp> 17 #include <boost/detail/workaround.hpp> 18 #include <boost/operators.hpp> 19 #include <boost/property_map/property_map.hpp> 20 #include <boost/pending/container_traits.hpp> 21 #include <boost/range/irange.hpp> 22 #include <boost/graph/graph_traits.hpp> 23 #include <memory> 24 #include <algorithm> 25 #include <boost/limits.hpp> 26 27 #include <boost/iterator/iterator_adaptor.hpp> 28 29 #include <boost/mpl/if.hpp> 30 #include <boost/mpl/not.hpp> 31 #include <boost/mpl/and.hpp> 32 #include <boost/graph/graph_concepts.hpp> 33 #include <boost/pending/container_traits.hpp> 34 #include <boost/graph/detail/adj_list_edge_iterator.hpp> 35 #include <boost/graph/properties.hpp> 36 #include <boost/pending/property.hpp> 37 #include <boost/graph/adjacency_iterator.hpp> 38 #include <boost/static_assert.hpp> 39 #include <boost/assert.hpp> 40 41 #ifdef BOOST_NO_CXX11_RVALUE_REFERENCES 42 #define BOOST_GRAPH_MOVE_IF_POSSIBLE(x) (x) 43 #else 44 #include <utility> 45 #define BOOST_GRAPH_MOVE_IF_POSSIBLE(x) (std::move((x))) 46 #endif 47 48 /* 49 Outline for this file: 50 51 out_edge_iterator and in_edge_iterator implementation 52 edge_iterator for undirected graph 53 stored edge types (these object live in the out-edge/in-edge lists) 54 directed edges helper class 55 directed graph helper class 56 undirected graph helper class 57 bidirectional graph helper class 58 bidirectional graph helper class (without edge properties) 59 bidirectional graph helper class (with edge properties) 60 adjacency_list helper class 61 adj_list_impl class 62 vec_adj_list_impl class 63 adj_list_gen class 64 vertex property map 65 edge property map 66 67 68 Note: it would be nice to merge some of the undirected and 69 bidirectional code... it is awful similar. 70 */ 71 72 73 namespace boost { 74 75 namespace detail { 76 77 template <typename DirectedS> 78 struct directed_category_traits { 79 typedef directed_tag directed_category; 80 }; 81 82 template <> 83 struct directed_category_traits<directedS> { 84 typedef directed_tag directed_category; 85 }; 86 template <> 87 struct directed_category_traits<undirectedS> { 88 typedef undirected_tag directed_category; 89 }; 90 template <> 91 struct directed_category_traits<bidirectionalS> { 92 typedef bidirectional_tag directed_category; 93 }; 94 95 template <class Vertex> 96 struct target_is { target_isboost::detail::target_is97 target_is(const Vertex& v) : m_target(v) { } 98 template <class StoredEdge> operator ()boost::detail::target_is99 bool operator()(const StoredEdge& e) const { 100 return e.get_target() == m_target; 101 } 102 Vertex m_target; 103 }; 104 105 // O(E/V) 106 template <class EdgeList, class vertex_descriptor> erase_from_incidence_list(EdgeList & el,vertex_descriptor v,allow_parallel_edge_tag)107 void erase_from_incidence_list(EdgeList& el, vertex_descriptor v, 108 allow_parallel_edge_tag) 109 { 110 boost::graph_detail::erase_if(el, detail::target_is<vertex_descriptor>(v)); 111 } 112 // O(log(E/V)) 113 template <class EdgeList, class vertex_descriptor> erase_from_incidence_list(EdgeList & el,vertex_descriptor v,disallow_parallel_edge_tag)114 void erase_from_incidence_list(EdgeList& el, vertex_descriptor v, 115 disallow_parallel_edge_tag) 116 { 117 typedef typename EdgeList::value_type StoredEdge; 118 el.erase(StoredEdge(v)); 119 } 120 121 //========================================================================= 122 // Out-Edge and In-Edge Iterator Implementation 123 124 template <class BaseIter, class VertexDescriptor, class EdgeDescriptor, class Difference> 125 struct out_edge_iter 126 : iterator_adaptor< 127 out_edge_iter<BaseIter, VertexDescriptor, EdgeDescriptor, Difference> 128 , BaseIter 129 , EdgeDescriptor 130 , use_default 131 , EdgeDescriptor 132 , Difference 133 > 134 { 135 typedef iterator_adaptor< 136 out_edge_iter<BaseIter, VertexDescriptor, EdgeDescriptor, Difference> 137 , BaseIter 138 , EdgeDescriptor 139 , use_default 140 , EdgeDescriptor 141 , Difference 142 > super_t; 143 out_edge_iterboost::detail::out_edge_iter144 inline out_edge_iter() { } out_edge_iterboost::detail::out_edge_iter145 inline out_edge_iter(const BaseIter& i, const VertexDescriptor& src) 146 : super_t(i), m_src(src) { } 147 148 inline EdgeDescriptor dereferenceboost::detail::out_edge_iter149 dereference() const 150 { 151 return EdgeDescriptor(m_src, (*this->base()).get_target(), 152 &(*this->base()).get_property()); 153 } 154 VertexDescriptor m_src; 155 }; 156 157 template <class BaseIter, class VertexDescriptor, class EdgeDescriptor, class Difference> 158 struct in_edge_iter 159 : iterator_adaptor< 160 in_edge_iter<BaseIter, VertexDescriptor, EdgeDescriptor, Difference> 161 , BaseIter 162 , EdgeDescriptor 163 , use_default 164 , EdgeDescriptor 165 , Difference 166 > 167 { 168 typedef iterator_adaptor< 169 in_edge_iter<BaseIter, VertexDescriptor, EdgeDescriptor, Difference> 170 , BaseIter 171 , EdgeDescriptor 172 , use_default 173 , EdgeDescriptor 174 , Difference 175 > super_t; 176 in_edge_iterboost::detail::in_edge_iter177 inline in_edge_iter() { } in_edge_iterboost::detail::in_edge_iter178 inline in_edge_iter(const BaseIter& i, const VertexDescriptor& src) 179 : super_t(i), m_src(src) { } 180 181 inline EdgeDescriptor dereferenceboost::detail::in_edge_iter182 dereference() const 183 { 184 return EdgeDescriptor((*this->base()).get_target(), m_src, 185 &this->base()->get_property()); 186 } 187 VertexDescriptor m_src; 188 }; 189 190 //========================================================================= 191 // Undirected Edge Iterator Implementation 192 193 template <class EdgeIter, class EdgeDescriptor, class Difference> 194 struct undirected_edge_iter 195 : iterator_adaptor< 196 undirected_edge_iter<EdgeIter, EdgeDescriptor, Difference> 197 , EdgeIter 198 , EdgeDescriptor 199 , use_default 200 , EdgeDescriptor 201 , Difference 202 > 203 { 204 typedef iterator_adaptor< 205 undirected_edge_iter<EdgeIter, EdgeDescriptor, Difference> 206 , EdgeIter 207 , EdgeDescriptor 208 , use_default 209 , EdgeDescriptor 210 , Difference 211 > super_t; 212 undirected_edge_iterboost::detail::undirected_edge_iter213 undirected_edge_iter() {} 214 undirected_edge_iterboost::detail::undirected_edge_iter215 explicit undirected_edge_iter(EdgeIter i) 216 : super_t(i) {} 217 218 inline EdgeDescriptor dereferenceboost::detail::undirected_edge_iter219 dereference() const { 220 return EdgeDescriptor( 221 (*this->base()).m_source 222 , (*this->base()).m_target 223 , &this->base()->get_property()); 224 } 225 }; 226 227 //========================================================================= 228 // Edge Storage Types (stored in the out-edge/in-edge lists) 229 230 template <class Vertex> 231 class stored_edge 232 : public boost::equality_comparable1< stored_edge<Vertex>, 233 boost::less_than_comparable1< stored_edge<Vertex> > > 234 { 235 public: 236 typedef no_property property_type; stored_edge()237 inline stored_edge() { } stored_edge(Vertex target,const no_property &=no_property ())238 inline stored_edge(Vertex target, const no_property& = no_property()) 239 : m_target(target) { } get_target() const240 inline Vertex& get_target() const { return m_target; } get_property() const241 inline const no_property& get_property() const { return s_prop; } operator ==(const stored_edge & x) const242 inline bool operator==(const stored_edge& x) const 243 { return m_target == x.get_target(); } operator <(const stored_edge & x) const244 inline bool operator<(const stored_edge& x) const 245 { return m_target < x.get_target(); } 246 //protected: need to add hash<> as a friend 247 static no_property s_prop; 248 // Sometimes target not used as key in the set, and in that case 249 // it is ok to change the target. 250 mutable Vertex m_target; 251 }; 252 template <class Vertex> 253 no_property stored_edge<Vertex>::s_prop; 254 255 #if defined(BOOST_NO_CXX11_RVALUE_REFERENCES) || defined(BOOST_NO_CXX11_SMART_PTR) 256 template <class Vertex, class Property> 257 class stored_edge_property : public stored_edge<Vertex> { 258 typedef stored_edge_property self; 259 typedef stored_edge<Vertex> Base; 260 public: 261 typedef Property property_type; stored_edge_property()262 inline stored_edge_property() { } stored_edge_property(Vertex target,const Property & p=Property ())263 inline stored_edge_property(Vertex target, 264 const Property& p = Property()) 265 : stored_edge<Vertex>(target), m_property(new Property(p)) { } stored_edge_property(const self & x)266 stored_edge_property(const self& x) 267 : Base(static_cast< Base const& >(x)), m_property(const_cast<self&>(x).m_property) { } operator =(const self & x)268 self& operator=(const self& x) { 269 // NOTE: avoid 'Base::operator=(x);' broken on SGI MIPSpro (bug 55771 of Mozilla). 270 static_cast<Base&>(*this) = static_cast< Base const& >(x); 271 m_property = const_cast<self&>(x).m_property; 272 return *this; 273 } 274 #if !defined(BOOST_NO_CXX11_RVALUE_REFERENCES) 275 // NOTE Don't rely on default operators, their behavior is broken on several compilers (GCC 4.6). stored_edge_property(self && x)276 stored_edge_property(self&& x) 277 : Base(static_cast< Base&& >(x)), m_property(std::move(x.m_property)) { } operator =(self && x)278 self& operator=(self&& x) { 279 // NOTE: avoid 'Base::operator=(x);' broken on SGI MIPSpro (bug 55771 of Mozilla). 280 static_cast<Base&>(*this) = static_cast< Base&& >(x); 281 m_property = std::move(x.m_property); 282 return *this; 283 } 284 #endif get_property()285 inline Property& get_property() { return *m_property; } get_property() const286 inline const Property& get_property() const { return *m_property; } 287 protected: 288 // Holding the property by-value causes edge-descriptor 289 // invalidation for add_edge() with EdgeList=vecS. Instead we 290 // hold a pointer to the property. std::auto_ptr is not 291 // a perfect fit for the job, but it is darn close. 292 std::auto_ptr<Property> m_property; 293 }; 294 #else 295 template <class Vertex, class Property> 296 class stored_edge_property : public stored_edge<Vertex> { 297 typedef stored_edge_property self; 298 typedef stored_edge<Vertex> Base; 299 public: 300 typedef Property property_type; stored_edge_property()301 inline stored_edge_property() { } stored_edge_property(Vertex target,const Property & p=Property ())302 inline stored_edge_property(Vertex target, 303 const Property& p = Property()) 304 : stored_edge<Vertex>(target), m_property(new Property(p)) { } stored_edge_property(self && x)305 stored_edge_property(self&& x) : Base(static_cast< Base&& >(x)), 306 m_property(std::move(x.m_property)) { } stored_edge_property(self const & x)307 stored_edge_property(self const& x) : Base(static_cast< Base const& >(x)), 308 m_property(std::move(const_cast<self&>(x).m_property)) { } operator =(self && x)309 self& operator=(self&& x) { 310 // NOTE: avoid 'Base::operator=(x);' broken on SGI MIPSpro (bug 55771 of Mozilla). 311 static_cast<Base&>(*this) = static_cast< Base&& >(x); 312 m_property = std::move(x.m_property); 313 return *this; 314 } operator =(self const & x)315 self& operator=(self const& x) { 316 // NOTE: avoid 'Base::operator=(x);' broken on SGI MIPSpro (bug 55771 of Mozilla). 317 static_cast<Base&>(*this) = static_cast< Base const& >(x); 318 m_property = std::move(const_cast<self&>(x).m_property); 319 return *this; 320 } get_property()321 inline Property& get_property() { return *m_property; } get_property() const322 inline const Property& get_property() const { return *m_property; } 323 protected: 324 std::unique_ptr<Property> m_property; 325 }; 326 #endif 327 328 329 template <class Vertex, class Iter, class Property> 330 class stored_edge_iter 331 : public stored_edge<Vertex> 332 { 333 public: 334 typedef Property property_type; stored_edge_iter()335 inline stored_edge_iter() { } stored_edge_iter(Vertex v)336 inline stored_edge_iter(Vertex v) 337 : stored_edge<Vertex>(v) { } stored_edge_iter(Vertex v,Iter i,void * =0)338 inline stored_edge_iter(Vertex v, Iter i, void* = 0) 339 : stored_edge<Vertex>(v), m_iter(i) { } get_property()340 inline Property& get_property() { return m_iter->get_property(); } get_property() const341 inline const Property& get_property() const { 342 return m_iter->get_property(); 343 } get_iter() const344 inline Iter get_iter() const { return m_iter; } 345 protected: 346 Iter m_iter; 347 }; 348 349 // For when the EdgeList is a std::vector. 350 // Want to make the iterator stable, so use an offset 351 // instead of an iterator into a std::vector 352 template <class Vertex, class EdgeVec, class Property> 353 class stored_ra_edge_iter 354 : public stored_edge<Vertex> 355 { 356 typedef typename EdgeVec::iterator Iter; 357 public: 358 typedef Property property_type; stored_ra_edge_iter()359 inline stored_ra_edge_iter() { } stored_ra_edge_iter(Vertex v)360 inline explicit stored_ra_edge_iter(Vertex v) // Only used for comparisons 361 : stored_edge<Vertex>(v), m_i(0), m_vec(0){ } stored_ra_edge_iter(Vertex v,Iter i,EdgeVec * edge_vec)362 inline stored_ra_edge_iter(Vertex v, Iter i, EdgeVec* edge_vec) 363 : stored_edge<Vertex>(v), m_i(i - edge_vec->begin()), m_vec(edge_vec){ } get_property()364 inline Property& get_property() { BOOST_ASSERT ((m_vec != 0)); return (*m_vec)[m_i].get_property(); } get_property() const365 inline const Property& get_property() const { 366 BOOST_ASSERT ((m_vec != 0)); 367 return (*m_vec)[m_i].get_property(); 368 } get_iter() const369 inline Iter get_iter() const { BOOST_ASSERT ((m_vec != 0)); return m_vec->begin() + m_i; } 370 protected: 371 std::size_t m_i; 372 EdgeVec* m_vec; 373 }; 374 375 } // namespace detail 376 377 template <class Tag, class Vertex, class Property> 378 const typename property_value<Property,Tag>::type& get(Tag property_tag,const detail::stored_edge_property<Vertex,Property> & e)379 get(Tag property_tag, 380 const detail::stored_edge_property<Vertex, Property>& e) 381 { 382 return get_property_value(e.get_property(), property_tag); 383 } 384 385 template <class Tag, class Vertex, class Iter, class Property> 386 const typename property_value<Property,Tag>::type& get(Tag property_tag,const detail::stored_edge_iter<Vertex,Iter,Property> & e)387 get(Tag property_tag, 388 const detail::stored_edge_iter<Vertex, Iter, Property>& e) 389 { 390 return get_property_value(e.get_property(), property_tag); 391 } 392 393 template <class Tag, class Vertex, class EdgeVec, class Property> 394 const typename property_value<Property,Tag>::type& get(Tag property_tag,const detail::stored_ra_edge_iter<Vertex,EdgeVec,Property> & e)395 get(Tag property_tag, 396 const detail::stored_ra_edge_iter<Vertex, EdgeVec, Property>& e) 397 { 398 return get_property_value(e.get_property(), property_tag); 399 } 400 401 //========================================================================= 402 // Directed Edges Helper Class 403 404 namespace detail { 405 406 // O(E/V) 407 template <class edge_descriptor, class EdgeList, class StoredProperty> 408 inline void remove_directed_edge_dispatch(edge_descriptor,EdgeList & el,StoredProperty & p)409 remove_directed_edge_dispatch(edge_descriptor, EdgeList& el, 410 StoredProperty& p) 411 { 412 for (typename EdgeList::iterator i = el.begin(); 413 i != el.end(); ++i) 414 if (&(*i).get_property() == &p) { 415 el.erase(i); 416 return; 417 } 418 } 419 420 template <class incidence_iterator, class EdgeList, class Predicate> 421 inline void remove_directed_edge_if_dispatch(incidence_iterator first,incidence_iterator last,EdgeList & el,Predicate pred,boost::allow_parallel_edge_tag)422 remove_directed_edge_if_dispatch(incidence_iterator first, 423 incidence_iterator last, 424 EdgeList& el, Predicate pred, 425 boost::allow_parallel_edge_tag) 426 { 427 // remove_if 428 while (first != last && !pred(*first)) 429 ++first; 430 incidence_iterator i = first; 431 if (first != last) 432 for (++i; i != last; ++i) 433 if (!pred(*i)) { 434 *first.base() = BOOST_GRAPH_MOVE_IF_POSSIBLE(*i.base()); 435 ++first; 436 } 437 el.erase(first.base(), el.end()); 438 } 439 template <class incidence_iterator, class EdgeList, class Predicate> 440 inline void remove_directed_edge_if_dispatch(incidence_iterator first,incidence_iterator last,EdgeList & el,Predicate pred,boost::disallow_parallel_edge_tag)441 remove_directed_edge_if_dispatch(incidence_iterator first, 442 incidence_iterator last, 443 EdgeList& el, 444 Predicate pred, 445 boost::disallow_parallel_edge_tag) 446 { 447 for (incidence_iterator next = first; 448 first != last; first = next) { 449 ++next; 450 if (pred(*first)) 451 el.erase( first.base() ); 452 } 453 } 454 455 template <class PropT, class Graph, class incidence_iterator, 456 class EdgeList, class Predicate> 457 inline void undirected_remove_out_edge_if_dispatch(Graph & g,incidence_iterator first,incidence_iterator last,EdgeList & el,Predicate pred,boost::allow_parallel_edge_tag)458 undirected_remove_out_edge_if_dispatch(Graph& g, 459 incidence_iterator first, 460 incidence_iterator last, 461 EdgeList& el, Predicate pred, 462 boost::allow_parallel_edge_tag) 463 { 464 typedef typename Graph::global_edgelist_selector EdgeListS; 465 BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value)); 466 467 // remove_if 468 while (first != last && !pred(*first)) 469 ++first; 470 incidence_iterator i = first; 471 bool self_loop_removed = false; 472 if (first != last) 473 for (; i != last; ++i) { 474 if (self_loop_removed) { 475 /* With self loops, the descriptor will show up 476 * twice. The first time it will be removed, and now it 477 * will be skipped. 478 */ 479 self_loop_removed = false; 480 } 481 else if (!pred(*i)) { 482 *first.base() = BOOST_GRAPH_MOVE_IF_POSSIBLE(*i.base()); 483 ++first; 484 } else { 485 if (source(*i, g) == target(*i, g)) self_loop_removed = true; 486 else { 487 // Remove the edge from the target 488 detail::remove_directed_edge_dispatch 489 (*i, 490 g.out_edge_list(target(*i, g)), 491 *(PropT*)(*i).get_property()); 492 } 493 494 // Erase the edge property 495 g.m_edges.erase( (*i.base()).get_iter() ); 496 } 497 } 498 el.erase(first.base(), el.end()); 499 } 500 template <class PropT, class Graph, class incidence_iterator, 501 class EdgeList, class Predicate> 502 inline void undirected_remove_out_edge_if_dispatch(Graph & g,incidence_iterator first,incidence_iterator last,EdgeList & el,Predicate pred,boost::disallow_parallel_edge_tag)503 undirected_remove_out_edge_if_dispatch(Graph& g, 504 incidence_iterator first, 505 incidence_iterator last, 506 EdgeList& el, 507 Predicate pred, 508 boost::disallow_parallel_edge_tag) 509 { 510 typedef typename Graph::global_edgelist_selector EdgeListS; 511 BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value)); 512 513 for (incidence_iterator next = first; 514 first != last; first = next) { 515 ++next; 516 if (pred(*first)) { 517 if (source(*first, g) != target(*first, g)) { 518 // Remove the edge from the target 519 detail::remove_directed_edge_dispatch 520 (*first, 521 g.out_edge_list(target(*first, g)), 522 *(PropT*)(*first).get_property()); 523 } 524 525 // Erase the edge property 526 g.m_edges.erase( (*first.base()).get_iter() ); 527 528 // Erase the edge in the source 529 el.erase( first.base() ); 530 } 531 } 532 } 533 534 // O(E/V) 535 template <class edge_descriptor, class EdgeList, class StoredProperty> 536 inline void remove_directed_edge_dispatch(edge_descriptor e,EdgeList & el,no_property &)537 remove_directed_edge_dispatch(edge_descriptor e, EdgeList& el, 538 no_property&) 539 { 540 for (typename EdgeList::iterator i = el.begin(); 541 i != el.end(); ++i) 542 if ((*i).get_target() == e.m_target) { 543 el.erase(i); 544 return; 545 } 546 } 547 548 } // namespace detail 549 550 template <class Config> 551 struct directed_edges_helper { 552 553 // Placement of these overloaded remove_edge() functions 554 // inside the class avoids a VC++ bug. 555 556 // O(E/V) 557 inline void remove_edgeboost::directed_edges_helper558 remove_edge(typename Config::edge_descriptor e) 559 { 560 typedef typename Config::graph_type graph_type; 561 graph_type& g = static_cast<graph_type&>(*this); 562 typename Config::OutEdgeList& el = g.out_edge_list(source(e, g)); 563 typedef typename Config::OutEdgeList::value_type::property_type PType; 564 detail::remove_directed_edge_dispatch(e, el, 565 *(PType*)e.get_property()); 566 } 567 568 // O(1) 569 inline void remove_edgeboost::directed_edges_helper570 remove_edge(typename Config::out_edge_iterator iter) 571 { 572 typedef typename Config::graph_type graph_type; 573 graph_type& g = static_cast<graph_type&>(*this); 574 typename Config::edge_descriptor e = *iter; 575 typename Config::OutEdgeList& el = g.out_edge_list(source(e, g)); 576 el.erase(iter.base()); 577 } 578 579 }; 580 581 // O(1) 582 template <class Config> 583 inline std::pair<typename Config::edge_iterator, 584 typename Config::edge_iterator> edges(const directed_edges_helper<Config> & g_)585 edges(const directed_edges_helper<Config>& g_) 586 { 587 typedef typename Config::graph_type graph_type; 588 typedef typename Config::edge_iterator edge_iterator; 589 const graph_type& cg = static_cast<const graph_type&>(g_); 590 graph_type& g = const_cast<graph_type&>(cg); 591 return std::make_pair( edge_iterator(g.vertex_set().begin(), 592 g.vertex_set().begin(), 593 g.vertex_set().end(), g), 594 edge_iterator(g.vertex_set().begin(), 595 g.vertex_set().end(), 596 g.vertex_set().end(), g) ); 597 } 598 599 //========================================================================= 600 // Directed Graph Helper Class 601 602 struct adj_list_dir_traversal_tag : 603 public virtual vertex_list_graph_tag, 604 public virtual incidence_graph_tag, 605 public virtual adjacency_graph_tag, 606 public virtual edge_list_graph_tag { }; 607 608 template <class Config> 609 struct directed_graph_helper 610 : public directed_edges_helper<Config> { 611 typedef typename Config::edge_descriptor edge_descriptor; 612 typedef adj_list_dir_traversal_tag traversal_category; 613 }; 614 615 // O(E/V) 616 template <class Config> 617 inline void remove_edge(typename Config::vertex_descriptor u,typename Config::vertex_descriptor v,directed_graph_helper<Config> & g_)618 remove_edge(typename Config::vertex_descriptor u, 619 typename Config::vertex_descriptor v, 620 directed_graph_helper<Config>& g_) 621 { 622 typedef typename Config::graph_type graph_type; 623 typedef typename Config::edge_parallel_category Cat; 624 graph_type& g = static_cast<graph_type&>(g_); 625 detail::erase_from_incidence_list(g.out_edge_list(u), v, Cat()); 626 } 627 628 template <class Config, class Predicate> 629 inline void remove_out_edge_if(typename Config::vertex_descriptor u,Predicate pred,directed_graph_helper<Config> & g_)630 remove_out_edge_if(typename Config::vertex_descriptor u, Predicate pred, 631 directed_graph_helper<Config>& g_) 632 { 633 typedef typename Config::graph_type graph_type; 634 graph_type& g = static_cast<graph_type&>(g_); 635 typename Config::out_edge_iterator first, last; 636 boost::tie(first, last) = out_edges(u, g); 637 typedef typename Config::edge_parallel_category edge_parallel_category; 638 detail::remove_directed_edge_if_dispatch 639 (first, last, g.out_edge_list(u), pred, edge_parallel_category()); 640 } 641 642 template <class Config, class Predicate> 643 inline void remove_edge_if(Predicate pred,directed_graph_helper<Config> & g_)644 remove_edge_if(Predicate pred, directed_graph_helper<Config>& g_) 645 { 646 typedef typename Config::graph_type graph_type; 647 graph_type& g = static_cast<graph_type&>(g_); 648 649 typename Config::vertex_iterator vi, vi_end; 650 for (boost::tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi) 651 remove_out_edge_if(*vi, pred, g); 652 } 653 654 template <class EdgeOrIter, class Config> 655 inline void remove_edge(EdgeOrIter e_or_iter,directed_graph_helper<Config> & g_)656 remove_edge(EdgeOrIter e_or_iter, directed_graph_helper<Config>& g_) 657 { 658 g_.remove_edge(e_or_iter); 659 } 660 661 // O(V + E) for allow_parallel_edges 662 // O(V * log(E/V)) for disallow_parallel_edges 663 template <class Config> 664 inline void clear_vertex(typename Config::vertex_descriptor u,directed_graph_helper<Config> & g_)665 clear_vertex(typename Config::vertex_descriptor u, 666 directed_graph_helper<Config>& g_) 667 { 668 typedef typename Config::graph_type graph_type; 669 typedef typename Config::edge_parallel_category Cat; 670 graph_type& g = static_cast<graph_type&>(g_); 671 typename Config::vertex_iterator vi, viend; 672 for (boost::tie(vi, viend) = vertices(g); vi != viend; ++vi) 673 detail::erase_from_incidence_list(g.out_edge_list(*vi), u, Cat()); 674 g.out_edge_list(u).clear(); 675 // clear() should be a req of Sequence and AssociativeContainer, 676 // or maybe just Container 677 } 678 679 template <class Config> 680 inline void clear_out_edges(typename Config::vertex_descriptor u,directed_graph_helper<Config> & g_)681 clear_out_edges(typename Config::vertex_descriptor u, 682 directed_graph_helper<Config>& g_) 683 { 684 typedef typename Config::graph_type graph_type; 685 graph_type& g = static_cast<graph_type&>(g_); 686 g.out_edge_list(u).clear(); 687 // clear() should be a req of Sequence and AssociativeContainer, 688 // or maybe just Container 689 } 690 691 // O(V), could do better... 692 template <class Config> 693 inline typename Config::edges_size_type num_edges(const directed_graph_helper<Config> & g_)694 num_edges(const directed_graph_helper<Config>& g_) 695 { 696 typedef typename Config::graph_type graph_type; 697 const graph_type& g = static_cast<const graph_type&>(g_); 698 typename Config::edges_size_type num_e = 0; 699 typename Config::vertex_iterator vi, vi_end; 700 for (boost::tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi) 701 num_e += out_degree(*vi, g); 702 return num_e; 703 } 704 // O(1) for allow_parallel_edge_tag 705 // O(log(E/V)) for disallow_parallel_edge_tag 706 template <class Config> 707 inline std::pair<typename directed_graph_helper<Config>::edge_descriptor, bool> add_edge(typename Config::vertex_descriptor u,typename Config::vertex_descriptor v,const typename Config::edge_property_type & p,directed_graph_helper<Config> & g_)708 add_edge(typename Config::vertex_descriptor u, 709 typename Config::vertex_descriptor v, 710 const typename Config::edge_property_type& p, 711 directed_graph_helper<Config>& g_) 712 { 713 typedef typename Config::edge_descriptor edge_descriptor; 714 typedef typename Config::graph_type graph_type; 715 typedef typename Config::StoredEdge StoredEdge; 716 graph_type& g = static_cast<graph_type&>(g_); 717 typename Config::OutEdgeList::iterator i; 718 bool inserted; 719 boost::tie(i, inserted) = boost::graph_detail::push(g.out_edge_list(u), 720 StoredEdge(v, p)); 721 return std::make_pair(edge_descriptor(u, v, &(*i).get_property()), 722 inserted); 723 } 724 // Did not use default argument here because that 725 // causes Visual C++ to get confused. 726 template <class Config> 727 inline std::pair<typename Config::edge_descriptor, bool> add_edge(typename Config::vertex_descriptor u,typename Config::vertex_descriptor v,directed_graph_helper<Config> & g_)728 add_edge(typename Config::vertex_descriptor u, 729 typename Config::vertex_descriptor v, 730 directed_graph_helper<Config>& g_) 731 { 732 typename Config::edge_property_type p; 733 return add_edge(u, v, p, g_); 734 } 735 //========================================================================= 736 // Undirected Graph Helper Class 737 738 template <class Config> 739 struct undirected_graph_helper; 740 741 struct undir_adj_list_traversal_tag : 742 public virtual vertex_list_graph_tag, 743 public virtual incidence_graph_tag, 744 public virtual adjacency_graph_tag, 745 public virtual edge_list_graph_tag, 746 public virtual bidirectional_graph_tag { }; 747 748 namespace detail { 749 750 // using class with specialization for dispatch is a VC++ workaround. 751 template <class StoredProperty> 752 struct remove_undirected_edge_dispatch { 753 754 // O(E/V) 755 template <class edge_descriptor, class Config> 756 static void applyboost::detail::remove_undirected_edge_dispatch757 apply(edge_descriptor e, 758 undirected_graph_helper<Config>& g_, 759 StoredProperty& p) 760 { 761 typedef typename Config::global_edgelist_selector EdgeListS; 762 BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value)); 763 764 typedef typename Config::graph_type graph_type; 765 graph_type& g = static_cast<graph_type&>(g_); 766 767 typename Config::OutEdgeList& out_el = g.out_edge_list(source(e, g)); 768 typename Config::OutEdgeList::iterator out_i = out_el.begin(); 769 typename Config::EdgeIter edge_iter_to_erase; 770 for (; out_i != out_el.end(); ++out_i) 771 if (&(*out_i).get_property() == &p) { 772 edge_iter_to_erase = (*out_i).get_iter(); 773 out_el.erase(out_i); 774 break; 775 } 776 typename Config::OutEdgeList& in_el = g.out_edge_list(target(e, g)); 777 typename Config::OutEdgeList::iterator in_i = in_el.begin(); 778 for (; in_i != in_el.end(); ++in_i) 779 if (&(*in_i).get_property() == &p) { 780 in_el.erase(in_i); 781 break; 782 } 783 g.m_edges.erase(edge_iter_to_erase); 784 } 785 }; 786 787 template <> 788 struct remove_undirected_edge_dispatch<no_property> { 789 // O(E/V) 790 template <class edge_descriptor, class Config> 791 static void applyboost::detail::remove_undirected_edge_dispatch792 apply(edge_descriptor e, 793 undirected_graph_helper<Config>& g_, 794 no_property&) 795 { 796 typedef typename Config::global_edgelist_selector EdgeListS; 797 BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value)); 798 799 typedef typename Config::graph_type graph_type; 800 graph_type& g = static_cast<graph_type&>(g_); 801 no_property* p = (no_property*)e.get_property(); 802 typename Config::OutEdgeList& out_el = g.out_edge_list(source(e, g)); 803 typename Config::OutEdgeList::iterator out_i = out_el.begin(); 804 typename Config::EdgeIter edge_iter_to_erase; 805 for (; out_i != out_el.end(); ++out_i) 806 if (&(*out_i).get_property() == p) { 807 edge_iter_to_erase = (*out_i).get_iter(); 808 out_el.erase(out_i); 809 break; 810 } 811 typename Config::OutEdgeList& in_el = g.out_edge_list(target(e, g)); 812 typename Config::OutEdgeList::iterator in_i = in_el.begin(); 813 for (; in_i != in_el.end(); ++in_i) 814 if (&(*in_i).get_property() == p) { 815 in_el.erase(in_i); 816 break; 817 } 818 g.m_edges.erase(edge_iter_to_erase); 819 } 820 }; 821 822 // O(E/V) 823 template <class Graph, class EdgeList, class Vertex> 824 inline void remove_edge_and_property(Graph & g,EdgeList & el,Vertex v,boost::allow_parallel_edge_tag cat)825 remove_edge_and_property(Graph& g, EdgeList& el, Vertex v, 826 boost::allow_parallel_edge_tag cat) 827 { 828 typedef typename Graph::global_edgelist_selector EdgeListS; 829 BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value)); 830 831 typename EdgeList::iterator i = el.begin(), end = el.end(); 832 for (; i != end; ++i) { 833 if ((*i).get_target() == v) { 834 // NOTE: Wihtout this skip, this loop will double-delete properties 835 // of loop edges. This solution is based on the observation that 836 // the incidence edges of a vertex with a loop are adjacent in the 837 // out edge list. This *may* actually hold for multisets also. 838 bool skip = (boost::next(i) != end && i->get_iter() == boost::next(i)->get_iter()); 839 g.m_edges.erase((*i).get_iter()); 840 if (skip) ++i; 841 } 842 } 843 detail::erase_from_incidence_list(el, v, cat); 844 } 845 // O(log(E/V)) 846 template <class Graph, class EdgeList, class Vertex> 847 inline void remove_edge_and_property(Graph & g,EdgeList & el,Vertex v,boost::disallow_parallel_edge_tag)848 remove_edge_and_property(Graph& g, EdgeList& el, Vertex v, 849 boost::disallow_parallel_edge_tag) 850 { 851 typedef typename Graph::global_edgelist_selector EdgeListS; 852 BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value)); 853 854 typedef typename EdgeList::value_type StoredEdge; 855 typename EdgeList::iterator i = el.find(StoredEdge(v)), end = el.end(); 856 if (i != end) { 857 g.m_edges.erase((*i).get_iter()); 858 el.erase(i); 859 } 860 } 861 862 } // namespace detail 863 864 template <class Vertex, class EdgeProperty> 865 struct list_edge // short name due to VC++ truncation and linker problems 866 : public boost::detail::edge_base<boost::undirected_tag, Vertex> 867 { 868 typedef EdgeProperty property_type; 869 typedef boost::detail::edge_base<boost::undirected_tag, Vertex> Base; list_edgeboost::list_edge870 list_edge(Vertex u, Vertex v, const EdgeProperty& p = EdgeProperty()) 871 : Base(u, v), m_property(p) { } get_propertyboost::list_edge872 EdgeProperty& get_property() { return m_property; } get_propertyboost::list_edge873 const EdgeProperty& get_property() const { return m_property; } 874 // the following methods should never be used, but are needed 875 // to make SGI MIPSpro C++ happy list_edgeboost::list_edge876 list_edge() { } operator ==boost::list_edge877 bool operator==(const list_edge&) const { return false; } operator <boost::list_edge878 bool operator<(const list_edge&) const { return false; } 879 EdgeProperty m_property; 880 }; 881 882 template <class Config> 883 struct undirected_graph_helper { 884 885 typedef undir_adj_list_traversal_tag traversal_category; 886 887 // Placement of these overloaded remove_edge() functions 888 // inside the class avoids a VC++ bug. 889 890 // O(E/V) 891 inline void remove_edgeboost::undirected_graph_helper892 remove_edge(typename Config::edge_descriptor e) 893 { 894 typedef typename Config::global_edgelist_selector EdgeListS; 895 BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value)); 896 897 typedef typename Config::OutEdgeList::value_type::property_type PType; 898 detail::remove_undirected_edge_dispatch<PType>::apply 899 (e, *this, *(PType*)e.get_property()); 900 } 901 // O(E/V) 902 inline void remove_edgeboost::undirected_graph_helper903 remove_edge(typename Config::out_edge_iterator iter) 904 { 905 this->remove_edge(*iter); 906 } 907 }; 908 909 // Had to make these non-members to avoid accidental instantiation 910 // on SGI MIPSpro C++ 911 template <class C> 912 inline typename C::InEdgeList& in_edge_list(undirected_graph_helper<C> &,typename C::vertex_descriptor v)913 in_edge_list(undirected_graph_helper<C>&, 914 typename C::vertex_descriptor v) 915 { 916 typename C::stored_vertex* sv = (typename C::stored_vertex*)v; 917 return sv->m_out_edges; 918 } 919 template <class C> 920 inline const typename C::InEdgeList& in_edge_list(const undirected_graph_helper<C> &,typename C::vertex_descriptor v)921 in_edge_list(const undirected_graph_helper<C>&, 922 typename C::vertex_descriptor v) { 923 typename C::stored_vertex* sv = (typename C::stored_vertex*)v; 924 return sv->m_out_edges; 925 } 926 927 // O(E/V) 928 template <class EdgeOrIter, class Config> 929 inline void remove_edge(EdgeOrIter e,undirected_graph_helper<Config> & g_)930 remove_edge(EdgeOrIter e, undirected_graph_helper<Config>& g_) 931 { 932 typedef typename Config::global_edgelist_selector EdgeListS; 933 BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value)); 934 935 g_.remove_edge(e); 936 } 937 938 // O(E/V) or O(log(E/V)) 939 template <class Config> 940 void remove_edge(typename Config::vertex_descriptor u,typename Config::vertex_descriptor v,undirected_graph_helper<Config> & g_)941 remove_edge(typename Config::vertex_descriptor u, 942 typename Config::vertex_descriptor v, 943 undirected_graph_helper<Config>& g_) 944 { 945 typedef typename Config::global_edgelist_selector EdgeListS; 946 BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value)); 947 948 typedef typename Config::graph_type graph_type; 949 graph_type& g = static_cast<graph_type&>(g_); 950 typedef typename Config::edge_parallel_category Cat; 951 detail::remove_edge_and_property(g, g.out_edge_list(u), v, Cat()); 952 detail::erase_from_incidence_list(g.out_edge_list(v), u, Cat()); 953 } 954 955 template <class Config, class Predicate> 956 void remove_out_edge_if(typename Config::vertex_descriptor u,Predicate pred,undirected_graph_helper<Config> & g_)957 remove_out_edge_if(typename Config::vertex_descriptor u, Predicate pred, 958 undirected_graph_helper<Config>& g_) 959 { 960 typedef typename Config::global_edgelist_selector EdgeListS; 961 BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value)); 962 963 typedef typename Config::graph_type graph_type; 964 typedef typename Config::OutEdgeList::value_type::property_type PropT; 965 graph_type& g = static_cast<graph_type&>(g_); 966 typename Config::out_edge_iterator first, last; 967 boost::tie(first, last) = out_edges(u, g); 968 typedef typename Config::edge_parallel_category Cat; 969 detail::undirected_remove_out_edge_if_dispatch<PropT> 970 (g, first, last, g.out_edge_list(u), pred, Cat()); 971 } 972 template <class Config, class Predicate> 973 void remove_in_edge_if(typename Config::vertex_descriptor u,Predicate pred,undirected_graph_helper<Config> & g_)974 remove_in_edge_if(typename Config::vertex_descriptor u, Predicate pred, 975 undirected_graph_helper<Config>& g_) 976 { 977 typedef typename Config::global_edgelist_selector EdgeListS; 978 BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value)); 979 980 remove_out_edge_if(u, pred, g_); 981 } 982 983 // O(E/V * E) or O(log(E/V) * E) 984 template <class Predicate, class Config> 985 void remove_edge_if(Predicate pred,undirected_graph_helper<Config> & g_)986 remove_edge_if(Predicate pred, undirected_graph_helper<Config>& g_) 987 { 988 typedef typename Config::global_edgelist_selector EdgeListS; 989 BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value)); 990 991 typedef typename Config::graph_type graph_type; 992 graph_type& g = static_cast<graph_type&>(g_); 993 typename Config::edge_iterator ei, ei_end, next; 994 boost::tie(ei, ei_end) = edges(g); 995 for (next = ei; ei != ei_end; ei = next) { 996 ++next; 997 if (pred(*ei)) 998 remove_edge(*ei, g); 999 } 1000 } 1001 1002 // O(1) 1003 template <class Config> 1004 inline std::pair<typename Config::edge_iterator, 1005 typename Config::edge_iterator> edges(const undirected_graph_helper<Config> & g_)1006 edges(const undirected_graph_helper<Config>& g_) 1007 { 1008 typedef typename Config::graph_type graph_type; 1009 typedef typename Config::edge_iterator edge_iterator; 1010 const graph_type& cg = static_cast<const graph_type&>(g_); 1011 graph_type& g = const_cast<graph_type&>(cg); 1012 return std::make_pair( edge_iterator(g.m_edges.begin()), 1013 edge_iterator(g.m_edges.end()) ); 1014 } 1015 // O(1) 1016 template <class Config> 1017 inline typename Config::edges_size_type num_edges(const undirected_graph_helper<Config> & g_)1018 num_edges(const undirected_graph_helper<Config>& g_) 1019 { 1020 typedef typename Config::graph_type graph_type; 1021 const graph_type& g = static_cast<const graph_type&>(g_); 1022 return g.m_edges.size(); 1023 } 1024 // O(E/V * E/V) 1025 template <class Config> 1026 inline void clear_vertex(typename Config::vertex_descriptor u,undirected_graph_helper<Config> & g_)1027 clear_vertex(typename Config::vertex_descriptor u, 1028 undirected_graph_helper<Config>& g_) 1029 { 1030 typedef typename Config::global_edgelist_selector EdgeListS; 1031 BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value)); 1032 1033 typedef typename Config::graph_type graph_type; 1034 graph_type& g = static_cast<graph_type&>(g_); 1035 while (true) { 1036 typename Config::out_edge_iterator ei, ei_end; 1037 boost::tie(ei, ei_end) = out_edges(u, g); 1038 if (ei == ei_end) break; 1039 remove_edge(*ei, g); 1040 } 1041 } 1042 // O(1) for allow_parallel_edge_tag 1043 // O(log(E/V)) for disallow_parallel_edge_tag 1044 template <class Config> 1045 inline std::pair<typename Config::edge_descriptor, bool> add_edge(typename Config::vertex_descriptor u,typename Config::vertex_descriptor v,const typename Config::edge_property_type & p,undirected_graph_helper<Config> & g_)1046 add_edge(typename Config::vertex_descriptor u, 1047 typename Config::vertex_descriptor v, 1048 const typename Config::edge_property_type& p, 1049 undirected_graph_helper<Config>& g_) 1050 { 1051 typedef typename Config::StoredEdge StoredEdge; 1052 typedef typename Config::edge_descriptor edge_descriptor; 1053 typedef typename Config::graph_type graph_type; 1054 graph_type& g = static_cast<graph_type&>(g_); 1055 1056 bool inserted; 1057 typename Config::EdgeContainer::value_type e(u, v, p); 1058 typename Config::EdgeContainer::iterator p_iter 1059 = graph_detail::push(g.m_edges, e).first; 1060 1061 typename Config::OutEdgeList::iterator i; 1062 boost::tie(i, inserted) = boost::graph_detail::push(g.out_edge_list(u), 1063 StoredEdge(v, p_iter, &g.m_edges)); 1064 if (inserted) { 1065 boost::graph_detail::push(g.out_edge_list(v), StoredEdge(u, p_iter, &g.m_edges)); 1066 return std::make_pair(edge_descriptor(u, v, &p_iter->get_property()), 1067 true); 1068 } else { 1069 g.m_edges.erase(p_iter); 1070 return std::make_pair 1071 (edge_descriptor(u, v, &i->get_iter()->get_property()), false); 1072 } 1073 } 1074 template <class Config> 1075 inline std::pair<typename Config::edge_descriptor, bool> add_edge(typename Config::vertex_descriptor u,typename Config::vertex_descriptor v,undirected_graph_helper<Config> & g_)1076 add_edge(typename Config::vertex_descriptor u, 1077 typename Config::vertex_descriptor v, 1078 undirected_graph_helper<Config>& g_) 1079 { 1080 typename Config::edge_property_type p; 1081 return add_edge(u, v, p, g_); 1082 } 1083 1084 // O(1) 1085 template <class Config> 1086 inline typename Config::degree_size_type degree(typename Config::vertex_descriptor u,const undirected_graph_helper<Config> & g_)1087 degree(typename Config::vertex_descriptor u, 1088 const undirected_graph_helper<Config>& g_) 1089 { 1090 typedef typename Config::graph_type Graph; 1091 const Graph& g = static_cast<const Graph&>(g_); 1092 return out_degree(u, g); 1093 } 1094 1095 template <class Config> 1096 inline std::pair<typename Config::in_edge_iterator, 1097 typename Config::in_edge_iterator> in_edges(typename Config::vertex_descriptor u,const undirected_graph_helper<Config> & g_)1098 in_edges(typename Config::vertex_descriptor u, 1099 const undirected_graph_helper<Config>& g_) 1100 { 1101 typedef typename Config::graph_type Graph; 1102 const Graph& cg = static_cast<const Graph&>(g_); 1103 Graph& g = const_cast<Graph&>(cg); 1104 typedef typename Config::in_edge_iterator in_edge_iterator; 1105 return 1106 std::make_pair(in_edge_iterator(g.out_edge_list(u).begin(), u), 1107 in_edge_iterator(g.out_edge_list(u).end(), u)); 1108 } 1109 1110 template <class Config> 1111 inline typename Config::degree_size_type in_degree(typename Config::vertex_descriptor u,const undirected_graph_helper<Config> & g_)1112 in_degree(typename Config::vertex_descriptor u, 1113 const undirected_graph_helper<Config>& g_) 1114 { return degree(u, g_); } 1115 1116 //========================================================================= 1117 // Bidirectional Graph Helper Class 1118 1119 struct bidir_adj_list_traversal_tag : 1120 public virtual vertex_list_graph_tag, 1121 public virtual incidence_graph_tag, 1122 public virtual adjacency_graph_tag, 1123 public virtual edge_list_graph_tag, 1124 public virtual bidirectional_graph_tag { }; 1125 1126 template <class Config> 1127 struct bidirectional_graph_helper 1128 : public directed_edges_helper<Config> { 1129 typedef bidir_adj_list_traversal_tag traversal_category; 1130 }; 1131 1132 // Had to make these non-members to avoid accidental instantiation 1133 // on SGI MIPSpro C++ 1134 template <class C> 1135 inline typename C::InEdgeList& in_edge_list(bidirectional_graph_helper<C> &,typename C::vertex_descriptor v)1136 in_edge_list(bidirectional_graph_helper<C>&, 1137 typename C::vertex_descriptor v) 1138 { 1139 typename C::stored_vertex* sv = (typename C::stored_vertex*)v; 1140 return sv->m_in_edges; 1141 } 1142 template <class C> 1143 inline const typename C::InEdgeList& in_edge_list(const bidirectional_graph_helper<C> &,typename C::vertex_descriptor v)1144 in_edge_list(const bidirectional_graph_helper<C>&, 1145 typename C::vertex_descriptor v) { 1146 typename C::stored_vertex* sv = (typename C::stored_vertex*)v; 1147 return sv->m_in_edges; 1148 } 1149 1150 template <class Predicate, class Config> 1151 inline void remove_edge_if(Predicate pred,bidirectional_graph_helper<Config> & g_)1152 remove_edge_if(Predicate pred, bidirectional_graph_helper<Config>& g_) 1153 { 1154 typedef typename Config::global_edgelist_selector EdgeListS; 1155 BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value)); 1156 1157 typedef typename Config::graph_type graph_type; 1158 graph_type& g = static_cast<graph_type&>(g_); 1159 typename Config::edge_iterator ei, ei_end, next; 1160 boost::tie(ei, ei_end) = edges(g); 1161 for (next = ei; ei != ei_end; ei = next) { 1162 ++next; 1163 if (pred(*ei)) 1164 remove_edge(*ei, g); 1165 } 1166 } 1167 1168 template <class Config> 1169 inline std::pair<typename Config::in_edge_iterator, 1170 typename Config::in_edge_iterator> in_edges(typename Config::vertex_descriptor u,const bidirectional_graph_helper<Config> & g_)1171 in_edges(typename Config::vertex_descriptor u, 1172 const bidirectional_graph_helper<Config>& g_) 1173 { 1174 typedef typename Config::graph_type graph_type; 1175 const graph_type& cg = static_cast<const graph_type&>(g_); 1176 graph_type& g = const_cast<graph_type&>(cg); 1177 typedef typename Config::in_edge_iterator in_edge_iterator; 1178 return 1179 std::make_pair(in_edge_iterator(in_edge_list(g, u).begin(), u), 1180 in_edge_iterator(in_edge_list(g, u).end(), u)); 1181 } 1182 1183 // O(1) 1184 template <class Config> 1185 inline std::pair<typename Config::edge_iterator, 1186 typename Config::edge_iterator> edges(const bidirectional_graph_helper<Config> & g_)1187 edges(const bidirectional_graph_helper<Config>& g_) 1188 { 1189 typedef typename Config::graph_type graph_type; 1190 typedef typename Config::edge_iterator edge_iterator; 1191 const graph_type& cg = static_cast<const graph_type&>(g_); 1192 graph_type& g = const_cast<graph_type&>(cg); 1193 return std::make_pair( edge_iterator(g.m_edges.begin()), 1194 edge_iterator(g.m_edges.end()) ); 1195 } 1196 1197 //========================================================================= 1198 // Bidirectional Graph Helper Class (with edge properties) 1199 1200 1201 template <class Config> 1202 struct bidirectional_graph_helper_with_property 1203 : public bidirectional_graph_helper<Config> 1204 { 1205 typedef typename Config::graph_type graph_type; 1206 typedef typename Config::out_edge_iterator out_edge_iterator; 1207 1208 std::pair<out_edge_iterator, out_edge_iterator> get_parallel_edge_sublistboost::bidirectional_graph_helper_with_property1209 get_parallel_edge_sublist(typename Config::edge_descriptor e, 1210 const graph_type& g, 1211 void*) 1212 { return out_edges(source(e, g), g); } 1213 1214 std::pair<out_edge_iterator, out_edge_iterator> get_parallel_edge_sublistboost::bidirectional_graph_helper_with_property1215 get_parallel_edge_sublist(typename Config::edge_descriptor e, 1216 const graph_type& g, 1217 setS*) 1218 { return edge_range(source(e, g), target(e, g), g); } 1219 1220 std::pair<out_edge_iterator, out_edge_iterator> get_parallel_edge_sublistboost::bidirectional_graph_helper_with_property1221 get_parallel_edge_sublist(typename Config::edge_descriptor e, 1222 const graph_type& g, 1223 multisetS*) 1224 { return edge_range(source(e, g), target(e, g), g); } 1225 1226 std::pair<out_edge_iterator, out_edge_iterator> get_parallel_edge_sublistboost::bidirectional_graph_helper_with_property1227 get_parallel_edge_sublist(typename Config::edge_descriptor e, 1228 const graph_type& g, 1229 hash_setS*) 1230 { return edge_range(source(e, g), target(e, g), g); } 1231 1232 // Placement of these overloaded remove_edge() functions 1233 // inside the class avoids a VC++ bug. 1234 1235 // O(E/V) or O(log(E/V)) 1236 void remove_edgeboost::bidirectional_graph_helper_with_property1237 remove_edge(typename Config::edge_descriptor e) 1238 { 1239 typedef typename Config::global_edgelist_selector EdgeListS; 1240 BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value)); 1241 1242 graph_type& g = static_cast<graph_type&>(*this); 1243 1244 typedef typename Config::edgelist_selector OutEdgeListS; 1245 1246 std::pair<out_edge_iterator, out_edge_iterator> rng = 1247 get_parallel_edge_sublist(e, g, (OutEdgeListS*)(0)); 1248 rng.first = std::find(rng.first, rng.second, e); 1249 BOOST_ASSERT(rng.first != rng.second); 1250 remove_edge(rng.first); 1251 } 1252 1253 inline void remove_edgeboost::bidirectional_graph_helper_with_property1254 remove_edge(typename Config::out_edge_iterator iter) 1255 { 1256 typedef typename Config::global_edgelist_selector EdgeListS; 1257 BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value)); 1258 1259 typedef typename Config::graph_type graph_type; 1260 graph_type& g = static_cast<graph_type&>(*this); 1261 typename Config::edge_descriptor e = *iter; 1262 typename Config::OutEdgeList& oel = g.out_edge_list(source(e, g)); 1263 typename Config::InEdgeList& iel = in_edge_list(g, target(e, g)); 1264 typedef typename Config::OutEdgeList::value_type::property_type PType; 1265 PType& p = *(PType*)e.get_property(); 1266 detail::remove_directed_edge_dispatch(*iter, iel, p); 1267 g.m_edges.erase(iter.base()->get_iter()); 1268 oel.erase(iter.base()); 1269 } 1270 }; 1271 1272 // O(E/V) for allow_parallel_edge_tag 1273 // O(log(E/V)) for disallow_parallel_edge_tag 1274 template <class Config> 1275 inline void remove_edge(typename Config::vertex_descriptor u,typename Config::vertex_descriptor v,bidirectional_graph_helper_with_property<Config> & g_)1276 remove_edge(typename Config::vertex_descriptor u, 1277 typename Config::vertex_descriptor v, 1278 bidirectional_graph_helper_with_property<Config>& g_) 1279 { 1280 typedef typename Config::global_edgelist_selector EdgeListS; 1281 BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value)); 1282 1283 typedef typename Config::graph_type graph_type; 1284 graph_type& g = static_cast<graph_type&>(g_); 1285 typedef typename Config::edge_parallel_category Cat; 1286 detail::remove_edge_and_property(g, g.out_edge_list(u), v, Cat()); 1287 detail::erase_from_incidence_list(in_edge_list(g, v), u, Cat()); 1288 } 1289 1290 // O(E/V) or O(log(E/V)) 1291 template <class EdgeOrIter, class Config> 1292 inline void remove_edge(EdgeOrIter e,bidirectional_graph_helper_with_property<Config> & g_)1293 remove_edge(EdgeOrIter e, 1294 bidirectional_graph_helper_with_property<Config>& g_) 1295 { 1296 typedef typename Config::global_edgelist_selector EdgeListS; 1297 BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value)); 1298 1299 g_.remove_edge(e); 1300 } 1301 1302 template <class Config, class Predicate> 1303 inline void remove_out_edge_if(typename Config::vertex_descriptor u,Predicate pred,bidirectional_graph_helper_with_property<Config> & g_)1304 remove_out_edge_if(typename Config::vertex_descriptor u, Predicate pred, 1305 bidirectional_graph_helper_with_property<Config>& g_) 1306 { 1307 typedef typename Config::global_edgelist_selector EdgeListS; 1308 BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value)); 1309 1310 typedef typename Config::graph_type graph_type; 1311 typedef typename Config::OutEdgeList::value_type::property_type PropT; 1312 graph_type& g = static_cast<graph_type&>(g_); 1313 1314 typedef typename Config::EdgeIter EdgeIter; 1315 typedef std::vector<EdgeIter> Garbage; 1316 Garbage garbage; 1317 1318 // First remove the edges from the targets' in-edge lists and 1319 // from the graph's edge set list. 1320 typename Config::out_edge_iterator out_i, out_end; 1321 for (boost::tie(out_i, out_end) = out_edges(u, g); out_i != out_end; ++out_i) 1322 if (pred(*out_i)) { 1323 detail::remove_directed_edge_dispatch 1324 (*out_i, in_edge_list(g, target(*out_i, g)), 1325 *(PropT*)(*out_i).get_property()); 1326 // Put in garbage to delete later. Will need the properties 1327 // for the remove_if of the out-edges. 1328 garbage.push_back((*out_i.base()).get_iter()); 1329 } 1330 1331 // Now remove the edges from this out-edge list. 1332 typename Config::out_edge_iterator first, last; 1333 boost::tie(first, last) = out_edges(u, g); 1334 typedef typename Config::edge_parallel_category Cat; 1335 detail::remove_directed_edge_if_dispatch 1336 (first, last, g.out_edge_list(u), pred, Cat()); 1337 1338 // Now delete the edge properties from the g.m_edges list 1339 for (typename Garbage::iterator i = garbage.begin(); 1340 i != garbage.end(); ++i) 1341 g.m_edges.erase(*i); 1342 } 1343 template <class Config, class Predicate> 1344 inline void remove_in_edge_if(typename Config::vertex_descriptor v,Predicate pred,bidirectional_graph_helper_with_property<Config> & g_)1345 remove_in_edge_if(typename Config::vertex_descriptor v, Predicate pred, 1346 bidirectional_graph_helper_with_property<Config>& g_) 1347 { 1348 typedef typename Config::global_edgelist_selector EdgeListS; 1349 BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value)); 1350 1351 typedef typename Config::graph_type graph_type; 1352 typedef typename Config::OutEdgeList::value_type::property_type PropT; 1353 graph_type& g = static_cast<graph_type&>(g_); 1354 1355 typedef typename Config::EdgeIter EdgeIter; 1356 typedef std::vector<EdgeIter> Garbage; 1357 Garbage garbage; 1358 1359 // First remove the edges from the sources' out-edge lists and 1360 // from the graph's edge set list. 1361 typename Config::in_edge_iterator in_i, in_end; 1362 for (boost::tie(in_i, in_end) = in_edges(v, g); in_i != in_end; ++in_i) 1363 if (pred(*in_i)) { 1364 typename Config::vertex_descriptor u = source(*in_i, g); 1365 detail::remove_directed_edge_dispatch 1366 (*in_i, g.out_edge_list(u), *(PropT*)(*in_i).get_property()); 1367 // Put in garbage to delete later. Will need the properties 1368 // for the remove_if of the out-edges. 1369 garbage.push_back((*in_i.base()).get_iter()); 1370 } 1371 // Now remove the edges from this in-edge list. 1372 typename Config::in_edge_iterator first, last; 1373 boost::tie(first, last) = in_edges(v, g); 1374 typedef typename Config::edge_parallel_category Cat; 1375 detail::remove_directed_edge_if_dispatch 1376 (first, last, in_edge_list(g, v), pred, Cat()); 1377 1378 // Now delete the edge properties from the g.m_edges list 1379 for (typename Garbage::iterator i = garbage.begin(); 1380 i != garbage.end(); ++i) 1381 g.m_edges.erase(*i); 1382 } 1383 1384 // O(1) 1385 template <class Config> 1386 inline typename Config::edges_size_type num_edges(const bidirectional_graph_helper_with_property<Config> & g_)1387 num_edges(const bidirectional_graph_helper_with_property<Config>& g_) 1388 { 1389 typedef typename Config::graph_type graph_type; 1390 const graph_type& g = static_cast<const graph_type&>(g_); 1391 return g.m_edges.size(); 1392 } 1393 // O(E/V * E/V) for allow_parallel_edge_tag 1394 // O(E/V * log(E/V)) for disallow_parallel_edge_tag 1395 template <class Config> 1396 inline void clear_vertex(typename Config::vertex_descriptor u,bidirectional_graph_helper_with_property<Config> & g_)1397 clear_vertex(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::OutEdgeList& el = g.out_edge_list(u); 1407 typename Config::OutEdgeList::iterator 1408 ei = el.begin(), ei_end = el.end(); 1409 for (; ei != ei_end; ++ei) { 1410 detail::erase_from_incidence_list 1411 (in_edge_list(g, (*ei).get_target()), u, Cat()); 1412 g.m_edges.erase((*ei).get_iter()); 1413 } 1414 typename Config::InEdgeList& in_el = in_edge_list(g, u); 1415 typename Config::InEdgeList::iterator 1416 in_ei = in_el.begin(), in_ei_end = in_el.end(); 1417 for (; in_ei != in_ei_end; ++in_ei) { 1418 detail::erase_from_incidence_list 1419 (g.out_edge_list((*in_ei).get_target()), u, Cat()); 1420 g.m_edges.erase((*in_ei).get_iter()); 1421 } 1422 g.out_edge_list(u).clear(); 1423 in_edge_list(g, u).clear(); 1424 } 1425 1426 template <class Config> 1427 inline void clear_out_edges(typename Config::vertex_descriptor u,bidirectional_graph_helper_with_property<Config> & g_)1428 clear_out_edges(typename Config::vertex_descriptor u, 1429 bidirectional_graph_helper_with_property<Config>& g_) 1430 { 1431 typedef typename Config::global_edgelist_selector EdgeListS; 1432 BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value)); 1433 1434 typedef typename Config::graph_type graph_type; 1435 typedef typename Config::edge_parallel_category Cat; 1436 graph_type& g = static_cast<graph_type&>(g_); 1437 typename Config::OutEdgeList& el = g.out_edge_list(u); 1438 typename Config::OutEdgeList::iterator 1439 ei = el.begin(), ei_end = el.end(); 1440 for (; ei != ei_end; ++ei) { 1441 detail::erase_from_incidence_list 1442 (in_edge_list(g, (*ei).get_target()), u, Cat()); 1443 g.m_edges.erase((*ei).get_iter()); 1444 } 1445 g.out_edge_list(u).clear(); 1446 } 1447 1448 template <class Config> 1449 inline void clear_in_edges(typename Config::vertex_descriptor u,bidirectional_graph_helper_with_property<Config> & g_)1450 clear_in_edges(typename Config::vertex_descriptor u, 1451 bidirectional_graph_helper_with_property<Config>& g_) 1452 { 1453 typedef typename Config::global_edgelist_selector EdgeListS; 1454 BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value)); 1455 1456 typedef typename Config::graph_type graph_type; 1457 typedef typename Config::edge_parallel_category Cat; 1458 graph_type& g = static_cast<graph_type&>(g_); 1459 typename Config::InEdgeList& in_el = in_edge_list(g, u); 1460 typename Config::InEdgeList::iterator 1461 in_ei = in_el.begin(), in_ei_end = in_el.end(); 1462 for (; in_ei != in_ei_end; ++in_ei) { 1463 detail::erase_from_incidence_list 1464 (g.out_edge_list((*in_ei).get_target()), u, Cat()); 1465 g.m_edges.erase((*in_ei).get_iter()); 1466 } 1467 in_edge_list(g, u).clear(); 1468 } 1469 1470 // O(1) for allow_parallel_edge_tag 1471 // O(log(E/V)) for disallow_parallel_edge_tag 1472 template <class Config> 1473 inline std::pair<typename Config::edge_descriptor, bool> add_edge(typename Config::vertex_descriptor u,typename Config::vertex_descriptor v,const typename Config::edge_property_type & p,bidirectional_graph_helper_with_property<Config> & g_)1474 add_edge(typename Config::vertex_descriptor u, 1475 typename Config::vertex_descriptor v, 1476 const typename Config::edge_property_type& p, 1477 bidirectional_graph_helper_with_property<Config>& g_) 1478 { 1479 typedef typename Config::graph_type graph_type; 1480 graph_type& g = static_cast<graph_type&>(g_); 1481 typedef typename Config::edge_descriptor edge_descriptor; 1482 typedef typename Config::StoredEdge StoredEdge; 1483 bool inserted; 1484 typename Config::EdgeContainer::value_type e(u, v, p); 1485 typename Config::EdgeContainer::iterator p_iter 1486 = graph_detail::push(g.m_edges, e).first; 1487 typename Config::OutEdgeList::iterator i; 1488 boost::tie(i, inserted) = boost::graph_detail::push(g.out_edge_list(u), 1489 StoredEdge(v, p_iter, &g.m_edges)); 1490 if (inserted) { 1491 boost::graph_detail::push(in_edge_list(g, v), StoredEdge(u, p_iter, &g.m_edges)); 1492 return std::make_pair(edge_descriptor(u, v, &p_iter->m_property), 1493 true); 1494 } else { 1495 g.m_edges.erase(p_iter); 1496 return std::make_pair(edge_descriptor(u, v, 1497 &i->get_iter()->get_property()), 1498 false); 1499 } 1500 } 1501 1502 template <class Config> 1503 inline std::pair<typename Config::edge_descriptor, bool> add_edge(typename Config::vertex_descriptor u,typename Config::vertex_descriptor v,bidirectional_graph_helper_with_property<Config> & g_)1504 add_edge(typename Config::vertex_descriptor u, 1505 typename Config::vertex_descriptor v, 1506 bidirectional_graph_helper_with_property<Config>& g_) 1507 { 1508 typename Config::edge_property_type p; 1509 return add_edge(u, v, p, g_); 1510 } 1511 // O(1) 1512 template <class Config> 1513 inline typename Config::degree_size_type degree(typename Config::vertex_descriptor u,const bidirectional_graph_helper_with_property<Config> & g_)1514 degree(typename Config::vertex_descriptor u, 1515 const bidirectional_graph_helper_with_property<Config>& g_) 1516 { 1517 typedef typename Config::graph_type graph_type; 1518 const graph_type& g = static_cast<const graph_type&>(g_); 1519 return in_degree(u, g) + out_degree(u, g); 1520 } 1521 1522 //========================================================================= 1523 // Adjacency List Helper Class 1524 1525 template <class Config, class Base> 1526 struct adj_list_helper : public Base 1527 { 1528 typedef typename Config::graph_type AdjList; 1529 typedef typename Config::vertex_descriptor vertex_descriptor; 1530 typedef typename Config::edge_descriptor edge_descriptor; 1531 typedef typename Config::out_edge_iterator out_edge_iterator; 1532 typedef typename Config::in_edge_iterator in_edge_iterator; 1533 typedef typename Config::adjacency_iterator adjacency_iterator; 1534 typedef typename Config::inv_adjacency_iterator inv_adjacency_iterator; 1535 typedef typename Config::vertex_iterator vertex_iterator; 1536 typedef typename Config::edge_iterator edge_iterator; 1537 typedef typename Config::directed_category directed_category; 1538 typedef typename Config::edge_parallel_category edge_parallel_category; 1539 typedef typename Config::vertices_size_type vertices_size_type; 1540 typedef typename Config::edges_size_type edges_size_type; 1541 typedef typename Config::degree_size_type degree_size_type; 1542 typedef typename Config::StoredEdge StoredEdge; 1543 typedef typename Config::vertex_property_type vertex_property_type; 1544 typedef typename Config::edge_property_type edge_property_type; 1545 typedef typename Config::graph_property_type graph_property_type; 1546 1547 typedef typename Config::global_edgelist_selector 1548 global_edgelist_selector; 1549 1550 typedef typename lookup_one_property<vertex_property_type, vertex_bundle_t>::type vertex_bundled; 1551 typedef typename lookup_one_property<edge_property_type, edge_bundle_t>::type edge_bundled; 1552 typedef typename lookup_one_property<graph_property_type, graph_bundle_t>::type graph_bundled; 1553 }; 1554 1555 template <class Config, class Base> 1556 inline std::pair<typename Config::adjacency_iterator, 1557 typename Config::adjacency_iterator> adjacent_vertices(typename Config::vertex_descriptor u,const adj_list_helper<Config,Base> & g_)1558 adjacent_vertices(typename Config::vertex_descriptor u, 1559 const adj_list_helper<Config, Base>& g_) 1560 { 1561 typedef typename Config::graph_type AdjList; 1562 const AdjList& cg = static_cast<const AdjList&>(g_); 1563 AdjList& g = const_cast<AdjList&>(cg); 1564 typedef typename Config::adjacency_iterator adjacency_iterator; 1565 typename Config::out_edge_iterator first, last; 1566 boost::tie(first, last) = out_edges(u, g); 1567 return std::make_pair(adjacency_iterator(first, &g), 1568 adjacency_iterator(last, &g)); 1569 } 1570 template <class Config, class Base> 1571 inline std::pair<typename Config::inv_adjacency_iterator, 1572 typename Config::inv_adjacency_iterator> inv_adjacent_vertices(typename Config::vertex_descriptor u,const adj_list_helper<Config,Base> & g_)1573 inv_adjacent_vertices(typename Config::vertex_descriptor u, 1574 const adj_list_helper<Config, Base>& g_) 1575 { 1576 typedef typename Config::graph_type AdjList; 1577 const AdjList& cg = static_cast<const AdjList&>(g_); 1578 AdjList& g = const_cast<AdjList&>(cg); 1579 typedef typename Config::inv_adjacency_iterator inv_adjacency_iterator; 1580 typename Config::in_edge_iterator first, last; 1581 boost::tie(first, last) = in_edges(u, g); 1582 return std::make_pair(inv_adjacency_iterator(first, &g), 1583 inv_adjacency_iterator(last, &g)); 1584 } 1585 template <class Config, class Base> 1586 inline std::pair<typename Config::out_edge_iterator, 1587 typename Config::out_edge_iterator> out_edges(typename Config::vertex_descriptor u,const adj_list_helper<Config,Base> & g_)1588 out_edges(typename Config::vertex_descriptor u, 1589 const adj_list_helper<Config, Base>& g_) 1590 { 1591 typedef typename Config::graph_type AdjList; 1592 typedef typename Config::out_edge_iterator out_edge_iterator; 1593 const AdjList& cg = static_cast<const AdjList&>(g_); 1594 AdjList& g = const_cast<AdjList&>(cg); 1595 return 1596 std::make_pair(out_edge_iterator(g.out_edge_list(u).begin(), u), 1597 out_edge_iterator(g.out_edge_list(u).end(), u)); 1598 } 1599 template <class Config, class Base> 1600 inline std::pair<typename Config::vertex_iterator, 1601 typename Config::vertex_iterator> vertices(const adj_list_helper<Config,Base> & g_)1602 vertices(const adj_list_helper<Config, Base>& g_) 1603 { 1604 typedef typename Config::graph_type AdjList; 1605 const AdjList& cg = static_cast<const AdjList&>(g_); 1606 AdjList& g = const_cast<AdjList&>(cg); 1607 return std::make_pair( g.vertex_set().begin(), g.vertex_set().end() ); 1608 } 1609 template <class Config, class Base> 1610 inline typename Config::vertices_size_type num_vertices(const adj_list_helper<Config,Base> & g_)1611 num_vertices(const adj_list_helper<Config, Base>& g_) 1612 { 1613 typedef typename Config::graph_type AdjList; 1614 const AdjList& g = static_cast<const AdjList&>(g_); 1615 return g.vertex_set().size(); 1616 } 1617 template <class Config, class Base> 1618 inline typename Config::degree_size_type out_degree(typename Config::vertex_descriptor u,const adj_list_helper<Config,Base> & g_)1619 out_degree(typename Config::vertex_descriptor u, 1620 const adj_list_helper<Config, Base>& g_) 1621 { 1622 typedef typename Config::graph_type AdjList; 1623 const AdjList& g = static_cast<const AdjList&>(g_); 1624 return g.out_edge_list(u).size(); 1625 } 1626 template <class Config, class Base> 1627 inline std::pair<typename Config::edge_descriptor, bool> edge(typename Config::vertex_descriptor u,typename Config::vertex_descriptor v,const adj_list_helper<Config,Base> & g_)1628 edge(typename Config::vertex_descriptor u, 1629 typename Config::vertex_descriptor v, 1630 const adj_list_helper<Config, Base>& g_) 1631 { 1632 typedef typename Config::graph_type Graph; 1633 typedef typename Config::StoredEdge StoredEdge; 1634 const Graph& cg = static_cast<const Graph&>(g_); 1635 const typename Config::OutEdgeList& el = cg.out_edge_list(u); 1636 typename Config::OutEdgeList::const_iterator it = graph_detail:: 1637 find(el, StoredEdge(v)); 1638 return std::make_pair( 1639 typename Config::edge_descriptor 1640 (u, v, (it == el.end() ? 0 : &(*it).get_property())), 1641 (it != el.end())); 1642 } 1643 1644 template <class Config, class Base> 1645 inline std::pair<typename Config::out_edge_iterator, 1646 typename Config::out_edge_iterator> edge_range(typename Config::vertex_descriptor u,typename Config::vertex_descriptor v,const adj_list_helper<Config,Base> & g_)1647 edge_range(typename Config::vertex_descriptor u, 1648 typename Config::vertex_descriptor v, 1649 const adj_list_helper<Config, Base>& g_) 1650 { 1651 typedef typename Config::graph_type Graph; 1652 typedef typename Config::StoredEdge StoredEdge; 1653 const Graph& cg = static_cast<const Graph&>(g_); 1654 Graph& g = const_cast<Graph&>(cg); 1655 typedef typename Config::out_edge_iterator out_edge_iterator; 1656 typename Config::OutEdgeList& el = g.out_edge_list(u); 1657 typename Config::OutEdgeList::iterator first, last; 1658 typename Config::EdgeContainer fake_edge_container; 1659 boost::tie(first, last) = graph_detail:: 1660 equal_range(el, StoredEdge(v)); 1661 return std::make_pair(out_edge_iterator(first, u), 1662 out_edge_iterator(last, u)); 1663 } 1664 1665 template <class Config> 1666 inline typename Config::degree_size_type in_degree(typename Config::vertex_descriptor u,const directed_edges_helper<Config> & g_)1667 in_degree(typename Config::vertex_descriptor u, 1668 const directed_edges_helper<Config>& g_) 1669 { 1670 typedef typename Config::graph_type Graph; 1671 const Graph& cg = static_cast<const Graph&>(g_); 1672 Graph& g = const_cast<Graph&>(cg); 1673 return in_edge_list(g, u).size(); 1674 } 1675 1676 namespace detail { 1677 template <class Config, class Base, class Property> 1678 inline 1679 typename boost::property_map<typename Config::graph_type, 1680 Property>::type get_dispatch(adj_list_helper<Config,Base> &,Property p,boost::edge_property_tag)1681 get_dispatch(adj_list_helper<Config,Base>&, Property p, 1682 boost::edge_property_tag) { 1683 typedef typename Config::graph_type Graph; 1684 typedef typename boost::property_map<Graph, Property>::type PA; 1685 return PA(p); 1686 } 1687 template <class Config, class Base, class Property> 1688 inline 1689 typename boost::property_map<typename Config::graph_type, 1690 Property>::const_type get_dispatch(const adj_list_helper<Config,Base> &,Property p,boost::edge_property_tag)1691 get_dispatch(const adj_list_helper<Config,Base>&, Property p, 1692 boost::edge_property_tag) { 1693 typedef typename Config::graph_type Graph; 1694 typedef typename boost::property_map<Graph, Property>::const_type PA; 1695 return PA(p); 1696 } 1697 1698 template <class Config, class Base, class Property> 1699 inline 1700 typename boost::property_map<typename Config::graph_type, 1701 Property>::type get_dispatch(adj_list_helper<Config,Base> & g,Property p,boost::vertex_property_tag)1702 get_dispatch(adj_list_helper<Config,Base>& g, Property p, 1703 boost::vertex_property_tag) { 1704 typedef typename Config::graph_type Graph; 1705 typedef typename boost::property_map<Graph, Property>::type PA; 1706 return PA(&static_cast<Graph&>(g), p); 1707 } 1708 template <class Config, class Base, class Property> 1709 inline 1710 typename boost::property_map<typename Config::graph_type, 1711 Property>::const_type get_dispatch(const adj_list_helper<Config,Base> & g,Property p,boost::vertex_property_tag)1712 get_dispatch(const adj_list_helper<Config, Base>& g, Property p, 1713 boost::vertex_property_tag) { 1714 typedef typename Config::graph_type Graph; 1715 typedef typename boost::property_map<Graph, Property>::const_type PA; 1716 const Graph& cg = static_cast<const Graph&>(g); 1717 return PA(&cg, p); 1718 } 1719 1720 } // namespace detail 1721 1722 // Implementation of the PropertyGraph interface 1723 template <class Config, class Base, class Property> 1724 inline 1725 typename boost::property_map<typename Config::graph_type, Property>::type get(Property p,adj_list_helper<Config,Base> & g)1726 get(Property p, adj_list_helper<Config, Base>& g) { 1727 typedef typename detail::property_kind_from_graph<adj_list_helper<Config, Base>, Property>::type Kind; 1728 return detail::get_dispatch(g, p, Kind()); 1729 } 1730 template <class Config, class Base, class Property> 1731 inline 1732 typename boost::property_map<typename Config::graph_type, 1733 Property>::const_type get(Property p,const adj_list_helper<Config,Base> & g)1734 get(Property p, const adj_list_helper<Config, Base>& g) { 1735 typedef typename detail::property_kind_from_graph<adj_list_helper<Config, Base>, Property>::type Kind; 1736 return detail::get_dispatch(g, p, Kind()); 1737 } 1738 1739 template <class Config, class Base, class Property, class Key> 1740 inline 1741 typename boost::property_traits< 1742 typename boost::property_map<typename Config::graph_type, 1743 Property>::type 1744 >::reference get(Property p,adj_list_helper<Config,Base> & g,const Key & key)1745 get(Property p, adj_list_helper<Config, Base>& g, const Key& key) { 1746 return get(get(p, g), key); 1747 } 1748 1749 template <class Config, class Base, class Property, class Key> 1750 inline 1751 typename boost::property_traits< 1752 typename boost::property_map<typename Config::graph_type, 1753 Property>::const_type 1754 >::reference get(Property p,const adj_list_helper<Config,Base> & g,const Key & key)1755 get(Property p, const adj_list_helper<Config, Base>& g, const Key& key) { 1756 return get(get(p, g), key); 1757 } 1758 1759 template <class Config, class Base, class Property, class Key,class Value> 1760 inline void put(Property p,adj_list_helper<Config,Base> & g,const Key & key,const Value & value)1761 put(Property p, adj_list_helper<Config, Base>& g, 1762 const Key& key, const Value& value) 1763 { 1764 typedef typename Config::graph_type Graph; 1765 typedef typename boost::property_map<Graph, Property>::type Map; 1766 Map pmap = get(p, static_cast<Graph&>(g)); 1767 put(pmap, key, value); 1768 } 1769 1770 1771 //========================================================================= 1772 // Generalize Adjacency List Implementation 1773 1774 struct adj_list_tag { }; 1775 1776 template <class Derived, class Config, class Base> 1777 class adj_list_impl 1778 : public adj_list_helper<Config, Base> 1779 { 1780 typedef typename Config::OutEdgeList OutEdgeList; 1781 typedef typename Config::InEdgeList InEdgeList; 1782 typedef typename Config::StoredVertexList StoredVertexList; 1783 public: 1784 typedef typename Config::stored_vertex stored_vertex; 1785 typedef typename Config::EdgeContainer EdgeContainer; 1786 typedef typename Config::vertex_descriptor vertex_descriptor; 1787 typedef typename Config::edge_descriptor edge_descriptor; 1788 typedef typename Config::vertex_iterator vertex_iterator; 1789 typedef typename Config::edge_iterator edge_iterator; 1790 typedef typename Config::edge_parallel_category edge_parallel_category; 1791 typedef typename Config::vertices_size_type vertices_size_type; 1792 typedef typename Config::edges_size_type edges_size_type; 1793 typedef typename Config::degree_size_type degree_size_type; 1794 typedef typename Config::edge_property_type edge_property_type; 1795 typedef adj_list_tag graph_tag; 1796 null_vertex()1797 static vertex_descriptor null_vertex() 1798 { 1799 return 0; 1800 } 1801 adj_list_impl()1802 inline adj_list_impl() { } 1803 adj_list_impl(const adj_list_impl & x)1804 inline adj_list_impl(const adj_list_impl& x) { 1805 copy_impl(x); 1806 } operator =(const adj_list_impl & x)1807 inline adj_list_impl& operator=(const adj_list_impl& x) { 1808 this->clear(); 1809 copy_impl(x); 1810 return *this; 1811 } clear()1812 inline void clear() { 1813 for (typename StoredVertexList::iterator i = m_vertices.begin(); 1814 i != m_vertices.end(); ++i) 1815 delete (stored_vertex*)*i; 1816 m_vertices.clear(); 1817 m_edges.clear(); 1818 } adj_list_impl(vertices_size_type num_vertices)1819 inline adj_list_impl(vertices_size_type num_vertices) { 1820 for (vertices_size_type i = 0; i < num_vertices; ++i) 1821 add_vertex(static_cast<Derived&>(*this)); 1822 } 1823 template <class EdgeIterator> adj_list_impl(vertices_size_type num_vertices,EdgeIterator first,EdgeIterator last)1824 inline adj_list_impl(vertices_size_type num_vertices, 1825 EdgeIterator first, EdgeIterator last) 1826 { 1827 vertex_descriptor* v = new vertex_descriptor[num_vertices]; 1828 for (vertices_size_type i = 0; i < num_vertices; ++i) 1829 v[i] = add_vertex(static_cast<Derived&>(*this)); 1830 1831 while (first != last) { 1832 add_edge(v[(*first).first], v[(*first).second], *this); 1833 ++first; 1834 } 1835 delete [] v; 1836 } 1837 template <class EdgeIterator, class EdgePropertyIterator> adj_list_impl(vertices_size_type num_vertices,EdgeIterator first,EdgeIterator last,EdgePropertyIterator ep_iter)1838 inline adj_list_impl(vertices_size_type num_vertices, 1839 EdgeIterator first, EdgeIterator last, 1840 EdgePropertyIterator ep_iter) 1841 { 1842 vertex_descriptor* v = new vertex_descriptor[num_vertices]; 1843 for (vertices_size_type i = 0; i < num_vertices; ++i) 1844 v[i] = add_vertex(static_cast<Derived&>(*this)); 1845 1846 while (first != last) { 1847 add_edge(v[(*first).first], v[(*first).second], *ep_iter, *this); 1848 ++first; 1849 ++ep_iter; 1850 } 1851 delete [] v; 1852 } ~adj_list_impl()1853 ~adj_list_impl() { 1854 for (typename StoredVertexList::iterator i = m_vertices.begin(); 1855 i != m_vertices.end(); ++i) 1856 delete (stored_vertex*)*i; 1857 } 1858 // protected: out_edge_list(vertex_descriptor v)1859 inline OutEdgeList& out_edge_list(vertex_descriptor v) { 1860 stored_vertex* sv = (stored_vertex*)v; 1861 return sv->m_out_edges; 1862 } out_edge_list(vertex_descriptor v) const1863 inline const OutEdgeList& out_edge_list(vertex_descriptor v) const { 1864 stored_vertex* sv = (stored_vertex*)v; 1865 return sv->m_out_edges; 1866 } vertex_set()1867 inline StoredVertexList& vertex_set() { return m_vertices; } vertex_set() const1868 inline const StoredVertexList& vertex_set() const { return m_vertices; } 1869 copy_impl(const adj_list_impl & x_)1870 inline void copy_impl(const adj_list_impl& x_) 1871 { 1872 const Derived& x = static_cast<const Derived&>(x_); 1873 1874 // Would be better to have a constant time way to get from 1875 // vertices in x to the corresponding vertices in *this. 1876 std::map<stored_vertex*,stored_vertex*> vertex_map; 1877 1878 // Copy the stored vertex objects by adding each vertex 1879 // and copying its property object. 1880 vertex_iterator vi, vi_end; 1881 for (boost::tie(vi, vi_end) = vertices(x); vi != vi_end; ++vi) { 1882 stored_vertex* v = (stored_vertex*)add_vertex(*this); 1883 v->m_property = ((stored_vertex*)*vi)->m_property; 1884 vertex_map[(stored_vertex*)*vi] = v; 1885 } 1886 // Copy the edges by adding each edge and copying its 1887 // property object. 1888 edge_iterator ei, ei_end; 1889 for (boost::tie(ei, ei_end) = edges(x); ei != ei_end; ++ei) { 1890 edge_descriptor e; 1891 bool inserted; 1892 vertex_descriptor s = source(*ei,x), t = target(*ei,x); 1893 boost::tie(e, inserted) = add_edge(vertex_map[(stored_vertex*)s], 1894 vertex_map[(stored_vertex*)t], *this); 1895 *((edge_property_type*)e.m_eproperty) 1896 = *((edge_property_type*)(*ei).m_eproperty); 1897 } 1898 } 1899 1900 1901 typename Config::EdgeContainer m_edges; 1902 StoredVertexList m_vertices; 1903 }; 1904 1905 // O(1) 1906 template <class Derived, class Config, class Base> 1907 inline typename Config::vertex_descriptor add_vertex(adj_list_impl<Derived,Config,Base> & g_)1908 add_vertex(adj_list_impl<Derived, Config, Base>& g_) 1909 { 1910 Derived& g = static_cast<Derived&>(g_); 1911 typedef typename Config::stored_vertex stored_vertex; 1912 stored_vertex* v = new stored_vertex; 1913 typename Config::StoredVertexList::iterator pos; 1914 bool inserted; 1915 boost::tie(pos,inserted) = boost::graph_detail::push(g.m_vertices, v); 1916 v->m_position = pos; 1917 g.added_vertex(v); 1918 return v; 1919 } 1920 // O(1) 1921 template <class Derived, class Config, class Base> 1922 inline typename Config::vertex_descriptor add_vertex(const typename Config::vertex_property_type & p,adj_list_impl<Derived,Config,Base> & g_)1923 add_vertex(const typename Config::vertex_property_type& p, 1924 adj_list_impl<Derived, Config, Base>& g_) 1925 { 1926 typedef typename Config::vertex_descriptor vertex_descriptor; 1927 Derived& g = static_cast<Derived&>(g_); 1928 if (optional<vertex_descriptor> v 1929 = g.vertex_by_property(get_property_value(p, vertex_bundle))) 1930 return *v; 1931 1932 typedef typename Config::stored_vertex stored_vertex; 1933 stored_vertex* v = new stored_vertex(p); 1934 typename Config::StoredVertexList::iterator pos; 1935 bool inserted; 1936 boost::tie(pos,inserted) = boost::graph_detail::push(g.m_vertices, v); 1937 v->m_position = pos; 1938 g.added_vertex(v); 1939 return v; 1940 } 1941 // O(1) 1942 template <class Derived, class Config, class Base> remove_vertex(typename Config::vertex_descriptor u,adj_list_impl<Derived,Config,Base> & g_)1943 inline void remove_vertex(typename Config::vertex_descriptor u, 1944 adj_list_impl<Derived, Config, Base>& g_) 1945 { 1946 typedef typename Config::stored_vertex stored_vertex; 1947 Derived& g = static_cast<Derived&>(g_); 1948 g.removing_vertex(u, boost::graph_detail::iterator_stability(g_.m_vertices)); 1949 stored_vertex* su = (stored_vertex*)u; 1950 g.m_vertices.erase(su->m_position); 1951 delete su; 1952 } 1953 // O(V) 1954 template <class Derived, class Config, class Base> 1955 inline typename Config::vertex_descriptor vertex(typename Config::vertices_size_type n,const adj_list_impl<Derived,Config,Base> & g_)1956 vertex(typename Config::vertices_size_type n, 1957 const adj_list_impl<Derived, Config, Base>& g_) 1958 { 1959 const Derived& g = static_cast<const Derived&>(g_); 1960 typename Config::vertex_iterator i = vertices(g).first; 1961 while (n--) ++i; // std::advance(i, n); (not VC++ portable) 1962 return *i; 1963 } 1964 1965 //========================================================================= 1966 // Vector-Backbone Adjacency List Implementation 1967 1968 namespace detail { 1969 1970 template <class Graph, class vertex_descriptor> 1971 inline void remove_vertex_dispatch(Graph & g,vertex_descriptor u,boost::directed_tag)1972 remove_vertex_dispatch(Graph& g, vertex_descriptor u, 1973 boost::directed_tag) 1974 { 1975 typedef typename Graph::edge_parallel_category edge_parallel_category; 1976 g.m_vertices.erase(g.m_vertices.begin() + u); 1977 vertex_descriptor V = num_vertices(g); 1978 if (u != V) { 1979 for (vertex_descriptor v = 0; v < V; ++v) 1980 reindex_edge_list(g.out_edge_list(v), u, edge_parallel_category()); 1981 } 1982 } 1983 1984 template <class Graph, class vertex_descriptor> 1985 inline void remove_vertex_dispatch(Graph & g,vertex_descriptor u,boost::undirected_tag)1986 remove_vertex_dispatch(Graph& g, vertex_descriptor u, 1987 boost::undirected_tag) 1988 { 1989 typedef typename Graph::global_edgelist_selector EdgeListS; 1990 BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value)); 1991 1992 typedef typename Graph::edge_parallel_category edge_parallel_category; 1993 g.m_vertices.erase(g.m_vertices.begin() + u); 1994 vertex_descriptor V = num_vertices(g); 1995 for (vertex_descriptor v = 0; v < V; ++v) 1996 reindex_edge_list(g.out_edge_list(v), u, 1997 edge_parallel_category()); 1998 typedef typename Graph::EdgeContainer Container; 1999 typedef typename Container::iterator Iter; 2000 Iter ei = g.m_edges.begin(), ei_end = g.m_edges.end(); 2001 for (; ei != ei_end; ++ei) { 2002 if (ei->m_source > u) 2003 --ei->m_source; 2004 if (ei->m_target > u) 2005 --ei->m_target; 2006 } 2007 } 2008 template <class Graph, class vertex_descriptor> 2009 inline void remove_vertex_dispatch(Graph & g,vertex_descriptor u,boost::bidirectional_tag)2010 remove_vertex_dispatch(Graph& g, vertex_descriptor u, 2011 boost::bidirectional_tag) 2012 { 2013 typedef typename Graph::global_edgelist_selector EdgeListS; 2014 BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value)); 2015 2016 typedef typename Graph::edge_parallel_category edge_parallel_category; 2017 g.m_vertices.erase(g.m_vertices.begin() + u); 2018 vertex_descriptor V = num_vertices(g); 2019 vertex_descriptor v; 2020 if (u != V) { 2021 for (v = 0; v < V; ++v) 2022 reindex_edge_list(g.out_edge_list(v), u, 2023 edge_parallel_category()); 2024 for (v = 0; v < V; ++v) 2025 reindex_edge_list(in_edge_list(g, v), u, 2026 edge_parallel_category()); 2027 2028 typedef typename Graph::EdgeContainer Container; 2029 typedef typename Container::iterator Iter; 2030 Iter ei = g.m_edges.begin(), ei_end = g.m_edges.end(); 2031 for (; ei != ei_end; ++ei) { 2032 if (ei->m_source > u) 2033 --ei->m_source; 2034 if (ei->m_target > u) 2035 --ei->m_target; 2036 } 2037 } 2038 } 2039 2040 template <class EdgeList, class vertex_descriptor> 2041 inline void reindex_edge_list(EdgeList & el,vertex_descriptor u,boost::allow_parallel_edge_tag)2042 reindex_edge_list(EdgeList& el, vertex_descriptor u, 2043 boost::allow_parallel_edge_tag) 2044 { 2045 typename EdgeList::iterator ei = el.begin(), e_end = el.end(); 2046 for (; ei != e_end; ++ei) 2047 if ((*ei).get_target() > u) 2048 --(*ei).get_target(); 2049 } 2050 template <class EdgeList, class vertex_descriptor> 2051 inline void reindex_edge_list(EdgeList & el,vertex_descriptor u,boost::disallow_parallel_edge_tag)2052 reindex_edge_list(EdgeList& el, vertex_descriptor u, 2053 boost::disallow_parallel_edge_tag) 2054 { 2055 typename EdgeList::iterator ei = el.begin(), e_end = el.end(); 2056 while (ei != e_end) { 2057 typename EdgeList::value_type ce = *ei; 2058 ++ei; 2059 if (ce.get_target() > u) { 2060 el.erase(ce); 2061 --ce.get_target(); 2062 el.insert(ce); 2063 } 2064 } 2065 } 2066 } // namespace detail 2067 2068 struct vec_adj_list_tag { }; 2069 2070 template <class Graph, class Config, class Base> 2071 class vec_adj_list_impl 2072 : public adj_list_helper<Config, Base> 2073 { 2074 typedef typename Config::OutEdgeList OutEdgeList; 2075 typedef typename Config::InEdgeList InEdgeList; 2076 typedef typename Config::StoredVertexList StoredVertexList; 2077 public: 2078 typedef typename Config::vertex_descriptor vertex_descriptor; 2079 typedef typename Config::edge_descriptor edge_descriptor; 2080 typedef typename Config::out_edge_iterator out_edge_iterator; 2081 typedef typename Config::edge_iterator edge_iterator; 2082 typedef typename Config::directed_category directed_category; 2083 typedef typename Config::vertices_size_type vertices_size_type; 2084 typedef typename Config::edges_size_type edges_size_type; 2085 typedef typename Config::degree_size_type degree_size_type; 2086 typedef typename Config::StoredEdge StoredEdge; 2087 typedef typename Config::stored_vertex stored_vertex; 2088 typedef typename Config::EdgeContainer EdgeContainer; 2089 typedef typename Config::edge_property_type edge_property_type; 2090 typedef vec_adj_list_tag graph_tag; 2091 null_vertex()2092 static vertex_descriptor null_vertex() 2093 { 2094 return (std::numeric_limits<vertex_descriptor>::max)(); 2095 } 2096 vec_adj_list_impl()2097 inline vec_adj_list_impl() { } 2098 vec_adj_list_impl(const vec_adj_list_impl & x)2099 inline vec_adj_list_impl(const vec_adj_list_impl& x) { 2100 copy_impl(x); 2101 } operator =(const vec_adj_list_impl & x)2102 inline vec_adj_list_impl& operator=(const vec_adj_list_impl& x) { 2103 this->clear(); 2104 copy_impl(x); 2105 return *this; 2106 } clear()2107 inline void clear() { 2108 m_vertices.clear(); 2109 m_edges.clear(); 2110 } 2111 vec_adj_list_impl(vertices_size_type _num_vertices)2112 inline vec_adj_list_impl(vertices_size_type _num_vertices) 2113 : m_vertices(_num_vertices) { } 2114 2115 template <class EdgeIterator> vec_adj_list_impl(vertices_size_type num_vertices,EdgeIterator first,EdgeIterator last)2116 inline vec_adj_list_impl(vertices_size_type num_vertices, 2117 EdgeIterator first, EdgeIterator last) 2118 : m_vertices(num_vertices) 2119 { 2120 while (first != last) { 2121 add_edge((*first).first, (*first).second, 2122 static_cast<Graph&>(*this)); 2123 ++first; 2124 } 2125 } 2126 template <class EdgeIterator, class EdgePropertyIterator> vec_adj_list_impl(vertices_size_type num_vertices,EdgeIterator first,EdgeIterator last,EdgePropertyIterator ep_iter)2127 inline vec_adj_list_impl(vertices_size_type num_vertices, 2128 EdgeIterator first, EdgeIterator last, 2129 EdgePropertyIterator ep_iter) 2130 : m_vertices(num_vertices) 2131 { 2132 while (first != last) { 2133 add_edge((*first).first, (*first).second, *ep_iter, 2134 static_cast<Graph&>(*this)); 2135 ++first; 2136 ++ep_iter; 2137 } 2138 } 2139 2140 // protected: vertex_set() const2141 inline boost::integer_range<vertex_descriptor> vertex_set() const { 2142 return boost::integer_range<vertex_descriptor>(0, m_vertices.size()); 2143 } out_edge_list(vertex_descriptor v)2144 inline OutEdgeList& out_edge_list(vertex_descriptor v) { 2145 return m_vertices[v].m_out_edges; 2146 } out_edge_list(vertex_descriptor v) const2147 inline const OutEdgeList& out_edge_list(vertex_descriptor v) const { 2148 return m_vertices[v].m_out_edges; 2149 } copy_impl(const vec_adj_list_impl & x_)2150 inline void copy_impl(const vec_adj_list_impl& x_) 2151 { 2152 const Graph& x = static_cast<const Graph&>(x_); 2153 // Copy the stored vertex objects by adding each vertex 2154 // and copying its property object. 2155 for (vertices_size_type i = 0; i < num_vertices(x); ++i) { 2156 vertex_descriptor v = add_vertex(*this); 2157 m_vertices[v].m_property = x.m_vertices[i].m_property; 2158 } 2159 // Copy the edges by adding each edge and copying its 2160 // property object. 2161 edge_iterator ei, ei_end; 2162 for (boost::tie(ei, ei_end) = edges(x); ei != ei_end; ++ei) { 2163 edge_descriptor e; 2164 bool inserted; 2165 boost::tie(e, inserted) = add_edge(source(*ei,x), target(*ei,x) , *this); 2166 *((edge_property_type*)e.m_eproperty) 2167 = *((edge_property_type*)(*ei).m_eproperty); 2168 } 2169 } 2170 typename Config::EdgeContainer m_edges; 2171 StoredVertexList m_vertices; 2172 }; 2173 // Had to make these non-members to avoid accidental instantiation 2174 // on SGI MIPSpro C++ 2175 template <class G, class C, class B> 2176 inline typename C::InEdgeList& in_edge_list(vec_adj_list_impl<G,C,B> & g,typename C::vertex_descriptor v)2177 in_edge_list(vec_adj_list_impl<G,C,B>& g, 2178 typename C::vertex_descriptor v) { 2179 return g.m_vertices[v].m_in_edges; 2180 } 2181 template <class G, class C, class B> 2182 inline const typename C::InEdgeList& in_edge_list(const vec_adj_list_impl<G,C,B> & g,typename C::vertex_descriptor v)2183 in_edge_list(const vec_adj_list_impl<G,C,B>& g, 2184 typename C::vertex_descriptor v) { 2185 return g.m_vertices[v].m_in_edges; 2186 } 2187 2188 // O(1) 2189 template <class Graph, class Config, class Base> 2190 inline typename Config::vertex_descriptor add_vertex(vec_adj_list_impl<Graph,Config,Base> & g_)2191 add_vertex(vec_adj_list_impl<Graph, Config, Base>& g_) { 2192 Graph& g = static_cast<Graph&>(g_); 2193 g.m_vertices.resize(g.m_vertices.size() + 1); 2194 g.added_vertex(g.m_vertices.size() - 1); 2195 return g.m_vertices.size() - 1; 2196 } 2197 2198 template <class Graph, class Config, class Base> 2199 inline typename Config::vertex_descriptor add_vertex(const typename Config::vertex_property_type & p,vec_adj_list_impl<Graph,Config,Base> & g_)2200 add_vertex(const typename Config::vertex_property_type& p, 2201 vec_adj_list_impl<Graph, Config, Base>& g_) { 2202 typedef typename Config::vertex_descriptor vertex_descriptor; 2203 Graph& g = static_cast<Graph&>(g_); 2204 if (optional<vertex_descriptor> v 2205 = g.vertex_by_property(get_property_value(p, vertex_bundle))) 2206 return *v; 2207 typedef typename Config::stored_vertex stored_vertex; 2208 g.m_vertices.push_back(stored_vertex(p)); 2209 g.added_vertex(g.m_vertices.size() - 1); 2210 return g.m_vertices.size() - 1; 2211 } 2212 2213 // Here we override the directed_graph_helper add_edge() function 2214 // so that the number of vertices is automatically changed if 2215 // either u or v is greater than the number of vertices. 2216 template <class Graph, class Config, class Base> 2217 inline std::pair<typename Config::edge_descriptor, bool> add_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_)2218 add_edge(typename Config::vertex_descriptor u, 2219 typename Config::vertex_descriptor v, 2220 const typename Config::edge_property_type& p, 2221 vec_adj_list_impl<Graph, Config, Base>& g_) 2222 { 2223 BOOST_USING_STD_MAX(); 2224 typename Config::vertex_descriptor x = max BOOST_PREVENT_MACRO_SUBSTITUTION(u, v); 2225 if (x >= num_vertices(g_)) 2226 g_.m_vertices.resize(x + 1); 2227 adj_list_helper<Config, Base>& g = g_; 2228 return add_edge(u, v, p, g); 2229 } 2230 template <class Graph, class Config, class Base> 2231 inline std::pair<typename Config::edge_descriptor, bool> add_edge(typename Config::vertex_descriptor u,typename Config::vertex_descriptor v,vec_adj_list_impl<Graph,Config,Base> & g_)2232 add_edge(typename Config::vertex_descriptor u, 2233 typename Config::vertex_descriptor v, 2234 vec_adj_list_impl<Graph, Config, Base>& g_) 2235 { 2236 typename Config::edge_property_type p; 2237 return add_edge(u, v, p, g_); 2238 } 2239 2240 2241 // O(V + E) 2242 template <class Graph, class Config, class Base> remove_vertex(typename Config::vertex_descriptor v,vec_adj_list_impl<Graph,Config,Base> & g_)2243 inline void remove_vertex(typename Config::vertex_descriptor v, 2244 vec_adj_list_impl<Graph, Config, Base>& g_) 2245 { 2246 typedef typename Config::directed_category Cat; 2247 Graph& g = static_cast<Graph&>(g_); 2248 g.removing_vertex(v, boost::graph_detail::iterator_stability(g_.m_vertices)); 2249 detail::remove_vertex_dispatch(g, v, Cat()); 2250 } 2251 // O(1) 2252 template <class Graph, class Config, class Base> 2253 inline typename Config::vertex_descriptor vertex(typename Config::vertices_size_type n,const vec_adj_list_impl<Graph,Config,Base> &)2254 vertex(typename Config::vertices_size_type n, 2255 const vec_adj_list_impl<Graph, Config, Base>&) 2256 { 2257 return n; 2258 } 2259 2260 2261 namespace detail { 2262 2263 //========================================================================= 2264 // Adjacency List Generator 2265 2266 template <class Graph, class VertexListS, class OutEdgeListS, 2267 class DirectedS, class VertexProperty, class EdgeProperty, 2268 class GraphProperty, class EdgeListS> 2269 struct adj_list_gen 2270 { 2271 typedef typename detail::is_random_access<VertexListS>::type 2272 is_rand_access; 2273 typedef typename has_property<EdgeProperty>::type has_edge_property; 2274 typedef typename DirectedS::is_directed_t DirectedT; 2275 typedef typename DirectedS::is_bidir_t BidirectionalT; 2276 2277 struct config 2278 { 2279 typedef OutEdgeListS edgelist_selector; 2280 typedef EdgeListS global_edgelist_selector; 2281 2282 typedef Graph graph_type; 2283 typedef EdgeProperty edge_property_type; 2284 typedef VertexProperty vertex_property_type; 2285 typedef GraphProperty graph_property_type; 2286 typedef std::size_t vertices_size_type; 2287 2288 typedef adjacency_list_traits<OutEdgeListS, VertexListS, DirectedS> 2289 Traits; 2290 2291 typedef typename Traits::directed_category directed_category; 2292 typedef typename Traits::edge_parallel_category edge_parallel_category; 2293 typedef typename Traits::vertex_descriptor vertex_descriptor; 2294 typedef typename Traits::edge_descriptor edge_descriptor; 2295 2296 typedef void* vertex_ptr; 2297 2298 // need to reorganize this to avoid instantiating stuff 2299 // that doesn't get used -JGS 2300 2301 // VertexList and vertex_iterator 2302 typedef typename container_gen<VertexListS, 2303 vertex_ptr>::type SeqVertexList; 2304 typedef boost::integer_range<vertex_descriptor> RandVertexList; 2305 typedef typename mpl::if_<is_rand_access, 2306 RandVertexList, SeqVertexList>::type VertexList; 2307 2308 typedef typename VertexList::iterator vertex_iterator; 2309 2310 // EdgeContainer and StoredEdge 2311 2312 typedef typename container_gen<EdgeListS, 2313 list_edge<vertex_descriptor, EdgeProperty> >::type EdgeContainer; 2314 2315 typedef typename mpl::and_<DirectedT, 2316 typename mpl::not_<BidirectionalT>::type >::type on_edge_storage; 2317 2318 typedef typename mpl::if_<on_edge_storage, 2319 std::size_t, typename EdgeContainer::size_type 2320 >::type edges_size_type; 2321 2322 typedef typename EdgeContainer::iterator EdgeIter; 2323 2324 typedef typename detail::is_random_access<EdgeListS>::type is_edge_ra; 2325 2326 typedef typename mpl::if_<on_edge_storage, 2327 stored_edge_property<vertex_descriptor, EdgeProperty>, 2328 typename mpl::if_<is_edge_ra, 2329 stored_ra_edge_iter<vertex_descriptor, EdgeContainer, EdgeProperty>, 2330 stored_edge_iter<vertex_descriptor, EdgeIter, EdgeProperty> 2331 >::type 2332 >::type StoredEdge; 2333 2334 // Adjacency Types 2335 2336 typedef typename container_gen<OutEdgeListS, StoredEdge>::type 2337 OutEdgeList; 2338 typedef typename OutEdgeList::size_type degree_size_type; 2339 typedef typename OutEdgeList::iterator OutEdgeIter; 2340 2341 typedef boost::detail::iterator_traits<OutEdgeIter> OutEdgeIterTraits; 2342 typedef typename OutEdgeIterTraits::iterator_category OutEdgeIterCat; 2343 typedef typename OutEdgeIterTraits::difference_type OutEdgeIterDiff; 2344 2345 typedef out_edge_iter< 2346 OutEdgeIter, vertex_descriptor, edge_descriptor, OutEdgeIterDiff 2347 > out_edge_iterator; 2348 2349 typedef typename adjacency_iterator_generator<graph_type, 2350 vertex_descriptor, out_edge_iterator>::type adjacency_iterator; 2351 2352 typedef OutEdgeList InEdgeList; 2353 typedef OutEdgeIter InEdgeIter; 2354 typedef OutEdgeIterCat InEdgeIterCat; 2355 typedef OutEdgeIterDiff InEdgeIterDiff; 2356 2357 typedef in_edge_iter< 2358 InEdgeIter, vertex_descriptor, edge_descriptor, InEdgeIterDiff 2359 > in_edge_iterator; 2360 2361 typedef typename inv_adjacency_iterator_generator<graph_type, 2362 vertex_descriptor, in_edge_iterator>::type inv_adjacency_iterator; 2363 2364 // Edge Iterator 2365 2366 typedef boost::detail::iterator_traits<EdgeIter> EdgeIterTraits; 2367 typedef typename EdgeIterTraits::iterator_category EdgeIterCat; 2368 typedef typename EdgeIterTraits::difference_type EdgeIterDiff; 2369 2370 typedef undirected_edge_iter< 2371 EdgeIter 2372 , edge_descriptor 2373 , EdgeIterDiff 2374 > UndirectedEdgeIter; // also used for bidirectional 2375 2376 typedef adj_list_edge_iterator<vertex_iterator, out_edge_iterator, 2377 graph_type> DirectedEdgeIter; 2378 2379 typedef typename mpl::if_<on_edge_storage, 2380 DirectedEdgeIter, UndirectedEdgeIter>::type edge_iterator; 2381 2382 // stored_vertex and StoredVertexList 2383 typedef typename container_gen<VertexListS, vertex_ptr>::type 2384 SeqStoredVertexList; 2385 struct seq_stored_vertex { seq_stored_vertexboost::detail::adj_list_gen::config::seq_stored_vertex2386 seq_stored_vertex() { } seq_stored_vertexboost::detail::adj_list_gen::config::seq_stored_vertex2387 seq_stored_vertex(const VertexProperty& p) : m_property(p) { } 2388 OutEdgeList m_out_edges; 2389 VertexProperty m_property; 2390 typename SeqStoredVertexList::iterator m_position; 2391 }; 2392 struct bidir_seq_stored_vertex { bidir_seq_stored_vertexboost::detail::adj_list_gen::config::bidir_seq_stored_vertex2393 bidir_seq_stored_vertex() { } bidir_seq_stored_vertexboost::detail::adj_list_gen::config::bidir_seq_stored_vertex2394 bidir_seq_stored_vertex(const VertexProperty& p) : m_property(p) { } 2395 OutEdgeList m_out_edges; 2396 InEdgeList m_in_edges; 2397 VertexProperty m_property; 2398 typename SeqStoredVertexList::iterator m_position; 2399 }; 2400 struct rand_stored_vertex { rand_stored_vertexboost::detail::adj_list_gen::config::rand_stored_vertex2401 rand_stored_vertex() { } rand_stored_vertexboost::detail::adj_list_gen::config::rand_stored_vertex2402 rand_stored_vertex(const VertexProperty& p) : m_property(p) { } 2403 OutEdgeList m_out_edges; 2404 VertexProperty m_property; 2405 }; 2406 struct bidir_rand_stored_vertex { bidir_rand_stored_vertexboost::detail::adj_list_gen::config::bidir_rand_stored_vertex2407 bidir_rand_stored_vertex() { } bidir_rand_stored_vertexboost::detail::adj_list_gen::config::bidir_rand_stored_vertex2408 bidir_rand_stored_vertex(const VertexProperty& p) : m_property(p) { } 2409 OutEdgeList m_out_edges; 2410 InEdgeList m_in_edges; 2411 VertexProperty m_property; 2412 }; 2413 typedef typename mpl::if_<is_rand_access, 2414 typename mpl::if_<BidirectionalT, 2415 bidir_rand_stored_vertex, rand_stored_vertex>::type, 2416 typename mpl::if_<BidirectionalT, 2417 bidir_seq_stored_vertex, seq_stored_vertex>::type 2418 >::type StoredVertex; 2419 struct stored_vertex : public StoredVertex { stored_vertexboost::detail::adj_list_gen::config::stored_vertex2420 stored_vertex() { } stored_vertexboost::detail::adj_list_gen::config::stored_vertex2421 stored_vertex(const VertexProperty& p) : StoredVertex(p) { } 2422 }; 2423 2424 typedef typename container_gen<VertexListS, stored_vertex>::type 2425 RandStoredVertexList; 2426 typedef typename mpl::if_< is_rand_access, 2427 RandStoredVertexList, SeqStoredVertexList>::type StoredVertexList; 2428 }; // end of config 2429 2430 2431 typedef typename mpl::if_<BidirectionalT, 2432 bidirectional_graph_helper_with_property<config>, 2433 typename mpl::if_<DirectedT, 2434 directed_graph_helper<config>, 2435 undirected_graph_helper<config> 2436 >::type 2437 >::type DirectedHelper; 2438 2439 typedef typename mpl::if_<is_rand_access, 2440 vec_adj_list_impl<Graph, config, DirectedHelper>, 2441 adj_list_impl<Graph, config, DirectedHelper> 2442 >::type type; 2443 2444 }; 2445 2446 } // namespace detail 2447 2448 //========================================================================= 2449 // Vertex Property Maps 2450 2451 template <class Graph, class ValueType, class Reference, class Tag> 2452 struct adj_list_vertex_property_map 2453 : public boost::put_get_helper< 2454 Reference, 2455 adj_list_vertex_property_map<Graph, ValueType, Reference, Tag> 2456 > 2457 { 2458 typedef typename Graph::stored_vertex StoredVertex; 2459 typedef ValueType value_type; 2460 typedef Reference reference; 2461 typedef typename Graph::vertex_descriptor key_type; 2462 typedef boost::lvalue_property_map_tag category; adj_list_vertex_property_mapboost::adj_list_vertex_property_map2463 inline adj_list_vertex_property_map(const Graph* = 0, Tag tag = Tag()): m_tag(tag) { } operator []boost::adj_list_vertex_property_map2464 inline Reference operator[](key_type v) const { 2465 StoredVertex* sv = (StoredVertex*)v; 2466 return get_property_value(sv->m_property, m_tag); 2467 } operator ()boost::adj_list_vertex_property_map2468 inline Reference operator()(key_type v) const { 2469 return this->operator[](v); 2470 } 2471 Tag m_tag; 2472 }; 2473 2474 template <class Graph, class Property, class PropRef> 2475 struct adj_list_vertex_all_properties_map 2476 : public boost::put_get_helper<PropRef, 2477 adj_list_vertex_all_properties_map<Graph, Property, PropRef> 2478 > 2479 { 2480 typedef typename Graph::stored_vertex StoredVertex; 2481 typedef Property value_type; 2482 typedef PropRef reference; 2483 typedef typename Graph::vertex_descriptor key_type; 2484 typedef boost::lvalue_property_map_tag category; adj_list_vertex_all_properties_mapboost::adj_list_vertex_all_properties_map2485 inline adj_list_vertex_all_properties_map(const Graph* = 0, vertex_all_t = vertex_all_t()) { } operator []boost::adj_list_vertex_all_properties_map2486 inline PropRef operator[](key_type v) const { 2487 StoredVertex* sv = (StoredVertex*)v; 2488 return sv->m_property; 2489 } operator ()boost::adj_list_vertex_all_properties_map2490 inline PropRef operator()(key_type v) const { 2491 return this->operator[](v); 2492 } 2493 }; 2494 2495 template <class Graph, class GraphPtr, class ValueType, class Reference, 2496 class Tag> 2497 struct vec_adj_list_vertex_property_map 2498 : public boost::put_get_helper< 2499 Reference, 2500 vec_adj_list_vertex_property_map<Graph,GraphPtr,ValueType,Reference, 2501 Tag> 2502 > 2503 { 2504 typedef ValueType value_type; 2505 typedef Reference reference; 2506 typedef typename boost::graph_traits<Graph>::vertex_descriptor key_type; 2507 typedef boost::lvalue_property_map_tag category; vec_adj_list_vertex_property_mapboost::vec_adj_list_vertex_property_map2508 vec_adj_list_vertex_property_map(GraphPtr g = 0, Tag tag = Tag()) : m_g(g), m_tag(tag) { } operator []boost::vec_adj_list_vertex_property_map2509 inline Reference operator[](key_type v) const { 2510 return get_property_value(m_g->m_vertices[v].m_property, m_tag); 2511 } operator ()boost::vec_adj_list_vertex_property_map2512 inline Reference operator()(key_type v) const { 2513 return this->operator[](v); 2514 } 2515 GraphPtr m_g; 2516 Tag m_tag; 2517 }; 2518 2519 template <class Graph, class GraphPtr, class Property, class PropertyRef> 2520 struct vec_adj_list_vertex_all_properties_map 2521 : public boost::put_get_helper<PropertyRef, 2522 vec_adj_list_vertex_all_properties_map<Graph,GraphPtr,Property, 2523 PropertyRef> 2524 > 2525 { 2526 typedef Property value_type; 2527 typedef PropertyRef reference; 2528 typedef typename boost::graph_traits<Graph>::vertex_descriptor key_type; 2529 typedef boost::lvalue_property_map_tag category; vec_adj_list_vertex_all_properties_mapboost::vec_adj_list_vertex_all_properties_map2530 vec_adj_list_vertex_all_properties_map(GraphPtr g = 0, vertex_all_t = vertex_all_t()) : m_g(g) { } operator []boost::vec_adj_list_vertex_all_properties_map2531 inline PropertyRef operator[](key_type v) const { 2532 return m_g->m_vertices[v].m_property; 2533 } operator ()boost::vec_adj_list_vertex_all_properties_map2534 inline PropertyRef operator()(key_type v) const { 2535 return this->operator[](v); 2536 } 2537 GraphPtr m_g; 2538 }; 2539 2540 struct adj_list_any_vertex_pa { 2541 template <class Tag, class Graph, class Property> 2542 struct bind_ { 2543 typedef typename property_value<Property, Tag>::type value_type; 2544 typedef value_type& reference; 2545 typedef const value_type& const_reference; 2546 2547 typedef adj_list_vertex_property_map 2548 <Graph, value_type, reference, Tag> type; 2549 typedef adj_list_vertex_property_map 2550 <Graph, value_type, const_reference, Tag> const_type; 2551 }; 2552 }; 2553 struct adj_list_all_vertex_pa { 2554 template <class Tag, class Graph, class Property> 2555 struct bind_ { 2556 typedef typename Graph::vertex_descriptor Vertex; 2557 typedef adj_list_vertex_all_properties_map<Graph,Property, 2558 Property&> type; 2559 typedef adj_list_vertex_all_properties_map<Graph,Property, 2560 const Property&> const_type; 2561 }; 2562 }; 2563 2564 template <class Property, class Vertex> 2565 struct vec_adj_list_vertex_id_map 2566 : public boost::put_get_helper< 2567 Vertex, vec_adj_list_vertex_id_map<Property, Vertex> 2568 > 2569 { 2570 typedef Vertex value_type; 2571 typedef Vertex key_type; 2572 typedef Vertex reference; 2573 typedef boost::readable_property_map_tag category; vec_adj_list_vertex_id_mapboost::vec_adj_list_vertex_id_map2574 inline vec_adj_list_vertex_id_map() { } 2575 template <class Graph> vec_adj_list_vertex_id_mapboost::vec_adj_list_vertex_id_map2576 inline vec_adj_list_vertex_id_map(const Graph&, vertex_index_t) { } operator []boost::vec_adj_list_vertex_id_map2577 inline value_type operator[](key_type v) const { return v; } operator ()boost::vec_adj_list_vertex_id_map2578 inline value_type operator()(key_type v) const { return v; } 2579 }; 2580 2581 struct vec_adj_list_any_vertex_pa { 2582 template <class Tag, class Graph, class Property> 2583 struct bind_ { 2584 typedef typename property_value<Property, Tag>::type value_type; 2585 typedef value_type& reference; 2586 typedef const value_type& const_reference; 2587 2588 typedef vec_adj_list_vertex_property_map 2589 <Graph, Graph*, value_type, reference, Tag> type; 2590 typedef vec_adj_list_vertex_property_map 2591 <Graph, const Graph*, value_type, const_reference, Tag> const_type; 2592 }; 2593 }; 2594 struct vec_adj_list_id_vertex_pa { 2595 template <class Tag, class Graph, class Property> 2596 struct bind_ { 2597 typedef typename Graph::vertex_descriptor Vertex; 2598 typedef vec_adj_list_vertex_id_map<Property, Vertex> type; 2599 typedef vec_adj_list_vertex_id_map<Property, Vertex> const_type; 2600 }; 2601 }; 2602 struct vec_adj_list_all_vertex_pa { 2603 template <class Tag, class Graph, class Property> 2604 struct bind_ { 2605 typedef typename Graph::vertex_descriptor Vertex; 2606 typedef vec_adj_list_vertex_all_properties_map 2607 <Graph, Graph*, Property, Property&> type; 2608 typedef vec_adj_list_vertex_all_properties_map 2609 <Graph, const Graph*, Property, const Property&> const_type; 2610 }; 2611 }; 2612 namespace detail { 2613 template <class Tag, class Graph, class Property> 2614 struct adj_list_choose_vertex_pa 2615 : boost::mpl::if_< 2616 boost::is_same<Tag, vertex_all_t>, 2617 adj_list_all_vertex_pa, 2618 adj_list_any_vertex_pa>::type 2619 ::template bind_<Tag, Graph, Property> 2620 {}; 2621 2622 2623 template <class Tag> 2624 struct vec_adj_list_choose_vertex_pa_helper { 2625 typedef vec_adj_list_any_vertex_pa type; 2626 }; 2627 template <> 2628 struct vec_adj_list_choose_vertex_pa_helper<vertex_index_t> { 2629 typedef vec_adj_list_id_vertex_pa type; 2630 }; 2631 template <> 2632 struct vec_adj_list_choose_vertex_pa_helper<vertex_all_t> { 2633 typedef vec_adj_list_all_vertex_pa type; 2634 }; 2635 template <class Tag, class Graph, class Property> 2636 struct vec_adj_list_choose_vertex_pa 2637 : vec_adj_list_choose_vertex_pa_helper<Tag>::type::template bind_<Tag,Graph,Property> 2638 {}; 2639 } // namespace detail 2640 2641 //========================================================================= 2642 // Edge Property Map 2643 2644 template <class Directed, class Value, class Ref, class Vertex, 2645 class Property, class Tag> 2646 struct adj_list_edge_property_map 2647 : public put_get_helper< 2648 Ref, 2649 adj_list_edge_property_map<Directed, Value, Ref, Vertex, Property, 2650 Tag> 2651 > 2652 { 2653 Tag tag; adj_list_edge_property_mapboost::adj_list_edge_property_map2654 explicit adj_list_edge_property_map(Tag tag = Tag()): tag(tag) {} 2655 2656 typedef Value value_type; 2657 typedef Ref reference; 2658 typedef detail::edge_desc_impl<Directed, Vertex> key_type; 2659 typedef boost::lvalue_property_map_tag category; operator []boost::adj_list_edge_property_map2660 inline Ref operator[](key_type e) const { 2661 Property& p = *(Property*)e.get_property(); 2662 return get_property_value(p, tag); 2663 } operator ()boost::adj_list_edge_property_map2664 inline Ref operator()(key_type e) const { 2665 return this->operator[](e); 2666 } 2667 }; 2668 2669 template <class Directed, class Property, class PropRef, class PropPtr, 2670 class Vertex> 2671 struct adj_list_edge_all_properties_map 2672 : public put_get_helper<PropRef, 2673 adj_list_edge_all_properties_map<Directed, Property, PropRef, 2674 PropPtr, Vertex> 2675 > 2676 { adj_list_edge_all_properties_mapboost::adj_list_edge_all_properties_map2677 explicit adj_list_edge_all_properties_map(edge_all_t = edge_all_t()) {} 2678 typedef Property value_type; 2679 typedef PropRef reference; 2680 typedef detail::edge_desc_impl<Directed, Vertex> key_type; 2681 typedef boost::lvalue_property_map_tag category; operator []boost::adj_list_edge_all_properties_map2682 inline PropRef operator[](key_type e) const { 2683 return *(PropPtr)e.get_property(); 2684 } operator ()boost::adj_list_edge_all_properties_map2685 inline PropRef operator()(key_type e) const { 2686 return this->operator[](e); 2687 } 2688 }; 2689 2690 // Edge Property Maps 2691 2692 namespace detail { 2693 struct adj_list_any_edge_pmap { 2694 template <class Graph, class Property, class Tag> 2695 struct bind_ { 2696 typedef typename property_value<Property,Tag>::type value_type; 2697 typedef value_type& reference; 2698 typedef const value_type& const_reference; 2699 2700 typedef adj_list_edge_property_map 2701 <typename Graph::directed_category, value_type, reference, 2702 typename Graph::vertex_descriptor,Property,Tag> type; 2703 typedef adj_list_edge_property_map 2704 <typename Graph::directed_category, value_type, const_reference, 2705 typename Graph::vertex_descriptor,const Property, Tag> const_type; 2706 }; 2707 }; 2708 struct adj_list_all_edge_pmap { 2709 template <class Graph, class Property, class Tag> 2710 struct bind_ { 2711 typedef adj_list_edge_all_properties_map 2712 <typename Graph::directed_category, Property, Property&, Property*, 2713 typename Graph::vertex_descriptor> type; 2714 typedef adj_list_edge_all_properties_map 2715 <typename Graph::directed_category, Property, const Property&, 2716 const Property*, typename Graph::vertex_descriptor> const_type; 2717 }; 2718 }; 2719 2720 template <class Tag> 2721 struct adj_list_choose_edge_pmap_helper { 2722 typedef adj_list_any_edge_pmap type; 2723 }; 2724 template <> 2725 struct adj_list_choose_edge_pmap_helper<edge_all_t> { 2726 typedef adj_list_all_edge_pmap type; 2727 }; 2728 template <class Tag, class Graph, class Property> 2729 struct adj_list_choose_edge_pmap 2730 : adj_list_choose_edge_pmap_helper<Tag>::type::template bind_<Graph, Property, Tag> 2731 {}; 2732 struct adj_list_edge_property_selector { 2733 template <class Graph, class Property, class Tag> 2734 struct bind_: adj_list_choose_edge_pmap<Tag, Graph, Property> {}; 2735 }; 2736 } // namespace detail 2737 2738 template <> 2739 struct edge_property_selector<adj_list_tag> { 2740 typedef detail::adj_list_edge_property_selector type; 2741 }; 2742 template <> 2743 struct edge_property_selector<vec_adj_list_tag> { 2744 typedef detail::adj_list_edge_property_selector type; 2745 }; 2746 2747 // Vertex Property Maps 2748 2749 struct adj_list_vertex_property_selector { 2750 template <class Graph, class Property, class Tag> 2751 struct bind_ 2752 : detail::adj_list_choose_vertex_pa<Tag,Graph,Property> 2753 {}; 2754 }; 2755 template <> 2756 struct vertex_property_selector<adj_list_tag> { 2757 typedef adj_list_vertex_property_selector type; 2758 }; 2759 2760 struct vec_adj_list_vertex_property_selector { 2761 template <class Graph, class Property, class Tag> 2762 struct bind_: detail::vec_adj_list_choose_vertex_pa<Tag,Graph,Property> {}; 2763 }; 2764 template <> 2765 struct vertex_property_selector<vec_adj_list_tag> { 2766 typedef vec_adj_list_vertex_property_selector type; 2767 }; 2768 2769 } // namespace boost 2770 2771 namespace boost { 2772 2773 template <typename V> 2774 struct hash< boost::detail::stored_edge<V> > 2775 { 2776 std::size_t operator ()boost::hash2777 operator()(const boost::detail::stored_edge<V>& e) const 2778 { 2779 return hash<V>()(e.m_target); 2780 } 2781 }; 2782 2783 template <typename V, typename P> 2784 struct hash< boost::detail::stored_edge_property <V,P> > 2785 { 2786 std::size_t operator ()boost::hash2787 operator()(const boost::detail::stored_edge_property<V,P>& e) const 2788 { 2789 return hash<V>()(e.m_target); 2790 } 2791 }; 2792 2793 template <typename V, typename I, typename P> 2794 struct hash< boost::detail::stored_edge_iter<V,I, P> > 2795 { 2796 std::size_t operator ()boost::hash2797 operator()(const boost::detail::stored_edge_iter<V,I,P>& e) const 2798 { 2799 return hash<V>()(e.m_target); 2800 } 2801 }; 2802 2803 } 2804 2805 2806 #endif // BOOST_GRAPH_DETAIL_DETAIL_ADJACENCY_LIST_CCT 2807 2808 /* 2809 Implementation Notes: 2810 2811 Many of the public interface functions in this file would have been 2812 more conveniently implemented as inline friend functions. 2813 However there are a few compiler bugs that make that approach 2814 non-portable. 2815 2816 1. g++ inline friend in namespace bug 2817 2. g++ using clause doesn't work with inline friends 2818 3. VC++ doesn't have Koenig lookup 2819 2820 For these reasons, the functions were all written as non-inline free 2821 functions, and static cast was used to convert from the helper 2822 class to the adjacency_list derived class. 2823 2824 Looking back, it might have been better to write out all functions 2825 in terms of the adjacency_list, and then use a tag to dispatch 2826 to the various helpers instead of using inheritance. 2827 2828 */ 2829