epoc32/include/stdapis/boost/graph/properties.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/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 */