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
30namespace boost
31{
32
33namespace 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
56template < 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
81template < typename G >
82inline typename graph_traits< G >::vertex_descriptor
83graph_traits< G >::null_vertex()
84{
85 return G::null_vertex();
86}
87
88// directed_category tags
89struct directed_tag
90{
91};
92struct undirected_tag
93{
94};
95struct bidirectional_tag : public directed_tag
96{
97};
98
99namespace 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. */
106template < 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. */
113template < typename Graph > bool is_undirected(const Graph& g)
114{
115 return !is_directed(g);
116}
117
118/** @name Directed/Undirected Graph Traits */
119//@{
120namespace 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
129template < typename Graph >
130struct is_directed_graph
131: graph_detail::is_directed_tag<
132 typename graph_traits< Graph >::directed_category >
133{
134};
135
136template < typename Graph >
137struct is_undirected_graph : mpl::not_< is_directed_graph< Graph > >
138{
139};
140//@}
141
142// edge_parallel_category tags
143struct allow_parallel_edge_tag
144{
145};
146struct disallow_parallel_edge_tag
147{
148};
149
150namespace 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
156template < 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 */
170template < typename Graph >
171struct 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
179struct incidence_graph_tag
180{
181};
182struct adjacency_graph_tag
183{
184};
185struct bidirectional_graph_tag : virtual incidence_graph_tag
186{
187};
188struct vertex_list_graph_tag
189{
190};
191struct edge_list_graph_tag
192{
193};
194struct adjacency_matrix_tag
195{
196};
197
198// Parallel traversal_category tags
199struct distributed_graph_tag
200{
201};
202struct distributed_vertex_list_graph_tag
203{
204};
205struct 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//@{
218template < typename Graph >
219struct is_incidence_graph
220: mpl::bool_<
221 is_convertible< typename graph_traits< Graph >::traversal_category,
222 incidence_graph_tag >::value >
223{
224};
225
226template < typename Graph >
227struct is_bidirectional_graph
228: mpl::bool_<
229 is_convertible< typename graph_traits< Graph >::traversal_category,
230 bidirectional_graph_tag >::value >
231{
232};
233
234template < typename Graph >
235struct 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
242template < typename Graph >
243struct 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
250template < typename Graph >
251struct 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//@{
265template < typename Graph >
266struct is_directed_unidirectional_graph
267: mpl::and_< is_directed_graph< Graph >,
268 mpl::not_< is_bidirectional_graph< Graph > > >
269{
270};
271
272template < typename Graph >
273struct 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
280typedef boost::forward_traversal_tag multi_pass_input_iterator_tag;
281
282namespace 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
302template < typename G >
303struct 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};
308template < typename G >
309struct 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};
314template < typename G >
315struct 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
321template < typename G > struct graph_bundle_type
322{
323 typedef typename G::graph_bundled type;
324};
325
326template < typename G > struct vertex_bundle_type
327{
328 typedef typename G::vertex_bundled type;
329};
330
331template < typename G > struct edge_bundle_type
332{
333 typedef typename G::edge_bundled type;
334};
335
336namespace 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
364namespace 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//@{
380template < typename Graph >
381struct has_graph_property
382: mpl::not_< typename detail::is_no_property<
383 typename graph_property_type< Graph >::type >::type >::type
384{
385};
386
387template < typename Graph >
388struct has_bundled_graph_property
389: mpl::not_<
390 graph_detail::is_no_bundle< typename graph_bundle_type< Graph >::type > >
391{
392};
393
394template < typename Graph >
395struct has_vertex_property
396: mpl::not_< typename detail::is_no_property<
397 typename vertex_property_type< Graph >::type > >::type
398{
399};
400
401template < typename Graph >
402struct has_bundled_vertex_property
403: mpl::not_<
404 graph_detail::is_no_bundle< typename vertex_bundle_type< Graph >::type > >
405{
406};
407
408template < typename Graph >
409struct has_edge_property
410: mpl::not_< typename detail::is_no_property<
411 typename edge_property_type< Graph >::type > >::type
412{
413};
414
415template < typename Graph >
416struct 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).
430namespace std
431{
432
433/* Some helper functions for dealing with pairs as edges */
434template < class T, class G > T source(pair< T, T > p, const G&)
435{
436 return p.first;
437}
438
439template < 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.
450namespace boost
451{
452using std::source;
453using std::target;
454}
455#endif
456
457#endif // BOOST_GRAPH_TRAITS_HPP
458