// -*- c++ -*-

//=======================================================================

// Copyright 1997, 1998, 1999, 2000 University of Notre Dame.

// Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek

//

// Distributed under the Boost Software License, Version 1.0. (See

// accompanying file LICENSE_1_0.txt or copy at

// http://www.boost.org/LICENSE_1_0.txt)

//=======================================================================

#ifndef BOOST_GRAPH_DETAIL_ADJACENCY_LIST_HPP

#define BOOST_GRAPH_DETAIL_ADJACENCY_LIST_HPP

#include <map> // for vertex_map in copy_impl

#include <boost/config.hpp>

#include <boost/detail/workaround.hpp>

#include <boost/operators.hpp>

#include <boost/property_map.hpp>

#include <boost/pending/integer_range.hpp>

#include <boost/graph/graph_traits.hpp>

#include <memory>

#include <algorithm>

#include <boost/limits.hpp>

#include <boost/iterator/iterator_adaptor.hpp>

#include <boost/pending/ct_if.hpp>

#include <boost/graph/graph_concepts.hpp>

#include <boost/pending/container_traits.hpp>

#include <boost/graph/detail/adj_list_edge_iterator.hpp>

#include <boost/graph/properties.hpp>

#include <boost/pending/property.hpp>

#include <boost/graph/adjacency_iterator.hpp>

#include <boost/static_assert.hpp>

// Symbol truncation problems with MSVC, trying to shorten names.

#define stored_edge se_

#define stored_edge_property sep_

#define stored_edge_iter sei_

/*

  Outline for this file:

  out_edge_iterator and in_edge_iterator implementation

  edge_iterator for undirected graph

  stored edge types (these object live in the out-edge/in-edge lists)

  directed edges helper class

  directed graph helper class

  undirected graph helper class

  bidirectional graph helper class

  bidirectional graph helper class (without edge properties)

  bidirectional graph helper class (with edge properties)

  adjacency_list helper class

  adj_list_impl class

  vec_adj_list_impl class

  adj_list_gen class

  vertex property map

  edge property map

  Note: it would be nice to merge some of the undirected and

  bidirectional code... it is awful similar.

 */

namespace boost {

  namespace detail {

    template <typename DirectedS>

    struct directed_category_traits {

      typedef directed_tag directed_category;

    };

    template <>

    struct directed_category_traits<directedS> {

      typedef directed_tag directed_category;

    };

    template <>

    struct directed_category_traits<undirectedS> {

      typedef undirected_tag directed_category;

    };

    template <>

    struct directed_category_traits<bidirectionalS> {

      typedef bidirectional_tag directed_category;

    };

    template <class Vertex>

    struct target_is {

      target_is(const Vertex& v) : m_target(v) { }

      template <class StoredEdge>

      bool operator()(const StoredEdge& e) const {

        return e.get_target() == m_target;

      }

      Vertex m_target;

    };

    // O(E/V)

    template <class EdgeList, class vertex_descriptor>

    void erase_from_incidence_list(EdgeList& el, vertex_descriptor v,

                                   allow_parallel_edge_tag)

    {

      boost::graph_detail::erase_if(el, detail::target_is<vertex_descriptor>(v));

    }

    // O(log(E/V))

    template <class EdgeList, class vertex_descriptor>

    void erase_from_incidence_list(EdgeList& el, vertex_descriptor v,

                                   disallow_parallel_edge_tag)

    {

      typedef typename EdgeList::value_type StoredEdge;

      el.erase(StoredEdge(v));

    }

    //=========================================================================

    // Out-Edge and In-Edge Iterator Implementation

    template <class BaseIter, class VertexDescriptor, class EdgeDescriptor, class Difference>

    struct out_edge_iter

      : iterator_adaptor<

            out_edge_iter<BaseIter, VertexDescriptor, EdgeDescriptor, Difference>

          , BaseIter

          , EdgeDescriptor

          , use_default

          , EdgeDescriptor

          , Difference

        >

