| // (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 |