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