| // -*- c++ -*- |
| //======================================================================= |
| // Copyright 1997, 1998, 1999, 2000 University of Notre Dame. |
| // Copyright 2010 Thomas Claveirole |
| // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek, Thomas Claveirole |
| // |
| // 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 <map> // for vertex_map in copy_impl |
| #include <boost/config.hpp> |
| #include <boost/detail/workaround.hpp> |
| #include <boost/operators.hpp> |
| #include <boost/property_map/property_map.hpp> |
| #include <boost/range/irange.hpp> |
| #include <boost/graph/graph_traits.hpp> |
| #include <memory> |
| #include <algorithm> |
| #include <boost/limits.hpp> |
| |
| #include <boost/iterator/iterator_adaptor.hpp> |
| |
| #include <boost/mpl/if.hpp> |
| #include <boost/mpl/not.hpp> |
| #include <boost/mpl/and.hpp> |
| #include <boost/graph/graph_concepts.hpp> |
| #include <boost/pending/container_traits.hpp> |
| #include <boost/graph/detail/adj_list_edge_iterator.hpp> |
| #include <boost/graph/properties.hpp> |
| #include <boost/pending/property.hpp> |
| #include <boost/graph/adjacency_iterator.hpp> |
| #include <boost/static_assert.hpp> |
| |
| // 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. |
| */ |
| |
| |
| #if BOOST_WORKAROUND(BOOST_MSVC, < 1300) |
| // Stay out of the way of the concept checking class |
| # define Graph Graph_ |
| #endif |
| |
| namespace boost { |
| |
| namespace detail { |
| |
| template <typename DirectedS> |
| struct directed_category_traits { |
| typedef directed_tag directed_category; |
| }; |
| |
| template <> |
| struct directed_category_traits<directedS> { |
| typedef directed_tag directed_category; |
| }; |
| template <> |
| struct directed_category_traits<undirectedS> { |
| typedef undirected_tag directed_category; |
| }; |
| template <> |
| struct directed_category_traits<bidirectionalS> { |
| typedef bidirectional_tag directed_category; |
| }; |
| |
| template <class Vertex> |
| struct target_is { |
| target_is(const Vertex& v) : m_target(v) { } |
| template <class StoredEdge> |
| bool operator()(const StoredEdge& e) const { |
| return e.get_target() == m_target; |
| } |
| Vertex m_target; |
| }; |
| |
| // O(E/V) |
| template <class EdgeList, class vertex_descriptor> |
| void erase_from_incidence_list(EdgeList& el, vertex_descriptor v, |
| allow_parallel_edge_tag) |
| { |
| boost::graph_detail::erase_if(el, detail::target_is<vertex_descriptor>(v)); |
| } |
| // O(log(E/V)) |
| template <class EdgeList, class vertex_descriptor> |
| 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 <class BaseIter, class VertexDescriptor, class EdgeDescriptor, class Difference> |
| struct out_edge_iter |
| : iterator_adaptor< |
| out_edge_iter<BaseIter, VertexDescriptor, EdgeDescriptor, Difference> |
| , BaseIter |
| , EdgeDescriptor |
| , use_default |
| , EdgeDescriptor |
| , Difference |
| > |
| { |
| typedef iterator_adaptor< |
| out_edge_iter<BaseIter, VertexDescriptor, EdgeDescriptor, Difference> |
| , 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 <class BaseIter, class VertexDescriptor, class EdgeDescriptor, class Difference> |
| struct in_edge_iter |
| : iterator_adaptor< |
| in_edge_iter<BaseIter, VertexDescriptor, EdgeDescriptor, Difference> |
| , BaseIter |
| , EdgeDescriptor |
| , use_default |
| , EdgeDescriptor |
| , Difference |
| > |
| { |
| typedef iterator_adaptor< |
| in_edge_iter<BaseIter, VertexDescriptor, EdgeDescriptor, Difference> |
| , 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 <class EdgeIter, class EdgeDescriptor, class Difference> |
| struct undirected_edge_iter |
| : iterator_adaptor< |
| undirected_edge_iter<EdgeIter, EdgeDescriptor, Difference> |
| , EdgeIter |
| , EdgeDescriptor |
| , use_default |
| , EdgeDescriptor |
| , Difference |
| > |
| { |
| typedef iterator_adaptor< |
| undirected_edge_iter<EdgeIter, EdgeDescriptor, Difference> |
| , 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 Vertex> |
| class stored_edge |
| : public boost::equality_comparable1< stored_edge<Vertex>, |
| boost::less_than_comparable1< stored_edge<Vertex> > > |
| { |
| 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 <class Vertex> |
| no_property stored_edge<Vertex>::s_prop; |
| |
| template <class Vertex, class Property> |
| class stored_edge_property : public stored_edge<Vertex> { |
| typedef stored_edge_property self; |
| typedef stored_edge<Vertex> Base; |
| public: |
| typedef Property property_type; |
| inline stored_edge_property() { } |
| inline stored_edge_property(Vertex target, |
| const Property& p = Property()) |
| : stored_edge<Vertex>(target), m_property(new Property(p)) { } |
| stored_edge_property(const self& x) |
| : Base(x), m_property(const_cast<self&>(x).m_property) { } |
| self& operator=(const self& x) { |
| Base::operator=(x); |
| m_property = const_cast<self&>(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<Property> m_property; |
| }; |
| |
| |
| template <class Vertex, class Iter, class Property> |
| class stored_edge_iter |
| : public stored_edge<Vertex> |
| { |
| public: |
| typedef Property property_type; |
| inline stored_edge_iter() { } |
| inline stored_edge_iter(Vertex v) |
| : stored_edge<Vertex>(v) { } |
| inline stored_edge_iter(Vertex v, Iter i, void* = 0) |
| : stored_edge<Vertex>(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 Vertex, class EdgeVec, class Property> |
| class stored_ra_edge_iter |
| : public stored_edge<Vertex> |
| { |
| 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<Vertex>(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 <class Tag, class Vertex, class Property> |
| const typename property_value<Property,Tag>::type& |
| get(Tag property_tag, |
| const detail::stored_edge_property<Vertex, Property>& e) |
| { |
| return get_property_value(e.get_property(), property_tag); |
| } |
| |
| template <class Tag, class Vertex, class Iter, class Property> |
| const typename property_value<Property,Tag>::type& |
| get(Tag property_tag, |
| const detail::stored_edge_iter<Vertex, Iter, Property>& e) |
| { |
| return get_property_value(e.get_property(), property_tag); |
| } |
| |
| template <class Tag, class Vertex, class EdgeVec, class Property> |
| const typename property_value<Property,Tag>::type& |
| get(Tag property_tag, |
| const detail::stored_ra_edge_iter<Vertex, EdgeVec, Property>& e) |
| { |
| return get_property_value(e.get_property(), property_tag); |
| } |
| |
| //========================================================================= |
| // Directed Edges Helper Class |
| |
| namespace detail { |
| |
| // O(E/V) |
| template <class edge_descriptor, class EdgeList, class StoredProperty> |
| 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 <class incidence_iterator, class EdgeList, class Predicate> |
| 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; i != last; ++i) |
| if (!pred(*i)) { |
| *first.base() = *i.base(); |
| ++first; |
| } |
| el.erase(first.base(), el.end()); |
| } |
| template <class incidence_iterator, class EdgeList, class Predicate> |
| 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 <class PropT, class Graph, class incidence_iterator, |
| class EdgeList, class Predicate> |
| 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<EdgeListS, vecS>::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 <class PropT, class Graph, class incidence_iterator, |
| class EdgeList, class Predicate> |
| 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<EdgeListS, vecS>::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 <class edge_descriptor, class EdgeList, class StoredProperty> |
| 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 <class Config> |
| 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<graph_type&>(*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<graph_type&>(*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 <class Config> |
| inline std::pair<typename Config::edge_iterator, |
| typename Config::edge_iterator> |
| edges(const directed_edges_helper<Config>& g_) |
| { |
| typedef typename Config::graph_type graph_type; |
| typedef typename Config::edge_iterator edge_iterator; |
| const graph_type& cg = static_cast<const graph_type&>(g_); |
| graph_type& g = const_cast<graph_type&>(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 <class Config> |
| struct directed_graph_helper |
| : public directed_edges_helper<Config> { |
| typedef typename Config::edge_descriptor edge_descriptor; |
| typedef adj_list_dir_traversal_tag traversal_category; |
| }; |
| |
| // O(E/V) |
| template <class Config> |
| inline void |
| remove_edge(typename Config::vertex_descriptor u, |
| typename Config::vertex_descriptor v, |
| directed_graph_helper<Config>& g_) |
| { |
| typedef typename Config::graph_type graph_type; |
| typedef typename Config::edge_parallel_category Cat; |
| graph_type& g = static_cast<graph_type&>(g_); |
| detail::erase_from_incidence_list(g.out_edge_list(u), v, Cat()); |
| } |
| |
| template <class Config, class Predicate> |
| inline void |
| remove_out_edge_if(typename Config::vertex_descriptor u, Predicate pred, |
| directed_graph_helper<Config>& g_) |
| { |
| typedef typename Config::graph_type graph_type; |
| graph_type& g = static_cast<graph_type&>(g_); |
| typename Config::out_edge_iterator first, last; |
| boost::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 <class Config, class Predicate> |
| inline void |
| remove_edge_if(Predicate pred, directed_graph_helper<Config>& g_) |
| { |
| typedef typename Config::graph_type graph_type; |
| graph_type& g = static_cast<graph_type&>(g_); |
| |
| typename Config::vertex_iterator vi, vi_end; |
| for (boost::tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi) |
| remove_out_edge_if(*vi, pred, g); |
| } |
| |
| template <class EdgeOrIter, class Config> |
| inline void |
| remove_edge(EdgeOrIter e_or_iter, directed_graph_helper<Config>& g_) |
| { |
| g_.remove_edge(e_or_iter); |
| } |
| |
| // O(V + E) for allow_parallel_edges |
| // O(V * log(E/V)) for disallow_parallel_edges |
| template <class Config> |
| inline void |
| clear_vertex(typename Config::vertex_descriptor u, |
| directed_graph_helper<Config>& g_) |
| { |
| typedef typename Config::graph_type graph_type; |
| typedef typename Config::edge_parallel_category Cat; |
| graph_type& g = static_cast<graph_type&>(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 <class Config> |
| inline void |
| clear_out_edges(typename Config::vertex_descriptor u, |
| directed_graph_helper<Config>& g_) |
| { |
| typedef typename Config::graph_type graph_type; |
| typedef typename Config::edge_parallel_category Cat; |
| graph_type& g = static_cast<graph_type&>(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 <class Config> |
| inline typename Config::edges_size_type |
| num_edges(const directed_graph_helper<Config>& g_) |
| { |
| typedef typename Config::graph_type graph_type; |
| const graph_type& g = static_cast<const graph_type&>(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 <class Config> |
| inline std::pair<typename directed_graph_helper<Config>::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<Config>& 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<graph_type&>(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 <class Config> |
| inline std::pair<typename Config::edge_descriptor, bool> |
| add_edge(typename Config::vertex_descriptor u, |
| typename Config::vertex_descriptor v, |
| directed_graph_helper<Config>& g_) |
| { |
| typename Config::edge_property_type p; |
| return add_edge(u, v, p, g_); |
| } |
| //========================================================================= |
| // Undirected Graph Helper Class |
| |
| template <class Config> |
| 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 <class StoredProperty> |
| struct remove_undirected_edge_dispatch { |
| |
| // O(E/V) |
| template <class edge_descriptor, class Config> |
| static void |
| apply(edge_descriptor e, |
| undirected_graph_helper<Config>& g_, |
| StoredProperty& p) |
| { |
| typedef typename Config::global_edgelist_selector EdgeListS; |
| BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value)); |
| |
| typedef typename Config::graph_type graph_type; |
| graph_type& g = static_cast<graph_type&>(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<no_property> { |
| // O(E/V) |
| template <class edge_descriptor, class Config> |
| static void |
| apply(edge_descriptor e, |
| undirected_graph_helper<Config>& g_, |
| no_property&) |
| { |
| typedef typename Config::global_edgelist_selector EdgeListS; |
| BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value)); |
| |
| typedef typename Config::graph_type graph_type; |
| graph_type& g = static_cast<graph_type&>(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 <class Graph, class EdgeList, class Vertex> |
| 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<EdgeListS, vecS>::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) { |
| // NOTE: Wihtout this skip, this loop will double-delete properties |
| // of loop edges. This solution is based on the observation that |
| // the incidence edges of a vertex with a loop are adjacent in the |
| // out edge list. This *may* actually hold for multisets also. |
| bool skip = (boost::next(i) != end && i->get_iter() == boost::next(i)->get_iter()); |
| g.m_edges.erase((*i).get_iter()); |
| if (skip) ++i; |
| } |
| } |
| detail::erase_from_incidence_list(el, v, cat); |
| } |
| // O(log(E/V)) |
| template <class Graph, class EdgeList, class Vertex> |
| 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<EdgeListS, vecS>::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 <class Vertex, class EdgeProperty> |
| struct list_edge // short name due to VC++ truncation and linker problems |
| : public boost::detail::edge_base<boost::undirected_tag, Vertex> |
| { |
| typedef EdgeProperty property_type; |
| typedef boost::detail::edge_base<boost::undirected_tag, Vertex> 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 <class Config> |
| 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<EdgeListS, vecS>::value)); |
| |
| typedef typename Config::OutEdgeList::value_type::property_type PType; |
| detail::remove_undirected_edge_dispatch<PType>::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 <class C> |
| inline typename C::InEdgeList& |
| in_edge_list(undirected_graph_helper<C>&, |
| typename C::vertex_descriptor v) |
| { |
| typename C::stored_vertex* sv = (typename C::stored_vertex*)v; |
| return sv->m_out_edges; |
| } |
| template <class C> |
| inline const typename C::InEdgeList& |
| in_edge_list(const undirected_graph_helper<C>&, |
| typename C::vertex_descriptor v) { |
| typename C::stored_vertex* sv = (typename C::stored_vertex*)v; |
| return sv->m_out_edges; |
| } |
| |
| // O(E/V) |
| template <class EdgeOrIter, class Config> |
| inline void |
| remove_edge(EdgeOrIter e, undirected_graph_helper<Config>& g_) |
| { |
| typedef typename Config::global_edgelist_selector EdgeListS; |
| BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value)); |
| |
| g_.remove_edge(e); |
| } |
| |
| // O(E/V) or O(log(E/V)) |
| template <class Config> |
| void |
| remove_edge(typename Config::vertex_descriptor u, |
| typename Config::vertex_descriptor v, |
| undirected_graph_helper<Config>& g_) |
| { |
| typedef typename Config::global_edgelist_selector EdgeListS; |
| BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value)); |
| |
| typedef typename Config::graph_type graph_type; |
| graph_type& g = static_cast<graph_type&>(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 <class Config, class Predicate> |
| void |
| remove_out_edge_if(typename Config::vertex_descriptor u, Predicate pred, |
| undirected_graph_helper<Config>& g_) |
| { |
| typedef typename Config::global_edgelist_selector EdgeListS; |
| BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value)); |
| |
| typedef typename Config::graph_type graph_type; |
| typedef typename Config::OutEdgeList::value_type::property_type PropT; |
| graph_type& g = static_cast<graph_type&>(g_); |
| typename Config::out_edge_iterator first, last; |
| boost::tie(first, last) = out_edges(u, g); |
| typedef typename Config::edge_parallel_category Cat; |
| detail::undirected_remove_out_edge_if_dispatch<PropT> |
| (g, first, last, g.out_edge_list(u), pred, Cat()); |
| } |
| template <class Config, class Predicate> |
| void |
| remove_in_edge_if(typename Config::vertex_descriptor u, Predicate pred, |
| undirected_graph_helper<Config>& g_) |
| { |
| typedef typename Config::global_edgelist_selector EdgeListS; |
| BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value)); |
| |
| remove_out_edge_if(u, pred, g_); |
| } |
| |
| // O(E/V * E) or O(log(E/V) * E) |
| template <class Predicate, class Config> |
| void |
| remove_edge_if(Predicate pred, undirected_graph_helper<Config>& g_) |
| { |
| typedef typename Config::global_edgelist_selector EdgeListS; |
| BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value)); |
| |
| typedef typename Config::graph_type graph_type; |
| graph_type& g = static_cast<graph_type&>(g_); |
| typename Config::edge_iterator ei, ei_end, next; |
| boost::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 <class Config> |
| inline std::pair<typename Config::edge_iterator, |
| typename Config::edge_iterator> |
| edges(const undirected_graph_helper<Config>& g_) |
| { |
| typedef typename Config::graph_type graph_type; |
| typedef typename Config::edge_iterator edge_iterator; |
| const graph_type& cg = static_cast<const graph_type&>(g_); |
| graph_type& g = const_cast<graph_type&>(cg); |
| return std::make_pair( edge_iterator(g.m_edges.begin()), |
| edge_iterator(g.m_edges.end()) ); |
| } |
| // O(1) |
| template <class Config> |
| inline typename Config::edges_size_type |
| num_edges(const undirected_graph_helper<Config>& g_) |
| { |
| typedef typename Config::graph_type graph_type; |
| const graph_type& g = static_cast<const graph_type&>(g_); |
| return g.m_edges.size(); |
| } |
| // O(E/V * E/V) |
| template <class Config> |
| inline void |
| clear_vertex(typename Config::vertex_descriptor u, |
| undirected_graph_helper<Config>& g_) |
| { |
| typedef typename Config::global_edgelist_selector EdgeListS; |
| BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value)); |
| |
| typedef typename Config::graph_type graph_type; |
| typedef typename Config::edge_parallel_category Cat; |
| graph_type& g = static_cast<graph_type&>(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; /* Increment below */ ) { |
| bool is_self_loop = (*ei).get_target() == u; |
| // Don't erase from our own incidence list in the case of a self-loop |
| // since we're clearing it anyway. |
| if (!is_self_loop) { |
| detail::erase_from_incidence_list |
| (g.out_edge_list((*ei).get_target()), u, Cat()); |
| typename Config::OutEdgeList::iterator ei_copy = ei; |
| ++ei; |
| if (!is_self_loop) g.m_edges.erase((*ei_copy).get_iter()); |
| } else { |
| ++ei; |
| } |
| } |
| g.out_edge_list(u).clear(); |
| } |
| // O(1) for allow_parallel_edge_tag |
| // O(log(E/V)) for disallow_parallel_edge_tag |
| template <class Config> |
| inline std::pair<typename Config::edge_descriptor, bool> |
| add_edge(typename Config::vertex_descriptor u, |
| typename Config::vertex_descriptor v, |
| const typename Config::edge_property_type& p, |
| undirected_graph_helper<Config>& 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<graph_type&>(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 <class Config> |
| inline std::pair<typename Config::edge_descriptor, bool> |
| add_edge(typename Config::vertex_descriptor u, |
| typename Config::vertex_descriptor v, |
| undirected_graph_helper<Config>& g_) |
| { |
| typename Config::edge_property_type p; |
| return add_edge(u, v, p, g_); |
| } |
| |
| // O(1) |
| template <class Config> |
| inline typename Config::degree_size_type |
| degree(typename Config::vertex_descriptor u, |
| const undirected_graph_helper<Config>& g_) |
| { |
| typedef typename Config::graph_type Graph; |
| const Graph& g = static_cast<const Graph&>(g_); |
| return out_degree(u, g); |
| } |
| |
| template <class Config> |
| inline std::pair<typename Config::in_edge_iterator, |
| typename Config::in_edge_iterator> |
| in_edges(typename Config::vertex_descriptor u, |
| const undirected_graph_helper<Config>& g_) |
| { |
| typedef typename Config::graph_type Graph; |
| const Graph& cg = static_cast<const Graph&>(g_); |
| Graph& g = const_cast<Graph&>(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 <class Config> |
| inline typename Config::degree_size_type |
| in_degree(typename Config::vertex_descriptor u, |
| const undirected_graph_helper<Config>& 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 <class Config> |
| struct bidirectional_graph_helper |
| : public directed_edges_helper<Config> { |
| typedef bidir_adj_list_traversal_tag traversal_category; |
| }; |
| |
| // Had to make these non-members to avoid accidental instantiation |
| // on SGI MIPSpro C++ |
| template <class C> |
| inline typename C::InEdgeList& |
| in_edge_list(bidirectional_graph_helper<C>&, |
| typename C::vertex_descriptor v) |
| { |
| typename C::stored_vertex* sv = (typename C::stored_vertex*)v; |
| return sv->m_in_edges; |
| } |
| template <class C> |
| inline const typename C::InEdgeList& |
| in_edge_list(const bidirectional_graph_helper<C>&, |
| typename C::vertex_descriptor v) { |
| typename C::stored_vertex* sv = (typename C::stored_vertex*)v; |
| return sv->m_in_edges; |
| } |
| |
| template <class Predicate, class Config> |
| inline void |
| remove_edge_if(Predicate pred, bidirectional_graph_helper<Config>& g_) |
| { |
| typedef typename Config::global_edgelist_selector EdgeListS; |
| BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value)); |
| |
| typedef typename Config::graph_type graph_type; |
| graph_type& g = static_cast<graph_type&>(g_); |
| typename Config::edge_iterator ei, ei_end, next; |
| boost::tie(ei, ei_end) = edges(g); |
| for (next = ei; ei != ei_end; ei = next) { |
| ++next; |
| if (pred(*ei)) |
| remove_edge(*ei, g); |
| } |
| } |
| |
| template <class Config> |
| inline std::pair<typename Config::in_edge_iterator, |
| typename Config::in_edge_iterator> |
| in_edges(typename Config::vertex_descriptor u, |
| const bidirectional_graph_helper<Config>& g_) |
| { |
| typedef typename Config::graph_type graph_type; |
| const graph_type& cg = static_cast<const graph_type&>(g_); |
| graph_type& g = const_cast<graph_type&>(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 <class Config> |
| inline std::pair<typename Config::edge_iterator, |
| typename Config::edge_iterator> |
| edges(const bidirectional_graph_helper<Config>& g_) |
| { |
| typedef typename Config::graph_type graph_type; |
| typedef typename Config::edge_iterator edge_iterator; |
| const graph_type& cg = static_cast<const graph_type&>(g_); |
| graph_type& g = const_cast<graph_type&>(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 <class Config> |
| struct bidirectional_graph_helper_with_property |
| : public bidirectional_graph_helper<Config> |
| { |
| typedef typename Config::graph_type graph_type; |
| typedef typename Config::out_edge_iterator out_edge_iterator; |
| |
| std::pair<out_edge_iterator, out_edge_iterator> |
| get_parallel_edge_sublist(typename Config::edge_descriptor e, |
| const graph_type& g, |
| void*) |
| { return out_edges(source(e, g), g); } |
| |
| std::pair<out_edge_iterator, out_edge_iterator> |
| 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<out_edge_iterator, out_edge_iterator> |
| get_parallel_edge_sublist(typename Config::edge_descriptor e, |
| const graph_type& g, |
| multisetS*) |
| { return edge_range(source(e, g), target(e, g), g); } |
| |
| std::pair<out_edge_iterator, out_edge_iterator> |
| 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); } |
| |
| // 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<EdgeListS, vecS>::value)); |
| |
| graph_type& g = static_cast<graph_type&>(*this); |
| |
| typedef typename Config::edgelist_selector OutEdgeListS; |
| |
| std::pair<out_edge_iterator, out_edge_iterator> 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<EdgeListS, vecS>::value)); |
| |
| typedef typename Config::graph_type graph_type; |
| graph_type& g = static_cast<graph_type&>(*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 <class Config> |
| inline void |
| remove_edge(typename Config::vertex_descriptor u, |
| typename Config::vertex_descriptor v, |
| bidirectional_graph_helper_with_property<Config>& g_) |
| { |
| typedef typename Config::global_edgelist_selector EdgeListS; |
| BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value)); |
| |
| typedef typename Config::graph_type graph_type; |
| graph_type& g = static_cast<graph_type&>(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 <class EdgeOrIter, class Config> |
| inline void |
| remove_edge(EdgeOrIter e, |
| bidirectional_graph_helper_with_property<Config>& g_) |
| { |
| typedef typename Config::global_edgelist_selector EdgeListS; |
| BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value)); |
| |
| g_.remove_edge(e); |
| } |
| |
| template <class Config, class Predicate> |
| inline void |
| remove_out_edge_if(typename Config::vertex_descriptor u, Predicate pred, |
| bidirectional_graph_helper_with_property<Config>& g_) |
| { |
| typedef typename Config::global_edgelist_selector EdgeListS; |
| BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value)); |
| |
| typedef typename Config::graph_type graph_type; |
| typedef typename Config::OutEdgeList::value_type::property_type PropT; |
| graph_type& g = static_cast<graph_type&>(g_); |
| |
| typedef typename Config::EdgeIter EdgeIter; |
| typedef std::vector<EdgeIter> 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 (boost::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; |
| boost::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 <class Config, class Predicate> |
| inline void |
| remove_in_edge_if(typename Config::vertex_descriptor v, Predicate pred, |
| bidirectional_graph_helper_with_property<Config>& g_) |
| { |
| typedef typename Config::global_edgelist_selector EdgeListS; |
| BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value)); |
| |
| typedef typename Config::graph_type graph_type; |
| typedef typename Config::OutEdgeList::value_type::property_type PropT; |
| graph_type& g = static_cast<graph_type&>(g_); |
| |
| typedef typename Config::EdgeIter EdgeIter; |
| typedef std::vector<EdgeIter> 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 (boost::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; |
| boost::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 <class Config> |
| inline typename Config::edges_size_type |
| num_edges(const bidirectional_graph_helper_with_property<Config>& g_) |
| { |
| typedef typename Config::graph_type graph_type; |
| const graph_type& g = static_cast<const graph_type&>(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 <class Config> |
| inline void |
| clear_vertex(typename Config::vertex_descriptor u, |
| bidirectional_graph_helper_with_property<Config>& g_) |
| { |
| typedef typename Config::global_edgelist_selector EdgeListS; |
| BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value)); |
| |
| typedef typename Config::graph_type graph_type; |
| typedef typename Config::edge_parallel_category Cat; |
| graph_type& g = static_cast<graph_type&>(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 <class Config> |
| inline void |
| clear_out_edges(typename Config::vertex_descriptor u, |
| bidirectional_graph_helper_with_property<Config>& g_) |
| { |
| typedef typename Config::global_edgelist_selector EdgeListS; |
| BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value)); |
| |
| typedef typename Config::graph_type graph_type; |
| typedef typename Config::edge_parallel_category Cat; |
| graph_type& g = static_cast<graph_type&>(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 <class Config> |
| inline void |
| clear_in_edges(typename Config::vertex_descriptor u, |
| bidirectional_graph_helper_with_property<Config>& g_) |
| { |
| typedef typename Config::global_edgelist_selector EdgeListS; |
| BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value)); |
| |
| typedef typename Config::graph_type graph_type; |
| typedef typename Config::edge_parallel_category Cat; |
| graph_type& g = static_cast<graph_type&>(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 <class Config> |
| inline std::pair<typename Config::edge_descriptor, bool> |
| add_edge(typename Config::vertex_descriptor u, |
| typename Config::vertex_descriptor v, |
| const typename Config::edge_property_type& p, |
| bidirectional_graph_helper_with_property<Config>& g_) |
| { |
| typedef typename Config::graph_type graph_type; |
| graph_type& g = static_cast<graph_type&>(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 <class Config> |
| inline std::pair<typename Config::edge_descriptor, bool> |
| add_edge(typename Config::vertex_descriptor u, |
| typename Config::vertex_descriptor v, |
| bidirectional_graph_helper_with_property<Config>& g_) |
| { |
| typename Config::edge_property_type p; |
| return add_edge(u, v, p, g_); |
| } |
| // O(1) |
| template <class Config> |
| inline typename Config::degree_size_type |
| degree(typename Config::vertex_descriptor u, |
| const bidirectional_graph_helper_with_property<Config>& g_) |
| { |
| typedef typename Config::graph_type graph_type; |
| const graph_type& g = static_cast<const graph_type&>(g_); |
| return in_degree(u, g) + out_degree(u, g); |
| } |
| |
| //========================================================================= |
| // Adjacency List Helper Class |
| |
| template <class Config, class Base> |
| 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; |
| }; |
| |
| template <class Config, class Base> |
| inline std::pair<typename Config::adjacency_iterator, |
| typename Config::adjacency_iterator> |
| adjacent_vertices(typename Config::vertex_descriptor u, |
| const adj_list_helper<Config, Base>& g_) |
| { |
| typedef typename Config::graph_type AdjList; |
| const AdjList& cg = static_cast<const AdjList&>(g_); |
| AdjList& g = const_cast<AdjList&>(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 <class Config, class Base> |
| inline std::pair<typename Config::inv_adjacency_iterator, |
| typename Config::inv_adjacency_iterator> |
| inv_adjacent_vertices(typename Config::vertex_descriptor u, |
| const adj_list_helper<Config, Base>& g_) |
| { |
| typedef typename Config::graph_type AdjList; |
| const AdjList& cg = static_cast<const AdjList&>(g_); |
| AdjList& g = const_cast<AdjList&>(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 <class Config, class Base> |
| inline std::pair<typename Config::out_edge_iterator, |
| typename Config::out_edge_iterator> |
| out_edges(typename Config::vertex_descriptor u, |
| const adj_list_helper<Config, Base>& g_) |
| { |
| typedef typename Config::graph_type AdjList; |
| typedef typename Config::out_edge_iterator out_edge_iterator; |
| const AdjList& cg = static_cast<const AdjList&>(g_); |
| AdjList& g = const_cast<AdjList&>(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 <class Config, class Base> |
| inline std::pair<typename Config::vertex_iterator, |
| typename Config::vertex_iterator> |
| vertices(const adj_list_helper<Config, Base>& g_) |
| { |
| typedef typename Config::graph_type AdjList; |
| const AdjList& cg = static_cast<const AdjList&>(g_); |
| AdjList& g = const_cast<AdjList&>(cg); |
| return std::make_pair( g.vertex_set().begin(), g.vertex_set().end() ); |
| } |
| template <class Config, class Base> |
| inline typename Config::vertices_size_type |
| num_vertices(const adj_list_helper<Config, Base>& g_) |
| { |
| typedef typename Config::graph_type AdjList; |
| const AdjList& g = static_cast<const AdjList&>(g_); |
| return g.vertex_set().size(); |
| } |
| template <class Config, class Base> |
| inline typename Config::degree_size_type |
| out_degree(typename Config::vertex_descriptor u, |
| const adj_list_helper<Config, Base>& g_) |
| { |
| typedef typename Config::graph_type AdjList; |
| const AdjList& g = static_cast<const AdjList&>(g_); |
| return g.out_edge_list(u).size(); |
| } |
| template <class Config, class Base> |
| inline std::pair<typename Config::edge_descriptor, bool> |
| edge(typename Config::vertex_descriptor u, |
| typename Config::vertex_descriptor v, |
| const adj_list_helper<Config, Base>& g_) |
| { |
| typedef typename Config::graph_type Graph; |
| typedef typename Config::StoredEdge StoredEdge; |
| const Graph& cg = static_cast<const Graph&>(g_); |
| typedef typename Config::out_edge_iterator out_edge_iterator; |
| const typename Config::OutEdgeList& el = cg.out_edge_list(u); |
| typename Config::OutEdgeList::const_iterator it = graph_detail:: |
| find(el, StoredEdge(v)); |
| return std::make_pair( |
| typename Config::edge_descriptor |
| (u, v, (it == el.end() ? 0 : &(*it).get_property())), |
| (it != el.end())); |
| } |
| |
| template <class Config, class Base> |
| inline std::pair<typename Config::out_edge_iterator, |
| typename Config::out_edge_iterator> |
| edge_range(typename Config::vertex_descriptor u, |
| typename Config::vertex_descriptor v, |
| const adj_list_helper<Config, Base>& g_) |
| { |
| typedef typename Config::graph_type Graph; |
| typedef typename Config::StoredEdge StoredEdge; |
| const Graph& cg = static_cast<const Graph&>(g_); |
| Graph& g = const_cast<Graph&>(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; |
| boost::tie(first, last) = graph_detail:: |
| equal_range(el, StoredEdge(v, fake_edge_container.end(), |
| &fake_edge_container)); |
| return std::make_pair(out_edge_iterator(first, u), |
| out_edge_iterator(last, u)); |
| } |
| |
| template <class Config> |
| inline typename Config::degree_size_type |
| in_degree(typename Config::vertex_descriptor u, |
| const directed_edges_helper<Config>& g_) |
| { |
| typedef typename Config::graph_type Graph; |
| const Graph& cg = static_cast<const Graph&>(g_); |
| Graph& g = const_cast<Graph&>(cg); |
| return in_edge_list(g, u).size(); |
| } |
| |
| namespace detail { |
| template <class Config, class Base, class Property> |
| inline |
| typename boost::property_map<typename Config::graph_type, |
| Property>::type |
| get_dispatch(adj_list_helper<Config,Base>&, Property, |
| boost::edge_property_tag) { |
| typedef typename Config::graph_type Graph; |
| typedef typename boost::property_map<Graph, Property>::type PA; |
| return PA(); |
| } |
| template <class Config, class Base, class Property> |
| inline |
| typename boost::property_map<typename Config::graph_type, |
| Property>::const_type |
| get_dispatch(const adj_list_helper<Config,Base>&, Property, |
| boost::edge_property_tag) { |
| typedef typename Config::graph_type Graph; |
| typedef typename boost::property_map<Graph, Property>::const_type PA; |
| return PA(); |
| } |
| |
| template <class Config, class Base, class Property> |
| inline |
| typename boost::property_map<typename Config::graph_type, |
| Property>::type |
| get_dispatch(adj_list_helper<Config,Base>& g, Property, |
| boost::vertex_property_tag) { |
| typedef typename Config::graph_type Graph; |
| typedef typename boost::property_map<Graph, Property>::type PA; |
| return PA(&static_cast<Graph&>(g)); |
| } |
| template <class Config, class Base, class Property> |
| inline |
| typename boost::property_map<typename Config::graph_type, |
| Property>::const_type |
| get_dispatch(const adj_list_helper<Config, Base>& g, Property, |
| boost::vertex_property_tag) { |
| typedef typename Config::graph_type Graph; |
| typedef typename boost::property_map<Graph, Property>::const_type PA; |
| const Graph& cg = static_cast<const Graph&>(g); |
| return PA(&cg); |
| } |
| |
| } // namespace detail |
| |
| // Implementation of the PropertyGraph interface |
| template <class Config, class Base, class Property> |
| inline |
| typename boost::property_map<typename Config::graph_type, Property>::type |
| get(Property p, adj_list_helper<Config, Base>& g) { |
| typedef typename property_kind<Property>::type Kind; |
| return detail::get_dispatch(g, p, Kind()); |
| } |
| template <class Config, class Base, class Property> |
| inline |
| typename boost::property_map<typename Config::graph_type, |
| Property>::const_type |
| get(Property p, const adj_list_helper<Config, Base>& g) { |
| typedef typename property_kind<Property>::type Kind; |
| return detail::get_dispatch(g, p, Kind()); |
| } |
| |
| template <class Config, class Base, class Property, class Key> |
| inline |
| typename boost::property_traits< |
| typename boost::property_map<typename Config::graph_type, |
| Property>::type |
| >::reference |
| get(Property p, adj_list_helper<Config, Base>& g, const Key& key) { |
| return get(get(p, g), key); |
| } |
| |
| template <class Config, class Base, class Property, class Key> |
| inline |
| typename boost::property_traits< |
| typename boost::property_map<typename Config::graph_type, |
| Property>::const_type |
| >::reference |
| get(Property p, const adj_list_helper<Config, Base>& g, const Key& key) { |
| return get(get(p, g), key); |
| } |
| |
| template <class Config, class Base, class Property, class Key,class Value> |
| inline void |
| put(Property p, adj_list_helper<Config, Base>& g, |
| const Key& key, const Value& value) |
| { |
| typedef typename Config::graph_type Graph; |
| typedef typename boost::property_map<Graph, Property>::type Map; |
| Map pmap = get(p, static_cast<Graph&>(g)); |
| put(pmap, key, value); |
| } |
| |
| |
| //========================================================================= |
| // Generalize Adjacency List Implementation |
| |
| struct adj_list_tag { }; |
| |
| template <class Derived, class Config, class Base> |
| class adj_list_impl |
| : public adj_list_helper<Config, Base> |
| { |
| 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<Derived&>(*this)); |
| } |
| template <class EdgeIterator> |
| 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<Derived&>(*this)); |
| |
| while (first != last) { |
| add_edge(v[(*first).first], v[(*first).second], *this); |
| ++first; |
| } |
| delete [] v; |
| } |
| template <class EdgeIterator, class EdgePropertyIterator> |
| 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<Derived&>(*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<const Derived&>(x_); |
| |
| // Would be better to have a constant time way to get from |
| // vertices in x to the corresponding vertices in *this. |
| std::map<stored_vertex*,stored_vertex*> vertex_map; |
| |
| // Copy the stored vertex objects by adding each vertex |
| // and copying its property object. |
| vertex_iterator vi, vi_end; |
| for (boost::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 (boost::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); |
| boost::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 <class Derived, class Config, class Base> |
| inline typename Config::vertex_descriptor |
| add_vertex(adj_list_impl<Derived, Config, Base>& g_) |
| { |
| Derived& g = static_cast<Derived&>(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; |
| g.added_vertex(v); |
| return v; |
| } |
| // O(1) |
| template <class Derived, class Config, class Base> |
| inline typename Config::vertex_descriptor |
| add_vertex(const typename Config::vertex_property_type& p, |
| adj_list_impl<Derived, Config, Base>& g_) |
| { |
| typedef typename Config::vertex_descriptor vertex_descriptor; |
| Derived& g = static_cast<Derived&>(g_); |
| if (optional<vertex_descriptor> v |
| = g.vertex_by_property(get_property_value(p, vertex_bundle))) |
| return *v; |
| |
| 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; |
| g.added_vertex(v); |
| return v; |
| } |
| // O(1) |
| template <class Derived, class Config, class Base> |
| inline void remove_vertex(typename Config::vertex_descriptor u, |
| adj_list_impl<Derived, Config, Base>& g_) |
| { |
| typedef typename Config::stored_vertex stored_vertex; |
| Derived& g = static_cast<Derived&>(g_); |
| g.removing_vertex(u); |
| stored_vertex* su = (stored_vertex*)u; |
| g.m_vertices.erase(su->m_position); |
| delete su; |
| } |
| // O(V) |
| template <class Derived, class Config, class Base> |
| inline typename Config::vertex_descriptor |
| vertex(typename Config::vertices_size_type n, |
| const adj_list_impl<Derived, Config, Base>& g_) |
| { |
| const Derived& g = static_cast<const Derived&>(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 <class Graph, class vertex_descriptor> |
| 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 <class Graph, class vertex_descriptor> |
| 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<EdgeListS, vecS>::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 <class Graph, class vertex_descriptor> |
| 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<EdgeListS, vecS>::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 <class EdgeList, class vertex_descriptor> |
| 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 <class EdgeList, class vertex_descriptor> |
| 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 Graph, class Config, class Base> |
| class vec_adj_list_impl |
| : public adj_list_helper<Config, Base> |
| { |
| 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<vertex_descriptor>::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 <class EdgeIterator> |
| 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<Graph&>(*this)); |
| ++first; |
| } |
| } |
| template <class EdgeIterator, class EdgePropertyIterator> |
| 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<Graph&>(*this)); |
| ++first; |
| ++ep_iter; |
| } |
| } |
| |
| // protected: |
| inline boost::integer_range<vertex_descriptor> vertex_set() const { |
| return boost::integer_range<vertex_descriptor>(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<const Graph&>(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 (boost::tie(ei, ei_end) = edges(x); ei != ei_end; ++ei) { |
| edge_descriptor e; |
| bool inserted; |
| boost::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 <class G, class C, class B> |
| inline typename C::InEdgeList& |
| in_edge_list(vec_adj_list_impl<G,C,B>& g, |
| typename C::vertex_descriptor v) { |
| return g.m_vertices[v].m_in_edges; |
| } |
| template <class G, class C, class B> |
| inline const typename C::InEdgeList& |
| in_edge_list(const vec_adj_list_impl<G,C,B>& g, |
| typename C::vertex_descriptor v) { |
| return g.m_vertices[v].m_in_edges; |
| } |
| |
| // O(1) |
| template <class Graph, class Config, class Base> |
| inline typename Config::vertex_descriptor |
| add_vertex(vec_adj_list_impl<Graph, Config, Base>& g_) { |
| Graph& g = static_cast<Graph&>(g_); |
| g.m_vertices.resize(g.m_vertices.size() + 1); |
| g.added_vertex(g.m_vertices.size() - 1); |
| return g.m_vertices.size() - 1; |
| } |
| |
| template <class Graph, class Config, class Base> |
| inline typename Config::vertex_descriptor |
| add_vertex(const typename Config::vertex_property_type& p, |
| vec_adj_list_impl<Graph, Config, Base>& g_) { |
| typedef typename Config::vertex_descriptor vertex_descriptor; |
| Graph& g = static_cast<Graph&>(g_); |
| if (optional<vertex_descriptor> v |
| = g.vertex_by_property(get_property_value(p, vertex_bundle))) |
| return *v; |
| typedef typename Config::stored_vertex stored_vertex; |
| g.m_vertices.push_back(stored_vertex(p)); |
| g.added_vertex(g.m_vertices.size() - 1); |
| 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 <class Graph, class Config, class Base> |
| inline std::pair<typename Config::edge_descriptor, bool> |
| add_edge(typename Config::vertex_descriptor u, |
| typename Config::vertex_descriptor v, |
| const typename Config::edge_property_type& p, |
| vec_adj_list_impl<Graph, Config, Base>& 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<Config, Base>& g = g_; |
| return add_edge(u, v, p, g); |
| } |
| template <class Graph, class Config, class Base> |
| inline std::pair<typename Config::edge_descriptor, bool> |
| add_edge(typename Config::vertex_descriptor u, |
| typename Config::vertex_descriptor v, |
| vec_adj_list_impl<Graph, Config, Base>& g_) |
| { |
| typename Config::edge_property_type p; |
| return add_edge(u, v, p, g_); |
| } |
| |
| |
| // O(V + E) |
| template <class Graph, class Config, class Base> |
| inline void remove_vertex(typename Config::vertex_descriptor v, |
| vec_adj_list_impl<Graph, Config, Base>& g_) |
| { |
| typedef typename Config::directed_category Cat; |
| Graph& g = static_cast<Graph&>(g_); |
| g.removing_vertex(v); |
| detail::remove_vertex_dispatch(g, v, Cat()); |
| } |
| // O(1) |
| template <class Graph, class Config, class Base> |
| inline typename Config::vertex_descriptor |
| vertex(typename Config::vertices_size_type n, |
| const vec_adj_list_impl<Graph, Config, Base>&) |
| { |
| return n; |
| } |
| |
| |
| namespace detail { |
| |
| //========================================================================= |
| // Adjacency List Generator |
| |
| template <class Graph, class VertexListS, class OutEdgeListS, |
| class DirectedS, class VertexProperty, class EdgeProperty, |
| class GraphProperty, class EdgeListS> |
| struct adj_list_gen |
| { |
| typedef typename detail::is_random_access<VertexListS>::type |
| is_rand_access; |
| typedef typename has_property<EdgeProperty>::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<OutEdgeListS, VertexListS, DirectedS> |
| 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<VertexListS, |
| vertex_ptr>::type SeqVertexList; |
| typedef boost::integer_range<vertex_descriptor> RandVertexList; |
| typedef typename mpl::if_<is_rand_access, |
| RandVertexList, SeqVertexList>::type VertexList; |
| |
| typedef typename VertexList::iterator vertex_iterator; |
| |
| // EdgeContainer and StoredEdge |
| |
| typedef typename container_gen<EdgeListS, |
| list_edge<vertex_descriptor, EdgeProperty> >::type EdgeContainer; |
| |
| typedef typename mpl::and_<DirectedT, |
| typename mpl::not_<BidirectionalT>::type >::type on_edge_storage; |
| |
| typedef typename mpl::if_<on_edge_storage, |
| std::size_t, typename EdgeContainer::size_type |
| >::type edges_size_type; |
| |
| typedef typename EdgeContainer::iterator EdgeIter; |
| |
| typedef typename detail::is_random_access<EdgeListS>::type is_edge_ra; |
| |
| typedef typename mpl::if_<on_edge_storage, |
| stored_edge_property<vertex_descriptor, EdgeProperty>, |
| typename mpl::if_<is_edge_ra, |
| stored_ra_edge_iter<vertex_descriptor, EdgeContainer, EdgeProperty>, |
| stored_edge_iter<vertex_descriptor, EdgeIter, EdgeProperty> |
| >::type |
| >::type StoredEdge; |
| |
| // Adjacency Types |
| |
| typedef typename container_gen<OutEdgeListS, StoredEdge>::type |
| OutEdgeList; |
| typedef typename OutEdgeList::size_type degree_size_type; |
| typedef typename OutEdgeList::iterator OutEdgeIter; |
| |
| typedef boost::detail::iterator_traits<OutEdgeIter> OutEdgeIterTraits; |
| typedef typename OutEdgeIterTraits::iterator_category OutEdgeIterCat; |
| typedef typename OutEdgeIterTraits::difference_type OutEdgeIterDiff; |
| |
| typedef out_edge_iter< |
| OutEdgeIter, vertex_descriptor, edge_descriptor, OutEdgeIterDiff |
| > out_edge_iterator; |
| |
| typedef typename adjacency_iterator_generator<graph_type, |
| vertex_descriptor, out_edge_iterator>::type adjacency_iterator; |
| |
| typedef OutEdgeList InEdgeList; |
| typedef OutEdgeIter InEdgeIter; |
| typedef OutEdgeIterCat InEdgeIterCat; |
| typedef OutEdgeIterDiff InEdgeIterDiff; |
| |
| typedef in_edge_iter< |
| InEdgeIter, vertex_descriptor, edge_descriptor, InEdgeIterDiff |
| > in_edge_iterator; |
| |
| typedef typename inv_adjacency_iterator_generator<graph_type, |
| vertex_descriptor, in_edge_iterator>::type inv_adjacency_iterator; |
| |
| // Edge Iterator |
| |
| typedef boost::detail::iterator_traits<EdgeIter> EdgeIterTraits; |
| typedef typename EdgeIterTraits::iterator_category EdgeIterCat; |
| typedef typename EdgeIterTraits::difference_type EdgeIterDiff; |
| |
| typedef undirected_edge_iter< |
| EdgeIter |
| , edge_descriptor |
| , EdgeIterDiff |
| > UndirectedEdgeIter; // also used for bidirectional |
| |
| typedef adj_list_edge_iterator<vertex_iterator, out_edge_iterator, |
| graph_type> DirectedEdgeIter; |
| |
| typedef typename mpl::if_<on_edge_storage, |
| DirectedEdgeIter, UndirectedEdgeIter>::type edge_iterator; |
| |
| // stored_vertex and StoredVertexList |
| typedef typename container_gen<VertexListS, vertex_ptr>::type |
| SeqStoredVertexList; |
| struct seq_stored_vertex { |
| seq_stored_vertex() { } |
| seq_stored_vertex(const VertexProperty& p) : m_property(p) { } |
| OutEdgeList m_out_edges; |
| VertexProperty m_property; |
| typename SeqStoredVertexList::iterator m_position; |
| }; |
| struct bidir_seq_stored_vertex { |
| bidir_seq_stored_vertex() { } |
| bidir_seq_stored_vertex(const VertexProperty& p) : m_property(p) { } |
| OutEdgeList m_out_edges; |
| InEdgeList m_in_edges; |
| VertexProperty m_property; |
| typename SeqStoredVertexList::iterator m_position; |
| }; |
| struct rand_stored_vertex { |
| rand_stored_vertex() { } |
| rand_stored_vertex(const VertexProperty& p) : m_property(p) { } |
| OutEdgeList m_out_edges; |
| VertexProperty m_property; |
| }; |
| struct bidir_rand_stored_vertex { |
| bidir_rand_stored_vertex() { } |
| bidir_rand_stored_vertex(const VertexProperty& p) : m_property(p) { } |
| OutEdgeList m_out_edges; |
| InEdgeList m_in_edges; |
| VertexProperty m_property; |
| }; |
| typedef typename mpl::if_<is_rand_access, |
| typename mpl::if_<BidirectionalT, |
| bidir_rand_stored_vertex, rand_stored_vertex>::type, |
| typename mpl::if_<BidirectionalT, |
| bidir_seq_stored_vertex, seq_stored_vertex>::type |
| >::type StoredVertex; |
| struct stored_vertex : public StoredVertex { |
| stored_vertex() { } |
| stored_vertex(const VertexProperty& p) : StoredVertex(p) { } |
| }; |
| |
| typedef typename container_gen<VertexListS, stored_vertex>::type |
| RandStoredVertexList; |
| typedef typename mpl::if_< is_rand_access, |
| RandStoredVertexList, SeqStoredVertexList>::type StoredVertexList; |
| }; // end of config |
| |
| |
| typedef typename mpl::if_<BidirectionalT, |
| bidirectional_graph_helper_with_property<config>, |
| typename mpl::if_<DirectedT, |
| directed_graph_helper<config>, |
| undirected_graph_helper<config> |
| >::type |
| >::type DirectedHelper; |
| |
| typedef typename mpl::if_<is_rand_access, |
| vec_adj_list_impl<Graph, config, DirectedHelper>, |
| adj_list_impl<Graph, config, DirectedHelper> |
| >::type type; |
| |
| }; |
| |
| } // namespace detail |
| |
| //========================================================================= |
| // Vertex Property Maps |
| |
| template <class Graph, class ValueType, class Reference, class Tag> |
| struct adj_list_vertex_property_map |
| : public boost::put_get_helper< |
| Reference, |
| adj_list_vertex_property_map<Graph, ValueType, Reference, Tag> |
| > |
| { |
| typedef typename Graph::stored_vertex StoredVertex; |
| typedef ValueType value_type; |
| typedef Reference reference; |
| typedef typename Graph::vertex_descriptor key_type; |
| typedef boost::lvalue_property_map_tag category; |
| inline adj_list_vertex_property_map() { } |
| inline adj_list_vertex_property_map(const Graph*) { } |
| inline Reference operator[](key_type v) const { |
| StoredVertex* sv = (StoredVertex*)v; |
| return get_property_value(sv->m_property, Tag()); |
| } |
| inline Reference operator()(key_type v) const { |
| return this->operator[](v); |
| } |
| }; |
| |
| template <class Graph, class Property, class PropRef> |
| struct adj_list_vertex_all_properties_map |
| : public boost::put_get_helper<PropRef, |
| adj_list_vertex_all_properties_map<Graph, Property, PropRef> |
| > |
| { |
| typedef typename Graph::stored_vertex StoredVertex; |
| typedef Property value_type; |
| typedef PropRef reference; |
| typedef typename Graph::vertex_descriptor key_type; |
| typedef boost::lvalue_property_map_tag category; |
| inline adj_list_vertex_all_properties_map() { } |
| inline adj_list_vertex_all_properties_map(const Graph*) { } |
| inline PropRef operator[](key_type v) const { |
| StoredVertex* sv = (StoredVertex*)v; |
| return sv->m_property; |
| } |
| inline PropRef operator()(key_type v) const { |
| return this->operator[](v); |
| } |
| }; |
| |
| template <class Graph, class GraphPtr, class ValueType, class Reference, |
| class Tag> |
| struct vec_adj_list_vertex_property_map |
| : public boost::put_get_helper< |
| Reference, |
| vec_adj_list_vertex_property_map<Graph,GraphPtr,ValueType,Reference, |
| Tag> |
| > |
| { |
| typedef ValueType value_type; |
| typedef Reference reference; |
| typedef typename boost::graph_traits<Graph>::vertex_descriptor key_type; |
| typedef boost::lvalue_property_map_tag category; |
| vec_adj_list_vertex_property_map() { } |
| vec_adj_list_vertex_property_map(GraphPtr g) : m_g(g) { } |
| inline Reference operator[](key_type v) const { |
| return get_property_value(m_g->m_vertices[v].m_property, Tag()); |
| } |
| inline Reference operator()(key_type v) const { |
| return this->operator[](v); |
| } |
| GraphPtr m_g; |
| }; |
| |
| template <class Graph, class GraphPtr, class Property, class PropertyRef> |
| struct vec_adj_list_vertex_all_properties_map |
| : public boost::put_get_helper<PropertyRef, |
| vec_adj_list_vertex_all_properties_map<Graph,GraphPtr,Property, |
| PropertyRef> |
| > |
| { |
| typedef Property value_type; |
| typedef PropertyRef reference; |
| typedef typename boost::graph_traits<Graph>::vertex_descriptor key_type; |
| typedef boost::lvalue_property_map_tag category; |
| vec_adj_list_vertex_all_properties_map() { } |
| vec_adj_list_vertex_all_properties_map(GraphPtr g) : m_g(g) { } |
| inline PropertyRef operator[](key_type v) const { |
| return m_g->m_vertices[v].m_property; |
| } |
| inline PropertyRef operator()(key_type v) const { |
| return this->operator[](v); |
| } |
| GraphPtr m_g; |
| }; |
| |
| struct adj_list_any_vertex_pa { |
| template <class Tag, class Graph, class Property> |
| struct bind_ { |
| typedef typename property_value<Property, Tag>::type value_type; |
| typedef value_type& reference; |
| typedef const value_type& const_reference; |
| |
| typedef adj_list_vertex_property_map |
| <Graph, value_type, reference, Tag> type; |
| typedef adj_list_vertex_property_map |
| <Graph, value_type, const_reference, Tag> const_type; |
| }; |
| }; |
| struct adj_list_all_vertex_pa { |
| template <class Tag, class Graph, class Property> |
| struct bind_ { |
| typedef typename Graph::vertex_descriptor Vertex; |
| typedef adj_list_vertex_all_properties_map<Graph,Property, |
| Property&> type; |
| typedef adj_list_vertex_all_properties_map<Graph,Property, |
| const Property&> const_type; |
| }; |
| }; |
| |
| template <class Property, class Vertex> |
| struct vec_adj_list_vertex_id_map |
| : public boost::put_get_helper< |
| Vertex, vec_adj_list_vertex_id_map<Property, Vertex> |
| > |
| { |
| typedef Vertex value_type; |
| typedef Vertex key_type; |
| typedef Vertex reference; |
| typedef boost::readable_property_map_tag category; |
| inline vec_adj_list_vertex_id_map() { } |
| template <class Graph> |
| inline vec_adj_list_vertex_id_map(const Graph&) { } |
| inline value_type operator[](key_type v) const { return v; } |
| inline value_type operator()(key_type v) const { return v; } |
| }; |
| |
| struct vec_adj_list_any_vertex_pa { |
| template <class Tag, class Graph, class Property> |
| struct bind_ { |
| typedef typename property_value<Property, Tag>::type value_type; |
| typedef value_type& reference; |
| typedef const value_type& const_reference; |
| |
| typedef vec_adj_list_vertex_property_map |
| <Graph, Graph*, value_type, reference, Tag> type; |
| typedef vec_adj_list_vertex_property_map |
| <Graph, const Graph*, value_type, const_reference, Tag> const_type; |
| }; |
| }; |
| struct vec_adj_list_id_vertex_pa { |
| template <class Tag, class Graph, class Property> |
| struct bind_ { |
| typedef typename Graph::vertex_descriptor Vertex; |
| typedef vec_adj_list_vertex_id_map<Property, Vertex> type; |
| typedef vec_adj_list_vertex_id_map<Property, Vertex> const_type; |
| }; |
| }; |
| struct vec_adj_list_all_vertex_pa { |
| template <class Tag, class Graph, class Property> |
| struct bind_ { |
| typedef typename Graph::vertex_descriptor Vertex; |
| typedef vec_adj_list_vertex_all_properties_map |
| <Graph, Graph*, Property, Property&> type; |
| typedef vec_adj_list_vertex_all_properties_map |
| <Graph, const Graph*, Property, const Property&> const_type; |
| }; |
| }; |
| namespace detail { |
| template <class Tag> |
| struct adj_list_choose_vertex_pa_helper { |
| typedef adj_list_any_vertex_pa type; |
| }; |
| template <> |
| struct adj_list_choose_vertex_pa_helper<vertex_all_t> { |
| typedef adj_list_all_vertex_pa type; |
| }; |
| template <class Tag, class Graph, class Property> |
| struct adj_list_choose_vertex_pa { |
| typedef typename adj_list_choose_vertex_pa_helper<Tag>::type Helper; |
| typedef typename Helper::template bind_<Tag,Graph,Property> Bind; |
| typedef typename Bind::type type; |
| typedef typename Bind::const_type const_type; |
| }; |
| |
| |
| template <class Tag> |
| struct vec_adj_list_choose_vertex_pa_helper { |
| typedef vec_adj_list_any_vertex_pa type; |
| }; |
| template <> |
| struct vec_adj_list_choose_vertex_pa_helper<vertex_index_t> { |
| typedef vec_adj_list_id_vertex_pa type; |
| }; |
| template <> |
| struct vec_adj_list_choose_vertex_pa_helper<vertex_all_t> { |
| typedef vec_adj_list_all_vertex_pa type; |
| }; |
| template <class Tag, class Graph, class Property> |
| struct vec_adj_list_choose_vertex_pa { |
| typedef typename vec_adj_list_choose_vertex_pa_helper<Tag>::type Helper; |
| typedef typename Helper::template bind_<Tag,Graph,Property> Bind; |
| typedef typename Bind::type type; |
| typedef typename Bind::const_type const_type; |
| }; |
| } // namespace detail |
| |
| //========================================================================= |
| // Edge Property Map |
| |
| template <class Directed, class Value, class Ref, class Vertex, |
| class Property, class Tag> |
| struct adj_list_edge_property_map |
| : public put_get_helper< |
| Ref, |
| adj_list_edge_property_map<Directed, Value, Ref, Vertex, Property, |
| Tag> |
| > |
| { |
| typedef Value value_type; |
| typedef Ref reference; |
| typedef detail::edge_desc_impl<Directed, Vertex> key_type; |
| typedef boost::lvalue_property_map_tag category; |
| inline Ref operator[](key_type e) const { |
| Property& p = *(Property*)e.get_property(); |
| return get_property_value(p, Tag()); |
| } |
| inline Ref operator()(key_type e) const { |
| return this->operator[](e); |
| } |
| }; |
| |
| template <class Directed, class Property, class PropRef, class PropPtr, |
| class Vertex> |
| struct adj_list_edge_all_properties_map |
| : public put_get_helper<PropRef, |
| adj_list_edge_all_properties_map<Directed, Property, PropRef, |
| PropPtr, Vertex> |
| > |
| { |
| typedef Property value_type; |
| typedef PropRef reference; |
| typedef detail::edge_desc_impl<Directed, Vertex> key_type; |
| typedef boost::lvalue_property_map_tag category; |
| inline PropRef operator[](key_type e) const { |
| return *(PropPtr)e.get_property(); |
| } |
| inline PropRef operator()(key_type e) const { |
| return this->operator[](e); |
| } |
| }; |
| |
| // Edge Property Maps |
| |
| namespace detail { |
| struct adj_list_any_edge_pmap { |
| template <class Graph, class Property, class Tag> |
| struct bind_ { |
| typedef typename property_value<Property,Tag>::type value_type; |
| typedef value_type& reference; |
| typedef const value_type& const_reference; |
| |
| typedef adj_list_edge_property_map |
| <typename Graph::directed_category, value_type, reference, |
| typename Graph::vertex_descriptor,Property,Tag> type; |
| typedef adj_list_edge_property_map |
| <typename Graph::directed_category, value_type, const_reference, |
| typename Graph::vertex_descriptor,const Property, Tag> const_type; |
| }; |
| }; |
| struct adj_list_all_edge_pmap { |
| template <class Graph, class Property, class Tag> |
| struct bind_ { |
| typedef adj_list_edge_all_properties_map |
| <typename Graph::directed_category, Property, Property&, Property*, |
| typename Graph::vertex_descriptor> type; |
| typedef adj_list_edge_all_properties_map |
| <typename Graph::directed_category, Property, const Property&, |
| const Property*, typename Graph::vertex_descriptor> const_type; |
| }; |
| }; |
| |
| template <class Tag> |
| struct adj_list_choose_edge_pmap_helper { |
| typedef adj_list_any_edge_pmap type; |
| }; |
| template <> |
| struct adj_list_choose_edge_pmap_helper<edge_all_t> { |
| typedef adj_list_all_edge_pmap type; |
| }; |
| template <class Tag, class Graph, class Property> |
| struct adj_list_choose_edge_pmap { |
| typedef typename adj_list_choose_edge_pmap_helper<Tag>::type Helper; |
| typedef typename Helper::template bind_<Graph,Property,Tag> Bind; |
| typedef typename Bind::type type; |
| typedef typename Bind::const_type const_type; |
| }; |
| struct adj_list_edge_property_selector { |
| template <class Graph, class Property, class Tag> |
| struct bind_ { |
| typedef adj_list_choose_edge_pmap<Tag,Graph,Property> Choice; |
| typedef typename Choice::type type; |
| typedef typename Choice::const_type const_type; |
| }; |
| }; |
| } // namespace detail |
| |
| template <> |
| struct edge_property_selector<adj_list_tag> { |
| typedef detail::adj_list_edge_property_selector type; |
| }; |
| template <> |
| struct edge_property_selector<vec_adj_list_tag> { |
| typedef detail::adj_list_edge_property_selector type; |
| }; |
| |
| // Vertex Property Maps |
| |
| struct adj_list_vertex_property_selector { |
| template <class Graph, class Property, class Tag> |
| struct bind_ { |
| typedef detail::adj_list_choose_vertex_pa<Tag,Graph,Property> Choice; |
| typedef typename Choice::type type; |
| typedef typename Choice::const_type const_type; |
| }; |
| }; |
| template <> |
| struct vertex_property_selector<adj_list_tag> { |
| typedef adj_list_vertex_property_selector type; |
| }; |
| |
| struct vec_adj_list_vertex_property_selector { |
| template <class Graph, class Property, class Tag> |
| struct bind_ { |
| typedef detail::vec_adj_list_choose_vertex_pa<Tag,Graph,Property> Choice; |
| typedef typename Choice::type type; |
| typedef typename Choice::const_type const_type; |
| }; |
| }; |
| template <> |
| struct vertex_property_selector<vec_adj_list_tag> { |
| typedef vec_adj_list_vertex_property_selector type; |
| }; |
| |
| } // namespace boost |
| |
| #if !defined(BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION) |
| namespace boost { |
| |
| #if BOOST_WORKAROUND( _STLPORT_VERSION, >= 0x500 ) |
| // STLport 5 already defines a hash<void*> specialization. |
| #else |
| template <> |
| struct hash< void* > // Need this when vertex_descriptor=void* |
| { |
| std::size_t |
| operator()(void* v) const { return (std::size_t)v; } |
| }; |
| #endif |
| |
| template <typename V> |
| struct hash< boost::detail::stored_edge<V> > |
| { |
| std::size_t |
| operator()(const boost::detail::stored_edge<V>& e) const |
| { |
| return hash<V>()(e.m_target); |
| } |
| }; |
| |
| template <typename V, typename P> |
| struct hash< boost::detail::stored_edge_property <V,P> > |
| { |
| std::size_t |
| operator()(const boost::detail::stored_edge_property<V,P>& e) const |
| { |
| return hash<V>()(e.m_target); |
| } |
| }; |
| |
| template <typename V, typename I, typename P> |
| struct hash< boost::detail::stored_edge_iter<V,I, P> > |
| { |
| std::size_t |
| operator()(const boost::detail::stored_edge_iter<V,I,P>& e) const |
| { |
| return hash<V>()(e.m_target); |
| } |
| }; |
| |
| } |
| #endif |
| |
| |
| #undef stored_edge |
| #undef stored_edge_property |
| #undef stored_edge_iter |
| |
| #if BOOST_WORKAROUND(BOOST_MSVC, < 1300) |
| // Stay out of the way of the concept checking class |
| #undef Graph |
| #endif |
| |
| #endif // BOOST_GRAPH_DETAIL_DETAIL_ADJACENCY_LIST_CCT |
| |
| /* |
| Implementation Notes: |
| |
| Many of the public interface functions in this file would have been |
| more conveniently implemented as inline friend functions. |
| However there are a few compiler bugs that make that approach |
| non-portable. |
| |
| 1. g++ inline friend in namespace bug |
| 2. g++ using clause doesn't work with inline friends |
| 3. VC++ doesn't have Koenig lookup |
| |
| For these reasons, the functions were all written as non-inline free |
| functions, and static cast was used to convert from the helper |
| class to the adjacency_list derived class. |
| |
| Looking back, it might have been better to write out all functions |
| in terms of the adjacency_list, and then use a tag to dispatch |
| to the various helpers instead of using inheritance. |
| |
| */ |