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