1 //  (C) Copyright David Abrahams 2000.

     2 // Distributed under the Boost Software License, Version 1.0. (See

     3 // accompanying file LICENSE_1_0.txt or copy at

     4 // http://www.boost.org/LICENSE_1_0.txt)

     5 

     6 #ifndef REVERSE_GRAPH_DWA092300_H_

     7 # define REVERSE_GRAPH_DWA092300_H_

     8 

     9 #include <boost/graph/adjacency_iterator.hpp>

    10 #include <boost/graph/properties.hpp>

    11 #include <boost/tuple/tuple.hpp>

    12 

    13 namespace boost {

    14 

    15 struct reverse_graph_tag { };

    16 

    17   namespace detail {

    18 

    19     template <bool isEdgeList> struct choose_rev_edge_iter { };

    20     template <> struct choose_rev_edge_iter<true> {

    21       template <class G> struct bind_ {

    22         typedef typename graph_traits<G>::edge_iterator type;

    23       };

    24     };

    25     template <> struct choose_rev_edge_iter<false> {

    26       template <class G> struct bind_ {

    27         typedef void type;

    28       };

    29     };

    30 

    31   } // namespace detail

    32 

    33 template <class BidirectionalGraph, class GraphRef = const BidirectionalGraph&>

    34 class reverse_graph {

    35     typedef reverse_graph<BidirectionalGraph, GraphRef> Self;

    36     typedef graph_traits<BidirectionalGraph> Traits;

    37  public:

    38     typedef BidirectionalGraph base_type;

    39 

    40     // Constructor

    41     reverse_graph(GraphRef g) : m_g(g) {}

    42 

    43     // Graph requirements

    44     typedef typename Traits::vertex_descriptor vertex_descriptor;

    45     typedef typename Traits::edge_descriptor edge_descriptor;

    46     typedef typename Traits::directed_category directed_category;

    47     typedef typename Traits::edge_parallel_category edge_parallel_category;

    48     typedef typename Traits::traversal_category traversal_category;

    49 

    50     // IncidenceGraph requirements

    51     typedef typename Traits::in_edge_iterator out_edge_iterator;

    52     typedef typename Traits::degree_size_type degree_size_type;

    53 

    54     // BidirectionalGraph requirements

    55     typedef typename Traits::out_edge_iterator in_edge_iterator;

    56 

    57     // AdjacencyGraph requirements

    58   typedef typename adjacency_iterator_generator<Self,

    59     vertex_descriptor, out_edge_iterator>::type adjacency_iterator;

    60 

    61     // VertexListGraph requirements

    62     typedef typename Traits::vertex_iterator vertex_iterator;

    63 

    64     // EdgeListGraph requirements

    65     enum { is_edge_list = is_convertible<traversal_category,

    66            edge_list_graph_tag>::value };

    67     typedef detail::choose_rev_edge_iter<is_edge_list> ChooseEdgeIter;

    68     typedef typename ChooseEdgeIter::

    69       template bind_<BidirectionalGraph>::type   edge_iterator;

    70     typedef typename Traits::vertices_size_type vertices_size_type;

    71     typedef typename Traits::edges_size_type edges_size_type;

    72 

    73     // More typedefs used by detail::edge_property_map, vertex_property_map

    74     typedef typename BidirectionalGraph::edge_property_type

    75       edge_property_type;

    76     typedef typename BidirectionalGraph::vertex_property_type

    77       vertex_property_type;

    78     typedef reverse_graph_tag graph_tag;

    79 

    80 #ifndef BOOST_GRAPH_NO_BUNDLED_PROPERTIES

    81     // Bundled properties support

    82     template<typename Descriptor>

    83     typename graph::detail::bundled_result<BidirectionalGraph, 

    84                                            Descriptor>::type&

    85     operator[](Descriptor x)

    86     { return m_g[x]; }

    87 

    88     template<typename Descriptor>

    89     typename graph::detail::bundled_result<BidirectionalGraph, 

    90                                            Descriptor>::type const&

    91     operator[](Descriptor x) const

    92     { return m_g[x]; }

    93 #endif // BOOST_GRAPH_NO_BUNDLED_PROPERTIES

    94 

    95     static vertex_descriptor null_vertex()

    96     { return Traits::null_vertex(); }

    97 

    98     // would be private, but template friends aren't portable enough.

    99  // private:

   100     GraphRef m_g;

   101 };

   102 

   103 #ifndef BOOST_GRAPH_NO_BUNDLED_PROPERTIES

   104   template<typename Graph, typename GraphRef>

   105   struct vertex_bundle_type<reverse_graph<Graph, GraphRef> > 

   106     : vertex_bundle_type<Graph> { };

   107 

   108   template<typename Graph, typename GraphRef>

   109   struct edge_bundle_type<reverse_graph<Graph, GraphRef> > 

   110     : edge_bundle_type<Graph> { };

   111 #endif // BOOST_GRAPH_NO_BUNDLED_PROPERTIES

   112 

   113 template <class BidirectionalGraph>

   114 inline reverse_graph<BidirectionalGraph>

   115 make_reverse_graph(const BidirectionalGraph& g)

   116 {

   117     return reverse_graph<BidirectionalGraph>(g);

   118 }

   119 

   120 template <class BidirectionalGraph>

   121 inline reverse_graph<BidirectionalGraph, BidirectionalGraph&>

   122 make_reverse_graph(BidirectionalGraph& g)

   123 {

   124     return reverse_graph<BidirectionalGraph, BidirectionalGraph&>(g);

   125 }

   126 

   127 template <class BidirectionalGraph, class GRef>

   128 std::pair<typename reverse_graph<BidirectionalGraph>::vertex_iterator,

   129           typename reverse_graph<BidirectionalGraph>::vertex_iterator>

   130 vertices(const reverse_graph<BidirectionalGraph,GRef>& g)

   131 {

   132     return vertices(g.m_g);

   133 }

   134 

   135 template <class BidirectionalGraph, class GRef>

   136 std::pair<typename reverse_graph<BidirectionalGraph>::edge_iterator,

   137           typename reverse_graph<BidirectionalGraph>::edge_iterator>

   138 edges(const reverse_graph<BidirectionalGraph,GRef>& g)

   139 {

   140     return edges(g.m_g);

   141 }

   142 

   143 template <class BidirectionalGraph, class GRef>

   144 inline std::pair<typename BidirectionalGraph::in_edge_iterator,

   145                  typename BidirectionalGraph::in_edge_iterator>

   146 out_edges(const typename BidirectionalGraph::vertex_descriptor u,

   147           const reverse_graph<BidirectionalGraph,GRef>& g)

   148 {

   149     return in_edges(u, g.m_g);

   150 }

   151 

   152 template <class BidirectionalGraph, class GRef>

   153 inline typename BidirectionalGraph::vertices_size_type

   154 num_vertices(const reverse_graph<BidirectionalGraph,GRef>& g)

   155 {

   156     return num_vertices(g.m_g);

   157 }

   158 

   159 template <class BidirectionalGraph, class GRef>

   160 inline typename reverse_graph<BidirectionalGraph>::edges_size_type

   161 num_edges(const reverse_graph<BidirectionalGraph,GRef>& g)

   162 {

   163     return num_edges(g.m_g);

   164 }

   165 

   166 template <class BidirectionalGraph, class GRef>

   167 inline typename BidirectionalGraph::degree_size_type

   168 out_degree(const typename BidirectionalGraph::vertex_descriptor u,

   169            const reverse_graph<BidirectionalGraph,GRef>& g)

   170 {

   171     return in_degree(u, g.m_g);

   172 }

   173 

   174 template <class BidirectionalGraph, class GRef>

   175 inline std::pair<typename BidirectionalGraph::edge_descriptor, bool>

   176 edge(const typename BidirectionalGraph::vertex_descriptor u,

   177      const typename BidirectionalGraph::vertex_descriptor v,

   178      const reverse_graph<BidirectionalGraph,GRef>& g)

   179 {

   180     return edge(v, u, g.m_g);

   181 }

   182 

   183 template <class BidirectionalGraph, class GRef>

   184 inline std::pair<typename BidirectionalGraph::out_edge_iterator,

   185     typename BidirectionalGraph::out_edge_iterator>

   186 in_edges(const typename BidirectionalGraph::vertex_descriptor u,

   187          const reverse_graph<BidirectionalGraph,GRef>& g)

   188 {

   189     return out_edges(u, g.m_g);

   190 }

   191 

   192 template <class BidirectionalGraph, class GRef>

   193 inline std::pair<typename reverse_graph<BidirectionalGraph,GRef>::adjacency_iterator,

   194     typename reverse_graph<BidirectionalGraph,GRef>::adjacency_iterator>

   195 adjacent_vertices(const typename BidirectionalGraph::vertex_descriptor u,

   196                   const reverse_graph<BidirectionalGraph,GRef>& g)

   197 {

   198     typedef reverse_graph<BidirectionalGraph,GRef> Graph;

   199     typename Graph::out_edge_iterator first, last;

   200     tie(first, last) = out_edges(u, g);

   201     typedef typename Graph::adjacency_iterator adjacency_iterator;

   202     return std::make_pair(adjacency_iterator(first, const_cast<Graph*>(&g)),

   203                           adjacency_iterator(last, const_cast<Graph*>(&g)));

   204 }

   205 

   206 template <class BidirectionalGraph, class GRef>

   207 inline typename BidirectionalGraph::degree_size_type

   208 in_degree(const typename BidirectionalGraph::vertex_descriptor u,

   209           const reverse_graph<BidirectionalGraph,GRef>& g)

   210 {

   211     return out_degree(u, g.m_g);

   212 }

   213 

   214 template <class Edge, class BidirectionalGraph, class GRef>

   215 inline typename graph_traits<BidirectionalGraph>::vertex_descriptor

   216 source(const Edge& e, const reverse_graph<BidirectionalGraph,GRef>& g)

   217 {

   218     return target(e, g.m_g);

   219 }

   220 

   221 template <class Edge, class BidirectionalGraph, class GRef>

   222 inline typename graph_traits<BidirectionalGraph>::vertex_descriptor

   223 target(const Edge& e, const reverse_graph<BidirectionalGraph,GRef>& g)

   224 {

   225     return source(e, g.m_g);

   226 }

   227 

   228 

   229 namespace detail {

   230 

   231   struct reverse_graph_vertex_property_selector {

   232     template <class ReverseGraph, class Property, class Tag>

   233     struct bind_ {

   234       typedef typename ReverseGraph::base_type Graph;

   235       typedef property_map<Graph, Tag> PMap;

   236       typedef typename PMap::type type;

   237       typedef typename PMap::const_type const_type;

   238     };

   239   };

   240 

   241   struct reverse_graph_edge_property_selector {

   242     template <class ReverseGraph, class Property, class Tag>

   243     struct bind_ {

   244       typedef typename ReverseGraph::base_type Graph;

   245       typedef property_map<Graph, Tag> PMap;

   246       typedef typename PMap::type type;

   247       typedef typename PMap::const_type const_type;

   248     };

   249   };

   250 

   251 } // namespace detail

   252 

   253 template <>

   254 struct vertex_property_selector<reverse_graph_tag> {

   255   typedef detail::reverse_graph_vertex_property_selector type;

   256 };

   257 

   258 template <>

   259 struct edge_property_selector<reverse_graph_tag> {

   260   typedef detail::reverse_graph_edge_property_selector type;

   261 };

   262 

   263 template <class BidirGraph, class GRef, class Property>

   264 typename property_map<BidirGraph, Property>::type

   265 get(Property p, reverse_graph<BidirGraph,GRef>& g)

   266 {

   267   return get(p, g.m_g);

   268 }

   269 

   270 template <class BidirGraph, class GRef, class Property>

   271 typename property_map<BidirGraph, Property>::const_type

   272 get(Property p, const reverse_graph<BidirGraph,GRef>& g)

   273 {

   274   const BidirGraph& gref = g.m_g; // in case GRef is non-const

   275   return get(p, gref);

   276 }

   277 

   278 template <class BidirectionalGraph, class GRef, class Property, class Key>

   279 typename property_traits<

   280   typename property_map<BidirectionalGraph, Property>::const_type

   281 >::value_type

   282 get(Property p, const reverse_graph<BidirectionalGraph,GRef>& g, const Key& k)

   283 {

   284   return get(p, g.m_g, k);

   285 }

   286 

   287 template <class BidirectionalGraph, class GRef, class Property, class Key, class Value>

   288 void

   289 put(Property p, const reverse_graph<BidirectionalGraph,GRef>& g, const Key& k,

   290     const Value& val)

   291 {

   292   put(p, g.m_g, k, val);

   293 }

   294 

   295 template<typename BidirectionalGraph, typename GRef, typename Tag,

   296          typename Value>

   297 inline void

   298 set_property(const reverse_graph<BidirectionalGraph,GRef>& g, Tag tag, 

   299              const Value& value)

   300 {

   301   set_property(g.m_g, tag, value);

   302 }

   303 

   304 template<typename BidirectionalGraph, typename GRef, typename Tag>

   305 inline

   306 typename graph_property<BidirectionalGraph, Tag>::type

   307 get_property(const reverse_graph<BidirectionalGraph,GRef>& g, Tag tag)

   308 {

   309   return get_property(g.m_g, tag);

   310 }

   311 

   312 } // namespace boost

   313 

   314 #endif