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