epoc32/include/stdapis/boost/graph/detail/adjacency_list.hpp
author William Roberts <williamr@symbian.org>
Tue, 16 Mar 2010 16:12:26 +0000
branchSymbian2
changeset 2 2fe1408b6811
permissions -rw-r--r--
Final list of Symbian^2 public API header files
williamr@2
     1
// -*- c++ -*-
williamr@2
     2
//=======================================================================
williamr@2
     3
// Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
williamr@2
     4
// Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek
williamr@2
     5
//
williamr@2
     6
// Distributed under the Boost Software License, Version 1.0. (See
williamr@2
     7
// accompanying file LICENSE_1_0.txt or copy at
williamr@2
     8
// http://www.boost.org/LICENSE_1_0.txt)
williamr@2
     9
//=======================================================================
williamr@2
    10
williamr@2
    11
#ifndef BOOST_GRAPH_DETAIL_ADJACENCY_LIST_HPP
williamr@2
    12
#define BOOST_GRAPH_DETAIL_ADJACENCY_LIST_HPP
williamr@2
    13
williamr@2
    14
#include <map> // for vertex_map in copy_impl
williamr@2
    15
#include <boost/config.hpp>
williamr@2
    16
#include <boost/detail/workaround.hpp>
williamr@2
    17
#include <boost/operators.hpp>
williamr@2
    18
#include <boost/property_map.hpp>
williamr@2
    19
#include <boost/pending/integer_range.hpp>
williamr@2
    20
#include <boost/graph/graph_traits.hpp>
williamr@2
    21
#include <memory>
williamr@2
    22
#include <algorithm>
williamr@2
    23
#include <boost/limits.hpp>
williamr@2
    24
williamr@2
    25
#include <boost/iterator/iterator_adaptor.hpp>
williamr@2
    26
williamr@2
    27
#include <boost/pending/ct_if.hpp>
williamr@2
    28
#include <boost/graph/graph_concepts.hpp>
williamr@2
    29
#include <boost/pending/container_traits.hpp>
williamr@2
    30
#include <boost/graph/detail/adj_list_edge_iterator.hpp>
williamr@2
    31
#include <boost/graph/properties.hpp>
williamr@2
    32
#include <boost/pending/property.hpp>
williamr@2
    33
#include <boost/graph/adjacency_iterator.hpp>
williamr@2
    34
#include <boost/static_assert.hpp>
williamr@2
    35
williamr@2
    36
// Symbol truncation problems with MSVC, trying to shorten names.
williamr@2
    37
#define stored_edge se_
williamr@2
    38
#define stored_edge_property sep_
williamr@2
    39
#define stored_edge_iter sei_
williamr@2
    40
williamr@2
    41
/*
williamr@2
    42
  Outline for this file:
williamr@2
    43
williamr@2
    44
  out_edge_iterator and in_edge_iterator implementation
williamr@2
    45
  edge_iterator for undirected graph
williamr@2
    46
  stored edge types (these object live in the out-edge/in-edge lists)
williamr@2
    47
  directed edges helper class
williamr@2
    48
  directed graph helper class
williamr@2
    49
  undirected graph helper class
williamr@2
    50
  bidirectional graph helper class
williamr@2
    51
  bidirectional graph helper class (without edge properties)
williamr@2
    52
  bidirectional graph helper class (with edge properties)
williamr@2
    53
  adjacency_list helper class
williamr@2
    54
  adj_list_impl class
williamr@2
    55
  vec_adj_list_impl class
williamr@2
    56
  adj_list_gen class
williamr@2
    57
  vertex property map
williamr@2
    58
  edge property map
williamr@2
    59
williamr@2
    60
williamr@2
    61
  Note: it would be nice to merge some of the undirected and
williamr@2
    62
  bidirectional code... it is awful similar.
williamr@2
    63
 */
williamr@2
    64
williamr@2
    65
williamr@2
    66
