]>
Commit | Line | Data |
---|---|---|
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 |