source: NonGTP/Boost/boost/graph/detail/adjacency_list.hpp @ 857

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