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