epoc32/include/stdapis/boost/graph/reverse_graph.hpp
author William Roberts <williamr@symbian.org>
Wed, 31 Mar 2010 12:33:34 +0100
branchSymbian3
changeset 4 837f303aceeb
permissions -rw-r--r--
Current Symbian^3 public API header files (from PDK 3.0.h)
This is the epoc32/include tree with the "platform" subtrees removed, and
all but a selected few mbg and rsg files removed.
     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