Ugly, not-to-be-pushed sucking in of all of Boost to get windows to work.
[dyninst.git] / external / boost / graph / detail / adjacency_list.hpp
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
66 namespace 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)
2671 namespace 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  */