    {

      typedef iterator_adaptor<

          out_edge_iter<BaseIter, VertexDescriptor, EdgeDescriptor, Difference>

        , BaseIter

        , EdgeDescriptor

        , use_default

        , EdgeDescriptor

        , Difference

      > super_t;

      inline out_edge_iter() { }

        inline out_edge_iter(const BaseIter& i, const VertexDescriptor& src)

          : super_t(i), m_src(src) { }

      inline EdgeDescriptor

      dereference() const

      {

        return EdgeDescriptor(m_src, (*this->base()).get_target(), 

                              &(*this->base()).get_property());

      }

      VertexDescriptor m_src;

    };

    template <class BaseIter, class VertexDescriptor, class EdgeDescriptor, class Difference>

    struct in_edge_iter

      : iterator_adaptor<

            in_edge_iter<BaseIter, VertexDescriptor, EdgeDescriptor, Difference>

          , BaseIter

          , EdgeDescriptor

          , use_default

          , EdgeDescriptor

          , Difference

        >

    {

      typedef iterator_adaptor<

          in_edge_iter<BaseIter, VertexDescriptor, EdgeDescriptor, Difference>

        , BaseIter

        , EdgeDescriptor

        , use_default

        , EdgeDescriptor

        , Difference

      > super_t;

      inline in_edge_iter() { }

      inline in_edge_iter(const BaseIter& i, const VertexDescriptor& src) 

        : super_t(i), m_src(src) { }

      inline EdgeDescriptor

      dereference() const

      {

        return EdgeDescriptor((*this->base()).get_target(), m_src,

                              &this->base()->get_property());

      }

      VertexDescriptor m_src;

    };

    //=========================================================================

    // Undirected Edge Iterator Implementation

    template <class EdgeIter, class EdgeDescriptor, class Difference>

    struct undirected_edge_iter

      : iterator_adaptor<

            undirected_edge_iter<EdgeIter, EdgeDescriptor, Difference>

          , EdgeIter

          , EdgeDescriptor

          , use_default

          , EdgeDescriptor

          , Difference

        >

    {

      typedef iterator_adaptor<

          undirected_edge_iter<EdgeIter, EdgeDescriptor, Difference>

        , EdgeIter

        , EdgeDescriptor

        , use_default

        , EdgeDescriptor

        , Difference

      > super_t;

      undirected_edge_iter() {}

      explicit undirected_edge_iter(EdgeIter i)

          : super_t(i) {}

      inline EdgeDescriptor

      dereference() const {

        return EdgeDescriptor(

            (*this->base()).m_source

          , (*this->base()).m_target

          , &this->base()->get_property());

      }

    };

    //=========================================================================

    // Edge Storage Types (stored in the out-edge/in-edge lists)

    template <class Vertex>

    class stored_edge

      : public boost::equality_comparable1< stored_edge<Vertex>,

        boost::less_than_comparable1< stored_edge<Vertex> > >

    {

    public:

      typedef no_property property_type;

      inline stored_edge() { }

      inline stored_edge(Vertex target, const no_property& = no_property())

        : m_target(target) { }

      // Need to write this explicitly so stored_edge_property can

      // invoke Base::operator= (at least, for SGI MIPSPro compiler)

      inline stored_edge& operator=(const stored_edge& x) {

        m_target = x.m_target;

        return *this;

      }

      inline Vertex& get_target() const { return m_target; }

      inline const no_property& get_property() const { return s_prop; }

      inline bool operator==(const stored_edge& x) const

        { return m_target == x.get_target(); }

      inline bool operator<(const stored_edge& x) const

        { return m_target < x.get_target(); }

      //protected: need to add hash<> as a friend

      static no_property s_prop;

      // Sometimes target not used as key in the set, and in that case

      // it is ok to change the target.

      mutable Vertex m_target;

    };

    template <class Vertex>

    no_property stored_edge<Vertex>::s_prop;

    template <class Vertex, class Property>

    class stored_edge_property : public stored_edge<Vertex> {

      typedef stored_edge_property self;

      typedef stored_edge<Vertex> Base;

    public:

      typedef Property property_type;

      inline stored_edge_property() { }

      inline stored_edge_property(Vertex target,

                                  const Property& p = Property())

        : stored_edge<Vertex>(target), m_property(new Property(p)) { }

      stored_edge_property(const self& x) 

        : Base(x), m_property(const_cast<self&>(x).m_property) { }

