2 //=======================================================================
3 // Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
4 // Copyright 2010 Thomas Claveirole
5 // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek, Thomas Claveirole
7 // Distributed under the Boost Software License, Version 1.0. (See
8 // accompanying file LICENSE_1_0.txt or copy at
9 // http://www.boost.org/LICENSE_1_0.txt)
10 //=======================================================================
12 #ifndef BOOST_GRAPH_DETAIL_ADJACENCY_LIST_HPP
13 #define BOOST_GRAPH_DETAIL_ADJACENCY_LIST_HPP
15 #include <map> // for vertex_map in copy_impl
16 #include <boost/config.hpp>
17 #include <boost/detail/workaround.hpp>
18 #include <boost/operators.hpp>
19 #include <boost/property_map/property_map.hpp>
20 #include <boost/pending/container_traits.hpp>
21 #include <boost/range/irange.hpp>
22 #include <boost/graph/graph_traits.hpp>
25 #include <boost/limits.hpp>
27 #include <boost/iterator/iterator_adaptor.hpp>
29 #include <boost/mpl/if.hpp>
30 #include <boost/mpl/not.hpp>
31 #include <boost/mpl/and.hpp>
32 #include <boost/graph/graph_concepts.hpp>
33 #include <boost/pending/container_traits.hpp>
34 #include <boost/graph/detail/adj_list_edge_iterator.hpp>
35 #include <boost/graph/properties.hpp>
36 #include <boost/pending/property.hpp>
37 #include <boost/graph/adjacency_iterator.hpp>
38 #include <boost/static_assert.hpp>
39 #include <boost/assert.hpp>
41 #ifdef BOOST_NO_CXX11_RVALUE_REFERENCES
42 #define BOOST_GRAPH_MOVE_IF_POSSIBLE(x) (x)
45 #define BOOST_GRAPH_MOVE_IF_POSSIBLE(x) (std::move((x)))
49 Outline for this file:
51 out_edge_iterator and in_edge_iterator implementation
52 edge_iterator for undirected graph
53 stored edge types (these object live in the out-edge/in-edge lists)
54 directed edges helper class
55 directed graph helper class
56 undirected graph helper class
57 bidirectional graph helper class
58 bidirectional graph helper class (without edge properties)
59 bidirectional graph helper class (with edge properties)
60 adjacency_list helper class
62 vec_adj_list_impl class
68 Note: it would be nice to merge some of the undirected and
69 bidirectional code... it is awful similar.
77 template <typename DirectedS>
78 struct directed_category_traits {
79 typedef directed_tag directed_category;
83 struct directed_category_traits<directedS> {
84 typedef directed_tag directed_category;
87 struct directed_category_traits<undirectedS> {
88 typedef undirected_tag directed_category;
91 struct directed_category_traits<bidirectionalS> {
92 typedef bidirectional_tag directed_category;
95 template <class Vertex>
97 target_is(const Vertex& v) : m_target(v) { }
98 template <class StoredEdge>
99 bool operator()(const StoredEdge& e) const {
100 return e.get_target() == m_target;
106 template <class EdgeList, class vertex_descriptor>
107 void erase_from_incidence_list(EdgeList& el, vertex_descriptor v,
108 allow_parallel_edge_tag)
110 boost::graph_detail::erase_if(el, detail::target_is<vertex_descriptor>(v));
113 template <class EdgeList, class vertex_descriptor>
114 void erase_from_incidence_list(EdgeList& el, vertex_descriptor v,
115 disallow_parallel_edge_tag)
117 typedef typename EdgeList::value_type StoredEdge;
118 el.erase(StoredEdge(v));
121 //=========================================================================
122 // Out-Edge and In-Edge Iterator Implementation
124 template <class BaseIter, class VertexDescriptor, class EdgeDescriptor, class Difference>
127 out_edge_iter<BaseIter, VertexDescriptor, EdgeDescriptor, Difference>
135 typedef iterator_adaptor<
136 out_edge_iter<BaseIter, VertexDescriptor, EdgeDescriptor, Difference>
144 inline out_edge_iter() { }
145 inline out_edge_iter(const BaseIter& i, const VertexDescriptor& src)
146 : super_t(i), m_src(src) { }
148 inline EdgeDescriptor
151 return EdgeDescriptor(m_src, (*this->base()).get_target(),
152 &(*this->base()).get_property());
154 VertexDescriptor m_src;
157 template <class BaseIter, class VertexDescriptor, class EdgeDescriptor, class Difference>
160 in_edge_iter<BaseIter, VertexDescriptor, EdgeDescriptor, Difference>
168 typedef iterator_adaptor<
169 in_edge_iter<BaseIter, VertexDescriptor, EdgeDescriptor, Difference>
177 inline in_edge_iter() { }
178 inline in_edge_iter(const BaseIter& i, const VertexDescriptor& src)
179 : super_t(i), m_src(src) { }
181 inline EdgeDescriptor
184 return EdgeDescriptor((*this->base()).get_target(), m_src,
185 &this->base()->get_property());
187 VertexDescriptor m_src;
190 //=========================================================================
191 // Undirected Edge Iterator Implementation
193 template <class EdgeIter, class EdgeDescriptor, class Difference>
194 struct undirected_edge_iter
196 undirected_edge_iter<EdgeIter, EdgeDescriptor, Difference>
204 typedef iterator_adaptor<
205 undirected_edge_iter<EdgeIter, EdgeDescriptor, Difference>
213 undirected_edge_iter() {}
215 explicit undirected_edge_iter(EdgeIter i)
218 inline EdgeDescriptor
219 dereference() const {
220 return EdgeDescriptor(
221 (*this->base()).m_source
222 , (*this->base()).m_target
223 , &this->base()->get_property());
227 //=========================================================================
228 // Edge Storage Types (stored in the out-edge/in-edge lists)
230 template <class Vertex>
232 : public boost::equality_comparable1< stored_edge<Vertex>,
233 boost::less_than_comparable1< stored_edge<Vertex> > >
236 typedef no_property property_type;
237 inline stored_edge() { }
238 inline stored_edge(Vertex target, const no_property& = no_property())
239 : m_target(target) { }
240 inline Vertex& get_target() const { return m_target; }
241 inline const no_property& get_property() const { return s_prop; }
242 inline bool operator==(const stored_edge& x) const
243 { return m_target == x.get_target(); }
244 inline bool operator<(const stored_edge& x) const
245 { return m_target < x.get_target(); }
246 //protected: need to add hash<> as a friend
247 static no_property s_prop;
248 // Sometimes target not used as key in the set, and in that case
249 // it is ok to change the target.
250 mutable Vertex m_target;
252 template <class Vertex>
253 no_property stored_edge<Vertex>::s_prop;
255 #if defined(BOOST_NO_CXX11_RVALUE_REFERENCES) || defined(BOOST_NO_CXX11_SMART_PTR)
256 template <class Vertex, class Property>
257 class stored_edge_property : public stored_edge<Vertex> {
258 typedef stored_edge_property self;
259 typedef stored_edge<Vertex> Base;
261 typedef Property property_type;
262 inline stored_edge_property() { }
263 inline stored_edge_property(Vertex target,
264 const Property& p = Property())
265 : stored_edge<Vertex>(target), m_property(new Property(p)) { }
266 stored_edge_property(const self& x)
267 : Base(static_cast< Base const& >(x)), m_property(const_cast<self&>(x).m_property) { }
268 self& operator=(const self& x) {
269 // NOTE: avoid 'Base::operator=(x);' broken on SGI MIPSpro (bug 55771 of Mozilla).
270 static_cast<Base&>(*this) = static_cast< Base const& >(x);
271 m_property = const_cast<self&>(x).m_property;
274 #if !defined(BOOST_NO_CXX11_RVALUE_REFERENCES)
275 // NOTE Don't rely on default operators, their behavior is broken on several compilers (GCC 4.6).
276 stored_edge_property(self&& x)
277 : Base(static_cast< Base&& >(x)), m_property(std::move(x.m_property)) { }
278 self& operator=(self&& x) {
279 // NOTE: avoid 'Base::operator=(x);' broken on SGI MIPSpro (bug 55771 of Mozilla).
280 static_cast<Base&>(*this) = static_cast< Base&& >(x);
281 m_property = std::move(x.m_property);
285 inline Property& get_property() { return *m_property; }
286 inline const Property& get_property() const { return *m_property; }
288 // Holding the property by-value causes edge-descriptor
289 // invalidation for add_edge() with EdgeList=vecS. Instead we
290 // hold a pointer to the property. std::auto_ptr is not
291 // a perfect fit for the job, but it is darn close.
292 std::auto_ptr<Property> m_property;
295 template <class Vertex, class Property>
296 class stored_edge_property : public stored_edge<Vertex> {
297 typedef stored_edge_property self;
298 typedef stored_edge<Vertex> Base;
300 typedef Property property_type;
301 inline stored_edge_property() { }
302 inline stored_edge_property(Vertex target,
303 const Property& p = Property())
304 : stored_edge<Vertex>(target), m_property(new Property(p)) { }
305 stored_edge_property(self&& x) : Base(static_cast< Base&& >(x)),
306 m_property(std::move(x.m_property)) { }
307 stored_edge_property(self const& x) : Base(static_cast< Base const& >(x)),
308 m_property(std::move(const_cast<self&>(x).m_property)) { }
309 self& operator=(self&& x) {
310 // NOTE: avoid 'Base::operator=(x);' broken on SGI MIPSpro (bug 55771 of Mozilla).
311 static_cast<Base&>(*this) = static_cast< Base&& >(x);
312 m_property = std::move(x.m_property);
315 self& operator=(self const& x) {
316 // NOTE: avoid 'Base::operator=(x);' broken on SGI MIPSpro (bug 55771 of Mozilla).
317 static_cast<Base&>(*this) = static_cast< Base const& >(x);
318 m_property = std::move(const_cast<self&>(x).m_property);
321 inline Property& get_property() { return *m_property; }
322 inline const Property& get_property() const { return *m_property; }
324 std::unique_ptr<Property> m_property;
329 template <class Vertex, class Iter, class Property>
330 class stored_edge_iter
331 : public stored_edge<Vertex>
334 typedef Property property_type;
335 inline stored_edge_iter() { }
336 inline stored_edge_iter(Vertex v)
337 : stored_edge<Vertex>(v) { }
338 inline stored_edge_iter(Vertex v, Iter i, void* = 0)
339 : stored_edge<Vertex>(v), m_iter(i) { }
340 inline Property& get_property() { return m_iter->get_property(); }
341 inline const Property& get_property() const {
342 return m_iter->get_property();
344 inline Iter get_iter() const { return m_iter; }
349 // For when the EdgeList is a std::vector.
350 // Want to make the iterator stable, so use an offset
351 // instead of an iterator into a std::vector
352 template <class Vertex, class EdgeVec, class Property>
353 class stored_ra_edge_iter
354 : public stored_edge<Vertex>
356 typedef typename EdgeVec::iterator Iter;
358 typedef Property property_type;
359 inline stored_ra_edge_iter() { }
360 inline explicit stored_ra_edge_iter(Vertex v) // Only used for comparisons
361 : stored_edge<Vertex>(v), m_i(0), m_vec(0){ }
362 inline stored_ra_edge_iter(Vertex v, Iter i, EdgeVec* edge_vec)
363 : stored_edge<Vertex>(v), m_i(i - edge_vec->begin()), m_vec(edge_vec){ }
364 inline Property& get_property() { BOOST_ASSERT ((m_vec != 0)); return (*m_vec)[m_i].get_property(); }
365 inline const Property& get_property() const {
366 BOOST_ASSERT ((m_vec != 0));
367 return (*m_vec)[m_i].get_property();
369 inline Iter get_iter() const { BOOST_ASSERT ((m_vec != 0)); return m_vec->begin() + m_i; }
375 } // namespace detail
377 template <class Tag, class Vertex, class Property>
378 const typename property_value<Property,Tag>::type&
379 get(Tag property_tag,
380 const detail::stored_edge_property<Vertex, Property>& e)
382 return get_property_value(e.get_property(), property_tag);
385 template <class Tag, class Vertex, class Iter, class Property>
386 const typename property_value<Property,Tag>::type&
387 get(Tag property_tag,
388 const detail::stored_edge_iter<Vertex, Iter, Property>& e)
390 return get_property_value(e.get_property(), property_tag);
393 template <class Tag, class Vertex, class EdgeVec, class Property>
394 const typename property_value<Property,Tag>::type&
395 get(Tag property_tag,
396 const detail::stored_ra_edge_iter<Vertex, EdgeVec, Property>& e)
398 return get_property_value(e.get_property(), property_tag);
401 //=========================================================================
402 // Directed Edges Helper Class
407 template <class edge_descriptor, class EdgeList, class StoredProperty>
409 remove_directed_edge_dispatch(edge_descriptor, EdgeList& el,
412 for (typename EdgeList::iterator i = el.begin();
414 if (&(*i).get_property() == &p) {
420 template <class incidence_iterator, class EdgeList, class Predicate>
422 remove_directed_edge_if_dispatch(incidence_iterator first,
423 incidence_iterator last,
424 EdgeList& el, Predicate pred,
425 boost::allow_parallel_edge_tag)
428 while (first != last && !pred(*first))
430 incidence_iterator i = first;
432 for (++i; i != last; ++i)
434 *first.base() = BOOST_GRAPH_MOVE_IF_POSSIBLE(*i.base());
437 el.erase(first.base(), el.end());
439 template <class incidence_iterator, class EdgeList, class Predicate>
441 remove_directed_edge_if_dispatch(incidence_iterator first,
442 incidence_iterator last,
445 boost::disallow_parallel_edge_tag)
447 for (incidence_iterator next = first;
448 first != last; first = next) {
451 el.erase( first.base() );
455 template <class PropT, class Graph, class incidence_iterator,
456 class EdgeList, class Predicate>
458 undirected_remove_out_edge_if_dispatch(Graph& g,
459 incidence_iterator first,
460 incidence_iterator last,
461 EdgeList& el, Predicate pred,
462 boost::allow_parallel_edge_tag)
464 typedef typename Graph::global_edgelist_selector EdgeListS;
465 BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
468 while (first != last && !pred(*first))
470 incidence_iterator i = first;
471 bool self_loop_removed = false;
473 for (; i != last; ++i) {
474 if (self_loop_removed) {
475 /* With self loops, the descriptor will show up
476 * twice. The first time it will be removed, and now it
479 self_loop_removed = false;
481 else if (!pred(*i)) {
482 *first.base() = BOOST_GRAPH_MOVE_IF_POSSIBLE(*i.base());
485 if (source(*i, g) == target(*i, g)) self_loop_removed = true;
487 // Remove the edge from the target
488 detail::remove_directed_edge_dispatch
490 g.out_edge_list(target(*i, g)),
491 *(PropT*)(*i).get_property());
494 // Erase the edge property
495 g.m_edges.erase( (*i.base()).get_iter() );
498 el.erase(first.base(), el.end());
500 template <class PropT, class Graph, class incidence_iterator,
501 class EdgeList, class Predicate>
503 undirected_remove_out_edge_if_dispatch(Graph& g,
504 incidence_iterator first,
505 incidence_iterator last,
508 boost::disallow_parallel_edge_tag)
510 typedef typename Graph::global_edgelist_selector EdgeListS;
511 BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
513 for (incidence_iterator next = first;
514 first != last; first = next) {
517 if (source(*first, g) != target(*first, g)) {
518 // Remove the edge from the target
519 detail::remove_directed_edge_dispatch
521 g.out_edge_list(target(*first, g)),
522 *(PropT*)(*first).get_property());
525 // Erase the edge property
526 g.m_edges.erase( (*first.base()).get_iter() );
528 // Erase the edge in the source
529 el.erase( first.base() );
535 template <class edge_descriptor, class EdgeList, class StoredProperty>
537 remove_directed_edge_dispatch(edge_descriptor e, EdgeList& el,
540 for (typename EdgeList::iterator i = el.begin();
542 if ((*i).get_target() == e.m_target) {
548 } // namespace detail
550 template <class Config>
551 struct directed_edges_helper {
553 // Placement of these overloaded remove_edge() functions
554 // inside the class avoids a VC++ bug.
558 remove_edge(typename Config::edge_descriptor e)
560 typedef typename Config::graph_type graph_type;
561 graph_type& g = static_cast<graph_type&>(*this);
562 typename Config::OutEdgeList& el = g.out_edge_list(source(e, g));
563 typedef typename Config::OutEdgeList::value_type::property_type PType;
564 detail::remove_directed_edge_dispatch(e, el,
565 *(PType*)e.get_property());
570 remove_edge(typename Config::out_edge_iterator iter)
572 typedef typename Config::graph_type graph_type;
573 graph_type& g = static_cast<graph_type&>(*this);
574 typename Config::edge_descriptor e = *iter;
575 typename Config::OutEdgeList& el = g.out_edge_list(source(e, g));
576 el.erase(iter.base());
582 template <class Config>
583 inline std::pair<typename Config::edge_iterator,
584 typename Config::edge_iterator>
585 edges(const directed_edges_helper<Config>& g_)
587 typedef typename Config::graph_type graph_type;
588 typedef typename Config::edge_iterator edge_iterator;
589 const graph_type& cg = static_cast<const graph_type&>(g_);
590 graph_type& g = const_cast<graph_type&>(cg);
591 return std::make_pair( edge_iterator(g.vertex_set().begin(),
592 g.vertex_set().begin(),
593 g.vertex_set().end(), g),
594 edge_iterator(g.vertex_set().begin(),
595 g.vertex_set().end(),
596 g.vertex_set().end(), g) );
599 //=========================================================================
600 // Directed Graph Helper Class
602 struct adj_list_dir_traversal_tag :
603 public virtual vertex_list_graph_tag,
604 public virtual incidence_graph_tag,
605 public virtual adjacency_graph_tag,
606 public virtual edge_list_graph_tag { };
608 template <class Config>
609 struct directed_graph_helper
610 : public directed_edges_helper<Config> {
611 typedef typename Config::edge_descriptor edge_descriptor;
612 typedef adj_list_dir_traversal_tag traversal_category;
616 template <class Config>
618 remove_edge(typename Config::vertex_descriptor u,
619 typename Config::vertex_descriptor v,
620 directed_graph_helper<Config>& g_)
622 typedef typename Config::graph_type graph_type;
623 typedef typename Config::edge_parallel_category Cat;
624 graph_type& g = static_cast<graph_type&>(g_);
625 detail::erase_from_incidence_list(g.out_edge_list(u), v, Cat());
628 template <class Config, class Predicate>
630 remove_out_edge_if(typename Config::vertex_descriptor u, Predicate pred,
631 directed_graph_helper<Config>& g_)
633 typedef typename Config::graph_type graph_type;
634 graph_type& g = static_cast<graph_type&>(g_);
635 typename Config::out_edge_iterator first, last;
636 boost::tie(first, last) = out_edges(u, g);
637 typedef typename Config::edge_parallel_category edge_parallel_category;
638 detail::remove_directed_edge_if_dispatch
639 (first, last, g.out_edge_list(u), pred, edge_parallel_category());
642 template <class Config, class Predicate>
644 remove_edge_if(Predicate pred, directed_graph_helper<Config>& g_)
646 typedef typename Config::graph_type graph_type;
647 graph_type& g = static_cast<graph_type&>(g_);
649 typename Config::vertex_iterator vi, vi_end;
650 for (boost::tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi)
651 remove_out_edge_if(*vi, pred, g);
654 template <class EdgeOrIter, class Config>
656 remove_edge(EdgeOrIter e_or_iter, directed_graph_helper<Config>& g_)
658 g_.remove_edge(e_or_iter);
661 // O(V + E) for allow_parallel_edges
662 // O(V * log(E/V)) for disallow_parallel_edges
663 template <class Config>
665 clear_vertex(typename Config::vertex_descriptor u,
666 directed_graph_helper<Config>& g_)
668 typedef typename Config::graph_type graph_type;
669 typedef typename Config::edge_parallel_category Cat;
670 graph_type& g = static_cast<graph_type&>(g_);
671 typename Config::vertex_iterator vi, viend;
672 for (boost::tie(vi, viend) = vertices(g); vi != viend; ++vi)
673 detail::erase_from_incidence_list(g.out_edge_list(*vi), u, Cat());
674 g.out_edge_list(u).clear();
675 // clear() should be a req of Sequence and AssociativeContainer,
676 // or maybe just Container
679 template <class Config>
681 clear_out_edges(typename Config::vertex_descriptor u,
682 directed_graph_helper<Config>& g_)
684 typedef typename Config::graph_type graph_type;
685 graph_type& g = static_cast<graph_type&>(g_);
686 g.out_edge_list(u).clear();
687 // clear() should be a req of Sequence and AssociativeContainer,
688 // or maybe just Container
691 // O(V), could do better...
692 template <class Config>
693 inline typename Config::edges_size_type
694 num_edges(const directed_graph_helper<Config>& g_)
696 typedef typename Config::graph_type graph_type;
697 const graph_type& g = static_cast<const graph_type&>(g_);
698 typename Config::edges_size_type num_e = 0;
699 typename Config::vertex_iterator vi, vi_end;
700 for (boost::tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi)
701 num_e += out_degree(*vi, g);
704 // O(1) for allow_parallel_edge_tag
705 // O(log(E/V)) for disallow_parallel_edge_tag
706 template <class Config>
707 inline std::pair<typename directed_graph_helper<Config>::edge_descriptor, bool>
708 add_edge(typename Config::vertex_descriptor u,
709 typename Config::vertex_descriptor v,
710 const typename Config::edge_property_type& p,
711 directed_graph_helper<Config>& g_)
713 typedef typename Config::edge_descriptor edge_descriptor;
714 typedef typename Config::graph_type graph_type;
715 typedef typename Config::StoredEdge StoredEdge;
716 graph_type& g = static_cast<graph_type&>(g_);
717 typename Config::OutEdgeList::iterator i;
719 boost::tie(i, inserted) = boost::graph_detail::push(g.out_edge_list(u),
721 return std::make_pair(edge_descriptor(u, v, &(*i).get_property()),
724 // Did not use default argument here because that
725 // causes Visual C++ to get confused.
726 template <class Config>
727 inline std::pair<typename Config::edge_descriptor, bool>
728 add_edge(typename Config::vertex_descriptor u,
729 typename Config::vertex_descriptor v,
730 directed_graph_helper<Config>& g_)
732 typename Config::edge_property_type p;
733 return add_edge(u, v, p, g_);
735 //=========================================================================
736 // Undirected Graph Helper Class
738 template <class Config>
739 struct undirected_graph_helper;
741 struct undir_adj_list_traversal_tag :
742 public virtual vertex_list_graph_tag,
743 public virtual incidence_graph_tag,
744 public virtual adjacency_graph_tag,
745 public virtual edge_list_graph_tag,
746 public virtual bidirectional_graph_tag { };
750 // using class with specialization for dispatch is a VC++ workaround.
751 template <class StoredProperty>
752 struct remove_undirected_edge_dispatch {
755 template <class edge_descriptor, class Config>
757 apply(edge_descriptor e,
758 undirected_graph_helper<Config>& g_,
761 typedef typename Config::global_edgelist_selector EdgeListS;
762 BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
764 typedef typename Config::graph_type graph_type;
765 graph_type& g = static_cast<graph_type&>(g_);
767 typename Config::OutEdgeList& out_el = g.out_edge_list(source(e, g));
768 typename Config::OutEdgeList::iterator out_i = out_el.begin();
769 typename Config::EdgeIter edge_iter_to_erase;
770 for (; out_i != out_el.end(); ++out_i)
771 if (&(*out_i).get_property() == &p) {
772 edge_iter_to_erase = (*out_i).get_iter();
776 typename Config::OutEdgeList& in_el = g.out_edge_list(target(e, g));
777 typename Config::OutEdgeList::iterator in_i = in_el.begin();
778 for (; in_i != in_el.end(); ++in_i)
779 if (&(*in_i).get_property() == &p) {
783 g.m_edges.erase(edge_iter_to_erase);
788 struct remove_undirected_edge_dispatch<no_property> {
790 template <class edge_descriptor, class Config>
792 apply(edge_descriptor e,
793 undirected_graph_helper<Config>& g_,
796 typedef typename Config::global_edgelist_selector EdgeListS;
797 BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
799 typedef typename Config::graph_type graph_type;
800 graph_type& g = static_cast<graph_type&>(g_);
801 no_property* p = (no_property*)e.get_property();
802 typename Config::OutEdgeList& out_el = g.out_edge_list(source(e, g));
803 typename Config::OutEdgeList::iterator out_i = out_el.begin();
804 typename Config::EdgeIter edge_iter_to_erase;
805 for (; out_i != out_el.end(); ++out_i)
806 if (&(*out_i).get_property() == p) {
807 edge_iter_to_erase = (*out_i).get_iter();
811 typename Config::OutEdgeList& in_el = g.out_edge_list(target(e, g));
812 typename Config::OutEdgeList::iterator in_i = in_el.begin();
813 for (; in_i != in_el.end(); ++in_i)
814 if (&(*in_i).get_property() == p) {
818 g.m_edges.erase(edge_iter_to_erase);
823 template <class Graph, class EdgeList, class Vertex>
825 remove_edge_and_property(Graph& g, EdgeList& el, Vertex v,
826 boost::allow_parallel_edge_tag cat)
828 typedef typename Graph::global_edgelist_selector EdgeListS;
829 BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
831 typename EdgeList::iterator i = el.begin(), end = el.end();
832 for (; i != end; ++i) {
833 if ((*i).get_target() == v) {
834 // NOTE: Wihtout this skip, this loop will double-delete properties
835 // of loop edges. This solution is based on the observation that
836 // the incidence edges of a vertex with a loop are adjacent in the
837 // out edge list. This *may* actually hold for multisets also.
838 bool skip = (boost::next(i) != end && i->get_iter() == boost::next(i)->get_iter());
839 g.m_edges.erase((*i).get_iter());
843 detail::erase_from_incidence_list(el, v, cat);
846 template <class Graph, class EdgeList, class Vertex>
848 remove_edge_and_property(Graph& g, EdgeList& el, Vertex v,
849 boost::disallow_parallel_edge_tag)
851 typedef typename Graph::global_edgelist_selector EdgeListS;
852 BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
854 typedef typename EdgeList::value_type StoredEdge;
855 typename EdgeList::iterator i = el.find(StoredEdge(v)), end = el.end();
857 g.m_edges.erase((*i).get_iter());
862 } // namespace detail
864 template <class Vertex, class EdgeProperty>
865 struct list_edge // short name due to VC++ truncation and linker problems
866 : public boost::detail::edge_base<boost::undirected_tag, Vertex>
868 typedef EdgeProperty property_type;
869 typedef boost::detail::edge_base<boost::undirected_tag, Vertex> Base;
870 list_edge(Vertex u, Vertex v, const EdgeProperty& p = EdgeProperty())
871 : Base(u, v), m_property(p) { }
872 EdgeProperty& get_property() { return m_property; }
873 const EdgeProperty& get_property() const { return m_property; }
874 // the following methods should never be used, but are needed
875 // to make SGI MIPSpro C++ happy
877 bool operator==(const list_edge&) const { return false; }
878 bool operator<(const list_edge&) const { return false; }
879 EdgeProperty m_property;
882 template <class Config>
883 struct undirected_graph_helper {
885 typedef undir_adj_list_traversal_tag traversal_category;
887 // Placement of these overloaded remove_edge() functions
888 // inside the class avoids a VC++ bug.
892 remove_edge(typename Config::edge_descriptor e)
894 typedef typename Config::global_edgelist_selector EdgeListS;
895 BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
897 typedef typename Config::OutEdgeList::value_type::property_type PType;
898 detail::remove_undirected_edge_dispatch<PType>::apply
899 (e, *this, *(PType*)e.get_property());
903 remove_edge(typename Config::out_edge_iterator iter)
905 this->remove_edge(*iter);
909 // Had to make these non-members to avoid accidental instantiation
910 // on SGI MIPSpro C++
912 inline typename C::InEdgeList&
913 in_edge_list(undirected_graph_helper<C>&,
914 typename C::vertex_descriptor v)
916 typename C::stored_vertex* sv = (typename C::stored_vertex*)v;
917 return sv->m_out_edges;
920 inline const typename C::InEdgeList&
921 in_edge_list(const undirected_graph_helper<C>&,
922 typename C::vertex_descriptor v) {
923 typename C::stored_vertex* sv = (typename C::stored_vertex*)v;
924 return sv->m_out_edges;
928 template <class EdgeOrIter, class Config>
930 remove_edge(EdgeOrIter e, undirected_graph_helper<Config>& g_)
932 typedef typename Config::global_edgelist_selector EdgeListS;
933 BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
938 // O(E/V) or O(log(E/V))
939 template <class Config>
941 remove_edge(typename Config::vertex_descriptor u,
942 typename Config::vertex_descriptor v,
943 undirected_graph_helper<Config>& g_)
945 typedef typename Config::global_edgelist_selector EdgeListS;
946 BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
948 typedef typename Config::graph_type graph_type;
949 graph_type& g = static_cast<graph_type&>(g_);
950 typedef typename Config::edge_parallel_category Cat;
951 detail::remove_edge_and_property(g, g.out_edge_list(u), v, Cat());
952 detail::erase_from_incidence_list(g.out_edge_list(v), u, Cat());
955 template <class Config, class Predicate>
957 remove_out_edge_if(typename Config::vertex_descriptor u, Predicate pred,
958 undirected_graph_helper<Config>& g_)
960 typedef typename Config::global_edgelist_selector EdgeListS;
961 BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
963 typedef typename Config::graph_type graph_type;
964 typedef typename Config::OutEdgeList::value_type::property_type PropT;
965 graph_type& g = static_cast<graph_type&>(g_);
966 typename Config::out_edge_iterator first, last;
967 boost::tie(first, last) = out_edges(u, g);
968 typedef typename Config::edge_parallel_category Cat;
969 detail::undirected_remove_out_edge_if_dispatch<PropT>
970 (g, first, last, g.out_edge_list(u), pred, Cat());
972 template <class Config, class Predicate>
974 remove_in_edge_if(typename Config::vertex_descriptor u, Predicate pred,
975 undirected_graph_helper<Config>& g_)
977 typedef typename Config::global_edgelist_selector EdgeListS;
978 BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
980 remove_out_edge_if(u, pred, g_);
983 // O(E/V * E) or O(log(E/V) * E)
984 template <class Predicate, class Config>
986 remove_edge_if(Predicate pred, undirected_graph_helper<Config>& g_)
988 typedef typename Config::global_edgelist_selector EdgeListS;
989 BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
991 typedef typename Config::graph_type graph_type;
992 graph_type& g = static_cast<graph_type&>(g_);
993 typename Config::edge_iterator ei, ei_end, next;
994 boost::tie(ei, ei_end) = edges(g);
995 for (next = ei; ei != ei_end; ei = next) {
1003 template <class Config>
1004 inline std::pair<typename Config::edge_iterator,
1005 typename Config::edge_iterator>
1006 edges(const undirected_graph_helper<Config>& g_)
1008 typedef typename Config::graph_type graph_type;
1009 typedef typename Config::edge_iterator edge_iterator;
1010 const graph_type& cg = static_cast<const graph_type&>(g_);
1011 graph_type& g = const_cast<graph_type&>(cg);
1012 return std::make_pair( edge_iterator(g.m_edges.begin()),
1013 edge_iterator(g.m_edges.end()) );
1016 template <class Config>
1017 inline typename Config::edges_size_type
1018 num_edges(const undirected_graph_helper<Config>& g_)
1020 typedef typename Config::graph_type graph_type;
1021 const graph_type& g = static_cast<const graph_type&>(g_);
1022 return g.m_edges.size();
1025 template <class Config>
1027 clear_vertex(typename Config::vertex_descriptor u,
1028 undirected_graph_helper<Config>& g_)
1030 typedef typename Config::global_edgelist_selector EdgeListS;
1031 BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
1033 typedef typename Config::graph_type graph_type;
1034 graph_type& g = static_cast<graph_type&>(g_);
1036 typename Config::out_edge_iterator ei, ei_end;
1037 boost::tie(ei, ei_end) = out_edges(u, g);
1038 if (ei == ei_end) break;
1039 remove_edge(*ei, g);
1042 // O(1) for allow_parallel_edge_tag
1043 // O(log(E/V)) for disallow_parallel_edge_tag
1044 template <class Config>
1045 inline std::pair<typename Config::edge_descriptor, bool>
1046 add_edge(typename Config::vertex_descriptor u,
1047 typename Config::vertex_descriptor v,
1048 const typename Config::edge_property_type& p,
1049 undirected_graph_helper<Config>& g_)
1051 typedef typename Config::StoredEdge StoredEdge;
1052 typedef typename Config::edge_descriptor edge_descriptor;
1053 typedef typename Config::graph_type graph_type;
1054 graph_type& g = static_cast<graph_type&>(g_);
1057 typename Config::EdgeContainer::value_type e(u, v, p);
1058 typename Config::EdgeContainer::iterator p_iter
1059 = graph_detail::push(g.m_edges, e).first;
1061 typename Config::OutEdgeList::iterator i;
1062 boost::tie(i, inserted) = boost::graph_detail::push(g.out_edge_list(u),
1063 StoredEdge(v, p_iter, &g.m_edges));
1065 boost::graph_detail::push(g.out_edge_list(v), StoredEdge(u, p_iter, &g.m_edges));
1066 return std::make_pair(edge_descriptor(u, v, &p_iter->get_property()),
1069 g.m_edges.erase(p_iter);
1070 return std::make_pair
1071 (edge_descriptor(u, v, &i->get_iter()->get_property()), false);
1074 template <class Config>
1075 inline std::pair<typename Config::edge_descriptor, bool>
1076 add_edge(typename Config::vertex_descriptor u,
1077 typename Config::vertex_descriptor v,
1078 undirected_graph_helper<Config>& g_)
1080 typename Config::edge_property_type p;
1081 return add_edge(u, v, p, g_);
1085 template <class Config>
1086 inline typename Config::degree_size_type
1087 degree(typename Config::vertex_descriptor u,
1088 const undirected_graph_helper<Config>& g_)
1090 typedef typename Config::graph_type Graph;
1091 const Graph& g = static_cast<const Graph&>(g_);
1092 return out_degree(u, g);
1095 template <class Config>
1096 inline std::pair<typename Config::in_edge_iterator,
1097 typename Config::in_edge_iterator>
1098 in_edges(typename Config::vertex_descriptor u,
1099 const undirected_graph_helper<Config>& g_)
1101 typedef typename Config::graph_type Graph;
1102 const Graph& cg = static_cast<const Graph&>(g_);
1103 Graph& g = const_cast<Graph&>(cg);
1104 typedef typename Config::in_edge_iterator in_edge_iterator;
1106 std::make_pair(in_edge_iterator(g.out_edge_list(u).begin(), u),
1107 in_edge_iterator(g.out_edge_list(u).end(), u));
1110 template <class Config>
1111 inline typename Config::degree_size_type
1112 in_degree(typename Config::vertex_descriptor u,
1113 const undirected_graph_helper<Config>& g_)
1114 { return degree(u, g_); }
1116 //=========================================================================
1117 // Bidirectional Graph Helper Class
1119 struct bidir_adj_list_traversal_tag :
1120 public virtual vertex_list_graph_tag,
1121 public virtual incidence_graph_tag,
1122 public virtual adjacency_graph_tag,
1123 public virtual edge_list_graph_tag,
1124 public virtual bidirectional_graph_tag { };
1126 template <class Config>
1127 struct bidirectional_graph_helper
1128 : public directed_edges_helper<Config> {
1129 typedef bidir_adj_list_traversal_tag traversal_category;
1132 // Had to make these non-members to avoid accidental instantiation
1133 // on SGI MIPSpro C++
1135 inline typename C::InEdgeList&
1136 in_edge_list(bidirectional_graph_helper<C>&,
1137 typename C::vertex_descriptor v)
1139 typename C::stored_vertex* sv = (typename C::stored_vertex*)v;
1140 return sv->m_in_edges;
1143 inline const typename C::InEdgeList&
1144 in_edge_list(const bidirectional_graph_helper<C>&,
1145 typename C::vertex_descriptor v) {
1146 typename C::stored_vertex* sv = (typename C::stored_vertex*)v;
1147 return sv->m_in_edges;
1150 template <class Predicate, class Config>
1152 remove_edge_if(Predicate pred, bidirectional_graph_helper<Config>& g_)
1154 typedef typename Config::global_edgelist_selector EdgeListS;
1155 BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
1157 typedef typename Config::graph_type graph_type;
1158 graph_type& g = static_cast<graph_type&>(g_);
1159 typename Config::edge_iterator ei, ei_end, next;
1160 boost::tie(ei, ei_end) = edges(g);
1161 for (next = ei; ei != ei_end; ei = next) {
1164 remove_edge(*ei, g);
1168 template <class Config>
1169 inline std::pair<typename Config::in_edge_iterator,
1170 typename Config::in_edge_iterator>
1171 in_edges(typename Config::vertex_descriptor u,
1172 const bidirectional_graph_helper<Config>& g_)
1174 typedef typename Config::graph_type graph_type;
1175 const graph_type& cg = static_cast<const graph_type&>(g_);
1176 graph_type& g = const_cast<graph_type&>(cg);
1177 typedef typename Config::in_edge_iterator in_edge_iterator;
1179 std::make_pair(in_edge_iterator(in_edge_list(g, u).begin(), u),
1180 in_edge_iterator(in_edge_list(g, u).end(), u));
1184 template <class Config>
1185 inline std::pair<typename Config::edge_iterator,
1186 typename Config::edge_iterator>
1187 edges(const bidirectional_graph_helper<Config>& g_)
1189 typedef typename Config::graph_type graph_type;
1190 typedef typename Config::edge_iterator edge_iterator;
1191 const graph_type& cg = static_cast<const graph_type&>(g_);
1192 graph_type& g = const_cast<graph_type&>(cg);
1193 return std::make_pair( edge_iterator(g.m_edges.begin()),
1194 edge_iterator(g.m_edges.end()) );
1197 //=========================================================================
1198 // Bidirectional Graph Helper Class (with edge properties)
1201 template <class Config>
1202 struct bidirectional_graph_helper_with_property
1203 : public bidirectional_graph_helper<Config>
1205 typedef typename Config::graph_type graph_type;
1206 typedef typename Config::out_edge_iterator out_edge_iterator;
1208 std::pair<out_edge_iterator, out_edge_iterator>
1209 get_parallel_edge_sublist(typename Config::edge_descriptor e,
1210 const graph_type& g,
1212 { return out_edges(source(e, g), g); }
1214 std::pair<out_edge_iterator, out_edge_iterator>
1215 get_parallel_edge_sublist(typename Config::edge_descriptor e,
1216 const graph_type& g,
1218 { return edge_range(source(e, g), target(e, g), g); }
1220 std::pair<out_edge_iterator, out_edge_iterator>
1221 get_parallel_edge_sublist(typename Config::edge_descriptor e,
1222 const graph_type& g,
1224 { return edge_range(source(e, g), target(e, g), g); }
1226 std::pair<out_edge_iterator, out_edge_iterator>
1227 get_parallel_edge_sublist(typename Config::edge_descriptor e,
1228 const graph_type& g,
1230 { return edge_range(source(e, g), target(e, g), g); }
1232 // Placement of these overloaded remove_edge() functions
1233 // inside the class avoids a VC++ bug.
1235 // O(E/V) or O(log(E/V))
1237 remove_edge(typename Config::edge_descriptor e)
1239 typedef typename Config::global_edgelist_selector EdgeListS;
1240 BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
1242 graph_type& g = static_cast<graph_type&>(*this);
1244 typedef typename Config::edgelist_selector OutEdgeListS;
1246 std::pair<out_edge_iterator, out_edge_iterator> rng =
1247 get_parallel_edge_sublist(e, g, (OutEdgeListS*)(0));
1248 rng.first = std::find(rng.first, rng.second, e);
1249 BOOST_ASSERT(rng.first != rng.second);
1250 remove_edge(rng.first);
1254 remove_edge(typename Config::out_edge_iterator iter)
1256 typedef typename Config::global_edgelist_selector EdgeListS;
1257 BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
1259 typedef typename Config::graph_type graph_type;
1260 graph_type& g = static_cast<graph_type&>(*this);
1261 typename Config::edge_descriptor e = *iter;
1262 typename Config::OutEdgeList& oel = g.out_edge_list(source(e, g));
1263 typename Config::InEdgeList& iel = in_edge_list(g, target(e, g));
1264 typedef typename Config::OutEdgeList::value_type::property_type PType;
1265 PType& p = *(PType*)e.get_property();
1266 detail::remove_directed_edge_dispatch(*iter, iel, p);
1267 g.m_edges.erase(iter.base()->get_iter());
1268 oel.erase(iter.base());
1272 // O(E/V) for allow_parallel_edge_tag
1273 // O(log(E/V)) for disallow_parallel_edge_tag
1274 template <class Config>
1276 remove_edge(typename Config::vertex_descriptor u,
1277 typename Config::vertex_descriptor v,
1278 bidirectional_graph_helper_with_property<Config>& g_)
1280 typedef typename Config::global_edgelist_selector EdgeListS;
1281 BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
1283 typedef typename Config::graph_type graph_type;
1284 graph_type& g = static_cast<graph_type&>(g_);
1285 typedef typename Config::edge_parallel_category Cat;
1286 detail::remove_edge_and_property(g, g.out_edge_list(u), v, Cat());
1287 detail::erase_from_incidence_list(in_edge_list(g, v), u, Cat());
1290 // O(E/V) or O(log(E/V))
1291 template <class EdgeOrIter, class Config>
1293 remove_edge(EdgeOrIter e,
1294 bidirectional_graph_helper_with_property<Config>& g_)
1296 typedef typename Config::global_edgelist_selector EdgeListS;
1297 BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
1302 template <class Config, class Predicate>
1304 remove_out_edge_if(typename Config::vertex_descriptor u, Predicate pred,
1305 bidirectional_graph_helper_with_property<Config>& g_)
1307 typedef typename Config::global_edgelist_selector EdgeListS;
1308 BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
1310 typedef typename Config::graph_type graph_type;
1311 typedef typename Config::OutEdgeList::value_type::property_type PropT;
1312 graph_type& g = static_cast<graph_type&>(g_);
1314 typedef typename Config::EdgeIter EdgeIter;
1315 typedef std::vector<EdgeIter> Garbage;
1318 // First remove the edges from the targets' in-edge lists and
1319 // from the graph's edge set list.
1320 typename Config::out_edge_iterator out_i, out_end;
1321 for (boost::tie(out_i, out_end) = out_edges(u, g); out_i != out_end; ++out_i)
1323 detail::remove_directed_edge_dispatch
1324 (*out_i, in_edge_list(g, target(*out_i, g)),
1325 *(PropT*)(*out_i).get_property());
1326 // Put in garbage to delete later. Will need the properties
1327 // for the remove_if of the out-edges.
1328 garbage.push_back((*out_i.base()).get_iter());
1331 // Now remove the edges from this out-edge list.
1332 typename Config::out_edge_iterator first, last;
1333 boost::tie(first, last) = out_edges(u, g);
1334 typedef typename Config::edge_parallel_category Cat;
1335 detail::remove_directed_edge_if_dispatch
1336 (first, last, g.out_edge_list(u), pred, Cat());
1338 // Now delete the edge properties from the g.m_edges list
1339 for (typename Garbage::iterator i = garbage.begin();
1340 i != garbage.end(); ++i)
1341 g.m_edges.erase(*i);
1343 template <class Config, class Predicate>
1345 remove_in_edge_if(typename Config::vertex_descriptor v, Predicate pred,
1346 bidirectional_graph_helper_with_property<Config>& g_)
1348 typedef typename Config::global_edgelist_selector EdgeListS;
1349 BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
1351 typedef typename Config::graph_type graph_type;
1352 typedef typename Config::OutEdgeList::value_type::property_type PropT;
1353 graph_type& g = static_cast<graph_type&>(g_);
1355 typedef typename Config::EdgeIter EdgeIter;
1356 typedef std::vector<EdgeIter> Garbage;
1359 // First remove the edges from the sources' out-edge lists and
1360 // from the graph's edge set list.
1361 typename Config::in_edge_iterator in_i, in_end;
1362 for (boost::tie(in_i, in_end) = in_edges(v, g); in_i != in_end; ++in_i)
1364 typename Config::vertex_descriptor u = source(*in_i, g);
1365 detail::remove_directed_edge_dispatch
1366 (*in_i, g.out_edge_list(u), *(PropT*)(*in_i).get_property());
1367 // Put in garbage to delete later. Will need the properties
1368 // for the remove_if of the out-edges.
1369 garbage.push_back((*in_i.base()).get_iter());
1371 // Now remove the edges from this in-edge list.
1372 typename Config::in_edge_iterator first, last;
1373 boost::tie(first, last) = in_edges(v, g);
1374 typedef typename Config::edge_parallel_category Cat;
1375 detail::remove_directed_edge_if_dispatch
1376 (first, last, in_edge_list(g, v), pred, Cat());
1378 // Now delete the edge properties from the g.m_edges list
1379 for (typename Garbage::iterator i = garbage.begin();
1380 i != garbage.end(); ++i)
1381 g.m_edges.erase(*i);
1385 template <class Config>
1386 inline typename Config::edges_size_type
1387 num_edges(const bidirectional_graph_helper_with_property<Config>& g_)
1389 typedef typename Config::graph_type graph_type;
1390 const graph_type& g = static_cast<const graph_type&>(g_);
1391 return g.m_edges.size();
1393 // O(E/V * E/V) for allow_parallel_edge_tag
1394 // O(E/V * log(E/V)) for disallow_parallel_edge_tag
1395 template <class Config>
1397 clear_vertex(typename Config::vertex_descriptor u,
1398 bidirectional_graph_helper_with_property<Config>& g_)
1400 typedef typename Config::global_edgelist_selector EdgeListS;
1401 BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
1403 typedef typename Config::graph_type graph_type;
1404 typedef typename Config::edge_parallel_category Cat;
1405 graph_type& g = static_cast<graph_type&>(g_);
1406 typename Config::OutEdgeList& el = g.out_edge_list(u);
1407 typename Config::OutEdgeList::iterator
1408 ei = el.begin(), ei_end = el.end();
1409 for (; ei != ei_end; ++ei) {
1410 detail::erase_from_incidence_list
1411 (in_edge_list(g, (*ei).get_target()), u, Cat());
1412 g.m_edges.erase((*ei).get_iter());
1414 typename Config::InEdgeList& in_el = in_edge_list(g, u);
1415 typename Config::InEdgeList::iterator
1416 in_ei = in_el.begin(), in_ei_end = in_el.end();
1417 for (; in_ei != in_ei_end; ++in_ei) {
1418 detail::erase_from_incidence_list
1419 (g.out_edge_list((*in_ei).get_target()), u, Cat());
1420 g.m_edges.erase((*in_ei).get_iter());
1422 g.out_edge_list(u).clear();
1423 in_edge_list(g, u).clear();
1426 template <class Config>
1428 clear_out_edges(typename Config::vertex_descriptor u,
1429 bidirectional_graph_helper_with_property<Config>& g_)
1431 typedef typename Config::global_edgelist_selector EdgeListS;
1432 BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
1434 typedef typename Config::graph_type graph_type;
1435 typedef typename Config::edge_parallel_category Cat;
1436 graph_type& g = static_cast<graph_type&>(g_);
1437 typename Config::OutEdgeList& el = g.out_edge_list(u);
1438 typename Config::OutEdgeList::iterator
1439 ei = el.begin(), ei_end = el.end();
1440 for (; ei != ei_end; ++ei) {
1441 detail::erase_from_incidence_list
1442 (in_edge_list(g, (*ei).get_target()), u, Cat());
1443 g.m_edges.erase((*ei).get_iter());
1445 g.out_edge_list(u).clear();
1448 template <class Config>
1450 clear_in_edges(typename Config::vertex_descriptor u,
1451 bidirectional_graph_helper_with_property<Config>& g_)
1453 typedef typename Config::global_edgelist_selector EdgeListS;
1454 BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
1456 typedef typename Config::graph_type graph_type;
1457 typedef typename Config::edge_parallel_category Cat;
1458 graph_type& g = static_cast<graph_type&>(g_);
1459 typename Config::InEdgeList& in_el = in_edge_list(g, u);
1460 typename Config::InEdgeList::iterator
1461 in_ei = in_el.begin(), in_ei_end = in_el.end();
1462 for (; in_ei != in_ei_end; ++in_ei) {
1463 detail::erase_from_incidence_list
1464 (g.out_edge_list((*in_ei).get_target()), u, Cat());
1465 g.m_edges.erase((*in_ei).get_iter());
1467 in_edge_list(g, u).clear();
1470 // O(1) for allow_parallel_edge_tag
1471 // O(log(E/V)) for disallow_parallel_edge_tag
1472 template <class Config>
1473 inline std::pair<typename Config::edge_descriptor, bool>
1474 add_edge(typename Config::vertex_descriptor u,
1475 typename Config::vertex_descriptor v,
1476 const typename Config::edge_property_type& p,
1477 bidirectional_graph_helper_with_property<Config>& g_)
1479 typedef typename Config::graph_type graph_type;
1480 graph_type& g = static_cast<graph_type&>(g_);
1481 typedef typename Config::edge_descriptor edge_descriptor;
1482 typedef typename Config::StoredEdge StoredEdge;
1484 typename Config::EdgeContainer::value_type e(u, v, p);
1485 typename Config::EdgeContainer::iterator p_iter
1486 = graph_detail::push(g.m_edges, e).first;
1487 typename Config::OutEdgeList::iterator i;
1488 boost::tie(i, inserted) = boost::graph_detail::push(g.out_edge_list(u),
1489 StoredEdge(v, p_iter, &g.m_edges));
1491 boost::graph_detail::push(in_edge_list(g, v), StoredEdge(u, p_iter, &g.m_edges));
1492 return std::make_pair(edge_descriptor(u, v, &p_iter->m_property),
1495 g.m_edges.erase(p_iter);
1496 return std::make_pair(edge_descriptor(u, v,
1497 &i->get_iter()->get_property()),
1502 template <class Config>
1503 inline std::pair<typename Config::edge_descriptor, bool>
1504 add_edge(typename Config::vertex_descriptor u,
1505 typename Config::vertex_descriptor v,
1506 bidirectional_graph_helper_with_property<Config>& g_)
1508 typename Config::edge_property_type p;
1509 return add_edge(u, v, p, g_);
1512 template <class Config>
1513 inline typename Config::degree_size_type
1514 degree(typename Config::vertex_descriptor u,
1515 const bidirectional_graph_helper_with_property<Config>& g_)
1517 typedef typename Config::graph_type graph_type;
1518 const graph_type& g = static_cast<const graph_type&>(g_);
1519 return in_degree(u, g) + out_degree(u, g);
1522 //=========================================================================
1523 // Adjacency List Helper Class
1525 template <class Config, class Base>
1526 struct adj_list_helper : public Base
1528 typedef typename Config::graph_type AdjList;
1529 typedef typename Config::vertex_descriptor vertex_descriptor;
1530 typedef typename Config::edge_descriptor edge_descriptor;
1531 typedef typename Config::out_edge_iterator out_edge_iterator;
1532 typedef typename Config::in_edge_iterator in_edge_iterator;
1533 typedef typename Config::adjacency_iterator adjacency_iterator;
1534 typedef typename Config::inv_adjacency_iterator inv_adjacency_iterator;
1535 typedef typename Config::vertex_iterator vertex_iterator;
1536 typedef typename Config::edge_iterator edge_iterator;
1537 typedef typename Config::directed_category directed_category;
1538 typedef typename Config::edge_parallel_category edge_parallel_category;
1539 typedef typename Config::vertices_size_type vertices_size_type;
1540 typedef typename Config::edges_size_type edges_size_type;
1541 typedef typename Config::degree_size_type degree_size_type;
1542 typedef typename Config::StoredEdge StoredEdge;
1543 typedef typename Config::vertex_property_type vertex_property_type;
1544 typedef typename Config::edge_property_type edge_property_type;
1545 typedef typename Config::graph_property_type graph_property_type;
1547 typedef typename Config::global_edgelist_selector
1548 global_edgelist_selector;
1550 typedef typename lookup_one_property<vertex_property_type, vertex_bundle_t>::type vertex_bundled;
1551 typedef typename lookup_one_property<edge_property_type, edge_bundle_t>::type edge_bundled;
1552 typedef typename lookup_one_property<graph_property_type, graph_bundle_t>::type graph_bundled;
1555 template <class Config, class Base>
1556 inline std::pair<typename Config::adjacency_iterator,
1557 typename Config::adjacency_iterator>
1558 adjacent_vertices(typename Config::vertex_descriptor u,
1559 const adj_list_helper<Config, Base>& g_)
1561 typedef typename Config::graph_type AdjList;
1562 const AdjList& cg = static_cast<const AdjList&>(g_);
1563 AdjList& g = const_cast<AdjList&>(cg);
1564 typedef typename Config::adjacency_iterator adjacency_iterator;
1565 typename Config::out_edge_iterator first, last;
1566 boost::tie(first, last) = out_edges(u, g);
1567 return std::make_pair(adjacency_iterator(first, &g),
1568 adjacency_iterator(last, &g));
1570 template <class Config, class Base>
1571 inline std::pair<typename Config::inv_adjacency_iterator,
1572 typename Config::inv_adjacency_iterator>
1573 inv_adjacent_vertices(typename Config::vertex_descriptor u,
1574 const adj_list_helper<Config, Base>& g_)
1576 typedef typename Config::graph_type AdjList;
1577 const AdjList& cg = static_cast<const AdjList&>(g_);
1578 AdjList& g = const_cast<AdjList&>(cg);
1579 typedef typename Config::inv_adjacency_iterator inv_adjacency_iterator;
1580 typename Config::in_edge_iterator first, last;
1581 boost::tie(first, last) = in_edges(u, g);
1582 return std::make_pair(inv_adjacency_iterator(first, &g),
1583 inv_adjacency_iterator(last, &g));
1585 template <class Config, class Base>
1586 inline std::pair<typename Config::out_edge_iterator,
1587 typename Config::out_edge_iterator>
1588 out_edges(typename Config::vertex_descriptor u,
1589 const adj_list_helper<Config, Base>& g_)
1591 typedef typename Config::graph_type AdjList;
1592 typedef typename Config::out_edge_iterator out_edge_iterator;
1593 const AdjList& cg = static_cast<const AdjList&>(g_);
1594 AdjList& g = const_cast<AdjList&>(cg);
1596 std::make_pair(out_edge_iterator(g.out_edge_list(u).begin(), u),
1597 out_edge_iterator(g.out_edge_list(u).end(), u));
1599 template <class Config, class Base>
1600 inline std::pair<typename Config::vertex_iterator,
1601 typename Config::vertex_iterator>
1602 vertices(const adj_list_helper<Config, Base>& g_)
1604 typedef typename Config::graph_type AdjList;
1605 const AdjList& cg = static_cast<const AdjList&>(g_);
1606 AdjList& g = const_cast<AdjList&>(cg);
1607 return std::make_pair( g.vertex_set().begin(), g.vertex_set().end() );
1609 template <class Config, class Base>
1610 inline typename Config::vertices_size_type
1611 num_vertices(const adj_list_helper<Config, Base>& g_)
1613 typedef typename Config::graph_type AdjList;
1614 const AdjList& g = static_cast<const AdjList&>(g_);
1615 return g.vertex_set().size();
1617 template <class Config, class Base>
1618 inline typename Config::degree_size_type
1619 out_degree(typename Config::vertex_descriptor u,
1620 const adj_list_helper<Config, Base>& g_)
1622 typedef typename Config::graph_type AdjList;
1623 const AdjList& g = static_cast<const AdjList&>(g_);
1624 return g.out_edge_list(u).size();
1626 template <class Config, class Base>
1627 inline std::pair<typename Config::edge_descriptor, bool>
1628 edge(typename Config::vertex_descriptor u,
1629 typename Config::vertex_descriptor v,
1630 const adj_list_helper<Config, Base>& g_)
1632 typedef typename Config::graph_type Graph;
1633 typedef typename Config::StoredEdge StoredEdge;
1634 const Graph& cg = static_cast<const Graph&>(g_);
1635 const typename Config::OutEdgeList& el = cg.out_edge_list(u);
1636 typename Config::OutEdgeList::const_iterator it = graph_detail::
1637 find(el, StoredEdge(v));
1638 return std::make_pair(
1639 typename Config::edge_descriptor
1640 (u, v, (it == el.end() ? 0 : &(*it).get_property())),
1644 template <class Config, class Base>
1645 inline std::pair<typename Config::out_edge_iterator,
1646 typename Config::out_edge_iterator>
1647 edge_range(typename Config::vertex_descriptor u,
1648 typename Config::vertex_descriptor v,
1649 const adj_list_helper<Config, Base>& g_)
1651 typedef typename Config::graph_type Graph;
1652 typedef typename Config::StoredEdge StoredEdge;
1653 const Graph& cg = static_cast<const Graph&>(g_);
1654 Graph& g = const_cast<Graph&>(cg);
1655 typedef typename Config::out_edge_iterator out_edge_iterator;
1656 typename Config::OutEdgeList& el = g.out_edge_list(u);
1657 typename Config::OutEdgeList::iterator first, last;
1658 typename Config::EdgeContainer fake_edge_container;
1659 boost::tie(first, last) = graph_detail::
1660 equal_range(el, StoredEdge(v));
1661 return std::make_pair(out_edge_iterator(first, u),
1662 out_edge_iterator(last, u));
1665 template <class Config>
1666 inline typename Config::degree_size_type
1667 in_degree(typename Config::vertex_descriptor u,
1668 const directed_edges_helper<Config>& g_)
1670 typedef typename Config::graph_type Graph;
1671 const Graph& cg = static_cast<const Graph&>(g_);
1672 Graph& g = const_cast<Graph&>(cg);
1673 return in_edge_list(g, u).size();
1677 template <class Config, class Base, class Property>
1679 typename boost::property_map<typename Config::graph_type,
1681 get_dispatch(adj_list_helper<Config,Base>&, Property p,
1682 boost::edge_property_tag) {
1683 typedef typename Config::graph_type Graph;
1684 typedef typename boost::property_map<Graph, Property>::type PA;
1687 template <class Config, class Base, class Property>
1689 typename boost::property_map<typename Config::graph_type,
1690 Property>::const_type
1691 get_dispatch(const adj_list_helper<Config,Base>&, Property p,
1692 boost::edge_property_tag) {
1693 typedef typename Config::graph_type Graph;
1694 typedef typename boost::property_map<Graph, Property>::const_type PA;
1698 template <class Config, class Base, class Property>
1700 typename boost::property_map<typename Config::graph_type,
1702 get_dispatch(adj_list_helper<Config,Base>& g, Property p,
1703 boost::vertex_property_tag) {
1704 typedef typename Config::graph_type Graph;
1705 typedef typename boost::property_map<Graph, Property>::type PA;
1706 return PA(&static_cast<Graph&>(g), p);
1708 template <class Config, class Base, class Property>
1710 typename boost::property_map<typename Config::graph_type,
1711 Property>::const_type
1712 get_dispatch(const adj_list_helper<Config, Base>& g, Property p,
1713 boost::vertex_property_tag) {
1714 typedef typename Config::graph_type Graph;
1715 typedef typename boost::property_map<Graph, Property>::const_type PA;
1716 const Graph& cg = static_cast<const Graph&>(g);
1720 } // namespace detail
1722 // Implementation of the PropertyGraph interface
1723 template <class Config, class Base, class Property>
1725 typename boost::property_map<typename Config::graph_type, Property>::type
1726 get(Property p, adj_list_helper<Config, Base>& g) {
1727 typedef typename detail::property_kind_from_graph<adj_list_helper<Config, Base>, Property>::type Kind;
1728 return detail::get_dispatch(g, p, Kind());
1730 template <class Config, class Base, class Property>
1732 typename boost::property_map<typename Config::graph_type,
1733 Property>::const_type
1734 get(Property p, const adj_list_helper<Config, Base>& g) {
1735 typedef typename detail::property_kind_from_graph<adj_list_helper<Config, Base>, Property>::type Kind;
1736 return detail::get_dispatch(g, p, Kind());
1739 template <class Config, class Base, class Property, class Key>
1741 typename boost::property_traits<
1742 typename boost::property_map<typename Config::graph_type,
1745 get(Property p, adj_list_helper<Config, Base>& g, const Key& key) {
1746 return get(get(p, g), key);
1749 template <class Config, class Base, class Property, class Key>
1751 typename boost::property_traits<
1752 typename boost::property_map<typename Config::graph_type,
1753 Property>::const_type
1755 get(Property p, const adj_list_helper<Config, Base>& g, const Key& key) {
1756 return get(get(p, g), key);
1759 template <class Config, class Base, class Property, class Key,class Value>
1761 put(Property p, adj_list_helper<Config, Base>& g,
1762 const Key& key, const Value& value)
1764 typedef typename Config::graph_type Graph;
1765 typedef typename boost::property_map<Graph, Property>::type Map;
1766 Map pmap = get(p, static_cast<Graph&>(g));
1767 put(pmap, key, value);
1771 //=========================================================================
1772 // Generalize Adjacency List Implementation
1774 struct adj_list_tag { };
1776 template <class Derived, class Config, class Base>
1778 : public adj_list_helper<Config, Base>
1780 typedef typename Config::OutEdgeList OutEdgeList;
1781 typedef typename Config::InEdgeList InEdgeList;
1782 typedef typename Config::StoredVertexList StoredVertexList;
1784 typedef typename Config::stored_vertex stored_vertex;
1785 typedef typename Config::EdgeContainer EdgeContainer;
1786 typedef typename Config::vertex_descriptor vertex_descriptor;
1787 typedef typename Config::edge_descriptor edge_descriptor;
1788 typedef typename Config::vertex_iterator vertex_iterator;
1789 typedef typename Config::edge_iterator edge_iterator;
1790 typedef typename Config::edge_parallel_category edge_parallel_category;
1791 typedef typename Config::vertices_size_type vertices_size_type;
1792 typedef typename Config::edges_size_type edges_size_type;
1793 typedef typename Config::degree_size_type degree_size_type;
1794 typedef typename Config::edge_property_type edge_property_type;
1795 typedef adj_list_tag graph_tag;
1797 static vertex_descriptor null_vertex()
1802 inline adj_list_impl() { }
1804 inline adj_list_impl(const adj_list_impl& x) {
1807 inline adj_list_impl& operator=(const adj_list_impl& x) {
1812 inline void clear() {
1813 for (typename StoredVertexList::iterator i = m_vertices.begin();
1814 i != m_vertices.end(); ++i)
1815 delete (stored_vertex*)*i;
1819 inline adj_list_impl(vertices_size_type num_vertices) {
1820 for (vertices_size_type i = 0; i < num_vertices; ++i)
1821 add_vertex(static_cast<Derived&>(*this));
1823 template <class EdgeIterator>
1824 inline adj_list_impl(vertices_size_type num_vertices,
1825 EdgeIterator first, EdgeIterator last)
1827 vertex_descriptor* v = new vertex_descriptor[num_vertices];
1828 for (vertices_size_type i = 0; i < num_vertices; ++i)
1829 v[i] = add_vertex(static_cast<Derived&>(*this));
1831 while (first != last) {
1832 add_edge(v[(*first).first], v[(*first).second], *this);
1837 template <class EdgeIterator, class EdgePropertyIterator>
1838 inline adj_list_impl(vertices_size_type num_vertices,
1839 EdgeIterator first, EdgeIterator last,
1840 EdgePropertyIterator ep_iter)
1842 vertex_descriptor* v = new vertex_descriptor[num_vertices];
1843 for (vertices_size_type i = 0; i < num_vertices; ++i)
1844 v[i] = add_vertex(static_cast<Derived&>(*this));
1846 while (first != last) {
1847 add_edge(v[(*first).first], v[(*first).second], *ep_iter, *this);
1854 for (typename StoredVertexList::iterator i = m_vertices.begin();
1855 i != m_vertices.end(); ++i)
1856 delete (stored_vertex*)*i;
1859 inline OutEdgeList& out_edge_list(vertex_descriptor v) {
1860 stored_vertex* sv = (stored_vertex*)v;
1861 return sv->m_out_edges;
1863 inline const OutEdgeList& out_edge_list(vertex_descriptor v) const {
1864 stored_vertex* sv = (stored_vertex*)v;
1865 return sv->m_out_edges;
1867 inline StoredVertexList& vertex_set() { return m_vertices; }
1868 inline const StoredVertexList& vertex_set() const { return m_vertices; }
1870 inline void copy_impl(const adj_list_impl& x_)
1872 const Derived& x = static_cast<const Derived&>(x_);
1874 // Would be better to have a constant time way to get from
1875 // vertices in x to the corresponding vertices in *this.
1876 std::map<stored_vertex*,stored_vertex*> vertex_map;
1878 // Copy the stored vertex objects by adding each vertex
1879 // and copying its property object.
1880 vertex_iterator vi, vi_end;
1881 for (boost::tie(vi, vi_end) = vertices(x); vi != vi_end; ++vi) {
1882 stored_vertex* v = (stored_vertex*)add_vertex(*this);
1883 v->m_property = ((stored_vertex*)*vi)->m_property;
1884 vertex_map[(stored_vertex*)*vi] = v;
1886 // Copy the edges by adding each edge and copying its
1888 edge_iterator ei, ei_end;
1889 for (boost::tie(ei, ei_end) = edges(x); ei != ei_end; ++ei) {
1892 vertex_descriptor s = source(*ei,x), t = target(*ei,x);
1893 boost::tie(e, inserted) = add_edge(vertex_map[(stored_vertex*)s],
1894 vertex_map[(stored_vertex*)t], *this);
1895 *((edge_property_type*)e.m_eproperty)
1896 = *((edge_property_type*)(*ei).m_eproperty);
1901 typename Config::EdgeContainer m_edges;
1902 StoredVertexList m_vertices;
1906 template <class Derived, class Config, class Base>
1907 inline typename Config::vertex_descriptor
1908 add_vertex(adj_list_impl<Derived, Config, Base>& g_)
1910 Derived& g = static_cast<Derived&>(g_);
1911 typedef typename Config::stored_vertex stored_vertex;
1912 stored_vertex* v = new stored_vertex;
1913 typename Config::StoredVertexList::iterator pos;
1915 boost::tie(pos,inserted) = boost::graph_detail::push(g.m_vertices, v);
1916 v->m_position = pos;
1921 template <class Derived, class Config, class Base>
1922 inline typename Config::vertex_descriptor
1923 add_vertex(const typename Config::vertex_property_type& p,
1924 adj_list_impl<Derived, Config, Base>& g_)
1926 typedef typename Config::vertex_descriptor vertex_descriptor;
1927 Derived& g = static_cast<Derived&>(g_);
1928 if (optional<vertex_descriptor> v
1929 = g.vertex_by_property(get_property_value(p, vertex_bundle)))
1932 typedef typename Config::stored_vertex stored_vertex;
1933 stored_vertex* v = new stored_vertex(p);
1934 typename Config::StoredVertexList::iterator pos;
1936 boost::tie(pos,inserted) = boost::graph_detail::push(g.m_vertices, v);
1937 v->m_position = pos;
1942 template <class Derived, class Config, class Base>
1943 inline void remove_vertex(typename Config::vertex_descriptor u,
1944 adj_list_impl<Derived, Config, Base>& g_)
1946 typedef typename Config::stored_vertex stored_vertex;
1947 Derived& g = static_cast<Derived&>(g_);
1948 g.removing_vertex(u, boost::graph_detail::iterator_stability(g_.m_vertices));
1949 stored_vertex* su = (stored_vertex*)u;
1950 g.m_vertices.erase(su->m_position);
1954 template <class Derived, class Config, class Base>
1955 inline typename Config::vertex_descriptor
1956 vertex(typename Config::vertices_size_type n,
1957 const adj_list_impl<Derived, Config, Base>& g_)
1959 const Derived& g = static_cast<const Derived&>(g_);
1960 typename Config::vertex_iterator i = vertices(g).first;
1961 while (n--) ++i; // std::advance(i, n); (not VC++ portable)
1965 //=========================================================================
1966 // Vector-Backbone Adjacency List Implementation
1970 template <class Graph, class vertex_descriptor>
1972 remove_vertex_dispatch(Graph& g, vertex_descriptor u,
1973 boost::directed_tag)
1975 typedef typename Graph::edge_parallel_category edge_parallel_category;
1976 g.m_vertices.erase(g.m_vertices.begin() + u);
1977 vertex_descriptor V = num_vertices(g);
1979 for (vertex_descriptor v = 0; v < V; ++v)
1980 reindex_edge_list(g.out_edge_list(v), u, edge_parallel_category());
1984 template <class Graph, class vertex_descriptor>
1986 remove_vertex_dispatch(Graph& g, vertex_descriptor u,
1987 boost::undirected_tag)
1989 typedef typename Graph::global_edgelist_selector EdgeListS;
1990 BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
1992 typedef typename Graph::edge_parallel_category edge_parallel_category;
1993 g.m_vertices.erase(g.m_vertices.begin() + u);
1994 vertex_descriptor V = num_vertices(g);
1995 for (vertex_descriptor v = 0; v < V; ++v)
1996 reindex_edge_list(g.out_edge_list(v), u,
1997 edge_parallel_category());
1998 typedef typename Graph::EdgeContainer Container;
1999 typedef typename Container::iterator Iter;
2000 Iter ei = g.m_edges.begin(), ei_end = g.m_edges.end();
2001 for (; ei != ei_end; ++ei) {
2002 if (ei->m_source > u)
2004 if (ei->m_target > u)
2008 template <class Graph, class vertex_descriptor>
2010 remove_vertex_dispatch(Graph& g, vertex_descriptor u,
2011 boost::bidirectional_tag)
2013 typedef typename Graph::global_edgelist_selector EdgeListS;
2014 BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
2016 typedef typename Graph::edge_parallel_category edge_parallel_category;
2017 g.m_vertices.erase(g.m_vertices.begin() + u);
2018 vertex_descriptor V = num_vertices(g);
2019 vertex_descriptor v;
2021 for (v = 0; v < V; ++v)
2022 reindex_edge_list(g.out_edge_list(v), u,
2023 edge_parallel_category());
2024 for (v = 0; v < V; ++v)
2025 reindex_edge_list(in_edge_list(g, v), u,
2026 edge_parallel_category());
2028 typedef typename Graph::EdgeContainer Container;
2029 typedef typename Container::iterator Iter;
2030 Iter ei = g.m_edges.begin(), ei_end = g.m_edges.end();
2031 for (; ei != ei_end; ++ei) {
2032 if (ei->m_source > u)
2034 if (ei->m_target > u)
2040 template <class EdgeList, class vertex_descriptor>
2042 reindex_edge_list(EdgeList& el, vertex_descriptor u,
2043 boost::allow_parallel_edge_tag)
2045 typename EdgeList::iterator ei = el.begin(), e_end = el.end();
2046 for (; ei != e_end; ++ei)
2047 if ((*ei).get_target() > u)
2048 --(*ei).get_target();
2050 template <class EdgeList, class vertex_descriptor>
2052 reindex_edge_list(EdgeList& el, vertex_descriptor u,
2053 boost::disallow_parallel_edge_tag)
2055 typename EdgeList::iterator ei = el.begin(), e_end = el.end();
2056 while (ei != e_end) {
2057 typename EdgeList::value_type ce = *ei;
2059 if (ce.get_target() > u) {
2066 } // namespace detail
2068 struct vec_adj_list_tag { };
2070 template <class Graph, class Config, class Base>
2071 class vec_adj_list_impl
2072 : public adj_list_helper<Config, Base>
2074 typedef typename Config::OutEdgeList OutEdgeList;
2075 typedef typename Config::InEdgeList InEdgeList;
2076 typedef typename Config::StoredVertexList StoredVertexList;
2078 typedef typename Config::vertex_descriptor vertex_descriptor;
2079 typedef typename Config::edge_descriptor edge_descriptor;
2080 typedef typename Config::out_edge_iterator out_edge_iterator;
2081 typedef typename Config::edge_iterator edge_iterator;
2082 typedef typename Config::directed_category directed_category;
2083 typedef typename Config::vertices_size_type vertices_size_type;
2084 typedef typename Config::edges_size_type edges_size_type;
2085 typedef typename Config::degree_size_type degree_size_type;
2086 typedef typename Config::StoredEdge StoredEdge;
2087 typedef typename Config::stored_vertex stored_vertex;
2088 typedef typename Config::EdgeContainer EdgeContainer;
2089 typedef typename Config::edge_property_type edge_property_type;
2090 typedef vec_adj_list_tag graph_tag;
2092 static vertex_descriptor null_vertex()
2094 return (std::numeric_limits<vertex_descriptor>::max)();
2097 inline vec_adj_list_impl() { }
2099 inline vec_adj_list_impl(const vec_adj_list_impl& x) {
2102 inline vec_adj_list_impl& operator=(const vec_adj_list_impl& x) {
2107 inline void clear() {
2112 inline vec_adj_list_impl(vertices_size_type _num_vertices)
2113 : m_vertices(_num_vertices) { }
2115 template <class EdgeIterator>
2116 inline vec_adj_list_impl(vertices_size_type num_vertices,
2117 EdgeIterator first, EdgeIterator last)
2118 : m_vertices(num_vertices)
2120 while (first != last) {
2121 add_edge((*first).first, (*first).second,
2122 static_cast<Graph&>(*this));
2126 template <class EdgeIterator, class EdgePropertyIterator>
2127 inline vec_adj_list_impl(vertices_size_type num_vertices,
2128 EdgeIterator first, EdgeIterator last,
2129 EdgePropertyIterator ep_iter)
2130 : m_vertices(num_vertices)
2132 while (first != last) {
2133 add_edge((*first).first, (*first).second, *ep_iter,
2134 static_cast<Graph&>(*this));
2141 inline boost::integer_range<vertex_descriptor> vertex_set() const {
2142 return boost::integer_range<vertex_descriptor>(0, m_vertices.size());
2144 inline OutEdgeList& out_edge_list(vertex_descriptor v) {
2145 return m_vertices[v].m_out_edges;
2147 inline const OutEdgeList& out_edge_list(vertex_descriptor v) const {
2148 return m_vertices[v].m_out_edges;
2150 inline void copy_impl(const vec_adj_list_impl& x_)
2152 const Graph& x = static_cast<const Graph&>(x_);
2153 // Copy the stored vertex objects by adding each vertex
2154 // and copying its property object.
2155 for (vertices_size_type i = 0; i < num_vertices(x); ++i) {
2156 vertex_descriptor v = add_vertex(*this);
2157 m_vertices[v].m_property = x.m_vertices[i].m_property;
2159 // Copy the edges by adding each edge and copying its
2161 edge_iterator ei, ei_end;
2162 for (boost::tie(ei, ei_end) = edges(x); ei != ei_end; ++ei) {
2165 boost::tie(e, inserted) = add_edge(source(*ei,x), target(*ei,x) , *this);
2166 *((edge_property_type*)e.m_eproperty)
2167 = *((edge_property_type*)(*ei).m_eproperty);
2170 typename Config::EdgeContainer m_edges;
2171 StoredVertexList m_vertices;
2173 // Had to make these non-members to avoid accidental instantiation
2174 // on SGI MIPSpro C++
2175 template <class G, class C, class B>
2176 inline typename C::InEdgeList&
2177 in_edge_list(vec_adj_list_impl<G,C,B>& g,
2178 typename C::vertex_descriptor v) {
2179 return g.m_vertices[v].m_in_edges;
2181 template <class G, class C, class B>
2182 inline const typename C::InEdgeList&
2183 in_edge_list(const vec_adj_list_impl<G,C,B>& g,
2184 typename C::vertex_descriptor v) {
2185 return g.m_vertices[v].m_in_edges;
2189 template <class Graph, class Config, class Base>
2190 inline typename Config::vertex_descriptor
2191 add_vertex(vec_adj_list_impl<Graph, Config, Base>& g_) {
2192 Graph& g = static_cast<Graph&>(g_);
2193 g.m_vertices.resize(g.m_vertices.size() + 1);
2194 g.added_vertex(g.m_vertices.size() - 1);
2195 return g.m_vertices.size() - 1;
2198 template <class Graph, class Config, class Base>
2199 inline typename Config::vertex_descriptor
2200 add_vertex(const typename Config::vertex_property_type& p,
2201 vec_adj_list_impl<Graph, Config, Base>& g_) {
2202 typedef typename Config::vertex_descriptor vertex_descriptor;
2203 Graph& g = static_cast<Graph&>(g_);
2204 if (optional<vertex_descriptor> v
2205 = g.vertex_by_property(get_property_value(p, vertex_bundle)))
2207 typedef typename Config::stored_vertex stored_vertex;
2208 g.m_vertices.push_back(stored_vertex(p));
2209 g.added_vertex(g.m_vertices.size() - 1);
2210 return g.m_vertices.size() - 1;
2213 // Here we override the directed_graph_helper add_edge() function
2214 // so that the number of vertices is automatically changed if
2215 // either u or v is greater than the number of vertices.
2216 template <class Graph, class Config, class Base>
2217 inline std::pair<typename Config::edge_descriptor, bool>
2218 add_edge(typename Config::vertex_descriptor u,
2219 typename Config::vertex_descriptor v,
2220 const typename Config::edge_property_type& p,
2221 vec_adj_list_impl<Graph, Config, Base>& g_)
2223 BOOST_USING_STD_MAX();
2224 typename Config::vertex_descriptor x = max BOOST_PREVENT_MACRO_SUBSTITUTION(u, v);
2225 if (x >= num_vertices(g_))
2226 g_.m_vertices.resize(x + 1);
2227 adj_list_helper<Config, Base>& g = g_;
2228 return add_edge(u, v, p, g);
2230 template <class Graph, class Config, class Base>
2231 inline std::pair<typename Config::edge_descriptor, bool>
2232 add_edge(typename Config::vertex_descriptor u,
2233 typename Config::vertex_descriptor v,
2234 vec_adj_list_impl<Graph, Config, Base>& g_)
2236 typename Config::edge_property_type p;
2237 return add_edge(u, v, p, g_);
2242 template <class Graph, class Config, class Base>
2243 inline void remove_vertex(typename Config::vertex_descriptor v,
2244 vec_adj_list_impl<Graph, Config, Base>& g_)
2246 typedef typename Config::directed_category Cat;
2247 Graph& g = static_cast<Graph&>(g_);
2248 g.removing_vertex(v, boost::graph_detail::iterator_stability(g_.m_vertices));
2249 detail::remove_vertex_dispatch(g, v, Cat());
2252 template <class Graph, class Config, class Base>
2253 inline typename Config::vertex_descriptor
2254 vertex(typename Config::vertices_size_type n,
2255 const vec_adj_list_impl<Graph, Config, Base>&)
2263 //=========================================================================
2264 // Adjacency List Generator
2266 template <class Graph, class VertexListS, class OutEdgeListS,
2267 class DirectedS, class VertexProperty, class EdgeProperty,
2268 class GraphProperty, class EdgeListS>
2271 typedef typename detail::is_random_access<VertexListS>::type
2273 typedef typename has_property<EdgeProperty>::type has_edge_property;
2274 typedef typename DirectedS::is_directed_t DirectedT;
2275 typedef typename DirectedS::is_bidir_t BidirectionalT;
2279 typedef OutEdgeListS edgelist_selector;
2280 typedef EdgeListS global_edgelist_selector;
2282 typedef Graph graph_type;
2283 typedef EdgeProperty edge_property_type;
2284 typedef VertexProperty vertex_property_type;
2285 typedef GraphProperty graph_property_type;
2286 typedef std::size_t vertices_size_type;
2288 typedef adjacency_list_traits<OutEdgeListS, VertexListS, DirectedS>
2291 typedef typename Traits::directed_category directed_category;
2292 typedef typename Traits::edge_parallel_category edge_parallel_category;
2293 typedef typename Traits::vertex_descriptor vertex_descriptor;
2294 typedef typename Traits::edge_descriptor edge_descriptor;
2296 typedef void* vertex_ptr;
2298 // need to reorganize this to avoid instantiating stuff
2299 // that doesn't get used -JGS
2301 // VertexList and vertex_iterator
2302 typedef typename container_gen<VertexListS,
2303 vertex_ptr>::type SeqVertexList;
2304 typedef boost::integer_range<vertex_descriptor> RandVertexList;
2305 typedef typename mpl::if_<is_rand_access,
2306 RandVertexList, SeqVertexList>::type VertexList;
2308 typedef typename VertexList::iterator vertex_iterator;
2310 // EdgeContainer and StoredEdge
2312 typedef typename container_gen<EdgeListS,
2313 list_edge<vertex_descriptor, EdgeProperty> >::type EdgeContainer;
2315 typedef typename mpl::and_<DirectedT,
2316 typename mpl::not_<BidirectionalT>::type >::type on_edge_storage;
2318 typedef typename mpl::if_<on_edge_storage,
2319 std::size_t, typename EdgeContainer::size_type
2320 >::type edges_size_type;
2322 typedef typename EdgeContainer::iterator EdgeIter;
2324 typedef typename detail::is_random_access<EdgeListS>::type is_edge_ra;
2326 typedef typename mpl::if_<on_edge_storage,
2327 stored_edge_property<vertex_descriptor, EdgeProperty>,
2328 typename mpl::if_<is_edge_ra,
2329 stored_ra_edge_iter<vertex_descriptor, EdgeContainer, EdgeProperty>,
2330 stored_edge_iter<vertex_descriptor, EdgeIter, EdgeProperty>
2336 typedef typename container_gen<OutEdgeListS, StoredEdge>::type
2338 typedef typename OutEdgeList::size_type degree_size_type;
2339 typedef typename OutEdgeList::iterator OutEdgeIter;
2341 typedef boost::detail::iterator_traits<OutEdgeIter> OutEdgeIterTraits;
2342 typedef typename OutEdgeIterTraits::iterator_category OutEdgeIterCat;
2343 typedef typename OutEdgeIterTraits::difference_type OutEdgeIterDiff;
2345 typedef out_edge_iter<
2346 OutEdgeIter, vertex_descriptor, edge_descriptor, OutEdgeIterDiff
2347 > out_edge_iterator;
2349 typedef typename adjacency_iterator_generator<graph_type,
2350 vertex_descriptor, out_edge_iterator>::type adjacency_iterator;
2352 typedef OutEdgeList InEdgeList;
2353 typedef OutEdgeIter InEdgeIter;
2354 typedef OutEdgeIterCat InEdgeIterCat;
2355 typedef OutEdgeIterDiff InEdgeIterDiff;
2357 typedef in_edge_iter<
2358 InEdgeIter, vertex_descriptor, edge_descriptor, InEdgeIterDiff
2361 typedef typename inv_adjacency_iterator_generator<graph_type,
2362 vertex_descriptor, in_edge_iterator>::type inv_adjacency_iterator;
2366 typedef boost::detail::iterator_traits<EdgeIter> EdgeIterTraits;
2367 typedef typename EdgeIterTraits::iterator_category EdgeIterCat;
2368 typedef typename EdgeIterTraits::difference_type EdgeIterDiff;
2370 typedef undirected_edge_iter<
2374 > UndirectedEdgeIter; // also used for bidirectional
2376 typedef adj_list_edge_iterator<vertex_iterator, out_edge_iterator,
2377 graph_type> DirectedEdgeIter;
2379 typedef typename mpl::if_<on_edge_storage,
2380 DirectedEdgeIter, UndirectedEdgeIter>::type edge_iterator;
2382 // stored_vertex and StoredVertexList
2383 typedef typename container_gen<VertexListS, vertex_ptr>::type
2384 SeqStoredVertexList;
2385 struct seq_stored_vertex {
2386 seq_stored_vertex() { }
2387 seq_stored_vertex(const VertexProperty& p) : m_property(p) { }
2388 OutEdgeList m_out_edges;
2389 VertexProperty m_property;
2390 typename SeqStoredVertexList::iterator m_position;
2392 struct bidir_seq_stored_vertex {
2393 bidir_seq_stored_vertex() { }
2394 bidir_seq_stored_vertex(const VertexProperty& p) : m_property(p) { }
2395 OutEdgeList m_out_edges;
2396 InEdgeList m_in_edges;
2397 VertexProperty m_property;
2398 typename SeqStoredVertexList::iterator m_position;
2400 struct rand_stored_vertex {
2401 rand_stored_vertex() { }
2402 rand_stored_vertex(const VertexProperty& p) : m_property(p) { }
2403 OutEdgeList m_out_edges;
2404 VertexProperty m_property;
2406 struct bidir_rand_stored_vertex {
2407 bidir_rand_stored_vertex() { }
2408 bidir_rand_stored_vertex(const VertexProperty& p) : m_property(p) { }
2409 OutEdgeList m_out_edges;
2410 InEdgeList m_in_edges;
2411 VertexProperty m_property;
2413 typedef typename mpl::if_<is_rand_access,
2414 typename mpl::if_<BidirectionalT,
2415 bidir_rand_stored_vertex, rand_stored_vertex>::type,
2416 typename mpl::if_<BidirectionalT,
2417 bidir_seq_stored_vertex, seq_stored_vertex>::type
2418 >::type StoredVertex;
2419 struct stored_vertex : public StoredVertex {
2421 stored_vertex(const VertexProperty& p) : StoredVertex(p) { }
2424 typedef typename container_gen<VertexListS, stored_vertex>::type
2425 RandStoredVertexList;
2426 typedef typename mpl::if_< is_rand_access,
2427 RandStoredVertexList, SeqStoredVertexList>::type StoredVertexList;
2431 typedef typename mpl::if_<BidirectionalT,
2432 bidirectional_graph_helper_with_property<config>,
2433 typename mpl::if_<DirectedT,
2434 directed_graph_helper<config>,
2435 undirected_graph_helper<config>
2437 >::type DirectedHelper;
2439 typedef typename mpl::if_<is_rand_access,
2440 vec_adj_list_impl<Graph, config, DirectedHelper>,
2441 adj_list_impl<Graph, config, DirectedHelper>
2446 } // namespace detail
2448 //=========================================================================
2449 // Vertex Property Maps
2451 template <class Graph, class ValueType, class Reference, class Tag>
2452 struct adj_list_vertex_property_map
2453 : public boost::put_get_helper<
2455 adj_list_vertex_property_map<Graph, ValueType, Reference, Tag>
2458 typedef typename Graph::stored_vertex StoredVertex;
2459 typedef ValueType value_type;
2460 typedef Reference reference;
2461 typedef typename Graph::vertex_descriptor key_type;
2462 typedef boost::lvalue_property_map_tag category;
2463 inline adj_list_vertex_property_map(const Graph* = 0, Tag tag = Tag()): m_tag(tag) { }
2464 inline Reference operator[](key_type v) const {
2465 StoredVertex* sv = (StoredVertex*)v;
2466 return get_property_value(sv->m_property, m_tag);
2468 inline Reference operator()(key_type v) const {
2469 return this->operator[](v);
2474 template <class Graph, class Property, class PropRef>
2475 struct adj_list_vertex_all_properties_map
2476 : public boost::put_get_helper<PropRef,
2477 adj_list_vertex_all_properties_map<Graph, Property, PropRef>
2480 typedef typename Graph::stored_vertex StoredVertex;
2481 typedef Property value_type;
2482 typedef PropRef reference;
2483 typedef typename Graph::vertex_descriptor key_type;
2484 typedef boost::lvalue_property_map_tag category;
2485 inline adj_list_vertex_all_properties_map(const Graph* = 0, vertex_all_t = vertex_all_t()) { }
2486 inline PropRef operator[](key_type v) const {
2487 StoredVertex* sv = (StoredVertex*)v;
2488 return sv->m_property;
2490 inline PropRef operator()(key_type v) const {
2491 return this->operator[](v);
2495 template <class Graph, class GraphPtr, class ValueType, class Reference,
2497 struct vec_adj_list_vertex_property_map
2498 : public boost::put_get_helper<
2500 vec_adj_list_vertex_property_map<Graph,GraphPtr,ValueType,Reference,
2504 typedef ValueType value_type;
2505 typedef Reference reference;
2506 typedef typename boost::graph_traits<Graph>::vertex_descriptor key_type;
2507 typedef boost::lvalue_property_map_tag category;
2508 vec_adj_list_vertex_property_map(GraphPtr g = 0, Tag tag = Tag()) : m_g(g), m_tag(tag) { }
2509 inline Reference operator[](key_type v) const {
2510 return get_property_value(m_g->m_vertices[v].m_property, m_tag);
2512 inline Reference operator()(key_type v) const {
2513 return this->operator[](v);
2519 template <class Graph, class GraphPtr, class Property, class PropertyRef>
2520 struct vec_adj_list_vertex_all_properties_map
2521 : public boost::put_get_helper<PropertyRef,
2522 vec_adj_list_vertex_all_properties_map<Graph,GraphPtr,Property,
2526 typedef Property value_type;
2527 typedef PropertyRef reference;
2528 typedef typename boost::graph_traits<Graph>::vertex_descriptor key_type;
2529 typedef boost::lvalue_property_map_tag category;
2530 vec_adj_list_vertex_all_properties_map(GraphPtr g = 0, vertex_all_t = vertex_all_t()) : m_g(g) { }
2531 inline PropertyRef operator[](key_type v) const {
2532 return m_g->m_vertices[v].m_property;
2534 inline PropertyRef operator()(key_type v) const {
2535 return this->operator[](v);
2540 struct adj_list_any_vertex_pa {
2541 template <class Tag, class Graph, class Property>
2543 typedef typename property_value<Property, Tag>::type value_type;
2544 typedef value_type& reference;
2545 typedef const value_type& const_reference;
2547 typedef adj_list_vertex_property_map
2548 <Graph, value_type, reference, Tag> type;
2549 typedef adj_list_vertex_property_map
2550 <Graph, value_type, const_reference, Tag> const_type;
2553 struct adj_list_all_vertex_pa {
2554 template <class Tag, class Graph, class Property>
2556 typedef typename Graph::vertex_descriptor Vertex;
2557 typedef adj_list_vertex_all_properties_map<Graph,Property,
2559 typedef adj_list_vertex_all_properties_map<Graph,Property,
2560 const Property&> const_type;
2564 template <class Property, class Vertex>
2565 struct vec_adj_list_vertex_id_map
2566 : public boost::put_get_helper<
2567 Vertex, vec_adj_list_vertex_id_map<Property, Vertex>
2570 typedef Vertex value_type;
2571 typedef Vertex key_type;
2572 typedef Vertex reference;
2573 typedef boost::readable_property_map_tag category;
2574 inline vec_adj_list_vertex_id_map() { }
2575 template <class Graph>
2576 inline vec_adj_list_vertex_id_map(const Graph&, vertex_index_t) { }
2577 inline value_type operator[](key_type v) const { return v; }
2578 inline value_type operator()(key_type v) const { return v; }
2581 struct vec_adj_list_any_vertex_pa {
2582 template <class Tag, class Graph, class Property>
2584 typedef typename property_value<Property, Tag>::type value_type;
2585 typedef value_type& reference;
2586 typedef const value_type& const_reference;
2588 typedef vec_adj_list_vertex_property_map
2589 <Graph, Graph*, value_type, reference, Tag> type;
2590 typedef vec_adj_list_vertex_property_map
2591 <Graph, const Graph*, value_type, const_reference, Tag> const_type;
2594 struct vec_adj_list_id_vertex_pa {
2595 template <class Tag, class Graph, class Property>
2597 typedef typename Graph::vertex_descriptor Vertex;
2598 typedef vec_adj_list_vertex_id_map<Property, Vertex> type;
2599 typedef vec_adj_list_vertex_id_map<Property, Vertex> const_type;
2602 struct vec_adj_list_all_vertex_pa {
2603 template <class Tag, class Graph, class Property>
2605 typedef typename Graph::vertex_descriptor Vertex;
2606 typedef vec_adj_list_vertex_all_properties_map
2607 <Graph, Graph*, Property, Property&> type;
2608 typedef vec_adj_list_vertex_all_properties_map
2609 <Graph, const Graph*, Property, const Property&> const_type;
2613 template <class Tag, class Graph, class Property>
2614 struct adj_list_choose_vertex_pa
2616 boost::is_same<Tag, vertex_all_t>,
2617 adj_list_all_vertex_pa,
2618 adj_list_any_vertex_pa>::type
2619 ::template bind_<Tag, Graph, Property>
2623 template <class Tag>
2624 struct vec_adj_list_choose_vertex_pa_helper {
2625 typedef vec_adj_list_any_vertex_pa type;
2628 struct vec_adj_list_choose_vertex_pa_helper<vertex_index_t> {
2629 typedef vec_adj_list_id_vertex_pa type;
2632 struct vec_adj_list_choose_vertex_pa_helper<vertex_all_t> {
2633 typedef vec_adj_list_all_vertex_pa type;
2635 template <class Tag, class Graph, class Property>
2636 struct vec_adj_list_choose_vertex_pa
2637 : vec_adj_list_choose_vertex_pa_helper<Tag>::type::template bind_<Tag,Graph,Property>
2639 } // namespace detail
2641 //=========================================================================
2642 // Edge Property Map
2644 template <class Directed, class Value, class Ref, class Vertex,
2645 class Property, class Tag>
2646 struct adj_list_edge_property_map
2647 : public put_get_helper<
2649 adj_list_edge_property_map<Directed, Value, Ref, Vertex, Property,
2654 explicit adj_list_edge_property_map(Tag tag = Tag()): tag(tag) {}
2656 typedef Value value_type;
2657 typedef Ref reference;
2658 typedef detail::edge_desc_impl<Directed, Vertex> key_type;
2659 typedef boost::lvalue_property_map_tag category;
2660 inline Ref operator[](key_type e) const {
2661 Property& p = *(Property*)e.get_property();
2662 return get_property_value(p, tag);
2664 inline Ref operator()(key_type e) const {
2665 return this->operator[](e);
2669 template <class Directed, class Property, class PropRef, class PropPtr,
2671 struct adj_list_edge_all_properties_map
2672 : public put_get_helper<PropRef,
2673 adj_list_edge_all_properties_map<Directed, Property, PropRef,
2677 explicit adj_list_edge_all_properties_map(edge_all_t = edge_all_t()) {}
2678 typedef Property value_type;
2679 typedef PropRef reference;
2680 typedef detail::edge_desc_impl<Directed, Vertex> key_type;
2681 typedef boost::lvalue_property_map_tag category;
2682 inline PropRef operator[](key_type e) const {
2683 return *(PropPtr)e.get_property();
2685 inline PropRef operator()(key_type e) const {
2686 return this->operator[](e);
2690 // Edge Property Maps
2693 struct adj_list_any_edge_pmap {
2694 template <class Graph, class Property, class Tag>
2696 typedef typename property_value<Property,Tag>::type value_type;
2697 typedef value_type& reference;
2698 typedef const value_type& const_reference;
2700 typedef adj_list_edge_property_map
2701 <typename Graph::directed_category, value_type, reference,
2702 typename Graph::vertex_descriptor,Property,Tag> type;
2703 typedef adj_list_edge_property_map
2704 <typename Graph::directed_category, value_type, const_reference,
2705 typename Graph::vertex_descriptor,const Property, Tag> const_type;
2708 struct adj_list_all_edge_pmap {
2709 template <class Graph, class Property, class Tag>
2711 typedef adj_list_edge_all_properties_map
2712 <typename Graph::directed_category, Property, Property&, Property*,
2713 typename Graph::vertex_descriptor> type;
2714 typedef adj_list_edge_all_properties_map
2715 <typename Graph::directed_category, Property, const Property&,
2716 const Property*, typename Graph::vertex_descriptor> const_type;
2720 template <class Tag>
2721 struct adj_list_choose_edge_pmap_helper {
2722 typedef adj_list_any_edge_pmap type;
2725 struct adj_list_choose_edge_pmap_helper<edge_all_t> {
2726 typedef adj_list_all_edge_pmap type;
2728 template <class Tag, class Graph, class Property>
2729 struct adj_list_choose_edge_pmap
2730 : adj_list_choose_edge_pmap_helper<Tag>::type::template bind_<Graph, Property, Tag>
2732 struct adj_list_edge_property_selector {
2733 template <class Graph, class Property, class Tag>
2734 struct bind_: adj_list_choose_edge_pmap<Tag, Graph, Property> {};
2736 } // namespace detail
2739 struct edge_property_selector<adj_list_tag> {
2740 typedef detail::adj_list_edge_property_selector type;
2743 struct edge_property_selector<vec_adj_list_tag> {
2744 typedef detail::adj_list_edge_property_selector type;
2747 // Vertex Property Maps
2749 struct adj_list_vertex_property_selector {
2750 template <class Graph, class Property, class Tag>
2752 : detail::adj_list_choose_vertex_pa<Tag,Graph,Property>
2756 struct vertex_property_selector<adj_list_tag> {
2757 typedef adj_list_vertex_property_selector type;
2760 struct vec_adj_list_vertex_property_selector {
2761 template <class Graph, class Property, class Tag>
2762 struct bind_: detail::vec_adj_list_choose_vertex_pa<Tag,Graph,Property> {};
2765 struct vertex_property_selector<vec_adj_list_tag> {
2766 typedef vec_adj_list_vertex_property_selector type;
2769 } // namespace boost
2773 template <typename V>
2774 struct hash< boost::detail::stored_edge<V> >
2777 operator()(const boost::detail::stored_edge<V>& e) const
2779 return hash<V>()(e.m_target);
2783 template <typename V, typename P>
2784 struct hash< boost::detail::stored_edge_property <V,P> >
2787 operator()(const boost::detail::stored_edge_property<V,P>& e) const
2789 return hash<V>()(e.m_target);
2793 template <typename V, typename I, typename P>
2794 struct hash< boost::detail::stored_edge_iter<V,I, P> >
2797 operator()(const boost::detail::stored_edge_iter<V,I,P>& e) const
2799 return hash<V>()(e.m_target);
2806 #endif // BOOST_GRAPH_DETAIL_DETAIL_ADJACENCY_LIST_CCT
2809 Implementation Notes:
2811 Many of the public interface functions in this file would have been
2812 more conveniently implemented as inline friend functions.
2813 However there are a few compiler bugs that make that approach
2816 1. g++ inline friend in namespace bug
2817 2. g++ using clause doesn't work with inline friends
2818 3. VC++ doesn't have Koenig lookup
2820 For these reasons, the functions were all written as non-inline free
2821 functions, and static cast was used to convert from the helper
2822 class to the adjacency_list derived class.
2824 Looking back, it might have been better to write out all functions
2825 in terms of the adjacency_list, and then use a tag to dispatch
2826 to the various helpers instead of using inheritance.