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