Boost_1_39_0/boost/graph/graph_traits.hpp

   1 //=======================================================================
   2 // Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
   3 // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek
   4 //
   5 // Distributed under the Boost Software License, Version 1.0. (See
   6 // accompanying file LICENSE_1_0.txt or copy at
   7 // http://www.boost.org/LICENSE_1_0.txt)
   8 //=======================================================================
   9
  10 #ifndef BOOST_GRAPH_TRAITS_HPP
  11 #define BOOST_GRAPH_TRAITS_HPP
  12
  13 #include <boost/config.hpp>
  14 #include <iterator>
  15 #include <boost/tuple/tuple.hpp>
  16 #include <boost/mpl/if.hpp>
  17 #include <boost/type_traits/is_same.hpp>
  18 #include <boost/iterator/iterator_categories.hpp>
  19 #include <boost/iterator/iterator_adaptor.hpp>
  20 #include <boost/detail/workaround.hpp>
  21
  22 namespace boost {
  23
  24   template <typename G>
  25   struct graph_traits {
  26     typedef typename G::vertex_descriptor      vertex_descriptor;
  27     typedef typename G::edge_descriptor        edge_descriptor;
  28     typedef typename G::adjacency_iterator     adjacency_iterator;
  29     typedef typename G::out_edge_iterator      out_edge_iterator;
  30     typedef typename G::in_edge_iterator       in_edge_iterator;
  31     typedef typename G::vertex_iterator        vertex_iterator;
  32     typedef typename G::edge_iterator          edge_iterator;
  33
  34     typedef typename G::directed_category      directed_category;
  35     typedef typename G::edge_parallel_category edge_parallel_category;
  36     typedef typename G::traversal_category     traversal_category;
  37
  38     typedef typename G::vertices_size_type     vertices_size_type;
  39     typedef typename G::edges_size_type        edges_size_type;
  40     typedef typename G::degree_size_type       degree_size_type;
  41
  42     static inline vertex_descriptor null_vertex();
  43   };
  44
  45   template <typename G>
  46   inline typename graph_traits<G>::vertex_descriptor
  47   graph_traits<G>::null_vertex()
  48   {
  49     return G::null_vertex();
  50   }
  51
  52   // directed_category tags
  53   struct directed_tag { };
  54   struct undirected_tag { };
  55   struct bidirectional_tag : public directed_tag { };
  56
  57   namespace detail {
  58     inline bool is_directed(directed_tag) { return true; }
  59     inline bool is_directed(undirected_tag) { return false; }
  60   }
  61
  62   template <typename Graph>
  63   bool is_directed(const Graph&) {
  64     typedef typename graph_traits<Graph>::directed_category Cat;
  65     return detail::is_directed(Cat());
  66   }
  67   template <typename Graph>
  68   bool is_undirected(const Graph& g) {
  69     return ! is_directed(g);
  70   }
  71
  72   // edge_parallel_category tags
  73   struct allow_parallel_edge_tag {};
  74   struct disallow_parallel_edge_tag {};
  75
  76   namespace detail {
  77     inline bool allows_parallel(allow_parallel_edge_tag) { return true; }
  78     inline bool allows_parallel(disallow_parallel_edge_tag) { return false; }
  79   }
  80
  81   template <typename Graph>
  82   bool allows_parallel_edges(const Graph&) {
  83     typedef typename graph_traits<Graph>::edge_parallel_category Cat;
  84     return detail::allows_parallel(Cat());
  85   }
  86
  87   // traversal_category tags
  88   struct incidence_graph_tag { };
  89   struct adjacency_graph_tag { };
  90   struct bidirectional_graph_tag :
  91     public virtual incidence_graph_tag { };
  92   struct vertex_list_graph_tag { };
  93   struct edge_list_graph_tag { };
  94   struct adjacency_matrix_tag { };
  95
  96   //?? not the right place ?? Lee
  97   typedef boost::forward_traversal_tag multi_pass_input_iterator_tag;
  98
  99   template <typename G>
 100   struct edge_property_type {
 101     typedef typename G::edge_property_type type;
 102   };
 103   template <typename G>
 104   struct vertex_property_type {
 105     typedef typename G::vertex_property_type type;
 106   };
 107   template <typename G>
 108   struct graph_property_type {
 109     typedef typename G::graph_property_type type;
 110   };
 111
 112   struct no_vertex_bundle {};
 113   struct no_edge_bundle {};
 114
 115   template<typename G>
 116   struct vertex_bundle_type
 117   {
 118     typedef typename G::vertex_bundled type;
 119   };
 120
 121   template<typename G>
 122   struct edge_bundle_type
 123   {
 124     typedef typename G::edge_bundled type;
 125   };
 126
 127   namespace graph { namespace detail {
 128     template<typename Graph, typename Descriptor>
 129     class bundled_result
 130     {
 131       typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
 132       typedef typename mpl::if_c<(is_same<Descriptor, Vertex>::value),
 133                                  vertex_bundle_type<Graph>,
 134                                  edge_bundle_type<Graph> >::type bundler;
 135
 136     public:
 137       typedef typename bundler::type type;
 138     };
 139   } } // end namespace graph::detail
 140 } // namespace boost
 141
 142 // Since pair is in namespace std, Koenig lookup will find source and
 143 // target if they are also defined in namespace std.  This is illegal,
 144 // but the alternative is to put source and target in the global
 145 // namespace which causes name conflicts with other libraries (like
 146 // SUIF).
 147 namespace std {
 148
 149   /* Some helper functions for dealing with pairs as edges */
 150   template <class T, class G>
 151   T source(pair<T,T> p, const G&) { return p.first; }
 152
 153   template <class T, class G>
 154   T target(pair<T,T> p, const G&) { return p.second; }
 155
 156 }
 157
 158 #if defined(__GNUC__) && defined(__SGI_STL_PORT)
 159 // For some reason g++ with STLport does not see the above definition
 160 // of source() and target() unless we bring them into the boost
 161 // namespace.
 162 namespace boost {
 163   using std::source;
 164   using std::target;
 165 }
 166 #endif
 167
 168 #endif // BOOST_GRAPH_TRAITS_HPP