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