1 //=======================================================================
2 // Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
3 // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek
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 //=======================================================================
10 #ifndef BOOST_GRAPH_TRAITS_HPP
11 #define BOOST_GRAPH_TRAITS_HPP
13 #include <boost/config.hpp>
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>
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> > \
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)
54 #define BOOST_GRAPH_PULL_OPT_MEMBER(name) \
55 typedef typename detail::BOOST_JOIN(get_opt_member_, name)<G>::type name;
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)
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;
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
74 static inline vertex_descriptor null_vertex();
78 inline typename graph_traits<G>::vertex_descriptor
79 graph_traits<G>::null_vertex()
80 { return G::null_vertex(); }
82 // directed_category tags
83 struct directed_tag { };
84 struct undirected_tag { };
85 struct bidirectional_tag : public directed_tag { };
88 inline bool is_directed(directed_tag) { return true; }
89 inline bool is_directed(undirected_tag) { return false; }
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());
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);
105 /** @name Directed/Undirected Graph Traits */
107 namespace graph_detail {
108 template <typename Tag>
109 struct is_directed_tag
110 : mpl::bool_<is_convertible<Tag, directed_tag>::value>
112 } // namespace graph_detail
114 template <typename Graph>
115 struct is_directed_graph
116 : graph_detail::is_directed_tag<
117 typename graph_traits<Graph>::directed_category
121 template <typename Graph>
122 struct is_undirected_graph
123 : mpl::not_< is_directed_graph<Graph> >
127 // edge_parallel_category tags
128 struct allow_parallel_edge_tag { };
129 struct disallow_parallel_edge_tag { };
132 inline bool allows_parallel(allow_parallel_edge_tag) { return true; }
133 inline bool allows_parallel(disallow_parallel_edge_tag) { return false; }
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());
142 /** @name Parallel Edges Traits */
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.
150 template <typename Graph>
154 typename graph_traits<Graph>::edge_parallel_category,
155 allow_parallel_edge_tag
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 { };
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
175 /** @name Traversal Category Traits
176 * These traits classify graph types by their supported methods of
177 * vertex and edge traversal.
180 template <typename Graph>
181 struct is_incidence_graph
184 typename graph_traits<Graph>::traversal_category,
190 template <typename Graph>
191 struct is_bidirectional_graph
194 typename graph_traits<Graph>::traversal_category,
195 bidirectional_graph_tag
200 template <typename Graph>
201 struct is_vertex_list_graph
204 typename graph_traits<Graph>::traversal_category,
205 vertex_list_graph_tag
210 template <typename Graph>
211 struct is_edge_list_graph
214 typename graph_traits<Graph>::traversal_category,
220 template <typename Graph>
221 struct is_adjacency_matrix
224 typename graph_traits<Graph>::traversal_category,
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.
237 template <typename Graph>
238 struct is_directed_unidirectional_graph
240 is_directed_graph<Graph>, mpl::not_< is_bidirectional_graph<Graph> >
244 template <typename Graph>
245 struct is_directed_bidirectional_graph
247 is_directed_graph<Graph>, is_bidirectional_graph<Graph>
252 //?? not the right place ?? Lee
253 typedef boost::forward_traversal_tag multi_pass_input_iterator_tag;
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)
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;};
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>,
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>,
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>,
282 struct graph_bundle_type {
283 typedef typename G::graph_bundled type;
287 struct vertex_bundle_type {
288 typedef typename G::vertex_bundled type;
292 struct edge_bundle_type {
293 typedef typename G::edge_bundled type;
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;
304 typedef typename bundler::type type;
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;
312 typedef typename bundler::type type;
315 } } // namespace graph::detail
317 namespace graph_detail {
318 // A helper metafunction for determining whether or not a type is
320 template <typename T>
321 struct is_no_bundle : mpl::bool_<is_same<T, no_property>::value>
323 } // namespace graph_detail
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
331 template<typename Graph>
332 struct has_graph_property
334 typename detail::is_no_property<
335 typename graph_property_type<Graph>::type
340 template<typename Graph>
341 struct has_bundled_graph_property
343 graph_detail::is_no_bundle<typename graph_bundle_type<Graph>::type>
347 template <typename Graph>
348 struct has_vertex_property
350 typename detail::is_no_property<typename vertex_property_type<Graph>::type>
354 template <typename Graph>
355 struct has_bundled_vertex_property
357 graph_detail::is_no_bundle<typename vertex_bundle_type<Graph>::type>
361 template <typename Graph>
362 struct has_edge_property
364 typename detail::is_no_property<typename edge_property_type<Graph>::type>
368 template <typename Graph>
369 struct has_bundled_edge_property
371 graph_detail::is_no_bundle<typename edge_bundle_type<Graph>::type>
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
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; }
389 template <class T, class G>
390 T target(pair<T,T> p, const G&) { return p.second; }
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
404 #endif // BOOST_GRAPH_TRAITS_HPP