Ticket #1326: leda_graph.hpp

File leda_graph.hpp, 19.0 KB (added by iouri.smirnov@…, 15 years ago)

Patched LEDA graph adapter

Line 
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
5//
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
12
13#ifndef BOOST_GRAPH_LEDA_NAMESPACE
14#define BOOST_GRAPH_LEDA_NAMESPACE leda
15#endif
16#ifndef BOOST_GRAPH_LEDA_DECL
17#define BOOST_GRAPH_LEDA_DECL(VT,ET) BOOST_GRAPH_LEDA_NAMESPACE::GRAPH< VT, ET >
18#endif
19
20#include <boost/config.hpp>
21#include <boost/iterator/iterator_facade.hpp>
22#include <boost/graph/graph_traits.hpp>
23#include <boost/graph/properties.hpp>
24
25#include <LEDA/graph.h>
26#include <LEDA/node_array.h>
27#include <LEDA/node_map.h>
28
29// The functions and classes in this file allows the user to
30// treat a LEDA GRAPH object as a boost graph "as is". No
31// wrapper is needed for the GRAPH object.
32
33// Remember to define LEDA_PREFIX so that LEDA types such as
34// leda_edge show up as "leda_edge" and not just "edge".
35
36// Warning: this implementation relies on partial specialization
37// for the graph_traits class (so it won't compile with Visual C++)
38
39// Warning: this implementation is in alpha and has not been tested
40
41#if !defined BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
42namespace boost {
43
44 struct leda_graph_traversal_category :
45 public virtual bidirectional_graph_tag,
46 public virtual adjacency_graph_tag,
47 public virtual edge_list_graph_tag,
48 public virtual vertex_list_graph_tag { };
49
50 template <class vtype, class etype>
51 struct graph_traits< BOOST_GRAPH_LEDA_DECL(vtype,etype) > {
52 typedef leda_node vertex_descriptor;
53 typedef leda_edge edge_descriptor;
54
55 class adjacency_iterator
56 : public iterator_facade<adjacency_iterator,
57 leda_node,
58 bidirectional_traversal_tag,
59 leda_node>
60 {
61 public:
62 explicit adjacency_iterator(leda_edge edge = 0) : base(edge) {}
63
64 private:
65 leda_node dereference() const { return BOOST_GRAPH_LEDA_NAMESPACE::target(base); }
66
67 bool equal(const adjacency_iterator& other) const
68 { return base == other.base; }
69
70 void increment() { base = Succ_Adj_Edge(base, 0); }
71 void decrement() { base = Pred_Adj_Edge(base, 0); }
72
73 leda_edge base;
74
75 friend class iterator_core_access;
76 };
77
78 class out_edge_iterator
79 : public iterator_facade<out_edge_iterator,
80 leda_edge,
81 bidirectional_traversal_tag,
82 leda_edge>
83 {
84 public:
85 explicit out_edge_iterator(leda_edge edge = 0) : base(edge) {}
86
87 private:
88 leda_edge dereference() const { return base; }
89
90 bool equal(const out_edge_iterator& other) const
91 { return base == other.base; }
92
93 void increment() { base = Succ_Adj_Edge(base, 0); }
94 void decrement() { base = Pred_Adj_Edge(base, 0); }
95
96 leda_edge base;
97
98 friend class iterator_core_access;
99 };
100
101 class in_edge_iterator
102 : public iterator_facade<in_edge_iterator,
103 leda_edge,
104 bidirectional_traversal_tag,
105 leda_edge>
106 {
107 public:
108 explicit in_edge_iterator(leda_edge edge = 0) : base(edge) {}
109
110 private:
111 leda_edge dereference() const { return base; }
112
113 bool equal(const in_edge_iterator& other) const
114 { return base == other.base; }
115
116 void increment() { base = Succ_Adj_Edge(base, 1); }
117 void decrement() { base = Pred_Adj_Edge(base, 1); }
118
119 leda_edge base;
120
121 friend class iterator_core_access;
122 };
123
124 class edge_iterator
125 : public iterator_facade<edge_iterator,
126 leda_edge,
127 bidirectional_traversal_tag,
128 leda_edge>
129 {
130 public:
131 explicit edge_iterator(leda_edge edge = 0) : base(edge) {}
132
133 private:
134 leda_edge dereference() const { return base; }
135
136 bool equal(const edge_iterator& other) const
137 { return base == other.base; }
138
139 void increment() { base = graph_of(base)->succ_edge(base); }
140 void decrement() { base = graph_of(base)->pred_edge(base); }
141
142 leda_edge base;
143
144 friend class iterator_core_access;
145 };
146
147 class vertex_iterator
148 : public iterator_facade<vertex_iterator,
149 leda_node,
150 bidirectional_traversal_tag,
151 leda_node>
152 {
153 public:
154 explicit vertex_iterator(leda_node node = 0) : base(node) {}
155
156 private:
157 leda_node dereference() const { return base; }
158
159 bool equal(const vertex_iterator& other) const
160 { return base == other.base; }
161
162 void increment() { base = graph_of(base)->succ_node(base); }
163 void decrement() { base = graph_of(base)->pred_node(base); }
164
165 leda_node base;
166
167 friend class iterator_core_access;
168 };
169
170 typedef directed_tag directed_category;
171 typedef allow_parallel_edge_tag edge_parallel_category; // not sure here
172 typedef leda_graph_traversal_category traversal_category;
173 typedef int vertices_size_type;
174 typedef int edges_size_type;
175 typedef int degree_size_type;
176 };
177
178 template <class vtype, class etype>
179 struct vertex_property< BOOST_GRAPH_LEDA_DECL(vtype,etype) > {
180 typedef vtype type;
181 };
182
183 template <class vtype, class etype>
184 struct edge_property< BOOST_GRAPH_LEDA_DECL(vtype,etype) > {
185 typedef etype type;
186 };
187
188} // namespace boost
189#endif
190
191namespace boost {
192
193 template <class vtype, class etype>
194 typename graph_traits< BOOST_GRAPH_LEDA_DECL(vtype,etype) >::vertex_descriptor
195 source(typename graph_traits< BOOST_GRAPH_LEDA_DECL(vtype,etype) >::edge_descriptor e,
196 const BOOST_GRAPH_LEDA_DECL(vtype,etype)& g)
197 {
198 return source(e);
199 }
200
201 template <class vtype, class etype>
202 typename graph_traits< BOOST_GRAPH_LEDA_DECL(vtype,etype) >::vertex_descriptor
203 target(typename graph_traits< BOOST_GRAPH_LEDA_DECL(vtype,etype) >::edge_descriptor e,
204 const BOOST_GRAPH_LEDA_DECL(vtype,etype)& g)
205 {
206 return target(e);
207 }
208
209 template <class vtype, class etype>
210 inline std::pair<
211 typename graph_traits< BOOST_GRAPH_LEDA_DECL(vtype,etype) >::vertex_iterator,
212 typename graph_traits< BOOST_GRAPH_LEDA_DECL(vtype,etype) >::vertex_iterator >
213 vertices(const BOOST_GRAPH_LEDA_DECL(vtype,etype)& g)
214 {
215 typedef typename graph_traits< BOOST_GRAPH_LEDA_DECL(vtype,etype) >::vertex_iterator
216 Iter;
217 return std::make_pair( Iter(g.first_node()), Iter(0) );
218 }
219
220 template <class vtype, class etype>
221 inline std::pair<
222 typename graph_traits< BOOST_GRAPH_LEDA_DECL(vtype,etype) >::edge_iterator,
223 typename graph_traits< BOOST_GRAPH_LEDA_DECL(vtype,etype) >::edge_iterator >
224 edges(const BOOST_GRAPH_LEDA_DECL(vtype,etype)& g)
225 {
226 typedef typename graph_traits< BOOST_GRAPH_LEDA_DECL(vtype,etype) >::edge_iterator
227 Iter;
228 return std::make_pair( Iter(g.first_edge()), Iter(0) );
229 }
230
231 template <class vtype, class etype>
232 inline std::pair<
233 typename graph_traits< BOOST_GRAPH_LEDA_DECL(vtype,etype) >::out_edge_iterator,
234 typename graph_traits< BOOST_GRAPH_LEDA_DECL(vtype,etype) >::out_edge_iterator >
235 out_edges(
236 typename graph_traits< BOOST_GRAPH_LEDA_DECL(vtype,etype) >::vertex_descriptor u,
237 const BOOST_GRAPH_LEDA_DECL(vtype,etype)& g)
238 {
239 typedef typename graph_traits< BOOST_GRAPH_LEDA_DECL(vtype,etype) >
240 ::out_edge_iterator Iter;
241 return std::make_pair( Iter(First_Adj_Edge(u,0)), Iter(0) );
242 }
243
244 template <class vtype, class etype>
245 inline std::pair<
246 typename graph_traits< BOOST_GRAPH_LEDA_DECL(vtype,etype) >::in_edge_iterator,
247 typename graph_traits< BOOST_GRAPH_LEDA_DECL(vtype,etype) >::in_edge_iterator >
248 in_edges(
249 typename graph_traits< BOOST_GRAPH_LEDA_DECL(vtype,etype) >::vertex_descriptor u,
250 const BOOST_GRAPH_LEDA_DECL(vtype,etype)& g)
251 {
252 typedef typename graph_traits< BOOST_GRAPH_LEDA_DECL(vtype,etype) >
253 ::in_edge_iterator Iter;
254 return std::make_pair( Iter(First_Adj_Edge(u,1)), Iter(0) );
255 }
256
257 template <class vtype, class etype>
258 inline std::pair<
259 typename graph_traits< BOOST_GRAPH_LEDA_DECL(vtype,etype) >::adjacency_iterator,
260 typename graph_traits< BOOST_GRAPH_LEDA_DECL(vtype,etype) >::adjacency_iterator >
261 adjacent_vertices(
262 typename graph_traits< BOOST_GRAPH_LEDA_DECL(vtype,etype) >::vertex_descriptor u,
263 const BOOST_GRAPH_LEDA_DECL(vtype,etype)& g)
264 {
265 typedef typename graph_traits< BOOST_GRAPH_LEDA_DECL(vtype,etype) >
266 ::adjacency_iterator Iter;
267 return std::make_pair( Iter(First_Adj_Edge(u,0)), Iter(0) );
268 }
269
270 template <class vtype, class etype>
271 typename graph_traits< BOOST_GRAPH_LEDA_DECL(vtype,etype) >::vertices_size_type
272 num_vertices(const BOOST_GRAPH_LEDA_DECL(vtype,etype)& g)
273 {
274 return g.number_of_nodes();
275 }
276
277 template <class vtype, class etype>
278 typename graph_traits< BOOST_GRAPH_LEDA_DECL(vtype,etype) >::edges_size_type
279 num_edges(const BOOST_GRAPH_LEDA_DECL(vtype,etype)& g)
280 {
281 return g.number_of_edges();
282 }
283
284 template <class vtype, class etype>
285 typename graph_traits< BOOST_GRAPH_LEDA_DECL(vtype,etype) >::degree_size_type
286 out_degree(
287 typename graph_traits< BOOST_GRAPH_LEDA_DECL(vtype,etype) >::vertex_descriptor u,
288 const BOOST_GRAPH_LEDA_DECL(vtype,etype)&)
289 {
290 return outdeg(u);
291 }
292
293 template <class vtype, class etype>
294 typename graph_traits< BOOST_GRAPH_LEDA_DECL(vtype,etype) >::degree_size_type
295 in_degree(
296 typename graph_traits< BOOST_GRAPH_LEDA_DECL(vtype,etype) >::vertex_descriptor u,
297 const BOOST_GRAPH_LEDA_DECL(vtype,etype)&)
298 {
299 return indeg(u);
300 }
301
302 template <class vtype, class etype>
303 typename graph_traits< BOOST_GRAPH_LEDA_DECL(vtype,etype) >::degree_size_type
304 degree(
305 typename graph_traits< BOOST_GRAPH_LEDA_DECL(vtype,etype) >::vertex_descriptor u,
306 const BOOST_GRAPH_LEDA_DECL(vtype,etype)&)
307 {
308 return outdeg(u) + indeg(u);
309 }
310
311 template <class vtype, class etype>
312 typename graph_traits< BOOST_GRAPH_LEDA_DECL(vtype,etype) >::vertex_descriptor
313 add_vertex(BOOST_GRAPH_LEDA_DECL(vtype,etype)& g)
314 {
315 return g.new_node();
316 }
317
318 template <class vtype, class etype>
319 typename graph_traits< BOOST_GRAPH_LEDA_DECL(vtype,etype) >::vertex_descriptor
320 add_vertex(const vtype& vp, BOOST_GRAPH_LEDA_DECL(vtype,etype)& g)
321 {
322 return g.new_node(vp);
323 }
324
325 // Hmm, LEDA doesn't have the equivalent of clear_vertex() -JGS
326 // need to write an implementation
327 template <class vtype, class etype>
328 void clear_vertex(
329 typename graph_traits< BOOST_GRAPH_LEDA_DECL(vtype,etype) >::vertex_descriptor u,
330 BOOST_GRAPH_LEDA_DECL(vtype,etype)& g)
331 {
332 g.del_node(u);
333 }
334
335 template <class vtype, class etype>
336 void remove_vertex(
337 typename graph_traits< BOOST_GRAPH_LEDA_DECL(vtype,etype) >::vertex_descriptor u,
338 BOOST_GRAPH_LEDA_DECL(vtype,etype)& g)
339 {
340 g.del_node(u);
341 }
342
343 template <class vtype, class etype>
344 std::pair<
345 typename graph_traits< BOOST_GRAPH_LEDA_DECL(vtype,etype) >::edge_descriptor,
346 bool>
347 add_edge(
348 typename graph_traits< BOOST_GRAPH_LEDA_DECL(vtype,etype) >::vertex_descriptor u,
349 typename graph_traits< BOOST_GRAPH_LEDA_DECL(vtype,etype) >::vertex_descriptor v,
350 BOOST_GRAPH_LEDA_DECL(vtype,etype)& g)
351 {
352 return std::make_pair(g.new_edge(u, v), true);
353 }
354
355 template <class vtype, class etype>
356 std::pair<
357 typename graph_traits< BOOST_GRAPH_LEDA_DECL(vtype,etype) >::edge_descriptor,
358 bool>
359 add_edge(
360 typename graph_traits< BOOST_GRAPH_LEDA_DECL(vtype,etype) >::vertex_descriptor u,
361 typename graph_traits< BOOST_GRAPH_LEDA_DECL(vtype,etype) >::vertex_descriptor v,
362 const etype& et,
363 BOOST_GRAPH_LEDA_DECL(vtype,etype)& g)
364 {
365 return std::make_pair(g.new_edge(u, v, et), true);
366 }
367
368 template <class vtype, class etype>
369 void
370 remove_edge(
371 typename graph_traits< BOOST_GRAPH_LEDA_DECL(vtype,etype) >::vertex_descriptor u,
372 typename graph_traits< BOOST_GRAPH_LEDA_DECL(vtype,etype) >::vertex_descriptor v,
373 BOOST_GRAPH_LEDA_DECL(vtype,etype)& g)
374 {
375 typename graph_traits< BOOST_GRAPH_LEDA_DECL(vtype,etype) >::out_edge_iterator
376 i,iend;
377 for (boost::tie(i,iend) = out_edges(u,g); i != iend; ++i)
378 if (target(*i,g) == v)
379 g.del_edge(*i);
380 }
381
382 template <class vtype, class etype>
383 void
384 remove_edge(
385 typename graph_traits< BOOST_GRAPH_LEDA_DECL(vtype,etype) >::edge_descriptor e,
386 BOOST_GRAPH_LEDA_DECL(vtype,etype)& g)
387 {
388 g.del_edge(e);
389 }
390
391 //===========================================================================
392 // property maps
393
394 class leda_graph_id_map
395 : public put_get_helper<int, leda_graph_id_map>
396 {
397 public:
398 typedef readable_property_map_tag category;
399 typedef int value_type;
400 typedef int reference;
401 typedef leda_node key_type;
402 leda_graph_id_map() { }
403 template <class T>
404 long operator[](T x) const { return x->id(); }
405 };
406 template <class vtype, class etype>
407 inline leda_graph_id_map
408 get(vertex_index_t, const BOOST_GRAPH_LEDA_DECL(vtype,etype)& g) {
409 return leda_graph_id_map();
410 }
411 template <class vtype, class etype>
412 inline leda_graph_id_map
413 get(edge_index_t, const BOOST_GRAPH_LEDA_DECL(vtype,etype)& g) {
414 return leda_graph_id_map();
415 }
416
417 template <class Tag>
418 struct leda_property_map { };
419
420 template <>
421 struct leda_property_map<vertex_index_t> {
422 template <class vtype, class etype>
423 struct bind_ {
424 typedef leda_graph_id_map type;
425 typedef leda_graph_id_map const_type;
426 };
427 };
428 template <>
429 struct leda_property_map<edge_index_t> {
430 template <class vtype, class etype>
431 struct bind_ {
432 typedef leda_graph_id_map type;
433 typedef leda_graph_id_map const_type;
434 };
435 };
436
437
438 template <class Data, class DataRef, class GraphPtr>
439 class leda_graph_data_map
440 : public put_get_helper<DataRef,
441 leda_graph_data_map<Data,DataRef,GraphPtr> >
442 {
443 public:
444 typedef Data value_type;
445 typedef DataRef reference;
446 typedef void key_type;
447 typedef lvalue_property_map_tag category;
448 leda_graph_data_map(GraphPtr g) : m_g(g) { }
449 template <class NodeOrEdge>
450 DataRef operator[](NodeOrEdge x) const { return (*m_g)[x]; }
451 protected:
452 GraphPtr m_g;
453 };
454
455 template <>
456 struct leda_property_map<vertex_all_t> {
457 template <class vtype, class etype>
458 struct bind_ {
459 typedef leda_graph_data_map<vtype, vtype&, BOOST_GRAPH_LEDA_DECL(vtype,etype)*> type;
460 typedef leda_graph_data_map<vtype, const vtype&,
461 const BOOST_GRAPH_LEDA_DECL(vtype,etype)*> const_type;
462 };
463 };
464 template <class vtype, class etype >
465 inline typename property_map< BOOST_GRAPH_LEDA_DECL(vtype,etype), vertex_all_t>::type
466 get(vertex_all_t, BOOST_GRAPH_LEDA_DECL(vtype,etype)& g) {
467 typedef typename property_map< BOOST_GRAPH_LEDA_DECL(vtype,etype), vertex_all_t>::type
468 pmap_type;
469 return pmap_type(&g);
470 }
471 template <class vtype, class etype >
472 inline typename property_map< BOOST_GRAPH_LEDA_DECL(vtype,etype), vertex_all_t>::const_type
473 get(vertex_all_t, const BOOST_GRAPH_LEDA_DECL(vtype,etype)& g) {
474 typedef typename property_map< BOOST_GRAPH_LEDA_DECL(vtype,etype),
475 vertex_all_t>::const_type pmap_type;
476 return pmap_type(&g);
477 }
478
479 template <>
480 struct leda_property_map<edge_all_t> {
481 template <class vtype, class etype>
482 struct bind_ {
483 typedef leda_graph_data_map<etype, etype&, BOOST_GRAPH_LEDA_DECL(vtype,etype)*> type;
484 typedef leda_graph_data_map<etype, const etype&,
485 const BOOST_GRAPH_LEDA_DECL(vtype,etype)*> const_type;
486 };
487 };
488 template <class vtype, class etype >
489 inline typename property_map< BOOST_GRAPH_LEDA_DECL(vtype,etype), edge_all_t>::type
490 get(edge_all_t, BOOST_GRAPH_LEDA_DECL(vtype,etype)& g) {
491 typedef typename property_map< BOOST_GRAPH_LEDA_DECL(vtype,etype), edge_all_t>::type
492 pmap_type;
493 return pmap_type(&g);
494 }
495 template <class vtype, class etype >
496 inline typename property_map< BOOST_GRAPH_LEDA_DECL(vtype,etype), edge_all_t>::const_type
497 get(edge_all_t, const BOOST_GRAPH_LEDA_DECL(vtype,etype)& g) {
498 typedef typename property_map< BOOST_GRAPH_LEDA_DECL(vtype,etype),
499 edge_all_t>::const_type pmap_type;
500 return pmap_type(&g);
501 }
502
503 // property map interface to the LEDA node_array class
504
505 template <class E, class ERef, class NodeMapPtr>
506 class leda_node_property_map
507 : public put_get_helper<ERef, leda_node_property_map<E, ERef, NodeMapPtr> >
508 {
509 public:
510 typedef E value_type;
511 typedef ERef reference;
512 typedef leda_node key_type;
513 typedef lvalue_property_map_tag category;
514 leda_node_property_map(NodeMapPtr a) : m_array(a) { }
515 ERef operator[](leda_node n) const { return (*m_array)[n]; }
516 protected:
517 NodeMapPtr m_array;
518 };
519 template <class E>
520 leda_node_property_map<E, const E&, const leda_node_array<E>*>
521 make_leda_node_property_map(const leda_node_array<E>& a)
522 {
523 typedef leda_node_property_map<E, const E&, const leda_node_array<E>*>
524 pmap_type;
525 return pmap_type(&a);
526 }
527 template <class E>
528 leda_node_property_map<E, E&, leda_node_array<E>*>
529 make_leda_node_property_map(leda_node_array<E>& a)
530 {
531 typedef leda_node_property_map<E, E&, leda_node_array<E>*> pmap_type;
532 return pmap_type(&a);
533 }
534
535 template <class E>
536 leda_node_property_map<E, const E&, const leda_node_map<E>*>
537 make_leda_node_property_map(const leda_node_map<E>& a)
538 {
539 typedef leda_node_property_map<E,const E&,const leda_node_map<E>*>
540 pmap_type;
541 return pmap_type(&a);
542 }
543 template <class E>
544 leda_node_property_map<E, E&, leda_node_map<E>*>
545 make_leda_node_property_map(leda_node_map<E>& a)
546 {
547 typedef leda_node_property_map<E, E&, leda_node_map<E>*> pmap_type;
548 return pmap_type(&a);
549 }
550
551 // g++ 'enumeral_type' in template unification not implemented workaround
552 template <class vtype, class etype, class Tag>
553 struct property_map<BOOST_GRAPH_LEDA_DECL(vtype,etype), Tag> {
554 typedef typename
555 leda_property_map<Tag>::template bind_<vtype, etype> map_gen;
556 typedef typename map_gen::type type;
557 typedef typename map_gen::const_type const_type;
558 };
559
560 template <class vtype, class etype, class PropertyTag, class Key>
561 inline
562 typename boost::property_traits<
563 typename boost::property_map<BOOST_GRAPH_LEDA_DECL(vtype,etype),PropertyTag>::const_type
564 >::value_type
565 get(PropertyTag p, const BOOST_GRAPH_LEDA_DECL(vtype,etype)& g, const Key& key) {
566 return get(get(p, g), key);
567 }
568
569 template <class vtype, class etype, class PropertyTag, class Key,class Value>
570 inline void
571 put(PropertyTag p, BOOST_GRAPH_LEDA_DECL(vtype,etype)& g,
572 const Key& key, const Value& value)
573 {
574 typedef typename property_map<BOOST_GRAPH_LEDA_DECL(vtype,etype), PropertyTag>::type Map;
575 Map pmap = get(p, g);
576 put(pmap, key, value);
577 }
578
579} // namespace boost
580
581
582#endif // BOOST_GRAPH_LEDA_HPP