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)
6 #ifndef REVERSE_GRAPH_DWA092300_H_
7 # define REVERSE_GRAPH_DWA092300_H_
9 #include <boost/graph/adjacency_iterator.hpp>
10 #include <boost/graph/properties.hpp>
11 #include <boost/tuple/tuple.hpp>
15 struct reverse_graph_tag { };
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;
25 template <> struct choose_rev_edge_iter<false> {
26 template <class G> struct bind_ {
33 template <class BidirectionalGraph, class GraphRef = const BidirectionalGraph&>
35 typedef reverse_graph<BidirectionalGraph, GraphRef> Self;
36 typedef graph_traits<BidirectionalGraph> Traits;
38 typedef BidirectionalGraph base_type;
41 reverse_graph(GraphRef g) : m_g(g) {}
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;
50 // IncidenceGraph requirements
51 typedef typename Traits::in_edge_iterator out_edge_iterator;
52 typedef typename Traits::degree_size_type degree_size_type;
54 // BidirectionalGraph requirements
55 typedef typename Traits::out_edge_iterator in_edge_iterator;
57 // AdjacencyGraph requirements
58 typedef typename adjacency_iterator_generator<Self,
59 vertex_descriptor, out_edge_iterator>::type adjacency_iterator;
61 // VertexListGraph requirements
62 typedef typename Traits::vertex_iterator vertex_iterator;
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;
73 // More typedefs used by detail::edge_property_map, vertex_property_map
74 typedef typename BidirectionalGraph::edge_property_type
76 typedef typename BidirectionalGraph::vertex_property_type
78 typedef reverse_graph_tag graph_tag;
80 #ifndef BOOST_GRAPH_NO_BUNDLED_PROPERTIES
81 // Bundled properties support
82 template<typename Descriptor>
83 typename graph::detail::bundled_result<BidirectionalGraph,
85 operator[](Descriptor x)
88 template<typename Descriptor>
89 typename graph::detail::bundled_result<BidirectionalGraph,
90 Descriptor>::type const&
91 operator[](Descriptor x) const
93 #endif // BOOST_GRAPH_NO_BUNDLED_PROPERTIES
95 static vertex_descriptor null_vertex()
96 { return Traits::null_vertex(); }
98 // would be private, but template friends aren't portable enough.
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> { };
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
113 template <class BidirectionalGraph>
114 inline reverse_graph<BidirectionalGraph>
115 make_reverse_graph(const BidirectionalGraph& g)
117 return reverse_graph<BidirectionalGraph>(g);
120 template <class BidirectionalGraph>
121 inline reverse_graph<BidirectionalGraph, BidirectionalGraph&>
122 make_reverse_graph(BidirectionalGraph& g)
124 return reverse_graph<BidirectionalGraph, BidirectionalGraph&>(g);
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)
132 return vertices(g.m_g);
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)
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)
149 return in_edges(u, g.m_g);
152 template <class BidirectionalGraph, class GRef>
153 inline typename BidirectionalGraph::vertices_size_type
154 num_vertices(const reverse_graph<BidirectionalGraph,GRef>& g)
156 return num_vertices(g.m_g);
159 template <class BidirectionalGraph, class GRef>
160 inline typename reverse_graph<BidirectionalGraph>::edges_size_type
161 num_edges(const reverse_graph<BidirectionalGraph,GRef>& g)
163 return num_edges(g.m_g);
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)
171 return in_degree(u, g.m_g);
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)
180 return edge(v, u, g.m_g);
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)
189 return out_edges(u, g.m_g);
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)
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)));
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)
211 return out_degree(u, g.m_g);
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)
218 return target(e, g.m_g);
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)
225 return source(e, g.m_g);
231 struct reverse_graph_vertex_property_selector {
232 template <class ReverseGraph, class Property, class Tag>
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;
241 struct reverse_graph_edge_property_selector {
242 template <class ReverseGraph, class Property, class Tag>
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;
251 } // namespace detail
254 struct vertex_property_selector<reverse_graph_tag> {
255 typedef detail::reverse_graph_vertex_property_selector type;
259 struct edge_property_selector<reverse_graph_tag> {
260 typedef detail::reverse_graph_edge_property_selector type;
263 template <class BidirGraph, class GRef, class Property>
264 typename property_map<BidirGraph, Property>::type
265 get(Property p, reverse_graph<BidirGraph,GRef>& g)
267 return get(p, g.m_g);
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)
274 const BidirGraph& gref = g.m_g; // in case GRef is non-const
278 template <class BidirectionalGraph, class GRef, class Property, class Key>
279 typename property_traits<
280 typename property_map<BidirectionalGraph, Property>::const_type
282 get(Property p, const reverse_graph<BidirectionalGraph,GRef>& g, const Key& k)
284 return get(p, g.m_g, k);
287 template <class BidirectionalGraph, class GRef, class Property, class Key, class Value>
289 put(Property p, const reverse_graph<BidirectionalGraph,GRef>& g, const Key& k,
292 put(p, g.m_g, k, val);
295 template<typename BidirectionalGraph, typename GRef, typename Tag,
298 set_property(const reverse_graph<BidirectionalGraph,GRef>& g, Tag tag,
301 set_property(g.m_g, tag, value);
304 template<typename BidirectionalGraph, typename GRef, typename Tag>
306 typename graph_property<BidirectionalGraph, Tag>::type
307 get_property(const reverse_graph<BidirectionalGraph,GRef>& g, Tag tag)
309 return get_property(g.m_g, tag);