]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
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 | ||
f67539c2 TL |
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 | } | |
7c673cae | 55 | |
f67539c2 TL |
56 | template < typename G > struct graph_traits |
57 | { | |
7c673cae | 58 | #define BOOST_GRAPH_PULL_OPT_MEMBER(name) \ |
f67539c2 TL |
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) | |
7c673cae FG |
76 | #undef BOOST_GRAPH_PULL_OPT_MEMBER |
77 | ||
f67539c2 TL |
78 | static inline vertex_descriptor null_vertex(); |
79 | }; | |
7c673cae | 80 | |
f67539c2 TL |
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 | } | |
7c673cae | 87 | |
f67539c2 TL |
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 | } | |
7c673cae | 104 | |
f67539c2 TL |
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 | } | |
7c673cae | 111 | |
f67539c2 TL |
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 | } | |
7c673cae | 117 | |
f67539c2 TL |
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 | } | |
7c673cae | 155 | |
f67539c2 TL |
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 | } | |
7c673cae | 161 | |
f67539c2 TL |
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; | |
7c673cae | 291 | }; |
f67539c2 TL |
292 | template < typename G > struct get_edge_property_type |
293 | { | |
294 | typedef typename G::edge_property_type type; | |
7c673cae | 295 | }; |
f67539c2 TL |
296 | template < typename G > struct get_vertex_property_type |
297 | { | |
298 | typedef typename G::vertex_property_type type; | |
7c673cae | 299 | }; |
f67539c2 TL |
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; | |
7c673cae | 346 | |
7c673cae FG |
347 | public: |
348 | typedef typename bundler::type type; | |
349 | }; | |
350 | ||
f67539c2 TL |
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 | ||
7c673cae FG |
357 | public: |
358 | typedef typename bundler::type type; | |
359 | }; | |
360 | ||
f67539c2 TL |
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 | //@} | |
7c673cae FG |
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). | |
f67539c2 TL |
430 | namespace std |
431 | { | |
7c673cae | 432 | |
f67539c2 TL |
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 | } | |
7c673cae | 438 | |
f67539c2 TL |
439 | template < class T, class G > T target(pair< T, T > p, const G&) |
440 | { | |
441 | return p.second; | |
442 | } | |
7c673cae FG |
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. | |
f67539c2 TL |
450 | namespace boost |
451 | { | |
452 | using std::source; | |
453 | using std::target; | |
7c673cae FG |
454 | } |
455 | #endif | |
456 | ||
457 | #endif // BOOST_GRAPH_TRAITS_HPP |