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