williamr@2: //  (C) Copyright David Abrahams 2000.
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: #ifndef REVERSE_GRAPH_DWA092300_H_
williamr@2: # define REVERSE_GRAPH_DWA092300_H_
williamr@2: 
williamr@2: #include <boost/graph/adjacency_iterator.hpp>
williamr@2: #include <boost/graph/properties.hpp>
williamr@2: #include <boost/tuple/tuple.hpp>
williamr@2: 
williamr@2: namespace boost {
williamr@2: 
williamr@2: struct reverse_graph_tag { };
williamr@2: 
williamr@2:   namespace detail {
williamr@2: 
williamr@2:     template <bool isEdgeList> struct choose_rev_edge_iter { };
williamr@2:     template <> struct choose_rev_edge_iter<true> {
williamr@2:       template <class G> struct bind_ {
williamr@2:         typedef typename graph_traits<G>::edge_iterator type;
williamr@2:       };
williamr@2:     };
williamr@2:     template <> struct choose_rev_edge_iter<false> {
williamr@2:       template <class G> struct bind_ {
williamr@2:         typedef void type;
williamr@2:       };
williamr@2:     };
williamr@2: 
williamr@2:   } // namespace detail
williamr@2: 
williamr@2: template <class BidirectionalGraph, class GraphRef = const BidirectionalGraph&>
williamr@2: class reverse_graph {
williamr@2:     typedef reverse_graph<BidirectionalGraph, GraphRef> Self;
williamr@2:     typedef graph_traits<BidirectionalGraph> Traits;
williamr@2:  public:
williamr@2:     typedef BidirectionalGraph base_type;
williamr@2: 
williamr@2:     // Constructor
williamr@2:     reverse_graph(GraphRef g) : m_g(g) {}
williamr@2: 
williamr@2:     // Graph requirements
williamr@2:     typedef typename Traits::vertex_descriptor vertex_descriptor;
williamr@2:     typedef typename Traits::edge_descriptor edge_descriptor;
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::traversal_category traversal_category;
williamr@2: 
williamr@2:     // IncidenceGraph requirements
williamr@2:     typedef typename Traits::in_edge_iterator out_edge_iterator;
williamr@2:     typedef typename Traits::degree_size_type degree_size_type;
williamr@2: 
williamr@2:     // BidirectionalGraph requirements
williamr@2:     typedef typename Traits::out_edge_iterator in_edge_iterator;
williamr@2: 
williamr@2:     // AdjacencyGraph requirements
williamr@2:   typedef typename adjacency_iterator_generator<Self,
williamr@2:     vertex_descriptor, out_edge_iterator>::type adjacency_iterator;
williamr@2: 
williamr@2:     // VertexListGraph requirements
williamr@2:     typedef typename Traits::vertex_iterator vertex_iterator;
williamr@2: 
williamr@2:     // EdgeListGraph requirements
williamr@2:     enum { is_edge_list = is_convertible<traversal_category,
williamr@2:            edge_list_graph_tag>::value };
williamr@2:     typedef detail::choose_rev_edge_iter<is_edge_list> ChooseEdgeIter;
williamr@2:     typedef typename ChooseEdgeIter::
williamr@2:       template bind_<BidirectionalGraph>::type   edge_iterator;
williamr@2:     typedef typename Traits::vertices_size_type vertices_size_type;
williamr@2:     typedef typename Traits::edges_size_type edges_size_type;
williamr@2: 
williamr@2:     // More typedefs used by detail::edge_property_map, vertex_property_map
williamr@2:     typedef typename BidirectionalGraph::edge_property_type
williamr@2:       edge_property_type;
williamr@2:     typedef typename BidirectionalGraph::vertex_property_type
williamr@2:       vertex_property_type;
williamr@2:     typedef reverse_graph_tag graph_tag;
williamr@2: 
williamr@2: #ifndef BOOST_GRAPH_NO_BUNDLED_PROPERTIES
williamr@2:     // Bundled properties support
williamr@2:     template<typename Descriptor>
williamr@2:     typename graph::detail::bundled_result<BidirectionalGraph, 
williamr@2:                                            Descriptor>::type&
williamr@2:     operator[](Descriptor x)
williamr@2:     { return m_g[x]; }
williamr@2: 
williamr@2:     template<typename Descriptor>
williamr@2:     typename graph::detail::bundled_result<BidirectionalGraph, 
williamr@2:                                            Descriptor>::type const&
williamr@2:     operator[](Descriptor x) const
williamr@2:     { return m_g[x]; }
williamr@2: #endif // BOOST_GRAPH_NO_BUNDLED_PROPERTIES
williamr@2: 
williamr@2:     static vertex_descriptor null_vertex()
williamr@2:     { return Traits::null_vertex(); }
williamr@2: 
williamr@2:     // would be private, but template friends aren't portable enough.
williamr@2:  // private:
williamr@2:     GraphRef m_g;
williamr@2: };
williamr@2: 
williamr@2: #ifndef BOOST_GRAPH_NO_BUNDLED_PROPERTIES
williamr@2:   template<typename Graph, typename GraphRef>
williamr@2:   struct vertex_bundle_type<reverse_graph<Graph, GraphRef> > 
williamr@2:     : vertex_bundle_type<Graph> { };
williamr@2: 
williamr@2:   template<typename Graph, typename GraphRef>
williamr@2:   struct edge_bundle_type<reverse_graph<Graph, GraphRef> > 
williamr@2:     : edge_bundle_type<Graph> { };
williamr@2: #endif // BOOST_GRAPH_NO_BUNDLED_PROPERTIES
williamr@2: 
williamr@2: template <class BidirectionalGraph>
williamr@2: inline reverse_graph<BidirectionalGraph>
williamr@2: make_reverse_graph(const BidirectionalGraph& g)
williamr@2: {
williamr@2:     return reverse_graph<BidirectionalGraph>(g);
williamr@2: }
williamr@2: 
williamr@2: template <class BidirectionalGraph>
williamr@2: inline reverse_graph<BidirectionalGraph, BidirectionalGraph&>
williamr@2: make_reverse_graph(BidirectionalGraph& g)
williamr@2: {
williamr@2:     return reverse_graph<BidirectionalGraph, BidirectionalGraph&>(g);
williamr@2: }
williamr@2: 
williamr@2: template <class BidirectionalGraph, class GRef>
williamr@2: std::pair<typename reverse_graph<BidirectionalGraph>::vertex_iterator,
williamr@2:           typename reverse_graph<BidirectionalGraph>::vertex_iterator>
williamr@2: vertices(const reverse_graph<BidirectionalGraph,GRef>& g)
williamr@2: {
williamr@2:     return vertices(g.m_g);
williamr@2: }
williamr@2: 
williamr@2: template <class BidirectionalGraph, class GRef>
williamr@2: std::pair<typename reverse_graph<BidirectionalGraph>::edge_iterator,
williamr@2:           typename reverse_graph<BidirectionalGraph>::edge_iterator>
williamr@2: edges(const reverse_graph<BidirectionalGraph,GRef>& g)
williamr@2: {
williamr@2:     return edges(g.m_g);
williamr@2: }
williamr@2: 
williamr@2: template <class BidirectionalGraph, class GRef>
williamr@2: inline std::pair<typename BidirectionalGraph::in_edge_iterator,
williamr@2:                  typename BidirectionalGraph::in_edge_iterator>
williamr@2: out_edges(const typename BidirectionalGraph::vertex_descriptor u,
williamr@2:           const reverse_graph<BidirectionalGraph,GRef>& g)
williamr@2: {
williamr@2:     return in_edges(u, g.m_g);
williamr@2: }
williamr@2: 
williamr@2: template <class BidirectionalGraph, class GRef>
williamr@2: inline typename BidirectionalGraph::vertices_size_type
williamr@2: num_vertices(const reverse_graph<BidirectionalGraph,GRef>& g)
williamr@2: {
williamr@2:     return num_vertices(g.m_g);
williamr@2: }
williamr@2: 
williamr@2: template <class BidirectionalGraph, class GRef>
williamr@2: inline typename reverse_graph<BidirectionalGraph>::edges_size_type
williamr@2: num_edges(const reverse_graph<BidirectionalGraph,GRef>& g)
williamr@2: {
williamr@2:     return num_edges(g.m_g);
williamr@2: }
williamr@2: 
williamr@2: template <class BidirectionalGraph, class GRef>
williamr@2: inline typename BidirectionalGraph::degree_size_type
williamr@2: out_degree(const typename BidirectionalGraph::vertex_descriptor u,
williamr@2:            const reverse_graph<BidirectionalGraph,GRef>& g)
williamr@2: {
williamr@2:     return in_degree(u, g.m_g);
williamr@2: }
williamr@2: 
williamr@2: template <class BidirectionalGraph, class GRef>
williamr@2: inline std::pair<typename BidirectionalGraph::edge_descriptor, bool>
williamr@2: edge(const typename BidirectionalGraph::vertex_descriptor u,
williamr@2:      const typename BidirectionalGraph::vertex_descriptor v,
williamr@2:      const reverse_graph<BidirectionalGraph,GRef>& g)
williamr@2: {
williamr@2:     return edge(v, u, g.m_g);
williamr@2: }
williamr@2: 
williamr@2: template <class BidirectionalGraph, class GRef>
williamr@2: inline std::pair<typename BidirectionalGraph::out_edge_iterator,
williamr@2:     typename BidirectionalGraph::out_edge_iterator>
williamr@2: in_edges(const typename BidirectionalGraph::vertex_descriptor u,
williamr@2:          const reverse_graph<BidirectionalGraph,GRef>& g)
williamr@2: {
williamr@2:     return out_edges(u, g.m_g);
williamr@2: }
williamr@2: 
williamr@2: template <class BidirectionalGraph, class GRef>
williamr@2: inline std::pair<typename reverse_graph<BidirectionalGraph,GRef>::adjacency_iterator,
williamr@2:     typename reverse_graph<BidirectionalGraph,GRef>::adjacency_iterator>
williamr@2: adjacent_vertices(const typename BidirectionalGraph::vertex_descriptor u,
williamr@2:                   const reverse_graph<BidirectionalGraph,GRef>& g)
williamr@2: {
williamr@2:     typedef reverse_graph<BidirectionalGraph,GRef> Graph;
williamr@2:     typename Graph::out_edge_iterator first, last;
williamr@2:     tie(first, last) = out_edges(u, g);
williamr@2:     typedef typename Graph::adjacency_iterator adjacency_iterator;
williamr@2:     return std::make_pair(adjacency_iterator(first, const_cast<Graph*>(&g)),
williamr@2:                           adjacency_iterator(last, const_cast<Graph*>(&g)));
williamr@2: }
williamr@2: 
williamr@2: template <class BidirectionalGraph, class GRef>
williamr@2: inline typename BidirectionalGraph::degree_size_type
williamr@2: in_degree(const typename BidirectionalGraph::vertex_descriptor u,
williamr@2:           const reverse_graph<BidirectionalGraph,GRef>& g)
williamr@2: {
williamr@2:     return out_degree(u, g.m_g);
williamr@2: }
williamr@2: 
williamr@2: template <class Edge, class BidirectionalGraph, class GRef>
williamr@2: inline typename graph_traits<BidirectionalGraph>::vertex_descriptor
williamr@2: source(const Edge& e, const reverse_graph<BidirectionalGraph,GRef>& g)
williamr@2: {
williamr@2:     return target(e, g.m_g);
williamr@2: }
williamr@2: 
williamr@2: template <class Edge, class BidirectionalGraph, class GRef>
williamr@2: inline typename graph_traits<BidirectionalGraph>::vertex_descriptor
williamr@2: target(const Edge& e, const reverse_graph<BidirectionalGraph,GRef>& g)
williamr@2: {
williamr@2:     return source(e, g.m_g);
williamr@2: }
williamr@2: 
williamr@2: 
williamr@2: namespace detail {
williamr@2: 
williamr@2:   struct reverse_graph_vertex_property_selector {
williamr@2:     template <class ReverseGraph, class Property, class Tag>
williamr@2:     struct bind_ {
williamr@2:       typedef typename ReverseGraph::base_type Graph;
williamr@2:       typedef property_map<Graph, Tag> PMap;
williamr@2:       typedef typename PMap::type type;
williamr@2:       typedef typename PMap::const_type const_type;
williamr@2:     };
williamr@2:   };
williamr@2: 
williamr@2:   struct reverse_graph_edge_property_selector {
williamr@2:     template <class ReverseGraph, class Property, class Tag>
williamr@2:     struct bind_ {
williamr@2:       typedef typename ReverseGraph::base_type Graph;
williamr@2:       typedef property_map<Graph, Tag> PMap;
williamr@2:       typedef typename PMap::type type;
williamr@2:       typedef typename PMap::const_type const_type;
williamr@2:     };
williamr@2:   };
williamr@2: 
williamr@2: } // namespace detail
williamr@2: 
williamr@2: template <>
williamr@2: struct vertex_property_selector<reverse_graph_tag> {
williamr@2:   typedef detail::reverse_graph_vertex_property_selector type;
williamr@2: };
williamr@2: 
williamr@2: template <>
williamr@2: struct edge_property_selector<reverse_graph_tag> {
williamr@2:   typedef detail::reverse_graph_edge_property_selector type;
williamr@2: };
williamr@2: 
williamr@2: template <class BidirGraph, class GRef, class Property>
williamr@2: typename property_map<BidirGraph, Property>::type
williamr@2: get(Property p, reverse_graph<BidirGraph,GRef>& g)
williamr@2: {
williamr@2:   return get(p, g.m_g);
williamr@2: }
williamr@2: 
williamr@2: template <class BidirGraph, class GRef, class Property>
williamr@2: typename property_map<BidirGraph, Property>::const_type
williamr@2: get(Property p, const reverse_graph<BidirGraph,GRef>& g)
williamr@2: {
williamr@2:   const BidirGraph& gref = g.m_g; // in case GRef is non-const
williamr@2:   return get(p, gref);
williamr@2: }
williamr@2: 
williamr@2: template <class BidirectionalGraph, class GRef, class Property, class Key>
williamr@2: typename property_traits<
williamr@2:   typename property_map<BidirectionalGraph, Property>::const_type
williamr@2: >::value_type
williamr@2: get(Property p, const reverse_graph<BidirectionalGraph,GRef>& g, const Key& k)
williamr@2: {
williamr@2:   return get(p, g.m_g, k);
williamr@2: }
williamr@2: 
williamr@2: template <class BidirectionalGraph, class GRef, class Property, class Key, class Value>
williamr@2: void
williamr@2: put(Property p, const reverse_graph<BidirectionalGraph,GRef>& g, const Key& k,
williamr@2:     const Value& val)
williamr@2: {
williamr@2:   put(p, g.m_g, k, val);
williamr@2: }
williamr@2: 
williamr@2: template<typename BidirectionalGraph, typename GRef, typename Tag,
williamr@2:          typename Value>
williamr@2: inline void
williamr@2: set_property(const reverse_graph<BidirectionalGraph,GRef>& g, Tag tag, 
williamr@2:              const Value& value)
williamr@2: {
williamr@2:   set_property(g.m_g, tag, value);
williamr@2: }
williamr@2: 
williamr@2: template<typename BidirectionalGraph, typename GRef, typename Tag>
williamr@2: inline
williamr@2: typename graph_property<BidirectionalGraph, Tag>::type
williamr@2: get_property(const reverse_graph<BidirectionalGraph,GRef>& g, Tag tag)
williamr@2: {
williamr@2:   return get_property(g.m_g, tag);
williamr@2: }
williamr@2: 
williamr@2: } // namespace boost
williamr@2: 
williamr@2: #endif