epoc32/include/stdapis/boost/graph/detail/adjacency_list.hpp
branchSymbian2
changeset 2 2fe1408b6811
     1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/epoc32/include/stdapis/boost/graph/detail/adjacency_list.hpp	Tue Mar 16 16:12:26 2010 +0000
     1.3 @@ -0,0 +1,2832 @@
     1.4 +// -*- c++ -*-
     1.5 +//=======================================================================
     1.6 +// Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
     1.7 +// Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek
     1.8 +//
     1.9 +// Distributed under the Boost Software License, Version 1.0. (See
    1.10 +// accompanying file LICENSE_1_0.txt or copy at
    1.11 +// http://www.boost.org/LICENSE_1_0.txt)
    1.12 +//=======================================================================
    1.13 +
    1.14 +#ifndef BOOST_GRAPH_DETAIL_ADJACENCY_LIST_HPP
    1.15 +#define BOOST_GRAPH_DETAIL_ADJACENCY_LIST_HPP
    1.16 +
    1.17 +#include <map> // for vertex_map in copy_impl
    1.18 +#include <boost/config.hpp>
    1.19 +#include <boost/detail/workaround.hpp>
    1.20 +#include <boost/operators.hpp>
    1.21 +#include <boost/property_map.hpp>
    1.22 +#include <boost/pending/integer_range.hpp>
    1.23 +#include <boost/graph/graph_traits.hpp>
    1.24 +#include <memory>
    1.25 +#include <algorithm>
    1.26 +#include <boost/limits.hpp>
    1.27 +
    1.28 +#include <boost/iterator/iterator_adaptor.hpp>
    1.29 +
    1.30 +#include <boost/pending/ct_if.hpp>
    1.31 +#include <boost/graph/graph_concepts.hpp>
    1.32 +#include <boost/pending/container_traits.hpp>
    1.33 +#include <boost/graph/detail/adj_list_edge_iterator.hpp>
    1.34 +#include <boost/graph/properties.hpp>
    1.35 +#include <boost/pending/property.hpp>
    1.36 +#include <boost/graph/adjacency_iterator.hpp>
    1.37 +#include <boost/static_assert.hpp>
    1.38 +
    1.39 +// Symbol truncation problems with MSVC, trying to shorten names.
    1.40 +#define stored_edge se_
    1.41 +#define stored_edge_property sep_
    1.42 +#define stored_edge_iter sei_
    1.43 +
    1.44 +/*
    1.45 +  Outline for this file:
    1.46 +
    1.47 +  out_edge_iterator and in_edge_iterator implementation
    1.48 +  edge_iterator for undirected graph
    1.49 +  stored edge types (these object live in the out-edge/in-edge lists)
    1.50 +  directed edges helper class
    1.51 +  directed graph helper class
    1.52 +  undirected graph helper class
    1.53 +  bidirectional graph helper class
    1.54 +  bidirectional graph helper class (without edge properties)
    1.55 +  bidirectional graph helper class (with edge properties)
    1.56 +  adjacency_list helper class
    1.57 +  adj_list_impl class
    1.58 +  vec_adj_list_impl class
    1.59 +  adj_list_gen class
    1.60 +  vertex property map
    1.61 +  edge property map
    1.62 +
    1.63 +
    1.64 +  Note: it would be nice to merge some of the undirected and
    1.65 +  bidirectional code... it is awful similar.
    1.66 + */
    1.67 +
    1.68 +
    1.69 +namespace boost {
    1.70 +
    1.71 +  namespace detail {
    1.72 +
    1.73 +    template <typename DirectedS>
    1.74 +    struct directed_category_traits {
    1.75 +      typedef directed_tag directed_category;
    1.76 +    };
    1.77 +
    1.78 +    template <>
    1.79 +    struct directed_category_traits<directedS> {
    1.80 +      typedef directed_tag directed_category;
    1.81 +    };
    1.82 +    template <>
    1.83 +    struct directed_category_traits<undirectedS> {
    1.84 +      typedef undirected_tag directed_category;
    1.85 +    };
    1.86 +    template <>
    1.87 +    struct directed_category_traits<bidirectionalS> {
    1.88 +      typedef bidirectional_tag directed_category;
    1.89 +    };
    1.90 +
    1.91 +    template <class Vertex>
    1.92 +    struct target_is {
    1.93 +      target_is(const Vertex& v) : m_target(v) { }
    1.94 +      template <class StoredEdge>
    1.95 +      bool operator()(const StoredEdge& e) const {
    1.96 +        return e.get_target() == m_target;
    1.97 +      }
    1.98 +      Vertex m_target;
    1.99 +    };
   1.100 +
   1.101 +    // O(E/V)
   1.102 +    template <class EdgeList, class vertex_descriptor>
   1.103 +    void erase_from_incidence_list(EdgeList& el, vertex_descriptor v,
   1.104 +                                   allow_parallel_edge_tag)
   1.105 +    {
   1.106 +      boost::graph_detail::erase_if(el, detail::target_is<vertex_descriptor>(v));
   1.107 +    }
   1.108 +    // O(log(E/V))
   1.109 +    template <class EdgeList, class vertex_descriptor>
   1.110 +    void erase_from_incidence_list(EdgeList& el, vertex_descriptor v,
   1.111 +                                   disallow_parallel_edge_tag)
   1.112 +    {
   1.113 +      typedef typename EdgeList::value_type StoredEdge;
   1.114 +      el.erase(StoredEdge(v));
   1.115 +    }
   1.116 +
   1.117 +    //=========================================================================
   1.118 +    // Out-Edge and In-Edge Iterator Implementation
   1.119 +
   1.120 +    template <class BaseIter, class VertexDescriptor, class EdgeDescriptor, class Difference>
   1.121 +    struct out_edge_iter
   1.122 +      : iterator_adaptor<
   1.123 +            out_edge_iter<BaseIter, VertexDescriptor, EdgeDescriptor, Difference>
   1.124 +          , BaseIter
   1.125 +          , EdgeDescriptor
   1.126 +          , use_default
   1.127 +          , EdgeDescriptor
   1.128 +          , Difference
   1.129 +        >
   1.130 +    {
   1.131 +      typedef iterator_adaptor<
   1.132 +          out_edge_iter<BaseIter, VertexDescriptor, EdgeDescriptor, Difference>
   1.133 +        , BaseIter
   1.134 +        , EdgeDescriptor
   1.135 +        , use_default
   1.136 +        , EdgeDescriptor
   1.137 +        , Difference
   1.138 +      > super_t;
   1.139 +        
   1.140 +      inline out_edge_iter() { }
   1.141 +        inline out_edge_iter(const BaseIter& i, const VertexDescriptor& src)
   1.142 +          : super_t(i), m_src(src) { }
   1.143 +
   1.144 +      inline EdgeDescriptor
   1.145 +      dereference() const
   1.146 +      {
   1.147 +        return EdgeDescriptor(m_src, (*this->base()).get_target(), 
   1.148 +                              &(*this->base()).get_property());
   1.149 +      }
   1.150 +      VertexDescriptor m_src;
   1.151 +    };
   1.152 +  
   1.153 +    template <class BaseIter, class VertexDescriptor, class EdgeDescriptor, class Difference>
   1.154 +    struct in_edge_iter
   1.155 +      : iterator_adaptor<
   1.156 +            in_edge_iter<BaseIter, VertexDescriptor, EdgeDescriptor, Difference>
   1.157 +          , BaseIter
   1.158 +          , EdgeDescriptor
   1.159 +          , use_default
   1.160 +          , EdgeDescriptor
   1.161 +          , Difference
   1.162 +        >
   1.163 +    {
   1.164 +      typedef iterator_adaptor<
   1.165 +          in_edge_iter<BaseIter, VertexDescriptor, EdgeDescriptor, Difference>
   1.166 +        , BaseIter
   1.167 +        , EdgeDescriptor
   1.168 +        , use_default
   1.169 +        , EdgeDescriptor
   1.170 +        , Difference
   1.171 +      > super_t;
   1.172 +        
   1.173 +      inline in_edge_iter() { }
   1.174 +      inline in_edge_iter(const BaseIter& i, const VertexDescriptor& src) 
   1.175 +        : super_t(i), m_src(src) { }
   1.176 +
   1.177 +      inline EdgeDescriptor
   1.178 +      dereference() const
   1.179 +      {
   1.180 +        return EdgeDescriptor((*this->base()).get_target(), m_src,
   1.181 +                              &this->base()->get_property());
   1.182 +      }
   1.183 +      VertexDescriptor m_src;
   1.184 +    };
   1.185 +
   1.186 +    //=========================================================================
   1.187 +    // Undirected Edge Iterator Implementation
   1.188 +
   1.189 +    template <class EdgeIter, class EdgeDescriptor, class Difference>
   1.190 +    struct undirected_edge_iter
   1.191 +      : iterator_adaptor<
   1.192 +            undirected_edge_iter<EdgeIter, EdgeDescriptor, Difference>
   1.193 +          , EdgeIter
   1.194 +          , EdgeDescriptor
   1.195 +          , use_default
   1.196 +          , EdgeDescriptor
   1.197 +          , Difference
   1.198 +        >
   1.199 +    {
   1.200 +      typedef iterator_adaptor<
   1.201 +          undirected_edge_iter<EdgeIter, EdgeDescriptor, Difference>
   1.202 +        , EdgeIter
   1.203 +        , EdgeDescriptor
   1.204 +        , use_default
   1.205 +        , EdgeDescriptor
   1.206 +        , Difference
   1.207 +      > super_t;
   1.208 +
   1.209 +      undirected_edge_iter() {}
   1.210 +        
   1.211 +      explicit undirected_edge_iter(EdgeIter i)
   1.212 +          : super_t(i) {}
   1.213 +        
   1.214 +      inline EdgeDescriptor
   1.215 +      dereference() const {
   1.216 +        return EdgeDescriptor(
   1.217 +            (*this->base()).m_source
   1.218 +          , (*this->base()).m_target
   1.219 +          , &this->base()->get_property());
   1.220 +      }
   1.221 +    };
   1.222 +
   1.223 +    //=========================================================================
   1.224 +    // Edge Storage Types (stored in the out-edge/in-edge lists)
   1.225 +
   1.226 +    template <class Vertex>
   1.227 +    class stored_edge
   1.228 +      : public boost::equality_comparable1< stored_edge<Vertex>,
   1.229 +        boost::less_than_comparable1< stored_edge<Vertex> > >
   1.230 +    {
   1.231 +    public:
   1.232 +      typedef no_property property_type;
   1.233 +      inline stored_edge() { }
   1.234 +      inline stored_edge(Vertex target, const no_property& = no_property())
   1.235 +        : m_target(target) { }
   1.236 +      // Need to write this explicitly so stored_edge_property can
   1.237 +      // invoke Base::operator= (at least, for SGI MIPSPro compiler)
   1.238 +      inline stored_edge& operator=(const stored_edge& x) {
   1.239 +        m_target = x.m_target;
   1.240 +        return *this;
   1.241 +      }
   1.242 +      inline Vertex& get_target() const { return m_target; }
   1.243 +      inline const no_property& get_property() const { return s_prop; }
   1.244 +      inline bool operator==(const stored_edge& x) const
   1.245 +        { return m_target == x.get_target(); }
   1.246 +      inline bool operator<(const stored_edge& x) const
   1.247 +        { return m_target < x.get_target(); }
   1.248 +      //protected: need to add hash<> as a friend
   1.249 +      static no_property s_prop;
   1.250 +      // Sometimes target not used as key in the set, and in that case
   1.251 +      // it is ok to change the target.
   1.252 +      mutable Vertex m_target;
   1.253 +    };
   1.254 +    template <class Vertex>
   1.255 +    no_property stored_edge<Vertex>::s_prop;
   1.256 +
   1.257 +    template <class Vertex, class Property>
   1.258 +    class stored_edge_property : public stored_edge<Vertex> {
   1.259 +      typedef stored_edge_property self;
   1.260 +      typedef stored_edge<Vertex> Base;
   1.261 +    public:
   1.262 +      typedef Property property_type;
   1.263 +      inline stored_edge_property() { }
   1.264 +      inline stored_edge_property(Vertex target,
   1.265 +                                  const Property& p = Property())
   1.266 +        : stored_edge<Vertex>(target), m_property(new Property(p)) { }
   1.267 +      stored_edge_property(const self& x) 
   1.268 +        : Base(x), m_property(const_cast<self&>(x).m_property) { }
   1.269 +      self& operator=(const self& x) {
   1.270 +        Base::operator=(x);
   1.271 +        m_property = const_cast<self&>(x).m_property; 
   1.272 +        return *this;
   1.273 +      }
   1.274 +      inline Property& get_property() { return *m_property; }
   1.275 +      inline const Property& get_property() const { return *m_property; }
   1.276 +    protected:
   1.277 +      // Holding the property by-value causes edge-descriptor
   1.278 +      // invalidation for add_edge() with EdgeList=vecS. Instead we
   1.279 +      // hold a pointer to the property. std::auto_ptr is not
   1.280 +      // a perfect fit for the job, but it is darn close.
   1.281 +      std::auto_ptr<Property> m_property;
   1.282 +    };
   1.283 +
   1.284 +
   1.285 +    template <class Vertex, class Iter, class Property>
   1.286 +    class stored_edge_iter
   1.287 +      : public stored_edge<Vertex>
   1.288 +    {
   1.289 +    public:
   1.290 +      typedef Property property_type;
   1.291 +      inline stored_edge_iter() { }
   1.292 +      inline stored_edge_iter(Vertex v)
   1.293 +        : stored_edge<Vertex>(v) { }
   1.294 +      inline stored_edge_iter(Vertex v, Iter i, void* = 0)
   1.295 +        : stored_edge<Vertex>(v), m_iter(i) { }
   1.296 +      inline Property& get_property() { return m_iter->get_property(); }
   1.297 +      inline const Property& get_property() const { 
   1.298 +        return m_iter->get_property();
   1.299 +      }
   1.300 +      inline Iter get_iter() const { return m_iter; }
   1.301 +    protected:
   1.302 +      Iter m_iter;
   1.303 +    };
   1.304 +
   1.305 +    // For when the EdgeList is a std::vector.
   1.306 +    // Want to make the iterator stable, so use an offset
   1.307 +    // instead of an iterator into a std::vector
   1.308 +    template <class Vertex, class EdgeVec, class Property>
   1.309 +    class stored_ra_edge_iter
   1.310 +      : public stored_edge<Vertex>
   1.311 +    {
   1.312 +      typedef typename EdgeVec::iterator Iter;
   1.313 +    public:
   1.314 +      typedef Property property_type;
   1.315 +      inline stored_ra_edge_iter() { }
   1.316 +      inline stored_ra_edge_iter(Vertex v, Iter i = Iter(), 
   1.317 +                                 EdgeVec* edge_vec = 0)
   1.318 +        : stored_edge<Vertex>(v), m_i(i - edge_vec->begin()), m_vec(edge_vec){ }
   1.319 +      inline Property& get_property() { return (*m_vec)[m_i].get_property(); }
   1.320 +      inline const Property& get_property() const { 
   1.321 +        return (*m_vec)[m_i].get_property();
   1.322 +      }
   1.323 +      inline Iter get_iter() const { return m_vec->begin() + m_i; }
   1.324 +    protected:
   1.325 +      std::size_t m_i;
   1.326 +      EdgeVec* m_vec;
   1.327 +    };
   1.328 +
   1.329 +  } // namespace detail
   1.330 +    
   1.331 +  template <class Tag, class Vertex, class Property>
   1.332 +  const typename property_value<Property,Tag>::type&
   1.333 +  get(Tag property_tag,
   1.334 +      const detail::stored_edge_property<Vertex, Property>& e)
   1.335 +  {
   1.336 +    return get_property_value(e.get_property(), property_tag);
   1.337 +  }
   1.338 +
   1.339 +  template <class Tag, class Vertex, class Iter, class Property>
   1.340 +  const typename property_value<Property,Tag>::type&
   1.341 +  get(Tag property_tag,
   1.342 +      const detail::stored_edge_iter<Vertex, Iter, Property>& e)
   1.343 +  {
   1.344 +    return get_property_value(e.get_property(), property_tag);
   1.345 +  }
   1.346 +
   1.347 +  template <class Tag, class Vertex, class EdgeVec, class Property>
   1.348 +  const typename property_value<Property,Tag>::type&
   1.349 +  get(Tag property_tag,
   1.350 +      const detail::stored_ra_edge_iter<Vertex, EdgeVec, Property>& e)
   1.351 +  {
   1.352 +    return get_property_value(e.get_property(), property_tag);
   1.353 +  }
   1.354 +    
   1.355 +    //=========================================================================
   1.356 +    // Directed Edges Helper Class
   1.357 +
   1.358 +    namespace detail {
   1.359 +
   1.360 +      // O(E/V)
   1.361 +      template <class edge_descriptor, class EdgeList, class StoredProperty>
   1.362 +      inline void
   1.363 +      remove_directed_edge_dispatch(edge_descriptor, EdgeList& el,
   1.364 +                                    StoredProperty& p)
   1.365 +      {
   1.366 +        for (typename EdgeList::iterator i = el.begin();
   1.367 +             i != el.end(); ++i)
   1.368 +          if (&(*i).get_property() == &p) {
   1.369 +            el.erase(i);
   1.370 +            return;
   1.371 +          }
   1.372 +      }
   1.373 +
   1.374 +      template <class incidence_iterator, class EdgeList, class Predicate>
   1.375 +      inline void
   1.376 +      remove_directed_edge_if_dispatch(incidence_iterator first,
   1.377 +                                       incidence_iterator last, 
   1.378 +                                       EdgeList& el, Predicate pred,
   1.379 +                                       boost::allow_parallel_edge_tag)
   1.380 +      {
   1.381 +        // remove_if
   1.382 +        while (first != last && !pred(*first))
   1.383 +          ++first;
   1.384 +        incidence_iterator i = first;
   1.385 +        if (first != last)
   1.386 +          for (; i != last; ++i)
   1.387 +            if (!pred(*i)) {
   1.388 +              *first.base() = *i.base();
   1.389 +              ++first;
   1.390 +            }
   1.391 +        el.erase(first.base(), el.end());
   1.392 +      }
   1.393 +      template <class incidence_iterator, class EdgeList, class Predicate>
   1.394 +      inline void
   1.395 +      remove_directed_edge_if_dispatch(incidence_iterator first,
   1.396 +                                       incidence_iterator last, 
   1.397 +                                       EdgeList& el, 
   1.398 +                                       Predicate pred,
   1.399 +                                       boost::disallow_parallel_edge_tag)
   1.400 +      {
   1.401 +        for (incidence_iterator next = first;
   1.402 +             first != last; first = next) {
   1.403 +          ++next;
   1.404 +          if (pred(*first))
   1.405 +            el.erase( first.base() );
   1.406 +        }
   1.407 +      }
   1.408 +
   1.409 +      template <class PropT, class Graph, class incidence_iterator, 
   1.410 +                class EdgeList, class Predicate>
   1.411 +      inline void
   1.412 +      undirected_remove_out_edge_if_dispatch(Graph& g, 
   1.413 +                                             incidence_iterator first,
   1.414 +                                             incidence_iterator last, 
   1.415 +                                             EdgeList& el, Predicate pred,
   1.416 +                                             boost::allow_parallel_edge_tag)
   1.417 +      {
   1.418 +        typedef typename Graph::global_edgelist_selector EdgeListS;
   1.419 +        BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
   1.420 +
   1.421 +        // remove_if
   1.422 +        while (first != last && !pred(*first))
   1.423 +          ++first;
   1.424 +        incidence_iterator i = first;
   1.425 +        bool self_loop_removed = false;
   1.426 +        if (first != last)
   1.427 +          for (; i != last; ++i) {
   1.428 +            if (self_loop_removed) {
   1.429 +              /* With self loops, the descriptor will show up
   1.430 +               * twice. The first time it will be removed, and now it
   1.431 +               * will be skipped.
   1.432 +               */
   1.433 +              self_loop_removed = false;
   1.434 +            }
   1.435 +            else if (!pred(*i)) {
   1.436 +              *first.base() = *i.base();
   1.437 +              ++first;
   1.438 +            } else {
   1.439 +              if (source(*i, g) == target(*i, g)) self_loop_removed = true;
   1.440 +              else {
   1.441 +                // Remove the edge from the target
   1.442 +                detail::remove_directed_edge_dispatch
   1.443 +                  (*i, 
   1.444 +                   g.out_edge_list(target(*i, g)), 
   1.445 +                   *(PropT*)(*i).get_property());
   1.446 +              }
   1.447 +
   1.448 +              // Erase the edge property
   1.449 +              g.m_edges.erase( (*i.base()).get_iter() );
   1.450 +            }
   1.451 +          }
   1.452 +        el.erase(first.base(), el.end());
   1.453 +      }
   1.454 +      template <class PropT, class Graph, class incidence_iterator, 
   1.455 +                class EdgeList, class Predicate>
   1.456 +      inline void
   1.457 +      undirected_remove_out_edge_if_dispatch(Graph& g, 
   1.458 +                                             incidence_iterator first,
   1.459 +                                             incidence_iterator last, 
   1.460 +                                             EdgeList& el, 
   1.461 +                                             Predicate pred,
   1.462 +                                             boost::disallow_parallel_edge_tag)
   1.463 +      {
   1.464 +        typedef typename Graph::global_edgelist_selector EdgeListS;
   1.465 +        BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
   1.466 +
   1.467 +        for (incidence_iterator next = first;
   1.468 +             first != last; first = next) {
   1.469 +          ++next;
   1.470 +          if (pred(*first)) {
   1.471 +            if (source(*first, g) != target(*first, g)) {
   1.472 +              // Remove the edge from the target
   1.473 +              detail::remove_directed_edge_dispatch
   1.474 +                (*first, 
   1.475 +                 g.out_edge_list(target(*first, g)), 
   1.476 +                 *(PropT*)(*first).get_property());
   1.477 +            }
   1.478 +
   1.479 +            // Erase the edge property
   1.480 +            g.m_edges.erase( (*first.base()).get_iter() );
   1.481 +
   1.482 +            // Erase the edge in the source
   1.483 +            el.erase( first.base() );
   1.484 +          }
   1.485 +        }
   1.486 +      }
   1.487 +
   1.488 +      // O(E/V)
   1.489 +      template <class edge_descriptor, class EdgeList, class StoredProperty>
   1.490 +      inline void
   1.491 +      remove_directed_edge_dispatch(edge_descriptor e, EdgeList& el,
   1.492 +                                    no_property&)
   1.493 +      {
   1.494 +        for (typename EdgeList::iterator i = el.begin();
   1.495 +             i != el.end(); ++i)
   1.496 +          if ((*i).get_target() == e.m_target) {
   1.497 +            el.erase(i);
   1.498 +            return;
   1.499 +          }
   1.500 +      }
   1.501 +
   1.502 +    } // namespace detail
   1.503 +
   1.504 +    template <class Config>
   1.505 +    struct directed_edges_helper {
   1.506 +
   1.507 +      // Placement of these overloaded remove_edge() functions
   1.508 +      // inside the class avoids a VC++ bug.
   1.509 +      
   1.510 +      // O(E/V)
   1.511 +      inline void
   1.512 +      remove_edge(typename Config::edge_descriptor e)
   1.513 +      {
   1.514 +        typedef typename Config::graph_type graph_type;
   1.515 +        graph_type& g = static_cast<graph_type&>(*this);
   1.516 +        typename Config::OutEdgeList& el = g.out_edge_list(source(e, g));
   1.517 +        typedef typename Config::OutEdgeList::value_type::property_type PType;
   1.518 +        detail::remove_directed_edge_dispatch(e, el,
   1.519 +                                              *(PType*)e.get_property());
   1.520 +      }
   1.521 +
   1.522 +      // O(1)
   1.523 +      inline void
   1.524 +      remove_edge(typename Config::out_edge_iterator iter)
   1.525 +      {
   1.526 +        typedef typename Config::graph_type graph_type;
   1.527 +        graph_type& g = static_cast<graph_type&>(*this);
   1.528 +        typename Config::edge_descriptor e = *iter;
   1.529 +        typename Config::OutEdgeList& el = g.out_edge_list(source(e, g));
   1.530 +        el.erase(iter.base());
   1.531 +      }
   1.532 +
   1.533 +    };
   1.534 +
   1.535 +    // O(1)
   1.536 +    template <class Config>
   1.537 +    inline std::pair<typename Config::edge_iterator, 
   1.538 +                     typename Config::edge_iterator>
   1.539 +    edges(const directed_edges_helper<Config>& g_)
   1.540 +    {
   1.541 +      typedef typename Config::graph_type graph_type;
   1.542 +      typedef typename Config::edge_iterator edge_iterator;
   1.543 +      const graph_type& cg = static_cast<const graph_type&>(g_);
   1.544 +      graph_type& g = const_cast<graph_type&>(cg);
   1.545 +      return std::make_pair( edge_iterator(g.vertex_set().begin(), 
   1.546 +                                           g.vertex_set().begin(), 
   1.547 +                                           g.vertex_set().end(), g),
   1.548 +                             edge_iterator(g.vertex_set().begin(),
   1.549 +                                           g.vertex_set().end(),
   1.550 +                                           g.vertex_set().end(), g) );
   1.551 +    }
   1.552 +
   1.553 +    //=========================================================================
   1.554 +    // Directed Graph Helper Class
   1.555 +
   1.556 +    struct adj_list_dir_traversal_tag :
   1.557 +      public virtual vertex_list_graph_tag,
   1.558 +      public virtual incidence_graph_tag,
   1.559 +      public virtual adjacency_graph_tag,
   1.560 +      public virtual edge_list_graph_tag { };
   1.561 +
   1.562 +    template <class Config>
   1.563 +    struct directed_graph_helper
   1.564 +      : public directed_edges_helper<Config> { 
   1.565 +      typedef typename Config::edge_descriptor edge_descriptor;
   1.566 +      typedef adj_list_dir_traversal_tag traversal_category;
   1.567 +    };
   1.568 +
   1.569 +    // O(E/V)
   1.570 +    template <class Config>
   1.571 +    inline void
   1.572 +    remove_edge(typename Config::vertex_descriptor u,
   1.573 +                typename Config::vertex_descriptor v,
   1.574 +                directed_graph_helper<Config>& g_)
   1.575 +    {
   1.576 +      typedef typename Config::graph_type graph_type;
   1.577 +      typedef typename Config::edge_parallel_category Cat;
   1.578 +      graph_type& g = static_cast<graph_type&>(g_);
   1.579 +      detail::erase_from_incidence_list(g.out_edge_list(u), v, Cat());
   1.580 +    }
   1.581 +
   1.582 +    template <class Config, class Predicate>
   1.583 +    inline void
   1.584 +    remove_out_edge_if(typename Config::vertex_descriptor u, Predicate pred,
   1.585 +                       directed_graph_helper<Config>& g_)
   1.586 +    {
   1.587 +      typedef typename Config::graph_type graph_type;
   1.588 +      graph_type& g = static_cast<graph_type&>(g_);
   1.589 +      typename Config::out_edge_iterator first, last;
   1.590 +      tie(first, last) = out_edges(u, g);
   1.591 +      typedef typename Config::edge_parallel_category edge_parallel_category;
   1.592 +      detail::remove_directed_edge_if_dispatch
   1.593 +        (first, last, g.out_edge_list(u), pred, edge_parallel_category());
   1.594 +    }
   1.595 +
   1.596 +    template <class Config, class Predicate>
   1.597 +    inline void
   1.598 +    remove_edge_if(Predicate pred, directed_graph_helper<Config>& g_)
   1.599 +    {
   1.600 +      typedef typename Config::graph_type graph_type;
   1.601 +      graph_type& g = static_cast<graph_type&>(g_);
   1.602 +
   1.603 +      typename Config::vertex_iterator vi, vi_end;
   1.604 +      for (tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi)
   1.605 +        remove_out_edge_if(*vi, pred, g);
   1.606 +    }    
   1.607 +
   1.608 +    template <class EdgeOrIter, class Config>
   1.609 +    inline void
   1.610 +    remove_edge(EdgeOrIter e_or_iter, directed_graph_helper<Config>& g_)
   1.611 +    {
   1.612 +      g_.remove_edge(e_or_iter);
   1.613 +    }
   1.614 +
   1.615 +    // O(V + E) for allow_parallel_edges
   1.616 +    // O(V * log(E/V)) for disallow_parallel_edges
   1.617 +    template <class Config>
   1.618 +    inline void 
   1.619 +    clear_vertex(typename Config::vertex_descriptor u,
   1.620 +                 directed_graph_helper<Config>& g_)
   1.621 +    {
   1.622 +      typedef typename Config::graph_type graph_type;
   1.623 +      typedef typename Config::edge_parallel_category Cat;
   1.624 +      graph_type& g = static_cast<graph_type&>(g_);
   1.625 +      typename Config::vertex_iterator vi, viend;
   1.626 +      for (boost::tie(vi, viend) = vertices(g); vi != viend; ++vi)
   1.627 +        detail::erase_from_incidence_list(g.out_edge_list(*vi), u, Cat());
   1.628 +      g.out_edge_list(u).clear();
   1.629 +      // clear() should be a req of Sequence and AssociativeContainer,
   1.630 +      // or maybe just Container
   1.631 +    }
   1.632 +
   1.633 +    template <class Config>
   1.634 +    inline void 
   1.635 +    clear_out_edges(typename Config::vertex_descriptor u,
   1.636 +                    directed_graph_helper<Config>& g_)
   1.637 +    {
   1.638 +      typedef typename Config::graph_type graph_type;
   1.639 +      typedef typename Config::edge_parallel_category Cat;
   1.640 +      graph_type& g = static_cast<graph_type&>(g_);
   1.641 +      g.out_edge_list(u).clear();
   1.642 +      // clear() should be a req of Sequence and AssociativeContainer,
   1.643 +      // or maybe just Container
   1.644 +    }
   1.645 +
   1.646 +    // O(V), could do better...
   1.647 +    template <class Config>
   1.648 +    inline typename Config::edges_size_type
   1.649 +    num_edges(const directed_graph_helper<Config>& g_)
   1.650 +    {
   1.651 +      typedef typename Config::graph_type graph_type;
   1.652 +      const graph_type& g = static_cast<const graph_type&>(g_);
   1.653 +      typename Config::edges_size_type num_e = 0;
   1.654 +      typename Config::vertex_iterator vi, vi_end;
   1.655 +      for (boost::tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi)
   1.656 +        num_e += out_degree(*vi, g);
   1.657 +      return num_e;
   1.658 +    }
   1.659 +    // O(1) for allow_parallel_edge_tag
   1.660 +    // O(log(E/V)) for disallow_parallel_edge_tag
   1.661 +    template <class Config>
   1.662 +    inline std::pair<typename directed_graph_helper<Config>::edge_descriptor, bool>
   1.663 +    add_edge(typename Config::vertex_descriptor u, 
   1.664 +             typename Config::vertex_descriptor v,
   1.665 +             const typename Config::edge_property_type& p, 
   1.666 +             directed_graph_helper<Config>& g_)
   1.667 +    {
   1.668 +      typedef typename Config::edge_descriptor edge_descriptor;
   1.669 +      typedef typename Config::graph_type graph_type;
   1.670 +      typedef typename Config::StoredEdge StoredEdge;
   1.671 +      graph_type& g = static_cast<graph_type&>(g_);
   1.672 +      typename Config::OutEdgeList::iterator i; 
   1.673 +      bool inserted;
   1.674 +      boost::tie(i, inserted) = boost::graph_detail::push(g.out_edge_list(u), 
   1.675 +                                            StoredEdge(v, p));
   1.676 +      return std::make_pair(edge_descriptor(u, v, &(*i).get_property()), 
   1.677 +                            inserted);
   1.678 +    }
   1.679 +    // Did not use default argument here because that
   1.680 +    // causes Visual C++ to get confused.
   1.681 +    template <class Config>
   1.682 +    inline std::pair<typename Config::edge_descriptor, bool>
   1.683 +    add_edge(typename Config::vertex_descriptor u, 
   1.684 +             typename Config::vertex_descriptor v,
   1.685 +             directed_graph_helper<Config>& g_)
   1.686 +    {
   1.687 +      typename Config::edge_property_type p;
   1.688 +      return add_edge(u, v, p, g_);
   1.689 +    }
   1.690 +    //=========================================================================
   1.691 +    // Undirected Graph Helper Class
   1.692 +
   1.693 +    template <class Config>
   1.694 +    struct undirected_graph_helper;
   1.695 +
   1.696 +    struct undir_adj_list_traversal_tag : 
   1.697 +      public virtual vertex_list_graph_tag,
   1.698 +      public virtual incidence_graph_tag,
   1.699 +      public virtual adjacency_graph_tag,
   1.700 +      public virtual edge_list_graph_tag,
   1.701 +      public virtual bidirectional_graph_tag { };
   1.702 +
   1.703 +    namespace detail {
   1.704 +
   1.705 +      // using class with specialization for dispatch is a VC++ workaround.
   1.706 +      template <class StoredProperty>
   1.707 +      struct remove_undirected_edge_dispatch {
   1.708 +
   1.709 +        // O(E/V)
   1.710 +        template <class edge_descriptor, class Config>
   1.711 +        static void
   1.712 +        apply(edge_descriptor e, 
   1.713 +              undirected_graph_helper<Config>& g_, 
   1.714 +              StoredProperty& p)
   1.715 +        {
   1.716 +          typedef typename Config::global_edgelist_selector EdgeListS;
   1.717 +          BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
   1.718 +
   1.719 +          typedef typename Config::graph_type graph_type;
   1.720 +          graph_type& g = static_cast<graph_type&>(g_);
   1.721 +          
   1.722 +          typename Config::OutEdgeList& out_el = g.out_edge_list(source(e, g));
   1.723 +          typename Config::OutEdgeList::iterator out_i = out_el.begin();
   1.724 +          for (; out_i != out_el.end(); ++out_i)
   1.725 +            if (&(*out_i).get_property() == &p) {
   1.726 +              out_el.erase(out_i);
   1.727 +              break;
   1.728 +            }
   1.729 +          typename Config::OutEdgeList& in_el = g.out_edge_list(target(e, g));
   1.730 +          typename Config::OutEdgeList::iterator in_i = in_el.begin();
   1.731 +          for (; in_i != in_el.end(); ++in_i)
   1.732 +            if (&(*in_i).get_property() == &p) {
   1.733 +              g.m_edges.erase((*in_i).get_iter());
   1.734 +              in_el.erase(in_i);
   1.735 +              return;
   1.736 +            }
   1.737 +        }
   1.738 +      };
   1.739 +
   1.740 +      template <>
   1.741 +      struct remove_undirected_edge_dispatch<no_property> {
   1.742 +        // O(E/V)
   1.743 +        template <class edge_descriptor, class Config>
   1.744 +        static void
   1.745 +        apply(edge_descriptor e,
   1.746 +              undirected_graph_helper<Config>& g_,
   1.747 +              no_property&)
   1.748 +        {
   1.749 +          typedef typename Config::global_edgelist_selector EdgeListS;
   1.750 +          BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
   1.751 +
   1.752 +          typedef typename Config::graph_type graph_type;
   1.753 +          graph_type& g = static_cast<graph_type&>(g_);
   1.754 +          no_property* p = (no_property*)e.get_property();
   1.755 +          typename Config::OutEdgeList& out_el = g.out_edge_list(source(e, g));
   1.756 +          typename Config::OutEdgeList::iterator out_i = out_el.begin();
   1.757 +          for (; out_i != out_el.end(); ++out_i)
   1.758 +            if (&(*out_i).get_property() == p) {
   1.759 +              out_el.erase(out_i);
   1.760 +              break;
   1.761 +            }
   1.762 +          typename Config::OutEdgeList& in_el = g.out_edge_list(target(e, g));
   1.763 +          typename Config::OutEdgeList::iterator in_i = in_el.begin();
   1.764 +          for (; in_i != in_el.end(); ++in_i)
   1.765 +            if (&(*in_i).get_property() == p) {
   1.766 +              g.m_edges.erase((*in_i).get_iter());
   1.767 +              in_el.erase(in_i);
   1.768 +              return;
   1.769 +            }
   1.770 +        }
   1.771 +      };
   1.772 +
   1.773 +      // O(E/V)
   1.774 +      template <class Graph, class EdgeList, class Vertex>
   1.775 +      inline void
   1.776 +      remove_edge_and_property(Graph& g, EdgeList& el, Vertex v, 
   1.777 +                               boost::allow_parallel_edge_tag cat)
   1.778 +      {
   1.779 +        typedef typename Graph::global_edgelist_selector EdgeListS;
   1.780 +        BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
   1.781 +
   1.782 +        typedef typename EdgeList::value_type StoredEdge;
   1.783 +        typename EdgeList::iterator i = el.begin(), end = el.end();
   1.784 +        for (; i != end; ++i)
   1.785 +          if ((*i).get_target() == v)
   1.786 +            g.m_edges.erase((*i).get_iter());
   1.787 +        detail::erase_from_incidence_list(el, v, cat);
   1.788 +      }
   1.789 +      // O(log(E/V))
   1.790 +      template <class Graph, class EdgeList, class Vertex>
   1.791 +      inline void
   1.792 +      remove_edge_and_property(Graph& g, EdgeList& el, Vertex v, 
   1.793 +                               boost::disallow_parallel_edge_tag)
   1.794 +      {
   1.795 +        typedef typename Graph::global_edgelist_selector EdgeListS;
   1.796 +        BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
   1.797 +
   1.798 +        typedef typename EdgeList::value_type StoredEdge;
   1.799 +        typename EdgeList::iterator i = el.find(StoredEdge(v)), end = el.end();
   1.800 +        if (i != end) {
   1.801 +          g.m_edges.erase((*i).get_iter());
   1.802 +          el.erase(i);
   1.803 +        }
   1.804 +      }
   1.805 +
   1.806 +    } // namespace detail
   1.807 +
   1.808 +    template <class Vertex, class EdgeProperty>
   1.809 +    struct list_edge // short name due to VC++ truncation and linker problems
   1.810 +      : public boost::detail::edge_base<boost::undirected_tag, Vertex>
   1.811 +    {
   1.812 +      typedef EdgeProperty property_type;
   1.813 +      typedef boost::detail::edge_base<boost::undirected_tag, Vertex> Base;
   1.814 +      list_edge(Vertex u, Vertex v, const EdgeProperty& p = EdgeProperty())
   1.815 +        : Base(u, v), m_property(p) { }
   1.816 +      EdgeProperty& get_property() { return m_property; }
   1.817 +      const EdgeProperty& get_property() const { return m_property; }
   1.818 +      // the following methods should never be used, but are needed
   1.819 +      // to make SGI MIPSpro C++ happy
   1.820 +      list_edge() { }
   1.821 +      bool operator==(const list_edge&) const { return false; }
   1.822 +      bool operator<(const list_edge&) const { return false; }
   1.823 +      EdgeProperty m_property;
   1.824 +    };
   1.825 +
   1.826 +    template <class Config>
   1.827 +    struct undirected_graph_helper {
   1.828 +
   1.829 +      typedef undir_adj_list_traversal_tag traversal_category;
   1.830 +
   1.831 +      // Placement of these overloaded remove_edge() functions
   1.832 +      // inside the class avoids a VC++ bug.
   1.833 +
   1.834 +      // O(E/V)
   1.835 +      inline void
   1.836 +      remove_edge(typename Config::edge_descriptor e)
   1.837 +      {
   1.838 +        typedef typename Config::global_edgelist_selector EdgeListS;
   1.839 +        BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
   1.840 +
   1.841 +        typedef typename Config::OutEdgeList::value_type::property_type PType;
   1.842 +        detail::remove_undirected_edge_dispatch<PType>::apply
   1.843 +          (e, *this, *(PType*)e.get_property());
   1.844 +      }
   1.845 +      // O(E/V)
   1.846 +      inline void
   1.847 +      remove_edge(typename Config::out_edge_iterator iter)
   1.848 +      {
   1.849 +        this->remove_edge(*iter);
   1.850 +      }
   1.851 +    };
   1.852 +
   1.853 +    // Had to make these non-members to avoid accidental instantiation
   1.854 +    // on SGI MIPSpro C++
   1.855 +    template <class C>
   1.856 +    inline typename C::InEdgeList& 
   1.857 +    in_edge_list(undirected_graph_helper<C>&, 
   1.858 +                 typename C::vertex_descriptor v)
   1.859 +    {
   1.860 +      typename C::stored_vertex* sv = (typename C::stored_vertex*)v;
   1.861 +      return sv->m_out_edges;
   1.862 +    }
   1.863 +    template <class C>
   1.864 +    inline const typename C::InEdgeList& 
   1.865 +    in_edge_list(const undirected_graph_helper<C>&,
   1.866 +                 typename C::vertex_descriptor v) {
   1.867 +      typename C::stored_vertex* sv = (typename C::stored_vertex*)v;
   1.868 +      return sv->m_out_edges;
   1.869 +    }
   1.870 +
   1.871 +    // O(E/V)
   1.872 +    template <class EdgeOrIter, class Config>
   1.873 +    inline void
   1.874 +    remove_edge(EdgeOrIter e, undirected_graph_helper<Config>& g_)
   1.875 +    {
   1.876 +      typedef typename Config::global_edgelist_selector EdgeListS;
   1.877 +      BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
   1.878 +
   1.879 +      g_.remove_edge(e);
   1.880 +    }
   1.881 +
   1.882 +    // O(E/V) or O(log(E/V))
   1.883 +    template <class Config>
   1.884 +    void
   1.885 +    remove_edge(typename Config::vertex_descriptor u, 
   1.886 +                typename Config::vertex_descriptor v, 
   1.887 +                undirected_graph_helper<Config>& g_)
   1.888 +    {
   1.889 +      typedef typename Config::global_edgelist_selector EdgeListS;
   1.890 +      BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
   1.891 +
   1.892 +      typedef typename Config::graph_type graph_type;
   1.893 +      graph_type& g = static_cast<graph_type&>(g_);
   1.894 +      typedef typename Config::edge_parallel_category Cat;
   1.895 +      detail::remove_edge_and_property(g, g.out_edge_list(u), v, Cat());
   1.896 +      detail::erase_from_incidence_list(g.out_edge_list(v), u, Cat());
   1.897 +    }
   1.898 +  
   1.899 +    template <class Config, class Predicate>
   1.900 +    void
   1.901 +    remove_out_edge_if(typename Config::vertex_descriptor u, Predicate pred,
   1.902 +                       undirected_graph_helper<Config>& g_)
   1.903 +    {
   1.904 +      typedef typename Config::global_edgelist_selector EdgeListS;
   1.905 +      BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
   1.906 +        
   1.907 +      typedef typename Config::graph_type graph_type;
   1.908 +      typedef typename Config::OutEdgeList::value_type::property_type PropT;
   1.909 +      graph_type& g = static_cast<graph_type&>(g_);
   1.910 +      typename Config::out_edge_iterator first, last;
   1.911 +      tie(first, last) = out_edges(u, g);
   1.912 +      typedef typename Config::edge_parallel_category Cat;
   1.913 +      detail::undirected_remove_out_edge_if_dispatch<PropT>
   1.914 +        (g, first, last, g.out_edge_list(u), pred, Cat());
   1.915 +    }
   1.916 +    template <class Config, class Predicate>
   1.917 +    void
   1.918 +    remove_in_edge_if(typename Config::vertex_descriptor u, Predicate pred,
   1.919 +                      undirected_graph_helper<Config>& g_)
   1.920 +    {
   1.921 +      typedef typename Config::global_edgelist_selector EdgeListS;
   1.922 +      BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
   1.923 +
   1.924 +      remove_out_edge_if(u, pred, g_);
   1.925 +    }
   1.926 +
   1.927 +    // O(E/V * E) or O(log(E/V) * E)
   1.928 +    template <class Predicate, class Config>
   1.929 +    void
   1.930 +    remove_edge_if(Predicate pred, undirected_graph_helper<Config>& g_)
   1.931 +    {
   1.932 +      typedef typename Config::global_edgelist_selector EdgeListS;
   1.933 +      BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
   1.934 +
   1.935 +      typedef typename Config::graph_type graph_type;
   1.936 +      graph_type& g = static_cast<graph_type&>(g_);
   1.937 +      typename Config::edge_iterator ei, ei_end, next;
   1.938 +      tie(ei, ei_end) = edges(g);
   1.939 +      for (next = ei; ei != ei_end; ei = next) {
   1.940 +        ++next;
   1.941 +        if (pred(*ei))
   1.942 +          remove_edge(*ei, g);
   1.943 +      }
   1.944 +    }
   1.945 +
   1.946 +    // O(1)
   1.947 +    template <class Config>
   1.948 +    inline std::pair<typename Config::edge_iterator, 
   1.949 +                     typename Config::edge_iterator>
   1.950 +    edges(const undirected_graph_helper<Config>& g_)
   1.951 +    {
   1.952 +      typedef typename Config::graph_type graph_type;
   1.953 +      typedef typename Config::edge_iterator edge_iterator;
   1.954 +      const graph_type& cg = static_cast<const graph_type&>(g_);
   1.955 +      graph_type& g = const_cast<graph_type&>(cg);
   1.956 +      return std::make_pair( edge_iterator(g.m_edges.begin()),
   1.957 +                             edge_iterator(g.m_edges.end()) );
   1.958 +    }
   1.959 +    // O(1)
   1.960 +    template <class Config>
   1.961 +    inline typename Config::edges_size_type
   1.962 +    num_edges(const undirected_graph_helper<Config>& g_) 
   1.963 +    {
   1.964 +      typedef typename Config::graph_type graph_type;
   1.965 +      const graph_type& g = static_cast<const graph_type&>(g_);
   1.966 +      return g.m_edges.size();
   1.967 +    }
   1.968 +    // O(E/V * E/V)
   1.969 +    template <class Config>
   1.970 +    inline void 
   1.971 +    clear_vertex(typename Config::vertex_descriptor u,
   1.972 +                 undirected_graph_helper<Config>& g_)
   1.973 +    {
   1.974 +      typedef typename Config::global_edgelist_selector EdgeListS;
   1.975 +      BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
   1.976 +
   1.977 +      typedef typename Config::graph_type graph_type;
   1.978 +      typedef typename Config::edge_parallel_category Cat;
   1.979 +      graph_type& g = static_cast<graph_type&>(g_);
   1.980 +      typename Config::OutEdgeList& el = g.out_edge_list(u);
   1.981 +      typename Config::OutEdgeList::iterator 
   1.982 +        ei = el.begin(), ei_end = el.end();
   1.983 +      for (; ei != ei_end; ++ei) {
   1.984 +        detail::erase_from_incidence_list
   1.985 +          (g.out_edge_list((*ei).get_target()), u, Cat());
   1.986 +        g.m_edges.erase((*ei).get_iter());
   1.987 +      }
   1.988 +      g.out_edge_list(u).clear();
   1.989 +    }
   1.990 +    // O(1) for allow_parallel_edge_tag
   1.991 +    // O(log(E/V)) for disallow_parallel_edge_tag
   1.992 +    template <class Config>
   1.993 +    inline std::pair<typename Config::edge_descriptor, bool>
   1.994 +    add_edge(typename Config::vertex_descriptor u, 
   1.995 +             typename Config::vertex_descriptor v, 
   1.996 +             const typename Config::edge_property_type& p,
   1.997 +             undirected_graph_helper<Config>& g_)
   1.998 +    {
   1.999 +      typedef typename Config::StoredEdge StoredEdge;
  1.1000 +      typedef typename Config::edge_descriptor edge_descriptor;
  1.1001 +      typedef typename Config::graph_type graph_type;
  1.1002 +      graph_type& g = static_cast<graph_type&>(g_);
  1.1003 +
  1.1004 +      bool inserted;
  1.1005 +      typename Config::EdgeContainer::value_type e(u, v, p);
  1.1006 +      typename Config::EdgeContainer::iterator p_iter 
  1.1007 +        = graph_detail::push(g.m_edges, e).first;
  1.1008 +
  1.1009 +      typename Config::OutEdgeList::iterator i;
  1.1010 +      boost::tie(i, inserted) = boost::graph_detail::push(g.out_edge_list(u), 
  1.1011 +                                    StoredEdge(v, p_iter, &g.m_edges));
  1.1012 +      if (inserted) {
  1.1013 +        boost::graph_detail::push(g.out_edge_list(v), StoredEdge(u, p_iter, &g.m_edges));
  1.1014 +        return std::make_pair(edge_descriptor(u, v, &p_iter->get_property()),
  1.1015 +                              true);
  1.1016 +      } else {
  1.1017 +        g.m_edges.erase(p_iter);
  1.1018 +        return std::make_pair
  1.1019 +          (edge_descriptor(u, v, &i->get_iter()->get_property()), false);
  1.1020 +      }
  1.1021 +    }
  1.1022 +    template <class Config>
  1.1023 +    inline std::pair<typename Config::edge_descriptor, bool>
  1.1024 +    add_edge(typename Config::vertex_descriptor u, 
  1.1025 +             typename Config::vertex_descriptor v, 
  1.1026 +             undirected_graph_helper<Config>& g_)
  1.1027 +    {
  1.1028 +      typename Config::edge_property_type p;
  1.1029 +      return add_edge(u, v, p, g_);
  1.1030 +    }
  1.1031 +
  1.1032 +    // O(1)
  1.1033 +    template <class Config>
  1.1034 +    inline typename Config::degree_size_type
  1.1035 +    degree(typename Config::vertex_descriptor u, 
  1.1036 +           const undirected_graph_helper<Config>& g_)
  1.1037 +    {
  1.1038 +      typedef typename Config::graph_type Graph;
  1.1039 +      const Graph& g = static_cast<const Graph&>(g_);
  1.1040 +      return out_degree(u, g);
  1.1041 +    }
  1.1042 +
  1.1043 +    template <class Config>
  1.1044 +    inline std::pair<typename Config::in_edge_iterator, 
  1.1045 +                     typename Config::in_edge_iterator>
  1.1046 +    in_edges(typename Config::vertex_descriptor u, 
  1.1047 +             const undirected_graph_helper<Config>& g_)
  1.1048 +    {
  1.1049 +      typedef typename Config::graph_type Graph;
  1.1050 +      const Graph& cg = static_cast<const Graph&>(g_);
  1.1051 +      Graph& g = const_cast<Graph&>(cg);
  1.1052 +      typedef typename Config::in_edge_iterator in_edge_iterator;
  1.1053 +      return
  1.1054 +        std::make_pair(in_edge_iterator(g.out_edge_list(u).begin(), u),
  1.1055 +                       in_edge_iterator(g.out_edge_list(u).end(), u));
  1.1056 +    }
  1.1057 +
  1.1058 +    template <class Config>
  1.1059 +    inline typename Config::degree_size_type
  1.1060 +    in_degree(typename Config::vertex_descriptor u,
  1.1061 +              const undirected_graph_helper<Config>& g_)
  1.1062 +    { return degree(u, g_); }
  1.1063 +
  1.1064 +    //=========================================================================
  1.1065 +    // Bidirectional Graph Helper Class
  1.1066 +
  1.1067 +    struct bidir_adj_list_traversal_tag : 
  1.1068 +      public virtual vertex_list_graph_tag,
  1.1069 +      public virtual incidence_graph_tag,
  1.1070 +      public virtual adjacency_graph_tag,
  1.1071 +      public virtual edge_list_graph_tag,
  1.1072 +      public virtual bidirectional_graph_tag { };
  1.1073 +
  1.1074 +    template <class Config>
  1.1075 +    struct bidirectional_graph_helper
  1.1076 +      : public directed_edges_helper<Config> {
  1.1077 +      typedef bidir_adj_list_traversal_tag traversal_category;
  1.1078 +    };
  1.1079 +
  1.1080 +    // Had to make these non-members to avoid accidental instantiation
  1.1081 +    // on SGI MIPSpro C++
  1.1082 +    template <class C>
  1.1083 +    inline typename C::InEdgeList& 
  1.1084 +    in_edge_list(bidirectional_graph_helper<C>&, 
  1.1085 +                 typename C::vertex_descriptor v)
  1.1086 +    {
  1.1087 +      typename C::stored_vertex* sv = (typename C::stored_vertex*)v;
  1.1088 +      return sv->m_in_edges;
  1.1089 +    }
  1.1090 +    template <class C>
  1.1091 +    inline const typename C::InEdgeList& 
  1.1092 +    in_edge_list(const bidirectional_graph_helper<C>&,
  1.1093 +                 typename C::vertex_descriptor v) {
  1.1094 +      typename C::stored_vertex* sv = (typename C::stored_vertex*)v;
  1.1095 +      return sv->m_in_edges;
  1.1096 +    }
  1.1097 +
  1.1098 +    template <class Predicate, class Config>
  1.1099 +    inline void
  1.1100 +    remove_edge_if(Predicate pred, bidirectional_graph_helper<Config>& g_)
  1.1101 +    {
  1.1102 +      typedef typename Config::global_edgelist_selector EdgeListS;
  1.1103 +      BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
  1.1104 +
  1.1105 +      typedef typename Config::graph_type graph_type;
  1.1106 +      graph_type& g = static_cast<graph_type&>(g_);
  1.1107 +      typename Config::edge_iterator ei, ei_end, next;
  1.1108 +      tie(ei, ei_end) = edges(g);
  1.1109 +      for (next = ei; ei != ei_end; ei = next) {
  1.1110 +        ++next;
  1.1111 +        if (pred(*ei))
  1.1112 +          remove_edge(*ei, g);
  1.1113 +      }
  1.1114 +    }
  1.1115 +
  1.1116 +    template <class Config>
  1.1117 +    inline std::pair<typename Config::in_edge_iterator, 
  1.1118 +                     typename Config::in_edge_iterator>
  1.1119 +    in_edges(typename Config::vertex_descriptor u, 
  1.1120 +             const bidirectional_graph_helper<Config>& g_)
  1.1121 +    {
  1.1122 +      typedef typename Config::graph_type graph_type;
  1.1123 +      const graph_type& cg = static_cast<const graph_type&>(g_);
  1.1124 +      graph_type& g = const_cast<graph_type&>(cg);
  1.1125 +      typedef typename Config::in_edge_iterator in_edge_iterator;
  1.1126 +      return
  1.1127 +        std::make_pair(in_edge_iterator(in_edge_list(g, u).begin(), u),
  1.1128 +                       in_edge_iterator(in_edge_list(g, u).end(), u));
  1.1129 +    }
  1.1130 +
  1.1131 +    // O(1)
  1.1132 +    template <class Config>
  1.1133 +    inline std::pair<typename Config::edge_iterator, 
  1.1134 +                     typename Config::edge_iterator>
  1.1135 +    edges(const bidirectional_graph_helper<Config>& g_)
  1.1136 +    {
  1.1137 +      typedef typename Config::graph_type graph_type;
  1.1138 +      typedef typename Config::edge_iterator edge_iterator;
  1.1139 +      const graph_type& cg = static_cast<const graph_type&>(g_);
  1.1140 +      graph_type& g = const_cast<graph_type&>(cg);
  1.1141 +      return std::make_pair( edge_iterator(g.m_edges.begin()),
  1.1142 +                             edge_iterator(g.m_edges.end()) );
  1.1143 +    }
  1.1144 +
  1.1145 +    //=========================================================================
  1.1146 +    // Bidirectional Graph Helper Class (with edge properties)
  1.1147 +
  1.1148 +
  1.1149 +    template <class Config>
  1.1150 +    struct bidirectional_graph_helper_with_property
  1.1151 +      : public bidirectional_graph_helper<Config>
  1.1152 +    {
  1.1153 +      typedef typename Config::graph_type graph_type;
  1.1154 +      typedef typename Config::out_edge_iterator out_edge_iterator;
  1.1155 +      
  1.1156 +      std::pair<out_edge_iterator, out_edge_iterator>
  1.1157 +      get_parallel_edge_sublist(typename Config::edge_descriptor e,
  1.1158 +                                const graph_type& g,
  1.1159 +                                void*)
  1.1160 +      { return out_edges(source(e, g), g); }
  1.1161 +
  1.1162 +      std::pair<out_edge_iterator, out_edge_iterator>
  1.1163 +      get_parallel_edge_sublist(typename Config::edge_descriptor e,
  1.1164 +                                const graph_type& g,
  1.1165 +                                setS*)
  1.1166 +      { return edge_range(source(e, g), target(e, g), g); }
  1.1167 +
  1.1168 +      std::pair<out_edge_iterator, out_edge_iterator>
  1.1169 +      get_parallel_edge_sublist(typename Config::edge_descriptor e,
  1.1170 +                                const graph_type& g,
  1.1171 +                                multisetS*)
  1.1172 +      { return edge_range(source(e, g), target(e, g), g); }
  1.1173 +
  1.1174 +#if !defined BOOST_NO_HASH
  1.1175 +      std::pair<out_edge_iterator, out_edge_iterator>
  1.1176 +      get_parallel_edge_sublist(typename Config::edge_descriptor e,
  1.1177 +                                const graph_type& g,
  1.1178 +                                hash_setS*)
  1.1179 +      { return edge_range(source(e, g), target(e, g), g); }
  1.1180 +#endif
  1.1181 +
  1.1182 +      // Placement of these overloaded remove_edge() functions
  1.1183 +      // inside the class avoids a VC++ bug.
  1.1184 +
  1.1185 +      // O(E/V) or O(log(E/V))
  1.1186 +      void
  1.1187 +      remove_edge(typename Config::edge_descriptor e)
  1.1188 +      {
  1.1189 +        typedef typename Config::global_edgelist_selector EdgeListS;
  1.1190 +        BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
  1.1191 +
  1.1192 +        graph_type& g = static_cast<graph_type&>(*this);
  1.1193 +
  1.1194 +        typedef typename Config::edgelist_selector OutEdgeListS;
  1.1195 +
  1.1196 +        std::pair<out_edge_iterator, out_edge_iterator> rng = 
  1.1197 +          get_parallel_edge_sublist(e, g, (OutEdgeListS*)(0));
  1.1198 +        rng.first = std::find(rng.first, rng.second, e);
  1.1199 +        assert(rng.first != rng.second);
  1.1200 +        remove_edge(rng.first);
  1.1201 +      }
  1.1202 +
  1.1203 +      inline void
  1.1204 +      remove_edge(typename Config::out_edge_iterator iter)
  1.1205 +      {
  1.1206 +        typedef typename Config::global_edgelist_selector EdgeListS;
  1.1207 +        BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
  1.1208 +
  1.1209 +        typedef typename Config::graph_type graph_type;
  1.1210 +        graph_type& g = static_cast<graph_type&>(*this);
  1.1211 +        typename Config::edge_descriptor e = *iter;
  1.1212 +        typename Config::OutEdgeList& oel = g.out_edge_list(source(e, g));
  1.1213 +        typename Config::InEdgeList& iel = in_edge_list(g, target(e, g));
  1.1214 +        typedef typename Config::OutEdgeList::value_type::property_type PType;
  1.1215 +        PType& p = *(PType*)e.get_property();
  1.1216 +        detail::remove_directed_edge_dispatch(*iter, iel, p);
  1.1217 +        g.m_edges.erase(iter.base()->get_iter());
  1.1218 +        oel.erase(iter.base());
  1.1219 +      }
  1.1220 +    };
  1.1221 +
  1.1222 +    // O(E/V) for allow_parallel_edge_tag
  1.1223 +    // O(log(E/V)) for disallow_parallel_edge_tag
  1.1224 +    template <class Config>
  1.1225 +    inline void
  1.1226 +    remove_edge(typename Config::vertex_descriptor u, 
  1.1227 +                typename Config::vertex_descriptor v, 
  1.1228 +                bidirectional_graph_helper_with_property<Config>& g_)
  1.1229 +    {
  1.1230 +      typedef typename Config::global_edgelist_selector EdgeListS;
  1.1231 +      BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
  1.1232 +
  1.1233 +      typedef typename Config::graph_type graph_type;
  1.1234 +      graph_type& g = static_cast<graph_type&>(g_);
  1.1235 +      typedef typename Config::edge_parallel_category Cat;
  1.1236 +      detail::remove_edge_and_property(g, g.out_edge_list(u), v, Cat());
  1.1237 +      detail::erase_from_incidence_list(in_edge_list(g, v), u, Cat());
  1.1238 +    }
  1.1239 +
  1.1240 +    // O(E/V) or O(log(E/V))
  1.1241 +    template <class EdgeOrIter, class Config>
  1.1242 +    inline void
  1.1243 +    remove_edge(EdgeOrIter e,
  1.1244 +                bidirectional_graph_helper_with_property<Config>& g_)
  1.1245 +    {
  1.1246 +      typedef typename Config::global_edgelist_selector EdgeListS;
  1.1247 +      BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
  1.1248 +
  1.1249 +      g_.remove_edge(e);
  1.1250 +    }
  1.1251 +
  1.1252 +    template <class Config, class Predicate>
  1.1253 +    inline void
  1.1254 +    remove_out_edge_if(typename Config::vertex_descriptor u, Predicate pred,
  1.1255 +                       bidirectional_graph_helper_with_property<Config>& g_)
  1.1256 +    {
  1.1257 +      typedef typename Config::global_edgelist_selector EdgeListS;
  1.1258 +      BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
  1.1259 +
  1.1260 +      typedef typename Config::graph_type graph_type;
  1.1261 +      typedef typename Config::OutEdgeList::value_type::property_type PropT;
  1.1262 +      graph_type& g = static_cast<graph_type&>(g_);
  1.1263 +      
  1.1264 +      typedef typename Config::EdgeIter EdgeIter;
  1.1265 +      typedef std::vector<EdgeIter> Garbage;
  1.1266 +      Garbage garbage;
  1.1267 +
  1.1268 +      // First remove the edges from the targets' in-edge lists and
  1.1269 +      // from the graph's edge set list.
  1.1270 +      typename Config::out_edge_iterator out_i, out_end;
  1.1271 +      for (tie(out_i, out_end) = out_edges(u, g); out_i != out_end; ++out_i)
  1.1272 +        if (pred(*out_i)) {
  1.1273 +          detail::remove_directed_edge_dispatch
  1.1274 +            (*out_i, in_edge_list(g, target(*out_i, g)),
  1.1275 +             *(PropT*)(*out_i).get_property());
  1.1276 +          // Put in garbage to delete later. Will need the properties
  1.1277 +          // for the remove_if of the out-edges.
  1.1278 +          garbage.push_back((*out_i.base()).get_iter());
  1.1279 +        }
  1.1280 +
  1.1281 +      // Now remove the edges from this out-edge list.
  1.1282 +      typename Config::out_edge_iterator first, last;
  1.1283 +      tie(first, last) = out_edges(u, g);
  1.1284 +      typedef typename Config::edge_parallel_category Cat;
  1.1285 +      detail::remove_directed_edge_if_dispatch
  1.1286 +        (first, last, g.out_edge_list(u), pred, Cat());
  1.1287 +
  1.1288 +      // Now delete the edge properties from the g.m_edges list
  1.1289 +      for (typename Garbage::iterator i = garbage.begin();
  1.1290 +           i != garbage.end(); ++i)
  1.1291 +        g.m_edges.erase(*i);
  1.1292 +    }
  1.1293 +    template <class Config, class Predicate>
  1.1294 +    inline void
  1.1295 +    remove_in_edge_if(typename Config::vertex_descriptor v, Predicate pred,
  1.1296 +                      bidirectional_graph_helper_with_property<Config>& g_)
  1.1297 +    {
  1.1298 +      typedef typename Config::global_edgelist_selector EdgeListS;
  1.1299 +      BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
  1.1300 +
  1.1301 +      typedef typename Config::graph_type graph_type;
  1.1302 +      typedef typename Config::OutEdgeList::value_type::property_type PropT;
  1.1303 +      graph_type& g = static_cast<graph_type&>(g_);
  1.1304 +
  1.1305 +      typedef typename Config::EdgeIter EdgeIter;
  1.1306 +      typedef std::vector<EdgeIter> Garbage;
  1.1307 +      Garbage garbage;
  1.1308 +
  1.1309 +      // First remove the edges from the sources' out-edge lists and
  1.1310 +      // from the graph's edge set list.
  1.1311 +      typename Config::in_edge_iterator in_i, in_end;
  1.1312 +      for (tie(in_i, in_end) = in_edges(v, g); in_i != in_end; ++in_i)
  1.1313 +        if (pred(*in_i)) {
  1.1314 +          typename Config::vertex_descriptor u = source(*in_i, g);
  1.1315 +          detail::remove_directed_edge_dispatch
  1.1316 +            (*in_i, g.out_edge_list(u), *(PropT*)(*in_i).get_property());
  1.1317 +          // Put in garbage to delete later. Will need the properties
  1.1318 +          // for the remove_if of the out-edges.
  1.1319 +          garbage.push_back((*in_i.base()).get_iter());
  1.1320 +        }
  1.1321 +      // Now remove the edges from this in-edge list.
  1.1322 +      typename Config::in_edge_iterator first, last;
  1.1323 +      tie(first, last) = in_edges(v, g);
  1.1324 +      typedef typename Config::edge_parallel_category Cat;
  1.1325 +      detail::remove_directed_edge_if_dispatch
  1.1326 +        (first, last, in_edge_list(g, v), pred, Cat());
  1.1327 +
  1.1328 +      // Now delete the edge properties from the g.m_edges list
  1.1329 +      for (typename Garbage::iterator i = garbage.begin();
  1.1330 +           i != garbage.end(); ++i)
  1.1331 +        g.m_edges.erase(*i);
  1.1332 +    }
  1.1333 +
  1.1334 +    // O(1)
  1.1335 +    template <class Config>
  1.1336 +    inline typename Config::edges_size_type
  1.1337 +    num_edges(const bidirectional_graph_helper_with_property<Config>& g_) 
  1.1338 +    {
  1.1339 +      typedef typename Config::graph_type graph_type;
  1.1340 +      const graph_type& g = static_cast<const graph_type&>(g_);
  1.1341 +      return g.m_edges.size();
  1.1342 +    }
  1.1343 +    // O(E/V * E/V) for allow_parallel_edge_tag
  1.1344 +    // O(E/V * log(E/V)) for disallow_parallel_edge_tag
  1.1345 +    template <class Config>
  1.1346 +    inline void
  1.1347 +    clear_vertex(typename Config::vertex_descriptor u,
  1.1348 +                 bidirectional_graph_helper_with_property<Config>& g_)
  1.1349 +    {
  1.1350 +      typedef typename Config::global_edgelist_selector EdgeListS;
  1.1351 +      BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
  1.1352 +
  1.1353 +      typedef typename Config::graph_type graph_type;
  1.1354 +      typedef typename Config::edge_parallel_category Cat;
  1.1355 +      graph_type& g = static_cast<graph_type&>(g_);
  1.1356 +      typename Config::OutEdgeList& el = g.out_edge_list(u);
  1.1357 +      typename Config::OutEdgeList::iterator 
  1.1358 +        ei = el.begin(), ei_end = el.end();
  1.1359 +      for (; ei != ei_end; ++ei) {
  1.1360 +        detail::erase_from_incidence_list
  1.1361 +          (in_edge_list(g, (*ei).get_target()), u, Cat());
  1.1362 +        g.m_edges.erase((*ei).get_iter());
  1.1363 +      }      
  1.1364 +      typename Config::InEdgeList& in_el = in_edge_list(g, u);
  1.1365 +      typename Config::InEdgeList::iterator 
  1.1366 +        in_ei = in_el.begin(), in_ei_end = in_el.end();
  1.1367 +      for (; in_ei != in_ei_end; ++in_ei) {
  1.1368 +        detail::erase_from_incidence_list
  1.1369 +          (g.out_edge_list((*in_ei).get_target()), u, Cat());
  1.1370 +        g.m_edges.erase((*in_ei).get_iter());   
  1.1371 +      }
  1.1372 +      g.out_edge_list(u).clear();
  1.1373 +      in_edge_list(g, u).clear();
  1.1374 +    }
  1.1375 +
  1.1376 +    template <class Config>
  1.1377 +    inline void
  1.1378 +    clear_out_edges(typename Config::vertex_descriptor u,
  1.1379 +                    bidirectional_graph_helper_with_property<Config>& g_)
  1.1380 +    {
  1.1381 +      typedef typename Config::global_edgelist_selector EdgeListS;
  1.1382 +      BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
  1.1383 +
  1.1384 +      typedef typename Config::graph_type graph_type;
  1.1385 +      typedef typename Config::edge_parallel_category Cat;
  1.1386 +      graph_type& g = static_cast<graph_type&>(g_);
  1.1387 +      typename Config::OutEdgeList& el = g.out_edge_list(u);
  1.1388 +      typename Config::OutEdgeList::iterator 
  1.1389 +        ei = el.begin(), ei_end = el.end();
  1.1390 +      for (; ei != ei_end; ++ei) {
  1.1391 +        detail::erase_from_incidence_list
  1.1392 +          (in_edge_list(g, (*ei).get_target()), u, Cat());
  1.1393 +        g.m_edges.erase((*ei).get_iter());
  1.1394 +      }      
  1.1395 +      g.out_edge_list(u).clear();
  1.1396 +    }
  1.1397 +
  1.1398 +    template <class Config>
  1.1399 +    inline void
  1.1400 +    clear_in_edges(typename Config::vertex_descriptor u,
  1.1401 +                   bidirectional_graph_helper_with_property<Config>& g_)
  1.1402 +    {
  1.1403 +      typedef typename Config::global_edgelist_selector EdgeListS;
  1.1404 +      BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
  1.1405 +
  1.1406 +      typedef typename Config::graph_type graph_type;
  1.1407 +      typedef typename Config::edge_parallel_category Cat;
  1.1408 +      graph_type& g = static_cast<graph_type&>(g_);
  1.1409 +      typename Config::InEdgeList& in_el = in_edge_list(g, u);
  1.1410 +      typename Config::InEdgeList::iterator 
  1.1411 +        in_ei = in_el.begin(), in_ei_end = in_el.end();
  1.1412 +      for (; in_ei != in_ei_end; ++in_ei) {
  1.1413 +        detail::erase_from_incidence_list
  1.1414 +          (g.out_edge_list((*in_ei).get_target()), u, Cat());
  1.1415 +        g.m_edges.erase((*in_ei).get_iter());   
  1.1416 +      }
  1.1417 +      in_edge_list(g, u).clear();
  1.1418 +    }
  1.1419 +
  1.1420 +    // O(1) for allow_parallel_edge_tag
  1.1421 +    // O(log(E/V)) for disallow_parallel_edge_tag
  1.1422 +    template <class Config>
  1.1423 +    inline std::pair<typename Config::edge_descriptor, bool>
  1.1424 +    add_edge(typename Config::vertex_descriptor u,
  1.1425 +             typename Config::vertex_descriptor v, 
  1.1426 +             const typename Config::edge_property_type& p,
  1.1427 +             bidirectional_graph_helper_with_property<Config>& g_)
  1.1428 +    {
  1.1429 +      typedef typename Config::graph_type graph_type;
  1.1430 +      graph_type& g = static_cast<graph_type&>(g_);
  1.1431 +      typedef typename Config::edge_descriptor edge_descriptor;
  1.1432 +      typedef typename Config::StoredEdge StoredEdge;
  1.1433 +      bool inserted;
  1.1434 +      typename Config::EdgeContainer::value_type e(u, v, p);
  1.1435 +      typename Config::EdgeContainer::iterator p_iter 
  1.1436 +        = graph_detail::push(g.m_edges, e).first;
  1.1437 +      typename Config::OutEdgeList::iterator i;
  1.1438 +      boost::tie(i, inserted) = boost::graph_detail::push(g.out_edge_list(u), 
  1.1439 +                                        StoredEdge(v, p_iter, &g.m_edges));
  1.1440 +      if (inserted) {
  1.1441 +        boost::graph_detail::push(in_edge_list(g, v), StoredEdge(u, p_iter, &g.m_edges));
  1.1442 +        return std::make_pair(edge_descriptor(u, v, &p_iter->m_property), 
  1.1443 +                              true);
  1.1444 +      } else {
  1.1445 +        g.m_edges.erase(p_iter);
  1.1446 +        return std::make_pair(edge_descriptor(u, v, 
  1.1447 +                                     &i->get_iter()->get_property()), 
  1.1448 +                              false);
  1.1449 +      }
  1.1450 +    }
  1.1451 +
  1.1452 +    template <class Config>
  1.1453 +    inline std::pair<typename Config::edge_descriptor, bool>
  1.1454 +    add_edge(typename Config::vertex_descriptor u,
  1.1455 +             typename Config::vertex_descriptor v,
  1.1456 +             bidirectional_graph_helper_with_property<Config>& g_)
  1.1457 +    {
  1.1458 +      typename Config::edge_property_type p;
  1.1459 +      return add_edge(u, v, p, g_);
  1.1460 +    }
  1.1461 +    // O(1)
  1.1462 +    template <class Config>
  1.1463 +    inline typename Config::degree_size_type
  1.1464 +    degree(typename Config::vertex_descriptor u, 
  1.1465 +           const bidirectional_graph_helper_with_property<Config>& g_)
  1.1466 +    {
  1.1467 +      typedef typename Config::graph_type graph_type;
  1.1468 +      const graph_type& g = static_cast<const graph_type&>(g_);
  1.1469 +      return in_degree(u, g) + out_degree(u, g);
  1.1470 +    }
  1.1471 +
  1.1472 +    //=========================================================================
  1.1473 +    // Adjacency List Helper Class
  1.1474 +
  1.1475 +    template <class Config, class Base>
  1.1476 +    struct adj_list_helper : public Base
  1.1477 +    {
  1.1478 +      typedef typename Config::graph_type AdjList;
  1.1479 +      typedef typename Config::vertex_descriptor vertex_descriptor;
  1.1480 +      typedef typename Config::edge_descriptor edge_descriptor;
  1.1481 +      typedef typename Config::out_edge_iterator out_edge_iterator;
  1.1482 +      typedef typename Config::in_edge_iterator in_edge_iterator;
  1.1483 +      typedef typename Config::adjacency_iterator adjacency_iterator;
  1.1484 +      typedef typename Config::inv_adjacency_iterator inv_adjacency_iterator;
  1.1485 +      typedef typename Config::vertex_iterator vertex_iterator;
  1.1486 +      typedef typename Config::edge_iterator edge_iterator;
  1.1487 +      typedef typename Config::directed_category directed_category;
  1.1488 +      typedef typename Config::edge_parallel_category edge_parallel_category;
  1.1489 +      typedef typename Config::vertices_size_type vertices_size_type;
  1.1490 +      typedef typename Config::edges_size_type edges_size_type;
  1.1491 +      typedef typename Config::degree_size_type degree_size_type;
  1.1492 +      typedef typename Config::StoredEdge StoredEdge;
  1.1493 +      typedef typename Config::edge_property_type edge_property_type;
  1.1494 +
  1.1495 +      typedef typename Config::global_edgelist_selector
  1.1496 +        global_edgelist_selector;
  1.1497 +
  1.1498 +      //    protected:
  1.1499 +
  1.1500 +      // The edge_dispatch() functions should be static, but
  1.1501 +      // Borland gets confused about constness.
  1.1502 +
  1.1503 +      // O(E/V)
  1.1504 +      inline std::pair<edge_descriptor,bool>      
  1.1505 +      edge_dispatch(const AdjList& g, 
  1.1506 +                    vertex_descriptor u, vertex_descriptor v, 
  1.1507 +                    boost::allow_parallel_edge_tag) const
  1.1508 +      {
  1.1509 +        bool found;
  1.1510 +        const typename Config::OutEdgeList& el = g.out_edge_list(u);
  1.1511 +        typename Config::OutEdgeList::const_iterator 
  1.1512 +          i = std::find_if(el.begin(), el.end(), 
  1.1513 +                           detail::target_is<vertex_descriptor>(v));
  1.1514 +        found = (i != g.out_edge_list(u).end());
  1.1515 +        if (found)
  1.1516 +          return std::make_pair(edge_descriptor(u, v, &(*i).get_property()),
  1.1517 +                                true);
  1.1518 +        else
  1.1519 +          return std::make_pair(edge_descriptor(u, v, 0), false);
  1.1520 +      }
  1.1521 +      // O(log(E/V))
  1.1522 +      inline std::pair<edge_descriptor,bool>      
  1.1523 +      edge_dispatch(const AdjList& g, 
  1.1524 +                    vertex_descriptor u, vertex_descriptor v, 
  1.1525 +                    boost::disallow_parallel_edge_tag) const
  1.1526 +      {
  1.1527 +        bool found;
  1.1528 +        /* According to the standard, this should be iterator, not const_iterator,
  1.1529 +           but the VC++ std::set::find() const returns const_iterator.
  1.1530 +           And since iterator should be convertible to const_iterator, the
  1.1531 +           following should work everywhere. -Jeremy */
  1.1532 +        typename Config::OutEdgeList::const_iterator 
  1.1533 +          i = g.out_edge_list(u).find(StoredEdge(v)),
  1.1534 +          end = g.out_edge_list(u).end();
  1.1535 +        found = (i != end);
  1.1536 +        if (found)
  1.1537 +          return std::make_pair(edge_descriptor(u, v, &(*i).get_property()),
  1.1538 +                                true);
  1.1539 +        else
  1.1540 +          return std::make_pair(edge_descriptor(u, v, 0), false);
  1.1541 +      }
  1.1542 +    };
  1.1543 +
  1.1544 +    template <class Config, class Base>
  1.1545 +    inline std::pair<typename Config::adjacency_iterator, 
  1.1546 +                     typename Config::adjacency_iterator>
  1.1547 +    adjacent_vertices(typename Config::vertex_descriptor u, 
  1.1548 +                      const adj_list_helper<Config, Base>& g_)
  1.1549 +    {
  1.1550 +      typedef typename Config::graph_type AdjList;
  1.1551 +      const AdjList& cg = static_cast<const AdjList&>(g_);
  1.1552 +      AdjList& g = const_cast<AdjList&>(cg);
  1.1553 +      typedef typename Config::adjacency_iterator adjacency_iterator;
  1.1554 +      typename Config::out_edge_iterator first, last;
  1.1555 +      boost::tie(first, last) = out_edges(u, g);
  1.1556 +      return std::make_pair(adjacency_iterator(first, &g),
  1.1557 +                            adjacency_iterator(last, &g));
  1.1558 +    }
  1.1559 +    template <class Config, class Base>
  1.1560 +    inline std::pair<typename Config::inv_adjacency_iterator, 
  1.1561 +                     typename Config::inv_adjacency_iterator>
  1.1562 +    inv_adjacent_vertices(typename Config::vertex_descriptor u, 
  1.1563 +                          const adj_list_helper<Config, Base>& g_)
  1.1564 +    {
  1.1565 +      typedef typename Config::graph_type AdjList;
  1.1566 +      const AdjList& cg = static_cast<const AdjList&>(g_);
  1.1567 +      AdjList& g = const_cast<AdjList&>(cg);
  1.1568 +      typedef typename Config::inv_adjacency_iterator inv_adjacency_iterator;
  1.1569 +      typename Config::in_edge_iterator first, last;
  1.1570 +      boost::tie(first, last) = in_edges(u, g);
  1.1571 +      return std::make_pair(inv_adjacency_iterator(first, &g),
  1.1572 +                            inv_adjacency_iterator(last, &g));
  1.1573 +    }
  1.1574 +    template <class Config, class Base>
  1.1575 +    inline std::pair<typename Config::out_edge_iterator, 
  1.1576 +                     typename Config::out_edge_iterator>
  1.1577 +    out_edges(typename Config::vertex_descriptor u, 
  1.1578 +              const adj_list_helper<Config, Base>& g_)
  1.1579 +    {
  1.1580 +      typedef typename Config::graph_type AdjList;
  1.1581 +      typedef typename Config::out_edge_iterator out_edge_iterator;
  1.1582 +      const AdjList& cg = static_cast<const AdjList&>(g_);
  1.1583 +      AdjList& g = const_cast<AdjList&>(cg);
  1.1584 +      return
  1.1585 +        std::make_pair(out_edge_iterator(g.out_edge_list(u).begin(), u),
  1.1586 +                       out_edge_iterator(g.out_edge_list(u).end(), u));
  1.1587 +    }
  1.1588 +    template <class Config, class Base>
  1.1589 +    inline std::pair<typename Config::vertex_iterator, 
  1.1590 +                     typename Config::vertex_iterator>
  1.1591 +    vertices(const adj_list_helper<Config, Base>& g_)
  1.1592 +    {
  1.1593 +      typedef typename Config::graph_type AdjList;
  1.1594 +      const AdjList& cg = static_cast<const AdjList&>(g_);
  1.1595 +      AdjList& g = const_cast<AdjList&>(cg);
  1.1596 +      return std::make_pair( g.vertex_set().begin(), g.vertex_set().end() );
  1.1597 +    }
  1.1598 +    template <class Config, class Base>
  1.1599 +    inline typename Config::vertices_size_type
  1.1600 +    num_vertices(const adj_list_helper<Config, Base>& g_)
  1.1601 +    {
  1.1602 +      typedef typename Config::graph_type AdjList;
  1.1603 +      const AdjList& g = static_cast<const AdjList&>(g_);
  1.1604 +      return g.vertex_set().size();
  1.1605 +    }
  1.1606 +    template <class Config, class Base>
  1.1607 +    inline typename Config::degree_size_type
  1.1608 +    out_degree(typename Config::vertex_descriptor u, 
  1.1609 +               const adj_list_helper<Config, Base>& g_)
  1.1610 +    {
  1.1611 +      typedef typename Config::graph_type AdjList;
  1.1612 +      const AdjList& g = static_cast<const AdjList&>(g_);
  1.1613 +      return g.out_edge_list(u).size();
  1.1614 +    }
  1.1615 +    template <class Config, class Base>
  1.1616 +    inline std::pair<typename Config::edge_descriptor, bool>
  1.1617 +    edge(typename Config::vertex_descriptor u, 
  1.1618 +         typename Config::vertex_descriptor v, 
  1.1619 +         const adj_list_helper<Config, Base>& g_)
  1.1620 +    {
  1.1621 +      typedef typename Config::graph_type Graph;
  1.1622 +      typedef typename Config::edge_parallel_category Cat;
  1.1623 +      const Graph& g = static_cast<const Graph&>(g_);
  1.1624 +      return g_.edge_dispatch(g, u, v, Cat());
  1.1625 +    }
  1.1626 +    template <class Config, class Base>
  1.1627 +    inline std::pair<typename Config::out_edge_iterator,
  1.1628 +                     typename Config::out_edge_iterator>
  1.1629 +    edge_range(typename Config::vertex_descriptor u,
  1.1630 +               typename Config::vertex_descriptor v,
  1.1631 +               const adj_list_helper<Config, Base>& g_)
  1.1632 +    {
  1.1633 +      typedef typename Config::graph_type Graph;
  1.1634 +      typedef typename Config::StoredEdge StoredEdge;
  1.1635 +      const Graph& cg = static_cast<const Graph&>(g_);
  1.1636 +      Graph& g = const_cast<Graph&>(cg);
  1.1637 +      typedef typename Config::out_edge_iterator out_edge_iterator;
  1.1638 +      typename Config::OutEdgeList& el = g.out_edge_list(u);
  1.1639 +      typename Config::OutEdgeList::iterator first, last;
  1.1640 +      typename Config::EdgeContainer fake_edge_container;
  1.1641 +      tie(first, last) = 
  1.1642 +        std::equal_range(el.begin(), el.end(), 
  1.1643 +                         StoredEdge(v, fake_edge_container.end(),
  1.1644 +                                    &fake_edge_container));
  1.1645 +      return std::make_pair(out_edge_iterator(first, u),
  1.1646 +                            out_edge_iterator(last, u));
  1.1647 +    }
  1.1648 +
  1.1649 +    template <class Config>
  1.1650 +    inline typename Config::degree_size_type
  1.1651 +    in_degree(typename Config::vertex_descriptor u, 
  1.1652 +              const directed_edges_helper<Config>& g_)
  1.1653 +    {
  1.1654 +      typedef typename Config::graph_type Graph;
  1.1655 +      const Graph& cg = static_cast<const Graph&>(g_);
  1.1656 +      Graph& g = const_cast<Graph&>(cg);
  1.1657 +      return in_edge_list(g, u).size();
  1.1658 +    }
  1.1659 +
  1.1660 +    namespace detail {
  1.1661 +      template <class Config, class Base, class Property>
  1.1662 +      inline
  1.1663 +      typename boost::property_map<typename Config::graph_type,
  1.1664 +        Property>::type
  1.1665 +      get_dispatch(adj_list_helper<Config,Base>&, Property, 
  1.1666 +                   boost::edge_property_tag) {
  1.1667 +        typedef typename Config::graph_type Graph;
  1.1668 +        typedef typename boost::property_map<Graph, Property>::type PA;
  1.1669 +        return PA();
  1.1670 +      }
  1.1671 +      template <class Config, class Base, class Property>
  1.1672 +      inline
  1.1673 +      typename boost::property_map<typename Config::graph_type, 
  1.1674 +        Property>::const_type
  1.1675 +      get_dispatch(const adj_list_helper<Config,Base>&, Property, 
  1.1676 +                   boost::edge_property_tag) {
  1.1677 +        typedef typename Config::graph_type Graph;
  1.1678 +        typedef typename boost::property_map<Graph, Property>::const_type PA;
  1.1679 +        return PA();
  1.1680 +      }
  1.1681 +
  1.1682 +      template <class Config, class Base, class Property>
  1.1683 +      inline
  1.1684 +      typename boost::property_map<typename Config::graph_type, 
  1.1685 +        Property>::type
  1.1686 +      get_dispatch(adj_list_helper<Config,Base>& g, Property, 
  1.1687 +                   boost::vertex_property_tag) {
  1.1688 +        typedef typename Config::graph_type Graph;
  1.1689 +        typedef typename boost::property_map<Graph, Property>::type PA;
  1.1690 +        return PA(&static_cast<Graph&>(g));
  1.1691 +      }
  1.1692 +      template <class Config, class Base, class Property>
  1.1693 +      inline
  1.1694 +      typename boost::property_map<typename Config::graph_type,
  1.1695 +        Property>::const_type
  1.1696 +      get_dispatch(const adj_list_helper<Config, Base>& g, Property, 
  1.1697 +                   boost::vertex_property_tag) {
  1.1698 +        typedef typename Config::graph_type Graph;
  1.1699 +        typedef typename boost::property_map<Graph, Property>::const_type PA;
  1.1700 +        const Graph& cg = static_cast<const Graph&>(g);
  1.1701 +        return PA(&cg);
  1.1702 +      }
  1.1703 +
  1.1704 +    } // namespace detail
  1.1705 +
  1.1706 +    // Implementation of the PropertyGraph interface
  1.1707 +    template <class Config, class Base, class Property>
  1.1708 +    inline
  1.1709 +    typename boost::property_map<typename Config::graph_type, Property>::type
  1.1710 +    get(Property p, adj_list_helper<Config, Base>& g) {
  1.1711 +      typedef typename property_kind<Property>::type Kind;
  1.1712 +      return detail::get_dispatch(g, p, Kind());
  1.1713 +    }
  1.1714 +    template <class Config, class Base, class Property>
  1.1715 +    inline
  1.1716 +    typename boost::property_map<typename Config::graph_type, 
  1.1717 +      Property>::const_type
  1.1718 +    get(Property p, const adj_list_helper<Config, Base>& g) {
  1.1719 +      typedef typename property_kind<Property>::type Kind;
  1.1720 +      return detail::get_dispatch(g, p, Kind());
  1.1721 +    }
  1.1722 +
  1.1723 +    template <class Config, class Base, class Property, class Key>
  1.1724 +    inline
  1.1725 +    typename boost::property_traits<
  1.1726 +      typename boost::property_map<typename Config::graph_type, 
  1.1727 +        Property>::type
  1.1728 +    >::reference
  1.1729 +    get(Property p, adj_list_helper<Config, Base>& g, const Key& key) {
  1.1730 +      return get(get(p, g), key);
  1.1731 +    }
  1.1732 +
  1.1733 +    template <class Config, class Base, class Property, class Key>
  1.1734 +    inline
  1.1735 +    typename boost::property_traits<
  1.1736 +      typename boost::property_map<typename Config::graph_type, 
  1.1737 +        Property>::const_type
  1.1738 +    >::reference
  1.1739 +    get(Property p, const adj_list_helper<Config, Base>& g, const Key& key) {
  1.1740 +      return get(get(p, g), key);
  1.1741 +    }
  1.1742 +
  1.1743 +    template <class Config, class Base, class Property, class Key,class Value>
  1.1744 +    inline void
  1.1745 +    put(Property p, adj_list_helper<Config, Base>& g, 
  1.1746 +        const Key& key, const Value& value)
  1.1747 +    {
  1.1748 +      typedef typename Config::graph_type Graph;
  1.1749 +      typedef typename boost::property_map<Graph, Property>::type Map;
  1.1750 +      Map pmap = get(p, static_cast<Graph&>(g));
  1.1751 +      put(pmap, key, value);
  1.1752 +    }
  1.1753 +
  1.1754 +
  1.1755 +    //=========================================================================
  1.1756 +    // Generalize Adjacency List Implementation
  1.1757 +
  1.1758 +    struct adj_list_tag { };
  1.1759 +
  1.1760 +    template <class Derived, class Config, class Base>
  1.1761 +    class adj_list_impl
  1.1762 +      : public adj_list_helper<Config, Base>
  1.1763 +    {
  1.1764 +      typedef typename Config::OutEdgeList OutEdgeList;
  1.1765 +      typedef typename Config::InEdgeList InEdgeList;
  1.1766 +      typedef typename Config::StoredVertexList StoredVertexList;
  1.1767 +    public:
  1.1768 +      typedef typename Config::stored_vertex stored_vertex;
  1.1769 +      typedef typename Config::EdgeContainer EdgeContainer;
  1.1770 +      typedef typename Config::vertex_descriptor vertex_descriptor;
  1.1771 +      typedef typename Config::edge_descriptor edge_descriptor;
  1.1772 +      typedef typename Config::vertex_iterator vertex_iterator;
  1.1773 +      typedef typename Config::edge_iterator edge_iterator;
  1.1774 +      typedef typename Config::edge_parallel_category edge_parallel_category;
  1.1775 +      typedef typename Config::vertices_size_type vertices_size_type;
  1.1776 +      typedef typename Config::edges_size_type edges_size_type;
  1.1777 +      typedef typename Config::degree_size_type degree_size_type;
  1.1778 +      typedef typename Config::edge_property_type edge_property_type;
  1.1779 +      typedef adj_list_tag graph_tag;
  1.1780 +
  1.1781 +      static vertex_descriptor null_vertex()
  1.1782 +      {
  1.1783 +        return 0;
  1.1784 +      }
  1.1785 +      
  1.1786 +      inline adj_list_impl() { }
  1.1787 +
  1.1788 +      inline adj_list_impl(const adj_list_impl& x) {
  1.1789 +        copy_impl(x);
  1.1790 +      }
  1.1791 +      inline adj_list_impl& operator=(const adj_list_impl& x) {
  1.1792 +        this->clear();
  1.1793 +        copy_impl(x);
  1.1794 +        return *this;
  1.1795 +      }
  1.1796 +      inline void clear() {
  1.1797 +        for (typename StoredVertexList::iterator i = m_vertices.begin();
  1.1798 +             i != m_vertices.end(); ++i)
  1.1799 +          delete (stored_vertex*)*i;
  1.1800 +        m_vertices.clear();
  1.1801 +        m_edges.clear();
  1.1802 +      }
  1.1803 +      inline adj_list_impl(vertices_size_type num_vertices) {
  1.1804 +        for (vertices_size_type i = 0; i < num_vertices; ++i)
  1.1805 +          add_vertex(static_cast<Derived&>(*this));
  1.1806 +      }
  1.1807 +      template <class EdgeIterator>
  1.1808 +      inline adj_list_impl(vertices_size_type num_vertices,
  1.1809 +                           EdgeIterator first, EdgeIterator last)
  1.1810 +      {
  1.1811 +        vertex_descriptor* v = new vertex_descriptor[num_vertices];
  1.1812 +        for (vertices_size_type i = 0; i < num_vertices; ++i)
  1.1813 +          v[i] = add_vertex(static_cast<Derived&>(*this));
  1.1814 +
  1.1815 +        while (first != last) {
  1.1816 +          add_edge(v[(*first).first], v[(*first).second], *this);
  1.1817 +          ++first;
  1.1818 +        }
  1.1819 +        delete [] v;
  1.1820 +      }
  1.1821 +      template <class EdgeIterator, class EdgePropertyIterator>
  1.1822 +      inline adj_list_impl(vertices_size_type num_vertices,
  1.1823 +                           EdgeIterator first, EdgeIterator last,
  1.1824 +                           EdgePropertyIterator ep_iter)
  1.1825 +      {
  1.1826 +        vertex_descriptor* v = new vertex_descriptor[num_vertices];
  1.1827 +        for (vertices_size_type i = 0; i < num_vertices; ++i)
  1.1828 +          v[i] = add_vertex(static_cast<Derived&>(*this));
  1.1829 +
  1.1830 +        while (first != last) {
  1.1831 +          add_edge(v[(*first).first], v[(*first).second], *ep_iter, *this);
  1.1832 +          ++first;
  1.1833 +          ++ep_iter;
  1.1834 +        }
  1.1835 +        delete [] v;
  1.1836 +      }
  1.1837 +      ~adj_list_impl() {
  1.1838 +        for (typename StoredVertexList::iterator i = m_vertices.begin();
  1.1839 +             i != m_vertices.end(); ++i)
  1.1840 +          delete (stored_vertex*)*i;
  1.1841 +      }
  1.1842 +      //    protected:
  1.1843 +      inline OutEdgeList& out_edge_list(vertex_descriptor v) {
  1.1844 +        stored_vertex* sv = (stored_vertex*)v;
  1.1845 +        return sv->m_out_edges;
  1.1846 +      }
  1.1847 +      inline const OutEdgeList& out_edge_list(vertex_descriptor v) const {
  1.1848 +        stored_vertex* sv = (stored_vertex*)v;
  1.1849 +        return sv->m_out_edges;
  1.1850 +      }
  1.1851 +      inline StoredVertexList& vertex_set() { return m_vertices; }
  1.1852 +      inline const StoredVertexList& vertex_set() const { return m_vertices; }
  1.1853 +
  1.1854 +      inline void copy_impl(const adj_list_impl& x_) 
  1.1855 +      {
  1.1856 +        const Derived& x = static_cast<const Derived&>(x_);
  1.1857 +
  1.1858 +        // Would be better to have a constant time way to get from
  1.1859 +        // vertices in x to the corresponding vertices in *this.
  1.1860 +        std::map<stored_vertex*,stored_vertex*> vertex_map;
  1.1861 +
  1.1862 +        // Copy the stored vertex objects by adding each vertex
  1.1863 +        // and copying its property object.
  1.1864 +        vertex_iterator vi, vi_end;
  1.1865 +        for (tie(vi, vi_end) = vertices(x); vi != vi_end; ++vi) {
  1.1866 +          stored_vertex* v = (stored_vertex*)add_vertex(*this);
  1.1867 +          v->m_property = ((stored_vertex*)*vi)->m_property;
  1.1868 +          vertex_map[(stored_vertex*)*vi] = v;
  1.1869 +        }
  1.1870 +        // Copy the edges by adding each edge and copying its
  1.1871 +        // property object.
  1.1872 +        edge_iterator ei, ei_end;
  1.1873 +        for (tie(ei, ei_end) = edges(x); ei != ei_end; ++ei) {
  1.1874 +          edge_descriptor e;
  1.1875 +          bool inserted; 
  1.1876 +          vertex_descriptor s = source(*ei,x), t = target(*ei,x);
  1.1877 +          tie(e, inserted) = add_edge(vertex_map[(stored_vertex*)s], 
  1.1878 +                                      vertex_map[(stored_vertex*)t], *this);
  1.1879 +          *((edge_property_type*)e.m_eproperty)
  1.1880 +            = *((edge_property_type*)(*ei).m_eproperty);
  1.1881 +        }
  1.1882 +      }
  1.1883 +
  1.1884 +
  1.1885 +      typename Config::EdgeContainer m_edges;
  1.1886 +      StoredVertexList m_vertices;
  1.1887 +    };
  1.1888 +
  1.1889 +    // O(1)
  1.1890 +    template <class Derived, class Config, class Base>
  1.1891 +    inline typename Config::vertex_descriptor
  1.1892 +    add_vertex(adj_list_impl<Derived, Config, Base>& g_)
  1.1893 +    {
  1.1894 +      Derived& g = static_cast<Derived&>(g_);
  1.1895 +      typedef typename Config::stored_vertex stored_vertex;
  1.1896 +      stored_vertex* v = new stored_vertex;
  1.1897 +      typename Config::StoredVertexList::iterator pos;
  1.1898 +      bool inserted;
  1.1899 +      boost::tie(pos,inserted) = boost::graph_detail::push(g.m_vertices, v);
  1.1900 +      v->m_position = pos;
  1.1901 +      return v;
  1.1902 +    }
  1.1903 +    // O(1)
  1.1904 +    template <class Derived, class Config, class Base>
  1.1905 +    inline typename Config::vertex_descriptor
  1.1906 +    add_vertex(const typename Config::vertex_property_type& p,
  1.1907 +               adj_list_impl<Derived, Config, Base>& g_)
  1.1908 +    {
  1.1909 +      Derived& g = static_cast<Derived&>(g_);
  1.1910 +      typedef typename Config::stored_vertex stored_vertex;
  1.1911 +      stored_vertex* v = new stored_vertex(p);
  1.1912 +      typename Config::StoredVertexList::iterator pos;
  1.1913 +      bool inserted;
  1.1914 +      boost::tie(pos,inserted) = boost::graph_detail::push(g.m_vertices, v);
  1.1915 +      v->m_position = pos;
  1.1916 +      return v;
  1.1917 +    }
  1.1918 +    // O(1)
  1.1919 +    template <class Derived, class Config, class Base>
  1.1920 +    inline void remove_vertex(typename Config::vertex_descriptor u,
  1.1921 +                              adj_list_impl<Derived, Config, Base>& g_)
  1.1922 +    {
  1.1923 +      typedef typename Config::stored_vertex stored_vertex;
  1.1924 +      Derived& g = static_cast<Derived&>(g_);
  1.1925 +      stored_vertex* su = (stored_vertex*)u;
  1.1926 +      g.m_vertices.erase(su->m_position);
  1.1927 +      delete su;
  1.1928 +    }
  1.1929 +    // O(V)
  1.1930 +    template <class Derived, class Config, class Base>
  1.1931 +    inline typename Config::vertex_descriptor
  1.1932 +    vertex(typename Config::vertices_size_type n, 
  1.1933 +           const adj_list_impl<Derived, Config, Base>& g_)
  1.1934 +    {
  1.1935 +      const Derived& g = static_cast<const Derived&>(g_);
  1.1936 +      typename Config::vertex_iterator i = vertices(g).first;
  1.1937 +      while (n--) ++i; // std::advance(i, n); (not VC++ portable)
  1.1938 +      return *i;
  1.1939 +    }
  1.1940 +
  1.1941 +    //=========================================================================
  1.1942 +    // Vector-Backbone Adjacency List Implementation
  1.1943 +
  1.1944 +    namespace detail {
  1.1945 +
  1.1946 +      template <class Graph, class vertex_descriptor>
  1.1947 +      inline void 
  1.1948 +      remove_vertex_dispatch(Graph& g, vertex_descriptor u, 
  1.1949 +                             boost::directed_tag)
  1.1950 +      {
  1.1951 +        typedef typename Graph::edge_parallel_category edge_parallel_category;
  1.1952 +        g.m_vertices.erase(g.m_vertices.begin() + u);
  1.1953 +        vertex_descriptor V = num_vertices(g);
  1.1954 +        if (u != V) {
  1.1955 +          for (vertex_descriptor v = 0; v < V; ++v)
  1.1956 +            reindex_edge_list(g.out_edge_list(v), u, edge_parallel_category());
  1.1957 +        }
  1.1958 +      }
  1.1959 +
  1.1960 +      template <class Graph, class vertex_descriptor>
  1.1961 +      inline void 
  1.1962 +      remove_vertex_dispatch(Graph& g, vertex_descriptor u, 
  1.1963 +                             boost::undirected_tag)
  1.1964 +      {
  1.1965 +        typedef typename Graph::global_edgelist_selector EdgeListS;
  1.1966 +        BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
  1.1967 +
  1.1968 +        typedef typename Graph::edge_parallel_category edge_parallel_category;
  1.1969 +        g.m_vertices.erase(g.m_vertices.begin() + u);
  1.1970 +        vertex_descriptor V = num_vertices(g);
  1.1971 +        for (vertex_descriptor v = 0; v < V; ++v)
  1.1972 +          reindex_edge_list(g.out_edge_list(v), u, 
  1.1973 +                            edge_parallel_category());
  1.1974 +        typedef typename Graph::EdgeContainer Container;
  1.1975 +        typedef typename Container::iterator Iter;
  1.1976 +        Iter ei = g.m_edges.begin(), ei_end = g.m_edges.end();
  1.1977 +        for (; ei != ei_end; ++ei) {
  1.1978 +          if (ei->m_source > u)
  1.1979 +            --ei->m_source;
  1.1980 +          if (ei->m_target > u)
  1.1981 +            --ei->m_target;
  1.1982 +        }
  1.1983 +      }
  1.1984 +      template <class Graph, class vertex_descriptor>
  1.1985 +      inline void 
  1.1986 +      remove_vertex_dispatch(Graph& g, vertex_descriptor u, 
  1.1987 +                             boost::bidirectional_tag)
  1.1988 +      {
  1.1989 +        typedef typename Graph::global_edgelist_selector EdgeListS;
  1.1990 +        BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
  1.1991 +
  1.1992 +        typedef typename Graph::edge_parallel_category edge_parallel_category;
  1.1993 +        g.m_vertices.erase(g.m_vertices.begin() + u);
  1.1994 +        vertex_descriptor V = num_vertices(g);
  1.1995 +        vertex_descriptor v;
  1.1996 +        if (u != V) {
  1.1997 +          for (v = 0; v < V; ++v)
  1.1998 +            reindex_edge_list(g.out_edge_list(v), u, 
  1.1999 +                              edge_parallel_category());
  1.2000 +          for (v = 0; v < V; ++v)
  1.2001 +            reindex_edge_list(in_edge_list(g, v), u, 
  1.2002 +                              edge_parallel_category());
  1.2003 +
  1.2004 +          typedef typename Graph::EdgeContainer Container;
  1.2005 +          typedef typename Container::iterator Iter;
  1.2006 +          Iter ei = g.m_edges.begin(), ei_end = g.m_edges.end();
  1.2007 +          for (; ei != ei_end; ++ei) {
  1.2008 +            if (ei->m_source > u)
  1.2009 +              --ei->m_source;
  1.2010 +            if (ei->m_target > u)
  1.2011 +              --ei->m_target;
  1.2012 +          }
  1.2013 +        }
  1.2014 +      }
  1.2015 +
  1.2016 +      template <class EdgeList, class vertex_descriptor>
  1.2017 +      inline void
  1.2018 +      reindex_edge_list(EdgeList& el, vertex_descriptor u, 
  1.2019 +                        boost::allow_parallel_edge_tag)
  1.2020 +      {
  1.2021 +        typename EdgeList::iterator ei = el.begin(), e_end = el.end();
  1.2022 +        for (; ei != e_end; ++ei)
  1.2023 +          if ((*ei).get_target() > u)
  1.2024 +            --(*ei).get_target();
  1.2025 +      }
  1.2026 +      template <class EdgeList, class vertex_descriptor>
  1.2027 +      inline void
  1.2028 +      reindex_edge_list(EdgeList& el, vertex_descriptor u, 
  1.2029 +                        boost::disallow_parallel_edge_tag)
  1.2030 +      {
  1.2031 +        typename EdgeList::iterator ei = el.begin(), e_end = el.end();
  1.2032 +        while (ei != e_end) {
  1.2033 +          typename EdgeList::value_type ce = *ei;
  1.2034 +          ++ei;
  1.2035 +          if (ce.get_target() > u) {
  1.2036 +            el.erase(ce);
  1.2037 +            --ce.get_target();
  1.2038 +            el.insert(ce);
  1.2039 +          }
  1.2040 +        }
  1.2041 +      }
  1.2042 +    } // namespace detail
  1.2043 +
  1.2044 +    struct vec_adj_list_tag { };
  1.2045 +    
  1.2046 +    template <class Graph, class Config, class Base>
  1.2047 +    class vec_adj_list_impl
  1.2048 +      : public adj_list_helper<Config, Base>
  1.2049 +    {
  1.2050 +      typedef typename Config::OutEdgeList OutEdgeList;
  1.2051 +      typedef typename Config::InEdgeList InEdgeList;
  1.2052 +      typedef typename Config::StoredVertexList StoredVertexList; 
  1.2053 +    public:
  1.2054 +      typedef typename Config::vertex_descriptor vertex_descriptor;
  1.2055 +      typedef typename Config::edge_descriptor edge_descriptor;
  1.2056 +      typedef typename Config::out_edge_iterator out_edge_iterator;
  1.2057 +      typedef typename Config::edge_iterator edge_iterator;
  1.2058 +      typedef typename Config::directed_category directed_category;
  1.2059 +      typedef typename Config::vertices_size_type vertices_size_type;
  1.2060 +      typedef typename Config::edges_size_type edges_size_type;
  1.2061 +      typedef typename Config::degree_size_type degree_size_type;
  1.2062 +      typedef typename Config::StoredEdge StoredEdge;
  1.2063 +      typedef typename Config::stored_vertex stored_vertex;
  1.2064 +      typedef typename Config::EdgeContainer EdgeContainer;
  1.2065 +      typedef typename Config::edge_property_type edge_property_type;
  1.2066 +      typedef vec_adj_list_tag graph_tag;
  1.2067 +
  1.2068 +      static vertex_descriptor null_vertex()
  1.2069 +      {
  1.2070 +        return (std::numeric_limits<vertex_descriptor>::max)();
  1.2071 +      }
  1.2072 +      
  1.2073 +      inline vec_adj_list_impl() { }
  1.2074 +
  1.2075 +      inline vec_adj_list_impl(const vec_adj_list_impl& x) {
  1.2076 +        copy_impl(x);
  1.2077 +      }
  1.2078 +      inline vec_adj_list_impl& operator=(const vec_adj_list_impl& x) {
  1.2079 +        this->clear();
  1.2080 +        copy_impl(x);
  1.2081 +        return *this;
  1.2082 +      }
  1.2083 +      inline void clear() {
  1.2084 +        m_vertices.clear();
  1.2085 +        m_edges.clear();
  1.2086 +      }
  1.2087 +
  1.2088 +      inline vec_adj_list_impl(vertices_size_type _num_vertices)
  1.2089 +        : m_vertices(_num_vertices) { }
  1.2090 +
  1.2091 +      template <class EdgeIterator>
  1.2092 +      inline vec_adj_list_impl(vertices_size_type num_vertices,
  1.2093 +                               EdgeIterator first, EdgeIterator last)
  1.2094 +        : m_vertices(num_vertices)
  1.2095 +      {
  1.2096 +        while (first != last) {
  1.2097 +          add_edge((*first).first, (*first).second, 
  1.2098 +                   static_cast<Graph&>(*this));
  1.2099 +          ++first;
  1.2100 +        }
  1.2101 +      }
  1.2102 +      template <class EdgeIterator, class EdgePropertyIterator>
  1.2103 +      inline vec_adj_list_impl(vertices_size_type num_vertices,
  1.2104 +                               EdgeIterator first, EdgeIterator last,
  1.2105 +                               EdgePropertyIterator ep_iter)
  1.2106 +        : m_vertices(num_vertices)
  1.2107 +      {
  1.2108 +        while (first != last) {
  1.2109 +          add_edge((*first).first, (*first).second, *ep_iter, 
  1.2110 +                   static_cast<Graph&>(*this));
  1.2111 +          ++first;
  1.2112 +          ++ep_iter;
  1.2113 +        }
  1.2114 +      }
  1.2115 +
  1.2116 +      //    protected:
  1.2117 +      inline boost::integer_range<vertex_descriptor> vertex_set() const {
  1.2118 +        return boost::integer_range<vertex_descriptor>(0, m_vertices.size());
  1.2119 +      }
  1.2120 +      inline OutEdgeList& out_edge_list(vertex_descriptor v) {
  1.2121 +        return m_vertices[v].m_out_edges;
  1.2122 +      }
  1.2123 +      inline const OutEdgeList& out_edge_list(vertex_descriptor v) const {
  1.2124 +        return m_vertices[v].m_out_edges;
  1.2125 +      }
  1.2126 +      inline void copy_impl(const vec_adj_list_impl& x_) 
  1.2127 +      {
  1.2128 +        const Graph& x = static_cast<const Graph&>(x_);
  1.2129 +        // Copy the stored vertex objects by adding each vertex
  1.2130 +        // and copying its property object.
  1.2131 +        for (vertices_size_type i = 0; i < num_vertices(x); ++i) {
  1.2132 +          vertex_descriptor v = add_vertex(*this);
  1.2133 +          m_vertices[v].m_property = x.m_vertices[i].m_property;
  1.2134 +        }
  1.2135 +        // Copy the edges by adding each edge and copying its
  1.2136 +        // property object.
  1.2137 +        edge_iterator ei, ei_end;
  1.2138 +        for (tie(ei, ei_end) = edges(x); ei != ei_end; ++ei) {
  1.2139 +          edge_descriptor e;
  1.2140 +          bool inserted; 
  1.2141 +          tie(e, inserted) = add_edge(source(*ei,x), target(*ei,x) , *this);
  1.2142 +          *((edge_property_type*)e.m_eproperty)
  1.2143 +            = *((edge_property_type*)(*ei).m_eproperty);
  1.2144 +        }
  1.2145 +      }
  1.2146 +      typename Config::EdgeContainer m_edges;
  1.2147 +      StoredVertexList m_vertices;
  1.2148 +    };
  1.2149 +    // Had to make these non-members to avoid accidental instantiation
  1.2150 +    // on SGI MIPSpro C++
  1.2151 +    template <class G, class C, class B>
  1.2152 +    inline typename C::InEdgeList& 
  1.2153 +    in_edge_list(vec_adj_list_impl<G,C,B>& g, 
  1.2154 +                 typename C::vertex_descriptor v) {
  1.2155 +      return g.m_vertices[v].m_in_edges;
  1.2156 +    }
  1.2157 +    template <class G, class C, class B>
  1.2158 +    inline const typename C::InEdgeList& 
  1.2159 +    in_edge_list(const vec_adj_list_impl<G,C,B>& g, 
  1.2160 +                 typename C::vertex_descriptor v) {
  1.2161 +      return g.m_vertices[v].m_in_edges;
  1.2162 +    }
  1.2163 +
  1.2164 +      // O(1)
  1.2165 +    template <class Graph, class Config, class Base>
  1.2166 +    inline typename Config::vertex_descriptor
  1.2167 +    add_vertex(vec_adj_list_impl<Graph, Config, Base>& g_) {
  1.2168 +      Graph& g = static_cast<Graph&>(g_);
  1.2169 +      g.m_vertices.resize(g.m_vertices.size() + 1);
  1.2170 +      return g.m_vertices.size() - 1;
  1.2171 +    }
  1.2172 +
  1.2173 +    template <class Graph, class Config, class Base>
  1.2174 +    inline typename Config::vertex_descriptor
  1.2175 +    add_vertex(const typename Config::vertex_property_type& p,
  1.2176 +               vec_adj_list_impl<Graph, Config, Base>& g_) {
  1.2177 +      Graph& g = static_cast<Graph&>(g_);
  1.2178 +      typedef typename Config::stored_vertex stored_vertex;
  1.2179 +      g.m_vertices.push_back(stored_vertex(p));
  1.2180 +      return g.m_vertices.size() - 1;
  1.2181 +    }
  1.2182 +
  1.2183 +    // Here we override the directed_graph_helper add_edge() function
  1.2184 +    // so that the number of vertices is automatically changed if
  1.2185 +    // either u or v is greater than the number of vertices.
  1.2186 +    template <class Graph, class Config, class Base>
  1.2187 +    inline std::pair<typename Config::edge_descriptor, bool>
  1.2188 +    add_edge(typename Config::vertex_descriptor u, 
  1.2189 +             typename Config::vertex_descriptor v,
  1.2190 +             const typename Config::edge_property_type& p,
  1.2191 +             vec_adj_list_impl<Graph, Config, Base>& g_)
  1.2192 +    {
  1.2193 +      BOOST_USING_STD_MAX();
  1.2194 +      typename Config::vertex_descriptor x = max BOOST_PREVENT_MACRO_SUBSTITUTION(u, v);
  1.2195 +      if (x >= num_vertices(g_))
  1.2196 +        g_.m_vertices.resize(x + 1);
  1.2197 +      adj_list_helper<Config, Base>& g = g_;
  1.2198 +      return add_edge(u, v, p, g);
  1.2199 +    }
  1.2200 +    template <class Graph, class Config, class Base>
  1.2201 +    inline std::pair<typename Config::edge_descriptor, bool>
  1.2202 +    add_edge(typename Config::vertex_descriptor u, 
  1.2203 +             typename Config::vertex_descriptor v,
  1.2204 +             vec_adj_list_impl<Graph, Config, Base>& g_)
  1.2205 +    {
  1.2206 +      typename Config::edge_property_type p;
  1.2207 +      return add_edge(u, v, p, g_);
  1.2208 +    }
  1.2209 +
  1.2210 +
  1.2211 +    // O(V + E)
  1.2212 +    template <class Graph, class Config, class Base>
  1.2213 +    inline void remove_vertex(typename Config::vertex_descriptor v,
  1.2214 +                              vec_adj_list_impl<Graph, Config, Base>& g_)
  1.2215 +    {
  1.2216 +      typedef typename Config::directed_category Cat;
  1.2217 +      Graph& g = static_cast<Graph&>(g_);
  1.2218 +      detail::remove_vertex_dispatch(g, v, Cat());
  1.2219 +    }
  1.2220 +    // O(1)
  1.2221 +    template <class Graph, class Config, class Base>
  1.2222 +    inline typename Config::vertex_descriptor 
  1.2223 +    vertex(typename Config::vertices_size_type n, 
  1.2224 +           const vec_adj_list_impl<Graph, Config, Base>&)
  1.2225 +    {
  1.2226 +      return n;
  1.2227 +    }
  1.2228 +
  1.2229 +
  1.2230 +  namespace detail {
  1.2231 +
  1.2232 +    //=========================================================================
  1.2233 +    // Adjacency List Generator
  1.2234 +
  1.2235 +    template <class Graph, class VertexListS, class OutEdgeListS,
  1.2236 +              class DirectedS, class VertexProperty, class EdgeProperty, 
  1.2237 +              class GraphProperty, class EdgeListS>
  1.2238 +    struct adj_list_gen
  1.2239 +    {
  1.2240 +      typedef typename detail::is_random_access<VertexListS>::type 
  1.2241 +        is_rand_access;
  1.2242 +      typedef typename has_property<EdgeProperty>::type has_edge_property; 
  1.2243 +      typedef typename DirectedS::is_directed_t DirectedT;
  1.2244 +      typedef typename DirectedS::is_bidir_t BidirectionalT;
  1.2245 +
  1.2246 +      struct config
  1.2247 +      {
  1.2248 +        typedef OutEdgeListS edgelist_selector;
  1.2249 +        typedef EdgeListS global_edgelist_selector;
  1.2250 +
  1.2251 +        typedef Graph graph_type;
  1.2252 +        typedef EdgeProperty edge_property_type;
  1.2253 +        typedef VertexProperty vertex_property_type;
  1.2254 +        typedef GraphProperty graph_property_type;
  1.2255 +        typedef std::size_t vertices_size_type;
  1.2256 +
  1.2257 +        typedef adjacency_list_traits<OutEdgeListS, VertexListS, DirectedS> 
  1.2258 +           Traits;
  1.2259 +
  1.2260 +        typedef typename Traits::directed_category directed_category;
  1.2261 +        typedef typename Traits::edge_parallel_category edge_parallel_category;
  1.2262 +        typedef typename Traits::vertex_descriptor vertex_descriptor;
  1.2263 +        typedef typename Traits::edge_descriptor edge_descriptor;
  1.2264 +
  1.2265 +        typedef void* vertex_ptr; 
  1.2266 +
  1.2267 +        // need to reorganize this to avoid instantiating stuff
  1.2268 +        // that doesn't get used -JGS
  1.2269 +
  1.2270 +        // VertexList and vertex_iterator
  1.2271 +        typedef typename container_gen<VertexListS, 
  1.2272 +          vertex_ptr>::type SeqVertexList;
  1.2273 +        typedef boost::integer_range<std::size_t> RandVertexList;
  1.2274 +        typedef typename boost::ct_if_t<is_rand_access,
  1.2275 +          RandVertexList, SeqVertexList>::type VertexList;
  1.2276 +
  1.2277 +        typedef typename VertexList::iterator vertex_iterator;
  1.2278 +
  1.2279 +        // EdgeContainer and StoredEdge
  1.2280 +
  1.2281 +        typedef typename container_gen<EdgeListS, 
  1.2282 +          list_edge<vertex_descriptor, EdgeProperty> >::type EdgeContainer;
  1.2283 +
  1.2284 +        typedef typename ct_and<DirectedT, 
  1.2285 +             typename ct_not<BidirectionalT>::type >::type on_edge_storage;
  1.2286 +
  1.2287 +        typedef typename boost::ct_if_t<on_edge_storage,
  1.2288 +          std::size_t, typename EdgeContainer::size_type
  1.2289 +        >::type edges_size_type;
  1.2290 +
  1.2291 +        typedef typename EdgeContainer::iterator EdgeIter;
  1.2292 +
  1.2293 +        typedef typename detail::is_random_access<EdgeListS>::type is_edge_ra;
  1.2294 +
  1.2295 +        typedef typename boost::ct_if_t<on_edge_storage,
  1.2296 +          stored_edge_property<vertex_descriptor, EdgeProperty>,
  1.2297 +          typename boost::ct_if_t<is_edge_ra,
  1.2298 +            stored_ra_edge_iter<vertex_descriptor, EdgeContainer, EdgeProperty>,
  1.2299 +            stored_edge_iter<vertex_descriptor, EdgeIter, EdgeProperty>
  1.2300 +          >::type
  1.2301 +        >::type StoredEdge;
  1.2302 +
  1.2303 +        // Adjacency Types
  1.2304 +
  1.2305 +        typedef typename container_gen<OutEdgeListS, StoredEdge>::type 
  1.2306 +          OutEdgeList;
  1.2307 +        typedef typename OutEdgeList::size_type degree_size_type;
  1.2308 +        typedef typename OutEdgeList::iterator OutEdgeIter;
  1.2309 +
  1.2310 +        typedef boost::detail::iterator_traits<OutEdgeIter> OutEdgeIterTraits;
  1.2311 +        typedef typename OutEdgeIterTraits::iterator_category OutEdgeIterCat;
  1.2312 +        typedef typename OutEdgeIterTraits::difference_type OutEdgeIterDiff;
  1.2313 +
  1.2314 +        typedef out_edge_iter<
  1.2315 +            OutEdgeIter, vertex_descriptor, edge_descriptor, OutEdgeIterDiff
  1.2316 +        > out_edge_iterator;
  1.2317 +
  1.2318 +        typedef typename adjacency_iterator_generator<graph_type,
  1.2319 +           vertex_descriptor, out_edge_iterator>::type adjacency_iterator;
  1.2320 +
  1.2321 +        typedef OutEdgeList InEdgeList;
  1.2322 +        typedef OutEdgeIter InEdgeIter;
  1.2323 +        typedef OutEdgeIterCat InEdgeIterCat;
  1.2324 +        typedef OutEdgeIterDiff InEdgeIterDiff;
  1.2325 +
  1.2326 +        typedef in_edge_iter<
  1.2327 +            InEdgeIter, vertex_descriptor, edge_descriptor, InEdgeIterDiff
  1.2328 +        > in_edge_iterator;
  1.2329 +
  1.2330 +        typedef typename inv_adjacency_iterator_generator<graph_type,
  1.2331 +           vertex_descriptor, in_edge_iterator>::type inv_adjacency_iterator;
  1.2332 +
  1.2333 +        // Edge Iterator
  1.2334 +
  1.2335 +        typedef boost::detail::iterator_traits<EdgeIter> EdgeIterTraits;
  1.2336 +        typedef typename EdgeIterTraits::iterator_category EdgeIterCat;
  1.2337 +        typedef typename EdgeIterTraits::difference_type EdgeIterDiff;
  1.2338 +
  1.2339 +        typedef undirected_edge_iter<
  1.2340 +            EdgeIter
  1.2341 +          , edge_descriptor
  1.2342 +          , EdgeIterDiff          
  1.2343 +        > UndirectedEdgeIter; // also used for bidirectional
  1.2344 +
  1.2345 +        typedef adj_list_edge_iterator<vertex_iterator, out_edge_iterator, 
  1.2346 +           graph_type> DirectedEdgeIter;
  1.2347 +
  1.2348 +        typedef typename boost::ct_if_t<on_edge_storage,
  1.2349 +          DirectedEdgeIter, UndirectedEdgeIter>::type edge_iterator;
  1.2350 +
  1.2351 +        // stored_vertex and StoredVertexList
  1.2352 +        typedef typename container_gen<VertexListS, vertex_ptr>::type
  1.2353 +          SeqStoredVertexList;
  1.2354 +        struct seq_stored_vertex {
  1.2355 +          seq_stored_vertex() { }
  1.2356 +          seq_stored_vertex(const VertexProperty& p) : m_property(p) { }
  1.2357 +          OutEdgeList m_out_edges;
  1.2358 +          VertexProperty m_property;
  1.2359 +          typename SeqStoredVertexList::iterator m_position;
  1.2360 +        };
  1.2361 +        struct bidir_seq_stored_vertex {
  1.2362 +          bidir_seq_stored_vertex() { }
  1.2363 +          bidir_seq_stored_vertex(const VertexProperty& p) : m_property(p) { }
  1.2364 +          OutEdgeList m_out_edges;
  1.2365 +          InEdgeList m_in_edges;
  1.2366 +          VertexProperty m_property;
  1.2367 +          typename SeqStoredVertexList::iterator m_position;
  1.2368 +        };
  1.2369 +        struct rand_stored_vertex {
  1.2370 +          rand_stored_vertex() { }
  1.2371 +          rand_stored_vertex(const VertexProperty& p) : m_property(p) { }
  1.2372 +          OutEdgeList m_out_edges;
  1.2373 +          VertexProperty m_property;
  1.2374 +        };
  1.2375 +        struct bidir_rand_stored_vertex {
  1.2376 +          bidir_rand_stored_vertex() { }
  1.2377 +          bidir_rand_stored_vertex(const VertexProperty& p) : m_property(p) { }
  1.2378 +          OutEdgeList m_out_edges;
  1.2379 +          InEdgeList m_in_edges;
  1.2380 +          VertexProperty m_property;
  1.2381 +        };
  1.2382 +        typedef typename boost::ct_if_t<is_rand_access,
  1.2383 +          typename boost::ct_if_t<BidirectionalT,
  1.2384 +            bidir_rand_stored_vertex, rand_stored_vertex>::type,
  1.2385 +          typename boost::ct_if_t<BidirectionalT,
  1.2386 +            bidir_seq_stored_vertex, seq_stored_vertex>::type
  1.2387 +        >::type StoredVertex;
  1.2388 +        struct stored_vertex : public StoredVertex {
  1.2389 +          stored_vertex() { }
  1.2390 +          stored_vertex(const VertexProperty& p) : StoredVertex(p) { }
  1.2391 +        };
  1.2392 +
  1.2393 +        typedef typename container_gen<VertexListS, stored_vertex>::type
  1.2394 +          RandStoredVertexList;
  1.2395 +        typedef typename boost::ct_if_t< is_rand_access,
  1.2396 +          RandStoredVertexList, SeqStoredVertexList>::type StoredVertexList;
  1.2397 +      }; // end of config
  1.2398 +
  1.2399 +
  1.2400 +      typedef typename boost::ct_if_t<BidirectionalT,
  1.2401 +        bidirectional_graph_helper_with_property<config>,
  1.2402 +        typename boost::ct_if_t<DirectedT,
  1.2403 +          directed_graph_helper<config>,
  1.2404 +          undirected_graph_helper<config>
  1.2405 +        >::type
  1.2406 +      >::type DirectedHelper;
  1.2407 +
  1.2408 +      typedef typename boost::ct_if_t<is_rand_access,
  1.2409 +        vec_adj_list_impl<Graph, config, DirectedHelper>,
  1.2410 +        adj_list_impl<Graph, config, DirectedHelper>
  1.2411 +      >::type type;
  1.2412 +
  1.2413 +    };
  1.2414 +
  1.2415 +  } // namespace detail
  1.2416 +
  1.2417 +    //=========================================================================
  1.2418 +    // Vertex Property Maps
  1.2419 +
  1.2420 +    template <class Graph, class ValueType, class Reference, class Tag>
  1.2421 +    struct adj_list_vertex_property_map
  1.2422 +      : public boost::put_get_helper<
  1.2423 +          Reference,
  1.2424 +          adj_list_vertex_property_map<Graph, ValueType, Reference, Tag>
  1.2425 +        >
  1.2426 +    {
  1.2427 +      typedef typename Graph::stored_vertex StoredVertex;
  1.2428 +      typedef ValueType value_type;
  1.2429 +      typedef Reference reference;
  1.2430 +      typedef typename Graph::vertex_descriptor key_type;
  1.2431 +      typedef boost::lvalue_property_map_tag category;
  1.2432 +      inline adj_list_vertex_property_map() { }
  1.2433 +      inline adj_list_vertex_property_map(const Graph*) { }
  1.2434 +      inline Reference operator[](key_type v) const {
  1.2435 +        StoredVertex* sv = (StoredVertex*)v;
  1.2436 +        return get_property_value(sv->m_property, Tag());
  1.2437 +      }
  1.2438 +      inline Reference operator()(key_type v) const {
  1.2439 +        return this->operator[](v);
  1.2440 +      }
  1.2441 +    };
  1.2442 +
  1.2443 +    template <class Graph, class Property, class PropRef>
  1.2444 +    struct adj_list_vertex_all_properties_map
  1.2445 +      : public boost::put_get_helper<PropRef,
  1.2446 +          adj_list_vertex_all_properties_map<Graph, Property, PropRef>
  1.2447 +        >
  1.2448 +    {
  1.2449 +      typedef typename Graph::stored_vertex StoredVertex;
  1.2450 +      typedef Property value_type;
  1.2451 +      typedef PropRef reference;
  1.2452 +      typedef typename Graph::vertex_descriptor key_type;
  1.2453 +      typedef boost::lvalue_property_map_tag category;
  1.2454 +      inline adj_list_vertex_all_properties_map() { }
  1.2455 +      inline adj_list_vertex_all_properties_map(const Graph*) { }
  1.2456 +      inline PropRef operator[](key_type v) const {
  1.2457 +        StoredVertex* sv = (StoredVertex*)v;
  1.2458 +        return sv->m_property;
  1.2459 +      }
  1.2460 +      inline PropRef operator()(key_type v) const {
  1.2461 +        return this->operator[](v);
  1.2462 +      }
  1.2463 +    };
  1.2464 +
  1.2465 +    template <class Graph, class GraphPtr, class ValueType, class Reference,
  1.2466 +              class Tag>
  1.2467 +    struct vec_adj_list_vertex_property_map
  1.2468 +      : public boost::put_get_helper<
  1.2469 +          Reference,
  1.2470 +          vec_adj_list_vertex_property_map<Graph,GraphPtr,ValueType,Reference,
  1.2471 +             Tag>
  1.2472 +        >
  1.2473 +    {
  1.2474 +      typedef ValueType value_type;
  1.2475 +      typedef Reference reference;
  1.2476 +      typedef typename boost::graph_traits<Graph>::vertex_descriptor key_type;
  1.2477 +      typedef boost::lvalue_property_map_tag category;
  1.2478 +      vec_adj_list_vertex_property_map() { }
  1.2479 +      vec_adj_list_vertex_property_map(GraphPtr g) : m_g(g) { }
  1.2480 +      inline Reference operator[](key_type v) const {
  1.2481 +        return get_property_value(m_g->m_vertices[v].m_property,  Tag());
  1.2482 +      }
  1.2483 +      inline Reference operator()(key_type v) const {
  1.2484 +        return this->operator[](v);
  1.2485 +      }
  1.2486 +      GraphPtr m_g;
  1.2487 +    };
  1.2488 +
  1.2489 +    template <class Graph, class GraphPtr, class Property, class PropertyRef>
  1.2490 +    struct vec_adj_list_vertex_all_properties_map
  1.2491 +      : public boost::put_get_helper<PropertyRef,
  1.2492 +          vec_adj_list_vertex_all_properties_map<Graph,GraphPtr,Property,
  1.2493 +            PropertyRef>
  1.2494 +        >
  1.2495 +    {
  1.2496 +      typedef Property value_type;
  1.2497 +      typedef PropertyRef reference;
  1.2498 +      typedef typename boost::graph_traits<Graph>::vertex_descriptor key_type;
  1.2499 +      typedef boost::lvalue_property_map_tag category;
  1.2500 +      vec_adj_list_vertex_all_properties_map() { }
  1.2501 +      vec_adj_list_vertex_all_properties_map(GraphPtr g) : m_g(g) { }
  1.2502 +      inline PropertyRef operator[](key_type v) const {
  1.2503 +        return m_g->m_vertices[v].m_property;
  1.2504 +      }
  1.2505 +      inline PropertyRef operator()(key_type v) const {
  1.2506 +        return this->operator[](v);
  1.2507 +      }
  1.2508 +      GraphPtr m_g;
  1.2509 +    };
  1.2510 +
  1.2511 +    struct adj_list_any_vertex_pa {
  1.2512 +      template <class Tag, class Graph, class Property>
  1.2513 +      struct bind_ {
  1.2514 +        typedef typename property_value<Property, Tag>::type value_type;
  1.2515 +        typedef value_type& reference;
  1.2516 +        typedef const value_type& const_reference;
  1.2517 +
  1.2518 +        typedef adj_list_vertex_property_map
  1.2519 +          <Graph, value_type, reference, Tag> type;
  1.2520 +        typedef adj_list_vertex_property_map
  1.2521 +          <Graph, value_type, const_reference, Tag> const_type;
  1.2522 +      };
  1.2523 +    };
  1.2524 +    struct adj_list_all_vertex_pa {
  1.2525 +      template <class Tag, class Graph, class Property>
  1.2526 +      struct bind_ {
  1.2527 +        typedef typename Graph::vertex_descriptor Vertex;
  1.2528 +        typedef adj_list_vertex_all_properties_map<Graph,Property,
  1.2529 +          Property&> type;
  1.2530 +        typedef adj_list_vertex_all_properties_map<Graph,Property,
  1.2531 +          const Property&> const_type;
  1.2532 +      };
  1.2533 +    };
  1.2534 +
  1.2535 +    template <class Property, class Vertex>
  1.2536 +    struct vec_adj_list_vertex_id_map
  1.2537 +      : public boost::put_get_helper<
  1.2538 +          Vertex, vec_adj_list_vertex_id_map<Property, Vertex>
  1.2539 +        >
  1.2540 +    {
  1.2541 +      typedef Vertex value_type;
  1.2542 +      typedef Vertex key_type;
  1.2543 +      typedef Vertex reference;
  1.2544 +      typedef boost::readable_property_map_tag category;
  1.2545 +      inline vec_adj_list_vertex_id_map() { }
  1.2546 +      template <class Graph>
  1.2547 +      inline vec_adj_list_vertex_id_map(const Graph&) { }
  1.2548 +      inline value_type operator[](key_type v) const { return v; }
  1.2549 +      inline value_type operator()(key_type v) const { return v; }
  1.2550 +    };
  1.2551 +
  1.2552 +    struct vec_adj_list_any_vertex_pa {
  1.2553 +      template <class Tag, class Graph, class Property>
  1.2554 +      struct bind_ {
  1.2555 +        typedef typename property_value<Property, Tag>::type value_type;
  1.2556 +        typedef value_type& reference;
  1.2557 +        typedef const value_type& const_reference;
  1.2558 +
  1.2559 +        typedef vec_adj_list_vertex_property_map
  1.2560 +          <Graph, Graph*, value_type, reference, Tag> type;
  1.2561 +        typedef vec_adj_list_vertex_property_map
  1.2562 +          <Graph, const Graph*, value_type, const_reference, Tag> const_type;
  1.2563 +      };
  1.2564 +    };
  1.2565 +    struct vec_adj_list_id_vertex_pa {
  1.2566 +      template <class Tag, class Graph, class Property>
  1.2567 +      struct bind_ {
  1.2568 +        typedef typename Graph::vertex_descriptor Vertex;
  1.2569 +        typedef vec_adj_list_vertex_id_map<Property, Vertex> type;
  1.2570 +        typedef vec_adj_list_vertex_id_map<Property, Vertex> const_type;
  1.2571 +      };
  1.2572 +    };
  1.2573 +    struct vec_adj_list_all_vertex_pa {
  1.2574 +      template <class Tag, class Graph, class Property>
  1.2575 +      struct bind_ {
  1.2576 +        typedef typename Graph::vertex_descriptor Vertex;
  1.2577 +        typedef vec_adj_list_vertex_all_properties_map
  1.2578 +          <Graph, Graph*, Property, Property&> type;
  1.2579 +        typedef vec_adj_list_vertex_all_properties_map
  1.2580 +          <Graph, const Graph*, Property, const Property&> const_type;
  1.2581 +      };
  1.2582 +    };
  1.2583 +  namespace detail {
  1.2584 +    template <class Tag>
  1.2585 +    struct adj_list_choose_vertex_pa_helper {
  1.2586 +      typedef adj_list_any_vertex_pa type;
  1.2587 +    };
  1.2588 +    template <>
  1.2589 +    struct adj_list_choose_vertex_pa_helper<vertex_all_t> {
  1.2590 +      typedef adj_list_all_vertex_pa type;
  1.2591 +    };
  1.2592 +    template <class Tag, class Graph, class Property>
  1.2593 +    struct adj_list_choose_vertex_pa {
  1.2594 +      typedef typename adj_list_choose_vertex_pa_helper<Tag>::type Helper;
  1.2595 +      typedef typename Helper::template bind_<Tag,Graph,Property> Bind;
  1.2596 +      typedef typename Bind::type type;
  1.2597 +      typedef typename Bind::const_type const_type;
  1.2598 +    };
  1.2599 +
  1.2600 +
  1.2601 +    template <class Tag>
  1.2602 +    struct vec_adj_list_choose_vertex_pa_helper {
  1.2603 +      typedef vec_adj_list_any_vertex_pa type;
  1.2604 +    };
  1.2605 +    template <>
  1.2606 +    struct vec_adj_list_choose_vertex_pa_helper<vertex_index_t> {
  1.2607 +      typedef vec_adj_list_id_vertex_pa type;
  1.2608 +    };
  1.2609 +    template <>
  1.2610 +    struct vec_adj_list_choose_vertex_pa_helper<vertex_all_t> {
  1.2611 +      typedef vec_adj_list_all_vertex_pa type;
  1.2612 +    };
  1.2613 +    template <class Tag, class Graph, class Property>
  1.2614 +    struct vec_adj_list_choose_vertex_pa {
  1.2615 +      typedef typename vec_adj_list_choose_vertex_pa_helper<Tag>::type Helper;
  1.2616 +      typedef typename Helper::template bind_<Tag,Graph,Property> Bind;
  1.2617 +      typedef typename Bind::type type;
  1.2618 +      typedef typename Bind::const_type const_type;
  1.2619 +    };
  1.2620 +  } // namespace detail
  1.2621 +    
  1.2622 +    //=========================================================================
  1.2623 +    // Edge Property Map
  1.2624 +
  1.2625 +    template <class Directed, class Value, class Ref, class Vertex,
  1.2626 +              class Property, class Tag>
  1.2627 +    struct adj_list_edge_property_map
  1.2628 +      : public put_get_helper< 
  1.2629 +          Ref,
  1.2630 +          adj_list_edge_property_map<Directed, Value, Ref, Vertex, Property, 
  1.2631 +            Tag>
  1.2632 +        >
  1.2633 +    {
  1.2634 +      typedef Value value_type;
  1.2635 +      typedef Ref reference;
  1.2636 +      typedef detail::edge_desc_impl<Directed, Vertex> key_type;
  1.2637 +      typedef boost::lvalue_property_map_tag category;
  1.2638 +      inline Ref operator[](key_type e) const {
  1.2639 +        Property& p = *(Property*)e.get_property();
  1.2640 +        return get_property_value(p, Tag());
  1.2641 +      }
  1.2642 +      inline Ref operator()(key_type e) const {
  1.2643 +        return this->operator[](e);
  1.2644 +      }
  1.2645 +    };
  1.2646 +
  1.2647 +    template <class Directed, class Property, class PropRef, class PropPtr,
  1.2648 +      class Vertex>
  1.2649 +    struct adj_list_edge_all_properties_map
  1.2650 +      : public put_get_helper<PropRef,
  1.2651 +          adj_list_edge_all_properties_map<Directed, Property, PropRef, 
  1.2652 +            PropPtr, Vertex>
  1.2653 +        >
  1.2654 +    {
  1.2655 +      typedef Property value_type;
  1.2656 +      typedef PropRef reference;
  1.2657 +      typedef detail::edge_desc_impl<Directed, Vertex> key_type;
  1.2658 +      typedef boost::lvalue_property_map_tag category;
  1.2659 +      inline PropRef operator[](key_type e) const {
  1.2660 +        return *(PropPtr)e.get_property();
  1.2661 +      }
  1.2662 +      inline PropRef operator()(key_type e) const {
  1.2663 +        return this->operator[](e);
  1.2664 +      }
  1.2665 +    };
  1.2666 +
  1.2667 +  // Edge Property Maps
  1.2668 +
  1.2669 +  namespace detail {
  1.2670 +    struct adj_list_any_edge_pmap {
  1.2671 +      template <class Graph, class Property, class Tag>
  1.2672 +      struct bind_ {
  1.2673 +        typedef typename property_value<Property,Tag>::type value_type;
  1.2674 +        typedef value_type& reference;
  1.2675 +        typedef const value_type& const_reference;
  1.2676 +        
  1.2677 +        typedef adj_list_edge_property_map
  1.2678 +           <typename Graph::directed_category, value_type, reference, 
  1.2679 +            typename Graph::vertex_descriptor,Property,Tag> type;
  1.2680 +        typedef adj_list_edge_property_map
  1.2681 +           <typename Graph::directed_category, value_type, const_reference, 
  1.2682 +            typename Graph::vertex_descriptor,const Property, Tag> const_type;
  1.2683 +      };
  1.2684 +    };
  1.2685 +    struct adj_list_all_edge_pmap {
  1.2686 +      template <class Graph, class Property, class Tag>
  1.2687 +      struct bind_ {
  1.2688 +        typedef adj_list_edge_all_properties_map
  1.2689 +        <typename Graph::directed_category, Property, Property&, Property*,
  1.2690 +            typename Graph::vertex_descriptor> type;
  1.2691 +        typedef adj_list_edge_all_properties_map
  1.2692 +        <typename Graph::directed_category, Property, const Property&, 
  1.2693 +            const Property*, typename Graph::vertex_descriptor> const_type;
  1.2694 +      };
  1.2695 +    };
  1.2696 +
  1.2697 +    template <class Tag>
  1.2698 +    struct adj_list_choose_edge_pmap_helper {
  1.2699 +      typedef adj_list_any_edge_pmap type;
  1.2700 +    };
  1.2701 +    template <>
  1.2702 +    struct adj_list_choose_edge_pmap_helper<edge_all_t> {
  1.2703 +      typedef adj_list_all_edge_pmap type;
  1.2704 +    };
  1.2705 +    template <class Tag, class Graph, class Property>
  1.2706 +    struct adj_list_choose_edge_pmap {
  1.2707 +      typedef typename adj_list_choose_edge_pmap_helper<Tag>::type Helper;
  1.2708 +      typedef typename Helper::template bind_<Graph,Property,Tag> Bind;
  1.2709 +      typedef typename Bind::type type;
  1.2710 +      typedef typename Bind::const_type const_type;
  1.2711 +    };
  1.2712 +    struct adj_list_edge_property_selector {
  1.2713 +      template <class Graph, class Property, class Tag>
  1.2714 +      struct bind_ {
  1.2715 +        typedef adj_list_choose_edge_pmap<Tag,Graph,Property> Choice;
  1.2716 +        typedef typename Choice::type type;
  1.2717 +        typedef typename Choice::const_type const_type;
  1.2718 +      };
  1.2719 +    };
  1.2720 +  } // namespace detail
  1.2721 +
  1.2722 +  template <>  
  1.2723 +  struct edge_property_selector<adj_list_tag> {
  1.2724 +    typedef detail::adj_list_edge_property_selector type;
  1.2725 +  };
  1.2726 +  template <>  
  1.2727 +  struct edge_property_selector<vec_adj_list_tag> {
  1.2728 +    typedef detail::adj_list_edge_property_selector type;
  1.2729 +  };
  1.2730 +
  1.2731 +  // Vertex Property Maps
  1.2732 +
  1.2733 +  struct adj_list_vertex_property_selector {
  1.2734 +    template <class Graph, class Property, class Tag>
  1.2735 +    struct bind_ {
  1.2736 +      typedef detail::adj_list_choose_vertex_pa<Tag,Graph,Property> Choice;
  1.2737 +      typedef typename Choice::type type;
  1.2738 +      typedef typename Choice::const_type const_type;
  1.2739 +    };
  1.2740 +  };
  1.2741 +  template <>  
  1.2742 +  struct vertex_property_selector<adj_list_tag> {
  1.2743 +    typedef adj_list_vertex_property_selector type;
  1.2744 +  };
  1.2745 +
  1.2746 +  struct vec_adj_list_vertex_property_selector {
  1.2747 +    template <class Graph, class Property, class Tag>
  1.2748 +    struct bind_ {
  1.2749 +      typedef detail::vec_adj_list_choose_vertex_pa<Tag,Graph,Property> Choice;
  1.2750 +      typedef typename Choice::type type;
  1.2751 +      typedef typename Choice::const_type const_type;
  1.2752 +    };
  1.2753 +  };
  1.2754 +  template <>  
  1.2755 +  struct vertex_property_selector<vec_adj_list_tag> {
  1.2756 +    typedef vec_adj_list_vertex_property_selector type;
  1.2757 +  };
  1.2758 +
  1.2759 +} // namespace boost
  1.2760 +
  1.2761 +#if !defined(BOOST_NO_HASH) && !defined(BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION)
  1.2762 +namespace BOOST_STD_EXTENSION_NAMESPACE {
  1.2763 +
  1.2764 +  #if BOOST_WORKAROUND( _STLPORT_VERSION, >= 0x500 )
  1.2765 +  // STLport 5 already defines a hash<void*> specialization.
  1.2766 +  #else
  1.2767 +  template <>
  1.2768 +  struct hash< void* > // Need this when vertex_descriptor=void*
  1.2769 +  {
  1.2770 +    std::size_t
  1.2771 +    operator()(void* v) const { return (std::size_t)v; }
  1.2772 +  };
  1.2773 +  #endif
  1.2774 +
  1.2775 +  template <typename V>
  1.2776 +  struct hash< boost::detail::stored_edge<V> > 
  1.2777 +  {
  1.2778 +    std::size_t
  1.2779 +    operator()(const boost::detail::stored_edge<V>& e) const
  1.2780 +    {
  1.2781 +      return hash<V>()(e.m_target);
  1.2782 +    }
  1.2783 +  };
  1.2784 +
  1.2785 +  template <typename V, typename P>
  1.2786 +  struct hash< boost::detail::stored_edge_property <V,P> > 
  1.2787 +  {
  1.2788 +    std::size_t
  1.2789 +    operator()(const boost::detail::stored_edge_property<V,P>& e) const
  1.2790 +    {
  1.2791 +      return hash<V>()(e.m_target);
  1.2792 +    }
  1.2793 +  };
  1.2794 +
  1.2795 +  template <typename V, typename I, typename P>
  1.2796 +  struct hash< boost::detail::stored_edge_iter<V,I, P> > 
  1.2797 +  {
  1.2798 +    std::size_t
  1.2799 +    operator()(const boost::detail::stored_edge_iter<V,I,P>& e) const
  1.2800 +    {
  1.2801 +      return hash<V>()(e.m_target);
  1.2802 +    }
  1.2803 +  };
  1.2804 +
  1.2805 +}
  1.2806 +#endif
  1.2807 +
  1.2808 +
  1.2809 +#undef stored_edge
  1.2810 +#undef stored_edge_property
  1.2811 +#undef stored_edge_iter
  1.2812 +
  1.2813 +#endif // BOOST_GRAPH_DETAIL_DETAIL_ADJACENCY_LIST_CCT
  1.2814 +
  1.2815 +/*
  1.2816 +  Implementation Notes:
  1.2817 +  
  1.2818 +  Many of the public interface functions in this file would have been
  1.2819 +  more conveniently implemented as inline friend functions.
  1.2820 +  However there are a few compiler bugs that make that approach
  1.2821 +  non-portable.
  1.2822 + 
  1.2823 +  1. g++ inline friend in namespace bug
  1.2824 +  2. g++ using clause doesn't work with inline friends
  1.2825 +  3. VC++ doesn't have Koenig lookup
  1.2826 +
  1.2827 +  For these reasons, the functions were all written as non-inline free 
  1.2828 +  functions, and static cast was used to convert from the helper
  1.2829 +  class to the adjacency_list derived class.
  1.2830 +
  1.2831 +  Looking back, it might have been better to write out all functions
  1.2832 +  in terms of the adjacency_list, and then use a tag to dispatch
  1.2833 +  to the various helpers instead of using inheritance.
  1.2834 +
  1.2835 + */