1.1 --- a/epoc32/include/stdapis/boost/graph/adjacency_list.hpp Wed Mar 31 12:27:01 2010 +0100
1.2 +++ b/epoc32/include/stdapis/boost/graph/adjacency_list.hpp Wed Mar 31 12:33:34 2010 +0100
1.3 @@ -1,4 +1,3 @@
1.4 -// -*- c++ -*-
1.5 //=======================================================================
1.6 // Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
1.7 // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek
1.8 @@ -8,2825 +7,538 @@
1.9 // http://www.boost.org/LICENSE_1_0.txt)
1.10 //=======================================================================
1.11
1.12 -#ifndef BOOST_GRAPH_DETAIL_ADJACENCY_LIST_HPP
1.13 -#define BOOST_GRAPH_DETAIL_ADJACENCY_LIST_HPP
1.14 +#ifndef BOOST_GRAPH_ADJACENCY_LIST_HPP
1.15 +#define BOOST_GRAPH_ADJACENCY_LIST_HPP
1.16
1.17 -#include <map> // for vertex_map in copy_impl
1.18 +
1.19 #include <boost/config.hpp>
1.20 +
1.21 +#include <vector>
1.22 +#include <list>
1.23 +#include <set>
1.24 +
1.25 +#if !defined BOOST_NO_HASH
1.26 +# ifdef BOOST_HASH_SET_HEADER
1.27 +# include BOOST_HASH_SET_HEADER
1.28 +# else
1.29 +# include <hash_set>
1.30 +# endif
1.31 +#endif
1.32 +
1.33 +#if !defined BOOST_NO_SLIST
1.34 +# ifdef BOOST_SLIST_HEADER
1.35 +# include BOOST_SLIST_HEADER
1.36 +# else
1.37 +# include <slist>
1.38 +# endif
1.39 +#endif
1.40 +
1.41 +#include <boost/graph/graph_traits.hpp>
1.42 +#include <boost/graph/graph_selectors.hpp>
1.43 +#include <boost/property_map.hpp>
1.44 +#include <boost/pending/ct_if.hpp>
1.45 +#include <boost/graph/detail/edge.hpp>
1.46 +#include <boost/type_traits/is_same.hpp>
1.47 #include <boost/detail/workaround.hpp>
1.48 -#include <boost/operators.hpp>
1.49 -#include <boost/property_map.hpp>
1.50 -#include <boost/pending/integer_range.hpp>
1.51 -#include <boost/graph/graph_traits.hpp>
1.52 -#include <memory>
1.53 -#include <algorithm>
1.54 -#include <boost/limits.hpp>
1.55 -
1.56 -#include <boost/iterator/iterator_adaptor.hpp>
1.57 -
1.58 -#include <boost/pending/ct_if.hpp>
1.59 -#include <boost/graph/graph_concepts.hpp>
1.60 -#include <boost/pending/container_traits.hpp>
1.61 -#include <boost/graph/detail/adj_list_edge_iterator.hpp>
1.62 #include <boost/graph/properties.hpp>
1.63 -#include <boost/pending/property.hpp>
1.64 -#include <boost/graph/adjacency_iterator.hpp>
1.65 -#include <boost/static_assert.hpp>
1.66 -
1.67 -// Symbol truncation problems with MSVC, trying to shorten names.
1.68 -#define stored_edge se_
1.69 -#define stored_edge_property sep_
1.70 -#define stored_edge_iter sei_
1.71 -
1.72 -/*
1.73 - Outline for this file:
1.74 -
1.75 - out_edge_iterator and in_edge_iterator implementation
1.76 - edge_iterator for undirected graph
1.77 - stored edge types (these object live in the out-edge/in-edge lists)
1.78 - directed edges helper class
1.79 - directed graph helper class
1.80 - undirected graph helper class
1.81 - bidirectional graph helper class
1.82 - bidirectional graph helper class (without edge properties)
1.83 - bidirectional graph helper class (with edge properties)
1.84 - adjacency_list helper class
1.85 - adj_list_impl class
1.86 - vec_adj_list_impl class
1.87 - adj_list_gen class
1.88 - vertex property map
1.89 - edge property map
1.90 -
1.91 -
1.92 - Note: it would be nice to merge some of the undirected and
1.93 - bidirectional code... it is awful similar.
1.94 - */
1.95 -
1.96
1.97 namespace boost {
1.98
1.99 + //===========================================================================
1.100 + // Selectors for the VertexList and EdgeList template parameters of
1.101 + // adjacency_list, and the container_gen traits class which is used
1.102 + // to map the selectors to the container type used to implement the
1.103 + // graph.
1.104 + //
1.105 + // The main container_gen traits class uses partial specialization,
1.106 + // so we also include a workaround.
1.107 +
1.108 +#if !defined BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
1.109 +
1.110 +#if !defined BOOST_NO_SLIST
1.111 + struct slistS {};
1.112 +#endif
1.113 +
1.114 + struct vecS { };
1.115 + struct listS { };
1.116 + struct setS { };
1.117 + struct multisetS { };
1.118 + struct mapS { };
1.119 +#if !defined BOOST_NO_HASH
1.120 + struct hash_mapS { };
1.121 + struct hash_setS { };
1.122 +#endif
1.123 +
1.124 + template <class Selector, class ValueType>
1.125 + struct container_gen { };
1.126 +
1.127 + template <class ValueType>
1.128 + struct container_gen<listS, ValueType> {
1.129 + typedef std::list<ValueType> type;
1.130 + };
1.131 +#if !defined BOOST_NO_SLIST
1.132 + template <class ValueType>
1.133 + struct container_gen<slistS, ValueType> {
1.134 + typedef BOOST_STD_EXTENSION_NAMESPACE::slist<ValueType> type;
1.135 + };
1.136 +#endif
1.137 + template <class ValueType>
1.138 + struct container_gen<vecS, ValueType> {
1.139 + typedef std::vector<ValueType> type;
1.140 + };
1.141 +
1.142 + template <class ValueType>
1.143 + struct container_gen<mapS, ValueType> {
1.144 + typedef std::set<ValueType> type;
1.145 + };
1.146 +
1.147 + template <class ValueType>
1.148 + struct container_gen<setS, ValueType> {
1.149 + typedef std::set<ValueType> type;
1.150 + };
1.151 +
1.152 + template <class ValueType>
1.153 + struct container_gen<multisetS, ValueType> {
1.154 + typedef std::multiset<ValueType> type;
1.155 + };
1.156 +
1.157 +#if !defined BOOST_NO_HASH
1.158 + template <class ValueType>
1.159 + struct container_gen<hash_mapS, ValueType> {
1.160 + typedef BOOST_STD_EXTENSION_NAMESPACE::hash_set<ValueType> type;
1.161 + };
1.162 +
1.163 + template <class ValueType>
1.164 + struct container_gen<hash_setS, ValueType> {
1.165 + typedef BOOST_STD_EXTENSION_NAMESPACE::hash_set<ValueType> type;
1.166 + };
1.167 +#endif
1.168 +
1.169 +#else // !defined BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
1.170 +
1.171 +#if !defined BOOST_NO_SLIST
1.172 + struct slistS {
1.173 + template <class T>
1.174 + struct bind_ { typedef BOOST_STD_EXTENSION_NAMESPACE::slist<T> type; };
1.175 + };
1.176 +#endif
1.177 +
1.178 + struct vecS {
1.179 + template <class T>
1.180 + struct bind_ { typedef std::vector<T> type; };
1.181 + };
1.182 +
1.183 + struct listS {
1.184 + template <class T>
1.185 + struct bind_ { typedef std::list<T> type; };
1.186 + };
1.187 +
1.188 + struct setS {
1.189 + template <class T>
1.190 + struct bind_ { typedef std::set<T, std::less<T> > type; };
1.191 + };
1.192 +
1.193 + struct multisetS {
1.194 + template <class T>
1.195 + struct bind_ { typedef std::multiset<T, std::less<T> > type; };
1.196 + };
1.197 +
1.198 +#if !defined BOOST_NO_HASH
1.199 + struct hash_setS {
1.200 + template <class T>
1.201 + struct bind_ { typedef BOOST_STD_EXTENSION_NAMESPACE::hash_set<T, std::less<T> > type; };
1.202 + };
1.203 +#endif
1.204 +
1.205 + struct mapS {
1.206 + template <class T>
1.207 + struct bind_ { typedef std::set<T, std::less<T> > type; };
1.208 + };
1.209 +
1.210 +#if !defined BOOST_NO_HASH
1.211 + struct hash_mapS {
1.212 + template <class T>
1.213 + struct bind_ { typedef BOOST_STD_EXTENSION_NAMESPACE::hash_set<T, std::less<T> > type; };
1.214 + };
1.215 +#endif
1.216 +
1.217 + template <class Selector> struct container_selector {
1.218 + typedef vecS type;
1.219 + };
1.220 +
1.221 +#define BOOST_CONTAINER_SELECTOR(NAME) \
1.222 + template <> struct container_selector<NAME> { \
1.223 + typedef NAME type; \
1.224 + }
1.225 +
1.226 + BOOST_CONTAINER_SELECTOR(vecS);
1.227 + BOOST_CONTAINER_SELECTOR(listS);
1.228 + BOOST_CONTAINER_SELECTOR(mapS);
1.229 + BOOST_CONTAINER_SELECTOR(setS);
1.230 + BOOST_CONTAINER_SELECTOR(multisetS);
1.231 +#if !defined BOOST_NO_HASH
1.232 + BOOST_CONTAINER_SELECTOR(hash_mapS);
1.233 +#endif
1.234 +#if !defined BOOST_NO_SLIST
1.235 + BOOST_CONTAINER_SELECTOR(slistS);
1.236 +#endif
1.237 +
1.238 + template <class Selector, class ValueType>
1.239 + struct container_gen {
1.240 + typedef typename container_selector<Selector>::type Select;
1.241 + typedef typename Select:: template bind_<ValueType>::type type;
1.242 + };
1.243 +
1.244 +#endif // !defined BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
1.245 +
1.246 + template <class StorageSelector>
1.247 + struct parallel_edge_traits { };
1.248 +
1.249 + template <>
1.250 + struct parallel_edge_traits<vecS> {
1.251 + typedef allow_parallel_edge_tag type; };
1.252 +
1.253 + template <>
1.254 + struct parallel_edge_traits<listS> {
1.255 + typedef allow_parallel_edge_tag type; };
1.256 +
1.257 +#if !defined BOOST_NO_SLIST
1.258 + template <>
1.259 + struct parallel_edge_traits<slistS> {
1.260 + typedef allow_parallel_edge_tag type; };
1.261 +#endif
1.262 +
1.263 + template <>
1.264 + struct parallel_edge_traits<setS> {
1.265 + typedef disallow_parallel_edge_tag type; };
1.266 +
1.267 + template <>
1.268 + struct parallel_edge_traits<multisetS> {
1.269 + typedef allow_parallel_edge_tag type; };
1.270 +
1.271 +#if !defined BOOST_NO_HASH
1.272 + template <>
1.273 + struct parallel_edge_traits<hash_setS> {
1.274 + typedef disallow_parallel_edge_tag type;
1.275 + };
1.276 +#endif
1.277 +
1.278 + // mapS is obsolete, replaced with setS
1.279 + template <>
1.280 + struct parallel_edge_traits<mapS> {
1.281 + typedef disallow_parallel_edge_tag type; };
1.282 +
1.283 +#if !defined BOOST_NO_HASH
1.284 + template <>
1.285 + struct parallel_edge_traits<hash_mapS> {
1.286 + typedef disallow_parallel_edge_tag type;
1.287 + };
1.288 +#endif
1.289 +
1.290 namespace detail {
1.291 -
1.292 - template <typename DirectedS>
1.293 - struct directed_category_traits {
1.294 - typedef directed_tag directed_category;
1.295 - };
1.296 -
1.297 - template <>
1.298 - struct directed_category_traits<directedS> {
1.299 - typedef directed_tag directed_category;
1.300 + template <class Directed> struct is_random_access {
1.301 + enum { value = false};
1.302 + typedef false_type type;
1.303 };
1.304 template <>
1.305 - struct directed_category_traits<undirectedS> {
1.306 - typedef undirected_tag directed_category;
1.307 - };
1.308 - template <>
1.309 - struct directed_category_traits<bidirectionalS> {
1.310 - typedef bidirectional_tag directed_category;
1.311 - };
1.312 -
1.313 - template <class Vertex>
1.314 - struct target_is {
1.315 - target_is(const Vertex& v) : m_target(v) { }
1.316 - template <class StoredEdge>
1.317 - bool operator()(const StoredEdge& e) const {
1.318 - return e.get_target() == m_target;
1.319 - }
1.320 - Vertex m_target;
1.321 - };
1.322 -
1.323 - // O(E/V)
1.324 - template <class EdgeList, class vertex_descriptor>
1.325 - void erase_from_incidence_list(EdgeList& el, vertex_descriptor v,
1.326 - allow_parallel_edge_tag)
1.327 - {
1.328 - boost::graph_detail::erase_if(el, detail::target_is<vertex_descriptor>(v));
1.329 - }
1.330 - // O(log(E/V))
1.331 - template <class EdgeList, class vertex_descriptor>
1.332 - void erase_from_incidence_list(EdgeList& el, vertex_descriptor v,
1.333 - disallow_parallel_edge_tag)
1.334 - {
1.335 - typedef typename EdgeList::value_type StoredEdge;
1.336 - el.erase(StoredEdge(v));
1.337 - }
1.338 -
1.339 - //=========================================================================
1.340 - // Out-Edge and In-Edge Iterator Implementation
1.341 -
1.342 - template <class BaseIter, class VertexDescriptor, class EdgeDescriptor, class Difference>
1.343 - struct out_edge_iter
1.344 - : iterator_adaptor<
1.345 - out_edge_iter<BaseIter, VertexDescriptor, EdgeDescriptor, Difference>
1.346 - , BaseIter
1.347 - , EdgeDescriptor
1.348 - , use_default
1.349 - , EdgeDescriptor
1.350 - , Difference
1.351 - >
1.352 - {
1.353 - typedef iterator_adaptor<
1.354 - out_edge_iter<BaseIter, VertexDescriptor, EdgeDescriptor, Difference>
1.355 - , BaseIter
1.356 - , EdgeDescriptor
1.357 - , use_default
1.358 - , EdgeDescriptor
1.359 - , Difference
1.360 - > super_t;
1.361 -
1.362 - inline out_edge_iter() { }
1.363 - inline out_edge_iter(const BaseIter& i, const VertexDescriptor& src)
1.364 - : super_t(i), m_src(src) { }
1.365 -
1.366 - inline EdgeDescriptor
1.367 - dereference() const
1.368 - {
1.369 - return EdgeDescriptor(m_src, (*this->base()).get_target(),
1.370 - &(*this->base()).get_property());
1.371 - }
1.372 - VertexDescriptor m_src;
1.373 - };
1.374 -
1.375 - template <class BaseIter, class VertexDescriptor, class EdgeDescriptor, class Difference>
1.376 - struct in_edge_iter
1.377 - : iterator_adaptor<
1.378 - in_edge_iter<BaseIter, VertexDescriptor, EdgeDescriptor, Difference>
1.379 - , BaseIter
1.380 - , EdgeDescriptor
1.381 - , use_default
1.382 - , EdgeDescriptor
1.383 - , Difference
1.384 - >
1.385 - {
1.386 - typedef iterator_adaptor<
1.387 - in_edge_iter<BaseIter, VertexDescriptor, EdgeDescriptor, Difference>
1.388 - , BaseIter
1.389 - , EdgeDescriptor
1.390 - , use_default
1.391 - , EdgeDescriptor
1.392 - , Difference
1.393 - > super_t;
1.394 -
1.395 - inline in_edge_iter() { }
1.396 - inline in_edge_iter(const BaseIter& i, const VertexDescriptor& src)
1.397 - : super_t(i), m_src(src) { }
1.398 -
1.399 - inline EdgeDescriptor
1.400 - dereference() const
1.401 - {
1.402 - return EdgeDescriptor((*this->base()).get_target(), m_src,
1.403 - &this->base()->get_property());
1.404 - }
1.405 - VertexDescriptor m_src;
1.406 - };
1.407 -
1.408 - //=========================================================================
1.409 - // Undirected Edge Iterator Implementation
1.410 -
1.411 - template <class EdgeIter, class EdgeDescriptor, class Difference>
1.412 - struct undirected_edge_iter
1.413 - : iterator_adaptor<
1.414 - undirected_edge_iter<EdgeIter, EdgeDescriptor, Difference>
1.415 - , EdgeIter
1.416 - , EdgeDescriptor
1.417 - , use_default
1.418 - , EdgeDescriptor
1.419 - , Difference
1.420 - >
1.421 - {
1.422 - typedef iterator_adaptor<
1.423 - undirected_edge_iter<EdgeIter, EdgeDescriptor, Difference>
1.424 - , EdgeIter
1.425 - , EdgeDescriptor
1.426 - , use_default
1.427 - , EdgeDescriptor
1.428 - , Difference
1.429 - > super_t;
1.430 -
1.431 - undirected_edge_iter() {}
1.432 -
1.433 - explicit undirected_edge_iter(EdgeIter i)
1.434 - : super_t(i) {}
1.435 -
1.436 - inline EdgeDescriptor
1.437 - dereference() const {
1.438 - return EdgeDescriptor(
1.439 - (*this->base()).m_source
1.440 - , (*this->base()).m_target
1.441 - , &this->base()->get_property());
1.442 - }
1.443 - };
1.444 -
1.445 - //=========================================================================
1.446 - // Edge Storage Types (stored in the out-edge/in-edge lists)
1.447 -
1.448 - template <class Vertex>
1.449 - class stored_edge
1.450 - : public boost::equality_comparable1< stored_edge<Vertex>,
1.451 - boost::less_than_comparable1< stored_edge<Vertex> > >
1.452 - {
1.453 - public:
1.454 - typedef no_property property_type;
1.455 - inline stored_edge() { }
1.456 - inline stored_edge(Vertex target, const no_property& = no_property())
1.457 - : m_target(target) { }
1.458 - // Need to write this explicitly so stored_edge_property can
1.459 - // invoke Base::operator= (at least, for SGI MIPSPro compiler)
1.460 - inline stored_edge& operator=(const stored_edge& x) {
1.461 - m_target = x.m_target;
1.462 - return *this;
1.463 - }
1.464 - inline Vertex& get_target() const { return m_target; }
1.465 - inline const no_property& get_property() const { return s_prop; }
1.466 - inline bool operator==(const stored_edge& x) const
1.467 - { return m_target == x.get_target(); }
1.468 - inline bool operator<(const stored_edge& x) const
1.469 - { return m_target < x.get_target(); }
1.470 - //protected: need to add hash<> as a friend
1.471 - static no_property s_prop;
1.472 - // Sometimes target not used as key in the set, and in that case
1.473 - // it is ok to change the target.
1.474 - mutable Vertex m_target;
1.475 - };
1.476 - template <class Vertex>
1.477 - no_property stored_edge<Vertex>::s_prop;
1.478 -
1.479 - template <class Vertex, class Property>
1.480 - class stored_edge_property : public stored_edge<Vertex> {
1.481 - typedef stored_edge_property self;
1.482 - typedef stored_edge<Vertex> Base;
1.483 - public:
1.484 - typedef Property property_type;
1.485 - inline stored_edge_property() { }
1.486 - inline stored_edge_property(Vertex target,
1.487 - const Property& p = Property())
1.488 - : stored_edge<Vertex>(target), m_property(new Property(p)) { }
1.489 - stored_edge_property(const self& x)
1.490 - : Base(x), m_property(const_cast<self&>(x).m_property) { }
1.491 - self& operator=(const self& x) {
1.492 - Base::operator=(x);
1.493 - m_property = const_cast<self&>(x).m_property;
1.494 - return *this;
1.495 - }
1.496 - inline Property& get_property() { return *m_property; }
1.497 - inline const Property& get_property() const { return *m_property; }
1.498 - protected:
1.499 - // Holding the property by-value causes edge-descriptor
1.500 - // invalidation for add_edge() with EdgeList=vecS. Instead we
1.501 - // hold a pointer to the property. std::auto_ptr is not
1.502 - // a perfect fit for the job, but it is darn close.
1.503 - std::auto_ptr<Property> m_property;
1.504 - };
1.505 -
1.506 -
1.507 - template <class Vertex, class Iter, class Property>
1.508 - class stored_edge_iter
1.509 - : public stored_edge<Vertex>
1.510 - {
1.511 - public:
1.512 - typedef Property property_type;
1.513 - inline stored_edge_iter() { }
1.514 - inline stored_edge_iter(Vertex v)
1.515 - : stored_edge<Vertex>(v) { }
1.516 - inline stored_edge_iter(Vertex v, Iter i, void* = 0)
1.517 - : stored_edge<Vertex>(v), m_iter(i) { }
1.518 - inline Property& get_property() { return m_iter->get_property(); }
1.519 - inline const Property& get_property() const {
1.520 - return m_iter->get_property();
1.521 - }
1.522 - inline Iter get_iter() const { return m_iter; }
1.523 - protected:
1.524 - Iter m_iter;
1.525 - };
1.526 -
1.527 - // For when the EdgeList is a std::vector.
1.528 - // Want to make the iterator stable, so use an offset
1.529 - // instead of an iterator into a std::vector
1.530 - template <class Vertex, class EdgeVec, class Property>
1.531 - class stored_ra_edge_iter
1.532 - : public stored_edge<Vertex>
1.533 - {
1.534 - typedef typename EdgeVec::iterator Iter;
1.535 - public:
1.536 - typedef Property property_type;
1.537 - inline stored_ra_edge_iter() { }
1.538 - inline stored_ra_edge_iter(Vertex v, Iter i = Iter(),
1.539 - EdgeVec* edge_vec = 0)
1.540 - : stored_edge<Vertex>(v), m_i(i - edge_vec->begin()), m_vec(edge_vec){ }
1.541 - inline Property& get_property() { return (*m_vec)[m_i].get_property(); }
1.542 - inline const Property& get_property() const {
1.543 - return (*m_vec)[m_i].get_property();
1.544 - }
1.545 - inline Iter get_iter() const { return m_vec->begin() + m_i; }
1.546 - protected:
1.547 - std::size_t m_i;
1.548 - EdgeVec* m_vec;
1.549 - };
1.550 -
1.551 - } // namespace detail
1.552 -
1.553 - template <class Tag, class Vertex, class Property>
1.554 - const typename property_value<Property,Tag>::type&
1.555 - get(Tag property_tag,
1.556 - const detail::stored_edge_property<Vertex, Property>& e)
1.557 - {
1.558 - return get_property_value(e.get_property(), property_tag);
1.559 - }
1.560 -
1.561 - template <class Tag, class Vertex, class Iter, class Property>
1.562 - const typename property_value<Property,Tag>::type&
1.563 - get(Tag property_tag,
1.564 - const detail::stored_edge_iter<Vertex, Iter, Property>& e)
1.565 - {
1.566 - return get_property_value(e.get_property(), property_tag);
1.567 - }
1.568 -
1.569 - template <class Tag, class Vertex, class EdgeVec, class Property>
1.570 - const typename property_value<Property,Tag>::type&
1.571 - get(Tag property_tag,
1.572 - const detail::stored_ra_edge_iter<Vertex, EdgeVec, Property>& e)
1.573 - {
1.574 - return get_property_value(e.get_property(), property_tag);
1.575 - }
1.576 -
1.577 - //=========================================================================
1.578 - // Directed Edges Helper Class
1.579 -
1.580 - namespace detail {
1.581 -
1.582 - // O(E/V)
1.583 - template <class edge_descriptor, class EdgeList, class StoredProperty>
1.584 - inline void
1.585 - remove_directed_edge_dispatch(edge_descriptor, EdgeList& el,
1.586 - StoredProperty& p)
1.587 - {
1.588 - for (typename EdgeList::iterator i = el.begin();
1.589 - i != el.end(); ++i)
1.590 - if (&(*i).get_property() == &p) {
1.591 - el.erase(i);
1.592 - return;
1.593 - }
1.594 - }
1.595 -
1.596 - template <class incidence_iterator, class EdgeList, class Predicate>
1.597 - inline void
1.598 - remove_directed_edge_if_dispatch(incidence_iterator first,
1.599 - incidence_iterator last,
1.600 - EdgeList& el, Predicate pred,
1.601 - boost::allow_parallel_edge_tag)
1.602 - {
1.603 - // remove_if
1.604 - while (first != last && !pred(*first))
1.605 - ++first;
1.606 - incidence_iterator i = first;
1.607 - if (first != last)
1.608 - for (; i != last; ++i)
1.609 - if (!pred(*i)) {
1.610 - *first.base() = *i.base();
1.611 - ++first;
1.612 - }
1.613 - el.erase(first.base(), el.end());
1.614 - }
1.615 - template <class incidence_iterator, class EdgeList, class Predicate>
1.616 - inline void
1.617 - remove_directed_edge_if_dispatch(incidence_iterator first,
1.618 - incidence_iterator last,
1.619 - EdgeList& el,
1.620 - Predicate pred,
1.621 - boost::disallow_parallel_edge_tag)
1.622 - {
1.623 - for (incidence_iterator next = first;
1.624 - first != last; first = next) {
1.625 - ++next;
1.626 - if (pred(*first))
1.627 - el.erase( first.base() );
1.628 - }
1.629 - }
1.630 -
1.631 - template <class PropT, class Graph, class incidence_iterator,
1.632 - class EdgeList, class Predicate>
1.633 - inline void
1.634 - undirected_remove_out_edge_if_dispatch(Graph& g,
1.635 - incidence_iterator first,
1.636 - incidence_iterator last,
1.637 - EdgeList& el, Predicate pred,
1.638 - boost::allow_parallel_edge_tag)
1.639 - {
1.640 - typedef typename Graph::global_edgelist_selector EdgeListS;
1.641 - BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
1.642 -
1.643 - // remove_if
1.644 - while (first != last && !pred(*first))
1.645 - ++first;
1.646 - incidence_iterator i = first;
1.647 - bool self_loop_removed = false;
1.648 - if (first != last)
1.649 - for (; i != last; ++i) {
1.650 - if (self_loop_removed) {
1.651 - /* With self loops, the descriptor will show up
1.652 - * twice. The first time it will be removed, and now it
1.653 - * will be skipped.
1.654 - */
1.655 - self_loop_removed = false;
1.656 - }
1.657 - else if (!pred(*i)) {
1.658 - *first.base() = *i.base();
1.659 - ++first;
1.660 - } else {
1.661 - if (source(*i, g) == target(*i, g)) self_loop_removed = true;
1.662 - else {
1.663 - // Remove the edge from the target
1.664 - detail::remove_directed_edge_dispatch
1.665 - (*i,
1.666 - g.out_edge_list(target(*i, g)),
1.667 - *(PropT*)(*i).get_property());
1.668 - }
1.669 -
1.670 - // Erase the edge property
1.671 - g.m_edges.erase( (*i.base()).get_iter() );
1.672 - }
1.673 - }
1.674 - el.erase(first.base(), el.end());
1.675 - }
1.676 - template <class PropT, class Graph, class incidence_iterator,
1.677 - class EdgeList, class Predicate>
1.678 - inline void
1.679 - undirected_remove_out_edge_if_dispatch(Graph& g,
1.680 - incidence_iterator first,
1.681 - incidence_iterator last,
1.682 - EdgeList& el,
1.683 - Predicate pred,
1.684 - boost::disallow_parallel_edge_tag)
1.685 - {
1.686 - typedef typename Graph::global_edgelist_selector EdgeListS;
1.687 - BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
1.688 -
1.689 - for (incidence_iterator next = first;
1.690 - first != last; first = next) {
1.691 - ++next;
1.692 - if (pred(*first)) {
1.693 - if (source(*first, g) != target(*first, g)) {
1.694 - // Remove the edge from the target
1.695 - detail::remove_directed_edge_dispatch
1.696 - (*first,
1.697 - g.out_edge_list(target(*first, g)),
1.698 - *(PropT*)(*first).get_property());
1.699 - }
1.700 -
1.701 - // Erase the edge property
1.702 - g.m_edges.erase( (*first.base()).get_iter() );
1.703 -
1.704 - // Erase the edge in the source
1.705 - el.erase( first.base() );
1.706 - }
1.707 - }
1.708 - }
1.709 -
1.710 - // O(E/V)
1.711 - template <class edge_descriptor, class EdgeList, class StoredProperty>
1.712 - inline void
1.713 - remove_directed_edge_dispatch(edge_descriptor e, EdgeList& el,
1.714 - no_property&)
1.715 - {
1.716 - for (typename EdgeList::iterator i = el.begin();
1.717 - i != el.end(); ++i)
1.718 - if ((*i).get_target() == e.m_target) {
1.719 - el.erase(i);
1.720 - return;
1.721 - }
1.722 - }
1.723 -
1.724 - } // namespace detail
1.725 -
1.726 - template <class Config>
1.727 - struct directed_edges_helper {
1.728 -
1.729 - // Placement of these overloaded remove_edge() functions
1.730 - // inside the class avoids a VC++ bug.
1.731 -
1.732 - // O(E/V)
1.733 - inline void
1.734 - remove_edge(typename Config::edge_descriptor e)
1.735 - {
1.736 - typedef typename Config::graph_type graph_type;
1.737 - graph_type& g = static_cast<graph_type&>(*this);
1.738 - typename Config::OutEdgeList& el = g.out_edge_list(source(e, g));
1.739 - typedef typename Config::OutEdgeList::value_type::property_type PType;
1.740 - detail::remove_directed_edge_dispatch(e, el,
1.741 - *(PType*)e.get_property());
1.742 - }
1.743 -
1.744 - // O(1)
1.745 - inline void
1.746 - remove_edge(typename Config::out_edge_iterator iter)
1.747 - {
1.748 - typedef typename Config::graph_type graph_type;
1.749 - graph_type& g = static_cast<graph_type&>(*this);
1.750 - typename Config::edge_descriptor e = *iter;
1.751 - typename Config::OutEdgeList& el = g.out_edge_list(source(e, g));
1.752 - el.erase(iter.base());
1.753 - }
1.754 -
1.755 - };
1.756 -
1.757 - // O(1)
1.758 - template <class Config>
1.759 - inline std::pair<typename Config::edge_iterator,
1.760 - typename Config::edge_iterator>
1.761 - edges(const directed_edges_helper<Config>& g_)
1.762 - {
1.763 - typedef typename Config::graph_type graph_type;
1.764 - typedef typename Config::edge_iterator edge_iterator;
1.765 - const graph_type& cg = static_cast<const graph_type&>(g_);
1.766 - graph_type& g = const_cast<graph_type&>(cg);
1.767 - return std::make_pair( edge_iterator(g.vertex_set().begin(),
1.768 - g.vertex_set().begin(),
1.769 - g.vertex_set().end(), g),
1.770 - edge_iterator(g.vertex_set().begin(),
1.771 - g.vertex_set().end(),
1.772 - g.vertex_set().end(), g) );
1.773 - }
1.774 -
1.775 - //=========================================================================
1.776 - // Directed Graph Helper Class
1.777 -
1.778 - struct adj_list_dir_traversal_tag :
1.779 - public virtual vertex_list_graph_tag,
1.780 - public virtual incidence_graph_tag,
1.781 - public virtual adjacency_graph_tag,
1.782 - public virtual edge_list_graph_tag { };
1.783 -
1.784 - template <class Config>
1.785 - struct directed_graph_helper
1.786 - : public directed_edges_helper<Config> {
1.787 - typedef typename Config::edge_descriptor edge_descriptor;
1.788 - typedef adj_list_dir_traversal_tag traversal_category;
1.789 - };
1.790 -
1.791 - // O(E/V)
1.792 - template <class Config>
1.793 - inline void
1.794 - remove_edge(typename Config::vertex_descriptor u,
1.795 - typename Config::vertex_descriptor v,
1.796 - directed_graph_helper<Config>& g_)
1.797 - {
1.798 - typedef typename Config::graph_type graph_type;
1.799 - typedef typename Config::edge_parallel_category Cat;
1.800 - graph_type& g = static_cast<graph_type&>(g_);
1.801 - detail::erase_from_incidence_list(g.out_edge_list(u), v, Cat());
1.802 - }
1.803 -
1.804 - template <class Config, class Predicate>
1.805 - inline void
1.806 - remove_out_edge_if(typename Config::vertex_descriptor u, Predicate pred,
1.807 - directed_graph_helper<Config>& g_)
1.808 - {
1.809 - typedef typename Config::graph_type graph_type;
1.810 - graph_type& g = static_cast<graph_type&>(g_);
1.811 - typename Config::out_edge_iterator first, last;
1.812 - tie(first, last) = out_edges(u, g);
1.813 - typedef typename Config::edge_parallel_category edge_parallel_category;
1.814 - detail::remove_directed_edge_if_dispatch
1.815 - (first, last, g.out_edge_list(u), pred, edge_parallel_category());
1.816 - }
1.817 -
1.818 - template <class Config, class Predicate>
1.819 - inline void
1.820 - remove_edge_if(Predicate pred, directed_graph_helper<Config>& g_)
1.821 - {
1.822 - typedef typename Config::graph_type graph_type;
1.823 - graph_type& g = static_cast<graph_type&>(g_);
1.824 -
1.825 - typename Config::vertex_iterator vi, vi_end;
1.826 - for (tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi)
1.827 - remove_out_edge_if(*vi, pred, g);
1.828 - }
1.829 -
1.830 - template <class EdgeOrIter, class Config>
1.831 - inline void
1.832 - remove_edge(EdgeOrIter e_or_iter, directed_graph_helper<Config>& g_)
1.833 - {
1.834 - g_.remove_edge(e_or_iter);
1.835 - }
1.836 -
1.837 - // O(V + E) for allow_parallel_edges
1.838 - // O(V * log(E/V)) for disallow_parallel_edges
1.839 - template <class Config>
1.840 - inline void
1.841 - clear_vertex(typename Config::vertex_descriptor u,
1.842 - directed_graph_helper<Config>& g_)
1.843 - {
1.844 - typedef typename Config::graph_type graph_type;
1.845 - typedef typename Config::edge_parallel_category Cat;
1.846 - graph_type& g = static_cast<graph_type&>(g_);
1.847 - typename Config::vertex_iterator vi, viend;
1.848 - for (boost::tie(vi, viend) = vertices(g); vi != viend; ++vi)
1.849 - detail::erase_from_incidence_list(g.out_edge_list(*vi), u, Cat());
1.850 - g.out_edge_list(u).clear();
1.851 - // clear() should be a req of Sequence and AssociativeContainer,
1.852 - // or maybe just Container
1.853 - }
1.854 -
1.855 - template <class Config>
1.856 - inline void
1.857 - clear_out_edges(typename Config::vertex_descriptor u,
1.858 - directed_graph_helper<Config>& g_)
1.859 - {
1.860 - typedef typename Config::graph_type graph_type;
1.861 - typedef typename Config::edge_parallel_category Cat;
1.862 - graph_type& g = static_cast<graph_type&>(g_);
1.863 - g.out_edge_list(u).clear();
1.864 - // clear() should be a req of Sequence and AssociativeContainer,
1.865 - // or maybe just Container
1.866 - }
1.867 -
1.868 - // O(V), could do better...
1.869 - template <class Config>
1.870 - inline typename Config::edges_size_type
1.871 - num_edges(const directed_graph_helper<Config>& g_)
1.872 - {
1.873 - typedef typename Config::graph_type graph_type;
1.874 - const graph_type& g = static_cast<const graph_type&>(g_);
1.875 - typename Config::edges_size_type num_e = 0;
1.876 - typename Config::vertex_iterator vi, vi_end;
1.877 - for (boost::tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi)
1.878 - num_e += out_degree(*vi, g);
1.879 - return num_e;
1.880 - }
1.881 - // O(1) for allow_parallel_edge_tag
1.882 - // O(log(E/V)) for disallow_parallel_edge_tag
1.883 - template <class Config>
1.884 - inline std::pair<typename directed_graph_helper<Config>::edge_descriptor, bool>
1.885 - add_edge(typename Config::vertex_descriptor u,
1.886 - typename Config::vertex_descriptor v,
1.887 - const typename Config::edge_property_type& p,
1.888 - directed_graph_helper<Config>& g_)
1.889 - {
1.890 - typedef typename Config::edge_descriptor edge_descriptor;
1.891 - typedef typename Config::graph_type graph_type;
1.892 - typedef typename Config::StoredEdge StoredEdge;
1.893 - graph_type& g = static_cast<graph_type&>(g_);
1.894 - typename Config::OutEdgeList::iterator i;
1.895 - bool inserted;
1.896 - boost::tie(i, inserted) = boost::graph_detail::push(g.out_edge_list(u),
1.897 - StoredEdge(v, p));
1.898 - return std::make_pair(edge_descriptor(u, v, &(*i).get_property()),
1.899 - inserted);
1.900 - }
1.901 - // Did not use default argument here because that
1.902 - // causes Visual C++ to get confused.
1.903 - template <class Config>
1.904 - inline std::pair<typename Config::edge_descriptor, bool>
1.905 - add_edge(typename Config::vertex_descriptor u,
1.906 - typename Config::vertex_descriptor v,
1.907 - directed_graph_helper<Config>& g_)
1.908 - {
1.909 - typename Config::edge_property_type p;
1.910 - return add_edge(u, v, p, g_);
1.911 - }
1.912 - //=========================================================================
1.913 - // Undirected Graph Helper Class
1.914 -
1.915 - template <class Config>
1.916 - struct undirected_graph_helper;
1.917 -
1.918 - struct undir_adj_list_traversal_tag :
1.919 - public virtual vertex_list_graph_tag,
1.920 - public virtual incidence_graph_tag,
1.921 - public virtual adjacency_graph_tag,
1.922 - public virtual edge_list_graph_tag,
1.923 - public virtual bidirectional_graph_tag { };
1.924 -
1.925 - namespace detail {
1.926 -
1.927 - // using class with specialization for dispatch is a VC++ workaround.
1.928 - template <class StoredProperty>
1.929 - struct remove_undirected_edge_dispatch {
1.930 -
1.931 - // O(E/V)
1.932 - template <class edge_descriptor, class Config>
1.933 - static void
1.934 - apply(edge_descriptor e,
1.935 - undirected_graph_helper<Config>& g_,
1.936 - StoredProperty& p)
1.937 - {
1.938 - typedef typename Config::global_edgelist_selector EdgeListS;
1.939 - BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
1.940 -
1.941 - typedef typename Config::graph_type graph_type;
1.942 - graph_type& g = static_cast<graph_type&>(g_);
1.943 -
1.944 - typename Config::OutEdgeList& out_el = g.out_edge_list(source(e, g));
1.945 - typename Config::OutEdgeList::iterator out_i = out_el.begin();
1.946 - for (; out_i != out_el.end(); ++out_i)
1.947 - if (&(*out_i).get_property() == &p) {
1.948 - out_el.erase(out_i);
1.949 - break;
1.950 - }
1.951 - typename Config::OutEdgeList& in_el = g.out_edge_list(target(e, g));
1.952 - typename Config::OutEdgeList::iterator in_i = in_el.begin();
1.953 - for (; in_i != in_el.end(); ++in_i)
1.954 - if (&(*in_i).get_property() == &p) {
1.955 - g.m_edges.erase((*in_i).get_iter());
1.956 - in_el.erase(in_i);
1.957 - return;
1.958 - }
1.959 - }
1.960 - };
1.961 -
1.962 - template <>
1.963 - struct remove_undirected_edge_dispatch<no_property> {
1.964 - // O(E/V)
1.965 - template <class edge_descriptor, class Config>
1.966 - static void
1.967 - apply(edge_descriptor e,
1.968 - undirected_graph_helper<Config>& g_,
1.969 - no_property&)
1.970 - {
1.971 - typedef typename Config::global_edgelist_selector EdgeListS;
1.972 - BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
1.973 -
1.974 - typedef typename Config::graph_type graph_type;
1.975 - graph_type& g = static_cast<graph_type&>(g_);
1.976 - no_property* p = (no_property*)e.get_property();
1.977 - typename Config::OutEdgeList& out_el = g.out_edge_list(source(e, g));
1.978 - typename Config::OutEdgeList::iterator out_i = out_el.begin();
1.979 - for (; out_i != out_el.end(); ++out_i)
1.980 - if (&(*out_i).get_property() == p) {
1.981 - out_el.erase(out_i);
1.982 - break;
1.983 - }
1.984 - typename Config::OutEdgeList& in_el = g.out_edge_list(target(e, g));
1.985 - typename Config::OutEdgeList::iterator in_i = in_el.begin();
1.986 - for (; in_i != in_el.end(); ++in_i)
1.987 - if (&(*in_i).get_property() == p) {
1.988 - g.m_edges.erase((*in_i).get_iter());
1.989 - in_el.erase(in_i);
1.990 - return;
1.991 - }
1.992 - }
1.993 - };
1.994 -
1.995 - // O(E/V)
1.996 - template <class Graph, class EdgeList, class Vertex>
1.997 - inline void
1.998 - remove_edge_and_property(Graph& g, EdgeList& el, Vertex v,
1.999 - boost::allow_parallel_edge_tag cat)
1.1000 - {
1.1001 - typedef typename Graph::global_edgelist_selector EdgeListS;
1.1002 - BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
1.1003 -
1.1004 - typedef typename EdgeList::value_type StoredEdge;
1.1005 - typename EdgeList::iterator i = el.begin(), end = el.end();
1.1006 - for (; i != end; ++i)
1.1007 - if ((*i).get_target() == v)
1.1008 - g.m_edges.erase((*i).get_iter());
1.1009 - detail::erase_from_incidence_list(el, v, cat);
1.1010 - }
1.1011 - // O(log(E/V))
1.1012 - template <class Graph, class EdgeList, class Vertex>
1.1013 - inline void
1.1014 - remove_edge_and_property(Graph& g, EdgeList& el, Vertex v,
1.1015 - boost::disallow_parallel_edge_tag)
1.1016 - {
1.1017 - typedef typename Graph::global_edgelist_selector EdgeListS;
1.1018 - BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
1.1019 -
1.1020 - typedef typename EdgeList::value_type StoredEdge;
1.1021 - typename EdgeList::iterator i = el.find(StoredEdge(v)), end = el.end();
1.1022 - if (i != end) {
1.1023 - g.m_edges.erase((*i).get_iter());
1.1024 - el.erase(i);
1.1025 - }
1.1026 - }
1.1027 -
1.1028 - } // namespace detail
1.1029 -
1.1030 - template <class Vertex, class EdgeProperty>
1.1031 - struct list_edge // short name due to VC++ truncation and linker problems
1.1032 - : public boost::detail::edge_base<boost::undirected_tag, Vertex>
1.1033 - {
1.1034 - typedef EdgeProperty property_type;
1.1035 - typedef boost::detail::edge_base<boost::undirected_tag, Vertex> Base;
1.1036 - list_edge(Vertex u, Vertex v, const EdgeProperty& p = EdgeProperty())
1.1037 - : Base(u, v), m_property(p) { }
1.1038 - EdgeProperty& get_property() { return m_property; }
1.1039 - const EdgeProperty& get_property() const { return m_property; }
1.1040 - // the following methods should never be used, but are needed
1.1041 - // to make SGI MIPSpro C++ happy
1.1042 - list_edge() { }
1.1043 - bool operator==(const list_edge&) const { return false; }
1.1044 - bool operator<(const list_edge&) const { return false; }
1.1045 - EdgeProperty m_property;
1.1046 - };
1.1047 -
1.1048 - template <class Config>
1.1049 - struct undirected_graph_helper {
1.1050 -
1.1051 - typedef undir_adj_list_traversal_tag traversal_category;
1.1052 -
1.1053 - // Placement of these overloaded remove_edge() functions
1.1054 - // inside the class avoids a VC++ bug.
1.1055 -
1.1056 - // O(E/V)
1.1057 - inline void
1.1058 - remove_edge(typename Config::edge_descriptor e)
1.1059 - {
1.1060 - typedef typename Config::global_edgelist_selector EdgeListS;
1.1061 - BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
1.1062 -
1.1063 - typedef typename Config::OutEdgeList::value_type::property_type PType;
1.1064 - detail::remove_undirected_edge_dispatch<PType>::apply
1.1065 - (e, *this, *(PType*)e.get_property());
1.1066 - }
1.1067 - // O(E/V)
1.1068 - inline void
1.1069 - remove_edge(typename Config::out_edge_iterator iter)
1.1070 - {
1.1071 - this->remove_edge(*iter);
1.1072 - }
1.1073 - };
1.1074 -
1.1075 - // Had to make these non-members to avoid accidental instantiation
1.1076 - // on SGI MIPSpro C++
1.1077 - template <class C>
1.1078 - inline typename C::InEdgeList&
1.1079 - in_edge_list(undirected_graph_helper<C>&,
1.1080 - typename C::vertex_descriptor v)
1.1081 - {
1.1082 - typename C::stored_vertex* sv = (typename C::stored_vertex*)v;
1.1083 - return sv->m_out_edges;
1.1084 - }
1.1085 - template <class C>
1.1086 - inline const typename C::InEdgeList&
1.1087 - in_edge_list(const undirected_graph_helper<C>&,
1.1088 - typename C::vertex_descriptor v) {
1.1089 - typename C::stored_vertex* sv = (typename C::stored_vertex*)v;
1.1090 - return sv->m_out_edges;
1.1091 - }
1.1092 -
1.1093 - // O(E/V)
1.1094 - template <class EdgeOrIter, class Config>
1.1095 - inline void
1.1096 - remove_edge(EdgeOrIter e, undirected_graph_helper<Config>& g_)
1.1097 - {
1.1098 - typedef typename Config::global_edgelist_selector EdgeListS;
1.1099 - BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
1.1100 -
1.1101 - g_.remove_edge(e);
1.1102 - }
1.1103 -
1.1104 - // O(E/V) or O(log(E/V))
1.1105 - template <class Config>
1.1106 - void
1.1107 - remove_edge(typename Config::vertex_descriptor u,
1.1108 - typename Config::vertex_descriptor v,
1.1109 - undirected_graph_helper<Config>& g_)
1.1110 - {
1.1111 - typedef typename Config::global_edgelist_selector EdgeListS;
1.1112 - BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
1.1113 -
1.1114 - typedef typename Config::graph_type graph_type;
1.1115 - graph_type& g = static_cast<graph_type&>(g_);
1.1116 - typedef typename Config::edge_parallel_category Cat;
1.1117 - detail::remove_edge_and_property(g, g.out_edge_list(u), v, Cat());
1.1118 - detail::erase_from_incidence_list(g.out_edge_list(v), u, Cat());
1.1119 - }
1.1120 -
1.1121 - template <class Config, class Predicate>
1.1122 - void
1.1123 - remove_out_edge_if(typename Config::vertex_descriptor u, Predicate pred,
1.1124 - undirected_graph_helper<Config>& g_)
1.1125 - {
1.1126 - typedef typename Config::global_edgelist_selector EdgeListS;
1.1127 - BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
1.1128 -
1.1129 - typedef typename Config::graph_type graph_type;
1.1130 - typedef typename Config::OutEdgeList::value_type::property_type PropT;
1.1131 - graph_type& g = static_cast<graph_type&>(g_);
1.1132 - typename Config::out_edge_iterator first, last;
1.1133 - tie(first, last) = out_edges(u, g);
1.1134 - typedef typename Config::edge_parallel_category Cat;
1.1135 - detail::undirected_remove_out_edge_if_dispatch<PropT>
1.1136 - (g, first, last, g.out_edge_list(u), pred, Cat());
1.1137 - }
1.1138 - template <class Config, class Predicate>
1.1139 - void
1.1140 - remove_in_edge_if(typename Config::vertex_descriptor u, Predicate pred,
1.1141 - undirected_graph_helper<Config>& g_)
1.1142 - {
1.1143 - typedef typename Config::global_edgelist_selector EdgeListS;
1.1144 - BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
1.1145 -
1.1146 - remove_out_edge_if(u, pred, g_);
1.1147 - }
1.1148 -
1.1149 - // O(E/V * E) or O(log(E/V) * E)
1.1150 - template <class Predicate, class Config>
1.1151 - void
1.1152 - remove_edge_if(Predicate pred, undirected_graph_helper<Config>& g_)
1.1153 - {
1.1154 - typedef typename Config::global_edgelist_selector EdgeListS;
1.1155 - BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
1.1156 -
1.1157 - typedef typename Config::graph_type graph_type;
1.1158 - graph_type& g = static_cast<graph_type&>(g_);
1.1159 - typename Config::edge_iterator ei, ei_end, next;
1.1160 - tie(ei, ei_end) = edges(g);
1.1161 - for (next = ei; ei != ei_end; ei = next) {
1.1162 - ++next;
1.1163 - if (pred(*ei))
1.1164 - remove_edge(*ei, g);
1.1165 - }
1.1166 - }
1.1167 -
1.1168 - // O(1)
1.1169 - template <class Config>
1.1170 - inline std::pair<typename Config::edge_iterator,
1.1171 - typename Config::edge_iterator>
1.1172 - edges(const undirected_graph_helper<Config>& g_)
1.1173 - {
1.1174 - typedef typename Config::graph_type graph_type;
1.1175 - typedef typename Config::edge_iterator edge_iterator;
1.1176 - const graph_type& cg = static_cast<const graph_type&>(g_);
1.1177 - graph_type& g = const_cast<graph_type&>(cg);
1.1178 - return std::make_pair( edge_iterator(g.m_edges.begin()),
1.1179 - edge_iterator(g.m_edges.end()) );
1.1180 - }
1.1181 - // O(1)
1.1182 - template <class Config>
1.1183 - inline typename Config::edges_size_type
1.1184 - num_edges(const undirected_graph_helper<Config>& g_)
1.1185 - {
1.1186 - typedef typename Config::graph_type graph_type;
1.1187 - const graph_type& g = static_cast<const graph_type&>(g_);
1.1188 - return g.m_edges.size();
1.1189 - }
1.1190 - // O(E/V * E/V)
1.1191 - template <class Config>
1.1192 - inline void
1.1193 - clear_vertex(typename Config::vertex_descriptor u,
1.1194 - undirected_graph_helper<Config>& g_)
1.1195 - {
1.1196 - typedef typename Config::global_edgelist_selector EdgeListS;
1.1197 - BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
1.1198 -
1.1199 - typedef typename Config::graph_type graph_type;
1.1200 - typedef typename Config::edge_parallel_category Cat;
1.1201 - graph_type& g = static_cast<graph_type&>(g_);
1.1202 - typename Config::OutEdgeList& el = g.out_edge_list(u);
1.1203 - typename Config::OutEdgeList::iterator
1.1204 - ei = el.begin(), ei_end = el.end();
1.1205 - for (; ei != ei_end; ++ei) {
1.1206 - detail::erase_from_incidence_list
1.1207 - (g.out_edge_list((*ei).get_target()), u, Cat());
1.1208 - g.m_edges.erase((*ei).get_iter());
1.1209 - }
1.1210 - g.out_edge_list(u).clear();
1.1211 - }
1.1212 - // O(1) for allow_parallel_edge_tag
1.1213 - // O(log(E/V)) for disallow_parallel_edge_tag
1.1214 - template <class Config>
1.1215 - inline std::pair<typename Config::edge_descriptor, bool>
1.1216 - add_edge(typename Config::vertex_descriptor u,
1.1217 - typename Config::vertex_descriptor v,
1.1218 - const typename Config::edge_property_type& p,
1.1219 - undirected_graph_helper<Config>& g_)
1.1220 - {
1.1221 - typedef typename Config::StoredEdge StoredEdge;
1.1222 - typedef typename Config::edge_descriptor edge_descriptor;
1.1223 - typedef typename Config::graph_type graph_type;
1.1224 - graph_type& g = static_cast<graph_type&>(g_);
1.1225 -
1.1226 - bool inserted;
1.1227 - typename Config::EdgeContainer::value_type e(u, v, p);
1.1228 - typename Config::EdgeContainer::iterator p_iter
1.1229 - = graph_detail::push(g.m_edges, e).first;
1.1230 -
1.1231 - typename Config::OutEdgeList::iterator i;
1.1232 - boost::tie(i, inserted) = boost::graph_detail::push(g.out_edge_list(u),
1.1233 - StoredEdge(v, p_iter, &g.m_edges));
1.1234 - if (inserted) {
1.1235 - boost::graph_detail::push(g.out_edge_list(v), StoredEdge(u, p_iter, &g.m_edges));
1.1236 - return std::make_pair(edge_descriptor(u, v, &p_iter->get_property()),
1.1237 - true);
1.1238 - } else {
1.1239 - g.m_edges.erase(p_iter);
1.1240 - return std::make_pair
1.1241 - (edge_descriptor(u, v, &i->get_iter()->get_property()), false);
1.1242 - }
1.1243 - }
1.1244 - template <class Config>
1.1245 - inline std::pair<typename Config::edge_descriptor, bool>
1.1246 - add_edge(typename Config::vertex_descriptor u,
1.1247 - typename Config::vertex_descriptor v,
1.1248 - undirected_graph_helper<Config>& g_)
1.1249 - {
1.1250 - typename Config::edge_property_type p;
1.1251 - return add_edge(u, v, p, g_);
1.1252 - }
1.1253 -
1.1254 - // O(1)
1.1255 - template <class Config>
1.1256 - inline typename Config::degree_size_type
1.1257 - degree(typename Config::vertex_descriptor u,
1.1258 - const undirected_graph_helper<Config>& g_)
1.1259 - {
1.1260 - typedef typename Config::graph_type Graph;
1.1261 - const Graph& g = static_cast<const Graph&>(g_);
1.1262 - return out_degree(u, g);
1.1263 - }
1.1264 -
1.1265 - template <class Config>
1.1266 - inline std::pair<typename Config::in_edge_iterator,
1.1267 - typename Config::in_edge_iterator>
1.1268 - in_edges(typename Config::vertex_descriptor u,
1.1269 - const undirected_graph_helper<Config>& g_)
1.1270 - {
1.1271 - typedef typename Config::graph_type Graph;
1.1272 - const Graph& cg = static_cast<const Graph&>(g_);
1.1273 - Graph& g = const_cast<Graph&>(cg);
1.1274 - typedef typename Config::in_edge_iterator in_edge_iterator;
1.1275 - return
1.1276 - std::make_pair(in_edge_iterator(g.out_edge_list(u).begin(), u),
1.1277 - in_edge_iterator(g.out_edge_list(u).end(), u));
1.1278 - }
1.1279 -
1.1280 - template <class Config>
1.1281 - inline typename Config::degree_size_type
1.1282 - in_degree(typename Config::vertex_descriptor u,
1.1283 - const undirected_graph_helper<Config>& g_)
1.1284 - { return degree(u, g_); }
1.1285 -
1.1286 - //=========================================================================
1.1287 - // Bidirectional Graph Helper Class
1.1288 -
1.1289 - struct bidir_adj_list_traversal_tag :
1.1290 - public virtual vertex_list_graph_tag,
1.1291 - public virtual incidence_graph_tag,
1.1292 - public virtual adjacency_graph_tag,
1.1293 - public virtual edge_list_graph_tag,
1.1294 - public virtual bidirectional_graph_tag { };
1.1295 -
1.1296 - template <class Config>
1.1297 - struct bidirectional_graph_helper
1.1298 - : public directed_edges_helper<Config> {
1.1299 - typedef bidir_adj_list_traversal_tag traversal_category;
1.1300 - };
1.1301 -
1.1302 - // Had to make these non-members to avoid accidental instantiation
1.1303 - // on SGI MIPSpro C++
1.1304 - template <class C>
1.1305 - inline typename C::InEdgeList&
1.1306 - in_edge_list(bidirectional_graph_helper<C>&,
1.1307 - typename C::vertex_descriptor v)
1.1308 - {
1.1309 - typename C::stored_vertex* sv = (typename C::stored_vertex*)v;
1.1310 - return sv->m_in_edges;
1.1311 - }
1.1312 - template <class C>
1.1313 - inline const typename C::InEdgeList&
1.1314 - in_edge_list(const bidirectional_graph_helper<C>&,
1.1315 - typename C::vertex_descriptor v) {
1.1316 - typename C::stored_vertex* sv = (typename C::stored_vertex*)v;
1.1317 - return sv->m_in_edges;
1.1318 - }
1.1319 -
1.1320 - template <class Predicate, class Config>
1.1321 - inline void
1.1322 - remove_edge_if(Predicate pred, bidirectional_graph_helper<Config>& g_)
1.1323 - {
1.1324 - typedef typename Config::global_edgelist_selector EdgeListS;
1.1325 - BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
1.1326 -
1.1327 - typedef typename Config::graph_type graph_type;
1.1328 - graph_type& g = static_cast<graph_type&>(g_);
1.1329 - typename Config::edge_iterator ei, ei_end, next;
1.1330 - tie(ei, ei_end) = edges(g);
1.1331 - for (next = ei; ei != ei_end; ei = next) {
1.1332 - ++next;
1.1333 - if (pred(*ei))
1.1334 - remove_edge(*ei, g);
1.1335 - }
1.1336 - }
1.1337 -
1.1338 - template <class Config>
1.1339 - inline std::pair<typename Config::in_edge_iterator,
1.1340 - typename Config::in_edge_iterator>
1.1341 - in_edges(typename Config::vertex_descriptor u,
1.1342 - const bidirectional_graph_helper<Config>& g_)
1.1343 - {
1.1344 - typedef typename Config::graph_type graph_type;
1.1345 - const graph_type& cg = static_cast<const graph_type&>(g_);
1.1346 - graph_type& g = const_cast<graph_type&>(cg);
1.1347 - typedef typename Config::in_edge_iterator in_edge_iterator;
1.1348 - return
1.1349 - std::make_pair(in_edge_iterator(in_edge_list(g, u).begin(), u),
1.1350 - in_edge_iterator(in_edge_list(g, u).end(), u));
1.1351 - }
1.1352 -
1.1353 - // O(1)
1.1354 - template <class Config>
1.1355 - inline std::pair<typename Config::edge_iterator,
1.1356 - typename Config::edge_iterator>
1.1357 - edges(const bidirectional_graph_helper<Config>& g_)
1.1358 - {
1.1359 - typedef typename Config::graph_type graph_type;
1.1360 - typedef typename Config::edge_iterator edge_iterator;
1.1361 - const graph_type& cg = static_cast<const graph_type&>(g_);
1.1362 - graph_type& g = const_cast<graph_type&>(cg);
1.1363 - return std::make_pair( edge_iterator(g.m_edges.begin()),
1.1364 - edge_iterator(g.m_edges.end()) );
1.1365 - }
1.1366 -
1.1367 - //=========================================================================
1.1368 - // Bidirectional Graph Helper Class (with edge properties)
1.1369 -
1.1370 -
1.1371 - template <class Config>
1.1372 - struct bidirectional_graph_helper_with_property
1.1373 - : public bidirectional_graph_helper<Config>
1.1374 - {
1.1375 - typedef typename Config::graph_type graph_type;
1.1376 - typedef typename Config::out_edge_iterator out_edge_iterator;
1.1377 -
1.1378 - std::pair<out_edge_iterator, out_edge_iterator>
1.1379 - get_parallel_edge_sublist(typename Config::edge_descriptor e,
1.1380 - const graph_type& g,
1.1381 - void*)
1.1382 - { return out_edges(source(e, g), g); }
1.1383 -
1.1384 - std::pair<out_edge_iterator, out_edge_iterator>
1.1385 - get_parallel_edge_sublist(typename Config::edge_descriptor e,
1.1386 - const graph_type& g,
1.1387 - setS*)
1.1388 - { return edge_range(source(e, g), target(e, g), g); }
1.1389 -
1.1390 - std::pair<out_edge_iterator, out_edge_iterator>
1.1391 - get_parallel_edge_sublist(typename Config::edge_descriptor e,
1.1392 - const graph_type& g,
1.1393 - multisetS*)
1.1394 - { return edge_range(source(e, g), target(e, g), g); }
1.1395 -
1.1396 -#if !defined BOOST_NO_HASH
1.1397 - std::pair<out_edge_iterator, out_edge_iterator>
1.1398 - get_parallel_edge_sublist(typename Config::edge_descriptor e,
1.1399 - const graph_type& g,
1.1400 - hash_setS*)
1.1401 - { return edge_range(source(e, g), target(e, g), g); }
1.1402 -#endif
1.1403 -
1.1404 - // Placement of these overloaded remove_edge() functions
1.1405 - // inside the class avoids a VC++ bug.
1.1406 -
1.1407 - // O(E/V) or O(log(E/V))
1.1408 - void
1.1409 - remove_edge(typename Config::edge_descriptor e)
1.1410 - {
1.1411 - typedef typename Config::global_edgelist_selector EdgeListS;
1.1412 - BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
1.1413 -
1.1414 - graph_type& g = static_cast<graph_type&>(*this);
1.1415 -
1.1416 - typedef typename Config::edgelist_selector OutEdgeListS;
1.1417 -
1.1418 - std::pair<out_edge_iterator, out_edge_iterator> rng =
1.1419 - get_parallel_edge_sublist(e, g, (OutEdgeListS*)(0));
1.1420 - rng.first = std::find(rng.first, rng.second, e);
1.1421 - assert(rng.first != rng.second);
1.1422 - remove_edge(rng.first);
1.1423 - }
1.1424 -
1.1425 - inline void
1.1426 - remove_edge(typename Config::out_edge_iterator iter)
1.1427 - {
1.1428 - typedef typename Config::global_edgelist_selector EdgeListS;
1.1429 - BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
1.1430 -
1.1431 - typedef typename Config::graph_type graph_type;
1.1432 - graph_type& g = static_cast<graph_type&>(*this);
1.1433 - typename Config::edge_descriptor e = *iter;
1.1434 - typename Config::OutEdgeList& oel = g.out_edge_list(source(e, g));
1.1435 - typename Config::InEdgeList& iel = in_edge_list(g, target(e, g));
1.1436 - typedef typename Config::OutEdgeList::value_type::property_type PType;
1.1437 - PType& p = *(PType*)e.get_property();
1.1438 - detail::remove_directed_edge_dispatch(*iter, iel, p);
1.1439 - g.m_edges.erase(iter.base()->get_iter());
1.1440 - oel.erase(iter.base());
1.1441 - }
1.1442 - };
1.1443 -
1.1444 - // O(E/V) for allow_parallel_edge_tag
1.1445 - // O(log(E/V)) for disallow_parallel_edge_tag
1.1446 - template <class Config>
1.1447 - inline void
1.1448 - remove_edge(typename Config::vertex_descriptor u,
1.1449 - typename Config::vertex_descriptor v,
1.1450 - bidirectional_graph_helper_with_property<Config>& g_)
1.1451 - {
1.1452 - typedef typename Config::global_edgelist_selector EdgeListS;
1.1453 - BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
1.1454 -
1.1455 - typedef typename Config::graph_type graph_type;
1.1456 - graph_type& g = static_cast<graph_type&>(g_);
1.1457 - typedef typename Config::edge_parallel_category Cat;
1.1458 - detail::remove_edge_and_property(g, g.out_edge_list(u), v, Cat());
1.1459 - detail::erase_from_incidence_list(in_edge_list(g, v), u, Cat());
1.1460 - }
1.1461 -
1.1462 - // O(E/V) or O(log(E/V))
1.1463 - template <class EdgeOrIter, class Config>
1.1464 - inline void
1.1465 - remove_edge(EdgeOrIter e,
1.1466 - bidirectional_graph_helper_with_property<Config>& g_)
1.1467 - {
1.1468 - typedef typename Config::global_edgelist_selector EdgeListS;
1.1469 - BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
1.1470 -
1.1471 - g_.remove_edge(e);
1.1472 - }
1.1473 -
1.1474 - template <class Config, class Predicate>
1.1475 - inline void
1.1476 - remove_out_edge_if(typename Config::vertex_descriptor u, Predicate pred,
1.1477 - bidirectional_graph_helper_with_property<Config>& g_)
1.1478 - {
1.1479 - typedef typename Config::global_edgelist_selector EdgeListS;
1.1480 - BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
1.1481 -
1.1482 - typedef typename Config::graph_type graph_type;
1.1483 - typedef typename Config::OutEdgeList::value_type::property_type PropT;
1.1484 - graph_type& g = static_cast<graph_type&>(g_);
1.1485 -
1.1486 - typedef typename Config::EdgeIter EdgeIter;
1.1487 - typedef std::vector<EdgeIter> Garbage;
1.1488 - Garbage garbage;
1.1489 -
1.1490 - // First remove the edges from the targets' in-edge lists and
1.1491 - // from the graph's edge set list.
1.1492 - typename Config::out_edge_iterator out_i, out_end;
1.1493 - for (tie(out_i, out_end) = out_edges(u, g); out_i != out_end; ++out_i)
1.1494 - if (pred(*out_i)) {
1.1495 - detail::remove_directed_edge_dispatch
1.1496 - (*out_i, in_edge_list(g, target(*out_i, g)),
1.1497 - *(PropT*)(*out_i).get_property());
1.1498 - // Put in garbage to delete later. Will need the properties
1.1499 - // for the remove_if of the out-edges.
1.1500 - garbage.push_back((*out_i.base()).get_iter());
1.1501 - }
1.1502 -
1.1503 - // Now remove the edges from this out-edge list.
1.1504 - typename Config::out_edge_iterator first, last;
1.1505 - tie(first, last) = out_edges(u, g);
1.1506 - typedef typename Config::edge_parallel_category Cat;
1.1507 - detail::remove_directed_edge_if_dispatch
1.1508 - (first, last, g.out_edge_list(u), pred, Cat());
1.1509 -
1.1510 - // Now delete the edge properties from the g.m_edges list
1.1511 - for (typename Garbage::iterator i = garbage.begin();
1.1512 - i != garbage.end(); ++i)
1.1513 - g.m_edges.erase(*i);
1.1514 - }
1.1515 - template <class Config, class Predicate>
1.1516 - inline void
1.1517 - remove_in_edge_if(typename Config::vertex_descriptor v, Predicate pred,
1.1518 - bidirectional_graph_helper_with_property<Config>& g_)
1.1519 - {
1.1520 - typedef typename Config::global_edgelist_selector EdgeListS;
1.1521 - BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
1.1522 -
1.1523 - typedef typename Config::graph_type graph_type;
1.1524 - typedef typename Config::OutEdgeList::value_type::property_type PropT;
1.1525 - graph_type& g = static_cast<graph_type&>(g_);
1.1526 -
1.1527 - typedef typename Config::EdgeIter EdgeIter;
1.1528 - typedef std::vector<EdgeIter> Garbage;
1.1529 - Garbage garbage;
1.1530 -
1.1531 - // First remove the edges from the sources' out-edge lists and
1.1532 - // from the graph's edge set list.
1.1533 - typename Config::in_edge_iterator in_i, in_end;
1.1534 - for (tie(in_i, in_end) = in_edges(v, g); in_i != in_end; ++in_i)
1.1535 - if (pred(*in_i)) {
1.1536 - typename Config::vertex_descriptor u = source(*in_i, g);
1.1537 - detail::remove_directed_edge_dispatch
1.1538 - (*in_i, g.out_edge_list(u), *(PropT*)(*in_i).get_property());
1.1539 - // Put in garbage to delete later. Will need the properties
1.1540 - // for the remove_if of the out-edges.
1.1541 - garbage.push_back((*in_i.base()).get_iter());
1.1542 - }
1.1543 - // Now remove the edges from this in-edge list.
1.1544 - typename Config::in_edge_iterator first, last;
1.1545 - tie(first, last) = in_edges(v, g);
1.1546 - typedef typename Config::edge_parallel_category Cat;
1.1547 - detail::remove_directed_edge_if_dispatch
1.1548 - (first, last, in_edge_list(g, v), pred, Cat());
1.1549 -
1.1550 - // Now delete the edge properties from the g.m_edges list
1.1551 - for (typename Garbage::iterator i = garbage.begin();
1.1552 - i != garbage.end(); ++i)
1.1553 - g.m_edges.erase(*i);
1.1554 - }
1.1555 -
1.1556 - // O(1)
1.1557 - template <class Config>
1.1558 - inline typename Config::edges_size_type
1.1559 - num_edges(const bidirectional_graph_helper_with_property<Config>& g_)
1.1560 - {
1.1561 - typedef typename Config::graph_type graph_type;
1.1562 - const graph_type& g = static_cast<const graph_type&>(g_);
1.1563 - return g.m_edges.size();
1.1564 - }
1.1565 - // O(E/V * E/V) for allow_parallel_edge_tag
1.1566 - // O(E/V * log(E/V)) for disallow_parallel_edge_tag
1.1567 - template <class Config>
1.1568 - inline void
1.1569 - clear_vertex(typename Config::vertex_descriptor u,
1.1570 - bidirectional_graph_helper_with_property<Config>& g_)
1.1571 - {
1.1572 - typedef typename Config::global_edgelist_selector EdgeListS;
1.1573 - BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
1.1574 -
1.1575 - typedef typename Config::graph_type graph_type;
1.1576 - typedef typename Config::edge_parallel_category Cat;
1.1577 - graph_type& g = static_cast<graph_type&>(g_);
1.1578 - typename Config::OutEdgeList& el = g.out_edge_list(u);
1.1579 - typename Config::OutEdgeList::iterator
1.1580 - ei = el.begin(), ei_end = el.end();
1.1581 - for (; ei != ei_end; ++ei) {
1.1582 - detail::erase_from_incidence_list
1.1583 - (in_edge_list(g, (*ei).get_target()), u, Cat());
1.1584 - g.m_edges.erase((*ei).get_iter());
1.1585 - }
1.1586 - typename Config::InEdgeList& in_el = in_edge_list(g, u);
1.1587 - typename Config::InEdgeList::iterator
1.1588 - in_ei = in_el.begin(), in_ei_end = in_el.end();
1.1589 - for (; in_ei != in_ei_end; ++in_ei) {
1.1590 - detail::erase_from_incidence_list
1.1591 - (g.out_edge_list((*in_ei).get_target()), u, Cat());
1.1592 - g.m_edges.erase((*in_ei).get_iter());
1.1593 - }
1.1594 - g.out_edge_list(u).clear();
1.1595 - in_edge_list(g, u).clear();
1.1596 - }
1.1597 -
1.1598 - template <class Config>
1.1599 - inline void
1.1600 - clear_out_edges(typename Config::vertex_descriptor u,
1.1601 - bidirectional_graph_helper_with_property<Config>& g_)
1.1602 - {
1.1603 - typedef typename Config::global_edgelist_selector EdgeListS;
1.1604 - BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
1.1605 -
1.1606 - typedef typename Config::graph_type graph_type;
1.1607 - typedef typename Config::edge_parallel_category Cat;
1.1608 - graph_type& g = static_cast<graph_type&>(g_);
1.1609 - typename Config::OutEdgeList& el = g.out_edge_list(u);
1.1610 - typename Config::OutEdgeList::iterator
1.1611 - ei = el.begin(), ei_end = el.end();
1.1612 - for (; ei != ei_end; ++ei) {
1.1613 - detail::erase_from_incidence_list
1.1614 - (in_edge_list(g, (*ei).get_target()), u, Cat());
1.1615 - g.m_edges.erase((*ei).get_iter());
1.1616 - }
1.1617 - g.out_edge_list(u).clear();
1.1618 - }
1.1619 -
1.1620 - template <class Config>
1.1621 - inline void
1.1622 - clear_in_edges(typename Config::vertex_descriptor u,
1.1623 - bidirectional_graph_helper_with_property<Config>& g_)
1.1624 - {
1.1625 - typedef typename Config::global_edgelist_selector EdgeListS;
1.1626 - BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
1.1627 -
1.1628 - typedef typename Config::graph_type graph_type;
1.1629 - typedef typename Config::edge_parallel_category Cat;
1.1630 - graph_type& g = static_cast<graph_type&>(g_);
1.1631 - typename Config::InEdgeList& in_el = in_edge_list(g, u);
1.1632 - typename Config::InEdgeList::iterator
1.1633 - in_ei = in_el.begin(), in_ei_end = in_el.end();
1.1634 - for (; in_ei != in_ei_end; ++in_ei) {
1.1635 - detail::erase_from_incidence_list
1.1636 - (g.out_edge_list((*in_ei).get_target()), u, Cat());
1.1637 - g.m_edges.erase((*in_ei).get_iter());
1.1638 - }
1.1639 - in_edge_list(g, u).clear();
1.1640 - }
1.1641 -
1.1642 - // O(1) for allow_parallel_edge_tag
1.1643 - // O(log(E/V)) for disallow_parallel_edge_tag
1.1644 - template <class Config>
1.1645 - inline std::pair<typename Config::edge_descriptor, bool>
1.1646 - add_edge(typename Config::vertex_descriptor u,
1.1647 - typename Config::vertex_descriptor v,
1.1648 - const typename Config::edge_property_type& p,
1.1649 - bidirectional_graph_helper_with_property<Config>& g_)
1.1650 - {
1.1651 - typedef typename Config::graph_type graph_type;
1.1652 - graph_type& g = static_cast<graph_type&>(g_);
1.1653 - typedef typename Config::edge_descriptor edge_descriptor;
1.1654 - typedef typename Config::StoredEdge StoredEdge;
1.1655 - bool inserted;
1.1656 - typename Config::EdgeContainer::value_type e(u, v, p);
1.1657 - typename Config::EdgeContainer::iterator p_iter
1.1658 - = graph_detail::push(g.m_edges, e).first;
1.1659 - typename Config::OutEdgeList::iterator i;
1.1660 - boost::tie(i, inserted) = boost::graph_detail::push(g.out_edge_list(u),
1.1661 - StoredEdge(v, p_iter, &g.m_edges));
1.1662 - if (inserted) {
1.1663 - boost::graph_detail::push(in_edge_list(g, v), StoredEdge(u, p_iter, &g.m_edges));
1.1664 - return std::make_pair(edge_descriptor(u, v, &p_iter->m_property),
1.1665 - true);
1.1666 - } else {
1.1667 - g.m_edges.erase(p_iter);
1.1668 - return std::make_pair(edge_descriptor(u, v,
1.1669 - &i->get_iter()->get_property()),
1.1670 - false);
1.1671 - }
1.1672 - }
1.1673 -
1.1674 - template <class Config>
1.1675 - inline std::pair<typename Config::edge_descriptor, bool>
1.1676 - add_edge(typename Config::vertex_descriptor u,
1.1677 - typename Config::vertex_descriptor v,
1.1678 - bidirectional_graph_helper_with_property<Config>& g_)
1.1679 - {
1.1680 - typename Config::edge_property_type p;
1.1681 - return add_edge(u, v, p, g_);
1.1682 - }
1.1683 - // O(1)
1.1684 - template <class Config>
1.1685 - inline typename Config::degree_size_type
1.1686 - degree(typename Config::vertex_descriptor u,
1.1687 - const bidirectional_graph_helper_with_property<Config>& g_)
1.1688 - {
1.1689 - typedef typename Config::graph_type graph_type;
1.1690 - const graph_type& g = static_cast<const graph_type&>(g_);
1.1691 - return in_degree(u, g) + out_degree(u, g);
1.1692 - }
1.1693 -
1.1694 - //=========================================================================
1.1695 - // Adjacency List Helper Class
1.1696 -
1.1697 - template <class Config, class Base>
1.1698 - struct adj_list_helper : public Base
1.1699 - {
1.1700 - typedef typename Config::graph_type AdjList;
1.1701 - typedef typename Config::vertex_descriptor vertex_descriptor;
1.1702 - typedef typename Config::edge_descriptor edge_descriptor;
1.1703 - typedef typename Config::out_edge_iterator out_edge_iterator;
1.1704 - typedef typename Config::in_edge_iterator in_edge_iterator;
1.1705 - typedef typename Config::adjacency_iterator adjacency_iterator;
1.1706 - typedef typename Config::inv_adjacency_iterator inv_adjacency_iterator;
1.1707 - typedef typename Config::vertex_iterator vertex_iterator;
1.1708 - typedef typename Config::edge_iterator edge_iterator;
1.1709 - typedef typename Config::directed_category directed_category;
1.1710 - typedef typename Config::edge_parallel_category edge_parallel_category;
1.1711 - typedef typename Config::vertices_size_type vertices_size_type;
1.1712 - typedef typename Config::edges_size_type edges_size_type;
1.1713 - typedef typename Config::degree_size_type degree_size_type;
1.1714 - typedef typename Config::StoredEdge StoredEdge;
1.1715 - typedef typename Config::edge_property_type edge_property_type;
1.1716 -
1.1717 - typedef typename Config::global_edgelist_selector
1.1718 - global_edgelist_selector;
1.1719 -
1.1720 - // protected:
1.1721 -
1.1722 - // The edge_dispatch() functions should be static, but
1.1723 - // Borland gets confused about constness.
1.1724 -
1.1725 - // O(E/V)
1.1726 - inline std::pair<edge_descriptor,bool>
1.1727 - edge_dispatch(const AdjList& g,
1.1728 - vertex_descriptor u, vertex_descriptor v,
1.1729 - boost::allow_parallel_edge_tag) const
1.1730 - {
1.1731 - bool found;
1.1732 - const typename Config::OutEdgeList& el = g.out_edge_list(u);
1.1733 - typename Config::OutEdgeList::const_iterator
1.1734 - i = std::find_if(el.begin(), el.end(),
1.1735 - detail::target_is<vertex_descriptor>(v));
1.1736 - found = (i != g.out_edge_list(u).end());
1.1737 - if (found)
1.1738 - return std::make_pair(edge_descriptor(u, v, &(*i).get_property()),
1.1739 - true);
1.1740 - else
1.1741 - return std::make_pair(edge_descriptor(u, v, 0), false);
1.1742 - }
1.1743 - // O(log(E/V))
1.1744 - inline std::pair<edge_descriptor,bool>
1.1745 - edge_dispatch(const AdjList& g,
1.1746 - vertex_descriptor u, vertex_descriptor v,
1.1747 - boost::disallow_parallel_edge_tag) const
1.1748 - {
1.1749 - bool found;
1.1750 - /* According to the standard, this should be iterator, not const_iterator,
1.1751 - but the VC++ std::set::find() const returns const_iterator.
1.1752 - And since iterator should be convertible to const_iterator, the
1.1753 - following should work everywhere. -Jeremy */
1.1754 - typename Config::OutEdgeList::const_iterator
1.1755 - i = g.out_edge_list(u).find(StoredEdge(v)),
1.1756 - end = g.out_edge_list(u).end();
1.1757 - found = (i != end);
1.1758 - if (found)
1.1759 - return std::make_pair(edge_descriptor(u, v, &(*i).get_property()),
1.1760 - true);
1.1761 - else
1.1762 - return std::make_pair(edge_descriptor(u, v, 0), false);
1.1763 - }
1.1764 - };
1.1765 -
1.1766 - template <class Config, class Base>
1.1767 - inline std::pair<typename Config::adjacency_iterator,
1.1768 - typename Config::adjacency_iterator>
1.1769 - adjacent_vertices(typename Config::vertex_descriptor u,
1.1770 - const adj_list_helper<Config, Base>& g_)
1.1771 - {
1.1772 - typedef typename Config::graph_type AdjList;
1.1773 - const AdjList& cg = static_cast<const AdjList&>(g_);
1.1774 - AdjList& g = const_cast<AdjList&>(cg);
1.1775 - typedef typename Config::adjacency_iterator adjacency_iterator;
1.1776 - typename Config::out_edge_iterator first, last;
1.1777 - boost::tie(first, last) = out_edges(u, g);
1.1778 - return std::make_pair(adjacency_iterator(first, &g),
1.1779 - adjacency_iterator(last, &g));
1.1780 - }
1.1781 - template <class Config, class Base>
1.1782 - inline std::pair<typename Config::inv_adjacency_iterator,
1.1783 - typename Config::inv_adjacency_iterator>
1.1784 - inv_adjacent_vertices(typename Config::vertex_descriptor u,
1.1785 - const adj_list_helper<Config, Base>& g_)
1.1786 - {
1.1787 - typedef typename Config::graph_type AdjList;
1.1788 - const AdjList& cg = static_cast<const AdjList&>(g_);
1.1789 - AdjList& g = const_cast<AdjList&>(cg);
1.1790 - typedef typename Config::inv_adjacency_iterator inv_adjacency_iterator;
1.1791 - typename Config::in_edge_iterator first, last;
1.1792 - boost::tie(first, last) = in_edges(u, g);
1.1793 - return std::make_pair(inv_adjacency_iterator(first, &g),
1.1794 - inv_adjacency_iterator(last, &g));
1.1795 - }
1.1796 - template <class Config, class Base>
1.1797 - inline std::pair<typename Config::out_edge_iterator,
1.1798 - typename Config::out_edge_iterator>
1.1799 - out_edges(typename Config::vertex_descriptor u,
1.1800 - const adj_list_helper<Config, Base>& g_)
1.1801 - {
1.1802 - typedef typename Config::graph_type AdjList;
1.1803 - typedef typename Config::out_edge_iterator out_edge_iterator;
1.1804 - const AdjList& cg = static_cast<const AdjList&>(g_);
1.1805 - AdjList& g = const_cast<AdjList&>(cg);
1.1806 - return
1.1807 - std::make_pair(out_edge_iterator(g.out_edge_list(u).begin(), u),
1.1808 - out_edge_iterator(g.out_edge_list(u).end(), u));
1.1809 - }
1.1810 - template <class Config, class Base>
1.1811 - inline std::pair<typename Config::vertex_iterator,
1.1812 - typename Config::vertex_iterator>
1.1813 - vertices(const adj_list_helper<Config, Base>& g_)
1.1814 - {
1.1815 - typedef typename Config::graph_type AdjList;
1.1816 - const AdjList& cg = static_cast<const AdjList&>(g_);
1.1817 - AdjList& g = const_cast<AdjList&>(cg);
1.1818 - return std::make_pair( g.vertex_set().begin(), g.vertex_set().end() );
1.1819 - }
1.1820 - template <class Config, class Base>
1.1821 - inline typename Config::vertices_size_type
1.1822 - num_vertices(const adj_list_helper<Config, Base>& g_)
1.1823 - {
1.1824 - typedef typename Config::graph_type AdjList;
1.1825 - const AdjList& g = static_cast<const AdjList&>(g_);
1.1826 - return g.vertex_set().size();
1.1827 - }
1.1828 - template <class Config, class Base>
1.1829 - inline typename Config::degree_size_type
1.1830 - out_degree(typename Config::vertex_descriptor u,
1.1831 - const adj_list_helper<Config, Base>& g_)
1.1832 - {
1.1833 - typedef typename Config::graph_type AdjList;
1.1834 - const AdjList& g = static_cast<const AdjList&>(g_);
1.1835 - return g.out_edge_list(u).size();
1.1836 - }
1.1837 - template <class Config, class Base>
1.1838 - inline std::pair<typename Config::edge_descriptor, bool>
1.1839 - edge(typename Config::vertex_descriptor u,
1.1840 - typename Config::vertex_descriptor v,
1.1841 - const adj_list_helper<Config, Base>& g_)
1.1842 - {
1.1843 - typedef typename Config::graph_type Graph;
1.1844 - typedef typename Config::edge_parallel_category Cat;
1.1845 - const Graph& g = static_cast<const Graph&>(g_);
1.1846 - return g_.edge_dispatch(g, u, v, Cat());
1.1847 - }
1.1848 - template <class Config, class Base>
1.1849 - inline std::pair<typename Config::out_edge_iterator,
1.1850 - typename Config::out_edge_iterator>
1.1851 - edge_range(typename Config::vertex_descriptor u,
1.1852 - typename Config::vertex_descriptor v,
1.1853 - const adj_list_helper<Config, Base>& g_)
1.1854 - {
1.1855 - typedef typename Config::graph_type Graph;
1.1856 - typedef typename Config::StoredEdge StoredEdge;
1.1857 - const Graph& cg = static_cast<const Graph&>(g_);
1.1858 - Graph& g = const_cast<Graph&>(cg);
1.1859 - typedef typename Config::out_edge_iterator out_edge_iterator;
1.1860 - typename Config::OutEdgeList& el = g.out_edge_list(u);
1.1861 - typename Config::OutEdgeList::iterator first, last;
1.1862 - typename Config::EdgeContainer fake_edge_container;
1.1863 - tie(first, last) =
1.1864 - std::equal_range(el.begin(), el.end(),
1.1865 - StoredEdge(v, fake_edge_container.end(),
1.1866 - &fake_edge_container));
1.1867 - return std::make_pair(out_edge_iterator(first, u),
1.1868 - out_edge_iterator(last, u));
1.1869 - }
1.1870 -
1.1871 - template <class Config>
1.1872 - inline typename Config::degree_size_type
1.1873 - in_degree(typename Config::vertex_descriptor u,
1.1874 - const directed_edges_helper<Config>& g_)
1.1875 - {
1.1876 - typedef typename Config::graph_type Graph;
1.1877 - const Graph& cg = static_cast<const Graph&>(g_);
1.1878 - Graph& g = const_cast<Graph&>(cg);
1.1879 - return in_edge_list(g, u).size();
1.1880 - }
1.1881 -
1.1882 - namespace detail {
1.1883 - template <class Config, class Base, class Property>
1.1884 - inline
1.1885 - typename boost::property_map<typename Config::graph_type,
1.1886 - Property>::type
1.1887 - get_dispatch(adj_list_helper<Config,Base>&, Property,
1.1888 - boost::edge_property_tag) {
1.1889 - typedef typename Config::graph_type Graph;
1.1890 - typedef typename boost::property_map<Graph, Property>::type PA;
1.1891 - return PA();
1.1892 - }
1.1893 - template <class Config, class Base, class Property>
1.1894 - inline
1.1895 - typename boost::property_map<typename Config::graph_type,
1.1896 - Property>::const_type
1.1897 - get_dispatch(const adj_list_helper<Config,Base>&, Property,
1.1898 - boost::edge_property_tag) {
1.1899 - typedef typename Config::graph_type Graph;
1.1900 - typedef typename boost::property_map<Graph, Property>::const_type PA;
1.1901 - return PA();
1.1902 - }
1.1903 -
1.1904 - template <class Config, class Base, class Property>
1.1905 - inline
1.1906 - typename boost::property_map<typename Config::graph_type,
1.1907 - Property>::type
1.1908 - get_dispatch(adj_list_helper<Config,Base>& g, Property,
1.1909 - boost::vertex_property_tag) {
1.1910 - typedef typename Config::graph_type Graph;
1.1911 - typedef typename boost::property_map<Graph, Property>::type PA;
1.1912 - return PA(&static_cast<Graph&>(g));
1.1913 - }
1.1914 - template <class Config, class Base, class Property>
1.1915 - inline
1.1916 - typename boost::property_map<typename Config::graph_type,
1.1917 - Property>::const_type
1.1918 - get_dispatch(const adj_list_helper<Config, Base>& g, Property,
1.1919 - boost::vertex_property_tag) {
1.1920 - typedef typename Config::graph_type Graph;
1.1921 - typedef typename boost::property_map<Graph, Property>::const_type PA;
1.1922 - const Graph& cg = static_cast<const Graph&>(g);
1.1923 - return PA(&cg);
1.1924 - }
1.1925 -
1.1926 - } // namespace detail
1.1927 -
1.1928 - // Implementation of the PropertyGraph interface
1.1929 - template <class Config, class Base, class Property>
1.1930 - inline
1.1931 - typename boost::property_map<typename Config::graph_type, Property>::type
1.1932 - get(Property p, adj_list_helper<Config, Base>& g) {
1.1933 - typedef typename property_kind<Property>::type Kind;
1.1934 - return detail::get_dispatch(g, p, Kind());
1.1935 - }
1.1936 - template <class Config, class Base, class Property>
1.1937 - inline
1.1938 - typename boost::property_map<typename Config::graph_type,
1.1939 - Property>::const_type
1.1940 - get(Property p, const adj_list_helper<Config, Base>& g) {
1.1941 - typedef typename property_kind<Property>::type Kind;
1.1942 - return detail::get_dispatch(g, p, Kind());
1.1943 - }
1.1944 -
1.1945 - template <class Config, class Base, class Property, class Key>
1.1946 - inline
1.1947 - typename boost::property_traits<
1.1948 - typename boost::property_map<typename Config::graph_type,
1.1949 - Property>::type
1.1950 - >::reference
1.1951 - get(Property p, adj_list_helper<Config, Base>& g, const Key& key) {
1.1952 - return get(get(p, g), key);
1.1953 - }
1.1954 -
1.1955 - template <class Config, class Base, class Property, class Key>
1.1956 - inline
1.1957 - typename boost::property_traits<
1.1958 - typename boost::property_map<typename Config::graph_type,
1.1959 - Property>::const_type
1.1960 - >::reference
1.1961 - get(Property p, const adj_list_helper<Config, Base>& g, const Key& key) {
1.1962 - return get(get(p, g), key);
1.1963 - }
1.1964 -
1.1965 - template <class Config, class Base, class Property, class Key,class Value>
1.1966 - inline void
1.1967 - put(Property p, adj_list_helper<Config, Base>& g,
1.1968 - const Key& key, const Value& value)
1.1969 - {
1.1970 - typedef typename Config::graph_type Graph;
1.1971 - typedef typename boost::property_map<Graph, Property>::type Map;
1.1972 - Map pmap = get(p, static_cast<Graph&>(g));
1.1973 - put(pmap, key, value);
1.1974 - }
1.1975 -
1.1976 -
1.1977 - //=========================================================================
1.1978 - // Generalize Adjacency List Implementation
1.1979 -
1.1980 - struct adj_list_tag { };
1.1981 -
1.1982 - template <class Derived, class Config, class Base>
1.1983 - class adj_list_impl
1.1984 - : public adj_list_helper<Config, Base>
1.1985 - {
1.1986 - typedef typename Config::OutEdgeList OutEdgeList;
1.1987 - typedef typename Config::InEdgeList InEdgeList;
1.1988 - typedef typename Config::StoredVertexList StoredVertexList;
1.1989 - public:
1.1990 - typedef typename Config::stored_vertex stored_vertex;
1.1991 - typedef typename Config::EdgeContainer EdgeContainer;
1.1992 - typedef typename Config::vertex_descriptor vertex_descriptor;
1.1993 - typedef typename Config::edge_descriptor edge_descriptor;
1.1994 - typedef typename Config::vertex_iterator vertex_iterator;
1.1995 - typedef typename Config::edge_iterator edge_iterator;
1.1996 - typedef typename Config::edge_parallel_category edge_parallel_category;
1.1997 - typedef typename Config::vertices_size_type vertices_size_type;
1.1998 - typedef typename Config::edges_size_type edges_size_type;
1.1999 - typedef typename Config::degree_size_type degree_size_type;
1.2000 - typedef typename Config::edge_property_type edge_property_type;
1.2001 - typedef adj_list_tag graph_tag;
1.2002 -
1.2003 - static vertex_descriptor null_vertex()
1.2004 - {
1.2005 - return 0;
1.2006 - }
1.2007 -
1.2008 - inline adj_list_impl() { }
1.2009 -
1.2010 - inline adj_list_impl(const adj_list_impl& x) {
1.2011 - copy_impl(x);
1.2012 - }
1.2013 - inline adj_list_impl& operator=(const adj_list_impl& x) {
1.2014 - this->clear();
1.2015 - copy_impl(x);
1.2016 - return *this;
1.2017 - }
1.2018 - inline void clear() {
1.2019 - for (typename StoredVertexList::iterator i = m_vertices.begin();
1.2020 - i != m_vertices.end(); ++i)
1.2021 - delete (stored_vertex*)*i;
1.2022 - m_vertices.clear();
1.2023 - m_edges.clear();
1.2024 - }
1.2025 - inline adj_list_impl(vertices_size_type num_vertices) {
1.2026 - for (vertices_size_type i = 0; i < num_vertices; ++i)
1.2027 - add_vertex(static_cast<Derived&>(*this));
1.2028 - }
1.2029 - template <class EdgeIterator>
1.2030 - inline adj_list_impl(vertices_size_type num_vertices,
1.2031 - EdgeIterator first, EdgeIterator last)
1.2032 - {
1.2033 - vertex_descriptor* v = new vertex_descriptor[num_vertices];
1.2034 - for (vertices_size_type i = 0; i < num_vertices; ++i)
1.2035 - v[i] = add_vertex(static_cast<Derived&>(*this));
1.2036 -
1.2037 - while (first != last) {
1.2038 - add_edge(v[(*first).first], v[(*first).second], *this);
1.2039 - ++first;
1.2040 - }
1.2041 - delete [] v;
1.2042 - }
1.2043 - template <class EdgeIterator, class EdgePropertyIterator>
1.2044 - inline adj_list_impl(vertices_size_type num_vertices,
1.2045 - EdgeIterator first, EdgeIterator last,
1.2046 - EdgePropertyIterator ep_iter)
1.2047 - {
1.2048 - vertex_descriptor* v = new vertex_descriptor[num_vertices];
1.2049 - for (vertices_size_type i = 0; i < num_vertices; ++i)
1.2050 - v[i] = add_vertex(static_cast<Derived&>(*this));
1.2051 -
1.2052 - while (first != last) {
1.2053 - add_edge(v[(*first).first], v[(*first).second], *ep_iter, *this);
1.2054 - ++first;
1.2055 - ++ep_iter;
1.2056 - }
1.2057 - delete [] v;
1.2058 - }
1.2059 - ~adj_list_impl() {
1.2060 - for (typename StoredVertexList::iterator i = m_vertices.begin();
1.2061 - i != m_vertices.end(); ++i)
1.2062 - delete (stored_vertex*)*i;
1.2063 - }
1.2064 - // protected:
1.2065 - inline OutEdgeList& out_edge_list(vertex_descriptor v) {
1.2066 - stored_vertex* sv = (stored_vertex*)v;
1.2067 - return sv->m_out_edges;
1.2068 - }
1.2069 - inline const OutEdgeList& out_edge_list(vertex_descriptor v) const {
1.2070 - stored_vertex* sv = (stored_vertex*)v;
1.2071 - return sv->m_out_edges;
1.2072 - }
1.2073 - inline StoredVertexList& vertex_set() { return m_vertices; }
1.2074 - inline const StoredVertexList& vertex_set() const { return m_vertices; }
1.2075 -
1.2076 - inline void copy_impl(const adj_list_impl& x_)
1.2077 - {
1.2078 - const Derived& x = static_cast<const Derived&>(x_);
1.2079 -
1.2080 - // Would be better to have a constant time way to get from
1.2081 - // vertices in x to the corresponding vertices in *this.
1.2082 - std::map<stored_vertex*,stored_vertex*> vertex_map;
1.2083 -
1.2084 - // Copy the stored vertex objects by adding each vertex
1.2085 - // and copying its property object.
1.2086 - vertex_iterator vi, vi_end;
1.2087 - for (tie(vi, vi_end) = vertices(x); vi != vi_end; ++vi) {
1.2088 - stored_vertex* v = (stored_vertex*)add_vertex(*this);
1.2089 - v->m_property = ((stored_vertex*)*vi)->m_property;
1.2090 - vertex_map[(stored_vertex*)*vi] = v;
1.2091 - }
1.2092 - // Copy the edges by adding each edge and copying its
1.2093 - // property object.
1.2094 - edge_iterator ei, ei_end;
1.2095 - for (tie(ei, ei_end) = edges(x); ei != ei_end; ++ei) {
1.2096 - edge_descriptor e;
1.2097 - bool inserted;
1.2098 - vertex_descriptor s = source(*ei,x), t = target(*ei,x);
1.2099 - tie(e, inserted) = add_edge(vertex_map[(stored_vertex*)s],
1.2100 - vertex_map[(stored_vertex*)t], *this);
1.2101 - *((edge_property_type*)e.m_eproperty)
1.2102 - = *((edge_property_type*)(*ei).m_eproperty);
1.2103 - }
1.2104 - }
1.2105 -
1.2106 -
1.2107 - typename Config::EdgeContainer m_edges;
1.2108 - StoredVertexList m_vertices;
1.2109 - };
1.2110 -
1.2111 - // O(1)
1.2112 - template <class Derived, class Config, class Base>
1.2113 - inline typename Config::vertex_descriptor
1.2114 - add_vertex(adj_list_impl<Derived, Config, Base>& g_)
1.2115 - {
1.2116 - Derived& g = static_cast<Derived&>(g_);
1.2117 - typedef typename Config::stored_vertex stored_vertex;
1.2118 - stored_vertex* v = new stored_vertex;
1.2119 - typename Config::StoredVertexList::iterator pos;
1.2120 - bool inserted;
1.2121 - boost::tie(pos,inserted) = boost::graph_detail::push(g.m_vertices, v);
1.2122 - v->m_position = pos;
1.2123 - return v;
1.2124 - }
1.2125 - // O(1)
1.2126 - template <class Derived, class Config, class Base>
1.2127 - inline typename Config::vertex_descriptor
1.2128 - add_vertex(const typename Config::vertex_property_type& p,
1.2129 - adj_list_impl<Derived, Config, Base>& g_)
1.2130 - {
1.2131 - Derived& g = static_cast<Derived&>(g_);
1.2132 - typedef typename Config::stored_vertex stored_vertex;
1.2133 - stored_vertex* v = new stored_vertex(p);
1.2134 - typename Config::StoredVertexList::iterator pos;
1.2135 - bool inserted;
1.2136 - boost::tie(pos,inserted) = boost::graph_detail::push(g.m_vertices, v);
1.2137 - v->m_position = pos;
1.2138 - return v;
1.2139 - }
1.2140 - // O(1)
1.2141 - template <class Derived, class Config, class Base>
1.2142 - inline void remove_vertex(typename Config::vertex_descriptor u,
1.2143 - adj_list_impl<Derived, Config, Base>& g_)
1.2144 - {
1.2145 - typedef typename Config::stored_vertex stored_vertex;
1.2146 - Derived& g = static_cast<Derived&>(g_);
1.2147 - stored_vertex* su = (stored_vertex*)u;
1.2148 - g.m_vertices.erase(su->m_position);
1.2149 - delete su;
1.2150 - }
1.2151 - // O(V)
1.2152 - template <class Derived, class Config, class Base>
1.2153 - inline typename Config::vertex_descriptor
1.2154 - vertex(typename Config::vertices_size_type n,
1.2155 - const adj_list_impl<Derived, Config, Base>& g_)
1.2156 - {
1.2157 - const Derived& g = static_cast<const Derived&>(g_);
1.2158 - typename Config::vertex_iterator i = vertices(g).first;
1.2159 - while (n--) ++i; // std::advance(i, n); (not VC++ portable)
1.2160 - return *i;
1.2161 - }
1.2162 -
1.2163 - //=========================================================================
1.2164 - // Vector-Backbone Adjacency List Implementation
1.2165 -
1.2166 - namespace detail {
1.2167 -
1.2168 - template <class Graph, class vertex_descriptor>
1.2169 - inline void
1.2170 - remove_vertex_dispatch(Graph& g, vertex_descriptor u,
1.2171 - boost::directed_tag)
1.2172 - {
1.2173 - typedef typename Graph::edge_parallel_category edge_parallel_category;
1.2174 - g.m_vertices.erase(g.m_vertices.begin() + u);
1.2175 - vertex_descriptor V = num_vertices(g);
1.2176 - if (u != V) {
1.2177 - for (vertex_descriptor v = 0; v < V; ++v)
1.2178 - reindex_edge_list(g.out_edge_list(v), u, edge_parallel_category());
1.2179 - }
1.2180 - }
1.2181 -
1.2182 - template <class Graph, class vertex_descriptor>
1.2183 - inline void
1.2184 - remove_vertex_dispatch(Graph& g, vertex_descriptor u,
1.2185 - boost::undirected_tag)
1.2186 - {
1.2187 - typedef typename Graph::global_edgelist_selector EdgeListS;
1.2188 - BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
1.2189 -
1.2190 - typedef typename Graph::edge_parallel_category edge_parallel_category;
1.2191 - g.m_vertices.erase(g.m_vertices.begin() + u);
1.2192 - vertex_descriptor V = num_vertices(g);
1.2193 - for (vertex_descriptor v = 0; v < V; ++v)
1.2194 - reindex_edge_list(g.out_edge_list(v), u,
1.2195 - edge_parallel_category());
1.2196 - typedef typename Graph::EdgeContainer Container;
1.2197 - typedef typename Container::iterator Iter;
1.2198 - Iter ei = g.m_edges.begin(), ei_end = g.m_edges.end();
1.2199 - for (; ei != ei_end; ++ei) {
1.2200 - if (ei->m_source > u)
1.2201 - --ei->m_source;
1.2202 - if (ei->m_target > u)
1.2203 - --ei->m_target;
1.2204 - }
1.2205 - }
1.2206 - template <class Graph, class vertex_descriptor>
1.2207 - inline void
1.2208 - remove_vertex_dispatch(Graph& g, vertex_descriptor u,
1.2209 - boost::bidirectional_tag)
1.2210 - {
1.2211 - typedef typename Graph::global_edgelist_selector EdgeListS;
1.2212 - BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
1.2213 -
1.2214 - typedef typename Graph::edge_parallel_category edge_parallel_category;
1.2215 - g.m_vertices.erase(g.m_vertices.begin() + u);
1.2216 - vertex_descriptor V = num_vertices(g);
1.2217 - vertex_descriptor v;
1.2218 - if (u != V) {
1.2219 - for (v = 0; v < V; ++v)
1.2220 - reindex_edge_list(g.out_edge_list(v), u,
1.2221 - edge_parallel_category());
1.2222 - for (v = 0; v < V; ++v)
1.2223 - reindex_edge_list(in_edge_list(g, v), u,
1.2224 - edge_parallel_category());
1.2225 -
1.2226 - typedef typename Graph::EdgeContainer Container;
1.2227 - typedef typename Container::iterator Iter;
1.2228 - Iter ei = g.m_edges.begin(), ei_end = g.m_edges.end();
1.2229 - for (; ei != ei_end; ++ei) {
1.2230 - if (ei->m_source > u)
1.2231 - --ei->m_source;
1.2232 - if (ei->m_target > u)
1.2233 - --ei->m_target;
1.2234 - }
1.2235 - }
1.2236 - }
1.2237 -
1.2238 - template <class EdgeList, class vertex_descriptor>
1.2239 - inline void
1.2240 - reindex_edge_list(EdgeList& el, vertex_descriptor u,
1.2241 - boost::allow_parallel_edge_tag)
1.2242 - {
1.2243 - typename EdgeList::iterator ei = el.begin(), e_end = el.end();
1.2244 - for (; ei != e_end; ++ei)
1.2245 - if ((*ei).get_target() > u)
1.2246 - --(*ei).get_target();
1.2247 - }
1.2248 - template <class EdgeList, class vertex_descriptor>
1.2249 - inline void
1.2250 - reindex_edge_list(EdgeList& el, vertex_descriptor u,
1.2251 - boost::disallow_parallel_edge_tag)
1.2252 - {
1.2253 - typename EdgeList::iterator ei = el.begin(), e_end = el.end();
1.2254 - while (ei != e_end) {
1.2255 - typename EdgeList::value_type ce = *ei;
1.2256 - ++ei;
1.2257 - if (ce.get_target() > u) {
1.2258 - el.erase(ce);
1.2259 - --ce.get_target();
1.2260 - el.insert(ce);
1.2261 - }
1.2262 - }
1.2263 - }
1.2264 - } // namespace detail
1.2265 -
1.2266 - struct vec_adj_list_tag { };
1.2267 -
1.2268 - template <class Graph, class Config, class Base>
1.2269 - class vec_adj_list_impl
1.2270 - : public adj_list_helper<Config, Base>
1.2271 - {
1.2272 - typedef typename Config::OutEdgeList OutEdgeList;
1.2273 - typedef typename Config::InEdgeList InEdgeList;
1.2274 - typedef typename Config::StoredVertexList StoredVertexList;
1.2275 - public:
1.2276 - typedef typename Config::vertex_descriptor vertex_descriptor;
1.2277 - typedef typename Config::edge_descriptor edge_descriptor;
1.2278 - typedef typename Config::out_edge_iterator out_edge_iterator;
1.2279 - typedef typename Config::edge_iterator edge_iterator;
1.2280 - typedef typename Config::directed_category directed_category;
1.2281 - typedef typename Config::vertices_size_type vertices_size_type;
1.2282 - typedef typename Config::edges_size_type edges_size_type;
1.2283 - typedef typename Config::degree_size_type degree_size_type;
1.2284 - typedef typename Config::StoredEdge StoredEdge;
1.2285 - typedef typename Config::stored_vertex stored_vertex;
1.2286 - typedef typename Config::EdgeContainer EdgeContainer;
1.2287 - typedef typename Config::edge_property_type edge_property_type;
1.2288 - typedef vec_adj_list_tag graph_tag;
1.2289 -
1.2290 - static vertex_descriptor null_vertex()
1.2291 - {
1.2292 - return (std::numeric_limits<vertex_descriptor>::max)();
1.2293 - }
1.2294 -
1.2295 - inline vec_adj_list_impl() { }
1.2296 -
1.2297 - inline vec_adj_list_impl(const vec_adj_list_impl& x) {
1.2298 - copy_impl(x);
1.2299 - }
1.2300 - inline vec_adj_list_impl& operator=(const vec_adj_list_impl& x) {
1.2301 - this->clear();
1.2302 - copy_impl(x);
1.2303 - return *this;
1.2304 - }
1.2305 - inline void clear() {
1.2306 - m_vertices.clear();
1.2307 - m_edges.clear();
1.2308 - }
1.2309 -
1.2310 - inline vec_adj_list_impl(vertices_size_type _num_vertices)
1.2311 - : m_vertices(_num_vertices) { }
1.2312 -
1.2313 - template <class EdgeIterator>
1.2314 - inline vec_adj_list_impl(vertices_size_type num_vertices,
1.2315 - EdgeIterator first, EdgeIterator last)
1.2316 - : m_vertices(num_vertices)
1.2317 - {
1.2318 - while (first != last) {
1.2319 - add_edge((*first).first, (*first).second,
1.2320 - static_cast<Graph&>(*this));
1.2321 - ++first;
1.2322 - }
1.2323 - }
1.2324 - template <class EdgeIterator, class EdgePropertyIterator>
1.2325 - inline vec_adj_list_impl(vertices_size_type num_vertices,
1.2326 - EdgeIterator first, EdgeIterator last,
1.2327 - EdgePropertyIterator ep_iter)
1.2328 - : m_vertices(num_vertices)
1.2329 - {
1.2330 - while (first != last) {
1.2331 - add_edge((*first).first, (*first).second, *ep_iter,
1.2332 - static_cast<Graph&>(*this));
1.2333 - ++first;
1.2334 - ++ep_iter;
1.2335 - }
1.2336 - }
1.2337 -
1.2338 - // protected:
1.2339 - inline boost::integer_range<vertex_descriptor> vertex_set() const {
1.2340 - return boost::integer_range<vertex_descriptor>(0, m_vertices.size());
1.2341 - }
1.2342 - inline OutEdgeList& out_edge_list(vertex_descriptor v) {
1.2343 - return m_vertices[v].m_out_edges;
1.2344 - }
1.2345 - inline const OutEdgeList& out_edge_list(vertex_descriptor v) const {
1.2346 - return m_vertices[v].m_out_edges;
1.2347 - }
1.2348 - inline void copy_impl(const vec_adj_list_impl& x_)
1.2349 - {
1.2350 - const Graph& x = static_cast<const Graph&>(x_);
1.2351 - // Copy the stored vertex objects by adding each vertex
1.2352 - // and copying its property object.
1.2353 - for (vertices_size_type i = 0; i < num_vertices(x); ++i) {
1.2354 - vertex_descriptor v = add_vertex(*this);
1.2355 - m_vertices[v].m_property = x.m_vertices[i].m_property;
1.2356 - }
1.2357 - // Copy the edges by adding each edge and copying its
1.2358 - // property object.
1.2359 - edge_iterator ei, ei_end;
1.2360 - for (tie(ei, ei_end) = edges(x); ei != ei_end; ++ei) {
1.2361 - edge_descriptor e;
1.2362 - bool inserted;
1.2363 - tie(e, inserted) = add_edge(source(*ei,x), target(*ei,x) , *this);
1.2364 - *((edge_property_type*)e.m_eproperty)
1.2365 - = *((edge_property_type*)(*ei).m_eproperty);
1.2366 - }
1.2367 - }
1.2368 - typename Config::EdgeContainer m_edges;
1.2369 - StoredVertexList m_vertices;
1.2370 - };
1.2371 - // Had to make these non-members to avoid accidental instantiation
1.2372 - // on SGI MIPSpro C++
1.2373 - template <class G, class C, class B>
1.2374 - inline typename C::InEdgeList&
1.2375 - in_edge_list(vec_adj_list_impl<G,C,B>& g,
1.2376 - typename C::vertex_descriptor v) {
1.2377 - return g.m_vertices[v].m_in_edges;
1.2378 - }
1.2379 - template <class G, class C, class B>
1.2380 - inline const typename C::InEdgeList&
1.2381 - in_edge_list(const vec_adj_list_impl<G,C,B>& g,
1.2382 - typename C::vertex_descriptor v) {
1.2383 - return g.m_vertices[v].m_in_edges;
1.2384 - }
1.2385 -
1.2386 - // O(1)
1.2387 - template <class Graph, class Config, class Base>
1.2388 - inline typename Config::vertex_descriptor
1.2389 - add_vertex(vec_adj_list_impl<Graph, Config, Base>& g_) {
1.2390 - Graph& g = static_cast<Graph&>(g_);
1.2391 - g.m_vertices.resize(g.m_vertices.size() + 1);
1.2392 - return g.m_vertices.size() - 1;
1.2393 - }
1.2394 -
1.2395 - template <class Graph, class Config, class Base>
1.2396 - inline typename Config::vertex_descriptor
1.2397 - add_vertex(const typename Config::vertex_property_type& p,
1.2398 - vec_adj_list_impl<Graph, Config, Base>& g_) {
1.2399 - Graph& g = static_cast<Graph&>(g_);
1.2400 - typedef typename Config::stored_vertex stored_vertex;
1.2401 - g.m_vertices.push_back(stored_vertex(p));
1.2402 - return g.m_vertices.size() - 1;
1.2403 - }
1.2404 -
1.2405 - // Here we override the directed_graph_helper add_edge() function
1.2406 - // so that the number of vertices is automatically changed if
1.2407 - // either u or v is greater than the number of vertices.
1.2408 - template <class Graph, class Config, class Base>
1.2409 - inline std::pair<typename Config::edge_descriptor, bool>
1.2410 - add_edge(typename Config::vertex_descriptor u,
1.2411 - typename Config::vertex_descriptor v,
1.2412 - const typename Config::edge_property_type& p,
1.2413 - vec_adj_list_impl<Graph, Config, Base>& g_)
1.2414 - {
1.2415 - BOOST_USING_STD_MAX();
1.2416 - typename Config::vertex_descriptor x = max BOOST_PREVENT_MACRO_SUBSTITUTION(u, v);
1.2417 - if (x >= num_vertices(g_))
1.2418 - g_.m_vertices.resize(x + 1);
1.2419 - adj_list_helper<Config, Base>& g = g_;
1.2420 - return add_edge(u, v, p, g);
1.2421 - }
1.2422 - template <class Graph, class Config, class Base>
1.2423 - inline std::pair<typename Config::edge_descriptor, bool>
1.2424 - add_edge(typename Config::vertex_descriptor u,
1.2425 - typename Config::vertex_descriptor v,
1.2426 - vec_adj_list_impl<Graph, Config, Base>& g_)
1.2427 - {
1.2428 - typename Config::edge_property_type p;
1.2429 - return add_edge(u, v, p, g_);
1.2430 - }
1.2431 -
1.2432 -
1.2433 - // O(V + E)
1.2434 - template <class Graph, class Config, class Base>
1.2435 - inline void remove_vertex(typename Config::vertex_descriptor v,
1.2436 - vec_adj_list_impl<Graph, Config, Base>& g_)
1.2437 - {
1.2438 - typedef typename Config::directed_category Cat;
1.2439 - Graph& g = static_cast<Graph&>(g_);
1.2440 - detail::remove_vertex_dispatch(g, v, Cat());
1.2441 - }
1.2442 - // O(1)
1.2443 - template <class Graph, class Config, class Base>
1.2444 - inline typename Config::vertex_descriptor
1.2445 - vertex(typename Config::vertices_size_type n,
1.2446 - const vec_adj_list_impl<Graph, Config, Base>&)
1.2447 - {
1.2448 - return n;
1.2449 - }
1.2450 -
1.2451 -
1.2452 - namespace detail {
1.2453 -
1.2454 - //=========================================================================
1.2455 - // Adjacency List Generator
1.2456 -
1.2457 - template <class Graph, class VertexListS, class OutEdgeListS,
1.2458 - class DirectedS, class VertexProperty, class EdgeProperty,
1.2459 - class GraphProperty, class EdgeListS>
1.2460 - struct adj_list_gen
1.2461 - {
1.2462 - typedef typename detail::is_random_access<VertexListS>::type
1.2463 - is_rand_access;
1.2464 - typedef typename has_property<EdgeProperty>::type has_edge_property;
1.2465 - typedef typename DirectedS::is_directed_t DirectedT;
1.2466 - typedef typename DirectedS::is_bidir_t BidirectionalT;
1.2467 -
1.2468 - struct config
1.2469 - {
1.2470 - typedef OutEdgeListS edgelist_selector;
1.2471 - typedef EdgeListS global_edgelist_selector;
1.2472 -
1.2473 - typedef Graph graph_type;
1.2474 - typedef EdgeProperty edge_property_type;
1.2475 - typedef VertexProperty vertex_property_type;
1.2476 - typedef GraphProperty graph_property_type;
1.2477 - typedef std::size_t vertices_size_type;
1.2478 -
1.2479 - typedef adjacency_list_traits<OutEdgeListS, VertexListS, DirectedS>
1.2480 - Traits;
1.2481 -
1.2482 - typedef typename Traits::directed_category directed_category;
1.2483 - typedef typename Traits::edge_parallel_category edge_parallel_category;
1.2484 - typedef typename Traits::vertex_descriptor vertex_descriptor;
1.2485 - typedef typename Traits::edge_descriptor edge_descriptor;
1.2486 -
1.2487 - typedef void* vertex_ptr;
1.2488 -
1.2489 - // need to reorganize this to avoid instantiating stuff
1.2490 - // that doesn't get used -JGS
1.2491 -
1.2492 - // VertexList and vertex_iterator
1.2493 - typedef typename container_gen<VertexListS,
1.2494 - vertex_ptr>::type SeqVertexList;
1.2495 - typedef boost::integer_range<std::size_t> RandVertexList;
1.2496 - typedef typename boost::ct_if_t<is_rand_access,
1.2497 - RandVertexList, SeqVertexList>::type VertexList;
1.2498 -
1.2499 - typedef typename VertexList::iterator vertex_iterator;
1.2500 -
1.2501 - // EdgeContainer and StoredEdge
1.2502 -
1.2503 - typedef typename container_gen<EdgeListS,
1.2504 - list_edge<vertex_descriptor, EdgeProperty> >::type EdgeContainer;
1.2505 -
1.2506 - typedef typename ct_and<DirectedT,
1.2507 - typename ct_not<BidirectionalT>::type >::type on_edge_storage;
1.2508 -
1.2509 - typedef typename boost::ct_if_t<on_edge_storage,
1.2510 - std::size_t, typename EdgeContainer::size_type
1.2511 - >::type edges_size_type;
1.2512 -
1.2513 - typedef typename EdgeContainer::iterator EdgeIter;
1.2514 -
1.2515 - typedef typename detail::is_random_access<EdgeListS>::type is_edge_ra;
1.2516 -
1.2517 - typedef typename boost::ct_if_t<on_edge_storage,
1.2518 - stored_edge_property<vertex_descriptor, EdgeProperty>,
1.2519 - typename boost::ct_if_t<is_edge_ra,
1.2520 - stored_ra_edge_iter<vertex_descriptor, EdgeContainer, EdgeProperty>,
1.2521 - stored_edge_iter<vertex_descriptor, EdgeIter, EdgeProperty>
1.2522 - >::type
1.2523 - >::type StoredEdge;
1.2524 -
1.2525 - // Adjacency Types
1.2526 -
1.2527 - typedef typename container_gen<OutEdgeListS, StoredEdge>::type
1.2528 - OutEdgeList;
1.2529 - typedef typename OutEdgeList::size_type degree_size_type;
1.2530 - typedef typename OutEdgeList::iterator OutEdgeIter;
1.2531 -
1.2532 - typedef boost::detail::iterator_traits<OutEdgeIter> OutEdgeIterTraits;
1.2533 - typedef typename OutEdgeIterTraits::iterator_category OutEdgeIterCat;
1.2534 - typedef typename OutEdgeIterTraits::difference_type OutEdgeIterDiff;
1.2535 -
1.2536 - typedef out_edge_iter<
1.2537 - OutEdgeIter, vertex_descriptor, edge_descriptor, OutEdgeIterDiff
1.2538 - > out_edge_iterator;
1.2539 -
1.2540 - typedef typename adjacency_iterator_generator<graph_type,
1.2541 - vertex_descriptor, out_edge_iterator>::type adjacency_iterator;
1.2542 -
1.2543 - typedef OutEdgeList InEdgeList;
1.2544 - typedef OutEdgeIter InEdgeIter;
1.2545 - typedef OutEdgeIterCat InEdgeIterCat;
1.2546 - typedef OutEdgeIterDiff InEdgeIterDiff;
1.2547 -
1.2548 - typedef in_edge_iter<
1.2549 - InEdgeIter, vertex_descriptor, edge_descriptor, InEdgeIterDiff
1.2550 - > in_edge_iterator;
1.2551 -
1.2552 - typedef typename inv_adjacency_iterator_generator<graph_type,
1.2553 - vertex_descriptor, in_edge_iterator>::type inv_adjacency_iterator;
1.2554 -
1.2555 - // Edge Iterator
1.2556 -
1.2557 - typedef boost::detail::iterator_traits<EdgeIter> EdgeIterTraits;
1.2558 - typedef typename EdgeIterTraits::iterator_category EdgeIterCat;
1.2559 - typedef typename EdgeIterTraits::difference_type EdgeIterDiff;
1.2560 -
1.2561 - typedef undirected_edge_iter<
1.2562 - EdgeIter
1.2563 - , edge_descriptor
1.2564 - , EdgeIterDiff
1.2565 - > UndirectedEdgeIter; // also used for bidirectional
1.2566 -
1.2567 - typedef adj_list_edge_iterator<vertex_iterator, out_edge_iterator,
1.2568 - graph_type> DirectedEdgeIter;
1.2569 -
1.2570 - typedef typename boost::ct_if_t<on_edge_storage,
1.2571 - DirectedEdgeIter, UndirectedEdgeIter>::type edge_iterator;
1.2572 -
1.2573 - // stored_vertex and StoredVertexList
1.2574 - typedef typename container_gen<VertexListS, vertex_ptr>::type
1.2575 - SeqStoredVertexList;
1.2576 - struct seq_stored_vertex {
1.2577 - seq_stored_vertex() { }
1.2578 - seq_stored_vertex(const VertexProperty& p) : m_property(p) { }
1.2579 - OutEdgeList m_out_edges;
1.2580 - VertexProperty m_property;
1.2581 - typename SeqStoredVertexList::iterator m_position;
1.2582 - };
1.2583 - struct bidir_seq_stored_vertex {
1.2584 - bidir_seq_stored_vertex() { }
1.2585 - bidir_seq_stored_vertex(const VertexProperty& p) : m_property(p) { }
1.2586 - OutEdgeList m_out_edges;
1.2587 - InEdgeList m_in_edges;
1.2588 - VertexProperty m_property;
1.2589 - typename SeqStoredVertexList::iterator m_position;
1.2590 - };
1.2591 - struct rand_stored_vertex {
1.2592 - rand_stored_vertex() { }
1.2593 - rand_stored_vertex(const VertexProperty& p) : m_property(p) { }
1.2594 - OutEdgeList m_out_edges;
1.2595 - VertexProperty m_property;
1.2596 - };
1.2597 - struct bidir_rand_stored_vertex {
1.2598 - bidir_rand_stored_vertex() { }
1.2599 - bidir_rand_stored_vertex(const VertexProperty& p) : m_property(p) { }
1.2600 - OutEdgeList m_out_edges;
1.2601 - InEdgeList m_in_edges;
1.2602 - VertexProperty m_property;
1.2603 - };
1.2604 - typedef typename boost::ct_if_t<is_rand_access,
1.2605 - typename boost::ct_if_t<BidirectionalT,
1.2606 - bidir_rand_stored_vertex, rand_stored_vertex>::type,
1.2607 - typename boost::ct_if_t<BidirectionalT,
1.2608 - bidir_seq_stored_vertex, seq_stored_vertex>::type
1.2609 - >::type StoredVertex;
1.2610 - struct stored_vertex : public StoredVertex {
1.2611 - stored_vertex() { }
1.2612 - stored_vertex(const VertexProperty& p) : StoredVertex(p) { }
1.2613 - };
1.2614 -
1.2615 - typedef typename container_gen<VertexListS, stored_vertex>::type
1.2616 - RandStoredVertexList;
1.2617 - typedef typename boost::ct_if_t< is_rand_access,
1.2618 - RandStoredVertexList, SeqStoredVertexList>::type StoredVertexList;
1.2619 - }; // end of config
1.2620 -
1.2621 -
1.2622 - typedef typename boost::ct_if_t<BidirectionalT,
1.2623 - bidirectional_graph_helper_with_property<config>,
1.2624 - typename boost::ct_if_t<DirectedT,
1.2625 - directed_graph_helper<config>,
1.2626 - undirected_graph_helper<config>
1.2627 - >::type
1.2628 - >::type DirectedHelper;
1.2629 -
1.2630 - typedef typename boost::ct_if_t<is_rand_access,
1.2631 - vec_adj_list_impl<Graph, config, DirectedHelper>,
1.2632 - adj_list_impl<Graph, config, DirectedHelper>
1.2633 - >::type type;
1.2634 -
1.2635 + struct is_random_access<vecS> {
1.2636 + enum { value = true };
1.2637 + typedef true_type type;
1.2638 };
1.2639
1.2640 } // namespace detail
1.2641
1.2642 - //=========================================================================
1.2643 - // Vertex Property Maps
1.2644
1.2645 - template <class Graph, class ValueType, class Reference, class Tag>
1.2646 - struct adj_list_vertex_property_map
1.2647 - : public boost::put_get_helper<
1.2648 - Reference,
1.2649 - adj_list_vertex_property_map<Graph, ValueType, Reference, Tag>
1.2650 - >
1.2651 - {
1.2652 - typedef typename Graph::stored_vertex StoredVertex;
1.2653 - typedef ValueType value_type;
1.2654 - typedef Reference reference;
1.2655 - typedef typename Graph::vertex_descriptor key_type;
1.2656 - typedef boost::lvalue_property_map_tag category;
1.2657 - inline adj_list_vertex_property_map() { }
1.2658 - inline adj_list_vertex_property_map(const Graph*) { }
1.2659 - inline Reference operator[](key_type v) const {
1.2660 - StoredVertex* sv = (StoredVertex*)v;
1.2661 - return get_property_value(sv->m_property, Tag());
1.2662 - }
1.2663 - inline Reference operator()(key_type v) const {
1.2664 - return this->operator[](v);
1.2665 - }
1.2666 - };
1.2667
1.2668 - template <class Graph, class Property, class PropRef>
1.2669 - struct adj_list_vertex_all_properties_map
1.2670 - : public boost::put_get_helper<PropRef,
1.2671 - adj_list_vertex_all_properties_map<Graph, Property, PropRef>
1.2672 - >
1.2673 - {
1.2674 - typedef typename Graph::stored_vertex StoredVertex;
1.2675 - typedef Property value_type;
1.2676 - typedef PropRef reference;
1.2677 - typedef typename Graph::vertex_descriptor key_type;
1.2678 - typedef boost::lvalue_property_map_tag category;
1.2679 - inline adj_list_vertex_all_properties_map() { }
1.2680 - inline adj_list_vertex_all_properties_map(const Graph*) { }
1.2681 - inline PropRef operator[](key_type v) const {
1.2682 - StoredVertex* sv = (StoredVertex*)v;
1.2683 - return sv->m_property;
1.2684 - }
1.2685 - inline PropRef operator()(key_type v) const {
1.2686 - return this->operator[](v);
1.2687 - }
1.2688 - };
1.2689 + //===========================================================================
1.2690 + // The adjacency_list_traits class, which provides a way to access
1.2691 + // some of the associated types of an adjacency_list type without
1.2692 + // having to first create the adjacency_list type. This is useful
1.2693 + // when trying to create interior vertex or edge properties who's
1.2694 + // value type is a vertex or edge descriptor.
1.2695
1.2696 - template <class Graph, class GraphPtr, class ValueType, class Reference,
1.2697 - class Tag>
1.2698 - struct vec_adj_list_vertex_property_map
1.2699 - : public boost::put_get_helper<
1.2700 - Reference,
1.2701 - vec_adj_list_vertex_property_map<Graph,GraphPtr,ValueType,Reference,
1.2702 - Tag>
1.2703 - >
1.2704 - {
1.2705 - typedef ValueType value_type;
1.2706 - typedef Reference reference;
1.2707 - typedef typename boost::graph_traits<Graph>::vertex_descriptor key_type;
1.2708 - typedef boost::lvalue_property_map_tag category;
1.2709 - vec_adj_list_vertex_property_map() { }
1.2710 - vec_adj_list_vertex_property_map(GraphPtr g) : m_g(g) { }
1.2711 - inline Reference operator[](key_type v) const {
1.2712 - return get_property_value(m_g->m_vertices[v].m_property, Tag());
1.2713 - }
1.2714 - inline Reference operator()(key_type v) const {
1.2715 - return this->operator[](v);
1.2716 - }
1.2717 - GraphPtr m_g;
1.2718 - };
1.2719 + template <class OutEdgeListS = vecS,
1.2720 + class VertexListS = vecS,
1.2721 + class DirectedS = directedS>
1.2722 + struct adjacency_list_traits
1.2723 + {
1.2724 + typedef typename detail::is_random_access<VertexListS>::type
1.2725 + is_rand_access;
1.2726 + typedef typename DirectedS::is_bidir_t is_bidir;
1.2727 + typedef typename DirectedS::is_directed_t is_directed;
1.2728
1.2729 - template <class Graph, class GraphPtr, class Property, class PropertyRef>
1.2730 - struct vec_adj_list_vertex_all_properties_map
1.2731 - : public boost::put_get_helper<PropertyRef,
1.2732 - vec_adj_list_vertex_all_properties_map<Graph,GraphPtr,Property,
1.2733 - PropertyRef>
1.2734 - >
1.2735 - {
1.2736 - typedef Property value_type;
1.2737 - typedef PropertyRef reference;
1.2738 - typedef typename boost::graph_traits<Graph>::vertex_descriptor key_type;
1.2739 - typedef boost::lvalue_property_map_tag category;
1.2740 - vec_adj_list_vertex_all_properties_map() { }
1.2741 - vec_adj_list_vertex_all_properties_map(GraphPtr g) : m_g(g) { }
1.2742 - inline PropertyRef operator[](key_type v) const {
1.2743 - return m_g->m_vertices[v].m_property;
1.2744 - }
1.2745 - inline PropertyRef operator()(key_type v) const {
1.2746 - return this->operator[](v);
1.2747 - }
1.2748 - GraphPtr m_g;
1.2749 - };
1.2750 + typedef typename boost::ct_if_t<is_bidir,
1.2751 + bidirectional_tag,
1.2752 + typename boost::ct_if_t<is_directed,
1.2753 + directed_tag, undirected_tag
1.2754 + >::type
1.2755 + >::type directed_category;
1.2756
1.2757 - struct adj_list_any_vertex_pa {
1.2758 - template <class Tag, class Graph, class Property>
1.2759 - struct bind_ {
1.2760 - typedef typename property_value<Property, Tag>::type value_type;
1.2761 - typedef value_type& reference;
1.2762 - typedef const value_type& const_reference;
1.2763 + typedef typename parallel_edge_traits<OutEdgeListS>::type
1.2764 + edge_parallel_category;
1.2765
1.2766 - typedef adj_list_vertex_property_map
1.2767 - <Graph, value_type, reference, Tag> type;
1.2768 - typedef adj_list_vertex_property_map
1.2769 - <Graph, value_type, const_reference, Tag> const_type;
1.2770 - };
1.2771 - };
1.2772 - struct adj_list_all_vertex_pa {
1.2773 - template <class Tag, class Graph, class Property>
1.2774 - struct bind_ {
1.2775 - typedef typename Graph::vertex_descriptor Vertex;
1.2776 - typedef adj_list_vertex_all_properties_map<Graph,Property,
1.2777 - Property&> type;
1.2778 - typedef adj_list_vertex_all_properties_map<Graph,Property,
1.2779 - const Property&> const_type;
1.2780 - };
1.2781 - };
1.2782 -
1.2783 - template <class Property, class Vertex>
1.2784 - struct vec_adj_list_vertex_id_map
1.2785 - : public boost::put_get_helper<
1.2786 - Vertex, vec_adj_list_vertex_id_map<Property, Vertex>
1.2787 - >
1.2788 - {
1.2789 - typedef Vertex value_type;
1.2790 - typedef Vertex key_type;
1.2791 - typedef Vertex reference;
1.2792 - typedef boost::readable_property_map_tag category;
1.2793 - inline vec_adj_list_vertex_id_map() { }
1.2794 - template <class Graph>
1.2795 - inline vec_adj_list_vertex_id_map(const Graph&) { }
1.2796 - inline value_type operator[](key_type v) const { return v; }
1.2797 - inline value_type operator()(key_type v) const { return v; }
1.2798 - };
1.2799 -
1.2800 - struct vec_adj_list_any_vertex_pa {
1.2801 - template <class Tag, class Graph, class Property>
1.2802 - struct bind_ {
1.2803 - typedef typename property_value<Property, Tag>::type value_type;
1.2804 - typedef value_type& reference;
1.2805 - typedef const value_type& const_reference;
1.2806 -
1.2807 - typedef vec_adj_list_vertex_property_map
1.2808 - <Graph, Graph*, value_type, reference, Tag> type;
1.2809 - typedef vec_adj_list_vertex_property_map
1.2810 - <Graph, const Graph*, value_type, const_reference, Tag> const_type;
1.2811 - };
1.2812 - };
1.2813 - struct vec_adj_list_id_vertex_pa {
1.2814 - template <class Tag, class Graph, class Property>
1.2815 - struct bind_ {
1.2816 - typedef typename Graph::vertex_descriptor Vertex;
1.2817 - typedef vec_adj_list_vertex_id_map<Property, Vertex> type;
1.2818 - typedef vec_adj_list_vertex_id_map<Property, Vertex> const_type;
1.2819 - };
1.2820 - };
1.2821 - struct vec_adj_list_all_vertex_pa {
1.2822 - template <class Tag, class Graph, class Property>
1.2823 - struct bind_ {
1.2824 - typedef typename Graph::vertex_descriptor Vertex;
1.2825 - typedef vec_adj_list_vertex_all_properties_map
1.2826 - <Graph, Graph*, Property, Property&> type;
1.2827 - typedef vec_adj_list_vertex_all_properties_map
1.2828 - <Graph, const Graph*, Property, const Property&> const_type;
1.2829 - };
1.2830 - };
1.2831 - namespace detail {
1.2832 - template <class Tag>
1.2833 - struct adj_list_choose_vertex_pa_helper {
1.2834 - typedef adj_list_any_vertex_pa type;
1.2835 - };
1.2836 - template <>
1.2837 - struct adj_list_choose_vertex_pa_helper<vertex_all_t> {
1.2838 - typedef adj_list_all_vertex_pa type;
1.2839 - };
1.2840 - template <class Tag, class Graph, class Property>
1.2841 - struct adj_list_choose_vertex_pa {
1.2842 - typedef typename adj_list_choose_vertex_pa_helper<Tag>::type Helper;
1.2843 - typedef typename Helper::template bind_<Tag,Graph,Property> Bind;
1.2844 - typedef typename Bind::type type;
1.2845 - typedef typename Bind::const_type const_type;
1.2846 - };
1.2847 -
1.2848 -
1.2849 - template <class Tag>
1.2850 - struct vec_adj_list_choose_vertex_pa_helper {
1.2851 - typedef vec_adj_list_any_vertex_pa type;
1.2852 - };
1.2853 - template <>
1.2854 - struct vec_adj_list_choose_vertex_pa_helper<vertex_index_t> {
1.2855 - typedef vec_adj_list_id_vertex_pa type;
1.2856 - };
1.2857 - template <>
1.2858 - struct vec_adj_list_choose_vertex_pa_helper<vertex_all_t> {
1.2859 - typedef vec_adj_list_all_vertex_pa type;
1.2860 - };
1.2861 - template <class Tag, class Graph, class Property>
1.2862 - struct vec_adj_list_choose_vertex_pa {
1.2863 - typedef typename vec_adj_list_choose_vertex_pa_helper<Tag>::type Helper;
1.2864 - typedef typename Helper::template bind_<Tag,Graph,Property> Bind;
1.2865 - typedef typename Bind::type type;
1.2866 - typedef typename Bind::const_type const_type;
1.2867 - };
1.2868 - } // namespace detail
1.2869 -
1.2870 - //=========================================================================
1.2871 - // Edge Property Map
1.2872 -
1.2873 - template <class Directed, class Value, class Ref, class Vertex,
1.2874 - class Property, class Tag>
1.2875 - struct adj_list_edge_property_map
1.2876 - : public put_get_helper<
1.2877 - Ref,
1.2878 - adj_list_edge_property_map<Directed, Value, Ref, Vertex, Property,
1.2879 - Tag>
1.2880 - >
1.2881 - {
1.2882 - typedef Value value_type;
1.2883 - typedef Ref reference;
1.2884 - typedef detail::edge_desc_impl<Directed, Vertex> key_type;
1.2885 - typedef boost::lvalue_property_map_tag category;
1.2886 - inline Ref operator[](key_type e) const {
1.2887 - Property& p = *(Property*)e.get_property();
1.2888 - return get_property_value(p, Tag());
1.2889 - }
1.2890 - inline Ref operator()(key_type e) const {
1.2891 - return this->operator[](e);
1.2892 - }
1.2893 - };
1.2894 -
1.2895 - template <class Directed, class Property, class PropRef, class PropPtr,
1.2896 - class Vertex>
1.2897 - struct adj_list_edge_all_properties_map
1.2898 - : public put_get_helper<PropRef,
1.2899 - adj_list_edge_all_properties_map<Directed, Property, PropRef,
1.2900 - PropPtr, Vertex>
1.2901 - >
1.2902 - {
1.2903 - typedef Property value_type;
1.2904 - typedef PropRef reference;
1.2905 - typedef detail::edge_desc_impl<Directed, Vertex> key_type;
1.2906 - typedef boost::lvalue_property_map_tag category;
1.2907 - inline PropRef operator[](key_type e) const {
1.2908 - return *(PropPtr)e.get_property();
1.2909 - }
1.2910 - inline PropRef operator()(key_type e) const {
1.2911 - return this->operator[](e);
1.2912 - }
1.2913 - };
1.2914 -
1.2915 - // Edge Property Maps
1.2916 -
1.2917 - namespace detail {
1.2918 - struct adj_list_any_edge_pmap {
1.2919 - template <class Graph, class Property, class Tag>
1.2920 - struct bind_ {
1.2921 - typedef typename property_value<Property,Tag>::type value_type;
1.2922 - typedef value_type& reference;
1.2923 - typedef const value_type& const_reference;
1.2924 -
1.2925 - typedef adj_list_edge_property_map
1.2926 - <typename Graph::directed_category, value_type, reference,
1.2927 - typename Graph::vertex_descriptor,Property,Tag> type;
1.2928 - typedef adj_list_edge_property_map
1.2929 - <typename Graph::directed_category, value_type, const_reference,
1.2930 - typename Graph::vertex_descriptor,const Property, Tag> const_type;
1.2931 - };
1.2932 - };
1.2933 - struct adj_list_all_edge_pmap {
1.2934 - template <class Graph, class Property, class Tag>
1.2935 - struct bind_ {
1.2936 - typedef adj_list_edge_all_properties_map
1.2937 - <typename Graph::directed_category, Property, Property&, Property*,
1.2938 - typename Graph::vertex_descriptor> type;
1.2939 - typedef adj_list_edge_all_properties_map
1.2940 - <typename Graph::directed_category, Property, const Property&,
1.2941 - const Property*, typename Graph::vertex_descriptor> const_type;
1.2942 - };
1.2943 - };
1.2944 -
1.2945 - template <class Tag>
1.2946 - struct adj_list_choose_edge_pmap_helper {
1.2947 - typedef adj_list_any_edge_pmap type;
1.2948 - };
1.2949 - template <>
1.2950 - struct adj_list_choose_edge_pmap_helper<edge_all_t> {
1.2951 - typedef adj_list_all_edge_pmap type;
1.2952 - };
1.2953 - template <class Tag, class Graph, class Property>
1.2954 - struct adj_list_choose_edge_pmap {
1.2955 - typedef typename adj_list_choose_edge_pmap_helper<Tag>::type Helper;
1.2956 - typedef typename Helper::template bind_<Graph,Property,Tag> Bind;
1.2957 - typedef typename Bind::type type;
1.2958 - typedef typename Bind::const_type const_type;
1.2959 - };
1.2960 - struct adj_list_edge_property_selector {
1.2961 - template <class Graph, class Property, class Tag>
1.2962 - struct bind_ {
1.2963 - typedef adj_list_choose_edge_pmap<Tag,Graph,Property> Choice;
1.2964 - typedef typename Choice::type type;
1.2965 - typedef typename Choice::const_type const_type;
1.2966 - };
1.2967 - };
1.2968 - } // namespace detail
1.2969 -
1.2970 - template <>
1.2971 - struct edge_property_selector<adj_list_tag> {
1.2972 - typedef detail::adj_list_edge_property_selector type;
1.2973 - };
1.2974 - template <>
1.2975 - struct edge_property_selector<vec_adj_list_tag> {
1.2976 - typedef detail::adj_list_edge_property_selector type;
1.2977 - };
1.2978 -
1.2979 - // Vertex Property Maps
1.2980 -
1.2981 - struct adj_list_vertex_property_selector {
1.2982 - template <class Graph, class Property, class Tag>
1.2983 - struct bind_ {
1.2984 - typedef detail::adj_list_choose_vertex_pa<Tag,Graph,Property> Choice;
1.2985 - typedef typename Choice::type type;
1.2986 - typedef typename Choice::const_type const_type;
1.2987 - };
1.2988 - };
1.2989 - template <>
1.2990 - struct vertex_property_selector<adj_list_tag> {
1.2991 - typedef adj_list_vertex_property_selector type;
1.2992 - };
1.2993 -
1.2994 - struct vec_adj_list_vertex_property_selector {
1.2995 - template <class Graph, class Property, class Tag>
1.2996 - struct bind_ {
1.2997 - typedef detail::vec_adj_list_choose_vertex_pa<Tag,Graph,Property> Choice;
1.2998 - typedef typename Choice::type type;
1.2999 - typedef typename Choice::const_type const_type;
1.3000 - };
1.3001 - };
1.3002 - template <>
1.3003 - struct vertex_property_selector<vec_adj_list_tag> {
1.3004 - typedef vec_adj_list_vertex_property_selector type;
1.3005 + typedef void* vertex_ptr;
1.3006 + typedef typename boost::ct_if_t<is_rand_access,
1.3007 + std::size_t, vertex_ptr>::type vertex_descriptor;
1.3008 + typedef detail::edge_desc_impl<directed_category, vertex_descriptor>
1.3009 + edge_descriptor;
1.3010 };
1.3011
1.3012 } // namespace boost
1.3013
1.3014 -#if !defined(BOOST_NO_HASH) && !defined(BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION)
1.3015 -namespace BOOST_STD_EXTENSION_NAMESPACE {
1.3016 +#include <boost/graph/detail/adjacency_list.hpp>
1.3017
1.3018 - #if BOOST_WORKAROUND( _STLPORT_VERSION, >= 0x500 )
1.3019 - // STLport 5 already defines a hash<void*> specialization.
1.3020 - #else
1.3021 - template <>
1.3022 - struct hash< void* > // Need this when vertex_descriptor=void*
1.3023 +namespace boost {
1.3024 +
1.3025 + //===========================================================================
1.3026 + // The adjacency_list class.
1.3027 + //
1.3028 +
1.3029 + template <class OutEdgeListS = vecS, // a Sequence or an AssociativeContainer
1.3030 + class VertexListS = vecS, // a Sequence or a RandomAccessContainer
1.3031 + class DirectedS = directedS,
1.3032 + class VertexProperty = no_property,
1.3033 + class EdgeProperty = no_property,
1.3034 + class GraphProperty = no_property,
1.3035 + class EdgeListS = listS>
1.3036 + class adjacency_list
1.3037 + : public detail::adj_list_gen<
1.3038 + adjacency_list<OutEdgeListS,VertexListS,DirectedS,
1.3039 + VertexProperty,EdgeProperty,GraphProperty,EdgeListS>,
1.3040 + VertexListS, OutEdgeListS, DirectedS,
1.3041 +#if !defined(BOOST_GRAPH_NO_BUNDLED_PROPERTIES)
1.3042 + typename detail::retag_property_list<vertex_bundle_t,
1.3043 + VertexProperty>::type,
1.3044 + typename detail::retag_property_list<edge_bundle_t, EdgeProperty>::type,
1.3045 +#else
1.3046 + VertexProperty, EdgeProperty,
1.3047 +#endif
1.3048 + GraphProperty, EdgeListS>::type
1.3049 {
1.3050 - std::size_t
1.3051 - operator()(void* v) const { return (std::size_t)v; }
1.3052 - };
1.3053 - #endif
1.3054 +#if !defined(BOOST_GRAPH_NO_BUNDLED_PROPERTIES)
1.3055 + typedef typename detail::retag_property_list<vertex_bundle_t,
1.3056 + VertexProperty>::retagged
1.3057 + maybe_vertex_bundled;
1.3058
1.3059 - template <typename V>
1.3060 - struct hash< boost::detail::stored_edge<V> >
1.3061 - {
1.3062 - std::size_t
1.3063 - operator()(const boost::detail::stored_edge<V>& e) const
1.3064 - {
1.3065 - return hash<V>()(e.m_target);
1.3066 + typedef typename detail::retag_property_list<edge_bundle_t,
1.3067 + EdgeProperty>::retagged
1.3068 + maybe_edge_bundled;
1.3069 +#endif
1.3070 +
1.3071 + public:
1.3072 +#if !defined(BOOST_GRAPH_NO_BUNDLED_PROPERTIES)
1.3073 + typedef typename detail::retag_property_list<vertex_bundle_t,
1.3074 + VertexProperty>::type
1.3075 + vertex_property_type;
1.3076 + typedef typename detail::retag_property_list<edge_bundle_t,
1.3077 + EdgeProperty>::type
1.3078 + edge_property_type;
1.3079 +
1.3080 + // The types that are actually bundled
1.3081 + typedef typename ct_if<(is_same<maybe_vertex_bundled, no_property>::value),
1.3082 + no_vertex_bundle,
1.3083 + maybe_vertex_bundled>::type vertex_bundled;
1.3084 + typedef typename ct_if<(is_same<maybe_edge_bundled, no_property>::value),
1.3085 + no_edge_bundle,
1.3086 + maybe_edge_bundled>::type edge_bundled;
1.3087 +#else
1.3088 + typedef VertexProperty vertex_property_type;
1.3089 + typedef EdgeProperty edge_property_type;
1.3090 + typedef no_vertex_bundle vertex_bundled;
1.3091 + typedef no_edge_bundle edge_bundled;
1.3092 +#endif
1.3093 +
1.3094 + private:
1.3095 + typedef adjacency_list self;
1.3096 + typedef typename detail::adj_list_gen<
1.3097 + self, VertexListS, OutEdgeListS, DirectedS,
1.3098 + vertex_property_type, edge_property_type, GraphProperty, EdgeListS
1.3099 + >::type Base;
1.3100 +
1.3101 + public:
1.3102 + typedef typename Base::stored_vertex stored_vertex;
1.3103 + typedef typename Base::vertices_size_type vertices_size_type;
1.3104 + typedef typename Base::edges_size_type edges_size_type;
1.3105 + typedef typename Base::degree_size_type degree_size_type;
1.3106 + typedef typename Base::vertex_descriptor vertex_descriptor;
1.3107 + typedef typename Base::edge_descriptor edge_descriptor;
1.3108 + typedef OutEdgeListS out_edge_list_selector;
1.3109 + typedef VertexListS vertex_list_selector;
1.3110 + typedef DirectedS directed_selector;
1.3111 + typedef EdgeListS edge_list_selector;
1.3112 +
1.3113 + typedef GraphProperty graph_property_type;
1.3114 +
1.3115 + inline adjacency_list(const GraphProperty& p = GraphProperty())
1.3116 + : m_property(p) { }
1.3117 +
1.3118 + inline adjacency_list(const adjacency_list& x)
1.3119 + : Base(x), m_property(x.m_property) { }
1.3120 +
1.3121 + inline adjacency_list& operator=(const adjacency_list& x) {
1.3122 + // TBD: probably should give the strong guarantee
1.3123 + if (&x != this) {
1.3124 + Base::operator=(x);
1.3125 + m_property = x.m_property;
1.3126 + }
1.3127 + return *this;
1.3128 }
1.3129 +
1.3130 + // Required by Mutable Graph
1.3131 + inline adjacency_list(vertices_size_type num_vertices,
1.3132 + const GraphProperty& p = GraphProperty())
1.3133 + : Base(num_vertices), m_property(p) { }
1.3134 +
1.3135 +#if !defined(BOOST_MSVC) || BOOST_MSVC >= 1300
1.3136 + // Required by Iterator Constructible Graph
1.3137 + template <class EdgeIterator>
1.3138 + inline adjacency_list(EdgeIterator first, EdgeIterator last,
1.3139 + vertices_size_type n,
1.3140 + edges_size_type = 0,
1.3141 + const GraphProperty& p = GraphProperty())
1.3142 + : Base(n, first, last), m_property(p) { }
1.3143 +
1.3144 + template <class EdgeIterator, class EdgePropertyIterator>
1.3145 + inline adjacency_list(EdgeIterator first, EdgeIterator last,
1.3146 + EdgePropertyIterator ep_iter,
1.3147 + vertices_size_type n,
1.3148 + edges_size_type = 0,
1.3149 + const GraphProperty& p = GraphProperty())
1.3150 + : Base(n, first, last, ep_iter), m_property(p) { }
1.3151 +#endif
1.3152 +
1.3153 + void swap(adjacency_list& x) {
1.3154 + // Is there a more efficient way to do this?
1.3155 + adjacency_list tmp(x);
1.3156 + x = *this;
1.3157 + *this = tmp;
1.3158 + }
1.3159 +
1.3160 +#ifndef BOOST_GRAPH_NO_BUNDLED_PROPERTIES
1.3161 + // Directly access a vertex or edge bundle
1.3162 + vertex_bundled& operator[](vertex_descriptor v)
1.3163 + { return get(vertex_bundle, *this)[v]; }
1.3164 +
1.3165 + const vertex_bundled& operator[](vertex_descriptor v) const
1.3166 + { return get(vertex_bundle, *this)[v]; }
1.3167 +
1.3168 + edge_bundled& operator[](edge_descriptor e)
1.3169 + { return get(edge_bundle, *this)[e]; }
1.3170 +
1.3171 + const edge_bundled& operator[](edge_descriptor e) const
1.3172 + { return get(edge_bundle, *this)[e]; }
1.3173 +#endif
1.3174 +
1.3175 + // protected: (would be protected if friends were more portable)
1.3176 + GraphProperty m_property;
1.3177 };
1.3178
1.3179 - template <typename V, typename P>
1.3180 - struct hash< boost::detail::stored_edge_property <V,P> >
1.3181 + template <class OEL, class VL, class DirS, class VP,class EP, class GP,
1.3182 + class EL, class Tag, class Value>
1.3183 + inline void
1.3184 + set_property(adjacency_list<OEL,VL,DirS,VP,EP,GP,EL>& g, Tag,
1.3185 + const Value& value) {
1.3186 + get_property_value(g.m_property, Tag()) = value;;
1.3187 + }
1.3188 +
1.3189 + template <class OEL, class VL, class DirS, class VP, class EP, class GP,
1.3190 + class Tag, class EL>
1.3191 + inline
1.3192 + typename graph_property<adjacency_list<OEL,VL,DirS,VP,EP,GP,EL>, Tag>::type&
1.3193 + get_property(adjacency_list<OEL,VL,DirS,VP,EP,GP,EL>& g, Tag) {
1.3194 + return get_property_value(g.m_property, Tag());
1.3195 + }
1.3196 +
1.3197 + template <class OEL, class VL, class DirS, class VP, class EP, class GP,
1.3198 + class Tag, class EL>
1.3199 + inline
1.3200 + const
1.3201 + typename graph_property<adjacency_list<OEL,VL,DirS,VP,EP,GP,EL>, Tag>::type&
1.3202 + get_property(const adjacency_list<OEL,VL,DirS,VP,EP,GP,EL>& g, Tag) {
1.3203 + return get_property_value(g.m_property, Tag());
1.3204 + }
1.3205 +
1.3206 + // dwa 09/25/00 - needed to be more explicit so reverse_graph would work.
1.3207 + template <class Directed, class Vertex,
1.3208 + class OutEdgeListS,
1.3209 + class VertexListS,
1.3210 + class DirectedS,
1.3211 + class VertexProperty,
1.3212 + class EdgeProperty,
1.3213 + class GraphProperty, class EdgeListS>
1.3214 + inline Vertex
1.3215 + source(const detail::edge_base<Directed,Vertex>& e,
1.3216 + const adjacency_list<OutEdgeListS, VertexListS, DirectedS,
1.3217 + VertexProperty, EdgeProperty, GraphProperty, EdgeListS>&)
1.3218 {
1.3219 - std::size_t
1.3220 - operator()(const boost::detail::stored_edge_property<V,P>& e) const
1.3221 - {
1.3222 - return hash<V>()(e.m_target);
1.3223 - }
1.3224 - };
1.3225 + return e.m_source;
1.3226 + }
1.3227
1.3228 - template <typename V, typename I, typename P>
1.3229 - struct hash< boost::detail::stored_edge_iter<V,I, P> >
1.3230 + template <class Directed, class Vertex, class OutEdgeListS,
1.3231 + class VertexListS, class DirectedS, class VertexProperty,
1.3232 + class EdgeProperty, class GraphProperty, class EdgeListS>
1.3233 + inline Vertex
1.3234 + target(const detail::edge_base<Directed,Vertex>& e,
1.3235 + const adjacency_list<OutEdgeListS, VertexListS, DirectedS,
1.3236 + VertexProperty, EdgeProperty, GraphProperty, EdgeListS>&)
1.3237 {
1.3238 - std::size_t
1.3239 - operator()(const boost::detail::stored_edge_iter<V,I,P>& e) const
1.3240 - {
1.3241 - return hash<V>()(e.m_target);
1.3242 - }
1.3243 - };
1.3244 + return e.m_target;
1.3245 + }
1.3246
1.3247 -}
1.3248 + // Support for bundled properties
1.3249 +#ifndef BOOST_GRAPH_NO_BUNDLED_PROPERTIES
1.3250 + template<typename OutEdgeListS, typename VertexListS, typename DirectedS, typename VertexProperty,
1.3251 + typename EdgeProperty, typename GraphProperty, typename EdgeListS, typename T, typename Bundle>
1.3252 + inline
1.3253 + typename property_map<adjacency_list<OutEdgeListS, VertexListS, DirectedS, VertexProperty, EdgeProperty,
1.3254 + GraphProperty, EdgeListS>, T Bundle::*>::type
1.3255 + get(T Bundle::* p, adjacency_list<OutEdgeListS, VertexListS, DirectedS, VertexProperty, EdgeProperty,
1.3256 + GraphProperty, EdgeListS>& g)
1.3257 + {
1.3258 + typedef typename property_map<adjacency_list<OutEdgeListS, VertexListS, DirectedS, VertexProperty,
1.3259 + EdgeProperty, GraphProperty, EdgeListS>, T Bundle::*>::type
1.3260 + result_type;
1.3261 + return result_type(&g, p);
1.3262 + }
1.3263 +
1.3264 + template<typename OutEdgeListS, typename VertexListS, typename DirectedS, typename VertexProperty,
1.3265 + typename EdgeProperty, typename GraphProperty, typename EdgeListS, typename T, typename Bundle>
1.3266 + inline
1.3267 + typename property_map<adjacency_list<OutEdgeListS, VertexListS, DirectedS, VertexProperty, EdgeProperty,
1.3268 + GraphProperty, EdgeListS>, T Bundle::*>::const_type
1.3269 + get(T Bundle::* p, adjacency_list<OutEdgeListS, VertexListS, DirectedS, VertexProperty, EdgeProperty,
1.3270 + GraphProperty, EdgeListS> const & g)
1.3271 + {
1.3272 + typedef typename property_map<adjacency_list<OutEdgeListS, VertexListS, DirectedS, VertexProperty,
1.3273 + EdgeProperty, GraphProperty, EdgeListS>, T Bundle::*>::const_type
1.3274 + result_type;
1.3275 + return result_type(&g, p);
1.3276 + }
1.3277 +
1.3278 + template<typename OutEdgeListS, typename VertexListS, typename DirectedS, typename VertexProperty,
1.3279 + typename EdgeProperty, typename GraphProperty, typename EdgeListS, typename T, typename Bundle,
1.3280 + typename Key>
1.3281 + inline T
1.3282 + get(T Bundle::* p, adjacency_list<OutEdgeListS, VertexListS, DirectedS, VertexProperty, EdgeProperty,
1.3283 + GraphProperty, EdgeListS> const & g, const Key& key)
1.3284 + {
1.3285 + return get(get(p, g), key);
1.3286 + }
1.3287 +
1.3288 + template<typename OutEdgeListS, typename VertexListS, typename DirectedS, typename VertexProperty,
1.3289 + typename EdgeProperty, typename GraphProperty, typename EdgeListS, typename T, typename Bundle,
1.3290 + typename Key>
1.3291 + inline void
1.3292 + put(T Bundle::* p, adjacency_list<OutEdgeListS, VertexListS, DirectedS, VertexProperty, EdgeProperty,
1.3293 + GraphProperty, EdgeListS>& g, const Key& key, const T& value)
1.3294 + {
1.3295 + put(get(p, g), key, value);
1.3296 + }
1.3297 +
1.3298 #endif
1.3299
1.3300
1.3301 -#undef stored_edge
1.3302 -#undef stored_edge_property
1.3303 -#undef stored_edge_iter
1.3304 +} // namespace boost
1.3305
1.3306 -#endif // BOOST_GRAPH_DETAIL_DETAIL_ADJACENCY_LIST_CCT
1.3307
1.3308 -/*
1.3309 - Implementation Notes:
1.3310 -
1.3311 - Many of the public interface functions in this file would have been
1.3312 - more conveniently implemented as inline friend functions.
1.3313 - However there are a few compiler bugs that make that approach
1.3314 - non-portable.
1.3315 -
1.3316 - 1. g++ inline friend in namespace bug
1.3317 - 2. g++ using clause doesn't work with inline friends
1.3318 - 3. VC++ doesn't have Koenig lookup
1.3319 -
1.3320 - For these reasons, the functions were all written as non-inline free
1.3321 - functions, and static cast was used to convert from the helper
1.3322 - class to the adjacency_list derived class.
1.3323 -
1.3324 - Looking back, it might have been better to write out all functions
1.3325 - in terms of the adjacency_list, and then use a tag to dispatch
1.3326 - to the various helpers instead of using inheritance.
1.3327 -
1.3328 - */
1.3329 +#endif // BOOST_GRAPH_ADJACENCY_LIST_HPP