1 //=======================================================================
2 // Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
3 // Copyright 2004 The Trustees of Indiana University.
4 // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek, Douglas Gregor
6 // Distributed under the Boost Software License, Version 1.0. (See
7 // accompanying file LICENSE_1_0.txt or copy at
8 // http://www.boost.org/LICENSE_1_0.txt)
9 //=======================================================================
10 #ifndef BOOST_GRAPH_LEDA_HPP
11 #define BOOST_GRAPH_LEDA_HPP
13 #include <boost/config.hpp>
14 #include <boost/iterator/iterator_facade.hpp>
15 #include <boost/graph/graph_traits.hpp>
16 #include <boost/graph/properties.hpp>
18 #include <LEDA/graph.h>
19 #include <LEDA/node_array.h>
20 #include <LEDA/node_map.h>
22 // The functions and classes in this file allows the user to
23 // treat a LEDA GRAPH object as a boost graph "as is". No
24 // wrapper is needed for the GRAPH object.
26 // Remember to define LEDA_PREFIX so that LEDA types such as
27 // leda_edge show up as "leda_edge" and not just "edge".
29 // Warning: this implementation relies on partial specialization
30 // for the graph_traits class (so it won't compile with Visual C++)
32 // Warning: this implementation is in alpha and has not been tested
34 #if !defined BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
37 struct leda_graph_traversal_category :
38 public virtual bidirectional_graph_tag,
39 public virtual adjacency_graph_tag,
40 public virtual vertex_list_graph_tag { };
42 template <class vtype, class etype>
43 struct graph_traits< leda::GRAPH<vtype,etype> > {
44 typedef leda_node vertex_descriptor;
45 typedef leda_edge edge_descriptor;
47 class adjacency_iterator
48 : public iterator_facade<adjacency_iterator,
50 bidirectional_traversal_tag,
55 explicit adjacency_iterator(leda_edge edge = 0) : base(edge) {}
58 leda_node dereference() const { return leda::target(base); }
60 bool equal(const adjacency_iterator& other) const
61 { return base == other.base; }
63 void increment() { base = Succ_Adj_Edge(base, 0); }
64 void decrement() { base = Pred_Adj_Edge(base, 0); }
68 friend class iterator_core_access;
71 class out_edge_iterator
72 : public iterator_facade<out_edge_iterator,
74 bidirectional_traversal_tag,
79 explicit out_edge_iterator(leda_edge edge = 0) : base(edge) {}
82 const leda_edge& dereference() const { return base; }
84 bool equal(const out_edge_iterator& other) const
85 { return base == other.base; }
87 void increment() { base = Succ_Adj_Edge(base, 0); }
88 void decrement() { base = Pred_Adj_Edge(base, 0); }
92 friend class iterator_core_access;
95 class in_edge_iterator
96 : public iterator_facade<in_edge_iterator,
98 bidirectional_traversal_tag,
103 explicit in_edge_iterator(leda_edge edge = 0) : base(edge) {}
106 const leda_edge& dereference() const { return base; }
108 bool equal(const in_edge_iterator& other) const
109 { return base == other.base; }
111 void increment() { base = Succ_Adj_Edge(base, 1); }
112 void decrement() { base = Pred_Adj_Edge(base, 1); }
116 friend class iterator_core_access;
119 class vertex_iterator
120 : public iterator_facade<vertex_iterator,
122 bidirectional_traversal_tag,
127 vertex_iterator(leda_node node = 0,
128 const leda::GRAPH<vtype, etype>* g = 0)
129 : base(node), g(g) {}
132 const leda_node& dereference() const { return base; }
134 bool equal(const vertex_iterator& other) const
135 { return base == other.base; }
137 void increment() { base = g->succ_node(base); }
138 void decrement() { base = g->pred_node(base); }
141 const leda::GRAPH<vtype, etype>* g;
143 friend class iterator_core_access;
146 typedef directed_tag directed_category;
147 typedef allow_parallel_edge_tag edge_parallel_category; // not sure here
148 typedef leda_graph_traversal_category traversal_category;
149 typedef int vertices_size_type;
150 typedef int edges_size_type;
151 typedef int degree_size_type;
154 template <class vtype, class etype>
155 struct vertex_property< leda::GRAPH<vtype,etype> > {
159 template <class vtype, class etype>
160 struct edge_property< leda::GRAPH<vtype,etype> > {
169 template <class vtype, class etype>
170 typename graph_traits< leda::GRAPH<vtype,etype> >::vertex_descriptor
171 source(typename graph_traits< leda::GRAPH<vtype,etype> >::edge_descriptor e,
172 const leda::GRAPH<vtype,etype>& g)
177 template <class vtype, class etype>
178 typename graph_traits< leda::GRAPH<vtype,etype> >::vertex_descriptor
179 target(typename graph_traits< leda::GRAPH<vtype,etype> >::edge_descriptor e,
180 const leda::GRAPH<vtype,etype>& g)
185 template <class vtype, class etype>
187 typename graph_traits< leda::GRAPH<vtype,etype> >::vertex_iterator,
188 typename graph_traits< leda::GRAPH<vtype,etype> >::vertex_iterator >
189 vertices(const leda::GRAPH<vtype,etype>& g)
191 typedef typename graph_traits< leda::GRAPH<vtype,etype> >::vertex_iterator
193 return std::make_pair( Iter(g.first_node(),&g), Iter(0,&g) );
196 // no edges(g) function
198 template <class vtype, class etype>
200 typename graph_traits< leda::GRAPH<vtype,etype> >::out_edge_iterator,
201 typename graph_traits< leda::GRAPH<vtype,etype> >::out_edge_iterator >
203 typename graph_traits< leda::GRAPH<vtype,etype> >::vertex_descriptor u,
204 const leda::GRAPH<vtype,etype>& g)
206 typedef typename graph_traits< leda::GRAPH<vtype,etype> >
207 ::out_edge_iterator Iter;
208 return std::make_pair( Iter(First_Adj_Edge(u,0)), Iter(0) );
211 template <class vtype, class etype>
213 typename graph_traits< leda::GRAPH<vtype,etype> >::in_edge_iterator,
214 typename graph_traits< leda::GRAPH<vtype,etype> >::in_edge_iterator >
216 typename graph_traits< leda::GRAPH<vtype,etype> >::vertex_descriptor u,
217 const leda::GRAPH<vtype,etype>& g)
219 typedef typename graph_traits< leda::GRAPH<vtype,etype> >
220 ::in_edge_iterator Iter;
221 return std::make_pair( Iter(First_Adj_Edge(u,1)), Iter(0) );
224 template <class vtype, class etype>
226 typename graph_traits< leda::GRAPH<vtype,etype> >::adjacency_iterator,
227 typename graph_traits< leda::GRAPH<vtype,etype> >::adjacency_iterator >
229 typename graph_traits< leda::GRAPH<vtype,etype> >::vertex_descriptor u,
230 const leda::GRAPH<vtype,etype>& g)
232 typedef typename graph_traits< leda::GRAPH<vtype,etype> >
233 ::adjacency_iterator Iter;
234 return std::make_pair( Iter(First_Adj_Edge(u,0)), Iter(0) );
237 template <class vtype, class etype>
238 typename graph_traits< leda::GRAPH<vtype,etype> >::vertices_size_type
239 num_vertices(const leda::GRAPH<vtype,etype>& g)
241 return g.number_of_nodes();
244 template <class vtype, class etype>
245 typename graph_traits< leda::GRAPH<vtype,etype> >::edges_size_type
246 num_edges(const leda::GRAPH<vtype,etype>& g)
248 return g.number_of_edges();
251 template <class vtype, class etype>
252 typename graph_traits< leda::GRAPH<vtype,etype> >::degree_size_type
254 typename graph_traits< leda::GRAPH<vtype,etype> >::vertex_descriptor u,
255 const leda::GRAPH<vtype,etype>&)
260 template <class vtype, class etype>
261 typename graph_traits< leda::GRAPH<vtype,etype> >::degree_size_type
263 typename graph_traits< leda::GRAPH<vtype,etype> >::vertex_descriptor u,
264 const leda::GRAPH<vtype,etype>&)
269 template <class vtype, class etype>
270 typename graph_traits< leda::GRAPH<vtype,etype> >::degree_size_type
272 typename graph_traits< leda::GRAPH<vtype,etype> >::vertex_descriptor u,
273 const leda::GRAPH<vtype,etype>&)
275 return outdeg(u) + indeg(u);
278 template <class vtype, class etype>
279 typename graph_traits< leda::GRAPH<vtype,etype> >::vertex_descriptor
280 add_vertex(leda::GRAPH<vtype,etype>& g)
285 template <class vtype, class etype>
286 typename graph_traits< leda::GRAPH<vtype,etype> >::vertex_descriptor
287 add_vertex(const vtype& vp, leda::GRAPH<vtype,etype>& g)
289 return g.new_node(vp);
292 // Hmm, LEDA doesn't have the equivalent of clear_vertex() -JGS
293 // need to write an implementation
294 template <class vtype, class etype>
296 typename graph_traits< leda::GRAPH<vtype,etype> >::vertex_descriptor u,
297 leda::GRAPH<vtype,etype>& g)
302 template <class vtype, class etype>
304 typename graph_traits< leda::GRAPH<vtype,etype> >::vertex_descriptor u,
305 leda::GRAPH<vtype,etype>& g)
310 template <class vtype, class etype>
312 typename graph_traits< leda::GRAPH<vtype,etype> >::edge_descriptor,
315 typename graph_traits< leda::GRAPH<vtype,etype> >::vertex_descriptor u,
316 typename graph_traits< leda::GRAPH<vtype,etype> >::vertex_descriptor v,
317 leda::GRAPH<vtype,etype>& g)
319 return std::make_pair(g.new_edge(u, v), true);
322 template <class vtype, class etype>
324 typename graph_traits< leda::GRAPH<vtype,etype> >::edge_descriptor,
327 typename graph_traits< leda::GRAPH<vtype,etype> >::vertex_descriptor u,
328 typename graph_traits< leda::GRAPH<vtype,etype> >::vertex_descriptor v,
330 leda::GRAPH<vtype,etype>& g)
332 return std::make_pair(g.new_edge(u, v, et), true);
335 template <class vtype, class etype>
338 typename graph_traits< leda::GRAPH<vtype,etype> >::vertex_descriptor u,
339 typename graph_traits< leda::GRAPH<vtype,etype> >::vertex_descriptor v,
340 leda::GRAPH<vtype,etype>& g)
342 typename graph_traits< leda::GRAPH<vtype,etype> >::out_edge_iterator
344 for (boost::tie(i,iend) = out_edges(u,g); i != iend; ++i)
345 if (target(*i,g) == v)
349 template <class vtype, class etype>
352 typename graph_traits< leda::GRAPH<vtype,etype> >::edge_descriptor e,
353 leda::GRAPH<vtype,etype>& g)
358 //===========================================================================
361 class leda_graph_id_map
362 : public put_get_helper<int, leda_graph_id_map>
365 typedef readable_property_map_tag category;
366 typedef int value_type;
367 typedef int reference;
368 typedef leda_node key_type;
369 leda_graph_id_map() { }
371 long operator[](T x) const { return x->id(); }
373 template <class vtype, class etype>
374 inline leda_graph_id_map
375 get(vertex_index_t, const leda::GRAPH<vtype, etype>& g) {
376 return leda_graph_id_map();
378 template <class vtype, class etype>
379 inline leda_graph_id_map
380 get(edge_index_t, const leda::GRAPH<vtype, etype>& g) {
381 return leda_graph_id_map();
385 struct leda_property_map { };
388 struct leda_property_map<vertex_index_t> {
389 template <class vtype, class etype>
391 typedef leda_graph_id_map type;
392 typedef leda_graph_id_map const_type;
396 struct leda_property_map<edge_index_t> {
397 template <class vtype, class etype>
399 typedef leda_graph_id_map type;
400 typedef leda_graph_id_map const_type;
405 template <class Data, class DataRef, class GraphPtr>
406 class leda_graph_data_map
407 : public put_get_helper<DataRef,
408 leda_graph_data_map<Data,DataRef,GraphPtr> >
411 typedef Data value_type;
412 typedef DataRef reference;
413 typedef void key_type;
414 typedef lvalue_property_map_tag category;
415 leda_graph_data_map(GraphPtr g) : m_g(g) { }
416 template <class NodeOrEdge>
417 DataRef operator[](NodeOrEdge x) const { return (*m_g)[x]; }
423 struct leda_property_map<vertex_all_t> {
424 template <class vtype, class etype>
426 typedef leda_graph_data_map<vtype, vtype&, leda::GRAPH<vtype, etype>*> type;
427 typedef leda_graph_data_map<vtype, const vtype&,
428 const leda::GRAPH<vtype, etype>*> const_type;
431 template <class vtype, class etype >
432 inline typename property_map< leda::GRAPH<vtype, etype>, vertex_all_t>::type
433 get(vertex_all_t, leda::GRAPH<vtype, etype>& g) {
434 typedef typename property_map< leda::GRAPH<vtype, etype>, vertex_all_t>::type
436 return pmap_type(&g);
438 template <class vtype, class etype >
439 inline typename property_map< leda::GRAPH<vtype, etype>, vertex_all_t>::const_type
440 get(vertex_all_t, const leda::GRAPH<vtype, etype>& g) {
441 typedef typename property_map< leda::GRAPH<vtype, etype>,
442 vertex_all_t>::const_type pmap_type;
443 return pmap_type(&g);
447 struct leda_property_map<edge_all_t> {
448 template <class vtype, class etype>
450 typedef leda_graph_data_map<etype, etype&, leda::GRAPH<vtype, etype>*> type;
451 typedef leda_graph_data_map<etype, const etype&,
452 const leda::GRAPH<vtype, etype>*> const_type;
455 template <class vtype, class etype >
456 inline typename property_map< leda::GRAPH<vtype, etype>, edge_all_t>::type
457 get(edge_all_t, leda::GRAPH<vtype, etype>& g) {
458 typedef typename property_map< leda::GRAPH<vtype, etype>, edge_all_t>::type
460 return pmap_type(&g);
462 template <class vtype, class etype >
463 inline typename property_map< leda::GRAPH<vtype, etype>, edge_all_t>::const_type
464 get(edge_all_t, const leda::GRAPH<vtype, etype>& g) {
465 typedef typename property_map< leda::GRAPH<vtype, etype>,
466 edge_all_t>::const_type pmap_type;
467 return pmap_type(&g);
470 // property map interface to the LEDA node_array class
472 template <class E, class ERef, class NodeMapPtr>
473 class leda_node_property_map
474 : public put_get_helper<ERef, leda_node_property_map<E, ERef, NodeMapPtr> >
477 typedef E value_type;
478 typedef ERef reference;
479 typedef leda_node key_type;
480 typedef lvalue_property_map_tag category;
481 leda_node_property_map(NodeMapPtr a) : m_array(a) { }
482 ERef operator[](leda_node n) const { return (*m_array)[n]; }
487 leda_node_property_map<E, const E&, const leda_node_array<E>*>
488 make_leda_node_property_map(const leda_node_array<E>& a)
490 typedef leda_node_property_map<E, const E&, const leda_node_array<E>*>
492 return pmap_type(&a);
495 leda_node_property_map<E, E&, leda_node_array<E>*>
496 make_leda_node_property_map(leda_node_array<E>& a)
498 typedef leda_node_property_map<E, E&, leda_node_array<E>*> pmap_type;
499 return pmap_type(&a);
503 leda_node_property_map<E, const E&, const leda_node_map<E>*>
504 make_leda_node_property_map(const leda_node_map<E>& a)
506 typedef leda_node_property_map<E,const E&,const leda_node_map<E>*>
508 return pmap_type(&a);
511 leda_node_property_map<E, E&, leda_node_map<E>*>
512 make_leda_node_property_map(leda_node_map<E>& a)
514 typedef leda_node_property_map<E, E&, leda_node_map<E>*> pmap_type;
515 return pmap_type(&a);
518 // g++ 'enumeral_type' in template unification not implemented workaround
519 template <class vtype, class etype, class Tag>
520 struct property_map<leda::GRAPH<vtype, etype>, Tag> {
522 leda_property_map<Tag>::template bind_<vtype, etype> map_gen;
523 typedef typename map_gen::type type;
524 typedef typename map_gen::const_type const_type;
527 template <class vtype, class etype, class PropertyTag, class Key>
529 typename boost::property_traits<
530 typename boost::property_map<leda::GRAPH<vtype, etype>,PropertyTag>::const_type
532 get(PropertyTag p, const leda::GRAPH<vtype, etype>& g, const Key& key) {
533 return get(get(p, g), key);
536 template <class vtype, class etype, class PropertyTag, class Key,class Value>
538 put(PropertyTag p, leda::GRAPH<vtype, etype>& g,
539 const Key& key, const Value& value)
541 typedef typename property_map<leda::GRAPH<vtype, etype>, PropertyTag>::type Map;
542 Map pmap = get(p, g);
543 put(pmap, key, value);
549 #endif // BOOST_GRAPH_LEDA_HPP