Chris@16: // -*- c++ -*-
Chris@16: //=======================================================================
Chris@16: // Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
Chris@16: // Copyright 2010 Thomas Claveirole
Chris@16: // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek, Thomas Claveirole
Chris@16: //
Chris@16: // Distributed under the Boost Software License, Version 1.0. (See
Chris@16: // accompanying file LICENSE_1_0.txt or copy at
Chris@16: // http://www.boost.org/LICENSE_1_0.txt)
Chris@16: //=======================================================================
Chris@16: 
Chris@16: #ifndef BOOST_GRAPH_DETAIL_ADJACENCY_LIST_HPP
Chris@16: #define BOOST_GRAPH_DETAIL_ADJACENCY_LIST_HPP
Chris@16: 
Chris@16: #include <map> // for vertex_map in copy_impl
Chris@16: #include <boost/config.hpp>
Chris@16: #include <boost/detail/workaround.hpp>
Chris@16: #include <boost/operators.hpp>
Chris@16: #include <boost/property_map/property_map.hpp>
Chris@16: #include <boost/pending/container_traits.hpp>
Chris@16: #include <boost/range/irange.hpp>
Chris@16: #include <boost/graph/graph_traits.hpp>
Chris@16: #include <memory>
Chris@16: #include <algorithm>
Chris@16: #include <boost/limits.hpp>
Chris@16: 
Chris@16: #include <boost/iterator/iterator_adaptor.hpp>
Chris@16: 
Chris@16: #include <boost/mpl/if.hpp>
Chris@16: #include <boost/mpl/not.hpp>
Chris@16: #include <boost/mpl/and.hpp>
Chris@16: #include <boost/graph/graph_concepts.hpp>
Chris@16: #include <boost/pending/container_traits.hpp>
Chris@16: #include <boost/graph/detail/adj_list_edge_iterator.hpp>
Chris@16: #include <boost/graph/properties.hpp>
Chris@16: #include <boost/pending/property.hpp>
Chris@16: #include <boost/graph/adjacency_iterator.hpp>
Chris@16: #include <boost/static_assert.hpp>
Chris@16: #include <boost/assert.hpp>
Chris@16: 
Chris@101: #ifdef BOOST_NO_CXX11_RVALUE_REFERENCES
Chris@101: #define BOOST_GRAPH_MOVE_IF_POSSIBLE(x) (x)
Chris@101: #else
Chris@101: #include <utility>
Chris@101: #define BOOST_GRAPH_MOVE_IF_POSSIBLE(x) (std::move((x)))
Chris@101: #endif
Chris@101: 
Chris@16: /*
Chris@16:   Outline for this file:
Chris@16: 
Chris@16:   out_edge_iterator and in_edge_iterator implementation
Chris@16:   edge_iterator for undirected graph
Chris@16:   stored edge types (these object live in the out-edge/in-edge lists)
Chris@16:   directed edges helper class
Chris@16:   directed graph helper class
Chris@16:   undirected graph helper class
Chris@16:   bidirectional graph helper class
Chris@16:   bidirectional graph helper class (without edge properties)
Chris@16:   bidirectional graph helper class (with edge properties)
Chris@16:   adjacency_list helper class
Chris@16:   adj_list_impl class
Chris@16:   vec_adj_list_impl class
Chris@16:   adj_list_gen class
Chris@16:   vertex property map
Chris@16:   edge property map
Chris@16: 
Chris@16: 
Chris@16:   Note: it would be nice to merge some of the undirected and
Chris@16:   bidirectional code... it is awful similar.
Chris@16:  */
Chris@16: 
Chris@16: 
Chris@16: namespace boost {
Chris@16: 
Chris@16:   namespace detail {
Chris@16: 
Chris@16:     template <typename DirectedS>
Chris@16:     struct directed_category_traits {
Chris@16:       typedef directed_tag directed_category;
Chris@16:     };
Chris@16: 
Chris@16:     template <>
Chris@16:     struct directed_category_traits<directedS> {
Chris@16:       typedef directed_tag directed_category;
Chris@16:     };
Chris@16:     template <>
Chris@16:     struct directed_category_traits<undirectedS> {
Chris@16:       typedef undirected_tag directed_category;
Chris@16:     };
Chris@16:     template <>
Chris@16:     struct directed_category_traits<bidirectionalS> {
Chris@16:       typedef bidirectional_tag directed_category;
Chris@16:     };
Chris@16: 
Chris@16:     template <class Vertex>
Chris@16:     struct target_is {
Chris@16:       target_is(const Vertex& v) : m_target(v) { }
Chris@16:       template <class StoredEdge>
Chris@16:       bool operator()(const StoredEdge& e) const {
Chris@16:         return e.get_target() == m_target;
Chris@16:       }
Chris@16:       Vertex m_target;
Chris@16:     };
Chris@16: 
Chris@16:     // O(E/V)
Chris@16:     template <class EdgeList, class vertex_descriptor>
Chris@16:     void erase_from_incidence_list(EdgeList& el, vertex_descriptor v,
Chris@16:                                    allow_parallel_edge_tag)
Chris@16:     {
Chris@16:       boost::graph_detail::erase_if(el, detail::target_is<vertex_descriptor>(v));
Chris@16:     }
Chris@16:     // O(log(E/V))
Chris@16:     template <class EdgeList, class vertex_descriptor>
Chris@16:     void erase_from_incidence_list(EdgeList& el, vertex_descriptor v,
Chris@16:                                    disallow_parallel_edge_tag)
Chris@16:     {
Chris@16:       typedef typename EdgeList::value_type StoredEdge;
Chris@16:       el.erase(StoredEdge(v));
Chris@16:     }
Chris@16: 
Chris@16:     //=========================================================================
Chris@16:     // Out-Edge and In-Edge Iterator Implementation
Chris@16: 
Chris@16:     template <class BaseIter, class VertexDescriptor, class EdgeDescriptor, class Difference>
Chris@16:     struct out_edge_iter
Chris@16:       : iterator_adaptor<
Chris@16:             out_edge_iter<BaseIter, VertexDescriptor, EdgeDescriptor, Difference>
Chris@16:           , BaseIter
Chris@16:           , EdgeDescriptor
Chris@16:           , use_default
Chris@16:           , EdgeDescriptor
Chris@16:           , Difference
Chris@16:         >
Chris@16:     {
Chris@16:       typedef iterator_adaptor<
Chris@16:           out_edge_iter<BaseIter, VertexDescriptor, EdgeDescriptor, Difference>
Chris@16:         , BaseIter
Chris@16:         , EdgeDescriptor
Chris@16:         , use_default
Chris@16:         , EdgeDescriptor
Chris@16:         , Difference
Chris@16:       > super_t;
Chris@16: 
Chris@16:       inline out_edge_iter() { }
Chris@16:         inline out_edge_iter(const BaseIter& i, const VertexDescriptor& src)
Chris@16:           : super_t(i), m_src(src) { }
Chris@16: 
Chris@16:       inline EdgeDescriptor
Chris@16:       dereference() const
Chris@16:       {
Chris@16:         return EdgeDescriptor(m_src, (*this->base()).get_target(),
Chris@16:                               &(*this->base()).get_property());
Chris@16:       }
Chris@16:       VertexDescriptor m_src;
Chris@16:     };
Chris@16: 
Chris@16:     template <class BaseIter, class VertexDescriptor, class EdgeDescriptor, class Difference>
Chris@16:     struct in_edge_iter
Chris@16:       : iterator_adaptor<
Chris@16:             in_edge_iter<BaseIter, VertexDescriptor, EdgeDescriptor, Difference>
Chris@16:           , BaseIter
Chris@16:           , EdgeDescriptor
Chris@16:           , use_default
Chris@16:           , EdgeDescriptor
Chris@16:           , Difference
Chris@16:         >
Chris@16:     {
Chris@16:       typedef iterator_adaptor<
Chris@16:           in_edge_iter<BaseIter, VertexDescriptor, EdgeDescriptor, Difference>
Chris@16:         , BaseIter
Chris@16:         , EdgeDescriptor
Chris@16:         , use_default
Chris@16:         , EdgeDescriptor
Chris@16:         , Difference
Chris@16:       > super_t;
Chris@16: 
Chris@16:       inline in_edge_iter() { }
Chris@16:       inline in_edge_iter(const BaseIter& i, const VertexDescriptor& src)
Chris@16:         : super_t(i), m_src(src) { }
Chris@16: 
Chris@16:       inline EdgeDescriptor
Chris@16:       dereference() const
Chris@16:       {
Chris@16:         return EdgeDescriptor((*this->base()).get_target(), m_src,
Chris@16:                               &this->base()->get_property());
Chris@16:       }
Chris@16:       VertexDescriptor m_src;
Chris@16:     };
Chris@16: 
Chris@16:     //=========================================================================
Chris@16:     // Undirected Edge Iterator Implementation
Chris@16: 
Chris@16:     template <class EdgeIter, class EdgeDescriptor, class Difference>
Chris@16:     struct undirected_edge_iter
Chris@16:       : iterator_adaptor<
Chris@16:             undirected_edge_iter<EdgeIter, EdgeDescriptor, Difference>
Chris@16:           , EdgeIter
Chris@16:           , EdgeDescriptor
Chris@16:           , use_default
Chris@16:           , EdgeDescriptor
Chris@16:           , Difference
Chris@16:         >
Chris@16:     {
Chris@16:       typedef iterator_adaptor<
Chris@16:           undirected_edge_iter<EdgeIter, EdgeDescriptor, Difference>
Chris@16:         , EdgeIter
Chris@16:         , EdgeDescriptor
Chris@16:         , use_default
Chris@16:         , EdgeDescriptor
Chris@16:         , Difference
Chris@16:       > super_t;
Chris@16: 
Chris@16:       undirected_edge_iter() {}
Chris@16: 
Chris@16:       explicit undirected_edge_iter(EdgeIter i)
Chris@16:           : super_t(i) {}
Chris@16: 
Chris@16:       inline EdgeDescriptor
Chris@16:       dereference() const {
Chris@16:         return EdgeDescriptor(
Chris@16:             (*this->base()).m_source
Chris@16:           , (*this->base()).m_target
Chris@16:           , &this->base()->get_property());
Chris@16:       }
Chris@16:     };
Chris@16: 
Chris@16:     //=========================================================================
Chris@16:     // Edge Storage Types (stored in the out-edge/in-edge lists)
Chris@16: 
Chris@16:     template <class Vertex>
Chris@16:     class stored_edge
Chris@16:       : public boost::equality_comparable1< stored_edge<Vertex>,
Chris@16:         boost::less_than_comparable1< stored_edge<Vertex> > >
Chris@16:     {
Chris@16:     public:
Chris@16:       typedef no_property property_type;
Chris@16:       inline stored_edge() { }
Chris@16:       inline stored_edge(Vertex target, const no_property& = no_property())
Chris@16:         : m_target(target) { }
Chris@16:       // Need to write this explicitly so stored_edge_property can
Chris@16:       // invoke Base::operator= (at least, for SGI MIPSPro compiler)
Chris@16:       inline stored_edge& operator=(const stored_edge& x) {
Chris@16:         m_target = x.m_target;
Chris@16:         return *this;
Chris@16:       }
Chris@16:       inline Vertex& get_target() const { return m_target; }
Chris@16:       inline const no_property& get_property() const { return s_prop; }
Chris@16:       inline bool operator==(const stored_edge& x) const
Chris@16:         { return m_target == x.get_target(); }
Chris@16:       inline bool operator<(const stored_edge& x) const
Chris@16:         { return m_target < x.get_target(); }
Chris@16:       //protected: need to add hash<> as a friend
Chris@16:       static no_property s_prop;
Chris@16:       // Sometimes target not used as key in the set, and in that case
Chris@16:       // it is ok to change the target.
Chris@16:       mutable Vertex m_target;
Chris@16:     };
Chris@16:     template <class Vertex>
Chris@16:     no_property stored_edge<Vertex>::s_prop;
Chris@16: 
Chris@101: #if defined(BOOST_NO_CXX11_RVALUE_REFERENCES) || defined(BOOST_NO_CXX11_DEFAULTED_FUNCTIONS)
Chris@16:     template <class Vertex, class Property>
Chris@16:     class stored_edge_property : public stored_edge<Vertex> {
Chris@16:       typedef stored_edge_property self;
Chris@16:       typedef stored_edge<Vertex> Base;
Chris@16:     public:
Chris@16:       typedef Property property_type;
Chris@16:       inline stored_edge_property() { }
Chris@16:       inline stored_edge_property(Vertex target,
Chris@16:                                   const Property& p = Property())
Chris@16:         : stored_edge<Vertex>(target), m_property(new Property(p)) { }
Chris@16:       stored_edge_property(const self& x)
Chris@16:         : Base(x), m_property(const_cast<self&>(x).m_property) { }
Chris@16:       self& operator=(const self& x) {
Chris@16:         Base::operator=(x);
Chris@16:         m_property = const_cast<self&>(x).m_property;
Chris@16:         return *this;
Chris@16:       }
Chris@16:       inline Property& get_property() { return *m_property; }
Chris@16:       inline const Property& get_property() const { return *m_property; }
Chris@16:     protected:
Chris@16:       // Holding the property by-value causes edge-descriptor
Chris@16:       // invalidation for add_edge() with EdgeList=vecS. Instead we
Chris@16:       // hold a pointer to the property. std::auto_ptr is not
Chris@16:       // a perfect fit for the job, but it is darn close.
Chris@16:       std::auto_ptr<Property> m_property;
Chris@16:     };
Chris@101: #else
Chris@101:     template <class Vertex, class Property>
Chris@101:     class stored_edge_property : public stored_edge<Vertex> {
Chris@101:       typedef stored_edge_property self;
Chris@101:       typedef stored_edge<Vertex> Base;
Chris@101:     public:
Chris@101:       typedef Property property_type;
Chris@101:       inline stored_edge_property() { }
Chris@101:       inline stored_edge_property(Vertex target,
Chris@101:                                   const Property& p = Property())
Chris@101:         : stored_edge<Vertex>(target), m_property(new Property(p)) { }
Chris@101: #if defined(BOOST_MSVC) || (defined(BOOST_GCC) && (BOOST_GCC / 100) < 406)
Chris@101:       stored_edge_property(self&& x) : Base(static_cast< Base const& >(x)) {
Chris@101:         m_property.swap(x.m_property);
Chris@101:       }
Chris@101:       stored_edge_property(self const& x) : Base(static_cast< Base const& >(x)) {
Chris@101:         m_property.swap(const_cast<self&>(x).m_property);
Chris@101:       }
Chris@101:       self& operator=(self&& x) {
Chris@101:         Base::operator=(static_cast< Base const& >(x));
Chris@101:         m_property = std::move(x.m_property);
Chris@101:         return *this;
Chris@101:       }
Chris@101:       self& operator=(self const& x) {
Chris@101:         Base::operator=(static_cast< Base const& >(x));
Chris@101:         m_property = std::move(const_cast<self&>(x).m_property);
Chris@101:         return *this;
Chris@101:       }
Chris@101: #else
Chris@101:       stored_edge_property(self&& x) = default;
Chris@101:       self& operator=(self&& x) = default;
Chris@101: #endif
Chris@101:       inline Property& get_property() { return *m_property; }
Chris@101:       inline const Property& get_property() const { return *m_property; }
Chris@101:     protected:
Chris@101:       std::unique_ptr<Property> m_property;
Chris@101:     };
Chris@101: #endif
Chris@16: 
Chris@16: 
Chris@16:     template <class Vertex, class Iter, class Property>
Chris@16:     class stored_edge_iter
Chris@16:       : public stored_edge<Vertex>
Chris@16:     {
Chris@16:     public:
Chris@16:       typedef Property property_type;
Chris@16:       inline stored_edge_iter() { }
Chris@16:       inline stored_edge_iter(Vertex v)
Chris@16:         : stored_edge<Vertex>(v) { }
Chris@16:       inline stored_edge_iter(Vertex v, Iter i, void* = 0)
Chris@16:         : stored_edge<Vertex>(v), m_iter(i) { }
Chris@16:       inline Property& get_property() { return m_iter->get_property(); }
Chris@16:       inline const Property& get_property() const {
Chris@16:         return m_iter->get_property();
Chris@16:       }
Chris@16:       inline Iter get_iter() const { return m_iter; }
Chris@16:     protected:
Chris@16:       Iter m_iter;
Chris@16:     };
Chris@16: 
Chris@16:     // For when the EdgeList is a std::vector.
Chris@16:     // Want to make the iterator stable, so use an offset
Chris@16:     // instead of an iterator into a std::vector
Chris@16:     template <class Vertex, class EdgeVec, class Property>
Chris@16:     class stored_ra_edge_iter
Chris@16:       : public stored_edge<Vertex>
Chris@16:     {
Chris@16:       typedef typename EdgeVec::iterator Iter;
Chris@16:     public:
Chris@16:       typedef Property property_type;
Chris@16:       inline stored_ra_edge_iter() { }
Chris@16:       inline explicit stored_ra_edge_iter(Vertex v) // Only used for comparisons
Chris@16:         : stored_edge<Vertex>(v), m_i(0), m_vec(0){ }
Chris@16:       inline stored_ra_edge_iter(Vertex v, Iter i, EdgeVec* edge_vec)
Chris@16:         : stored_edge<Vertex>(v), m_i(i - edge_vec->begin()), m_vec(edge_vec){ }
Chris@16:       inline Property& get_property() { BOOST_ASSERT ((m_vec != 0)); return (*m_vec)[m_i].get_property(); }
Chris@16:       inline const Property& get_property() const {
Chris@16:         BOOST_ASSERT ((m_vec != 0));
Chris@16:         return (*m_vec)[m_i].get_property();
Chris@16:       }
Chris@16:       inline Iter get_iter() const { BOOST_ASSERT ((m_vec != 0)); return m_vec->begin() + m_i; }
Chris@16:     protected:
Chris@16:       std::size_t m_i;
Chris@16:       EdgeVec* m_vec;
Chris@16:     };
Chris@16: 
Chris@16:   } // namespace detail
Chris@16: 
Chris@16:   template <class Tag, class Vertex, class Property>
Chris@16:   const typename property_value<Property,Tag>::type&
Chris@16:   get(Tag property_tag,
Chris@16:       const detail::stored_edge_property<Vertex, Property>& e)
Chris@16:   {
Chris@16:     return get_property_value(e.get_property(), property_tag);
Chris@16:   }
Chris@16: 
Chris@16:   template <class Tag, class Vertex, class Iter, class Property>
Chris@16:   const typename property_value<Property,Tag>::type&
Chris@16:   get(Tag property_tag,
Chris@16:       const detail::stored_edge_iter<Vertex, Iter, Property>& e)
Chris@16:   {
Chris@16:     return get_property_value(e.get_property(), property_tag);
Chris@16:   }
Chris@16: 
Chris@16:   template <class Tag, class Vertex, class EdgeVec, class Property>
Chris@16:   const typename property_value<Property,Tag>::type&
Chris@16:   get(Tag property_tag,
Chris@16:       const detail::stored_ra_edge_iter<Vertex, EdgeVec, Property>& e)
Chris@16:   {
Chris@16:     return get_property_value(e.get_property(), property_tag);
Chris@16:   }
Chris@16: 
Chris@16:     //=========================================================================
Chris@16:     // Directed Edges Helper Class
Chris@16: 
Chris@16:     namespace detail {
Chris@16: 
Chris@16:       // O(E/V)
Chris@16:       template <class edge_descriptor, class EdgeList, class StoredProperty>
Chris@16:       inline void
Chris@16:       remove_directed_edge_dispatch(edge_descriptor, EdgeList& el,
Chris@16:                                     StoredProperty& p)
Chris@16:       {
Chris@16:         for (typename EdgeList::iterator i = el.begin();
Chris@16:              i != el.end(); ++i)
Chris@16:           if (&(*i).get_property() == &p) {
Chris@16:             el.erase(i);
Chris@16:             return;
Chris@16:           }
Chris@16:       }
Chris@16: 
Chris@16:       template <class incidence_iterator, class EdgeList, class Predicate>
Chris@16:       inline void
Chris@16:       remove_directed_edge_if_dispatch(incidence_iterator first,
Chris@16:                                        incidence_iterator last,
Chris@16:                                        EdgeList& el, Predicate pred,
Chris@16:                                        boost::allow_parallel_edge_tag)
Chris@16:       {
Chris@16:         // remove_if
Chris@16:         while (first != last && !pred(*first))
Chris@16:           ++first;
Chris@16:         incidence_iterator i = first;
Chris@16:         if (first != last)
Chris@16:           for (++i; i != last; ++i)
Chris@16:             if (!pred(*i)) {
Chris@101:               *first.base() = BOOST_GRAPH_MOVE_IF_POSSIBLE(*i.base());
Chris@16:               ++first;
Chris@16:             }
Chris@16:         el.erase(first.base(), el.end());
Chris@16:       }
Chris@16:       template <class incidence_iterator, class EdgeList, class Predicate>
Chris@16:       inline void
Chris@16:       remove_directed_edge_if_dispatch(incidence_iterator first,
Chris@16:                                        incidence_iterator last,
Chris@16:                                        EdgeList& el,
Chris@16:                                        Predicate pred,
Chris@16:                                        boost::disallow_parallel_edge_tag)
Chris@16:       {
Chris@16:         for (incidence_iterator next = first;
Chris@16:              first != last; first = next) {
Chris@16:           ++next;
Chris@16:           if (pred(*first))
Chris@16:             el.erase( first.base() );
Chris@16:         }
Chris@16:       }
Chris@16: 
Chris@16:       template <class PropT, class Graph, class incidence_iterator,
Chris@16:                 class EdgeList, class Predicate>
Chris@16:       inline void
Chris@16:       undirected_remove_out_edge_if_dispatch(Graph& g,
Chris@16:                                              incidence_iterator first,
Chris@16:                                              incidence_iterator last,
Chris@16:                                              EdgeList& el, Predicate pred,
Chris@16:                                              boost::allow_parallel_edge_tag)
Chris@16:       {
Chris@16:         typedef typename Graph::global_edgelist_selector EdgeListS;
Chris@16:         BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
Chris@16: 
Chris@16:         // remove_if
Chris@16:         while (first != last && !pred(*first))
Chris@16:           ++first;
Chris@16:         incidence_iterator i = first;
Chris@16:         bool self_loop_removed = false;
Chris@16:         if (first != last)
Chris@16:           for (; i != last; ++i) {
Chris@16:             if (self_loop_removed) {
Chris@16:               /* With self loops, the descriptor will show up
Chris@16:                * twice. The first time it will be removed, and now it
Chris@16:                * will be skipped.
Chris@16:                */
Chris@16:               self_loop_removed = false;
Chris@16:             }
Chris@16:             else if (!pred(*i)) {
Chris@101:               *first.base() = BOOST_GRAPH_MOVE_IF_POSSIBLE(*i.base());
Chris@16:               ++first;
Chris@16:             } else {
Chris@16:               if (source(*i, g) == target(*i, g)) self_loop_removed = true;
Chris@16:               else {
Chris@16:                 // Remove the edge from the target
Chris@16:                 detail::remove_directed_edge_dispatch
Chris@16:                   (*i,
Chris@16:                    g.out_edge_list(target(*i, g)),
Chris@16:                    *(PropT*)(*i).get_property());
Chris@16:               }
Chris@16: 
Chris@16:               // Erase the edge property
Chris@16:               g.m_edges.erase( (*i.base()).get_iter() );
Chris@16:             }
Chris@16:           }
Chris@16:         el.erase(first.base(), el.end());
Chris@16:       }
Chris@16:       template <class PropT, class Graph, class incidence_iterator,
Chris@16:                 class EdgeList, class Predicate>
Chris@16:       inline void
Chris@16:       undirected_remove_out_edge_if_dispatch(Graph& g,
Chris@16:                                              incidence_iterator first,
Chris@16:                                              incidence_iterator last,
Chris@16:                                              EdgeList& el,
Chris@16:                                              Predicate pred,
Chris@16:                                              boost::disallow_parallel_edge_tag)
Chris@16:       {
Chris@16:         typedef typename Graph::global_edgelist_selector EdgeListS;
Chris@16:         BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
Chris@16: 
Chris@16:         for (incidence_iterator next = first;
Chris@16:              first != last; first = next) {
Chris@16:           ++next;
Chris@16:           if (pred(*first)) {
Chris@16:             if (source(*first, g) != target(*first, g)) {
Chris@16:               // Remove the edge from the target
Chris@16:               detail::remove_directed_edge_dispatch
Chris@16:                 (*first,
Chris@16:                  g.out_edge_list(target(*first, g)),
Chris@16:                  *(PropT*)(*first).get_property());
Chris@16:             }
Chris@16: 
Chris@16:             // Erase the edge property
Chris@16:             g.m_edges.erase( (*first.base()).get_iter() );
Chris@16: 
Chris@16:             // Erase the edge in the source
Chris@16:             el.erase( first.base() );
Chris@16:           }
Chris@16:         }
Chris@16:       }
Chris@16: 
Chris@16:       // O(E/V)
Chris@16:       template <class edge_descriptor, class EdgeList, class StoredProperty>
Chris@16:       inline void
Chris@16:       remove_directed_edge_dispatch(edge_descriptor e, EdgeList& el,
Chris@16:                                     no_property&)
Chris@16:       {
Chris@16:         for (typename EdgeList::iterator i = el.begin();
Chris@16:              i != el.end(); ++i)
Chris@16:           if ((*i).get_target() == e.m_target) {
Chris@16:             el.erase(i);
Chris@16:             return;
Chris@16:           }
Chris@16:       }
Chris@16: 
Chris@16:     } // namespace detail
Chris@16: 
Chris@16:     template <class Config>
Chris@16:     struct directed_edges_helper {
Chris@16: 
Chris@16:       // Placement of these overloaded remove_edge() functions
Chris@16:       // inside the class avoids a VC++ bug.
Chris@16: 
Chris@16:       // O(E/V)
Chris@16:       inline void
Chris@16:       remove_edge(typename Config::edge_descriptor e)
Chris@16:       {
Chris@16:         typedef typename Config::graph_type graph_type;
Chris@16:         graph_type& g = static_cast<graph_type&>(*this);
Chris@16:         typename Config::OutEdgeList& el = g.out_edge_list(source(e, g));
Chris@16:         typedef typename Config::OutEdgeList::value_type::property_type PType;
Chris@16:         detail::remove_directed_edge_dispatch(e, el,
Chris@16:                                               *(PType*)e.get_property());
Chris@16:       }
Chris@16: 
Chris@16:       // O(1)
Chris@16:       inline void
Chris@16:       remove_edge(typename Config::out_edge_iterator iter)
Chris@16:       {
Chris@16:         typedef typename Config::graph_type graph_type;
Chris@16:         graph_type& g = static_cast<graph_type&>(*this);
Chris@16:         typename Config::edge_descriptor e = *iter;
Chris@16:         typename Config::OutEdgeList& el = g.out_edge_list(source(e, g));
Chris@16:         el.erase(iter.base());
Chris@16:       }
Chris@16: 
Chris@16:     };
Chris@16: 
Chris@16:     // O(1)
Chris@16:     template <class Config>
Chris@16:     inline std::pair<typename Config::edge_iterator,
Chris@16:                      typename Config::edge_iterator>
Chris@16:     edges(const directed_edges_helper<Config>& g_)
Chris@16:     {
Chris@16:       typedef typename Config::graph_type graph_type;
Chris@16:       typedef typename Config::edge_iterator edge_iterator;
Chris@16:       const graph_type& cg = static_cast<const graph_type&>(g_);
Chris@16:       graph_type& g = const_cast<graph_type&>(cg);
Chris@16:       return std::make_pair( edge_iterator(g.vertex_set().begin(),
Chris@16:                                            g.vertex_set().begin(),
Chris@16:                                            g.vertex_set().end(), g),
Chris@16:                              edge_iterator(g.vertex_set().begin(),
Chris@16:                                            g.vertex_set().end(),
Chris@16:                                            g.vertex_set().end(), g) );
Chris@16:     }
Chris@16: 
Chris@16:     //=========================================================================
Chris@16:     // Directed Graph Helper Class
Chris@16: 
Chris@16:     struct adj_list_dir_traversal_tag :
Chris@16:       public virtual vertex_list_graph_tag,
Chris@16:       public virtual incidence_graph_tag,
Chris@16:       public virtual adjacency_graph_tag,
Chris@16:       public virtual edge_list_graph_tag { };
Chris@16: 
Chris@16:     template <class Config>
Chris@16:     struct directed_graph_helper
Chris@16:       : public directed_edges_helper<Config> {
Chris@16:       typedef typename Config::edge_descriptor edge_descriptor;
Chris@16:       typedef adj_list_dir_traversal_tag traversal_category;
Chris@16:     };
Chris@16: 
Chris@16:     // O(E/V)
Chris@16:     template <class Config>
Chris@16:     inline void
Chris@16:     remove_edge(typename Config::vertex_descriptor u,
Chris@16:                 typename Config::vertex_descriptor v,
Chris@16:                 directed_graph_helper<Config>& g_)
Chris@16:     {
Chris@16:       typedef typename Config::graph_type graph_type;
Chris@16:       typedef typename Config::edge_parallel_category Cat;
Chris@16:       graph_type& g = static_cast<graph_type&>(g_);
Chris@16:       detail::erase_from_incidence_list(g.out_edge_list(u), v, Cat());
Chris@16:     }
Chris@16: 
Chris@16:     template <class Config, class Predicate>
Chris@16:     inline void
Chris@16:     remove_out_edge_if(typename Config::vertex_descriptor u, Predicate pred,
Chris@16:                        directed_graph_helper<Config>& g_)
Chris@16:     {
Chris@16:       typedef typename Config::graph_type graph_type;
Chris@16:       graph_type& g = static_cast<graph_type&>(g_);
Chris@16:       typename Config::out_edge_iterator first, last;
Chris@16:       boost::tie(first, last) = out_edges(u, g);
Chris@16:       typedef typename Config::edge_parallel_category edge_parallel_category;
Chris@16:       detail::remove_directed_edge_if_dispatch
Chris@16:         (first, last, g.out_edge_list(u), pred, edge_parallel_category());
Chris@16:     }
Chris@16: 
Chris@16:     template <class Config, class Predicate>
Chris@16:     inline void
Chris@16:     remove_edge_if(Predicate pred, directed_graph_helper<Config>& g_)
Chris@16:     {
Chris@16:       typedef typename Config::graph_type graph_type;
Chris@16:       graph_type& g = static_cast<graph_type&>(g_);
Chris@16: 
Chris@16:       typename Config::vertex_iterator vi, vi_end;
Chris@16:       for (boost::tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi)
Chris@16:         remove_out_edge_if(*vi, pred, g);
Chris@16:     }
Chris@16: 
Chris@16:     template <class EdgeOrIter, class Config>
Chris@16:     inline void
Chris@16:     remove_edge(EdgeOrIter e_or_iter, directed_graph_helper<Config>& g_)
Chris@16:     {
Chris@16:       g_.remove_edge(e_or_iter);
Chris@16:     }
Chris@16: 
Chris@16:     // O(V + E) for allow_parallel_edges
Chris@16:     // O(V * log(E/V)) for disallow_parallel_edges
Chris@16:     template <class Config>
Chris@16:     inline void
Chris@16:     clear_vertex(typename Config::vertex_descriptor u,
Chris@16:                  directed_graph_helper<Config>& g_)
Chris@16:     {
Chris@16:       typedef typename Config::graph_type graph_type;
Chris@16:       typedef typename Config::edge_parallel_category Cat;
Chris@16:       graph_type& g = static_cast<graph_type&>(g_);
Chris@16:       typename Config::vertex_iterator vi, viend;
Chris@16:       for (boost::tie(vi, viend) = vertices(g); vi != viend; ++vi)
Chris@16:         detail::erase_from_incidence_list(g.out_edge_list(*vi), u, Cat());
Chris@16:       g.out_edge_list(u).clear();
Chris@16:       // clear() should be a req of Sequence and AssociativeContainer,
Chris@16:       // or maybe just Container
Chris@16:     }
Chris@16: 
Chris@16:     template <class Config>
Chris@16:     inline void
Chris@16:     clear_out_edges(typename Config::vertex_descriptor u,
Chris@16:                     directed_graph_helper<Config>& g_)
Chris@16:     {
Chris@16:       typedef typename Config::graph_type graph_type;
Chris@16:       graph_type& g = static_cast<graph_type&>(g_);
Chris@16:       g.out_edge_list(u).clear();
Chris@16:       // clear() should be a req of Sequence and AssociativeContainer,
Chris@16:       // or maybe just Container
Chris@16:     }
Chris@16: 
Chris@16:     // O(V), could do better...
Chris@16:     template <class Config>
Chris@16:     inline typename Config::edges_size_type
Chris@16:     num_edges(const directed_graph_helper<Config>& g_)
Chris@16:     {
Chris@16:       typedef typename Config::graph_type graph_type;
Chris@16:       const graph_type& g = static_cast<const graph_type&>(g_);
Chris@16:       typename Config::edges_size_type num_e = 0;
Chris@16:       typename Config::vertex_iterator vi, vi_end;
Chris@16:       for (boost::tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi)
Chris@16:         num_e += out_degree(*vi, g);
Chris@16:       return num_e;
Chris@16:     }
Chris@16:     // O(1) for allow_parallel_edge_tag
Chris@16:     // O(log(E/V)) for disallow_parallel_edge_tag
Chris@16:     template <class Config>
Chris@16:     inline std::pair<typename directed_graph_helper<Config>::edge_descriptor, bool>
Chris@16:     add_edge(typename Config::vertex_descriptor u,
Chris@16:              typename Config::vertex_descriptor v,
Chris@16:              const typename Config::edge_property_type& p,
Chris@16:              directed_graph_helper<Config>& g_)
Chris@16:     {
Chris@16:       typedef typename Config::edge_descriptor edge_descriptor;
Chris@16:       typedef typename Config::graph_type graph_type;
Chris@16:       typedef typename Config::StoredEdge StoredEdge;
Chris@16:       graph_type& g = static_cast<graph_type&>(g_);
Chris@16:       typename Config::OutEdgeList::iterator i;
Chris@16:       bool inserted;
Chris@16:       boost::tie(i, inserted) = boost::graph_detail::push(g.out_edge_list(u),
Chris@16:                                             StoredEdge(v, p));
Chris@16:       return std::make_pair(edge_descriptor(u, v, &(*i).get_property()),
Chris@16:                             inserted);
Chris@16:     }
Chris@16:     // Did not use default argument here because that
Chris@16:     // causes Visual C++ to get confused.
Chris@16:     template <class Config>
Chris@16:     inline std::pair<typename Config::edge_descriptor, bool>
Chris@16:     add_edge(typename Config::vertex_descriptor u,
Chris@16:              typename Config::vertex_descriptor v,
Chris@16:              directed_graph_helper<Config>& g_)
Chris@16:     {
Chris@16:       typename Config::edge_property_type p;
Chris@16:       return add_edge(u, v, p, g_);
Chris@16:     }
Chris@16:     //=========================================================================
Chris@16:     // Undirected Graph Helper Class
Chris@16: 
Chris@16:     template <class Config>
Chris@16:     struct undirected_graph_helper;
Chris@16: 
Chris@16:     struct undir_adj_list_traversal_tag :
Chris@16:       public virtual vertex_list_graph_tag,
Chris@16:       public virtual incidence_graph_tag,
Chris@16:       public virtual adjacency_graph_tag,
Chris@16:       public virtual edge_list_graph_tag,
Chris@16:       public virtual bidirectional_graph_tag { };
Chris@16: 
Chris@16:     namespace detail {
Chris@16: 
Chris@16:       // using class with specialization for dispatch is a VC++ workaround.
Chris@16:       template <class StoredProperty>
Chris@16:       struct remove_undirected_edge_dispatch {
Chris@16: 
Chris@16:         // O(E/V)
Chris@16:         template <class edge_descriptor, class Config>
Chris@16:         static void
Chris@16:         apply(edge_descriptor e,
Chris@16:               undirected_graph_helper<Config>& g_,
Chris@16:               StoredProperty& p)
Chris@16:         {
Chris@16:           typedef typename Config::global_edgelist_selector EdgeListS;
Chris@16:           BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
Chris@16: 
Chris@16:           typedef typename Config::graph_type graph_type;
Chris@16:           graph_type& g = static_cast<graph_type&>(g_);
Chris@16: 
Chris@16:           typename Config::OutEdgeList& out_el = g.out_edge_list(source(e, g));
Chris@16:           typename Config::OutEdgeList::iterator out_i = out_el.begin();
Chris@16:           typename Config::EdgeIter edge_iter_to_erase;
Chris@16:           for (; out_i != out_el.end(); ++out_i)
Chris@16:             if (&(*out_i).get_property() == &p) {
Chris@16:               edge_iter_to_erase = (*out_i).get_iter();
Chris@16:               out_el.erase(out_i);
Chris@16:               break;
Chris@16:             }
Chris@16:           typename Config::OutEdgeList& in_el = g.out_edge_list(target(e, g));
Chris@16:           typename Config::OutEdgeList::iterator in_i = in_el.begin();
Chris@16:           for (; in_i != in_el.end(); ++in_i)
Chris@16:             if (&(*in_i).get_property() == &p) {
Chris@16:               in_el.erase(in_i);
Chris@16:               break;
Chris@16:             }
Chris@16:           g.m_edges.erase(edge_iter_to_erase);
Chris@16:         }
Chris@16:       };
Chris@16: 
Chris@16:       template <>
Chris@16:       struct remove_undirected_edge_dispatch<no_property> {
Chris@16:         // O(E/V)
Chris@16:         template <class edge_descriptor, class Config>
Chris@16:         static void
Chris@16:         apply(edge_descriptor e,
Chris@16:               undirected_graph_helper<Config>& g_,
Chris@16:               no_property&)
Chris@16:         {
Chris@16:           typedef typename Config::global_edgelist_selector EdgeListS;
Chris@16:           BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
Chris@16: 
Chris@16:           typedef typename Config::graph_type graph_type;
Chris@16:           graph_type& g = static_cast<graph_type&>(g_);
Chris@16:           no_property* p = (no_property*)e.get_property();
Chris@16:           typename Config::OutEdgeList& out_el = g.out_edge_list(source(e, g));
Chris@16:           typename Config::OutEdgeList::iterator out_i = out_el.begin();
Chris@16:           typename Config::EdgeIter edge_iter_to_erase;
Chris@16:           for (; out_i != out_el.end(); ++out_i)
Chris@16:             if (&(*out_i).get_property() == p) {
Chris@16:               edge_iter_to_erase = (*out_i).get_iter();
Chris@16:               out_el.erase(out_i);
Chris@16:               break;
Chris@16:             }
Chris@16:           typename Config::OutEdgeList& in_el = g.out_edge_list(target(e, g));
Chris@16:           typename Config::OutEdgeList::iterator in_i = in_el.begin();
Chris@16:           for (; in_i != in_el.end(); ++in_i)
Chris@16:             if (&(*in_i).get_property() == p) {
Chris@16:               in_el.erase(in_i);
Chris@16:               break;
Chris@16:             }
Chris@16:           g.m_edges.erase(edge_iter_to_erase);
Chris@16:         }
Chris@16:       };
Chris@16: 
Chris@16:       // O(E/V)
Chris@16:       template <class Graph, class EdgeList, class Vertex>
Chris@16:       inline void
Chris@16:       remove_edge_and_property(Graph& g, EdgeList& el, Vertex v,
Chris@16:                                boost::allow_parallel_edge_tag cat)
Chris@16:       {
Chris@16:         typedef typename Graph::global_edgelist_selector EdgeListS;
Chris@16:         BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
Chris@16: 
Chris@16:         typename EdgeList::iterator i = el.begin(), end = el.end();
Chris@16:         for (; i != end; ++i) {
Chris@16:           if ((*i).get_target() == v) {
Chris@16:             // NOTE: Wihtout this skip, this loop will double-delete properties
Chris@16:             // of loop edges. This solution is based on the observation that
Chris@16:             // the incidence edges of a vertex with a loop are adjacent in the
Chris@16:             // out edge list. This *may* actually hold for multisets also.
Chris@16:             bool skip = (boost::next(i) != end && i->get_iter() == boost::next(i)->get_iter());
Chris@16:             g.m_edges.erase((*i).get_iter());
Chris@16:             if (skip) ++i;
Chris@16:           }
Chris@16:         }
Chris@16:         detail::erase_from_incidence_list(el, v, cat);
Chris@16:       }
Chris@16:       // O(log(E/V))
Chris@16:       template <class Graph, class EdgeList, class Vertex>
Chris@16:       inline void
Chris@16:       remove_edge_and_property(Graph& g, EdgeList& el, Vertex v,
Chris@16:                                boost::disallow_parallel_edge_tag)
Chris@16:       {
Chris@16:         typedef typename Graph::global_edgelist_selector EdgeListS;
Chris@16:         BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
Chris@16: 
Chris@16:         typedef typename EdgeList::value_type StoredEdge;
Chris@16:         typename EdgeList::iterator i = el.find(StoredEdge(v)), end = el.end();
Chris@16:         if (i != end) {
Chris@16:           g.m_edges.erase((*i).get_iter());
Chris@16:           el.erase(i);
Chris@16:         }
Chris@16:       }
Chris@16: 
Chris@16:     } // namespace detail
Chris@16: 
Chris@16:     template <class Vertex, class EdgeProperty>
Chris@16:     struct list_edge // short name due to VC++ truncation and linker problems
Chris@16:       : public boost::detail::edge_base<boost::undirected_tag, Vertex>
Chris@16:     {
Chris@16:       typedef EdgeProperty property_type;
Chris@16:       typedef boost::detail::edge_base<boost::undirected_tag, Vertex> Base;
Chris@16:       list_edge(Vertex u, Vertex v, const EdgeProperty& p = EdgeProperty())
Chris@16:         : Base(u, v), m_property(p) { }
Chris@16:       EdgeProperty& get_property() { return m_property; }
Chris@16:       const EdgeProperty& get_property() const { return m_property; }
Chris@16:       // the following methods should never be used, but are needed
Chris@16:       // to make SGI MIPSpro C++ happy
Chris@16:       list_edge() { }
Chris@16:       bool operator==(const list_edge&) const { return false; }
Chris@16:       bool operator<(const list_edge&) const { return false; }
Chris@16:       EdgeProperty m_property;
Chris@16:     };
Chris@16: 
Chris@16:     template <class Config>
Chris@16:     struct undirected_graph_helper {
Chris@16: 
Chris@16:       typedef undir_adj_list_traversal_tag traversal_category;
Chris@16: 
Chris@16:       // Placement of these overloaded remove_edge() functions
Chris@16:       // inside the class avoids a VC++ bug.
Chris@16: 
Chris@16:       // O(E/V)
Chris@16:       inline void
Chris@16:       remove_edge(typename Config::edge_descriptor e)
Chris@16:       {
Chris@16:         typedef typename Config::global_edgelist_selector EdgeListS;
Chris@16:         BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
Chris@16: 
Chris@16:         typedef typename Config::OutEdgeList::value_type::property_type PType;
Chris@16:         detail::remove_undirected_edge_dispatch<PType>::apply
Chris@16:           (e, *this, *(PType*)e.get_property());
Chris@16:       }
Chris@16:       // O(E/V)
Chris@16:       inline void
Chris@16:       remove_edge(typename Config::out_edge_iterator iter)
Chris@16:       {
Chris@16:         this->remove_edge(*iter);
Chris@16:       }
Chris@16:     };
Chris@16: 
Chris@16:     // Had to make these non-members to avoid accidental instantiation
Chris@16:     // on SGI MIPSpro C++
Chris@16:     template <class C>
Chris@16:     inline typename C::InEdgeList&
Chris@16:     in_edge_list(undirected_graph_helper<C>&,
Chris@16:                  typename C::vertex_descriptor v)
Chris@16:     {
Chris@16:       typename C::stored_vertex* sv = (typename C::stored_vertex*)v;
Chris@16:       return sv->m_out_edges;
Chris@16:     }
Chris@16:     template <class C>
Chris@16:     inline const typename C::InEdgeList&
Chris@16:     in_edge_list(const undirected_graph_helper<C>&,
Chris@16:                  typename C::vertex_descriptor v) {
Chris@16:       typename C::stored_vertex* sv = (typename C::stored_vertex*)v;
Chris@16:       return sv->m_out_edges;
Chris@16:     }
Chris@16: 
Chris@16:     // O(E/V)
Chris@16:     template <class EdgeOrIter, class Config>
Chris@16:     inline void
Chris@16:     remove_edge(EdgeOrIter e, undirected_graph_helper<Config>& g_)
Chris@16:     {
Chris@16:       typedef typename Config::global_edgelist_selector EdgeListS;
Chris@16:       BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
Chris@16: 
Chris@16:       g_.remove_edge(e);
Chris@16:     }
Chris@16: 
Chris@16:     // O(E/V) or O(log(E/V))
Chris@16:     template <class Config>
Chris@16:     void
Chris@16:     remove_edge(typename Config::vertex_descriptor u,
Chris@16:                 typename Config::vertex_descriptor v,
Chris@16:                 undirected_graph_helper<Config>& g_)
Chris@16:     {
Chris@16:       typedef typename Config::global_edgelist_selector EdgeListS;
Chris@16:       BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
Chris@16: 
Chris@16:       typedef typename Config::graph_type graph_type;
Chris@16:       graph_type& g = static_cast<graph_type&>(g_);
Chris@16:       typedef typename Config::edge_parallel_category Cat;
Chris@16:       detail::remove_edge_and_property(g, g.out_edge_list(u), v, Cat());
Chris@16:       detail::erase_from_incidence_list(g.out_edge_list(v), u, Cat());
Chris@16:     }
Chris@16: 
Chris@16:     template <class Config, class Predicate>
Chris@16:     void
Chris@16:     remove_out_edge_if(typename Config::vertex_descriptor u, Predicate pred,
Chris@16:                        undirected_graph_helper<Config>& g_)
Chris@16:     {
Chris@16:       typedef typename Config::global_edgelist_selector EdgeListS;
Chris@16:       BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
Chris@16: 
Chris@16:       typedef typename Config::graph_type graph_type;
Chris@16:       typedef typename Config::OutEdgeList::value_type::property_type PropT;
Chris@16:       graph_type& g = static_cast<graph_type&>(g_);
Chris@16:       typename Config::out_edge_iterator first, last;
Chris@16:       boost::tie(first, last) = out_edges(u, g);
Chris@16:       typedef typename Config::edge_parallel_category Cat;
Chris@16:       detail::undirected_remove_out_edge_if_dispatch<PropT>
Chris@16:         (g, first, last, g.out_edge_list(u), pred, Cat());
Chris@16:     }
Chris@16:     template <class Config, class Predicate>
Chris@16:     void
Chris@16:     remove_in_edge_if(typename Config::vertex_descriptor u, Predicate pred,
Chris@16:                       undirected_graph_helper<Config>& g_)
Chris@16:     {
Chris@16:       typedef typename Config::global_edgelist_selector EdgeListS;
Chris@16:       BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
Chris@16: 
Chris@16:       remove_out_edge_if(u, pred, g_);
Chris@16:     }
Chris@16: 
Chris@16:     // O(E/V * E) or O(log(E/V) * E)
Chris@16:     template <class Predicate, class Config>
Chris@16:     void
Chris@16:     remove_edge_if(Predicate pred, undirected_graph_helper<Config>& g_)
Chris@16:     {
Chris@16:       typedef typename Config::global_edgelist_selector EdgeListS;
Chris@16:       BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
Chris@16: 
Chris@16:       typedef typename Config::graph_type graph_type;
Chris@16:       graph_type& g = static_cast<graph_type&>(g_);
Chris@16:       typename Config::edge_iterator ei, ei_end, next;
Chris@16:       boost::tie(ei, ei_end) = edges(g);
Chris@16:       for (next = ei; ei != ei_end; ei = next) {
Chris@16:         ++next;
Chris@16:         if (pred(*ei))
Chris@16:           remove_edge(*ei, g);
Chris@16:       }
Chris@16:     }
Chris@16: 
Chris@16:     // O(1)
Chris@16:     template <class Config>
Chris@16:     inline std::pair<typename Config::edge_iterator,
Chris@16:                      typename Config::edge_iterator>
Chris@16:     edges(const undirected_graph_helper<Config>& g_)
Chris@16:     {
Chris@16:       typedef typename Config::graph_type graph_type;
Chris@16:       typedef typename Config::edge_iterator edge_iterator;
Chris@16:       const graph_type& cg = static_cast<const graph_type&>(g_);
Chris@16:       graph_type& g = const_cast<graph_type&>(cg);
Chris@16:       return std::make_pair( edge_iterator(g.m_edges.begin()),
Chris@16:                              edge_iterator(g.m_edges.end()) );
Chris@16:     }
Chris@16:     // O(1)
Chris@16:     template <class Config>
Chris@16:     inline typename Config::edges_size_type
Chris@16:     num_edges(const undirected_graph_helper<Config>& g_)
Chris@16:     {
Chris@16:       typedef typename Config::graph_type graph_type;
Chris@16:       const graph_type& g = static_cast<const graph_type&>(g_);
Chris@16:       return g.m_edges.size();
Chris@16:     }
Chris@16:     // O(E/V * E/V)
Chris@16:     template <class Config>
Chris@16:     inline void
Chris@16:     clear_vertex(typename Config::vertex_descriptor u,
Chris@16:                  undirected_graph_helper<Config>& g_)
Chris@16:     {
Chris@16:       typedef typename Config::global_edgelist_selector EdgeListS;
Chris@16:       BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
Chris@16: 
Chris@16:       typedef typename Config::graph_type graph_type;
Chris@16:       graph_type& g = static_cast<graph_type&>(g_);
Chris@16:       while (true) {
Chris@16:         typename Config::out_edge_iterator ei, ei_end;
Chris@16:         boost::tie(ei, ei_end) = out_edges(u, g);
Chris@16:         if (ei == ei_end) break;
Chris@16:         remove_edge(*ei, g);
Chris@16:       }
Chris@16:     }
Chris@16:     // O(1) for allow_parallel_edge_tag
Chris@16:     // O(log(E/V)) for disallow_parallel_edge_tag
Chris@16:     template <class Config>
Chris@16:     inline std::pair<typename Config::edge_descriptor, bool>
Chris@16:     add_edge(typename Config::vertex_descriptor u,
Chris@16:              typename Config::vertex_descriptor v,
Chris@16:              const typename Config::edge_property_type& p,
Chris@16:              undirected_graph_helper<Config>& g_)
Chris@16:     {
Chris@16:       typedef typename Config::StoredEdge StoredEdge;
Chris@16:       typedef typename Config::edge_descriptor edge_descriptor;
Chris@16:       typedef typename Config::graph_type graph_type;
Chris@16:       graph_type& g = static_cast<graph_type&>(g_);
Chris@16: 
Chris@16:       bool inserted;
Chris@16:       typename Config::EdgeContainer::value_type e(u, v, p);
Chris@16:       typename Config::EdgeContainer::iterator p_iter
Chris@16:         = graph_detail::push(g.m_edges, e).first;
Chris@16: 
Chris@16:       typename Config::OutEdgeList::iterator i;
Chris@16:       boost::tie(i, inserted) = boost::graph_detail::push(g.out_edge_list(u),
Chris@16:                                     StoredEdge(v, p_iter, &g.m_edges));
Chris@16:       if (inserted) {
Chris@16:         boost::graph_detail::push(g.out_edge_list(v), StoredEdge(u, p_iter, &g.m_edges));
Chris@16:         return std::make_pair(edge_descriptor(u, v, &p_iter->get_property()),
Chris@16:                               true);
Chris@16:       } else {
Chris@16:         g.m_edges.erase(p_iter);
Chris@16:         return std::make_pair
Chris@16:           (edge_descriptor(u, v, &i->get_iter()->get_property()), false);
Chris@16:       }
Chris@16:     }
Chris@16:     template <class Config>
Chris@16:     inline std::pair<typename Config::edge_descriptor, bool>
Chris@16:     add_edge(typename Config::vertex_descriptor u,
Chris@16:              typename Config::vertex_descriptor v,
Chris@16:              undirected_graph_helper<Config>& g_)
Chris@16:     {
Chris@16:       typename Config::edge_property_type p;
Chris@16:       return add_edge(u, v, p, g_);
Chris@16:     }
Chris@16: 
Chris@16:     // O(1)
Chris@16:     template <class Config>
Chris@16:     inline typename Config::degree_size_type
Chris@16:     degree(typename Config::vertex_descriptor u,
Chris@16:            const undirected_graph_helper<Config>& g_)
Chris@16:     {
Chris@16:       typedef typename Config::graph_type Graph;
Chris@16:       const Graph& g = static_cast<const Graph&>(g_);
Chris@16:       return out_degree(u, g);
Chris@16:     }
Chris@16: 
Chris@16:     template <class Config>
Chris@16:     inline std::pair<typename Config::in_edge_iterator,
Chris@16:                      typename Config::in_edge_iterator>
Chris@16:     in_edges(typename Config::vertex_descriptor u,
Chris@16:              const undirected_graph_helper<Config>& g_)
Chris@16:     {
Chris@16:       typedef typename Config::graph_type Graph;
Chris@16:       const Graph& cg = static_cast<const Graph&>(g_);
Chris@16:       Graph& g = const_cast<Graph&>(cg);
Chris@16:       typedef typename Config::in_edge_iterator in_edge_iterator;
Chris@16:       return
Chris@16:         std::make_pair(in_edge_iterator(g.out_edge_list(u).begin(), u),
Chris@16:                        in_edge_iterator(g.out_edge_list(u).end(), u));
Chris@16:     }
Chris@16: 
Chris@16:     template <class Config>
Chris@16:     inline typename Config::degree_size_type
Chris@16:     in_degree(typename Config::vertex_descriptor u,
Chris@16:               const undirected_graph_helper<Config>& g_)
Chris@16:     { return degree(u, g_); }
Chris@16: 
Chris@16:     //=========================================================================
Chris@16:     // Bidirectional Graph Helper Class
Chris@16: 
Chris@16:     struct bidir_adj_list_traversal_tag :
Chris@16:       public virtual vertex_list_graph_tag,
Chris@16:       public virtual incidence_graph_tag,
Chris@16:       public virtual adjacency_graph_tag,
Chris@16:       public virtual edge_list_graph_tag,
Chris@16:       public virtual bidirectional_graph_tag { };
Chris@16: 
Chris@16:     template <class Config>
Chris@16:     struct bidirectional_graph_helper
Chris@16:       : public directed_edges_helper<Config> {
Chris@16:       typedef bidir_adj_list_traversal_tag traversal_category;
Chris@16:     };
Chris@16: 
Chris@16:     // Had to make these non-members to avoid accidental instantiation
Chris@16:     // on SGI MIPSpro C++
Chris@16:     template <class C>
Chris@16:     inline typename C::InEdgeList&
Chris@16:     in_edge_list(bidirectional_graph_helper<C>&,
Chris@16:                  typename C::vertex_descriptor v)
Chris@16:     {
Chris@16:       typename C::stored_vertex* sv = (typename C::stored_vertex*)v;
Chris@16:       return sv->m_in_edges;
Chris@16:     }
Chris@16:     template <class C>
Chris@16:     inline const typename C::InEdgeList&
Chris@16:     in_edge_list(const bidirectional_graph_helper<C>&,
Chris@16:                  typename C::vertex_descriptor v) {
Chris@16:       typename C::stored_vertex* sv = (typename C::stored_vertex*)v;
Chris@16:       return sv->m_in_edges;
Chris@16:     }
Chris@16: 
Chris@16:     template <class Predicate, class Config>
Chris@16:     inline void
Chris@16:     remove_edge_if(Predicate pred, bidirectional_graph_helper<Config>& g_)
Chris@16:     {
Chris@16:       typedef typename Config::global_edgelist_selector EdgeListS;
Chris@16:       BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
Chris@16: 
Chris@16:       typedef typename Config::graph_type graph_type;
Chris@16:       graph_type& g = static_cast<graph_type&>(g_);
Chris@16:       typename Config::edge_iterator ei, ei_end, next;
Chris@16:       boost::tie(ei, ei_end) = edges(g);
Chris@16:       for (next = ei; ei != ei_end; ei = next) {
Chris@16:         ++next;
Chris@16:         if (pred(*ei))
Chris@16:           remove_edge(*ei, g);
Chris@16:       }
Chris@16:     }
Chris@16: 
Chris@16:     template <class Config>
Chris@16:     inline std::pair<typename Config::in_edge_iterator,
Chris@16:                      typename Config::in_edge_iterator>
Chris@16:     in_edges(typename Config::vertex_descriptor u,
Chris@16:              const bidirectional_graph_helper<Config>& g_)
Chris@16:     {
Chris@16:       typedef typename Config::graph_type graph_type;
Chris@16:       const graph_type& cg = static_cast<const graph_type&>(g_);
Chris@16:       graph_type& g = const_cast<graph_type&>(cg);
Chris@16:       typedef typename Config::in_edge_iterator in_edge_iterator;
Chris@16:       return
Chris@16:         std::make_pair(in_edge_iterator(in_edge_list(g, u).begin(), u),
Chris@16:                        in_edge_iterator(in_edge_list(g, u).end(), u));
Chris@16:     }
Chris@16: 
Chris@16:     // O(1)
Chris@16:     template <class Config>
Chris@16:     inline std::pair<typename Config::edge_iterator,
Chris@16:                      typename Config::edge_iterator>
Chris@16:     edges(const bidirectional_graph_helper<Config>& g_)
Chris@16:     {
Chris@16:       typedef typename Config::graph_type graph_type;
Chris@16:       typedef typename Config::edge_iterator edge_iterator;
Chris@16:       const graph_type& cg = static_cast<const graph_type&>(g_);
Chris@16:       graph_type& g = const_cast<graph_type&>(cg);
Chris@16:       return std::make_pair( edge_iterator(g.m_edges.begin()),
Chris@16:                              edge_iterator(g.m_edges.end()) );
Chris@16:     }
Chris@16: 
Chris@16:     //=========================================================================
Chris@16:     // Bidirectional Graph Helper Class (with edge properties)
Chris@16: 
Chris@16: 
Chris@16:     template <class Config>
Chris@16:     struct bidirectional_graph_helper_with_property
Chris@16:       : public bidirectional_graph_helper<Config>
Chris@16:     {
Chris@16:       typedef typename Config::graph_type graph_type;
Chris@16:       typedef typename Config::out_edge_iterator out_edge_iterator;
Chris@16: 
Chris@16:       std::pair<out_edge_iterator, out_edge_iterator>
Chris@16:       get_parallel_edge_sublist(typename Config::edge_descriptor e,
Chris@16:                                 const graph_type& g,
Chris@16:                                 void*)
Chris@16:       { return out_edges(source(e, g), g); }
Chris@16: 
Chris@16:       std::pair<out_edge_iterator, out_edge_iterator>
Chris@16:       get_parallel_edge_sublist(typename Config::edge_descriptor e,
Chris@16:                                 const graph_type& g,
Chris@16:                                 setS*)
Chris@16:       { return edge_range(source(e, g), target(e, g), g); }
Chris@16: 
Chris@16:       std::pair<out_edge_iterator, out_edge_iterator>
Chris@16:       get_parallel_edge_sublist(typename Config::edge_descriptor e,
Chris@16:                                 const graph_type& g,
Chris@16:                                 multisetS*)
Chris@16:       { return edge_range(source(e, g), target(e, g), g); }
Chris@16: 
Chris@16:       std::pair<out_edge_iterator, out_edge_iterator>
Chris@16:       get_parallel_edge_sublist(typename Config::edge_descriptor e,
Chris@16:                                 const graph_type& g,
Chris@16:                                 hash_setS*)
Chris@16:       { return edge_range(source(e, g), target(e, g), g); }
Chris@16: 
Chris@16:       // Placement of these overloaded remove_edge() functions
Chris@16:       // inside the class avoids a VC++ bug.
Chris@16: 
Chris@16:       // O(E/V) or O(log(E/V))
Chris@16:       void
Chris@16:       remove_edge(typename Config::edge_descriptor e)
Chris@16:       {
Chris@16:         typedef typename Config::global_edgelist_selector EdgeListS;
Chris@16:         BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
Chris@16: 
Chris@16:         graph_type& g = static_cast<graph_type&>(*this);
Chris@16: 
Chris@16:         typedef typename Config::edgelist_selector OutEdgeListS;
Chris@16: 
Chris@16:         std::pair<out_edge_iterator, out_edge_iterator> rng =
Chris@16:           get_parallel_edge_sublist(e, g, (OutEdgeListS*)(0));
Chris@16:         rng.first = std::find(rng.first, rng.second, e);
Chris@16:         BOOST_ASSERT(rng.first != rng.second);
Chris@16:         remove_edge(rng.first);
Chris@16:       }
Chris@16: 
Chris@16:       inline void
Chris@16:       remove_edge(typename Config::out_edge_iterator iter)
Chris@16:       {
Chris@16:         typedef typename Config::global_edgelist_selector EdgeListS;
Chris@16:         BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
Chris@16: 
Chris@16:         typedef typename Config::graph_type graph_type;
Chris@16:         graph_type& g = static_cast<graph_type&>(*this);
Chris@16:         typename Config::edge_descriptor e = *iter;
Chris@16:         typename Config::OutEdgeList& oel = g.out_edge_list(source(e, g));
Chris@16:         typename Config::InEdgeList& iel = in_edge_list(g, target(e, g));
Chris@16:         typedef typename Config::OutEdgeList::value_type::property_type PType;
Chris@16:         PType& p = *(PType*)e.get_property();
Chris@16:         detail::remove_directed_edge_dispatch(*iter, iel, p);
Chris@16:         g.m_edges.erase(iter.base()->get_iter());
Chris@16:         oel.erase(iter.base());
Chris@16:       }
Chris@16:     };
Chris@16: 
Chris@16:     // O(E/V) for allow_parallel_edge_tag
Chris@16:     // O(log(E/V)) for disallow_parallel_edge_tag
Chris@16:     template <class Config>
Chris@16:     inline void
Chris@16:     remove_edge(typename Config::vertex_descriptor u,
Chris@16:                 typename Config::vertex_descriptor v,
Chris@16:                 bidirectional_graph_helper_with_property<Config>& g_)
Chris@16:     {
Chris@16:       typedef typename Config::global_edgelist_selector EdgeListS;
Chris@16:       BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
Chris@16: 
Chris@16:       typedef typename Config::graph_type graph_type;
Chris@16:       graph_type& g = static_cast<graph_type&>(g_);
Chris@16:       typedef typename Config::edge_parallel_category Cat;
Chris@16:       detail::remove_edge_and_property(g, g.out_edge_list(u), v, Cat());
Chris@16:       detail::erase_from_incidence_list(in_edge_list(g, v), u, Cat());
Chris@16:     }
Chris@16: 
Chris@16:     // O(E/V) or O(log(E/V))
Chris@16:     template <class EdgeOrIter, class Config>
Chris@16:     inline void
Chris@16:     remove_edge(EdgeOrIter e,
Chris@16:                 bidirectional_graph_helper_with_property<Config>& g_)
Chris@16:     {
Chris@16:       typedef typename Config::global_edgelist_selector EdgeListS;
Chris@16:       BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
Chris@16: 
Chris@16:       g_.remove_edge(e);
Chris@16:     }
Chris@16: 
Chris@16:     template <class Config, class Predicate>
Chris@16:     inline void
Chris@16:     remove_out_edge_if(typename Config::vertex_descriptor u, Predicate pred,
Chris@16:                        bidirectional_graph_helper_with_property<Config>& g_)
Chris@16:     {
Chris@16:       typedef typename Config::global_edgelist_selector EdgeListS;
Chris@16:       BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
Chris@16: 
Chris@16:       typedef typename Config::graph_type graph_type;
Chris@16:       typedef typename Config::OutEdgeList::value_type::property_type PropT;
Chris@16:       graph_type& g = static_cast<graph_type&>(g_);
Chris@16: 
Chris@16:       typedef typename Config::EdgeIter EdgeIter;
Chris@16:       typedef std::vector<EdgeIter> Garbage;
Chris@16:       Garbage garbage;
Chris@16: 
Chris@16:       // First remove the edges from the targets' in-edge lists and
Chris@16:       // from the graph's edge set list.
Chris@16:       typename Config::out_edge_iterator out_i, out_end;
Chris@16:       for (boost::tie(out_i, out_end) = out_edges(u, g); out_i != out_end; ++out_i)
Chris@16:         if (pred(*out_i)) {
Chris@16:           detail::remove_directed_edge_dispatch
Chris@16:             (*out_i, in_edge_list(g, target(*out_i, g)),
Chris@16:              *(PropT*)(*out_i).get_property());
Chris@16:           // Put in garbage to delete later. Will need the properties
Chris@16:           // for the remove_if of the out-edges.
Chris@16:           garbage.push_back((*out_i.base()).get_iter());
Chris@16:         }
Chris@16: 
Chris@16:       // Now remove the edges from this out-edge list.
Chris@16:       typename Config::out_edge_iterator first, last;
Chris@16:       boost::tie(first, last) = out_edges(u, g);
Chris@16:       typedef typename Config::edge_parallel_category Cat;
Chris@16:       detail::remove_directed_edge_if_dispatch
Chris@16:         (first, last, g.out_edge_list(u), pred, Cat());
Chris@16: 
Chris@16:       // Now delete the edge properties from the g.m_edges list
Chris@16:       for (typename Garbage::iterator i = garbage.begin();
Chris@16:            i != garbage.end(); ++i)
Chris@16:         g.m_edges.erase(*i);
Chris@16:     }
Chris@16:     template <class Config, class Predicate>
Chris@16:     inline void
Chris@16:     remove_in_edge_if(typename Config::vertex_descriptor v, Predicate pred,
Chris@16:                       bidirectional_graph_helper_with_property<Config>& g_)
Chris@16:     {
Chris@16:       typedef typename Config::global_edgelist_selector EdgeListS;
Chris@16:       BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
Chris@16: 
Chris@16:       typedef typename Config::graph_type graph_type;
Chris@16:       typedef typename Config::OutEdgeList::value_type::property_type PropT;
Chris@16:       graph_type& g = static_cast<graph_type&>(g_);
Chris@16: 
Chris@16:       typedef typename Config::EdgeIter EdgeIter;
Chris@16:       typedef std::vector<EdgeIter> Garbage;
Chris@16:       Garbage garbage;
Chris@16: 
Chris@16:       // First remove the edges from the sources' out-edge lists and
Chris@16:       // from the graph's edge set list.
Chris@16:       typename Config::in_edge_iterator in_i, in_end;
Chris@16:       for (boost::tie(in_i, in_end) = in_edges(v, g); in_i != in_end; ++in_i)
Chris@16:         if (pred(*in_i)) {
Chris@16:           typename Config::vertex_descriptor u = source(*in_i, g);
Chris@16:           detail::remove_directed_edge_dispatch
Chris@16:             (*in_i, g.out_edge_list(u), *(PropT*)(*in_i).get_property());
Chris@16:           // Put in garbage to delete later. Will need the properties
Chris@16:           // for the remove_if of the out-edges.
Chris@16:           garbage.push_back((*in_i.base()).get_iter());
Chris@16:         }
Chris@16:       // Now remove the edges from this in-edge list.
Chris@16:       typename Config::in_edge_iterator first, last;
Chris@16:       boost::tie(first, last) = in_edges(v, g);
Chris@16:       typedef typename Config::edge_parallel_category Cat;
Chris@16:       detail::remove_directed_edge_if_dispatch
Chris@16:         (first, last, in_edge_list(g, v), pred, Cat());
Chris@16: 
Chris@16:       // Now delete the edge properties from the g.m_edges list
Chris@16:       for (typename Garbage::iterator i = garbage.begin();
Chris@16:            i != garbage.end(); ++i)
Chris@16:         g.m_edges.erase(*i);
Chris@16:     }
Chris@16: 
Chris@16:     // O(1)
Chris@16:     template <class Config>
Chris@16:     inline typename Config::edges_size_type
Chris@16:     num_edges(const bidirectional_graph_helper_with_property<Config>& g_)
Chris@16:     {
Chris@16:       typedef typename Config::graph_type graph_type;
Chris@16:       const graph_type& g = static_cast<const graph_type&>(g_);
Chris@16:       return g.m_edges.size();
Chris@16:     }
Chris@16:     // O(E/V * E/V) for allow_parallel_edge_tag
Chris@16:     // O(E/V * log(E/V)) for disallow_parallel_edge_tag
Chris@16:     template <class Config>
Chris@16:     inline void
Chris@16:     clear_vertex(typename Config::vertex_descriptor u,
Chris@16:                  bidirectional_graph_helper_with_property<Config>& g_)
Chris@16:     {
Chris@16:       typedef typename Config::global_edgelist_selector EdgeListS;
Chris@16:       BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
Chris@16: 
Chris@16:       typedef typename Config::graph_type graph_type;
Chris@16:       typedef typename Config::edge_parallel_category Cat;
Chris@16:       graph_type& g = static_cast<graph_type&>(g_);
Chris@16:       typename Config::OutEdgeList& el = g.out_edge_list(u);
Chris@16:       typename Config::OutEdgeList::iterator
Chris@16:         ei = el.begin(), ei_end = el.end();
Chris@16:       for (; ei != ei_end; ++ei) {
Chris@16:         detail::erase_from_incidence_list
Chris@16:           (in_edge_list(g, (*ei).get_target()), u, Cat());
Chris@16:         g.m_edges.erase((*ei).get_iter());
Chris@16:       }
Chris@16:       typename Config::InEdgeList& in_el = in_edge_list(g, u);
Chris@16:       typename Config::InEdgeList::iterator
Chris@16:         in_ei = in_el.begin(), in_ei_end = in_el.end();
Chris@16:       for (; in_ei != in_ei_end; ++in_ei) {
Chris@16:         detail::erase_from_incidence_list
Chris@16:           (g.out_edge_list((*in_ei).get_target()), u, Cat());
Chris@16:         g.m_edges.erase((*in_ei).get_iter());
Chris@16:       }
Chris@16:       g.out_edge_list(u).clear();
Chris@16:       in_edge_list(g, u).clear();
Chris@16:     }
Chris@16: 
Chris@16:     template <class Config>
Chris@16:     inline void
Chris@16:     clear_out_edges(typename Config::vertex_descriptor u,
Chris@16:                     bidirectional_graph_helper_with_property<Config>& g_)
Chris@16:     {
Chris@16:       typedef typename Config::global_edgelist_selector EdgeListS;
Chris@16:       BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
Chris@16: 
Chris@16:       typedef typename Config::graph_type graph_type;
Chris@16:       typedef typename Config::edge_parallel_category Cat;
Chris@16:       graph_type& g = static_cast<graph_type&>(g_);
Chris@16:       typename Config::OutEdgeList& el = g.out_edge_list(u);
Chris@16:       typename Config::OutEdgeList::iterator
Chris@16:         ei = el.begin(), ei_end = el.end();
Chris@16:       for (; ei != ei_end; ++ei) {
Chris@16:         detail::erase_from_incidence_list
Chris@16:           (in_edge_list(g, (*ei).get_target()), u, Cat());
Chris@16:         g.m_edges.erase((*ei).get_iter());
Chris@16:       }
Chris@16:       g.out_edge_list(u).clear();
Chris@16:     }
Chris@16: 
Chris@16:     template <class Config>
Chris@16:     inline void
Chris@16:     clear_in_edges(typename Config::vertex_descriptor u,
Chris@16:                    bidirectional_graph_helper_with_property<Config>& g_)
Chris@16:     {
Chris@16:       typedef typename Config::global_edgelist_selector EdgeListS;
Chris@16:       BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
Chris@16: 
Chris@16:       typedef typename Config::graph_type graph_type;
Chris@16:       typedef typename Config::edge_parallel_category Cat;
Chris@16:       graph_type& g = static_cast<graph_type&>(g_);
Chris@16:       typename Config::InEdgeList& in_el = in_edge_list(g, u);
Chris@16:       typename Config::InEdgeList::iterator
Chris@16:         in_ei = in_el.begin(), in_ei_end = in_el.end();
Chris@16:       for (; in_ei != in_ei_end; ++in_ei) {
Chris@16:         detail::erase_from_incidence_list
Chris@16:           (g.out_edge_list((*in_ei).get_target()), u, Cat());
Chris@16:         g.m_edges.erase((*in_ei).get_iter());
Chris@16:       }
Chris@16:       in_edge_list(g, u).clear();
Chris@16:     }
Chris@16: 
Chris@16:     // O(1) for allow_parallel_edge_tag
Chris@16:     // O(log(E/V)) for disallow_parallel_edge_tag
Chris@16:     template <class Config>
Chris@16:     inline std::pair<typename Config::edge_descriptor, bool>
Chris@16:     add_edge(typename Config::vertex_descriptor u,
Chris@16:              typename Config::vertex_descriptor v,
Chris@16:              const typename Config::edge_property_type& p,
Chris@16:              bidirectional_graph_helper_with_property<Config>& g_)
Chris@16:     {
Chris@16:       typedef typename Config::graph_type graph_type;
Chris@16:       graph_type& g = static_cast<graph_type&>(g_);
Chris@16:       typedef typename Config::edge_descriptor edge_descriptor;
Chris@16:       typedef typename Config::StoredEdge StoredEdge;
Chris@16:       bool inserted;
Chris@16:       typename Config::EdgeContainer::value_type e(u, v, p);
Chris@16:       typename Config::EdgeContainer::iterator p_iter
Chris@16:         = graph_detail::push(g.m_edges, e).first;
Chris@16:       typename Config::OutEdgeList::iterator i;
Chris@16:       boost::tie(i, inserted) = boost::graph_detail::push(g.out_edge_list(u),
Chris@16:                                         StoredEdge(v, p_iter, &g.m_edges));
Chris@16:       if (inserted) {
Chris@16:         boost::graph_detail::push(in_edge_list(g, v), StoredEdge(u, p_iter, &g.m_edges));
Chris@16:         return std::make_pair(edge_descriptor(u, v, &p_iter->m_property),
Chris@16:                               true);
Chris@16:       } else {
Chris@16:         g.m_edges.erase(p_iter);
Chris@16:         return std::make_pair(edge_descriptor(u, v,
Chris@16:                                      &i->get_iter()->get_property()),
Chris@16:                               false);
Chris@16:       }
Chris@16:     }
Chris@16: 
Chris@16:     template <class Config>
Chris@16:     inline std::pair<typename Config::edge_descriptor, bool>
Chris@16:     add_edge(typename Config::vertex_descriptor u,
Chris@16:              typename Config::vertex_descriptor v,
Chris@16:              bidirectional_graph_helper_with_property<Config>& g_)
Chris@16:     {
Chris@16:       typename Config::edge_property_type p;
Chris@16:       return add_edge(u, v, p, g_);
Chris@16:     }
Chris@16:     // O(1)
Chris@16:     template <class Config>
Chris@16:     inline typename Config::degree_size_type
Chris@16:     degree(typename Config::vertex_descriptor u,
Chris@16:            const bidirectional_graph_helper_with_property<Config>& g_)
Chris@16:     {
Chris@16:       typedef typename Config::graph_type graph_type;
Chris@16:       const graph_type& g = static_cast<const graph_type&>(g_);
Chris@16:       return in_degree(u, g) + out_degree(u, g);
Chris@16:     }
Chris@16: 
Chris@16:     //=========================================================================
Chris@16:     // Adjacency List Helper Class
Chris@16: 
Chris@16:     template <class Config, class Base>
Chris@16:     struct adj_list_helper : public Base
Chris@16:     {
Chris@16:       typedef typename Config::graph_type AdjList;
Chris@16:       typedef typename Config::vertex_descriptor vertex_descriptor;
Chris@16:       typedef typename Config::edge_descriptor edge_descriptor;
Chris@16:       typedef typename Config::out_edge_iterator out_edge_iterator;
Chris@16:       typedef typename Config::in_edge_iterator in_edge_iterator;
Chris@16:       typedef typename Config::adjacency_iterator adjacency_iterator;
Chris@16:       typedef typename Config::inv_adjacency_iterator inv_adjacency_iterator;
Chris@16:       typedef typename Config::vertex_iterator vertex_iterator;
Chris@16:       typedef typename Config::edge_iterator edge_iterator;
Chris@16:       typedef typename Config::directed_category directed_category;
Chris@16:       typedef typename Config::edge_parallel_category edge_parallel_category;
Chris@16:       typedef typename Config::vertices_size_type vertices_size_type;
Chris@16:       typedef typename Config::edges_size_type edges_size_type;
Chris@16:       typedef typename Config::degree_size_type degree_size_type;
Chris@16:       typedef typename Config::StoredEdge StoredEdge;
Chris@16:       typedef typename Config::vertex_property_type vertex_property_type;
Chris@16:       typedef typename Config::edge_property_type edge_property_type;
Chris@16:       typedef typename Config::graph_property_type graph_property_type;
Chris@16: 
Chris@16:       typedef typename Config::global_edgelist_selector
Chris@16:         global_edgelist_selector;
Chris@16: 
Chris@16:       typedef typename lookup_one_property<vertex_property_type, vertex_bundle_t>::type vertex_bundled;
Chris@16:       typedef typename lookup_one_property<edge_property_type, edge_bundle_t>::type edge_bundled;
Chris@16:       typedef typename lookup_one_property<graph_property_type, graph_bundle_t>::type graph_bundled;
Chris@16:     };
Chris@16: 
Chris@16:     template <class Config, class Base>
Chris@16:     inline std::pair<typename Config::adjacency_iterator,
Chris@16:                      typename Config::adjacency_iterator>
Chris@16:     adjacent_vertices(typename Config::vertex_descriptor u,
Chris@16:                       const adj_list_helper<Config, Base>& g_)
Chris@16:     {
Chris@16:       typedef typename Config::graph_type AdjList;
Chris@16:       const AdjList& cg = static_cast<const AdjList&>(g_);
Chris@16:       AdjList& g = const_cast<AdjList&>(cg);
Chris@16:       typedef typename Config::adjacency_iterator adjacency_iterator;
Chris@16:       typename Config::out_edge_iterator first, last;
Chris@16:       boost::tie(first, last) = out_edges(u, g);
Chris@16:       return std::make_pair(adjacency_iterator(first, &g),
Chris@16:                             adjacency_iterator(last, &g));
Chris@16:     }
Chris@16:     template <class Config, class Base>
Chris@16:     inline std::pair<typename Config::inv_adjacency_iterator,
Chris@16:                      typename Config::inv_adjacency_iterator>
Chris@16:     inv_adjacent_vertices(typename Config::vertex_descriptor u,
Chris@16:                           const adj_list_helper<Config, Base>& g_)
Chris@16:     {
Chris@16:       typedef typename Config::graph_type AdjList;
Chris@16:       const AdjList& cg = static_cast<const AdjList&>(g_);
Chris@16:       AdjList& g = const_cast<AdjList&>(cg);
Chris@16:       typedef typename Config::inv_adjacency_iterator inv_adjacency_iterator;
Chris@16:       typename Config::in_edge_iterator first, last;
Chris@16:       boost::tie(first, last) = in_edges(u, g);
Chris@16:       return std::make_pair(inv_adjacency_iterator(first, &g),
Chris@16:                             inv_adjacency_iterator(last, &g));
Chris@16:     }
Chris@16:     template <class Config, class Base>
Chris@16:     inline std::pair<typename Config::out_edge_iterator,
Chris@16:                      typename Config::out_edge_iterator>
Chris@16:     out_edges(typename Config::vertex_descriptor u,
Chris@16:               const adj_list_helper<Config, Base>& g_)
Chris@16:     {
Chris@16:       typedef typename Config::graph_type AdjList;
Chris@16:       typedef typename Config::out_edge_iterator out_edge_iterator;
Chris@16:       const AdjList& cg = static_cast<const AdjList&>(g_);
Chris@16:       AdjList& g = const_cast<AdjList&>(cg);
Chris@16:       return
Chris@16:         std::make_pair(out_edge_iterator(g.out_edge_list(u).begin(), u),
Chris@16:                        out_edge_iterator(g.out_edge_list(u).end(), u));
Chris@16:     }
Chris@16:     template <class Config, class Base>
Chris@16:     inline std::pair<typename Config::vertex_iterator,
Chris@16:                      typename Config::vertex_iterator>
Chris@16:     vertices(const adj_list_helper<Config, Base>& g_)
Chris@16:     {
Chris@16:       typedef typename Config::graph_type AdjList;
Chris@16:       const AdjList& cg = static_cast<const AdjList&>(g_);
Chris@16:       AdjList& g = const_cast<AdjList&>(cg);
Chris@16:       return std::make_pair( g.vertex_set().begin(), g.vertex_set().end() );
Chris@16:     }
Chris@16:     template <class Config, class Base>
Chris@16:     inline typename Config::vertices_size_type
Chris@16:     num_vertices(const adj_list_helper<Config, Base>& g_)
Chris@16:     {
Chris@16:       typedef typename Config::graph_type AdjList;
Chris@16:       const AdjList& g = static_cast<const AdjList&>(g_);
Chris@16:       return g.vertex_set().size();
Chris@16:     }
Chris@16:     template <class Config, class Base>
Chris@16:     inline typename Config::degree_size_type
Chris@16:     out_degree(typename Config::vertex_descriptor u,
Chris@16:                const adj_list_helper<Config, Base>& g_)
Chris@16:     {
Chris@16:       typedef typename Config::graph_type AdjList;
Chris@16:       const AdjList& g = static_cast<const AdjList&>(g_);
Chris@16:       return g.out_edge_list(u).size();
Chris@16:     }
Chris@16:     template <class Config, class Base>
Chris@16:     inline std::pair<typename Config::edge_descriptor, bool>
Chris@16:     edge(typename Config::vertex_descriptor u,
Chris@16:          typename Config::vertex_descriptor v,
Chris@16:          const adj_list_helper<Config, Base>& g_)
Chris@16:     {
Chris@16:       typedef typename Config::graph_type Graph;
Chris@16:       typedef typename Config::StoredEdge StoredEdge;
Chris@16:       const Graph& cg = static_cast<const Graph&>(g_);
Chris@16:       const typename Config::OutEdgeList& el = cg.out_edge_list(u);
Chris@16:       typename Config::OutEdgeList::const_iterator it = graph_detail::
Chris@16:         find(el, StoredEdge(v));
Chris@16:       return std::make_pair(
Chris@16:                typename Config::edge_descriptor
Chris@16:                      (u, v, (it == el.end() ? 0 : &(*it).get_property())),
Chris@16:                (it != el.end()));
Chris@16:     }
Chris@16: 
Chris@16:     template <class Config, class Base>
Chris@16:     inline std::pair<typename Config::out_edge_iterator,
Chris@16:                      typename Config::out_edge_iterator>
Chris@16:     edge_range(typename Config::vertex_descriptor u,
Chris@16:                typename Config::vertex_descriptor v,
Chris@16:                const adj_list_helper<Config, Base>& g_)
Chris@16:     {
Chris@16:       typedef typename Config::graph_type Graph;
Chris@16:       typedef typename Config::StoredEdge StoredEdge;
Chris@16:       const Graph& cg = static_cast<const Graph&>(g_);
Chris@16:       Graph& g = const_cast<Graph&>(cg);
Chris@16:       typedef typename Config::out_edge_iterator out_edge_iterator;
Chris@16:       typename Config::OutEdgeList& el = g.out_edge_list(u);
Chris@16:       typename Config::OutEdgeList::iterator first, last;
Chris@16:       typename Config::EdgeContainer fake_edge_container;
Chris@16:       boost::tie(first, last) = graph_detail::
Chris@101:         equal_range(el, StoredEdge(v));
Chris@16:       return std::make_pair(out_edge_iterator(first, u),
Chris@16:                             out_edge_iterator(last, u));
Chris@16:     }
Chris@16: 
Chris@16:     template <class Config>
Chris@16:     inline typename Config::degree_size_type
Chris@16:     in_degree(typename Config::vertex_descriptor u,
Chris@16:               const directed_edges_helper<Config>& g_)
Chris@16:     {
Chris@16:       typedef typename Config::graph_type Graph;
Chris@16:       const Graph& cg = static_cast<const Graph&>(g_);
Chris@16:       Graph& g = const_cast<Graph&>(cg);
Chris@16:       return in_edge_list(g, u).size();
Chris@16:     }
Chris@16: 
Chris@16:     namespace detail {
Chris@16:       template <class Config, class Base, class Property>
Chris@16:       inline
Chris@16:       typename boost::property_map<typename Config::graph_type,
Chris@16:         Property>::type
Chris@16:       get_dispatch(adj_list_helper<Config,Base>&, Property p,
Chris@16:                    boost::edge_property_tag) {
Chris@16:         typedef typename Config::graph_type Graph;
Chris@16:         typedef typename boost::property_map<Graph, Property>::type PA;
Chris@16:         return PA(p);
Chris@16:       }
Chris@16:       template <class Config, class Base, class Property>
Chris@16:       inline
Chris@16:       typename boost::property_map<typename Config::graph_type,
Chris@16:         Property>::const_type
Chris@16:       get_dispatch(const adj_list_helper<Config,Base>&, Property p,
Chris@16:                    boost::edge_property_tag) {
Chris@16:         typedef typename Config::graph_type Graph;
Chris@16:         typedef typename boost::property_map<Graph, Property>::const_type PA;
Chris@16:         return PA(p);
Chris@16:       }
Chris@16: 
Chris@16:       template <class Config, class Base, class Property>
Chris@16:       inline
Chris@16:       typename boost::property_map<typename Config::graph_type,
Chris@16:         Property>::type
Chris@16:       get_dispatch(adj_list_helper<Config,Base>& g, Property p,
Chris@16:                    boost::vertex_property_tag) {
Chris@16:         typedef typename Config::graph_type Graph;
Chris@16:         typedef typename boost::property_map<Graph, Property>::type PA;
Chris@16:         return PA(&static_cast<Graph&>(g), p);
Chris@16:       }
Chris@16:       template <class Config, class Base, class Property>
Chris@16:       inline
Chris@16:       typename boost::property_map<typename Config::graph_type,
Chris@16:         Property>::const_type
Chris@16:       get_dispatch(const adj_list_helper<Config, Base>& g, Property p,
Chris@16:                    boost::vertex_property_tag) {
Chris@16:         typedef typename Config::graph_type Graph;
Chris@16:         typedef typename boost::property_map<Graph, Property>::const_type PA;
Chris@16:         const Graph& cg = static_cast<const Graph&>(g);
Chris@16:         return PA(&cg, p);
Chris@16:       }
Chris@16: 
Chris@16:     } // namespace detail
Chris@16: 
Chris@16:     // Implementation of the PropertyGraph interface
Chris@16:     template <class Config, class Base, class Property>
Chris@16:     inline
Chris@16:     typename boost::property_map<typename Config::graph_type, Property>::type
Chris@16:     get(Property p, adj_list_helper<Config, Base>& g) {
Chris@16:       typedef typename detail::property_kind_from_graph<adj_list_helper<Config, Base>, Property>::type Kind;
Chris@16:       return detail::get_dispatch(g, p, Kind());
Chris@16:     }
Chris@16:     template <class Config, class Base, class Property>
Chris@16:     inline
Chris@16:     typename boost::property_map<typename Config::graph_type,
Chris@16:       Property>::const_type
Chris@16:     get(Property p, const adj_list_helper<Config, Base>& g) {
Chris@16:       typedef typename detail::property_kind_from_graph<adj_list_helper<Config, Base>, Property>::type Kind;
Chris@16:       return detail::get_dispatch(g, p, Kind());
Chris@16:     }
Chris@16: 
Chris@16:     template <class Config, class Base, class Property, class Key>
Chris@16:     inline
Chris@16:     typename boost::property_traits<
Chris@16:       typename boost::property_map<typename Config::graph_type,
Chris@16:         Property>::type
Chris@16:     >::reference
Chris@16:     get(Property p, adj_list_helper<Config, Base>& g, const Key& key) {
Chris@16:       return get(get(p, g), key);
Chris@16:     }
Chris@16: 
Chris@16:     template <class Config, class Base, class Property, class Key>
Chris@16:     inline
Chris@16:     typename boost::property_traits<
Chris@16:       typename boost::property_map<typename Config::graph_type,
Chris@16:         Property>::const_type
Chris@16:     >::reference
Chris@16:     get(Property p, const adj_list_helper<Config, Base>& g, const Key& key) {
Chris@16:       return get(get(p, g), key);
Chris@16:     }
Chris@16: 
Chris@16:     template <class Config, class Base, class Property, class Key,class Value>
Chris@16:     inline void
Chris@16:     put(Property p, adj_list_helper<Config, Base>& g,
Chris@16:         const Key& key, const Value& value)
Chris@16:     {
Chris@16:       typedef typename Config::graph_type Graph;
Chris@16:       typedef typename boost::property_map<Graph, Property>::type Map;
Chris@16:       Map pmap = get(p, static_cast<Graph&>(g));
Chris@16:       put(pmap, key, value);
Chris@16:     }
Chris@16: 
Chris@16: 
Chris@16:     //=========================================================================
Chris@16:     // Generalize Adjacency List Implementation
Chris@16: 
Chris@16:     struct adj_list_tag { };
Chris@16: 
Chris@16:     template <class Derived, class Config, class Base>
Chris@16:     class adj_list_impl
Chris@16:       : public adj_list_helper<Config, Base>
Chris@16:     {
Chris@16:       typedef typename Config::OutEdgeList OutEdgeList;
Chris@16:       typedef typename Config::InEdgeList InEdgeList;
Chris@16:       typedef typename Config::StoredVertexList StoredVertexList;
Chris@16:     public:
Chris@16:       typedef typename Config::stored_vertex stored_vertex;
Chris@16:       typedef typename Config::EdgeContainer EdgeContainer;
Chris@16:       typedef typename Config::vertex_descriptor vertex_descriptor;
Chris@16:       typedef typename Config::edge_descriptor edge_descriptor;
Chris@16:       typedef typename Config::vertex_iterator vertex_iterator;
Chris@16:       typedef typename Config::edge_iterator edge_iterator;
Chris@16:       typedef typename Config::edge_parallel_category edge_parallel_category;
Chris@16:       typedef typename Config::vertices_size_type vertices_size_type;
Chris@16:       typedef typename Config::edges_size_type edges_size_type;
Chris@16:       typedef typename Config::degree_size_type degree_size_type;
Chris@16:       typedef typename Config::edge_property_type edge_property_type;
Chris@16:       typedef adj_list_tag graph_tag;
Chris@16: 
Chris@16:       static vertex_descriptor null_vertex()
Chris@16:       {
Chris@16:         return 0;
Chris@16:       }
Chris@16: 
Chris@16:       inline adj_list_impl() { }
Chris@16: 
Chris@16:       inline adj_list_impl(const adj_list_impl& x) {
Chris@16:         copy_impl(x);
Chris@16:       }
Chris@16:       inline adj_list_impl& operator=(const adj_list_impl& x) {
Chris@16:         this->clear();
Chris@16:         copy_impl(x);
Chris@16:         return *this;
Chris@16:       }
Chris@16:       inline void clear() {
Chris@16:         for (typename StoredVertexList::iterator i = m_vertices.begin();
Chris@16:              i != m_vertices.end(); ++i)
Chris@16:           delete (stored_vertex*)*i;
Chris@16:         m_vertices.clear();
Chris@16:         m_edges.clear();
Chris@16:       }
Chris@16:       inline adj_list_impl(vertices_size_type num_vertices) {
Chris@16:         for (vertices_size_type i = 0; i < num_vertices; ++i)
Chris@16:           add_vertex(static_cast<Derived&>(*this));
Chris@16:       }
Chris@16:       template <class EdgeIterator>
Chris@16:       inline adj_list_impl(vertices_size_type num_vertices,
Chris@16:                            EdgeIterator first, EdgeIterator last)
Chris@16:       {
Chris@16:         vertex_descriptor* v = new vertex_descriptor[num_vertices];
Chris@16:         for (vertices_size_type i = 0; i < num_vertices; ++i)
Chris@16:           v[i] = add_vertex(static_cast<Derived&>(*this));
Chris@16: 
Chris@16:         while (first != last) {
Chris@16:           add_edge(v[(*first).first], v[(*first).second], *this);
Chris@16:           ++first;
Chris@16:         }
Chris@16:         delete [] v;
Chris@16:       }
Chris@16:       template <class EdgeIterator, class EdgePropertyIterator>
Chris@16:       inline adj_list_impl(vertices_size_type num_vertices,
Chris@16:                            EdgeIterator first, EdgeIterator last,
Chris@16:                            EdgePropertyIterator ep_iter)
Chris@16:       {
Chris@16:         vertex_descriptor* v = new vertex_descriptor[num_vertices];
Chris@16:         for (vertices_size_type i = 0; i < num_vertices; ++i)
Chris@16:           v[i] = add_vertex(static_cast<Derived&>(*this));
Chris@16: 
Chris@16:         while (first != last) {
Chris@16:           add_edge(v[(*first).first], v[(*first).second], *ep_iter, *this);
Chris@16:           ++first;
Chris@16:           ++ep_iter;
Chris@16:         }
Chris@16:         delete [] v;
Chris@16:       }
Chris@16:       ~adj_list_impl() {
Chris@16:         for (typename StoredVertexList::iterator i = m_vertices.begin();
Chris@16:              i != m_vertices.end(); ++i)
Chris@16:           delete (stored_vertex*)*i;
Chris@16:       }
Chris@16:       //    protected:
Chris@16:       inline OutEdgeList& out_edge_list(vertex_descriptor v) {
Chris@16:         stored_vertex* sv = (stored_vertex*)v;
Chris@16:         return sv->m_out_edges;
Chris@16:       }
Chris@16:       inline const OutEdgeList& out_edge_list(vertex_descriptor v) const {
Chris@16:         stored_vertex* sv = (stored_vertex*)v;
Chris@16:         return sv->m_out_edges;
Chris@16:       }
Chris@16:       inline StoredVertexList& vertex_set() { return m_vertices; }
Chris@16:       inline const StoredVertexList& vertex_set() const { return m_vertices; }
Chris@16: 
Chris@16:       inline void copy_impl(const adj_list_impl& x_)
Chris@16:       {
Chris@16:         const Derived& x = static_cast<const Derived&>(x_);
Chris@16: 
Chris@16:         // Would be better to have a constant time way to get from
Chris@16:         // vertices in x to the corresponding vertices in *this.
Chris@16:         std::map<stored_vertex*,stored_vertex*> vertex_map;
Chris@16: 
Chris@16:         // Copy the stored vertex objects by adding each vertex
Chris@16:         // and copying its property object.
Chris@16:         vertex_iterator vi, vi_end;
Chris@16:         for (boost::tie(vi, vi_end) = vertices(x); vi != vi_end; ++vi) {
Chris@16:           stored_vertex* v = (stored_vertex*)add_vertex(*this);
Chris@16:           v->m_property = ((stored_vertex*)*vi)->m_property;
Chris@16:           vertex_map[(stored_vertex*)*vi] = v;
Chris@16:         }
Chris@16:         // Copy the edges by adding each edge and copying its
Chris@16:         // property object.
Chris@16:         edge_iterator ei, ei_end;
Chris@16:         for (boost::tie(ei, ei_end) = edges(x); ei != ei_end; ++ei) {
Chris@16:           edge_descriptor e;
Chris@16:           bool inserted;
Chris@16:           vertex_descriptor s = source(*ei,x), t = target(*ei,x);
Chris@16:           boost::tie(e, inserted) = add_edge(vertex_map[(stored_vertex*)s],
Chris@16:                                              vertex_map[(stored_vertex*)t], *this);
Chris@16:           *((edge_property_type*)e.m_eproperty)
Chris@16:             = *((edge_property_type*)(*ei).m_eproperty);
Chris@16:         }
Chris@16:       }
Chris@16: 
Chris@16: 
Chris@16:       typename Config::EdgeContainer m_edges;
Chris@16:       StoredVertexList m_vertices;
Chris@16:     };
Chris@16: 
Chris@16:     // O(1)
Chris@16:     template <class Derived, class Config, class Base>
Chris@16:     inline typename Config::vertex_descriptor
Chris@16:     add_vertex(adj_list_impl<Derived, Config, Base>& g_)
Chris@16:     {
Chris@16:       Derived& g = static_cast<Derived&>(g_);
Chris@16:       typedef typename Config::stored_vertex stored_vertex;
Chris@16:       stored_vertex* v = new stored_vertex;
Chris@16:       typename Config::StoredVertexList::iterator pos;
Chris@16:       bool inserted;
Chris@16:       boost::tie(pos,inserted) = boost::graph_detail::push(g.m_vertices, v);
Chris@16:       v->m_position = pos;
Chris@16:       g.added_vertex(v);
Chris@16:       return v;
Chris@16:     }
Chris@16:     // O(1)
Chris@16:     template <class Derived, class Config, class Base>
Chris@16:     inline typename Config::vertex_descriptor
Chris@16:     add_vertex(const typename Config::vertex_property_type& p,
Chris@16:                adj_list_impl<Derived, Config, Base>& g_)
Chris@16:     {
Chris@16:       typedef typename Config::vertex_descriptor vertex_descriptor;
Chris@16:       Derived& g = static_cast<Derived&>(g_);
Chris@16:       if (optional<vertex_descriptor> v
Chris@16:             = g.vertex_by_property(get_property_value(p, vertex_bundle)))
Chris@16:         return *v;
Chris@16: 
Chris@16:       typedef typename Config::stored_vertex stored_vertex;
Chris@16:       stored_vertex* v = new stored_vertex(p);
Chris@16:       typename Config::StoredVertexList::iterator pos;
Chris@16:       bool inserted;
Chris@16:       boost::tie(pos,inserted) = boost::graph_detail::push(g.m_vertices, v);
Chris@16:       v->m_position = pos;
Chris@16:       g.added_vertex(v);
Chris@16:       return v;
Chris@16:     }
Chris@16:     // O(1)
Chris@16:     template <class Derived, class Config, class Base>
Chris@16:     inline void remove_vertex(typename Config::vertex_descriptor u,
Chris@16:                               adj_list_impl<Derived, Config, Base>& g_)
Chris@16:     {
Chris@16:       typedef typename Config::stored_vertex stored_vertex;
Chris@16:       Derived& g = static_cast<Derived&>(g_);
Chris@16:       g.removing_vertex(u, boost::graph_detail::iterator_stability(g_.m_vertices));
Chris@16:       stored_vertex* su = (stored_vertex*)u;
Chris@16:       g.m_vertices.erase(su->m_position);
Chris@16:       delete su;
Chris@16:     }
Chris@16:     // O(V)
Chris@16:     template <class Derived, class Config, class Base>
Chris@16:     inline typename Config::vertex_descriptor
Chris@16:     vertex(typename Config::vertices_size_type n,
Chris@16:            const adj_list_impl<Derived, Config, Base>& g_)
Chris@16:     {
Chris@16:       const Derived& g = static_cast<const Derived&>(g_);
Chris@16:       typename Config::vertex_iterator i = vertices(g).first;
Chris@16:       while (n--) ++i; // std::advance(i, n); (not VC++ portable)
Chris@16:       return *i;
Chris@16:     }
Chris@16: 
Chris@16:     //=========================================================================
Chris@16:     // Vector-Backbone Adjacency List Implementation
Chris@16: 
Chris@16:     namespace detail {
Chris@16: 
Chris@16:       template <class Graph, class vertex_descriptor>
Chris@16:       inline void
Chris@16:       remove_vertex_dispatch(Graph& g, vertex_descriptor u,
Chris@16:                              boost::directed_tag)
Chris@16:       {
Chris@16:         typedef typename Graph::edge_parallel_category edge_parallel_category;
Chris@16:         g.m_vertices.erase(g.m_vertices.begin() + u);
Chris@16:         vertex_descriptor V = num_vertices(g);
Chris@16:         if (u != V) {
Chris@16:           for (vertex_descriptor v = 0; v < V; ++v)
Chris@16:             reindex_edge_list(g.out_edge_list(v), u, edge_parallel_category());
Chris@16:         }
Chris@16:       }
Chris@16: 
Chris@16:       template <class Graph, class vertex_descriptor>
Chris@16:       inline void
Chris@16:       remove_vertex_dispatch(Graph& g, vertex_descriptor u,
Chris@16:                              boost::undirected_tag)
Chris@16:       {
Chris@16:         typedef typename Graph::global_edgelist_selector EdgeListS;
Chris@16:         BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
Chris@16: 
Chris@16:         typedef typename Graph::edge_parallel_category edge_parallel_category;
Chris@16:         g.m_vertices.erase(g.m_vertices.begin() + u);
Chris@16:         vertex_descriptor V = num_vertices(g);
Chris@16:         for (vertex_descriptor v = 0; v < V; ++v)
Chris@16:           reindex_edge_list(g.out_edge_list(v), u,
Chris@16:                             edge_parallel_category());
Chris@16:         typedef typename Graph::EdgeContainer Container;
Chris@16:         typedef typename Container::iterator Iter;
Chris@16:         Iter ei = g.m_edges.begin(), ei_end = g.m_edges.end();
Chris@16:         for (; ei != ei_end; ++ei) {
Chris@16:           if (ei->m_source > u)
Chris@16:             --ei->m_source;
Chris@16:           if (ei->m_target > u)
Chris@16:             --ei->m_target;
Chris@16:         }
Chris@16:       }
Chris@16:       template <class Graph, class vertex_descriptor>
Chris@16:       inline void
Chris@16:       remove_vertex_dispatch(Graph& g, vertex_descriptor u,
Chris@16:                              boost::bidirectional_tag)
Chris@16:       {
Chris@16:         typedef typename Graph::global_edgelist_selector EdgeListS;
Chris@16:         BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
Chris@16: 
Chris@16:         typedef typename Graph::edge_parallel_category edge_parallel_category;
Chris@16:         g.m_vertices.erase(g.m_vertices.begin() + u);
Chris@16:         vertex_descriptor V = num_vertices(g);
Chris@16:         vertex_descriptor v;
Chris@16:         if (u != V) {
Chris@16:           for (v = 0; v < V; ++v)
Chris@16:             reindex_edge_list(g.out_edge_list(v), u,
Chris@16:                               edge_parallel_category());
Chris@16:           for (v = 0; v < V; ++v)
Chris@16:             reindex_edge_list(in_edge_list(g, v), u,
Chris@16:                               edge_parallel_category());
Chris@16: 
Chris@16:           typedef typename Graph::EdgeContainer Container;
Chris@16:           typedef typename Container::iterator Iter;
Chris@16:           Iter ei = g.m_edges.begin(), ei_end = g.m_edges.end();
Chris@16:           for (; ei != ei_end; ++ei) {
Chris@16:             if (ei->m_source > u)
Chris@16:               --ei->m_source;
Chris@16:             if (ei->m_target > u)
Chris@16:               --ei->m_target;
Chris@16:           }
Chris@16:         }
Chris@16:       }
Chris@16: 
Chris@16:       template <class EdgeList, class vertex_descriptor>
Chris@16:       inline void
Chris@16:       reindex_edge_list(EdgeList& el, vertex_descriptor u,
Chris@16:                         boost::allow_parallel_edge_tag)
Chris@16:       {
Chris@16:         typename EdgeList::iterator ei = el.begin(), e_end = el.end();
Chris@16:         for (; ei != e_end; ++ei)
Chris@16:           if ((*ei).get_target() > u)
Chris@16:             --(*ei).get_target();
Chris@16:       }
Chris@16:       template <class EdgeList, class vertex_descriptor>
Chris@16:       inline void
Chris@16:       reindex_edge_list(EdgeList& el, vertex_descriptor u,
Chris@16:                         boost::disallow_parallel_edge_tag)
Chris@16:       {
Chris@16:         typename EdgeList::iterator ei = el.begin(), e_end = el.end();
Chris@16:         while (ei != e_end) {
Chris@16:           typename EdgeList::value_type ce = *ei;
Chris@16:           ++ei;
Chris@16:           if (ce.get_target() > u) {
Chris@16:             el.erase(ce);
Chris@16:             --ce.get_target();
Chris@16:             el.insert(ce);
Chris@16:           }
Chris@16:         }
Chris@16:       }
Chris@16:     } // namespace detail
Chris@16: 
Chris@16:     struct vec_adj_list_tag { };
Chris@16: 
Chris@16:     template <class Graph, class Config, class Base>
Chris@16:     class vec_adj_list_impl
Chris@16:       : public adj_list_helper<Config, Base>
Chris@16:     {
Chris@16:       typedef typename Config::OutEdgeList OutEdgeList;
Chris@16:       typedef typename Config::InEdgeList InEdgeList;
Chris@16:       typedef typename Config::StoredVertexList StoredVertexList;
Chris@16:     public:
Chris@16:       typedef typename Config::vertex_descriptor vertex_descriptor;
Chris@16:       typedef typename Config::edge_descriptor edge_descriptor;
Chris@16:       typedef typename Config::out_edge_iterator out_edge_iterator;
Chris@16:       typedef typename Config::edge_iterator edge_iterator;
Chris@16:       typedef typename Config::directed_category directed_category;
Chris@16:       typedef typename Config::vertices_size_type vertices_size_type;
Chris@16:       typedef typename Config::edges_size_type edges_size_type;
Chris@16:       typedef typename Config::degree_size_type degree_size_type;
Chris@16:       typedef typename Config::StoredEdge StoredEdge;
Chris@16:       typedef typename Config::stored_vertex stored_vertex;
Chris@16:       typedef typename Config::EdgeContainer EdgeContainer;
Chris@16:       typedef typename Config::edge_property_type edge_property_type;
Chris@16:       typedef vec_adj_list_tag graph_tag;
Chris@16: 
Chris@16:       static vertex_descriptor null_vertex()
Chris@16:       {
Chris@16:         return (std::numeric_limits<vertex_descriptor>::max)();
Chris@16:       }
Chris@16: 
Chris@16:       inline vec_adj_list_impl() { }
Chris@16: 
Chris@16:       inline vec_adj_list_impl(const vec_adj_list_impl& x) {
Chris@16:         copy_impl(x);
Chris@16:       }
Chris@16:       inline vec_adj_list_impl& operator=(const vec_adj_list_impl& x) {
Chris@16:         this->clear();
Chris@16:         copy_impl(x);
Chris@16:         return *this;
Chris@16:       }
Chris@16:       inline void clear() {
Chris@16:         m_vertices.clear();
Chris@16:         m_edges.clear();
Chris@16:       }
Chris@16: 
Chris@16:       inline vec_adj_list_impl(vertices_size_type _num_vertices)
Chris@16:         : m_vertices(_num_vertices) { }
Chris@16: 
Chris@16:       template <class EdgeIterator>
Chris@16:       inline vec_adj_list_impl(vertices_size_type num_vertices,
Chris@16:                                EdgeIterator first, EdgeIterator last)
Chris@16:         : m_vertices(num_vertices)
Chris@16:       {
Chris@16:         while (first != last) {
Chris@16:           add_edge((*first).first, (*first).second,
Chris@16:                    static_cast<Graph&>(*this));
Chris@16:           ++first;
Chris@16:         }
Chris@16:       }
Chris@16:       template <class EdgeIterator, class EdgePropertyIterator>
Chris@16:       inline vec_adj_list_impl(vertices_size_type num_vertices,
Chris@16:                                EdgeIterator first, EdgeIterator last,
Chris@16:                                EdgePropertyIterator ep_iter)
Chris@16:         : m_vertices(num_vertices)
Chris@16:       {
Chris@16:         while (first != last) {
Chris@16:           add_edge((*first).first, (*first).second, *ep_iter,
Chris@16:                    static_cast<Graph&>(*this));
Chris@16:           ++first;
Chris@16:           ++ep_iter;
Chris@16:         }
Chris@16:       }
Chris@16: 
Chris@16:       //    protected:
Chris@16:       inline boost::integer_range<vertex_descriptor> vertex_set() const {
Chris@16:         return boost::integer_range<vertex_descriptor>(0, m_vertices.size());
Chris@16:       }
Chris@16:       inline OutEdgeList& out_edge_list(vertex_descriptor v) {
Chris@16:         return m_vertices[v].m_out_edges;
Chris@16:       }
Chris@16:       inline const OutEdgeList& out_edge_list(vertex_descriptor v) const {
Chris@16:         return m_vertices[v].m_out_edges;
Chris@16:       }
Chris@16:       inline void copy_impl(const vec_adj_list_impl& x_)
Chris@16:       {
Chris@16:         const Graph& x = static_cast<const Graph&>(x_);
Chris@16:         // Copy the stored vertex objects by adding each vertex
Chris@16:         // and copying its property object.
Chris@16:         for (vertices_size_type i = 0; i < num_vertices(x); ++i) {
Chris@16:           vertex_descriptor v = add_vertex(*this);
Chris@16:           m_vertices[v].m_property = x.m_vertices[i].m_property;
Chris@16:         }
Chris@16:         // Copy the edges by adding each edge and copying its
Chris@16:         // property object.
Chris@16:         edge_iterator ei, ei_end;
Chris@16:         for (boost::tie(ei, ei_end) = edges(x); ei != ei_end; ++ei) {
Chris@16:           edge_descriptor e;
Chris@16:           bool inserted;
Chris@16:           boost::tie(e, inserted) = add_edge(source(*ei,x), target(*ei,x) , *this);
Chris@16:           *((edge_property_type*)e.m_eproperty)
Chris@16:             = *((edge_property_type*)(*ei).m_eproperty);
Chris@16:         }
Chris@16:       }
Chris@16:       typename Config::EdgeContainer m_edges;
Chris@16:       StoredVertexList m_vertices;
Chris@16:     };
Chris@16:     // Had to make these non-members to avoid accidental instantiation
Chris@16:     // on SGI MIPSpro C++
Chris@16:     template <class G, class C, class B>
Chris@16:     inline typename C::InEdgeList&
Chris@16:     in_edge_list(vec_adj_list_impl<G,C,B>& g,
Chris@16:                  typename C::vertex_descriptor v) {
Chris@16:       return g.m_vertices[v].m_in_edges;
Chris@16:     }
Chris@16:     template <class G, class C, class B>
Chris@16:     inline const typename C::InEdgeList&
Chris@16:     in_edge_list(const vec_adj_list_impl<G,C,B>& g,
Chris@16:                  typename C::vertex_descriptor v) {
Chris@16:       return g.m_vertices[v].m_in_edges;
Chris@16:     }
Chris@16: 
Chris@16:       // O(1)
Chris@16:     template <class Graph, class Config, class Base>
Chris@16:     inline typename Config::vertex_descriptor
Chris@16:     add_vertex(vec_adj_list_impl<Graph, Config, Base>& g_) {
Chris@16:       Graph& g = static_cast<Graph&>(g_);
Chris@16:       g.m_vertices.resize(g.m_vertices.size() + 1);
Chris@16:       g.added_vertex(g.m_vertices.size() - 1);
Chris@16:       return g.m_vertices.size() - 1;
Chris@16:     }
Chris@16: 
Chris@16:     template <class Graph, class Config, class Base>
Chris@16:     inline typename Config::vertex_descriptor
Chris@16:     add_vertex(const typename Config::vertex_property_type& p,
Chris@16:                vec_adj_list_impl<Graph, Config, Base>& g_) {
Chris@16:       typedef typename Config::vertex_descriptor vertex_descriptor;
Chris@16:       Graph& g = static_cast<Graph&>(g_);
Chris@16:       if (optional<vertex_descriptor> v
Chris@16:             = g.vertex_by_property(get_property_value(p, vertex_bundle)))
Chris@16:         return *v;
Chris@16:       typedef typename Config::stored_vertex stored_vertex;
Chris@16:       g.m_vertices.push_back(stored_vertex(p));
Chris@16:       g.added_vertex(g.m_vertices.size() - 1);
Chris@16:       return g.m_vertices.size() - 1;
Chris@16:     }
Chris@16: 
Chris@16:     // Here we override the directed_graph_helper add_edge() function
Chris@16:     // so that the number of vertices is automatically changed if
Chris@16:     // either u or v is greater than the number of vertices.
Chris@16:     template <class Graph, class Config, class Base>
Chris@16:     inline std::pair<typename Config::edge_descriptor, bool>
Chris@16:     add_edge(typename Config::vertex_descriptor u,
Chris@16:              typename Config::vertex_descriptor v,
Chris@16:              const typename Config::edge_property_type& p,
Chris@16:              vec_adj_list_impl<Graph, Config, Base>& g_)
Chris@16:     {
Chris@16:       BOOST_USING_STD_MAX();
Chris@16:       typename Config::vertex_descriptor x = max BOOST_PREVENT_MACRO_SUBSTITUTION(u, v);
Chris@16:       if (x >= num_vertices(g_))
Chris@16:         g_.m_vertices.resize(x + 1);
Chris@16:       adj_list_helper<Config, Base>& g = g_;
Chris@16:       return add_edge(u, v, p, g);
Chris@16:     }
Chris@16:     template <class Graph, class Config, class Base>
Chris@16:     inline std::pair<typename Config::edge_descriptor, bool>
Chris@16:     add_edge(typename Config::vertex_descriptor u,
Chris@16:              typename Config::vertex_descriptor v,
Chris@16:              vec_adj_list_impl<Graph, Config, Base>& g_)
Chris@16:     {
Chris@16:       typename Config::edge_property_type p;
Chris@16:       return add_edge(u, v, p, g_);
Chris@16:     }
Chris@16: 
Chris@16: 
Chris@16:     // O(V + E)
Chris@16:     template <class Graph, class Config, class Base>
Chris@16:     inline void remove_vertex(typename Config::vertex_descriptor v,
Chris@16:                               vec_adj_list_impl<Graph, Config, Base>& g_)
Chris@16:     {
Chris@16:       typedef typename Config::directed_category Cat;
Chris@16:       Graph& g = static_cast<Graph&>(g_);
Chris@16:       g.removing_vertex(v, boost::graph_detail::iterator_stability(g_.m_vertices));
Chris@16:       detail::remove_vertex_dispatch(g, v, Cat());
Chris@16:     }
Chris@16:     // O(1)
Chris@16:     template <class Graph, class Config, class Base>
Chris@16:     inline typename Config::vertex_descriptor
Chris@16:     vertex(typename Config::vertices_size_type n,
Chris@16:            const vec_adj_list_impl<Graph, Config, Base>&)
Chris@16:     {
Chris@16:       return n;
Chris@16:     }
Chris@16: 
Chris@16: 
Chris@16:   namespace detail {
Chris@16: 
Chris@16:     //=========================================================================
Chris@16:     // Adjacency List Generator
Chris@16: 
Chris@16:     template <class Graph, class VertexListS, class OutEdgeListS,
Chris@16:               class DirectedS, class VertexProperty, class EdgeProperty,
Chris@16:               class GraphProperty, class EdgeListS>
Chris@16:     struct adj_list_gen
Chris@16:     {
Chris@16:       typedef typename detail::is_random_access<VertexListS>::type
Chris@16:         is_rand_access;
Chris@16:       typedef typename has_property<EdgeProperty>::type has_edge_property;
Chris@16:       typedef typename DirectedS::is_directed_t DirectedT;
Chris@16:       typedef typename DirectedS::is_bidir_t BidirectionalT;
Chris@16: 
Chris@16:       struct config
Chris@16:       {
Chris@16:         typedef OutEdgeListS edgelist_selector;
Chris@16:         typedef EdgeListS global_edgelist_selector;
Chris@16: 
Chris@16:         typedef Graph graph_type;
Chris@16:         typedef EdgeProperty edge_property_type;
Chris@16:         typedef VertexProperty vertex_property_type;
Chris@16:         typedef GraphProperty graph_property_type;
Chris@16:         typedef std::size_t vertices_size_type;
Chris@16: 
Chris@16:         typedef adjacency_list_traits<OutEdgeListS, VertexListS, DirectedS>
Chris@16:            Traits;
Chris@16: 
Chris@16:         typedef typename Traits::directed_category directed_category;
Chris@16:         typedef typename Traits::edge_parallel_category edge_parallel_category;
Chris@16:         typedef typename Traits::vertex_descriptor vertex_descriptor;
Chris@16:         typedef typename Traits::edge_descriptor edge_descriptor;
Chris@16: 
Chris@16:         typedef void* vertex_ptr;
Chris@16: 
Chris@16:         // need to reorganize this to avoid instantiating stuff
Chris@16:         // that doesn't get used -JGS
Chris@16: 
Chris@16:         // VertexList and vertex_iterator
Chris@16:         typedef typename container_gen<VertexListS,
Chris@16:           vertex_ptr>::type SeqVertexList;
Chris@16:         typedef boost::integer_range<vertex_descriptor> RandVertexList;
Chris@16:         typedef typename mpl::if_<is_rand_access,
Chris@16:           RandVertexList, SeqVertexList>::type VertexList;
Chris@16: 
Chris@16:         typedef typename VertexList::iterator vertex_iterator;
Chris@16: 
Chris@16:         // EdgeContainer and StoredEdge
Chris@16: 
Chris@16:         typedef typename container_gen<EdgeListS,
Chris@16:           list_edge<vertex_descriptor, EdgeProperty> >::type EdgeContainer;
Chris@16: 
Chris@16:         typedef typename mpl::and_<DirectedT,
Chris@16:              typename mpl::not_<BidirectionalT>::type >::type on_edge_storage;
Chris@16: 
Chris@16:         typedef typename mpl::if_<on_edge_storage,
Chris@16:           std::size_t, typename EdgeContainer::size_type
Chris@16:         >::type edges_size_type;
Chris@16: 
Chris@16:         typedef typename EdgeContainer::iterator EdgeIter;
Chris@16: 
Chris@16:         typedef typename detail::is_random_access<EdgeListS>::type is_edge_ra;
Chris@16: 
Chris@16:         typedef typename mpl::if_<on_edge_storage,
Chris@16:           stored_edge_property<vertex_descriptor, EdgeProperty>,
Chris@16:           typename mpl::if_<is_edge_ra,
Chris@16:             stored_ra_edge_iter<vertex_descriptor, EdgeContainer, EdgeProperty>,
Chris@16:             stored_edge_iter<vertex_descriptor, EdgeIter, EdgeProperty>
Chris@16:           >::type
Chris@16:         >::type StoredEdge;
Chris@16: 
Chris@16:         // Adjacency Types
Chris@16: 
Chris@16:         typedef typename container_gen<OutEdgeListS, StoredEdge>::type
Chris@16:           OutEdgeList;
Chris@16:         typedef typename OutEdgeList::size_type degree_size_type;
Chris@16:         typedef typename OutEdgeList::iterator OutEdgeIter;
Chris@16: 
Chris@16:         typedef boost::detail::iterator_traits<OutEdgeIter> OutEdgeIterTraits;
Chris@16:         typedef typename OutEdgeIterTraits::iterator_category OutEdgeIterCat;
Chris@16:         typedef typename OutEdgeIterTraits::difference_type OutEdgeIterDiff;
Chris@16: 
Chris@16:         typedef out_edge_iter<
Chris@16:             OutEdgeIter, vertex_descriptor, edge_descriptor, OutEdgeIterDiff
Chris@16:         > out_edge_iterator;
Chris@16: 
Chris@16:         typedef typename adjacency_iterator_generator<graph_type,
Chris@16:            vertex_descriptor, out_edge_iterator>::type adjacency_iterator;
Chris@16: 
Chris@16:         typedef OutEdgeList InEdgeList;
Chris@16:         typedef OutEdgeIter InEdgeIter;
Chris@16:         typedef OutEdgeIterCat InEdgeIterCat;
Chris@16:         typedef OutEdgeIterDiff InEdgeIterDiff;
Chris@16: 
Chris@16:         typedef in_edge_iter<
Chris@16:             InEdgeIter, vertex_descriptor, edge_descriptor, InEdgeIterDiff
Chris@16:         > in_edge_iterator;
Chris@16: 
Chris@16:         typedef typename inv_adjacency_iterator_generator<graph_type,
Chris@16:            vertex_descriptor, in_edge_iterator>::type inv_adjacency_iterator;
Chris@16: 
Chris@16:         // Edge Iterator
Chris@16: 
Chris@16:         typedef boost::detail::iterator_traits<EdgeIter> EdgeIterTraits;
Chris@16:         typedef typename EdgeIterTraits::iterator_category EdgeIterCat;
Chris@16:         typedef typename EdgeIterTraits::difference_type EdgeIterDiff;
Chris@16: 
Chris@16:         typedef undirected_edge_iter<
Chris@16:             EdgeIter
Chris@16:           , edge_descriptor
Chris@16:           , EdgeIterDiff
Chris@16:         > UndirectedEdgeIter; // also used for bidirectional
Chris@16: 
Chris@16:         typedef adj_list_edge_iterator<vertex_iterator, out_edge_iterator,
Chris@16:            graph_type> DirectedEdgeIter;
Chris@16: 
Chris@16:         typedef typename mpl::if_<on_edge_storage,
Chris@16:           DirectedEdgeIter, UndirectedEdgeIter>::type edge_iterator;
Chris@16: 
Chris@16:         // stored_vertex and StoredVertexList
Chris@16:         typedef typename container_gen<VertexListS, vertex_ptr>::type
Chris@16:           SeqStoredVertexList;
Chris@16:         struct seq_stored_vertex {
Chris@16:           seq_stored_vertex() { }
Chris@16:           seq_stored_vertex(const VertexProperty& p) : m_property(p) { }
Chris@16:           OutEdgeList m_out_edges;
Chris@16:           VertexProperty m_property;
Chris@16:           typename SeqStoredVertexList::iterator m_position;
Chris@16:         };
Chris@16:         struct bidir_seq_stored_vertex {
Chris@16:           bidir_seq_stored_vertex() { }
Chris@16:           bidir_seq_stored_vertex(const VertexProperty& p) : m_property(p) { }
Chris@16:           OutEdgeList m_out_edges;
Chris@16:           InEdgeList m_in_edges;
Chris@16:           VertexProperty m_property;
Chris@16:           typename SeqStoredVertexList::iterator m_position;
Chris@16:         };
Chris@16:         struct rand_stored_vertex {
Chris@16:           rand_stored_vertex() { }
Chris@16:           rand_stored_vertex(const VertexProperty& p) : m_property(p) { }
Chris@16:           OutEdgeList m_out_edges;
Chris@16:           VertexProperty m_property;
Chris@16:         };
Chris@16:         struct bidir_rand_stored_vertex {
Chris@16:           bidir_rand_stored_vertex() { }
Chris@16:           bidir_rand_stored_vertex(const VertexProperty& p) : m_property(p) { }
Chris@16:           OutEdgeList m_out_edges;
Chris@16:           InEdgeList m_in_edges;
Chris@16:           VertexProperty m_property;
Chris@16:         };
Chris@16:         typedef typename mpl::if_<is_rand_access,
Chris@16:           typename mpl::if_<BidirectionalT,
Chris@16:             bidir_rand_stored_vertex, rand_stored_vertex>::type,
Chris@16:           typename mpl::if_<BidirectionalT,
Chris@16:             bidir_seq_stored_vertex, seq_stored_vertex>::type
Chris@16:         >::type StoredVertex;
Chris@16:         struct stored_vertex : public StoredVertex {
Chris@16:           stored_vertex() { }
Chris@16:           stored_vertex(const VertexProperty& p) : StoredVertex(p) { }
Chris@16:         };
Chris@16: 
Chris@16:         typedef typename container_gen<VertexListS, stored_vertex>::type
Chris@16:           RandStoredVertexList;
Chris@16:         typedef typename mpl::if_< is_rand_access,
Chris@16:           RandStoredVertexList, SeqStoredVertexList>::type StoredVertexList;
Chris@16:       }; // end of config
Chris@16: 
Chris@16: 
Chris@16:       typedef typename mpl::if_<BidirectionalT,
Chris@16:         bidirectional_graph_helper_with_property<config>,
Chris@16:         typename mpl::if_<DirectedT,
Chris@16:           directed_graph_helper<config>,
Chris@16:           undirected_graph_helper<config>
Chris@16:         >::type
Chris@16:       >::type DirectedHelper;
Chris@16: 
Chris@16:       typedef typename mpl::if_<is_rand_access,
Chris@16:         vec_adj_list_impl<Graph, config, DirectedHelper>,
Chris@16:         adj_list_impl<Graph, config, DirectedHelper>
Chris@16:       >::type type;
Chris@16: 
Chris@16:     };
Chris@16: 
Chris@16:   } // namespace detail
Chris@16: 
Chris@16:     //=========================================================================
Chris@16:     // Vertex Property Maps
Chris@16: 
Chris@16:     template <class Graph, class ValueType, class Reference, class Tag>
Chris@16:     struct adj_list_vertex_property_map
Chris@16:       : public boost::put_get_helper<
Chris@16:           Reference,
Chris@16:           adj_list_vertex_property_map<Graph, ValueType, Reference, Tag>
Chris@16:         >
Chris@16:     {
Chris@16:       typedef typename Graph::stored_vertex StoredVertex;
Chris@16:       typedef ValueType value_type;
Chris@16:       typedef Reference reference;
Chris@16:       typedef typename Graph::vertex_descriptor key_type;
Chris@16:       typedef boost::lvalue_property_map_tag category;
Chris@16:       inline adj_list_vertex_property_map(const Graph* = 0, Tag tag = Tag()): m_tag(tag) { }
Chris@16:       inline Reference operator[](key_type v) const {
Chris@16:         StoredVertex* sv = (StoredVertex*)v;
Chris@16:         return get_property_value(sv->m_property, m_tag);
Chris@16:       }
Chris@16:       inline Reference operator()(key_type v) const {
Chris@16:         return this->operator[](v);
Chris@16:       }
Chris@16:       Tag m_tag;
Chris@16:     };
Chris@16: 
Chris@16:     template <class Graph, class Property, class PropRef>
Chris@16:     struct adj_list_vertex_all_properties_map
Chris@16:       : public boost::put_get_helper<PropRef,
Chris@16:           adj_list_vertex_all_properties_map<Graph, Property, PropRef>
Chris@16:         >
Chris@16:     {
Chris@16:       typedef typename Graph::stored_vertex StoredVertex;
Chris@16:       typedef Property value_type;
Chris@16:       typedef PropRef reference;
Chris@16:       typedef typename Graph::vertex_descriptor key_type;
Chris@16:       typedef boost::lvalue_property_map_tag category;
Chris@16:       inline adj_list_vertex_all_properties_map(const Graph* = 0, vertex_all_t = vertex_all_t()) { }
Chris@16:       inline PropRef operator[](key_type v) const {
Chris@16:         StoredVertex* sv = (StoredVertex*)v;
Chris@16:         return sv->m_property;
Chris@16:       }
Chris@16:       inline PropRef operator()(key_type v) const {
Chris@16:         return this->operator[](v);
Chris@16:       }
Chris@16:     };
Chris@16: 
Chris@16:     template <class Graph, class GraphPtr, class ValueType, class Reference,
Chris@16:               class Tag>
Chris@16:     struct vec_adj_list_vertex_property_map
Chris@16:       : public boost::put_get_helper<
Chris@16:           Reference,
Chris@16:           vec_adj_list_vertex_property_map<Graph,GraphPtr,ValueType,Reference,
Chris@16:              Tag>
Chris@16:         >
Chris@16:     {
Chris@16:       typedef ValueType value_type;
Chris@16:       typedef Reference reference;
Chris@16:       typedef typename boost::graph_traits<Graph>::vertex_descriptor key_type;
Chris@16:       typedef boost::lvalue_property_map_tag category;
Chris@16:       vec_adj_list_vertex_property_map(GraphPtr g = 0, Tag tag = Tag()) : m_g(g), m_tag(tag) { }
Chris@16:       inline Reference operator[](key_type v) const {
Chris@16:         return get_property_value(m_g->m_vertices[v].m_property, m_tag);
Chris@16:       }
Chris@16:       inline Reference operator()(key_type v) const {
Chris@16:         return this->operator[](v);
Chris@16:       }
Chris@16:       GraphPtr m_g;
Chris@16:       Tag m_tag;
Chris@16:     };
Chris@16: 
Chris@16:     template <class Graph, class GraphPtr, class Property, class PropertyRef>
Chris@16:     struct vec_adj_list_vertex_all_properties_map
Chris@16:       : public boost::put_get_helper<PropertyRef,
Chris@16:           vec_adj_list_vertex_all_properties_map<Graph,GraphPtr,Property,
Chris@16:             PropertyRef>
Chris@16:         >
Chris@16:     {
Chris@16:       typedef Property value_type;
Chris@16:       typedef PropertyRef reference;
Chris@16:       typedef typename boost::graph_traits<Graph>::vertex_descriptor key_type;
Chris@16:       typedef boost::lvalue_property_map_tag category;
Chris@16:       vec_adj_list_vertex_all_properties_map(GraphPtr g = 0, vertex_all_t = vertex_all_t()) : m_g(g) { }
Chris@16:       inline PropertyRef operator[](key_type v) const {
Chris@16:         return m_g->m_vertices[v].m_property;
Chris@16:       }
Chris@16:       inline PropertyRef operator()(key_type v) const {
Chris@16:         return this->operator[](v);
Chris@16:       }
Chris@16:       GraphPtr m_g;
Chris@16:     };
Chris@16: 
Chris@16:     struct adj_list_any_vertex_pa {
Chris@16:       template <class Tag, class Graph, class Property>
Chris@16:       struct bind_ {
Chris@16:         typedef typename property_value<Property, Tag>::type value_type;
Chris@16:         typedef value_type& reference;
Chris@16:         typedef const value_type& const_reference;
Chris@16: 
Chris@16:         typedef adj_list_vertex_property_map
Chris@16:           <Graph, value_type, reference, Tag> type;
Chris@16:         typedef adj_list_vertex_property_map
Chris@16:           <Graph, value_type, const_reference, Tag> const_type;
Chris@16:       };
Chris@16:     };
Chris@16:     struct adj_list_all_vertex_pa {
Chris@16:       template <class Tag, class Graph, class Property>
Chris@16:       struct bind_ {
Chris@16:         typedef typename Graph::vertex_descriptor Vertex;
Chris@16:         typedef adj_list_vertex_all_properties_map<Graph,Property,
Chris@16:           Property&> type;
Chris@16:         typedef adj_list_vertex_all_properties_map<Graph,Property,
Chris@16:           const Property&> const_type;
Chris@16:       };
Chris@16:     };
Chris@16: 
Chris@16:     template <class Property, class Vertex>
Chris@16:     struct vec_adj_list_vertex_id_map
Chris@16:       : public boost::put_get_helper<
Chris@16:           Vertex, vec_adj_list_vertex_id_map<Property, Vertex>
Chris@16:         >
Chris@16:     {
Chris@16:       typedef Vertex value_type;
Chris@16:       typedef Vertex key_type;
Chris@16:       typedef Vertex reference;
Chris@16:       typedef boost::readable_property_map_tag category;
Chris@16:       inline vec_adj_list_vertex_id_map() { }
Chris@16:       template <class Graph>
Chris@16:       inline vec_adj_list_vertex_id_map(const Graph&, vertex_index_t) { }
Chris@16:       inline value_type operator[](key_type v) const { return v; }
Chris@16:       inline value_type operator()(key_type v) const { return v; }
Chris@16:     };
Chris@16: 
Chris@16:     struct vec_adj_list_any_vertex_pa {
Chris@16:       template <class Tag, class Graph, class Property>
Chris@16:       struct bind_ {
Chris@16:         typedef typename property_value<Property, Tag>::type value_type;
Chris@16:         typedef value_type& reference;
Chris@16:         typedef const value_type& const_reference;
Chris@16: 
Chris@16:         typedef vec_adj_list_vertex_property_map
Chris@16:           <Graph, Graph*, value_type, reference, Tag> type;
Chris@16:         typedef vec_adj_list_vertex_property_map
Chris@16:           <Graph, const Graph*, value_type, const_reference, Tag> const_type;
Chris@16:       };
Chris@16:     };
Chris@16:     struct vec_adj_list_id_vertex_pa {
Chris@16:       template <class Tag, class Graph, class Property>
Chris@16:       struct bind_ {
Chris@16:         typedef typename Graph::vertex_descriptor Vertex;
Chris@16:         typedef vec_adj_list_vertex_id_map<Property, Vertex> type;
Chris@16:         typedef vec_adj_list_vertex_id_map<Property, Vertex> const_type;
Chris@16:       };
Chris@16:     };
Chris@16:     struct vec_adj_list_all_vertex_pa {
Chris@16:       template <class Tag, class Graph, class Property>
Chris@16:       struct bind_ {
Chris@16:         typedef typename Graph::vertex_descriptor Vertex;
Chris@16:         typedef vec_adj_list_vertex_all_properties_map
Chris@16:           <Graph, Graph*, Property, Property&> type;
Chris@16:         typedef vec_adj_list_vertex_all_properties_map
Chris@16:           <Graph, const Graph*, Property, const Property&> const_type;
Chris@16:       };
Chris@16:     };
Chris@16:   namespace detail {
Chris@16:     template <class Tag, class Graph, class Property>
Chris@16:     struct adj_list_choose_vertex_pa
Chris@16:       : boost::mpl::if_<
Chris@16:           boost::is_same<Tag, vertex_all_t>,
Chris@16:           adj_list_all_vertex_pa,
Chris@16:           adj_list_any_vertex_pa>::type
Chris@16:         ::template bind_<Tag, Graph, Property>
Chris@16:     {};
Chris@16: 
Chris@16: 
Chris@16:     template <class Tag>
Chris@16:     struct vec_adj_list_choose_vertex_pa_helper {
Chris@16:       typedef vec_adj_list_any_vertex_pa type;
Chris@16:     };
Chris@16:     template <>
Chris@16:     struct vec_adj_list_choose_vertex_pa_helper<vertex_index_t> {
Chris@16:       typedef vec_adj_list_id_vertex_pa type;
Chris@16:     };
Chris@16:     template <>
Chris@16:     struct vec_adj_list_choose_vertex_pa_helper<vertex_all_t> {
Chris@16:       typedef vec_adj_list_all_vertex_pa type;
Chris@16:     };
Chris@16:     template <class Tag, class Graph, class Property>
Chris@16:     struct vec_adj_list_choose_vertex_pa
Chris@16:       : vec_adj_list_choose_vertex_pa_helper<Tag>::type::template bind_<Tag,Graph,Property>
Chris@16:     {};
Chris@16:   } // namespace detail
Chris@16: 
Chris@16:     //=========================================================================
Chris@16:     // Edge Property Map
Chris@16: 
Chris@16:     template <class Directed, class Value, class Ref, class Vertex,
Chris@16:               class Property, class Tag>
Chris@16:     struct adj_list_edge_property_map
Chris@16:       : public put_get_helper<
Chris@16:           Ref,
Chris@16:           adj_list_edge_property_map<Directed, Value, Ref, Vertex, Property,
Chris@16:             Tag>
Chris@16:         >
Chris@16:     {
Chris@16:       Tag tag;
Chris@16:       explicit adj_list_edge_property_map(Tag tag = Tag()): tag(tag) {}
Chris@16: 
Chris@16:       typedef Value value_type;
Chris@16:       typedef Ref reference;
Chris@16:       typedef detail::edge_desc_impl<Directed, Vertex> key_type;
Chris@16:       typedef boost::lvalue_property_map_tag category;
Chris@16:       inline Ref operator[](key_type e) const {
Chris@16:         Property& p = *(Property*)e.get_property();
Chris@16:         return get_property_value(p, tag);
Chris@16:       }
Chris@16:       inline Ref operator()(key_type e) const {
Chris@16:         return this->operator[](e);
Chris@16:       }
Chris@16:     };
Chris@16: 
Chris@16:     template <class Directed, class Property, class PropRef, class PropPtr,
Chris@16:       class Vertex>
Chris@16:     struct adj_list_edge_all_properties_map
Chris@16:       : public put_get_helper<PropRef,
Chris@16:           adj_list_edge_all_properties_map<Directed, Property, PropRef,
Chris@16:             PropPtr, Vertex>
Chris@16:         >
Chris@16:     {
Chris@16:       explicit adj_list_edge_all_properties_map(edge_all_t = edge_all_t()) {}
Chris@16:       typedef Property value_type;
Chris@16:       typedef PropRef reference;
Chris@16:       typedef detail::edge_desc_impl<Directed, Vertex> key_type;
Chris@16:       typedef boost::lvalue_property_map_tag category;
Chris@16:       inline PropRef operator[](key_type e) const {
Chris@16:         return *(PropPtr)e.get_property();
Chris@16:       }
Chris@16:       inline PropRef operator()(key_type e) const {
Chris@16:         return this->operator[](e);
Chris@16:       }
Chris@16:     };
Chris@16: 
Chris@16:   // Edge Property Maps
Chris@16: 
Chris@16:   namespace detail {
Chris@16:     struct adj_list_any_edge_pmap {
Chris@16:       template <class Graph, class Property, class Tag>
Chris@16:       struct bind_ {
Chris@16:         typedef typename property_value<Property,Tag>::type value_type;
Chris@16:         typedef value_type& reference;
Chris@16:         typedef const value_type& const_reference;
Chris@16: 
Chris@16:         typedef adj_list_edge_property_map
Chris@16:            <typename Graph::directed_category, value_type, reference,
Chris@16:             typename Graph::vertex_descriptor,Property,Tag> type;
Chris@16:         typedef adj_list_edge_property_map
Chris@16:            <typename Graph::directed_category, value_type, const_reference,
Chris@16:             typename Graph::vertex_descriptor,const Property, Tag> const_type;
Chris@16:       };
Chris@16:     };
Chris@16:     struct adj_list_all_edge_pmap {
Chris@16:       template <class Graph, class Property, class Tag>
Chris@16:       struct bind_ {
Chris@16:         typedef adj_list_edge_all_properties_map
Chris@16:         <typename Graph::directed_category, Property, Property&, Property*,
Chris@16:             typename Graph::vertex_descriptor> type;
Chris@16:         typedef adj_list_edge_all_properties_map
Chris@16:         <typename Graph::directed_category, Property, const Property&,
Chris@16:             const Property*, typename Graph::vertex_descriptor> const_type;
Chris@16:       };
Chris@16:     };
Chris@16: 
Chris@16:     template <class Tag>
Chris@16:     struct adj_list_choose_edge_pmap_helper {
Chris@16:       typedef adj_list_any_edge_pmap type;
Chris@16:     };
Chris@16:     template <>
Chris@16:     struct adj_list_choose_edge_pmap_helper<edge_all_t> {
Chris@16:       typedef adj_list_all_edge_pmap type;
Chris@16:     };
Chris@16:     template <class Tag, class Graph, class Property>
Chris@16:     struct adj_list_choose_edge_pmap
Chris@16:       : adj_list_choose_edge_pmap_helper<Tag>::type::template bind_<Graph, Property, Tag>
Chris@16:       {};
Chris@16:     struct adj_list_edge_property_selector {
Chris@16:       template <class Graph, class Property, class Tag>
Chris@16:       struct bind_: adj_list_choose_edge_pmap<Tag, Graph, Property> {};
Chris@16:     };
Chris@16:   } // namespace detail
Chris@16: 
Chris@16:   template <>
Chris@16:   struct edge_property_selector<adj_list_tag> {
Chris@16:     typedef detail::adj_list_edge_property_selector type;
Chris@16:   };
Chris@16:   template <>
Chris@16:   struct edge_property_selector<vec_adj_list_tag> {
Chris@16:     typedef detail::adj_list_edge_property_selector type;
Chris@16:   };
Chris@16: 
Chris@16:   // Vertex Property Maps
Chris@16: 
Chris@16:   struct adj_list_vertex_property_selector {
Chris@16:     template <class Graph, class Property, class Tag>
Chris@16:     struct bind_
Chris@16:       : detail::adj_list_choose_vertex_pa<Tag,Graph,Property>
Chris@16:     {};
Chris@16:   };
Chris@16:   template <>
Chris@16:   struct vertex_property_selector<adj_list_tag> {
Chris@16:     typedef adj_list_vertex_property_selector type;
Chris@16:   };
Chris@16: 
Chris@16:   struct vec_adj_list_vertex_property_selector {
Chris@16:     template <class Graph, class Property, class Tag>
Chris@16:     struct bind_: detail::vec_adj_list_choose_vertex_pa<Tag,Graph,Property> {};
Chris@16:   };
Chris@16:   template <>
Chris@16:   struct vertex_property_selector<vec_adj_list_tag> {
Chris@16:     typedef vec_adj_list_vertex_property_selector type;
Chris@16:   };
Chris@16: 
Chris@16: } // namespace boost
Chris@16: 
Chris@16: namespace boost {
Chris@16: 
Chris@16:   template <typename V>
Chris@16:   struct hash< boost::detail::stored_edge<V> >
Chris@16:   {
Chris@16:     std::size_t
Chris@16:     operator()(const boost::detail::stored_edge<V>& e) const
Chris@16:     {
Chris@16:       return hash<V>()(e.m_target);
Chris@16:     }
Chris@16:   };
Chris@16: 
Chris@16:   template <typename V, typename P>
Chris@16:   struct hash< boost::detail::stored_edge_property <V,P> >
Chris@16:   {
Chris@16:     std::size_t
Chris@16:     operator()(const boost::detail::stored_edge_property<V,P>& e) const
Chris@16:     {
Chris@16:       return hash<V>()(e.m_target);
Chris@16:     }
Chris@16:   };
Chris@16: 
Chris@16:   template <typename V, typename I, typename P>
Chris@16:   struct hash< boost::detail::stored_edge_iter<V,I, P> >
Chris@16:   {
Chris@16:     std::size_t
Chris@16:     operator()(const boost::detail::stored_edge_iter<V,I,P>& e) const
Chris@16:     {
Chris@16:       return hash<V>()(e.m_target);
Chris@16:     }
Chris@16:   };
Chris@16: 
Chris@16: }
Chris@16: 
Chris@16: 
Chris@16: #endif // BOOST_GRAPH_DETAIL_DETAIL_ADJACENCY_LIST_CCT
Chris@16: 
Chris@16: /*
Chris@16:   Implementation Notes:
Chris@16: 
Chris@16:   Many of the public interface functions in this file would have been
Chris@16:   more conveniently implemented as inline friend functions.
Chris@16:   However there are a few compiler bugs that make that approach
Chris@16:   non-portable.
Chris@16: 
Chris@16:   1. g++ inline friend in namespace bug
Chris@16:   2. g++ using clause doesn't work with inline friends
Chris@16:   3. VC++ doesn't have Koenig lookup
Chris@16: 
Chris@16:   For these reasons, the functions were all written as non-inline free
Chris@16:   functions, and static cast was used to convert from the helper
Chris@16:   class to the adjacency_list derived class.
Chris@16: 
Chris@16:   Looking back, it might have been better to write out all functions
Chris@16:   in terms of the adjacency_list, and then use a tag to dispatch
Chris@16:   to the various helpers instead of using inheritance.
Chris@16: 
Chris@16:  */