Ugly, not-to-be-pushed sucking in of all of Boost to get windows to work.
[dyninst.git] / external / boost / graph / reverse_graph.hpp
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