boost/graph/reverse_graph.hpp

   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 #if BOOST_WORKAROUND(BOOST_MSVC, < 1300)
  14 // Stay out of the way of the concept checking class
  15 # define BidirectionalGraph BidirectionalGraph_
  16 #endif
  17
  18 namespace boost {
  19
  20 struct reverse_graph_tag { };
  21
  22   namespace detail {
  23
  24     template <bool isEdgeList> struct choose_rev_edge_iter { };
  25     template <> struct choose_rev_edge_iter<true> {
  26       template <class G> struct bind_ {
  27         typedef typename graph_traits<G>::edge_iterator type;
  28       };
  29     };
  30     template <> struct choose_rev_edge_iter<false> {
  31       template <class G> struct bind_ {
  32         typedef void type;
  33       };
  34     };
  35
  36   } // namespace detail
  37
  38 template <class BidirectionalGraph, class GraphRef = const BidirectionalGraph&>
  39 class reverse_graph {
  40     typedef reverse_graph<BidirectionalGraph, GraphRef> Self;
  41     typedef graph_traits<BidirectionalGraph> Traits;
  42  public:
  43     typedef BidirectionalGraph base_type;
  44
  45     // Constructor
  46     reverse_graph(GraphRef g) : m_g(g) {}
  47
  48     // Graph requirements
  49     typedef typename Traits::vertex_descriptor vertex_descriptor;
  50     typedef typename Traits::edge_descriptor edge_descriptor;
  51     typedef typename Traits::directed_category directed_category;
  52     typedef typename Traits::edge_parallel_category edge_parallel_category;
  53     typedef typename Traits::traversal_category traversal_category;
  54
  55     // IncidenceGraph requirements
  56     typedef typename Traits::in_edge_iterator out_edge_iterator;
  57     typedef typename Traits::degree_size_type degree_size_type;
  58
  59     // BidirectionalGraph requirements
  60     typedef typename Traits::out_edge_iterator in_edge_iterator;
  61
  62     // AdjacencyGraph requirements
  63   typedef typename adjacency_iterator_generator<Self,
  64     vertex_descriptor, out_edge_iterator>::type adjacency_iterator;
  65
  66     // VertexListGraph requirements
  67     typedef typename Traits::vertex_iterator vertex_iterator;
  68
  69     // EdgeListGraph requirements
  70     enum { is_edge_list = is_convertible<traversal_category,
  71            edge_list_graph_tag>::value };
  72     typedef detail::choose_rev_edge_iter<is_edge_list> ChooseEdgeIter;
  73     typedef typename ChooseEdgeIter::
  74       template bind_<BidirectionalGraph>::type   edge_iterator;
  75     typedef typename Traits::vertices_size_type vertices_size_type;
  76     typedef typename Traits::edges_size_type edges_size_type;
  77
  78     // More typedefs used by detail::edge_property_map, vertex_property_map
  79     typedef typename boost::edge_property_type<BidirectionalGraph>::type
  80       edge_property_type;
  81     typedef typename boost::vertex_property_type<BidirectionalGraph>::type
  82       vertex_property_type;
  83     typedef reverse_graph_tag graph_tag;
  84
  85 #ifndef BOOST_GRAPH_NO_BUNDLED_PROPERTIES
  86     // Bundled properties support
  87     template<typename Descriptor>
  88     typename graph::detail::bundled_result<BidirectionalGraph,
  89                                            Descriptor>::type&
  90     operator[](Descriptor x)
  91     { return m_g[x]; }
  92
  93     template<typename Descriptor>
  94     typename graph::detail::bundled_result<BidirectionalGraph,
  95                                            Descriptor>::type const&
  96     operator[](Descriptor x) const
  97     { return m_g[x]; }
  98 #endif // BOOST_GRAPH_NO_BUNDLED_PROPERTIES
  99
 100     static vertex_descriptor null_vertex()
 101     { return Traits::null_vertex(); }
 102
 103     // would be private, but template friends aren't portable enough.
 104  // private:
 105     GraphRef m_g;
 106 };
 107
 108 #ifndef BOOST_GRAPH_NO_BUNDLED_PROPERTIES
 109   template<typename Graph, typename GraphRef>
 110   struct vertex_bundle_type<reverse_graph<Graph, GraphRef> >
 111     : vertex_bundle_type<Graph> { };
 112
 113   template<typename Graph, typename GraphRef>
 114   struct edge_bundle_type<reverse_graph<Graph, GraphRef> >
 115     : edge_bundle_type<Graph> { };
 116 #endif // BOOST_GRAPH_NO_BUNDLED_PROPERTIES
 117
 118 template <class BidirectionalGraph>
 119 inline reverse_graph<BidirectionalGraph>
 120 make_reverse_graph(const BidirectionalGraph& g)
 121 {
 122     return reverse_graph<BidirectionalGraph>(g);
 123 }
 124
 125 template <class BidirectionalGraph>
 126 inline reverse_graph<BidirectionalGraph, BidirectionalGraph&>
 127 make_reverse_graph(BidirectionalGraph& g)
 128 {
 129     return reverse_graph<BidirectionalGraph, BidirectionalGraph&>(g);
 130 }
 131
 132 template <class BidirectionalGraph, class GRef>
 133 std::pair<typename reverse_graph<BidirectionalGraph>::vertex_iterator,
 134           typename reverse_graph<BidirectionalGraph>::vertex_iterator>
 135 vertices(const reverse_graph<BidirectionalGraph,GRef>& g)
 136 {
 137     return vertices(g.m_g);
 138 }
 139
 140 template <class BidirectionalGraph, class GRef>
 141 std::pair<typename reverse_graph<BidirectionalGraph>::edge_iterator,
 142           typename reverse_graph<BidirectionalGraph>::edge_iterator>
 143 edges(const reverse_graph<BidirectionalGraph,GRef>& g)
 144 {
 145     return edges(g.m_g);
 146 }
 147
 148 template <class BidirectionalGraph, class GRef>
 149 inline std::pair<typename graph_traits<BidirectionalGraph>::in_edge_iterator,
 150                  typename graph_traits<BidirectionalGraph>::in_edge_iterator>
 151 out_edges(const typename graph_traits<BidirectionalGraph>::vertex_descriptor u,
 152           const reverse_graph<BidirectionalGraph,GRef>& g)
 153 {
 154     return in_edges(u, g.m_g);
 155 }
 156
 157 template <class BidirectionalGraph, class GRef>
 158 inline typename graph_traits<BidirectionalGraph>::vertices_size_type
 159 num_vertices(const reverse_graph<BidirectionalGraph,GRef>& g)
 160 {
 161     return num_vertices(g.m_g);
 162 }
 163
 164 template <class BidirectionalGraph, class GRef>
 165 inline typename reverse_graph<BidirectionalGraph>::edges_size_type
 166 num_edges(const reverse_graph<BidirectionalGraph,GRef>& g)
 167 {
 168     return num_edges(g.m_g);
 169 }
 170
 171 template <class BidirectionalGraph, class GRef>
 172 inline typename graph_traits<BidirectionalGraph>::degree_size_type
 173 out_degree(const typename graph_traits<BidirectionalGraph>::vertex_descriptor u,
 174            const reverse_graph<BidirectionalGraph,GRef>& g)
 175 {
 176     return in_degree(u, g.m_g);
 177 }
 178
 179 template <class BidirectionalGraph, class GRef>
 180 inline std::pair<typename graph_traits<BidirectionalGraph>::edge_descriptor,
 181                  bool>
 182 edge(const typename graph_traits<BidirectionalGraph>::vertex_descriptor u,
 183      const typename graph_traits<BidirectionalGraph>::vertex_descriptor v,
 184      const reverse_graph<BidirectionalGraph,GRef>& g)
 185 {
 186     return edge(v, u, g.m_g);
 187 }
 188
 189 template <class BidirectionalGraph, class GRef>
 190 inline std::pair<typename graph_traits<BidirectionalGraph>::out_edge_iterator,
 191                  typename graph_traits<BidirectionalGraph>::out_edge_iterator>
 192 in_edges(const typename graph_traits<BidirectionalGraph>::vertex_descriptor u,
 193          const reverse_graph<BidirectionalGraph,GRef>& g)
 194 {
 195     return out_edges(u, g.m_g);
 196 }
 197
 198 template <class BidirectionalGraph, class GRef>
 199 inline std::pair<typename reverse_graph<BidirectionalGraph,GRef>::adjacency_iterator,
 200     typename reverse_graph<BidirectionalGraph,GRef>::adjacency_iterator>
 201 adjacent_vertices(typename graph_traits<BidirectionalGraph>::vertex_descriptor u,
 202                   const reverse_graph<BidirectionalGraph,GRef>& g)
 203 {
 204     typedef reverse_graph<BidirectionalGraph,GRef> Graph;
 205     typename graph_traits<Graph>::out_edge_iterator first, last;
 206     tie(first, last) = out_edges(u, g);
 207     typedef typename graph_traits<Graph>::adjacency_iterator adjacency_iterator;
 208     return std::make_pair(adjacency_iterator(first, const_cast<Graph*>(&g)),
 209                           adjacency_iterator(last, const_cast<Graph*>(&g)));
 210 }
 211
 212 template <class BidirectionalGraph, class GRef>
 213 inline typename graph_traits<BidirectionalGraph>::degree_size_type
 214 in_degree(const typename graph_traits<BidirectionalGraph>::vertex_descriptor u,
 215           const reverse_graph<BidirectionalGraph,GRef>& g)
 216 {
 217     return out_degree(u, g.m_g);
 218 }
 219
 220 template <class Edge, class BidirectionalGraph, class GRef>
 221 inline typename graph_traits<BidirectionalGraph>::vertex_descriptor
 222 source(const Edge& e, const reverse_graph<BidirectionalGraph,GRef>& g)
 223 {
 224     return target(e, g.m_g);
 225 }
 226
 227 template <class Edge, class BidirectionalGraph, class GRef>
 228 inline typename graph_traits<BidirectionalGraph>::vertex_descriptor
 229 target(const Edge& e, const reverse_graph<BidirectionalGraph,GRef>& g)
 230 {
 231     return source(e, g.m_g);
 232 }
 233
 234
 235 namespace detail {
 236
 237   struct reverse_graph_vertex_property_selector {
 238     template <class ReverseGraph, class Property, class Tag>
 239     struct bind_ {
 240       typedef typename ReverseGraph::base_type Graph;
 241       typedef property_map<Graph, Tag> PMap;
 242       typedef typename PMap::type type;
 243       typedef typename PMap::const_type const_type;
 244     };
 245   };
 246
 247   struct reverse_graph_edge_property_selector {
 248     template <class ReverseGraph, class Property, class Tag>
 249     struct bind_ {
 250       typedef typename ReverseGraph::base_type Graph;
 251       typedef property_map<Graph, Tag> PMap;
 252       typedef typename PMap::type type;
 253       typedef typename PMap::const_type const_type;
 254     };
 255   };
 256
 257 } // namespace detail
 258
 259 template <>
 260 struct vertex_property_selector<reverse_graph_tag> {
 261   typedef detail::reverse_graph_vertex_property_selector type;
 262 };
 263
 264 template <>
 265 struct edge_property_selector<reverse_graph_tag> {
 266   typedef detail::reverse_graph_edge_property_selector type;
 267 };
 268
 269 template <class BidirGraph, class GRef, class Property>
 270 typename property_map<BidirGraph, Property>::type
 271 get(Property p, reverse_graph<BidirGraph,GRef>& g)
 272 {
 273   return get(p, g.m_g);
 274 }
 275
 276 template <class BidirGraph, class GRef, class Property>
 277 typename property_map<BidirGraph, Property>::const_type
 278 get(Property p, const reverse_graph<BidirGraph,GRef>& g)
 279 {
 280   const BidirGraph& gref = g.m_g; // in case GRef is non-const
 281   return get(p, gref);
 282 }
 283
 284 template <class BidirectionalGraph, class GRef, class Property, class Key>
 285 typename property_traits<
 286   typename property_map<BidirectionalGraph, Property>::const_type
 287 >::value_type
 288 get(Property p, const reverse_graph<BidirectionalGraph,GRef>& g, const Key& k)
 289 {
 290   return get(p, g.m_g, k);
 291 }
 292
 293 template <class BidirectionalGraph, class GRef, class Property, class Key, class Value>
 294 void
 295 put(Property p, const reverse_graph<BidirectionalGraph,GRef>& g, const Key& k,
 296     const Value& val)
 297 {
 298   put(p, g.m_g, k, val);
 299 }
 300
 301 template<typename BidirectionalGraph, typename GRef, typename Tag,
 302          typename Value>
 303 inline void
 304 set_property(const reverse_graph<BidirectionalGraph,GRef>& g, Tag tag,
 305              const Value& value)
 306 {
 307   set_property(g.m_g, tag, value);
 308 }
 309
 310 template<typename BidirectionalGraph, typename GRef, typename Tag>
 311 inline
 312 typename graph_property<BidirectionalGraph, Tag>::type
 313 get_property(const reverse_graph<BidirectionalGraph,GRef>& g, Tag tag)
 314 {
 315   return get_property(g.m_g, tag);
 316 }
 317
 318 } // namespace boost
 319
 320 #if BOOST_WORKAROUND(BOOST_MSVC, < 1300)
 321 // Stay out of the way of the concept checking class
 322 # undef BidirectionalGraph
 323 #endif
 324
 325 #endif