epoc32/include/stdapis/boost/graph/graph_traits.hpp
branchSymbian2
changeset 2 2fe1408b6811
     1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/epoc32/include/stdapis/boost/graph/graph_traits.hpp	Tue Mar 16 16:12:26 2010 +0000
     1.3 @@ -0,0 +1,168 @@
     1.4 +//=======================================================================
     1.5 +// Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
     1.6 +// Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek
     1.7 +//
     1.8 +// Distributed under the Boost Software License, Version 1.0. (See
     1.9 +// accompanying file LICENSE_1_0.txt or copy at
    1.10 +// http://www.boost.org/LICENSE_1_0.txt)
    1.11 +//=======================================================================
    1.12 +
    1.13 +#ifndef BOOST_GRAPH_TRAITS_HPP
    1.14 +#define BOOST_GRAPH_TRAITS_HPP
    1.15 +
    1.16 +#include <boost/config.hpp>
    1.17 +#include <iterator>
    1.18 +#include <boost/tuple/tuple.hpp>
    1.19 +#include <boost/mpl/if.hpp>
    1.20 +#include <boost/type_traits/is_same.hpp>
    1.21 +#include <boost/iterator/iterator_categories.hpp>
    1.22 +#include <boost/iterator/iterator_adaptor.hpp>
    1.23 +#include <boost/detail/workaround.hpp>
    1.24 +
    1.25 +namespace boost {
    1.26 +
    1.27 +  template <typename G>
    1.28 +  struct graph_traits {
    1.29 +    typedef typename G::vertex_descriptor      vertex_descriptor;
    1.30 +    typedef typename G::edge_descriptor        edge_descriptor;
    1.31 +    typedef typename G::adjacency_iterator     adjacency_iterator;
    1.32 +    typedef typename G::out_edge_iterator      out_edge_iterator;
    1.33 +    typedef typename G::in_edge_iterator       in_edge_iterator;
    1.34 +    typedef typename G::vertex_iterator        vertex_iterator;
    1.35 +    typedef typename G::edge_iterator          edge_iterator;
    1.36 +
    1.37 +    typedef typename G::directed_category      directed_category;
    1.38 +    typedef typename G::edge_parallel_category edge_parallel_category;
    1.39 +    typedef typename G::traversal_category     traversal_category;
    1.40 +
    1.41 +    typedef typename G::vertices_size_type     vertices_size_type;
    1.42 +    typedef typename G::edges_size_type        edges_size_type;
    1.43 +    typedef typename G::degree_size_type       degree_size_type;
    1.44 +
    1.45 +    static inline vertex_descriptor null_vertex();
    1.46 +  };
    1.47 +
    1.48 +  template <typename G>
    1.49 +  inline typename graph_traits<G>::vertex_descriptor
    1.50 +  graph_traits<G>::null_vertex()
    1.51 +  {
    1.52 +    return G::null_vertex();
    1.53 +  }
    1.54 +
    1.55 +  // directed_category tags
    1.56 +  struct directed_tag { };
    1.57 +  struct undirected_tag { };
    1.58 +  struct bidirectional_tag : public directed_tag { };
    1.59 +
    1.60 +  namespace detail {
    1.61 +    inline bool is_directed(directed_tag) { return true; }
    1.62 +    inline bool is_directed(undirected_tag) { return false; }
    1.63 +  }
    1.64 +
    1.65 +  template <typename Graph>
    1.66 +  bool is_directed(const Graph&) { 
    1.67 +    typedef typename graph_traits<Graph>::directed_category Cat;
    1.68 +    return detail::is_directed(Cat());
    1.69 +  }
    1.70 +  template <typename Graph>
    1.71 +  bool is_undirected(const Graph& g) { 
    1.72 +    return ! is_directed(g);
    1.73 +  }
    1.74 +
    1.75 +  // edge_parallel_category tags
    1.76 +  struct allow_parallel_edge_tag {};
    1.77 +  struct disallow_parallel_edge_tag {};
    1.78 +
    1.79 +  namespace detail {
    1.80 +    inline bool allows_parallel(allow_parallel_edge_tag) { return true; }
    1.81 +    inline bool allows_parallel(disallow_parallel_edge_tag) { return false; }
    1.82 +  }
    1.83 +
    1.84 +  template <typename Graph>
    1.85 +  bool allows_parallel_edges(const Graph&) { 
    1.86 +    typedef typename graph_traits<Graph>::edge_parallel_category Cat;
    1.87 +    return detail::allows_parallel(Cat());
    1.88 +  }
    1.89 +
    1.90 +  // traversal_category tags
    1.91 +  struct incidence_graph_tag { };
    1.92 +  struct adjacency_graph_tag { };
    1.93 +  struct bidirectional_graph_tag : 
    1.94 +    public virtual incidence_graph_tag { };
    1.95 +  struct vertex_list_graph_tag { };
    1.96 +  struct edge_list_graph_tag { };
    1.97 +  struct adjacency_matrix_tag { };
    1.98 +
    1.99 +  //?? not the right place ?? Lee
   1.100 +  typedef boost::forward_traversal_tag multi_pass_input_iterator_tag;
   1.101 +
   1.102 +  template <typename G>
   1.103 +  struct edge_property_type {
   1.104 +    typedef typename G::edge_property_type type;
   1.105 +  };
   1.106 +  template <typename G>
   1.107 +  struct vertex_property_type {
   1.108 +    typedef typename G::vertex_property_type type;
   1.109 +  };
   1.110 +  template <typename G>
   1.111 +  struct graph_property_type {
   1.112 +    typedef typename G::graph_property_type type;
   1.113 +  };
   1.114 +
   1.115 +  struct no_vertex_bundle {};
   1.116 +  struct no_edge_bundle {};
   1.117 +
   1.118 +  template<typename G>
   1.119 +  struct vertex_bundle_type
   1.120 +  {
   1.121 +    typedef typename G::vertex_bundled type;
   1.122 +  };
   1.123 +
   1.124 +  template<typename G>
   1.125 +  struct edge_bundle_type
   1.126 +  {
   1.127 +    typedef typename G::edge_bundled type;
   1.128 +  };
   1.129 +
   1.130 +  namespace graph { namespace detail {
   1.131 +    template<typename Graph, typename Descriptor>
   1.132 +    class bundled_result
   1.133 +    {
   1.134 +      typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
   1.135 +      typedef typename mpl::if_c<(is_same<Descriptor, Vertex>::value),
   1.136 +                                 vertex_bundle_type<Graph>,
   1.137 +                                 edge_bundle_type<Graph> >::type bundler;
   1.138 +
   1.139 +    public:
   1.140 +      typedef typename bundler::type type;
   1.141 +    };
   1.142 +  } } // end namespace graph::detail
   1.143 +} // namespace boost
   1.144 +
   1.145 +// Since pair is in namespace std, Koenig lookup will find source and
   1.146 +// target if they are also defined in namespace std.  This is illegal,
   1.147 +// but the alternative is to put source and target in the global
   1.148 +// namespace which causes name conflicts with other libraries (like
   1.149 +// SUIF).
   1.150 +namespace std {
   1.151 +
   1.152 +  /* Some helper functions for dealing with pairs as edges */
   1.153 +  template <class T, class G>
   1.154 +  T source(pair<T,T> p, const G&) { return p.first; }
   1.155 +
   1.156 +  template <class T, class G>
   1.157 +  T target(pair<T,T> p, const G&) { return p.second; }
   1.158 +
   1.159 +}
   1.160 +
   1.161 +#if defined(__GNUC__) && defined(__SGI_STL_PORT)
   1.162 +// For some reason g++ with STLport does not see the above definition
   1.163 +// of source() and target() unless we bring them into the boost
   1.164 +// namespace.
   1.165 +namespace boost {
   1.166 +  using std::source;
   1.167 +  using std::target;
   1.168 +}
   1.169 +#endif
   1.170 +
   1.171 +#endif // BOOST_GRAPH_TRAITS_HPP