test: epoc32/include/stdapis/boost/graph/detail/adjacency

     1 // -*- c++ -*-

     2 //=======================================================================

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

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

     5 //

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

     7 // accompanying file LICENSE_1_0.txt or copy at

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

     9 //=======================================================================

    11 #ifndef BOOST_GRAPH_DETAIL_ADJACENCY_LIST_HPP

    12 #define BOOST_GRAPH_DETAIL_ADJACENCY_LIST_HPP

    14 #include <map> // for vertex_map in copy_impl

    15 #include <boost/config.hpp>

    16 #include <boost/detail/workaround.hpp>

    17 #include <boost/operators.hpp>

    18 #include <boost/property_map.hpp>

    19 #include <boost/pending/integer_range.hpp>

    20 #include <boost/graph/graph_traits.hpp>

    21 #include <memory>

    22 #include <algorithm>

    23 #include <boost/limits.hpp>

    25 #include <boost/iterator/iterator_adaptor.hpp>

    27 #include <boost/pending/ct_if.hpp>

    28 #include <boost/graph/graph_concepts.hpp>

    29 #include <boost/pending/container_traits.hpp>

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

    31 #include <boost/graph/properties.hpp>

    32 #include <boost/pending/property.hpp>

    33 #include <boost/graph/adjacency_iterator.hpp>

    34 #include <boost/static_assert.hpp>

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

    37 #define stored_edge se_

    38 #define stored_edge_property sep_

    39 #define stored_edge_iter sei_

    41 /*

    42   Outline for this file:

    44   out_edge_iterator and in_edge_iterator implementation

    45   edge_iterator for undirected graph

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

    47   directed edges helper class

    48   directed graph helper class

    49   undirected graph helper class

    50   bidirectional graph helper class

    51   bidirectional graph helper class (without edge properties)

    52   bidirectional graph helper class (with edge properties)

    53   adjacency_list helper class

    54   adj_list_impl class

    55   vec_adj_list_impl class

    56   adj_list_gen class

    57   vertex property map

    58   edge property map

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

    62   bidirectional code... it is awful similar.

    63  */

    66 namespace boost {

    68   namespace detail {

    70     template <typename DirectedS>

    71     struct directed_category_traits {

    72       typedef directed_tag directed_category;

    73     };

    75     template <>

    76     struct directed_category_traits<directedS> {

    77       typedef directed_tag directed_category;

    78     };

    79     template <>

    80     struct directed_category_traits<undirectedS> {

    81       typedef undirected_tag directed_category;

    82     };

    83     template <>

    84     struct directed_category_traits<bidirectionalS> {

    85       typedef bidirectional_tag directed_category;

    86     };

    88     template <class Vertex>

    89     struct target_is {

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

    91       template <class StoredEdge>

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

    93         return e.get_target() == m_target;

    94       }

    95       Vertex m_target;

    96     };

    98     // O(E/V)

    99     template <class EdgeList, class vertex_descriptor>

   100     void erase_from_incidence_list(EdgeList& el, vertex_descriptor v,

   101                                    allow_parallel_edge_tag)

   102     {

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

   104     }

   105     // O(log(E/V))

   106     template <class EdgeList, class vertex_descriptor>

   107     void erase_from_incidence_list(EdgeList& el, vertex_descriptor v,

   108                                    disallow_parallel_edge_tag)

   109     {

   110       typedef typename EdgeList::value_type StoredEdge;

   111       el.erase(StoredEdge(v));

   112     }

   114     //=========================================================================

   115     // Out-Edge and In-Edge Iterator Implementation

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

   118     struct out_edge_iter

   119       : iterator_adaptor<

   120             out_edge_iter<BaseIter, VertexDescriptor, EdgeDescriptor, Difference>

   121           , BaseIter

   122           , EdgeDescriptor

   123           , use_default

   124           , EdgeDescriptor

   125           , Difference

   126         >

   127     {

   128       typedef iterator_adaptor<

   129           out_edge_iter<BaseIter, VertexDescriptor, EdgeDescriptor, Difference>

   130         , BaseIter

   131         , EdgeDescriptor

   132         , use_default

   133         , EdgeDescriptor

   134         , Difference

   135       > super_t;

   137       inline out_edge_iter() { }

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

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

   141       inline EdgeDescriptor

   142       dereference() const

   143       {

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

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

   146       }

   147       VertexDescriptor m_src;

   148     };

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

   151     struct in_edge_iter

   152       : iterator_adaptor<

   153             in_edge_iter<BaseIter, VertexDescriptor, EdgeDescriptor, Difference>

   154           , BaseIter

   155           , EdgeDescriptor

   156           , use_default

   157           , EdgeDescriptor

   158           , Difference

   159         >

   160     {

   161       typedef iterator_adaptor<

   162           in_edge_iter<BaseIter, VertexDescriptor, EdgeDescriptor, Difference>

   163         , BaseIter

   164         , EdgeDescriptor

   165         , use_default

   166         , EdgeDescriptor

   167         , Difference

   168       > super_t;

   170       inline in_edge_iter() { }

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

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

   174       inline EdgeDescriptor

   175       dereference() const

   176       {

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

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

   179       }

   180       VertexDescriptor m_src;

   181     };

   183     //=========================================================================

   184     // Undirected Edge Iterator Implementation

   186     template <class EdgeIter, class EdgeDescriptor, class Difference>

   187     struct undirected_edge_iter

   188       : iterator_adaptor<

   189             undirected_edge_iter<EdgeIter, EdgeDescriptor, Difference>

   190           , EdgeIter

   191           , EdgeDescriptor

   192           , use_default

   193           , EdgeDescriptor

   194           , Difference

   195         >

   196     {

   197       typedef iterator_adaptor<

   198           undirected_edge_iter<EdgeIter, EdgeDescriptor, Difference>

   199         , EdgeIter

   200         , EdgeDescriptor

   201         , use_default

   202         , EdgeDescriptor

   203         , Difference

   204       > super_t;

   206       undirected_edge_iter() {}

   208       explicit undirected_edge_iter(EdgeIter i)

   209           : super_t(i) {}

   211       inline EdgeDescriptor

   212       dereference() const {

   213         return EdgeDescriptor(

   214             (*this->base()).m_source

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

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

   217       }

   218     };

   220     //=========================================================================

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

   223     template <class Vertex>

   224     class stored_edge

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

   226         boost::less_than_comparable1< stored_edge<Vertex> > >

   227     {

   228     public:

   229       typedef no_property property_type;

   230       inline stored_edge() { }

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

   232         : m_target(target) { }

   233       // Need to write this explicitly so stored_edge_property can

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

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

   236         m_target = x.m_target;

   237         return *this;

   238       }

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

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

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

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

   243       inline bool operator<(const stored_edge& x) const

   244         { return m_target < x.get_target(); }

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

   246       static no_property s_prop;

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

   248       // it is ok to change the target.

   249       mutable Vertex m_target;

   250     };

   251     template <class Vertex>

   252     no_property stored_edge<Vertex>::s_prop;

   254     template <class Vertex, class Property>

   255     class stored_edge_property : public stored_edge<Vertex> {

   256       typedef stored_edge_property self;

   257       typedef stored_edge<Vertex> Base;

   258     public:

   259       typedef Property property_type;

   260       inline stored_edge_property() { }

   261       inline stored_edge_property(Vertex target,

   262                                   const Property& p = Property())

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

   264       stored_edge_property(const self& x)

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

   266       self& operator=(const self& x) {

   267         Base::operator=(x);

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

   269         return *this;

   270       }

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

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

   273     protected:

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

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

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

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

   278       std::auto_ptr<Property> m_property;

   279     };

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

   283     class stored_edge_iter

   284       : public stored_edge<Vertex>

   285     {

   286     public:

   287       typedef Property property_type;

   288       inline stored_edge_iter() { }

   289       inline stored_edge_iter(Vertex v)

   290         : stored_edge<Vertex>(v) { }

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

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

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

   294       inline const Property& get_property() const {

   295         return m_iter->get_property();

   296       }

   297       inline Iter get_iter() const { return m_iter; }

   298     protected:

   299       Iter m_iter;

   300     };

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

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

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

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

   306     class stored_ra_edge_iter

   307       : public stored_edge<Vertex>

   308     {

   309       typedef typename EdgeVec::iterator Iter;

   310     public:

   311       typedef Property property_type;

   312       inline stored_ra_edge_iter() { }

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

   314                                  EdgeVec* edge_vec = 0)

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

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

   317       inline const Property& get_property() const {

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

   319       }

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

   321     protected:

   322       std::size_t m_i;

   323       EdgeVec* m_vec;

   324     };

   326   } // namespace detail

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

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

   330   get(Tag property_tag,

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

   332   {

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

   334   }

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

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

   338   get(Tag property_tag,

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

   340   {

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

   342   }

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

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

   346   get(Tag property_tag,

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

   348   {

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

   350   }

   352     //=========================================================================

   353     // Directed Edges Helper Class

   355     namespace detail {

   357       // O(E/V)

   358       template <class edge_descriptor, class EdgeList, class StoredProperty>

   359       inline void

   360       remove_directed_edge_dispatch(edge_descriptor, EdgeList& el,

   361                                     StoredProperty& p)

   362       {

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

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

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

   366             el.erase(i);

   367             return;

   368           }

   369       }

   371       template <class incidence_iterator, class EdgeList, class Predicate>

   372       inline void

   373       remove_directed_edge_if_dispatch(incidence_iterator first,

   374                                        incidence_iterator last,

   375                                        EdgeList& el, Predicate pred,

   376                                        boost::allow_parallel_edge_tag)

   377       {

   378         // remove_if

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

   380           ++first;

   381         incidence_iterator i = first;

   382         if (first != last)

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

   384             if (!pred(*i)) {

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

   386               ++first;

   387             }

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

   389       }

   390       template <class incidence_iterator, class EdgeList, class Predicate>

   391       inline void

   392       remove_directed_edge_if_dispatch(incidence_iterator first,

   393                                        incidence_iterator last,

   394                                        EdgeList& el,

   395                                        Predicate pred,

   396                                        boost::disallow_parallel_edge_tag)

   397       {

   398         for (incidence_iterator next = first;

   399              first != last; first = next) {

   400           ++next;

   401           if (pred(*first))

   402             el.erase( first.base() );

   403         }

   404       }

   406       template <class PropT, class Graph, class incidence_iterator,

   407                 class EdgeList, class Predicate>

   408       inline void

   409       undirected_remove_out_edge_if_dispatch(Graph& g,

   410                                              incidence_iterator first,

   411                                              incidence_iterator last,

   412                                              EdgeList& el, Predicate pred,

   413                                              boost::allow_parallel_edge_tag)

   414       {

   415         typedef typename Graph::global_edgelist_selector EdgeListS;

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

   418         // remove_if

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

   420           ++first;

   421         incidence_iterator i = first;

   422         bool self_loop_removed = false;

   423         if (first != last)

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

   425             if (self_loop_removed) {

   426               /* With self loops, the descriptor will show up

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

   428                * will be skipped.

   429                */

   430               self_loop_removed = false;

   431             }

   432             else if (!pred(*i)) {

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

   434               ++first;

   435             } else {

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

   437               else {

   438                 // Remove the edge from the target

   439                 detail::remove_directed_edge_dispatch

   440                   (*i,

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

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

   443               }

   445               // Erase the edge property

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

   447             }

   448           }

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

   450       }

   451       template <class PropT, class Graph, class incidence_iterator,

   452                 class EdgeList, class Predicate>

   453       inline void

   454       undirected_remove_out_edge_if_dispatch(Graph& g,

   455                                              incidence_iterator first,

   456                                              incidence_iterator last,

   457                                              EdgeList& el,

   458                                              Predicate pred,

   459                                              boost::disallow_parallel_edge_tag)

   460       {

   461         typedef typename Graph::global_edgelist_selector EdgeListS;

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

   464         for (incidence_iterator next = first;

   465              first != last; first = next) {

   466           ++next;

   467           if (pred(*first)) {

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

   469               // Remove the edge from the target

   470               detail::remove_directed_edge_dispatch

   471                 (*first,

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

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

   474             }

   476             // Erase the edge property

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

   479             // Erase the edge in the source

   480             el.erase( first.base() );

   481           }

   482         }

   483       }

   485       // O(E/V)

   486       template <class edge_descriptor, class EdgeList, class StoredProperty>

   487       inline void

   488       remove_directed_edge_dispatch(edge_descriptor e, EdgeList& el,

   489                                     no_property&)

   490       {

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

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

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

   494             el.erase(i);

   495             return;

   496           }

   497       }

   499     } // namespace detail

   501     template <class Config>

   502     struct directed_edges_helper {

   504       // Placement of these overloaded remove_edge() functions

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

   507       // O(E/V)

   508       inline void

   509       remove_edge(typename Config::edge_descriptor e)

   510       {

   511         typedef typename Config::graph_type graph_type;

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

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

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

   515         detail::remove_directed_edge_dispatch(e, el,

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

   517       }

   519       // O(1)

   520       inline void

   521       remove_edge(typename Config::out_edge_iterator iter)

   522       {

   523         typedef typename Config::graph_type graph_type;

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

   525         typename Config::edge_descriptor e = *iter;

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

   527         el.erase(iter.base());

   528       }

   530     };

   532     // O(1)

   533     template <class Config>

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

   535                      typename Config::edge_iterator>

   536     edges(const directed_edges_helper<Config>& g_)

   537     {

   538       typedef typename Config::graph_type graph_type;

   539       typedef typename Config::edge_iterator edge_iterator;

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

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

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

   543                                            g.vertex_set().begin(),

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

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

   546                                            g.vertex_set().end(),

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

   548     }

   550     //=========================================================================

   551     // Directed Graph Helper Class

   553     struct adj_list_dir_traversal_tag :

   554       public virtual vertex_list_graph_tag,

   555       public virtual incidence_graph_tag,

   556       public virtual adjacency_graph_tag,

   557       public virtual edge_list_graph_tag { };

   559     template <class Config>

   560     struct directed_graph_helper

   561       : public directed_edges_helper<Config> {

   562       typedef typename Config::edge_descriptor edge_descriptor;

   563       typedef adj_list_dir_traversal_tag traversal_category;

   564     };

   566     // O(E/V)

   567     template <class Config>

   568     inline void

   569     remove_edge(typename Config::vertex_descriptor u,

   570                 typename Config::vertex_descriptor v,

   571                 directed_graph_helper<Config>& g_)

   572     {

   573       typedef typename Config::graph_type graph_type;

   574       typedef typename Config::edge_parallel_category Cat;

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

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

   577     }

   579     template <class Config, class Predicate>

   580     inline void

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

   582                        directed_graph_helper<Config>& g_)

   583     {

   584       typedef typename Config::graph_type graph_type;

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

   586       typename Config::out_edge_iterator first, last;

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

   588       typedef typename Config::edge_parallel_category edge_parallel_category;

   589       detail::remove_directed_edge_if_dispatch

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

   591     }

   593     template <class Config, class Predicate>

   594     inline void

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

   596     {

   597       typedef typename Config::graph_type graph_type;

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

   600       typename Config::vertex_iterator vi, vi_end;

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

   602         remove_out_edge_if(*vi, pred, g);

   603     }

   605     template <class EdgeOrIter, class Config>

   606     inline void

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

   608     {

   609       g_.remove_edge(e_or_iter);

   610     }

   612     // O(V + E) for allow_parallel_edges

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

   614     template <class Config>

   615     inline void

   616     clear_vertex(typename Config::vertex_descriptor u,

   617                  directed_graph_helper<Config>& g_)

   618     {

   619       typedef typename Config::graph_type graph_type;

   620       typedef typename Config::edge_parallel_category Cat;

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

   622       typename Config::vertex_iterator vi, viend;

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

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

   625       g.out_edge_list(u).clear();

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

   627       // or maybe just Container

   628     }

   630     template <class Config>

   631     inline void

   632     clear_out_edges(typename Config::vertex_descriptor u,

   633                     directed_graph_helper<Config>& g_)

   634     {

   635       typedef typename Config::graph_type graph_type;

   636       typedef typename Config::edge_parallel_category Cat;

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

   638       g.out_edge_list(u).clear();

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

   640       // or maybe just Container

   641     }

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

   644     template <class Config>

   645     inline typename Config::edges_size_type

   646     num_edges(const directed_graph_helper<Config>& g_)

   647     {

   648       typedef typename Config::graph_type graph_type;

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

   650       typename Config::edges_size_type num_e = 0;

   651       typename Config::vertex_iterator vi, vi_end;

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

   653         num_e += out_degree(*vi, g);

   654       return num_e;

   655     }

   656     // O(1) for allow_parallel_edge_tag

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

   658     template <class Config>

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

   660     add_edge(typename Config::vertex_descriptor u,

   661              typename Config::vertex_descriptor v,

   662              const typename Config::edge_property_type& p,

   663              directed_graph_helper<Config>& g_)

   664     {

   665       typedef typename Config::edge_descriptor edge_descriptor;

   666       typedef typename Config::graph_type graph_type;

   667       typedef typename Config::StoredEdge StoredEdge;

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

   669       typename Config::OutEdgeList::iterator i;

   670       bool inserted;

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

   672                                             StoredEdge(v, p));

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

   674                             inserted);

   675     }

   676     // Did not use default argument here because that

   677     // causes Visual C++ to get confused.

   678     template <class Config>

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

   680     add_edge(typename Config::vertex_descriptor u,

   681              typename Config::vertex_descriptor v,

   682              directed_graph_helper<Config>& g_)

   683     {

   684       typename Config::edge_property_type p;

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

   686     }

   687     //=========================================================================

   688     // Undirected Graph Helper Class

   690     template <class Config>

   691     struct undirected_graph_helper;

   693     struct undir_adj_list_traversal_tag :

   694       public virtual vertex_list_graph_tag,

   695       public virtual incidence_graph_tag,

   696       public virtual adjacency_graph_tag,

   697       public virtual edge_list_graph_tag,

   698       public virtual bidirectional_graph_tag { };

   700     namespace detail {

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

   703       template <class StoredProperty>

   704       struct remove_undirected_edge_dispatch {

   706         // O(E/V)

   707         template <class edge_descriptor, class Config>

   708         static void

   709         apply(edge_descriptor e,

   710               undirected_graph_helper<Config>& g_,

   711               StoredProperty& p)

   712         {

   713           typedef typename Config::global_edgelist_selector EdgeListS;

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

   716           typedef typename Config::graph_type graph_type;

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

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

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

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

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

   723               out_el.erase(out_i);

   724               break;

   725             }

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

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

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

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

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

   731               in_el.erase(in_i);

   732               return;

   733             }

   734         }

   735       };

   737       template <>

   738       struct remove_undirected_edge_dispatch<no_property> {

   739         // O(E/V)

   740         template <class edge_descriptor, class Config>

   741         static void

   742         apply(edge_descriptor e,

   743               undirected_graph_helper<Config>& g_,

   744               no_property&)

   745         {

   746           typedef typename Config::global_edgelist_selector EdgeListS;

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

   749           typedef typename Config::graph_type graph_type;

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

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

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

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

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

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

   756               out_el.erase(out_i);

   757               break;

   758             }

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

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

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

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

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

   764               in_el.erase(in_i);

   765               return;

   766             }

   767         }

   768       };

   770       // O(E/V)

   771       template <class Graph, class EdgeList, class Vertex>

   772       inline void

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

   774                                boost::allow_parallel_edge_tag cat)

   775       {

   776         typedef typename Graph::global_edgelist_selector EdgeListS;

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

   779         typedef typename EdgeList::value_type StoredEdge;

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

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

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

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

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

   785       }

   786       // O(log(E/V))

   787       template <class Graph, class EdgeList, class Vertex>

   788       inline void

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

   790                                boost::disallow_parallel_edge_tag)

   791       {

   792         typedef typename Graph::global_edgelist_selector EdgeListS;

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

   795         typedef typename EdgeList::value_type StoredEdge;

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

   797         if (i != end) {

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

   799           el.erase(i);

   800         }

   801       }

   803     } // namespace detail

   805     template <class Vertex, class EdgeProperty>

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

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

   808     {

   809       typedef EdgeProperty property_type;

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

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

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

   813       EdgeProperty& get_property() { return m_property; }

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

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

   816       // to make SGI MIPSpro C++ happy

   817       list_edge() { }

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

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

   820       EdgeProperty m_property;

   821     };

   823     template <class Config>

   824     struct undirected_graph_helper {

   826       typedef undir_adj_list_traversal_tag traversal_category;

   828       // Placement of these overloaded remove_edge() functions

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

   831       // O(E/V)

   832       inline void

   833       remove_edge(typename Config::edge_descriptor e)

   834       {

   835         typedef typename Config::global_edgelist_selector EdgeListS;

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

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

   839         detail::remove_undirected_edge_dispatch<PType>::apply

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

   841       }

   842       // O(E/V)

   843       inline void

   844       remove_edge(typename Config::out_edge_iterator iter)

   845       {

   846         this->remove_edge(*iter);

   847       }

   848     };

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

   851     // on SGI MIPSpro C++

   852     template <class C>

   853     inline typename C::InEdgeList&

   854     in_edge_list(undirected_graph_helper<C>&,

   855                  typename C::vertex_descriptor v)

   856     {

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

   858       return sv->m_out_edges;

   859     }

   860     template <class C>

   861     inline const typename C::InEdgeList&

   862     in_edge_list(const undirected_graph_helper<C>&,

   863                  typename C::vertex_descriptor v) {

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

   865       return sv->m_out_edges;

   866     }

   868     // O(E/V)

   869     template <class EdgeOrIter, class Config>

   870     inline void

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

   872     {

   873       typedef typename Config::global_edgelist_selector EdgeListS;

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

   876       g_.remove_edge(e);

   877     }

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

   880     template <class Config>

   881     void

   882     remove_edge(typename Config::vertex_descriptor u,

   883                 typename Config::vertex_descriptor v,

   884                 undirected_graph_helper<Config>& g_)

   885     {

   886       typedef typename Config::global_edgelist_selector EdgeListS;

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

   889       typedef typename Config::graph_type graph_type;

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

   891       typedef typename Config::edge_parallel_category Cat;

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

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

   894     }

   896     template <class Config, class Predicate>

   897     void

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

   899                        undirected_graph_helper<Config>& g_)

   900     {

   901       typedef typename Config::global_edgelist_selector EdgeListS;

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

   904       typedef typename Config::graph_type graph_type;

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

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

   907       typename Config::out_edge_iterator first, last;

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

   909       typedef typename Config::edge_parallel_category Cat;

   910       detail::undirected_remove_out_edge_if_dispatch<PropT>

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

   912     }

   913     template <class Config, class Predicate>

   914     void

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

   916                       undirected_graph_helper<Config>& g_)

   917     {

   918       typedef typename Config::global_edgelist_selector EdgeListS;

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

   921       remove_out_edge_if(u, pred, g_);

   922     }

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

   925     template <class Predicate, class Config>

   926     void

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

   928     {

   929       typedef typename Config::global_edgelist_selector EdgeListS;

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

   932       typedef typename Config::graph_type graph_type;

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

   934       typename Config::edge_iterator ei, ei_end, next;

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

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

   937         ++next;

   938         if (pred(*ei))

   939           remove_edge(*ei, g);

   940       }

   941     }

   943     // O(1)

   944     template <class Config>

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

   946                      typename Config::edge_iterator>

   947     edges(const undirected_graph_helper<Config>& g_)

   948     {

   949       typedef typename Config::graph_type graph_type;

   950       typedef typename Config::edge_iterator edge_iterator;

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

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

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

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

   955     }

   956     // O(1)

   957     template <class Config>

   958     inline typename Config::edges_size_type

   959     num_edges(const undirected_graph_helper<Config>& g_)

   960     {

   961       typedef typename Config::graph_type graph_type;

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

   963       return g.m_edges.size();

   964     }

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

   966     template <class Config>

   967     inline void

   968     clear_vertex(typename Config::vertex_descriptor u,

   969                  undirected_graph_helper<Config>& g_)

   970     {

   971       typedef typename Config::global_edgelist_selector EdgeListS;

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

   974       typedef typename Config::graph_type graph_type;

   975       typedef typename Config::edge_parallel_category Cat;

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

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

   978       typename Config::OutEdgeList::iterator

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

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

   981         detail::erase_from_incidence_list

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

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

   984       }

   985       g.out_edge_list(u).clear();

   986     }

   987     // O(1) for allow_parallel_edge_tag

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

   989     template <class Config>

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

   991     add_edge(typename Config::vertex_descriptor u,

   992              typename Config::vertex_descriptor v,

   993              const typename Config::edge_property_type& p,

   994              undirected_graph_helper<Config>& g_)

   995     {

   996       typedef typename Config::StoredEdge StoredEdge;

   997       typedef typename Config::edge_descriptor edge_descriptor;

   998       typedef typename Config::graph_type graph_type;

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

  1001       bool inserted;

  1002       typename Config::EdgeContainer::value_type e(u, v, p);

  1003       typename Config::EdgeContainer::iterator p_iter

  1004         = graph_detail::push(g.m_edges, e).first;

  1006       typename Config::OutEdgeList::iterator i;

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

  1008                                     StoredEdge(v, p_iter, &g.m_edges));

  1009       if (inserted) {

  1010         boost::graph_detail::push(g.out_edge_list(v), StoredEdge(u, p_iter, &g.m_edges));

  1011         return std::make_pair(edge_descriptor(u, v, &p_iter->get_property()),

  1012                               true);

  1013       } else {

  1014         g.m_edges.erase(p_iter);

  1015         return std::make_pair

  1016           (edge_descriptor(u, v, &i->get_iter()->get_property()), false);

  1017       }

  1018     }

  1019     template <class Config>

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

  1021     add_edge(typename Config::vertex_descriptor u,

  1022              typename Config::vertex_descriptor v,

  1023              undirected_graph_helper<Config>& g_)

  1024     {

  1025       typename Config::edge_property_type p;

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

  1027     }

  1029     // O(1)

  1030     template <class Config>

  1031     inline typename Config::degree_size_type

  1032     degree(typename Config::vertex_descriptor u,

  1033            const undirected_graph_helper<Config>& g_)

  1034     {

  1035       typedef typename Config::graph_type Graph;

  1036       const Graph& g = static_cast<const Graph&>(g_);

  1037       return out_degree(u, g);

  1038     }

  1040     template <class Config>

  1041     inline std::pair<typename Config::in_edge_iterator,

  1042                      typename Config::in_edge_iterator>

  1043     in_edges(typename Config::vertex_descriptor u,

  1044              const undirected_graph_helper<Config>& g_)

  1045     {

  1046       typedef typename Config::graph_type Graph;

  1047       const Graph& cg = static_cast<const Graph&>(g_);

  1048       Graph& g = const_cast<Graph&>(cg);

  1049       typedef typename Config::in_edge_iterator in_edge_iterator;

  1050       return

  1051         std::make_pair(in_edge_iterator(g.out_edge_list(u).begin(), u),

  1052                        in_edge_iterator(g.out_edge_list(u).end(), u));

  1053     }

  1055     template <class Config>

  1056     inline typename Config::degree_size_type

  1057     in_degree(typename Config::vertex_descriptor u,

  1058               const undirected_graph_helper<Config>& g_)

  1059     { return degree(u, g_); }

  1061     //=========================================================================

  1062     // Bidirectional Graph Helper Class

  1064     struct bidir_adj_list_traversal_tag :

  1065       public virtual vertex_list_graph_tag,

  1066       public virtual incidence_graph_tag,

  1067       public virtual adjacency_graph_tag,

  1068       public virtual edge_list_graph_tag,

  1069       public virtual bidirectional_graph_tag { };

  1071     template <class Config>

  1072     struct bidirectional_graph_helper

  1073       : public directed_edges_helper<Config> {

  1074       typedef bidir_adj_list_traversal_tag traversal_category;

  1075     };

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

  1078     // on SGI MIPSpro C++

  1079     template <class C>

  1080     inline typename C::InEdgeList&

  1081     in_edge_list(bidirectional_graph_helper<C>&,

  1082                  typename C::vertex_descriptor v)

  1083     {

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

  1085       return sv->m_in_edges;

  1086     }

  1087     template <class C>

  1088     inline const typename C::InEdgeList&

  1089     in_edge_list(const bidirectional_graph_helper<C>&,

  1090                  typename C::vertex_descriptor v) {

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

  1092       return sv->m_in_edges;

  1093     }

  1095     template <class Predicate, class Config>

  1096     inline void

  1097     remove_edge_if(Predicate pred, bidirectional_graph_helper<Config>& g_)

  1098     {

  1099       typedef typename Config::global_edgelist_selector EdgeListS;

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

  1102       typedef typename Config::graph_type graph_type;

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

  1104       typename Config::edge_iterator ei, ei_end, next;

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

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

  1107         ++next;

  1108         if (pred(*ei))

  1109           remove_edge(*ei, g);

  1110       }

  1111     }

  1113     template <class Config>

  1114     inline std::pair<typename Config::in_edge_iterator,

  1115                      typename Config::in_edge_iterator>

  1116     in_edges(typename Config::vertex_descriptor u,

  1117              const bidirectional_graph_helper<Config>& g_)

  1118     {

  1119       typedef typename Config::graph_type graph_type;

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

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

  1122       typedef typename Config::in_edge_iterator in_edge_iterator;

  1123       return

  1124         std::make_pair(in_edge_iterator(in_edge_list(g, u).begin(), u),

  1125                        in_edge_iterator(in_edge_list(g, u).end(), u));

  1126     }

  1128     // O(1)

  1129     template <class Config>

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

  1131                      typename Config::edge_iterator>

  1132     edges(const bidirectional_graph_helper<Config>& g_)

  1133     {

  1134       typedef typename Config::graph_type graph_type;

  1135       typedef typename Config::edge_iterator edge_iterator;

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

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

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

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

  1140     }

  1142     //=========================================================================

  1143     // Bidirectional Graph Helper Class (with edge properties)

  1146     template <class Config>

  1147     struct bidirectional_graph_helper_with_property

  1148       : public bidirectional_graph_helper<Config>

  1149     {

  1150       typedef typename Config::graph_type graph_type;

  1151       typedef typename Config::out_edge_iterator out_edge_iterator;

  1153       std::pair<out_edge_iterator, out_edge_iterator>

  1154       get_parallel_edge_sublist(typename Config::edge_descriptor e,

  1155                                 const graph_type& g,

  1156                                 void*)

  1157       { return out_edges(source(e, g), g); }

  1159       std::pair<out_edge_iterator, out_edge_iterator>

  1160       get_parallel_edge_sublist(typename Config::edge_descriptor e,

  1161                                 const graph_type& g,

  1162                                 setS*)

  1163       { return edge_range(source(e, g), target(e, g), g); }

  1165       std::pair<out_edge_iterator, out_edge_iterator>

  1166       get_parallel_edge_sublist(typename Config::edge_descriptor e,

  1167                                 const graph_type& g,

  1168                                 multisetS*)

  1169       { return edge_range(source(e, g), target(e, g), g); }

  1171 #if !defined BOOST_NO_HASH

  1172       std::pair<out_edge_iterator, out_edge_iterator>

  1173       get_parallel_edge_sublist(typename Config::edge_descriptor e,

  1174                                 const graph_type& g,

  1175                                 hash_setS*)

  1176       { return edge_range(source(e, g), target(e, g), g); }

  1177 #endif

  1179       // Placement of these overloaded remove_edge() functions

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

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

  1183       void

  1184       remove_edge(typename Config::edge_descriptor e)

  1185       {

  1186         typedef typename Config::global_edgelist_selector EdgeListS;

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

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

  1191         typedef typename Config::edgelist_selector OutEdgeListS;

  1193         std::pair<out_edge_iterator, out_edge_iterator> rng =

  1194           get_parallel_edge_sublist(e, g, (OutEdgeListS*)(0));

  1195         rng.first = std::find(rng.first, rng.second, e);

  1196         assert(rng.first != rng.second);

  1197         remove_edge(rng.first);

  1198       }

  1200       inline void

  1201       remove_edge(typename Config::out_edge_iterator iter)

  1202       {

  1203         typedef typename Config::global_edgelist_selector EdgeListS;

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

  1206         typedef typename Config::graph_type graph_type;

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

  1208         typename Config::edge_descriptor e = *iter;

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

  1210         typename Config::InEdgeList& iel = in_edge_list(g, target(e, g));

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

  1212         PType& p = *(PType*)e.get_property();

  1213         detail::remove_directed_edge_dispatch(*iter, iel, p);

  1214         g.m_edges.erase(iter.base()->get_iter());

  1215         oel.erase(iter.base());

  1216       }

  1217     };

  1219     // O(E/V) for allow_parallel_edge_tag

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

  1221     template <class Config>

  1222     inline void

  1223     remove_edge(typename Config::vertex_descriptor u,

  1224                 typename Config::vertex_descriptor v,

  1225                 bidirectional_graph_helper_with_property<Config>& g_)

  1226     {

  1227       typedef typename Config::global_edgelist_selector EdgeListS;

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

  1230       typedef typename Config::graph_type graph_type;

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

  1232       typedef typename Config::edge_parallel_category Cat;

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

  1234       detail::erase_from_incidence_list(in_edge_list(g, v), u, Cat());

  1235     }

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

  1238     template <class EdgeOrIter, class Config>

  1239     inline void

  1240     remove_edge(EdgeOrIter e,

  1241                 bidirectional_graph_helper_with_property<Config>& g_)

  1242     {

  1243       typedef typename Config::global_edgelist_selector EdgeListS;

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

  1246       g_.remove_edge(e);

  1247     }

  1249     template <class Config, class Predicate>

  1250     inline void

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

  1252                        bidirectional_graph_helper_with_property<Config>& g_)

  1253     {

  1254       typedef typename Config::global_edgelist_selector EdgeListS;

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

  1257       typedef typename Config::graph_type graph_type;

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

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

  1261       typedef typename Config::EdgeIter EdgeIter;

  1262       typedef std::vector<EdgeIter> Garbage;

  1263       Garbage garbage;

  1265       // First remove the edges from the targets' in-edge lists and

  1266       // from the graph's edge set list.

  1267       typename Config::out_edge_iterator out_i, out_end;

  1268       for (tie(out_i, out_end) = out_edges(u, g); out_i != out_end; ++out_i)

  1269         if (pred(*out_i)) {

  1270           detail::remove_directed_edge_dispatch

  1271             (*out_i, in_edge_list(g, target(*out_i, g)),

  1272              *(PropT*)(*out_i).get_property());

  1273           // Put in garbage to delete later. Will need the properties

  1274           // for the remove_if of the out-edges.

  1275           garbage.push_back((*out_i.base()).get_iter());

  1276         }

  1278       // Now remove the edges from this out-edge list.

  1279       typename Config::out_edge_iterator first, last;

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

  1281       typedef typename Config::edge_parallel_category Cat;

  1282       detail::remove_directed_edge_if_dispatch

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

  1285       // Now delete the edge properties from the g.m_edges list

  1286       for (typename Garbage::iterator i = garbage.begin();

  1287            i != garbage.end(); ++i)

  1288         g.m_edges.erase(*i);

  1289     }

  1290     template <class Config, class Predicate>

  1291     inline void

  1292     remove_in_edge_if(typename Config::vertex_descriptor v, Predicate pred,

  1293                       bidirectional_graph_helper_with_property<Config>& g_)

  1294     {

  1295       typedef typename Config::global_edgelist_selector EdgeListS;

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

  1298       typedef typename Config::graph_type graph_type;

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

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

  1302       typedef typename Config::EdgeIter EdgeIter;

  1303       typedef std::vector<EdgeIter> Garbage;

  1304       Garbage garbage;

  1306       // First remove the edges from the sources' out-edge lists and

  1307       // from the graph's edge set list.

  1308       typename Config::in_edge_iterator in_i, in_end;

  1309       for (tie(in_i, in_end) = in_edges(v, g); in_i != in_end; ++in_i)

  1310         if (pred(*in_i)) {

  1311           typename Config::vertex_descriptor u = source(*in_i, g);

  1312           detail::remove_directed_edge_dispatch

  1313             (*in_i, g.out_edge_list(u), *(PropT*)(*in_i).get_property());

  1314           // Put in garbage to delete later. Will need the properties

  1315           // for the remove_if of the out-edges.

  1316           garbage.push_back((*in_i.base()).get_iter());

  1317         }

  1318       // Now remove the edges from this in-edge list.

  1319       typename Config::in_edge_iterator first, last;

  1320       tie(first, last) = in_edges(v, g);

  1321       typedef typename Config::edge_parallel_category Cat;

  1322       detail::remove_directed_edge_if_dispatch

  1323         (first, last, in_edge_list(g, v), pred, Cat());

  1325       // Now delete the edge properties from the g.m_edges list

  1326       for (typename Garbage::iterator i = garbage.begin();

  1327            i != garbage.end(); ++i)

  1328         g.m_edges.erase(*i);

  1329     }

  1331     // O(1)

  1332     template <class Config>

  1333     inline typename Config::edges_size_type

  1334     num_edges(const bidirectional_graph_helper_with_property<Config>& g_)

  1335     {

  1336       typedef typename Config::graph_type graph_type;

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

  1338       return g.m_edges.size();

  1339     }

  1340     // O(E/V * E/V) for allow_parallel_edge_tag

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

  1342     template <class Config>

  1343     inline void

  1344     clear_vertex(typename Config::vertex_descriptor u,

  1345                  bidirectional_graph_helper_with_property<Config>& g_)

  1346     {

  1347       typedef typename Config::global_edgelist_selector EdgeListS;

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

  1350       typedef typename Config::graph_type graph_type;

  1351       typedef typename Config::edge_parallel_category Cat;

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

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

  1354       typename Config::OutEdgeList::iterator

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

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

  1357         detail::erase_from_incidence_list

  1358           (in_edge_list(g, (*ei).get_target()), u, Cat());

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

  1360       }

  1361       typename Config::InEdgeList& in_el = in_edge_list(g, u);

  1362       typename Config::InEdgeList::iterator

  1363         in_ei = in_el.begin(), in_ei_end = in_el.end();

  1364       for (; in_ei != in_ei_end; ++in_ei) {

  1365         detail::erase_from_incidence_list

  1366           (g.out_edge_list((*in_ei).get_target()), u, Cat());

  1367         g.m_edges.erase((*in_ei).get_iter());

  1368       }

  1369       g.out_edge_list(u).clear();

  1370       in_edge_list(g, u).clear();

  1371     }

  1373     template <class Config>

  1374     inline void

  1375     clear_out_edges(typename Config::vertex_descriptor u,

  1376                     bidirectional_graph_helper_with_property<Config>& g_)

  1377     {

  1378       typedef typename Config::global_edgelist_selector EdgeListS;

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

  1381       typedef typename Config::graph_type graph_type;

  1382       typedef typename Config::edge_parallel_category Cat;

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

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

  1385       typename Config::OutEdgeList::iterator

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

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

  1388         detail::erase_from_incidence_list

  1389           (in_edge_list(g, (*ei).get_target()), u, Cat());

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

  1391       }

  1392       g.out_edge_list(u).clear();

  1393     }

  1395     template <class Config>

  1396     inline void

  1397     clear_in_edges(typename Config::vertex_descriptor u,

  1398                    bidirectional_graph_helper_with_property<Config>& g_)

  1399     {

  1400       typedef typename Config::global_edgelist_selector EdgeListS;

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

  1403       typedef typename Config::graph_type graph_type;

  1404       typedef typename Config::edge_parallel_category Cat;

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

  1406       typename Config::InEdgeList& in_el = in_edge_list(g, u);

  1407       typename Config::InEdgeList::iterator

  1408         in_ei = in_el.begin(), in_ei_end = in_el.end();

  1409       for (; in_ei != in_ei_end; ++in_ei) {

  1410         detail::erase_from_incidence_list

  1411           (g.out_edge_list((*in_ei).get_target()), u, Cat());

  1412         g.m_edges.erase((*in_ei).get_iter());

  1413       }

  1414       in_edge_list(g, u).clear();

  1415     }

  1417     // O(1) for allow_parallel_edge_tag

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

  1419     template <class Config>

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

  1421     add_edge(typename Config::vertex_descriptor u,

  1422              typename Config::vertex_descriptor v,

  1423              const typename Config::edge_property_type& p,

  1424              bidirectional_graph_helper_with_property<Config>& g_)

  1425     {

  1426       typedef typename Config::graph_type graph_type;

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

  1428       typedef typename Config::edge_descriptor edge_descriptor;

  1429       typedef typename Config::StoredEdge StoredEdge;

  1430       bool inserted;

  1431       typename Config::EdgeContainer::value_type e(u, v, p);

  1432       typename Config::EdgeContainer::iterator p_iter

  1433         = graph_detail::push(g.m_edges, e).first;

  1434       typename Config::OutEdgeList::iterator i;

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

  1436                                         StoredEdge(v, p_iter, &g.m_edges));

  1437       if (inserted) {

  1438         boost::graph_detail::push(in_edge_list(g, v), StoredEdge(u, p_iter, &g.m_edges));

  1439         return std::make_pair(edge_descriptor(u, v, &p_iter->m_property),

  1440                               true);

  1441       } else {

  1442         g.m_edges.erase(p_iter);

  1443         return std::make_pair(edge_descriptor(u, v,

  1444                                      &i->get_iter()->get_property()),

  1445                               false);

  1446       }

  1447     }

  1449     template <class Config>

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

  1451     add_edge(typename Config::vertex_descriptor u,

  1452              typename Config::vertex_descriptor v,

  1453              bidirectional_graph_helper_with_property<Config>& g_)

  1454     {

  1455       typename Config::edge_property_type p;

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

  1457     }

  1458     // O(1)

  1459     template <class Config>

  1460     inline typename Config::degree_size_type

  1461     degree(typename Config::vertex_descriptor u,

  1462            const bidirectional_graph_helper_with_property<Config>& g_)

  1463     {

  1464       typedef typename Config::graph_type graph_type;

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

  1466       return in_degree(u, g) + out_degree(u, g);

  1467     }

  1469     //=========================================================================

  1470     // Adjacency List Helper Class

  1472     template <class Config, class Base>

  1473     struct adj_list_helper : public Base

  1474     {

  1475       typedef typename Config::graph_type AdjList;

  1476       typedef typename Config::vertex_descriptor vertex_descriptor;

  1477       typedef typename Config::edge_descriptor edge_descriptor;

  1478       typedef typename Config::out_edge_iterator out_edge_iterator;

  1479       typedef typename Config::in_edge_iterator in_edge_iterator;

  1480       typedef typename Config::adjacency_iterator adjacency_iterator;

  1481       typedef typename Config::inv_adjacency_iterator inv_adjacency_iterator;

  1482       typedef typename Config::vertex_iterator vertex_iterator;

  1483       typedef typename Config::edge_iterator edge_iterator;

  1484       typedef typename Config::directed_category directed_category;

  1485       typedef typename Config::edge_parallel_category edge_parallel_category;

  1486       typedef typename Config::vertices_size_type vertices_size_type;

  1487       typedef typename Config::edges_size_type edges_size_type;

  1488       typedef typename Config::degree_size_type degree_size_type;

  1489       typedef typename Config::StoredEdge StoredEdge;

  1490       typedef typename Config::edge_property_type edge_property_type;

  1492       typedef typename Config::global_edgelist_selector

  1493         global_edgelist_selector;

  1495       //    protected:

  1497       // The edge_dispatch() functions should be static, but

  1498       // Borland gets confused about constness.

  1500       // O(E/V)

  1501       inline std::pair<edge_descriptor,bool>

  1502       edge_dispatch(const AdjList& g,

  1503                     vertex_descriptor u, vertex_descriptor v,

  1504                     boost::allow_parallel_edge_tag) const

  1505       {

  1506         bool found;

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

  1508         typename Config::OutEdgeList::const_iterator

  1509           i = std::find_if(el.begin(), el.end(),

  1510                            detail::target_is<vertex_descriptor>(v));

  1511         found = (i != g.out_edge_list(u).end());

  1512         if (found)

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

  1514                                 true);

  1515         else

  1516           return std::make_pair(edge_descriptor(u, v, 0), false);

  1517       }

  1518       // O(log(E/V))

  1519       inline std::pair<edge_descriptor,bool>

  1520       edge_dispatch(const AdjList& g,

  1521                     vertex_descriptor u, vertex_descriptor v,

  1522                     boost::disallow_parallel_edge_tag) const

  1523       {

  1524         bool found;

  1525         /* According to the standard, this should be iterator, not const_iterator,

  1526            but the VC++ std::set::find() const returns const_iterator.

  1527            And since iterator should be convertible to const_iterator, the

  1528            following should work everywhere. -Jeremy */

  1529         typename Config::OutEdgeList::const_iterator

  1530           i = g.out_edge_list(u).find(StoredEdge(v)),

  1531           end = g.out_edge_list(u).end();

  1532         found = (i != end);

  1533         if (found)

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

  1535                                 true);

  1536         else

  1537           return std::make_pair(edge_descriptor(u, v, 0), false);

  1538       }

  1539     };

  1541     template <class Config, class Base>

  1542     inline std::pair<typename Config::adjacency_iterator,

  1543                      typename Config::adjacency_iterator>

  1544     adjacent_vertices(typename Config::vertex_descriptor u,

  1545                       const adj_list_helper<Config, Base>& g_)

  1546     {

  1547       typedef typename Config::graph_type AdjList;

  1548       const AdjList& cg = static_cast<const AdjList&>(g_);

  1549       AdjList& g = const_cast<AdjList&>(cg);

  1550       typedef typename Config::adjacency_iterator adjacency_iterator;

  1551       typename Config::out_edge_iterator first, last;

  1552       boost::tie(first, last) = out_edges(u, g);

  1553       return std::make_pair(adjacency_iterator(first, &g),

  1554                             adjacency_iterator(last, &g));

  1555     }

  1556     template <class Config, class Base>

  1557     inline std::pair<typename Config::inv_adjacency_iterator,

  1558                      typename Config::inv_adjacency_iterator>

  1559     inv_adjacent_vertices(typename Config::vertex_descriptor u,

  1560                           const adj_list_helper<Config, Base>& g_)

  1561     {

  1562       typedef typename Config::graph_type AdjList;

  1563       const AdjList& cg = static_cast<const AdjList&>(g_);

  1564       AdjList& g = const_cast<AdjList&>(cg);

  1565       typedef typename Config::inv_adjacency_iterator inv_adjacency_iterator;

  1566       typename Config::in_edge_iterator first, last;

  1567       boost::tie(first, last) = in_edges(u, g);

  1568       return std::make_pair(inv_adjacency_iterator(first, &g),

  1569                             inv_adjacency_iterator(last, &g));

  1570     }

  1571     template <class Config, class Base>

  1572     inline std::pair<typename Config::out_edge_iterator,

  1573                      typename Config::out_edge_iterator>

  1574     out_edges(typename Config::vertex_descriptor u,

  1575               const adj_list_helper<Config, Base>& g_)

  1576     {

  1577       typedef typename Config::graph_type AdjList;

  1578       typedef typename Config::out_edge_iterator out_edge_iterator;

  1579       const AdjList& cg = static_cast<const AdjList&>(g_);

  1580       AdjList& g = const_cast<AdjList&>(cg);

  1581       return

  1582         std::make_pair(out_edge_iterator(g.out_edge_list(u).begin(), u),

  1583                        out_edge_iterator(g.out_edge_list(u).end(), u));

  1584     }

  1585     template <class Config, class Base>

  1586     inline std::pair<typename Config::vertex_iterator,

  1587                      typename Config::vertex_iterator>

  1588     vertices(const adj_list_helper<Config, Base>& g_)

  1589     {

  1590       typedef typename Config::graph_type AdjList;

  1591       const AdjList& cg = static_cast<const AdjList&>(g_);

  1592       AdjList& g = const_cast<AdjList&>(cg);

  1593       return std::make_pair( g.vertex_set().begin(), g.vertex_set().end() );

  1594     }

  1595     template <class Config, class Base>

  1596     inline typename Config::vertices_size_type

  1597     num_vertices(const adj_list_helper<Config, Base>& g_)

  1598     {

  1599       typedef typename Config::graph_type AdjList;

  1600       const AdjList& g = static_cast<const AdjList&>(g_);

  1601       return g.vertex_set().size();

  1602     }

  1603     template <class Config, class Base>

  1604     inline typename Config::degree_size_type

  1605     out_degree(typename Config::vertex_descriptor u,

  1606                const adj_list_helper<Config, Base>& g_)

  1607     {

  1608       typedef typename Config::graph_type AdjList;

  1609       const AdjList& g = static_cast<const AdjList&>(g_);

  1610       return g.out_edge_list(u).size();

  1611     }

  1612     template <class Config, class Base>

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

  1614     edge(typename Config::vertex_descriptor u,

  1615          typename Config::vertex_descriptor v,

  1616          const adj_list_helper<Config, Base>& g_)

  1617     {

  1618       typedef typename Config::graph_type Graph;

  1619       typedef typename Config::edge_parallel_category Cat;

  1620       const Graph& g = static_cast<const Graph&>(g_);

  1621       return g_.edge_dispatch(g, u, v, Cat());

  1622     }

  1623     template <class Config, class Base>

  1624     inline std::pair<typename Config::out_edge_iterator,

  1625                      typename Config::out_edge_iterator>

  1626     edge_range(typename Config::vertex_descriptor u,

  1627                typename Config::vertex_descriptor v,

  1628                const adj_list_helper<Config, Base>& g_)

  1629     {

  1630       typedef typename Config::graph_type Graph;

  1631       typedef typename Config::StoredEdge StoredEdge;

  1632       const Graph& cg = static_cast<const Graph&>(g_);

  1633       Graph& g = const_cast<Graph&>(cg);

  1634       typedef typename Config::out_edge_iterator out_edge_iterator;

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

  1636       typename Config::OutEdgeList::iterator first, last;

  1637       typename Config::EdgeContainer fake_edge_container;

  1638       tie(first, last) =

  1639         std::equal_range(el.begin(), el.end(),

  1640                          StoredEdge(v, fake_edge_container.end(),

  1641                                     &fake_edge_container));

  1642       return std::make_pair(out_edge_iterator(first, u),

  1643                             out_edge_iterator(last, u));

  1644     }

  1646     template <class Config>

  1647     inline typename Config::degree_size_type

  1648     in_degree(typename Config::vertex_descriptor u,

  1649               const directed_edges_helper<Config>& g_)

  1650     {

  1651       typedef typename Config::graph_type Graph;

  1652       const Graph& cg = static_cast<const Graph&>(g_);

  1653       Graph& g = const_cast<Graph&>(cg);

  1654       return in_edge_list(g, u).size();

  1655     }

  1657     namespace detail {

  1658       template <class Config, class Base, class Property>

  1659       inline

  1660       typename boost::property_map<typename Config::graph_type,

  1661         Property>::type

  1662       get_dispatch(adj_list_helper<Config,Base>&, Property,

  1663                    boost::edge_property_tag) {

  1664         typedef typename Config::graph_type Graph;

  1665         typedef typename boost::property_map<Graph, Property>::type PA;

  1666         return PA();

  1667       }

  1668       template <class Config, class Base, class Property>

  1669       inline

  1670       typename boost::property_map<typename Config::graph_type,

  1671         Property>::const_type

  1672       get_dispatch(const adj_list_helper<Config,Base>&, Property,

  1673                    boost::edge_property_tag) {

  1674         typedef typename Config::graph_type Graph;

  1675         typedef typename boost::property_map<Graph, Property>::const_type PA;

  1676         return PA();

  1677       }

  1679       template <class Config, class Base, class Property>

  1680       inline

  1681       typename boost::property_map<typename Config::graph_type,

  1682         Property>::type

  1683       get_dispatch(adj_list_helper<Config,Base>& g, Property,

  1684                    boost::vertex_property_tag) {

  1685         typedef typename Config::graph_type Graph;

  1686         typedef typename boost::property_map<Graph, Property>::type PA;

  1687         return PA(&static_cast<Graph&>(g));

  1688       }

  1689       template <class Config, class Base, class Property>

  1690       inline

  1691       typename boost::property_map<typename Config::graph_type,

  1692         Property>::const_type

  1693       get_dispatch(const adj_list_helper<Config, Base>& g, Property,

  1694                    boost::vertex_property_tag) {

  1695         typedef typename Config::graph_type Graph;

  1696         typedef typename boost::property_map<Graph, Property>::const_type PA;

  1697         const Graph& cg = static_cast<const Graph&>(g);

  1698         return PA(&cg);

  1699       }

  1701     } // namespace detail

  1703     // Implementation of the PropertyGraph interface

  1704     template <class Config, class Base, class Property>

  1705     inline

  1706     typename boost::property_map<typename Config::graph_type, Property>::type

  1707     get(Property p, adj_list_helper<Config, Base>& g) {

  1708       typedef typename property_kind<Property>::type Kind;

  1709       return detail::get_dispatch(g, p, Kind());

  1710     }

  1711     template <class Config, class Base, class Property>

  1712     inline

  1713     typename boost::property_map<typename Config::graph_type,

  1714       Property>::const_type

  1715     get(Property p, const adj_list_helper<Config, Base>& g) {

  1716       typedef typename property_kind<Property>::type Kind;

  1717       return detail::get_dispatch(g, p, Kind());

  1718     }

  1720     template <class Config, class Base, class Property, class Key>

  1721     inline

  1722     typename boost::property_traits<

  1723       typename boost::property_map<typename Config::graph_type,

  1724         Property>::type

  1725     >::reference

  1726     get(Property p, adj_list_helper<Config, Base>& g, const Key& key) {

  1727       return get(get(p, g), key);

  1728     }

  1730     template <class Config, class Base, class Property, class Key>

  1731     inline

  1732     typename boost::property_traits<

  1733       typename boost::property_map<typename Config::graph_type,

  1734         Property>::const_type

  1735     >::reference

  1736     get(Property p, const adj_list_helper<Config, Base>& g, const Key& key) {

  1737       return get(get(p, g), key);

  1738     }

  1740     template <class Config, class Base, class Property, class Key,class Value>

  1741     inline void

  1742     put(Property p, adj_list_helper<Config, Base>& g,

  1743         const Key& key, const Value& value)

  1744     {

  1745       typedef typename Config::graph_type Graph;

  1746       typedef typename boost::property_map<Graph, Property>::type Map;

  1747       Map pmap = get(p, static_cast<Graph&>(g));

  1748       put(pmap, key, value);

  1749     }

  1752     //=========================================================================

  1753     // Generalize Adjacency List Implementation

  1755     struct adj_list_tag { };

  1757     template <class Derived, class Config, class Base>

  1758     class adj_list_impl

  1759       : public adj_list_helper<Config, Base>

  1760     {

  1761       typedef typename Config::OutEdgeList OutEdgeList;

  1762       typedef typename Config::InEdgeList InEdgeList;

  1763       typedef typename Config::StoredVertexList StoredVertexList;

  1764     public:

  1765       typedef typename Config::stored_vertex stored_vertex;

  1766       typedef typename Config::EdgeContainer EdgeContainer;

  1767       typedef typename Config::vertex_descriptor vertex_descriptor;

  1768       typedef typename Config::edge_descriptor edge_descriptor;

  1769       typedef typename Config::vertex_iterator vertex_iterator;

  1770       typedef typename Config::edge_iterator edge_iterator;

  1771       typedef typename Config::edge_parallel_category edge_parallel_category;

  1772       typedef typename Config::vertices_size_type vertices_size_type;

  1773       typedef typename Config::edges_size_type edges_size_type;

  1774       typedef typename Config::degree_size_type degree_size_type;

  1775       typedef typename Config::edge_property_type edge_property_type;

  1776       typedef adj_list_tag graph_tag;

  1778       static vertex_descriptor null_vertex()

  1779       {

  1780         return 0;

  1781       }

  1783       inline adj_list_impl() { }

  1785       inline adj_list_impl(const adj_list_impl& x) {

  1786         copy_impl(x);

  1787       }

  1788       inline adj_list_impl& operator=(const adj_list_impl& x) {

  1789         this->clear();

  1790         copy_impl(x);

  1791         return *this;

  1792       }

  1793       inline void clear() {

  1794         for (typename StoredVertexList::iterator i = m_vertices.begin();

  1795              i != m_vertices.end(); ++i)

  1796           delete (stored_vertex*)*i;

  1797         m_vertices.clear();

  1798         m_edges.clear();

  1799       }

  1800       inline adj_list_impl(vertices_size_type num_vertices) {

  1801         for (vertices_size_type i = 0; i < num_vertices; ++i)

  1802           add_vertex(static_cast<Derived&>(*this));

  1803       }

  1804       template <class EdgeIterator>

  1805       inline adj_list_impl(vertices_size_type num_vertices,

  1806                            EdgeIterator first, EdgeIterator last)

  1807       {

  1808         vertex_descriptor* v = new vertex_descriptor[num_vertices];

  1809         for (vertices_size_type i = 0; i < num_vertices; ++i)

  1810           v[i] = add_vertex(static_cast<Derived&>(*this));

  1812         while (first != last) {

  1813           add_edge(v[(*first).first], v[(*first).second], *this);

  1814           ++first;

  1815         }

  1816         delete [] v;

  1817       }

  1818       template <class EdgeIterator, class EdgePropertyIterator>

  1819       inline adj_list_impl(vertices_size_type num_vertices,

  1820                            EdgeIterator first, EdgeIterator last,

  1821                            EdgePropertyIterator ep_iter)

  1822       {

  1823         vertex_descriptor* v = new vertex_descriptor[num_vertices];

  1824         for (vertices_size_type i = 0; i < num_vertices; ++i)

  1825           v[i] = add_vertex(static_cast<Derived&>(*this));

  1827         while (first != last) {

  1828           add_edge(v[(*first).first], v[(*first).second], *ep_iter, *this);

  1829           ++first;

  1830           ++ep_iter;

  1831         }

  1832         delete [] v;

  1833       }

  1834       ~adj_list_impl() {

  1835         for (typename StoredVertexList::iterator i = m_vertices.begin();

  1836              i != m_vertices.end(); ++i)

  1837           delete (stored_vertex*)*i;

  1838       }

  1839       //    protected:

  1840       inline OutEdgeList& out_edge_list(vertex_descriptor v) {

  1841         stored_vertex* sv = (stored_vertex*)v;

  1842         return sv->m_out_edges;

  1843       }

  1844       inline const OutEdgeList& out_edge_list(vertex_descriptor v) const {

  1845         stored_vertex* sv = (stored_vertex*)v;

  1846         return sv->m_out_edges;

  1847       }

  1848       inline StoredVertexList& vertex_set() { return m_vertices; }

  1849       inline const StoredVertexList& vertex_set() const { return m_vertices; }

  1851       inline void copy_impl(const adj_list_impl& x_)

  1852       {

  1853         const Derived& x = static_cast<const Derived&>(x_);

  1855         // Would be better to have a constant time way to get from

  1856         // vertices in x to the corresponding vertices in *this.

  1857         std::map<stored_vertex*,stored_vertex*> vertex_map;

  1859         // Copy the stored vertex objects by adding each vertex

  1860         // and copying its property object.

  1861         vertex_iterator vi, vi_end;

  1862         for (tie(vi, vi_end) = vertices(x); vi != vi_end; ++vi) {

  1863           stored_vertex* v = (stored_vertex*)add_vertex(*this);

  1864           v->m_property = ((stored_vertex*)*vi)->m_property;

  1865           vertex_map[(stored_vertex*)*vi] = v;

  1866         }

  1867         // Copy the edges by adding each edge and copying its

  1868         // property object.

  1869         edge_iterator ei, ei_end;

  1870         for (tie(ei, ei_end) = edges(x); ei != ei_end; ++ei) {

  1871           edge_descriptor e;

  1872           bool inserted;

  1873           vertex_descriptor s = source(*ei,x), t = target(*ei,x);

  1874           tie(e, inserted) = add_edge(vertex_map[(stored_vertex*)s],

  1875                                       vertex_map[(stored_vertex*)t], *this);

  1876           *((edge_property_type*)e.m_eproperty)

  1877             = *((edge_property_type*)(*ei).m_eproperty);

  1878         }

  1879       }

  1882       typename Config::EdgeContainer m_edges;

  1883       StoredVertexList m_vertices;

  1884     };

  1886     // O(1)

  1887     template <class Derived, class Config, class Base>

  1888     inline typename Config::vertex_descriptor

  1889     add_vertex(adj_list_impl<Derived, Config, Base>& g_)

  1890     {

  1891       Derived& g = static_cast<Derived&>(g_);

  1892       typedef typename Config::stored_vertex stored_vertex;

  1893       stored_vertex* v = new stored_vertex;

  1894       typename Config::StoredVertexList::iterator pos;

  1895       bool inserted;

  1896       boost::tie(pos,inserted) = boost::graph_detail::push(g.m_vertices, v);

  1897       v->m_position = pos;

  1898       return v;

  1899     }

  1900     // O(1)

  1901     template <class Derived, class Config, class Base>

  1902     inline typename Config::vertex_descriptor

  1903     add_vertex(const typename Config::vertex_property_type& p,

  1904                adj_list_impl<Derived, Config, Base>& g_)

  1905     {

  1906       Derived& g = static_cast<Derived&>(g_);

  1907       typedef typename Config::stored_vertex stored_vertex;

  1908       stored_vertex* v = new stored_vertex(p);

  1909       typename Config::StoredVertexList::iterator pos;

  1910       bool inserted;

  1911       boost::tie(pos,inserted) = boost::graph_detail::push(g.m_vertices, v);

  1912       v->m_position = pos;

  1913       return v;

  1914     }

  1915     // O(1)

  1916     template <class Derived, class Config, class Base>

  1917     inline void remove_vertex(typename Config::vertex_descriptor u,

  1918                               adj_list_impl<Derived, Config, Base>& g_)

  1919     {

  1920       typedef typename Config::stored_vertex stored_vertex;

  1921       Derived& g = static_cast<Derived&>(g_);

  1922       stored_vertex* su = (stored_vertex*)u;

  1923       g.m_vertices.erase(su->m_position);

  1924       delete su;

  1925     }

  1926     // O(V)

  1927     template <class Derived, class Config, class Base>

  1928     inline typename Config::vertex_descriptor

  1929     vertex(typename Config::vertices_size_type n,

  1930            const adj_list_impl<Derived, Config, Base>& g_)

  1931     {

  1932       const Derived& g = static_cast<const Derived&>(g_);

  1933       typename Config::vertex_iterator i = vertices(g).first;

  1934       while (n--) ++i; // std::advance(i, n); (not VC++ portable)

  1935       return *i;

  1936     }

  1938     //=========================================================================

  1939     // Vector-Backbone Adjacency List Implementation

  1941     namespace detail {

  1943       template <class Graph, class vertex_descriptor>

  1944       inline void

  1945       remove_vertex_dispatch(Graph& g, vertex_descriptor u,

  1946                              boost::directed_tag)

  1947       {

  1948         typedef typename Graph::edge_parallel_category edge_parallel_category;

  1949         g.m_vertices.erase(g.m_vertices.begin() + u);

  1950         vertex_descriptor V = num_vertices(g);

  1951         if (u != V) {

  1952           for (vertex_descriptor v = 0; v < V; ++v)

  1953             reindex_edge_list(g.out_edge_list(v), u, edge_parallel_category());

  1954         }

  1955       }

  1957       template <class Graph, class vertex_descriptor>

  1958       inline void

  1959       remove_vertex_dispatch(Graph& g, vertex_descriptor u,

  1960                              boost::undirected_tag)

  1961       {

  1962         typedef typename Graph::global_edgelist_selector EdgeListS;

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

  1965         typedef typename Graph::edge_parallel_category edge_parallel_category;

  1966         g.m_vertices.erase(g.m_vertices.begin() + u);

  1967         vertex_descriptor V = num_vertices(g);

  1968         for (vertex_descriptor v = 0; v < V; ++v)

  1969           reindex_edge_list(g.out_edge_list(v), u,

  1970                             edge_parallel_category());

  1971         typedef typename Graph::EdgeContainer Container;

  1972         typedef typename Container::iterator Iter;

  1973         Iter ei = g.m_edges.begin(), ei_end = g.m_edges.end();

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

  1975           if (ei->m_source > u)

  1976             --ei->m_source;

  1977           if (ei->m_target > u)

  1978             --ei->m_target;

  1979         }

  1980       }

  1981       template <class Graph, class vertex_descriptor>

  1982       inline void

  1983       remove_vertex_dispatch(Graph& g, vertex_descriptor u,

  1984                              boost::bidirectional_tag)

  1985       {

  1986         typedef typename Graph::global_edgelist_selector EdgeListS;

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

  1989         typedef typename Graph::edge_parallel_category edge_parallel_category;

  1990         g.m_vertices.erase(g.m_vertices.begin() + u);

  1991         vertex_descriptor V = num_vertices(g);

  1992         vertex_descriptor v;

  1993         if (u != V) {

  1994           for (v = 0; v < V; ++v)

  1995             reindex_edge_list(g.out_edge_list(v), u,

  1996                               edge_parallel_category());

  1997           for (v = 0; v < V; ++v)

  1998             reindex_edge_list(in_edge_list(g, v), u,

  1999                               edge_parallel_category());

  2001           typedef typename Graph::EdgeContainer Container;

  2002           typedef typename Container::iterator Iter;

  2003           Iter ei = g.m_edges.begin(), ei_end = g.m_edges.end();

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

  2005             if (ei->m_source > u)

  2006               --ei->m_source;

  2007             if (ei->m_target > u)

  2008               --ei->m_target;

  2009           }

  2010         }

  2011       }

  2013       template <class EdgeList, class vertex_descriptor>

  2014       inline void

  2015       reindex_edge_list(EdgeList& el, vertex_descriptor u,

  2016                         boost::allow_parallel_edge_tag)

  2017       {

  2018         typename EdgeList::iterator ei = el.begin(), e_end = el.end();

  2019         for (; ei != e_end; ++ei)

  2020           if ((*ei).get_target() > u)

  2021             --(*ei).get_target();

  2022       }

  2023       template <class EdgeList, class vertex_descriptor>

  2024       inline void

  2025       reindex_edge_list(EdgeList& el, vertex_descriptor u,

  2026                         boost::disallow_parallel_edge_tag)

  2027       {

  2028         typename EdgeList::iterator ei = el.begin(), e_end = el.end();

  2029         while (ei != e_end) {

  2030           typename EdgeList::value_type ce = *ei;

  2031           ++ei;

  2032           if (ce.get_target() > u) {

  2033             el.erase(ce);

  2034             --ce.get_target();

  2035             el.insert(ce);

  2036           }

  2037         }

  2038       }

  2039     } // namespace detail

  2041     struct vec_adj_list_tag { };

  2043     template <class Graph, class Config, class Base>

  2044     class vec_adj_list_impl

  2045       : public adj_list_helper<Config, Base>

  2046     {

  2047       typedef typename Config::OutEdgeList OutEdgeList;

  2048       typedef typename Config::InEdgeList InEdgeList;

  2049       typedef typename Config::StoredVertexList StoredVertexList;

  2050     public:

  2051       typedef typename Config::vertex_descriptor vertex_descriptor;

  2052       typedef typename Config::edge_descriptor edge_descriptor;

  2053       typedef typename Config::out_edge_iterator out_edge_iterator;

  2054       typedef typename Config::edge_iterator edge_iterator;

  2055       typedef typename Config::directed_category directed_category;

  2056       typedef typename Config::vertices_size_type vertices_size_type;

  2057       typedef typename Config::edges_size_type edges_size_type;

  2058       typedef typename Config::degree_size_type degree_size_type;

  2059       typedef typename Config::StoredEdge StoredEdge;

  2060       typedef typename Config::stored_vertex stored_vertex;

  2061       typedef typename Config::EdgeContainer EdgeContainer;

  2062       typedef typename Config::edge_property_type edge_property_type;

  2063       typedef vec_adj_list_tag graph_tag;

  2065       static vertex_descriptor null_vertex()

  2066       {

  2067         return (std::numeric_limits<vertex_descriptor>::max)();

  2068       }

  2070       inline vec_adj_list_impl() { }

  2072       inline vec_adj_list_impl(const vec_adj_list_impl& x) {

  2073         copy_impl(x);

  2074       }

  2075       inline vec_adj_list_impl& operator=(const vec_adj_list_impl& x) {

  2076         this->clear();

  2077         copy_impl(x);

  2078         return *this;

  2079       }

  2080       inline void clear() {

  2081         m_vertices.clear();

  2082         m_edges.clear();

  2083       }

  2085       inline vec_adj_list_impl(vertices_size_type _num_vertices)

  2086         : m_vertices(_num_vertices) { }

  2088       template <class EdgeIterator>

  2089       inline vec_adj_list_impl(vertices_size_type num_vertices,

  2090                                EdgeIterator first, EdgeIterator last)

  2091         : m_vertices(num_vertices)

  2092       {

  2093         while (first != last) {

  2094           add_edge((*first).first, (*first).second,

  2095                    static_cast<Graph&>(*this));

  2096           ++first;

  2097         }

  2098       }

  2099       template <class EdgeIterator, class EdgePropertyIterator>

  2100       inline vec_adj_list_impl(vertices_size_type num_vertices,

  2101                                EdgeIterator first, EdgeIterator last,

  2102                                EdgePropertyIterator ep_iter)

  2103         : m_vertices(num_vertices)

  2104       {

  2105         while (first != last) {

  2106           add_edge((*first).first, (*first).second, *ep_iter,

  2107                    static_cast<Graph&>(*this));

  2108           ++first;

  2109           ++ep_iter;

  2110         }

  2111       }

  2113       //    protected:

  2114       inline boost::integer_range<vertex_descriptor> vertex_set() const {

  2115         return boost::integer_range<vertex_descriptor>(0, m_vertices.size());

  2116       }

  2117       inline OutEdgeList& out_edge_list(vertex_descriptor v) {

  2118         return m_vertices[v].m_out_edges;

  2119       }

  2120       inline const OutEdgeList& out_edge_list(vertex_descriptor v) const {

  2121         return m_vertices[v].m_out_edges;

  2122       }

  2123       inline void copy_impl(const vec_adj_list_impl& x_)

  2124       {

  2125         const Graph& x = static_cast<const Graph&>(x_);

  2126         // Copy the stored vertex objects by adding each vertex

  2127         // and copying its property object.

  2128         for (vertices_size_type i = 0; i < num_vertices(x); ++i) {

  2129           vertex_descriptor v = add_vertex(*this);

  2130           m_vertices[v].m_property = x.m_vertices[i].m_property;

  2131         }

  2132         // Copy the edges by adding each edge and copying its

  2133         // property object.

  2134         edge_iterator ei, ei_end;

  2135         for (tie(ei, ei_end) = edges(x); ei != ei_end; ++ei) {

  2136           edge_descriptor e;

  2137           bool inserted;

  2138           tie(e, inserted) = add_edge(source(*ei,x), target(*ei,x) , *this);

  2139           *((edge_property_type*)e.m_eproperty)

  2140             = *((edge_property_type*)(*ei).m_eproperty);

  2141         }

  2142       }

  2143       typename Config::EdgeContainer m_edges;

  2144       StoredVertexList m_vertices;

  2145     };

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

  2147     // on SGI MIPSpro C++

  2148     template <class G, class C, class B>

  2149     inline typename C::InEdgeList&

  2150     in_edge_list(vec_adj_list_impl<G,C,B>& g,

  2151                  typename C::vertex_descriptor v) {

  2152       return g.m_vertices[v].m_in_edges;

  2153     }

  2154     template <class G, class C, class B>

  2155     inline const typename C::InEdgeList&

  2156     in_edge_list(const vec_adj_list_impl<G,C,B>& g,

  2157                  typename C::vertex_descriptor v) {

  2158       return g.m_vertices[v].m_in_edges;

  2159     }

  2161       // O(1)

  2162     template <class Graph, class Config, class Base>

  2163     inline typename Config::vertex_descriptor

  2164     add_vertex(vec_adj_list_impl<Graph, Config, Base>& g_) {

  2165       Graph& g = static_cast<Graph&>(g_);

  2166       g.m_vertices.resize(g.m_vertices.size() + 1);

  2167       return g.m_vertices.size() - 1;

  2168     }

  2170     template <class Graph, class Config, class Base>

  2171     inline typename Config::vertex_descriptor

  2172     add_vertex(const typename Config::vertex_property_type& p,

  2173                vec_adj_list_impl<Graph, Config, Base>& g_) {

  2174       Graph& g = static_cast<Graph&>(g_);

  2175       typedef typename Config::stored_vertex stored_vertex;

  2176       g.m_vertices.push_back(stored_vertex(p));

  2177       return g.m_vertices.size() - 1;

  2178     }

  2180     // Here we override the directed_graph_helper add_edge() function

  2181     // so that the number of vertices is automatically changed if

  2182     // either u or v is greater than the number of vertices.

  2183     template <class Graph, class Config, class Base>

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

  2185     add_edge(typename Config::vertex_descriptor u,

  2186              typename Config::vertex_descriptor v,

  2187              const typename Config::edge_property_type& p,

  2188              vec_adj_list_impl<Graph, Config, Base>& g_)

  2189     {

  2190       BOOST_USING_STD_MAX();

  2191       typename Config::vertex_descriptor x = max BOOST_PREVENT_MACRO_SUBSTITUTION(u, v);

  2192       if (x >= num_vertices(g_))

  2193         g_.m_vertices.resize(x + 1);

  2194       adj_list_helper<Config, Base>& g = g_;

  2195       return add_edge(u, v, p, g);

  2196     }

  2197     template <class Graph, class Config, class Base>

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

  2199     add_edge(typename Config::vertex_descriptor u,

  2200              typename Config::vertex_descriptor v,

  2201              vec_adj_list_impl<Graph, Config, Base>& g_)

  2202     {

  2203       typename Config::edge_property_type p;

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

  2205     }

  2208     // O(V + E)

  2209     template <class Graph, class Config, class Base>

  2210     inline void remove_vertex(typename Config::vertex_descriptor v,

  2211                               vec_adj_list_impl<Graph, Config, Base>& g_)

  2212     {

  2213       typedef typename Config::directed_category Cat;

  2214       Graph& g = static_cast<Graph&>(g_);

  2215       detail::remove_vertex_dispatch(g, v, Cat());

  2216     }

  2217     // O(1)

  2218     template <class Graph, class Config, class Base>

  2219     inline typename Config::vertex_descriptor

  2220     vertex(typename Config::vertices_size_type n,

  2221            const vec_adj_list_impl<Graph, Config, Base>&)

  2222     {

  2223       return n;

  2224     }

  2227   namespace detail {

  2229     //=========================================================================

  2230     // Adjacency List Generator

  2232     template <class Graph, class VertexListS, class OutEdgeListS,

  2233               class DirectedS, class VertexProperty, class EdgeProperty,

  2234               class GraphProperty, class EdgeListS>

  2235     struct adj_list_gen

  2236     {

  2237       typedef typename detail::is_random_access<VertexListS>::type

  2238         is_rand_access;

  2239       typedef typename has_property<EdgeProperty>::type has_edge_property;

  2240       typedef typename DirectedS::is_directed_t DirectedT;

  2241       typedef typename DirectedS::is_bidir_t BidirectionalT;

  2243       struct config

  2244       {

  2245         typedef OutEdgeListS edgelist_selector;

  2246         typedef EdgeListS global_edgelist_selector;

  2248         typedef Graph graph_type;

  2249         typedef EdgeProperty edge_property_type;

  2250         typedef VertexProperty vertex_property_type;

  2251         typedef GraphProperty graph_property_type;

  2252         typedef std::size_t vertices_size_type;

  2254         typedef adjacency_list_traits<OutEdgeListS, VertexListS, DirectedS>

  2255            Traits;

  2257         typedef typename Traits::directed_category directed_category;

  2258         typedef typename Traits::edge_parallel_category edge_parallel_category;

  2259         typedef typename Traits::vertex_descriptor vertex_descriptor;

  2260         typedef typename Traits::edge_descriptor edge_descriptor;

  2262         typedef void* vertex_ptr;

  2264         // need to reorganize this to avoid instantiating stuff

  2265         // that doesn't get used -JGS

  2267         // VertexList and vertex_iterator

  2268         typedef typename container_gen<VertexListS,

  2269           vertex_ptr>::type SeqVertexList;

  2270         typedef boost::integer_range<std::size_t> RandVertexList;

  2271         typedef typename boost::ct_if_t<is_rand_access,

  2272           RandVertexList, SeqVertexList>::type VertexList;

  2274         typedef typename VertexList::iterator vertex_iterator;

  2276         // EdgeContainer and StoredEdge

  2278         typedef typename container_gen<EdgeListS,

  2279           list_edge<vertex_descriptor, EdgeProperty> >::type EdgeContainer;

  2281         typedef typename ct_and<DirectedT,

  2282              typename ct_not<BidirectionalT>::type >::type on_edge_storage;

  2284         typedef typename boost::ct_if_t<on_edge_storage,

  2285           std::size_t, typename EdgeContainer::size_type

  2286         >::type edges_size_type;

  2288         typedef typename EdgeContainer::iterator EdgeIter;

  2290         typedef typename detail::is_random_access<EdgeListS>::type is_edge_ra;

  2292         typedef typename boost::ct_if_t<on_edge_storage,

  2293           stored_edge_property<vertex_descriptor, EdgeProperty>,

  2294           typename boost::ct_if_t<is_edge_ra,

  2295             stored_ra_edge_iter<vertex_descriptor, EdgeContainer, EdgeProperty>,

  2296             stored_edge_iter<vertex_descriptor, EdgeIter, EdgeProperty>

  2297           >::type

  2298         >::type StoredEdge;

  2300         // Adjacency Types

  2302         typedef typename container_gen<OutEdgeListS, StoredEdge>::type

  2303           OutEdgeList;

  2304         typedef typename OutEdgeList::size_type degree_size_type;

  2305         typedef typename OutEdgeList::iterator OutEdgeIter;

  2307         typedef boost::detail::iterator_traits<OutEdgeIter> OutEdgeIterTraits;

  2308         typedef typename OutEdgeIterTraits::iterator_category OutEdgeIterCat;

  2309         typedef typename OutEdgeIterTraits::difference_type OutEdgeIterDiff;

  2311         typedef out_edge_iter<

  2312             OutEdgeIter, vertex_descriptor, edge_descriptor, OutEdgeIterDiff

  2313         > out_edge_iterator;

  2315         typedef typename adjacency_iterator_generator<graph_type,

  2316            vertex_descriptor, out_edge_iterator>::type adjacency_iterator;

  2318         typedef OutEdgeList InEdgeList;

  2319         typedef OutEdgeIter InEdgeIter;

  2320         typedef OutEdgeIterCat InEdgeIterCat;

  2321         typedef OutEdgeIterDiff InEdgeIterDiff;

  2323         typedef in_edge_iter<

  2324             InEdgeIter, vertex_descriptor, edge_descriptor, InEdgeIterDiff

  2325         > in_edge_iterator;

  2327         typedef typename inv_adjacency_iterator_generator<graph_type,

  2328            vertex_descriptor, in_edge_iterator>::type inv_adjacency_iterator;

  2330         // Edge Iterator

  2332         typedef boost::detail::iterator_traits<EdgeIter> EdgeIterTraits;

  2333         typedef typename EdgeIterTraits::iterator_category EdgeIterCat;

  2334         typedef typename EdgeIterTraits::difference_type EdgeIterDiff;

  2336         typedef undirected_edge_iter<

  2337             EdgeIter

  2338           , edge_descriptor

  2339           , EdgeIterDiff

  2340         > UndirectedEdgeIter; // also used for bidirectional

  2342         typedef adj_list_edge_iterator<vertex_iterator, out_edge_iterator,

  2343            graph_type> DirectedEdgeIter;

  2345         typedef typename boost::ct_if_t<on_edge_storage,

  2346           DirectedEdgeIter, UndirectedEdgeIter>::type edge_iterator;

  2348         // stored_vertex and StoredVertexList

  2349         typedef typename container_gen<VertexListS, vertex_ptr>::type

  2350           SeqStoredVertexList;

  2351         struct seq_stored_vertex {

  2352           seq_stored_vertex() { }

  2353           seq_stored_vertex(const VertexProperty& p) : m_property(p) { }

  2354           OutEdgeList m_out_edges;

  2355           VertexProperty m_property;

  2356           typename SeqStoredVertexList::iterator m_position;

  2357         };

  2358         struct bidir_seq_stored_vertex {

  2359           bidir_seq_stored_vertex() { }

  2360           bidir_seq_stored_vertex(const VertexProperty& p) : m_property(p) { }

  2361           OutEdgeList m_out_edges;

  2362           InEdgeList m_in_edges;

  2363           VertexProperty m_property;

  2364           typename SeqStoredVertexList::iterator m_position;

  2365         };

  2366         struct rand_stored_vertex {

  2367           rand_stored_vertex() { }

  2368           rand_stored_vertex(const VertexProperty& p) : m_property(p) { }

  2369           OutEdgeList m_out_edges;

  2370           VertexProperty m_property;

  2371         };

  2372         struct bidir_rand_stored_vertex {

  2373           bidir_rand_stored_vertex() { }

  2374           bidir_rand_stored_vertex(const VertexProperty& p) : m_property(p) { }

  2375           OutEdgeList m_out_edges;

  2376           InEdgeList m_in_edges;

  2377           VertexProperty m_property;

  2378         };

  2379         typedef typename boost::ct_if_t<is_rand_access,

  2380           typename boost::ct_if_t<BidirectionalT,

  2381             bidir_rand_stored_vertex, rand_stored_vertex>::type,

  2382           typename boost::ct_if_t<BidirectionalT,

  2383             bidir_seq_stored_vertex, seq_stored_vertex>::type

  2384         >::type StoredVertex;

  2385         struct stored_vertex : public StoredVertex {

  2386           stored_vertex() { }

  2387           stored_vertex(const VertexProperty& p) : StoredVertex(p) { }

  2388         };

  2390         typedef typename container_gen<VertexListS, stored_vertex>::type

  2391           RandStoredVertexList;

  2392         typedef typename boost::ct_if_t< is_rand_access,

  2393           RandStoredVertexList, SeqStoredVertexList>::type StoredVertexList;

  2394       }; // end of config

  2397       typedef typename boost::ct_if_t<BidirectionalT,

  2398         bidirectional_graph_helper_with_property<config>,

  2399         typename boost::ct_if_t<DirectedT,

  2400           directed_graph_helper<config>,

  2401           undirected_graph_helper<config>

  2402         >::type

  2403       >::type DirectedHelper;

  2405       typedef typename boost::ct_if_t<is_rand_access,

  2406         vec_adj_list_impl<Graph, config, DirectedHelper>,

  2407         adj_list_impl<Graph, config, DirectedHelper>

  2408       >::type type;

  2410     };

  2412   } // namespace detail

  2414     //=========================================================================

  2415     // Vertex Property Maps

  2417     template <class Graph, class ValueType, class Reference, class Tag>

  2418     struct adj_list_vertex_property_map

  2419       : public boost::put_get_helper<

  2420           Reference,

  2421           adj_list_vertex_property_map<Graph, ValueType, Reference, Tag>

  2422         >

  2423     {

  2424       typedef typename Graph::stored_vertex StoredVertex;

  2425       typedef ValueType value_type;

  2426       typedef Reference reference;

  2427       typedef typename Graph::vertex_descriptor key_type;

  2428       typedef boost::lvalue_property_map_tag category;

  2429       inline adj_list_vertex_property_map() { }

  2430       inline adj_list_vertex_property_map(const Graph*) { }

  2431       inline Reference operator[](key_type v) const {

  2432         StoredVertex* sv = (StoredVertex*)v;

  2433         return get_property_value(sv->m_property, Tag());

  2434       }

  2435       inline Reference operator()(key_type v) const {

  2436         return this->operator[](v);

  2437       }

  2438     };

  2440     template <class Graph, class Property, class PropRef>

  2441     struct adj_list_vertex_all_properties_map

  2442       : public boost::put_get_helper<PropRef,

  2443           adj_list_vertex_all_properties_map<Graph, Property, PropRef>

  2444         >

  2445     {

  2446       typedef typename Graph::stored_vertex StoredVertex;

  2447       typedef Property value_type;

  2448       typedef PropRef reference;

  2449       typedef typename Graph::vertex_descriptor key_type;

  2450       typedef boost::lvalue_property_map_tag category;

  2451       inline adj_list_vertex_all_properties_map() { }

  2452       inline adj_list_vertex_all_properties_map(const Graph*) { }

  2453       inline PropRef operator[](key_type v) const {

  2454         StoredVertex* sv = (StoredVertex*)v;

  2455         return sv->m_property;

  2456       }

  2457       inline PropRef operator()(key_type v) const {

  2458         return this->operator[](v);

  2459       }

  2460     };

  2462     template <class Graph, class GraphPtr, class ValueType, class Reference,

  2463               class Tag>

  2464     struct vec_adj_list_vertex_property_map

  2465       : public boost::put_get_helper<

  2466           Reference,

  2467           vec_adj_list_vertex_property_map<Graph,GraphPtr,ValueType,Reference,

  2468              Tag>

  2469         >

  2470     {

  2471       typedef ValueType value_type;

  2472       typedef Reference reference;

  2473       typedef typename boost::graph_traits<Graph>::vertex_descriptor key_type;

  2474       typedef boost::lvalue_property_map_tag category;

  2475       vec_adj_list_vertex_property_map() { }

  2476       vec_adj_list_vertex_property_map(GraphPtr g) : m_g(g) { }

  2477       inline Reference operator[](key_type v) const {

  2478         return get_property_value(m_g->m_vertices[v].m_property,  Tag());

  2479       }

  2480       inline Reference operator()(key_type v) const {

  2481         return this->operator[](v);

  2482       }

  2483       GraphPtr m_g;

  2484     };

  2486     template <class Graph, class GraphPtr, class Property, class PropertyRef>

  2487     struct vec_adj_list_vertex_all_properties_map

  2488       : public boost::put_get_helper<PropertyRef,

  2489           vec_adj_list_vertex_all_properties_map<Graph,GraphPtr,Property,

  2490             PropertyRef>

  2491         >

  2492     {

  2493       typedef Property value_type;

  2494       typedef PropertyRef reference;

  2495       typedef typename boost::graph_traits<Graph>::vertex_descriptor key_type;

  2496       typedef boost::lvalue_property_map_tag category;

  2497       vec_adj_list_vertex_all_properties_map() { }

  2498       vec_adj_list_vertex_all_properties_map(GraphPtr g) : m_g(g) { }

  2499       inline PropertyRef operator[](key_type v) const {

  2500         return m_g->m_vertices[v].m_property;

  2501       }

  2502       inline PropertyRef operator()(key_type v) const {

  2503         return this->operator[](v);

  2504       }

  2505       GraphPtr m_g;

  2506     };

  2508     struct adj_list_any_vertex_pa {

  2509       template <class Tag, class Graph, class Property>

  2510       struct bind_ {

  2511         typedef typename property_value<Property, Tag>::type value_type;

  2512         typedef value_type& reference;

  2513         typedef const value_type& const_reference;

  2515         typedef adj_list_vertex_property_map

  2516           <Graph, value_type, reference, Tag> type;

  2517         typedef adj_list_vertex_property_map

  2518           <Graph, value_type, const_reference, Tag> const_type;

  2519       };

  2520     };

  2521     struct adj_list_all_vertex_pa {

  2522       template <class Tag, class Graph, class Property>

  2523       struct bind_ {

  2524         typedef typename Graph::vertex_descriptor Vertex;

  2525         typedef adj_list_vertex_all_properties_map<Graph,Property,

  2526           Property&> type;

  2527         typedef adj_list_vertex_all_properties_map<Graph,Property,

  2528           const Property&> const_type;

  2529       };

  2530     };

  2532     template <class Property, class Vertex>

  2533     struct vec_adj_list_vertex_id_map

  2534       : public boost::put_get_helper<

  2535           Vertex, vec_adj_list_vertex_id_map<Property, Vertex>

  2536         >

  2537     {

  2538       typedef Vertex value_type;

  2539       typedef Vertex key_type;

  2540       typedef Vertex reference;

  2541       typedef boost::readable_property_map_tag category;

  2542       inline vec_adj_list_vertex_id_map() { }

  2543       template <class Graph>

  2544       inline vec_adj_list_vertex_id_map(const Graph&) { }

  2545       inline value_type operator[](key_type v) const { return v; }

  2546       inline value_type operator()(key_type v) const { return v; }

  2547     };

  2549     struct vec_adj_list_any_vertex_pa {

  2550       template <class Tag, class Graph, class Property>

  2551       struct bind_ {

  2552         typedef typename property_value<Property, Tag>::type value_type;

  2553         typedef value_type& reference;

  2554         typedef const value_type& const_reference;

  2556         typedef vec_adj_list_vertex_property_map

  2557           <Graph, Graph*, value_type, reference, Tag> type;

  2558         typedef vec_adj_list_vertex_property_map

  2559           <Graph, const Graph*, value_type, const_reference, Tag> const_type;

  2560       };

  2561     };

  2562     struct vec_adj_list_id_vertex_pa {

  2563       template <class Tag, class Graph, class Property>

  2564       struct bind_ {

  2565         typedef typename Graph::vertex_descriptor Vertex;

  2566         typedef vec_adj_list_vertex_id_map<Property, Vertex> type;

  2567         typedef vec_adj_list_vertex_id_map<Property, Vertex> const_type;

  2568       };

  2569     };

  2570     struct vec_adj_list_all_vertex_pa {

  2571       template <class Tag, class Graph, class Property>

  2572       struct bind_ {

  2573         typedef typename Graph::vertex_descriptor Vertex;

  2574         typedef vec_adj_list_vertex_all_properties_map

  2575           <Graph, Graph*, Property, Property&> type;

  2576         typedef vec_adj_list_vertex_all_properties_map

  2577           <Graph, const Graph*, Property, const Property&> const_type;

  2578       };

  2579     };

  2580   namespace detail {

  2581     template <class Tag>

  2582     struct adj_list_choose_vertex_pa_helper {

  2583       typedef adj_list_any_vertex_pa type;

  2584     };

  2585     template <>

  2586     struct adj_list_choose_vertex_pa_helper<vertex_all_t> {

  2587       typedef adj_list_all_vertex_pa type;

  2588     };

  2589     template <class Tag, class Graph, class Property>

  2590     struct adj_list_choose_vertex_pa {

  2591       typedef typename adj_list_choose_vertex_pa_helper<Tag>::type Helper;

  2592       typedef typename Helper::template bind_<Tag,Graph,Property> Bind;

  2593       typedef typename Bind::type type;

  2594       typedef typename Bind::const_type const_type;

  2595     };

  2598     template <class Tag>

  2599     struct vec_adj_list_choose_vertex_pa_helper {

  2600       typedef vec_adj_list_any_vertex_pa type;

  2601     };

  2602     template <>

  2603     struct vec_adj_list_choose_vertex_pa_helper<vertex_index_t> {

  2604       typedef vec_adj_list_id_vertex_pa type;

  2605     };

  2606     template <>

  2607     struct vec_adj_list_choose_vertex_pa_helper<vertex_all_t> {

  2608       typedef vec_adj_list_all_vertex_pa type;

  2609     };

  2610     template <class Tag, class Graph, class Property>

  2611     struct vec_adj_list_choose_vertex_pa {

  2612       typedef typename vec_adj_list_choose_vertex_pa_helper<Tag>::type Helper;

  2613       typedef typename Helper::template bind_<Tag,Graph,Property> Bind;

  2614       typedef typename Bind::type type;

  2615       typedef typename Bind::const_type const_type;

  2616     };

  2617   } // namespace detail

  2619     //=========================================================================

  2620     // Edge Property Map

  2622     template <class Directed, class Value, class Ref, class Vertex,

  2623               class Property, class Tag>

  2624     struct adj_list_edge_property_map

  2625       : public put_get_helper<

  2626           Ref,

  2627           adj_list_edge_property_map<Directed, Value, Ref, Vertex, Property,

  2628             Tag>

  2629         >

  2630     {

  2631       typedef Value value_type;

  2632       typedef Ref reference;

  2633       typedef detail::edge_desc_impl<Directed, Vertex> key_type;

  2634       typedef boost::lvalue_property_map_tag category;

  2635       inline Ref operator[](key_type e) const {

  2636         Property& p = *(Property*)e.get_property();

  2637         return get_property_value(p, Tag());

  2638       }

  2639       inline Ref operator()(key_type e) const {

  2640         return this->operator[](e);

  2641       }

  2642     };

  2644     template <class Directed, class Property, class PropRef, class PropPtr,

  2645       class Vertex>

  2646     struct adj_list_edge_all_properties_map

  2647       : public put_get_helper<PropRef,

  2648           adj_list_edge_all_properties_map<Directed, Property, PropRef,

  2649             PropPtr, Vertex>

  2650         >

  2651     {

  2652       typedef Property value_type;

  2653       typedef PropRef reference;

  2654       typedef detail::edge_desc_impl<Directed, Vertex> key_type;

  2655       typedef boost::lvalue_property_map_tag category;

  2656       inline PropRef operator[](key_type e) const {

  2657         return *(PropPtr)e.get_property();

  2658       }

  2659       inline PropRef operator()(key_type e) const {

  2660         return this->operator[](e);

  2661       }

  2662     };

  2664   // Edge Property Maps

  2666   namespace detail {

  2667     struct adj_list_any_edge_pmap {

  2668       template <class Graph, class Property, class Tag>

  2669       struct bind_ {

  2670         typedef typename property_value<Property,Tag>::type value_type;

  2671         typedef value_type& reference;

  2672         typedef const value_type& const_reference;

  2674         typedef adj_list_edge_property_map

  2675            <typename Graph::directed_category, value_type, reference,

  2676             typename Graph::vertex_descriptor,Property,Tag> type;

  2677         typedef adj_list_edge_property_map

  2678            <typename Graph::directed_category, value_type, const_reference,

  2679             typename Graph::vertex_descriptor,const Property, Tag> const_type;

  2680       };

  2681     };

  2682     struct adj_list_all_edge_pmap {

  2683       template <class Graph, class Property, class Tag>

  2684       struct bind_ {

  2685         typedef adj_list_edge_all_properties_map

  2686         <typename Graph::directed_category, Property, Property&, Property*,

  2687             typename Graph::vertex_descriptor> type;

  2688         typedef adj_list_edge_all_properties_map

  2689         <typename Graph::directed_category, Property, const Property&,

  2690             const Property*, typename Graph::vertex_descriptor> const_type;

  2691       };

  2692     };

  2694     template <class Tag>

  2695     struct adj_list_choose_edge_pmap_helper {

  2696       typedef adj_list_any_edge_pmap type;

  2697     };

  2698     template <>

  2699     struct adj_list_choose_edge_pmap_helper<edge_all_t> {

  2700       typedef adj_list_all_edge_pmap type;

  2701     };

  2702     template <class Tag, class Graph, class Property>

  2703     struct adj_list_choose_edge_pmap {

  2704       typedef typename adj_list_choose_edge_pmap_helper<Tag>::type Helper;

  2705       typedef typename Helper::template bind_<Graph,Property,Tag> Bind;

  2706       typedef typename Bind::type type;

  2707       typedef typename Bind::const_type const_type;

  2708     };

  2709     struct adj_list_edge_property_selector {

  2710       template <class Graph, class Property, class Tag>

  2711       struct bind_ {

  2712         typedef adj_list_choose_edge_pmap<Tag,Graph,Property> Choice;

  2713         typedef typename Choice::type type;

  2714         typedef typename Choice::const_type const_type;

  2715       };

  2716     };

  2717   } // namespace detail

  2719   template <>

  2720   struct edge_property_selector<adj_list_tag> {

  2721     typedef detail::adj_list_edge_property_selector type;

  2722   };

  2723   template <>

  2724   struct edge_property_selector<vec_adj_list_tag> {

  2725     typedef detail::adj_list_edge_property_selector type;

  2726   };

  2728   // Vertex Property Maps

  2730   struct adj_list_vertex_property_selector {

  2731     template <class Graph, class Property, class Tag>

  2732     struct bind_ {

  2733       typedef detail::adj_list_choose_vertex_pa<Tag,Graph,Property> Choice;

  2734       typedef typename Choice::type type;

  2735       typedef typename Choice::const_type const_type;

  2736     };

  2737   };

  2738   template <>

  2739   struct vertex_property_selector<adj_list_tag> {

  2740     typedef adj_list_vertex_property_selector type;

  2741   };

  2743   struct vec_adj_list_vertex_property_selector {

  2744     template <class Graph, class Property, class Tag>

  2745     struct bind_ {

  2746       typedef detail::vec_adj_list_choose_vertex_pa<Tag,Graph,Property> Choice;

  2747       typedef typename Choice::type type;

  2748       typedef typename Choice::const_type const_type;

  2749     };

  2750   };

  2751   template <>

  2752   struct vertex_property_selector<vec_adj_list_tag> {

  2753     typedef vec_adj_list_vertex_property_selector type;

  2754   };

  2756 } // namespace boost

  2758 #if !defined(BOOST_NO_HASH) && !defined(BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION)

  2759 namespace BOOST_STD_EXTENSION_NAMESPACE {

  2761   #if BOOST_WORKAROUND( _STLPORT_VERSION, >= 0x500 )

  2762   // STLport 5 already defines a hash<void*> specialization.

  2763   #else

  2764   template <>

  2765   struct hash< void* > // Need this when vertex_descriptor=void*

  2766   {

  2767     std::size_t

  2768     operator()(void* v) const { return (std::size_t)v; }

  2769   };

  2770   #endif

  2772   template <typename V>

  2773   struct hash< boost::detail::stored_edge<V> >

  2774   {

  2775     std::size_t

  2776     operator()(const boost::detail::stored_edge<V>& e) const

  2777     {

  2778       return hash<V>()(e.m_target);

  2779     }

  2780   };

  2782   template <typename V, typename P>

  2783   struct hash< boost::detail::stored_edge_property <V,P> >

  2784   {

  2785     std::size_t

  2786     operator()(const boost::detail::stored_edge_property<V,P>& e) const

  2787     {

  2788       return hash<V>()(e.m_target);

  2789     }

  2790   };

  2792   template <typename V, typename I, typename P>

  2793   struct hash< boost::detail::stored_edge_iter<V,I, P> >

  2794   {

  2795     std::size_t

  2796     operator()(const boost::detail::stored_edge_iter<V,I,P>& e) const

  2797     {

  2798       return hash<V>()(e.m_target);

  2799     }

  2800   };

  2802 }

  2803 #endif

  2806 #undef stored_edge

  2807 #undef stored_edge_property

  2808 #undef stored_edge_iter

  2810 #endif // BOOST_GRAPH_DETAIL_DETAIL_ADJACENCY_LIST_CCT

  2812 /*

  2813   Implementation Notes:

  2815   Many of the public interface functions in this file would have been

  2816   more conveniently implemented as inline friend functions.

  2817   However there are a few compiler bugs that make that approach

  2818   non-portable.

  2820   1. g++ inline friend in namespace bug

  2821   2. g++ using clause doesn't work with inline friends

  2822   3. VC++ doesn't have Koenig lookup

  2824   For these reasons, the functions were all written as non-inline free

  2825   functions, and static cast was used to convert from the helper

  2826   class to the adjacency_list derived class.

  2828   Looking back, it might have been better to write out all functions

  2829   in terms of the adjacency_list, and then use a tag to dispatch

  2830   to the various helpers instead of using inheritance.

  2832  */

author	William Roberts <williamr@symbian.org>
	Wed, 31 Mar 2010 12:33:34 +0100
branch	Symbian3
changeset 4	837f303aceeb
permissions	-rw-r--r--