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