1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/epoc32/include/stdapis/boost/graph/leda_graph.hpp Tue Mar 16 16:12:26 2010 +0000
1.3 @@ -0,0 +1,549 @@
1.4 +//=======================================================================
1.5 +// Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
1.6 +// Copyright 2004 The Trustees of Indiana University.
1.7 +// Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek, Douglas Gregor
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 +#ifndef BOOST_GRAPH_LEDA_HPP
1.14 +#define BOOST_GRAPH_LEDA_HPP
1.15 +
1.16 +#include <boost/config.hpp>
1.17 +#include <boost/iterator/iterator_facade.hpp>
1.18 +#include <boost/graph/graph_traits.hpp>
1.19 +#include <boost/graph/properties.hpp>
1.20 +
1.21 +#include <LEDA/graph.h>
1.22 +#include <LEDA/node_array.h>
1.23 +#include <LEDA/node_map.h>
1.24 +
1.25 +// The functions and classes in this file allows the user to
1.26 +// treat a LEDA GRAPH object as a boost graph "as is". No
1.27 +// wrapper is needed for the GRAPH object.
1.28 +
1.29 +// Remember to define LEDA_PREFIX so that LEDA types such as
1.30 +// leda_edge show up as "leda_edge" and not just "edge".
1.31 +
1.32 +// Warning: this implementation relies on partial specialization
1.33 +// for the graph_traits class (so it won't compile with Visual C++)
1.34 +
1.35 +// Warning: this implementation is in alpha and has not been tested
1.36 +
1.37 +#if !defined BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
1.38 +namespace boost {
1.39 +
1.40 + struct leda_graph_traversal_category :
1.41 + public virtual bidirectional_graph_tag,
1.42 + public virtual adjacency_graph_tag,
1.43 + public virtual vertex_list_graph_tag { };
1.44 +
1.45 + template <class vtype, class etype>
1.46 + struct graph_traits< leda::GRAPH<vtype,etype> > {
1.47 + typedef leda_node vertex_descriptor;
1.48 + typedef leda_edge edge_descriptor;
1.49 +
1.50 + class adjacency_iterator
1.51 + : public iterator_facade<adjacency_iterator,
1.52 + leda_node,
1.53 + bidirectional_traversal_tag,
1.54 + leda_node,
1.55 + const leda_node*>
1.56 + {
1.57 + public:
1.58 + explicit adjacency_iterator(leda_edge edge = 0) : base(edge) {}
1.59 +
1.60 + private:
1.61 + leda_node dereference() const { return leda::target(base); }
1.62 +
1.63 + bool equal(const adjacency_iterator& other) const
1.64 + { return base == other.base; }
1.65 +
1.66 + void increment() { base = Succ_Adj_Edge(base, 0); }
1.67 + void decrement() { base = Pred_Adj_Edge(base, 0); }
1.68 +
1.69 + leda_edge base;
1.70 +
1.71 + friend class iterator_core_access;
1.72 + };
1.73 +
1.74 + class out_edge_iterator
1.75 + : public iterator_facade<out_edge_iterator,
1.76 + leda_edge,
1.77 + bidirectional_traversal_tag,
1.78 + const leda_edge&,
1.79 + const leda_edge*>
1.80 + {
1.81 + public:
1.82 + explicit out_edge_iterator(leda_edge edge = 0) : base(edge) {}
1.83 +
1.84 + private:
1.85 + const leda_edge& dereference() const { return base; }
1.86 +
1.87 + bool equal(const out_edge_iterator& other) const
1.88 + { return base == other.base; }
1.89 +
1.90 + void increment() { base = Succ_Adj_Edge(base, 0); }
1.91 + void decrement() { base = Pred_Adj_Edge(base, 0); }
1.92 +
1.93 + leda_edge base;
1.94 +
1.95 + friend class iterator_core_access;
1.96 + };
1.97 +
1.98 + class in_edge_iterator
1.99 + : public iterator_facade<in_edge_iterator,
1.100 + leda_edge,
1.101 + bidirectional_traversal_tag,
1.102 + const leda_edge&,
1.103 + const leda_edge*>
1.104 + {
1.105 + public:
1.106 + explicit in_edge_iterator(leda_edge edge = 0) : base(edge) {}
1.107 +
1.108 + private:
1.109 + const leda_edge& dereference() const { return base; }
1.110 +
1.111 + bool equal(const in_edge_iterator& other) const
1.112 + { return base == other.base; }
1.113 +
1.114 + void increment() { base = Succ_Adj_Edge(base, 1); }
1.115 + void decrement() { base = Pred_Adj_Edge(base, 1); }
1.116 +
1.117 + leda_edge base;
1.118 +
1.119 + friend class iterator_core_access;
1.120 + };
1.121 +
1.122 + class vertex_iterator
1.123 + : public iterator_facade<vertex_iterator,
1.124 + leda_node,
1.125 + bidirectional_traversal_tag,
1.126 + const leda_node&,
1.127 + const leda_node*>
1.128 + {
1.129 + public:
1.130 + vertex_iterator(leda_node node = 0,
1.131 + const leda::GRAPH<vtype, etype>* g = 0)
1.132 + : base(node), g(g) {}
1.133 +
1.134 + private:
1.135 + const leda_node& dereference() const { return base; }
1.136 +
1.137 + bool equal(const vertex_iterator& other) const
1.138 + { return base == other.base; }
1.139 +
1.140 + void increment() { base = g->succ_node(base); }
1.141 + void decrement() { base = g->pred_node(base); }
1.142 +
1.143 + leda_node base;
1.144 + const leda::GRAPH<vtype, etype>* g;
1.145 +
1.146 + friend class iterator_core_access;
1.147 + };
1.148 +
1.149 + typedef directed_tag directed_category;
1.150 + typedef allow_parallel_edge_tag edge_parallel_category; // not sure here
1.151 + typedef leda_graph_traversal_category traversal_category;
1.152 + typedef int vertices_size_type;
1.153 + typedef int edges_size_type;
1.154 + typedef int degree_size_type;
1.155 + };
1.156 +
1.157 + template <class vtype, class etype>
1.158 + struct vertex_property< leda::GRAPH<vtype,etype> > {
1.159 + typedef vtype type;
1.160 + };
1.161 +
1.162 + template <class vtype, class etype>
1.163 + struct edge_property< leda::GRAPH<vtype,etype> > {
1.164 + typedef etype type;
1.165 + };
1.166 +
1.167 +} // namespace boost
1.168 +#endif
1.169 +
1.170 +namespace boost {
1.171 +
1.172 + template <class vtype, class etype>
1.173 + typename graph_traits< leda::GRAPH<vtype,etype> >::vertex_descriptor
1.174 + source(typename graph_traits< leda::GRAPH<vtype,etype> >::edge_descriptor e,
1.175 + const leda::GRAPH<vtype,etype>& g)
1.176 + {
1.177 + return source(e);
1.178 + }
1.179 +
1.180 + template <class vtype, class etype>
1.181 + typename graph_traits< leda::GRAPH<vtype,etype> >::vertex_descriptor
1.182 + target(typename graph_traits< leda::GRAPH<vtype,etype> >::edge_descriptor e,
1.183 + const leda::GRAPH<vtype,etype>& g)
1.184 + {
1.185 + return target(e);
1.186 + }
1.187 +
1.188 + template <class vtype, class etype>
1.189 + inline std::pair<
1.190 + typename graph_traits< leda::GRAPH<vtype,etype> >::vertex_iterator,
1.191 + typename graph_traits< leda::GRAPH<vtype,etype> >::vertex_iterator >
1.192 + vertices(const leda::GRAPH<vtype,etype>& g)
1.193 + {
1.194 + typedef typename graph_traits< leda::GRAPH<vtype,etype> >::vertex_iterator
1.195 + Iter;
1.196 + return std::make_pair( Iter(g.first_node(),&g), Iter(0,&g) );
1.197 + }
1.198 +
1.199 + // no edges(g) function
1.200 +
1.201 + template <class vtype, class etype>
1.202 + inline std::pair<
1.203 + typename graph_traits< leda::GRAPH<vtype,etype> >::out_edge_iterator,
1.204 + typename graph_traits< leda::GRAPH<vtype,etype> >::out_edge_iterator >
1.205 + out_edges(
1.206 + typename graph_traits< leda::GRAPH<vtype,etype> >::vertex_descriptor u,
1.207 + const leda::GRAPH<vtype,etype>& g)
1.208 + {
1.209 + typedef typename graph_traits< leda::GRAPH<vtype,etype> >
1.210 + ::out_edge_iterator Iter;
1.211 + return std::make_pair( Iter(First_Adj_Edge(u,0)), Iter(0) );
1.212 + }
1.213 +
1.214 + template <class vtype, class etype>
1.215 + inline std::pair<
1.216 + typename graph_traits< leda::GRAPH<vtype,etype> >::in_edge_iterator,
1.217 + typename graph_traits< leda::GRAPH<vtype,etype> >::in_edge_iterator >
1.218 + in_edges(
1.219 + typename graph_traits< leda::GRAPH<vtype,etype> >::vertex_descriptor u,
1.220 + const leda::GRAPH<vtype,etype>& g)
1.221 + {
1.222 + typedef typename graph_traits< leda::GRAPH<vtype,etype> >
1.223 + ::in_edge_iterator Iter;
1.224 + return std::make_pair( Iter(First_Adj_Edge(u,1)), Iter(0) );
1.225 + }
1.226 +
1.227 + template <class vtype, class etype>
1.228 + inline std::pair<
1.229 + typename graph_traits< leda::GRAPH<vtype,etype> >::adjacency_iterator,
1.230 + typename graph_traits< leda::GRAPH<vtype,etype> >::adjacency_iterator >
1.231 + adjacent_vertices(
1.232 + typename graph_traits< leda::GRAPH<vtype,etype> >::vertex_descriptor u,
1.233 + const leda::GRAPH<vtype,etype>& g)
1.234 + {
1.235 + typedef typename graph_traits< leda::GRAPH<vtype,etype> >
1.236 + ::adjacency_iterator Iter;
1.237 + return std::make_pair( Iter(First_Adj_Edge(u,0)), Iter(0) );
1.238 + }
1.239 +
1.240 + template <class vtype, class etype>
1.241 + typename graph_traits< leda::GRAPH<vtype,etype> >::vertices_size_type
1.242 + num_vertices(const leda::GRAPH<vtype,etype>& g)
1.243 + {
1.244 + return g.number_of_nodes();
1.245 + }
1.246 +
1.247 + template <class vtype, class etype>
1.248 + typename graph_traits< leda::GRAPH<vtype,etype> >::edges_size_type
1.249 + num_edges(const leda::GRAPH<vtype,etype>& g)
1.250 + {
1.251 + return g.number_of_edges();
1.252 + }
1.253 +
1.254 + template <class vtype, class etype>
1.255 + typename graph_traits< leda::GRAPH<vtype,etype> >::degree_size_type
1.256 + out_degree(
1.257 + typename graph_traits< leda::GRAPH<vtype,etype> >::vertex_descriptor u,
1.258 + const leda::GRAPH<vtype,etype>&)
1.259 + {
1.260 + return outdeg(u);
1.261 + }
1.262 +
1.263 + template <class vtype, class etype>
1.264 + typename graph_traits< leda::GRAPH<vtype,etype> >::degree_size_type
1.265 + in_degree(
1.266 + typename graph_traits< leda::GRAPH<vtype,etype> >::vertex_descriptor u,
1.267 + const leda::GRAPH<vtype,etype>&)
1.268 + {
1.269 + return indeg(u);
1.270 + }
1.271 +
1.272 + template <class vtype, class etype>
1.273 + typename graph_traits< leda::GRAPH<vtype,etype> >::degree_size_type
1.274 + degree(
1.275 + typename graph_traits< leda::GRAPH<vtype,etype> >::vertex_descriptor u,
1.276 + const leda::GRAPH<vtype,etype>&)
1.277 + {
1.278 + return outdeg(u) + indeg(u);
1.279 + }
1.280 +
1.281 + template <class vtype, class etype>
1.282 + typename graph_traits< leda::GRAPH<vtype,etype> >::vertex_descriptor
1.283 + add_vertex(leda::GRAPH<vtype,etype>& g)
1.284 + {
1.285 + return g.new_node();
1.286 + }
1.287 +
1.288 + template <class vtype, class etype>
1.289 + typename graph_traits< leda::GRAPH<vtype,etype> >::vertex_descriptor
1.290 + add_vertex(const vtype& vp, leda::GRAPH<vtype,etype>& g)
1.291 + {
1.292 + return g.new_node(vp);
1.293 + }
1.294 +
1.295 + // Hmm, LEDA doesn't have the equivalent of clear_vertex() -JGS
1.296 + // need to write an implementation
1.297 + template <class vtype, class etype>
1.298 + void clear_vertex(
1.299 + typename graph_traits< leda::GRAPH<vtype,etype> >::vertex_descriptor u,
1.300 + leda::GRAPH<vtype,etype>& g)
1.301 + {
1.302 + g.del_node(u);
1.303 + }
1.304 +
1.305 + template <class vtype, class etype>
1.306 + void remove_vertex(
1.307 + typename graph_traits< leda::GRAPH<vtype,etype> >::vertex_descriptor u,
1.308 + leda::GRAPH<vtype,etype>& g)
1.309 + {
1.310 + g.del_node(u);
1.311 + }
1.312 +
1.313 + template <class vtype, class etype>
1.314 + std::pair<
1.315 + typename graph_traits< leda::GRAPH<vtype,etype> >::edge_descriptor,
1.316 + bool>
1.317 + add_edge(
1.318 + typename graph_traits< leda::GRAPH<vtype,etype> >::vertex_descriptor u,
1.319 + typename graph_traits< leda::GRAPH<vtype,etype> >::vertex_descriptor v,
1.320 + leda::GRAPH<vtype,etype>& g)
1.321 + {
1.322 + return std::make_pair(g.new_edge(u, v), true);
1.323 + }
1.324 +
1.325 + template <class vtype, class etype>
1.326 + std::pair<
1.327 + typename graph_traits< leda::GRAPH<vtype,etype> >::edge_descriptor,
1.328 + bool>
1.329 + add_edge(
1.330 + typename graph_traits< leda::GRAPH<vtype,etype> >::vertex_descriptor u,
1.331 + typename graph_traits< leda::GRAPH<vtype,etype> >::vertex_descriptor v,
1.332 + const etype& et,
1.333 + leda::GRAPH<vtype,etype>& g)
1.334 + {
1.335 + return std::make_pair(g.new_edge(u, v, et), true);
1.336 + }
1.337 +
1.338 + template <class vtype, class etype>
1.339 + void
1.340 + remove_edge(
1.341 + typename graph_traits< leda::GRAPH<vtype,etype> >::vertex_descriptor u,
1.342 + typename graph_traits< leda::GRAPH<vtype,etype> >::vertex_descriptor v,
1.343 + leda::GRAPH<vtype,etype>& g)
1.344 + {
1.345 + typename graph_traits< leda::GRAPH<vtype,etype> >::out_edge_iterator
1.346 + i,iend;
1.347 + for (boost::tie(i,iend) = out_edges(u,g); i != iend; ++i)
1.348 + if (target(*i,g) == v)
1.349 + g.del_edge(*i);
1.350 + }
1.351 +
1.352 + template <class vtype, class etype>
1.353 + void
1.354 + remove_edge(
1.355 + typename graph_traits< leda::GRAPH<vtype,etype> >::edge_descriptor e,
1.356 + leda::GRAPH<vtype,etype>& g)
1.357 + {
1.358 + g.del_edge(e);
1.359 + }
1.360 +
1.361 + //===========================================================================
1.362 + // property maps
1.363 +
1.364 + class leda_graph_id_map
1.365 + : public put_get_helper<int, leda_graph_id_map>
1.366 + {
1.367 + public:
1.368 + typedef readable_property_map_tag category;
1.369 + typedef int value_type;
1.370 + typedef int reference;
1.371 + typedef leda_node key_type;
1.372 + leda_graph_id_map() { }
1.373 + template <class T>
1.374 + long operator[](T x) const { return x->id(); }
1.375 + };
1.376 + template <class vtype, class etype>
1.377 + inline leda_graph_id_map
1.378 + get(vertex_index_t, const leda::GRAPH<vtype, etype>& g) {
1.379 + return leda_graph_id_map();
1.380 + }
1.381 + template <class vtype, class etype>
1.382 + inline leda_graph_id_map
1.383 + get(edge_index_t, const leda::GRAPH<vtype, etype>& g) {
1.384 + return leda_graph_id_map();
1.385 + }
1.386 +
1.387 + template <class Tag>
1.388 + struct leda_property_map { };
1.389 +
1.390 + template <>
1.391 + struct leda_property_map<vertex_index_t> {
1.392 + template <class vtype, class etype>
1.393 + struct bind_ {
1.394 + typedef leda_graph_id_map type;
1.395 + typedef leda_graph_id_map const_type;
1.396 + };
1.397 + };
1.398 + template <>
1.399 + struct leda_property_map<edge_index_t> {
1.400 + template <class vtype, class etype>
1.401 + struct bind_ {
1.402 + typedef leda_graph_id_map type;
1.403 + typedef leda_graph_id_map const_type;
1.404 + };
1.405 + };
1.406 +
1.407 +
1.408 + template <class Data, class DataRef, class GraphPtr>
1.409 + class leda_graph_data_map
1.410 + : public put_get_helper<DataRef,
1.411 + leda_graph_data_map<Data,DataRef,GraphPtr> >
1.412 + {
1.413 + public:
1.414 + typedef Data value_type;
1.415 + typedef DataRef reference;
1.416 + typedef void key_type;
1.417 + typedef lvalue_property_map_tag category;
1.418 + leda_graph_data_map(GraphPtr g) : m_g(g) { }
1.419 + template <class NodeOrEdge>
1.420 + DataRef operator[](NodeOrEdge x) const { return (*m_g)[x]; }
1.421 + protected:
1.422 + GraphPtr m_g;
1.423 + };
1.424 +
1.425 + template <>
1.426 + struct leda_property_map<vertex_all_t> {
1.427 + template <class vtype, class etype>
1.428 + struct bind_ {
1.429 + typedef leda_graph_data_map<vtype, vtype&, leda::GRAPH<vtype, etype>*> type;
1.430 + typedef leda_graph_data_map<vtype, const vtype&,
1.431 + const leda::GRAPH<vtype, etype>*> const_type;
1.432 + };
1.433 + };
1.434 + template <class vtype, class etype >
1.435 + inline typename property_map< leda::GRAPH<vtype, etype>, vertex_all_t>::type
1.436 + get(vertex_all_t, leda::GRAPH<vtype, etype>& g) {
1.437 + typedef typename property_map< leda::GRAPH<vtype, etype>, vertex_all_t>::type
1.438 + pmap_type;
1.439 + return pmap_type(&g);
1.440 + }
1.441 + template <class vtype, class etype >
1.442 + inline typename property_map< leda::GRAPH<vtype, etype>, vertex_all_t>::const_type
1.443 + get(vertex_all_t, const leda::GRAPH<vtype, etype>& g) {
1.444 + typedef typename property_map< leda::GRAPH<vtype, etype>,
1.445 + vertex_all_t>::const_type pmap_type;
1.446 + return pmap_type(&g);
1.447 + }
1.448 +
1.449 + template <>
1.450 + struct leda_property_map<edge_all_t> {
1.451 + template <class vtype, class etype>
1.452 + struct bind_ {
1.453 + typedef leda_graph_data_map<etype, etype&, leda::GRAPH<vtype, etype>*> type;
1.454 + typedef leda_graph_data_map<etype, const etype&,
1.455 + const leda::GRAPH<vtype, etype>*> const_type;
1.456 + };
1.457 + };
1.458 + template <class vtype, class etype >
1.459 + inline typename property_map< leda::GRAPH<vtype, etype>, edge_all_t>::type
1.460 + get(edge_all_t, leda::GRAPH<vtype, etype>& g) {
1.461 + typedef typename property_map< leda::GRAPH<vtype, etype>, edge_all_t>::type
1.462 + pmap_type;
1.463 + return pmap_type(&g);
1.464 + }
1.465 + template <class vtype, class etype >
1.466 + inline typename property_map< leda::GRAPH<vtype, etype>, edge_all_t>::const_type
1.467 + get(edge_all_t, const leda::GRAPH<vtype, etype>& g) {
1.468 + typedef typename property_map< leda::GRAPH<vtype, etype>,
1.469 + edge_all_t>::const_type pmap_type;
1.470 + return pmap_type(&g);
1.471 + }
1.472 +
1.473 + // property map interface to the LEDA node_array class
1.474 +
1.475 + template <class E, class ERef, class NodeMapPtr>
1.476 + class leda_node_property_map
1.477 + : public put_get_helper<ERef, leda_node_property_map<E, ERef, NodeMapPtr> >
1.478 + {
1.479 + public:
1.480 + typedef E value_type;
1.481 + typedef ERef reference;
1.482 + typedef leda_node key_type;
1.483 + typedef lvalue_property_map_tag category;
1.484 + leda_node_property_map(NodeMapPtr a) : m_array(a) { }
1.485 + ERef operator[](leda_node n) const { return (*m_array)[n]; }
1.486 + protected:
1.487 + NodeMapPtr m_array;
1.488 + };
1.489 + template <class E>
1.490 + leda_node_property_map<E, const E&, const leda_node_array<E>*>
1.491 + make_leda_node_property_map(const leda_node_array<E>& a)
1.492 + {
1.493 + typedef leda_node_property_map<E, const E&, const leda_node_array<E>*>
1.494 + pmap_type;
1.495 + return pmap_type(&a);
1.496 + }
1.497 + template <class E>
1.498 + leda_node_property_map<E, E&, leda_node_array<E>*>
1.499 + make_leda_node_property_map(leda_node_array<E>& a)
1.500 + {
1.501 + typedef leda_node_property_map<E, E&, leda_node_array<E>*> pmap_type;
1.502 + return pmap_type(&a);
1.503 + }
1.504 +
1.505 + template <class E>
1.506 + leda_node_property_map<E, const E&, const leda_node_map<E>*>
1.507 + make_leda_node_property_map(const leda_node_map<E>& a)
1.508 + {
1.509 + typedef leda_node_property_map<E,const E&,const leda_node_map<E>*>
1.510 + pmap_type;
1.511 + return pmap_type(&a);
1.512 + }
1.513 + template <class E>
1.514 + leda_node_property_map<E, E&, leda_node_map<E>*>
1.515 + make_leda_node_property_map(leda_node_map<E>& a)
1.516 + {
1.517 + typedef leda_node_property_map<E, E&, leda_node_map<E>*> pmap_type;
1.518 + return pmap_type(&a);
1.519 + }
1.520 +
1.521 + // g++ 'enumeral_type' in template unification not implemented workaround
1.522 + template <class vtype, class etype, class Tag>
1.523 + struct property_map<leda::GRAPH<vtype, etype>, Tag> {
1.524 + typedef typename
1.525 + leda_property_map<Tag>::template bind_<vtype, etype> map_gen;
1.526 + typedef typename map_gen::type type;
1.527 + typedef typename map_gen::const_type const_type;
1.528 + };
1.529 +
1.530 + template <class vtype, class etype, class PropertyTag, class Key>
1.531 + inline
1.532 + typename boost::property_traits<
1.533 + typename boost::property_map<leda::GRAPH<vtype, etype>,PropertyTag>::const_type
1.534 + >::value_type
1.535 + get(PropertyTag p, const leda::GRAPH<vtype, etype>& g, const Key& key) {
1.536 + return get(get(p, g), key);
1.537 + }
1.538 +
1.539 + template <class vtype, class etype, class PropertyTag, class Key,class Value>
1.540 + inline void
1.541 + put(PropertyTag p, leda::GRAPH<vtype, etype>& g,
1.542 + const Key& key, const Value& value)
1.543 + {
1.544 + typedef typename property_map<leda::GRAPH<vtype, etype>, PropertyTag>::type Map;
1.545 + Map pmap = get(p, g);
1.546 + put(pmap, key, value);
1.547 + }
1.548 +
1.549 +} // namespace boost
1.550 +
1.551 +
1.552 +#endif // BOOST_GRAPH_LEDA_HPP