      self& operator=(const self& x) {

        Base::operator=(x);

        m_property = const_cast<self&>(x).m_property; 

        return *this;

      }

      inline Property& get_property() { return *m_property; }

      inline const Property& get_property() const { return *m_property; }

    protected:

      // Holding the property by-value causes edge-descriptor

      // invalidation for add_edge() with EdgeList=vecS. Instead we

      // hold a pointer to the property. std::auto_ptr is not

      // a perfect fit for the job, but it is darn close.

      std::auto_ptr<Property> m_property;

    };

    template <class Vertex, class Iter, class Property>

    class stored_edge_iter

      : public stored_edge<Vertex>

    {

    public:

      typedef Property property_type;

      inline stored_edge_iter() { }

      inline stored_edge_iter(Vertex v)

        : stored_edge<Vertex>(v) { }

      inline stored_edge_iter(Vertex v, Iter i, void* = 0)

        : stored_edge<Vertex>(v), m_iter(i) { }

      inline Property& get_property() { return m_iter->get_property(); }

      inline const Property& get_property() const { 

        return m_iter->get_property();

      }

      inline Iter get_iter() const { return m_iter; }

    protected:

      Iter m_iter;

    };

    // For when the EdgeList is a std::vector.

    // Want to make the iterator stable, so use an offset

    // instead of an iterator into a std::vector

    template <class Vertex, class EdgeVec, class Property>

    class stored_ra_edge_iter

      : public stored_edge<Vertex>

    {

      typedef typename EdgeVec::iterator Iter;

    public:

      typedef Property property_type;

      inline stored_ra_edge_iter() { }

      inline stored_ra_edge_iter(Vertex v, Iter i = Iter(), 

                                 EdgeVec* edge_vec = 0)

        : stored_edge<Vertex>(v), m_i(i - edge_vec->begin()), m_vec(edge_vec){ }

      inline Property& get_property() { return (*m_vec)[m_i].get_property(); }

      inline const Property& get_property() const { 

        return (*m_vec)[m_i].get_property();

      }

      inline Iter get_iter() const { return m_vec->begin() + m_i; }

    protected:

      std::size_t m_i;

      EdgeVec* m_vec;

    };

  } // namespace detail

  template <class Tag, class Vertex, class Property>

  const typename property_value<Property,Tag>::type&

  get(Tag property_tag,

      const detail::stored_edge_property<Vertex, Property>& e)

  {

    return get_property_value(e.get_property(), property_tag);

  }

  template <class Tag, class Vertex, class Iter, class Property>

  const typename property_value<Property,Tag>::type&

  get(Tag property_tag,

      const detail::stored_edge_iter<Vertex, Iter, Property>& e)

  {

    return get_property_value(e.get_property(), property_tag);

  }

  template <class Tag, class Vertex, class EdgeVec, class Property>

  const typename property_value<Property,Tag>::type&

  get(Tag property_tag,

      const detail::stored_ra_edge_iter<Vertex, EdgeVec, Property>& e)

  {

    return get_property_value(e.get_property(), property_tag);

  }

    //=========================================================================

    // Directed Edges Helper Class

    namespace detail {

      // O(E/V)

      template <class edge_descriptor, class EdgeList, class StoredProperty>

      inline void

      remove_directed_edge_dispatch(edge_descriptor, EdgeList& el,

                                    StoredProperty& p)

      {

        for (typename EdgeList::iterator i = el.begin();

             i != el.end(); ++i)

          if (&(*i).get_property() == &p) {

            el.erase(i);

            return;

          }

      }

      template <class incidence_iterator, class EdgeList, class Predicate>

      inline void

      remove_directed_edge_if_dispatch(incidence_iterator first,

                                       incidence_iterator last, 

                                       EdgeList& el, Predicate pred,

                                       boost::allow_parallel_edge_tag)

      {

        // remove_if

        while (first != last && !pred(*first))

          ++first;

        incidence_iterator i = first;

        if (first != last)

          for (; i != last; ++i)

            if (!pred(*i)) {

              *first.base() = *i.base();

              ++first;

            }

        el.erase(first.base(), el.end());

      }

      template <class incidence_iterator, class EdgeList, class Predicate>

      inline void

