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
null_vertex()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 {
is_directed(directed_tag)101 inline bool is_directed(directed_tag) { return true; }
is_directed(undirected_tag)102 inline bool is_directed(undirected_tag) { return false; }
103 }
104
105 /** Return true if the given graph is directed. */
is_directed(const Graph &)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. */
is_undirected(const Graph & g)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 {
allows_parallel(allow_parallel_edge_tag)152 inline bool allows_parallel(allow_parallel_edge_tag) { return true; }
allows_parallel(disallow_parallel_edge_tag)153 inline bool allows_parallel(disallow_parallel_edge_tag) { return false; }
154 }
155
allows_parallel_edges(const Graph &)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 */
source(pair<T,T> p,const G &)434 template < class T, class G > T source(pair< T, T > p, const G&)
435 {
436 return p.first;
437 }
438
target(pair<T,T> p,const G &)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