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