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 */