boost/graph/graph_traits.hpp

0001 //=======================================================================
0002 // Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
0003 // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek
0004 //
0005 // Distributed under the Boost Software License, Version 1.0. (See
0006 // accompanying file LICENSE_1_0.txt or copy at
0007 // http://www.boost.org/LICENSE_1_0.txt)
0008 //=======================================================================
0009
0010 #ifndef BOOST_GRAPH_TRAITS_HPP
0011 #define BOOST_GRAPH_TRAITS_HPP
0012
0013 #include <boost/config.hpp>
0014 #include <iterator>
0015 #include <utility> /* Primarily for std::pair */
0016 #include <boost/tuple/tuple.hpp>
0017 #include <boost/mpl/if.hpp>
0018 #include <boost/mpl/eval_if.hpp>
0019 #include <boost/mpl/bool.hpp>
0020 #include <boost/mpl/not.hpp>
0021 #include <boost/mpl/has_xxx.hpp>
0022 #include <boost/mpl/void.hpp>
0023 #include <boost/mpl/identity.hpp>
0024 #include <boost/mpl/and.hpp>
0025 #include <boost/type_traits/is_same.hpp>
0026 #include <boost/iterator/iterator_categories.hpp>
0027 #include <boost/iterator/iterator_adaptor.hpp>
0028 #include <boost/pending/property.hpp>
0029 #include <boost/detail/workaround.hpp>
0030
0031 namespace boost
0032 {
0033
0034 namespace detail
0035 {
0036 #define BOOST_GRAPH_MEMBER_OR_VOID(name)                                                                                            \
0037     BOOST_MPL_HAS_XXX_TRAIT_DEF(name)                                                                                               \
0038     template < typename T > struct BOOST_JOIN(get_member_, name)                                                                    \
0039     {                                                                                                                               \
0040         typedef typename T::name type;                                                                                              \
0041     };                                                                                                                              \
0042     template < typename T >                                                                                                         \
0043     struct BOOST_JOIN(get_opt_member_, name)                                                                                        \
0044     : boost::mpl::eval_if_c< BOOST_JOIN(has_, name) < T >::value, BOOST_JOIN(get_member_, name)< T >, boost::mpl::identity< void > >\
0045     {                                                                                                                               \
0046     };
0047     BOOST_GRAPH_MEMBER_OR_VOID(adjacency_iterator)
0048     BOOST_GRAPH_MEMBER_OR_VOID(out_edge_iterator)
0049     BOOST_GRAPH_MEMBER_OR_VOID(in_edge_iterator)
0050     BOOST_GRAPH_MEMBER_OR_VOID(vertex_iterator)
0051     BOOST_GRAPH_MEMBER_OR_VOID(edge_iterator)
0052     BOOST_GRAPH_MEMBER_OR_VOID(vertices_size_type)
0053     BOOST_GRAPH_MEMBER_OR_VOID(edges_size_type)
0054     BOOST_GRAPH_MEMBER_OR_VOID(degree_size_type)
0055 }
0056
0057 template < typename G > struct graph_traits
0058 {
0059 #define BOOST_GRAPH_PULL_OPT_MEMBER(name) \
0060     typedef typename detail::BOOST_JOIN(get_opt_member_, name)< G >::type name;
0061
0062     typedef typename G::vertex_descriptor vertex_descriptor;
0063     typedef typename G::edge_descriptor edge_descriptor;
0064     BOOST_GRAPH_PULL_OPT_MEMBER(adjacency_iterator)
0065     BOOST_GRAPH_PULL_OPT_MEMBER(out_edge_iterator)
0066     BOOST_GRAPH_PULL_OPT_MEMBER(in_edge_iterator)
0067     BOOST_GRAPH_PULL_OPT_MEMBER(vertex_iterator)
0068     BOOST_GRAPH_PULL_OPT_MEMBER(edge_iterator)
0069
0070     typedef typename G::directed_category directed_category;
0071     typedef typename G::edge_parallel_category edge_parallel_category;
0072     typedef typename G::traversal_category traversal_category;
0073
0074     BOOST_GRAPH_PULL_OPT_MEMBER(vertices_size_type)
0075     BOOST_GRAPH_PULL_OPT_MEMBER(edges_size_type)
0076     BOOST_GRAPH_PULL_OPT_MEMBER(degree_size_type)
0077 #undef BOOST_GRAPH_PULL_OPT_MEMBER
0078
0079     static inline vertex_descriptor null_vertex();
0080 };
0081
0082 template < typename G >
0083 inline typename graph_traits< G >::vertex_descriptor
0084 graph_traits< G >::null_vertex()
0085 {
0086     return G::null_vertex();
0087 }
0088
0089 // directed_category tags
0090 struct directed_tag
0091 {
0092 };
0093 struct undirected_tag
0094 {
0095 };
0096 struct bidirectional_tag : public directed_tag
0097 {
0098 };
0099
0100 namespace detail
0101 {
0102     inline bool is_directed(directed_tag) { return true; }
0103     inline bool is_directed(undirected_tag) { return false; }
0104 }
0105
0106 /** Return true if the given graph is directed. */
0107 template < typename Graph > bool is_directed(const Graph&)
0108 {
0109     typedef typename graph_traits< Graph >::directed_category Cat;
0110     return detail::is_directed(Cat());
0111 }
0112
0113 /** Return true if the given graph is undirected. */
0114 template < typename Graph > bool is_undirected(const Graph& g)
0115 {
0116     return !is_directed(g);
0117 }
0118
0119 /** @name Directed/Undirected Graph Traits */
0120 //@{
0121 namespace graph_detail
0122 {
0123     template < typename Tag >
0124     struct is_directed_tag
0125     : mpl::bool_< is_convertible< Tag, directed_tag >::value >
0126     {
0127     };
0128 } // namespace graph_detail
0129
0130 template < typename Graph >
0131 struct is_directed_graph
0132 : graph_detail::is_directed_tag<
0133       typename graph_traits< Graph >::directed_category >
0134 {
0135 };
0136
0137 template < typename Graph >
0138 struct is_undirected_graph : mpl::not_< is_directed_graph< Graph > >
0139 {
0140 };
0141 //@}
0142
0143 // edge_parallel_category tags
0144 struct allow_parallel_edge_tag
0145 {
0146 };
0147 struct disallow_parallel_edge_tag
0148 {
0149 };
0150
0151 namespace detail
0152 {
0153     inline bool allows_parallel(allow_parallel_edge_tag) { return true; }
0154     inline bool allows_parallel(disallow_parallel_edge_tag) { return false; }
0155 }
0156
0157 template < typename Graph > bool allows_parallel_edges(const Graph&)
0158 {
0159     typedef typename graph_traits< Graph >::edge_parallel_category Cat;
0160     return detail::allows_parallel(Cat());
0161 }
0162
0163 /** @name Parallel Edges Traits */
0164 //@{
0165 /**
0166  * The is_multigraph metafunction returns true if the graph allows
0167  * parallel edges. Technically, a multigraph is a simple graph that
0168  * allows parallel edges, but since there are no traits for the allowance
0169  * or disallowance of loops, this is a moot point.
0170  */
0171 template < typename Graph >
0172 struct is_multigraph
0173 : mpl::bool_< is_same< typename graph_traits< Graph >::edge_parallel_category,
0174       allow_parallel_edge_tag >::value >
0175 {
0176 };
0177 //@}
0178
0179 // traversal_category tags
0180 struct incidence_graph_tag
0181 {
0182 };
0183 struct adjacency_graph_tag
0184 {
0185 };
0186 struct bidirectional_graph_tag : virtual incidence_graph_tag
0187 {
0188 };
0189 struct vertex_list_graph_tag
0190 {
0191 };
0192 struct edge_list_graph_tag
0193 {
0194 };
0195 struct adjacency_matrix_tag
0196 {
0197 };
0198
0199 // Parallel traversal_category tags
0200 struct distributed_graph_tag
0201 {
0202 };
0203 struct distributed_vertex_list_graph_tag
0204 {
0205 };
0206 struct distributed_edge_list_graph_tag
0207 {
0208 };
0209 #define BOOST_GRAPH_SEQUENTIAL_TRAITS_DEFINES_DISTRIBUTED_TAGS // Disable these
0210                                                                // from external
0211                                                                // versions of
0212                                                                // PBGL
0213
0214 /** @name Traversal Category Traits
0215  * These traits classify graph types by their supported methods of
0216  * vertex and edge traversal.
0217  */
0218 //@{
0219 template < typename Graph >
0220 struct is_incidence_graph
0221 : mpl::bool_<
0222       is_convertible< typename graph_traits< Graph >::traversal_category,
0223           incidence_graph_tag >::value >
0224 {
0225 };
0226
0227 template < typename Graph >
0228 struct is_bidirectional_graph
0229 : mpl::bool_<
0230       is_convertible< typename graph_traits< Graph >::traversal_category,
0231           bidirectional_graph_tag >::value >
0232 {
0233 };
0234
0235 template < typename Graph >
0236 struct is_vertex_list_graph
0237 : mpl::bool_<
0238       is_convertible< typename graph_traits< Graph >::traversal_category,
0239           vertex_list_graph_tag >::value >
0240 {
0241 };
0242
0243 template < typename Graph >
0244 struct is_edge_list_graph
0245 : mpl::bool_<
0246       is_convertible< typename graph_traits< Graph >::traversal_category,
0247           edge_list_graph_tag >::value >
0248 {
0249 };
0250
0251 template < typename Graph >
0252 struct is_adjacency_matrix
0253 : mpl::bool_<
0254       is_convertible< typename graph_traits< Graph >::traversal_category,
0255           adjacency_matrix_tag >::value >
0256 {
0257 };
0258 //@}
0259
0260 /** @name Directed Graph Traits
0261  * These metafunctions are used to fully classify directed vs. undirected
0262  * graphs. Recall that an undirected graph is also bidirectional, but it
0263  * cannot be both undirected and directed at the same time.
0264  */
0265 //@{
0266 template < typename Graph >
0267 struct is_directed_unidirectional_graph
0268 : mpl::and_< is_directed_graph< Graph >,
0269       mpl::not_< is_bidirectional_graph< Graph > > >
0270 {
0271 };
0272
0273 template < typename Graph >
0274 struct is_directed_bidirectional_graph
0275 : mpl::and_< is_directed_graph< Graph >, is_bidirectional_graph< Graph > >
0276 {
0277 };
0278 //@}
0279
0280 //?? not the right place ?? Lee
0281 typedef boost::forward_traversal_tag multi_pass_input_iterator_tag;
0282
0283 namespace detail
0284 {
0285     BOOST_MPL_HAS_XXX_TRAIT_DEF(graph_property_type)
0286     BOOST_MPL_HAS_XXX_TRAIT_DEF(edge_property_type)
0287     BOOST_MPL_HAS_XXX_TRAIT_DEF(vertex_property_type)
0288
0289     template < typename G > struct get_graph_property_type
0290     {
0291         typedef typename G::graph_property_type type;
0292     };
0293     template < typename G > struct get_edge_property_type
0294     {
0295         typedef typename G::edge_property_type type;
0296     };
0297     template < typename G > struct get_vertex_property_type
0298     {
0299         typedef typename G::vertex_property_type type;
0300     };
0301 }
0302
0303 template < typename G >
0304 struct graph_property_type
0305 : boost::mpl::eval_if< detail::has_graph_property_type< G >,
0306       detail::get_graph_property_type< G >, no_property >
0307 {
0308 };
0309 template < typename G >
0310 struct edge_property_type
0311 : boost::mpl::eval_if< detail::has_edge_property_type< G >,
0312       detail::get_edge_property_type< G >, no_property >
0313 {
0314 };
0315 template < typename G >
0316 struct vertex_property_type
0317 : boost::mpl::eval_if< detail::has_vertex_property_type< G >,
0318       detail::get_vertex_property_type< G >, no_property >
0319 {
0320 };
0321
0322 template < typename G > struct graph_bundle_type
0323 {
0324     typedef typename G::graph_bundled type;
0325 };
0326
0327 template < typename G > struct vertex_bundle_type
0328 {
0329     typedef typename G::vertex_bundled type;
0330 };
0331
0332 template < typename G > struct edge_bundle_type
0333 {
0334     typedef typename G::edge_bundled type;
0335 };
0336
0337 namespace graph
0338 {
0339     namespace detail
0340     {
0341         template < typename Graph, typename Descriptor > class bundled_result
0342         {
0343             typedef typename graph_traits< Graph >::vertex_descriptor Vertex;
0344             typedef typename mpl::if_c< (is_same< Descriptor, Vertex >::value),
0345                 vertex_bundle_type< Graph >, edge_bundle_type< Graph > >::type
0346                 bundler;
0347
0348         public:
0349             typedef typename bundler::type type;
0350         };
0351
0352         template < typename Graph >
0353         class bundled_result< Graph, graph_bundle_t >
0354         {
0355             typedef typename graph_traits< Graph >::vertex_descriptor Vertex;
0356             typedef graph_bundle_type< Graph > bundler;
0357
0358         public:
0359             typedef typename bundler::type type;
0360         };
0361
0362     }
0363 } // namespace graph::detail
0364
0365 namespace graph_detail
0366 {
0367     // A helper metafunction for determining whether or not a type is
0368     // bundled.
0369     template < typename T >
0370     struct is_no_bundle : mpl::bool_< is_same< T, no_property >::value >
0371     {
0372     };
0373 } // namespace graph_detail
0374
0375 /** @name Graph Property Traits
0376  * These metafunctions (along with those above), can be used to access the
0377  * vertex and edge properties (bundled or otherwise) of vertices and
0378  * edges.
0379  */
0380 //@{
0381 template < typename Graph >
0382 struct has_graph_property
0383 : mpl::not_< typename detail::is_no_property<
0384       typename graph_property_type< Graph >::type >::type >::type
0385 {
0386 };
0387
0388 template < typename Graph >
0389 struct has_bundled_graph_property
0390 : mpl::not_<
0391       graph_detail::is_no_bundle< typename graph_bundle_type< Graph >::type > >
0392 {
0393 };
0394
0395 template < typename Graph >
0396 struct has_vertex_property
0397 : mpl::not_< typename detail::is_no_property<
0398       typename vertex_property_type< Graph >::type > >::type
0399 {
0400 };
0401
0402 template < typename Graph >
0403 struct has_bundled_vertex_property
0404 : mpl::not_<
0405       graph_detail::is_no_bundle< typename vertex_bundle_type< Graph >::type > >
0406 {
0407 };
0408
0409 template < typename Graph >
0410 struct has_edge_property
0411 : mpl::not_< typename detail::is_no_property<
0412       typename edge_property_type< Graph >::type > >::type
0413 {
0414 };
0415
0416 template < typename Graph >
0417 struct has_bundled_edge_property
0418 : mpl::not_<
0419       graph_detail::is_no_bundle< typename edge_bundle_type< Graph >::type > >
0420 {
0421 };
0422 //@}
0423
0424 } // namespace boost
0425
0426 // Since pair is in namespace std, Koenig lookup will find source and
0427 // target if they are also defined in namespace std.  This is illegal,
0428 // but the alternative is to put source and target in the global
0429 // namespace which causes name conflicts with other libraries (like
0430 // SUIF).
0431 namespace std
0432 {
0433
0434 /* Some helper functions for dealing with pairs as edges */
0435 template < class T, class G > T source(pair< T, T > p, const G&)
0436 {
0437     return p.first;
0438 }
0439
0440 template < class T, class G > T target(pair< T, T > p, const G&)
0441 {
0442     return p.second;
0443 }
0444
0445 }
0446
0447 #if defined(__GNUC__) && defined(__SGI_STL_PORT)
0448 // For some reason g++ with STLport does not see the above definition
0449 // of source() and target() unless we bring them into the boost
0450 // namespace.
0451 namespace boost
0452 {
0453 using std::source;
0454 using std::target;
0455 }
0456 #endif
0457
0458 #endif // BOOST_GRAPH_TRAITS_HPP