boost/graph/reverse_graph.hpp

0001 //  (C) Copyright David Abrahams 2000.
0002 // Distributed under the Boost Software License, Version 1.0. (See
0003 // accompanying file LICENSE_1_0.txt or copy at
0004 // http://www.boost.org/LICENSE_1_0.txt)
0005
0006 #ifndef REVERSE_GRAPH_DWA092300_H_
0007 #define REVERSE_GRAPH_DWA092300_H_
0008
0009 #include <boost/graph/adjacency_iterator.hpp>
0010 #include <boost/graph/properties.hpp>
0011 #include <boost/iterator/transform_iterator.hpp>
0012 #include <boost/tuple/tuple.hpp>
0013 #include <boost/type_traits.hpp>
0014 #include <boost/mpl/if.hpp>
0015
0016 namespace boost
0017 {
0018
0019 struct reverse_graph_tag
0020 {
0021 };
0022
0023 namespace detail
0024 {
0025
0026     template < typename EdgeDesc > class reverse_graph_edge_descriptor
0027     {
0028     public:
0029         EdgeDesc
0030             underlying_descx; // Odd name is because this needs to be public but
0031                               // shouldn't be exposed to users anymore
0032
0033     private:
0034         typedef EdgeDesc base_descriptor_type;
0035
0036     public:
0037         explicit reverse_graph_edge_descriptor(
0038             const EdgeDesc& underlying_descx = EdgeDesc())
0039         : underlying_descx(underlying_descx)
0040         {
0041         }
0042
0043         friend bool operator==(const reverse_graph_edge_descriptor& a,
0044             const reverse_graph_edge_descriptor& b)
0045         {
0046             return a.underlying_descx == b.underlying_descx;
0047         }
0048         friend bool operator!=(const reverse_graph_edge_descriptor& a,
0049             const reverse_graph_edge_descriptor& b)
0050         {
0051             return a.underlying_descx != b.underlying_descx;
0052         }
0053         friend bool operator<(const reverse_graph_edge_descriptor& a,
0054             const reverse_graph_edge_descriptor& b)
0055         {
0056             return a.underlying_descx < b.underlying_descx;
0057         }
0058         friend bool operator>(const reverse_graph_edge_descriptor& a,
0059             const reverse_graph_edge_descriptor& b)
0060         {
0061             return a.underlying_descx > b.underlying_descx;
0062         }
0063         friend bool operator<=(const reverse_graph_edge_descriptor& a,
0064             const reverse_graph_edge_descriptor& b)
0065         {
0066             return a.underlying_descx <= b.underlying_descx;
0067         }
0068         friend bool operator>=(const reverse_graph_edge_descriptor& a,
0069             const reverse_graph_edge_descriptor& b)
0070         {
0071             return a.underlying_descx >= b.underlying_descx;
0072         }
0073     };
0074
0075     template < typename EdgeDesc > struct reverse_graph_edge_descriptor_maker
0076     {
0077         typedef reverse_graph_edge_descriptor< EdgeDesc > result_type;
0078
0079         reverse_graph_edge_descriptor< EdgeDesc > operator()(
0080             const EdgeDesc& ed) const
0081         {
0082             return reverse_graph_edge_descriptor< EdgeDesc >(ed);
0083         }
0084     };
0085
0086     template < typename EdgeDesc, typename Iter >
0087     std::pair< transform_iterator<
0088                    reverse_graph_edge_descriptor_maker< EdgeDesc >, Iter >,
0089         transform_iterator< reverse_graph_edge_descriptor_maker< EdgeDesc >,
0090             Iter > >
0091     reverse_edge_iter_pair(const std::pair< Iter, Iter >& ip)
0092     {
0093         return std::make_pair(
0094             make_transform_iterator(
0095                 ip.first, reverse_graph_edge_descriptor_maker< EdgeDesc >()),
0096             make_transform_iterator(
0097                 ip.second, reverse_graph_edge_descriptor_maker< EdgeDesc >()));
0098     }
0099
0100     // Get the underlying descriptor from a vertex or edge descriptor
0101     template < typename Desc >
0102     struct get_underlying_descriptor_from_reverse_descriptor
0103     {
0104         typedef Desc type;
0105         static Desc convert(const Desc& d) { return d; }
0106     };
0107     template < typename Desc >
0108     struct get_underlying_descriptor_from_reverse_descriptor<
0109         reverse_graph_edge_descriptor< Desc > >
0110     {
0111         typedef Desc type;
0112         static Desc convert(const reverse_graph_edge_descriptor< Desc >& d)
0113         {
0114             return d.underlying_descx;
0115         }
0116     };
0117
0118     template < bool isEdgeList > struct choose_rev_edge_iter
0119     {
0120     };
0121     template <> struct choose_rev_edge_iter< true >
0122     {
0123         template < class G > struct bind_
0124         {
0125             typedef transform_iterator<
0126                 reverse_graph_edge_descriptor_maker<
0127                     typename graph_traits< G >::edge_descriptor >,
0128                 typename graph_traits< G >::edge_iterator >
0129                 type;
0130         };
0131     };
0132     template <> struct choose_rev_edge_iter< false >
0133     {
0134         template < class G > struct bind_
0135         {
0136             typedef void type;
0137         };
0138     };
0139
0140 } // namespace detail
0141
0142 template < class BidirectionalGraph,
0143     class GraphRef = const BidirectionalGraph& >
0144 class reverse_graph
0145 {
0146     typedef reverse_graph< BidirectionalGraph, GraphRef > Self;
0147     typedef graph_traits< BidirectionalGraph > Traits;
0148
0149 public:
0150     typedef BidirectionalGraph base_type;
0151     typedef GraphRef base_ref_type;
0152
0153     // Constructor
0154     reverse_graph(GraphRef g) : m_g(g) {}
0155     // Conversion from reverse_graph on non-const reference to one on const
0156     // reference
0157     reverse_graph(
0158         const reverse_graph< BidirectionalGraph, BidirectionalGraph& >& o)
0159     : m_g(o.m_g)
0160     {
0161     }
0162
0163     // Graph requirements
0164     typedef typename Traits::vertex_descriptor vertex_descriptor;
0165     typedef detail::reverse_graph_edge_descriptor<
0166         typename Traits::edge_descriptor >
0167         edge_descriptor;
0168     typedef typename Traits::directed_category directed_category;
0169     typedef typename Traits::edge_parallel_category edge_parallel_category;
0170     typedef typename Traits::traversal_category traversal_category;
0171
0172     // IncidenceGraph requirements
0173     typedef transform_iterator< detail::reverse_graph_edge_descriptor_maker<
0174                                     typename Traits::edge_descriptor >,
0175         typename Traits::in_edge_iterator >
0176         out_edge_iterator;
0177     typedef typename Traits::degree_size_type degree_size_type;
0178
0179     // BidirectionalGraph requirements
0180     typedef transform_iterator< detail::reverse_graph_edge_descriptor_maker<
0181                                     typename Traits::edge_descriptor >,
0182         typename Traits::out_edge_iterator >
0183         in_edge_iterator;
0184
0185     // AdjacencyGraph requirements
0186     typedef typename adjacency_iterator_generator< Self, vertex_descriptor,
0187         out_edge_iterator >::type adjacency_iterator;
0188
0189     // VertexListGraph requirements
0190     typedef typename Traits::vertex_iterator vertex_iterator;
0191
0192     // EdgeListGraph requirements
0193     enum
0194     {
0195         is_edge_list
0196         = is_convertible< traversal_category, edge_list_graph_tag >::value
0197     };
0198     typedef detail::choose_rev_edge_iter< is_edge_list > ChooseEdgeIter;
0199     typedef typename ChooseEdgeIter::template bind_< BidirectionalGraph >::type
0200         edge_iterator;
0201     typedef typename Traits::vertices_size_type vertices_size_type;
0202     typedef typename Traits::edges_size_type edges_size_type;
0203
0204     typedef reverse_graph_tag graph_tag;
0205
0206 #ifndef BOOST_GRAPH_NO_BUNDLED_PROPERTIES
0207     // Bundled properties support
0208     template < typename Descriptor >
0209     typename graph::detail::bundled_result< BidirectionalGraph,
0210         typename detail::get_underlying_descriptor_from_reverse_descriptor<
0211             Descriptor >::type >::type&
0212     operator[](Descriptor x)
0213     {
0214         return m_g[detail::get_underlying_descriptor_from_reverse_descriptor<
0215             Descriptor >::convert(x)];
0216     }
0217
0218     template < typename Descriptor >
0219     typename graph::detail::bundled_result< BidirectionalGraph,
0220         typename detail::get_underlying_descriptor_from_reverse_descriptor<
0221             Descriptor >::type >::type const&
0222     operator[](Descriptor x) const
0223     {
0224         return m_g[detail::get_underlying_descriptor_from_reverse_descriptor<
0225             Descriptor >::convert(x)];
0226     }
0227 #endif // BOOST_GRAPH_NO_BUNDLED_PROPERTIES
0228
0229     static vertex_descriptor null_vertex() { return Traits::null_vertex(); }
0230
0231     // would be private, but template friends aren't portable enough.
0232     // private:
0233     GraphRef m_g;
0234 };
0235
0236 // These are separate so they are not instantiated unless used (see bug 1021)
0237 template < class BidirectionalGraph, class GraphRef >
0238 struct vertex_property_type< reverse_graph< BidirectionalGraph, GraphRef > >
0239 {
0240     typedef
0241         typename boost::vertex_property_type< BidirectionalGraph >::type type;
0242 };
0243
0244 template < class BidirectionalGraph, class GraphRef >
0245 struct edge_property_type< reverse_graph< BidirectionalGraph, GraphRef > >
0246 {
0247     typedef typename boost::edge_property_type< BidirectionalGraph >::type type;
0248 };
0249
0250 template < class BidirectionalGraph, class GraphRef >
0251 struct graph_property_type< reverse_graph< BidirectionalGraph, GraphRef > >
0252 {
0253     typedef
0254         typename boost::graph_property_type< BidirectionalGraph >::type type;
0255 };
0256
0257 #ifndef BOOST_GRAPH_NO_BUNDLED_PROPERTIES
0258 template < typename Graph, typename GraphRef >
0259 struct vertex_bundle_type< reverse_graph< Graph, GraphRef > >
0260 : vertex_bundle_type< Graph >
0261 {
0262 };
0263
0264 template < typename Graph, typename GraphRef >
0265 struct edge_bundle_type< reverse_graph< Graph, GraphRef > >
0266 : edge_bundle_type< Graph >
0267 {
0268 };
0269
0270 template < typename Graph, typename GraphRef >
0271 struct graph_bundle_type< reverse_graph< Graph, GraphRef > >
0272 : graph_bundle_type< Graph >
0273 {
0274 };
0275 #endif // BOOST_GRAPH_NO_BUNDLED_PROPERTIES
0276
0277 template < class BidirectionalGraph >
0278 inline reverse_graph< BidirectionalGraph > make_reverse_graph(
0279     const BidirectionalGraph& g)
0280 {
0281     return reverse_graph< BidirectionalGraph >(g);
0282 }
0283
0284 template < class BidirectionalGraph >
0285 inline reverse_graph< BidirectionalGraph, BidirectionalGraph& >
0286 make_reverse_graph(BidirectionalGraph& g)
0287 {
0288     return reverse_graph< BidirectionalGraph, BidirectionalGraph& >(g);
0289 }
0290
0291 template < class BidirectionalGraph, class GRef >
0292 std::pair< typename reverse_graph< BidirectionalGraph >::vertex_iterator,
0293     typename reverse_graph< BidirectionalGraph >::vertex_iterator >
0294 vertices(const reverse_graph< BidirectionalGraph, GRef >& g)
0295 {
0296     return vertices(g.m_g);
0297 }
0298
0299 template < class BidirectionalGraph, class GRef >
0300 std::pair< typename reverse_graph< BidirectionalGraph >::edge_iterator,
0301     typename reverse_graph< BidirectionalGraph >::edge_iterator >
0302 edges(const reverse_graph< BidirectionalGraph, GRef >& g)
0303 {
0304     return detail::reverse_edge_iter_pair<
0305         typename graph_traits< BidirectionalGraph >::edge_descriptor >(
0306         edges(g.m_g));
0307 }
0308
0309 template < class BidirectionalGraph, class GRef >
0310 inline std::pair<
0311     typename reverse_graph< BidirectionalGraph >::out_edge_iterator,
0312     typename reverse_graph< BidirectionalGraph >::out_edge_iterator >
0313 out_edges(
0314     const typename graph_traits< BidirectionalGraph >::vertex_descriptor u,
0315     const reverse_graph< BidirectionalGraph, GRef >& g)
0316 {
0317     return detail::reverse_edge_iter_pair<
0318         typename graph_traits< BidirectionalGraph >::edge_descriptor >(
0319         in_edges(u, g.m_g));
0320 }
0321
0322 template < class BidirectionalGraph, class GRef >
0323 inline typename graph_traits< BidirectionalGraph >::vertices_size_type
0324 num_vertices(const reverse_graph< BidirectionalGraph, GRef >& g)
0325 {
0326     return num_vertices(g.m_g);
0327 }
0328
0329 template < class BidirectionalGraph, class GRef >
0330 inline typename reverse_graph< BidirectionalGraph >::edges_size_type num_edges(
0331     const reverse_graph< BidirectionalGraph, GRef >& g)
0332 {
0333     return num_edges(g.m_g);
0334 }
0335
0336 template < class BidirectionalGraph, class GRef >
0337 inline typename graph_traits< BidirectionalGraph >::degree_size_type out_degree(
0338     const typename graph_traits< BidirectionalGraph >::vertex_descriptor u,
0339     const reverse_graph< BidirectionalGraph, GRef >& g)
0340 {
0341     return in_degree(u, g.m_g);
0342 }
0343
0344 template < class BidirectionalGraph, class GRef >
0345 inline typename graph_traits< BidirectionalGraph >::vertex_descriptor vertex(
0346     const typename graph_traits< BidirectionalGraph >::vertices_size_type v,
0347     const reverse_graph< BidirectionalGraph, GRef >& g)
0348 {
0349     return vertex(v, g.m_g);
0350 }
0351
0352 template < class BidirectionalGraph, class GRef >
0353 inline std::pair< typename graph_traits< reverse_graph< BidirectionalGraph,
0354                       GRef > >::edge_descriptor,
0355     bool >
0356 edge(const typename graph_traits< BidirectionalGraph >::vertex_descriptor u,
0357     const typename graph_traits< BidirectionalGraph >::vertex_descriptor v,
0358     const reverse_graph< BidirectionalGraph, GRef >& g)
0359 {
0360     typedef typename graph_traits< BidirectionalGraph >::edge_descriptor
0361         underlying_edge_descriptor;
0362     std::pair< underlying_edge_descriptor, bool > e = edge(v, u, g.m_g);
0363     return std::make_pair(
0364         detail::reverse_graph_edge_descriptor< underlying_edge_descriptor >(
0365             e.first),
0366         e.second);
0367 }
0368
0369 template < class BidirectionalGraph, class GRef >
0370 inline std::pair<
0371     typename reverse_graph< BidirectionalGraph >::in_edge_iterator,
0372     typename reverse_graph< BidirectionalGraph >::in_edge_iterator >
0373 in_edges(const typename graph_traits< BidirectionalGraph >::vertex_descriptor u,
0374     const reverse_graph< BidirectionalGraph, GRef >& g)
0375 {
0376     return detail::reverse_edge_iter_pair<
0377         typename graph_traits< BidirectionalGraph >::edge_descriptor >(
0378         out_edges(u, g.m_g));
0379 }
0380
0381 template < class BidirectionalGraph, class GRef >
0382 inline std::pair<
0383     typename reverse_graph< BidirectionalGraph, GRef >::adjacency_iterator,
0384     typename reverse_graph< BidirectionalGraph, GRef >::adjacency_iterator >
0385 adjacent_vertices(
0386     typename graph_traits< BidirectionalGraph >::vertex_descriptor u,
0387     const reverse_graph< BidirectionalGraph, GRef >& g)
0388 {
0389     typedef reverse_graph< BidirectionalGraph, GRef > Graph;
0390     typename graph_traits< Graph >::out_edge_iterator first, last;
0391     boost::tie(first, last) = out_edges(u, g);
0392     typedef
0393         typename graph_traits< Graph >::adjacency_iterator adjacency_iterator;
0394     return std::make_pair(adjacency_iterator(first, const_cast< Graph* >(&g)),
0395         adjacency_iterator(last, const_cast< Graph* >(&g)));
0396 }
0397
0398 template < class BidirectionalGraph, class GRef >
0399 inline typename graph_traits< BidirectionalGraph >::degree_size_type in_degree(
0400     const typename graph_traits< BidirectionalGraph >::vertex_descriptor u,
0401     const reverse_graph< BidirectionalGraph, GRef >& g)
0402 {
0403     return out_degree(u, g.m_g);
0404 }
0405
0406 template < class Edge, class BidirectionalGraph, class GRef >
0407 inline typename graph_traits< BidirectionalGraph >::vertex_descriptor source(
0408     const detail::reverse_graph_edge_descriptor< Edge >& e,
0409     const reverse_graph< BidirectionalGraph, GRef >& g)
0410 {
0411     return target(e.underlying_descx, g.m_g);
0412 }
0413
0414 template < class Edge, class BidirectionalGraph, class GRef >
0415 inline typename graph_traits< BidirectionalGraph >::vertex_descriptor target(
0416     const detail::reverse_graph_edge_descriptor< Edge >& e,
0417     const reverse_graph< BidirectionalGraph, GRef >& g)
0418 {
0419     return source(e.underlying_descx, g.m_g);
0420 }
0421
0422 template < class BidirectionalGraph, class GRef >
0423 inline typename graph_traits< BidirectionalGraph >::degree_size_type degree(
0424     const typename graph_traits< BidirectionalGraph >::vertex_descriptor u,
0425     const reverse_graph< BidirectionalGraph, GRef >& g)
0426 {
0427     return degree(u, g.m_g);
0428 }
0429
0430 namespace detail
0431 {
0432
0433     template < typename PM > struct reverse_graph_edge_property_map
0434     {
0435     private:
0436         PM underlying_pm;
0437
0438     public:
0439         typedef reverse_graph_edge_descriptor<
0440             typename property_traits< PM >::key_type >
0441             key_type;
0442         typedef typename property_traits< PM >::value_type value_type;
0443         typedef typename property_traits< PM >::reference reference;
0444         typedef typename property_traits< PM >::category category;
0445
0446         explicit reverse_graph_edge_property_map(const PM& pm)
0447         : underlying_pm(pm)
0448         {
0449         }
0450
0451         friend reference get(
0452             const reverse_graph_edge_property_map& m, const key_type& e)
0453         {
0454             return get(m.underlying_pm, e.underlying_descx);
0455         }
0456
0457         friend void put(const reverse_graph_edge_property_map& m,
0458             const key_type& e, const value_type& v)
0459         {
0460             put(m.underlying_pm, e.underlying_descx, v);
0461         }
0462
0463         reference operator[](const key_type& k) const
0464         {
0465             return (this->underlying_pm)[k.underlying_descx];
0466         }
0467     };
0468
0469 } // namespace detail
0470
0471 template < class BidirGraph, class GRef, class Property >
0472 struct property_map< reverse_graph< BidirGraph, GRef >, Property >
0473 {
0474     typedef boost::is_same<
0475         typename detail::property_kind_from_graph< BidirGraph, Property >::type,
0476         edge_property_tag >
0477         is_edge_prop;
0478     typedef boost::is_const< typename boost::remove_reference< GRef >::type >
0479         is_ref_const;
0480     typedef typename boost::mpl::if_< is_ref_const,
0481         typename property_map< BidirGraph, Property >::const_type,
0482         typename property_map< BidirGraph, Property >::type >::type orig_type;
0483     typedef typename property_map< BidirGraph, Property >::const_type
0484         orig_const_type;
0485     typedef typename boost::mpl::if_< is_edge_prop,
0486         detail::reverse_graph_edge_property_map< orig_type >, orig_type >::type
0487         type;
0488     typedef typename boost::mpl::if_< is_edge_prop,
0489         detail::reverse_graph_edge_property_map< orig_const_type >,
0490         orig_const_type >::type const_type;
0491 };
0492
0493 template < class BidirGraph, class GRef, class Property >
0494 struct property_map< const reverse_graph< BidirGraph, GRef >, Property >
0495 {
0496     typedef boost::is_same<
0497         typename detail::property_kind_from_graph< BidirGraph, Property >::type,
0498         edge_property_tag >
0499         is_edge_prop;
0500     typedef typename property_map< BidirGraph, Property >::const_type
0501         orig_const_type;
0502     typedef typename boost::mpl::if_< is_edge_prop,
0503         detail::reverse_graph_edge_property_map< orig_const_type >,
0504         orig_const_type >::type const_type;
0505     typedef const_type type;
0506 };
0507
0508 template < class BidirGraph, class GRef, class Property >
0509 typename disable_if< is_same< Property, edge_underlying_t >,
0510     typename property_map< reverse_graph< BidirGraph, GRef >,
0511         Property >::type >::type
0512 get(Property p, reverse_graph< BidirGraph, GRef >& g)
0513 {
0514     return typename property_map< reverse_graph< BidirGraph, GRef >,
0515         Property >::type(get(p, g.m_g));
0516 }
0517
0518 template < class BidirGraph, class GRef, class Property >
0519 typename disable_if< is_same< Property, edge_underlying_t >,
0520     typename property_map< reverse_graph< BidirGraph, GRef >,
0521         Property >::const_type >::type
0522 get(Property p, const reverse_graph< BidirGraph, GRef >& g)
0523 {
0524     const BidirGraph& gref = g.m_g; // in case GRef is non-const
0525     return typename property_map< reverse_graph< BidirGraph, GRef >,
0526         Property >::const_type(get(p, gref));
0527 }
0528
0529 template < class BidirectionalGraph, class GRef, class Property, class Key >
0530 typename disable_if< is_same< Property, edge_underlying_t >,
0531     typename property_traits<
0532         typename property_map< reverse_graph< BidirectionalGraph, GRef >,
0533             Property >::const_type >::value_type >::type
0534 get(Property p, const reverse_graph< BidirectionalGraph, GRef >& g,
0535     const Key& k)
0536 {
0537     return get(get(p, g), k);
0538 }
0539
0540 template < class BidirectionalGraph, class GRef, class Property, class Key,
0541     class Value >
0542 void put(Property p, reverse_graph< BidirectionalGraph, GRef >& g, const Key& k,
0543     const Value& val)
0544 {
0545     put(get(p, g), k, val);
0546 }
0547
0548 // Get the underlying descriptor from a reverse_graph's wrapped edge descriptor
0549
0550 namespace detail
0551 {
0552     template < class E > struct underlying_edge_desc_map_type
0553     {
0554         E operator[](const reverse_graph_edge_descriptor< E >& k) const
0555         {
0556             return k.underlying_descx;
0557         }
0558     };
0559
0560     template < class E >
0561     E get(underlying_edge_desc_map_type< E > m,
0562         const reverse_graph_edge_descriptor< E >& k)
0563     {
0564         return m[k];
0565     }
0566 }
0567
0568 template < class E >
0569 struct property_traits< detail::underlying_edge_desc_map_type< E > >
0570 {
0571     typedef detail::reverse_graph_edge_descriptor< E > key_type;
0572     typedef E value_type;
0573     typedef const E& reference;
0574     typedef readable_property_map_tag category;
0575 };
0576
0577 template < class Graph, class GRef >
0578 struct property_map< reverse_graph< Graph, GRef >, edge_underlying_t >
0579 {
0580 private:
0581     typedef typename graph_traits< Graph >::edge_descriptor ed;
0582
0583 public:
0584     typedef detail::underlying_edge_desc_map_type< ed > type;
0585     typedef detail::underlying_edge_desc_map_type< ed > const_type;
0586 };
0587
0588 template < typename T > struct is_reverse_graph : boost::mpl::false_
0589 {
0590 };
0591 template < typename G, typename R >
0592 struct is_reverse_graph< reverse_graph< G, R > > : boost::mpl::true_
0593 {
0594 };
0595
0596 template < class G >
0597 typename enable_if< is_reverse_graph< G >,
0598     detail::underlying_edge_desc_map_type< typename graph_traits<
0599         typename G::base_type >::edge_descriptor > >::type
0600 get(edge_underlying_t, G&)
0601 {
0602     return detail::underlying_edge_desc_map_type<
0603         typename graph_traits< typename G::base_type >::edge_descriptor >();
0604 }
0605
0606 template < class G >
0607 typename enable_if< is_reverse_graph< G >,
0608     typename graph_traits< typename G::base_type >::edge_descriptor >::type
0609 get(edge_underlying_t, G&, const typename graph_traits< G >::edge_descriptor& k)
0610 {
0611     return k.underlying_descx;
0612 }
0613
0614 template < class G >
0615 typename enable_if< is_reverse_graph< G >,
0616     detail::underlying_edge_desc_map_type< typename graph_traits<
0617         typename G::base_type >::edge_descriptor > >::type
0618 get(edge_underlying_t, const G&)
0619 {
0620     return detail::underlying_edge_desc_map_type<
0621         typename graph_traits< typename G::base_type >::edge_descriptor >();
0622 }
0623
0624 template < class G >
0625 typename enable_if< is_reverse_graph< G >,
0626     typename graph_traits< typename G::base_type >::edge_descriptor >::type
0627 get(edge_underlying_t, const G&,
0628     const typename graph_traits< G >::edge_descriptor& k)
0629 {
0630     return k.underlying_descx;
0631 }
0632
0633 // Access to wrapped graph's graph properties
0634
0635 template < typename BidirectionalGraph, typename GRef, typename Tag,
0636     typename Value >
0637 inline void set_property(const reverse_graph< BidirectionalGraph, GRef >& g,
0638     Tag tag, const Value& value)
0639 {
0640     set_property(g.m_g, tag, value);
0641 }
0642
0643 template < typename BidirectionalGraph, typename GRef, typename Tag >
0644 inline typename boost::mpl::if_<
0645     boost::is_const< typename boost::remove_reference< GRef >::type >,
0646     const typename graph_property< BidirectionalGraph, Tag >::type&,
0647     typename graph_property< BidirectionalGraph, Tag >::type& >::type
0648 get_property(const reverse_graph< BidirectionalGraph, GRef >& g, Tag tag)
0649 {
0650     return get_property(g.m_g, tag);
0651 }
0652
0653 } // namespace boost
0654
0655 #endif