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