source: NonGTP/Boost/boost/graph/reverse_graph.hpp @ 857

Revision 857, 10.5 KB checked in by igarcia, 19 years ago (diff)
Line 
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
13namespace boost {
14
15struct 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
33template <class BidirectionalGraph, class GraphRef = const BidirectionalGraph&>
34class 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
113template <class BidirectionalGraph>
114inline reverse_graph<BidirectionalGraph>
115make_reverse_graph(const BidirectionalGraph& g)
116{
117    return reverse_graph<BidirectionalGraph>(g);
118}
119
120template <class BidirectionalGraph>
121inline reverse_graph<BidirectionalGraph, BidirectionalGraph&>
122make_reverse_graph(BidirectionalGraph& g)
123{
124    return reverse_graph<BidirectionalGraph, BidirectionalGraph&>(g);
125}
126
127template <class BidirectionalGraph, class GRef>
128std::pair<typename reverse_graph<BidirectionalGraph>::vertex_iterator,
129          typename reverse_graph<BidirectionalGraph>::vertex_iterator>
130vertices(const reverse_graph<BidirectionalGraph,GRef>& g)
131{
132    return vertices(g.m_g);
133}
134
135template <class BidirectionalGraph, class GRef>
136std::pair<typename reverse_graph<BidirectionalGraph>::edge_iterator,
137          typename reverse_graph<BidirectionalGraph>::edge_iterator>
138edges(const reverse_graph<BidirectionalGraph,GRef>& g)
139{
140    return edges(g.m_g);
141}
142
143template <class BidirectionalGraph, class GRef>
144inline std::pair<typename BidirectionalGraph::in_edge_iterator,
145                 typename BidirectionalGraph::in_edge_iterator>
146out_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
152template <class BidirectionalGraph, class GRef>
153inline typename BidirectionalGraph::vertices_size_type
154num_vertices(const reverse_graph<BidirectionalGraph,GRef>& g)
155{
156    return num_vertices(g.m_g);
157}
158
159template <class BidirectionalGraph, class GRef>
160inline typename reverse_graph<BidirectionalGraph>::edges_size_type
161num_edges(const reverse_graph<BidirectionalGraph,GRef>& g)
162{
163    return num_edges(g.m_g);
164}
165
166template <class BidirectionalGraph, class GRef>
167inline typename BidirectionalGraph::degree_size_type
168out_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
174template <class BidirectionalGraph, class GRef>
175inline std::pair<typename BidirectionalGraph::edge_descriptor, bool>
176edge(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
183template <class BidirectionalGraph, class GRef>
184inline std::pair<typename BidirectionalGraph::out_edge_iterator,
185    typename BidirectionalGraph::out_edge_iterator>
186in_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
192template <class BidirectionalGraph, class GRef>
193inline std::pair<typename reverse_graph<BidirectionalGraph,GRef>::adjacency_iterator,
194    typename reverse_graph<BidirectionalGraph,GRef>::adjacency_iterator>
195adjacent_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
206template <class BidirectionalGraph, class GRef>
207inline typename BidirectionalGraph::degree_size_type
208in_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
214template <class Edge, class BidirectionalGraph, class GRef>
215inline typename graph_traits<BidirectionalGraph>::vertex_descriptor
216source(const Edge& e, const reverse_graph<BidirectionalGraph,GRef>& g)
217{
218    return target(e, g.m_g);
219}
220
221template <class Edge, class BidirectionalGraph, class GRef>
222inline typename graph_traits<BidirectionalGraph>::vertex_descriptor
223target(const Edge& e, const reverse_graph<BidirectionalGraph,GRef>& g)
224{
225    return source(e, g.m_g);
226}
227
228
229namespace 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
253template <>
254struct vertex_property_selector<reverse_graph_tag> {
255  typedef detail::reverse_graph_vertex_property_selector type;
256};
257
258template <>
259struct edge_property_selector<reverse_graph_tag> {
260  typedef detail::reverse_graph_edge_property_selector type;
261};
262
263template <class BidirGraph, class GRef, class Property>
264typename property_map<BidirGraph, Property>::type
265get(Property p, reverse_graph<BidirGraph,GRef>& g)
266{
267  return get(p, g.m_g);
268}
269
270template <class BidirGraph, class GRef, class Property>
271typename property_map<BidirGraph, Property>::const_type
272get(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
278template <class BidirectionalGraph, class GRef, class Property, class Key>
279typename property_traits<
280  typename property_map<BidirectionalGraph, Property>::const_type
281>::value_type
282get(Property p, const reverse_graph<BidirectionalGraph,GRef>& g, const Key& k)
283{
284  return get(p, g.m_g, k);
285}
286
287template <class BidirectionalGraph, class GRef, class Property, class Key, class Value>
288void
289put(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
295template<typename BidirectionalGraph, typename GRef, typename Tag,
296         typename Value>
297inline void
298set_property(const reverse_graph<BidirectionalGraph,GRef>& g, Tag tag,
299             const Value& value)
300{
301  set_property(g.m_g, tag, value);
302}
303
304template<typename BidirectionalGraph, typename GRef, typename Tag>
305inline
306typename graph_property<BidirectionalGraph, Tag>::type
307get_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
Note: See TracBrowser for help on using the repository browser.