sl@0: //=======================================================================
sl@0: // Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
sl@0: // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek
sl@0: //
sl@0: // Distributed under the Boost Software License, Version 1.0. (See
sl@0: // accompanying file LICENSE_1_0.txt or copy at
sl@0: // http://www.boost.org/LICENSE_1_0.txt)
sl@0: //=======================================================================
sl@0: 
sl@0: #ifndef BOOST_GRAPH_TRAITS_HPP
sl@0: #define BOOST_GRAPH_TRAITS_HPP
sl@0: 
sl@0: #include <boost/config.hpp>
sl@0: #include <iterator>
sl@0: #include <boost/tuple/tuple.hpp>
sl@0: #include <boost/mpl/if.hpp>
sl@0: #include <boost/type_traits/is_same.hpp>
sl@0: #include <boost/iterator/iterator_categories.hpp>
sl@0: #include <boost/iterator/iterator_adaptor.hpp>
sl@0: #include <boost/detail/workaround.hpp>
sl@0: 
sl@0: namespace boost {
sl@0: 
sl@0:   template <typename G>
sl@0:   struct graph_traits {
sl@0:     typedef typename G::vertex_descriptor      vertex_descriptor;
sl@0:     typedef typename G::edge_descriptor        edge_descriptor;
sl@0:     typedef typename G::adjacency_iterator     adjacency_iterator;
sl@0:     typedef typename G::out_edge_iterator      out_edge_iterator;
sl@0:     typedef typename G::in_edge_iterator       in_edge_iterator;
sl@0:     typedef typename G::vertex_iterator        vertex_iterator;
sl@0:     typedef typename G::edge_iterator          edge_iterator;
sl@0: 
sl@0:     typedef typename G::directed_category      directed_category;
sl@0:     typedef typename G::edge_parallel_category edge_parallel_category;
sl@0:     typedef typename G::traversal_category     traversal_category;
sl@0: 
sl@0:     typedef typename G::vertices_size_type     vertices_size_type;
sl@0:     typedef typename G::edges_size_type        edges_size_type;
sl@0:     typedef typename G::degree_size_type       degree_size_type;
sl@0: 
sl@0:     static inline vertex_descriptor null_vertex();
sl@0:   };
sl@0: 
sl@0:   template <typename G>
sl@0:   inline typename graph_traits<G>::vertex_descriptor
sl@0:   graph_traits<G>::null_vertex()
sl@0:   {
sl@0:     return G::null_vertex();
sl@0:   }
sl@0: 
sl@0:   // directed_category tags
sl@0:   struct directed_tag { };
sl@0:   struct undirected_tag { };
sl@0:   struct bidirectional_tag : public directed_tag { };
sl@0: 
sl@0:   namespace detail {
sl@0:     inline bool is_directed(directed_tag) { return true; }
sl@0:     inline bool is_directed(undirected_tag) { return false; }
sl@0:   }
sl@0: 
sl@0:   template <typename Graph>
sl@0:   bool is_directed(const Graph&) { 
sl@0:     typedef typename graph_traits<Graph>::directed_category Cat;
sl@0:     return detail::is_directed(Cat());
sl@0:   }
sl@0:   template <typename Graph>
sl@0:   bool is_undirected(const Graph& g) { 
sl@0:     return ! is_directed(g);
sl@0:   }
sl@0: 
sl@0:   // edge_parallel_category tags
sl@0:   struct allow_parallel_edge_tag {};
sl@0:   struct disallow_parallel_edge_tag {};
sl@0: 
sl@0:   namespace detail {
sl@0:     inline bool allows_parallel(allow_parallel_edge_tag) { return true; }
sl@0:     inline bool allows_parallel(disallow_parallel_edge_tag) { return false; }
sl@0:   }
sl@0: 
sl@0:   template <typename Graph>
sl@0:   bool allows_parallel_edges(const Graph&) { 
sl@0:     typedef typename graph_traits<Graph>::edge_parallel_category Cat;
sl@0:     return detail::allows_parallel(Cat());
sl@0:   }
sl@0: 
sl@0:   // traversal_category tags
sl@0:   struct incidence_graph_tag { };
sl@0:   struct adjacency_graph_tag { };
sl@0:   struct bidirectional_graph_tag : 
sl@0:     public virtual incidence_graph_tag { };
sl@0:   struct vertex_list_graph_tag { };
sl@0:   struct edge_list_graph_tag { };
sl@0:   struct adjacency_matrix_tag { };
sl@0: 
sl@0:   //?? not the right place ?? Lee
sl@0:   typedef boost::forward_traversal_tag multi_pass_input_iterator_tag;
sl@0: 
sl@0:   template <typename G>
sl@0:   struct edge_property_type {
sl@0:     typedef typename G::edge_property_type type;
sl@0:   };
sl@0:   template <typename G>
sl@0:   struct vertex_property_type {
sl@0:     typedef typename G::vertex_property_type type;
sl@0:   };
sl@0:   template <typename G>
sl@0:   struct graph_property_type {
sl@0:     typedef typename G::graph_property_type type;
sl@0:   };
sl@0: 
sl@0:   struct no_vertex_bundle {};
sl@0:   struct no_edge_bundle {};
sl@0: 
sl@0:   template<typename G>
sl@0:   struct vertex_bundle_type
sl@0:   {
sl@0:     typedef typename G::vertex_bundled type;
sl@0:   };
sl@0: 
sl@0:   template<typename G>
sl@0:   struct edge_bundle_type
sl@0:   {
sl@0:     typedef typename G::edge_bundled type;
sl@0:   };
sl@0: 
sl@0:   namespace graph { namespace detail {
sl@0:     template<typename Graph, typename Descriptor>
sl@0:     class bundled_result
sl@0:     {
sl@0:       typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
sl@0:       typedef typename mpl::if_c<(is_same<Descriptor, Vertex>::value),
sl@0:                                  vertex_bundle_type<Graph>,
sl@0:                                  edge_bundle_type<Graph> >::type bundler;
sl@0: 
sl@0:     public:
sl@0:       typedef typename bundler::type type;
sl@0:     };
sl@0:   } } // end namespace graph::detail
sl@0: } // namespace boost
sl@0: 
sl@0: // Since pair is in namespace std, Koenig lookup will find source and
sl@0: // target if they are also defined in namespace std.  This is illegal,
sl@0: // but the alternative is to put source and target in the global
sl@0: // namespace which causes name conflicts with other libraries (like
sl@0: // SUIF).
sl@0: namespace std {
sl@0: 
sl@0:   /* Some helper functions for dealing with pairs as edges */
sl@0:   template <class T, class G>
sl@0:   T source(pair<T,T> p, const G&) { return p.first; }
sl@0: 
sl@0:   template <class T, class G>
sl@0:   T target(pair<T,T> p, const G&) { return p.second; }
sl@0: 
sl@0: }
sl@0: 
sl@0: #if defined(__GNUC__) && defined(__SGI_STL_PORT)
sl@0: // For some reason g++ with STLport does not see the above definition
sl@0: // of source() and target() unless we bring them into the boost
sl@0: // namespace.
sl@0: namespace boost {
sl@0:   using std::source;
sl@0:   using std::target;
sl@0: }
sl@0: #endif
sl@0: 
sl@0: #endif // BOOST_GRAPH_TRAITS_HPP