| // (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/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 <bool isEdgeList> struct choose_rev_edge_iter { }; |
| template <> struct choose_rev_edge_iter<true> { |
| template <class G> struct bind_ { |
| typedef 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; |
| |
| // Constructor |
| reverse_graph(GraphRef g) : m_g(g) {} |
| |
| // Graph requirements |
| typedef typename Traits::vertex_descriptor vertex_descriptor; |
| typedef 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 typename Traits::in_edge_iterator out_edge_iterator; |
| typedef typename Traits::degree_size_type degree_size_type; |
| |
| // BidirectionalGraph requirements |
| typedef 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, Descriptor>::type& |
| operator[](Descriptor x) |
| { return m_g[x]; } |
| |
| template<typename Descriptor> |
| typename graph::detail::bundled_result<BidirectionalGraph, Descriptor>::type const& |
| operator[](Descriptor x) const |
| { return m_g[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 edges(g.m_g); |
| } |
| |
| template <class BidirectionalGraph, class GRef> |
| inline std::pair<typename graph_traits<BidirectionalGraph>::in_edge_iterator, |
| typename graph_traits<BidirectionalGraph>::in_edge_iterator> |
| out_edges(const typename graph_traits<BidirectionalGraph>::vertex_descriptor u, |
| const reverse_graph<BidirectionalGraph,GRef>& g) |
| { |
| return 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<BidirectionalGraph>::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) |
| { |
| return edge(v, u, g.m_g); |
| } |
| |
| template <class BidirectionalGraph, class GRef> |
| inline std::pair<typename graph_traits<BidirectionalGraph>::out_edge_iterator, |
| typename graph_traits<BidirectionalGraph>::out_edge_iterator> |
| in_edges(const typename graph_traits<BidirectionalGraph>::vertex_descriptor u, |
| const reverse_graph<BidirectionalGraph,GRef>& g) |
| { |
| return 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 Edge& e, const reverse_graph<BidirectionalGraph,GRef>& g) |
| { |
| return target(e, g.m_g); |
| } |
| |
| template <class Edge, class BidirectionalGraph, class GRef> |
| inline typename graph_traits<BidirectionalGraph>::vertex_descriptor |
| target(const Edge& e, const reverse_graph<BidirectionalGraph,GRef>& g) |
| { |
| return source(e, g.m_g); |
| } |
| |
| |
| namespace detail { |
| |
| struct reverse_graph_vertex_property_selector { |
| template <class ReverseGraph, class Property, class Tag> |
| struct bind_ { |
| typedef typename ReverseGraph::base_type Graph; |
| typedef property_map<Graph, Tag> PMap; |
| typedef typename PMap::type type; |
| typedef typename PMap::const_type const_type; |
| }; |
| }; |
| |
| struct reverse_graph_edge_property_selector { |
| template <class ReverseGraph, class Property, class Tag> |
| struct bind_ { |
| typedef typename ReverseGraph::base_type Graph; |
| typedef property_map<Graph, Tag> PMap; |
| typedef typename PMap::type type; |
| typedef typename PMap::const_type const_type; |
| }; |
| }; |
| |
| } // namespace detail |
| |
| template <> |
| struct vertex_property_selector<reverse_graph_tag> { |
| typedef detail::reverse_graph_vertex_property_selector type; |
| }; |
| |
| template <> |
| struct edge_property_selector<reverse_graph_tag> { |
| typedef detail::reverse_graph_edge_property_selector type; |
| }; |
| |
| template <class BidirGraph, class GRef, class Property> |
| typename property_map<reverse_graph<BidirGraph,GRef>, Property>::type |
| get(Property p, reverse_graph<BidirGraph,GRef>& g) |
| { |
| return get(p, g.m_g); |
| } |
| |
| template <class BidirGraph, class GRef, class Property> |
| typename property_map<reverse_graph<BidirGraph,GRef>, Property>::const_type |
| get(Property p, const reverse_graph<BidirGraph,GRef>& g) |
| { |
| const BidirGraph& gref = g.m_g; // in case GRef is non-const |
| return get(p, gref); |
| } |
| |
| template <class BidirectionalGraph, class GRef, class Property, class Key> |
| typename property_traits< |
| typename property_map<BidirectionalGraph, Property>::const_type |
| >::value_type |
| get(Property p, const reverse_graph<BidirectionalGraph,GRef>& g, const Key& k) |
| { |
| return get(p, g.m_g, k); |
| } |
| |
| template <class BidirectionalGraph, class GRef, class Property, class Key, class Value> |
| void |
| put(Property p, const reverse_graph<BidirectionalGraph,GRef>& g, const Key& k, |
| const Value& val) |
| { |
| put(p, g.m_g, k, val); |
| } |
| |
| 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 |
| |
| #if BOOST_WORKAROUND(BOOST_MSVC, < 1300) |
| // Stay out of the way of the concept checking class |
| # undef BidirectionalGraph |
| #endif |
| |
| #endif |