1 | //======================================================================= |
2 | // Copyright 1997, 1998, 1999, 2000 University of Notre Dame. |
3 | // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek |
4 | // |
5 | // Distributed under the Boost Software License, Version 1.0. (See |
6 | // accompanying file LICENSE_1_0.txt or copy at |
7 | // http://www.boost.org/LICENSE_1_0.txt) |
8 | //======================================================================= |
9 | |
10 | #ifndef BOOST_GRAPH_TRAITS_HPP |
11 | #define BOOST_GRAPH_TRAITS_HPP |
12 | |
13 | #include <boost/config.hpp> |
14 | #include <iterator> |
15 | #include <utility> /* Primarily for std::pair */ |
16 | #include <boost/tuple/tuple.hpp> |
17 | #include <boost/mpl/if.hpp> |
18 | #include <boost/mpl/eval_if.hpp> |
19 | #include <boost/mpl/bool.hpp> |
20 | #include <boost/mpl/not.hpp> |
21 | #include <boost/mpl/has_xxx.hpp> |
22 | #include <boost/mpl/void.hpp> |
23 | #include <boost/mpl/identity.hpp> |
24 | #include <boost/type_traits/is_same.hpp> |
25 | #include <boost/iterator/iterator_categories.hpp> |
26 | #include <boost/iterator/iterator_adaptor.hpp> |
27 | #include <boost/pending/property.hpp> |
28 | #include <boost/detail/workaround.hpp> |
29 | |
30 | namespace boost { |
31 | |
32 | namespace detail { |
33 | #define BOOST_GRAPH_MEMBER_OR_VOID(name) \ |
34 | BOOST_MPL_HAS_XXX_TRAIT_DEF(name) \ |
35 | template <typename T> struct BOOST_JOIN(get_member_, name) {typedef typename T::name type;}; \ |
36 | template <typename T> struct BOOST_JOIN(get_opt_member_, name): \ |
37 | boost::mpl::eval_if_c< \ |
38 | BOOST_JOIN(has_, name)<T>::value, \ |
39 | BOOST_JOIN(get_member_, name)<T>, \ |
40 | boost::mpl::identity<void> > \ |
41 | {}; |
42 | BOOST_GRAPH_MEMBER_OR_VOID(adjacency_iterator) |
43 | BOOST_GRAPH_MEMBER_OR_VOID(out_edge_iterator) |
44 | BOOST_GRAPH_MEMBER_OR_VOID(in_edge_iterator) |
45 | BOOST_GRAPH_MEMBER_OR_VOID(vertex_iterator) |
46 | BOOST_GRAPH_MEMBER_OR_VOID(edge_iterator) |
47 | BOOST_GRAPH_MEMBER_OR_VOID(vertices_size_type) |
48 | BOOST_GRAPH_MEMBER_OR_VOID(edges_size_type) |
49 | BOOST_GRAPH_MEMBER_OR_VOID(degree_size_type) |
50 | } |
51 | |
52 | template <typename G> |
53 | struct graph_traits { |
54 | #define BOOST_GRAPH_PULL_OPT_MEMBER(name) \ |
55 | typedef typename detail::BOOST_JOIN(get_opt_member_, name)<G>::type name; |
56 | |
57 | typedef typename G::vertex_descriptor vertex_descriptor; |
58 | typedef typename G::edge_descriptor edge_descriptor; |
59 | BOOST_GRAPH_PULL_OPT_MEMBER(adjacency_iterator) |
60 | BOOST_GRAPH_PULL_OPT_MEMBER(out_edge_iterator) |
61 | BOOST_GRAPH_PULL_OPT_MEMBER(in_edge_iterator) |
62 | BOOST_GRAPH_PULL_OPT_MEMBER(vertex_iterator) |
63 | BOOST_GRAPH_PULL_OPT_MEMBER(edge_iterator) |
64 | |
65 | typedef typename G::directed_category directed_category; |
66 | typedef typename G::edge_parallel_category edge_parallel_category; |
67 | typedef typename G::traversal_category traversal_category; |
68 | |
69 | BOOST_GRAPH_PULL_OPT_MEMBER(vertices_size_type) |
70 | BOOST_GRAPH_PULL_OPT_MEMBER(edges_size_type) |
71 | BOOST_GRAPH_PULL_OPT_MEMBER(degree_size_type) |
72 | #undef BOOST_GRAPH_PULL_OPT_MEMBER |
73 | |
74 | static inline vertex_descriptor null_vertex(); |
75 | }; |
76 | |
77 | template <typename G> |
78 | inline typename graph_traits<G>::vertex_descriptor |
79 | graph_traits<G>::null_vertex() |
80 | { return G::null_vertex(); } |
81 | |
82 | // directed_category tags |
83 | struct directed_tag { }; |
84 | struct undirected_tag { }; |
85 | struct bidirectional_tag : public directed_tag { }; |
86 | |
87 | namespace detail { |
88 | inline bool is_directed(directed_tag) { return true; } |
89 | inline bool is_directed(undirected_tag) { return false; } |
90 | } |
91 | |
92 | /** Return true if the given graph is directed. */ |
93 | template <typename Graph> |
94 | bool is_directed(const Graph&) { |
95 | typedef typename graph_traits<Graph>::directed_category Cat; |
96 | return detail::is_directed(Cat()); |
97 | } |
98 | |
99 | /** Return true if the given graph is undirected. */ |
100 | template <typename Graph> |
101 | bool is_undirected(const Graph& g) { |
102 | return !is_directed(g); |
103 | } |
104 | |
105 | /** @name Directed/Undirected Graph Traits */ |
106 | //@{ |
107 | namespace graph_detail { |
108 | template <typename Tag> |
109 | struct is_directed_tag |
110 | : mpl::bool_<is_convertible<Tag, directed_tag>::value> |
111 | { }; |
112 | } // namespace graph_detail |
113 | |
114 | template <typename Graph> |
115 | struct is_directed_graph |
116 | : graph_detail::is_directed_tag< |
117 | typename graph_traits<Graph>::directed_category |
118 | > |
119 | { }; |
120 | |
121 | template <typename Graph> |
122 | struct is_undirected_graph |
123 | : mpl::not_< is_directed_graph<Graph> > |
124 | { }; |
125 | //@} |
126 | |
127 | // edge_parallel_category tags |
128 | struct allow_parallel_edge_tag { }; |
129 | struct disallow_parallel_edge_tag { }; |
130 | |
131 | namespace detail { |
132 | inline bool allows_parallel(allow_parallel_edge_tag) { return true; } |
133 | inline bool allows_parallel(disallow_parallel_edge_tag) { return false; } |
134 | } |
135 | |
136 | template <typename Graph> |
137 | bool allows_parallel_edges(const Graph&) { |
138 | typedef typename graph_traits<Graph>::edge_parallel_category Cat; |
139 | return detail::allows_parallel(Cat()); |
140 | } |
141 | |
142 | /** @name Parallel Edges Traits */ |
143 | //@{ |
144 | /** |
145 | * The is_multigraph metafunction returns true if the graph allows |
146 | * parallel edges. Technically, a multigraph is a simple graph that |
147 | * allows parallel edges, but since there are no traits for the allowance |
148 | * or disallowance of loops, this is a moot point. |
149 | */ |
150 | template <typename Graph> |
151 | struct is_multigraph |
152 | : mpl::bool_< |
153 | is_same< |
154 | typename graph_traits<Graph>::edge_parallel_category, |
155 | allow_parallel_edge_tag |
156 | >::value |
157 | > |
158 | { }; |
159 | //@} |
160 | |
161 | // traversal_category tags |
162 | struct incidence_graph_tag { }; |
163 | struct adjacency_graph_tag { }; |
164 | struct bidirectional_graph_tag : virtual incidence_graph_tag { }; |
165 | struct vertex_list_graph_tag { }; |
166 | struct edge_list_graph_tag { }; |
167 | struct adjacency_matrix_tag { }; |
168 | |
169 | // Parallel traversal_category tags |
170 | struct distributed_graph_tag { }; |
171 | struct distributed_vertex_list_graph_tag { }; |
172 | struct distributed_edge_list_graph_tag { }; |
173 | #define BOOST_GRAPH_SEQUENTIAL_TRAITS_DEFINES_DISTRIBUTED_TAGS // Disable these from external versions of PBGL |
174 | |
175 | /** @name Traversal Category Traits |
176 | * These traits classify graph types by their supported methods of |
177 | * vertex and edge traversal. |
178 | */ |
179 | //@{ |
180 | template <typename Graph> |
181 | struct is_incidence_graph |
182 | : mpl::bool_< |
183 | is_convertible< |
184 | typename graph_traits<Graph>::traversal_category, |
185 | incidence_graph_tag |
186 | >::value |
187 | > |
188 | { }; |
189 | |
190 | template <typename Graph> |
191 | struct is_bidirectional_graph |
192 | : mpl::bool_< |
193 | is_convertible< |
194 | typename graph_traits<Graph>::traversal_category, |
195 | bidirectional_graph_tag |
196 | >::value |
197 | > |
198 | { }; |
199 | |
200 | template <typename Graph> |
201 | struct is_vertex_list_graph |
202 | : mpl::bool_< |
203 | is_convertible< |
204 | typename graph_traits<Graph>::traversal_category, |
205 | vertex_list_graph_tag |
206 | >::value |
207 | > |
208 | { }; |
209 | |
210 | template <typename Graph> |
211 | struct is_edge_list_graph |
212 | : mpl::bool_< |
213 | is_convertible< |
214 | typename graph_traits<Graph>::traversal_category, |
215 | edge_list_graph_tag |
216 | >::value |
217 | > |
218 | { }; |
219 | |
220 | template <typename Graph> |
221 | struct is_adjacency_matrix |
222 | : mpl::bool_< |
223 | is_convertible< |
224 | typename graph_traits<Graph>::traversal_category, |
225 | adjacency_matrix_tag |
226 | >::value |
227 | > |
228 | { }; |
229 | //@} |
230 | |
231 | /** @name Directed Graph Traits |
232 | * These metafunctions are used to fully classify directed vs. undirected |
233 | * graphs. Recall that an undirected graph is also bidirectional, but it |
234 | * cannot be both undirected and directed at the same time. |
235 | */ |
236 | //@{ |
237 | template <typename Graph> |
238 | struct is_directed_unidirectional_graph |
239 | : mpl::and_< |
240 | is_directed_graph<Graph>, mpl::not_< is_bidirectional_graph<Graph> > |
241 | > |
242 | { }; |
243 | |
244 | template <typename Graph> |
245 | struct is_directed_bidirectional_graph |
246 | : mpl::and_< |
247 | is_directed_graph<Graph>, is_bidirectional_graph<Graph> |
248 | > |
249 | { }; |
250 | //@} |
251 | |
252 | //?? not the right place ?? Lee |
253 | typedef boost::forward_traversal_tag multi_pass_input_iterator_tag; |
254 | |
255 | namespace detail { |
256 | BOOST_MPL_HAS_XXX_TRAIT_DEF(graph_property_type) |
257 | BOOST_MPL_HAS_XXX_TRAIT_DEF(edge_property_type) |
258 | BOOST_MPL_HAS_XXX_TRAIT_DEF(vertex_property_type) |
259 | |
260 | template <typename G> struct get_graph_property_type {typedef typename G::graph_property_type type;}; |
261 | template <typename G> struct get_edge_property_type {typedef typename G::edge_property_type type;}; |
262 | template <typename G> struct get_vertex_property_type {typedef typename G::vertex_property_type type;}; |
263 | } |
264 | |
265 | template <typename G> |
266 | struct graph_property_type |
267 | : boost::mpl::eval_if<detail::has_graph_property_type<G>, |
268 | detail::get_graph_property_type<G>, |
269 | no_property> {}; |
270 | template <typename G> |
271 | struct edge_property_type |
272 | : boost::mpl::eval_if<detail::has_edge_property_type<G>, |
273 | detail::get_edge_property_type<G>, |
274 | no_property> {}; |
275 | template <typename G> |
276 | struct vertex_property_type |
277 | : boost::mpl::eval_if<detail::has_vertex_property_type<G>, |
278 | detail::get_vertex_property_type<G>, |
279 | no_property> {}; |
280 | |
281 | template<typename G> |
282 | struct graph_bundle_type { |
283 | typedef typename G::graph_bundled type; |
284 | }; |
285 | |
286 | template<typename G> |
287 | struct vertex_bundle_type { |
288 | typedef typename G::vertex_bundled type; |
289 | }; |
290 | |
291 | template<typename G> |
292 | struct edge_bundle_type { |
293 | typedef typename G::edge_bundled type; |
294 | }; |
295 | |
296 | namespace graph { namespace detail { |
297 | template<typename Graph, typename Descriptor> |
298 | class bundled_result { |
299 | typedef typename graph_traits<Graph>::vertex_descriptor Vertex; |
300 | typedef typename mpl::if_c<(is_same<Descriptor, Vertex>::value), |
301 | vertex_bundle_type<Graph>, |
302 | edge_bundle_type<Graph> >::type bundler; |
303 | public: |
304 | typedef typename bundler::type type; |
305 | }; |
306 | |
307 | template<typename Graph> |
308 | class bundled_result<Graph, graph_bundle_t> { |
309 | typedef typename graph_traits<Graph>::vertex_descriptor Vertex; |
310 | typedef graph_bundle_type<Graph> bundler; |
311 | public: |
312 | typedef typename bundler::type type; |
313 | }; |
314 | |
315 | } } // namespace graph::detail |
316 | |
317 | namespace graph_detail { |
318 | // A helper metafunction for determining whether or not a type is |
319 | // bundled. |
320 | template <typename T> |
321 | struct is_no_bundle : mpl::bool_<is_same<T, no_property>::value> |
322 | { }; |
323 | } // namespace graph_detail |
324 | |
325 | /** @name Graph Property Traits |
326 | * These metafunctions (along with those above), can be used to access the |
327 | * vertex and edge properties (bundled or otherwise) of vertices and |
328 | * edges. |
329 | */ |
330 | //@{ |
331 | template<typename Graph> |
332 | struct has_graph_property |
333 | : mpl::not_< |
334 | typename detail::is_no_property< |
335 | typename graph_property_type<Graph>::type |
336 | >::type |
337 | >::type |
338 | { }; |
339 | |
340 | template<typename Graph> |
341 | struct has_bundled_graph_property |
342 | : mpl::not_< |
343 | graph_detail::is_no_bundle<typename graph_bundle_type<Graph>::type> |
344 | > |
345 | { }; |
346 | |
347 | template <typename Graph> |
348 | struct has_vertex_property |
349 | : mpl::not_< |
350 | typename detail::is_no_property<typename vertex_property_type<Graph>::type> |
351 | >::type |
352 | { }; |
353 | |
354 | template <typename Graph> |
355 | struct has_bundled_vertex_property |
356 | : mpl::not_< |
357 | graph_detail::is_no_bundle<typename vertex_bundle_type<Graph>::type> |
358 | > |
359 | { }; |
360 | |
361 | template <typename Graph> |
362 | struct has_edge_property |
363 | : mpl::not_< |
364 | typename detail::is_no_property<typename edge_property_type<Graph>::type> |
365 | >::type |
366 | { }; |
367 | |
368 | template <typename Graph> |
369 | struct has_bundled_edge_property |
370 | : mpl::not_< |
371 | graph_detail::is_no_bundle<typename edge_bundle_type<Graph>::type> |
372 | > |
373 | { }; |
374 | //@} |
375 | |
376 | } // namespace boost |
377 | |
378 | // Since pair is in namespace std, Koenig lookup will find source and |
379 | // target if they are also defined in namespace std. This is illegal, |
380 | // but the alternative is to put source and target in the global |
381 | // namespace which causes name conflicts with other libraries (like |
382 | // SUIF). |
383 | namespace std { |
384 | |
385 | /* Some helper functions for dealing with pairs as edges */ |
386 | template <class T, class G> |
387 | T source(pair<T,T> p, const G&) { return p.first; } |
388 | |
389 | template <class T, class G> |
390 | T target(pair<T,T> p, const G&) { return p.second; } |
391 | |
392 | } |
393 | |
394 | #if defined(__GNUC__) && defined(__SGI_STL_PORT) |
395 | // For some reason g++ with STLport does not see the above definition |
396 | // of source() and target() unless we bring them into the boost |
397 | // namespace. |
398 | namespace boost { |
399 | using std::source; |
400 | using std::target; |
401 | } |
402 | #endif |
403 | |
404 | #endif // BOOST_GRAPH_TRAITS_HPP |
405 | |