]>
Commit | Line | Data |
---|---|---|
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 | ||
16 | namespace boost { | |
17 | ||
18 | struct 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 | ||
97 | template <class BidirectionalGraph, class GraphRef = const BidirectionalGraph&> | |
98 | class 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) | |
170 | template <class BidirectionalGraph, class GraphRef> | |
171 | struct vertex_property_type<reverse_graph<BidirectionalGraph, GraphRef> > { | |
172 | typedef typename boost::vertex_property_type<BidirectionalGraph>::type type; | |
173 | }; | |
174 | ||
175 | template <class BidirectionalGraph, class GraphRef> | |
176 | struct edge_property_type<reverse_graph<BidirectionalGraph, GraphRef> > { | |
177 | typedef typename boost::edge_property_type<BidirectionalGraph>::type type; | |
178 | }; | |
179 | ||
180 | template <class BidirectionalGraph, class GraphRef> | |
181 | struct 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 | ||
199 | template <class BidirectionalGraph> | |
200 | inline reverse_graph<BidirectionalGraph> | |
201 | make_reverse_graph(const BidirectionalGraph& g) | |
202 | { | |
203 | return reverse_graph<BidirectionalGraph>(g); | |
204 | } | |
205 | ||
206 | template <class BidirectionalGraph> | |
207 | inline reverse_graph<BidirectionalGraph, BidirectionalGraph&> | |
208 | make_reverse_graph(BidirectionalGraph& g) | |
209 | { | |
210 | return reverse_graph<BidirectionalGraph, BidirectionalGraph&>(g); | |
211 | } | |
212 | ||
213 | template <class BidirectionalGraph, class GRef> | |
214 | std::pair<typename reverse_graph<BidirectionalGraph>::vertex_iterator, | |
215 | typename reverse_graph<BidirectionalGraph>::vertex_iterator> | |
216 | vertices(const reverse_graph<BidirectionalGraph,GRef>& g) | |
217 | { | |
218 | return vertices(g.m_g); | |
219 | } | |
220 | ||
221 | template <class BidirectionalGraph, class GRef> | |
222 | std::pair<typename reverse_graph<BidirectionalGraph>::edge_iterator, | |
223 | typename reverse_graph<BidirectionalGraph>::edge_iterator> | |
224 | edges(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 | ||
229 | template <class BidirectionalGraph, class GRef> | |
230 | inline std::pair<typename reverse_graph<BidirectionalGraph>::out_edge_iterator, | |
231 | typename reverse_graph<BidirectionalGraph>::out_edge_iterator> | |
232 | out_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 | ||
238 | template <class BidirectionalGraph, class GRef> | |
239 | inline typename graph_traits<BidirectionalGraph>::vertices_size_type | |
240 | num_vertices(const reverse_graph<BidirectionalGraph,GRef>& g) | |
241 | { | |
242 | return num_vertices(g.m_g); | |
243 | } | |
244 | ||
245 | template <class BidirectionalGraph, class GRef> | |
246 | inline typename reverse_graph<BidirectionalGraph>::edges_size_type | |
247 | num_edges(const reverse_graph<BidirectionalGraph,GRef>& g) | |
248 | { | |
249 | return num_edges(g.m_g); | |
250 | } | |
251 | ||
252 | template <class BidirectionalGraph, class GRef> | |
253 | inline typename graph_traits<BidirectionalGraph>::degree_size_type | |
254 | out_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 | ||
260 | template <class BidirectionalGraph, class GRef> | |
261 | inline typename graph_traits<BidirectionalGraph>::vertex_descriptor | |
262 | vertex(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 | ||
268 | template <class BidirectionalGraph, class GRef> | |
269 | inline std::pair< typename graph_traits<reverse_graph<BidirectionalGraph,GRef> >::edge_descriptor, | |
270 | bool> | |
271 | edge(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 | ||
280 | template <class BidirectionalGraph, class GRef> | |
281 | inline std::pair<typename reverse_graph<BidirectionalGraph>::in_edge_iterator, | |
282 | typename reverse_graph<BidirectionalGraph>::in_edge_iterator> | |
283 | in_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 | ||
289 | template <class BidirectionalGraph, class GRef> | |
290 | inline std::pair<typename reverse_graph<BidirectionalGraph,GRef>::adjacency_iterator, | |
291 | typename reverse_graph<BidirectionalGraph,GRef>::adjacency_iterator> | |
292 | adjacent_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 | ||
303 | template <class BidirectionalGraph, class GRef> | |
304 | inline typename graph_traits<BidirectionalGraph>::degree_size_type | |
305 | in_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 | ||
311 | template <class Edge, class BidirectionalGraph, class GRef> | |
312 | inline typename graph_traits<BidirectionalGraph>::vertex_descriptor | |
313 | source(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 | ||
318 | template <class Edge, class BidirectionalGraph, class GRef> | |
319 | inline typename graph_traits<BidirectionalGraph>::vertex_descriptor | |
320 | target(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 | template <class BidirectionalGraph, class GRef> | |
326 | inline typename graph_traits<BidirectionalGraph>::degree_size_type | |
327 | degree(const typename graph_traits<BidirectionalGraph>::vertex_descriptor u, | |
328 | const reverse_graph<BidirectionalGraph,GRef>& g) | |
329 | { | |
330 | return degree(u, g.m_g); | |
331 | } | |
332 | ||
333 | namespace detail { | |
334 | ||
335 | template <typename PM> | |
336 | struct reverse_graph_edge_property_map { | |
337 | private: | |
338 | PM underlying_pm; | |
339 | ||
340 | public: | |
341 | typedef reverse_graph_edge_descriptor<typename property_traits<PM>::key_type> key_type; | |
342 | typedef typename property_traits<PM>::value_type value_type; | |
343 | typedef typename property_traits<PM>::reference reference; | |
344 | typedef typename property_traits<PM>::category category; | |
345 | ||
346 | explicit reverse_graph_edge_property_map(const PM& pm): underlying_pm(pm) {} | |
347 | ||
348 | friend reference | |
349 | get(const reverse_graph_edge_property_map& m, | |
350 | const key_type& e) { | |
351 | return get(m.underlying_pm, e.underlying_descx); | |
352 | } | |
353 | ||
354 | friend void | |
355 | put(const reverse_graph_edge_property_map& m, | |
356 | const key_type& e, | |
357 | const value_type& v) { | |
358 | put(m.underlying_pm, e.underlying_descx, v); | |
359 | } | |
360 | ||
361 | reference operator[](const key_type& k) const { | |
362 | return (this->underlying_pm)[k.underlying_descx]; | |
363 | } | |
364 | }; | |
365 | ||
366 | } // namespace detail | |
367 | ||
368 | template <class BidirGraph, class GRef, class Property> | |
369 | struct property_map<reverse_graph<BidirGraph, GRef>, Property> { | |
370 | typedef boost::is_same<typename detail::property_kind_from_graph<BidirGraph, Property>::type, edge_property_tag> is_edge_prop; | |
371 | typedef boost::is_const<typename boost::remove_reference<GRef>::type> is_ref_const; | |
372 | typedef typename boost::mpl::if_< | |
373 | is_ref_const, | |
374 | typename property_map<BidirGraph, Property>::const_type, | |
375 | typename property_map<BidirGraph, Property>::type>::type | |
376 | orig_type; | |
377 | typedef typename property_map<BidirGraph, Property>::const_type orig_const_type; | |
378 | typedef typename boost::mpl::if_<is_edge_prop, detail::reverse_graph_edge_property_map<orig_type>, orig_type>::type 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 | }; | |
381 | ||
382 | template <class BidirGraph, class GRef, class Property> | |
383 | struct property_map<const reverse_graph<BidirGraph, GRef>, Property> { | |
384 | typedef boost::is_same<typename detail::property_kind_from_graph<BidirGraph, Property>::type, edge_property_tag> is_edge_prop; | |
385 | typedef typename property_map<BidirGraph, Property>::const_type orig_const_type; | |
386 | typedef typename boost::mpl::if_<is_edge_prop, detail::reverse_graph_edge_property_map<orig_const_type>, orig_const_type>::type const_type; | |
387 | typedef const_type type; | |
388 | }; | |
389 | ||
390 | template <class BidirGraph, class GRef, class Property> | |
391 | typename disable_if< | |
392 | is_same<Property, edge_underlying_t>, | |
393 | typename property_map<reverse_graph<BidirGraph,GRef>, Property>::type>::type | |
394 | get(Property p, reverse_graph<BidirGraph,GRef>& g) | |
395 | { | |
396 | return typename property_map<reverse_graph<BidirGraph,GRef>, Property>::type(get(p, g.m_g)); | |
397 | } | |
398 | ||
399 | template <class BidirGraph, class GRef, class Property> | |
400 | typename disable_if< | |
401 | is_same<Property, edge_underlying_t>, | |
402 | typename property_map<reverse_graph<BidirGraph,GRef>, Property>::const_type>::type | |
403 | get(Property p, const reverse_graph<BidirGraph,GRef>& g) | |
404 | { | |
405 | const BidirGraph& gref = g.m_g; // in case GRef is non-const | |
406 | return typename property_map<reverse_graph<BidirGraph,GRef>, Property>::const_type(get(p, gref)); | |
407 | } | |
408 | ||
409 | template <class BidirectionalGraph, class GRef, class Property, class Key> | |
410 | typename disable_if< | |
411 | is_same<Property, edge_underlying_t>, | |
412 | typename property_traits< | |
413 | typename property_map<reverse_graph<BidirectionalGraph, GRef>, Property>::const_type | |
414 | >::value_type>::type | |
415 | get(Property p, const reverse_graph<BidirectionalGraph,GRef>& g, const Key& k) | |
416 | { | |
417 | return get(get(p, g), k); | |
418 | } | |
419 | ||
420 | template <class BidirectionalGraph, class GRef, class Property, class Key, class Value> | |
421 | void | |
422 | put(Property p, reverse_graph<BidirectionalGraph,GRef>& g, const Key& k, | |
423 | const Value& val) | |
424 | { | |
425 | put(get(p, g), k, val); | |
426 | } | |
427 | ||
428 | // Get the underlying descriptor from a reverse_graph's wrapped edge descriptor | |
429 | ||
430 | namespace detail { | |
431 | template <class E> | |
432 | struct underlying_edge_desc_map_type { | |
433 | E operator[](const reverse_graph_edge_descriptor<E>& k) const { | |
434 | return k.underlying_descx; | |
435 | } | |
436 | }; | |
437 | ||
438 | template <class E> | |
439 | E | |
440 | get(underlying_edge_desc_map_type<E> m, | |
441 | const reverse_graph_edge_descriptor<E>& k) | |
442 | { | |
443 | return m[k]; | |
444 | } | |
445 | } | |
446 | ||
447 | template <class E> | |
448 | struct property_traits<detail::underlying_edge_desc_map_type<E> > { | |
449 | typedef detail::reverse_graph_edge_descriptor<E> key_type; | |
450 | typedef E value_type; | |
451 | typedef const E& reference; | |
452 | typedef readable_property_map_tag category; | |
453 | }; | |
454 | ||
455 | template <class Graph, class GRef> | |
456 | struct property_map<reverse_graph<Graph, GRef>, edge_underlying_t> { | |
457 | private: | |
458 | typedef typename graph_traits<Graph>::edge_descriptor ed; | |
459 | ||
460 | public: | |
461 | typedef detail::underlying_edge_desc_map_type<ed> type; | |
462 | typedef detail::underlying_edge_desc_map_type<ed> const_type; | |
463 | }; | |
464 | ||
465 | template <typename T> struct is_reverse_graph: boost::mpl::false_ {}; | |
466 | template <typename G, typename R> struct is_reverse_graph<reverse_graph<G, R> >: boost::mpl::true_ {}; | |
467 | ||
468 | template <class G> | |
469 | typename enable_if<is_reverse_graph<G>, | |
470 | detail::underlying_edge_desc_map_type<typename graph_traits<typename G::base_type>::edge_descriptor> >::type | |
471 | get(edge_underlying_t, | |
472 | G&) | |
473 | { | |
474 | return detail::underlying_edge_desc_map_type<typename graph_traits<typename G::base_type>::edge_descriptor>(); | |
475 | } | |
476 | ||
477 | template <class G> | |
478 | typename enable_if<is_reverse_graph<G>, typename graph_traits<typename G::base_type>::edge_descriptor>::type | |
479 | get(edge_underlying_t, | |
480 | G&, | |
481 | const typename graph_traits<G>::edge_descriptor& k) | |
482 | { | |
483 | return k.underlying_descx; | |
484 | } | |
485 | ||
486 | template <class G> | |
487 | typename enable_if<is_reverse_graph<G>, detail::underlying_edge_desc_map_type<typename graph_traits<typename G::base_type>::edge_descriptor> >::type | |
488 | get(edge_underlying_t, | |
489 | const G&) | |
490 | { | |
491 | return detail::underlying_edge_desc_map_type<typename graph_traits<typename G::base_type>::edge_descriptor>(); | |
492 | } | |
493 | ||
494 | template <class G> | |
495 | typename enable_if<is_reverse_graph<G>, typename graph_traits<typename G::base_type>::edge_descriptor>::type | |
496 | get(edge_underlying_t, | |
497 | const G&, | |
498 | const typename graph_traits<G>::edge_descriptor& k) | |
499 | { | |
500 | return k.underlying_descx; | |
501 | } | |
502 | ||
503 | // Access to wrapped graph's graph properties | |
504 | ||
505 | template<typename BidirectionalGraph, typename GRef, typename Tag, | |
506 | typename Value> | |
507 | inline void | |
508 | set_property(const reverse_graph<BidirectionalGraph,GRef>& g, Tag tag, | |
509 | const Value& value) | |
510 | { | |
511 | set_property(g.m_g, tag, value); | |
512 | } | |
513 | ||
514 | template<typename BidirectionalGraph, typename GRef, typename Tag> | |
515 | inline | |
516 | typename boost::mpl::if_< | |
517 | boost::is_const<typename boost::remove_reference<GRef>::type>, | |
518 | const typename graph_property<BidirectionalGraph, Tag>::type&, | |
519 | typename graph_property<BidirectionalGraph, Tag>::type& >::type | |
520 | get_property(const reverse_graph<BidirectionalGraph,GRef>& g, Tag tag) | |
521 | { | |
522 | return get_property(g.m_g, tag); | |
523 | } | |
524 | ||
525 | } // namespace boost | |
526 | ||
527 | #endif |