2 //=======================================================================
3 // Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
4 // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek
6 // Distributed under the Boost Software License, Version 1.0. (See
7 // accompanying file LICENSE_1_0.txt or copy at
8 // http://www.boost.org/LICENSE_1_0.txt)
9 //=======================================================================
11 #ifndef BOOST_GRAPH_DETAIL_ADJACENCY_LIST_HPP
12 #define BOOST_GRAPH_DETAIL_ADJACENCY_LIST_HPP
14 #include <map> // for vertex_map in copy_impl
15 #include <boost/config.hpp>
16 #include <boost/detail/workaround.hpp>
17 #include <boost/operators.hpp>
18 #include <boost/property_map.hpp>
19 #include <boost/pending/integer_range.hpp>
20 #include <boost/graph/graph_traits.hpp>
23 #include <boost/limits.hpp>
25 #include <boost/iterator/iterator_adaptor.hpp>
27 #include <boost/pending/ct_if.hpp>
28 #include <boost/graph/graph_concepts.hpp>
29 #include <boost/pending/container_traits.hpp>
30 #include <boost/graph/detail/adj_list_edge_iterator.hpp>
31 #include <boost/graph/properties.hpp>
32 #include <boost/pending/property.hpp>
33 #include <boost/graph/adjacency_iterator.hpp>
34 #include <boost/static_assert.hpp>
36 // Symbol truncation problems with MSVC, trying to shorten names.
37 #define stored_edge se_
38 #define stored_edge_property sep_
39 #define stored_edge_iter sei_
42 Outline for this file:
44 out_edge_iterator and in_edge_iterator implementation
45 edge_iterator for undirected graph
46 stored edge types (these object live in the out-edge/in-edge lists)
47 directed edges helper class
48 directed graph helper class
49 undirected graph helper class
50 bidirectional graph helper class
51 bidirectional graph helper class (without edge properties)
52 bidirectional graph helper class (with edge properties)
53 adjacency_list helper class
55 vec_adj_list_impl class
61 Note: it would be nice to merge some of the undirected and
62 bidirectional code... it is awful similar.
70 template <typename DirectedS>
71 struct directed_category_traits {
72 typedef directed_tag directed_category;
76 struct directed_category_traits<directedS> {
77 typedef directed_tag directed_category;
80 struct directed_category_traits<undirectedS> {
81 typedef undirected_tag directed_category;
84 struct directed_category_traits<bidirectionalS> {
85 typedef bidirectional_tag directed_category;
88 template <class Vertex>
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;
99 template <class EdgeList, class vertex_descriptor>
100 void erase_from_incidence_list(EdgeList& el, vertex_descriptor v,
101 allow_parallel_edge_tag)
103 boost::graph_detail::erase_if(el, detail::target_is<vertex_descriptor>(v));
106 template <class EdgeList, class vertex_descriptor>
107 void erase_from_incidence_list(EdgeList& el, vertex_descriptor v,
108 disallow_parallel_edge_tag)
110 typedef typename EdgeList::value_type StoredEdge;
111 el.erase(StoredEdge(v));
114 //=========================================================================
115 // Out-Edge and In-Edge Iterator Implementation
117 template <class BaseIter, class VertexDescriptor, class EdgeDescriptor, class Difference>
120 out_edge_iter<BaseIter, VertexDescriptor, EdgeDescriptor, Difference>
128 typedef iterator_adaptor<
129 out_edge_iter<BaseIter, VertexDescriptor, EdgeDescriptor, Difference>
137 inline out_edge_iter() { }
138 inline out_edge_iter(const BaseIter& i, const VertexDescriptor& src)
139 : super_t(i), m_src(src) { }
141 inline EdgeDescriptor
144 return EdgeDescriptor(m_src, (*this->base()).get_target(),
145 &(*this->base()).get_property());
147 VertexDescriptor m_src;
150 template <class BaseIter, class VertexDescriptor, class EdgeDescriptor, class Difference>
153 in_edge_iter<BaseIter, VertexDescriptor, EdgeDescriptor, Difference>
161 typedef iterator_adaptor<
162 in_edge_iter<BaseIter, VertexDescriptor, EdgeDescriptor, Difference>
170 inline in_edge_iter() { }
171 inline in_edge_iter(const BaseIter& i, const VertexDescriptor& src)
172 : super_t(i), m_src(src) { }
174 inline EdgeDescriptor
177 return EdgeDescriptor((*this->base()).get_target(), m_src,
178 &this->base()->get_property());
180 VertexDescriptor m_src;
183 //=========================================================================
184 // Undirected Edge Iterator Implementation
186 template <class EdgeIter, class EdgeDescriptor, class Difference>
187 struct undirected_edge_iter
189 undirected_edge_iter<EdgeIter, EdgeDescriptor, Difference>
197 typedef iterator_adaptor<
198 undirected_edge_iter<EdgeIter, EdgeDescriptor, Difference>
206 undirected_edge_iter() {}
208 explicit undirected_edge_iter(EdgeIter i)
211 inline EdgeDescriptor
212 dereference() const {
213 return EdgeDescriptor(
214 (*this->base()).m_source
215 , (*this->base()).m_target
216 , &this->base()->get_property());
220 //=========================================================================
221 // Edge Storage Types (stored in the out-edge/in-edge lists)
223 template <class Vertex>
225 : public boost::equality_comparable1< stored_edge<Vertex>,
226 boost::less_than_comparable1< stored_edge<Vertex> > >
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;
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;
251 template <class Vertex>
252 no_property stored_edge<Vertex>::s_prop;
254 template <class Vertex, class Property>
255 class stored_edge_property : public stored_edge<Vertex> {
256 typedef stored_edge_property self;
257 typedef stored_edge<Vertex> Base;
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) {
268 m_property = const_cast<self&>(x).m_property;
271 inline Property& get_property() { return *m_property; }
272 inline const Property& get_property() const { return *m_property; }
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;
282 template <class Vertex, class Iter, class Property>
283 class stored_edge_iter
284 : public stored_edge<Vertex>
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();
297 inline Iter get_iter() const { return m_iter; }
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>
309 typedef typename EdgeVec::iterator Iter;
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();
320 inline Iter get_iter() const { return m_vec->begin() + m_i; }
326 } // namespace detail
328 template <class Tag, class Vertex, class Property>
329 const typename property_value<Property,Tag>::type&
330 get(Tag property_tag,
331 const detail::stored_edge_property<Vertex, Property>& e)
333 return get_property_value(e.get_property(), property_tag);
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)
341 return get_property_value(e.get_property(), property_tag);
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)
349 return get_property_value(e.get_property(), property_tag);
352 //=========================================================================
353 // Directed Edges Helper Class
358 template <class edge_descriptor, class EdgeList, class StoredProperty>
360 remove_directed_edge_dispatch(edge_descriptor, EdgeList& el,
363 for (typename EdgeList::iterator i = el.begin();
365 if (&(*i).get_property() == &p) {
371 template <class incidence_iterator, class EdgeList, class Predicate>
373 remove_directed_edge_if_dispatch(incidence_iterator first,
374 incidence_iterator last,
375 EdgeList& el, Predicate pred,
376 boost::allow_parallel_edge_tag)
379 while (first != last && !pred(*first))
381 incidence_iterator i = first;
383 for (; i != last; ++i)
385 *first.base() = *i.base();
388 el.erase(first.base(), el.end());
390 template <class incidence_iterator, class EdgeList, class Predicate>
392 remove_directed_edge_if_dispatch(incidence_iterator first,
393 incidence_iterator last,
396 boost::disallow_parallel_edge_tag)
398 for (incidence_iterator next = first;
399 first != last; first = next) {
402 el.erase( first.base() );
406 template <class PropT, class Graph, class incidence_iterator,
407 class EdgeList, class Predicate>
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)
415 typedef typename Graph::global_edgelist_selector EdgeListS;
416 BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
419 while (first != last && !pred(*first))
421 incidence_iterator i = first;
422 bool self_loop_removed = false;
424 for (; i != last; ++i) {
425 if (self_loop_removed) {
426 /* With self loops, the descriptor will show up
427 * twice. The first time it will be removed, and now it
430 self_loop_removed = false;
432 else if (!pred(*i)) {
433 *first.base() = *i.base();
436 if (source(*i, g) == target(*i, g)) self_loop_removed = true;
438 // Remove the edge from the target
439 detail::remove_directed_edge_dispatch
441 g.out_edge_list(target(*i, g)),
442 *(PropT*)(*i).get_property());
445 // Erase the edge property
446 g.m_edges.erase( (*i.base()).get_iter() );
449 el.erase(first.base(), el.end());
451 template <class PropT, class Graph, class incidence_iterator,
452 class EdgeList, class Predicate>
454 undirected_remove_out_edge_if_dispatch(Graph& g,
455 incidence_iterator first,
456 incidence_iterator last,
459 boost::disallow_parallel_edge_tag)
461 typedef typename Graph::global_edgelist_selector EdgeListS;
462 BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
464 for (incidence_iterator next = first;
465 first != last; first = next) {
468 if (source(*first, g) != target(*first, g)) {
469 // Remove the edge from the target
470 detail::remove_directed_edge_dispatch
472 g.out_edge_list(target(*first, g)),
473 *(PropT*)(*first).get_property());
476 // Erase the edge property
477 g.m_edges.erase( (*first.base()).get_iter() );
479 // Erase the edge in the source
480 el.erase( first.base() );
486 template <class edge_descriptor, class EdgeList, class StoredProperty>
488 remove_directed_edge_dispatch(edge_descriptor e, EdgeList& el,
491 for (typename EdgeList::iterator i = el.begin();
493 if ((*i).get_target() == e.m_target) {
499 } // namespace detail
501 template <class Config>
502 struct directed_edges_helper {
504 // Placement of these overloaded remove_edge() functions
505 // inside the class avoids a VC++ bug.
509 remove_edge(typename Config::edge_descriptor e)
511 typedef typename Config::graph_type graph_type;
512 graph_type& g = static_cast<graph_type&>(*this);
513 typename Config::OutEdgeList& el = g.out_edge_list(source(e, g));
514 typedef typename Config::OutEdgeList::value_type::property_type PType;
515 detail::remove_directed_edge_dispatch(e, el,
516 *(PType*)e.get_property());
521 remove_edge(typename Config::out_edge_iterator iter)
523 typedef typename Config::graph_type graph_type;
524 graph_type& g = static_cast<graph_type&>(*this);
525 typename Config::edge_descriptor e = *iter;
526 typename Config::OutEdgeList& el = g.out_edge_list(source(e, g));
527 el.erase(iter.base());
533 template <class Config>
534 inline std::pair<typename Config::edge_iterator,
535 typename Config::edge_iterator>
536 edges(const directed_edges_helper<Config>& g_)
538 typedef typename Config::graph_type graph_type;
539 typedef typename Config::edge_iterator edge_iterator;
540 const graph_type& cg = static_cast<const graph_type&>(g_);
541 graph_type& g = const_cast<graph_type&>(cg);
542 return std::make_pair( edge_iterator(g.vertex_set().begin(),
543 g.vertex_set().begin(),
544 g.vertex_set().end(), g),
545 edge_iterator(g.vertex_set().begin(),
546 g.vertex_set().end(),
547 g.vertex_set().end(), g) );
550 //=========================================================================
551 // Directed Graph Helper Class
553 struct adj_list_dir_traversal_tag :
554 public virtual vertex_list_graph_tag,
555 public virtual incidence_graph_tag,
556 public virtual adjacency_graph_tag,
557 public virtual edge_list_graph_tag { };
559 template <class Config>
560 struct directed_graph_helper
561 : public directed_edges_helper<Config> {
562 typedef typename Config::edge_descriptor edge_descriptor;
563 typedef adj_list_dir_traversal_tag traversal_category;
567 template <class Config>
569 remove_edge(typename Config::vertex_descriptor u,
570 typename Config::vertex_descriptor v,
571 directed_graph_helper<Config>& g_)
573 typedef typename Config::graph_type graph_type;
574 typedef typename Config::edge_parallel_category Cat;
575 graph_type& g = static_cast<graph_type&>(g_);
576 detail::erase_from_incidence_list(g.out_edge_list(u), v, Cat());
579 template <class Config, class Predicate>
581 remove_out_edge_if(typename Config::vertex_descriptor u, Predicate pred,
582 directed_graph_helper<Config>& g_)
584 typedef typename Config::graph_type graph_type;
585 graph_type& g = static_cast<graph_type&>(g_);
586 typename Config::out_edge_iterator first, last;
587 tie(first, last) = out_edges(u, g);
588 typedef typename Config::edge_parallel_category edge_parallel_category;
589 detail::remove_directed_edge_if_dispatch
590 (first, last, g.out_edge_list(u), pred, edge_parallel_category());
593 template <class Config, class Predicate>
595 remove_edge_if(Predicate pred, directed_graph_helper<Config>& g_)
597 typedef typename Config::graph_type graph_type;
598 graph_type& g = static_cast<graph_type&>(g_);
600 typename Config::vertex_iterator vi, vi_end;
601 for (tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi)
602 remove_out_edge_if(*vi, pred, g);
605 template <class EdgeOrIter, class Config>
607 remove_edge(EdgeOrIter e_or_iter, directed_graph_helper<Config>& g_)
609 g_.remove_edge(e_or_iter);
612 // O(V + E) for allow_parallel_edges
613 // O(V * log(E/V)) for disallow_parallel_edges
614 template <class Config>
616 clear_vertex(typename Config::vertex_descriptor u,
617 directed_graph_helper<Config>& g_)
619 typedef typename Config::graph_type graph_type;
620 typedef typename Config::edge_parallel_category Cat;
621 graph_type& g = static_cast<graph_type&>(g_);
622 typename Config::vertex_iterator vi, viend;
623 for (boost::tie(vi, viend) = vertices(g); vi != viend; ++vi)
624 detail::erase_from_incidence_list(g.out_edge_list(*vi), u, Cat());
625 g.out_edge_list(u).clear();
626 // clear() should be a req of Sequence and AssociativeContainer,
627 // or maybe just Container
630 template <class Config>
632 clear_out_edges(typename Config::vertex_descriptor u,
633 directed_graph_helper<Config>& g_)
635 typedef typename Config::graph_type graph_type;
636 typedef typename Config::edge_parallel_category Cat;
637 graph_type& g = static_cast<graph_type&>(g_);
638 g.out_edge_list(u).clear();
639 // clear() should be a req of Sequence and AssociativeContainer,
640 // or maybe just Container
643 // O(V), could do better...
644 template <class Config>
645 inline typename Config::edges_size_type
646 num_edges(const directed_graph_helper<Config>& g_)
648 typedef typename Config::graph_type graph_type;
649 const graph_type& g = static_cast<const graph_type&>(g_);
650 typename Config::edges_size_type num_e = 0;
651 typename Config::vertex_iterator vi, vi_end;
652 for (boost::tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi)
653 num_e += out_degree(*vi, g);
656 // O(1) for allow_parallel_edge_tag
657 // O(log(E/V)) for disallow_parallel_edge_tag
658 template <class Config>
659 inline std::pair<typename directed_graph_helper<Config>::edge_descriptor, bool>
660 add_edge(typename Config::vertex_descriptor u,
661 typename Config::vertex_descriptor v,
662 const typename Config::edge_property_type& p,
663 directed_graph_helper<Config>& g_)
665 typedef typename Config::edge_descriptor edge_descriptor;
666 typedef typename Config::graph_type graph_type;
667 typedef typename Config::StoredEdge StoredEdge;
668 graph_type& g = static_cast<graph_type&>(g_);
669 typename Config::OutEdgeList::iterator i;
671 boost::tie(i, inserted) = boost::graph_detail::push(g.out_edge_list(u),
673 return std::make_pair(edge_descriptor(u, v, &(*i).get_property()),
676 // Did not use default argument here because that
677 // causes Visual C++ to get confused.
678 template <class Config>
679 inline std::pair<typename Config::edge_descriptor, bool>
680 add_edge(typename Config::vertex_descriptor u,
681 typename Config::vertex_descriptor v,
682 directed_graph_helper<Config>& g_)
684 typename Config::edge_property_type p;
685 return add_edge(u, v, p, g_);
687 //=========================================================================
688 // Undirected Graph Helper Class
690 template <class Config>
691 struct undirected_graph_helper;
693 struct undir_adj_list_traversal_tag :
694 public virtual vertex_list_graph_tag,
695 public virtual incidence_graph_tag,
696 public virtual adjacency_graph_tag,
697 public virtual edge_list_graph_tag,
698 public virtual bidirectional_graph_tag { };
702 // using class with specialization for dispatch is a VC++ workaround.
703 template <class StoredProperty>
704 struct remove_undirected_edge_dispatch {
707 template <class edge_descriptor, class Config>
709 apply(edge_descriptor e,
710 undirected_graph_helper<Config>& g_,
713 typedef typename Config::global_edgelist_selector EdgeListS;
714 BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
716 typedef typename Config::graph_type graph_type;
717 graph_type& g = static_cast<graph_type&>(g_);
719 typename Config::OutEdgeList& out_el = g.out_edge_list(source(e, g));
720 typename Config::OutEdgeList::iterator out_i = out_el.begin();
721 for (; out_i != out_el.end(); ++out_i)
722 if (&(*out_i).get_property() == &p) {
726 typename Config::OutEdgeList& in_el = g.out_edge_list(target(e, g));
727 typename Config::OutEdgeList::iterator in_i = in_el.begin();
728 for (; in_i != in_el.end(); ++in_i)
729 if (&(*in_i).get_property() == &p) {
730 g.m_edges.erase((*in_i).get_iter());
738 struct remove_undirected_edge_dispatch<no_property> {
740 template <class edge_descriptor, class Config>
742 apply(edge_descriptor e,
743 undirected_graph_helper<Config>& g_,
746 typedef typename Config::global_edgelist_selector EdgeListS;
747 BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
749 typedef typename Config::graph_type graph_type;
750 graph_type& g = static_cast<graph_type&>(g_);
751 no_property* p = (no_property*)e.get_property();
752 typename Config::OutEdgeList& out_el = g.out_edge_list(source(e, g));
753 typename Config::OutEdgeList::iterator out_i = out_el.begin();
754 for (; out_i != out_el.end(); ++out_i)
755 if (&(*out_i).get_property() == p) {
759 typename Config::OutEdgeList& in_el = g.out_edge_list(target(e, g));
760 typename Config::OutEdgeList::iterator in_i = in_el.begin();
761 for (; in_i != in_el.end(); ++in_i)
762 if (&(*in_i).get_property() == p) {
763 g.m_edges.erase((*in_i).get_iter());
771 template <class Graph, class EdgeList, class Vertex>
773 remove_edge_and_property(Graph& g, EdgeList& el, Vertex v,
774 boost::allow_parallel_edge_tag cat)
776 typedef typename Graph::global_edgelist_selector EdgeListS;
777 BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
779 typedef typename EdgeList::value_type StoredEdge;
780 typename EdgeList::iterator i = el.begin(), end = el.end();
781 for (; i != end; ++i)
782 if ((*i).get_target() == v)
783 g.m_edges.erase((*i).get_iter());
784 detail::erase_from_incidence_list(el, v, cat);
787 template <class Graph, class EdgeList, class Vertex>
789 remove_edge_and_property(Graph& g, EdgeList& el, Vertex v,
790 boost::disallow_parallel_edge_tag)
792 typedef typename Graph::global_edgelist_selector EdgeListS;
793 BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
795 typedef typename EdgeList::value_type StoredEdge;
796 typename EdgeList::iterator i = el.find(StoredEdge(v)), end = el.end();
798 g.m_edges.erase((*i).get_iter());
803 } // namespace detail
805 template <class Vertex, class EdgeProperty>
806 struct list_edge // short name due to VC++ truncation and linker problems
807 : public boost::detail::edge_base<boost::undirected_tag, Vertex>
809 typedef EdgeProperty property_type;
810 typedef boost::detail::edge_base<boost::undirected_tag, Vertex> Base;
811 list_edge(Vertex u, Vertex v, const EdgeProperty& p = EdgeProperty())
812 : Base(u, v), m_property(p) { }
813 EdgeProperty& get_property() { return m_property; }
814 const EdgeProperty& get_property() const { return m_property; }
815 // the following methods should never be used, but are needed
816 // to make SGI MIPSpro C++ happy
818 bool operator==(const list_edge&) const { return false; }
819 bool operator<(const list_edge&) const { return false; }
820 EdgeProperty m_property;
823 template <class Config>
824 struct undirected_graph_helper {
826 typedef undir_adj_list_traversal_tag traversal_category;
828 // Placement of these overloaded remove_edge() functions
829 // inside the class avoids a VC++ bug.
833 remove_edge(typename Config::edge_descriptor e)
835 typedef typename Config::global_edgelist_selector EdgeListS;
836 BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
838 typedef typename Config::OutEdgeList::value_type::property_type PType;
839 detail::remove_undirected_edge_dispatch<PType>::apply
840 (e, *this, *(PType*)e.get_property());
844 remove_edge(typename Config::out_edge_iterator iter)
846 this->remove_edge(*iter);
850 // Had to make these non-members to avoid accidental instantiation
851 // on SGI MIPSpro C++
853 inline typename C::InEdgeList&
854 in_edge_list(undirected_graph_helper<C>&,
855 typename C::vertex_descriptor v)
857 typename C::stored_vertex* sv = (typename C::stored_vertex*)v;
858 return sv->m_out_edges;
861 inline const typename C::InEdgeList&
862 in_edge_list(const undirected_graph_helper<C>&,
863 typename C::vertex_descriptor v) {
864 typename C::stored_vertex* sv = (typename C::stored_vertex*)v;
865 return sv->m_out_edges;
869 template <class EdgeOrIter, class Config>
871 remove_edge(EdgeOrIter e, undirected_graph_helper<Config>& g_)
873 typedef typename Config::global_edgelist_selector EdgeListS;
874 BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
879 // O(E/V) or O(log(E/V))
880 template <class Config>
882 remove_edge(typename Config::vertex_descriptor u,
883 typename Config::vertex_descriptor v,
884 undirected_graph_helper<Config>& g_)
886 typedef typename Config::global_edgelist_selector EdgeListS;
887 BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
889 typedef typename Config::graph_type graph_type;
890 graph_type& g = static_cast<graph_type&>(g_);
891 typedef typename Config::edge_parallel_category Cat;
892 detail::remove_edge_and_property(g, g.out_edge_list(u), v, Cat());
893 detail::erase_from_incidence_list(g.out_edge_list(v), u, Cat());
896 template <class Config, class Predicate>
898 remove_out_edge_if(typename Config::vertex_descriptor u, Predicate pred,
899 undirected_graph_helper<Config>& g_)
901 typedef typename Config::global_edgelist_selector EdgeListS;
902 BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
904 typedef typename Config::graph_type graph_type;
905 typedef typename Config::OutEdgeList::value_type::property_type PropT;
906 graph_type& g = static_cast<graph_type&>(g_);
907 typename Config::out_edge_iterator first, last;
908 tie(first, last) = out_edges(u, g);
909 typedef typename Config::edge_parallel_category Cat;
910 detail::undirected_remove_out_edge_if_dispatch<PropT>
911 (g, first, last, g.out_edge_list(u), pred, Cat());
913 template <class Config, class Predicate>
915 remove_in_edge_if(typename Config::vertex_descriptor u, Predicate pred,
916 undirected_graph_helper<Config>& g_)
918 typedef typename Config::global_edgelist_selector EdgeListS;
919 BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
921 remove_out_edge_if(u, pred, g_);
924 // O(E/V * E) or O(log(E/V) * E)
925 template <class Predicate, class Config>
927 remove_edge_if(Predicate pred, undirected_graph_helper<Config>& g_)
929 typedef typename Config::global_edgelist_selector EdgeListS;
930 BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
932 typedef typename Config::graph_type graph_type;
933 graph_type& g = static_cast<graph_type&>(g_);
934 typename Config::edge_iterator ei, ei_end, next;
935 tie(ei, ei_end) = edges(g);
936 for (next = ei; ei != ei_end; ei = next) {
944 template <class Config>
945 inline std::pair<typename Config::edge_iterator,
946 typename Config::edge_iterator>
947 edges(const undirected_graph_helper<Config>& g_)
949 typedef typename Config::graph_type graph_type;
950 typedef typename Config::edge_iterator edge_iterator;
951 const graph_type& cg = static_cast<const graph_type&>(g_);
952 graph_type& g = const_cast<graph_type&>(cg);
953 return std::make_pair( edge_iterator(g.m_edges.begin()),
954 edge_iterator(g.m_edges.end()) );
957 template <class Config>
958 inline typename Config::edges_size_type
959 num_edges(const undirected_graph_helper<Config>& g_)
961 typedef typename Config::graph_type graph_type;
962 const graph_type& g = static_cast<const graph_type&>(g_);
963 return g.m_edges.size();
966 template <class Config>
968 clear_vertex(typename Config::vertex_descriptor u,
969 undirected_graph_helper<Config>& g_)
971 typedef typename Config::global_edgelist_selector EdgeListS;
972 BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
974 typedef typename Config::graph_type graph_type;
975 typedef typename Config::edge_parallel_category Cat;
976 graph_type& g = static_cast<graph_type&>(g_);
977 typename Config::OutEdgeList& el = g.out_edge_list(u);
978 typename Config::OutEdgeList::iterator
979 ei = el.begin(), ei_end = el.end();
980 for (; ei != ei_end; ++ei) {
981 detail::erase_from_incidence_list
982 (g.out_edge_list((*ei).get_target()), u, Cat());
983 g.m_edges.erase((*ei).get_iter());
985 g.out_edge_list(u).clear();
987 // O(1) for allow_parallel_edge_tag
988 // O(log(E/V)) for disallow_parallel_edge_tag
989 template <class Config>
990 inline std::pair<typename Config::edge_descriptor, bool>
991 add_edge(typename Config::vertex_descriptor u,
992 typename Config::vertex_descriptor v,
993 const typename Config::edge_property_type& p,
994 undirected_graph_helper<Config>& g_)
996 typedef typename Config::StoredEdge StoredEdge;
997 typedef typename Config::edge_descriptor edge_descriptor;
998 typedef typename Config::graph_type graph_type;
999 graph_type& g = static_cast<graph_type&>(g_);
1002 typename Config::EdgeContainer::value_type e(u, v, p);
1003 typename Config::EdgeContainer::iterator p_iter
1004 = graph_detail::push(g.m_edges, e).first;
1006 typename Config::OutEdgeList::iterator i;
1007 boost::tie(i, inserted) = boost::graph_detail::push(g.out_edge_list(u),
1008 StoredEdge(v, p_iter, &g.m_edges));
1010 boost::graph_detail::push(g.out_edge_list(v), StoredEdge(u, p_iter, &g.m_edges));
1011 return std::make_pair(edge_descriptor(u, v, &p_iter->get_property()),
1014 g.m_edges.erase(p_iter);
1015 return std::make_pair
1016 (edge_descriptor(u, v, &i->get_iter()->get_property()), false);
1019 template <class Config>
1020 inline std::pair<typename Config::edge_descriptor, bool>
1021 add_edge(typename Config::vertex_descriptor u,
1022 typename Config::vertex_descriptor v,
1023 undirected_graph_helper<Config>& g_)
1025 typename Config::edge_property_type p;
1026 return add_edge(u, v, p, g_);
1030 template <class Config>
1031 inline typename Config::degree_size_type
1032 degree(typename Config::vertex_descriptor u,
1033 const undirected_graph_helper<Config>& g_)
1035 typedef typename Config::graph_type Graph;
1036 const Graph& g = static_cast<const Graph&>(g_);
1037 return out_degree(u, g);
1040 template <class Config>
1041 inline std::pair<typename Config::in_edge_iterator,
1042 typename Config::in_edge_iterator>
1043 in_edges(typename Config::vertex_descriptor u,
1044 const undirected_graph_helper<Config>& g_)
1046 typedef typename Config::graph_type Graph;
1047 const Graph& cg = static_cast<const Graph&>(g_);
1048 Graph& g = const_cast<Graph&>(cg);
1049 typedef typename Config::in_edge_iterator in_edge_iterator;
1051 std::make_pair(in_edge_iterator(g.out_edge_list(u).begin(), u),
1052 in_edge_iterator(g.out_edge_list(u).end(), u));
1055 template <class Config>
1056 inline typename Config::degree_size_type
1057 in_degree(typename Config::vertex_descriptor u,
1058 const undirected_graph_helper<Config>& g_)
1059 { return degree(u, g_); }
1061 //=========================================================================
1062 // Bidirectional Graph Helper Class
1064 struct bidir_adj_list_traversal_tag :
1065 public virtual vertex_list_graph_tag,
1066 public virtual incidence_graph_tag,
1067 public virtual adjacency_graph_tag,
1068 public virtual edge_list_graph_tag,
1069 public virtual bidirectional_graph_tag { };
1071 template <class Config>
1072 struct bidirectional_graph_helper
1073 : public directed_edges_helper<Config> {
1074 typedef bidir_adj_list_traversal_tag traversal_category;
1077 // Had to make these non-members to avoid accidental instantiation
1078 // on SGI MIPSpro C++
1080 inline typename C::InEdgeList&
1081 in_edge_list(bidirectional_graph_helper<C>&,
1082 typename C::vertex_descriptor v)
1084 typename C::stored_vertex* sv = (typename C::stored_vertex*)v;
1085 return sv->m_in_edges;
1088 inline const typename C::InEdgeList&
1089 in_edge_list(const bidirectional_graph_helper<C>&,
1090 typename C::vertex_descriptor v) {
1091 typename C::stored_vertex* sv = (typename C::stored_vertex*)v;
1092 return sv->m_in_edges;
1095 template <class Predicate, class Config>
1097 remove_edge_if(Predicate pred, bidirectional_graph_helper<Config>& g_)
1099 typedef typename Config::global_edgelist_selector EdgeListS;
1100 BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
1102 typedef typename Config::graph_type graph_type;
1103 graph_type& g = static_cast<graph_type&>(g_);
1104 typename Config::edge_iterator ei, ei_end, next;
1105 tie(ei, ei_end) = edges(g);
1106 for (next = ei; ei != ei_end; ei = next) {
1109 remove_edge(*ei, g);
1113 template <class Config>
1114 inline std::pair<typename Config::in_edge_iterator,
1115 typename Config::in_edge_iterator>
1116 in_edges(typename Config::vertex_descriptor u,
1117 const bidirectional_graph_helper<Config>& g_)
1119 typedef typename Config::graph_type graph_type;
1120 const graph_type& cg = static_cast<const graph_type&>(g_);
1121 graph_type& g = const_cast<graph_type&>(cg);
1122 typedef typename Config::in_edge_iterator in_edge_iterator;
1124 std::make_pair(in_edge_iterator(in_edge_list(g, u).begin(), u),
1125 in_edge_iterator(in_edge_list(g, u).end(), u));
1129 template <class Config>
1130 inline std::pair<typename Config::edge_iterator,
1131 typename Config::edge_iterator>
1132 edges(const bidirectional_graph_helper<Config>& g_)
1134 typedef typename Config::graph_type graph_type;
1135 typedef typename Config::edge_iterator edge_iterator;
1136 const graph_type& cg = static_cast<const graph_type&>(g_);
1137 graph_type& g = const_cast<graph_type&>(cg);
1138 return std::make_pair( edge_iterator(g.m_edges.begin()),
1139 edge_iterator(g.m_edges.end()) );
1142 //=========================================================================
1143 // Bidirectional Graph Helper Class (with edge properties)
1146 template <class Config>
1147 struct bidirectional_graph_helper_with_property
1148 : public bidirectional_graph_helper<Config>
1150 typedef typename Config::graph_type graph_type;
1151 typedef typename Config::out_edge_iterator out_edge_iterator;
1153 std::pair<out_edge_iterator, out_edge_iterator>
1154 get_parallel_edge_sublist(typename Config::edge_descriptor e,
1155 const graph_type& g,
1157 { return out_edges(source(e, g), g); }
1159 std::pair<out_edge_iterator, out_edge_iterator>
1160 get_parallel_edge_sublist(typename Config::edge_descriptor e,
1161 const graph_type& g,
1163 { return edge_range(source(e, g), target(e, g), g); }
1165 std::pair<out_edge_iterator, out_edge_iterator>
1166 get_parallel_edge_sublist(typename Config::edge_descriptor e,
1167 const graph_type& g,
1169 { return edge_range(source(e, g), target(e, g), g); }
1171 #if !defined BOOST_NO_HASH
1172 std::pair<out_edge_iterator, out_edge_iterator>
1173 get_parallel_edge_sublist(typename Config::edge_descriptor e,
1174 const graph_type& g,
1176 { return edge_range(source(e, g), target(e, g), g); }
1179 // Placement of these overloaded remove_edge() functions
1180 // inside the class avoids a VC++ bug.
1182 // O(E/V) or O(log(E/V))
1184 remove_edge(typename Config::edge_descriptor e)
1186 typedef typename Config::global_edgelist_selector EdgeListS;
1187 BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
1189 graph_type& g = static_cast<graph_type&>(*this);
1191 typedef typename Config::edgelist_selector OutEdgeListS;
1193 std::pair<out_edge_iterator, out_edge_iterator> rng =
1194 get_parallel_edge_sublist(e, g, (OutEdgeListS*)(0));
1195 rng.first = std::find(rng.first, rng.second, e);
1196 assert(rng.first != rng.second);
1197 remove_edge(rng.first);
1201 remove_edge(typename Config::out_edge_iterator iter)
1203 typedef typename Config::global_edgelist_selector EdgeListS;
1204 BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
1206 typedef typename Config::graph_type graph_type;
1207 graph_type& g = static_cast<graph_type&>(*this);
1208 typename Config::edge_descriptor e = *iter;
1209 typename Config::OutEdgeList& oel = g.out_edge_list(source(e, g));
1210 typename Config::InEdgeList& iel = in_edge_list(g, target(e, g));
1211 typedef typename Config::OutEdgeList::value_type::property_type PType;
1212 PType& p = *(PType*)e.get_property();
1213 detail::remove_directed_edge_dispatch(*iter, iel, p);
1214 g.m_edges.erase(iter.base()->get_iter());
1215 oel.erase(iter.base());
1219 // O(E/V) for allow_parallel_edge_tag
1220 // O(log(E/V)) for disallow_parallel_edge_tag
1221 template <class Config>
1223 remove_edge(typename Config::vertex_descriptor u,
1224 typename Config::vertex_descriptor v,
1225 bidirectional_graph_helper_with_property<Config>& g_)
1227 typedef typename Config::global_edgelist_selector EdgeListS;
1228 BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
1230 typedef typename Config::graph_type graph_type;
1231 graph_type& g = static_cast<graph_type&>(g_);
1232 typedef typename Config::edge_parallel_category Cat;
1233 detail::remove_edge_and_property(g, g.out_edge_list(u), v, Cat());
1234 detail::erase_from_incidence_list(in_edge_list(g, v), u, Cat());
1237 // O(E/V) or O(log(E/V))
1238 template <class EdgeOrIter, class Config>
1240 remove_edge(EdgeOrIter e,
1241 bidirectional_graph_helper_with_property<Config>& g_)
1243 typedef typename Config::global_edgelist_selector EdgeListS;
1244 BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
1249 template <class Config, class Predicate>
1251 remove_out_edge_if(typename Config::vertex_descriptor u, Predicate pred,
1252 bidirectional_graph_helper_with_property<Config>& g_)
1254 typedef typename Config::global_edgelist_selector EdgeListS;
1255 BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
1257 typedef typename Config::graph_type graph_type;
1258 typedef typename Config::OutEdgeList::value_type::property_type PropT;
1259 graph_type& g = static_cast<graph_type&>(g_);
1261 typedef typename Config::EdgeIter EdgeIter;
1262 typedef std::vector<EdgeIter> Garbage;
1265 // First remove the edges from the targets' in-edge lists and
1266 // from the graph's edge set list.
1267 typename Config::out_edge_iterator out_i, out_end;
1268 for (tie(out_i, out_end) = out_edges(u, g); out_i != out_end; ++out_i)
1270 detail::remove_directed_edge_dispatch
1271 (*out_i, in_edge_list(g, target(*out_i, g)),
1272 *(PropT*)(*out_i).get_property());
1273 // Put in garbage to delete later. Will need the properties
1274 // for the remove_if of the out-edges.
1275 garbage.push_back((*out_i.base()).get_iter());
1278 // Now remove the edges from this out-edge list.
1279 typename Config::out_edge_iterator first, last;
1280 tie(first, last) = out_edges(u, g);
1281 typedef typename Config::edge_parallel_category Cat;
1282 detail::remove_directed_edge_if_dispatch
1283 (first, last, g.out_edge_list(u), pred, Cat());
1285 // Now delete the edge properties from the g.m_edges list
1286 for (typename Garbage::iterator i = garbage.begin();
1287 i != garbage.end(); ++i)
1288 g.m_edges.erase(*i);
1290 template <class Config, class Predicate>
1292 remove_in_edge_if(typename Config::vertex_descriptor v, Predicate pred,
1293 bidirectional_graph_helper_with_property<Config>& g_)
1295 typedef typename Config::global_edgelist_selector EdgeListS;
1296 BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
1298 typedef typename Config::graph_type graph_type;
1299 typedef typename Config::OutEdgeList::value_type::property_type PropT;
1300 graph_type& g = static_cast<graph_type&>(g_);
1302 typedef typename Config::EdgeIter EdgeIter;
1303 typedef std::vector<EdgeIter> Garbage;
1306 // First remove the edges from the sources' out-edge lists and
1307 // from the graph's edge set list.
1308 typename Config::in_edge_iterator in_i, in_end;
1309 for (tie(in_i, in_end) = in_edges(v, g); in_i != in_end; ++in_i)
1311 typename Config::vertex_descriptor u = source(*in_i, g);
1312 detail::remove_directed_edge_dispatch
1313 (*in_i, g.out_edge_list(u), *(PropT*)(*in_i).get_property());
1314 // Put in garbage to delete later. Will need the properties
1315 // for the remove_if of the out-edges.
1316 garbage.push_back((*in_i.base()).get_iter());
1318 // Now remove the edges from this in-edge list.
1319 typename Config::in_edge_iterator first, last;
1320 tie(first, last) = in_edges(v, g);
1321 typedef typename Config::edge_parallel_category Cat;
1322 detail::remove_directed_edge_if_dispatch
1323 (first, last, in_edge_list(g, v), pred, Cat());
1325 // Now delete the edge properties from the g.m_edges list
1326 for (typename Garbage::iterator i = garbage.begin();
1327 i != garbage.end(); ++i)
1328 g.m_edges.erase(*i);
1332 template <class Config>
1333 inline typename Config::edges_size_type
1334 num_edges(const bidirectional_graph_helper_with_property<Config>& g_)
1336 typedef typename Config::graph_type graph_type;
1337 const graph_type& g = static_cast<const graph_type&>(g_);
1338 return g.m_edges.size();
1340 // O(E/V * E/V) for allow_parallel_edge_tag
1341 // O(E/V * log(E/V)) for disallow_parallel_edge_tag
1342 template <class Config>
1344 clear_vertex(typename Config::vertex_descriptor u,
1345 bidirectional_graph_helper_with_property<Config>& g_)
1347 typedef typename Config::global_edgelist_selector EdgeListS;
1348 BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
1350 typedef typename Config::graph_type graph_type;
1351 typedef typename Config::edge_parallel_category Cat;
1352 graph_type& g = static_cast<graph_type&>(g_);
1353 typename Config::OutEdgeList& el = g.out_edge_list(u);
1354 typename Config::OutEdgeList::iterator
1355 ei = el.begin(), ei_end = el.end();
1356 for (; ei != ei_end; ++ei) {
1357 detail::erase_from_incidence_list
1358 (in_edge_list(g, (*ei).get_target()), u, Cat());
1359 g.m_edges.erase((*ei).get_iter());
1361 typename Config::InEdgeList& in_el = in_edge_list(g, u);
1362 typename Config::InEdgeList::iterator
1363 in_ei = in_el.begin(), in_ei_end = in_el.end();
1364 for (; in_ei != in_ei_end; ++in_ei) {
1365 detail::erase_from_incidence_list
1366 (g.out_edge_list((*in_ei).get_target()), u, Cat());
1367 g.m_edges.erase((*in_ei).get_iter());
1369 g.out_edge_list(u).clear();
1370 in_edge_list(g, u).clear();
1373 template <class Config>
1375 clear_out_edges(typename Config::vertex_descriptor u,
1376 bidirectional_graph_helper_with_property<Config>& g_)
1378 typedef typename Config::global_edgelist_selector EdgeListS;
1379 BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
1381 typedef typename Config::graph_type graph_type;
1382 typedef typename Config::edge_parallel_category Cat;
1383 graph_type& g = static_cast<graph_type&>(g_);
1384 typename Config::OutEdgeList& el = g.out_edge_list(u);
1385 typename Config::OutEdgeList::iterator
1386 ei = el.begin(), ei_end = el.end();
1387 for (; ei != ei_end; ++ei) {
1388 detail::erase_from_incidence_list
1389 (in_edge_list(g, (*ei).get_target()), u, Cat());
1390 g.m_edges.erase((*ei).get_iter());
1392 g.out_edge_list(u).clear();
1395 template <class Config>
1397 clear_in_edges(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::InEdgeList& in_el = in_edge_list(g, u);
1407 typename Config::InEdgeList::iterator
1408 in_ei = in_el.begin(), in_ei_end = in_el.end();
1409 for (; in_ei != in_ei_end; ++in_ei) {
1410 detail::erase_from_incidence_list
1411 (g.out_edge_list((*in_ei).get_target()), u, Cat());
1412 g.m_edges.erase((*in_ei).get_iter());
1414 in_edge_list(g, u).clear();
1417 // O(1) for allow_parallel_edge_tag
1418 // O(log(E/V)) for disallow_parallel_edge_tag
1419 template <class Config>
1420 inline std::pair<typename Config::edge_descriptor, bool>
1421 add_edge(typename Config::vertex_descriptor u,
1422 typename Config::vertex_descriptor v,
1423 const typename Config::edge_property_type& p,
1424 bidirectional_graph_helper_with_property<Config>& g_)
1426 typedef typename Config::graph_type graph_type;
1427 graph_type& g = static_cast<graph_type&>(g_);
1428 typedef typename Config::edge_descriptor edge_descriptor;
1429 typedef typename Config::StoredEdge StoredEdge;
1431 typename Config::EdgeContainer::value_type e(u, v, p);
1432 typename Config::EdgeContainer::iterator p_iter
1433 = graph_detail::push(g.m_edges, e).first;
1434 typename Config::OutEdgeList::iterator i;
1435 boost::tie(i, inserted) = boost::graph_detail::push(g.out_edge_list(u),
1436 StoredEdge(v, p_iter, &g.m_edges));
1438 boost::graph_detail::push(in_edge_list(g, v), StoredEdge(u, p_iter, &g.m_edges));
1439 return std::make_pair(edge_descriptor(u, v, &p_iter->m_property),
1442 g.m_edges.erase(p_iter);
1443 return std::make_pair(edge_descriptor(u, v,
1444 &i->get_iter()->get_property()),
1449 template <class Config>
1450 inline std::pair<typename Config::edge_descriptor, bool>
1451 add_edge(typename Config::vertex_descriptor u,
1452 typename Config::vertex_descriptor v,
1453 bidirectional_graph_helper_with_property<Config>& g_)
1455 typename Config::edge_property_type p;
1456 return add_edge(u, v, p, g_);
1459 template <class Config>
1460 inline typename Config::degree_size_type
1461 degree(typename Config::vertex_descriptor u,
1462 const bidirectional_graph_helper_with_property<Config>& g_)
1464 typedef typename Config::graph_type graph_type;
1465 const graph_type& g = static_cast<const graph_type&>(g_);
1466 return in_degree(u, g) + out_degree(u, g);
1469 //=========================================================================
1470 // Adjacency List Helper Class
1472 template <class Config, class Base>
1473 struct adj_list_helper : public Base
1475 typedef typename Config::graph_type AdjList;
1476 typedef typename Config::vertex_descriptor vertex_descriptor;
1477 typedef typename Config::edge_descriptor edge_descriptor;
1478 typedef typename Config::out_edge_iterator out_edge_iterator;
1479 typedef typename Config::in_edge_iterator in_edge_iterator;
1480 typedef typename Config::adjacency_iterator adjacency_iterator;
1481 typedef typename Config::inv_adjacency_iterator inv_adjacency_iterator;
1482 typedef typename Config::vertex_iterator vertex_iterator;
1483 typedef typename Config::edge_iterator edge_iterator;
1484 typedef typename Config::directed_category directed_category;
1485 typedef typename Config::edge_parallel_category edge_parallel_category;
1486 typedef typename Config::vertices_size_type vertices_size_type;
1487 typedef typename Config::edges_size_type edges_size_type;
1488 typedef typename Config::degree_size_type degree_size_type;
1489 typedef typename Config::StoredEdge StoredEdge;
1490 typedef typename Config::edge_property_type edge_property_type;
1492 typedef typename Config::global_edgelist_selector
1493 global_edgelist_selector;
1497 // The edge_dispatch() functions should be static, but
1498 // Borland gets confused about constness.
1501 inline std::pair<edge_descriptor,bool>
1502 edge_dispatch(const AdjList& g,
1503 vertex_descriptor u, vertex_descriptor v,
1504 boost::allow_parallel_edge_tag) const
1507 const typename Config::OutEdgeList& el = g.out_edge_list(u);
1508 typename Config::OutEdgeList::const_iterator
1509 i = std::find_if(el.begin(), el.end(),
1510 detail::target_is<vertex_descriptor>(v));
1511 found = (i != g.out_edge_list(u).end());
1513 return std::make_pair(edge_descriptor(u, v, &(*i).get_property()),
1516 return std::make_pair(edge_descriptor(u, v, 0), false);
1519 inline std::pair<edge_descriptor,bool>
1520 edge_dispatch(const AdjList& g,
1521 vertex_descriptor u, vertex_descriptor v,
1522 boost::disallow_parallel_edge_tag) const
1525 /* According to the standard, this should be iterator, not const_iterator,
1526 but the VC++ std::set::find() const returns const_iterator.
1527 And since iterator should be convertible to const_iterator, the
1528 following should work everywhere. -Jeremy */
1529 typename Config::OutEdgeList::const_iterator
1530 i = g.out_edge_list(u).find(StoredEdge(v)),
1531 end = g.out_edge_list(u).end();
1534 return std::make_pair(edge_descriptor(u, v, &(*i).get_property()),
1537 return std::make_pair(edge_descriptor(u, v, 0), false);
1541 template <class Config, class Base>
1542 inline std::pair<typename Config::adjacency_iterator,
1543 typename Config::adjacency_iterator>
1544 adjacent_vertices(typename Config::vertex_descriptor u,
1545 const adj_list_helper<Config, Base>& g_)
1547 typedef typename Config::graph_type AdjList;
1548 const AdjList& cg = static_cast<const AdjList&>(g_);
1549 AdjList& g = const_cast<AdjList&>(cg);
1550 typedef typename Config::adjacency_iterator adjacency_iterator;
1551 typename Config::out_edge_iterator first, last;
1552 boost::tie(first, last) = out_edges(u, g);
1553 return std::make_pair(adjacency_iterator(first, &g),
1554 adjacency_iterator(last, &g));
1556 template <class Config, class Base>
1557 inline std::pair<typename Config::inv_adjacency_iterator,
1558 typename Config::inv_adjacency_iterator>
1559 inv_adjacent_vertices(typename Config::vertex_descriptor u,
1560 const adj_list_helper<Config, Base>& g_)
1562 typedef typename Config::graph_type AdjList;
1563 const AdjList& cg = static_cast<const AdjList&>(g_);
1564 AdjList& g = const_cast<AdjList&>(cg);
1565 typedef typename Config::inv_adjacency_iterator inv_adjacency_iterator;
1566 typename Config::in_edge_iterator first, last;
1567 boost::tie(first, last) = in_edges(u, g);
1568 return std::make_pair(inv_adjacency_iterator(first, &g),
1569 inv_adjacency_iterator(last, &g));
1571 template <class Config, class Base>
1572 inline std::pair<typename Config::out_edge_iterator,
1573 typename Config::out_edge_iterator>
1574 out_edges(typename Config::vertex_descriptor u,
1575 const adj_list_helper<Config, Base>& g_)
1577 typedef typename Config::graph_type AdjList;
1578 typedef typename Config::out_edge_iterator out_edge_iterator;
1579 const AdjList& cg = static_cast<const AdjList&>(g_);
1580 AdjList& g = const_cast<AdjList&>(cg);
1582 std::make_pair(out_edge_iterator(g.out_edge_list(u).begin(), u),
1583 out_edge_iterator(g.out_edge_list(u).end(), u));
1585 template <class Config, class Base>
1586 inline std::pair<typename Config::vertex_iterator,
1587 typename Config::vertex_iterator>
1588 vertices(const adj_list_helper<Config, Base>& g_)
1590 typedef typename Config::graph_type AdjList;
1591 const AdjList& cg = static_cast<const AdjList&>(g_);
1592 AdjList& g = const_cast<AdjList&>(cg);
1593 return std::make_pair( g.vertex_set().begin(), g.vertex_set().end() );
1595 template <class Config, class Base>
1596 inline typename Config::vertices_size_type
1597 num_vertices(const adj_list_helper<Config, Base>& g_)
1599 typedef typename Config::graph_type AdjList;
1600 const AdjList& g = static_cast<const AdjList&>(g_);
1601 return g.vertex_set().size();
1603 template <class Config, class Base>
1604 inline typename Config::degree_size_type
1605 out_degree(typename Config::vertex_descriptor u,
1606 const adj_list_helper<Config, Base>& g_)
1608 typedef typename Config::graph_type AdjList;
1609 const AdjList& g = static_cast<const AdjList&>(g_);
1610 return g.out_edge_list(u).size();
1612 template <class Config, class Base>
1613 inline std::pair<typename Config::edge_descriptor, bool>
1614 edge(typename Config::vertex_descriptor u,
1615 typename Config::vertex_descriptor v,
1616 const adj_list_helper<Config, Base>& g_)
1618 typedef typename Config::graph_type Graph;
1619 typedef typename Config::edge_parallel_category Cat;
1620 const Graph& g = static_cast<const Graph&>(g_);
1621 return g_.edge_dispatch(g, u, v, Cat());
1623 template <class Config, class Base>
1624 inline std::pair<typename Config::out_edge_iterator,
1625 typename Config::out_edge_iterator>
1626 edge_range(typename Config::vertex_descriptor u,
1627 typename Config::vertex_descriptor v,
1628 const adj_list_helper<Config, Base>& g_)
1630 typedef typename Config::graph_type Graph;
1631 typedef typename Config::StoredEdge StoredEdge;
1632 const Graph& cg = static_cast<const Graph&>(g_);
1633 Graph& g = const_cast<Graph&>(cg);
1634 typedef typename Config::out_edge_iterator out_edge_iterator;
1635 typename Config::OutEdgeList& el = g.out_edge_list(u);
1636 typename Config::OutEdgeList::iterator first, last;
1637 typename Config::EdgeContainer fake_edge_container;
1639 std::equal_range(el.begin(), el.end(),
1640 StoredEdge(v, fake_edge_container.end(),
1641 &fake_edge_container));
1642 return std::make_pair(out_edge_iterator(first, u),
1643 out_edge_iterator(last, u));
1646 template <class Config>
1647 inline typename Config::degree_size_type
1648 in_degree(typename Config::vertex_descriptor u,
1649 const directed_edges_helper<Config>& g_)
1651 typedef typename Config::graph_type Graph;
1652 const Graph& cg = static_cast<const Graph&>(g_);
1653 Graph& g = const_cast<Graph&>(cg);
1654 return in_edge_list(g, u).size();
1658 template <class Config, class Base, class Property>
1660 typename boost::property_map<typename Config::graph_type,
1662 get_dispatch(adj_list_helper<Config,Base>&, Property,
1663 boost::edge_property_tag) {
1664 typedef typename Config::graph_type Graph;
1665 typedef typename boost::property_map<Graph, Property>::type PA;
1668 template <class Config, class Base, class Property>
1670 typename boost::property_map<typename Config::graph_type,
1671 Property>::const_type
1672 get_dispatch(const adj_list_helper<Config,Base>&, Property,
1673 boost::edge_property_tag) {
1674 typedef typename Config::graph_type Graph;
1675 typedef typename boost::property_map<Graph, Property>::const_type PA;
1679 template <class Config, class Base, class Property>
1681 typename boost::property_map<typename Config::graph_type,
1683 get_dispatch(adj_list_helper<Config,Base>& g, Property,
1684 boost::vertex_property_tag) {
1685 typedef typename Config::graph_type Graph;
1686 typedef typename boost::property_map<Graph, Property>::type PA;
1687 return PA(&static_cast<Graph&>(g));
1689 template <class Config, class Base, class Property>
1691 typename boost::property_map<typename Config::graph_type,
1692 Property>::const_type
1693 get_dispatch(const adj_list_helper<Config, Base>& g, Property,
1694 boost::vertex_property_tag) {
1695 typedef typename Config::graph_type Graph;
1696 typedef typename boost::property_map<Graph, Property>::const_type PA;
1697 const Graph& cg = static_cast<const Graph&>(g);
1701 } // namespace detail
1703 // Implementation of the PropertyGraph interface
1704 template <class Config, class Base, class Property>
1706 typename boost::property_map<typename Config::graph_type, Property>::type
1707 get(Property p, adj_list_helper<Config, Base>& g) {
1708 typedef typename property_kind<Property>::type Kind;
1709 return detail::get_dispatch(g, p, Kind());
1711 template <class Config, class Base, class Property>
1713 typename boost::property_map<typename Config::graph_type,
1714 Property>::const_type
1715 get(Property p, const adj_list_helper<Config, Base>& g) {
1716 typedef typename property_kind<Property>::type Kind;
1717 return detail::get_dispatch(g, p, Kind());
1720 template <class Config, class Base, class Property, class Key>
1722 typename boost::property_traits<
1723 typename boost::property_map<typename Config::graph_type,
1726 get(Property p, adj_list_helper<Config, Base>& g, const Key& key) {
1727 return get(get(p, g), key);
1730 template <class Config, class Base, class Property, class Key>
1732 typename boost::property_traits<
1733 typename boost::property_map<typename Config::graph_type,
1734 Property>::const_type
1736 get(Property p, const adj_list_helper<Config, Base>& g, const Key& key) {
1737 return get(get(p, g), key);
1740 template <class Config, class Base, class Property, class Key,class Value>
1742 put(Property p, adj_list_helper<Config, Base>& g,
1743 const Key& key, const Value& value)
1745 typedef typename Config::graph_type Graph;
1746 typedef typename boost::property_map<Graph, Property>::type Map;
1747 Map pmap = get(p, static_cast<Graph&>(g));
1748 put(pmap, key, value);
1752 //=========================================================================
1753 // Generalize Adjacency List Implementation
1755 struct adj_list_tag { };
1757 template <class Derived, class Config, class Base>
1759 : public adj_list_helper<Config, Base>
1761 typedef typename Config::OutEdgeList OutEdgeList;
1762 typedef typename Config::InEdgeList InEdgeList;
1763 typedef typename Config::StoredVertexList StoredVertexList;
1765 typedef typename Config::stored_vertex stored_vertex;
1766 typedef typename Config::EdgeContainer EdgeContainer;
1767 typedef typename Config::vertex_descriptor vertex_descriptor;
1768 typedef typename Config::edge_descriptor edge_descriptor;
1769 typedef typename Config::vertex_iterator vertex_iterator;
1770 typedef typename Config::edge_iterator edge_iterator;
1771 typedef typename Config::edge_parallel_category edge_parallel_category;
1772 typedef typename Config::vertices_size_type vertices_size_type;
1773 typedef typename Config::edges_size_type edges_size_type;
1774 typedef typename Config::degree_size_type degree_size_type;
1775 typedef typename Config::edge_property_type edge_property_type;
1776 typedef adj_list_tag graph_tag;
1778 static vertex_descriptor null_vertex()
1783 inline adj_list_impl() { }
1785 inline adj_list_impl(const adj_list_impl& x) {
1788 inline adj_list_impl& operator=(const adj_list_impl& x) {
1793 inline void clear() {
1794 for (typename StoredVertexList::iterator i = m_vertices.begin();
1795 i != m_vertices.end(); ++i)
1796 delete (stored_vertex*)*i;
1800 inline adj_list_impl(vertices_size_type num_vertices) {
1801 for (vertices_size_type i = 0; i < num_vertices; ++i)
1802 add_vertex(static_cast<Derived&>(*this));
1804 template <class EdgeIterator>
1805 inline adj_list_impl(vertices_size_type num_vertices,
1806 EdgeIterator first, EdgeIterator last)
1808 vertex_descriptor* v = new vertex_descriptor[num_vertices];
1809 for (vertices_size_type i = 0; i < num_vertices; ++i)
1810 v[i] = add_vertex(static_cast<Derived&>(*this));
1812 while (first != last) {
1813 add_edge(v[(*first).first], v[(*first).second], *this);
1818 template <class EdgeIterator, class EdgePropertyIterator>
1819 inline adj_list_impl(vertices_size_type num_vertices,
1820 EdgeIterator first, EdgeIterator last,
1821 EdgePropertyIterator ep_iter)
1823 vertex_descriptor* v = new vertex_descriptor[num_vertices];
1824 for (vertices_size_type i = 0; i < num_vertices; ++i)
1825 v[i] = add_vertex(static_cast<Derived&>(*this));
1827 while (first != last) {
1828 add_edge(v[(*first).first], v[(*first).second], *ep_iter, *this);
1835 for (typename StoredVertexList::iterator i = m_vertices.begin();
1836 i != m_vertices.end(); ++i)
1837 delete (stored_vertex*)*i;
1840 inline OutEdgeList& out_edge_list(vertex_descriptor v) {
1841 stored_vertex* sv = (stored_vertex*)v;
1842 return sv->m_out_edges;
1844 inline const OutEdgeList& out_edge_list(vertex_descriptor v) const {
1845 stored_vertex* sv = (stored_vertex*)v;
1846 return sv->m_out_edges;
1848 inline StoredVertexList& vertex_set() { return m_vertices; }
1849 inline const StoredVertexList& vertex_set() const { return m_vertices; }
1851 inline void copy_impl(const adj_list_impl& x_)
1853 const Derived& x = static_cast<const Derived&>(x_);
1855 // Would be better to have a constant time way to get from
1856 // vertices in x to the corresponding vertices in *this.
1857 std::map<stored_vertex*,stored_vertex*> vertex_map;
1859 // Copy the stored vertex objects by adding each vertex
1860 // and copying its property object.
1861 vertex_iterator vi, vi_end;
1862 for (tie(vi, vi_end) = vertices(x); vi != vi_end; ++vi) {
1863 stored_vertex* v = (stored_vertex*)add_vertex(*this);
1864 v->m_property = ((stored_vertex*)*vi)->m_property;
1865 vertex_map[(stored_vertex*)*vi] = v;
1867 // Copy the edges by adding each edge and copying its
1869 edge_iterator ei, ei_end;
1870 for (tie(ei, ei_end) = edges(x); ei != ei_end; ++ei) {
1873 vertex_descriptor s = source(*ei,x), t = target(*ei,x);
1874 tie(e, inserted) = add_edge(vertex_map[(stored_vertex*)s],
1875 vertex_map[(stored_vertex*)t], *this);
1876 *((edge_property_type*)e.m_eproperty)
1877 = *((edge_property_type*)(*ei).m_eproperty);
1882 typename Config::EdgeContainer m_edges;
1883 StoredVertexList m_vertices;
1887 template <class Derived, class Config, class Base>
1888 inline typename Config::vertex_descriptor
1889 add_vertex(adj_list_impl<Derived, Config, Base>& g_)
1891 Derived& g = static_cast<Derived&>(g_);
1892 typedef typename Config::stored_vertex stored_vertex;
1893 stored_vertex* v = new stored_vertex;
1894 typename Config::StoredVertexList::iterator pos;
1896 boost::tie(pos,inserted) = boost::graph_detail::push(g.m_vertices, v);
1897 v->m_position = pos;
1901 template <class Derived, class Config, class Base>
1902 inline typename Config::vertex_descriptor
1903 add_vertex(const typename Config::vertex_property_type& p,
1904 adj_list_impl<Derived, Config, Base>& g_)
1906 Derived& g = static_cast<Derived&>(g_);
1907 typedef typename Config::stored_vertex stored_vertex;
1908 stored_vertex* v = new stored_vertex(p);
1909 typename Config::StoredVertexList::iterator pos;
1911 boost::tie(pos,inserted) = boost::graph_detail::push(g.m_vertices, v);
1912 v->m_position = pos;
1916 template <class Derived, class Config, class Base>
1917 inline void remove_vertex(typename Config::vertex_descriptor u,
1918 adj_list_impl<Derived, Config, Base>& g_)
1920 typedef typename Config::stored_vertex stored_vertex;
1921 Derived& g = static_cast<Derived&>(g_);
1922 stored_vertex* su = (stored_vertex*)u;
1923 g.m_vertices.erase(su->m_position);
1927 template <class Derived, class Config, class Base>
1928 inline typename Config::vertex_descriptor
1929 vertex(typename Config::vertices_size_type n,
1930 const adj_list_impl<Derived, Config, Base>& g_)
1932 const Derived& g = static_cast<const Derived&>(g_);
1933 typename Config::vertex_iterator i = vertices(g).first;
1934 while (n--) ++i; // std::advance(i, n); (not VC++ portable)
1938 //=========================================================================
1939 // Vector-Backbone Adjacency List Implementation
1943 template <class Graph, class vertex_descriptor>
1945 remove_vertex_dispatch(Graph& g, vertex_descriptor u,
1946 boost::directed_tag)
1948 typedef typename Graph::edge_parallel_category edge_parallel_category;
1949 g.m_vertices.erase(g.m_vertices.begin() + u);
1950 vertex_descriptor V = num_vertices(g);
1952 for (vertex_descriptor v = 0; v < V; ++v)
1953 reindex_edge_list(g.out_edge_list(v), u, edge_parallel_category());
1957 template <class Graph, class vertex_descriptor>
1959 remove_vertex_dispatch(Graph& g, vertex_descriptor u,
1960 boost::undirected_tag)
1962 typedef typename Graph::global_edgelist_selector EdgeListS;
1963 BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
1965 typedef typename Graph::edge_parallel_category edge_parallel_category;
1966 g.m_vertices.erase(g.m_vertices.begin() + u);
1967 vertex_descriptor V = num_vertices(g);
1968 for (vertex_descriptor v = 0; v < V; ++v)
1969 reindex_edge_list(g.out_edge_list(v), u,
1970 edge_parallel_category());
1971 typedef typename Graph::EdgeContainer Container;
1972 typedef typename Container::iterator Iter;
1973 Iter ei = g.m_edges.begin(), ei_end = g.m_edges.end();
1974 for (; ei != ei_end; ++ei) {
1975 if (ei->m_source > u)
1977 if (ei->m_target > u)
1981 template <class Graph, class vertex_descriptor>
1983 remove_vertex_dispatch(Graph& g, vertex_descriptor u,
1984 boost::bidirectional_tag)
1986 typedef typename Graph::global_edgelist_selector EdgeListS;
1987 BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
1989 typedef typename Graph::edge_parallel_category edge_parallel_category;
1990 g.m_vertices.erase(g.m_vertices.begin() + u);
1991 vertex_descriptor V = num_vertices(g);
1992 vertex_descriptor v;
1994 for (v = 0; v < V; ++v)
1995 reindex_edge_list(g.out_edge_list(v), u,
1996 edge_parallel_category());
1997 for (v = 0; v < V; ++v)
1998 reindex_edge_list(in_edge_list(g, v), u,
1999 edge_parallel_category());
2001 typedef typename Graph::EdgeContainer Container;
2002 typedef typename Container::iterator Iter;
2003 Iter ei = g.m_edges.begin(), ei_end = g.m_edges.end();
2004 for (; ei != ei_end; ++ei) {
2005 if (ei->m_source > u)
2007 if (ei->m_target > u)
2013 template <class EdgeList, class vertex_descriptor>
2015 reindex_edge_list(EdgeList& el, vertex_descriptor u,
2016 boost::allow_parallel_edge_tag)
2018 typename EdgeList::iterator ei = el.begin(), e_end = el.end();
2019 for (; ei != e_end; ++ei)
2020 if ((*ei).get_target() > u)
2021 --(*ei).get_target();
2023 template <class EdgeList, class vertex_descriptor>
2025 reindex_edge_list(EdgeList& el, vertex_descriptor u,
2026 boost::disallow_parallel_edge_tag)
2028 typename EdgeList::iterator ei = el.begin(), e_end = el.end();
2029 while (ei != e_end) {
2030 typename EdgeList::value_type ce = *ei;
2032 if (ce.get_target() > u) {
2039 } // namespace detail
2041 struct vec_adj_list_tag { };
2043 template <class Graph, class Config, class Base>
2044 class vec_adj_list_impl
2045 : public adj_list_helper<Config, Base>
2047 typedef typename Config::OutEdgeList OutEdgeList;
2048 typedef typename Config::InEdgeList InEdgeList;
2049 typedef typename Config::StoredVertexList StoredVertexList;
2051 typedef typename Config::vertex_descriptor vertex_descriptor;
2052 typedef typename Config::edge_descriptor edge_descriptor;
2053 typedef typename Config::out_edge_iterator out_edge_iterator;
2054 typedef typename Config::edge_iterator edge_iterator;
2055 typedef typename Config::directed_category directed_category;
2056 typedef typename Config::vertices_size_type vertices_size_type;
2057 typedef typename Config::edges_size_type edges_size_type;
2058 typedef typename Config::degree_size_type degree_size_type;
2059 typedef typename Config::StoredEdge StoredEdge;
2060 typedef typename Config::stored_vertex stored_vertex;
2061 typedef typename Config::EdgeContainer EdgeContainer;
2062 typedef typename Config::edge_property_type edge_property_type;
2063 typedef vec_adj_list_tag graph_tag;
2065 static vertex_descriptor null_vertex()
2067 return (std::numeric_limits<vertex_descriptor>::max)();
2070 inline vec_adj_list_impl() { }
2072 inline vec_adj_list_impl(const vec_adj_list_impl& x) {
2075 inline vec_adj_list_impl& operator=(const vec_adj_list_impl& x) {
2080 inline void clear() {
2085 inline vec_adj_list_impl(vertices_size_type _num_vertices)
2086 : m_vertices(_num_vertices) { }
2088 template <class EdgeIterator>
2089 inline vec_adj_list_impl(vertices_size_type num_vertices,
2090 EdgeIterator first, EdgeIterator last)
2091 : m_vertices(num_vertices)
2093 while (first != last) {
2094 add_edge((*first).first, (*first).second,
2095 static_cast<Graph&>(*this));
2099 template <class EdgeIterator, class EdgePropertyIterator>
2100 inline vec_adj_list_impl(vertices_size_type num_vertices,
2101 EdgeIterator first, EdgeIterator last,
2102 EdgePropertyIterator ep_iter)
2103 : m_vertices(num_vertices)
2105 while (first != last) {
2106 add_edge((*first).first, (*first).second, *ep_iter,
2107 static_cast<Graph&>(*this));
2114 inline boost::integer_range<vertex_descriptor> vertex_set() const {
2115 return boost::integer_range<vertex_descriptor>(0, m_vertices.size());
2117 inline OutEdgeList& out_edge_list(vertex_descriptor v) {
2118 return m_vertices[v].m_out_edges;
2120 inline const OutEdgeList& out_edge_list(vertex_descriptor v) const {
2121 return m_vertices[v].m_out_edges;
2123 inline void copy_impl(const vec_adj_list_impl& x_)
2125 const Graph& x = static_cast<const Graph&>(x_);
2126 // Copy the stored vertex objects by adding each vertex
2127 // and copying its property object.
2128 for (vertices_size_type i = 0; i < num_vertices(x); ++i) {
2129 vertex_descriptor v = add_vertex(*this);
2130 m_vertices[v].m_property = x.m_vertices[i].m_property;
2132 // Copy the edges by adding each edge and copying its
2134 edge_iterator ei, ei_end;
2135 for (tie(ei, ei_end) = edges(x); ei != ei_end; ++ei) {
2138 tie(e, inserted) = add_edge(source(*ei,x), target(*ei,x) , *this);
2139 *((edge_property_type*)e.m_eproperty)
2140 = *((edge_property_type*)(*ei).m_eproperty);
2143 typename Config::EdgeContainer m_edges;
2144 StoredVertexList m_vertices;
2146 // Had to make these non-members to avoid accidental instantiation
2147 // on SGI MIPSpro C++
2148 template <class G, class C, class B>
2149 inline typename C::InEdgeList&
2150 in_edge_list(vec_adj_list_impl<G,C,B>& g,
2151 typename C::vertex_descriptor v) {
2152 return g.m_vertices[v].m_in_edges;
2154 template <class G, class C, class B>
2155 inline const typename C::InEdgeList&
2156 in_edge_list(const vec_adj_list_impl<G,C,B>& g,
2157 typename C::vertex_descriptor v) {
2158 return g.m_vertices[v].m_in_edges;
2162 template <class Graph, class Config, class Base>
2163 inline typename Config::vertex_descriptor
2164 add_vertex(vec_adj_list_impl<Graph, Config, Base>& g_) {
2165 Graph& g = static_cast<Graph&>(g_);
2166 g.m_vertices.resize(g.m_vertices.size() + 1);
2167 return g.m_vertices.size() - 1;
2170 template <class Graph, class Config, class Base>
2171 inline typename Config::vertex_descriptor
2172 add_vertex(const typename Config::vertex_property_type& p,
2173 vec_adj_list_impl<Graph, Config, Base>& g_) {
2174 Graph& g = static_cast<Graph&>(g_);
2175 typedef typename Config::stored_vertex stored_vertex;
2176 g.m_vertices.push_back(stored_vertex(p));
2177 return g.m_vertices.size() - 1;
2180 // Here we override the directed_graph_helper add_edge() function
2181 // so that the number of vertices is automatically changed if
2182 // either u or v is greater than the number of vertices.
2183 template <class Graph, class Config, class Base>
2184 inline std::pair<typename Config::edge_descriptor, bool>
2185 add_edge(typename Config::vertex_descriptor u,
2186 typename Config::vertex_descriptor v,
2187 const typename Config::edge_property_type& p,
2188 vec_adj_list_impl<Graph, Config, Base>& g_)
2190 BOOST_USING_STD_MAX();
2191 typename Config::vertex_descriptor x = max BOOST_PREVENT_MACRO_SUBSTITUTION(u, v);
2192 if (x >= num_vertices(g_))
2193 g_.m_vertices.resize(x + 1);
2194 adj_list_helper<Config, Base>& g = g_;
2195 return add_edge(u, v, p, g);
2197 template <class Graph, class Config, class Base>
2198 inline std::pair<typename Config::edge_descriptor, bool>
2199 add_edge(typename Config::vertex_descriptor u,
2200 typename Config::vertex_descriptor v,
2201 vec_adj_list_impl<Graph, Config, Base>& g_)
2203 typename Config::edge_property_type p;
2204 return add_edge(u, v, p, g_);
2209 template <class Graph, class Config, class Base>
2210 inline void remove_vertex(typename Config::vertex_descriptor v,
2211 vec_adj_list_impl<Graph, Config, Base>& g_)
2213 typedef typename Config::directed_category Cat;
2214 Graph& g = static_cast<Graph&>(g_);
2215 detail::remove_vertex_dispatch(g, v, Cat());
2218 template <class Graph, class Config, class Base>
2219 inline typename Config::vertex_descriptor
2220 vertex(typename Config::vertices_size_type n,
2221 const vec_adj_list_impl<Graph, Config, Base>&)
2229 //=========================================================================
2230 // Adjacency List Generator
2232 template <class Graph, class VertexListS, class OutEdgeListS,
2233 class DirectedS, class VertexProperty, class EdgeProperty,
2234 class GraphProperty, class EdgeListS>
2237 typedef typename detail::is_random_access<VertexListS>::type
2239 typedef typename has_property<EdgeProperty>::type has_edge_property;
2240 typedef typename DirectedS::is_directed_t DirectedT;
2241 typedef typename DirectedS::is_bidir_t BidirectionalT;
2245 typedef OutEdgeListS edgelist_selector;
2246 typedef EdgeListS global_edgelist_selector;
2248 typedef Graph graph_type;
2249 typedef EdgeProperty edge_property_type;
2250 typedef VertexProperty vertex_property_type;
2251 typedef GraphProperty graph_property_type;
2252 typedef std::size_t vertices_size_type;
2254 typedef adjacency_list_traits<OutEdgeListS, VertexListS, DirectedS>
2257 typedef typename Traits::directed_category directed_category;
2258 typedef typename Traits::edge_parallel_category edge_parallel_category;
2259 typedef typename Traits::vertex_descriptor vertex_descriptor;
2260 typedef typename Traits::edge_descriptor edge_descriptor;
2262 typedef void* vertex_ptr;
2264 // need to reorganize this to avoid instantiating stuff
2265 // that doesn't get used -JGS
2267 // VertexList and vertex_iterator
2268 typedef typename container_gen<VertexListS,
2269 vertex_ptr>::type SeqVertexList;
2270 typedef boost::integer_range<std::size_t> RandVertexList;
2271 typedef typename boost::ct_if_t<is_rand_access,
2272 RandVertexList, SeqVertexList>::type VertexList;
2274 typedef typename VertexList::iterator vertex_iterator;
2276 // EdgeContainer and StoredEdge
2278 typedef typename container_gen<EdgeListS,
2279 list_edge<vertex_descriptor, EdgeProperty> >::type EdgeContainer;
2281 typedef typename ct_and<DirectedT,
2282 typename ct_not<BidirectionalT>::type >::type on_edge_storage;
2284 typedef typename boost::ct_if_t<on_edge_storage,
2285 std::size_t, typename EdgeContainer::size_type
2286 >::type edges_size_type;
2288 typedef typename EdgeContainer::iterator EdgeIter;
2290 typedef typename detail::is_random_access<EdgeListS>::type is_edge_ra;
2292 typedef typename boost::ct_if_t<on_edge_storage,
2293 stored_edge_property<vertex_descriptor, EdgeProperty>,
2294 typename boost::ct_if_t<is_edge_ra,
2295 stored_ra_edge_iter<vertex_descriptor, EdgeContainer, EdgeProperty>,
2296 stored_edge_iter<vertex_descriptor, EdgeIter, EdgeProperty>
2302 typedef typename container_gen<OutEdgeListS, StoredEdge>::type
2304 typedef typename OutEdgeList::size_type degree_size_type;
2305 typedef typename OutEdgeList::iterator OutEdgeIter;
2307 typedef boost::detail::iterator_traits<OutEdgeIter> OutEdgeIterTraits;
2308 typedef typename OutEdgeIterTraits::iterator_category OutEdgeIterCat;
2309 typedef typename OutEdgeIterTraits::difference_type OutEdgeIterDiff;
2311 typedef out_edge_iter<
2312 OutEdgeIter, vertex_descriptor, edge_descriptor, OutEdgeIterDiff
2313 > out_edge_iterator;
2315 typedef typename adjacency_iterator_generator<graph_type,
2316 vertex_descriptor, out_edge_iterator>::type adjacency_iterator;
2318 typedef OutEdgeList InEdgeList;
2319 typedef OutEdgeIter InEdgeIter;
2320 typedef OutEdgeIterCat InEdgeIterCat;
2321 typedef OutEdgeIterDiff InEdgeIterDiff;
2323 typedef in_edge_iter<
2324 InEdgeIter, vertex_descriptor, edge_descriptor, InEdgeIterDiff
2327 typedef typename inv_adjacency_iterator_generator<graph_type,
2328 vertex_descriptor, in_edge_iterator>::type inv_adjacency_iterator;
2332 typedef boost::detail::iterator_traits<EdgeIter> EdgeIterTraits;
2333 typedef typename EdgeIterTraits::iterator_category EdgeIterCat;
2334 typedef typename EdgeIterTraits::difference_type EdgeIterDiff;
2336 typedef undirected_edge_iter<
2340 > UndirectedEdgeIter; // also used for bidirectional
2342 typedef adj_list_edge_iterator<vertex_iterator, out_edge_iterator,
2343 graph_type> DirectedEdgeIter;
2345 typedef typename boost::ct_if_t<on_edge_storage,
2346 DirectedEdgeIter, UndirectedEdgeIter>::type edge_iterator;
2348 // stored_vertex and StoredVertexList
2349 typedef typename container_gen<VertexListS, vertex_ptr>::type
2350 SeqStoredVertexList;
2351 struct seq_stored_vertex {
2352 seq_stored_vertex() { }
2353 seq_stored_vertex(const VertexProperty& p) : m_property(p) { }
2354 OutEdgeList m_out_edges;
2355 VertexProperty m_property;
2356 typename SeqStoredVertexList::iterator m_position;
2358 struct bidir_seq_stored_vertex {
2359 bidir_seq_stored_vertex() { }
2360 bidir_seq_stored_vertex(const VertexProperty& p) : m_property(p) { }
2361 OutEdgeList m_out_edges;
2362 InEdgeList m_in_edges;
2363 VertexProperty m_property;
2364 typename SeqStoredVertexList::iterator m_position;
2366 struct rand_stored_vertex {
2367 rand_stored_vertex() { }
2368 rand_stored_vertex(const VertexProperty& p) : m_property(p) { }
2369 OutEdgeList m_out_edges;
2370 VertexProperty m_property;
2372 struct bidir_rand_stored_vertex {
2373 bidir_rand_stored_vertex() { }
2374 bidir_rand_stored_vertex(const VertexProperty& p) : m_property(p) { }
2375 OutEdgeList m_out_edges;
2376 InEdgeList m_in_edges;
2377 VertexProperty m_property;
2379 typedef typename boost::ct_if_t<is_rand_access,
2380 typename boost::ct_if_t<BidirectionalT,
2381 bidir_rand_stored_vertex, rand_stored_vertex>::type,
2382 typename boost::ct_if_t<BidirectionalT,
2383 bidir_seq_stored_vertex, seq_stored_vertex>::type
2384 >::type StoredVertex;
2385 struct stored_vertex : public StoredVertex {
2387 stored_vertex(const VertexProperty& p) : StoredVertex(p) { }
2390 typedef typename container_gen<VertexListS, stored_vertex>::type
2391 RandStoredVertexList;
2392 typedef typename boost::ct_if_t< is_rand_access,
2393 RandStoredVertexList, SeqStoredVertexList>::type StoredVertexList;
2397 typedef typename boost::ct_if_t<BidirectionalT,
2398 bidirectional_graph_helper_with_property<config>,
2399 typename boost::ct_if_t<DirectedT,
2400 directed_graph_helper<config>,
2401 undirected_graph_helper<config>
2403 >::type DirectedHelper;
2405 typedef typename boost::ct_if_t<is_rand_access,
2406 vec_adj_list_impl<Graph, config, DirectedHelper>,
2407 adj_list_impl<Graph, config, DirectedHelper>
2412 } // namespace detail
2414 //=========================================================================
2415 // Vertex Property Maps
2417 template <class Graph, class ValueType, class Reference, class Tag>
2418 struct adj_list_vertex_property_map
2419 : public boost::put_get_helper<
2421 adj_list_vertex_property_map<Graph, ValueType, Reference, Tag>
2424 typedef typename Graph::stored_vertex StoredVertex;
2425 typedef ValueType value_type;
2426 typedef Reference reference;
2427 typedef typename Graph::vertex_descriptor key_type;
2428 typedef boost::lvalue_property_map_tag category;
2429 inline adj_list_vertex_property_map() { }
2430 inline adj_list_vertex_property_map(const Graph*) { }
2431 inline Reference operator[](key_type v) const {
2432 StoredVertex* sv = (StoredVertex*)v;
2433 return get_property_value(sv->m_property, Tag());
2435 inline Reference operator()(key_type v) const {
2436 return this->operator[](v);
2440 template <class Graph, class Property, class PropRef>
2441 struct adj_list_vertex_all_properties_map
2442 : public boost::put_get_helper<PropRef,
2443 adj_list_vertex_all_properties_map<Graph, Property, PropRef>
2446 typedef typename Graph::stored_vertex StoredVertex;
2447 typedef Property value_type;
2448 typedef PropRef reference;
2449 typedef typename Graph::vertex_descriptor key_type;
2450 typedef boost::lvalue_property_map_tag category;
2451 inline adj_list_vertex_all_properties_map() { }
2452 inline adj_list_vertex_all_properties_map(const Graph*) { }
2453 inline PropRef operator[](key_type v) const {
2454 StoredVertex* sv = (StoredVertex*)v;
2455 return sv->m_property;
2457 inline PropRef operator()(key_type v) const {
2458 return this->operator[](v);
2462 template <class Graph, class GraphPtr, class ValueType, class Reference,
2464 struct vec_adj_list_vertex_property_map
2465 : public boost::put_get_helper<
2467 vec_adj_list_vertex_property_map<Graph,GraphPtr,ValueType,Reference,
2471 typedef ValueType value_type;
2472 typedef Reference reference;
2473 typedef typename boost::graph_traits<Graph>::vertex_descriptor key_type;
2474 typedef boost::lvalue_property_map_tag category;
2475 vec_adj_list_vertex_property_map() { }
2476 vec_adj_list_vertex_property_map(GraphPtr g) : m_g(g) { }
2477 inline Reference operator[](key_type v) const {
2478 return get_property_value(m_g->m_vertices[v].m_property, Tag());
2480 inline Reference operator()(key_type v) const {
2481 return this->operator[](v);
2486 template <class Graph, class GraphPtr, class Property, class PropertyRef>
2487 struct vec_adj_list_vertex_all_properties_map
2488 : public boost::put_get_helper<PropertyRef,
2489 vec_adj_list_vertex_all_properties_map<Graph,GraphPtr,Property,
2493 typedef Property value_type;
2494 typedef PropertyRef reference;
2495 typedef typename boost::graph_traits<Graph>::vertex_descriptor key_type;
2496 typedef boost::lvalue_property_map_tag category;
2497 vec_adj_list_vertex_all_properties_map() { }
2498 vec_adj_list_vertex_all_properties_map(GraphPtr g) : m_g(g) { }
2499 inline PropertyRef operator[](key_type v) const {
2500 return m_g->m_vertices[v].m_property;
2502 inline PropertyRef operator()(key_type v) const {
2503 return this->operator[](v);
2508 struct adj_list_any_vertex_pa {
2509 template <class Tag, class Graph, class Property>
2511 typedef typename property_value<Property, Tag>::type value_type;
2512 typedef value_type& reference;
2513 typedef const value_type& const_reference;
2515 typedef adj_list_vertex_property_map
2516 <Graph, value_type, reference, Tag> type;
2517 typedef adj_list_vertex_property_map
2518 <Graph, value_type, const_reference, Tag> const_type;
2521 struct adj_list_all_vertex_pa {
2522 template <class Tag, class Graph, class Property>
2524 typedef typename Graph::vertex_descriptor Vertex;
2525 typedef adj_list_vertex_all_properties_map<Graph,Property,
2527 typedef adj_list_vertex_all_properties_map<Graph,Property,
2528 const Property&> const_type;
2532 template <class Property, class Vertex>
2533 struct vec_adj_list_vertex_id_map
2534 : public boost::put_get_helper<
2535 Vertex, vec_adj_list_vertex_id_map<Property, Vertex>
2538 typedef Vertex value_type;
2539 typedef Vertex key_type;
2540 typedef Vertex reference;
2541 typedef boost::readable_property_map_tag category;
2542 inline vec_adj_list_vertex_id_map() { }
2543 template <class Graph>
2544 inline vec_adj_list_vertex_id_map(const Graph&) { }
2545 inline value_type operator[](key_type v) const { return v; }
2546 inline value_type operator()(key_type v) const { return v; }
2549 struct vec_adj_list_any_vertex_pa {
2550 template <class Tag, class Graph, class Property>
2552 typedef typename property_value<Property, Tag>::type value_type;
2553 typedef value_type& reference;
2554 typedef const value_type& const_reference;
2556 typedef vec_adj_list_vertex_property_map
2557 <Graph, Graph*, value_type, reference, Tag> type;
2558 typedef vec_adj_list_vertex_property_map
2559 <Graph, const Graph*, value_type, const_reference, Tag> const_type;
2562 struct vec_adj_list_id_vertex_pa {
2563 template <class Tag, class Graph, class Property>
2565 typedef typename Graph::vertex_descriptor Vertex;
2566 typedef vec_adj_list_vertex_id_map<Property, Vertex> type;
2567 typedef vec_adj_list_vertex_id_map<Property, Vertex> const_type;
2570 struct vec_adj_list_all_vertex_pa {
2571 template <class Tag, class Graph, class Property>
2573 typedef typename Graph::vertex_descriptor Vertex;
2574 typedef vec_adj_list_vertex_all_properties_map
2575 <Graph, Graph*, Property, Property&> type;
2576 typedef vec_adj_list_vertex_all_properties_map
2577 <Graph, const Graph*, Property, const Property&> const_type;
2581 template <class Tag>
2582 struct adj_list_choose_vertex_pa_helper {
2583 typedef adj_list_any_vertex_pa type;
2586 struct adj_list_choose_vertex_pa_helper<vertex_all_t> {
2587 typedef adj_list_all_vertex_pa type;
2589 template <class Tag, class Graph, class Property>
2590 struct adj_list_choose_vertex_pa {
2591 typedef typename adj_list_choose_vertex_pa_helper<Tag>::type Helper;
2592 typedef typename Helper::template bind_<Tag,Graph,Property> Bind;
2593 typedef typename Bind::type type;
2594 typedef typename Bind::const_type const_type;
2598 template <class Tag>
2599 struct vec_adj_list_choose_vertex_pa_helper {
2600 typedef vec_adj_list_any_vertex_pa type;
2603 struct vec_adj_list_choose_vertex_pa_helper<vertex_index_t> {
2604 typedef vec_adj_list_id_vertex_pa type;
2607 struct vec_adj_list_choose_vertex_pa_helper<vertex_all_t> {
2608 typedef vec_adj_list_all_vertex_pa type;
2610 template <class Tag, class Graph, class Property>
2611 struct vec_adj_list_choose_vertex_pa {
2612 typedef typename vec_adj_list_choose_vertex_pa_helper<Tag>::type Helper;
2613 typedef typename Helper::template bind_<Tag,Graph,Property> Bind;
2614 typedef typename Bind::type type;
2615 typedef typename Bind::const_type const_type;
2617 } // namespace detail
2619 //=========================================================================
2620 // Edge Property Map
2622 template <class Directed, class Value, class Ref, class Vertex,
2623 class Property, class Tag>
2624 struct adj_list_edge_property_map
2625 : public put_get_helper<
2627 adj_list_edge_property_map<Directed, Value, Ref, Vertex, Property,
2631 typedef Value value_type;
2632 typedef Ref reference;
2633 typedef detail::edge_desc_impl<Directed, Vertex> key_type;
2634 typedef boost::lvalue_property_map_tag category;
2635 inline Ref operator[](key_type e) const {
2636 Property& p = *(Property*)e.get_property();
2637 return get_property_value(p, Tag());
2639 inline Ref operator()(key_type e) const {
2640 return this->operator[](e);
2644 template <class Directed, class Property, class PropRef, class PropPtr,
2646 struct adj_list_edge_all_properties_map
2647 : public put_get_helper<PropRef,
2648 adj_list_edge_all_properties_map<Directed, Property, PropRef,
2652 typedef Property value_type;
2653 typedef PropRef reference;
2654 typedef detail::edge_desc_impl<Directed, Vertex> key_type;
2655 typedef boost::lvalue_property_map_tag category;
2656 inline PropRef operator[](key_type e) const {
2657 return *(PropPtr)e.get_property();
2659 inline PropRef operator()(key_type e) const {
2660 return this->operator[](e);
2664 // Edge Property Maps
2667 struct adj_list_any_edge_pmap {
2668 template <class Graph, class Property, class Tag>
2670 typedef typename property_value<Property,Tag>::type value_type;
2671 typedef value_type& reference;
2672 typedef const value_type& const_reference;
2674 typedef adj_list_edge_property_map
2675 <typename Graph::directed_category, value_type, reference,
2676 typename Graph::vertex_descriptor,Property,Tag> type;
2677 typedef adj_list_edge_property_map
2678 <typename Graph::directed_category, value_type, const_reference,
2679 typename Graph::vertex_descriptor,const Property, Tag> const_type;
2682 struct adj_list_all_edge_pmap {
2683 template <class Graph, class Property, class Tag>
2685 typedef adj_list_edge_all_properties_map
2686 <typename Graph::directed_category, Property, Property&, Property*,
2687 typename Graph::vertex_descriptor> type;
2688 typedef adj_list_edge_all_properties_map
2689 <typename Graph::directed_category, Property, const Property&,
2690 const Property*, typename Graph::vertex_descriptor> const_type;
2694 template <class Tag>
2695 struct adj_list_choose_edge_pmap_helper {
2696 typedef adj_list_any_edge_pmap type;
2699 struct adj_list_choose_edge_pmap_helper<edge_all_t> {
2700 typedef adj_list_all_edge_pmap type;
2702 template <class Tag, class Graph, class Property>
2703 struct adj_list_choose_edge_pmap {
2704 typedef typename adj_list_choose_edge_pmap_helper<Tag>::type Helper;
2705 typedef typename Helper::template bind_<Graph,Property,Tag> Bind;
2706 typedef typename Bind::type type;
2707 typedef typename Bind::const_type const_type;
2709 struct adj_list_edge_property_selector {
2710 template <class Graph, class Property, class Tag>
2712 typedef adj_list_choose_edge_pmap<Tag,Graph,Property> Choice;
2713 typedef typename Choice::type type;
2714 typedef typename Choice::const_type const_type;
2717 } // namespace detail
2720 struct edge_property_selector<adj_list_tag> {
2721 typedef detail::adj_list_edge_property_selector type;
2724 struct edge_property_selector<vec_adj_list_tag> {
2725 typedef detail::adj_list_edge_property_selector type;
2728 // Vertex Property Maps
2730 struct adj_list_vertex_property_selector {
2731 template <class Graph, class Property, class Tag>
2733 typedef detail::adj_list_choose_vertex_pa<Tag,Graph,Property> Choice;
2734 typedef typename Choice::type type;
2735 typedef typename Choice::const_type const_type;
2739 struct vertex_property_selector<adj_list_tag> {
2740 typedef adj_list_vertex_property_selector type;
2743 struct vec_adj_list_vertex_property_selector {
2744 template <class Graph, class Property, class Tag>
2746 typedef detail::vec_adj_list_choose_vertex_pa<Tag,Graph,Property> Choice;
2747 typedef typename Choice::type type;
2748 typedef typename Choice::const_type const_type;
2752 struct vertex_property_selector<vec_adj_list_tag> {
2753 typedef vec_adj_list_vertex_property_selector type;
2756 } // namespace boost
2758 #if !defined(BOOST_NO_HASH) && !defined(BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION)
2759 namespace BOOST_STD_EXTENSION_NAMESPACE {
2761 #if BOOST_WORKAROUND( _STLPORT_VERSION, >= 0x500 )
2762 // STLport 5 already defines a hash<void*> specialization.
2765 struct hash< void* > // Need this when vertex_descriptor=void*
2768 operator()(void* v) const { return (std::size_t)v; }
2772 template <typename V>
2773 struct hash< boost::detail::stored_edge<V> >
2776 operator()(const boost::detail::stored_edge<V>& e) const
2778 return hash<V>()(e.m_target);
2782 template <typename V, typename P>
2783 struct hash< boost::detail::stored_edge_property <V,P> >
2786 operator()(const boost::detail::stored_edge_property<V,P>& e) const
2788 return hash<V>()(e.m_target);
2792 template <typename V, typename I, typename P>
2793 struct hash< boost::detail::stored_edge_iter<V,I, P> >
2796 operator()(const boost::detail::stored_edge_iter<V,I,P>& e) const
2798 return hash<V>()(e.m_target);
2807 #undef stored_edge_property
2808 #undef stored_edge_iter
2810 #endif // BOOST_GRAPH_DETAIL_DETAIL_ADJACENCY_LIST_CCT
2813 Implementation Notes:
2815 Many of the public interface functions in this file would have been
2816 more conveniently implemented as inline friend functions.
2817 However there are a few compiler bugs that make that approach
2820 1. g++ inline friend in namespace bug
2821 2. g++ using clause doesn't work with inline friends
2822 3. VC++ doesn't have Koenig lookup
2824 For these reasons, the functions were all written as non-inline free
2825 functions, and static cast was used to convert from the helper
2826 class to the adjacency_list derived class.
2828 Looking back, it might have been better to write out all functions
2829 in terms of the adjacency_list, and then use a tag to dispatch
2830 to the various helpers instead of using inheritance.