      remove_directed_edge_if_dispatch(incidence_iterator first,

                                       incidence_iterator last, 

                                       EdgeList& el, 

                                       Predicate pred,

                                       boost::disallow_parallel_edge_tag)

      {

        for (incidence_iterator next = first;

             first != last; first = next) {

          ++next;

          if (pred(*first))

            el.erase( first.base() );

        }

      }

      template <class PropT, class Graph, class incidence_iterator, 

                class EdgeList, class Predicate>

      inline void

      undirected_remove_out_edge_if_dispatch(Graph& g, 

                                             incidence_iterator first,

                                             incidence_iterator last, 

                                             EdgeList& el, Predicate pred,

                                             boost::allow_parallel_edge_tag)

      {

        typedef typename Graph::global_edgelist_selector EdgeListS;

        BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));

        // remove_if

        while (first != last && !pred(*first))

          ++first;

        incidence_iterator i = first;

        bool self_loop_removed = false;

        if (first != last)

          for (; i != last; ++i) {

            if (self_loop_removed) {

              /* With self loops, the descriptor will show up

               * twice. The first time it will be removed, and now it

               * will be skipped.

               */

              self_loop_removed = false;

            }

            else if (!pred(*i)) {

              *first.base() = *i.base();

              ++first;

            } else {

              if (source(*i, g) == target(*i, g)) self_loop_removed = true;

              else {

                // Remove the edge from the target

                detail::remove_directed_edge_dispatch

                  (*i, 

                   g.out_edge_list(target(*i, g)), 

                   *(PropT*)(*i).get_property());

              }

              // Erase the edge property

              g.m_edges.erase( (*i.base()).get_iter() );

            }

          }

