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