123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404 |
- //=======================================================================
- // Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
- // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek
- //
- // Distributed under the Boost Software License, Version 1.0. (See
- // accompanying file LICENSE_1_0.txt or copy at
- // http://www.boost.org/LICENSE_1_0.txt)
- //=======================================================================
- #ifndef BOOST_GRAPH_TRAITS_HPP
- #define BOOST_GRAPH_TRAITS_HPP
- #include <boost/config.hpp>
- #include <iterator>
- #include <utility> /* Primarily for std::pair */
- #include <boost/tuple/tuple.hpp>
- #include <boost/mpl/if.hpp>
- #include <boost/mpl/eval_if.hpp>
- #include <boost/mpl/bool.hpp>
- #include <boost/mpl/not.hpp>
- #include <boost/mpl/has_xxx.hpp>
- #include <boost/mpl/void.hpp>
- #include <boost/mpl/identity.hpp>
- #include <boost/type_traits/is_same.hpp>
- #include <boost/iterator/iterator_categories.hpp>
- #include <boost/iterator/iterator_adaptor.hpp>
- #include <boost/pending/property.hpp>
- #include <boost/detail/workaround.hpp>
- namespace boost {
- namespace detail {
- #define BOOST_GRAPH_MEMBER_OR_VOID(name) \
- BOOST_MPL_HAS_XXX_TRAIT_DEF(name) \
- template <typename T> struct BOOST_JOIN(get_member_, name) {typedef typename T::name type;}; \
- template <typename T> struct BOOST_JOIN(get_opt_member_, name): \
- boost::mpl::eval_if_c< \
- BOOST_JOIN(has_, name)<T>::value, \
- BOOST_JOIN(get_member_, name)<T>, \
- boost::mpl::identity<void> > \
- {};
- BOOST_GRAPH_MEMBER_OR_VOID(adjacency_iterator)
- BOOST_GRAPH_MEMBER_OR_VOID(out_edge_iterator)
- BOOST_GRAPH_MEMBER_OR_VOID(in_edge_iterator)
- BOOST_GRAPH_MEMBER_OR_VOID(vertex_iterator)
- BOOST_GRAPH_MEMBER_OR_VOID(edge_iterator)
- BOOST_GRAPH_MEMBER_OR_VOID(vertices_size_type)
- BOOST_GRAPH_MEMBER_OR_VOID(edges_size_type)
- BOOST_GRAPH_MEMBER_OR_VOID(degree_size_type)
- }
- template <typename G>
- struct graph_traits {
- #define BOOST_GRAPH_PULL_OPT_MEMBER(name) \
- typedef typename detail::BOOST_JOIN(get_opt_member_, name)<G>::type name;
- typedef typename G::vertex_descriptor vertex_descriptor;
- typedef typename G::edge_descriptor edge_descriptor;
- BOOST_GRAPH_PULL_OPT_MEMBER(adjacency_iterator)
- BOOST_GRAPH_PULL_OPT_MEMBER(out_edge_iterator)
- BOOST_GRAPH_PULL_OPT_MEMBER(in_edge_iterator)
- BOOST_GRAPH_PULL_OPT_MEMBER(vertex_iterator)
- BOOST_GRAPH_PULL_OPT_MEMBER(edge_iterator)
- typedef typename G::directed_category directed_category;
- typedef typename G::edge_parallel_category edge_parallel_category;
- typedef typename G::traversal_category traversal_category;
- BOOST_GRAPH_PULL_OPT_MEMBER(vertices_size_type)
- BOOST_GRAPH_PULL_OPT_MEMBER(edges_size_type)
- BOOST_GRAPH_PULL_OPT_MEMBER(degree_size_type)
- #undef BOOST_GRAPH_PULL_OPT_MEMBER
- static inline vertex_descriptor null_vertex();
- };
- template <typename G>
- inline typename graph_traits<G>::vertex_descriptor
- graph_traits<G>::null_vertex()
- { return G::null_vertex(); }
- // directed_category tags
- struct directed_tag { };
- struct undirected_tag { };
- struct bidirectional_tag : public directed_tag { };
- namespace detail {
- inline bool is_directed(directed_tag) { return true; }
- inline bool is_directed(undirected_tag) { return false; }
- }
- /** Return true if the given graph is directed. */
- template <typename Graph>
- bool is_directed(const Graph&) {
- typedef typename graph_traits<Graph>::directed_category Cat;
- return detail::is_directed(Cat());
- }
- /** Return true if the given graph is undirected. */
- template <typename Graph>
- bool is_undirected(const Graph& g) {
- return !is_directed(g);
- }
- /** @name Directed/Undirected Graph Traits */
- //@{
- namespace graph_detail {
- template <typename Tag>
- struct is_directed_tag
- : mpl::bool_<is_convertible<Tag, directed_tag>::value>
- { };
- } // namespace graph_detail
- template <typename Graph>
- struct is_directed_graph
- : graph_detail::is_directed_tag<
- typename graph_traits<Graph>::directed_category
- >
- { };
- template <typename Graph>
- struct is_undirected_graph
- : mpl::not_< is_directed_graph<Graph> >
- { };
- //@}
- // edge_parallel_category tags
- struct allow_parallel_edge_tag { };
- struct disallow_parallel_edge_tag { };
- namespace detail {
- inline bool allows_parallel(allow_parallel_edge_tag) { return true; }
- inline bool allows_parallel(disallow_parallel_edge_tag) { return false; }
- }
- template <typename Graph>
- bool allows_parallel_edges(const Graph&) {
- typedef typename graph_traits<Graph>::edge_parallel_category Cat;
- return detail::allows_parallel(Cat());
- }
- /** @name Parallel Edges Traits */
- //@{
- /**
- * The is_multigraph metafunction returns true if the graph allows
- * parallel edges. Technically, a multigraph is a simple graph that
- * allows parallel edges, but since there are no traits for the allowance
- * or disallowance of loops, this is a moot point.
- */
- template <typename Graph>
- struct is_multigraph
- : mpl::bool_<
- is_same<
- typename graph_traits<Graph>::edge_parallel_category,
- allow_parallel_edge_tag
- >::value
- >
- { };
- //@}
- // traversal_category tags
- struct incidence_graph_tag { };
- struct adjacency_graph_tag { };
- struct bidirectional_graph_tag : virtual incidence_graph_tag { };
- struct vertex_list_graph_tag { };
- struct edge_list_graph_tag { };
- struct adjacency_matrix_tag { };
- // Parallel traversal_category tags
- struct distributed_graph_tag { };
- struct distributed_vertex_list_graph_tag { };
- struct distributed_edge_list_graph_tag { };
- #define BOOST_GRAPH_SEQUENTIAL_TRAITS_DEFINES_DISTRIBUTED_TAGS // Disable these from external versions of PBGL
- /** @name Traversal Category Traits
- * These traits classify graph types by their supported methods of
- * vertex and edge traversal.
- */
- //@{
- template <typename Graph>
- struct is_incidence_graph
- : mpl::bool_<
- is_convertible<
- typename graph_traits<Graph>::traversal_category,
- incidence_graph_tag
- >::value
- >
- { };
- template <typename Graph>
- struct is_bidirectional_graph
- : mpl::bool_<
- is_convertible<
- typename graph_traits<Graph>::traversal_category,
- bidirectional_graph_tag
- >::value
- >
- { };
- template <typename Graph>
- struct is_vertex_list_graph
- : mpl::bool_<
- is_convertible<
- typename graph_traits<Graph>::traversal_category,
- vertex_list_graph_tag
- >::value
- >
- { };
- template <typename Graph>
- struct is_edge_list_graph
- : mpl::bool_<
- is_convertible<
- typename graph_traits<Graph>::traversal_category,
- edge_list_graph_tag
- >::value
- >
- { };
- template <typename Graph>
- struct is_adjacency_matrix
- : mpl::bool_<
- is_convertible<
- typename graph_traits<Graph>::traversal_category,
- adjacency_matrix_tag
- >::value
- >
- { };
- //@}
- /** @name Directed Graph Traits
- * These metafunctions are used to fully classify directed vs. undirected
- * graphs. Recall that an undirected graph is also bidirectional, but it
- * cannot be both undirected and directed at the same time.
- */
- //@{
- template <typename Graph>
- struct is_directed_unidirectional_graph
- : mpl::and_<
- is_directed_graph<Graph>, mpl::not_< is_bidirectional_graph<Graph> >
- >
- { };
- template <typename Graph>
- struct is_directed_bidirectional_graph
- : mpl::and_<
- is_directed_graph<Graph>, is_bidirectional_graph<Graph>
- >
- { };
- //@}
- //?? not the right place ?? Lee
- typedef boost::forward_traversal_tag multi_pass_input_iterator_tag;
- namespace detail {
- BOOST_MPL_HAS_XXX_TRAIT_DEF(graph_property_type)
- BOOST_MPL_HAS_XXX_TRAIT_DEF(edge_property_type)
- BOOST_MPL_HAS_XXX_TRAIT_DEF(vertex_property_type)
- template <typename G> struct get_graph_property_type {typedef typename G::graph_property_type type;};
- template <typename G> struct get_edge_property_type {typedef typename G::edge_property_type type;};
- template <typename G> struct get_vertex_property_type {typedef typename G::vertex_property_type type;};
- }
- template <typename G>
- struct graph_property_type
- : boost::mpl::eval_if<detail::has_graph_property_type<G>,
- detail::get_graph_property_type<G>,
- no_property> {};
- template <typename G>
- struct edge_property_type
- : boost::mpl::eval_if<detail::has_edge_property_type<G>,
- detail::get_edge_property_type<G>,
- no_property> {};
- template <typename G>
- struct vertex_property_type
- : boost::mpl::eval_if<detail::has_vertex_property_type<G>,
- detail::get_vertex_property_type<G>,
- no_property> {};
- template<typename G>
- struct graph_bundle_type {
- typedef typename G::graph_bundled type;
- };
- template<typename G>
- struct vertex_bundle_type {
- typedef typename G::vertex_bundled type;
- };
- template<typename G>
- struct edge_bundle_type {
- typedef typename G::edge_bundled type;
- };
- namespace graph { namespace detail {
- template<typename Graph, typename Descriptor>
- class bundled_result {
- typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
- typedef typename mpl::if_c<(is_same<Descriptor, Vertex>::value),
- vertex_bundle_type<Graph>,
- edge_bundle_type<Graph> >::type bundler;
- public:
- typedef typename bundler::type type;
- };
- template<typename Graph>
- class bundled_result<Graph, graph_bundle_t> {
- typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
- typedef graph_bundle_type<Graph> bundler;
- public:
- typedef typename bundler::type type;
- };
- } } // namespace graph::detail
- namespace graph_detail {
- // A helper metafunction for determining whether or not a type is
- // bundled.
- template <typename T>
- struct is_no_bundle : mpl::bool_<is_same<T, no_property>::value>
- { };
- } // namespace graph_detail
- /** @name Graph Property Traits
- * These metafunctions (along with those above), can be used to access the
- * vertex and edge properties (bundled or otherwise) of vertices and
- * edges.
- */
- //@{
- template<typename Graph>
- struct has_graph_property
- : mpl::not_<
- typename detail::is_no_property<
- typename graph_property_type<Graph>::type
- >::type
- >::type
- { };
- template<typename Graph>
- struct has_bundled_graph_property
- : mpl::not_<
- graph_detail::is_no_bundle<typename graph_bundle_type<Graph>::type>
- >
- { };
- template <typename Graph>
- struct has_vertex_property
- : mpl::not_<
- typename detail::is_no_property<typename vertex_property_type<Graph>::type>
- >::type
- { };
- template <typename Graph>
- struct has_bundled_vertex_property
- : mpl::not_<
- graph_detail::is_no_bundle<typename vertex_bundle_type<Graph>::type>
- >
- { };
- template <typename Graph>
- struct has_edge_property
- : mpl::not_<
- typename detail::is_no_property<typename edge_property_type<Graph>::type>
- >::type
- { };
- template <typename Graph>
- struct has_bundled_edge_property
- : mpl::not_<
- graph_detail::is_no_bundle<typename edge_bundle_type<Graph>::type>
- >
- { };
- //@}
- } // namespace boost
- // Since pair is in namespace std, Koenig lookup will find source and
- // target if they are also defined in namespace std. This is illegal,
- // but the alternative is to put source and target in the global
- // namespace which causes name conflicts with other libraries (like
- // SUIF).
- namespace std {
- /* Some helper functions for dealing with pairs as edges */
- template <class T, class G>
- T source(pair<T,T> p, const G&) { return p.first; }
- template <class T, class G>
- T target(pair<T,T> p, const G&) { return p.second; }
- }
- #if defined(__GNUC__) && defined(__SGI_STL_PORT)
- // For some reason g++ with STLport does not see the above definition
- // of source() and target() unless we bring them into the boost
- // namespace.
- namespace boost {
- using std::source;
- using std::target;
- }
- #endif
- #endif // BOOST_GRAPH_TRAITS_HPP
|