        el.erase(first.base(), el.end());

      }

      template <class PropT, class Graph, class incidence_iterator, 

                class EdgeList, class Predicate>

      inline void

      undirected_remove_out_edge_if_dispatch(Graph& g, 

                                             incidence_iterator first,

                                             incidence_iterator last, 

                                             EdgeList& el, 

                                             Predicate pred,

                                             boost::disallow_parallel_edge_tag)

      {

        typedef typename Graph::global_edgelist_selector EdgeListS;

        BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));

        for (incidence_iterator next = first;

             first != last; first = next) {

          ++next;

          if (pred(*first)) {

            if (source(*first, g) != target(*first, g)) {

              // Remove the edge from the target

              detail::remove_directed_edge_dispatch

                (*first, 

                 g.out_edge_list(target(*first, g)), 

                 *(PropT*)(*first).get_property());

            }

            // Erase the edge property

            g.m_edges.erase( (*first.base()).get_iter() );

            // Erase the edge in the source

            el.erase( first.base() );

          }

        }

      }

      // O(E/V)

      template <class edge_descriptor, class EdgeList, class StoredProperty>

      inline void

      remove_directed_edge_dispatch(edge_descriptor e, EdgeList& el,

                                    no_property&)

      {

        for (typename EdgeList::iterator i = el.begin();

             i != el.end(); ++i)

          if ((*i).get_target() == e.m_target) {

            el.erase(i);

            return;

          }

      }

    } // namespace detail

    template <class Config>

    struct directed_edges_helper {

      // Placement of these overloaded remove_edge() functions

      // inside the class avoids a VC++ bug.

      // O(E/V)

      inline void

      remove_edge(typename Config::edge_descriptor e)

      {

        typedef typename Config::graph_type graph_type;

        graph_type& g = static_cast<graph_type&>(*this);

        typename Config::OutEdgeList& el = g.out_edge_list(source(e, g));

        typedef typename Config::OutEdgeList::value_type::property_type PType;

        detail::remove_directed_edge_dispatch(e, el,

                                              *(PType*)e.get_property());

      }

      // O(1)

      inline void

      remove_edge(typename Config::out_edge_iterator iter)

      {

        typedef typename Config::graph_type graph_type;

        graph_type& g = static_cast<graph_type&>(*this);

        typename Config::edge_descriptor e = *iter;

        typename Config::OutEdgeList& el = g.out_edge_list(source(e, g));

        el.erase(iter.base());

      }

    };

    // O(1)

    template <class Config>

    inline std::pair<typename Config::edge_iterator, 

                     typename Config::edge_iterator>

    edges(const directed_edges_helper<Config>& g_)

    {

      typedef typename Config::graph_type graph_type;

      typedef typename Config::edge_iterator edge_iterator;

      const graph_type& cg = static_cast<const graph_type&>(g_);

      graph_type& g = const_cast<graph_type&>(cg);

      return std::make_pair( edge_iterator(g.vertex_set().begin(), 

                                           g.vertex_set().begin(), 

                                           g.vertex_set().end(), g),

                             edge_iterator(g.vertex_set().begin(),

                                           g.vertex_set().end(),

                                           g.vertex_set().end(), g) );

    }

    //=========================================================================

    // Directed Graph Helper Class

    struct adj_list_dir_traversal_tag :

      public virtual vertex_list_graph_tag,

      public virtual incidence_graph_tag,

      public virtual adjacency_graph_tag,

      public virtual edge_list_graph_tag { };

    template <class Config>

    struct directed_graph_helper

      : public directed_edges_helper<Config> { 

      typedef typename Config::edge_descriptor edge_descriptor;

      typedef adj_list_dir_traversal_tag traversal_category;

    };

    // O(E/V)

    template <class Config>

    inline void

    remove_edge(typename Config::vertex_descriptor u,

                typename Config::vertex_descriptor v,

                directed_graph_helper<Config>& g_)

    {

      typedef typename Config::graph_type graph_type;

      typedef typename Config::edge_parallel_category Cat;

      graph_type& g = static_cast<graph_type&>(g_);

      detail::erase_from_incidence_list(g.out_edge_list(u), v, Cat());

    }

    template <class Config, class Predicate>

    inline void

    remove_out_edge_if(typename Config::vertex_descriptor u, Predicate pred,

                       directed_graph_helper<Config>& g_)

    {

      typedef typename Config::graph_type graph_type;

      graph_type& g = static_cast<graph_type&>(g_);

      typename Config::out_edge_iterator first, last;

      tie(first, last) = out_edges(u, g);

      typedef typename Config::edge_parallel_category edge_parallel_category;

      detail::remove_directed_edge_if_dispatch

        (first, last, g.out_edge_list(u), pred, edge_parallel_category());

    }

    template <class Config, class Predicate>

    inline void

    remove_edge_if(Predicate pred, directed_graph_helper<Config>& g_)

    {

      typedef typename Config::graph_type graph_type;

      graph_type& g = static_cast<graph_type&>(g_);

      typename Config::vertex_iterator vi, vi_end;

      for (tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi)

        remove_out_edge_if(*vi, pred, g);

    }    

    template <class EdgeOrIter, class Config>

    inline void

    remove_edge(EdgeOrIter e_or_iter, directed_graph_helper<Config>& g_)

    {

      g_.remove_edge(e_or_iter);

    }

    // O(V + E) for allow_parallel_edges

    // O(V * log(E/V)) for disallow_parallel_edges

    template <class Config>

    inline void 

    clear_vertex(typename Config::vertex_descriptor u,

                 directed_graph_helper<Config>& g_)

    {

      typedef typename Config::graph_type graph_type;

      typedef typename Config::edge_parallel_category Cat;

      graph_type& g = static_cast<graph_type&>(g_);

      typename Config::vertex_iterator vi, viend;

      for (boost::tie(vi, viend) = vertices(g); vi != viend; ++vi)

        detail::erase_from_incidence_list(g.out_edge_list(*vi), u, Cat());

      g.out_edge_list(u).clear();

      // clear() should be a req of Sequence and AssociativeContainer,

      // or maybe just Container

    }

    template <class Config>

    inline void 

    clear_out_edges(typename Config::vertex_descriptor u,

                    directed_graph_helper<Config>& g_)

    {

      typedef typename Config::graph_type graph_type;

      typedef typename Config::edge_parallel_category Cat;

      graph_type& g = static_cast<graph_type&>(g_);

      g.out_edge_list(u).clear();

      // clear() should be a req of Sequence and AssociativeContainer,

      // or maybe just Container

    }

    // O(V), could do better...

    template <class Config>

    inline typename Config::edges_size_type

    num_edges(const directed_graph_helper<Config>& g_)

    {

      typedef typename Config::graph_type graph_type;

      const graph_type& g = static_cast<const graph_type&>(g_);

      typename Config::edges_size_type num_e = 0;

      typename Config::vertex_iterator vi, vi_end;

      for (boost::tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi)

        num_e += out_degree(*vi, g);

      return num_e;

    }

    // O(1) for allow_parallel_edge_tag

    // O(log(E/V)) for disallow_parallel_edge_tag

    template <class Config>

    inline std::pair<typename directed_graph_helper<Config>::edge_descriptor, bool>

    add_edge(typename Config::vertex_descriptor u, 

             typename Config::vertex_descriptor v,

             const typename Config::edge_property_type& p, 

             directed_graph_helper<Config>& g_)

    {

      typedef typename Config::edge_descriptor edge_descriptor;

      typedef typename Config::graph_type graph_type;

      typedef typename Config::StoredEdge StoredEdge;

      graph_type& g = static_cast<graph_type&>(g_);

      typename Config::OutEdgeList::iterator i; 

      bool inserted;

      boost::tie(i, inserted) = boost::graph_detail::push(g.out_edge_list(u), 

                                            StoredEdge(v, p));

      return std::make_pair(edge_descriptor(u, v, &(*i).get_property()), 

                            inserted);

    }

    // Did not use default argument here because that

    // causes Visual C++ to get confused.

    template <class Config>

    inline std::pair<typename Config::edge_descriptor, bool>

    add_edge(typename Config::vertex_descriptor u, 

             typename Config::vertex_descriptor v,

             directed_graph_helper<Config>& g_)

    {

      typename Config::edge_property_type p;

      return add_edge(u, v, p, g_);

    }

    //=========================================================================

    // Undirected Graph Helper Class

    template <class Config>

    struct undirected_graph_helper;

    struct undir_adj_list_traversal_tag : 

      public virtual vertex_list_graph_tag,

      public virtual incidence_graph_tag,

      public virtual adjacency_graph_tag,

      public virtual edge_list_graph_tag,

      public virtual bidirectional_graph_tag { };

    namespace detail {

      // using class with specialization for dispatch is a VC++ workaround.

      template <class StoredProperty>

      struct remove_undirected_edge_dispatch {

        // O(E/V)

        template <class edge_descriptor, class Config>

        static void

        apply(edge_descriptor e, 

              undirected_graph_helper<Config>& g_, 

              StoredProperty& p)

        {

          typedef typename Config::global_edgelist_selector EdgeListS;

          BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));

          typedef typename Config::graph_type graph_type;

          graph_type& g = static_cast<graph_type&>(g_);

          typename Config::OutEdgeList& out_el = g.out_edge_list(source(e, g));

          typename Config::OutEdgeList::iterator out_i = out_el.begin();

          for (; out_i != out_el.end(); ++out_i)

            if (&(*out_i).get_property() == &p) {

              out_el.erase(out_i);

              break;

            }

          typename Config::OutEdgeList& in_el = g.out_edge_list(target(e, g));

          typename Config::OutEdgeList::iterator in_i = in_el.begin();

          for (; in_i != in_el.end(); ++in_i)

            if (&(*in_i).get_property() == &p) {

              g.m_edges.erase((*in_i).get_iter());

              in_el.erase(in_i);

              return;

            }

        }

      };

      template <>

      struct remove_undirected_edge_dispatch<no_property> {

        // O(E/V)

        template <class edge_descriptor, class Config>

        static void

        apply(edge_descriptor e,

              undirected_graph_helper<Config>& g_,

              no_property&)

        {

          typedef typename Config::global_edgelist_selector EdgeListS;

          BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));

          typedef typename Config::graph_type graph_type;

          graph_type& g = static_cast<graph_type&>(g_);

          no_property* p = (no_property*)e.get_property();

          typename Config::OutEdgeList& out_el = g.out_edge_list(source(e, g));

          typename Config::OutEdgeList::iterator out_i = out_el.begin();

          for (; out_i != out_el.end(); ++out_i)

            if (&(*out_i).get_property() == p) {

              out_el.erase(out_i);

              break;

            }

          typename Config::OutEdgeList& in_el = g.out_edge_list(target(e, g));

          typename Config::OutEdgeList::iterator in_i = in_el.begin();

          for (; in_i != in_el.end(); ++in_i)

            if (&(*in_i).get_property() == p) {

              g.m_edges.erase((*in_i).get_iter());

              in_el.erase(in_i);

              return;

            }

        }

      };

      // O(E/V)

      template <class Graph, class EdgeList, class Vertex>

      inline void

      remove_edge_and_property(Graph& g, EdgeList& el, Vertex v, 

                               boost::allow_parallel_edge_tag cat)

      {

        typedef typename Graph::global_edgelist_selector EdgeListS;

        BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));

        typedef typename EdgeList::value_type StoredEdge;

        typename EdgeList::iterator i = el.begin(), end = el.end();

        for (; i != end; ++i)

          if ((*i).get_target() == v)

            g.m_edges.erase((*i).get_iter());

        detail::erase_from_incidence_list(el, v, cat);

      }

      // O(log(E/V))

      template <class Graph, class EdgeList, class Vertex>

      inline void

      remove_edge_and_property(Graph& g, EdgeList& el, Vertex v, 

                               boost::disallow_parallel_edge_tag)

      {

        typedef typename Graph::global_edgelist_selector EdgeListS;

        BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));

        typedef typename EdgeList::value_type StoredEdge;

        typename EdgeList::iterator i = el.find(StoredEdge(v)), end = el.end();

        if (i != end) {

          g.m_edges.erase((*i).get_iter());

          el.erase(i);

        }

      }

    } // namespace detail

    template <class Vertex, class EdgeProperty>

    struct list_edge // short name due to VC++ truncation and linker problems

      : public boost::detail::edge_base<boost::undirected_tag, Vertex>

    {

      typedef EdgeProperty property_type;

      typedef boost::detail::edge_base<boost::undirected_tag, Vertex> Base;

      list_edge(Vertex u, Vertex v, const EdgeProperty& p = EdgeProperty())

        : Base(u, v), m_property(p) { }

      EdgeProperty& get_property() { return m_property; }

      const EdgeProperty& get_property() const { return m_property; }

      // the following methods should never be used, but are needed

      // to make SGI MIPSpro C++ happy

      list_edge() { }

      bool operator==(const list_edge&) const { return false; }

      bool operator<(const list_edge&) const { return false; }

      EdgeProperty m_property;

    };

    template <class Config>

    struct undirected_graph_helper {

      typedef undir_adj_list_traversal_tag traversal_category;

      // Placement of these overloaded remove_edge() functions

      // inside the class avoids a VC++ bug.

      // O(E/V)

      inline void

      remove_edge(typename Config::edge_descriptor e)

      {

        typedef typename Config::global_edgelist_selector EdgeListS;

        BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));

        typedef typename Config::OutEdgeList::value_type::property_type PType;

        detail::remove_undirected_edge_dispatch<PType>::apply

          (e, *this, *(PType*)e.get_property());

      }

      // O(E/V)

      inline void

      remove_edge(typename Config::out_edge_iterator iter)

      {

        this->remove_edge(*iter);

      }

    };

    // Had to make these non-members to avoid accidental instantiation

    // on SGI MIPSpro C++

    template <class C>

    inline typename C::InEdgeList& 

    in_edge_list(undirected_graph_helper<C>&, 

                 typename C::vertex_descriptor v)

    {

      typename C::stored_vertex* sv = (typename C::stored_vertex*)v;

      return sv->m_out_edges;

    }

    template <class C>

    inline const typename C::InEdgeList& 

    in_edge_list(const undirected_graph_helper<C>&,

                 typename C::vertex_descriptor v) {

      typename C::stored_vertex* sv = (typename C::stored_vertex*)v;

      return sv->m_out_edges;

    }

    // O(E/V)

    template <class EdgeOrIter, class Config>

    inline void

    remove_edge(EdgeOrIter e, undirected_graph_helper<Config>& g_)

    {

      typedef typename Config::global_edgelist_selector EdgeListS;

      BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));

      g_.remove_edge(e);

    }

    // O(E/V) or O(log(E/V))

    template <class Config>

    void

    remove_edge(typename Config::vertex_descriptor u, 

                typename Config::vertex_descriptor v, 

                undirected_graph_helper<Config>& g_)

    {

      typedef typename Config::global_edgelist_selector EdgeListS;

      BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));

      typedef typename Config::graph_type graph_type;

      graph_type& g = static_cast<graph_type&>(g_);

      typedef typename Config::edge_parallel_category Cat;

      detail::remove_edge_and_property(g, g.out_edge_list(u), v, Cat());

      detail::erase_from_incidence_list(g.out_edge_list(v), u, Cat());

    }

    template <class Config, class Predicate>

    void

    remove_out_edge_if(typename Config::vertex_descriptor u, Predicate pred,

                       undirected_graph_helper<Config>& g_)

    {

      typedef typename Config::global_edgelist_selector EdgeListS;

      BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));

      typedef typename Config::graph_type graph_type;

      typedef typename Config::OutEdgeList::value_type::property_type PropT;

      graph_type& g = static_cast<graph_type&>(g_);

      typename Config::out_edge_iterator first, last;

      tie(first, last) = out_edges(u, g);

      typedef typename Config::edge_parallel_category Cat;

      detail::undirected_remove_out_edge_if_dispatch<PropT>

        (g, first, last, g.out_edge_list(u), pred, Cat());

    }

    template <class Config, class Predicate>

    void

    remove_in_edge_if(typename Config::vertex_descriptor u, Predicate pred,

                      undirected_graph_helper<Config>& g_)

    {

      typedef typename Config::global_edgelist_selector EdgeListS;

      BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));

      remove_out_edge_if(u, pred, g_);

    }

    // O(E/V * E) or O(log(E/V) * E)

    template <class Predicate, class Config>

    void

    remove_edge_if(Predicate pred, undirected_graph_helper<Config>& g_)

    {

      typedef typename Config::global_edgelist_selector EdgeListS;

      BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));

      typedef typename Config::graph_type graph_type;

      graph_type& g = static_cast<graph_type&>(g_);

      typename Config::edge_iterator ei, ei_end, next;

      tie(ei, ei_end) = edges(g);

      for (next = ei; ei != ei_end; ei = next) {

        ++next;

        if (pred(*ei))

          remove_edge(*ei, g);

      }

    }

    // O(1)

    template <class Config>

    inline std::pair<typename Config::edge_iterator, 

                     typename Config::edge_iterator>

    edges(const undirected_graph_helper<Config>& g_)

    {

      typedef typename Config::graph_type graph_type;

      typedef typename Config::edge_iterator edge_iterator;

      const graph_type& cg = static_cast<const graph_type&>(g_);

      graph_type& g = const_cast<graph_type&>(cg);

      return std::make_pair( edge_iterator(g.m_edges.begin()),

                             edge_iterator(g.m_edges.end()) );

    }

    // O(1)

    template <class Config>

    inline typename Config::edges_size_type

    num_edges(const undirected_graph_helper<Config>& g_) 

    {

      typedef typename Config::graph_type graph_type;

      const graph_type& g = static_cast<const graph_type&>(g_);

      return g.m_edges.size();

    }

    // O(E/V * E/V)

    template <class Config>

    inline void 

    clear_vertex(typename Config::vertex_descriptor u,

                 undirected_graph_helper<Config>& g_)

    {

      typedef typename Config::global_edgelist_selector EdgeListS;

      BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));

      typedef typename Config::graph_type graph_type;

      typedef typename Config::edge_parallel_category Cat;

      graph_type& g = static_cast<graph_type&>(g_);

      typename Config::OutEdgeList& el = g.out_edge_list(u);

      typename Config::OutEdgeList::iterator 

        ei = el.begin(), ei_end = el.end();

      for (; ei != ei_end; ++ei) {

        detail::erase_from_incidence_list

          (g.out_edge_list((*ei).get_target()), u, Cat());

        g.m_edges.erase((*ei).get_iter());

      }

      g.out_edge_list(u).clear();

    }

    // O(1) for allow_parallel_edge_tag

    // O(log(E/V)) for disallow_parallel_edge_tag

    template <class Config>

    inline std::pair<typename Config::edge_descriptor, bool>

    add_edge(typename Config::vertex_descriptor u, 

             typename Config::vertex_descriptor v, 

             const typename Config::edge_property_type& p,

             undirected_graph_helper<Config>& g_)