namespace boost {
williamr@2
    67
williamr@2
    68
  namespace detail {
williamr@2
    69
williamr@2
    70
    template <typename DirectedS>
williamr@2
    71
    struct directed_category_traits {
williamr@2
    72
      typedef directed_tag directed_category;
williamr@2
    73
    };
williamr@2
    74
williamr@2
    75
    template <>
williamr@2
    76
    struct directed_category_traits<directedS> {
williamr@2
    77
      typedef directed_tag directed_category;
williamr@2
    78
    };
williamr@2
    79
    template <>
williamr@2
    80
    struct directed_category_traits<undirectedS> {
williamr@2
    81
      typedef undirected_tag directed_category;
williamr@2
    82
    };
williamr@2
    83
    template <>
williamr@2
    84
    struct directed_category_traits<bidirectionalS> {
williamr@2
    85
      typedef bidirectional_tag directed_category;
williamr@2
    86
    };
williamr@2
    87
williamr@2
    88
    template <class Vertex>
williamr@2
    89
    struct target_is {
williamr@2
    90
      target_is(const Vertex& v) : m_target(v) { }
williamr@2
    91
      template <class StoredEdge>
williamr@2
    92
      bool operator()(const StoredEdge& e) const {
williamr@2
    93
        return e.get_target() == m_target;
williamr@2
    94
      }
williamr@2
    95
      Vertex m_target;
williamr@2
    96
    };
williamr@2
    97
williamr@2
    98
    // O(E/V)
williamr@2
    99
    template <class EdgeList, class vertex_descriptor>
williamr@2
   100
    void erase_from_incidence_list(EdgeList& el, vertex_descriptor v,
williamr@2
   101
                                   allow_parallel_edge_tag)
williamr@2
   102
    {
williamr@2
   103
      boost::graph_detail::erase_if(el, detail::target_is<vertex_descriptor>(v));
williamr@2
   104
    }
williamr@2
   105
    // O(log(E/V))
williamr@2
   106
    template <class EdgeList, class vertex_descriptor>
williamr@2
   107
    void erase_from_incidence_list(EdgeList& el, vertex_descriptor v,
williamr@2
   108
                                   disallow_parallel_edge_tag)
williamr@2
   109
    {
williamr@2
   110
      typedef typename EdgeList::value_type StoredEdge;
williamr@2
   111
      el.erase(StoredEdge(v));
williamr@2
   112
    }
williamr@2
   113
williamr@2
   114
    //=========================================================================
williamr@2
   115
    // Out-Edge and In-Edge Iterator Implementation
williamr@2
   116
williamr@2
   117
    template <class BaseIter, class VertexDescriptor, class EdgeDescriptor, class Difference>
williamr@2
   118
    struct out_edge_iter
williamr@2
   119
      : iterator_adaptor<
williamr@2
   120
            out_edge_iter<BaseIter, VertexDescriptor, EdgeDescriptor, Difference>
williamr@2
   121
          , BaseIter
williamr@2
   122
          , EdgeDescriptor
williamr@2
   123
          , use_default
williamr@2
   124
          , EdgeDescriptor
williamr@2
   125
          , Difference
williamr@2
   126
        >
williamr@2
   127
    {
williamr@2
   128
      typedef iterator_adaptor<
williamr@2
   129
          out_edge_iter<BaseIter, VertexDescriptor, EdgeDescriptor, Difference>
williamr@2
   130
        , BaseIter
williamr@2
   131
        , EdgeDescriptor
williamr@2
   132
        , use_default
williamr@2
   133
        , EdgeDescriptor
williamr@2
   134
        , Difference
williamr@2
   135
      > super_t;
williamr@2
   136
        
williamr@2
   137
      inline out_edge_iter() { }
williamr@2
   138
        inline out_edge_iter(const BaseIter& i, const VertexDescriptor& src)
williamr@2
   139
          : super_t(i), m_src(src) { }
williamr@2
   140
williamr@2
   141
      inline EdgeDescriptor
williamr@2
   142
      dereference() const
williamr@2
   143
      {
williamr@2
   144
        return EdgeDescriptor(m_src, (*this->base()).get_target(), 
williamr@2
   145
                              &(*this->base()).get_property());
williamr@2
   146
      }
williamr@2
   147
      VertexDescriptor m_src;
williamr@2
   148
    };
williamr@2
   149
  
williamr@2
   150
    template <class BaseIter, class VertexDescriptor, class EdgeDescriptor, class Difference>
williamr@2
   151
    struct in_edge_iter
williamr@2
   152
      : iterator_adaptor<
williamr@2
   153
            in_edge_iter<BaseIter, VertexDescriptor, EdgeDescriptor, Difference>
williamr@2
   154
          , BaseIter
williamr@2
   155
          , EdgeDescriptor
williamr@2
   156
          , use_default
williamr@2
   157
          , EdgeDescriptor
williamr@2
   158
          , Difference
williamr@2
   159
        >
williamr@2
   160
    {
williamr@2
   161
      typedef iterator_adaptor<
williamr@2
   162
          in_edge_iter<BaseIter, VertexDescriptor, EdgeDescriptor, Difference>
williamr@2
   163
        , BaseIter
williamr@2
   164
        , EdgeDescriptor
williamr@2
   165
        , use_default
williamr@2
   166
        , EdgeDescriptor
williamr@2
   167
        , Difference
williamr@2
   168
      > super_t;
williamr@2
   169
        
williamr@2
   170
      inline in_edge_iter() { }
williamr@2
   171
      inline in_edge_iter(const BaseIter& i, const VertexDescriptor& src) 
williamr@2
   172
        : super_t(i), m_src(src) { }
williamr@2
   173
williamr@2
   174
      inline EdgeDescriptor
williamr@2
   175
      dereference() const
williamr@2
   176
      {
williamr@2
   177
        return EdgeDescriptor((*this->base()).get_target(), m_src,
williamr@2
   178
                              &this->base()->get_property());
williamr@2
   179
      }
williamr@2
   180
      VertexDescriptor m_src;
williamr@2
   181
    };
williamr@2
   182
williamr@2
   183
    //=========================================================================
williamr@2
   184
    // Undirected Edge Iterator Implementation
williamr@2
   185
williamr@2
   186
    template <class EdgeIter, class EdgeDescriptor, class Difference>
williamr@2
   187
    struct undirected_edge_iter
williamr@2
   188
      : iterator_adaptor<
williamr@2
   189
            undirected_edge_iter<EdgeIter, EdgeDescriptor, Difference>
williamr@2
   190
          , EdgeIter
williamr@2
   191
          , EdgeDescriptor
williamr@2
   192
          , use_default
williamr@2
   193
          , EdgeDescriptor
williamr@2
   194
          , Difference
williamr@2
   195
        >
williamr@2
   196
    {
williamr@2
   197
      typedef iterator_adaptor<
williamr@2
   198
          undirected_edge_iter<EdgeIter, EdgeDescriptor, Difference>
williamr@2
   199
        , EdgeIter
williamr@2
   200
        , EdgeDescriptor
williamr@2
   201
        , use_default
williamr@2
   202
        , EdgeDescriptor
williamr@2
   203
        , Difference
williamr@2
   204
      > super_t;
williamr@2
   205
williamr@2
   206
      undirected_edge_iter() {}
williamr@2
   207
        
williamr@2
   208
      explicit undirected_edge_iter(EdgeIter i)
williamr@2
   209
          : super_t(i) {}
williamr@2
   210
        
williamr@2
   211
      inline EdgeDescriptor
williamr@2
   212
      dereference() const {
williamr@2
   213
        return EdgeDescriptor(
williamr@2
   214
            (*this->base()).m_source
williamr@2
   215
          , (*this->base()).m_target
williamr@2
   216
          , &this->base()->get_property());
williamr@2
   217
      }
williamr@2
   218
    };
williamr@2
   219
williamr@2
   220
    //=========================================================================
williamr@2
   221
    // Edge Storage Types (stored in the out-edge/in-edge lists)
williamr@2
   222
williamr@2
   223
    template <class Vertex>
williamr@2
   224
    class stored_edge
williamr@2
   225
      : public boost::equality_comparable1< stored_edge<Vertex>,
williamr@2
   226
        boost::less_than_comparable1< stored_edge<Vertex> > >
williamr@2
   227
    {
williamr@2
   228
    public:
williamr@2
   229
      typedef no_property property_type;
williamr@2
   230
      inline stored_edge() { }
williamr@2
   231
      inline stored_edge(Vertex target, const no_property& = no_property())
williamr@2
   232
        : m_target(target) { }
williamr@2
   233
      // Need to write this explicitly so stored_edge_property can
williamr@2
   234
      // invoke Base::operator= (at least, for SGI MIPSPro compiler)
williamr@2
   235
      inline stored_edge& operator=(const stored_edge& x) {
williamr@2
   236
        m_target = x.m_target;
williamr@2
   237
        return *this;
williamr@2
   238
      }
williamr@2
   239
      inline Vertex& get_target() const { return m_target; }
williamr@2
   240
      inline const no_property& get_property() const { return s_prop; }
williamr@2
   241
      inline bool operator==(const stored_edge& x) const
williamr@2
   242
        { return m_target == x.get_target(); }
williamr@2
   243
      inline bool operator<(const stored_edge& x) const
williamr@2
   244
        { return m_target < x.get_target(); }
williamr@2
   245
      //protected: need to add hash<> as a friend
williamr@2
   246
      static no_property s_prop;
williamr@2
   247
      // Sometimes target not used as key in the set, and in that case
williamr@2
   248
      // it is ok to change the target.
williamr@2
   249
      mutable Vertex m_target;
williamr@2
   250
    };
williamr@2
   251
    template <class Vertex>
williamr@2
   252
    no_property stored_edge<Vertex>::s_prop;
williamr@2
   253
williamr@2
   254
    template <class Vertex, class Property>
williamr@2
   255
    class stored_edge_property : public stored_edge<Vertex> {
williamr@2
   256
      typedef stored_edge_property self;
williamr@2
   257
      typedef stored_edge<Vertex> Base;
williamr@2
   258
    public:
williamr@2
   259
      typedef Property property_type;
williamr@2
   260
      inline stored_edge_property() { }
williamr@2
   261
      inline stored_edge_property(Vertex target,
williamr@2
   262
                                  const Property& p = Property())
williamr@2
   263
        : stored_edge<Vertex>(target), m_property(new Property(p)) { }
williamr@2
   264
      stored_edge_property(const self& x) 
williamr@2
   265
        : Base(x), m_property(const_cast<self&>(x).m_property) { }
williamr@2
   266
      self& operator=(const self& x) {
williamr@2
   267
        Base::operator=(x);
williamr@2
   268
        m_property = const_cast<self&>(x).m_property; 
williamr@2
   269
        return *this;
williamr@2
   270
      }
williamr@2
   271
      inline Property& get_property() { return *m_property; }
williamr@2
   272
      inline const Property& get_property() const { return *m_property; }
williamr@2
   273
    protected:
williamr@2
   274
      // Holding the property by-value causes edge-descriptor
williamr@2
   275
      // invalidation for add_edge() with EdgeList=vecS. Instead we
williamr@2
   276
      // hold a pointer to the property. std::auto_ptr is not
williamr@2
   277
      // a perfect fit for the job, but it is darn close.
williamr@2
   278
      std::auto_ptr<Property> m_property;
williamr@2
   279
    };
williamr@2
   280
williamr@2
   281
williamr@2
   282
    template <class Vertex, class Iter, class Property>
williamr@2
   283
    class stored_edge_iter
williamr@2
   284
      : public stored_edge<Vertex>
williamr@2
   285
    {
williamr@2
   286
    public:
williamr@2
   287
      typedef Property property_type;
williamr@2
   288
      inline stored_edge_iter() { }
williamr@2
   289
      inline stored_edge_iter(Vertex v)
williamr@2
   290
        : stored_edge<Vertex>(v) { }
williamr@2
   291
      inline stored_edge_iter(Vertex v, Iter i, void* = 0)
williamr@2
   292
        : stored_edge<Vertex>(v), m_iter(i) { }
williamr@2
   293
      inline Property& get_property() { return m_iter->get_property(); }
williamr@2
   294
      inline const Property& get_property() const { 
williamr@2
   295
        return m_iter->get_property();
williamr@2
   296
      }
williamr@2
   297
      inline Iter get_iter() const { return m_iter; }
williamr@2
   298
    protected:
williamr@2
   299
      Iter m_iter;
williamr@2
   300
    };
williamr@2
   301
williamr@2
   302
    // For when the EdgeList is a std::vector.
williamr@2
   303
    // Want to make the iterator stable, so use an offset
williamr@2
   304
    // instead of an iterator into a std::vector
williamr@2
   305
    template <class Vertex, class EdgeVec, class Property>
williamr@2
   306
    class stored_ra_edge_iter
williamr@2
   307
      : public stored_edge<Vertex>
williamr@2
   308
    {
williamr@2
   309
      typedef typename EdgeVec::iterator Iter;
williamr@2
   310
    public:
williamr@2
   311
      typedef Property property_type;
williamr@2
   312
      inline stored_ra_edge_iter() { }
williamr@2
   313
      inline stored_ra_edge_iter(Vertex v, Iter i = Iter(), 
williamr@2
   314
                                 EdgeVec* edge_vec = 0)
williamr@2
   315
        : stored_edge<Vertex>(v), m_i(i - edge_vec->begin()), m_vec(edge_vec){ }
williamr@2
   316
      inline Property& get_property() { return (*m_vec)[m_i].get_property(); }
williamr@2
   317
      inline const Property& get_property() const { 
williamr@2
   318
        return (*m_vec)[m_i].get_property();
williamr@2
   319
      }
williamr@2
   320
      inline Iter get_iter() const { return m_vec->begin() + m_i; }
williamr@2
   321
    protected:
williamr@2
   322
      std::size_t m_i;
williamr@2
   323
      EdgeVec* m_vec;
williamr@2
   324
    };
williamr@2
   325
williamr@2
   326
  } // namespace detail
williamr@2
   327
    
williamr@2
   328
  template <class Tag, class Vertex, class Property>
williamr@2
   329
  const typename property_value<Property,Tag>::type&
williamr@2
   330
  get(Tag property_tag,
williamr@2
   331
      const detail::stored_edge_property<Vertex, Property>& e)
williamr@2
   332
  {
williamr@2
   333
    return get_property_value(e.get_property(), property_tag);
williamr@2
   334
  }
williamr@2
   335
williamr@2
   336
  template <class Tag, class Vertex, class Iter, class Property>
williamr@2
   337
  const typename property_value<Property,Tag>::type&
williamr@2
   338
  get(Tag property_tag,
williamr@2
   339
      const detail::stored_edge_iter<Vertex, Iter, Property>& e)
williamr@2
   340
  {
williamr@2
   341
    return get_property_value(e.get_property(), property_tag);
williamr@2
   342
  }
williamr@2
   343
williamr@2
   344
  template <class Tag, class Vertex, class EdgeVec, class Property>
williamr@2
   345
  const typename property_value<Property,Tag>::type&
williamr@2
   346
  get(Tag property_tag,
williamr@2
   347
      const detail::stored_ra_edge_iter<Vertex, EdgeVec, Property>& e)
williamr@2
   348
  {
williamr@2
   349
    return get_property_value(e.get_property(), property_tag);
williamr@2
   350
  }
williamr@2
   351
    
williamr@2
   352
    //=========================================================================
williamr@2
   353
    // Directed Edges Helper Class
williamr@2
   354
williamr@2
   355
    namespace detail {
williamr@2
   356
williamr@2
   357
      // O(E/V)
williamr@2
   358
      template <class edge_descriptor, class EdgeList, class StoredProperty>
williamr@2
   359
      inline void
williamr@2
   360
      remove_directed_edge_dispatch(edge_descriptor, EdgeList& el,
williamr@2
   361
                                    StoredProperty& p)
williamr@2
   362
      {
williamr@2
   363
        for (typename EdgeList::iterator i = el.begin();
williamr@2
   364
             i != el.end(); ++i)
williamr@2
   365
          if (&(*i).get_property() == &p) {
williamr@2
   366
            el.erase(i);
williamr@2
   367
            return;
williamr@2
   368
          }
williamr@2
   369
      }
williamr@2
   370
williamr@2
   371
      template <class incidence_iterator, class EdgeList, class Predicate>
williamr@2
   372
      inline void
williamr@2
   373
      remove_directed_edge_if_dispatch(incidence_iterator first,
williamr@2
   374
                                       incidence_iterator last, 
williamr@2
   375
                                       EdgeList& el, Predicate pred,
williamr@2
   376
                                       boost::allow_parallel_edge_tag)
williamr@2
   377
      {
williamr@2
   378
        // remove_if
williamr@2
   379
        while (first != last && !pred(*first))
williamr@2
   380
          ++first;
williamr@2
   381
        incidence_iterator i = first;
williamr@2
   382
        if (first != last)
williamr@2
   383
          for (; i != last; ++i)
williamr@2
   384
            if (!pred(*i)) {
williamr@2
   385
              *first.base() = *i.base();
williamr@2
   386
              ++first;
williamr@2
   387
            }
williamr@2
   388
        el.erase(first.base(), el.end());
williamr@2
   389
      }
williamr@2
   390
      template <class incidence_iterator, class EdgeList, class Predicate>
williamr@2
   391
      inline void
williamr@2
   392
      remove_directed_edge_if_dispatch(incidence_iterator first,
williamr@2
   393
                                       incidence_iterator last, 
williamr@2
   394
                                       EdgeList& el, 
williamr@2
   395
                                       Predicate pred,
williamr@2
   396
                                       boost::disallow_parallel_edge_tag)
williamr@2
   397
      {
williamr@2
   398
        for (incidence_iterator next = first;
williamr@2
   399
             first != last; first = next) {
williamr@2
   400
          ++next;
williamr@2
   401
          if (pred(*first))
williamr@2
   402
            el.erase( first.base() );
williamr@2
   403
        }
williamr@2
   404
      }
williamr@2
   405
williamr@2
   406
      template <class PropT, class Graph, class incidence_iterator, 
williamr@2
   407
                class EdgeList, class Predicate>
williamr@2
   408
      inline void
williamr@2
   409
      undirected_remove_out_edge_if_dispatch(Graph& g, 
williamr@2
   410
                                             incidence_iterator first,
williamr@2
   411
                                             incidence_iterator last, 
williamr@2
   412
                                             EdgeList& el, Predicate pred,
williamr@2
   413
                                             boost::allow_parallel_edge_tag)
williamr@2
   414
      {
williamr@2
   415
        typedef typename Graph::global_edgelist_selector EdgeListS;
williamr@2
   416
        BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
williamr@2
   417
williamr@2
   418
        // remove_if
williamr@2
   419
        while (first != last && !pred(*first))
williamr@2
   420
          ++first;
williamr@2
   421
        incidence_iterator i = first;
williamr@2
   422
        bool self_loop_removed = false;
williamr@2
   423
        if (first != last)
williamr@2
   424
          for (; i != last; ++i) {
williamr@2
   425
            if (self_loop_removed) {
williamr@2
   426
              /* With self loops, the descriptor will show up
williamr@2
   427
               * twice. The first time it will be removed, and now it
williamr@2
   428
               * will be skipped.
williamr@2
   429
               */
williamr@2
   430
              self_loop_removed = false;
williamr@2
   431
            }
williamr@2
   432
            else if (!pred(*i)) {
williamr@2
   433
              *first.base() = *i.base();
williamr@2
   434
              ++first;
williamr@2
   435
            } else {
williamr@2
   436
              if (source(*i, g) == target(*i, g)) self_loop_removed = true;
williamr@2
   437
              else {
williamr@2
   438
                // Remove the edge from the target
williamr@2
   439
                detail::remove_directed_edge_dispatch
williamr@2
   440
                  (*i, 
williamr@2
   441
                   g.out_edge_list(target(*i, g)), 
williamr@2
   442
                   *(PropT*)(*i).get_property());
williamr@2
   443
              }
williamr@2
   444
williamr@2
   445
              // Erase the edge property
williamr@2
   446
              g.m_edges.erase( (*i.base()).get_iter() );
williamr@2
   447
            }
williamr@2
   448
          }
williamr@2
   449
        el.erase(first.base(), el.end());
williamr@2
   450
      }
williamr@2
   451
      template <class PropT, class Graph, class incidence_iterator, 
williamr@2
   452
                class EdgeList, class Predicate>
williamr@2
   453
      inline void
williamr@2
   454
      undirected_remove_out_edge_if_dispatch(Graph& g, 
williamr@2
   455
                                             incidence_iterator first,
williamr@2
   456
                                             incidence_iterator last, 
williamr@2
   457
                                             EdgeList& el, 
williamr@2
   458
                                             Predicate pred,
williamr@2
   459
                                             boost::disallow_parallel_edge_tag)
williamr@2
   460
      {
williamr@2
   461
        typedef typename Graph::global_edgelist_selector EdgeListS;
williamr@2
   462
        BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
williamr@2
   463
williamr@2
   464
        for (incidence_iterator next = first;
williamr@2
   465
             first != last; first = next) {
williamr@2
   466
          ++next;
williamr@2
   467
          if (pred(*first)) {
williamr@2
   468
            if (source(*first, g) != target(*first, g)) {
williamr@2
   469
              // Remove the edge from the target
williamr@2
   470
              detail::remove_directed_edge_dispatch
williamr@2
   471
                (*first, 
williamr@2
   472
                 g.out_edge_list(target(*first, g)), 
williamr@2
   473
                 *(PropT*)(*first).get_property());
williamr@2
   474
            }
williamr@2
   475
williamr@2
   476
            // Erase the edge property
williamr@2
   477
            g.m_edges.erase( (*first.base()).get_iter() );
williamr@2
   478
williamr@2
   479
            // Erase the edge in the source
williamr@2
   480
            el.erase( first.base() );
williamr@2
   481
          }
williamr@2
   482
        }
williamr@2
   483
      }
williamr@2
   484
williamr@2
   485
      // O(E/V)
williamr@2
   486
      template <class edge_descriptor, class EdgeList, class StoredProperty>
williamr@2
   487
      inline void
williamr@2
   488
      remove_directed_edge_dispatch(edge_descriptor e, EdgeList& el,
williamr@2
   489
                                    no_property&)
williamr@2
   490
      {
williamr@2
   491
        for (typename EdgeList::iterator i = el.begin();
williamr@2
   492
             i != el.end(); ++i)
williamr@2
   493
          if ((*i).get_target() == e.m_target) {
williamr@2
   494
            el.erase(i);
williamr@2
   495
            return;
williamr@2
   496
          }
williamr@2
   497
      }
williamr@2
   498
williamr@2
   499
    } // namespace detail
williamr@2
   500
williamr@2
   501
    template <class Config>
williamr@2
   502
    struct directed_edges_helper {
williamr@2
   503
williamr@2
   504
      // Placement of these overloaded remove_edge() functions
williamr@2
   505
      // inside the class avoids a VC++ bug.
williamr@2
   506
      
williamr@2
   507
      // O(E/V)
williamr@2
   508
      inline void
williamr@2
   509
      remove_edge(typename Config::edge_descriptor e)
williamr@2
   510
      {
williamr@2
   511
        typedef typename Config::graph_type graph_type;
williamr@2
   512
        graph_type& g = static_cast<graph_type&>(*this);
williamr@2
   513
        typename Config::OutEdgeList& el = g.out_edge_list(source(e, g));
williamr@2
   514
        typedef typename Config::OutEdgeList::value_type::property_type PType;
williamr@2
   515
        detail::remove_directed_edge_dispatch(e, el,
williamr@2
   516
                                              *(PType*)e.get_property());
williamr@2
   517
      }
williamr@2
   518
williamr@2
   519
      // O(1)
williamr@2
   520
      inline void
williamr@2
   521
      remove_edge(typename Config::out_edge_iterator iter)
williamr@2
   522
      {
williamr@2
   523
        typedef typename Config::graph_type graph_type;
williamr@2
   524
        graph_type& g = static_cast<graph_type&>(*this);
williamr@2
   525
        typename Config::edge_descriptor e = *iter;
williamr@2
   526
        typename Config::OutEdgeList& el = g.out_edge_list(source(e, g));
williamr@2
   527
        el.erase(iter.base());
williamr@2
   528
      }
williamr@2
   529
williamr@2
   530
    };
williamr@2
   531
williamr@2
   532
    // O(1)
williamr@2
   533
    template <class Config>
williamr@2
   534
    inline std::pair<typename Config::edge_iterator, 
williamr@2
   535
                     typename Config::edge_iterator>
williamr@2
   536
    edges(const directed_edges_helper<Config>& g_)
williamr@2
   537
    {
williamr@2
   538
      typedef typename Config::graph_type graph_type;
williamr@2
   539
      typedef typename Config::edge_iterator edge_iterator;
williamr@2
   540
      const graph_type& cg = static_cast<const graph_type&>(g_);
williamr@2
   541
      graph_type& g = const_cast<graph_type&>(cg);
williamr@2
   542
      return std::make_pair( edge_iterator(g.vertex_set().begin(), 
williamr@2
   543
                                           g.vertex_set().begin(), 
williamr@2
   544
                                           g.vertex_set().end(), g),
williamr@2
   545
                             edge_iterator(g.vertex_set().begin(),
williamr@2
   546
                                           g.vertex_set().end(),
williamr@2
   547
                                           g.vertex_set().end(), g) );
williamr@2
   548
    }
williamr@2
   549
williamr@2
   550
    //=========================================================================
williamr@2
   551
    // Directed Graph Helper Class
williamr@2
   552
williamr@2
   553
    struct adj_list_dir_traversal_tag :
williamr@2
   554
      public virtual vertex_list_graph_tag,
williamr@2
   555
      public virtual incidence_graph_tag,
williamr@2
   556
      public virtual adjacency_graph_tag,
williamr@2
   557
      public virtual edge_list_graph_tag { };
williamr@2
   558
williamr@2
   559
    template <class Config>
williamr@2
   560
    struct directed_graph_helper
williamr@2
   561
      : public directed_edges_helper<Config> { 
williamr@2
   562
      typedef typename Config::edge_descriptor edge_descriptor;
williamr@2
   563
      typedef adj_list_dir_traversal_tag traversal_category;
williamr@2
   564
    };
williamr@2
   565
williamr@2
   566
    // O(E/V)
williamr@2
   567
    template <class Config>
williamr@2
   568
    inline void
williamr@2
   569
    remove_edge(typename Config::vertex_descriptor u,
williamr@2
   570
                typename Config::vertex_descriptor v,
williamr@2
   571
                directed_graph_helper<Config>& g_)
williamr@2
   572
    {
williamr@2
   573
      typedef typename Config::graph_type graph_type;
williamr@2
   574
      typedef typename Config::edge_parallel_category Cat;
williamr@2
   575
      graph_type& g = static_cast<graph_type&>(g_);
williamr@2
   576
      detail::erase_from_incidence_list(g.out_edge_list(u), v, Cat());
williamr@2
   577
    }
williamr@2
   578
williamr@2
   579
    template <class Config, class Predicate>
williamr@2
   580
    inline void
williamr@2
   581
    remove_out_edge_if(typename Config::vertex_descriptor u, Predicate pred,
williamr@2
   582
                       directed_graph_helper<Config>& g_)
williamr@2
   583
    {
williamr@2
   584
      typedef typename Config::graph_type graph_type;
williamr@2
   585
      graph_type& g = static_cast<graph_type&>(g_);
williamr@2
   586
      typename Config::out_edge_iterator first, last;
williamr@2
   587
      tie(first, last) = out_edges(u, g);
williamr@2
   588
      typedef typename Config::edge_parallel_category edge_parallel_category;
williamr@2
   589
      detail::remove_directed_edge_if_dispatch
williamr@2
   590
        (first, last, g.out_edge_list(u), pred, edge_parallel_category());
williamr@2
   591
    }
williamr@2
   592
williamr@2
   593
    template <class Config, class Predicate>
williamr@2
   594
    inline void
williamr@2
   595
    remove_edge_if(Predicate pred, directed_graph_helper<Config>& g_)
williamr@2
   596
    {
williamr@2
   597
      typedef typename Config::graph_type graph_type;
williamr@2
   598
      graph_type& g = static_cast<graph_type&>(g_);
williamr@2
   599
williamr@2
   600
      typename Config::vertex_iterator vi, vi_end;
williamr@2
   601
      for (tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi)
williamr@2
   602
        remove_out_edge_if(*vi, pred, g);
williamr@2
   603
    }    
williamr@2
   604
williamr@2
   605
    template <class EdgeOrIter, class Config>
williamr@2
   606
    inline void
williamr@2
   607
    remove_edge(EdgeOrIter e_or_iter, directed_graph_helper<Config>& g_)
williamr@2
   608
    {
williamr@2
   609
      g_.remove_edge(e_or_iter);
williamr@2
   610
    }
williamr@2
   611
williamr@2
   612
    // O(V + E) for allow_parallel_edges
williamr@2
   613
    // O(V * log(E/V)) for disallow_parallel_edges
williamr@2
   614
    template <class Config>
williamr@2
   615
    inline void 
williamr@2
   616
    clear_vertex(typename Config::vertex_descriptor u,
williamr@2
   617
                 directed_graph_helper<Config>& g_)
williamr@2
   618
    {
williamr@2
   619
      typedef typename Config::graph_type graph_type;
williamr@2
   620
      typedef typename Config::edge_parallel_category Cat;
williamr@2
   621
      graph_type& g = static_cast<graph_type&>(g_);
williamr@2
   622
      typename Config::vertex_iterator vi, viend;
williamr@2
   623
      for (boost::tie(vi, viend) = vertices(g); vi != viend; ++vi)
williamr@2
   624
        detail::erase_from_incidence_list(g.out_edge_list(*vi), u, Cat());
williamr@2
   625
      g.out_edge_list(u).clear();
williamr@2
   626
      // clear() should be a req of Sequence and AssociativeContainer,
williamr@2
   627
      // or maybe just Container
williamr@2
   628
    }
williamr@2
   629
williamr@2
   630
    template <class Config>
williamr@2
   631
    inline void 
williamr@2
   632
    clear_out_edges(typename Config::vertex_descriptor u,
williamr@2
   633
                    directed_graph_helper<Config>& g_)
williamr@2
   634
    {
williamr@2
   635
      typedef typename Config::graph_type graph_type;
williamr@2
   636
      typedef typename Config::edge_parallel_category Cat;
williamr@2
   637
      graph_type& g = static_cast<graph_type&>(g_);
williamr@2
   638
      g.out_edge_list(u).clear();
williamr@2
   639
      // clear() should be a req of Sequence and AssociativeContainer,
williamr@2
   640
      // or maybe just Container
williamr@2
   641
    }
williamr@2
   642
williamr@2
   643
    // O(V), could do better...
williamr@2
   644
    template <class Config>
williamr@2
   645
    inline typename Config::edges_size_type
williamr@2
   646
    num_edges(const directed_graph_helper<Config>& g_)
williamr@2
   647
    {
williamr@2
   648
      typedef typename Config::graph_type graph_type;
williamr@2
   649
      const graph_type& g = static_cast<const graph_type&>(g_);
williamr@2
   650
      typename Config::edges_size_type num_e = 0;
williamr@2
   651
      typename Config::vertex_iterator vi, vi_end;
williamr@2
   652
      for (boost::tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi)
williamr@2
   653
        num_e += out_degree(*vi, g);
williamr@2
   654
      return num_e;
williamr@2
   655
    }
williamr@2
   656
    // O(1) for allow_parallel_edge_tag
williamr@2
   657
    // O(log(E/V)) for disallow_parallel_edge_tag
williamr@2
   658
    template <class Config>
williamr@2
   659
    inline std::pair<typename directed_graph_helper<Config>::edge_descriptor, bool>
williamr@2
   660
    add_edge(typename Config::vertex_descriptor u, 
williamr@2
   661
             typename Config::vertex_descriptor v,
williamr@2
   662
             const typename Config::edge_property_type& p, 
williamr@2
   663
             directed_graph_helper<Config>& g_)
williamr@2
   664
    {
williamr@2
   665
      typedef typename Config::edge_descriptor edge_descriptor;
williamr@2
   666
      typedef typename Config::graph_type graph_type;
williamr@2
   667
      typedef typename Config::StoredEdge StoredEdge;
williamr@2
   668
      graph_type& g = static_cast<graph_type&>(g_);
williamr@2
   669
      typename Config::OutEdgeList::iterator i; 
williamr@2
   670
      bool inserted;
williamr@2
   671
      boost::tie(i, inserted) = boost::graph_detail::push(g.out_edge_list(u), 
williamr@2
   672
                                            StoredEdge(v, p));
williamr@2
   673
      return std::make_pair(edge_descriptor(u, v, &(*i).get_property()), 
williamr@2
   674
                            inserted);
williamr@2
   675
    }
williamr@2
   676
    // Did not use default argument here because that
williamr@2
   677
    // causes Visual C++ to get confused.
williamr@2
   678
    template <class Config>
williamr@2
   679
    inline std::pair<typename Config::edge_descriptor, bool>
williamr@2
   680
    add_edge(typename Config::vertex_descriptor u, 
williamr@2
   681
             typename Config::vertex_descriptor v,
williamr@2
   682
             directed_graph_helper<Config>& g_)
williamr@2
   683
    {
williamr@2
   684
      typename Config::edge_property_type p;
williamr@2
   685
      return add_edge(u, v, p, g_);
williamr@2
   686
    }
williamr@2
   687
    //=========================================================================
williamr@2
   688
    // Undirected Graph Helper Class
williamr@2
   689
williamr@2
   690
    template <class Config>
williamr@2
   691
    struct undirected_graph_helper;
williamr@2
   692
williamr@2
   693
    struct undir_adj_list_traversal_tag : 
williamr@2
   694
      public virtual vertex_list_graph_tag,
williamr@2
   695
      public virtual incidence_graph_tag,
williamr@2
   696
      public virtual adjacency_graph_tag,
williamr@2
   697
      public virtual edge_list_graph_tag,
williamr@2
   698
      public virtual bidirectional_graph_tag { };
williamr@2
   699
williamr@2
   700
    namespace detail {
williamr@2
   701
williamr@2
   702
      // using class with specialization for dispatch is a VC++ workaround.
williamr@2
   703
      template <class StoredProperty>
williamr@2
   704
      struct remove_undirected_edge_dispatch {
williamr@2
   705
williamr@2
   706
        // O(E/V)
williamr@2
   707
        template <class edge_descriptor, class Config>
williamr@2
   708
        static void
williamr@2
   709
        apply(edge_descriptor e, 
williamr@2
   710
              undirected_graph_helper<Config>& g_, 
williamr@2
   711
              StoredProperty& p)
williamr@2
   712
        {
williamr@2
   713
          typedef typename Config::global_edgelist_selector EdgeListS;
williamr@2
   714
          BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
williamr@2
   715
williamr@2
   716
          typedef typename Config::graph_type graph_type;
williamr@2
   717
          graph_type& g = static_cast<graph_type&>(g_);
williamr@2
   718
          
williamr@2
   719
          typename Config::OutEdgeList& out_el = g.out_edge_list(source(e, g));
williamr@2
   720
          typename Config::OutEdgeList::iterator out_i = out_el.begin();
williamr@2
   721
          for (; out_i != out_el.end(); ++out_i)
williamr@2
   722
            if (&(*out_i).get_property() == &p) {
williamr@2
   723
              out_el.erase(out_i);
williamr@2
   724
              break;
williamr@2
   725
            }
williamr@2
   726
          typename Config::OutEdgeList& in_el = g.out_edge_list(target(e, g));
williamr@2
   727
          typename Config::OutEdgeList::iterator in_i = in_el.begin();
williamr@2
   728
          for (; in_i != in_el.end(); ++in_i)
williamr@2
   729
            if (&(*in_i).get_property() == &p) {
williamr@2
   730
              g.m_edges.erase((*in_i).get_iter());
williamr@2
   731
              in_el.erase(in_i);
williamr@2
   732
              return;
williamr@2
   733
            }
williamr@2
   734
        }
williamr@2
   735
      };
williamr@2
   736
williamr@2
   737
      template <>
williamr@2
   738
      struct remove_undirected_edge_dispatch<no_property> {
williamr@2
   739
        // O(E/V)
williamr@2
   740
        template <class edge_descriptor, class Config>
williamr@2
   741
        static void
williamr@2
   742
        apply(edge_descriptor e,
williamr@2
   743
              undirected_graph_helper<Config>& g_,
williamr@2
   744
              no_property&)
williamr@2
   745
        {
williamr@2
   746
          typedef typename Config::global_edgelist_selector EdgeListS;
williamr@2
   747
          BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
williamr@2
   748
williamr@2
   749
          typedef typename Config::graph_type graph_type;
williamr@2
   750
          graph_type& g = static_cast<graph_type&>(g_);
williamr@2
   751
          no_property* p = (no_property*)e.get_property();
williamr@2
   752
          typename Config::OutEdgeList& out_el = g.out_edge_list(source(e, g));
williamr@2
   753
          typename Config::OutEdgeList::iterator out_i = out_el.begin();
williamr@2
   754
          for (; out_i != out_el.end(); ++out_i)
williamr@2
   755
            if (&(*out_i).get_property() == p) {
williamr@2
   756
              out_el.erase(out_i);
williamr@2
   757
              break;
williamr@2
   758
            }
williamr@2
   759
          typename Config::OutEdgeList& in_el = g.out_edge_list(target(e, g));
williamr@2
   760
          typename Config::OutEdgeList::iterator in_i = in_el.begin();
williamr@2
   761
          for (; in_i != in_el.end(); ++in_i)
williamr@2
   762
            if (&(*in_i).get_property() == p) {
williamr@2
   763
              g.m_edges.erase((*in_i).get_iter());
williamr@2
   764
              in_el.erase(in_i);
williamr@2
   765
              return;
williamr@2
   766
            }
williamr@2
   767
        }
williamr@2
   768
      };
williamr@2
   769
williamr@2
   770
      // O(E/V)
williamr@2
   771
      template <class Graph, class EdgeList, class Vertex>
williamr@2
   772
      inline void
williamr@2
   773
      remove_edge_and_property(Graph& g, EdgeList& el, Vertex v, 
williamr@2
   774
                               boost::allow_parallel_edge_tag cat)
williamr@2
   775
      {
williamr@2
   776
        typedef typename Graph::global_edgelist_selector EdgeListS;
williamr@2
   777
        BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
williamr@2
   778
williamr@2
   779
        typedef typename EdgeList::value_type StoredEdge;
williamr@2
   780
        typename EdgeList::iterator i = el.begin(), end = el.end();
williamr@2
   781
        for (; i != end; ++i)
williamr@2
   782
          if ((*i).get_target() == v)
williamr@2
   783
            g.m_edges.erase((*i).get_iter());
williamr@2
   784
        detail::erase_from_incidence_list(el, v, cat);
williamr@2
   785
      }
williamr@2
   786
      // O(log(E/V))
williamr@2
   787
      template <class Graph, class EdgeList, class Vertex>
williamr@2
   788
      inline void
williamr@2
   789
      remove_edge_and_property(Graph& g, EdgeList& el, Vertex v, 
williamr@2
   790
                               boost::disallow_parallel_edge_tag)
williamr@2
   791
      {
williamr@2
   792
        typedef typename Graph::global_edgelist_selector EdgeListS;
williamr@2
   793
        BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
williamr@2
   794
williamr@2
   795
        typedef typename EdgeList::value_type StoredEdge;
williamr@2
   796
        typename EdgeList::iterator i = el.find(StoredEdge(v)), end = el.end();
williamr@2
   797
        if (i != end) {
williamr@2
   798
          g.m_edges.erase((*i).get_iter());
williamr@2
   799
          el.erase(i);
williamr@2
   800
        }
williamr@2
   801
      }
williamr@2
   802
williamr@2
   803
    } // namespace detail
williamr@2
   804
williamr@2
   805
    template <class Vertex, class EdgeProperty>
williamr@2
   806
    struct list_edge // short name due to VC++ truncation and linker problems
williamr@2
   807
      : public boost::detail::edge_base<boost::undirected_tag, Vertex>
williamr@2
   808
    {
williamr@2
   809
      typedef EdgeProperty property_type;
williamr@2
   810
      typedef boost::detail::edge_base<boost::undirected_tag, Vertex> Base;
williamr@2
   811
      list_edge(Vertex u, Vertex v, const EdgeProperty& p = EdgeProperty())
williamr@2
   812
        : Base(u, v), m_property(p) { }
williamr@2
   813
      EdgeProperty& get_property() { return m_property; }
williamr@2
   814
      const EdgeProperty& get_property() const { return m_property; }
williamr@2
   815
      // the following methods should never be used, but are needed
williamr@2
   816
      // to make SGI MIPSpro C++ happy
williamr@2
   817
      list_edge() { }
williamr@2
   818
      bool operator==(const list_edge&) const { return false; }
williamr@2
   819
      bool operator<(const list_edge&) const { return false; }
williamr@2
   820
      EdgeProperty m_property;
williamr@2
   821
    };
williamr@2
   822
williamr@2
   823
    template <class Config>
williamr@2
   824
    struct undirected_graph_helper {
williamr@2
   825
williamr@2
   826
      typedef undir_adj_list_traversal_tag traversal_category;
williamr@2
   827
williamr@2
   828
      // Placement of these overloaded remove_edge() functions
williamr@2
   829
      // inside the class avoids a VC++ bug.
williamr@2
   830
williamr@2
   831
      // O(E/V)
williamr@2
   832
      inline void
williamr@2
   833
      remove_edge(typename Config::edge_descriptor e)
williamr@2
   834
      {
williamr@2
   835
        typedef typename Config::global_edgelist_selector EdgeListS;
williamr@2
   836
        BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
williamr@2
   837
williamr@2
   838
        typedef typename Config::OutEdgeList::value_type::property_type PType;
williamr@2
   839
        detail::remove_undirected_edge_dispatch<PType>::apply
williamr@2
   840
          (e, *this, *(PType*)e.get_property());
williamr@2
   841
      }
williamr@2
   842
      // O(E/V)
williamr@2
   843
      inline void
williamr@2
   844
      remove_edge(typename Config::out_edge_iterator iter)
williamr@2
   845
      {
williamr@2
   846
        this->remove_edge(*iter);
williamr@2
   847
      }
williamr@2
   848
    };
williamr@2
   849
williamr@2
   850
    // Had to make these non-members to avoid accidental instantiation
williamr@2
   851
    // on SGI MIPSpro C++
williamr@2
   852
    template <class C>
williamr@2
   853
    inline typename C::InEdgeList& 
williamr@2
   854
    in_edge_list(undirected_graph_helper<C>&, 
williamr@2
   855
                 typename C::vertex_descriptor v)
williamr@2
   856
    {
williamr@2
   857
      typename C::stored_vertex* sv = (typename C::stored_vertex*)v;
williamr@2
   858
      return sv->m_out_edges;
williamr@2
   859
    }
williamr@2
   860
    template <class C>
williamr@2
   861
    inline const typename C::InEdgeList& 
williamr@2
   862
    in_edge_list(const undirected_graph_helper<C>&,
williamr@2
   863
                 typename C::vertex_descriptor v) {
williamr@2
   864
      typename C::stored_vertex* sv = (typename C::stored_vertex*)v;
williamr@2
   865
      return sv->m_out_edges;
williamr@2
   866
    }
williamr@2
   867
williamr@2
   868
    // O(E/V)
williamr@2
   869
    template <class EdgeOrIter, class Config>
williamr@2
   870
    inline void
williamr@2
   871
    remove_edge(EdgeOrIter e, undirected_graph_helper<Config>& g_)
williamr@2
   872
    {
williamr@2
   873
      typedef typename Config::global_edgelist_selector EdgeListS;
williamr@2
   874
      BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
williamr@2
   875
williamr@2
   876
      g_.remove_edge(e);
williamr@2
   877
    }
williamr@2
   878
williamr@2
   879
    // O(E/V) or O(log(E/V))
williamr@2
   880
    template <class Config>
williamr@2
   881
    void
williamr@2
   882
    remove_edge(typename Config::vertex_descriptor u, 
williamr@2
   883
                typename Config::vertex_descriptor v, 
williamr@2
   884
                undirected_graph_helper<Config>& g_)
williamr@2
   885
    {
williamr@2
   886
      typedef typename Config::global_edgelist_selector EdgeListS;
williamr@2
   887
      BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
williamr@2
   888
williamr@2
   889
      typedef typename Config::graph_type graph_type;
williamr@2
   890
      graph_type& g = static_cast<graph_type&>(g_);
williamr@2
   891
      typedef typename Config::edge_parallel_category Cat;
williamr@2
   892
      detail::remove_edge_and_property(g, g.out_edge_list(u), v, Cat());
williamr@2
   893
      detail::erase_from_incidence_list(g.out_edge_list(v), u, Cat());
williamr@2
   894
    }
williamr@2
   895
  
williamr@2
   896
    template <class Config, class Predicate>
williamr@2
   897
    void
williamr@2
   898
    remove_out_edge_if(typename Config::vertex_descriptor u, Predicate pred,
williamr@2
   899
                       undirected_graph_helper<Config>& g_)
williamr@2
   900
    {
williamr@2
   901
      typedef typename Config::global_edgelist_selector EdgeListS;
williamr@2
   902
      BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
williamr@2
   903
        
williamr@2
   904
      typedef typename Config::graph_type graph_type;
williamr@2
   905
      typedef typename Config::OutEdgeList::value_type::property_type PropT;
williamr@2
   906
      graph_type& g = static_cast<graph_type&>(g_);
williamr@2
   907
      typename Config::out_edge_iterator first, last;
williamr@2
   908
      tie(first, last) = out_edges(u, g);
williamr@2
   909
      typedef typename Config::edge_parallel_category Cat;
williamr@2
   910
      detail::undirected_remove_out_edge_if_dispatch<PropT>
williamr@2
   911
        (g, first, last, g.out_edge_list(u), pred, Cat());
williamr@2
   912
    }
williamr@2
   913
    template <class Config, class Predicate>
williamr@2
   914
    void
williamr@2
   915
    remove_in_edge_if(typename Config::vertex_descriptor u, Predicate pred,
williamr@2
   916
                      undirected_graph_helper<Config>& g_)
williamr@2
   917
    {
williamr@2
   918
      typedef typename Config::global_edgelist_selector EdgeListS;
williamr@2
   919
      BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
williamr@2
   920
williamr@2
   921
      remove_out_edge_if(u, pred, g_);
williamr@2
   922
    }
williamr@2
   923
williamr@2
   924
    // O(E/V * E) or O(log(E/V) * E)
williamr@2
   925
    template <class Predicate, class Config>
williamr@2
   926
    void
williamr@2
   927
    remove_edge_if(Predicate pred, undirected_graph_helper<Config>& g_)
williamr@2
   928
    {
williamr@2
   929
      typedef typename Config::global_edgelist_selector EdgeListS;
williamr@2
   930
      BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
williamr@2
   931
williamr@2
   932
      typedef typename Config::graph_type graph_type;
williamr@2
   933
      graph_type& g = static_cast<graph_type&>(g_);
williamr@2
   934
      typename Config::edge_iterator ei, ei_end, next;
williamr@2
   935
      tie(ei, ei_end) = edges(g);
williamr@2
   936
      for (next = ei; ei != ei_end; ei = next) {
williamr@2
   937
        ++next;
williamr@2
   938
        if (pred(*ei))
williamr@2
   939
          remove_edge(*ei, g);
williamr@2
   940
      }
williamr@2
   941
    }
williamr@2
   942
williamr@2
   943
    // O(1)
williamr@2
   944
    template <class Config>
williamr@2
   945
    inline std::pair<typename Config::edge_iterator, 
williamr@2
   946
                     typename Config::edge_iterator>
williamr@2
   947
    edges(const undirected_graph_helper<Config>& g_)
williamr@2
   948
    {
williamr@2
   949
      typedef typename Config::graph_type graph_type;
williamr@2
   950
      typedef typename Config::edge_iterator edge_iterator;
williamr@2
   951
      const graph_type& cg = static_cast<const graph_type&>(g_);
williamr@2
   952
      graph_type& g = const_cast<graph_type&>(cg);
williamr@2
   953
      return std::make_pair( edge_iterator(g.m_edges.begin()),
williamr@2
   954
                             edge_iterator(g.m_edges.end()) );
williamr@2
   955
    }
williamr@2
   956
    // O(1)
williamr@2
   957
    template <class Config>
williamr@2
   958
    inline typename Config::edges_size_type
williamr@2
   959
    num_edges(const undirected_graph_helper<Config>& g_) 
williamr@2
   960
    {
williamr@2
   961
      typedef typename Config::graph_type graph_type;
williamr@2
   962
      const graph_type& g = static_cast<const graph_type&>(g_);
williamr@2
   963
      return g.m_edges.size();
williamr@2
   964
    }
williamr@2
   965
    // O(E/V * E/V)
williamr@2
   966
    template <class Config>
williamr@2
   967
    inline void 
williamr@2
   968
    clear_vertex(typename Config::vertex_descriptor u,
williamr@2
   969
                 undirected_graph_helper<Config>& g_)
williamr@2
   970
    {
williamr@2
   971
      typedef typename Config::global_edgelist_selector EdgeListS;
williamr@2
   972
      BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
williamr@2
   973
williamr@2
   974
      typedef typename Config::graph_type graph_type;
williamr@2
   975
      typedef typename Config::edge_parallel_category Cat;
williamr@2
   976
      graph_type& g = static_cast<graph_type&>(g_);
williamr@2
   977
      typename Config::OutEdgeList& el = g.out_edge_list(u);
williamr@2
   978
      typename Config::OutEdgeList::iterator 
williamr@2
   979
        ei = el.begin(), ei_end = el.end();
williamr@2
   980
      for (; ei != ei_end; ++ei) {
williamr@2
   981
        detail::erase_from_incidence_list
williamr@2
   982
          (g.out_edge_list((*ei).get_target()), u, Cat());
williamr@2
   983
        g.m_edges.erase((*ei).get_iter());
williamr@2
   984
      }
williamr@2
   985
      g.out_edge_list(u).clear();
williamr@2
   986
    }
williamr@2
   987
    // O(1) for allow_parallel_edge_tag
williamr@2
   988
    // O(log(E/V)) for disallow_parallel_edge_tag
williamr@2
   989
    template <class Config>
williamr@2
   990
    inline std::pair<typename Config::edge_descriptor, bool>
williamr@2
   991
    add_edge(typename Config::vertex_descriptor u, 
williamr@2
   992
             typename Config::vertex_descriptor v, 
williamr@2
   993
             const typename Config::edge_property_type& p,
williamr@2
   994
             undirected_graph_helper<Config>& g_)
williamr@2
   995
    {
williamr@2
   996
      typedef typename Config::StoredEdge StoredEdge;
williamr@2
   997
      typedef typename Config::edge_descriptor edge_descriptor;
williamr@2
   998
      typedef typename Config::graph_type graph_type;
williamr@2
   999
      graph_type& g = static_cast<graph_type&>(g_);
williamr@2
  1000
williamr@2
  1001
      bool inserted;
williamr@2
  1002
      typename Config::EdgeContainer::value_type e(u, v, p);
williamr@2
  1003
      typename Config::EdgeContainer::iterator p_iter 
williamr@2
  1004
        = graph_detail::push(g.m_edges, e).first;
williamr@2
  1005
williamr@2
  1006
      typename Config::OutEdgeList::iterator i;
williamr@2
  1007
      boost::tie(i, inserted) = boost::graph_detail::push(g.out_edge_list(u), 
williamr@2
  1008
                                    StoredEdge(v, p_iter, &g.m_edges));
williamr@2
  1009
      if (inserted) {
williamr@2
  1010
        boost::graph_detail::push(g.out_edge_list(v), StoredEdge(u, p_iter, &g.m_edges));
williamr@2
  1011
        return std::make_pair(edge_descriptor(u, v, &p_iter->get_property()),
williamr@2
  1012
                              true);
williamr@2
  1013
      } else {
williamr@2
  1014
        g.m_edges.erase(p_iter);
williamr@2
  1015
        return std::make_pair
williamr@2
  1016
          (edge_descriptor(u, v, &i->get_iter()->get_property()), false);
williamr@2
  1017
      }
williamr@2
  1018
    }
williamr@2
  1019
    template <class Config>
williamr@2
  1020
    inline std::pair<typename Config::edge_descriptor, bool>
williamr@2
  1021
    add_edge(typename Config::vertex_descriptor u, 
williamr@2
  1022
             typename Config::vertex_descriptor v, 
williamr@2
  1023
             undirected_graph_helper<Config>& g_)
williamr@2
  1024
    {
williamr@2
  1025
      typename Config::edge_property_type p;
williamr@2
  1026
      return add_edge(u, v, p, g_);
williamr@2
  1027
    }
williamr@2
  1028
williamr@2
  1029
    // O(1)
williamr@2
  1030
    template <class Config>
williamr@2
  1031
    inline typename Config::degree_size_type
williamr@2
  1032
    degree(typename Config::vertex_descriptor u, 
williamr@2
  1033
           const undirected_graph_helper<Config>& g_)
williamr@2
  1034
    {
williamr@2
  1035
      typedef typename Config::graph_type Graph;
williamr@2
  1036
      const Graph& g = static_cast<const Graph&>(g_);
williamr@2
  1037
      return out_degree(u, g);
williamr@2
  1038
    }
williamr@2
  1039
williamr@2
  1040
    template <class Config>
williamr@2
  1041
    inline std::pair<typename Config::in_edge_iterator, 
williamr@2
  1042
                     typename Config::in_edge_iterator>
williamr@2
  1043
    in_edges(typename Config::vertex_descriptor u, 
williamr@2
  1044
             const undirected_graph_helper<Config>& g_)
williamr@2
  1045
    {
williamr@2
  1046
      typedef typename Config::graph_type Graph;
williamr@2
  1047
      const Graph& cg = static_cast<const Graph&>(g_);
williamr@2
  1048
      Graph& g = const_cast<Graph&>(cg);
williamr@2
  1049
      typedef typename Config::in_edge_iterator in_edge_iterator;
williamr@2
  1050
      return
williamr@2
  1051
        std::make_pair(in_edge_iterator(g.out_edge_list(u).begin(), u),
williamr@2
  1052
                       in_edge_iterator(g.out_edge_list(u).end(), u));
williamr@2
  1053
    }
williamr@2
  1054
williamr@2
  1055
    template <class Config>
williamr@2
  1056
    inline typename Config::degree_size_type
williamr@2
  1057
    in_degree(typename Config::vertex_descriptor u,
williamr@2
  1058
              const undirected_graph_helper<Config>& g_)
williamr@2
  1059
    { return degree(u, g_); }
williamr@2
  1060
williamr@2
  1061
    //=========================================================================
williamr@2
  1062
    // Bidirectional Graph Helper Class
williamr@2
  1063
williamr@2
  1064
    struct bidir_adj_list_traversal_tag : 
williamr@2
  1065
      public virtual vertex_list_graph_tag,
williamr@2
  1066
      public virtual incidence_graph_tag,
williamr@2
  1067
      public virtual adjacency_graph_tag,
williamr@2
  1068
      public virtual edge_list_graph_tag,
williamr@2
  1069
      public virtual bidirectional_graph_tag { };
williamr@2
  1070
williamr@2
  1071
    template <class Config>
williamr@2
  1072
    struct bidirectional_graph_helper
williamr@2
  1073
      : public directed_edges_helper<Config> {
williamr@2
  1074
      typedef bidir_adj_list_traversal_tag traversal_category;
williamr@2
  1075
    };
williamr@2
  1076
williamr@2
  1077
    // Had to make these non-members to avoid accidental instantiation
williamr@2
  1078
    // on SGI MIPSpro C++
williamr@2
  1079
    template <class C>
williamr@2
  1080
    inline typename C::InEdgeList& 
williamr@2
  1081
    in_edge_list(bidirectional_graph_helper<C>&, 
williamr@2
  1082
                 typename C::vertex_descriptor v)
williamr@2
  1083
    {
williamr@2
  1084
      typename C::stored_vertex* sv = (typename C::stored_vertex*)v;
williamr@2
  1085
      return sv->m_in_edges;
williamr@2
  1086
    }
williamr@2
  1087
    template <class C>
williamr@2
  1088
    inline const typename C::InEdgeList& 
williamr@2
  1089
    in_edge_list(const bidirectional_graph_helper<C>&,
williamr@2
  1090
                 typename C::vertex_descriptor v) {
williamr@2
  1091
      typename C::stored_vertex* sv = (typename C::stored_vertex*)v;
williamr@2
  1092
      return sv->m_in_edges;
williamr@2
  1093
    }
williamr@2
  1094
williamr@2
  1095
    template <class Predicate, class Config>
williamr@2
  1096
    inline void
williamr@2
  1097
    remove_edge_if(Predicate pred, bidirectional_graph_helper<Config>& g_)
williamr@2
  1098
    {
williamr@2
  1099
      typedef typename Config::global_edgelist_selector EdgeListS;
williamr@2
  1100
      BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
williamr@2
  1101
williamr@2
  1102
      typedef typename Config::graph_type graph_type;
williamr@2
  1103
      graph_type& g = static_cast<graph_type&>(g_);
williamr@2
  1104
      typename Config::edge_iterator ei, ei_end, next;
williamr@2
  1105
      tie(ei, ei_end) = edges(g);
williamr@2
  1106
      for (next = ei; ei != ei_end; ei = next) {
williamr@2
  1107
        ++next;
williamr@2
  1108
        if (pred(*ei))
williamr@2
  1109
          remove_edge(*ei, g);
williamr@2
  1110
      }
williamr@2
  1111
    }
williamr@2
  1112
williamr@2
  1113
    template <class Config>
williamr@2
  1114
    inline std::pair<typename Config::in_edge_iterator, 
williamr@2
  1115
                     typename Config::in_edge_iterator>
williamr@2
  1116
    in_edges(typename Config::vertex_descriptor u, 
williamr@2
  1117
             const bidirectional_graph_helper<Config>& g_)
williamr@2
  1118
    {
williamr@2
  1119
      typedef typename Config::graph_type graph_type;
williamr@2
  1120
      const graph_type& cg = static_cast<const graph_type&>(g_);
williamr@2
  1121
      graph_type& g = const_cast<graph_type&>(cg);
williamr@2
  1122
      typedef typename Config::in_edge_iterator in_edge_iterator;
williamr@2
  1123
      return
williamr@2
  1124
        std::make_pair(in_edge_iterator(in_edge_list(g, u).begin(), u),
williamr@2
  1125
                       in_edge_iterator(in_edge_list(g, u).end(), u));
williamr@2
  1126
    }
williamr@2
  1127
williamr@2
  1128
    // O(1)
williamr@2
  1129
    template <class Config>
williamr@2
  1130
    inline std::pair<typename Config::edge_iterator, 
williamr@2
  1131
                     typename Config::edge_iterator>
williamr@2
  1132
    edges(const bidirectional_graph_helper<Config>& g_)
williamr@2
  1133
    {
williamr@2
  1134
      typedef typename Config::graph_type graph_type;
williamr@2
  1135
      typedef typename Config::edge_iterator edge_iterator;
williamr@2
  1136
      const graph_type& cg = static_cast<const graph_type&>(g_);
williamr@2
  1137
      graph_type& g = const_cast<graph_type&>(cg);
williamr@2
  1138
      return std::make_pair( edge_iterator(g.m_edges.begin()),
williamr@2
  1139
                             edge_iterator(g.m_edges.end()) );
williamr@2
  1140
    }
williamr@2
  1141
williamr@2
  1142
    //=========================================================================
williamr@2
  1143
    // Bidirectional Graph Helper Class (with edge properties)
williamr@2
  1144
williamr@2
  1145
williamr@2
  1146
    template <class Config>
williamr@2
  1147
    struct bidirectional_graph_helper_with_property
williamr@2
  1148
      : public bidirectional_graph_helper<Config>
williamr@2
  1149
    {
williamr@2
  1150
      typedef typename Config::graph_type graph_type;
williamr@2
  1151
      typedef typename Config::out_edge_iterator out_edge_iterator;
williamr@2
  1152
      
williamr@2
  1153
      std::pair<out_edge_iterator, out_edge_iterator>
williamr@2
  1154
      get_parallel_edge_sublist(typename Config::edge_descriptor e,
williamr@2
  1155
                                const graph_type& g,
williamr@2
  1156
                                void*)
williamr@2
  1157
      { return out_edges(source(e, g), g); }
williamr@2
  1158
williamr@2
  1159
      std::pair<out_edge_iterator, out_edge_iterator>
williamr@2
  1160
      get_parallel_edge_sublist(typename Config::edge_descriptor e,
williamr@2
  1161
                                const graph_type& g,
williamr@2
  1162
                                setS*)
williamr@2
  1163
      { return edge_range(source(e, g), target(e, g), g); }
williamr@2
  1164
williamr@2
  1165
      std::pair<out_edge_iterator, out_edge_iterator>
williamr@2
  1166
      get_parallel_edge_sublist(typename Config::edge_descriptor e,
williamr@2
  1167
                                const graph_type& g,
williamr@2
  1168
                                multisetS*)
williamr@2
  1169
      { return edge_range(source(e, g), target(e, g), g); }
williamr@2
  1170
williamr@2
  1171
#if !defined BOOST_NO_HASH
williamr@2
  1172
      std::pair<out_edge_iterator, out_edge_iterator>
williamr@2
  1173
      get_parallel_edge_sublist(typename Config::edge_descriptor e,
williamr@2
  1174
                                const graph_type& g,
williamr@2
  1175
                                hash_setS*)
williamr@2
  1176
      { return edge_range(source(e, g), target(e, g), g); }
williamr@2
  1177
#endif
williamr@2
  1178
williamr@2
  1179
      // Placement of these overloaded remove_edge() functions
williamr@2
  1180
      // inside the class avoids a VC++ bug.
williamr@2
  1181
williamr@2
  1182
      // O(E/V) or O(log(E/V))
williamr@2
  1183
      void
williamr@2
  1184
      remove_edge(typename Config::edge_descriptor e)
williamr@2
  1185
      {
williamr@2
  1186
        typedef typename Config::global_edgelist_selector EdgeListS;
williamr@2
  1187
        BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
williamr@2
  1188
williamr@2
  1189
        graph_type& g = static_cast<graph_type&>(*this);
williamr@2
  1190
williamr@2
  1191
        typedef typename Config::edgelist_selector OutEdgeListS;
williamr@2
  1192
williamr@2
  1193
        std::pair<out_edge_iterator, out_edge_iterator> rng = 
williamr@2
  1194
          get_parallel_edge_sublist(e, g, (OutEdgeListS*)(0));
williamr@2
  1195
        rng.first = std::find(rng.first, rng.second, e);
williamr@2
  1196
        assert(rng.first != rng.second);
williamr@2
  1197
        remove_edge(rng.first);
williamr@2
  1198
      }
williamr@2
  1199
williamr@2
  1200
      inline void
williamr@2
  1201
      remove_edge(typename Config::out_edge_iterator iter)
williamr@2
  1202
      {
williamr@2
  1203
        typedef typename Config::global_edgelist_selector EdgeListS;
williamr@2
  1204
        BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
williamr@2
  1205
williamr@2
  1206
        typedef typename Config::graph_type graph_type;
williamr@2
  1207
        graph_type& g = static_cast<graph_type&>(*this);
williamr@2
  1208
        typename Config::edge_descriptor e = *iter;
williamr@2
  1209
        typename Config::OutEdgeList& oel = g.out_edge_list(source(e, g));
williamr@2
  1210
        typename Config::InEdgeList& iel = in_edge_list(g, target(e, g));
williamr@2
  1211
        typedef typename Config::OutEdgeList::value_type::property_type PType;
williamr@2
  1212
        PType& p = *(PType*)e.get_property();
williamr@2
  1213
        detail::remove_directed_edge_dispatch(*iter, iel, p);
williamr@2
  1214
        g.m_edges.erase(iter.base()->get_iter());
williamr@2
  1215
        oel.erase(iter.base());
williamr@2
  1216
      }
williamr@2
  1217
    };
williamr@2
  1218
williamr@2
  1219
    // O(E/V) for allow_parallel_edge_tag
williamr@2
  1220
    // O(log(E/V)) for disallow_parallel_edge_tag
williamr@2
  1221
    template <class Config>
williamr@2
  1222
    inline void
williamr@2
  1223
    remove_edge(typename Config::vertex_descriptor u, 
williamr@2
  1224
                typename Config::vertex_descriptor v, 
williamr@2
  1225
                bidirectional_graph_helper_with_property<Config>& g_)
williamr@2
  1226
    {
williamr@2
  1227
      typedef typename Config::global_edgelist_selector EdgeListS;
williamr@2
  1228
      BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
williamr@2
  1229
williamr@2
  1230
      typedef typename Config::graph_type graph_type;
williamr@2
  1231
      graph_type& g = static_cast<graph_type&>(g_);
williamr@2
  1232
      typedef typename Config::edge_parallel_category Cat;
williamr@2
  1233
      detail::remove_edge_and_property(g, g.out_edge_list(u), v, Cat());
williamr@2
  1234
      detail::erase_from_incidence_list(in_edge_list(g, v), u, Cat());
williamr@2
  1235
    }
williamr@2
  1236
williamr@2
  1237
    // O(E/V) or O(log(E/V))
williamr@2
  1238
    template <class EdgeOrIter, class Config>
williamr@2
  1239
    inline void
williamr@2
  1240
    remove_edge(EdgeOrIter e,
williamr@2
  1241
                bidirectional_graph_helper_with_property<Config>& g_)
williamr@2
  1242
    {
williamr@2
  1243
      typedef typename Config::global_edgelist_selector EdgeListS;
williamr@2
  1244
      BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
williamr@2
  1245
williamr@2
  1246
      g_.remove_edge(e);
williamr@2
  1247
    }
williamr@2
  1248
williamr@2
  1249
    template <class Config, class Predicate>
williamr@2
  1250
    inline void
williamr@2
  1251
    remove_out_edge_if(typename Config::vertex_descriptor u, Predicate pred,
williamr@2
  1252
                       bidirectional_graph_helper_with_property<Config>& g_)
williamr@2
  1253
    {
williamr@2
  1254
      typedef typename Config::global_edgelist_selector EdgeListS;
williamr@2
  1255
      BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
williamr@2
  1256
williamr@2
  1257
      typedef typename Config::graph_type graph_type;
williamr@2
  1258
      typedef typename Config::OutEdgeList::value_type::property_type PropT;
williamr@2
  1259
      graph_type& g = static_cast<graph_type&>(g_);
williamr@2
  1260
      
williamr@2
  1261
      typedef typename Config::EdgeIter EdgeIter;
williamr@2
  1262
      typedef std::vector<EdgeIter> Garbage;
williamr@2
  1263
      Garbage garbage;
williamr@2
  1264
williamr@2
  1265
      // First remove the edges from the targets' in-edge lists and
williamr@2
  1266
      // from the graph's edge set list.
williamr@2
  1267
      typename Config::out_edge_iterator out_i, out_end;
williamr@2
  1268
      for (tie(out_i, out_end) = out_edges(u, g); out_i != out_end; ++out_i)
williamr@2
  1269
        if (pred(*out_i)) {
williamr@2
  1270
          detail::remove_directed_edge_dispatch
williamr@2
  1271
            (*out_i, in_edge_list(g, target(*out_i, g)),
williamr@2
  1272
             *(PropT*)(*out_i).get_property());
williamr@2
  1273
          // Put in garbage to delete later. Will need the properties
williamr@2
  1274
          // for the remove_if of the out-edges.
williamr@2
  1275
          garbage.push_back((*out_i.base()).get_iter());
williamr@2
  1276
        }
williamr@2
  1277
williamr@2
  1278
      // Now remove the edges from this out-edge list.
williamr@2
  1279
      typename Config::out_edge_iterator first, last;
williamr@2
  1280
      tie(first, last) = out_edges(u, g);
williamr@2
  1281
      typedef typename Config::edge_parallel_category Cat;
williamr@2
  1282
      detail::remove_directed_edge_if_dispatch
williamr@2
  1283
        (first, last, g.out_edge_list(u), pred, Cat());
williamr@2
  1284
williamr@2
  1285
      // Now delete the edge properties from the g.m_edges list
williamr@2
  1286
      for (typename Garbage::iterator i = garbage.begin();
williamr@2
  1287
           i != garbage.end(); ++i)
williamr@2
  1288
        g.m_edges.erase(*i);
williamr@2
  1289
    }
williamr@2
  1290
    template <class Config, class Predicate>
williamr@2
  1291
    inline void
williamr@2
  1292
    remove_in_edge_if(typename Config::vertex_descriptor v, Predicate pred,
williamr@2
  1293
                      bidirectional_graph_helper_with_property<Config>& g_)
williamr@2
  1294
    {
williamr@2
  1295
      typedef typename Config::global_edgelist_selector EdgeListS;
williamr@2
  1296
      BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
williamr@2
  1297
williamr@2
  1298
      typedef typename Config::graph_type graph_type;
williamr@2
  1299
      typedef typename Config::OutEdgeList::value_type::property_type PropT;
williamr@2
  1300
      graph_type& g = static_cast<graph_type&>(g_);
williamr@2
  1301
williamr@2
  1302
      typedef typename Config::EdgeIter EdgeIter;
williamr@2
  1303
      typedef std::vector<EdgeIter> Garbage;
williamr@2
  1304
      Garbage garbage;
williamr@2
  1305
williamr@2
  1306
      // First remove the edges from the sources' out-edge lists and
williamr@2
  1307
      // from the graph's edge set list.
williamr@2
  1308
      typename Config::in_edge_iterator in_i, in_end;
williamr@2
  1309
      for (tie(in_i, in_end) = in_edges(v, g); in_i != in_end; ++in_i)
williamr@2
  1310
        if (pred(*in_i)) {
williamr@2
  1311
          typename Config::vertex_descriptor u = source(*in_i, g);
williamr@2
  1312
          detail::remove_directed_edge_dispatch
williamr@2
  1313
            (*in_i, g.out_edge_list(u), *(PropT*)(*in_i).get_property());
williamr@2
  1314
          // Put in garbage to delete later. Will need the properties
williamr@2
  1315
          // for the remove_if of the out-edges.
williamr@2
  1316
          garbage.push_back((*in_i.base()).get_iter());
williamr@2
  1317
        }
williamr@2
  1318
      // Now remove the edges from this in-edge list.
williamr@2
  1319
      typename Config::in_edge_iterator first, last;
williamr@2
  1320
      tie(first, last) = in_edges(v, g);
williamr@2
  1321
      typedef typename Config::edge_parallel_category Cat;
williamr@2
  1322
      detail::remove_directed_edge_if_dispatch
williamr@2
  1323
        (first, last, in_edge_list(g, v), pred, Cat());
williamr@2
  1324
williamr@2
  1325
      // Now delete the edge properties from the g.m_edges list
williamr@2
  1326
      for (typename Garbage::iterator i = garbage.begin();
williamr@2
  1327
           i != garbage.end(); ++i)
williamr@2
  1328
        g.m_edges.erase(*i);
williamr@2
  1329
    }
williamr@2
  1330
williamr@2
  1331
    // O(1)
williamr@2
  1332
    template <class Config>
williamr@2
  1333
    inline typename Config::edges_size_type
williamr@2
  1334
    num_edges(const bidirectional_graph_helper_with_property<Config>& g_) 
williamr@2
  1335
    {
williamr@2
  1336
      typedef typename Config::graph_type graph_type;
williamr@2
  1337
      const graph_type& g = static_cast<const graph_type&>(g_);
williamr@2
  1338
      return g.m_edges.size();
williamr@2
  1339
    }
williamr@2
  1340
    // O(E/V * E/V) for allow_parallel_edge_tag
williamr@2
  1341
    // O(E/V * log(E/V)) for disallow_parallel_edge_tag
williamr@2
  1342
    template <class Config>
williamr@2
  1343
    inline void
williamr@2
  1344
    clear_vertex(typename Config::vertex_descriptor u,
williamr@2
  1345
                 bidirectional_graph_helper_with_property<Config>& g_)
williamr@2
  1346
    {
williamr@2
  1347
      typedef typename Config::global_edgelist_selector EdgeListS;
williamr@2
  1348
      BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
williamr@2
  1349
williamr@2
  1350
      typedef typename Config::graph_type graph_type;
williamr@2
  1351
      typedef typename Config::edge_parallel_category Cat;
williamr@2
  1352
      graph_type& g = static_cast<graph_type&>(g_);
williamr@2
  1353
      typename Config::OutEdgeList& el = g.out_edge_list(u);
williamr@2
  1354
      typename Config::OutEdgeList::iterator 
williamr@2
  1355
        ei = el.begin(), ei_end = el.end();
williamr@2
  1356
      for (; ei != ei_end; ++ei) {
williamr@2
  1357
        detail::erase_from_incidence_list
williamr@2
  1358
          (in_edge_list(g, (*ei).get_target()), u, Cat());
williamr@2
  1359
        g.m_edges.erase((*ei).get_iter());
williamr@2
  1360
      }      
williamr@2
  1361
      typename Config::InEdgeList& in_el = in_edge_list(g, u);
williamr@2
  1362
      typename Config::InEdgeList::iterator 
williamr@2
  1363
        in_ei = in_el.begin(), in_ei_end = in_el.end();
williamr@2
  1364
      for (; in_ei != in_ei_end; ++in_ei) {
williamr@2
  1365
        detail::erase_from_incidence_list
williamr@2
  1366
          (g.out_edge_list((*in_ei).get_target()), u, Cat());
williamr@2
  1367
        g.m_edges.erase((*in_ei).get_iter());   
williamr@2
  1368
      }
williamr@2
  1369
      g.out_edge_list(u).clear();
williamr@2
  1370
      in_edge_list(g, u).clear();
williamr@2
  1371
    }
williamr@2
  1372
williamr@2
  1373
    template <class Config>
williamr@2
  1374
    inline void
williamr@2
  1375
    clear_out_edges(typename Config::vertex_descriptor u,
williamr@2
  1376
                    bidirectional_graph_helper_with_property<Config>& g_)
williamr@2
  1377
    {
williamr@2
  1378
      typedef typename Config::global_edgelist_selector EdgeListS;
williamr@2
  1379
      BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
williamr@2
  1380
williamr@2
  1381
      typedef typename Config::graph_type graph_type;
williamr@2
  1382
      typedef typename Config::edge_parallel_category Cat;
williamr@2
  1383
      graph_type& g = static_cast<graph_type&>(g_);
williamr@2
  1384
      typename Config::OutEdgeList& el = g.out_edge_list(u);
williamr@2
  1385
      typename Config::OutEdgeList::iterator 
williamr@2
  1386
        ei = el.begin(), ei_end = el.end();
williamr@2
  1387
      for (; ei != ei_end; ++ei) {
williamr@2
  1388
        detail::erase_from_incidence_list
williamr@2
  1389
          (in_edge_list(g, (*ei).get_target()), u, Cat());
williamr@2
  1390
        g.m_edges.erase((*ei).get_iter());
williamr@2
  1391
      }      
williamr@2
  1392
      g.out_edge_list(u).clear();
williamr@2
  1393
    }
williamr@2
  1394
williamr@2
  1395
    template <class Config>
williamr@2
  1396
    inline void
williamr@2
  1397
    clear_in_edges(typename Config::vertex_descriptor u,
williamr@2
  1398
                   bidirectional_graph_helper_with_property<Config>& g_)
williamr@2
  1399
    {
williamr@2
  1400
      typedef typename Config::global_edgelist_selector EdgeListS;
williamr@2
  1401
      BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
williamr@2
  1402
williamr@2
  1403
      typedef typename Config::graph_type graph_type;
williamr@2
  1404
      typedef typename Config::edge_parallel_category Cat;
williamr@2
  1405
      graph_type& g = static_cast<graph_type&>(g_);
williamr@2
  1406
      typename Config::InEdgeList& in_el = in_edge_list(g, u);
williamr@2
  1407
      typename Config::InEdgeList::iterator 
williamr@2
  1408
        in_ei = in_el.begin(), in_ei_end = in_el.end();
williamr@2
  1409
      for (; in_ei != in_ei_end; ++in_ei) {
williamr@2
  1410
        detail::erase_from_incidence_list
williamr@2
  1411
          (g.out_edge_list((*in_ei).get_target()), u, Cat());
williamr@2
  1412
        g.m_edges.erase((*in_ei).get_iter());   
williamr@2
  1413
      }
williamr@2
  1414
      in_edge_list(g, u).clear();
williamr@2
  1415
    }
williamr@2
  1416
williamr@2
  1417
    // O(1) for allow_parallel_edge_tag
williamr@2
  1418
    // O(log(E/V)) for disallow_parallel_edge_tag
williamr@2
  1419
    template <class Config>
williamr@2
  1420
    inline std::pair<typename Config::edge_descriptor, bool>
williamr@2
  1421
    add_edge(typename Config::vertex_descriptor u,
williamr@2
  1422
             typename Config::vertex_descriptor v, 
williamr@2
  1423
             const typename Config::edge_property_type& p,
williamr@2
  1424
             bidirectional_graph_helper_with_property<Config>& g_)
williamr@2
  1425
    {
williamr@2
  1426
      typedef typename Config::graph_type graph_type;
williamr@2
  1427
      graph_type& g = static_cast<graph_type&>(g_);
williamr@2
  1428
      typedef typename Config::edge_descriptor edge_descriptor;
williamr@2
  1429
      typedef typename Config::StoredEdge StoredEdge;
williamr@2
  1430
      bool inserted;
williamr@2
  1431
      typename Config::EdgeContainer::value_type e(u, v, p);
williamr@2
  1432
      typename Config::EdgeContainer::iterator p_iter 
williamr@2
  1433
        = graph_detail::push(g.m_edges, e).first;
williamr@2
  1434
      typename Config::OutEdgeList::iterator i;
williamr@2
  1435
      boost::tie(i, inserted) = boost::graph_detail::push(g.out_edge_list(u), 
williamr@2
  1436
                                        StoredEdge(v, p_iter, &g.m_edges));
williamr@2
  1437
      if (inserted) {
williamr@2
  1438
        boost::graph_detail::push(in_edge_list(g, v), StoredEdge(u, p_iter, &g.m_edges));
williamr@2
  1439
        return std::make_pair(edge_descriptor(u, v, &p_iter->m_property), 
williamr@2
  1440
                              true);
williamr@2
  1441
      } else {
williamr@2
  1442
        g.m_edges.erase(p_iter);
williamr@2
  1443
        return std::make_pair(edge_descriptor(u, v, 
williamr@2
  1444
                                     &i->get_iter()->get_property()), 
williamr@2
  1445
                              false);
williamr@2
  1446
      }
williamr@2
  1447
    }
williamr@2
  1448
williamr@2
  1449
    template <class Config>
williamr@2
  1450
    inline std::pair<typename Config::edge_descriptor, bool>
williamr@2
  1451
    add_edge(typename Config::vertex_descriptor u,
williamr@2
  1452
             typename Config::vertex_descriptor v,
williamr@2
  1453
             bidirectional_graph_helper_with_property<Config>& g_)
williamr@2
  1454
    {
williamr@2
  1455
      typename Config::edge_property_type p;
williamr@2
  1456
      return add_edge(u, v, p, g_);
williamr@2
  1457
    }
williamr@2
  1458
    // O(1)
williamr@2
  1459
    template <class Config>
williamr@2
  1460
    inline typename Config::degree_size_type
williamr@2
  1461
    degree(typename Config::vertex_descriptor u, 
williamr@2
  1462
           const bidirectional_graph_helper_with_property<Config>& g_)
williamr@2
  1463
    {
williamr@2
  1464
      typedef typename Config::graph_type graph_type;
williamr@2
  1465
      const graph_type& g = static_cast<const graph_type&>(g_);
williamr@2
  1466
      return in_degree(u, g) + out_degree(u, g);
williamr@2
  1467
    }
williamr@2
  1468
williamr@2
  1469
    //=========================================================================
williamr@2
  1470
    // Adjacency List Helper Class
williamr@2
  1471
williamr@2
  1472
    template <class Config, class Base>
williamr@2
  1473
    struct adj_list_helper : public Base
williamr@2
  1474
    {
williamr@2
  1475
      typedef typename Config::graph_type AdjList;
williamr@2
  1476
      typedef typename Config::vertex_descriptor vertex_descriptor;
williamr@2
  1477
      typedef typename Config::edge_descriptor edge_descriptor;
williamr@2
  1478
      typedef typename Config::out_edge_iterator out_edge_iterator;
williamr@2
  1479
      typedef typename Config::in_edge_iterator in_edge_iterator;
williamr@2
  1480
      typedef typename Config::adjacency_iterator adjacency_iterator;
williamr@2
  1481
      typedef typename Config::inv_adjacency_iterator inv_adjacency_iterator;
williamr@2
  1482
      typedef typename Config::vertex_iterator vertex_iterator;
williamr@2
  1483
      typedef typename Config::edge_iterator edge_iterator;
williamr@2
  1484
      typedef typename Config::directed_category directed_category;
williamr@2
  1485
      typedef typename Config::edge_parallel_category edge_parallel_category;
williamr@2
  1486
      typedef typename Config::vertices_size_type vertices_size_type;
williamr@2
  1487
      typedef typename Config::edges_size_type edges_size_type;
williamr@2
  1488
      typedef typename Config::degree_size_type degree_size_type;
williamr@2
  1489
      typedef typename Config::StoredEdge StoredEdge;
williamr@2
  1490
      typedef typename Config::edge_property_type edge_property_type;
williamr@2
  1491
williamr@2
  1492
      typedef typename Config::global_edgelist_selector
williamr@2
  1493
        global_edgelist_selector;
williamr@2
  1494
williamr@2
  1495
      //    protected:
williamr@2
  1496
williamr@2
  1497
      // The edge_dispatch() functions should be static, but
williamr@2
  1498
      // Borland gets confused about constness.
williamr@2
  1499
williamr@2
  1500
      // O(E/V)
williamr@2
  1501
      inline std::pair<edge_descriptor,bool>      
williamr@2
  1502
      edge_dispatch(const AdjList& g, 
williamr@2
  1503
                    vertex_descriptor u, vertex_descriptor v, 
williamr@2
  1504
                    boost::allow_parallel_edge_tag) const
williamr@2
  1505
      {
williamr@2
  1506
        bool found;
williamr@2
  1507
        const typename Config::OutEdgeList& el = g.out_edge_list(u);
williamr@2
  1508
        typename Config::OutEdgeList::const_iterator 
williamr@2
  1509
          i = std::find_if(el.begin(), el.end(), 
williamr@2
  1510
                           detail::target_is<vertex_descriptor>(v));
williamr@2
  1511
        found = (i != g.out_edge_list(u).end());
williamr@2
  1512
        if (found)
williamr@2
  1513
          return std::make_pair(edge_descriptor(u, v, &(*i).get_property()),
williamr@2
  1514
                                true);
williamr@2
  1515
        else
williamr@2
  1516
          return std::make_pair(edge_descriptor(u, v, 0), false);
williamr@2
  1517
      }
williamr@2
  1518
      // O(log(E/V))
williamr@2
  1519
      inline std::pair<edge_descriptor,bool>      
williamr@2
  1520
      edge_dispatch(const AdjList& g, 
williamr@2
  1521
                    vertex_descriptor u, vertex_descriptor v, 
williamr@2
  1522
                    boost::disallow_parallel_edge_tag) const
williamr@2
  1523
      {
williamr@2
  1524
        bool found;
williamr@2
  1525
        /* According to the standard, this should be iterator, not const_iterator,
williamr@2
  1526
           but the VC++ std::set::find() const returns const_iterator.
williamr@2
  1527
           And since iterator should be convertible to const_iterator, the
williamr@2
  1528
           following should work everywhere. -Jeremy */
williamr@2
  1529
        typename Config::OutEdgeList::const_iterator 
williamr@2
  1530
          i = g.out_edge_list(u).find(StoredEdge(v)),
williamr@2
  1531
          end = g.out_edge_list(u).end();
williamr@2
  1532
        found = (i != end);
williamr@2
  1533
        if (found)
williamr@2
  1534
          return std::make_pair(edge_descriptor(u, v, &(*i).get_property()),
williamr@2
  1535
                                true);
williamr@2
  1536
        else
williamr@2
  1537
          return std::make_pair(edge_descriptor(u, v, 0), false);
williamr@2
  1538
      }
williamr@2
  1539
    };
williamr@2
  1540
williamr@2
  1541
    template <class Config, class Base>
williamr@2
  1542
    inline std::pair<typename Config::adjacency_iterator, 
williamr@2
  1543
                     typename Config::adjacency_iterator>
williamr@2
  1544
    adjacent_vertices(typename Config::vertex_descriptor u, 
williamr@2
  1545
                      const adj_list_helper<Config, Base>& g_)
williamr@2
  1546
    {
williamr@2
  1547
      typedef typename Config::graph_type AdjList;
williamr@2
  1548
      const AdjList& cg = static_cast<const AdjList&>(g_);
williamr@2
  1549
      AdjList& g = const_cast<AdjList&>(cg);
williamr@2
  1550
      typedef typename Config::adjacency_iterator adjacency_iterator;
williamr@2
  1551
      typename Config::out_edge_iterator first, last;
williamr@2
  1552
      boost::tie(first, last) = out_edges(u, g);
williamr@2
  1553
      return std::make_pair(adjacency_iterator(first, &g),
williamr@2
  1554
                            adjacency_iterator(last, &g));
williamr@2
  1555
    }
williamr@2
  1556
    template <class Config, class Base>
williamr@2
  1557
    inline std::pair<typename Config::inv_adjacency_iterator, 
williamr@2
  1558
                     typename Config::inv_adjacency_iterator>
williamr@2
  1559
    inv_adjacent_vertices(typename Config::vertex_descriptor u, 
williamr@2
  1560
                          const adj_list_helper<Config, Base>& g_)
williamr@2
  1561
    {
williamr@2
  1562
      typedef typename Config::graph_type AdjList;
williamr@2
  1563
      const AdjList& cg = static_cast<const AdjList&>(g_);
williamr@2
  1564
      AdjList& g = const_cast<AdjList&>(cg);
williamr@2
  1565
      typedef typename Config::inv_adjacency_iterator inv_adjacency_iterator;
williamr@2
  1566
      typename Config::in_edge_iterator first, last;
williamr@2
  1567
      boost::tie(first, last) = in_edges(u, g);
williamr@2
  1568
      return std::make_pair(inv_adjacency_iterator(first, &g),
williamr@2
  1569
                            inv_adjacency_iterator(last, &g));
williamr@2
  1570
    }
williamr@2
  1571
    template <class Config, class Base>
williamr@2
  1572
    inline std::pair<typename Config::out_edge_iterator, 
williamr@2
  1573
                     typename Config::out_edge_iterator>
williamr@2
  1574
    out_edges(typename Config::vertex_descriptor u, 
williamr@2
  1575
              const adj_list_helper<Config, Base>& g_)
williamr@2
  1576
    {
williamr@2
  1577
      typedef typename Config::graph_type AdjList;
williamr@2
  1578
      typedef typename Config::out_edge_iterator out_edge_iterator;
williamr@2
  1579
      const AdjList& cg = static_cast<const AdjList&>(g_);
williamr@2
  1580
      AdjList& g = const_cast<AdjList&>(cg);
williamr@2
  1581
      return
williamr@2
  1582
        std::make_pair(out_edge_iterator(g.out_edge_list(u).begin(), u),
williamr@2
  1583
                       out_edge_iterator(g.out_edge_list(u).end(), u));
williamr@2
  1584
    }
williamr@2
  1585
    template <class Config, class Base>
williamr@2
  1586
    inline std::pair<typename Config::vertex_iterator, 
williamr@2
  1587
                     typename Config::vertex_iterator>
williamr@2
  1588
    vertices(const adj_list_helper<Config, Base>& g_)
williamr@2
  1589
    {
williamr@2
  1590
      typedef typename Config::graph_type AdjList;
williamr@2
  1591
      const AdjList& cg = static_cast<const AdjList&>(g_);
williamr@2
  1592
      AdjList& g = const_cast<AdjList&>(cg);
williamr@2
  1593
      return std::make_pair( g.vertex_set().begin(), g.vertex_set().end() );
williamr@2
  1594
    }
williamr@2
  1595
    template <class Config, class Base>
williamr@2
  1596
    inline typename Config::vertices_size_type
williamr@2
  1597
    num_vertices(const adj_list_helper<Config, Base>& g_)
williamr@2
  1598
    {
williamr@2
  1599
      typedef typename Config::graph_type AdjList;
williamr@2
  1600
      const AdjList& g = static_cast<const AdjList&>(g_);
williamr@2
  1601
      return g.vertex_set().size();
williamr@2
  1602
    }
williamr@2
  1603
    template <class Config, class Base>
williamr@2
  1604
    inline typename Config::degree_size_type
williamr@2
  1605
    out_degree(typename Config::vertex_descriptor u, 
williamr@2
  1606
               const adj_list_helper<Config, Base>& g_)
williamr@2
  1607
    {
williamr@2
  1608
      typedef typename Config::graph_type AdjList;
williamr@2
  1609
      const AdjList& g = static_cast<const AdjList&>(g_);
williamr@2
  1610
      return g.out_edge_list(u).size();
williamr@2
  1611
    }
williamr@2
  1612
    template <class Config, class Base>
williamr@2
  1613
    inline std::pair<typename Config::edge_descriptor, bool>
williamr@2
  1614
    edge(typename Config::vertex_descriptor u, 
williamr@2
  1615
         typename Config::vertex_descriptor v, 
williamr@2
  1616
         const adj_list_helper<Config, Base>& g_)
williamr@2
  1617
    {
williamr@2
  1618
      typedef typename Config::graph_type Graph;
williamr@2
  1619
      typedef typename Config::edge_parallel_category Cat;
williamr@2
  1620
      const Graph& g = static_cast<const Graph&>(g_);
williamr@2
  1621
      return g_.edge_dispatch(g, u, v, Cat());
williamr@2
  1622
    }
williamr@2
  1623
    template <class Config, class Base>
williamr@2
  1624
    inline std::pair<typename Config::out_edge_iterator,
williamr@2
  1625
                     typename Config::out_edge_iterator>
williamr@2
  1626
    edge_range(typename Config::vertex_descriptor u,
williamr@2
  1627
               typename Config::vertex_descriptor v,
williamr@2
  1628
               const adj_list_helper<Config, Base>& g_)
williamr@2
  1629
    {
williamr@2
  1630
      typedef typename Config::graph_type Graph;
williamr@2
  1631
      typedef typename Config::StoredEdge StoredEdge;
williamr@2
  1632
      const Graph& cg = static_cast<const Graph&>(g_);
williamr@2
  1633
      Graph& g = const_cast<Graph&>(cg);
williamr@2
  1634
      typedef typename Config::out_edge_iterator out_edge_iterator;
williamr@2
  1635
      typename Config::OutEdgeList& el = g.out_edge_list(u);
williamr@2
  1636
      typename Config::OutEdgeList::iterator first, last;
williamr@2
  1637
      typename Config::EdgeContainer fake_edge_container;
williamr@2
  1638
      tie(first, last) = 
williamr@2
  1639
        std::equal_range(el.begin(), el.end(), 
williamr@2
  1640
                         StoredEdge(v, fake_edge_container.end(),
williamr@2
  1641
                                    &fake_edge_container));
williamr@2
  1642
      return std::make_pair(out_edge_iterator(first, u),
williamr@2
  1643
                            out_edge_iterator(last, u));
williamr@2
  1644
    }
williamr@2
  1645
williamr@2
  1646
    template <class Config>
williamr@2
  1647
    inline typename Config::degree_size_type
williamr@2
  1648
    in_degree(typename Config::vertex_descriptor u, 
williamr@2
  1649
              const directed_edges_helper<Config>& g_)
williamr@2
  1650
    {
williamr@2
  1651
      typedef typename Config::graph_type Graph;
williamr@2
  1652
      const Graph& cg = static_cast<const Graph&>(g_);
williamr@2
  1653
      Graph& g = const_cast<Graph&>(cg);
williamr@2
  1654
      return in_edge_list(g, u).size();
williamr@2
  1655
    }
williamr@2
  1656
williamr@2
  1657
    namespace detail {
williamr@2
  1658
      template <class Config, class Base, class Property>
williamr@2
  1659
      inline
williamr@2
  1660
      typename boost::property_map<typename Config::graph_type,
williamr@2
  1661
        Property>::type
williamr@2
  1662
      get_dispatch(adj_list_helper<Config,Base>&, Property, 
williamr@2
  1663
                   boost::edge_property_tag) {
williamr@2
  1664
        typedef typename Config::graph_type Graph;
williamr@2
  1665
        typedef typename boost::property_map<Graph, Property>::type PA;
williamr@2
  1666
        return PA();
williamr@2
  1667
      }
williamr@2
  1668
      template <class Config, class Base, class Property>
williamr@2
  1669
      inline
williamr@2
  1670
      typename boost::property_map<typename Config::graph_type, 
williamr@2
  1671
        Property>::const_type
williamr@2
  1672
      get_dispatch(const adj_list_helper<Config,Base>&, Property, 
williamr@2
  1673
                   boost::edge_property_tag) {
williamr@2
  1674
        typedef typename Config::graph_type Graph;
williamr@2
  1675
        typedef typename boost::property_map<Graph, Property>::const_type PA;
williamr@2
  1676
        return PA();
williamr@2
  1677
      }
williamr@2
  1678
williamr@2
  1679
      template <class Config, class Base, class Property>
williamr@2
  1680
      inline
williamr@2
  1681
      typename boost::property_map<typename Config::graph_type, 
williamr@2
  1682
        Property>::type
williamr@2
  1683
      get_dispatch(adj_list_helper<Config,Base>& g, Property, 
williamr@2
  1684
                   boost::vertex_property_tag) {
williamr@2
  1685
        typedef typename Config::graph_type Graph;
williamr@2
  1686
        typedef typename boost::property_map<Graph, Property>::type PA;
williamr@2
  1687
        return PA(&static_cast<Graph&>(g));
williamr@2
  1688
      }
williamr@2
  1689
      template <class Config, class Base, class Property>
williamr@2
  1690
      inline
williamr@2
  1691
      typename boost::property_map<typename Config::graph_type,
williamr@2
  1692
        Property>::const_type
williamr@2
  1693
      get_dispatch(const adj_list_helper<Config, Base>& g, Property, 
williamr@2
  1694
                   boost::vertex_property_tag) {
williamr@2
  1695
        typedef typename Config::graph_type Graph;
williamr@2
  1696
        typedef typename boost::property_map<Graph, Property>::const_type PA;
williamr@2
  1697
        const Graph& cg = static_cast<const Graph&>(g);
williamr@2
  1698
        return PA(&cg);
williamr@2
  1699
      }
williamr@2
  1700
williamr@2
  1701
    } // namespace detail
williamr@2
  1702
williamr@2
  1703
    // Implementation of the PropertyGraph interface
williamr@2
  1704
    template <class Config, class Base, class Property>
williamr@2
  1705
    inline
williamr@2
  1706
    typename boost::property_map<typename Config::graph_type, Property>::type
williamr@2
  1707
    get(Property p, adj_list_helper<Config, Base>& g) {
williamr@2
  1708
      typedef typename property_kind<Property>::type Kind;
williamr@2
  1709
      return detail::get_dispatch(g, p, Kind());
williamr@2
  1710
    }
williamr@2
  1711
    template <class Config, class Base, class Property>
williamr@2
  1712
    inline
williamr@2
  1713
    typename boost::property_map<typename Config::graph_type, 
williamr@2
  1714
      Property>::const_type
williamr@2
  1715
    get(Property p, const adj_list_helper<Config, Base>& g) {
williamr@2
  1716
      typedef typename property_kind<Property>::type Kind;
williamr@2
  1717
      return detail::get_dispatch(g, p, Kind());
williamr@2
  1718
    }
williamr@2
  1719
williamr@2
  1720
    template <class Config, class Base, class Property, class Key>
williamr@2
  1721
    inline
williamr@2
  1722
    typename boost::property_traits<
williamr@2
  1723
      typename boost::property_map<typename Config::graph_type, 
williamr@2
  1724
        Property>::type
williamr@2
  1725
    >::reference
williamr@2
  1726
    get(Property p, adj_list_helper<Config, Base>& g, const Key& key) {
williamr@2
  1727
      return get(get(p, g), key);
williamr@2
  1728
    }
williamr@2
  1729
williamr@2
  1730
    template <class Config, class Base, class Property, class Key>
williamr@2
  1731
    inline
williamr@2
  1732
    typename boost::property_traits<
williamr@2
  1733
      typename boost::property_map<typename Config::graph_type, 
williamr@2
  1734
        Property>::const_type
williamr@2
  1735
    >::reference
williamr@2
  1736
    get(Property p, const adj_list_helper<Config, Base>& g, const Key& key) {
williamr@2
  1737
      return get(get(p, g), key);
williamr@2
  1738
    }
williamr@2
  1739
williamr@2
  1740
    template <class Config, class Base, class Property, class Key,class Value>
williamr@2
  1741
    inline void
williamr@2
  1742
    put(Property p, adj_list_helper<Config, Base>& g, 
williamr@2
  1743
        const Key& key, const Value& value)
williamr@2
  1744
    {
williamr@2
  1745
      typedef typename Config::graph_type Graph;
williamr@2
  1746
      typedef typename boost::property_map<Graph, Property>::type Map;
williamr@2
  1747
      Map pmap = get(p, static_cast<Graph&>(g));
williamr@2
  1748
      put(pmap, key, value);
williamr@2
  1749
    }
williamr@2
  1750
williamr@2
  1751
williamr@2
  1752
    //=========================================================================
williamr@2
  1753
    // Generalize Adjacency List Implementation
williamr@2
  1754
williamr@2
  1755
    struct adj_list_tag { };
williamr@2
  1756
williamr@2
  1757
    template <class Derived, class Config, class Base>
williamr@2
  1758
    class adj_list_impl
williamr@2
  1759
      : public adj_list_helper<Config, Base>
williamr@2
  1760
    {
williamr@2
  1761
      typedef typename Config::OutEdgeList OutEdgeList;
williamr@2
  1762
      typedef typename Config::InEdgeList InEdgeList;
williamr@2
  1763
      typedef typename Config::StoredVertexList StoredVertexList;
williamr@2
  1764
    public:
williamr@2
  1765
      typedef typename Config::stored_vertex stored_vertex;
williamr@2
  1766
      typedef typename Config::EdgeContainer EdgeContainer;
williamr@2
  1767
      typedef typename Config::vertex_descriptor vertex_descriptor;
williamr@2
  1768
      typedef typename Config::edge_descriptor edge_descriptor;
williamr@2
  1769
      typedef typename Config::vertex_iterator vertex_iterator;
williamr@2
  1770
      typedef typename Config::edge_iterator edge_iterator;
williamr@2
  1771
      typedef typename Config::edge_parallel_category edge_parallel_category;
williamr@2
  1772
      typedef typename Config::vertices_size_type vertices_size_type;
williamr@2
  1773
      typedef typename Config::edges_size_type edges_size_type;
williamr@2
  1774
      typedef typename Config::degree_size_type degree_size_type;
williamr@2
  1775
      typedef typename Config::edge_property_type edge_property_type;
williamr@2
  1776
      typedef adj_list_tag graph_tag;
williamr@2
  1777
williamr@2
  1778
      static vertex_descriptor null_vertex()
williamr@2
  1779
      {
williamr@2
  1780
        return 0;
williamr@2
  1781
      }
williamr@2
  1782
      
williamr@2
  1783
      inline adj_list_impl() { }
williamr@2
  1784
williamr@2
  1785
      inline adj_list_impl(const adj_list_impl& x) {
williamr@2
  1786
        copy_impl(x);
williamr@2
  1787
      }
williamr@2
  1788
      inline adj_list_impl& operator=(const adj_list_impl& x) {
williamr@2
  1789
        this->clear();
williamr@2
  1790
        copy_impl(x);
williamr@2
  1791
        return *this;
williamr@2
  1792
      }
williamr@2
  1793
      inline void clear() {
williamr@2
  1794
        for (typename StoredVertexList::iterator i = m_vertices.begin();
williamr@2
  1795
             i != m_vertices.end(); ++i)
williamr@2
  1796
          delete (stored_vertex*)*i;
williamr@2
  1797
        m_vertices.clear();
williamr@2
  1798
        m_edges.clear();
williamr@2
  1799
      }
williamr@2
  1800
      inline adj_list_impl(vertices_size_type num_vertices) {
williamr@2
  1801
        for (vertices_size_type i = 0; i < num_vertices; ++i)
williamr@2
  1802
          add_vertex(static_cast<Derived&>(*this));
williamr@2
  1803
      }
williamr@2
  1804
      template <class EdgeIterator>
williamr@2
  1805
      inline adj_list_impl(vertices_size_type num_vertices,
williamr@2
  1806
                           EdgeIterator first, EdgeIterator last)
williamr@2
  1807
      {
williamr@2
  1808
        vertex_descriptor* v = new vertex_descriptor[num_vertices];
williamr@2
  1809
        for (vertices_size_type i = 0; i < num_vertices; ++i)
williamr@2
  1810
          v[i] = add_vertex(static_cast<Derived&>(*this));
williamr@2
  1811
williamr@2
  1812
        while (first != last) {
williamr@2
  1813
          add_edge(v[(*first).first], v[(*first).second], *this);
williamr@2
  1814
          ++first;
williamr@2
  1815
        }
williamr@2
  1816
        delete [] v;
williamr@2
  1817
      }
williamr@2
  1818
      template <class EdgeIterator, class EdgePropertyIterator>
williamr@2
  1819
      inline adj_list_impl(vertices_size_type num_vertices,
williamr@2
  1820
                           EdgeIterator first, EdgeIterator last,
williamr@2
  1821
                           EdgePropertyIterator ep_iter)
williamr@2
  1822
      {
williamr@2
  1823
        vertex_descriptor* v = new vertex_descriptor[num_vertices];
williamr@2
  1824
        for (vertices_size_type i = 0; i < num_vertices; ++i)
williamr@2
  1825
          v[i] = add_vertex(static_cast<Derived&>(*this));
williamr@2
  1826
williamr@2
  1827
        while (first != last) {
williamr@2
  1828
          add_edge(v[(*first).first], v[(*first).second], *ep_iter, *this);
williamr@2
  1829
          ++first;
williamr@2
  1830
          ++ep_iter;
williamr@2
  1831
        }
williamr@2
  1832
        delete [] v;
williamr@2
  1833
      }
williamr@2
  1834
      ~adj_list_impl() {
williamr@2
  1835
        for (typename StoredVertexList::iterator i = m_vertices.begin();
williamr@2
  1836
             i != m_vertices.end(); ++i)
williamr@2
  1837
          delete (stored_vertex*)*i;
williamr@2
  1838
      }
williamr@2
  1839
      //    protected:
williamr@2
  1840
      inline OutEdgeList& out_edge_list(vertex_descriptor v) {
williamr@2
  1841
        stored_vertex* sv = (stored_vertex*)v;
williamr@2
  1842
        return sv->m_out_edges;
williamr@2
  1843
      }
williamr@2
  1844
      inline const OutEdgeList& out_edge_list(vertex_descriptor v) const {
williamr@2
  1845
        stored_vertex* sv = (stored_vertex*)v;
williamr@2
  1846
        return sv->m_out_edges;
williamr@2
  1847
      }
williamr@2
  1848
      inline StoredVertexList& vertex_set() { return m_vertices; }
williamr@2
  1849
      inline const StoredVertexList& vertex_set() const { return m_vertices; }
williamr@2
  1850
williamr@2
  1851
      inline void copy_impl(const adj_list_impl& x_) 
williamr@2
  1852
      {
williamr@2
  1853
        const Derived& x = static_cast<const Derived&>(x_);
williamr@2
  1854
williamr@2
  1855
        // Would be better to have a constant time way to get from
williamr@2
  1856
        // vertices in x to the corresponding vertices in *this.
williamr@2
  1857
        std::map<stored_vertex*,stored_vertex*> vertex_map;
williamr@2
  1858
williamr@2
  1859
        // Copy the stored vertex objects by adding each vertex
williamr@2
  1860
        // and copying its property object.
williamr@2
  1861
        vertex_iterator vi, vi_end;
williamr@2
  1862
        for (tie(vi, vi_end) = vertices(x); vi != vi_end; ++vi) {
williamr@2
  1863
          stored_vertex* v = (stored_vertex*)add_vertex(*this);
williamr@2
  1864
          v->m_property = ((stored_vertex*)*vi)->m_property;
williamr@2
  1865
          vertex_map[(stored_vertex*)*vi] = v;
williamr@2
  1866
        }
williamr@2
  1867
        // Copy the edges by adding each edge and copying its
williamr@2
  1868
        // property object.
williamr@2
  1869
        edge_iterator ei, ei_end;
williamr@2
  1870
        for (tie(ei, ei_end) = edges(x); ei != ei_end; ++ei) {
williamr@2
  1871
          edge_descriptor e;
williamr@2
  1872
          bool inserted; 
williamr@2
  1873
          vertex_descriptor s = source(*ei,x), t = target(*ei,x);
williamr@2
  1874
          tie(e, inserted) = add_edge(vertex_map[(stored_vertex*)s], 
williamr@2
  1875
                                      vertex_map[(stored_vertex*)t], *this);
williamr@2
  1876
          *((edge_property_type*)e.m_eproperty)
williamr@2
  1877
            = *((edge_property_type*)(*ei).m_eproperty);
williamr@2
  1878
        }
williamr@2
  1879
      }
williamr@2
  1880
williamr@2
  1881
williamr@2
  1882
      typename Config::EdgeContainer m_edges;
williamr@2
  1883
      StoredVertexList m_vertices;
williamr@2
  1884
    };
williamr@2
  1885
williamr@2
  1886
    // O(1)
williamr@2
  1887
    template <class Derived, class Config, class Base>
williamr@2
  1888
    inline typename Config::vertex_descriptor
williamr@2
  1889
    add_vertex(adj_list_impl<Derived, Config, Base>& g_)
williamr@2
  1890
    {
williamr@2
  1891
      Derived& g = static_cast<Derived&>(g_);
williamr@2
  1892
      typedef typename Config::stored_vertex stored_vertex;
williamr@2
  1893
      stored_vertex* v = new stored_vertex;
williamr@2
  1894
      typename Config::StoredVertexList::iterator pos;
williamr@2
  1895
      bool inserted;
williamr@2
  1896
      boost::tie(pos,inserted) = boost::graph_detail::push(g.m_vertices, v);
williamr@2
  1897
      v->m_position = pos;
williamr@2
  1898
      return v;
williamr@2
  1899
    }
williamr@2
  1900
    // O(1)
williamr@2
  1901
    template <class Derived, class Config, class Base>
williamr@2
  1902
    inline typename Config::vertex_descriptor
williamr@2
  1903
    add_vertex(const typename Config::vertex_property_type& p,
williamr@2
  1904
               adj_list_impl<Derived, Config, Base>& g_)
williamr@2
  1905
    {
williamr@2
  1906
      Derived& g = static_cast<Derived&>(g_);
williamr@2
  1907
      typedef typename Config::stored_vertex stored_vertex;
williamr@2
  1908
      stored_vertex* v = new stored_vertex(p);
williamr@2
  1909
      typename Config::StoredVertexList::iterator pos;
williamr@2
  1910
      bool inserted;
williamr@2
  1911
      boost::tie(pos,inserted) = boost::graph_detail::push(g.m_vertices, v);
williamr@2
  1912
      v->m_position = pos;
williamr@2
  1913
      return v;
williamr@2
  1914
    }
williamr@2
  1915
    // O(1)
williamr@2
  1916
    template <class Derived, class Config, class Base>
williamr@2
  1917
    inline void remove_vertex(typename Config::vertex_descriptor u,
williamr@2
  1918
                              adj_list_impl<Derived, Config, Base>& g_)
williamr@2
  1919
    {
williamr@2
  1920
      typedef typename Config::stored_vertex stored_vertex;
williamr@2
  1921
      Derived& g = static_cast<Derived&>(g_);
williamr@2
  1922
      stored_vertex* su = (stored_vertex*)u;
williamr@2
  1923
      g.m_vertices.erase(su->m_position);
williamr@2
  1924
      delete su;
williamr@2
  1925
    }
williamr@2
  1926
    // O(V)
williamr@2
  1927
    template <class Derived, class Config, class Base>
williamr@2
  1928
    inline typename Config::vertex_descriptor
williamr@2
  1929
    vertex(typename Config::vertices_size_type n, 
williamr@2
  1930
           const adj_list_impl<Derived, Config, Base>& g_)
williamr@2
  1931
    {
williamr@2
  1932
      const Derived& g = static_cast<const Derived&>(g_);
williamr@2
  1933
      typename Config::vertex_iterator i = vertices(g).first;
williamr@2
  1934
      while (n--) ++i; // std::advance(i, n); (not VC++ portable)
williamr@2
  1935
      return *i;
williamr@2
  1936
    }
williamr@2
  1937
williamr@2
  1938
    //=========================================================================
williamr@2
  1939
    // Vector-Backbone Adjacency List Implementation
williamr@2
  1940
williamr@2
  1941
    namespace detail {
williamr@2
  1942
williamr@2
  1943
      template <class Graph, class vertex_descriptor>
williamr@2
  1944
      inline void 
williamr@2
  1945
      remove_vertex_dispatch(Graph& g, vertex_descriptor u, 
williamr@2
  1946
                             boost::directed_tag)
williamr@2
  1947
      {
williamr@2
  1948
        typedef typename Graph::edge_parallel_category edge_parallel_category;
williamr@2
  1949
        g.m_vertices.erase(g.m_vertices.begin() + u);
williamr@2
  1950
        vertex_descriptor V = num_vertices(g);
williamr@2
  1951
        if (u != V) {
williamr@2
  1952
          for (vertex_descriptor v = 0; v < V; ++v)
williamr@2
  1953
            reindex_edge_list(g.out_edge_list(v), u, edge_parallel_category());
williamr@2
  1954
        }
williamr@2
  1955
      }
williamr@2
  1956
williamr@2
  1957
      template <class Graph, class vertex_descriptor>
williamr@2
  1958
      inline void 
williamr@2
  1959
      remove_vertex_dispatch(Graph& g, vertex_descriptor u, 
williamr@2
  1960
                             boost::undirected_tag)
williamr@2
  1961
      {
williamr@2
  1962
        typedef typename Graph::global_edgelist_selector EdgeListS;
williamr@2
  1963
        BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
williamr@2
  1964
williamr@2
  1965
        typedef typename Graph::edge_parallel_category edge_parallel_category;
williamr@2
  1966
        g.m_vertices.erase(g.m_vertices.begin() + u);
williamr@2
  1967
        vertex_descriptor V = num_vertices(g);
williamr@2
  1968
        for (vertex_descriptor v = 0; v < V; ++v)
williamr@2
  1969
          reindex_edge_list(g.out_edge_list(v), u, 
williamr@2
  1970
                            edge_parallel_category());
williamr@2
  1971
        typedef typename Graph::EdgeContainer Container;
williamr@2
  1972
        typedef typename Container::iterator Iter;
williamr@2
  1973
        Iter ei = g.m_edges.begin(), ei_end = g.m_edges.end();
williamr@2
  1974
        for (; ei != ei_end; ++ei) {
williamr@2
  1975
          if (ei->m_source > u)
williamr@2
  1976
            --ei->m_source;
williamr@2
  1977
          if (ei->m_target > u)
williamr@2
  1978
            --ei->m_target;
williamr@2
  1979
        }
williamr@2
  1980
      }
williamr@2
  1981
      template <class Graph, class vertex_descriptor>
williamr@2
  1982
      inline void 
williamr@2
  1983
      remove_vertex_dispatch(Graph& g, vertex_descriptor u, 
williamr@2
  1984
                             boost::bidirectional_tag)
williamr@2
  1985
      {
williamr@2
  1986
        typedef typename Graph::global_edgelist_selector EdgeListS;
williamr@2
  1987
        BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
williamr@2
  1988
williamr@2
  1989
        typedef typename Graph::edge_parallel_category edge_parallel_category;
williamr@2
  1990
        g.m_vertices.erase(g.m_vertices.begin() + u);
williamr@2
  1991
        vertex_descriptor V = num_vertices(g);
williamr@2
  1992
        vertex_descriptor v;
williamr@2
  1993
        if (u != V) {
williamr@2
  1994
          for (v = 0; v < V; ++v)
williamr@2
  1995
            reindex_edge_list(g.out_edge_list(v), u, 
williamr@2
  1996
                              edge_parallel_category());
williamr@2
  1997
          for (v = 0; v < V; ++v)
williamr@2
  1998
            reindex_edge_list(in_edge_list(g, v), u, 
williamr@2
  1999
                              edge_parallel_category());
williamr@2
  2000
williamr@2
  2001
          typedef typename Graph::EdgeContainer Container;
williamr@2
  2002
          typedef typename Container::iterator Iter;
williamr@2
  2003
          Iter ei = g.m_edges.begin(), ei_end = g.m_edges.end();
williamr@2
  2004
          for (; ei != ei_end; ++ei) {
williamr@2
  2005
            if (ei->m_source > u)
williamr@2
  2006
              --ei->m_source;
williamr@2
  2007
            if (ei->m_target > u)
williamr@2
  2008
              --ei->m_target;
williamr@2
  2009
          }
williamr@2
  2010
        }
williamr@2
  2011
      }
williamr@2
  2012
williamr@2
  2013
      template <class EdgeList, class vertex_descriptor>
williamr@2
  2014
      inline void
williamr@2
  2015
      reindex_edge_list(EdgeList& el, vertex_descriptor u, 
williamr@2
  2016
                        boost::allow_parallel_edge_tag)
williamr@2
  2017
      {
williamr@2
  2018
        typename EdgeList::iterator ei = el.begin(), e_end = el.end();
williamr@2
  2019
        for (; ei != e_end; ++ei)
williamr@2
  2020
          if ((*ei).get_target() > u)
williamr@2
  2021
            --(*ei).get_target();
williamr@2
  2022
      }
williamr@2
  2023
      template <class EdgeList, class vertex_descriptor>
williamr@2
  2024
      inline void
williamr@2
  2025
      reindex_edge_list(EdgeList& el, vertex_descriptor u, 
williamr@2
  2026
                        boost::disallow_parallel_edge_tag)
williamr@2
  2027
      {
williamr@2
  2028
        typename EdgeList::iterator ei = el.begin(), e_end = el.end();
williamr@2
  2029
        while (ei != e_end) {
williamr@2
  2030
          typename EdgeList::value_type ce = *ei;
williamr@2
  2031
          ++ei;
williamr@2
  2032
          if (ce.get_target() > u) {
williamr@2
  2033
            el.erase(ce);
williamr@2
  2034
            --ce.get_target();
williamr@2
  2035
            el.insert(ce);
williamr@2
  2036
          }
williamr@2
  2037
        }
williamr@2
  2038
      }
williamr@2
  2039
    } // namespace detail
williamr@2
  2040
williamr@2
  2041
    struct vec_adj_list_tag { };
williamr@2
  2042
    
williamr@2
  2043
    template <class Graph, class Config, class Base>
williamr@2
  2044
    class vec_adj_list_impl
williamr@2
  2045
      : public adj_list_helper<Config, Base>
williamr@2
  2046
    {
williamr@2
  2047
      typedef typename Config::OutEdgeList OutEdgeList;
williamr@2
  2048
      typedef typename Config::InEdgeList InEdgeList;
williamr@2
  2049
      typedef typename Config::StoredVertexList StoredVertexList; 
williamr@2
  2050
    public:
williamr@2
  2051
      typedef typename Config::vertex_descriptor vertex_descriptor;
williamr@2
  2052
      typedef typename Config::edge_descriptor edge_descriptor;
williamr@2
  2053
      typedef typename Config::out_edge_iterator out_edge_iterator;
williamr@2
  2054
      typedef typename Config::edge_iterator edge_iterator;
williamr@2
  2055
      typedef typename Config::directed_category directed_category;
williamr@2
  2056
      typedef typename Config::vertices_size_type vertices_size_type;
williamr@2
  2057
      typedef typename Config::edges_size_type edges_size_type;
williamr@2
  2058
      typedef typename Config::degree_size_type degree_size_type;
williamr@2
  2059
      typedef typename Config::StoredEdge StoredEdge;
williamr@2
  2060
      typedef typename Config::stored_vertex stored_vertex;
williamr@2
  2061
      typedef typename Config::EdgeContainer EdgeContainer;
williamr@2
  2062
      typedef typename Config::edge_property_type edge_property_type;
williamr@2
  2063
      typedef vec_adj_list_tag graph_tag;
williamr@2
  2064
williamr@2
  2065
      static vertex_descriptor null_vertex()
williamr@2
  2066
      {
williamr@2
  2067
        return (std::numeric_limits<vertex_descriptor>::max)();
williamr@2
  2068
      }
williamr@2
  2069
      
williamr@2
  2070
      inline vec_adj_list_impl() { }
williamr@2
  2071
williamr@2
  2072
      inline vec_adj_list_impl(const vec_adj_list_impl& x) {
williamr@2
  2073
        copy_impl(x);
williamr@2
  2074
      }
williamr@2
  2075
      inline vec_adj_list_impl& operator=(const vec_adj_list_impl& x) {
williamr@2
  2076
        this->clear();
williamr@2
  2077
        copy_impl(x);
williamr@2
  2078
        return *this;
williamr@2
  2079
      }
williamr@2
  2080
      inline void clear() {
williamr@2
  2081
        m_vertices.clear();
williamr@2
  2082
        m_edges.clear();
williamr@2
  2083
      }
williamr@2
  2084
williamr@2
  2085
      inline vec_adj_list_impl(vertices_size_type _num_vertices)
williamr@2
  2086
        : m_vertices(_num_vertices) { }
williamr@2
  2087
williamr@2
  2088
      template <class EdgeIterator>
williamr@2
  2089
      inline vec_adj_list_impl(vertices_size_type num_vertices,
williamr@2
  2090
                               EdgeIterator first, EdgeIterator last)
williamr@2
  2091
        : m_vertices(num_vertices)
williamr@2
  2092
      {
williamr@2
  2093
        while (first != last) {
williamr@2
  2094
          add_edge((*first).first, (*first).second, 
williamr@2
  2095
                   static_cast<Graph&>(*this));
williamr@2
  2096
          ++first;
williamr@2
  2097
        }
williamr@2
  2098
      }
williamr@2
  2099
      template <class EdgeIterator, class EdgePropertyIterator>
williamr@2
  2100
      inline vec_adj_list_impl(vertices_size_type num_vertices,
williamr@2
  2101
                               EdgeIterator first, EdgeIterator last,
williamr@2
  2102
                               EdgePropertyIterator ep_iter)
williamr@2
  2103
        : m_vertices(num_vertices)
williamr@2
  2104
      {
williamr@2
  2105
        while (first != last) {
williamr@2
  2106
          add_edge((*first).first, (*first).second, *ep_iter, 
williamr@2
  2107
                   static_cast<Graph&>(*this));
williamr@2
  2108
          ++first;
williamr@2
  2109
          ++ep_iter;
williamr@2
  2110
        }
williamr@2
  2111
      }
williamr@2
  2112
williamr@2
  2113
      //    protected:
williamr@2
  2114
      inline boost::integer_range<vertex_descriptor> vertex_set() const {
williamr@2
  2115
        return boost::integer_range<vertex_descriptor>(0, m_vertices.size());
williamr@2
  2116
      }
williamr@2
  2117
      inline OutEdgeList& out_edge_list(vertex_descriptor v) {
williamr@2
  2118
        return m_vertices[v].m_out_edges;
williamr@2
  2119
      }
williamr@2
  2120
      inline const OutEdgeList& out_edge_list(vertex_descriptor v) const {
williamr@2
  2121
        return m_vertices[v].m_out_edges;
williamr@2
  2122
      }
williamr@2
  2123
      inline void copy_impl(const vec_adj_list_impl& x_) 
williamr@2
  2124
      {
williamr@2
  2125
        const Graph& x = static_cast<const Graph&>(x_);
williamr@2
  2126
        // Copy the stored vertex objects by adding each vertex
williamr@2
  2127
        // and copying its property object.
williamr@2
  2128
        for (vertices_size_type i = 0; i < num_vertices(x); ++i) {
williamr@2
  2129
          vertex_descriptor v = add_vertex(*this);
williamr@2
  2130
          m_vertices[v].m_property = x.m_vertices[i].m_property;
williamr@2
  2131
        }
williamr@2
  2132
        // Copy the edges by adding each edge and copying its
williamr@2
  2133
        // property object.
williamr@2
  2134
        edge_iterator ei, ei_end;
williamr@2
  2135
        for (tie(ei, ei_end) = edges(x); ei != ei_end; ++ei) {
williamr@2
  2136
          edge_descriptor e;
williamr@2
  2137
          bool inserted; 
williamr@2
  2138
          tie(e, inserted) = add_edge(source(*ei,x), target(*ei,x) , *this);
williamr@2
  2139
          *((edge_property_type*)e.m_eproperty)
williamr@2
  2140
            = *((edge_property_type*)(*ei).m_eproperty);
williamr@2
  2141
        }
williamr@2
  2142
      }
williamr@2
  2143
      typename Config::EdgeContainer m_edges;
williamr@2
  2144
      StoredVertexList m_vertices;
williamr@2
  2145
    };
williamr@2
  2146
    // Had to make these non-members to avoid accidental instantiation
williamr@2
  2147
    // on SGI MIPSpro C++
williamr@2
  2148
    template <class G, class C, class B>
williamr@2
  2149
    inline typename C::InEdgeList& 
williamr@2
  2150
    in_edge_list(vec_adj_list_impl<G,C,B>& g, 
williamr@2
  2151
                 typename C::vertex_descriptor v) {
williamr@2
  2152
      return g.m_vertices[v].m_in_edges;
williamr@2
  2153
    }
williamr@2
  2154
    template <class G, class C, class B>
williamr@2
  2155
    inline const typename C::InEdgeList& 
williamr@2
  2156
    in_edge_list(const vec_adj_list_impl<G,C,B>& g, 
williamr@2
  2157
                 typename C::vertex_descriptor v) {
williamr@2
  2158
      return g.m_vertices[v].m_in_edges;
williamr@2
  2159
    }
williamr@2
  2160
williamr@2
  2161
      // O(1)
williamr@2
  2162
    template <class Graph, class Config, class Base>
williamr@2
  2163
    inline typename Config::vertex_descriptor
williamr@2
  2164
    add_vertex(vec_adj_list_impl<Graph, Config, Base>& g_) {
williamr@2
  2165
      Graph& g = static_cast<Graph&>(g_);
williamr@2
  2166
      g.m_vertices.resize(g.m_vertices.size() + 1);
williamr@2
  2167
      return g.m_vertices.size() - 1;
williamr@2
  2168
    }
williamr@2
  2169
williamr@2
  2170
    template <class Graph, class Config, class Base>
williamr@2
  2171
    inline typename Config::vertex_descriptor
williamr@2
  2172
    add_vertex(const typename Config::vertex_property_type& p,
williamr@2
  2173
               vec_adj_list_impl<Graph, Config, Base>& g_) {
williamr@2
  2174
      Graph& g = static_cast<Graph&>(g_);
williamr@2
  2175
      typedef typename Config::stored_vertex stored_vertex;
williamr@2
  2176
      g.m_vertices.push_back(stored_vertex(p));
williamr@2
  2177
      return g.m_vertices.size() - 1;
williamr@2
  2178
    }
williamr@2
  2179
williamr@2
  2180
    // Here we override the directed_graph_helper add_edge() function
williamr@2
  2181
    // so that the number of vertices is automatically changed if
williamr@2
  2182
    // either u or v is greater than the number of vertices.
williamr@2
  2183
    template <class Graph, class Config, class Base>
williamr@2
  2184
    inline std::pair<typename Config::edge_descriptor, bool>
williamr@2
  2185
    add_edge(typename Config::vertex_descriptor u, 
williamr@2
  2186
             typename Config::vertex_descriptor v,
williamr@2
  2187
             const typename Config::edge_property_type& p,
williamr@2
  2188
             vec_adj_list_impl<Graph, Config, Base>& g_)
williamr@2
  2189
    {
williamr@2
  2190
      BOOST_USING_STD_MAX();
williamr@2
  2191
      typename Config::vertex_descriptor x = max BOOST_PREVENT_MACRO_SUBSTITUTION(u, v);
williamr@2
  2192
      if (x >= num_vertices(g_))
williamr@2
  2193
        g_.m_vertices.resize(x + 1);
williamr@2
  2194
      adj_list_helper<Config, Base>& g = g_;
williamr@2
  2195
      return add_edge(u, v, p, g);
williamr@2
  2196
    }
williamr@2
  2197
    template <class Graph, class Config, class Base>
williamr@2
  2198
    inline std::pair<typename Config::edge_descriptor, bool>
williamr@2
  2199
    add_edge(typename Config::vertex_descriptor u, 
williamr@2
  2200
             typename Config::vertex_descriptor v,
williamr@2
  2201
             vec_adj_list_impl<Graph, Config, Base>& g_)
williamr@2
  2202
    {
williamr@2
  2203
      typename Config::edge_property_type p;
williamr@2
  2204
      return add_edge(u, v, p, g_);
williamr@2
  2205
    }
williamr@2
  2206
williamr@2
  2207
williamr@2
  2208
    // O(V + E)
williamr@2
  2209
    template <class Graph, class Config, class Base>
williamr@2
  2210
    inline void remove_vertex(typename Config::vertex_descriptor v,
williamr@2
  2211
                              vec_adj_list_impl<Graph, Config, Base>& g_)
williamr@2
  2212
    {
williamr@2
  2213
      typedef typename Config::directed_category Cat;
williamr@2
  2214
      Graph& g = static_cast<Graph&>(g_);
williamr@2
  2215
      detail::remove_vertex_dispatch(g, v, Cat());
williamr@2
  2216
    }
williamr@2
  2217
    // O(1)
williamr@2
  2218
    template <class Graph, class Config, class Base>
williamr@2
  2219
    inline typename Config::vertex_descriptor 
williamr@2
  2220
    vertex(typename Config::vertices_size_type n, 
williamr@2
  2221
           const vec_adj_list_impl<Graph, Config, Base>&)
williamr@2
  2222
    {
williamr@2
  2223
      return n;
williamr@2
  2224
    }
williamr@2
  2225
williamr@2
  2226
williamr@2
  2227
  namespace detail {
williamr@2
  2228
williamr@2
  2229
    //=========================================================================
williamr@2
  2230
    // Adjacency List Generator
williamr@2
  2231
williamr@2
  2232
    template <class Graph, class VertexListS, class OutEdgeListS,
williamr@2
  2233
              class DirectedS, class VertexProperty, class EdgeProperty, 
williamr@2
  2234
              class GraphProperty, class EdgeListS>
williamr@2
  2235
    struct adj_list_gen
williamr@2
  2236
    {
williamr@2
  2237
      typedef typename detail::is_random_access<VertexListS>::type 
williamr@2
  2238
        is_rand_access;
williamr@2
  2239
      typedef typename has_property<EdgeProperty>::type has_edge_property; 
williamr@2
  2240
      typedef typename DirectedS::is_directed_t DirectedT;
williamr@2
  2241
      typedef typename DirectedS::is_bidir_t BidirectionalT;
williamr@2
  2242
williamr@2
  2243
      struct config
williamr@2
  2244
      {
williamr@2
  2245
        typedef OutEdgeListS edgelist_selector;
williamr@2
  2246
        typedef EdgeListS global_edgelist_selector;
williamr@2
  2247
williamr@2
  2248
        typedef Graph graph_type;
williamr@2
  2249
        typedef EdgeProperty edge_property_type;
williamr@2
  2250
        typedef VertexProperty vertex_property_type;
williamr@2
  2251
        typedef GraphProperty graph_property_type;
williamr@2
  2252
        typedef std::size_t vertices_size_type;
williamr@2
  2253
williamr@2
  2254
        typedef adjacency_list_traits<OutEdgeListS, VertexListS, DirectedS> 
williamr@2
  2255
           Traits;
williamr@2
  2256
williamr@2
  2257
        typedef typename Traits::directed_category directed_category;
williamr@2
  2258
        typedef typename Traits::edge_parallel_category edge_parallel_category;
williamr@2
  2259
        typedef typename Traits::vertex_descriptor vertex_descriptor;
williamr@2
  2260
        typedef typename Traits::edge_descriptor edge_descriptor;
williamr@2
  2261
williamr@2
  2262
        typedef void* vertex_ptr; 
williamr@2
  2263
williamr@2
  2264
        // need to reorganize this to avoid instantiating stuff
williamr@2
  2265
        // that doesn't get used -JGS
williamr@2
  2266
williamr@2
  2267
        // VertexList and vertex_iterator
williamr@2
  2268
        typedef typename container_gen<VertexListS, 
williamr@2
  2269
          vertex_ptr>::type SeqVertexList;
williamr@2
  2270
        typedef boost::integer_range<std::size_t> RandVertexList;
williamr@2
  2271
        typedef typename boost::ct_if_t<is_rand_access,
williamr@2
  2272
          RandVertexList, SeqVertexList>::type VertexList;
williamr@2
  2273
williamr@2
  2274
        typedef typename VertexList::iterator vertex_iterator;
williamr@2
  2275
williamr@2
  2276
        // EdgeContainer and StoredEdge
williamr@2
  2277
williamr@2
  2278
        typedef typename container_gen<EdgeListS, 
williamr@2
  2279
          list_edge<vertex_descriptor, EdgeProperty> >::type EdgeContainer;
williamr@2
  2280
williamr@2
  2281
        typedef typename ct_and<DirectedT, 
williamr@2
  2282
             typename ct_not<BidirectionalT>::type >::type on_edge_storage;
williamr@2
  2283
williamr@2
  2284
        typedef typename boost::ct_if_t<on_edge_storage,
williamr@2
  2285
          std::size_t, typename EdgeContainer::size_type
williamr@2
  2286
        >::type edges_size_type;
williamr@2
  2287
williamr@2
  2288
        typedef typename EdgeContainer::iterator EdgeIter;
williamr@2
  2289
williamr@2
  2290
        typedef typename detail::is_random_access<EdgeListS>::type is_edge_ra;
williamr@2
  2291
williamr@2
  2292
        typedef typename boost::ct_if_t<on_edge_storage,
williamr@2
  2293
          stored_edge_property<vertex_descriptor, EdgeProperty>,
williamr@2
  2294
          typename boost::ct_if_t<is_edge_ra,
williamr@2
  2295
            stored_ra_edge_iter<vertex_descriptor, EdgeContainer, EdgeProperty>,
williamr@2
  2296
            stored_edge_iter<vertex_descriptor, EdgeIter, EdgeProperty>
williamr@2
  2297
          >::type
williamr@2
  2298
        >::type StoredEdge;
williamr@2
  2299
williamr@2
  2300
        // Adjacency Types
williamr@2
  2301
williamr@2
  2302
        typedef typename container_gen<OutEdgeListS, StoredEdge>::type 
williamr@2
  2303
          OutEdgeList;
williamr@2
  2304
        typedef typename OutEdgeList::size_type degree_size_type;
williamr@2
  2305
        typedef typename OutEdgeList::iterator OutEdgeIter;
williamr@2
  2306
williamr@2
  2307
        typedef boost::detail::iterator_traits<OutEdgeIter> OutEdgeIterTraits;
williamr@2
  2308
        typedef typename OutEdgeIterTraits::iterator_category OutEdgeIterCat;
williamr@2
  2309
        typedef typename OutEdgeIterTraits::difference_type OutEdgeIterDiff;
williamr@2
  2310
williamr@2
  2311
        typedef out_edge_iter<
williamr@2
  2312
            OutEdgeIter, vertex_descriptor, edge_descriptor, OutEdgeIterDiff
williamr@2
  2313
        > out_edge_iterator;
williamr@2
  2314
williamr@2
  2315
        typedef typename adjacency_iterator_generator<graph_type,
williamr@2
  2316
           vertex_descriptor, out_edge_iterator>::type adjacency_iterator;
williamr@2
  2317
williamr@2
  2318
        typedef OutEdgeList InEdgeList;
williamr@2
  2319
        typedef OutEdgeIter InEdgeIter;
williamr@2
  2320
        typedef OutEdgeIterCat InEdgeIterCat;
williamr@2
  2321
        typedef OutEdgeIterDiff InEdgeIterDiff;
williamr@2
  2322
williamr@2
  2323
        typedef in_edge_iter<
williamr@2
  2324
            InEdgeIter, vertex_descriptor, edge_descriptor, InEdgeIterDiff
williamr@2
  2325
        > in_edge_iterator;
williamr@2
  2326
williamr@2
  2327
        typedef typename inv_adjacency_iterator_generator<graph_type,
williamr@2
  2328
           vertex_descriptor, in_edge_iterator>::type inv_adjacency_iterator;
williamr@2
  2329
williamr@2
  2330
        // Edge Iterator
williamr@2
  2331
williamr@2
  2332
        typedef boost::detail::iterator_traits<EdgeIter> EdgeIterTraits;
williamr@2
  2333
        typedef typename EdgeIterTraits::iterator_category EdgeIterCat;
williamr@2
  2334
        typedef typename EdgeIterTraits::difference_type EdgeIterDiff;
williamr@2
  2335
williamr@2
  2336
        typedef undirected_edge_iter<
williamr@2
  2337
            EdgeIter
williamr@2
  2338
          , edge_descriptor
williamr@2
  2339
          , EdgeIterDiff          
williamr@2
  2340
        > UndirectedEdgeIter; // also used for bidirectional
williamr@2
  2341
williamr@2
  2342
        typedef adj_list_edge_iterator<vertex_iterator, out_edge_iterator, 
williamr@2
  2343
           graph_type> DirectedEdgeIter;
williamr@2
  2344
williamr@2
  2345
        typedef typename boost::ct_if_t<on_edge_storage,
williamr@2
  2346
          DirectedEdgeIter, UndirectedEdgeIter>::type edge_iterator;
williamr@2
  2347
williamr@2
  2348
        // stored_vertex and StoredVertexList
williamr@2
  2349
        typedef typename container_gen<VertexListS, vertex_ptr>::type
williamr@2
  2350
          SeqStoredVertexList;
williamr@2
  2351
        struct seq_stored_vertex {
williamr@2
  2352
          seq_stored_vertex() { }
williamr@2
  2353
          seq_stored_vertex(const VertexProperty& p) : m_property(p) { }
williamr@2
  2354
          OutEdgeList m_out_edges;
williamr@2
  2355
          VertexProperty m_property;
williamr@2
  2356
          typename SeqStoredVertexList::iterator m_position;
williamr@2
  2357
        };
williamr@2
  2358
        struct bidir_seq_stored_vertex {
williamr@2
  2359
          bidir_seq_stored_vertex() { }
williamr@2
  2360
          bidir_seq_stored_vertex(const VertexProperty& p) : m_property(p) { }
williamr@2
  2361
          OutEdgeList m_out_edges;
williamr@2
  2362
          InEdgeList m_in_edges;
williamr@2
  2363
          VertexProperty m_property;
williamr@2
  2364
          typename SeqStoredVertexList::iterator m_position;
williamr@2
  2365
        };
williamr@2
  2366
        struct rand_stored_vertex {
williamr@2
  2367
          rand_stored_vertex() { }
williamr@2
  2368
          rand_stored_vertex(const VertexProperty& p) : m_property(p) { }
williamr@2
  2369
          OutEdgeList m_out_edges;
williamr@2
  2370
          VertexProperty m_property;
williamr@2
  2371
        };
williamr@2
  2372
        struct bidir_rand_stored_vertex {
williamr@2
  2373
          bidir_rand_stored_vertex() { }
williamr@2
  2374
          bidir_rand_stored_vertex(const VertexProperty& p) : m_property(p) { }
williamr@2
  2375
          OutEdgeList m_out_edges;
williamr@2
  2376
          InEdgeList m_in_edges;
williamr@2
  2377
          VertexProperty m_property;
williamr@2
  2378
        };
williamr@2
  2379
        typedef typename boost::ct_if_t<is_rand_access,
williamr@2
  2380
          typename boost::ct_if_t<BidirectionalT,
williamr@2
  2381
            bidir_rand_stored_vertex, rand_stored_vertex>::type,
williamr@2
  2382
          typename boost::ct_if_t<BidirectionalT,
williamr@2
  2383
            bidir_seq_stored_vertex, seq_stored_vertex>::type
williamr@2
  2384
        >::type StoredVertex;
williamr@2
  2385
        struct stored_vertex : public StoredVertex {
williamr@2
  2386
          stored_vertex() { }
williamr@2
  2387
          stored_vertex(const VertexProperty& p) : StoredVertex(p) { }
williamr@2
  2388
        };
williamr@2
  2389
williamr@2
  2390
        typedef typename container_gen<VertexListS, stored_vertex>::type
williamr@2
  2391
          RandStoredVertexList;
williamr@2
  2392
        typedef typename boost::ct_if_t< is_rand_access,
williamr@2
  2393
          RandStoredVertexList, SeqStoredVertexList>::type StoredVertexList;
williamr@2
  2394
      }; // end of config
williamr@2
  2395
williamr@2
  2396
williamr@2
  2397
      typedef typename boost::ct_if_t<BidirectionalT,
williamr@2
  2398
        bidirectional_graph_helper_with_property<config>,
williamr@2
  2399
        typename boost::ct_if_t<DirectedT,
williamr@2
  2400
          directed_graph_helper<config>,
williamr@2
  2401
          undirected_graph_helper<config>
williamr@2
  2402
        >::type
williamr@2
  2403
      >::type DirectedHelper;
williamr@2
  2404
williamr@2
  2405
      typedef typename boost::ct_if_t<is_rand_access,
williamr@2
  2406
        vec_adj_list_impl<Graph, config, DirectedHelper>,
williamr@2
  2407
        adj_list_impl<Graph, config, DirectedHelper>
williamr@2
  2408
      >::type type;
williamr@2
  2409
williamr@2
  2410
    };
williamr@2
  2411
williamr@2
  2412
  } // namespace detail
williamr@2
  2413
williamr@2
  2414
    //=========================================================================
williamr@2
  2415
    // Vertex Property Maps
williamr@2
  2416
williamr@2
  2417
    template <class Graph, class ValueType, class Reference, class Tag>
williamr@2
  2418
    struct adj_list_vertex_property_map
williamr@2
  2419
      : public boost::put_get_helper<
williamr@2
  2420
          Reference,
williamr@2
  2421
          adj_list_vertex_property_map<Graph, ValueType, Reference, Tag>
williamr@2
  2422
        >
williamr@2
  2423
    {
williamr@2
  2424
      typedef typename Graph::stored_vertex StoredVertex;
williamr@2
  2425
      typedef ValueType value_type;
williamr@2
  2426
      typedef Reference reference;
williamr@2
  2427
      typedef typename Graph::vertex_descriptor key_type;
williamr@2
  2428
      typedef boost::lvalue_property_map_tag category;
williamr@2
  2429
      inline adj_list_vertex_property_map() { }
williamr@2
  2430
      inline adj_list_vertex_property_map(const Graph*) { }
williamr@2
  2431
      inline Reference operator[](key_type v) const {
williamr@2
  2432
        StoredVertex* sv = (StoredVertex*)v;
williamr@2
  2433
        return get_property_value(sv->m_property, Tag());
williamr@2
  2434
      }
williamr@2
  2435
      inline Reference operator()(key_type v) const {
williamr@2
  2436
        return this->operator[](v);
williamr@2
  2437
      }
williamr@2
  2438
    };
williamr@2
  2439
williamr@2
  2440
    template <class Graph, class Property, class PropRef>
williamr@2
  2441
    struct adj_list_vertex_all_properties_map
williamr@2
  2442
      : public boost::put_get_helper<PropRef,
williamr@2
  2443
          adj_list_vertex_all_properties_map<Graph, Property, PropRef>
williamr@2
  2444
        >
williamr@2
  2445
    {
williamr@2
  2446
      typedef typename Graph::stored_vertex StoredVertex;
williamr@2
  2447
      typedef Property value_type;
williamr@2
  2448
      typedef PropRef reference;
williamr@2
  2449
      typedef typename Graph::vertex_descriptor key_type;
williamr@2
  2450
      typedef boost::lvalue_property_map_tag category;
williamr@2
  2451
      inline adj_list_vertex_all_properties_map() { }
williamr@2
  2452
      inline adj_list_vertex_all_properties_map(const Graph*) { }
williamr@2
  2453
      inline PropRef operator[](key_type v) const {
williamr@2
  2454
        StoredVertex* sv = (StoredVertex*)v;
williamr@2
  2455
        return sv->m_property;
williamr@2
  2456
      }
williamr@2
  2457
      inline PropRef operator()(key_type v) const {
williamr@2
  2458
        return this->operator[](v);
williamr@2
  2459
      }
williamr@2
  2460
    };
williamr@2
  2461
williamr@2
  2462
    template <class Graph, class GraphPtr, class ValueType, class Reference,
williamr@2
  2463
              class Tag>
williamr@2
  2464
    struct vec_adj_list_vertex_property_map
williamr@2
  2465
      : public boost::put_get_helper<
williamr@2
  2466
          Reference,
williamr@2
  2467
          vec_adj_list_vertex_property_map<Graph,GraphPtr,ValueType,Reference,
williamr@2
  2468
             Tag>
williamr@2
  2469
        >
williamr@2
  2470
    {
williamr@2
  2471
      typedef ValueType value_type;
williamr@2
  2472
      typedef Reference reference;
williamr@2
  2473
      typedef typename boost::graph_traits<Graph>::vertex_descriptor key_type;
williamr@2
  2474
      typedef boost::lvalue_property_map_tag category;
williamr@2
  2475
      vec_adj_list_vertex_property_map() { }
williamr@2
  2476
      vec_adj_list_vertex_property_map(GraphPtr g) : m_g(g) { }
williamr@2
  2477
      inline Reference operator[](key_type v) const {
williamr@2
  2478
        return get_property_value(m_g->m_vertices[v].m_property,  Tag());
williamr@2
  2479
      }
williamr@2
  2480
      inline Reference operator()(key_type v) const {
williamr@2
  2481
        return this->operator[](v);
williamr@2
  2482
      }
williamr@2
  2483
      GraphPtr m_g;
williamr@2
  2484
    };
williamr@2
  2485
williamr@2
  2486
    template <class Graph, class GraphPtr, class Property, class PropertyRef>
williamr@2
  2487
    struct vec_adj_list_vertex_all_properties_map
williamr@2
  2488
      : public boost::put_get_helper<PropertyRef,
williamr@2
  2489
          vec_adj_list_vertex_all_properties_map<Graph,GraphPtr,Property,
williamr@2
  2490
            PropertyRef>
williamr@2
  2491
        >
williamr@2
  2492
    {
williamr@2
  2493
      typedef Property value_type;
williamr@2
  2494
      typedef PropertyRef reference;
williamr@2
  2495
      typedef typename boost::graph_traits<Graph>::vertex_descriptor key_type;
williamr@2
  2496
      typedef boost::lvalue_property_map_tag category;
williamr@2
  2497
      vec_adj_list_vertex_all_properties_map() { }
williamr@2
  2498
      vec_adj_list_vertex_all_properties_map(GraphPtr g) : m_g(g) { }
williamr@2
  2499
      inline PropertyRef operator[](key_type v) const {
williamr@2
  2500
        return m_g->m_vertices[v].m_property;
williamr@2
  2501
      }
williamr@2
  2502
      inline PropertyRef operator()(key_type v) const {
williamr@2
  2503
        return this->operator[](v);
williamr@2
  2504
      }
williamr@2
  2505
      GraphPtr m_g;
williamr@2
  2506
    };
williamr@2
  2507
williamr@2
  2508
    struct adj_list_any_vertex_pa {
williamr@2
  2509
      template <class Tag, class Graph, class Property>
williamr@2
  2510
      struct bind_ {
williamr@2
  2511
        typedef typename property_value<Property, Tag>::type value_type;
williamr@2
  2512
        typedef value_type& reference;
williamr@2
  2513
        typedef const value_type& const_reference;
williamr@2
  2514
williamr@2
  2515
        typedef adj_list_vertex_property_map
williamr@2
  2516
          <Graph, value_type, reference, Tag> type;
williamr@2
  2517
        typedef adj_list_vertex_property_map
williamr@2
  2518
          <Graph, value_type, const_reference, Tag> const_type;
williamr@2
  2519
      };
williamr@2
  2520
    };
williamr@2
  2521
    struct adj_list_all_vertex_pa {
williamr@2
  2522
      template <class Tag, class Graph, class Property>
williamr@2
  2523
      struct bind_ {
williamr@2
  2524
        typedef typename Graph::vertex_descriptor Vertex;
williamr@2
  2525
        typedef adj_list_vertex_all_properties_map<Graph,Property,
williamr@2
  2526
          Property&> type;
williamr@2
  2527
        typedef adj_list_vertex_all_properties_map<Graph,Property,
williamr@2
  2528
          const Property&> const_type;
williamr@2
  2529
      };
williamr@2
  2530
    };
williamr@2
  2531
williamr@2
  2532
    template <class Property, class Vertex>
williamr@2
  2533
    struct vec_adj_list_vertex_id_map
williamr@2
  2534
      : public boost::put_get_helper<
williamr@2
  2535
          Vertex, vec_adj_list_vertex_id_map<Property, Vertex>
williamr@2
  2536
        >
williamr@2
  2537
    {
williamr@2
  2538
      typedef Vertex value_type;
williamr@2
  2539
      typedef Vertex key_type;
williamr@2
  2540
      typedef Vertex reference;
williamr@2
  2541
      typedef boost::readable_property_map_tag category;
williamr@2
  2542
      inline vec_adj_list_vertex_id_map() { }
williamr@2
  2543
      template <class Graph>
williamr@2
  2544
      inline vec_adj_list_vertex_id_map(const Graph&) { }
williamr@2
  2545
      inline value_type operator[](key_type v) const { return v; }
williamr@2
  2546
      inline value_type operator()(key_type v) const { return v; }
williamr@2
  2547
    };
williamr@2
  2548
williamr@2
  2549
    struct vec_adj_list_any_vertex_pa {
williamr@2
  2550
      template <class Tag, class Graph, class Property>
williamr@2
  2551
      struct bind_ {
williamr@2
  2552
        typedef typename property_value<Property, Tag>::type value_type;
williamr@2
  2553
        typedef value_type& reference;
williamr@2
  2554
        typedef const value_type& const_reference;
williamr@2
  2555
williamr@2
  2556
        typedef vec_adj_list_vertex_property_map
williamr@2
  2557
          <Graph, Graph*, value_type, reference, Tag> type;
williamr@2
  2558
        typedef vec_adj_list_vertex_property_map
williamr@2
  2559
          <Graph, const Graph*, value_type, const_reference, Tag> const_type;
williamr@2
  2560
      };
williamr@2
  2561
    };
williamr@2
  2562
    struct vec_adj_list_id_vertex_pa {
williamr@2
  2563
      template <class Tag, class Graph, class Property>
williamr@2
  2564
      struct bind_ {
williamr@2
  2565
        typedef typename Graph::vertex_descriptor Vertex;
williamr@2
  2566
        typedef vec_adj_list_vertex_id_map<Property, Vertex> type;
williamr@2
  2567
        typedef vec_adj_list_vertex_id_map<Property, Vertex> const_type;
williamr@2
  2568
      };
williamr@2
  2569
    };
williamr@2
  2570
    struct vec_adj_list_all_vertex_pa {
williamr@2
  2571
      template <class Tag, class Graph, class Property>
williamr@2
  2572
      struct bind_ {
williamr@2
  2573
        typedef typename Graph::vertex_descriptor Vertex;
williamr@2
  2574
        typedef vec_adj_list_vertex_all_properties_map
williamr@2
  2575
          <Graph, Graph*, Property, Property&> type;
williamr@2
  2576
        typedef vec_adj_list_vertex_all_properties_map
williamr@2
  2577
          <Graph, const Graph*, Property, const Property&> const_type;
williamr@2
  2578
      };
williamr@2
  2579
    };
williamr@2
  2580
  namespace detail {
williamr@2
  2581
    template <class Tag>
williamr@2
  2582
    struct adj_list_choose_vertex_pa_helper {
williamr@2
  2583
      typedef adj_list_any_vertex_pa type;
williamr@2
  2584
    };
williamr@2
  2585
    template <>
williamr@2
  2586
    struct adj_list_choose_vertex_pa_helper<vertex_all_t> {
williamr@2
  2587
      typedef adj_list_all_vertex_pa type;
williamr@2
  2588
    };
williamr@2
  2589
    template <class Tag, class Graph, class Property>
williamr@2
  2590
    struct adj_list_choose_vertex_pa {
williamr@2
  2591
      typedef typename adj_list_choose_vertex_pa_helper<Tag>::type Helper;
williamr@2
  2592
      typedef typename Helper::template bind_<Tag,Graph,Property> Bind;
williamr@2
  2593
      typedef typename Bind::type type;
williamr@2
  2594
      typedef typename Bind::const_type const_type;
williamr@2
  2595
    };
williamr@2
  2596
williamr@2
  2597
williamr@2
  2598
    template <class Tag>
williamr@2
  2599
    struct vec_adj_list_choose_vertex_pa_helper {
williamr@2
  2600
      typedef vec_adj_list_any_vertex_pa type;
williamr@2
  2601
    };
williamr@2
  2602
    template <>
williamr@2
  2603
    struct vec_adj_list_choose_vertex_pa_helper<vertex_index_t> {
williamr@2
  2604
      typedef vec_adj_list_id_vertex_pa type;
williamr@2
  2605
    };
williamr@2
  2606
    template <>
williamr@2
  2607
    struct vec_adj_list_choose_vertex_pa_helper<vertex_all_t> {
williamr@2
  2608
      typedef vec_adj_list_all_vertex_pa type;
williamr@2
  2609
    };
williamr@2
  2610
    template <class Tag, class Graph, class Property>
williamr@2
  2611
    struct vec_adj_list_choose_vertex_pa {
williamr@2
  2612
      typedef typename vec_adj_list_choose_vertex_pa_helper<Tag>::type Helper;
williamr@2
  2613
      typedef typename Helper::template bind_<Tag,Graph,Property> Bind;
williamr@2
  2614
      typedef typename Bind::type type;
williamr@2
  2615
      typedef typename Bind::const_type const_type;
williamr@2
  2616
    };
williamr@2
  2617
  } // namespace detail
williamr@2
  2618
    
williamr@2
  2619
    //=========================================================================
williamr@2
  2620
    // Edge Property Map
williamr@2
  2621
williamr@2
  2622
    template <class Directed, class Value, class Ref, class Vertex,
williamr@2
  2623
              class Property, class Tag>
williamr@2
  2624
    struct adj_list_edge_property_map
williamr@2
  2625
      : public put_get_helper< 
williamr@2
  2626
          Ref,
williamr@2
  2627
          adj_list_edge_property_map<Directed, Value, Ref, Vertex, Property, 
williamr@2
  2628
            Tag>
williamr@2
  2629
        >
williamr@2
  2630
    {
williamr@2
  2631
      typedef Value value_type;
williamr@2
  2632
      typedef Ref reference;
williamr@2
  2633
      typedef detail::edge_desc_impl<Directed, Vertex> key_type;
williamr@2
  2634
      typedef boost::lvalue_property_map_tag category;
williamr@2
  2635
      inline Ref operator[](key_type e) const {
williamr@2
  2636
        Property& p = *(Property*)e.get_property();
williamr@2
  2637
        return get_property_value(p, Tag());
williamr@2
  2638
      }
williamr@2
  2639
      inline Ref operator()(key_type e) const {
williamr@2
  2640
        return this->operator[](e);
williamr@2
  2641
      }
williamr@2
  2642
    };
williamr@2
  2643
williamr@2
  2644
    template <class Directed, class Property, class PropRef, class PropPtr,
williamr@2
  2645
      class Vertex>
williamr@2
  2646
    struct adj_list_edge_all_properties_map
williamr@2
  2647
      : public put_get_helper<PropRef,
williamr@2
  2648
          adj_list_edge_all_properties_map<Directed, Property, PropRef, 
williamr@2
  2649
            PropPtr, Vertex>
williamr@2
  2650
        >
williamr@2
  2651
    {
williamr@2
  2652
      typedef Property value_type;
williamr@2
  2653
      typedef PropRef reference;
williamr@2
  2654
      typedef detail::edge_desc_impl<Directed, Vertex> key_type;
williamr@2
  2655
      typedef boost::lvalue_property_map_tag category;
williamr@2
  2656
      inline PropRef operator[](key_type e) const {
williamr@2
  2657
        return *(PropPtr)e.get_property();
williamr@2
  2658
      }
williamr@2
  2659
      inline PropRef operator()(key_type e) const {
williamr@2
  2660
        return this->operator[](e);
williamr@2
  2661
      }
williamr@2
  2662
    };
williamr@2
  2663
williamr@2
  2664
  // Edge Property Maps
williamr@2
  2665
williamr@2
  2666
  namespace detail {
williamr@2
  2667
    struct adj_list_any_edge_pmap {
williamr@2
  2668
      template <class Graph, class Property, class Tag>
williamr@2
  2669
      struct bind_ {
williamr@2
  2670
        typedef typename property_value<Property,Tag>::type value_type;
williamr@2
  2671
        typedef value_type& reference;
williamr@2
  2672
        typedef const value_type& const_reference;
williamr@2
  2673
        
williamr@2
  2674
        typedef adj_list_edge_property_map
williamr@2
  2675
           <typename Graph::directed_category, value_type, reference, 
williamr@2
  2676
            typename Graph::vertex_descriptor,Property,Tag> type;
williamr@2
  2677
        typedef adj_list_edge_property_map
williamr@2
  2678
           <typename Graph::directed_category, value_type, const_reference, 
williamr@2
  2679
            typename Graph::vertex_descriptor,const Property, Tag> const_type;
williamr@2
  2680
      };
williamr@2
  2681
    };
williamr@2
  2682
    struct adj_list_all_edge_pmap {
williamr@2
  2683
      template <class Graph, class Property, class Tag>
williamr@2
  2684
      struct bind_ {
williamr@2
  2685
        typedef adj_list_edge_all_properties_map
williamr@2
  2686
        <typename Graph::directed_category, Property, Property&, Property*,
williamr@2
  2687
            typename Graph::vertex_descriptor> type;
williamr@2
  2688
        typedef adj_list_edge_all_properties_map
williamr@2
  2689
        <typename Graph::directed_category, Property, const Property&, 
williamr@2
  2690
            const Property*, typename Graph::vertex_descriptor> const_type;
williamr@2
  2691
      };
williamr@2
  2692
    };
williamr@2
  2693
williamr@2
  2694
    template <class Tag>
williamr@2
  2695
    struct adj_list_choose_edge_pmap_helper {
williamr@2
  2696
      typedef adj_list_any_edge_pmap type;
williamr@2
  2697
    };
williamr@2
  2698
    template <>
williamr@2
  2699
    struct adj_list_choose_edge_pmap_helper<edge_all_t> {
williamr@2
  2700
      typedef adj_list_all_edge_pmap type;
williamr@2
  2701
    };
williamr@2
  2702
    template <class Tag, class Graph, class Property>
williamr@2
  2703
    struct adj_list_choose_edge_pmap {
williamr@2
  2704
      typedef typename adj_list_choose_edge_pmap_helper<Tag>::type Helper;
williamr@2
  2705
      typedef typename Helper::template bind_<Graph,Property,Tag> Bind;
williamr@2
  2706
      typedef typename Bind::type type;
williamr@2
  2707
      typedef typename Bind::const_type const_type;
williamr@2
  2708
    };
williamr@2
  2709
    struct adj_list_edge_property_selector {
williamr@2
  2710
      template <class Graph, class Property, class Tag>
williamr@2
  2711
      struct bind_ {
williamr@2
  2712
        typedef adj_list_choose_edge_pmap<Tag,Graph,Property> Choice;
williamr@2
  2713
        typedef typename Choice::type type;
williamr@2
  2714
        typedef typename Choice::const_type const_type;
williamr@2
  2715
      };
williamr@2
  2716
    };
williamr@2
  2717
  } // namespace detail
williamr@2
  2718
williamr@2
  2719
  template <>  
williamr@2
  2720
  struct edge_property_selector<adj_list_tag> {
williamr@2
  2721
    typedef detail::adj_list_edge_property_selector type;
williamr@2
  2722
  };
williamr@2
  2723
  template <>  
williamr@2
  2724
  struct edge_property_selector<vec_adj_list_tag> {
williamr@2
  2725
    typedef detail::adj_list_edge_property_selector type;
williamr@2
  2726
  };
williamr@2
  2727
williamr@2
  2728
  // Vertex Property Maps
williamr@2
  2729
williamr@2
  2730
  struct adj_list_vertex_property_selector {
williamr@2
  2731
    template <class Graph, class Property, class Tag>
williamr@2
  2732
    struct bind_ {
williamr@2
  2733
      typedef detail::adj_list_choose_vertex_pa<Tag,Graph,Property> Choice;
williamr@2
  2734
      typedef typename Choice::type type;
williamr@2
  2735
      typedef typename Choice::const_type const_type;
williamr@2
  2736
    };
williamr@2
  2737
  };
williamr@2
  2738
  template <>  
williamr@2
  2739
  struct vertex_property_selector<adj_list_tag> {
williamr@2
  2740
    typedef adj_list_vertex_property_selector type;
williamr@2
  2741
  };
williamr@2
  2742
williamr@2
  2743
  struct vec_adj_list_vertex_property_selector {
williamr@2
  2744
    template <class Graph, class Property, class Tag>
williamr@2
  2745
    struct bind_ {
williamr@2
  2746
      typedef detail::vec_adj_list_choose_vertex_pa<Tag,Graph,Property> Choice;
williamr@2
  2747
      typedef typename Choice::type type;
williamr@2
  2748
      typedef typename Choice::const_type const_type;
williamr@2
  2749
    };
williamr@2
  2750
  };
williamr@2
  2751
  template <>  
williamr@2
  2752
  struct vertex_property_selector<vec_adj_list_tag> {
williamr@2
  2753
    typedef vec_adj_list_vertex_property_selector type;
williamr@2
  2754
  };
williamr@2
  2755
williamr@2
  2756
} // namespace boost
williamr@2
  2757
