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