diff -r 000000000000 -r e4d67989cc36 ossrv_pub/boost_apis/boost/graph/detail/adjacency_list.hpp --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/ossrv_pub/boost_apis/boost/graph/detail/adjacency_list.hpp Tue Feb 02 02:01:42 2010 +0200 @@ -0,0 +1,2832 @@ +// -*- c++ -*- +//======================================================================= +// Copyright 1997, 1998, 1999, 2000 University of Notre Dame. +// Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek +// +// Distributed under the Boost Software License, Version 1.0. (See +// accompanying file LICENSE_1_0.txt or copy at +// http://www.boost.org/LICENSE_1_0.txt) +//======================================================================= + +#ifndef BOOST_GRAPH_DETAIL_ADJACENCY_LIST_HPP +#define BOOST_GRAPH_DETAIL_ADJACENCY_LIST_HPP + +#include // for vertex_map in copy_impl +#include +#include +#include +#include +#include +#include +#include +#include +#include + +#include + +#include +#include +#include +#include +#include +#include +#include +#include + +// Symbol truncation problems with MSVC, trying to shorten names. +#define stored_edge se_ +#define stored_edge_property sep_ +#define stored_edge_iter sei_ + +/* + Outline for this file: + + out_edge_iterator and in_edge_iterator implementation + edge_iterator for undirected graph + stored edge types (these object live in the out-edge/in-edge lists) + directed edges helper class + directed graph helper class + undirected graph helper class + bidirectional graph helper class + bidirectional graph helper class (without edge properties) + bidirectional graph helper class (with edge properties) + adjacency_list helper class + adj_list_impl class + vec_adj_list_impl class + adj_list_gen class + vertex property map + edge property map + + + Note: it would be nice to merge some of the undirected and + bidirectional code... it is awful similar. + */ + + +namespace boost { + + namespace detail { + + template + struct directed_category_traits { + typedef directed_tag directed_category; + }; + + template <> + struct directed_category_traits { + typedef directed_tag directed_category; + }; + template <> + struct directed_category_traits { + typedef undirected_tag directed_category; + }; + template <> + struct directed_category_traits { + typedef bidirectional_tag directed_category; + }; + + template + struct target_is { + target_is(const Vertex& v) : m_target(v) { } + template + bool operator()(const StoredEdge& e) const { + return e.get_target() == m_target; + } + Vertex m_target; + }; + + // O(E/V) + template + void erase_from_incidence_list(EdgeList& el, vertex_descriptor v, + allow_parallel_edge_tag) + { + boost::graph_detail::erase_if(el, detail::target_is(v)); + } + // O(log(E/V)) + template + void erase_from_incidence_list(EdgeList& el, vertex_descriptor v, + disallow_parallel_edge_tag) + { + typedef typename EdgeList::value_type StoredEdge; + el.erase(StoredEdge(v)); + } + + //========================================================================= + // Out-Edge and In-Edge Iterator Implementation + + template + struct out_edge_iter + : iterator_adaptor< + out_edge_iter + , BaseIter + , EdgeDescriptor + , use_default + , EdgeDescriptor + , Difference + > + { + typedef iterator_adaptor< + out_edge_iter + , BaseIter + , EdgeDescriptor + , use_default + , EdgeDescriptor + , Difference + > super_t; + + inline out_edge_iter() { } + inline out_edge_iter(const BaseIter& i, const VertexDescriptor& src) + : super_t(i), m_src(src) { } + + inline EdgeDescriptor + dereference() const + { + return EdgeDescriptor(m_src, (*this->base()).get_target(), + &(*this->base()).get_property()); + } + VertexDescriptor m_src; + }; + + template + struct in_edge_iter + : iterator_adaptor< + in_edge_iter + , BaseIter + , EdgeDescriptor + , use_default + , EdgeDescriptor + , Difference + > + { + typedef iterator_adaptor< + in_edge_iter + , BaseIter + , EdgeDescriptor + , use_default + , EdgeDescriptor + , Difference + > super_t; + + inline in_edge_iter() { } + inline in_edge_iter(const BaseIter& i, const VertexDescriptor& src) + : super_t(i), m_src(src) { } + + inline EdgeDescriptor + dereference() const + { + return EdgeDescriptor((*this->base()).get_target(), m_src, + &this->base()->get_property()); + } + VertexDescriptor m_src; + }; + + //========================================================================= + // Undirected Edge Iterator Implementation + + template + struct undirected_edge_iter + : iterator_adaptor< + undirected_edge_iter + , EdgeIter + , EdgeDescriptor + , use_default + , EdgeDescriptor + , Difference + > + { + typedef iterator_adaptor< + undirected_edge_iter + , EdgeIter + , EdgeDescriptor + , use_default + , EdgeDescriptor + , Difference + > super_t; + + undirected_edge_iter() {} + + explicit undirected_edge_iter(EdgeIter i) + : super_t(i) {} + + inline EdgeDescriptor + dereference() const { + return EdgeDescriptor( + (*this->base()).m_source + , (*this->base()).m_target + , &this->base()->get_property()); + } + }; + + //========================================================================= + // Edge Storage Types (stored in the out-edge/in-edge lists) + + template + class stored_edge + : public boost::equality_comparable1< stored_edge, + boost::less_than_comparable1< stored_edge > > + { + public: + typedef no_property property_type; + inline stored_edge() { } + inline stored_edge(Vertex target, const no_property& = no_property()) + : m_target(target) { } + // Need to write this explicitly so stored_edge_property can + // invoke Base::operator= (at least, for SGI MIPSPro compiler) + inline stored_edge& operator=(const stored_edge& x) { + m_target = x.m_target; + return *this; + } + inline Vertex& get_target() const { return m_target; } + inline const no_property& get_property() const { return s_prop; } + inline bool operator==(const stored_edge& x) const + { return m_target == x.get_target(); } + inline bool operator<(const stored_edge& x) const + { return m_target < x.get_target(); } + //protected: need to add hash<> as a friend + static no_property s_prop; + // Sometimes target not used as key in the set, and in that case + // it is ok to change the target. + mutable Vertex m_target; + }; + template + no_property stored_edge::s_prop; + + template + class stored_edge_property : public stored_edge { + typedef stored_edge_property self; + typedef stored_edge Base; + public: + typedef Property property_type; + inline stored_edge_property() { } + inline stored_edge_property(Vertex target, + const Property& p = Property()) + : stored_edge(target), m_property(new Property(p)) { } + stored_edge_property(const self& x) + : Base(x), m_property(const_cast(x).m_property) { } + self& operator=(const self& x) { + Base::operator=(x); + m_property = const_cast(x).m_property; + return *this; + } + inline Property& get_property() { return *m_property; } + inline const Property& get_property() const { return *m_property; } + protected: + // Holding the property by-value causes edge-descriptor + // invalidation for add_edge() with EdgeList=vecS. Instead we + // hold a pointer to the property. std::auto_ptr is not + // a perfect fit for the job, but it is darn close. + std::auto_ptr m_property; + }; + + + template + class stored_edge_iter + : public stored_edge + { + public: + typedef Property property_type; + inline stored_edge_iter() { } + inline stored_edge_iter(Vertex v) + : stored_edge(v) { } + inline stored_edge_iter(Vertex v, Iter i, void* = 0) + : stored_edge(v), m_iter(i) { } + inline Property& get_property() { return m_iter->get_property(); } + inline const Property& get_property() const { + return m_iter->get_property(); + } + inline Iter get_iter() const { return m_iter; } + protected: + Iter m_iter; + }; + + // For when the EdgeList is a std::vector. + // Want to make the iterator stable, so use an offset + // instead of an iterator into a std::vector + template + class stored_ra_edge_iter + : public stored_edge + { + typedef typename EdgeVec::iterator Iter; + public: + typedef Property property_type; + inline stored_ra_edge_iter() { } + inline stored_ra_edge_iter(Vertex v, Iter i = Iter(), + EdgeVec* edge_vec = 0) + : stored_edge(v), m_i(i - edge_vec->begin()), m_vec(edge_vec){ } + inline Property& get_property() { return (*m_vec)[m_i].get_property(); } + inline const Property& get_property() const { + return (*m_vec)[m_i].get_property(); + } + inline Iter get_iter() const { return m_vec->begin() + m_i; } + protected: + std::size_t m_i; + EdgeVec* m_vec; + }; + + } // namespace detail + + template + const typename property_value::type& + get(Tag property_tag, + const detail::stored_edge_property& e) + { + return get_property_value(e.get_property(), property_tag); + } + + template + const typename property_value::type& + get(Tag property_tag, + const detail::stored_edge_iter& e) + { + return get_property_value(e.get_property(), property_tag); + } + + template + const typename property_value::type& + get(Tag property_tag, + const detail::stored_ra_edge_iter& e) + { + return get_property_value(e.get_property(), property_tag); + } + + //========================================================================= + // Directed Edges Helper Class + + namespace detail { + + // O(E/V) + template + inline void + remove_directed_edge_dispatch(edge_descriptor, EdgeList& el, + StoredProperty& p) + { + for (typename EdgeList::iterator i = el.begin(); + i != el.end(); ++i) + if (&(*i).get_property() == &p) { + el.erase(i); + return; + } + } + + template + inline void + remove_directed_edge_if_dispatch(incidence_iterator first, + incidence_iterator last, + EdgeList& el, Predicate pred, + boost::allow_parallel_edge_tag) + { + // remove_if + while (first != last && !pred(*first)) + ++first; + incidence_iterator i = first; + if (first != last) + for (; i != last; ++i) + if (!pred(*i)) { + *first.base() = *i.base(); + ++first; + } + el.erase(first.base(), el.end()); + } + template + inline void + remove_directed_edge_if_dispatch(incidence_iterator first, + incidence_iterator last, + EdgeList& el, + Predicate pred, + boost::disallow_parallel_edge_tag) + { + for (incidence_iterator next = first; + first != last; first = next) { + ++next; + if (pred(*first)) + el.erase( first.base() ); + } + } + + template + inline void + undirected_remove_out_edge_if_dispatch(Graph& g, + incidence_iterator first, + incidence_iterator last, + EdgeList& el, Predicate pred, + boost::allow_parallel_edge_tag) + { + typedef typename Graph::global_edgelist_selector EdgeListS; + BOOST_STATIC_ASSERT((!is_same::value)); + + // remove_if + while (first != last && !pred(*first)) + ++first; + incidence_iterator i = first; + bool self_loop_removed = false; + if (first != last) + for (; i != last; ++i) { + if (self_loop_removed) { + /* With self loops, the descriptor will show up + * twice. The first time it will be removed, and now it + * will be skipped. + */ + self_loop_removed = false; + } + else if (!pred(*i)) { + *first.base() = *i.base(); + ++first; + } else { + if (source(*i, g) == target(*i, g)) self_loop_removed = true; + else { + // Remove the edge from the target + detail::remove_directed_edge_dispatch + (*i, + g.out_edge_list(target(*i, g)), + *(PropT*)(*i).get_property()); + } + + // Erase the edge property + g.m_edges.erase( (*i.base()).get_iter() ); + } + } + el.erase(first.base(), el.end()); + } + template + inline void + undirected_remove_out_edge_if_dispatch(Graph& g, + incidence_iterator first, + incidence_iterator last, + EdgeList& el, + Predicate pred, + boost::disallow_parallel_edge_tag) + { + typedef typename Graph::global_edgelist_selector EdgeListS; + BOOST_STATIC_ASSERT((!is_same::value)); + + for (incidence_iterator next = first; + first != last; first = next) { + ++next; + if (pred(*first)) { + if (source(*first, g) != target(*first, g)) { + // Remove the edge from the target + detail::remove_directed_edge_dispatch + (*first, + g.out_edge_list(target(*first, g)), + *(PropT*)(*first).get_property()); + } + + // Erase the edge property + g.m_edges.erase( (*first.base()).get_iter() ); + + // Erase the edge in the source + el.erase( first.base() ); + } + } + } + + // O(E/V) + template + inline void + remove_directed_edge_dispatch(edge_descriptor e, EdgeList& el, + no_property&) + { + for (typename EdgeList::iterator i = el.begin(); + i != el.end(); ++i) + if ((*i).get_target() == e.m_target) { + el.erase(i); + return; + } + } + + } // namespace detail + + template + struct directed_edges_helper { + + // Placement of these overloaded remove_edge() functions + // inside the class avoids a VC++ bug. + + // O(E/V) + inline void + remove_edge(typename Config::edge_descriptor e) + { + typedef typename Config::graph_type graph_type; + graph_type& g = static_cast(*this); + typename Config::OutEdgeList& el = g.out_edge_list(source(e, g)); + typedef typename Config::OutEdgeList::value_type::property_type PType; + detail::remove_directed_edge_dispatch(e, el, + *(PType*)e.get_property()); + } + + // O(1) + inline void + remove_edge(typename Config::out_edge_iterator iter) + { + typedef typename Config::graph_type graph_type; + graph_type& g = static_cast(*this); + typename Config::edge_descriptor e = *iter; + typename Config::OutEdgeList& el = g.out_edge_list(source(e, g)); + el.erase(iter.base()); + } + + }; + + // O(1) + template + inline std::pair + edges(const directed_edges_helper& g_) + { + typedef typename Config::graph_type graph_type; + typedef typename Config::edge_iterator edge_iterator; + const graph_type& cg = static_cast(g_); + graph_type& g = const_cast(cg); + return std::make_pair( edge_iterator(g.vertex_set().begin(), + g.vertex_set().begin(), + g.vertex_set().end(), g), + edge_iterator(g.vertex_set().begin(), + g.vertex_set().end(), + g.vertex_set().end(), g) ); + } + + //========================================================================= + // Directed Graph Helper Class + + struct adj_list_dir_traversal_tag : + public virtual vertex_list_graph_tag, + public virtual incidence_graph_tag, + public virtual adjacency_graph_tag, + public virtual edge_list_graph_tag { }; + + template + struct directed_graph_helper + : public directed_edges_helper { + typedef typename Config::edge_descriptor edge_descriptor; + typedef adj_list_dir_traversal_tag traversal_category; + }; + + // O(E/V) + template + inline void + remove_edge(typename Config::vertex_descriptor u, + typename Config::vertex_descriptor v, + directed_graph_helper& g_) + { + typedef typename Config::graph_type graph_type; + typedef typename Config::edge_parallel_category Cat; + graph_type& g = static_cast(g_); + detail::erase_from_incidence_list(g.out_edge_list(u), v, Cat()); + } + + template + inline void + remove_out_edge_if(typename Config::vertex_descriptor u, Predicate pred, + directed_graph_helper& g_) + { + typedef typename Config::graph_type graph_type; + graph_type& g = static_cast(g_); + typename Config::out_edge_iterator first, last; + tie(first, last) = out_edges(u, g); + typedef typename Config::edge_parallel_category edge_parallel_category; + detail::remove_directed_edge_if_dispatch + (first, last, g.out_edge_list(u), pred, edge_parallel_category()); + } + + template + inline void + remove_edge_if(Predicate pred, directed_graph_helper& g_) + { + typedef typename Config::graph_type graph_type; + graph_type& g = static_cast(g_); + + typename Config::vertex_iterator vi, vi_end; + for (tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi) + remove_out_edge_if(*vi, pred, g); + } + + template + inline void + remove_edge(EdgeOrIter e_or_iter, directed_graph_helper& g_) + { + g_.remove_edge(e_or_iter); + } + + // O(V + E) for allow_parallel_edges + // O(V * log(E/V)) for disallow_parallel_edges + template + inline void + clear_vertex(typename Config::vertex_descriptor u, + directed_graph_helper& g_) + { + typedef typename Config::graph_type graph_type; + typedef typename Config::edge_parallel_category Cat; + graph_type& g = static_cast(g_); + typename Config::vertex_iterator vi, viend; + for (boost::tie(vi, viend) = vertices(g); vi != viend; ++vi) + detail::erase_from_incidence_list(g.out_edge_list(*vi), u, Cat()); + g.out_edge_list(u).clear(); + // clear() should be a req of Sequence and AssociativeContainer, + // or maybe just Container + } + + template + inline void + clear_out_edges(typename Config::vertex_descriptor u, + directed_graph_helper& g_) + { + typedef typename Config::graph_type graph_type; + typedef typename Config::edge_parallel_category Cat; + graph_type& g = static_cast(g_); + g.out_edge_list(u).clear(); + // clear() should be a req of Sequence and AssociativeContainer, + // or maybe just Container + } + + // O(V), could do better... + template + inline typename Config::edges_size_type + num_edges(const directed_graph_helper& g_) + { + typedef typename Config::graph_type graph_type; + const graph_type& g = static_cast(g_); + typename Config::edges_size_type num_e = 0; + typename Config::vertex_iterator vi, vi_end; + for (boost::tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi) + num_e += out_degree(*vi, g); + return num_e; + } + // O(1) for allow_parallel_edge_tag + // O(log(E/V)) for disallow_parallel_edge_tag + template + inline std::pair::edge_descriptor, bool> + add_edge(typename Config::vertex_descriptor u, + typename Config::vertex_descriptor v, + const typename Config::edge_property_type& p, + directed_graph_helper& g_) + { + typedef typename Config::edge_descriptor edge_descriptor; + typedef typename Config::graph_type graph_type; + typedef typename Config::StoredEdge StoredEdge; + graph_type& g = static_cast(g_); + typename Config::OutEdgeList::iterator i; + bool inserted; + boost::tie(i, inserted) = boost::graph_detail::push(g.out_edge_list(u), + StoredEdge(v, p)); + return std::make_pair(edge_descriptor(u, v, &(*i).get_property()), + inserted); + } + // Did not use default argument here because that + // causes Visual C++ to get confused. + template + inline std::pair + add_edge(typename Config::vertex_descriptor u, + typename Config::vertex_descriptor v, + directed_graph_helper& g_) + { + typename Config::edge_property_type p; + return add_edge(u, v, p, g_); + } + //========================================================================= + // Undirected Graph Helper Class + + template + struct undirected_graph_helper; + + struct undir_adj_list_traversal_tag : + public virtual vertex_list_graph_tag, + public virtual incidence_graph_tag, + public virtual adjacency_graph_tag, + public virtual edge_list_graph_tag, + public virtual bidirectional_graph_tag { }; + + namespace detail { + + // using class with specialization for dispatch is a VC++ workaround. + template + struct remove_undirected_edge_dispatch { + + // O(E/V) + template + static void + apply(edge_descriptor e, + undirected_graph_helper& g_, + StoredProperty& p) + { + typedef typename Config::global_edgelist_selector EdgeListS; + BOOST_STATIC_ASSERT((!is_same::value)); + + typedef typename Config::graph_type graph_type; + graph_type& g = static_cast(g_); + + typename Config::OutEdgeList& out_el = g.out_edge_list(source(e, g)); + typename Config::OutEdgeList::iterator out_i = out_el.begin(); + for (; out_i != out_el.end(); ++out_i) + if (&(*out_i).get_property() == &p) { + out_el.erase(out_i); + break; + } + typename Config::OutEdgeList& in_el = g.out_edge_list(target(e, g)); + typename Config::OutEdgeList::iterator in_i = in_el.begin(); + for (; in_i != in_el.end(); ++in_i) + if (&(*in_i).get_property() == &p) { + g.m_edges.erase((*in_i).get_iter()); + in_el.erase(in_i); + return; + } + } + }; + + template <> + struct remove_undirected_edge_dispatch { + // O(E/V) + template + static void + apply(edge_descriptor e, + undirected_graph_helper& g_, + no_property&) + { + typedef typename Config::global_edgelist_selector EdgeListS; + BOOST_STATIC_ASSERT((!is_same::value)); + + typedef typename Config::graph_type graph_type; + graph_type& g = static_cast(g_); + no_property* p = (no_property*)e.get_property(); + typename Config::OutEdgeList& out_el = g.out_edge_list(source(e, g)); + typename Config::OutEdgeList::iterator out_i = out_el.begin(); + for (; out_i != out_el.end(); ++out_i) + if (&(*out_i).get_property() == p) { + out_el.erase(out_i); + break; + } + typename Config::OutEdgeList& in_el = g.out_edge_list(target(e, g)); + typename Config::OutEdgeList::iterator in_i = in_el.begin(); + for (; in_i != in_el.end(); ++in_i) + if (&(*in_i).get_property() == p) { + g.m_edges.erase((*in_i).get_iter()); + in_el.erase(in_i); + return; + } + } + }; + + // O(E/V) + template + inline void + remove_edge_and_property(Graph& g, EdgeList& el, Vertex v, + boost::allow_parallel_edge_tag cat) + { + typedef typename Graph::global_edgelist_selector EdgeListS; + BOOST_STATIC_ASSERT((!is_same::value)); + + typedef typename EdgeList::value_type StoredEdge; + typename EdgeList::iterator i = el.begin(), end = el.end(); + for (; i != end; ++i) + if ((*i).get_target() == v) + g.m_edges.erase((*i).get_iter()); + detail::erase_from_incidence_list(el, v, cat); + } + // O(log(E/V)) + template + inline void + remove_edge_and_property(Graph& g, EdgeList& el, Vertex v, + boost::disallow_parallel_edge_tag) + { + typedef typename Graph::global_edgelist_selector EdgeListS; + BOOST_STATIC_ASSERT((!is_same::value)); + + typedef typename EdgeList::value_type StoredEdge; + typename EdgeList::iterator i = el.find(StoredEdge(v)), end = el.end(); + if (i != end) { + g.m_edges.erase((*i).get_iter()); + el.erase(i); + } + } + + } // namespace detail + + template + struct list_edge // short name due to VC++ truncation and linker problems + : public boost::detail::edge_base + { + typedef EdgeProperty property_type; + typedef boost::detail::edge_base Base; + list_edge(Vertex u, Vertex v, const EdgeProperty& p = EdgeProperty()) + : Base(u, v), m_property(p) { } + EdgeProperty& get_property() { return m_property; } + const EdgeProperty& get_property() const { return m_property; } + // the following methods should never be used, but are needed + // to make SGI MIPSpro C++ happy + list_edge() { } + bool operator==(const list_edge&) const { return false; } + bool operator<(const list_edge&) const { return false; } + EdgeProperty m_property; + }; + + template + struct undirected_graph_helper { + + typedef undir_adj_list_traversal_tag traversal_category; + + // Placement of these overloaded remove_edge() functions + // inside the class avoids a VC++ bug. + + // O(E/V) + inline void + remove_edge(typename Config::edge_descriptor e) + { + typedef typename Config::global_edgelist_selector EdgeListS; + BOOST_STATIC_ASSERT((!is_same::value)); + + typedef typename Config::OutEdgeList::value_type::property_type PType; + detail::remove_undirected_edge_dispatch::apply + (e, *this, *(PType*)e.get_property()); + } + // O(E/V) + inline void + remove_edge(typename Config::out_edge_iterator iter) + { + this->remove_edge(*iter); + } + }; + + // Had to make these non-members to avoid accidental instantiation + // on SGI MIPSpro C++ + template + inline typename C::InEdgeList& + in_edge_list(undirected_graph_helper&, + typename C::vertex_descriptor v) + { + typename C::stored_vertex* sv = (typename C::stored_vertex*)v; + return sv->m_out_edges; + } + template + inline const typename C::InEdgeList& + in_edge_list(const undirected_graph_helper&, + typename C::vertex_descriptor v) { + typename C::stored_vertex* sv = (typename C::stored_vertex*)v; + return sv->m_out_edges; + } + + // O(E/V) + template + inline void + remove_edge(EdgeOrIter e, undirected_graph_helper& g_) + { + typedef typename Config::global_edgelist_selector EdgeListS; + BOOST_STATIC_ASSERT((!is_same::value)); + + g_.remove_edge(e); + } + + // O(E/V) or O(log(E/V)) + template + void + remove_edge(typename Config::vertex_descriptor u, + typename Config::vertex_descriptor v, + undirected_graph_helper& g_) + { + typedef typename Config::global_edgelist_selector EdgeListS; + BOOST_STATIC_ASSERT((!is_same::value)); + + typedef typename Config::graph_type graph_type; + graph_type& g = static_cast(g_); + typedef typename Config::edge_parallel_category Cat; + detail::remove_edge_and_property(g, g.out_edge_list(u), v, Cat()); + detail::erase_from_incidence_list(g.out_edge_list(v), u, Cat()); + } + + template + void + remove_out_edge_if(typename Config::vertex_descriptor u, Predicate pred, + undirected_graph_helper& g_) + { + typedef typename Config::global_edgelist_selector EdgeListS; + BOOST_STATIC_ASSERT((!is_same::value)); + + typedef typename Config::graph_type graph_type; + typedef typename Config::OutEdgeList::value_type::property_type PropT; + graph_type& g = static_cast(g_); + typename Config::out_edge_iterator first, last; + tie(first, last) = out_edges(u, g); + typedef typename Config::edge_parallel_category Cat; + detail::undirected_remove_out_edge_if_dispatch + (g, first, last, g.out_edge_list(u), pred, Cat()); + } + template + void + remove_in_edge_if(typename Config::vertex_descriptor u, Predicate pred, + undirected_graph_helper& g_) + { + typedef typename Config::global_edgelist_selector EdgeListS; + BOOST_STATIC_ASSERT((!is_same::value)); + + remove_out_edge_if(u, pred, g_); + } + + // O(E/V * E) or O(log(E/V) * E) + template + void + remove_edge_if(Predicate pred, undirected_graph_helper& g_) + { + typedef typename Config::global_edgelist_selector EdgeListS; + BOOST_STATIC_ASSERT((!is_same::value)); + + typedef typename Config::graph_type graph_type; + graph_type& g = static_cast(g_); + typename Config::edge_iterator ei, ei_end, next; + tie(ei, ei_end) = edges(g); + for (next = ei; ei != ei_end; ei = next) { + ++next; + if (pred(*ei)) + remove_edge(*ei, g); + } + } + + // O(1) + template + inline std::pair + edges(const undirected_graph_helper& g_) + { + typedef typename Config::graph_type graph_type; + typedef typename Config::edge_iterator edge_iterator; + const graph_type& cg = static_cast(g_); + graph_type& g = const_cast(cg); + return std::make_pair( edge_iterator(g.m_edges.begin()), + edge_iterator(g.m_edges.end()) ); + } + // O(1) + template + inline typename Config::edges_size_type + num_edges(const undirected_graph_helper& g_) + { + typedef typename Config::graph_type graph_type; + const graph_type& g = static_cast(g_); + return g.m_edges.size(); + } + // O(E/V * E/V) + template + inline void + clear_vertex(typename Config::vertex_descriptor u, + undirected_graph_helper& g_) + { + typedef typename Config::global_edgelist_selector EdgeListS; + BOOST_STATIC_ASSERT((!is_same::value)); + + typedef typename Config::graph_type graph_type; + typedef typename Config::edge_parallel_category Cat; + graph_type& g = static_cast(g_); + typename Config::OutEdgeList& el = g.out_edge_list(u); + typename Config::OutEdgeList::iterator + ei = el.begin(), ei_end = el.end(); + for (; ei != ei_end; ++ei) { + detail::erase_from_incidence_list + (g.out_edge_list((*ei).get_target()), u, Cat()); + g.m_edges.erase((*ei).get_iter()); + } + g.out_edge_list(u).clear(); + } + // O(1) for allow_parallel_edge_tag + // O(log(E/V)) for disallow_parallel_edge_tag + template + inline std::pair + add_edge(typename Config::vertex_descriptor u, + typename Config::vertex_descriptor v, + const typename Config::edge_property_type& p, + undirected_graph_helper& g_) + { + typedef typename Config::StoredEdge StoredEdge; + typedef typename Config::edge_descriptor edge_descriptor; + typedef typename Config::graph_type graph_type; + graph_type& g = static_cast(g_); + + bool inserted; + typename Config::EdgeContainer::value_type e(u, v, p); + typename Config::EdgeContainer::iterator p_iter + = graph_detail::push(g.m_edges, e).first; + + typename Config::OutEdgeList::iterator i; + boost::tie(i, inserted) = boost::graph_detail::push(g.out_edge_list(u), + StoredEdge(v, p_iter, &g.m_edges)); + if (inserted) { + boost::graph_detail::push(g.out_edge_list(v), StoredEdge(u, p_iter, &g.m_edges)); + return std::make_pair(edge_descriptor(u, v, &p_iter->get_property()), + true); + } else { + g.m_edges.erase(p_iter); + return std::make_pair + (edge_descriptor(u, v, &i->get_iter()->get_property()), false); + } + } + template + inline std::pair + add_edge(typename Config::vertex_descriptor u, + typename Config::vertex_descriptor v, + undirected_graph_helper& g_) + { + typename Config::edge_property_type p; + return add_edge(u, v, p, g_); + } + + // O(1) + template + inline typename Config::degree_size_type + degree(typename Config::vertex_descriptor u, + const undirected_graph_helper& g_) + { + typedef typename Config::graph_type Graph; + const Graph& g = static_cast(g_); + return out_degree(u, g); + } + + template + inline std::pair + in_edges(typename Config::vertex_descriptor u, + const undirected_graph_helper& g_) + { + typedef typename Config::graph_type Graph; + const Graph& cg = static_cast(g_); + Graph& g = const_cast(cg); + typedef typename Config::in_edge_iterator in_edge_iterator; + return + std::make_pair(in_edge_iterator(g.out_edge_list(u).begin(), u), + in_edge_iterator(g.out_edge_list(u).end(), u)); + } + + template + inline typename Config::degree_size_type + in_degree(typename Config::vertex_descriptor u, + const undirected_graph_helper& g_) + { return degree(u, g_); } + + //========================================================================= + // Bidirectional Graph Helper Class + + struct bidir_adj_list_traversal_tag : + public virtual vertex_list_graph_tag, + public virtual incidence_graph_tag, + public virtual adjacency_graph_tag, + public virtual edge_list_graph_tag, + public virtual bidirectional_graph_tag { }; + + template + struct bidirectional_graph_helper + : public directed_edges_helper { + typedef bidir_adj_list_traversal_tag traversal_category; + }; + + // Had to make these non-members to avoid accidental instantiation + // on SGI MIPSpro C++ + template + inline typename C::InEdgeList& + in_edge_list(bidirectional_graph_helper&, + typename C::vertex_descriptor v) + { + typename C::stored_vertex* sv = (typename C::stored_vertex*)v; + return sv->m_in_edges; + } + template + inline const typename C::InEdgeList& + in_edge_list(const bidirectional_graph_helper&, + typename C::vertex_descriptor v) { + typename C::stored_vertex* sv = (typename C::stored_vertex*)v; + return sv->m_in_edges; + } + + template + inline void + remove_edge_if(Predicate pred, bidirectional_graph_helper& g_) + { + typedef typename Config::global_edgelist_selector EdgeListS; + BOOST_STATIC_ASSERT((!is_same::value)); + + typedef typename Config::graph_type graph_type; + graph_type& g = static_cast(g_); + typename Config::edge_iterator ei, ei_end, next; + tie(ei, ei_end) = edges(g); + for (next = ei; ei != ei_end; ei = next) { + ++next; + if (pred(*ei)) + remove_edge(*ei, g); + } + } + + template + inline std::pair + in_edges(typename Config::vertex_descriptor u, + const bidirectional_graph_helper& g_) + { + typedef typename Config::graph_type graph_type; + const graph_type& cg = static_cast(g_); + graph_type& g = const_cast(cg); + typedef typename Config::in_edge_iterator in_edge_iterator; + return + std::make_pair(in_edge_iterator(in_edge_list(g, u).begin(), u), + in_edge_iterator(in_edge_list(g, u).end(), u)); + } + + // O(1) + template + inline std::pair + edges(const bidirectional_graph_helper& g_) + { + typedef typename Config::graph_type graph_type; + typedef typename Config::edge_iterator edge_iterator; + const graph_type& cg = static_cast(g_); + graph_type& g = const_cast(cg); + return std::make_pair( edge_iterator(g.m_edges.begin()), + edge_iterator(g.m_edges.end()) ); + } + + //========================================================================= + // Bidirectional Graph Helper Class (with edge properties) + + + template + struct bidirectional_graph_helper_with_property + : public bidirectional_graph_helper + { + typedef typename Config::graph_type graph_type; + typedef typename Config::out_edge_iterator out_edge_iterator; + + std::pair + get_parallel_edge_sublist(typename Config::edge_descriptor e, + const graph_type& g, + void*) + { return out_edges(source(e, g), g); } + + std::pair + get_parallel_edge_sublist(typename Config::edge_descriptor e, + const graph_type& g, + setS*) + { return edge_range(source(e, g), target(e, g), g); } + + std::pair + get_parallel_edge_sublist(typename Config::edge_descriptor e, + const graph_type& g, + multisetS*) + { return edge_range(source(e, g), target(e, g), g); } + +#if !defined BOOST_NO_HASH + std::pair + get_parallel_edge_sublist(typename Config::edge_descriptor e, + const graph_type& g, + hash_setS*) + { return edge_range(source(e, g), target(e, g), g); } +#endif + + // Placement of these overloaded remove_edge() functions + // inside the class avoids a VC++ bug. + + // O(E/V) or O(log(E/V)) + void + remove_edge(typename Config::edge_descriptor e) + { + typedef typename Config::global_edgelist_selector EdgeListS; + BOOST_STATIC_ASSERT((!is_same::value)); + + graph_type& g = static_cast(*this); + + typedef typename Config::edgelist_selector OutEdgeListS; + + std::pair rng = + get_parallel_edge_sublist(e, g, (OutEdgeListS*)(0)); + rng.first = std::find(rng.first, rng.second, e); + assert(rng.first != rng.second); + remove_edge(rng.first); + } + + inline void + remove_edge(typename Config::out_edge_iterator iter) + { + typedef typename Config::global_edgelist_selector EdgeListS; + BOOST_STATIC_ASSERT((!is_same::value)); + + typedef typename Config::graph_type graph_type; + graph_type& g = static_cast(*this); + typename Config::edge_descriptor e = *iter; + typename Config::OutEdgeList& oel = g.out_edge_list(source(e, g)); + typename Config::InEdgeList& iel = in_edge_list(g, target(e, g)); + typedef typename Config::OutEdgeList::value_type::property_type PType; + PType& p = *(PType*)e.get_property(); + detail::remove_directed_edge_dispatch(*iter, iel, p); + g.m_edges.erase(iter.base()->get_iter()); + oel.erase(iter.base()); + } + }; + + // O(E/V) for allow_parallel_edge_tag + // O(log(E/V)) for disallow_parallel_edge_tag + template + inline void + remove_edge(typename Config::vertex_descriptor u, + typename Config::vertex_descriptor v, + bidirectional_graph_helper_with_property& g_) + { + typedef typename Config::global_edgelist_selector EdgeListS; + BOOST_STATIC_ASSERT((!is_same::value)); + + typedef typename Config::graph_type graph_type; + graph_type& g = static_cast(g_); + typedef typename Config::edge_parallel_category Cat; + detail::remove_edge_and_property(g, g.out_edge_list(u), v, Cat()); + detail::erase_from_incidence_list(in_edge_list(g, v), u, Cat()); + } + + // O(E/V) or O(log(E/V)) + template + inline void + remove_edge(EdgeOrIter e, + bidirectional_graph_helper_with_property& g_) + { + typedef typename Config::global_edgelist_selector EdgeListS; + BOOST_STATIC_ASSERT((!is_same::value)); + + g_.remove_edge(e); + } + + template + inline void + remove_out_edge_if(typename Config::vertex_descriptor u, Predicate pred, + bidirectional_graph_helper_with_property& g_) + { + typedef typename Config::global_edgelist_selector EdgeListS; + BOOST_STATIC_ASSERT((!is_same::value)); + + typedef typename Config::graph_type graph_type; + typedef typename Config::OutEdgeList::value_type::property_type PropT; + graph_type& g = static_cast(g_); + + typedef typename Config::EdgeIter EdgeIter; + typedef std::vector Garbage; + Garbage garbage; + + // First remove the edges from the targets' in-edge lists and + // from the graph's edge set list. + typename Config::out_edge_iterator out_i, out_end; + for (tie(out_i, out_end) = out_edges(u, g); out_i != out_end; ++out_i) + if (pred(*out_i)) { + detail::remove_directed_edge_dispatch + (*out_i, in_edge_list(g, target(*out_i, g)), + *(PropT*)(*out_i).get_property()); + // Put in garbage to delete later. Will need the properties + // for the remove_if of the out-edges. + garbage.push_back((*out_i.base()).get_iter()); + } + + // Now remove the edges from this out-edge list. + typename Config::out_edge_iterator first, last; + tie(first, last) = out_edges(u, g); + typedef typename Config::edge_parallel_category Cat; + detail::remove_directed_edge_if_dispatch + (first, last, g.out_edge_list(u), pred, Cat()); + + // Now delete the edge properties from the g.m_edges list + for (typename Garbage::iterator i = garbage.begin(); + i != garbage.end(); ++i) + g.m_edges.erase(*i); + } + template + inline void + remove_in_edge_if(typename Config::vertex_descriptor v, Predicate pred, + bidirectional_graph_helper_with_property& g_) + { + typedef typename Config::global_edgelist_selector EdgeListS; + BOOST_STATIC_ASSERT((!is_same::value)); + + typedef typename Config::graph_type graph_type; + typedef typename Config::OutEdgeList::value_type::property_type PropT; + graph_type& g = static_cast(g_); + + typedef typename Config::EdgeIter EdgeIter; + typedef std::vector Garbage; + Garbage garbage; + + // First remove the edges from the sources' out-edge lists and + // from the graph's edge set list. + typename Config::in_edge_iterator in_i, in_end; + for (tie(in_i, in_end) = in_edges(v, g); in_i != in_end; ++in_i) + if (pred(*in_i)) { + typename Config::vertex_descriptor u = source(*in_i, g); + detail::remove_directed_edge_dispatch + (*in_i, g.out_edge_list(u), *(PropT*)(*in_i).get_property()); + // Put in garbage to delete later. Will need the properties + // for the remove_if of the out-edges. + garbage.push_back((*in_i.base()).get_iter()); + } + // Now remove the edges from this in-edge list. + typename Config::in_edge_iterator first, last; + tie(first, last) = in_edges(v, g); + typedef typename Config::edge_parallel_category Cat; + detail::remove_directed_edge_if_dispatch + (first, last, in_edge_list(g, v), pred, Cat()); + + // Now delete the edge properties from the g.m_edges list + for (typename Garbage::iterator i = garbage.begin(); + i != garbage.end(); ++i) + g.m_edges.erase(*i); + } + + // O(1) + template + inline typename Config::edges_size_type + num_edges(const bidirectional_graph_helper_with_property& g_) + { + typedef typename Config::graph_type graph_type; + const graph_type& g = static_cast(g_); + return g.m_edges.size(); + } + // O(E/V * E/V) for allow_parallel_edge_tag + // O(E/V * log(E/V)) for disallow_parallel_edge_tag + template + inline void + clear_vertex(typename Config::vertex_descriptor u, + bidirectional_graph_helper_with_property& g_) + { + typedef typename Config::global_edgelist_selector EdgeListS; + BOOST_STATIC_ASSERT((!is_same::value)); + + typedef typename Config::graph_type graph_type; + typedef typename Config::edge_parallel_category Cat; + graph_type& g = static_cast(g_); + typename Config::OutEdgeList& el = g.out_edge_list(u); + typename Config::OutEdgeList::iterator + ei = el.begin(), ei_end = el.end(); + for (; ei != ei_end; ++ei) { + detail::erase_from_incidence_list + (in_edge_list(g, (*ei).get_target()), u, Cat()); + g.m_edges.erase((*ei).get_iter()); + } + typename Config::InEdgeList& in_el = in_edge_list(g, u); + typename Config::InEdgeList::iterator + in_ei = in_el.begin(), in_ei_end = in_el.end(); + for (; in_ei != in_ei_end; ++in_ei) { + detail::erase_from_incidence_list + (g.out_edge_list((*in_ei).get_target()), u, Cat()); + g.m_edges.erase((*in_ei).get_iter()); + } + g.out_edge_list(u).clear(); + in_edge_list(g, u).clear(); + } + + template + inline void + clear_out_edges(typename Config::vertex_descriptor u, + bidirectional_graph_helper_with_property& g_) + { + typedef typename Config::global_edgelist_selector EdgeListS; + BOOST_STATIC_ASSERT((!is_same::value)); + + typedef typename Config::graph_type graph_type; + typedef typename Config::edge_parallel_category Cat; + graph_type& g = static_cast(g_); + typename Config::OutEdgeList& el = g.out_edge_list(u); + typename Config::OutEdgeList::iterator + ei = el.begin(), ei_end = el.end(); + for (; ei != ei_end; ++ei) { + detail::erase_from_incidence_list + (in_edge_list(g, (*ei).get_target()), u, Cat()); + g.m_edges.erase((*ei).get_iter()); + } + g.out_edge_list(u).clear(); + } + + template + inline void + clear_in_edges(typename Config::vertex_descriptor u, + bidirectional_graph_helper_with_property& g_) + { + typedef typename Config::global_edgelist_selector EdgeListS; + BOOST_STATIC_ASSERT((!is_same::value)); + + typedef typename Config::graph_type graph_type; + typedef typename Config::edge_parallel_category Cat; + graph_type& g = static_cast(g_); + typename Config::InEdgeList& in_el = in_edge_list(g, u); + typename Config::InEdgeList::iterator + in_ei = in_el.begin(), in_ei_end = in_el.end(); + for (; in_ei != in_ei_end; ++in_ei) { + detail::erase_from_incidence_list + (g.out_edge_list((*in_ei).get_target()), u, Cat()); + g.m_edges.erase((*in_ei).get_iter()); + } + in_edge_list(g, u).clear(); + } + + // O(1) for allow_parallel_edge_tag + // O(log(E/V)) for disallow_parallel_edge_tag + template + inline std::pair + add_edge(typename Config::vertex_descriptor u, + typename Config::vertex_descriptor v, + const typename Config::edge_property_type& p, + bidirectional_graph_helper_with_property& g_) + { + typedef typename Config::graph_type graph_type; + graph_type& g = static_cast(g_); + typedef typename Config::edge_descriptor edge_descriptor; + typedef typename Config::StoredEdge StoredEdge; + bool inserted; + typename Config::EdgeContainer::value_type e(u, v, p); + typename Config::EdgeContainer::iterator p_iter + = graph_detail::push(g.m_edges, e).first; + typename Config::OutEdgeList::iterator i; + boost::tie(i, inserted) = boost::graph_detail::push(g.out_edge_list(u), + StoredEdge(v, p_iter, &g.m_edges)); + if (inserted) { + boost::graph_detail::push(in_edge_list(g, v), StoredEdge(u, p_iter, &g.m_edges)); + return std::make_pair(edge_descriptor(u, v, &p_iter->m_property), + true); + } else { + g.m_edges.erase(p_iter); + return std::make_pair(edge_descriptor(u, v, + &i->get_iter()->get_property()), + false); + } + } + + template + inline std::pair + add_edge(typename Config::vertex_descriptor u, + typename Config::vertex_descriptor v, + bidirectional_graph_helper_with_property& g_) + { + typename Config::edge_property_type p; + return add_edge(u, v, p, g_); + } + // O(1) + template + inline typename Config::degree_size_type + degree(typename Config::vertex_descriptor u, + const bidirectional_graph_helper_with_property& g_) + { + typedef typename Config::graph_type graph_type; + const graph_type& g = static_cast(g_); + return in_degree(u, g) + out_degree(u, g); + } + + //========================================================================= + // Adjacency List Helper Class + + template + struct adj_list_helper : public Base + { + typedef typename Config::graph_type AdjList; + typedef typename Config::vertex_descriptor vertex_descriptor; + typedef typename Config::edge_descriptor edge_descriptor; + typedef typename Config::out_edge_iterator out_edge_iterator; + typedef typename Config::in_edge_iterator in_edge_iterator; + typedef typename Config::adjacency_iterator adjacency_iterator; + typedef typename Config::inv_adjacency_iterator inv_adjacency_iterator; + typedef typename Config::vertex_iterator vertex_iterator; + typedef typename Config::edge_iterator edge_iterator; + typedef typename Config::directed_category directed_category; + typedef typename Config::edge_parallel_category edge_parallel_category; + typedef typename Config::vertices_size_type vertices_size_type; + typedef typename Config::edges_size_type edges_size_type; + typedef typename Config::degree_size_type degree_size_type; + typedef typename Config::StoredEdge StoredEdge; + typedef typename Config::edge_property_type edge_property_type; + + typedef typename Config::global_edgelist_selector + global_edgelist_selector; + + // protected: + + // The edge_dispatch() functions should be static, but + // Borland gets confused about constness. + + // O(E/V) + inline std::pair + edge_dispatch(const AdjList& g, + vertex_descriptor u, vertex_descriptor v, + boost::allow_parallel_edge_tag) const + { + bool found; + const typename Config::OutEdgeList& el = g.out_edge_list(u); + typename Config::OutEdgeList::const_iterator + i = std::find_if(el.begin(), el.end(), + detail::target_is(v)); + found = (i != g.out_edge_list(u).end()); + if (found) + return std::make_pair(edge_descriptor(u, v, &(*i).get_property()), + true); + else + return std::make_pair(edge_descriptor(u, v, 0), false); + } + // O(log(E/V)) + inline std::pair + edge_dispatch(const AdjList& g, + vertex_descriptor u, vertex_descriptor v, + boost::disallow_parallel_edge_tag) const + { + bool found; + /* According to the standard, this should be iterator, not const_iterator, + but the VC++ std::set::find() const returns const_iterator. + And since iterator should be convertible to const_iterator, the + following should work everywhere. -Jeremy */ + typename Config::OutEdgeList::const_iterator + i = g.out_edge_list(u).find(StoredEdge(v)), + end = g.out_edge_list(u).end(); + found = (i != end); + if (found) + return std::make_pair(edge_descriptor(u, v, &(*i).get_property()), + true); + else + return std::make_pair(edge_descriptor(u, v, 0), false); + } + }; + + template + inline std::pair + adjacent_vertices(typename Config::vertex_descriptor u, + const adj_list_helper& g_) + { + typedef typename Config::graph_type AdjList; + const AdjList& cg = static_cast(g_); + AdjList& g = const_cast(cg); + typedef typename Config::adjacency_iterator adjacency_iterator; + typename Config::out_edge_iterator first, last; + boost::tie(first, last) = out_edges(u, g); + return std::make_pair(adjacency_iterator(first, &g), + adjacency_iterator(last, &g)); + } + template + inline std::pair + inv_adjacent_vertices(typename Config::vertex_descriptor u, + const adj_list_helper& g_) + { + typedef typename Config::graph_type AdjList; + const AdjList& cg = static_cast(g_); + AdjList& g = const_cast(cg); + typedef typename Config::inv_adjacency_iterator inv_adjacency_iterator; + typename Config::in_edge_iterator first, last; + boost::tie(first, last) = in_edges(u, g); + return std::make_pair(inv_adjacency_iterator(first, &g), + inv_adjacency_iterator(last, &g)); + } + template + inline std::pair + out_edges(typename Config::vertex_descriptor u, + const adj_list_helper& g_) + { + typedef typename Config::graph_type AdjList; + typedef typename Config::out_edge_iterator out_edge_iterator; + const AdjList& cg = static_cast(g_); + AdjList& g = const_cast(cg); + return + std::make_pair(out_edge_iterator(g.out_edge_list(u).begin(), u), + out_edge_iterator(g.out_edge_list(u).end(), u)); + } + template + inline std::pair + vertices(const adj_list_helper& g_) + { + typedef typename Config::graph_type AdjList; + const AdjList& cg = static_cast(g_); + AdjList& g = const_cast(cg); + return std::make_pair( g.vertex_set().begin(), g.vertex_set().end() ); + } + template + inline typename Config::vertices_size_type + num_vertices(const adj_list_helper& g_) + { + typedef typename Config::graph_type AdjList; + const AdjList& g = static_cast(g_); + return g.vertex_set().size(); + } + template + inline typename Config::degree_size_type + out_degree(typename Config::vertex_descriptor u, + const adj_list_helper& g_) + { + typedef typename Config::graph_type AdjList; + const AdjList& g = static_cast(g_); + return g.out_edge_list(u).size(); + } + template + inline std::pair + edge(typename Config::vertex_descriptor u, + typename Config::vertex_descriptor v, + const adj_list_helper& g_) + { + typedef typename Config::graph_type Graph; + typedef typename Config::edge_parallel_category Cat; + const Graph& g = static_cast(g_); + return g_.edge_dispatch(g, u, v, Cat()); + } + template + inline std::pair + edge_range(typename Config::vertex_descriptor u, + typename Config::vertex_descriptor v, + const adj_list_helper& g_) + { + typedef typename Config::graph_type Graph; + typedef typename Config::StoredEdge StoredEdge; + const Graph& cg = static_cast(g_); + Graph& g = const_cast(cg); + typedef typename Config::out_edge_iterator out_edge_iterator; + typename Config::OutEdgeList& el = g.out_edge_list(u); + typename Config::OutEdgeList::iterator first, last; + typename Config::EdgeContainer fake_edge_container; + tie(first, last) = + std::equal_range(el.begin(), el.end(), + StoredEdge(v, fake_edge_container.end(), + &fake_edge_container)); + return std::make_pair(out_edge_iterator(first, u), + out_edge_iterator(last, u)); + } + + template + inline typename Config::degree_size_type + in_degree(typename Config::vertex_descriptor u, + const directed_edges_helper& g_) + { + typedef typename Config::graph_type Graph; + const Graph& cg = static_cast(g_); + Graph& g = const_cast(cg); + return in_edge_list(g, u).size(); + } + + namespace detail { + template + inline + typename boost::property_map::type + get_dispatch(adj_list_helper&, Property, + boost::edge_property_tag) { + typedef typename Config::graph_type Graph; + typedef typename boost::property_map::type PA; + return PA(); + } + template + inline + typename boost::property_map::const_type + get_dispatch(const adj_list_helper&, Property, + boost::edge_property_tag) { + typedef typename Config::graph_type Graph; + typedef typename boost::property_map::const_type PA; + return PA(); + } + + template + inline + typename boost::property_map::type + get_dispatch(adj_list_helper& g, Property, + boost::vertex_property_tag) { + typedef typename Config::graph_type Graph; + typedef typename boost::property_map::type PA; + return PA(&static_cast(g)); + } + template + inline + typename boost::property_map::const_type + get_dispatch(const adj_list_helper& g, Property, + boost::vertex_property_tag) { + typedef typename Config::graph_type Graph; + typedef typename boost::property_map::const_type PA; + const Graph& cg = static_cast(g); + return PA(&cg); + } + + } // namespace detail + + // Implementation of the PropertyGraph interface + template + inline + typename boost::property_map::type + get(Property p, adj_list_helper& g) { + typedef typename property_kind::type Kind; + return detail::get_dispatch(g, p, Kind()); + } + template + inline + typename boost::property_map::const_type + get(Property p, const adj_list_helper& g) { + typedef typename property_kind::type Kind; + return detail::get_dispatch(g, p, Kind()); + } + + template + inline + typename boost::property_traits< + typename boost::property_map::type + >::reference + get(Property p, adj_list_helper& g, const Key& key) { + return get(get(p, g), key); + } + + template + inline + typename boost::property_traits< + typename boost::property_map::const_type + >::reference + get(Property p, const adj_list_helper& g, const Key& key) { + return get(get(p, g), key); + } + + template + inline void + put(Property p, adj_list_helper& g, + const Key& key, const Value& value) + { + typedef typename Config::graph_type Graph; + typedef typename boost::property_map::type Map; + Map pmap = get(p, static_cast(g)); + put(pmap, key, value); + } + + + //========================================================================= + // Generalize Adjacency List Implementation + + struct adj_list_tag { }; + + template + class adj_list_impl + : public adj_list_helper + { + typedef typename Config::OutEdgeList OutEdgeList; + typedef typename Config::InEdgeList InEdgeList; + typedef typename Config::StoredVertexList StoredVertexList; + public: + typedef typename Config::stored_vertex stored_vertex; + typedef typename Config::EdgeContainer EdgeContainer; + typedef typename Config::vertex_descriptor vertex_descriptor; + typedef typename Config::edge_descriptor edge_descriptor; + typedef typename Config::vertex_iterator vertex_iterator; + typedef typename Config::edge_iterator edge_iterator; + typedef typename Config::edge_parallel_category edge_parallel_category; + typedef typename Config::vertices_size_type vertices_size_type; + typedef typename Config::edges_size_type edges_size_type; + typedef typename Config::degree_size_type degree_size_type; + typedef typename Config::edge_property_type edge_property_type; + typedef adj_list_tag graph_tag; + + static vertex_descriptor null_vertex() + { + return 0; + } + + inline adj_list_impl() { } + + inline adj_list_impl(const adj_list_impl& x) { + copy_impl(x); + } + inline adj_list_impl& operator=(const adj_list_impl& x) { + this->clear(); + copy_impl(x); + return *this; + } + inline void clear() { + for (typename StoredVertexList::iterator i = m_vertices.begin(); + i != m_vertices.end(); ++i) + delete (stored_vertex*)*i; + m_vertices.clear(); + m_edges.clear(); + } + inline adj_list_impl(vertices_size_type num_vertices) { + for (vertices_size_type i = 0; i < num_vertices; ++i) + add_vertex(static_cast(*this)); + } + template + inline adj_list_impl(vertices_size_type num_vertices, + EdgeIterator first, EdgeIterator last) + { + vertex_descriptor* v = new vertex_descriptor[num_vertices]; + for (vertices_size_type i = 0; i < num_vertices; ++i) + v[i] = add_vertex(static_cast(*this)); + + while (first != last) { + add_edge(v[(*first).first], v[(*first).second], *this); + ++first; + } + delete [] v; + } + template + inline adj_list_impl(vertices_size_type num_vertices, + EdgeIterator first, EdgeIterator last, + EdgePropertyIterator ep_iter) + { + vertex_descriptor* v = new vertex_descriptor[num_vertices]; + for (vertices_size_type i = 0; i < num_vertices; ++i) + v[i] = add_vertex(static_cast(*this)); + + while (first != last) { + add_edge(v[(*first).first], v[(*first).second], *ep_iter, *this); + ++first; + ++ep_iter; + } + delete [] v; + } + ~adj_list_impl() { + for (typename StoredVertexList::iterator i = m_vertices.begin(); + i != m_vertices.end(); ++i) + delete (stored_vertex*)*i; + } + // protected: + inline OutEdgeList& out_edge_list(vertex_descriptor v) { + stored_vertex* sv = (stored_vertex*)v; + return sv->m_out_edges; + } + inline const OutEdgeList& out_edge_list(vertex_descriptor v) const { + stored_vertex* sv = (stored_vertex*)v; + return sv->m_out_edges; + } + inline StoredVertexList& vertex_set() { return m_vertices; } + inline const StoredVertexList& vertex_set() const { return m_vertices; } + + inline void copy_impl(const adj_list_impl& x_) + { + const Derived& x = static_cast(x_); + + // Would be better to have a constant time way to get from + // vertices in x to the corresponding vertices in *this. + std::map vertex_map; + + // Copy the stored vertex objects by adding each vertex + // and copying its property object. + vertex_iterator vi, vi_end; + for (tie(vi, vi_end) = vertices(x); vi != vi_end; ++vi) { + stored_vertex* v = (stored_vertex*)add_vertex(*this); + v->m_property = ((stored_vertex*)*vi)->m_property; + vertex_map[(stored_vertex*)*vi] = v; + } + // Copy the edges by adding each edge and copying its + // property object. + edge_iterator ei, ei_end; + for (tie(ei, ei_end) = edges(x); ei != ei_end; ++ei) { + edge_descriptor e; + bool inserted; + vertex_descriptor s = source(*ei,x), t = target(*ei,x); + tie(e, inserted) = add_edge(vertex_map[(stored_vertex*)s], + vertex_map[(stored_vertex*)t], *this); + *((edge_property_type*)e.m_eproperty) + = *((edge_property_type*)(*ei).m_eproperty); + } + } + + + typename Config::EdgeContainer m_edges; + StoredVertexList m_vertices; + }; + + // O(1) + template + inline typename Config::vertex_descriptor + add_vertex(adj_list_impl& g_) + { + Derived& g = static_cast(g_); + typedef typename Config::stored_vertex stored_vertex; + stored_vertex* v = new stored_vertex; + typename Config::StoredVertexList::iterator pos; + bool inserted; + boost::tie(pos,inserted) = boost::graph_detail::push(g.m_vertices, v); + v->m_position = pos; + return v; + } + // O(1) + template + inline typename Config::vertex_descriptor + add_vertex(const typename Config::vertex_property_type& p, + adj_list_impl& g_) + { + Derived& g = static_cast(g_); + typedef typename Config::stored_vertex stored_vertex; + stored_vertex* v = new stored_vertex(p); + typename Config::StoredVertexList::iterator pos; + bool inserted; + boost::tie(pos,inserted) = boost::graph_detail::push(g.m_vertices, v); + v->m_position = pos; + return v; + } + // O(1) + template + inline void remove_vertex(typename Config::vertex_descriptor u, + adj_list_impl& g_) + { + typedef typename Config::stored_vertex stored_vertex; + Derived& g = static_cast(g_); + stored_vertex* su = (stored_vertex*)u; + g.m_vertices.erase(su->m_position); + delete su; + } + // O(V) + template + inline typename Config::vertex_descriptor + vertex(typename Config::vertices_size_type n, + const adj_list_impl& g_) + { + const Derived& g = static_cast(g_); + typename Config::vertex_iterator i = vertices(g).first; + while (n--) ++i; // std::advance(i, n); (not VC++ portable) + return *i; + } + + //========================================================================= + // Vector-Backbone Adjacency List Implementation + + namespace detail { + + template + inline void + remove_vertex_dispatch(Graph& g, vertex_descriptor u, + boost::directed_tag) + { + typedef typename Graph::edge_parallel_category edge_parallel_category; + g.m_vertices.erase(g.m_vertices.begin() + u); + vertex_descriptor V = num_vertices(g); + if (u != V) { + for (vertex_descriptor v = 0; v < V; ++v) + reindex_edge_list(g.out_edge_list(v), u, edge_parallel_category()); + } + } + + template + inline void + remove_vertex_dispatch(Graph& g, vertex_descriptor u, + boost::undirected_tag) + { + typedef typename Graph::global_edgelist_selector EdgeListS; + BOOST_STATIC_ASSERT((!is_same::value)); + + typedef typename Graph::edge_parallel_category edge_parallel_category; + g.m_vertices.erase(g.m_vertices.begin() + u); + vertex_descriptor V = num_vertices(g); + for (vertex_descriptor v = 0; v < V; ++v) + reindex_edge_list(g.out_edge_list(v), u, + edge_parallel_category()); + typedef typename Graph::EdgeContainer Container; + typedef typename Container::iterator Iter; + Iter ei = g.m_edges.begin(), ei_end = g.m_edges.end(); + for (; ei != ei_end; ++ei) { + if (ei->m_source > u) + --ei->m_source; + if (ei->m_target > u) + --ei->m_target; + } + } + template + inline void + remove_vertex_dispatch(Graph& g, vertex_descriptor u, + boost::bidirectional_tag) + { + typedef typename Graph::global_edgelist_selector EdgeListS; + BOOST_STATIC_ASSERT((!is_same::value)); + + typedef typename Graph::edge_parallel_category edge_parallel_category; + g.m_vertices.erase(g.m_vertices.begin() + u); + vertex_descriptor V = num_vertices(g); + vertex_descriptor v; + if (u != V) { + for (v = 0; v < V; ++v) + reindex_edge_list(g.out_edge_list(v), u, + edge_parallel_category()); + for (v = 0; v < V; ++v) + reindex_edge_list(in_edge_list(g, v), u, + edge_parallel_category()); + + typedef typename Graph::EdgeContainer Container; + typedef typename Container::iterator Iter; + Iter ei = g.m_edges.begin(), ei_end = g.m_edges.end(); + for (; ei != ei_end; ++ei) { + if (ei->m_source > u) + --ei->m_source; + if (ei->m_target > u) + --ei->m_target; + } + } + } + + template + inline void + reindex_edge_list(EdgeList& el, vertex_descriptor u, + boost::allow_parallel_edge_tag) + { + typename EdgeList::iterator ei = el.begin(), e_end = el.end(); + for (; ei != e_end; ++ei) + if ((*ei).get_target() > u) + --(*ei).get_target(); + } + template + inline void + reindex_edge_list(EdgeList& el, vertex_descriptor u, + boost::disallow_parallel_edge_tag) + { + typename EdgeList::iterator ei = el.begin(), e_end = el.end(); + while (ei != e_end) { + typename EdgeList::value_type ce = *ei; + ++ei; + if (ce.get_target() > u) { + el.erase(ce); + --ce.get_target(); + el.insert(ce); + } + } + } + } // namespace detail + + struct vec_adj_list_tag { }; + + template + class vec_adj_list_impl + : public adj_list_helper + { + typedef typename Config::OutEdgeList OutEdgeList; + typedef typename Config::InEdgeList InEdgeList; + typedef typename Config::StoredVertexList StoredVertexList; + public: + typedef typename Config::vertex_descriptor vertex_descriptor; + typedef typename Config::edge_descriptor edge_descriptor; + typedef typename Config::out_edge_iterator out_edge_iterator; + typedef typename Config::edge_iterator edge_iterator; + typedef typename Config::directed_category directed_category; + typedef typename Config::vertices_size_type vertices_size_type; + typedef typename Config::edges_size_type edges_size_type; + typedef typename Config::degree_size_type degree_size_type; + typedef typename Config::StoredEdge StoredEdge; + typedef typename Config::stored_vertex stored_vertex; + typedef typename Config::EdgeContainer EdgeContainer; + typedef typename Config::edge_property_type edge_property_type; + typedef vec_adj_list_tag graph_tag; + + static vertex_descriptor null_vertex() + { + return (std::numeric_limits::max)(); + } + + inline vec_adj_list_impl() { } + + inline vec_adj_list_impl(const vec_adj_list_impl& x) { + copy_impl(x); + } + inline vec_adj_list_impl& operator=(const vec_adj_list_impl& x) { + this->clear(); + copy_impl(x); + return *this; + } + inline void clear() { + m_vertices.clear(); + m_edges.clear(); + } + + inline vec_adj_list_impl(vertices_size_type _num_vertices) + : m_vertices(_num_vertices) { } + + template + inline vec_adj_list_impl(vertices_size_type num_vertices, + EdgeIterator first, EdgeIterator last) + : m_vertices(num_vertices) + { + while (first != last) { + add_edge((*first).first, (*first).second, + static_cast(*this)); + ++first; + } + } + template + inline vec_adj_list_impl(vertices_size_type num_vertices, + EdgeIterator first, EdgeIterator last, + EdgePropertyIterator ep_iter) + : m_vertices(num_vertices) + { + while (first != last) { + add_edge((*first).first, (*first).second, *ep_iter, + static_cast(*this)); + ++first; + ++ep_iter; + } + } + + // protected: + inline boost::integer_range vertex_set() const { + return boost::integer_range(0, m_vertices.size()); + } + inline OutEdgeList& out_edge_list(vertex_descriptor v) { + return m_vertices[v].m_out_edges; + } + inline const OutEdgeList& out_edge_list(vertex_descriptor v) const { + return m_vertices[v].m_out_edges; + } + inline void copy_impl(const vec_adj_list_impl& x_) + { + const Graph& x = static_cast(x_); + // Copy the stored vertex objects by adding each vertex + // and copying its property object. + for (vertices_size_type i = 0; i < num_vertices(x); ++i) { + vertex_descriptor v = add_vertex(*this); + m_vertices[v].m_property = x.m_vertices[i].m_property; + } + // Copy the edges by adding each edge and copying its + // property object. + edge_iterator ei, ei_end; + for (tie(ei, ei_end) = edges(x); ei != ei_end; ++ei) { + edge_descriptor e; + bool inserted; + tie(e, inserted) = add_edge(source(*ei,x), target(*ei,x) , *this); + *((edge_property_type*)e.m_eproperty) + = *((edge_property_type*)(*ei).m_eproperty); + } + } + typename Config::EdgeContainer m_edges; + StoredVertexList m_vertices; + }; + // Had to make these non-members to avoid accidental instantiation + // on SGI MIPSpro C++ + template + inline typename C::InEdgeList& + in_edge_list(vec_adj_list_impl& g, + typename C::vertex_descriptor v) { + return g.m_vertices[v].m_in_edges; + } + template + inline const typename C::InEdgeList& + in_edge_list(const vec_adj_list_impl& g, + typename C::vertex_descriptor v) { + return g.m_vertices[v].m_in_edges; + } + + // O(1) + template + inline typename Config::vertex_descriptor + add_vertex(vec_adj_list_impl& g_) { + Graph& g = static_cast(g_); + g.m_vertices.resize(g.m_vertices.size() + 1); + return g.m_vertices.size() - 1; + } + + template + inline typename Config::vertex_descriptor + add_vertex(const typename Config::vertex_property_type& p, + vec_adj_list_impl& g_) { + Graph& g = static_cast(g_); + typedef typename Config::stored_vertex stored_vertex; + g.m_vertices.push_back(stored_vertex(p)); + return g.m_vertices.size() - 1; + } + + // Here we override the directed_graph_helper add_edge() function + // so that the number of vertices is automatically changed if + // either u or v is greater than the number of vertices. + template + inline std::pair + add_edge(typename Config::vertex_descriptor u, + typename Config::vertex_descriptor v, + const typename Config::edge_property_type& p, + vec_adj_list_impl& g_) + { + BOOST_USING_STD_MAX(); + typename Config::vertex_descriptor x = max BOOST_PREVENT_MACRO_SUBSTITUTION(u, v); + if (x >= num_vertices(g_)) + g_.m_vertices.resize(x + 1); + adj_list_helper& g = g_; + return add_edge(u, v, p, g); + } + template + inline std::pair + add_edge(typename Config::vertex_descriptor u, + typename Config::vertex_descriptor v, + vec_adj_list_impl& g_) + { + typename Config::edge_property_type p; + return add_edge(u, v, p, g_); + } + + + // O(V + E) + template + inline void remove_vertex(typename Config::vertex_descriptor v, + vec_adj_list_impl& g_) + { + typedef typename Config::directed_category Cat; + Graph& g = static_cast(g_); + detail::remove_vertex_dispatch(g, v, Cat()); + } + // O(1) + template + inline typename Config::vertex_descriptor + vertex(typename Config::vertices_size_type n, + const vec_adj_list_impl&) + { + return n; + } + + + namespace detail { + + //========================================================================= + // Adjacency List Generator + + template + struct adj_list_gen + { + typedef typename detail::is_random_access::type + is_rand_access; + typedef typename has_property::type has_edge_property; + typedef typename DirectedS::is_directed_t DirectedT; + typedef typename DirectedS::is_bidir_t BidirectionalT; + + struct config + { + typedef OutEdgeListS edgelist_selector; + typedef EdgeListS global_edgelist_selector; + + typedef Graph graph_type; + typedef EdgeProperty edge_property_type; + typedef VertexProperty vertex_property_type; + typedef GraphProperty graph_property_type; + typedef std::size_t vertices_size_type; + + typedef adjacency_list_traits + Traits; + + typedef typename Traits::directed_category directed_category; + typedef typename Traits::edge_parallel_category edge_parallel_category; + typedef typename Traits::vertex_descriptor vertex_descriptor; + typedef typename Traits::edge_descriptor edge_descriptor; + + typedef void* vertex_ptr; + + // need to reorganize this to avoid instantiating stuff + // that doesn't get used -JGS + + // VertexList and vertex_iterator + typedef typename container_gen::type SeqVertexList; + typedef boost::integer_range