1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/epoc32/include/stdapis/boost/graph/properties.hpp Tue Mar 16 16:12:26 2010 +0000
1.3 @@ -0,0 +1,375 @@
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 +#ifndef BOOST_GRAPH_PROPERTIES_HPP
1.13 +#define BOOST_GRAPH_PROPERTIES_HPP
1.14 +
1.15 +#include <boost/config.hpp>
1.16 +#include <cassert>
1.17 +#include <boost/pending/property.hpp>
1.18 +#include <boost/property_map.hpp>
1.19 +#include <boost/graph/graph_traits.hpp>
1.20 +#include <boost/type_traits/is_convertible.hpp>
1.21 +
1.22 +namespace boost {
1.23 +
1.24 + enum default_color_type { white_color, gray_color, green_color, red_color, black_color };
1.25 +
1.26 + template <class ColorValue>
1.27 + struct color_traits {
1.28 + static default_color_type white() { return white_color; }
1.29 + static default_color_type gray() { return gray_color; }
1.30 + static default_color_type green() { return green_color; }
1.31 + static default_color_type red() { return red_color; }
1.32 + static default_color_type black() { return black_color; }
1.33 + };
1.34 +
1.35 + // These functions are now obsolete, replaced by color_traits.
1.36 + inline default_color_type white(default_color_type) { return white_color; }
1.37 + inline default_color_type gray(default_color_type) { return gray_color; }
1.38 + inline default_color_type green(default_color_type) { return green_color; }
1.39 + inline default_color_type red(default_color_type) { return red_color; }
1.40 + inline default_color_type black(default_color_type) { return black_color; }
1.41 +
1.42 +#ifdef BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
1.43 + template <>
1.44 + struct property_traits<default_color_type*> {
1.45 + typedef default_color_type value_type;
1.46 + typedef std::ptrdiff_t key_type;
1.47 + typedef default_color_type& reference;
1.48 + typedef lvalue_property_map_tag category;
1.49 + };
1.50 + // get/put already defined for T*
1.51 +#endif
1.52 +
1.53 + struct graph_property_tag { };
1.54 + struct vertex_property_tag { };
1.55 + struct edge_property_tag { };
1.56 +
1.57 +#ifdef BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
1.58 + // See examples/edge_property.cpp for how to use this.
1.59 +#define BOOST_INSTALL_PROPERTY(KIND, NAME) \
1.60 + template <> struct property_kind<KIND##_##NAME##_t> { \
1.61 + typedef KIND##_property_tag type; \
1.62 + }
1.63 +#else
1.64 +#define BOOST_INSTALL_PROPERTY(KIND, NAME) \
1.65 + template <> struct property_kind<KIND##_##NAME##_t> { \
1.66 + typedef KIND##_property_tag type; \
1.67 + }
1.68 +#endif
1.69 +
1.70 +#define BOOST_DEF_PROPERTY(KIND, NAME) \
1.71 + enum KIND##_##NAME##_t { KIND##_##NAME }; \
1.72 + BOOST_INSTALL_PROPERTY(KIND, NAME)
1.73 +
1.74 + BOOST_DEF_PROPERTY(vertex, all);
1.75 + BOOST_DEF_PROPERTY(edge, all);
1.76 + BOOST_DEF_PROPERTY(graph, all);
1.77 + BOOST_DEF_PROPERTY(vertex, index);
1.78 + BOOST_DEF_PROPERTY(vertex, index1);
1.79 + BOOST_DEF_PROPERTY(vertex, index2);
1.80 + BOOST_DEF_PROPERTY(vertex, root);
1.81 + BOOST_DEF_PROPERTY(edge, index);
1.82 + BOOST_DEF_PROPERTY(edge, name);
1.83 + BOOST_DEF_PROPERTY(edge, weight);
1.84 + BOOST_DEF_PROPERTY(edge, weight2);
1.85 + BOOST_DEF_PROPERTY(edge, color);
1.86 + BOOST_DEF_PROPERTY(vertex, name);
1.87 + BOOST_DEF_PROPERTY(graph, name);
1.88 + BOOST_DEF_PROPERTY(vertex, distance);
1.89 + BOOST_DEF_PROPERTY(vertex, color);
1.90 + BOOST_DEF_PROPERTY(vertex, degree);
1.91 + BOOST_DEF_PROPERTY(vertex, in_degree);
1.92 + BOOST_DEF_PROPERTY(vertex, out_degree);
1.93 + BOOST_DEF_PROPERTY(vertex, current_degree);
1.94 + BOOST_DEF_PROPERTY(vertex, priority);
1.95 + BOOST_DEF_PROPERTY(vertex, discover_time);
1.96 + BOOST_DEF_PROPERTY(vertex, finish_time);
1.97 + BOOST_DEF_PROPERTY(vertex, predecessor);
1.98 + BOOST_DEF_PROPERTY(vertex, rank);
1.99 + BOOST_DEF_PROPERTY(vertex, centrality);
1.100 + BOOST_DEF_PROPERTY(vertex, lowpoint);
1.101 + BOOST_DEF_PROPERTY(edge, reverse);
1.102 + BOOST_DEF_PROPERTY(edge, capacity);
1.103 + BOOST_DEF_PROPERTY(edge, residual_capacity);
1.104 + BOOST_DEF_PROPERTY(edge, centrality);
1.105 + BOOST_DEF_PROPERTY(graph, visitor);
1.106 +
1.107 + // These tags are used for property bundles
1.108 + BOOST_DEF_PROPERTY(vertex, bundle);
1.109 + BOOST_DEF_PROPERTY(edge, bundle);
1.110 +
1.111 +#undef BOOST_DEF_PROPERTY
1.112 +
1.113 + namespace detail {
1.114 +
1.115 + struct dummy_edge_property_selector {
1.116 + template <class Graph, class Property, class Tag>
1.117 + struct bind_ {
1.118 + typedef identity_property_map type;
1.119 + typedef identity_property_map const_type;
1.120 + };
1.121 + };
1.122 + struct dummy_vertex_property_selector {
1.123 + template <class Graph, class Property, class Tag>
1.124 + struct bind_ {
1.125 + typedef identity_property_map type;
1.126 + typedef identity_property_map const_type;
1.127 + };
1.128 + };
1.129 +
1.130 + } // namespace detail
1.131 +
1.132 + // Graph classes can either partially specialize property_map
1.133 + // or they can specialize these two selector classes.
1.134 + template <class GraphTag>
1.135 + struct edge_property_selector {
1.136 + typedef detail::dummy_edge_property_selector type;
1.137 + };
1.138 +
1.139 + template <class GraphTag>
1.140 + struct vertex_property_selector {
1.141 + typedef detail::dummy_vertex_property_selector type;
1.142 + };
1.143 +
1.144 + namespace detail {
1.145 +
1.146 + template <class Graph, class PropertyTag>
1.147 + struct edge_property_map {
1.148 + typedef typename Graph::edge_property_type Property;
1.149 + typedef typename Graph::graph_tag graph_tag;
1.150 + typedef typename edge_property_selector<graph_tag>::type Selector;
1.151 + typedef typename Selector::template bind_<Graph,Property,PropertyTag>
1.152 + Bind;
1.153 + typedef typename Bind::type type;
1.154 + typedef typename Bind::const_type const_type;
1.155 + };
1.156 + template <class Graph, class PropertyTag>
1.157 + class vertex_property_map {
1.158 + typedef typename Graph::vertex_property_type Property;
1.159 + typedef typename Graph::graph_tag graph_tag;
1.160 + typedef typename vertex_property_selector<graph_tag>::type Selector;
1.161 + typedef typename Selector::template bind_<Graph,Property,PropertyTag>
1.162 + Bind;
1.163 + public:
1.164 + typedef typename Bind::type type;
1.165 + typedef typename Bind::const_type const_type;
1.166 + };
1.167 +
1.168 + // This selects the kind of property map, whether is maps from
1.169 + // edges or from vertices.
1.170 + //
1.171 + // It is overly complicated because it's a workaround for
1.172 + // partial specialization.
1.173 + struct choose_vertex_property_map {
1.174 + template <class Graph, class Property>
1.175 + struct bind_ {
1.176 + typedef vertex_property_map<Graph, Property> type;
1.177 + };
1.178 + };
1.179 + struct choose_edge_property_map {
1.180 + template <class Graph, class Property>
1.181 + struct bind_ {
1.182 + typedef edge_property_map<Graph, Property> type;
1.183 + };
1.184 + };
1.185 + template <class Kind>
1.186 + struct property_map_kind_selector {
1.187 + // VC++ gets confused if this isn't defined, even though
1.188 + // this never gets used.
1.189 + typedef choose_vertex_property_map type;
1.190 + };
1.191 + template <> struct property_map_kind_selector<vertex_property_tag> {
1.192 + typedef choose_vertex_property_map type;
1.193 + };
1.194 + template <> struct property_map_kind_selector<edge_property_tag> {
1.195 + typedef choose_edge_property_map type;
1.196 + };
1.197 + } // namespace detail
1.198 +
1.199 + template <class Graph, class Property>
1.200 + struct property_map {
1.201 + private:
1.202 + typedef typename property_kind<Property>::type Kind;
1.203 + typedef typename detail::property_map_kind_selector<Kind>::type Selector;
1.204 + typedef typename Selector::template bind_<Graph, Property> Bind;
1.205 + typedef typename Bind::type Map;
1.206 + public:
1.207 + typedef typename Map::type type;
1.208 + typedef typename Map::const_type const_type;
1.209 + };
1.210 +
1.211 + // shortcut for accessing the value type of the property map
1.212 + template <class Graph, class Property>
1.213 + class property_map_value {
1.214 + typedef typename property_map<Graph, Property>::const_type PMap;
1.215 + public:
1.216 + typedef typename property_traits<PMap>::value_type type;
1.217 + };
1.218 +
1.219 + template <class Graph, class Property>
1.220 + class graph_property {
1.221 + public:
1.222 + typedef typename property_value<typename Graph::graph_property_type,
1.223 + Property>::type type;
1.224 + };
1.225 +
1.226 + template <class Graph>
1.227 + class vertex_property {
1.228 + public:
1.229 + typedef typename Graph::vertex_property_type type;
1.230 + };
1.231 + template <class Graph>
1.232 + class edge_property {
1.233 + public:
1.234 + typedef typename Graph::edge_property_type type;
1.235 + };
1.236 +
1.237 + template <typename Graph>
1.238 + class degree_property_map
1.239 + : public put_get_helper<typename graph_traits<Graph>::degree_size_type,
1.240 + degree_property_map<Graph> >
1.241 + {
1.242 + public:
1.243 + typedef typename graph_traits<Graph>::vertex_descriptor key_type;
1.244 + typedef typename graph_traits<Graph>::degree_size_type value_type;
1.245 + typedef value_type reference;
1.246 + typedef readable_property_map_tag category;
1.247 + degree_property_map(const Graph& g) : m_g(g) { }
1.248 + value_type operator[](const key_type& v) const {
1.249 + return degree(v, m_g);
1.250 + }
1.251 + private:
1.252 + const Graph& m_g;
1.253 + };
1.254 + template <typename Graph>
1.255 + inline degree_property_map<Graph>
1.256 + make_degree_map(const Graph& g) {
1.257 + return degree_property_map<Graph>(g);
1.258 + }
1.259 +
1.260 + //========================================================================
1.261 + // Iterator Property Map Generating Functions contributed by
1.262 + // Kevin Vanhorn. (see also the property map generating functions
1.263 + // in boost/property_map.hpp)
1.264 +
1.265 +#if !defined(BOOST_NO_STD_ITERATOR_TRAITS)
1.266 + // A helper function for creating a vertex property map out of a
1.267 + // random access iterator and the internal vertex index map from a
1.268 + // graph.
1.269 + template <class PropertyGraph, class RandomAccessIterator>
1.270 + inline
1.271 + iterator_property_map<
1.272 + RandomAccessIterator,
1.273 + typename property_map<PropertyGraph, vertex_index_t>::type,
1.274 + typename std::iterator_traits<RandomAccessIterator>::value_type,
1.275 + typename std::iterator_traits<RandomAccessIterator>::reference
1.276 + >
1.277 + make_iterator_vertex_map(RandomAccessIterator iter, const PropertyGraph& g)
1.278 + {
1.279 + return make_iterator_property_map(iter, get(vertex_index, g));
1.280 + }
1.281 +
1.282 + // Use this next function when vertex_descriptor is known to be an
1.283 + // integer type, with values ranging from 0 to num_vertices(g).
1.284 + //
1.285 + template <class RandomAccessIterator>
1.286 + inline
1.287 + iterator_property_map<
1.288 + RandomAccessIterator,
1.289 + identity_property_map,
1.290 + typename std::iterator_traits<RandomAccessIterator>::value_type,
1.291 + typename std::iterator_traits<RandomAccessIterator>::reference
1.292 + >
1.293 + make_iterator_vertex_map(RandomAccessIterator iter)
1.294 + {
1.295 + return make_iterator_property_map(iter, identity_property_map());
1.296 + }
1.297 +#endif
1.298 +
1.299 + template <class PropertyGraph, class RandomAccessContainer>
1.300 + inline
1.301 + iterator_property_map<
1.302 + typename RandomAccessContainer::iterator,
1.303 + typename property_map<PropertyGraph, vertex_index_t>::type,
1.304 + typename RandomAccessContainer::value_type,
1.305 + typename RandomAccessContainer::reference
1.306 + >
1.307 + make_container_vertex_map(RandomAccessContainer& c, const PropertyGraph& g)
1.308 + {
1.309 + assert(c.size() >= num_vertices(g));
1.310 + return make_iterator_vertex_map(c.begin(), g);
1.311 + }
1.312 +
1.313 + template <class RandomAccessContainer> inline
1.314 + iterator_property_map<
1.315 + typename RandomAccessContainer::iterator,
1.316 + identity_property_map,
1.317 + typename RandomAccessContainer::value_type,
1.318 + typename RandomAccessContainer::reference
1.319 + >
1.320 + make_container_vertex_map(RandomAccessContainer& c)
1.321 + {
1.322 + return make_iterator_vertex_map(c.begin());
1.323 + }
1.324 +
1.325 +#if defined (BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION)
1.326 +# define BOOST_GRAPH_NO_BUNDLED_PROPERTIES
1.327 +#endif
1.328 +
1.329 +#ifndef BOOST_GRAPH_NO_BUNDLED_PROPERTIES
1.330 + template<typename Graph, typename Descriptor, typename Bundle, typename T>
1.331 + struct bundle_property_map
1.332 + : put_get_helper<T&, bundle_property_map<Graph, Descriptor, Bundle, T> >
1.333 + {
1.334 + typedef Descriptor key_type;
1.335 + typedef T value_type;
1.336 + typedef T& reference;
1.337 + typedef lvalue_property_map_tag category;
1.338 +
1.339 + bundle_property_map() { }
1.340 + bundle_property_map(Graph* g_, T Bundle::* pm_) : g(g_), pm(pm_) {}
1.341 +
1.342 + reference operator[](key_type k) const { return (*g)[k].*pm; }
1.343 + private:
1.344 + Graph* g;
1.345 + T Bundle::* pm;
1.346 + };
1.347 +
1.348 + namespace detail {
1.349 + template<typename VertexBundle, typename EdgeBundle, typename Bundle>
1.350 + struct is_vertex_bundle : is_convertible<VertexBundle*, Bundle*> {};
1.351 + }
1.352 +
1.353 + template <typename Graph, typename T, typename Bundle>
1.354 + struct property_map<Graph, T Bundle::*>
1.355 + {
1.356 + private:
1.357 + typedef graph_traits<Graph> traits;
1.358 + typedef typename Graph::vertex_bundled vertex_bundled;
1.359 + typedef typename Graph::edge_bundled edge_bundled;
1.360 + typedef typename ct_if<(detail::is_vertex_bundle<vertex_bundled, edge_bundled, Bundle>::value),
1.361 + typename traits::vertex_descriptor,
1.362 + typename traits::edge_descriptor>::type
1.363 + descriptor;
1.364 + typedef typename ct_if<(detail::is_vertex_bundle<vertex_bundled, edge_bundled, Bundle>::value),
1.365 + vertex_bundled,
1.366 + edge_bundled>::type
1.367 + actual_bundle;
1.368 +
1.369 + public:
1.370 + typedef bundle_property_map<Graph, descriptor, actual_bundle, T> type;
1.371 + typedef bundle_property_map<const Graph, descriptor, actual_bundle, const T>
1.372 + const_type;
1.373 + };
1.374 +#endif
1.375 +
1.376 +} // namespace boost
1.377 +
1.378 +#endif /* BOOST_GRAPH_PROPERTIES_HPPA */