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 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).
383namespace 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.
398namespace boost {
399 using std::source;
400 using std::target;
401}
402#endif
403
404#endif // BOOST_GRAPH_TRAITS_HPP
405

source code of boost/boost/graph/graph_traits.hpp