Line data Source code
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 0 : 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
|
