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