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