1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/epoc32/include/stdapis/boost/graph/detail/adjacency_list.hpp Tue Mar 16 16:12:26 2010 +0000
1.3 @@ -0,0 +1,2832 @@
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 + */