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_TT20070518_H_
|
---|
7 | # define REVERSE_GRAPH_TT20070518_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 | namespace detail {
|
---|
16 |
|
---|
17 | template <bool isEdgeList> struct choose_rev_edge_iter { };
|
---|
18 | template <> struct choose_rev_edge_iter<true> {
|
---|
19 | template <class G> struct bind_ {
|
---|
20 | typedef typename graph_traits<G>::edge_iterator type;
|
---|
21 | };
|
---|
22 | };
|
---|
23 | template <> struct choose_rev_edge_iter<false> {
|
---|
24 | template <class G> struct bind_ {
|
---|
25 | typedef void type;
|
---|
26 | };
|
---|
27 | };
|
---|
28 |
|
---|
29 | } // namespace detail
|
---|
30 |
|
---|
31 | template <class BidirectionalGraph, class GraphRef = const BidirectionalGraph&>
|
---|
32 | class reverse_graph {
|
---|
33 | typedef reverse_graph<BidirectionalGraph, GraphRef> Self;
|
---|
34 | typedef graph_traits<BidirectionalGraph> Traits;
|
---|
35 | public:
|
---|
36 | typedef BidirectionalGraph base_type;
|
---|
37 |
|
---|
38 | // Constructor
|
---|
39 | reverse_graph(GraphRef g) : m_g(g) {}
|
---|
40 |
|
---|
41 | // Graph requirements
|
---|
42 | typedef typename Traits::vertex_descriptor vertex_descriptor;
|
---|
43 | typedef typename Traits::edge_descriptor edge_descriptor;
|
---|
44 | typedef typename Traits::directed_category directed_category;
|
---|
45 | typedef typename Traits::edge_parallel_category edge_parallel_category;
|
---|
46 | typedef typename Traits::traversal_category traversal_category;
|
---|
47 |
|
---|
48 | // IncidenceGraph requirements
|
---|
49 | typedef typename Traits::in_edge_iterator out_edge_iterator;
|
---|
50 | typedef typename Traits::degree_size_type degree_size_type;
|
---|
51 |
|
---|
52 | // BidirectionalGraph requirements
|
---|
53 | typedef typename Traits::out_edge_iterator in_edge_iterator;
|
---|
54 |
|
---|
55 | // AdjacencyGraph requirements
|
---|
56 | typedef typename adjacency_iterator_generator<Self,
|
---|
57 | vertex_descriptor, out_edge_iterator>::type adjacency_iterator;
|
---|
58 |
|
---|
59 | // VertexListGraph requirements
|
---|
60 | typedef typename Traits::vertex_iterator vertex_iterator;
|
---|
61 |
|
---|
62 | // EdgeListGraph requirements
|
---|
63 | enum { is_edge_list = is_convertible<traversal_category,
|
---|
64 | edge_list_graph_tag>::value };
|
---|
65 | typedef detail::choose_rev_edge_iter<is_edge_list> ChooseEdgeIter;
|
---|
66 | typedef typename ChooseEdgeIter::
|
---|
67 | template bind_<BidirectionalGraph>::type edge_iterator;
|
---|
68 | typedef typename Traits::vertices_size_type vertices_size_type;
|
---|
69 | typedef typename Traits::edges_size_type edges_size_type;
|
---|
70 |
|
---|
71 | #ifndef BOOST_GRAPH_NO_BUNDLED_PROPERTIES
|
---|
72 | // Bundled properties support
|
---|
73 | template<typename Descriptor>
|
---|
74 | typename graph::detail::bundled_result<BidirectionalGraph,
|
---|
75 | Descriptor>::type&
|
---|
76 | operator[](Descriptor x)
|
---|
77 | { return m_g[x]; }
|
---|
78 |
|
---|
79 | template<typename Descriptor>
|
---|
80 | typename graph::detail::bundled_result<BidirectionalGraph,
|
---|
81 | Descriptor>::type const&
|
---|
82 | operator[](Descriptor x) const
|
---|
83 | { return m_g[x]; }
|
---|
84 | #endif // BOOST_GRAPH_NO_BUNDLED_PROPERTIES
|
---|
85 |
|
---|
86 | static vertex_descriptor null_vertex()
|
---|
87 | { return Traits::null_vertex(); }
|
---|
88 |
|
---|
89 | // would be private, but template friends aren't portable enough.
|
---|
90 | // private:
|
---|
91 | GraphRef m_g;
|
---|
92 | };
|
---|
93 |
|
---|
94 | #ifndef BOOST_GRAPH_NO_BUNDLED_PROPERTIES
|
---|
95 | template<typename Graph, typename GraphRef>
|
---|
96 | struct vertex_bundle_type<reverse_graph<Graph, GraphRef> >
|
---|
97 | : vertex_bundle_type<Graph> { };
|
---|
98 |
|
---|
99 | template<typename Graph, typename GraphRef>
|
---|
100 | struct edge_bundle_type<reverse_graph<Graph, GraphRef> >
|
---|
101 | : edge_bundle_type<Graph> { };
|
---|
102 | #endif // BOOST_GRAPH_NO_BUNDLED_PROPERTIES
|
---|
103 |
|
---|
104 | template<typename Graph, typename GraphRef, typename Property>
|
---|
105 | struct property_map<reverse_graph<Graph, GraphRef>, Property>
|
---|
106 | {
|
---|
107 | typedef typename property_map<Graph, Property>::type type;
|
---|
108 | typedef typename property_map<Graph, Property>::const_type const_type;
|
---|
109 | };
|
---|
110 |
|
---|
111 | template <class BidirectionalGraph>
|
---|
112 | inline reverse_graph<BidirectionalGraph>
|
---|
113 | make_reverse_graph(const BidirectionalGraph& g)
|
---|
114 | {
|
---|
115 | return reverse_graph<BidirectionalGraph>(g);
|
---|
116 | }
|
---|
117 |
|
---|
118 | template <class BidirectionalGraph>
|
---|
119 | inline reverse_graph<BidirectionalGraph, BidirectionalGraph&>
|
---|
120 | make_reverse_graph(BidirectionalGraph& g)
|
---|
121 | {
|
---|
122 | return reverse_graph<BidirectionalGraph, BidirectionalGraph&>(g);
|
---|
123 | }
|
---|
124 |
|
---|
125 | template <class BidirectionalGraph, class GRef>
|
---|
126 | std::pair<typename reverse_graph<BidirectionalGraph, GRef>::vertex_iterator,
|
---|
127 | typename reverse_graph<BidirectionalGraph, GRef>::vertex_iterator>
|
---|
128 | vertices(const reverse_graph<BidirectionalGraph,GRef>& g)
|
---|
129 | {
|
---|
130 | return vertices(g.m_g);
|
---|
131 | }
|
---|
132 |
|
---|
133 | template <class BidirectionalGraph, class GRef>
|
---|
134 | std::pair<typename reverse_graph<BidirectionalGraph, GRef>::edge_iterator,
|
---|
135 | typename reverse_graph<BidirectionalGraph, GRef>::edge_iterator>
|
---|
136 | edges(const reverse_graph<BidirectionalGraph,GRef>& g)
|
---|
137 | {
|
---|
138 | return edges(g.m_g);
|
---|
139 | }
|
---|
140 |
|
---|
141 | template <class BidirectionalGraph, class GRef>
|
---|
142 | inline std::pair<typename reverse_graph<BidirectionalGraph, GRef>::out_edge_iterator,
|
---|
143 | typename reverse_graph<BidirectionalGraph, GRef>::out_edge_iterator>
|
---|
144 | out_edges(const typename reverse_graph<BidirectionalGraph, GRef>::vertex_descriptor u,
|
---|
145 | const reverse_graph<BidirectionalGraph,GRef>& g)
|
---|
146 | {
|
---|
147 | return in_edges(u, g.m_g);
|
---|
148 | }
|
---|
149 |
|
---|
150 | template <class BidirectionalGraph, class GRef>
|
---|
151 | inline typename reverse_graph<BidirectionalGraph, GRef>::vertices_size_type
|
---|
152 | num_vertices(const reverse_graph<BidirectionalGraph,GRef>& g)
|
---|
153 | {
|
---|
154 | return num_vertices(g.m_g);
|
---|
155 | }
|
---|
156 |
|
---|
157 | template <class BidirectionalGraph, class GRef>
|
---|
158 | inline typename reverse_graph<BidirectionalGraph, GRef>::edges_size_type
|
---|
159 | num_edges(const reverse_graph<BidirectionalGraph,GRef>& g)
|
---|
160 | {
|
---|
161 | return num_edges(g.m_g);
|
---|
162 | }
|
---|
163 |
|
---|
164 | template <class BidirectionalGraph, class GRef>
|
---|
165 | inline typename reverse_graph<BidirectionalGraph, GRef>::degree_size_type
|
---|
166 | out_degree(const typename reverse_graph<BidirectionalGraph, GRef>::vertex_descriptor u,
|
---|
167 | const reverse_graph<BidirectionalGraph,GRef>& g)
|
---|
168 | {
|
---|
169 | return in_degree(u, g.m_g);
|
---|
170 | }
|
---|
171 |
|
---|
172 | template <class BidirectionalGraph, class GRef>
|
---|
173 | inline std::pair<typename reverse_graph<BidirectionalGraph, GRef>::edge_descriptor, bool>
|
---|
174 | edge(const typename reverse_graph<BidirectionalGraph, GRef>::vertex_descriptor u,
|
---|
175 | const typename reverse_graph<BidirectionalGraph, GRef>::vertex_descriptor v,
|
---|
176 | const reverse_graph<BidirectionalGraph,GRef>& g)
|
---|
177 | {
|
---|
178 | return edge(v, u, g.m_g);
|
---|
179 | }
|
---|
180 |
|
---|
181 | template <class BidirectionalGraph, class GRef>
|
---|
182 | inline std::pair<typename reverse_graph<BidirectionalGraph, GRef>::in_edge_iterator,
|
---|
183 | typename reverse_graph<BidirectionalGraph, GRef>::in_edge_iterator>
|
---|
184 | in_edges(const typename reverse_graph<BidirectionalGraph, GRef>::vertex_descriptor u,
|
---|
185 | const reverse_graph<BidirectionalGraph,GRef>& g)
|
---|
186 | {
|
---|
187 | return out_edges(u, g.m_g);
|
---|
188 | }
|
---|
189 |
|
---|
190 | template <class BidirectionalGraph, class GRef>
|
---|
191 | inline std::pair<typename reverse_graph<BidirectionalGraph,GRef>::adjacency_iterator,
|
---|
192 | typename reverse_graph<BidirectionalGraph,GRef>::adjacency_iterator>
|
---|
193 | adjacent_vertices(const typename reverse_graph<BidirectionalGraph, GRef>::vertex_descriptor u,
|
---|
194 | const reverse_graph<BidirectionalGraph,GRef>& g)
|
---|
195 | {
|
---|
196 | typedef reverse_graph<BidirectionalGraph,GRef> Graph;
|
---|
197 | typename Graph::out_edge_iterator first, last;
|
---|
198 | tie(first, last) = out_edges(u, g);
|
---|
199 | typedef typename Graph::adjacency_iterator adjacency_iterator;
|
---|
200 | return std::make_pair(adjacency_iterator(first, const_cast<Graph*>(&g)),
|
---|
201 | adjacency_iterator(last, const_cast<Graph*>(&g)));
|
---|
202 | }
|
---|
203 |
|
---|
204 | template <class BidirectionalGraph, class GRef>
|
---|
205 | inline typename reverse_graph<BidirectionalGraph, GRef>::degree_size_type
|
---|
206 | in_degree(const typename reverse_graph<BidirectionalGraph, GRef>::vertex_descriptor u,
|
---|
207 | const reverse_graph<BidirectionalGraph,GRef>& g)
|
---|
208 | {
|
---|
209 | return out_degree(u, g.m_g);
|
---|
210 | }
|
---|
211 |
|
---|
212 | template <class Edge, class BidirectionalGraph, class GRef>
|
---|
213 | inline typename reverse_graph<BidirectionalGraph, GRef>::vertex_descriptor
|
---|
214 | source(const Edge& e, const reverse_graph<BidirectionalGraph,GRef>& g)
|
---|
215 | {
|
---|
216 | return target(e, g.m_g);
|
---|
217 | }
|
---|
218 |
|
---|
219 | template <class Edge, class BidirectionalGraph, class GRef>
|
---|
220 | inline typename reverse_graph<BidirectionalGraph, GRef>::vertex_descriptor
|
---|
221 | target(const Edge& e, const reverse_graph<BidirectionalGraph,GRef>& g)
|
---|
222 | {
|
---|
223 | return source(e, g.m_g);
|
---|
224 | }
|
---|
225 |
|
---|
226 | template <class BidirGraph, class GRef, class Property>
|
---|
227 | typename property_map<BidirGraph, Property>::type
|
---|
228 | get(Property p, reverse_graph<BidirGraph,GRef>& g)
|
---|
229 | {
|
---|
230 | return get(p, g.m_g);
|
---|
231 | }
|
---|
232 |
|
---|
233 | template <class BidirGraph, class GRef, class Property>
|
---|
234 | typename property_map<BidirGraph, Property>::const_type
|
---|
235 | get(Property p, const reverse_graph<BidirGraph,GRef>& g)
|
---|
236 | {
|
---|
237 | const BidirGraph& gref = g.m_g; // in case GRef is non-const
|
---|
238 | return get(p, gref);
|
---|
239 | }
|
---|
240 |
|
---|
241 | template <class BidirectionalGraph, class GRef, class Property, class Key>
|
---|
242 | typename property_traits<
|
---|
243 | typename property_map<BidirectionalGraph, Property>::const_type
|
---|
244 | >::value_type
|
---|
245 | get(Property p, const reverse_graph<BidirectionalGraph,GRef>& g, const Key& k)
|
---|
246 | {
|
---|
247 | return get(p, g.m_g, k);
|
---|
248 | }
|
---|
249 |
|
---|
250 | template <class BidirectionalGraph, class GRef, class Property, class Key, class Value>
|
---|
251 | void
|
---|
252 | put(Property p, const reverse_graph<BidirectionalGraph,GRef>& g, const Key& k,
|
---|
253 | const Value& val)
|
---|
254 | {
|
---|
255 | put(p, g.m_g, k, val);
|
---|
256 | }
|
---|
257 |
|
---|
258 | template<typename BidirectionalGraph, typename GRef, typename Tag,
|
---|
259 | typename Value>
|
---|
260 | inline void
|
---|
261 | set_property(const reverse_graph<BidirectionalGraph,GRef>& g, Tag tag,
|
---|
262 | const Value& value)
|
---|
263 | {
|
---|
264 | set_property(g.m_g, tag, value);
|
---|
265 | }
|
---|
266 |
|
---|
267 | template<typename BidirectionalGraph, typename GRef, typename Tag>
|
---|
268 | inline
|
---|
269 | typename graph_property<BidirectionalGraph, Tag>::type
|
---|
270 | get_property(const reverse_graph<BidirectionalGraph,GRef>& g, Tag tag)
|
---|
271 | {
|
---|
272 | return get_property(g.m_g, tag);
|
---|
273 | }
|
---|
274 |
|
---|
275 | } // namespace boost
|
---|
276 |
|
---|
277 | #endif
|
---|