1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/epoc32/include/stdapis/boost/graph/reverse_graph.hpp Tue Mar 16 16:12:26 2010 +0000
1.3 @@ -0,0 +1,314 @@
1.4 +// (C) Copyright David Abrahams 2000.
1.5 +// Distributed under the Boost Software License, Version 1.0. (See
1.6 +// accompanying file LICENSE_1_0.txt or copy at
1.7 +// http://www.boost.org/LICENSE_1_0.txt)
1.8 +
1.9 +#ifndef REVERSE_GRAPH_DWA092300_H_
1.10 +# define REVERSE_GRAPH_DWA092300_H_
1.11 +
1.12 +#include <boost/graph/adjacency_iterator.hpp>
1.13 +#include <boost/graph/properties.hpp>
1.14 +#include <boost/tuple/tuple.hpp>
1.15 +
1.16 +namespace boost {
1.17 +
1.18 +struct reverse_graph_tag { };
1.19 +
1.20 + namespace detail {
1.21 +
1.22 + template <bool isEdgeList> struct choose_rev_edge_iter { };
1.23 + template <> struct choose_rev_edge_iter<true> {
1.24 + template <class G> struct bind_ {
1.25 + typedef typename graph_traits<G>::edge_iterator type;
1.26 + };
1.27 + };
1.28 + template <> struct choose_rev_edge_iter<false> {
1.29 + template <class G> struct bind_ {
1.30 + typedef void type;
1.31 + };
1.32 + };
1.33 +
1.34 + } // namespace detail
1.35 +
1.36 +template <class BidirectionalGraph, class GraphRef = const BidirectionalGraph&>
1.37 +class reverse_graph {
1.38 + typedef reverse_graph<BidirectionalGraph, GraphRef> Self;
1.39 + typedef graph_traits<BidirectionalGraph> Traits;
1.40 + public:
1.41 + typedef BidirectionalGraph base_type;
1.42 +
1.43 + // Constructor
1.44 + reverse_graph(GraphRef g) : m_g(g) {}
1.45 +
1.46 + // Graph requirements
1.47 + typedef typename Traits::vertex_descriptor vertex_descriptor;
1.48 + typedef typename Traits::edge_descriptor edge_descriptor;
1.49 + typedef typename Traits::directed_category directed_category;
1.50 + typedef typename Traits::edge_parallel_category edge_parallel_category;
1.51 + typedef typename Traits::traversal_category traversal_category;
1.52 +
1.53 + // IncidenceGraph requirements
1.54 + typedef typename Traits::in_edge_iterator out_edge_iterator;
1.55 + typedef typename Traits::degree_size_type degree_size_type;
1.56 +
1.57 + // BidirectionalGraph requirements
1.58 + typedef typename Traits::out_edge_iterator in_edge_iterator;
1.59 +
1.60 + // AdjacencyGraph requirements
1.61 + typedef typename adjacency_iterator_generator<Self,
1.62 + vertex_descriptor, out_edge_iterator>::type adjacency_iterator;
1.63 +
1.64 + // VertexListGraph requirements
1.65 + typedef typename Traits::vertex_iterator vertex_iterator;
1.66 +
1.67 + // EdgeListGraph requirements
1.68 + enum { is_edge_list = is_convertible<traversal_category,
1.69 + edge_list_graph_tag>::value };
1.70 + typedef detail::choose_rev_edge_iter<is_edge_list> ChooseEdgeIter;
1.71 + typedef typename ChooseEdgeIter::
1.72 + template bind_<BidirectionalGraph>::type edge_iterator;
1.73 + typedef typename Traits::vertices_size_type vertices_size_type;
1.74 + typedef typename Traits::edges_size_type edges_size_type;
1.75 +
1.76 + // More typedefs used by detail::edge_property_map, vertex_property_map
1.77 + typedef typename BidirectionalGraph::edge_property_type
1.78 + edge_property_type;
1.79 + typedef typename BidirectionalGraph::vertex_property_type
1.80 + vertex_property_type;
1.81 + typedef reverse_graph_tag graph_tag;
1.82 +
1.83 +#ifndef BOOST_GRAPH_NO_BUNDLED_PROPERTIES
1.84 + // Bundled properties support
1.85 + template<typename Descriptor>
1.86 + typename graph::detail::bundled_result<BidirectionalGraph,
1.87 + Descriptor>::type&
1.88 + operator[](Descriptor x)
1.89 + { return m_g[x]; }
1.90 +
1.91 + template<typename Descriptor>
1.92 + typename graph::detail::bundled_result<BidirectionalGraph,
1.93 + Descriptor>::type const&
1.94 + operator[](Descriptor x) const
1.95 + { return m_g[x]; }
1.96 +#endif // BOOST_GRAPH_NO_BUNDLED_PROPERTIES
1.97 +
1.98 + static vertex_descriptor null_vertex()
1.99 + { return Traits::null_vertex(); }
1.100 +
1.101 + // would be private, but template friends aren't portable enough.
1.102 + // private:
1.103 + GraphRef m_g;
1.104 +};
1.105 +
1.106 +#ifndef BOOST_GRAPH_NO_BUNDLED_PROPERTIES
1.107 + template<typename Graph, typename GraphRef>
1.108 + struct vertex_bundle_type<reverse_graph<Graph, GraphRef> >
1.109 + : vertex_bundle_type<Graph> { };
1.110 +
1.111 + template<typename Graph, typename GraphRef>
1.112 + struct edge_bundle_type<reverse_graph<Graph, GraphRef> >
1.113 + : edge_bundle_type<Graph> { };
1.114 +#endif // BOOST_GRAPH_NO_BUNDLED_PROPERTIES
1.115 +
1.116 +template <class BidirectionalGraph>
1.117 +inline reverse_graph<BidirectionalGraph>
1.118 +make_reverse_graph(const BidirectionalGraph& g)
1.119 +{
1.120 + return reverse_graph<BidirectionalGraph>(g);
1.121 +}
1.122 +
1.123 +template <class BidirectionalGraph>
1.124 +inline reverse_graph<BidirectionalGraph, BidirectionalGraph&>
1.125 +make_reverse_graph(BidirectionalGraph& g)
1.126 +{
1.127 + return reverse_graph<BidirectionalGraph, BidirectionalGraph&>(g);
1.128 +}
1.129 +
1.130 +template <class BidirectionalGraph, class GRef>
1.131 +std::pair<typename reverse_graph<BidirectionalGraph>::vertex_iterator,
1.132 + typename reverse_graph<BidirectionalGraph>::vertex_iterator>
1.133 +vertices(const reverse_graph<BidirectionalGraph,GRef>& g)
1.134 +{
1.135 + return vertices(g.m_g);
1.136 +}
1.137 +
1.138 +template <class BidirectionalGraph, class GRef>
1.139 +std::pair<typename reverse_graph<BidirectionalGraph>::edge_iterator,
1.140 + typename reverse_graph<BidirectionalGraph>::edge_iterator>
1.141 +edges(const reverse_graph<BidirectionalGraph,GRef>& g)
1.142 +{
1.143 + return edges(g.m_g);
1.144 +}
1.145 +
1.146 +template <class BidirectionalGraph, class GRef>
1.147 +inline std::pair<typename BidirectionalGraph::in_edge_iterator,
1.148 + typename BidirectionalGraph::in_edge_iterator>
1.149 +out_edges(const typename BidirectionalGraph::vertex_descriptor u,
1.150 + const reverse_graph<BidirectionalGraph,GRef>& g)
1.151 +{
1.152 + return in_edges(u, g.m_g);
1.153 +}
1.154 +
1.155 +template <class BidirectionalGraph, class GRef>
1.156 +inline typename BidirectionalGraph::vertices_size_type
1.157 +num_vertices(const reverse_graph<BidirectionalGraph,GRef>& g)
1.158 +{
1.159 + return num_vertices(g.m_g);
1.160 +}
1.161 +
1.162 +template <class BidirectionalGraph, class GRef>
1.163 +inline typename reverse_graph<BidirectionalGraph>::edges_size_type
1.164 +num_edges(const reverse_graph<BidirectionalGraph,GRef>& g)
1.165 +{
1.166 + return num_edges(g.m_g);
1.167 +}
1.168 +
1.169 +template <class BidirectionalGraph, class GRef>
1.170 +inline typename BidirectionalGraph::degree_size_type
1.171 +out_degree(const typename BidirectionalGraph::vertex_descriptor u,
1.172 + const reverse_graph<BidirectionalGraph,GRef>& g)
1.173 +{
1.174 + return in_degree(u, g.m_g);
1.175 +}
1.176 +
1.177 +template <class BidirectionalGraph, class GRef>
1.178 +inline std::pair<typename BidirectionalGraph::edge_descriptor, bool>
1.179 +edge(const typename BidirectionalGraph::vertex_descriptor u,
1.180 + const typename BidirectionalGraph::vertex_descriptor v,
1.181 + const reverse_graph<BidirectionalGraph,GRef>& g)
1.182 +{
1.183 + return edge(v, u, g.m_g);
1.184 +}
1.185 +
1.186 +template <class BidirectionalGraph, class GRef>
1.187 +inline std::pair<typename BidirectionalGraph::out_edge_iterator,
1.188 + typename BidirectionalGraph::out_edge_iterator>
1.189 +in_edges(const typename BidirectionalGraph::vertex_descriptor u,
1.190 + const reverse_graph<BidirectionalGraph,GRef>& g)
1.191 +{
1.192 + return out_edges(u, g.m_g);
1.193 +}
1.194 +
1.195 +template <class BidirectionalGraph, class GRef>
1.196 +inline std::pair<typename reverse_graph<BidirectionalGraph,GRef>::adjacency_iterator,
1.197 + typename reverse_graph<BidirectionalGraph,GRef>::adjacency_iterator>
1.198 +adjacent_vertices(const typename BidirectionalGraph::vertex_descriptor u,
1.199 + const reverse_graph<BidirectionalGraph,GRef>& g)
1.200 +{
1.201 + typedef reverse_graph<BidirectionalGraph,GRef> Graph;
1.202 + typename Graph::out_edge_iterator first, last;
1.203 + tie(first, last) = out_edges(u, g);
1.204 + typedef typename Graph::adjacency_iterator adjacency_iterator;
1.205 + return std::make_pair(adjacency_iterator(first, const_cast<Graph*>(&g)),
1.206 + adjacency_iterator(last, const_cast<Graph*>(&g)));
1.207 +}
1.208 +
1.209 +template <class BidirectionalGraph, class GRef>
1.210 +inline typename BidirectionalGraph::degree_size_type
1.211 +in_degree(const typename BidirectionalGraph::vertex_descriptor u,
1.212 + const reverse_graph<BidirectionalGraph,GRef>& g)
1.213 +{
1.214 + return out_degree(u, g.m_g);
1.215 +}
1.216 +
1.217 +template <class Edge, class BidirectionalGraph, class GRef>
1.218 +inline typename graph_traits<BidirectionalGraph>::vertex_descriptor
1.219 +source(const Edge& e, const reverse_graph<BidirectionalGraph,GRef>& g)
1.220 +{
1.221 + return target(e, g.m_g);
1.222 +}
1.223 +
1.224 +template <class Edge, class BidirectionalGraph, class GRef>
1.225 +inline typename graph_traits<BidirectionalGraph>::vertex_descriptor
1.226 +target(const Edge& e, const reverse_graph<BidirectionalGraph,GRef>& g)
1.227 +{
1.228 + return source(e, g.m_g);
1.229 +}
1.230 +
1.231 +
1.232 +namespace detail {
1.233 +
1.234 + struct reverse_graph_vertex_property_selector {
1.235 + template <class ReverseGraph, class Property, class Tag>
1.236 + struct bind_ {
1.237 + typedef typename ReverseGraph::base_type Graph;
1.238 + typedef property_map<Graph, Tag> PMap;
1.239 + typedef typename PMap::type type;
1.240 + typedef typename PMap::const_type const_type;
1.241 + };
1.242 + };
1.243 +
1.244 + struct reverse_graph_edge_property_selector {
1.245 + template <class ReverseGraph, class Property, class Tag>
1.246 + struct bind_ {
1.247 + typedef typename ReverseGraph::base_type Graph;
1.248 + typedef property_map<Graph, Tag> PMap;
1.249 + typedef typename PMap::type type;
1.250 + typedef typename PMap::const_type const_type;
1.251 + };
1.252 + };
1.253 +
1.254 +} // namespace detail
1.255 +
1.256 +template <>
1.257 +struct vertex_property_selector<reverse_graph_tag> {
1.258 + typedef detail::reverse_graph_vertex_property_selector type;
1.259 +};
1.260 +
1.261 +template <>
1.262 +struct edge_property_selector<reverse_graph_tag> {
1.263 + typedef detail::reverse_graph_edge_property_selector type;
1.264 +};
1.265 +
1.266 +template <class BidirGraph, class GRef, class Property>
1.267 +typename property_map<BidirGraph, Property>::type
1.268 +get(Property p, reverse_graph<BidirGraph,GRef>& g)
1.269 +{
1.270 + return get(p, g.m_g);
1.271 +}
1.272 +
1.273 +template <class BidirGraph, class GRef, class Property>
1.274 +typename property_map<BidirGraph, Property>::const_type
1.275 +get(Property p, const reverse_graph<BidirGraph,GRef>& g)
1.276 +{
1.277 + const BidirGraph& gref = g.m_g; // in case GRef is non-const
1.278 + return get(p, gref);
1.279 +}
1.280 +
1.281 +template <class BidirectionalGraph, class GRef, class Property, class Key>
1.282 +typename property_traits<
1.283 + typename property_map<BidirectionalGraph, Property>::const_type
1.284 +>::value_type
1.285 +get(Property p, const reverse_graph<BidirectionalGraph,GRef>& g, const Key& k)
1.286 +{
1.287 + return get(p, g.m_g, k);
1.288 +}
1.289 +
1.290 +template <class BidirectionalGraph, class GRef, class Property, class Key, class Value>
1.291 +void
1.292 +put(Property p, const reverse_graph<BidirectionalGraph,GRef>& g, const Key& k,
1.293 + const Value& val)
1.294 +{
1.295 + put(p, g.m_g, k, val);
1.296 +}
1.297 +
1.298 +template<typename BidirectionalGraph, typename GRef, typename Tag,
1.299 + typename Value>
1.300 +inline void
1.301 +set_property(const reverse_graph<BidirectionalGraph,GRef>& g, Tag tag,
1.302 + const Value& value)
1.303 +{
1.304 + set_property(g.m_g, tag, value);
1.305 +}
1.306 +
1.307 +template<typename BidirectionalGraph, typename GRef, typename Tag>
1.308 +inline
1.309 +typename graph_property<BidirectionalGraph, Tag>::type
1.310 +get_property(const reverse_graph<BidirectionalGraph,GRef>& g, Tag tag)
1.311 +{
1.312 + return get_property(g.m_g, tag);
1.313 +}
1.314 +
1.315 +} // namespace boost
1.316 +
1.317 +#endif