ceph/src/boost/libs/graph/include/boost/graph/detail/adjacency_list.hpp

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