1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/epoc32/include/stdapis/boost/graph/vector_as_graph.hpp Tue Mar 16 16:12:26 2010 +0000
1.3 @@ -0,0 +1,332 @@
1.4 +//=======================================================================
1.5 +// Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
1.6 +// Copyright 2006 The Trustees of Indiana University.
1.7 +// Copyright (C) 2001 Vladimir Prus <ghost@cs.msu.su>
1.8 +// Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek, Douglas Gregor
1.9 +//
1.10 +// Distributed under the Boost Software License, Version 1.0. (See
1.11 +// accompanying file LICENSE_1_0.txt or copy at
1.12 +// http://www.boost.org/LICENSE_1_0.txt)
1.13 +//=======================================================================
1.14 +
1.15 +// The mutating functions (add_edge, etc.) were added by Vladimir Prus.
1.16 +
1.17 +#ifndef BOOST_VECTOR_AS_GRAPH_HPP
1.18 +#define BOOST_VECTOR_AS_GRAPH_HPP
1.19 +
1.20 +#include <cassert>
1.21 +#include <utility>
1.22 +#include <vector>
1.23 +#include <cstddef>
1.24 +#include <boost/iterator.hpp>
1.25 +#include <boost/graph/graph_traits.hpp>
1.26 +#include <boost/pending/integer_range.hpp>
1.27 +#include <boost/property_map.hpp>
1.28 +#include <boost/graph/properties.hpp>
1.29 +#include <algorithm>
1.30 +
1.31 +/*
1.32 + This module implements the VertexListGraph concept using a
1.33 + std::vector as the "back-bone" of the graph (the vector *is* the
1.34 + graph object). The edge-lists type of the graph is templated, so the
1.35 + user can choose any STL container, so long as the value_type of the
1.36 + container is convertible to the size_type of the vector. For now any
1.37 + graph properties must be stored seperately.
1.38 +
1.39 + This module requires the C++ compiler to support partial
1.40 + specialization for the graph_traits class, so this is not portable
1.41 + to VC++.
1.42 +
1.43 +*/
1.44 +
1.45 +#ifdef BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
1.46 +#error The vector-as-graph module requires a compiler that supports partial specialization
1.47 +#endif
1.48 +
1.49 +
1.50 +namespace boost {
1.51 + namespace detail {
1.52 + template <class EdgeList> struct val_out_edge_ret;
1.53 + template <class EdgeList> struct val_out_edge_iter;
1.54 + template <class EdgeList> struct val_edge;
1.55 + }
1.56 +}
1.57 +
1.58 +#if !defined BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
1.59 +namespace boost {
1.60 +
1.61 + struct vector_as_graph_traversal_tag
1.62 + : public vertex_list_graph_tag,
1.63 + public adjacency_graph_tag,
1.64 + public incidence_graph_tag { };
1.65 +
1.66 + template <class EdgeList>
1.67 + struct graph_traits< std::vector<EdgeList> >
1.68 + {
1.69 + typedef typename EdgeList::value_type V;
1.70 + typedef V vertex_descriptor;
1.71 + typedef typename detail::val_edge<EdgeList>::type edge_descriptor;
1.72 + typedef typename EdgeList::const_iterator adjacency_iterator;
1.73 + typedef typename detail::val_out_edge_iter<EdgeList>::type
1.74 + out_edge_iterator;
1.75 + typedef void in_edge_iterator;
1.76 + typedef void edge_iterator;
1.77 + typedef typename integer_range<V>::iterator vertex_iterator;
1.78 + typedef directed_tag directed_category;
1.79 + typedef allow_parallel_edge_tag edge_parallel_category;
1.80 + typedef vector_as_graph_traversal_tag traversal_category;
1.81 + typedef typename std::vector<EdgeList>::size_type vertices_size_type;
1.82 + typedef void edges_size_type;
1.83 + typedef typename EdgeList::size_type degree_size_type;
1.84 + };
1.85 + template <class EdgeList>
1.86 + struct edge_property_type< std::vector<EdgeList> >
1.87 + {
1.88 + typedef void type;
1.89 + };
1.90 + template <class EdgeList>
1.91 + struct vertex_property_type< std::vector<EdgeList> >
1.92 + {
1.93 + typedef void type;
1.94 + };
1.95 + template <class EdgeList>
1.96 + struct graph_property_type< std::vector<EdgeList> >
1.97 + {
1.98 + typedef void type;
1.99 + };
1.100 +}
1.101 +#endif
1.102 +
1.103 +namespace boost {
1.104 +
1.105 + namespace detail {
1.106 +
1.107 + // "val" is short for Vector Adjacency List
1.108 +
1.109 + template <class EdgeList>
1.110 + struct val_edge
1.111 + {
1.112 + typedef typename EdgeList::value_type V;
1.113 + typedef std::pair<V,V> type;
1.114 + };
1.115 +
1.116 + // need rewrite this using boost::iterator_adaptor
1.117 + template <class V, class Iter>
1.118 + class val_out_edge_iterator
1.119 + : public boost::iterator<std::input_iterator_tag, std::pair<V,V>,
1.120 + std::ptrdiff_t, std::pair<V,V>*, const std::pair<V,V> >
1.121 + {
1.122 + typedef val_out_edge_iterator self;
1.123 + typedef std::pair<V,V> Edge;
1.124 + public:
1.125 + val_out_edge_iterator() { }
1.126 + val_out_edge_iterator(V s, Iter i) : _source(s), _iter(i) { }
1.127 + Edge operator*() const { return Edge(_source, *_iter); }
1.128 + self& operator++() { ++_iter; return *this; }
1.129 + self operator++(int) { self t = *this; ++_iter; return t; }
1.130 + bool operator==(const self& x) const { return _iter == x._iter; }
1.131 + bool operator!=(const self& x) const { return _iter != x._iter; }
1.132 + protected:
1.133 + V _source;
1.134 + Iter _iter;
1.135 + };
1.136 +
1.137 + template <class EdgeList>
1.138 + struct val_out_edge_iter
1.139 + {
1.140 + typedef typename EdgeList::value_type V;
1.141 + typedef typename EdgeList::const_iterator Iter;
1.142 + typedef val_out_edge_iterator<V,Iter> type;
1.143 + };
1.144 +
1.145 + template <class EdgeList>
1.146 + struct val_out_edge_ret
1.147 + {
1.148 + typedef typename val_out_edge_iter<EdgeList>::type IncIter;
1.149 + typedef std::pair<IncIter,IncIter> type;
1.150 + };
1.151 +
1.152 + } // namesapce detail
1.153 +
1.154 + template <class EdgeList, class Alloc>
1.155 + typename detail::val_out_edge_ret<EdgeList>::type
1.156 + out_edges(typename EdgeList::value_type v,
1.157 + const std::vector<EdgeList, Alloc>& g)
1.158 + {
1.159 + typedef typename detail::val_out_edge_iter<EdgeList>::type Iter;
1.160 + typedef typename detail::val_out_edge_ret<EdgeList>::type return_type;
1.161 + return return_type(Iter(v, g[v].begin()), Iter(v, g[v].end()));
1.162 + }
1.163 +
1.164 + template <class EdgeList, class Alloc>
1.165 + typename EdgeList::size_type
1.166 + out_degree(typename EdgeList::value_type v,
1.167 + const std::vector<EdgeList, Alloc>& g)
1.168 + {
1.169 + return g[v].size();
1.170 + }
1.171 +
1.172 + template <class EdgeList, class Alloc>
1.173 + std::pair<typename EdgeList::const_iterator,
1.174 + typename EdgeList::const_iterator>
1.175 + adjacent_vertices(typename EdgeList::value_type v,
1.176 + const std::vector<EdgeList, Alloc>& g)
1.177 + {
1.178 + return std::make_pair(g[v].begin(), g[v].end());
1.179 + }
1.180 +
1.181 + // source() and target() already provided for pairs in graph_traits.hpp
1.182 +
1.183 + template <class EdgeList, class Alloc>
1.184 + std::pair<typename boost::integer_range<typename EdgeList::value_type>
1.185 + ::iterator,
1.186 + typename boost::integer_range<typename EdgeList::value_type>
1.187 + ::iterator >
1.188 + vertices(const std::vector<EdgeList, Alloc>& v)
1.189 + {
1.190 + typedef typename boost::integer_range<typename EdgeList::value_type>
1.191 + ::iterator Iter;
1.192 + return std::make_pair(Iter(0), Iter(v.size()));
1.193 + }
1.194 +
1.195 + template <class EdgeList, class Alloc>
1.196 + typename std::vector<EdgeList, Alloc>::size_type
1.197 + num_vertices(const std::vector<EdgeList, Alloc>& v)
1.198 + {
1.199 + return v.size();
1.200 + }
1.201 +
1.202 + template<class EdgeList, class Allocator>
1.203 + typename std::pair<typename detail::val_edge<EdgeList>::type, bool>
1.204 + add_edge(typename EdgeList::value_type u, typename EdgeList::value_type v,
1.205 + std::vector<EdgeList, Allocator>& g)
1.206 + {
1.207 + typedef typename detail::val_edge<EdgeList>::type edge_type;
1.208 + g[u].insert(g[u].end(), v);
1.209 + return std::make_pair(edge_type(u, v), true);
1.210 + }
1.211 +
1.212 + template<class EdgeList, class Allocator>
1.213 + typename std::pair<typename detail::val_edge<EdgeList>::type, bool>
1.214 + edge(typename EdgeList::value_type u, typename EdgeList::value_type v,
1.215 + std::vector<EdgeList, Allocator>& g)
1.216 + {
1.217 + typedef typename detail::val_edge<EdgeList>::type edge_type;
1.218 + typename EdgeList::iterator i = g[u].begin(), end = g[u].end();
1.219 + for (; i != end; ++i)
1.220 + if (*i == v)
1.221 + return std::make_pair(edge_type(u, v), true);
1.222 + return std::make_pair(edge_type(), false);
1.223 + }
1.224 +
1.225 + template<class EdgeList, class Allocator>
1.226 + void
1.227 + remove_edge(typename EdgeList::value_type u, typename EdgeList::value_type v,
1.228 + std::vector<EdgeList, Allocator>& g)
1.229 + {
1.230 + typename EdgeList::iterator i = std::remove(g[u].begin(), g[u].end(), v);
1.231 + if (i != g[u].end())
1.232 + g[u].erase(i, g[u].end());
1.233 + }
1.234 +
1.235 + template<class EdgeList, class Allocator>
1.236 + void
1.237 + remove_edge(typename detail::val_edge<EdgeList>::type e,
1.238 + std::vector<EdgeList, Allocator>& g)
1.239 + {
1.240 + typename EdgeList::value_type u, v;
1.241 + u = e.first;
1.242 + v = e.second;
1.243 + // FIXME: edge type does not fully specify the edge to be deleted
1.244 + typename EdgeList::iterator i = std::remove(g[u].begin(), g[u].end(), v);
1.245 + if (i != g[u].end())
1.246 + g[u].erase(i, g[u].end());
1.247 + }
1.248 +
1.249 + template<class EdgeList, class Allocator, class Predicate>
1.250 + void
1.251 + remove_edge_if(Predicate p,
1.252 + std::vector<EdgeList, Allocator>& g)
1.253 + {
1.254 + for (std::size_t u = 0; u < g.size(); ++u) {
1.255 + // Oops! gcc gets internal compiler error on compose_.......
1.256 +
1.257 + typedef typename EdgeList::iterator iterator;
1.258 + iterator b = g[u].begin(), e = g[u].end();
1.259 +
1.260 + if (!g[u].empty()) {
1.261 +
1.262 + for(; b != e;) {
1.263 + if (p(std::make_pair(u, *b))) {
1.264 + --e;
1.265 + if (b == e)
1.266 + break;
1.267 + else
1.268 + iter_swap(b, e);
1.269 + } else {
1.270 + ++b;
1.271 + }
1.272 + }
1.273 + }
1.274 +
1.275 + if (e != g[u].end())
1.276 + g[u].erase(e, g[u].end());
1.277 + }
1.278 + }
1.279 +
1.280 + template<class EdgeList, class Allocator>
1.281 + typename EdgeList::value_type
1.282 + add_vertex(std::vector<EdgeList, Allocator>& g)
1.283 + {
1.284 + g.resize(g.size()+1);
1.285 + return g.size()-1;
1.286 + }
1.287 +
1.288 + template<class EdgeList, class Allocator>
1.289 + void
1.290 + clear_vertex(typename EdgeList::value_type u,
1.291 + std::vector<EdgeList, Allocator>& g)
1.292 + {
1.293 + g[u].clear();
1.294 + for (std::size_t i = 0; i < g.size(); ++i)
1.295 + remove_edge(i, u, g);
1.296 + }
1.297 +
1.298 + template<class EdgeList, class Allocator>
1.299 + void
1.300 + remove_vertex(typename EdgeList::value_type u,
1.301 + std::vector<EdgeList, Allocator>& g)
1.302 + {
1.303 + typedef typename EdgeList::iterator iterator;
1.304 + clear_vertex(u, g);
1.305 + g.erase(g.begin() + u);
1.306 + for (std::size_t i = 0; i < g.size(); ++i)
1.307 + for ( iterator it = g[i].begin(); it != g[i].end(); ++it )
1.308 + // after clear_vertex *it is never equal to u
1.309 + if ( *it > u )
1.310 + --*it;
1.311 + }
1.312 +
1.313 + template<typename EdgeList, typename Allocator>
1.314 + struct property_map<std::vector<EdgeList, Allocator>, vertex_index_t>
1.315 + {
1.316 + typedef identity_property_map type;
1.317 + typedef type const_type;
1.318 + };
1.319 +
1.320 + template<typename EdgeList, typename Allocator>
1.321 + identity_property_map
1.322 + get(vertex_index_t, const std::vector<EdgeList, Allocator>&)
1.323 + {
1.324 + return identity_property_map();
1.325 + }
1.326 +
1.327 + template<typename EdgeList, typename Allocator>
1.328 + identity_property_map
1.329 + get(vertex_index_t, std::vector<EdgeList, Allocator>&)
1.330 + {
1.331 + return identity_property_map();
1.332 + }
1.333 +} // namespace boost
1.334 +
1.335 +#endif // BOOST_VECTOR_AS_GRAPH_HPP