williamr@2
  2758
#if !defined(BOOST_NO_HASH) && !defined(BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION)
williamr@2
  2759
namespace BOOST_STD_EXTENSION_NAMESPACE {
williamr@2
  2760
williamr@2
  2761
  #if BOOST_WORKAROUND( _STLPORT_VERSION, >= 0x500 )
williamr@2
  2762
  // STLport 5 already defines a hash<void*> specialization.
williamr@2
  2763
  #else
williamr@2
  2764
  template <>
williamr@2
  2765
  struct hash< void* > // Need this when vertex_descriptor=void*
williamr@2
  2766
  {
williamr@2
  2767
    std::size_t
williamr@2
  2768
    operator()(void* v) const { return (std::size_t)v; }
williamr@2
  2769
  };
williamr@2
  2770
  #endif
williamr@2
  2771
williamr@2
  2772
  template <typename V>
williamr@2
  2773
  struct hash< boost::detail::stored_edge<V> > 
williamr@2
  2774
  {
williamr@2
  2775
    std::size_t
williamr@2
  2776
    operator()(const boost::detail::stored_edge<V>& e) const
williamr@2
  2777
    {
williamr@2
  2778
      return hash<V>()(e.m_target);
williamr@2
  2779
    }
williamr@2
  2780
  };
williamr@2
  2781
williamr@2
  2782
  template <typename V, typename P>
williamr@2
  2783
  struct hash< boost::detail::stored_edge_property <V,P> > 
williamr@2
  2784
  {
williamr@2
  2785
    std::size_t
williamr@2
  2786
    operator()(const boost::detail::stored_edge_property<V,P>& e) const
williamr@2
  2787
    {
williamr@2
  2788
      return hash<V>()(e.m_target);
williamr@2
  2789
    }
williamr@2
  2790
  };
williamr@2
  2791
williamr@2
  2792
  template <typename V, typename I, typename P>
williamr@2
  2793
  struct hash< boost::detail::stored_edge_iter<V,I, P> > 
williamr@2
  2794
  {
williamr@2
  2795
    std::size_t
williamr@2
  2796
    operator()(const boost::detail::stored_edge_iter<V,I,P>& e) const
williamr@2
  2797
    {
williamr@2
  2798
      return hash<V>()(e.m_target);
williamr@2
  2799
    }
williamr@2
  2800
  };
williamr@2
  2801
williamr@2
  2802
}
williamr@2
  2803
