// (C) Copyright David Abrahams 2000. // Distributed under the Boost Software License, Version 1.0. (See // accompanying file LICENSE_1_0.txt or copy at // http://www.boost.org/LICENSE_1_0.txt) #ifndef REVERSE_GRAPH_DWA092300_H_ # define REVERSE_GRAPH_DWA092300_H_ #include <boost/graph/adjacency_iterator.hpp> #include <boost/graph/properties.hpp> #include <boost/iterator/transform_iterator.hpp> #include <boost/tuple/tuple.hpp> #include <boost/type_traits.hpp> #include <boost/mpl/if.hpp> #if BOOST_WORKAROUND(BOOST_MSVC, < 1300) // Stay out of the way of the concept checking class # define BidirectionalGraph BidirectionalGraph_ #endif namespace boost { struct reverse_graph_tag { }; namespace detail { template <typename EdgeDesc> class reverse_graph_edge_descriptor { public: EdgeDesc underlying_descx; // Odd name is because this needs to be public but shouldn't be exposed to users anymore private: typedef EdgeDesc base_descriptor_type; public: explicit reverse_graph_edge_descriptor(const EdgeDesc& underlying_descx = EdgeDesc()) : underlying_descx(underlying_descx) {} friend bool operator==(const reverse_graph_edge_descriptor& a, const reverse_graph_edge_descriptor& b) { return a.underlying_descx == b.underlying_descx; } friend bool operator!=(const reverse_graph_edge_descriptor& a, const reverse_graph_edge_descriptor& b) { return a.underlying_descx != b.underlying_descx; } friend bool operator<(const reverse_graph_edge_descriptor& a, const reverse_graph_edge_descriptor& b) { return a.underlying_descx < b.underlying_descx; } friend bool operator>(const reverse_graph_edge_descriptor& a, const reverse_graph_edge_descriptor& b) { return a.underlying_descx > b.underlying_descx; } friend bool operator<=(const reverse_graph_edge_descriptor& a, const reverse_graph_edge_descriptor& b) { return a.underlying_descx <= b.underlying_descx; } friend bool operator>=(const reverse_graph_edge_descriptor& a, const reverse_graph_edge_descriptor& b) { return a.underlying_descx >= b.underlying_descx; } }; template <typename EdgeDesc> struct reverse_graph_edge_descriptor_maker { typedef reverse_graph_edge_descriptor<EdgeDesc> result_type; reverse_graph_edge_descriptor<EdgeDesc> operator()(const EdgeDesc& ed) const { return reverse_graph_edge_descriptor<EdgeDesc>(ed); } }; template <typename EdgeDesc, typename Iter> std::pair<transform_iterator<reverse_graph_edge_descriptor_maker<EdgeDesc>, Iter>, transform_iterator<reverse_graph_edge_descriptor_maker<EdgeDesc>, Iter> > reverse_edge_iter_pair(const std::pair<Iter, Iter>& ip) { return std::make_pair(make_transform_iterator(ip.first, reverse_graph_edge_descriptor_maker<EdgeDesc>()), make_transform_iterator(ip.second, reverse_graph_edge_descriptor_maker<EdgeDesc>())); } // Get the underlying descriptor from a vertex or edge descriptor template <typename Desc> struct get_underlying_descriptor_from_reverse_descriptor { typedef Desc type; static Desc convert(const Desc& d) {return d;} }; template <typename Desc> struct get_underlying_descriptor_from_reverse_descriptor<reverse_graph_edge_descriptor<Desc> > { typedef Desc type; static Desc convert(const reverse_graph_edge_descriptor<Desc>& d) {return d.underlying_descx;} }; template <bool isEdgeList> struct choose_rev_edge_iter { }; template <> struct choose_rev_edge_iter<true> { template <class G> struct bind_ { typedef transform_iterator<reverse_graph_edge_descriptor_maker<typename graph_traits<G>::edge_descriptor>, typename graph_traits<G>::edge_iterator> type; }; }; template <> struct choose_rev_edge_iter<false> { template <class G> struct bind_ { typedef void type; }; }; } // namespace detail template <class BidirectionalGraph, class GraphRef = const BidirectionalGraph&> class reverse_graph { typedef reverse_graph<BidirectionalGraph, GraphRef> Self; typedef graph_traits<BidirectionalGraph> Traits; public: typedef BidirectionalGraph base_type; typedef GraphRef base_ref_type; // Constructor reverse_graph(GraphRef g) : m_g(g) {} // Graph requirements typedef typename Traits::vertex_descriptor vertex_descriptor; typedef detail::reverse_graph_edge_descriptor<typename Traits::edge_descriptor> edge_descriptor; typedef typename Traits::directed_category directed_category; typedef typename Traits::edge_parallel_category edge_parallel_category; typedef typename Traits::traversal_category traversal_category; // IncidenceGraph requirements typedef transform_iterator<detail::reverse_graph_edge_descriptor_maker<typename Traits::edge_descriptor>, typename Traits::in_edge_iterator> out_edge_iterator; typedef typename Traits::degree_size_type degree_size_type; // BidirectionalGraph requirements typedef transform_iterator<detail::reverse_graph_edge_descriptor_maker<typename Traits::edge_descriptor>, typename Traits::out_edge_iterator> in_edge_iterator; // AdjacencyGraph requirements typedef typename adjacency_iterator_generator<Self, vertex_descriptor, out_edge_iterator>::type adjacency_iterator; // VertexListGraph requirements typedef typename Traits::vertex_iterator vertex_iterator; // EdgeListGraph requirements enum { is_edge_list = is_convertible<traversal_category, edge_list_graph_tag>::value }; typedef detail::choose_rev_edge_iter<is_edge_list> ChooseEdgeIter; typedef typename ChooseEdgeIter:: template bind_<BidirectionalGraph>::type edge_iterator; typedef typename Traits::vertices_size_type vertices_size_type; typedef typename Traits::edges_size_type edges_size_type; typedef reverse_graph_tag graph_tag; #ifndef BOOST_GRAPH_NO_BUNDLED_PROPERTIES // Bundled properties support template<typename Descriptor> typename graph::detail::bundled_result< BidirectionalGraph, typename detail::get_underlying_descriptor_from_reverse_descriptor<Descriptor>::type >::type& operator[](Descriptor x) { return m_g[detail::get_underlying_descriptor_from_reverse_descriptor<Descriptor>::convert(x)]; } template<typename Descriptor> typename graph::detail::bundled_result< BidirectionalGraph, typename detail::get_underlying_descriptor_from_reverse_descriptor<Descriptor>::type >::type const& operator[](Descriptor x) const { return m_g[detail::get_underlying_descriptor_from_reverse_descriptor<Descriptor>::convert(x)]; } #endif // BOOST_GRAPH_NO_BUNDLED_PROPERTIES static vertex_descriptor null_vertex() { return Traits::null_vertex(); } // would be private, but template friends aren't portable enough. // private: GraphRef m_g; }; // These are separate so they are not instantiated unless used (see bug 1021) template <class BidirectionalGraph, class GraphRef> struct vertex_property_type<reverse_graph<BidirectionalGraph, GraphRef> > { typedef typename boost::vertex_property_type<BidirectionalGraph>::type type; }; template <class BidirectionalGraph, class GraphRef> struct edge_property_type<reverse_graph<BidirectionalGraph, GraphRef> > { typedef typename boost::edge_property_type<BidirectionalGraph>::type type; }; template <class BidirectionalGraph, class GraphRef> struct graph_property_type<reverse_graph<BidirectionalGraph, GraphRef> > { typedef typename boost::graph_property_type<BidirectionalGraph>::type type; }; #ifndef BOOST_GRAPH_NO_BUNDLED_PROPERTIES template<typename Graph, typename GraphRef> struct vertex_bundle_type<reverse_graph<Graph, GraphRef> > : vertex_bundle_type<Graph> { }; template<typename Graph, typename GraphRef> struct edge_bundle_type<reverse_graph<Graph, GraphRef> > : edge_bundle_type<Graph> { }; template<typename Graph, typename GraphRef> struct graph_bundle_type<reverse_graph<Graph, GraphRef> > : graph_bundle_type<Graph> { }; #endif // BOOST_GRAPH_NO_BUNDLED_PROPERTIES template <class BidirectionalGraph> inline reverse_graph<BidirectionalGraph> make_reverse_graph(const BidirectionalGraph& g) { return reverse_graph<BidirectionalGraph>(g); } template <class BidirectionalGraph> inline reverse_graph<BidirectionalGraph, BidirectionalGraph&> make_reverse_graph(BidirectionalGraph& g) { return reverse_graph<BidirectionalGraph, BidirectionalGraph&>(g); } template <class BidirectionalGraph, class GRef> std::pair<typename reverse_graph<BidirectionalGraph>::vertex_iterator, typename reverse_graph<BidirectionalGraph>::vertex_iterator> vertices(const reverse_graph<BidirectionalGraph,GRef>& g) { return vertices(g.m_g); } template <class BidirectionalGraph, class GRef> std::pair<typename reverse_graph<BidirectionalGraph>::edge_iterator, typename reverse_graph<BidirectionalGraph>::edge_iterator> edges(const reverse_graph<BidirectionalGraph,GRef>& g) { return detail::reverse_edge_iter_pair<typename graph_traits<BidirectionalGraph>::edge_descriptor>(edges(g.m_g)); } template <class BidirectionalGraph, class GRef> inline std::pair<typename reverse_graph<BidirectionalGraph>::out_edge_iterator, typename reverse_graph<BidirectionalGraph>::out_edge_iterator> out_edges(const typename graph_traits<BidirectionalGraph>::vertex_descriptor u, const reverse_graph<BidirectionalGraph,GRef>& g) { return detail::reverse_edge_iter_pair<typename graph_traits<BidirectionalGraph>::edge_descriptor>(in_edges(u, g.m_g)); } template <class BidirectionalGraph, class GRef> inline typename graph_traits<BidirectionalGraph>::vertices_size_type num_vertices(const reverse_graph<BidirectionalGraph,GRef>& g) { return num_vertices(g.m_g); } template <class BidirectionalGraph, class GRef> inline typename reverse_graph<BidirectionalGraph>::edges_size_type num_edges(const reverse_graph<BidirectionalGraph,GRef>& g) { return num_edges(g.m_g); } template <class BidirectionalGraph, class GRef> inline typename graph_traits<BidirectionalGraph>::degree_size_type out_degree(const typename graph_traits<BidirectionalGraph>::vertex_descriptor u, const reverse_graph<BidirectionalGraph,GRef>& g) { return in_degree(u, g.m_g); } template <class BidirectionalGraph, class GRef> inline typename graph_traits<BidirectionalGraph>::vertex_descriptor vertex(const typename graph_traits<BidirectionalGraph>::vertices_size_type v, const reverse_graph<BidirectionalGraph,GRef>& g) { return vertex(v, g.m_g); } template <class BidirectionalGraph, class GRef> inline std::pair< typename graph_traits<reverse_graph<BidirectionalGraph,GRef> >::edge_descriptor, bool> edge(const typename graph_traits<BidirectionalGraph>::vertex_descriptor u, const typename graph_traits<BidirectionalGraph>::vertex_descriptor v, const reverse_graph<BidirectionalGraph,GRef>& g) { typedef typename graph_traits<BidirectionalGraph>::edge_descriptor underlying_edge_descriptor; std::pair<underlying_edge_descriptor, bool> e = edge(v, u, g.m_g); return std::make_pair(detail::reverse_graph_edge_descriptor<underlying_edge_descriptor>(e.first), e.second); } template <class BidirectionalGraph, class GRef> inline std::pair<typename reverse_graph<BidirectionalGraph>::in_edge_iterator, typename reverse_graph<BidirectionalGraph>::in_edge_iterator> in_edges(const typename graph_traits<BidirectionalGraph>::vertex_descriptor u, const reverse_graph<BidirectionalGraph,GRef>& g) { return detail::reverse_edge_iter_pair<typename graph_traits<BidirectionalGraph>::edge_descriptor>(out_edges(u, g.m_g)); } template <class BidirectionalGraph, class GRef> inline std::pair<typename reverse_graph<BidirectionalGraph,GRef>::adjacency_iterator, typename reverse_graph<BidirectionalGraph,GRef>::adjacency_iterator> adjacent_vertices(typename graph_traits<BidirectionalGraph>::vertex_descriptor u, const reverse_graph<BidirectionalGraph,GRef>& g) { typedef reverse_graph<BidirectionalGraph,GRef> Graph; typename graph_traits<Graph>::out_edge_iterator first, last; boost::tie(first, last) = out_edges(u, g); typedef typename graph_traits<Graph>::adjacency_iterator adjacency_iterator; return std::make_pair(adjacency_iterator(first, const_cast<Graph*>(&g)), adjacency_iterator(last, const_cast<Graph*>(&g))); } template <class BidirectionalGraph, class GRef> inline typename graph_traits<BidirectionalGraph>::degree_size_type in_degree(const typename graph_traits<BidirectionalGraph>::vertex_descriptor u, const reverse_graph<BidirectionalGraph,GRef>& g) { return out_degree(u, g.m_g); } template <class Edge, class BidirectionalGraph, class GRef> inline typename graph_traits<BidirectionalGraph>::vertex_descriptor source(const detail::reverse_graph_edge_descriptor<Edge>& e, const reverse_graph<BidirectionalGraph,GRef>& g) { return target(e.underlying_descx, g.m_g); } template <class Edge, class BidirectionalGraph, class GRef> inline typename graph_traits<BidirectionalGraph>::vertex_descriptor target(const detail::reverse_graph_edge_descriptor<Edge>& e, const reverse_graph<BidirectionalGraph,GRef>& g) { return source(e.underlying_descx, g.m_g); } namespace detail { template <typename PM> struct reverse_graph_edge_property_map { private: PM underlying_pm; public: typedef reverse_graph_edge_descriptor<typename property_traits<PM>::key_type> key_type; typedef typename property_traits<PM>::value_type value_type; typedef typename property_traits<PM>::reference reference; typedef typename property_traits<PM>::category category; explicit reverse_graph_edge_property_map(const PM& pm): underlying_pm(pm) {} friend reference get(const reverse_graph_edge_property_map& m, const key_type& e) { return get(m.underlying_pm, e.underlying_descx); } friend void put(const reverse_graph_edge_property_map& m, const key_type& e, const value_type& v) { put(m.underlying_pm, e.underlying_descx, v); } reference operator[](const key_type& k) const { return (this->underlying_pm)[k.underlying_descx]; } }; } // namespace detail template <class BidirGraph, class GRef, class Property> struct property_map<reverse_graph<BidirGraph, GRef>, Property> { typedef boost::is_same<typename detail::property_kind_from_graph<BidirGraph, Property>::type, edge_property_tag> is_edge_prop; typedef typename property_map<BidirGraph, Property>::type orig_type; typedef typename property_map<BidirGraph, Property>::const_type orig_const_type; typedef typename boost::mpl::if_<is_edge_prop, detail::reverse_graph_edge_property_map<orig_type>, orig_type>::type type; typedef typename boost::mpl::if_<is_edge_prop, detail::reverse_graph_edge_property_map<orig_const_type>, orig_const_type>::type const_type; }; template <class BidirGraph, class GRef, class Property> struct property_map<const reverse_graph<BidirGraph, GRef>, Property> { typedef boost::is_same<typename detail::property_kind_from_graph<BidirGraph, Property>::type, edge_property_tag> is_edge_prop; typedef typename property_map<BidirGraph, Property>::const_type orig_const_type; typedef typename boost::mpl::if_<is_edge_prop, detail::reverse_graph_edge_property_map<orig_const_type>, orig_const_type>::type const_type; typedef const_type type; }; template <class BidirGraph, class GRef, class Property> typename disable_if< is_same<Property, edge_underlying_t>, typename property_map<reverse_graph<BidirGraph,GRef>, Property>::type>::type get(Property p, reverse_graph<BidirGraph,GRef>& g) { return typename property_map<reverse_graph<BidirGraph,GRef>, Property>::type(get(p, g.m_g)); } template <class BidirGraph, class GRef, class Property> typename disable_if< is_same<Property, edge_underlying_t>, typename property_map<reverse_graph<BidirGraph,GRef>, Property>::const_type>::type get(Property p, const reverse_graph<BidirGraph,GRef>& g) { const BidirGraph& gref = g.m_g; // in case GRef is non-const return typename property_map<reverse_graph<BidirGraph,GRef>, Property>::const_type(get(p, gref)); } template <class BidirectionalGraph, class GRef, class Property, class Key> typename disable_if< is_same<Property, edge_underlying_t>, typename property_traits< typename property_map<reverse_graph<BidirectionalGraph, GRef>, Property>::const_type >::value_type>::type get(Property p, const reverse_graph<BidirectionalGraph,GRef>& g, const Key& k) { return get(get(p, g), k); } template <class BidirectionalGraph, class GRef, class Property, class Key, class Value> void put(Property p, reverse_graph<BidirectionalGraph,GRef>& g, const Key& k, const Value& val) { put(get(p, g), k, val); } // Get the underlying descriptor from a reverse_graph's wrapped edge descriptor namespace detail { template <class E> struct underlying_edge_desc_map_type { E operator[](const reverse_graph_edge_descriptor<E>& k) const { return k.underlying_descx; } }; template <class E> E get(underlying_edge_desc_map_type<E> m, const reverse_graph_edge_descriptor<E>& k) { return m[k]; } } template <class E> struct property_traits<detail::underlying_edge_desc_map_type<E> > { typedef detail::reverse_graph_edge_descriptor<E> key_type; typedef E value_type; typedef const E& reference; typedef readable_property_map_tag category; }; template <class Graph, class GRef> struct property_map<reverse_graph<Graph, GRef>, edge_underlying_t> { private: typedef typename graph_traits<Graph>::edge_descriptor ed; public: typedef detail::underlying_edge_desc_map_type<ed> type; typedef detail::underlying_edge_desc_map_type<ed> const_type; }; template <typename T> struct is_reverse_graph: boost::mpl::false_ {}; template <typename G, typename R> struct is_reverse_graph<reverse_graph<G, R> >: boost::mpl::true_ {}; template <class G> typename enable_if<is_reverse_graph<G>, detail::underlying_edge_desc_map_type<typename graph_traits<typename G::base_type>::edge_descriptor> >::type get(edge_underlying_t, G&) { return detail::underlying_edge_desc_map_type<typename graph_traits<typename G::base_type>::edge_descriptor>(); } template <class G> typename enable_if<is_reverse_graph<G>, typename graph_traits<typename G::base_type>::edge_descriptor>::type get(edge_underlying_t, G&, const typename graph_traits<G>::edge_descriptor& k) { return k.underlying_descx; } template <class G> typename enable_if<is_reverse_graph<G>, detail::underlying_edge_desc_map_type<typename graph_traits<typename G::base_type>::edge_descriptor> >::type get(edge_underlying_t, const G&) { return detail::underlying_edge_desc_map_type<typename graph_traits<typename G::base_type>::edge_descriptor>(); } template <class G> typename enable_if<is_reverse_graph<G>, typename graph_traits<typename G::base_type>::edge_descriptor>::type get(edge_underlying_t, const G&, const typename graph_traits<G>::edge_descriptor& k) { return k.underlying_descx; } // Access to wrapped graph's graph properties template<typename BidirectionalGraph, typename GRef, typename Tag, typename Value> inline void set_property(const reverse_graph<BidirectionalGraph,GRef>& g, Tag tag, const Value& value) { set_property(g.m_g, tag, value); } template<typename BidirectionalGraph, typename GRef, typename Tag> inline typename boost::mpl::if_< boost::is_const<typename boost::remove_reference<GRef>::type>, const typename graph_property<BidirectionalGraph, Tag>::type&, typename graph_property<BidirectionalGraph, Tag>::type& >::type get_property(const reverse_graph<BidirectionalGraph,GRef>& g, Tag tag) { return get_property(g.m_g, tag); } } // namespace boost #endif