1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/epoc32/include/stdapis/boost/graph/graph_concepts.hpp Tue Mar 16 16:12:26 2010 +0000
1.3 @@ -0,0 +1,492 @@
1.4 +//
1.5 +//=======================================================================
1.6 +// Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
1.7 +// Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek
1.8 +//
1.9 +// Distributed under the Boost Software License, Version 1.0. (See
1.10 +// accompanying file LICENSE_1_0.txt or copy at
1.11 +// http://www.boost.org/LICENSE_1_0.txt)
1.12 +//=======================================================================
1.13 +//
1.14 +#ifndef BOOST_GRAPH_CONCEPTS_HPP
1.15 +#define BOOST_GRAPH_CONCEPTS_HPP
1.16 +
1.17 +#include <boost/config.hpp>
1.18 +#include <boost/graph/graph_traits.hpp>
1.19 +#include <boost/property_map.hpp>
1.20 +#include <boost/graph/properties.hpp>
1.21 +#include <boost/concept_check.hpp>
1.22 +#include <boost/detail/workaround.hpp>
1.23 +
1.24 +namespace boost {
1.25 +
1.26 + template <class T>
1.27 + struct MultiPassInputIteratorConcept {
1.28 + void constraints() {
1.29 + function_requires< InputIteratorConcept<T> >();
1.30 + }
1.31 + };
1.32 +
1.33 + template <class G>
1.34 + struct GraphConcept
1.35 + {
1.36 + typedef typename graph_traits<G>::vertex_descriptor vertex_descriptor;
1.37 + typedef typename graph_traits<G>::directed_category directed_category;
1.38 + typedef typename graph_traits<G>::edge_parallel_category
1.39 + edge_parallel_category;
1.40 + typedef typename graph_traits<G>::traversal_category
1.41 + traversal_category;
1.42 + void constraints() {
1.43 + function_requires< DefaultConstructibleConcept<vertex_descriptor> >();
1.44 + function_requires< EqualityComparableConcept<vertex_descriptor> >();
1.45 + function_requires< AssignableConcept<vertex_descriptor> >();
1.46 + }
1.47 + G g;
1.48 + };
1.49 +
1.50 + template <class G>
1.51 + struct IncidenceGraphConcept
1.52 + {
1.53 + typedef typename graph_traits<G>::edge_descriptor edge_descriptor;
1.54 + typedef typename graph_traits<G>::out_edge_iterator
1.55 + out_edge_iterator;
1.56 + typedef typename graph_traits<G>::traversal_category
1.57 + traversal_category;
1.58 + void constraints() {
1.59 + function_requires< GraphConcept<G> >();
1.60 + function_requires< MultiPassInputIteratorConcept<out_edge_iterator> >();
1.61 + function_requires< DefaultConstructibleConcept<edge_descriptor> >();
1.62 + function_requires< EqualityComparableConcept<edge_descriptor> >();
1.63 + function_requires< AssignableConcept<edge_descriptor> >();
1.64 + function_requires< ConvertibleConcept<traversal_category,
1.65 + incidence_graph_tag> >();
1.66 +
1.67 + p = out_edges(u, g);
1.68 + n = out_degree(u, g);
1.69 + e = *p.first;
1.70 + u = source(e, g);
1.71 + v = target(e, g);
1.72 + const_constraints(g);
1.73 + }
1.74 + void const_constraints(const G& cg) {
1.75 + p = out_edges(u, cg);
1.76 + n = out_degree(u, cg);
1.77 + e = *p.first;
1.78 + u = source(e, cg);
1.79 + v = target(e, cg);
1.80 + }
1.81 + std::pair<out_edge_iterator, out_edge_iterator> p;
1.82 + typename graph_traits<G>::vertex_descriptor u, v;
1.83 + typename graph_traits<G>::edge_descriptor e;
1.84 + typename graph_traits<G>::degree_size_type n;
1.85 + G g;
1.86 + };
1.87 +
1.88 + template <class G>
1.89 + struct BidirectionalGraphConcept
1.90 + {
1.91 + typedef typename graph_traits<G>::in_edge_iterator
1.92 + in_edge_iterator;
1.93 + typedef typename graph_traits<G>::traversal_category
1.94 + traversal_category;
1.95 + void constraints() {
1.96 + function_requires< IncidenceGraphConcept<G> >();
1.97 + function_requires< MultiPassInputIteratorConcept<in_edge_iterator> >();
1.98 + function_requires< ConvertibleConcept<traversal_category,
1.99 + bidirectional_graph_tag> >();
1.100 +
1.101 + p = in_edges(v, g);
1.102 + n = in_degree(v, g);
1.103 + e = *p.first;
1.104 + const_constraints(g);
1.105 + }
1.106 + void const_constraints(const G& cg) {
1.107 + p = in_edges(v, cg);
1.108 + n = in_degree(v, cg);
1.109 + e = *p.first;
1.110 + }
1.111 + std::pair<in_edge_iterator, in_edge_iterator> p;
1.112 + typename graph_traits<G>::vertex_descriptor v;
1.113 + typename graph_traits<G>::edge_descriptor e;
1.114 + typename graph_traits<G>::degree_size_type n;
1.115 + G g;
1.116 + };
1.117 +
1.118 + template <class G>
1.119 + struct AdjacencyGraphConcept
1.120 + {
1.121 + typedef typename graph_traits<G>::adjacency_iterator
1.122 + adjacency_iterator;
1.123 + typedef typename graph_traits<G>::traversal_category
1.124 + traversal_category;
1.125 + void constraints() {
1.126 + function_requires< GraphConcept<G> >();
1.127 + function_requires< MultiPassInputIteratorConcept<adjacency_iterator> >();
1.128 + function_requires< ConvertibleConcept<traversal_category,
1.129 + adjacency_graph_tag> >();
1.130 +
1.131 + p = adjacent_vertices(v, g);
1.132 + v = *p.first;
1.133 + const_constraints(g);
1.134 + }
1.135 + void const_constraints(const G& cg) {
1.136 + p = adjacent_vertices(v, cg);
1.137 + }
1.138 + std::pair<adjacency_iterator,adjacency_iterator> p;
1.139 + typename graph_traits<G>::vertex_descriptor v;
1.140 + G g;
1.141 + };
1.142 +
1.143 +// dwa 2003/7/11 -- This clearly shouldn't be necessary, but if
1.144 +// you want to use vector_as_graph, it is! I'm sure the graph
1.145 +// library leaves these out all over the place. Probably a
1.146 +// redesign involving specializing a template with a static
1.147 +// member function is in order :(
1.148 +//
1.149 +// It is needed in order to allow us to write using boost::vertices as
1.150 +// needed for ADL when using vector_as_graph below.
1.151 +#if !defined(BOOST_NO_ARGUMENT_DEPENDENT_LOOKUP) \
1.152 + && !BOOST_WORKAROUND(__GNUC__, <= 2) \
1.153 + && !BOOST_WORKAROUND(__BORLANDC__, BOOST_TESTED_AT(0x564))
1.154 +# define BOOST_VECTOR_AS_GRAPH_GRAPH_ADL_HACK
1.155 +#endif
1.156 +
1.157 +#ifdef BOOST_VECTOR_AS_GRAPH_GRAPH_ADL_HACK
1.158 +template <class T>
1.159 +typename T::ThereReallyIsNoMemberByThisNameInT vertices(T const&);
1.160 +#endif
1.161 +
1.162 + template <class G>
1.163 + struct VertexListGraphConcept
1.164 + {
1.165 + typedef typename graph_traits<G>::vertex_iterator vertex_iterator;
1.166 + typedef typename graph_traits<G>::vertices_size_type vertices_size_type;
1.167 + typedef typename graph_traits<G>::traversal_category
1.168 + traversal_category;
1.169 + void constraints() {
1.170 + function_requires< GraphConcept<G> >();
1.171 + function_requires< MultiPassInputIteratorConcept<vertex_iterator> >();
1.172 + function_requires< ConvertibleConcept<traversal_category,
1.173 + vertex_list_graph_tag> >();
1.174 +
1.175 +#ifdef BOOST_VECTOR_AS_GRAPH_GRAPH_ADL_HACK
1.176 + // dwa 2003/7/11 -- This clearly shouldn't be necessary, but if
1.177 + // you want to use vector_as_graph, it is! I'm sure the graph
1.178 + // library leaves these out all over the place. Probably a
1.179 + // redesign involving specializing a template with a static
1.180 + // member function is in order :(
1.181 + using boost::vertices;
1.182 +#endif
1.183 + p = vertices(g);
1.184 + v = *p.first;
1.185 + const_constraints(g);
1.186 + }
1.187 + void const_constraints(const G& cg) {
1.188 +#ifdef BOOST_VECTOR_AS_GRAPH_GRAPH_ADL_HACK
1.189 + // dwa 2003/7/11 -- This clearly shouldn't be necessary, but if
1.190 + // you want to use vector_as_graph, it is! I'm sure the graph
1.191 + // library leaves these out all over the place. Probably a
1.192 + // redesign involving specializing a template with a static
1.193 + // member function is in order :(
1.194 + using boost::vertices;
1.195 +#endif
1.196 +
1.197 + p = vertices(cg);
1.198 + v = *p.first;
1.199 + V = num_vertices(cg);
1.200 + }
1.201 + std::pair<vertex_iterator,vertex_iterator> p;
1.202 + typename graph_traits<G>::vertex_descriptor v;
1.203 + G g;
1.204 + vertices_size_type V;
1.205 + };
1.206 +
1.207 + template <class G>
1.208 + struct EdgeListGraphConcept
1.209 + {
1.210 + typedef typename graph_traits<G>::edge_descriptor edge_descriptor;
1.211 + typedef typename graph_traits<G>::edge_iterator edge_iterator;
1.212 + typedef typename graph_traits<G>::edges_size_type edges_size_type;
1.213 + typedef typename graph_traits<G>::traversal_category
1.214 + traversal_category;
1.215 + void constraints() {
1.216 + function_requires< GraphConcept<G> >();
1.217 + function_requires< MultiPassInputIteratorConcept<edge_iterator> >();
1.218 + function_requires< DefaultConstructibleConcept<edge_descriptor> >();
1.219 + function_requires< EqualityComparableConcept<edge_descriptor> >();
1.220 + function_requires< AssignableConcept<edge_descriptor> >();
1.221 + function_requires< ConvertibleConcept<traversal_category,
1.222 + edge_list_graph_tag> >();
1.223 +
1.224 + p = edges(g);
1.225 + e = *p.first;
1.226 + u = source(e, g);
1.227 + v = target(e, g);
1.228 + const_constraints(g);
1.229 + }
1.230 + void const_constraints(const G& cg) {
1.231 + p = edges(cg);
1.232 + E = num_edges(cg);
1.233 + e = *p.first;
1.234 + u = source(e, cg);
1.235 + v = target(e, cg);
1.236 + }
1.237 + std::pair<edge_iterator,edge_iterator> p;
1.238 + typename graph_traits<G>::vertex_descriptor u, v;
1.239 + typename graph_traits<G>::edge_descriptor e;
1.240 + edges_size_type E;
1.241 + G g;
1.242 + };
1.243 +
1.244 + template <class G>
1.245 + struct VertexAndEdgeListGraphConcept
1.246 + {
1.247 + void constraints() {
1.248 + function_requires< VertexListGraphConcept<G> >();
1.249 + function_requires< EdgeListGraphConcept<G> >();
1.250 + }
1.251 + };
1.252 +
1.253 + // Where to put the requirement for this constructor?
1.254 + // G g(n_vertices);
1.255 + // Not in mutable graph, then LEDA graph's can't be models of
1.256 + // MutableGraph.
1.257 +
1.258 + template <class G>
1.259 + struct EdgeMutableGraphConcept
1.260 + {
1.261 + typedef typename graph_traits<G>::edge_descriptor edge_descriptor;
1.262 + void constraints() {
1.263 + p = add_edge(u, v, g);
1.264 + remove_edge(u, v, g);
1.265 + remove_edge(e, g);
1.266 + clear_vertex(v, g);
1.267 + }
1.268 + G g;
1.269 + edge_descriptor e;
1.270 + std::pair<edge_descriptor, bool> p;
1.271 + typename graph_traits<G>::vertex_descriptor u, v;
1.272 + };
1.273 +
1.274 + template <class G>
1.275 + struct VertexMutableGraphConcept
1.276 + {
1.277 + void constraints() {
1.278 + v = add_vertex(g);
1.279 + remove_vertex(v, g);
1.280 + }
1.281 + G g;
1.282 + typename graph_traits<G>::vertex_descriptor u, v;
1.283 + };
1.284 +
1.285 + template <class G>
1.286 + struct MutableGraphConcept
1.287 + {
1.288 + void constraints() {
1.289 + function_requires< EdgeMutableGraphConcept<G> >();
1.290 + function_requires< VertexMutableGraphConcept<G> >();
1.291 + }
1.292 + };
1.293 +
1.294 + template <class edge_descriptor>
1.295 + struct dummy_edge_predicate {
1.296 + bool operator()(const edge_descriptor&) const {
1.297 + return false;
1.298 + }
1.299 + };
1.300 +
1.301 + template <class G>
1.302 + struct MutableIncidenceGraphConcept
1.303 + {
1.304 + void constraints() {
1.305 + function_requires< MutableGraphConcept<G> >();
1.306 + remove_edge(iter, g);
1.307 + remove_out_edge_if(u, p, g);
1.308 + }
1.309 + G g;
1.310 + typedef typename graph_traits<G>::edge_descriptor edge_descriptor;
1.311 + dummy_edge_predicate<edge_descriptor> p;
1.312 + typename boost::graph_traits<G>::vertex_descriptor u;
1.313 + typename boost::graph_traits<G>::out_edge_iterator iter;
1.314 + };
1.315 +
1.316 + template <class G>
1.317 + struct MutableBidirectionalGraphConcept
1.318 + {
1.319 + void constraints() {
1.320 + function_requires< MutableIncidenceGraphConcept<G> >();
1.321 + remove_in_edge_if(u, p, g);
1.322 + }
1.323 + G g;
1.324 + typedef typename graph_traits<G>::edge_descriptor edge_descriptor;
1.325 + dummy_edge_predicate<edge_descriptor> p;
1.326 + typename boost::graph_traits<G>::vertex_descriptor u;
1.327 + };
1.328 +
1.329 + template <class G>
1.330 + struct MutableEdgeListGraphConcept
1.331 + {
1.332 + void constraints() {
1.333 + function_requires< EdgeMutableGraphConcept<G> >();
1.334 + remove_edge_if(p, g);
1.335 + }
1.336 + G g;
1.337 + typedef typename graph_traits<G>::edge_descriptor edge_descriptor;
1.338 + dummy_edge_predicate<edge_descriptor> p;
1.339 + };
1.340 +
1.341 + template <class G>
1.342 + struct VertexMutablePropertyGraphConcept
1.343 + {
1.344 + void constraints() {
1.345 + function_requires< VertexMutableGraphConcept<G> >();
1.346 + v = add_vertex(vp, g);
1.347 + }
1.348 + G g;
1.349 + typename graph_traits<G>::vertex_descriptor v;
1.350 + typename vertex_property<G>::type vp;
1.351 + };
1.352 +
1.353 + template <class G>
1.354 + struct EdgeMutablePropertyGraphConcept
1.355 + {
1.356 + typedef typename graph_traits<G>::edge_descriptor edge_descriptor;
1.357 + void constraints() {
1.358 + function_requires< EdgeMutableGraphConcept<G> >();
1.359 + p = add_edge(u, v, ep, g);
1.360 + }
1.361 + G g;
1.362 + std::pair<edge_descriptor, bool> p;
1.363 + typename graph_traits<G>::vertex_descriptor u, v;
1.364 + typename edge_property<G>::type ep;
1.365 + };
1.366 +
1.367 + template <class G>
1.368 + struct AdjacencyMatrixConcept
1.369 + {
1.370 + typedef typename graph_traits<G>::edge_descriptor edge_descriptor;
1.371 + void constraints() {
1.372 + function_requires< GraphConcept<G> >();
1.373 +
1.374 + p = edge(u, v, g);
1.375 + const_constraints(g);
1.376 + }
1.377 + void const_constraints(const G& cg) {
1.378 + p = edge(u, v, cg);
1.379 + }
1.380 + typename graph_traits<G>::vertex_descriptor u, v;
1.381 + std::pair<edge_descriptor, bool> p;
1.382 + G g;
1.383 + };
1.384 +
1.385 + template <class G, class X, class Property>
1.386 + struct ReadablePropertyGraphConcept
1.387 + {
1.388 + typedef typename property_map<G, Property>::const_type const_Map;
1.389 + void constraints() {
1.390 + function_requires< GraphConcept<G> >();
1.391 + function_requires< ReadablePropertyMapConcept<const_Map, X> >();
1.392 +
1.393 + const_constraints(g);
1.394 + }
1.395 + void const_constraints(const G& cg) {
1.396 + const_Map pmap = get(Property(), cg);
1.397 + pval = get(Property(), cg, x);
1.398 + ignore_unused_variable_warning(pmap);
1.399 + }
1.400 + G g;
1.401 + X x;
1.402 + typename property_traits<const_Map>::value_type pval;
1.403 + };
1.404 +
1.405 + template <class G, class X, class Property>
1.406 + struct PropertyGraphConcept
1.407 + {
1.408 + typedef typename property_map<G, Property>::type Map;
1.409 + void constraints() {
1.410 + function_requires< ReadablePropertyGraphConcept<G, X, Property> >();
1.411 + function_requires< ReadWritePropertyMapConcept<Map, X> >();
1.412 +
1.413 + Map pmap = get(Property(), g);
1.414 + pval = get(Property(), g, x);
1.415 + put(Property(), g, x, pval);
1.416 + ignore_unused_variable_warning(pmap);
1.417 + }
1.418 + G g;
1.419 + X x;
1.420 + typename property_traits<Map>::value_type pval;
1.421 + };
1.422 +
1.423 + template <class G, class X, class Property>
1.424 + struct LvaluePropertyGraphConcept
1.425 + {
1.426 + typedef typename property_map<G, Property>::type Map;
1.427 + typedef typename property_map<G, Property>::const_type const_Map;
1.428 + void constraints() {
1.429 + function_requires< ReadablePropertyGraphConcept<G, X, Property> >();
1.430 + function_requires< LvaluePropertyMapConcept<const_Map, X> >();
1.431 +
1.432 + pval = get(Property(), g, x);
1.433 + put(Property(), g, x, pval);
1.434 + }
1.435 + G g;
1.436 + X x;
1.437 + typename property_traits<Map>::value_type pval;
1.438 + };
1.439 +
1.440 + // This needs to move out of the graph library
1.441 + template <class B>
1.442 + struct BufferConcept
1.443 + {
1.444 + void constraints() {
1.445 + b.push(t);
1.446 + b.pop();
1.447 + typename B::value_type& v = b.top();
1.448 + const_constraints(b);
1.449 + ignore_unused_variable_warning(v);
1.450 + }
1.451 + void const_constraints(const B& cb) {
1.452 + const typename B::value_type& v = cb.top();
1.453 + n = cb.size();
1.454 + bool e = cb.empty();
1.455 + ignore_unused_variable_warning(v);
1.456 + ignore_unused_variable_warning(e);
1.457 + }
1.458 + typename B::size_type n;
1.459 + typename B::value_type t;
1.460 + B b;
1.461 + };
1.462 +
1.463 + template <class C>
1.464 + struct ColorValueConcept
1.465 + {
1.466 + void constraints() {
1.467 + function_requires< EqualityComparableConcept<C> >();
1.468 + function_requires< DefaultConstructibleConcept<C> >();
1.469 +
1.470 + c = color_traits<C>::white();
1.471 + c = color_traits<C>::gray();
1.472 + c = color_traits<C>::black();
1.473 + }
1.474 + C c;
1.475 + };
1.476 +
1.477 + template <class M, class I, class V>
1.478 + struct BasicMatrixConcept
1.479 + {
1.480 + void constraints() {
1.481 + V& elt = A[i][j];
1.482 + const_constraints(A);
1.483 + ignore_unused_variable_warning(elt);
1.484 + }
1.485 + void const_constraints(const M& cA) {
1.486 + const V& elt = cA[i][j];
1.487 + ignore_unused_variable_warning(elt);
1.488 + }
1.489 + M A;
1.490 + I i, j;
1.491 + };
1.492 +
1.493 +} // namespace boost
1.494 +
1.495 +#endif /* BOOST_GRAPH_CONCEPTS_H */