1 //=======================================================================
2 // Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
3 // Copyright 2004 The Trustees of Indiana University.
4 // Copyright 2007 University of Karlsruhe
5 // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek, Douglas Gregor,
6 // Jens Mueller
7 //
8 // Distributed under the Boost Software License, Version 1.0. (See
9 // accompanying file LICENSE_1_0.txt or copy at
10 // http://www.boost.org/LICENSE_1_0.txt)
11 //=======================================================================
12 #ifndef BOOST_GRAPH_LEDA_HPP
13 #define BOOST_GRAPH_LEDA_HPP
14
15 #include <boost/config.hpp>
16 #include <boost/iterator/iterator_facade.hpp>
17 #include <boost/graph/graph_traits.hpp>
18 #include <boost/graph/properties.hpp>
19
20 #include <LEDA/graph/graph.h>
21 #include <LEDA/graph/node_array.h>
22 #include <LEDA/graph/node_map.h>
23
24 // The functions and classes in this file allows the user to
25 // treat a LEDA GRAPH object as a boost graph "as is". No
26 // wrapper is needed for the GRAPH object.
27
28 // Warning: this implementation relies on partial specialization
29 // for the graph_traits class (so it won't compile with Visual C++)
30
31 // Warning: this implementation is in alpha and has not been tested
32
33 namespace boost
34 {
35
36 struct leda_graph_traversal_category : public virtual bidirectional_graph_tag,
37 public virtual adjacency_graph_tag,
38 public virtual vertex_list_graph_tag
39 {
40 };
41
42 template < class vtype, class etype >
43 struct graph_traits< leda::GRAPH< vtype, etype > >
44 {
45 typedef leda::node vertex_descriptor;
46 typedef leda::edge edge_descriptor;
47
48 class adjacency_iterator
49 : public iterator_facade< adjacency_iterator, leda::node,
50 bidirectional_traversal_tag, leda::node, const leda::node* >
51 {
52 public:
adjacency_iterator(leda::node node=0,const leda::GRAPH<vtype,etype> * g=0)53 adjacency_iterator(
54 leda::node node = 0, const leda::GRAPH< vtype, etype >* g = 0)
55 : base(node), g(g)
56 {
57 }
58
59 private:
dereference() const60 leda::node dereference() const { return leda::target(base); }
61
equal(const adjacency_iterator & other) const62 bool equal(const adjacency_iterator& other) const
63 {
64 return base == other.base;
65 }
66
increment()67 void increment() { base = g->adj_succ(base); }
decrement()68 void decrement() { base = g->adj_pred(base); }
69
70 leda::edge base;
71 const leda::GRAPH< vtype, etype >* g;
72
73 friend class iterator_core_access;
74 };
75
76 class out_edge_iterator
77 : public iterator_facade< out_edge_iterator, leda::edge,
78 bidirectional_traversal_tag, const leda::edge&, const leda::edge* >
79 {
80 public:
out_edge_iterator(leda::node node=0,const leda::GRAPH<vtype,etype> * g=0)81 out_edge_iterator(
82 leda::node node = 0, const leda::GRAPH< vtype, etype >* g = 0)
83 : base(node), g(g)
84 {
85 }
86
87 private:
dereference() const88 const leda::edge& dereference() const { return base; }
89
equal(const out_edge_iterator & other) const90 bool equal(const out_edge_iterator& other) const
91 {
92 return base == other.base;
93 }
94
increment()95 void increment() { base = g->adj_succ(base); }
decrement()96 void decrement() { base = g->adj_pred(base); }
97
98 leda::edge base;
99 const leda::GRAPH< vtype, etype >* g;
100
101 friend class iterator_core_access;
102 };
103
104 class in_edge_iterator
105 : public iterator_facade< in_edge_iterator, leda::edge,
106 bidirectional_traversal_tag, const leda::edge&, const leda::edge* >
107 {
108 public:
in_edge_iterator(leda::node node=0,const leda::GRAPH<vtype,etype> * g=0)109 in_edge_iterator(
110 leda::node node = 0, const leda::GRAPH< vtype, etype >* g = 0)
111 : base(node), g(g)
112 {
113 }
114
115 private:
dereference() const116 const leda::edge& dereference() const { return base; }
117
equal(const in_edge_iterator & other) const118 bool equal(const in_edge_iterator& other) const
119 {
120 return base == other.base;
121 }
122
increment()123 void increment() { base = g->in_succ(base); }
decrement()124 void decrement() { base = g->in_pred(base); }
125
126 leda::edge base;
127 const leda::GRAPH< vtype, etype >* g;
128
129 friend class iterator_core_access;
130 };
131
132 class vertex_iterator
133 : public iterator_facade< vertex_iterator, leda::node,
134 bidirectional_traversal_tag, const leda::node&, const leda::node* >
135 {
136 public:
vertex_iterator(leda::node node=0,const leda::GRAPH<vtype,etype> * g=0)137 vertex_iterator(
138 leda::node node = 0, const leda::GRAPH< vtype, etype >* g = 0)
139 : base(node), g(g)
140 {
141 }
142
143 private:
dereference() const144 const leda::node& dereference() const { return base; }
145
equal(const vertex_iterator & other) const146 bool equal(const vertex_iterator& other) const
147 {
148 return base == other.base;
149 }
150
increment()151 void increment() { base = g->succ_node(base); }
decrement()152 void decrement() { base = g->pred_node(base); }
153
154 leda::node base;
155 const leda::GRAPH< vtype, etype >* g;
156
157 friend class iterator_core_access;
158 };
159
160 class edge_iterator
161 : public iterator_facade< edge_iterator, leda::edge,
162 bidirectional_traversal_tag, const leda::edge&, const leda::edge* >
163 {
164 public:
edge_iterator(leda::edge edge=0,const leda::GRAPH<vtype,etype> * g=0)165 edge_iterator(
166 leda::edge edge = 0, const leda::GRAPH< vtype, etype >* g = 0)
167 : base(edge), g(g)
168 {
169 }
170
171 private:
dereference() const172 const leda::edge& dereference() const { return base; }
173
equal(const edge_iterator & other) const174 bool equal(const edge_iterator& other) const
175 {
176 return base == other.base;
177 }
178
increment()179 void increment() { base = g->succ_edge(base); }
decrement()180 void decrement() { base = g->pred_edge(base); }
181
182 leda::node base;
183 const leda::GRAPH< vtype, etype >* g;
184
185 friend class iterator_core_access;
186 };
187
188 typedef directed_tag directed_category;
189 typedef allow_parallel_edge_tag edge_parallel_category; // not sure here
190 typedef leda_graph_traversal_category traversal_category;
191 typedef int vertices_size_type;
192 typedef int edges_size_type;
193 typedef int degree_size_type;
194 };
195
196 template <> struct graph_traits< leda::graph >
197 {
198 typedef leda::node vertex_descriptor;
199 typedef leda::edge edge_descriptor;
200
201 class adjacency_iterator
202 : public iterator_facade< adjacency_iterator, leda::node,
203 bidirectional_traversal_tag, leda::node, const leda::node* >
204 {
205 public:
adjacency_iterator(leda::edge edge=0,const leda::graph * g=0)206 adjacency_iterator(leda::edge edge = 0, const leda::graph* g = 0)
207 : base(edge), g(g)
208 {
209 }
210
211 private:
dereference() const212 leda::node dereference() const { return leda::target(base); }
213
equal(const adjacency_iterator & other) const214 bool equal(const adjacency_iterator& other) const
215 {
216 return base == other.base;
217 }
218
increment()219 void increment() { base = g->adj_succ(base); }
decrement()220 void decrement() { base = g->adj_pred(base); }
221
222 leda::edge base;
223 const leda::graph* g;
224
225 friend class iterator_core_access;
226 };
227
228 class out_edge_iterator
229 : public iterator_facade< out_edge_iterator, leda::edge,
230 bidirectional_traversal_tag, const leda::edge&, const leda::edge* >
231 {
232 public:
out_edge_iterator(leda::edge edge=0,const leda::graph * g=0)233 out_edge_iterator(leda::edge edge = 0, const leda::graph* g = 0)
234 : base(edge), g(g)
235 {
236 }
237
238 private:
dereference() const239 const leda::edge& dereference() const { return base; }
240
equal(const out_edge_iterator & other) const241 bool equal(const out_edge_iterator& other) const
242 {
243 return base == other.base;
244 }
245
increment()246 void increment() { base = g->adj_succ(base); }
decrement()247 void decrement() { base = g->adj_pred(base); }
248
249 leda::edge base;
250 const leda::graph* g;
251
252 friend class iterator_core_access;
253 };
254
255 class in_edge_iterator
256 : public iterator_facade< in_edge_iterator, leda::edge,
257 bidirectional_traversal_tag, const leda::edge&, const leda::edge* >
258 {
259 public:
in_edge_iterator(leda::edge edge=0,const leda::graph * g=0)260 in_edge_iterator(leda::edge edge = 0, const leda::graph* g = 0)
261 : base(edge), g(g)
262 {
263 }
264
265 private:
dereference() const266 const leda::edge& dereference() const { return base; }
267
equal(const in_edge_iterator & other) const268 bool equal(const in_edge_iterator& other) const
269 {
270 return base == other.base;
271 }
272
increment()273 void increment() { base = g->in_succ(base); }
decrement()274 void decrement() { base = g->in_pred(base); }
275
276 leda::edge base;
277 const leda::graph* g;
278
279 friend class iterator_core_access;
280 };
281
282 class vertex_iterator
283 : public iterator_facade< vertex_iterator, leda::node,
284 bidirectional_traversal_tag, const leda::node&, const leda::node* >
285 {
286 public:
vertex_iterator(leda::node node=0,const leda::graph * g=0)287 vertex_iterator(leda::node node = 0, const leda::graph* g = 0)
288 : base(node), g(g)
289 {
290 }
291
292 private:
dereference() const293 const leda::node& dereference() const { return base; }
294
equal(const vertex_iterator & other) const295 bool equal(const vertex_iterator& other) const
296 {
297 return base == other.base;
298 }
299
increment()300 void increment() { base = g->succ_node(base); }
decrement()301 void decrement() { base = g->pred_node(base); }
302
303 leda::node base;
304 const leda::graph* g;
305
306 friend class iterator_core_access;
307 };
308
309 class edge_iterator
310 : public iterator_facade< edge_iterator, leda::edge,
311 bidirectional_traversal_tag, const leda::edge&, const leda::edge* >
312 {
313 public:
edge_iterator(leda::edge edge=0,const leda::graph * g=0)314 edge_iterator(leda::edge edge = 0, const leda::graph* g = 0)
315 : base(edge), g(g)
316 {
317 }
318
319 private:
dereference() const320 const leda::edge& dereference() const { return base; }
321
equal(const edge_iterator & other) const322 bool equal(const edge_iterator& other) const
323 {
324 return base == other.base;
325 }
326
increment()327 void increment() { base = g->succ_edge(base); }
decrement()328 void decrement() { base = g->pred_edge(base); }
329
330 leda::edge base;
331 const leda::graph* g;
332
333 friend class iterator_core_access;
334 };
335
336 typedef directed_tag directed_category;
337 typedef allow_parallel_edge_tag edge_parallel_category; // not sure here
338 typedef leda_graph_traversal_category traversal_category;
339 typedef int vertices_size_type;
340 typedef int edges_size_type;
341 typedef int degree_size_type;
342 };
343
344 } // namespace boost
345
346 namespace boost
347 {
348
349 //===========================================================================
350 // functions for GRAPH<vtype,etype>
351
352 template < class vtype, class etype >
source(typename graph_traits<leda::GRAPH<vtype,etype>>::edge_descriptor e,const leda::GRAPH<vtype,etype> & g)353 typename graph_traits< leda::GRAPH< vtype, etype > >::vertex_descriptor source(
354 typename graph_traits< leda::GRAPH< vtype, etype > >::edge_descriptor e,
355 const leda::GRAPH< vtype, etype >& g)
356 {
357 return source(e);
358 }
359
360 template < class vtype, class etype >
target(typename graph_traits<leda::GRAPH<vtype,etype>>::edge_descriptor e,const leda::GRAPH<vtype,etype> & g)361 typename graph_traits< leda::GRAPH< vtype, etype > >::vertex_descriptor target(
362 typename graph_traits< leda::GRAPH< vtype, etype > >::edge_descriptor e,
363 const leda::GRAPH< vtype, etype >& g)
364 {
365 return target(e);
366 }
367
368 template < class vtype, class etype >
369 inline std::pair<
370 typename graph_traits< leda::GRAPH< vtype, etype > >::vertex_iterator,
371 typename graph_traits< leda::GRAPH< vtype, etype > >::vertex_iterator >
vertices(const leda::GRAPH<vtype,etype> & g)372 vertices(const leda::GRAPH< vtype, etype >& g)
373 {
374 typedef
375 typename graph_traits< leda::GRAPH< vtype, etype > >::vertex_iterator
376 Iter;
377 return std::make_pair(Iter(g.first_node(), &g), Iter(0, &g));
378 }
379
380 template < class vtype, class etype >
381 inline std::pair<
382 typename graph_traits< leda::GRAPH< vtype, etype > >::edge_iterator,
383 typename graph_traits< leda::GRAPH< vtype, etype > >::edge_iterator >
edges(const leda::GRAPH<vtype,etype> & g)384 edges(const leda::GRAPH< vtype, etype >& g)
385 {
386 typedef typename graph_traits< leda::GRAPH< vtype, etype > >::edge_iterator
387 Iter;
388 return std::make_pair(Iter(g.first_edge(), &g), Iter(0, &g));
389 }
390
391 template < class vtype, class etype >
392 inline std::pair<
393 typename graph_traits< leda::GRAPH< vtype, etype > >::out_edge_iterator,
394 typename graph_traits< leda::GRAPH< vtype, etype > >::out_edge_iterator >
out_edges(typename graph_traits<leda::GRAPH<vtype,etype>>::vertex_descriptor u,const leda::GRAPH<vtype,etype> & g)395 out_edges(
396 typename graph_traits< leda::GRAPH< vtype, etype > >::vertex_descriptor u,
397 const leda::GRAPH< vtype, etype >& g)
398 {
399 typedef
400 typename graph_traits< leda::GRAPH< vtype, etype > >::out_edge_iterator
401 Iter;
402 return std::make_pair(Iter(g.first_adj_edge(u, 0), &g), Iter(0, &g));
403 }
404
405 template < class vtype, class etype >
406 inline std::pair<
407 typename graph_traits< leda::GRAPH< vtype, etype > >::in_edge_iterator,
408 typename graph_traits< leda::GRAPH< vtype, etype > >::in_edge_iterator >
in_edges(typename graph_traits<leda::GRAPH<vtype,etype>>::vertex_descriptor u,const leda::GRAPH<vtype,etype> & g)409 in_edges(
410 typename graph_traits< leda::GRAPH< vtype, etype > >::vertex_descriptor u,
411 const leda::GRAPH< vtype, etype >& g)
412 {
413 typedef
414 typename graph_traits< leda::GRAPH< vtype, etype > >::in_edge_iterator
415 Iter;
416 return std::make_pair(Iter(g.first_adj_edge(u, 1), &g), Iter(0, &g));
417 }
418
419 template < class vtype, class etype >
420 inline std::pair<
421 typename graph_traits< leda::GRAPH< vtype, etype > >::adjacency_iterator,
422 typename graph_traits< leda::GRAPH< vtype, etype > >::adjacency_iterator >
adjacent_vertices(typename graph_traits<leda::GRAPH<vtype,etype>>::vertex_descriptor u,const leda::GRAPH<vtype,etype> & g)423 adjacent_vertices(
424 typename graph_traits< leda::GRAPH< vtype, etype > >::vertex_descriptor u,
425 const leda::GRAPH< vtype, etype >& g)
426 {
427 typedef
428 typename graph_traits< leda::GRAPH< vtype, etype > >::adjacency_iterator
429 Iter;
430 return std::make_pair(Iter(g.first_adj_edge(u, 0), &g), Iter(0, &g));
431 }
432
433 template < class vtype, class etype >
434 typename graph_traits< leda::GRAPH< vtype, etype > >::vertices_size_type
num_vertices(const leda::GRAPH<vtype,etype> & g)435 num_vertices(const leda::GRAPH< vtype, etype >& g)
436 {
437 return g.number_of_nodes();
438 }
439
440 template < class vtype, class etype >
num_edges(const leda::GRAPH<vtype,etype> & g)441 typename graph_traits< leda::GRAPH< vtype, etype > >::edges_size_type num_edges(
442 const leda::GRAPH< vtype, etype >& g)
443 {
444 return g.number_of_edges();
445 }
446
447 template < class vtype, class etype >
448 typename graph_traits< leda::GRAPH< vtype, etype > >::degree_size_type
out_degree(typename graph_traits<leda::GRAPH<vtype,etype>>::vertex_descriptor u,const leda::GRAPH<vtype,etype> & g)449 out_degree(
450 typename graph_traits< leda::GRAPH< vtype, etype > >::vertex_descriptor u,
451 const leda::GRAPH< vtype, etype >& g)
452 {
453 return g.outdeg(u);
454 }
455
456 template < class vtype, class etype >
457 typename graph_traits< leda::GRAPH< vtype, etype > >::degree_size_type
in_degree(typename graph_traits<leda::GRAPH<vtype,etype>>::vertex_descriptor u,const leda::GRAPH<vtype,etype> & g)458 in_degree(
459 typename graph_traits< leda::GRAPH< vtype, etype > >::vertex_descriptor u,
460 const leda::GRAPH< vtype, etype >& g)
461 {
462 return g.indeg(u);
463 }
464
465 template < class vtype, class etype >
degree(typename graph_traits<leda::GRAPH<vtype,etype>>::vertex_descriptor u,const leda::GRAPH<vtype,etype> & g)466 typename graph_traits< leda::GRAPH< vtype, etype > >::degree_size_type degree(
467 typename graph_traits< leda::GRAPH< vtype, etype > >::vertex_descriptor u,
468 const leda::GRAPH< vtype, etype >& g)
469 {
470 return g.outdeg(u) + g.indeg(u);
471 }
472
473 template < class vtype, class etype >
474 typename graph_traits< leda::GRAPH< vtype, etype > >::vertex_descriptor
add_vertex(leda::GRAPH<vtype,etype> & g)475 add_vertex(leda::GRAPH< vtype, etype >& g)
476 {
477 return g.new_node();
478 }
479
480 template < class vtype, class etype >
481 typename graph_traits< leda::GRAPH< vtype, etype > >::vertex_descriptor
add_vertex(const vtype & vp,leda::GRAPH<vtype,etype> & g)482 add_vertex(const vtype& vp, leda::GRAPH< vtype, etype >& g)
483 {
484 return g.new_node(vp);
485 }
486
487 template < class vtype, class etype >
clear_vertex(typename graph_traits<leda::GRAPH<vtype,etype>>::vertex_descriptor u,leda::GRAPH<vtype,etype> & g)488 void clear_vertex(
489 typename graph_traits< leda::GRAPH< vtype, etype > >::vertex_descriptor u,
490 leda::GRAPH< vtype, etype >& g)
491 {
492 typename graph_traits< leda::GRAPH< vtype, etype > >::out_edge_iterator ei,
493 ei_end;
494 for (boost::tie(ei, ei_end) = out_edges(u, g); ei != ei_end; ei++)
495 remove_edge(*ei);
496
497 typename graph_traits< leda::GRAPH< vtype, etype > >::in_edge_iterator iei,
498 iei_end;
499 for (boost::tie(iei, iei_end) = in_edges(u, g); iei != iei_end; iei++)
500 remove_edge(*iei);
501 }
502
503 template < class vtype, class etype >
remove_vertex(typename graph_traits<leda::GRAPH<vtype,etype>>::vertex_descriptor u,leda::GRAPH<vtype,etype> & g)504 void remove_vertex(
505 typename graph_traits< leda::GRAPH< vtype, etype > >::vertex_descriptor u,
506 leda::GRAPH< vtype, etype >& g)
507 {
508 g.del_node(u);
509 }
510
511 template < class vtype, class etype >
512 std::pair<
513 typename graph_traits< leda::GRAPH< vtype, etype > >::edge_descriptor,
514 bool >
add_edge(typename graph_traits<leda::GRAPH<vtype,etype>>::vertex_descriptor u,typename graph_traits<leda::GRAPH<vtype,etype>>::vertex_descriptor v,leda::GRAPH<vtype,etype> & g)515 add_edge(
516 typename graph_traits< leda::GRAPH< vtype, etype > >::vertex_descriptor u,
517 typename graph_traits< leda::GRAPH< vtype, etype > >::vertex_descriptor v,
518 leda::GRAPH< vtype, etype >& g)
519 {
520 return std::make_pair(g.new_edge(u, v), true);
521 }
522
523 template < class vtype, class etype >
524 std::pair<
525 typename graph_traits< leda::GRAPH< vtype, etype > >::edge_descriptor,
526 bool >
add_edge(typename graph_traits<leda::GRAPH<vtype,etype>>::vertex_descriptor u,typename graph_traits<leda::GRAPH<vtype,etype>>::vertex_descriptor v,const etype & et,leda::GRAPH<vtype,etype> & g)527 add_edge(
528 typename graph_traits< leda::GRAPH< vtype, etype > >::vertex_descriptor u,
529 typename graph_traits< leda::GRAPH< vtype, etype > >::vertex_descriptor v,
530 const etype& et, leda::GRAPH< vtype, etype >& g)
531 {
532 return std::make_pair(g.new_edge(u, v, et), true);
533 }
534
535 template < class vtype, class etype >
remove_edge(typename graph_traits<leda::GRAPH<vtype,etype>>::vertex_descriptor u,typename graph_traits<leda::GRAPH<vtype,etype>>::vertex_descriptor v,leda::GRAPH<vtype,etype> & g)536 void remove_edge(
537 typename graph_traits< leda::GRAPH< vtype, etype > >::vertex_descriptor u,
538 typename graph_traits< leda::GRAPH< vtype, etype > >::vertex_descriptor v,
539 leda::GRAPH< vtype, etype >& g)
540 {
541 typename graph_traits< leda::GRAPH< vtype, etype > >::out_edge_iterator i,
542 iend;
543 for (boost::tie(i, iend) = out_edges(u, g); i != iend; ++i)
544 if (target(*i, g) == v)
545 g.del_edge(*i);
546 }
547
548 template < class vtype, class etype >
remove_edge(typename graph_traits<leda::GRAPH<vtype,etype>>::edge_descriptor e,leda::GRAPH<vtype,etype> & g)549 void remove_edge(
550 typename graph_traits< leda::GRAPH< vtype, etype > >::edge_descriptor e,
551 leda::GRAPH< vtype, etype >& g)
552 {
553 g.del_edge(e);
554 }
555
556 //===========================================================================
557 // functions for graph (non-templated version)
558
source(graph_traits<leda::graph>::edge_descriptor e,const leda::graph & g)559 graph_traits< leda::graph >::vertex_descriptor source(
560 graph_traits< leda::graph >::edge_descriptor e, const leda::graph& g)
561 {
562 return source(e);
563 }
564
target(graph_traits<leda::graph>::edge_descriptor e,const leda::graph & g)565 graph_traits< leda::graph >::vertex_descriptor target(
566 graph_traits< leda::graph >::edge_descriptor e, const leda::graph& g)
567 {
568 return target(e);
569 }
570
571 inline std::pair< graph_traits< leda::graph >::vertex_iterator,
572 graph_traits< leda::graph >::vertex_iterator >
vertices(const leda::graph & g)573 vertices(const leda::graph& g)
574 {
575 typedef graph_traits< leda::graph >::vertex_iterator Iter;
576 return std::make_pair(Iter(g.first_node(), &g), Iter(0, &g));
577 }
578
579 inline std::pair< graph_traits< leda::graph >::edge_iterator,
580 graph_traits< leda::graph >::edge_iterator >
edges(const leda::graph & g)581 edges(const leda::graph& g)
582 {
583 typedef graph_traits< leda::graph >::edge_iterator Iter;
584 return std::make_pair(Iter(g.first_edge(), &g), Iter(0, &g));
585 }
586
587 inline std::pair< graph_traits< leda::graph >::out_edge_iterator,
588 graph_traits< leda::graph >::out_edge_iterator >
out_edges(graph_traits<leda::graph>::vertex_descriptor u,const leda::graph & g)589 out_edges(
590 graph_traits< leda::graph >::vertex_descriptor u, const leda::graph& g)
591 {
592 typedef graph_traits< leda::graph >::out_edge_iterator Iter;
593 return std::make_pair(Iter(g.first_adj_edge(u), &g), Iter(0, &g));
594 }
595
596 inline std::pair< graph_traits< leda::graph >::in_edge_iterator,
597 graph_traits< leda::graph >::in_edge_iterator >
in_edges(graph_traits<leda::graph>::vertex_descriptor u,const leda::graph & g)598 in_edges(graph_traits< leda::graph >::vertex_descriptor u, const leda::graph& g)
599 {
600 typedef graph_traits< leda::graph >::in_edge_iterator Iter;
601 return std::make_pair(Iter(g.first_in_edge(u), &g), Iter(0, &g));
602 }
603
604 inline std::pair< graph_traits< leda::graph >::adjacency_iterator,
605 graph_traits< leda::graph >::adjacency_iterator >
adjacent_vertices(graph_traits<leda::graph>::vertex_descriptor u,const leda::graph & g)606 adjacent_vertices(
607 graph_traits< leda::graph >::vertex_descriptor u, const leda::graph& g)
608 {
609 typedef graph_traits< leda::graph >::adjacency_iterator Iter;
610 return std::make_pair(Iter(g.first_adj_edge(u), &g), Iter(0, &g));
611 }
612
num_vertices(const leda::graph & g)613 graph_traits< leda::graph >::vertices_size_type num_vertices(
614 const leda::graph& g)
615 {
616 return g.number_of_nodes();
617 }
618
num_edges(const leda::graph & g)619 graph_traits< leda::graph >::edges_size_type num_edges(const leda::graph& g)
620 {
621 return g.number_of_edges();
622 }
623
out_degree(graph_traits<leda::graph>::vertex_descriptor u,const leda::graph & g)624 graph_traits< leda::graph >::degree_size_type out_degree(
625 graph_traits< leda::graph >::vertex_descriptor u, const leda::graph& g)
626 {
627 return g.outdeg(u);
628 }
629
in_degree(graph_traits<leda::graph>::vertex_descriptor u,const leda::graph & g)630 graph_traits< leda::graph >::degree_size_type in_degree(
631 graph_traits< leda::graph >::vertex_descriptor u, const leda::graph& g)
632 {
633 return g.indeg(u);
634 }
635
degree(graph_traits<leda::graph>::vertex_descriptor u,const leda::graph & g)636 graph_traits< leda::graph >::degree_size_type degree(
637 graph_traits< leda::graph >::vertex_descriptor u, const leda::graph& g)
638 {
639 return g.outdeg(u) + g.indeg(u);
640 }
641
add_vertex(leda::graph & g)642 graph_traits< leda::graph >::vertex_descriptor add_vertex(leda::graph& g)
643 {
644 return g.new_node();
645 }
646
remove_edge(graph_traits<leda::graph>::vertex_descriptor u,graph_traits<leda::graph>::vertex_descriptor v,leda::graph & g)647 void remove_edge(graph_traits< leda::graph >::vertex_descriptor u,
648 graph_traits< leda::graph >::vertex_descriptor v, leda::graph& g)
649 {
650 graph_traits< leda::graph >::out_edge_iterator i, iend;
651 for (boost::tie(i, iend) = out_edges(u, g); i != iend; ++i)
652 if (target(*i, g) == v)
653 g.del_edge(*i);
654 }
655
remove_edge(graph_traits<leda::graph>::edge_descriptor e,leda::graph & g)656 void remove_edge(graph_traits< leda::graph >::edge_descriptor e, leda::graph& g)
657 {
658 g.del_edge(e);
659 }
660
clear_vertex(graph_traits<leda::graph>::vertex_descriptor u,leda::graph & g)661 void clear_vertex(
662 graph_traits< leda::graph >::vertex_descriptor u, leda::graph& g)
663 {
664 graph_traits< leda::graph >::out_edge_iterator ei, ei_end;
665 for (boost::tie(ei, ei_end) = out_edges(u, g); ei != ei_end; ei++)
666 remove_edge(*ei, g);
667
668 graph_traits< leda::graph >::in_edge_iterator iei, iei_end;
669 for (boost::tie(iei, iei_end) = in_edges(u, g); iei != iei_end; iei++)
670 remove_edge(*iei, g);
671 }
672
remove_vertex(graph_traits<leda::graph>::vertex_descriptor u,leda::graph & g)673 void remove_vertex(
674 graph_traits< leda::graph >::vertex_descriptor u, leda::graph& g)
675 {
676 g.del_node(u);
677 }
678
add_edge(graph_traits<leda::graph>::vertex_descriptor u,graph_traits<leda::graph>::vertex_descriptor v,leda::graph & g)679 std::pair< graph_traits< leda::graph >::edge_descriptor, bool > add_edge(
680 graph_traits< leda::graph >::vertex_descriptor u,
681 graph_traits< leda::graph >::vertex_descriptor v, leda::graph& g)
682 {
683 return std::make_pair(g.new_edge(u, v), true);
684 }
685
686 //===========================================================================
687 // property maps for GRAPH<vtype,etype>
688
689 class leda_graph_id_map : public put_get_helper< int, leda_graph_id_map >
690 {
691 public:
692 typedef readable_property_map_tag category;
693 typedef int value_type;
694 typedef int reference;
695 typedef leda::node key_type;
leda_graph_id_map()696 leda_graph_id_map() {}
operator [](T x) const697 template < class T > long operator[](T x) const { return x->id(); }
698 };
699 template < class vtype, class etype >
get(vertex_index_t,const leda::GRAPH<vtype,etype> & g)700 inline leda_graph_id_map get(
701 vertex_index_t, const leda::GRAPH< vtype, etype >& g)
702 {
703 return leda_graph_id_map();
704 }
705 template < class vtype, class etype >
get(edge_index_t,const leda::GRAPH<vtype,etype> & g)706 inline leda_graph_id_map get(edge_index_t, const leda::GRAPH< vtype, etype >& g)
707 {
708 return leda_graph_id_map();
709 }
710
711 template < class Tag > struct leda_property_map
712 {
713 };
714
715 template <> struct leda_property_map< vertex_index_t >
716 {
717 template < class vtype, class etype > struct bind_
718 {
719 typedef leda_graph_id_map type;
720 typedef leda_graph_id_map const_type;
721 };
722 };
723 template <> struct leda_property_map< edge_index_t >
724 {
725 template < class vtype, class etype > struct bind_
726 {
727 typedef leda_graph_id_map type;
728 typedef leda_graph_id_map const_type;
729 };
730 };
731
732 template < class Data, class DataRef, class GraphPtr >
733 class leda_graph_data_map : public put_get_helper< DataRef,
734 leda_graph_data_map< Data, DataRef, GraphPtr > >
735 {
736 public:
737 typedef Data value_type;
738 typedef DataRef reference;
739 typedef void key_type;
740 typedef lvalue_property_map_tag category;
leda_graph_data_map(GraphPtr g)741 leda_graph_data_map(GraphPtr g) : m_g(g) {}
operator [](NodeOrEdge x) const742 template < class NodeOrEdge > DataRef operator[](NodeOrEdge x) const
743 {
744 return (*m_g)[x];
745 }
746
747 protected:
748 GraphPtr m_g;
749 };
750
751 template <> struct leda_property_map< vertex_all_t >
752 {
753 template < class vtype, class etype > struct bind_
754 {
755 typedef leda_graph_data_map< vtype, vtype&,
756 leda::GRAPH< vtype, etype >* >
757 type;
758 typedef leda_graph_data_map< vtype, const vtype&,
759 const leda::GRAPH< vtype, etype >* >
760 const_type;
761 };
762 };
763 template < class vtype, class etype >
764 inline typename property_map< leda::GRAPH< vtype, etype >, vertex_all_t >::type
get(vertex_all_t,leda::GRAPH<vtype,etype> & g)765 get(vertex_all_t, leda::GRAPH< vtype, etype >& g)
766 {
767 typedef
768 typename property_map< leda::GRAPH< vtype, etype >, vertex_all_t >::type
769 pmap_type;
770 return pmap_type(&g);
771 }
772 template < class vtype, class etype >
773 inline typename property_map< leda::GRAPH< vtype, etype >,
774 vertex_all_t >::const_type
get(vertex_all_t,const leda::GRAPH<vtype,etype> & g)775 get(vertex_all_t, const leda::GRAPH< vtype, etype >& g)
776 {
777 typedef typename property_map< leda::GRAPH< vtype, etype >,
778 vertex_all_t >::const_type pmap_type;
779 return pmap_type(&g);
780 }
781
782 template <> struct leda_property_map< edge_all_t >
783 {
784 template < class vtype, class etype > struct bind_
785 {
786 typedef leda_graph_data_map< etype, etype&,
787 leda::GRAPH< vtype, etype >* >
788 type;
789 typedef leda_graph_data_map< etype, const etype&,
790 const leda::GRAPH< vtype, etype >* >
791 const_type;
792 };
793 };
794 template < class vtype, class etype >
795 inline typename property_map< leda::GRAPH< vtype, etype >, edge_all_t >::type
get(edge_all_t,leda::GRAPH<vtype,etype> & g)796 get(edge_all_t, leda::GRAPH< vtype, etype >& g)
797 {
798 typedef
799 typename property_map< leda::GRAPH< vtype, etype >, edge_all_t >::type
800 pmap_type;
801 return pmap_type(&g);
802 }
803 template < class vtype, class etype >
804 inline
805 typename property_map< leda::GRAPH< vtype, etype >, edge_all_t >::const_type
get(edge_all_t,const leda::GRAPH<vtype,etype> & g)806 get(edge_all_t, const leda::GRAPH< vtype, etype >& g)
807 {
808 typedef typename property_map< leda::GRAPH< vtype, etype >,
809 edge_all_t >::const_type pmap_type;
810 return pmap_type(&g);
811 }
812
813 // property map interface to the LEDA node_array class
814
815 template < class E, class ERef, class NodeMapPtr >
816 class leda_node_property_map
817 : public put_get_helper< ERef, leda_node_property_map< E, ERef, NodeMapPtr > >
818 {
819 public:
820 typedef E value_type;
821 typedef ERef reference;
822 typedef leda::node key_type;
823 typedef lvalue_property_map_tag category;
leda_node_property_map(NodeMapPtr a)824 leda_node_property_map(NodeMapPtr a) : m_array(a) {}
operator [](leda::node n) const825 ERef operator[](leda::node n) const { return (*m_array)[n]; }
826
827 protected:
828 NodeMapPtr m_array;
829 };
830 template < class E >
831 leda_node_property_map< E, const E&, const leda::node_array< E >* >
make_leda_node_property_map(const leda::node_array<E> & a)832 make_leda_node_property_map(const leda::node_array< E >& a)
833 {
834 typedef leda_node_property_map< E, const E&, const leda::node_array< E >* >
835 pmap_type;
836 return pmap_type(&a);
837 }
838 template < class E >
839 leda_node_property_map< E, E&, leda::node_array< E >* >
make_leda_node_property_map(leda::node_array<E> & a)840 make_leda_node_property_map(leda::node_array< E >& a)
841 {
842 typedef leda_node_property_map< E, E&, leda::node_array< E >* > pmap_type;
843 return pmap_type(&a);
844 }
845
846 template < class E >
847 leda_node_property_map< E, const E&, const leda::node_map< E >* >
make_leda_node_property_map(const leda::node_map<E> & a)848 make_leda_node_property_map(const leda::node_map< E >& a)
849 {
850 typedef leda_node_property_map< E, const E&, const leda::node_map< E >* >
851 pmap_type;
852 return pmap_type(&a);
853 }
854 template < class E >
855 leda_node_property_map< E, E&, leda::node_map< E >* >
make_leda_node_property_map(leda::node_map<E> & a)856 make_leda_node_property_map(leda::node_map< E >& a)
857 {
858 typedef leda_node_property_map< E, E&, leda::node_map< E >* > pmap_type;
859 return pmap_type(&a);
860 }
861
862 // g++ 'enumeral_type' in template unification not implemented workaround
863 template < class vtype, class etype, class Tag >
864 struct property_map< leda::GRAPH< vtype, etype >, Tag >
865 {
866 typedef typename leda_property_map< Tag >::template bind_< vtype, etype >
867 map_gen;
868 typedef typename map_gen::type type;
869 typedef typename map_gen::const_type const_type;
870 };
871
872 template < class vtype, class etype, class PropertyTag, class Key >
873 inline typename boost::property_traits< typename boost::property_map<
874 leda::GRAPH< vtype, etype >, PropertyTag >::const_type >::value_type
get(PropertyTag p,const leda::GRAPH<vtype,etype> & g,const Key & key)875 get(PropertyTag p, const leda::GRAPH< vtype, etype >& g, const Key& key)
876 {
877 return get(get(p, g), key);
878 }
879
880 template < class vtype, class etype, class PropertyTag, class Key, class Value >
put(PropertyTag p,leda::GRAPH<vtype,etype> & g,const Key & key,const Value & value)881 inline void put(PropertyTag p, leda::GRAPH< vtype, etype >& g, const Key& key,
882 const Value& value)
883 {
884 typedef
885 typename property_map< leda::GRAPH< vtype, etype >, PropertyTag >::type
886 Map;
887 Map pmap = get(p, g);
888 put(pmap, key, value);
889 }
890
891 // property map interface to the LEDA edge_array class
892
893 template < class E, class ERef, class EdgeMapPtr >
894 class leda_edge_property_map
895 : public put_get_helper< ERef, leda_edge_property_map< E, ERef, EdgeMapPtr > >
896 {
897 public:
898 typedef E value_type;
899 typedef ERef reference;
900 typedef leda::edge key_type;
901 typedef lvalue_property_map_tag category;
leda_edge_property_map(EdgeMapPtr a)902 leda_edge_property_map(EdgeMapPtr a) : m_array(a) {}
operator [](leda::edge n) const903 ERef operator[](leda::edge n) const { return (*m_array)[n]; }
904
905 protected:
906 EdgeMapPtr m_array;
907 };
908 template < class E >
909 leda_edge_property_map< E, const E&, const leda::edge_array< E >* >
make_leda_node_property_map(const leda::node_array<E> & a)910 make_leda_node_property_map(const leda::node_array< E >& a)
911 {
912 typedef leda_edge_property_map< E, const E&, const leda::node_array< E >* >
913 pmap_type;
914 return pmap_type(&a);
915 }
916 template < class E >
917 leda_edge_property_map< E, E&, leda::edge_array< E >* >
make_leda_edge_property_map(leda::edge_array<E> & a)918 make_leda_edge_property_map(leda::edge_array< E >& a)
919 {
920 typedef leda_edge_property_map< E, E&, leda::edge_array< E >* > pmap_type;
921 return pmap_type(&a);
922 }
923
924 template < class E >
925 leda_edge_property_map< E, const E&, const leda::edge_map< E >* >
make_leda_edge_property_map(const leda::edge_map<E> & a)926 make_leda_edge_property_map(const leda::edge_map< E >& a)
927 {
928 typedef leda_edge_property_map< E, const E&, const leda::edge_map< E >* >
929 pmap_type;
930 return pmap_type(&a);
931 }
932 template < class E >
933 leda_edge_property_map< E, E&, leda::edge_map< E >* >
make_leda_edge_property_map(leda::edge_map<E> & a)934 make_leda_edge_property_map(leda::edge_map< E >& a)
935 {
936 typedef leda_edge_property_map< E, E&, leda::edge_map< E >* > pmap_type;
937 return pmap_type(&a);
938 }
939
940 } // namespace boost
941
942 #endif // BOOST_GRAPH_LEDA_HPP
943