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