#endif
williamr@2
  2804
williamr@2
  2805
williamr@2
  2806
#undef stored_edge
williamr@2
  2807
#undef stored_edge_property
williamr@2
  2808
#undef stored_edge_iter
williamr@2
  2809
williamr@2
  2810
#endif // BOOST_GRAPH_DETAIL_DETAIL_ADJACENCY_LIST_CCT
williamr@2
  2811
williamr@2
  2812
/*
williamr@2
  2813
  Implementation Notes:
williamr@2
  2814
  
williamr@2
  2815
  Many of the public interface functions in this file would have been
williamr@2
  2816
  more conveniently implemented as inline friend functions.
williamr@2
  2817
  However there are a few compiler bugs that make that approach
williamr@2
  2818
  non-portable.
williamr@2
  2819
 
williamr@2
  2820
  1. g++ inline friend in namespace bug
williamr@2
  2821
  2. g++ using clause doesn't work with inline friends
williamr@2
  2822
  3. VC++ doesn't have Koenig lookup
williamr@2
  2823
williamr@2
  2824
  For these reasons, the functions were all written as non-inline free 
williamr@2
  2825
  functions, and static cast was used to convert from the helper
williamr@2
  2826
  class to the adjacency_list derived class.
williamr@2
  2827
williamr@2
  2828
  Looking back, it might have been better to write out all functions
williamr@2
  2829
  in terms of the adjacency_list, and then use a tag to dispatch
williamr@2
  2830
  to the various helpers instead of using inheritance.
williamr@2
  2831
williamr@2
  2832
 */