epoc32/include/stdapis/boost/graph/edge_list.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/edge_list.hpp	Tue Mar 16 16:12:26 2010 +0000
     1.3 @@ -0,0 +1,303 @@
     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 +
    1.14 +#ifndef BOOST_GRAPH_EDGE_LIST_HPP
    1.15 +#define BOOST_GRAPH_EDGE_LIST_HPP
    1.16 +
    1.17 +#include <iterator>
    1.18 +#include <boost/config.hpp>
    1.19 +#include <boost/pending/ct_if.hpp>
    1.20 +#include <boost/pending/integer_range.hpp>
    1.21 +#include <boost/graph/graph_traits.hpp>
    1.22 +#include <boost/graph/properties.hpp>
    1.23 +
    1.24 +namespace boost {
    1.25 +
    1.26 +  //
    1.27 +  // The edge_list class is an EdgeListGraph module that is constructed
    1.28 +  // from a pair of iterators whose value type is a pair of vertex
    1.29 +  // descriptors.
    1.30 +  //
    1.31 +  // For example:
    1.32 +  //
    1.33 +  //  typedef std::pair<int,int> E;
    1.34 +  //  list<E> elist;
    1.35 +  //  ...
    1.36 +  //  typedef edge_list<list<E>::iterator> Graph;
    1.37 +  //  Graph g(elist.begin(), elist.end());
    1.38 +  //
    1.39 +  // If the iterators are random access, then Graph::edge_descriptor
    1.40 +  // is of Integral type, otherwise it is a struct, though it is
    1.41 +  // convertible to an Integral type.
    1.42 +  // 
    1.43 +
    1.44 +  struct edge_list_tag { };
    1.45 +
    1.46 +  // The implementation class for edge_list.
    1.47 +  template <class G, class EdgeIter, class T, class D>
    1.48 +  class edge_list_impl
    1.49 +  {
    1.50 +  public:
    1.51 +    typedef D edge_id;
    1.52 +    typedef T Vpair;
    1.53 +    typedef typename Vpair::first_type V;
    1.54 +    typedef V vertex_descriptor;
    1.55 +    typedef edge_list_tag graph_tag;
    1.56 +    typedef void edge_property_type;
    1.57 +
    1.58 +    struct edge_descriptor
    1.59 +    {
    1.60 +      edge_descriptor() { }
    1.61 +      edge_descriptor(EdgeIter p, edge_id id) : _ptr(p), _id(id) { }
    1.62 +      operator edge_id() { return _id; }
    1.63 +      EdgeIter _ptr;
    1.64 +      edge_id _id;
    1.65 +    };
    1.66 +    typedef edge_descriptor E;
    1.67 +
    1.68 +    struct edge_iterator
    1.69 +    {
    1.70 +      typedef edge_iterator self;
    1.71 +      typedef E value_type;
    1.72 +      typedef E& reference;
    1.73 +      typedef E* pointer;
    1.74 +      typedef std::ptrdiff_t difference_type;
    1.75 +      typedef std::input_iterator_tag iterator_category;
    1.76 +      edge_iterator() { }
    1.77 +      edge_iterator(EdgeIter iter) : _iter(iter), _i(0) { }
    1.78 +      E operator*() { return E(_iter, _i); }
    1.79 +      self& operator++() { ++_iter; ++_i; return *this; }
    1.80 +      self operator++(int) { self t = *this; ++(*this); return t; }
    1.81 +      bool operator==(const self& x) { return _iter == x._iter; }
    1.82 +      bool operator!=(const self& x) { return _iter != x._iter; }
    1.83 +      EdgeIter _iter;
    1.84 +      edge_id _i;
    1.85 +    };
    1.86 +    typedef void out_edge_iterator;
    1.87 +    typedef void in_edge_iterator;
    1.88 +    typedef void adjacency_iterator;
    1.89 +    typedef void vertex_iterator;
    1.90 +  };
    1.91 +
    1.92 +  template <class G, class EI, class T, class D>
    1.93 +  std::pair<typename edge_list_impl<G,EI,T,D>::edge_iterator,
    1.94 +            typename edge_list_impl<G,EI,T,D>::edge_iterator>
    1.95 +  edges(const edge_list_impl<G,EI,T,D>& g_) {
    1.96 +    const G& g = static_cast<const G&>(g_);
    1.97 +    typedef typename edge_list_impl<G,EI,T,D>::edge_iterator edge_iterator;
    1.98 +    return std::make_pair(edge_iterator(g._first), edge_iterator(g._last));
    1.99 +  }
   1.100 +  template <class G, class EI, class T, class D>
   1.101 +  typename edge_list_impl<G,EI,T,D>::vertex_descriptor
   1.102 +  source(typename edge_list_impl<G,EI,T,D>::edge_descriptor e,
   1.103 +         const edge_list_impl<G,EI,T,D>&) {
   1.104 +    return (*e._ptr).first;
   1.105 +  }
   1.106 +  template <class G, class EI, class T, class D>
   1.107 +  typename edge_list_impl<G,EI,T,D>::vertex_descriptor
   1.108 +  target(typename edge_list_impl<G,EI,T,D>::edge_descriptor e,
   1.109 +           const edge_list_impl<G,EI,T,D>&) {
   1.110 +    return (*e._ptr).second;
   1.111 +  }
   1.112 +
   1.113 +  template <class D, class E>
   1.114 +  class el_edge_property_map
   1.115 +    : public put_get_helper<D, el_edge_property_map<D,E> >{
   1.116 +  public:
   1.117 +    typedef E key_type;
   1.118 +    typedef D value_type;
   1.119 +    typedef D reference;
   1.120 +    typedef readable_property_map_tag category;
   1.121 +
   1.122 +    value_type operator[](key_type e) const {
   1.123 +      return e._i;
   1.124 +    }
   1.125 +  };
   1.126 +  struct edge_list_edge_property_selector {
   1.127 +    template <class Graph, class Property, class Tag>
   1.128 +    struct bind_ {
   1.129 +      typedef el_edge_property_map<typename Graph::edge_id,
   1.130 +          typename Graph::edge_descriptor> type;
   1.131 +      typedef type const_type;
   1.132 +    };
   1.133 +  };
   1.134 +  template <>  
   1.135 +  struct edge_property_selector<edge_list_tag> {
   1.136 +    typedef edge_list_edge_property_selector type;
   1.137 +  };
   1.138 +
   1.139 +  template <class G, class EI, class T, class D>
   1.140 +  typename property_map< edge_list_impl<G,EI,T,D>, edge_index_t>::type
   1.141 +  get(edge_index_t, const edge_list_impl<G,EI,T,D>&) {
   1.142 +    typedef typename property_map< edge_list_impl<G,EI,T,D>, 
   1.143 +      edge_index_t>::type EdgeIndexMap;
   1.144 +    return EdgeIndexMap();
   1.145 +  }
   1.146 +
   1.147 +  template <class G, class EI, class T, class D>
   1.148 +  inline D
   1.149 +  get(edge_index_t, const edge_list_impl<G,EI,T,D>&,
   1.150 +      typename edge_list_impl<G,EI,T,D>::edge_descriptor e) {
   1.151 +    return e._i;
   1.152 +  }
   1.153 +
   1.154 +  // A specialized implementation for when the iterators are random access.
   1.155 +
   1.156 +  struct edge_list_ra_tag { };
   1.157 +
   1.158 +  template <class G, class EdgeIter, class T, class D>
   1.159 +  class edge_list_impl_ra
   1.160 +  {
   1.161 +  public:
   1.162 +    typedef D edge_id;
   1.163 +    typedef T Vpair;
   1.164 +    typedef typename Vpair::first_type V;
   1.165 +    typedef edge_list_ra_tag graph_tag;
   1.166 +    typedef void edge_property_type;
   1.167 +
   1.168 +    typedef edge_id edge_descriptor;
   1.169 +    typedef V vertex_descriptor;
   1.170 +    typedef typename boost::integer_range<edge_id>::iterator edge_iterator;
   1.171 +    typedef void out_edge_iterator;
   1.172 +    typedef void in_edge_iterator;
   1.173 +    typedef void adjacency_iterator;
   1.174 +    typedef void vertex_iterator;
   1.175 +  };
   1.176 +
   1.177 +  template <class G, class EI, class T, class D>
   1.178 +  std::pair<typename edge_list_impl_ra<G,EI,T,D>::edge_iterator,
   1.179 +            typename edge_list_impl_ra<G,EI,T,D>::edge_iterator>
   1.180 +  edges(const edge_list_impl_ra<G,EI,T,D>& g_)
   1.181 +  {
   1.182 +    const G& g = static_cast<const G&>(g_);
   1.183 +    typedef typename edge_list_impl_ra<G,EI,T,D>::edge_iterator edge_iterator;
   1.184 +    return std::make_pair(edge_iterator(0), edge_iterator(g._last - g._first));
   1.185 +  }    
   1.186 +  template <class G, class EI, class T, class D>
   1.187 +  typename edge_list_impl_ra<G,EI,T,D>::vertex_descriptor
   1.188 +  source(typename edge_list_impl_ra<G,EI,T,D>::edge_descriptor e,
   1.189 +         const edge_list_impl_ra<G,EI,T,D>& g_)
   1.190 +  {
   1.191 +    const G& g = static_cast<const G&>(g_);
   1.192 +    return g._first[e].first;
   1.193 +  }
   1.194 +  template <class G, class EI, class T, class D>
   1.195 +  typename edge_list_impl_ra<G,EI,T,D>::vertex_descriptor
   1.196 +  target(typename edge_list_impl_ra<G,EI,T,D>::edge_descriptor  e,
   1.197 +         const edge_list_impl_ra<G,EI,T,D>& g_)
   1.198 +  {
   1.199 +    const G& g = static_cast<const G&>(g_);
   1.200 +    return g._first[e].second;
   1.201 +  }
   1.202 +  template <class E>
   1.203 +  class el_ra_edge_property_map
   1.204 +    : public put_get_helper<E, el_ra_edge_property_map<E> >{
   1.205 +  public:
   1.206 +    typedef E key_type;
   1.207 +    typedef E value_type;
   1.208 +    typedef E reference;
   1.209 +    typedef readable_property_map_tag category;
   1.210 +
   1.211 +    value_type operator[](key_type e) const {
   1.212 +      return e;
   1.213 +    }
   1.214 +  };
   1.215 +  struct edge_list_ra_edge_property_selector {
   1.216 +    template <class Graph, class Property, class Tag>
   1.217 +    struct bind_ {
   1.218 +      typedef el_ra_edge_property_map<typename Graph::edge_descriptor> type;
   1.219 +      typedef type const_type;
   1.220 +    };
   1.221 +  };
   1.222 +  template <>  
   1.223 +  struct edge_property_selector<edge_list_ra_tag> {
   1.224 +    typedef edge_list_ra_edge_property_selector type;
   1.225 +  };
   1.226 +  template <class G, class EI, class T, class D>
   1.227 +  inline 
   1.228 +  typename property_map< edge_list_impl_ra<G,EI,T,D>, edge_index_t>::type
   1.229 +  get(edge_index_t, const edge_list_impl_ra<G,EI,T,D>&) {
   1.230 +    typedef typename property_map< edge_list_impl_ra<G,EI,T,D>, 
   1.231 +      edge_index_t>::type EdgeIndexMap;
   1.232 +    return EdgeIndexMap();
   1.233 +  }
   1.234 +
   1.235 +  template <class G, class EI, class T, class D>
   1.236 +  inline D
   1.237 +  get(edge_index_t, const edge_list_impl_ra<G,EI,T,D>&, 
   1.238 +      typename edge_list_impl_ra<G,EI,T,D>::edge_descriptor e) {
   1.239 +    return e;
   1.240 +  }
   1.241 +
   1.242 +
   1.243 +  // Some helper classes for determining if the iterators are random access
   1.244 +  template <class Cat>
   1.245 +  struct is_random {
   1.246 +    enum { RET = false }; 
   1.247 +    typedef false_type type; 
   1.248 +  };
   1.249 +  template <>
   1.250 +  struct is_random<std::random_access_iterator_tag> { 
   1.251 +    enum { RET = true }; typedef true_type type; 
   1.252 +  };
   1.253 +
   1.254 +  // The edge_list class conditionally inherits from one of the
   1.255 +  // above two classes.
   1.256 +
   1.257 +  template <class EdgeIter, 
   1.258 +#if !defined BOOST_NO_STD_ITERATOR_TRAITS
   1.259 +            class T = typename std::iterator_traits<EdgeIter>::value_type,
   1.260 +            class D = typename std::iterator_traits<EdgeIter>::difference_type,
   1.261 +            class Cat = typename std::iterator_traits<EdgeIter>::iterator_category>
   1.262 +#else
   1.263 +            class T,
   1.264 +            class D, 
   1.265 +            class Cat>
   1.266 +#endif
   1.267 +  class edge_list
   1.268 +    : public ct_if_t< typename is_random<Cat>::type,
   1.269 +                    edge_list_impl_ra< edge_list<EdgeIter,T,D,Cat>, EdgeIter,T,D>,
   1.270 +                    edge_list_impl< edge_list<EdgeIter,T,D,Cat>, EdgeIter,T,D> 
   1.271 +             >::type
   1.272 +  {
   1.273 +  public:
   1.274 +    typedef directed_tag directed_category;
   1.275 +    typedef allow_parallel_edge_tag edge_parallel_category;
   1.276 +    typedef edge_list_graph_tag traversal_category;
   1.277 +    typedef std::size_t edges_size_type;
   1.278 +    typedef std::size_t vertices_size_type;
   1.279 +    typedef std::size_t degree_size_type;
   1.280 +    edge_list(EdgeIter first, EdgeIter last) : _first(first), _last(last) { 
   1.281 +      m_num_edges = std::distance(first, last);
   1.282 +    }
   1.283 +    edge_list(EdgeIter first, EdgeIter last, edges_size_type E)
   1.284 +      : _first(first), _last(last), m_num_edges(E) { }  
   1.285 +    
   1.286 +    EdgeIter _first, _last;
   1.287 +    edges_size_type m_num_edges;
   1.288 +  };
   1.289 +
   1.290 +  template <class EdgeIter, class T, class D, class Cat>
   1.291 +  std::size_t num_edges(const edge_list<EdgeIter, T, D, Cat>& el) {
   1.292 +    return el.m_num_edges;
   1.293 +  }
   1.294 +
   1.295 +#ifndef BOOST_NO_STD_ITERATOR_TRAITS
   1.296 +  template <class EdgeIter>
   1.297 +  inline edge_list<EdgeIter>
   1.298 +  make_edge_list(EdgeIter first, EdgeIter last)
   1.299 +  {
   1.300 +    return edge_list<EdgeIter>(first, last);
   1.301 +  }
   1.302 +#endif
   1.303 +  
   1.304 +} /* namespace boost */
   1.305 +
   1.306 +#endif /* BOOST_GRAPH_EDGE_LIST_HPP */