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/iterator/transform_iterator.hpp>
12#include <boost/tuple/tuple.hpp>
13#include <boost/type_traits.hpp>
14#include <boost/mpl/if.hpp>
15
16namespace boost {
17
18struct reverse_graph_tag { };
19
20 namespace detail {
21
22 template <typename EdgeDesc>
23 class reverse_graph_edge_descriptor {
24 public:
25 EdgeDesc underlying_descx; // Odd name is because this needs to be public but shouldn't be exposed to users anymore
26
27 private:
28 typedef EdgeDesc base_descriptor_type;
29
30 public:
31 explicit reverse_graph_edge_descriptor(const EdgeDesc& underlying_descx = EdgeDesc())
32 : underlying_descx(underlying_descx) {}
33
34 friend bool operator==(const reverse_graph_edge_descriptor& a, const reverse_graph_edge_descriptor& b) {
35 return a.underlying_descx == b.underlying_descx;
36 }
37 friend bool operator!=(const reverse_graph_edge_descriptor& a, const reverse_graph_edge_descriptor& b) {
38 return a.underlying_descx != b.underlying_descx;
39 }
40 friend bool operator<(const reverse_graph_edge_descriptor& a, const reverse_graph_edge_descriptor& b) {
41 return a.underlying_descx < b.underlying_descx;
42 }
43 friend bool operator>(const reverse_graph_edge_descriptor& a, const reverse_graph_edge_descriptor& b) {
44 return a.underlying_descx > b.underlying_descx;
45 }
46 friend bool operator<=(const reverse_graph_edge_descriptor& a, const reverse_graph_edge_descriptor& b) {
47 return a.underlying_descx <= b.underlying_descx;
48 }
49 friend bool operator>=(const reverse_graph_edge_descriptor& a, const reverse_graph_edge_descriptor& b) {
50 return a.underlying_descx >= b.underlying_descx;
51 }
52 };
53
54 template <typename EdgeDesc>
55 struct reverse_graph_edge_descriptor_maker {
56 typedef reverse_graph_edge_descriptor<EdgeDesc> result_type;
57
58 reverse_graph_edge_descriptor<EdgeDesc> operator()(const EdgeDesc& ed) const {
59 return reverse_graph_edge_descriptor<EdgeDesc>(ed);
60 }
61 };
62
63 template <typename EdgeDesc, typename Iter>
64 std::pair<transform_iterator<reverse_graph_edge_descriptor_maker<EdgeDesc>, Iter>,
65 transform_iterator<reverse_graph_edge_descriptor_maker<EdgeDesc>, Iter> >
66 reverse_edge_iter_pair(const std::pair<Iter, Iter>& ip) {
67 return std::make_pair(make_transform_iterator(ip.first, reverse_graph_edge_descriptor_maker<EdgeDesc>()),
68 make_transform_iterator(ip.second, reverse_graph_edge_descriptor_maker<EdgeDesc>()));
69 }
70
71 // Get the underlying descriptor from a vertex or edge descriptor
72 template <typename Desc>
73 struct get_underlying_descriptor_from_reverse_descriptor {
74 typedef Desc type;
75 static Desc convert(const Desc& d) {return d;}
76 };
77 template <typename Desc>
78 struct get_underlying_descriptor_from_reverse_descriptor<reverse_graph_edge_descriptor<Desc> > {
79 typedef Desc type;
80 static Desc convert(const reverse_graph_edge_descriptor<Desc>& d) {return d.underlying_descx;}
81 };
82
83 template <bool isEdgeList> struct choose_rev_edge_iter { };
84 template <> struct choose_rev_edge_iter<true> {
85 template <class G> struct bind_ {
86 typedef transform_iterator<reverse_graph_edge_descriptor_maker<typename graph_traits<G>::edge_descriptor>, typename graph_traits<G>::edge_iterator> type;
87 };
88 };
89 template <> struct choose_rev_edge_iter<false> {
90 template <class G> struct bind_ {
91 typedef void type;
92 };
93 };
94
95 } // namespace detail
96
97template <class BidirectionalGraph, class GraphRef = const BidirectionalGraph&>
98class reverse_graph {
99 typedef reverse_graph<BidirectionalGraph, GraphRef> Self;
100 typedef graph_traits<BidirectionalGraph> Traits;
101 public:
102 typedef BidirectionalGraph base_type;
103 typedef GraphRef base_ref_type;
104
105 // Constructor
106 reverse_graph(GraphRef g) : m_g(g) {}
107 // Conversion from reverse_graph on non-const reference to one on const reference
108 reverse_graph(const reverse_graph<BidirectionalGraph, BidirectionalGraph&>& o): m_g(o.m_g) {}
109
110 // Graph requirements
111 typedef typename Traits::vertex_descriptor vertex_descriptor;
112 typedef detail::reverse_graph_edge_descriptor<typename Traits::edge_descriptor> edge_descriptor;
113 typedef typename Traits::directed_category directed_category;
114 typedef typename Traits::edge_parallel_category edge_parallel_category;
115 typedef typename Traits::traversal_category traversal_category;
116
117 // IncidenceGraph requirements
118 typedef transform_iterator<detail::reverse_graph_edge_descriptor_maker<typename Traits::edge_descriptor>, typename Traits::in_edge_iterator> out_edge_iterator;
119 typedef typename Traits::degree_size_type degree_size_type;
120
121 // BidirectionalGraph requirements
122 typedef transform_iterator<detail::reverse_graph_edge_descriptor_maker<typename Traits::edge_descriptor>, typename Traits::out_edge_iterator> in_edge_iterator;
123
124 // AdjacencyGraph requirements
125 typedef typename adjacency_iterator_generator<Self, vertex_descriptor, out_edge_iterator>::type adjacency_iterator;
126
127 // VertexListGraph requirements
128 typedef typename Traits::vertex_iterator vertex_iterator;
129
130 // EdgeListGraph requirements
131 enum { is_edge_list = is_convertible<traversal_category,
132 edge_list_graph_tag>::value };
133 typedef detail::choose_rev_edge_iter<is_edge_list> ChooseEdgeIter;
134 typedef typename ChooseEdgeIter::
135 template bind_<BidirectionalGraph>::type edge_iterator;
136 typedef typename Traits::vertices_size_type vertices_size_type;
137 typedef typename Traits::edges_size_type edges_size_type;
138
139 typedef reverse_graph_tag graph_tag;
140
141#ifndef BOOST_GRAPH_NO_BUNDLED_PROPERTIES
142 // Bundled properties support
143 template<typename Descriptor>
144 typename graph::detail::bundled_result<
145 BidirectionalGraph,
146 typename detail::get_underlying_descriptor_from_reverse_descriptor<Descriptor>::type
147 >::type&
148 operator[](Descriptor x)
149 { return m_g[detail::get_underlying_descriptor_from_reverse_descriptor<Descriptor>::convert(x)]; }
150
151 template<typename Descriptor>
152 typename graph::detail::bundled_result<
153 BidirectionalGraph,
154 typename detail::get_underlying_descriptor_from_reverse_descriptor<Descriptor>::type
155 >::type const&
156 operator[](Descriptor x) const
157 { return m_g[detail::get_underlying_descriptor_from_reverse_descriptor<Descriptor>::convert(x)]; }
158#endif // BOOST_GRAPH_NO_BUNDLED_PROPERTIES
159
160 static vertex_descriptor null_vertex()
161 { return Traits::null_vertex(); }
162
163 // would be private, but template friends aren't portable enough.
164 // private:
165 GraphRef m_g;
166};
167
168
169// These are separate so they are not instantiated unless used (see bug 1021)
170template <class BidirectionalGraph, class GraphRef>
171struct vertex_property_type<reverse_graph<BidirectionalGraph, GraphRef> > {
172 typedef typename boost::vertex_property_type<BidirectionalGraph>::type type;
173};
174
175template <class BidirectionalGraph, class GraphRef>
176struct edge_property_type<reverse_graph<BidirectionalGraph, GraphRef> > {
177 typedef typename boost::edge_property_type<BidirectionalGraph>::type type;
178};
179
180template <class BidirectionalGraph, class GraphRef>
181struct graph_property_type<reverse_graph<BidirectionalGraph, GraphRef> > {
182 typedef typename boost::graph_property_type<BidirectionalGraph>::type type;
183};
184
185#ifndef BOOST_GRAPH_NO_BUNDLED_PROPERTIES
186 template<typename Graph, typename GraphRef>
187 struct vertex_bundle_type<reverse_graph<Graph, GraphRef> >
188 : vertex_bundle_type<Graph> { };
189
190 template<typename Graph, typename GraphRef>
191 struct edge_bundle_type<reverse_graph<Graph, GraphRef> >
192 : edge_bundle_type<Graph> { };
193
194 template<typename Graph, typename GraphRef>
195 struct graph_bundle_type<reverse_graph<Graph, GraphRef> >
196 : graph_bundle_type<Graph> { };
197#endif // BOOST_GRAPH_NO_BUNDLED_PROPERTIES
198
199template <class BidirectionalGraph>
200inline reverse_graph<BidirectionalGraph>
201make_reverse_graph(const BidirectionalGraph& g)
202{
203 return reverse_graph<BidirectionalGraph>(g);
204}
205
206template <class BidirectionalGraph>
207inline reverse_graph<BidirectionalGraph, BidirectionalGraph&>
208make_reverse_graph(BidirectionalGraph& g)
209{
210 return reverse_graph<BidirectionalGraph, BidirectionalGraph&>(g);
211}
212
213template <class BidirectionalGraph, class GRef>
214std::pair<typename reverse_graph<BidirectionalGraph>::vertex_iterator,
215 typename reverse_graph<BidirectionalGraph>::vertex_iterator>
216vertices(const reverse_graph<BidirectionalGraph,GRef>& g)
217{
218 return vertices(g.m_g);
219}
220
221template <class BidirectionalGraph, class GRef>
222std::pair<typename reverse_graph<BidirectionalGraph>::edge_iterator,
223 typename reverse_graph<BidirectionalGraph>::edge_iterator>
224edges(const reverse_graph<BidirectionalGraph,GRef>& g)
225{
226 return detail::reverse_edge_iter_pair<typename graph_traits<BidirectionalGraph>::edge_descriptor>(edges(g.m_g));
227}
228
229template <class BidirectionalGraph, class GRef>
230inline std::pair<typename reverse_graph<BidirectionalGraph>::out_edge_iterator,
231 typename reverse_graph<BidirectionalGraph>::out_edge_iterator>
232out_edges(const typename graph_traits<BidirectionalGraph>::vertex_descriptor u,
233 const reverse_graph<BidirectionalGraph,GRef>& g)
234{
235 return detail::reverse_edge_iter_pair<typename graph_traits<BidirectionalGraph>::edge_descriptor>(in_edges(u, g.m_g));
236}
237
238template <class BidirectionalGraph, class GRef>
239inline typename graph_traits<BidirectionalGraph>::vertices_size_type
240num_vertices(const reverse_graph<BidirectionalGraph,GRef>& g)
241{
242 return num_vertices(g.m_g);
243}
244
245template <class BidirectionalGraph, class GRef>
246inline typename reverse_graph<BidirectionalGraph>::edges_size_type
247num_edges(const reverse_graph<BidirectionalGraph,GRef>& g)
248{
249 return num_edges(g.m_g);
250}
251
252template <class BidirectionalGraph, class GRef>
253inline typename graph_traits<BidirectionalGraph>::degree_size_type
254out_degree(const typename graph_traits<BidirectionalGraph>::vertex_descriptor u,
255 const reverse_graph<BidirectionalGraph,GRef>& g)
256{
257 return in_degree(u, g.m_g);
258}
259
260template <class BidirectionalGraph, class GRef>
261inline typename graph_traits<BidirectionalGraph>::vertex_descriptor
262vertex(const typename graph_traits<BidirectionalGraph>::vertices_size_type v,
263 const reverse_graph<BidirectionalGraph,GRef>& g)
264{
265 return vertex(v, g.m_g);
266}
267
268template <class BidirectionalGraph, class GRef>
269inline std::pair< typename graph_traits<reverse_graph<BidirectionalGraph,GRef> >::edge_descriptor,
270 bool>
271edge(const typename graph_traits<BidirectionalGraph>::vertex_descriptor u,
272 const typename graph_traits<BidirectionalGraph>::vertex_descriptor v,
273 const reverse_graph<BidirectionalGraph,GRef>& g)
274{
275 typedef typename graph_traits<BidirectionalGraph>::edge_descriptor underlying_edge_descriptor;
276 std::pair<underlying_edge_descriptor, bool> e = edge(v, u, g.m_g);
277 return std::make_pair(detail::reverse_graph_edge_descriptor<underlying_edge_descriptor>(e.first), e.second);
278}
279
280template <class BidirectionalGraph, class GRef>
281inline std::pair<typename reverse_graph<BidirectionalGraph>::in_edge_iterator,
282 typename reverse_graph<BidirectionalGraph>::in_edge_iterator>
283in_edges(const typename graph_traits<BidirectionalGraph>::vertex_descriptor u,
284 const reverse_graph<BidirectionalGraph,GRef>& g)
285{
286 return detail::reverse_edge_iter_pair<typename graph_traits<BidirectionalGraph>::edge_descriptor>(out_edges(u, g.m_g));
287}
288
289template <class BidirectionalGraph, class GRef>
290inline std::pair<typename reverse_graph<BidirectionalGraph,GRef>::adjacency_iterator,
291 typename reverse_graph<BidirectionalGraph,GRef>::adjacency_iterator>
292adjacent_vertices(typename graph_traits<BidirectionalGraph>::vertex_descriptor u,
293 const reverse_graph<BidirectionalGraph,GRef>& g)
294{
295 typedef reverse_graph<BidirectionalGraph,GRef> Graph;
296 typename graph_traits<Graph>::out_edge_iterator first, last;
297 boost::tie(first, last) = out_edges(u, g);
298 typedef typename graph_traits<Graph>::adjacency_iterator adjacency_iterator;
299 return std::make_pair(adjacency_iterator(first, const_cast<Graph*>(&g)),
300 adjacency_iterator(last, const_cast<Graph*>(&g)));
301}
302
303template <class BidirectionalGraph, class GRef>
304inline typename graph_traits<BidirectionalGraph>::degree_size_type
305in_degree(const typename graph_traits<BidirectionalGraph>::vertex_descriptor u,
306 const reverse_graph<BidirectionalGraph,GRef>& g)
307{
308 return out_degree(u, g.m_g);
309}
310
311template <class Edge, class BidirectionalGraph, class GRef>
312inline typename graph_traits<BidirectionalGraph>::vertex_descriptor
313source(const detail::reverse_graph_edge_descriptor<Edge>& e, const reverse_graph<BidirectionalGraph,GRef>& g)
314{
315 return target(e.underlying_descx, g.m_g);
316}
317
318template <class Edge, class BidirectionalGraph, class GRef>
319inline typename graph_traits<BidirectionalGraph>::vertex_descriptor
320target(const detail::reverse_graph_edge_descriptor<Edge>& e, const reverse_graph<BidirectionalGraph,GRef>& g)
321{
322 return source(e.underlying_descx, g.m_g);
323}
324
325
326namespace detail {
327
328 template <typename PM>
329 struct reverse_graph_edge_property_map {
330 private:
331 PM underlying_pm;
332
333 public:
334 typedef reverse_graph_edge_descriptor<typename property_traits<PM>::key_type> key_type;
335 typedef typename property_traits<PM>::value_type value_type;
336 typedef typename property_traits<PM>::reference reference;
337 typedef typename property_traits<PM>::category category;
338
339 explicit reverse_graph_edge_property_map(const PM& pm): underlying_pm(pm) {}
340
341 friend reference
342 get(const reverse_graph_edge_property_map& m,
343 const key_type& e) {
344 return get(m.underlying_pm, e.underlying_descx);
345 }
346
347 friend void
348 put(const reverse_graph_edge_property_map& m,
349 const key_type& e,
350 const value_type& v) {
351 put(m.underlying_pm, e.underlying_descx, v);
352 }
353
354 reference operator[](const key_type& k) const {
355 return (this->underlying_pm)[k.underlying_descx];
356 }
357 };
358
359} // namespace detail
360
361template <class BidirGraph, class GRef, class Property>
362struct property_map<reverse_graph<BidirGraph, GRef>, Property> {
363 typedef boost::is_same<typename detail::property_kind_from_graph<BidirGraph, Property>::type, edge_property_tag> is_edge_prop;
364 typedef boost::is_const<typename boost::remove_reference<GRef>::type> is_ref_const;
365 typedef typename boost::mpl::if_<
366 is_ref_const,
367 typename property_map<BidirGraph, Property>::const_type,
368 typename property_map<BidirGraph, Property>::type>::type
369 orig_type;
370 typedef typename property_map<BidirGraph, Property>::const_type orig_const_type;
371 typedef typename boost::mpl::if_<is_edge_prop, detail::reverse_graph_edge_property_map<orig_type>, orig_type>::type type;
372 typedef typename boost::mpl::if_<is_edge_prop, detail::reverse_graph_edge_property_map<orig_const_type>, orig_const_type>::type const_type;
373};
374
375template <class BidirGraph, class GRef, class Property>
376struct property_map<const reverse_graph<BidirGraph, GRef>, Property> {
377 typedef boost::is_same<typename detail::property_kind_from_graph<BidirGraph, Property>::type, edge_property_tag> is_edge_prop;
378 typedef typename property_map<BidirGraph, Property>::const_type orig_const_type;
379 typedef typename boost::mpl::if_<is_edge_prop, detail::reverse_graph_edge_property_map<orig_const_type>, orig_const_type>::type const_type;
380 typedef const_type type;
381};
382
383template <class BidirGraph, class GRef, class Property>
384typename disable_if<
385 is_same<Property, edge_underlying_t>,
386 typename property_map<reverse_graph<BidirGraph,GRef>, Property>::type>::type
387get(Property p, reverse_graph<BidirGraph,GRef>& g)
388{
389 return typename property_map<reverse_graph<BidirGraph,GRef>, Property>::type(get(p, g.m_g));
390}
391
392template <class BidirGraph, class GRef, class Property>
393typename disable_if<
394 is_same<Property, edge_underlying_t>,
395 typename property_map<reverse_graph<BidirGraph,GRef>, Property>::const_type>::type
396get(Property p, const reverse_graph<BidirGraph,GRef>& g)
397{
398 const BidirGraph& gref = g.m_g; // in case GRef is non-const
399 return typename property_map<reverse_graph<BidirGraph,GRef>, Property>::const_type(get(p, gref));
400}
401
402template <class BidirectionalGraph, class GRef, class Property, class Key>
403typename disable_if<
404 is_same<Property, edge_underlying_t>,
405 typename property_traits<
406 typename property_map<reverse_graph<BidirectionalGraph, GRef>, Property>::const_type
407 >::value_type>::type
408get(Property p, const reverse_graph<BidirectionalGraph,GRef>& g, const Key& k)
409{
410 return get(get(p, g), k);
411}
412
413template <class BidirectionalGraph, class GRef, class Property, class Key, class Value>
414void
415put(Property p, reverse_graph<BidirectionalGraph,GRef>& g, const Key& k,
416 const Value& val)
417{
418 put(get(p, g), k, val);
419}
420
421// Get the underlying descriptor from a reverse_graph's wrapped edge descriptor
422
423namespace detail {
424 template <class E>
425 struct underlying_edge_desc_map_type {
426 E operator[](const reverse_graph_edge_descriptor<E>& k) const {
427 return k.underlying_descx;
428 }
429 };
430
431 template <class E>
432 E
433 get(underlying_edge_desc_map_type<E> m,
434 const reverse_graph_edge_descriptor<E>& k)
435 {
436 return m[k];
437 }
438}
439
440template <class E>
441struct property_traits<detail::underlying_edge_desc_map_type<E> > {
442 typedef detail::reverse_graph_edge_descriptor<E> key_type;
443 typedef E value_type;
444 typedef const E& reference;
445 typedef readable_property_map_tag category;
446};
447
448template <class Graph, class GRef>
449struct property_map<reverse_graph<Graph, GRef>, edge_underlying_t> {
450 private:
451 typedef typename graph_traits<Graph>::edge_descriptor ed;
452
453 public:
454 typedef detail::underlying_edge_desc_map_type<ed> type;
455 typedef detail::underlying_edge_desc_map_type<ed> const_type;
456};
457
458template <typename T> struct is_reverse_graph: boost::mpl::false_ {};
459template <typename G, typename R> struct is_reverse_graph<reverse_graph<G, R> >: boost::mpl::true_ {};
460
461template <class G>
462typename enable_if<is_reverse_graph<G>,
463 detail::underlying_edge_desc_map_type<typename graph_traits<typename G::base_type>::edge_descriptor> >::type
464get(edge_underlying_t,
465 G&)
466{
467 return detail::underlying_edge_desc_map_type<typename graph_traits<typename G::base_type>::edge_descriptor>();
468}
469
470template <class G>
471typename enable_if<is_reverse_graph<G>, typename graph_traits<typename G::base_type>::edge_descriptor>::type
472get(edge_underlying_t,
473 G&,
474 const typename graph_traits<G>::edge_descriptor& k)
475{
476 return k.underlying_descx;
477}
478
479template <class G>
480typename enable_if<is_reverse_graph<G>, detail::underlying_edge_desc_map_type<typename graph_traits<typename G::base_type>::edge_descriptor> >::type
481get(edge_underlying_t,
482 const G&)
483{
484 return detail::underlying_edge_desc_map_type<typename graph_traits<typename G::base_type>::edge_descriptor>();
485}
486
487template <class G>
488typename enable_if<is_reverse_graph<G>, typename graph_traits<typename G::base_type>::edge_descriptor>::type
489get(edge_underlying_t,
490 const G&,
491 const typename graph_traits<G>::edge_descriptor& k)
492{
493 return k.underlying_descx;
494}
495
496// Access to wrapped graph's graph properties
497
498template<typename BidirectionalGraph, typename GRef, typename Tag,
499 typename Value>
500inline void
501set_property(const reverse_graph<BidirectionalGraph,GRef>& g, Tag tag,
502 const Value& value)
503{
504 set_property(g.m_g, tag, value);
505}
506
507template<typename BidirectionalGraph, typename GRef, typename Tag>
508inline
509typename boost::mpl::if_<
510 boost::is_const<typename boost::remove_reference<GRef>::type>,
511 const typename graph_property<BidirectionalGraph, Tag>::type&,
512 typename graph_property<BidirectionalGraph, Tag>::type& >::type
513get_property(const reverse_graph<BidirectionalGraph,GRef>& g, Tag tag)
514{
515 return get_property(g.m_g, tag);
516}
517
518} // namespace boost
519
520#endif
521

source code of boost/boost/graph/reverse_graph.hpp