]>
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 | ||
f67539c2 TL |
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 | { | |
7c673cae FG |
45 | typedef leda::node vertex_descriptor; |
46 | typedef leda::edge edge_descriptor; | |
47 | ||
f67539c2 TL |
48 | class adjacency_iterator |
49 | : public iterator_facade< adjacency_iterator, leda::node, | |
50 | bidirectional_traversal_tag, leda::node, const leda::node* > | |
7c673cae FG |
51 | { |
52 | public: | |
f67539c2 TL |
53 | adjacency_iterator( |
54 | leda::node node = 0, const leda::GRAPH< vtype, etype >* g = 0) | |
55 | : base(node), g(g) | |
56 | { | |
57 | } | |
58 | ||
7c673cae | 59 | private: |
f67539c2 | 60 | leda::node dereference() const { return leda::target(base); } |
7c673cae | 61 | |
f67539c2 TL |
62 | bool equal(const adjacency_iterator& other) const |
63 | { | |
64 | return base == other.base; | |
65 | } | |
7c673cae | 66 | |
f67539c2 TL |
67 | void increment() { base = g->adj_succ(base); } |
68 | void decrement() { base = g->adj_pred(base); } | |
7c673cae | 69 | |
f67539c2 TL |
70 | leda::edge base; |
71 | const leda::GRAPH< vtype, etype >* g; | |
7c673cae | 72 | |
f67539c2 | 73 | friend class iterator_core_access; |
7c673cae FG |
74 | }; |
75 | ||
f67539c2 TL |
76 | class out_edge_iterator |
77 | : public iterator_facade< out_edge_iterator, leda::edge, | |
78 | bidirectional_traversal_tag, const leda::edge&, const leda::edge* > | |
7c673cae FG |
79 | { |
80 | public: | |
f67539c2 TL |
81 | out_edge_iterator( |
82 | leda::node node = 0, const leda::GRAPH< vtype, etype >* g = 0) | |
83 | : base(node), g(g) | |
84 | { | |
85 | } | |
7c673cae FG |
86 | |
87 | private: | |
f67539c2 | 88 | const leda::edge& dereference() const { return base; } |
7c673cae | 89 | |
f67539c2 TL |
90 | bool equal(const out_edge_iterator& other) const |
91 | { | |
92 | return base == other.base; | |
93 | } | |
7c673cae | 94 | |
f67539c2 TL |
95 | void increment() { base = g->adj_succ(base); } |
96 | void decrement() { base = g->adj_pred(base); } | |
7c673cae | 97 | |
f67539c2 TL |
98 | leda::edge base; |
99 | const leda::GRAPH< vtype, etype >* g; | |
7c673cae | 100 | |
f67539c2 | 101 | friend class iterator_core_access; |
7c673cae FG |
102 | }; |
103 | ||
f67539c2 TL |
104 | class in_edge_iterator |
105 | : public iterator_facade< in_edge_iterator, leda::edge, | |
106 | bidirectional_traversal_tag, const leda::edge&, const leda::edge* > | |
7c673cae FG |
107 | { |
108 | public: | |
f67539c2 TL |
109 | in_edge_iterator( |
110 | leda::node node = 0, const leda::GRAPH< vtype, etype >* g = 0) | |
111 | : base(node), g(g) | |
112 | { | |
113 | } | |
7c673cae FG |
114 | |
115 | private: | |
f67539c2 | 116 | const leda::edge& dereference() const { return base; } |
7c673cae | 117 | |
f67539c2 TL |
118 | bool equal(const in_edge_iterator& other) const |
119 | { | |
120 | return base == other.base; | |
121 | } | |
7c673cae | 122 | |
f67539c2 TL |
123 | void increment() { base = g->in_succ(base); } |
124 | void decrement() { base = g->in_pred(base); } | |
7c673cae | 125 | |
f67539c2 TL |
126 | leda::edge base; |
127 | const leda::GRAPH< vtype, etype >* g; | |
7c673cae | 128 | |
f67539c2 | 129 | friend class iterator_core_access; |
7c673cae FG |
130 | }; |
131 | ||
f67539c2 TL |
132 | class vertex_iterator |
133 | : public iterator_facade< vertex_iterator, leda::node, | |
134 | bidirectional_traversal_tag, const leda::node&, const leda::node* > | |
7c673cae FG |
135 | { |
136 | public: | |
f67539c2 TL |
137 | vertex_iterator( |
138 | leda::node node = 0, const leda::GRAPH< vtype, etype >* g = 0) | |
139 | : base(node), g(g) | |
140 | { | |
141 | } | |
7c673cae FG |
142 | |
143 | private: | |
f67539c2 | 144 | const leda::node& dereference() const { return base; } |
7c673cae | 145 | |
f67539c2 TL |
146 | bool equal(const vertex_iterator& other) const |
147 | { | |
148 | return base == other.base; | |
149 | } | |
7c673cae | 150 | |
f67539c2 TL |
151 | void increment() { base = g->succ_node(base); } |
152 | void decrement() { base = g->pred_node(base); } | |
7c673cae | 153 | |
f67539c2 TL |
154 | leda::node base; |
155 | const leda::GRAPH< vtype, etype >* g; | |
7c673cae | 156 | |
f67539c2 | 157 | friend class iterator_core_access; |
7c673cae FG |
158 | }; |
159 | ||
f67539c2 TL |
160 | class edge_iterator |
161 | : public iterator_facade< edge_iterator, leda::edge, | |
162 | bidirectional_traversal_tag, const leda::edge&, const leda::edge* > | |
7c673cae FG |
163 | { |
164 | public: | |
f67539c2 TL |
165 | edge_iterator( |
166 | leda::edge edge = 0, const leda::GRAPH< vtype, etype >* g = 0) | |
167 | : base(edge), g(g) | |
168 | { | |
169 | } | |
7c673cae FG |
170 | |
171 | private: | |
f67539c2 | 172 | const leda::edge& dereference() const { return base; } |
7c673cae | 173 | |
f67539c2 TL |
174 | bool equal(const edge_iterator& other) const |
175 | { | |
176 | return base == other.base; | |
177 | } | |
7c673cae | 178 | |
f67539c2 TL |
179 | void increment() { base = g->succ_edge(base); } |
180 | void decrement() { base = g->pred_edge(base); } | |
7c673cae | 181 | |
f67539c2 TL |
182 | leda::node base; |
183 | const leda::GRAPH< vtype, etype >* g; | |
7c673cae | 184 | |
f67539c2 | 185 | friend class iterator_core_access; |
7c673cae FG |
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; | |
f67539c2 | 194 | }; |
7c673cae | 195 | |
f67539c2 TL |
196 | template <> struct graph_traits< leda::graph > |
197 | { | |
7c673cae FG |
198 | typedef leda::node vertex_descriptor; |
199 | typedef leda::edge edge_descriptor; | |
200 | ||
f67539c2 TL |
201 | class adjacency_iterator |
202 | : public iterator_facade< adjacency_iterator, leda::node, | |
203 | bidirectional_traversal_tag, leda::node, const leda::node* > | |
7c673cae FG |
204 | { |
205 | public: | |
f67539c2 TL |
206 | adjacency_iterator(leda::edge edge = 0, const leda::graph* g = 0) |
207 | : base(edge), g(g) | |
208 | { | |
209 | } | |
7c673cae FG |
210 | |
211 | private: | |
f67539c2 | 212 | leda::node dereference() const { return leda::target(base); } |
7c673cae | 213 | |
f67539c2 TL |
214 | bool equal(const adjacency_iterator& other) const |
215 | { | |
216 | return base == other.base; | |
217 | } | |
7c673cae | 218 | |
f67539c2 TL |
219 | void increment() { base = g->adj_succ(base); } |
220 | void decrement() { base = g->adj_pred(base); } | |
7c673cae | 221 | |
f67539c2 TL |
222 | leda::edge base; |
223 | const leda::graph* g; | |
7c673cae | 224 | |
f67539c2 | 225 | friend class iterator_core_access; |
7c673cae FG |
226 | }; |
227 | ||
f67539c2 TL |
228 | class out_edge_iterator |
229 | : public iterator_facade< out_edge_iterator, leda::edge, | |
230 | bidirectional_traversal_tag, const leda::edge&, const leda::edge* > | |
7c673cae FG |
231 | { |
232 | public: | |
f67539c2 TL |
233 | out_edge_iterator(leda::edge edge = 0, const leda::graph* g = 0) |
234 | : base(edge), g(g) | |
235 | { | |
236 | } | |
7c673cae FG |
237 | |
238 | private: | |
f67539c2 | 239 | const leda::edge& dereference() const { return base; } |
7c673cae | 240 | |
f67539c2 TL |
241 | bool equal(const out_edge_iterator& other) const |
242 | { | |
243 | return base == other.base; | |
244 | } | |
7c673cae | 245 | |
f67539c2 TL |
246 | void increment() { base = g->adj_succ(base); } |
247 | void decrement() { base = g->adj_pred(base); } | |
7c673cae | 248 | |
f67539c2 TL |
249 | leda::edge base; |
250 | const leda::graph* g; | |
7c673cae | 251 | |
f67539c2 | 252 | friend class iterator_core_access; |
7c673cae FG |
253 | }; |
254 | ||
f67539c2 TL |
255 | class in_edge_iterator |
256 | : public iterator_facade< in_edge_iterator, leda::edge, | |
257 | bidirectional_traversal_tag, const leda::edge&, const leda::edge* > | |
7c673cae FG |
258 | { |
259 | public: | |
f67539c2 TL |
260 | in_edge_iterator(leda::edge edge = 0, const leda::graph* g = 0) |
261 | : base(edge), g(g) | |
262 | { | |
263 | } | |
7c673cae FG |
264 | |
265 | private: | |
f67539c2 | 266 | const leda::edge& dereference() const { return base; } |
7c673cae | 267 | |
f67539c2 TL |
268 | bool equal(const in_edge_iterator& other) const |
269 | { | |
270 | return base == other.base; | |
271 | } | |
7c673cae | 272 | |
f67539c2 TL |
273 | void increment() { base = g->in_succ(base); } |
274 | void decrement() { base = g->in_pred(base); } | |
7c673cae | 275 | |
f67539c2 TL |
276 | leda::edge base; |
277 | const leda::graph* g; | |
7c673cae | 278 | |
f67539c2 | 279 | friend class iterator_core_access; |
7c673cae FG |
280 | }; |
281 | ||
f67539c2 TL |
282 | class vertex_iterator |
283 | : public iterator_facade< vertex_iterator, leda::node, | |
284 | bidirectional_traversal_tag, const leda::node&, const leda::node* > | |
7c673cae FG |
285 | { |
286 | public: | |
f67539c2 TL |
287 | vertex_iterator(leda::node node = 0, const leda::graph* g = 0) |
288 | : base(node), g(g) | |
289 | { | |
290 | } | |
7c673cae FG |
291 | |
292 | private: | |
f67539c2 | 293 | const leda::node& dereference() const { return base; } |
7c673cae | 294 | |
f67539c2 TL |
295 | bool equal(const vertex_iterator& other) const |
296 | { | |
297 | return base == other.base; | |
298 | } | |
7c673cae | 299 | |
f67539c2 TL |
300 | void increment() { base = g->succ_node(base); } |
301 | void decrement() { base = g->pred_node(base); } | |
7c673cae | 302 | |
f67539c2 TL |
303 | leda::node base; |
304 | const leda::graph* g; | |
7c673cae | 305 | |
f67539c2 | 306 | friend class iterator_core_access; |
7c673cae FG |
307 | }; |
308 | ||
f67539c2 TL |
309 | class edge_iterator |
310 | : public iterator_facade< edge_iterator, leda::edge, | |
311 | bidirectional_traversal_tag, const leda::edge&, const leda::edge* > | |
7c673cae FG |
312 | { |
313 | public: | |
f67539c2 TL |
314 | edge_iterator(leda::edge edge = 0, const leda::graph* g = 0) |
315 | : base(edge), g(g) | |
316 | { | |
317 | } | |
7c673cae FG |
318 | |
319 | private: | |
f67539c2 | 320 | const leda::edge& dereference() const { return base; } |
7c673cae | 321 | |
f67539c2 TL |
322 | bool equal(const edge_iterator& other) const |
323 | { | |
324 | return base == other.base; | |
325 | } | |
7c673cae | 326 | |
f67539c2 TL |
327 | void increment() { base = g->succ_edge(base); } |
328 | void decrement() { base = g->pred_edge(base); } | |
7c673cae | 329 | |
f67539c2 TL |
330 | leda::edge base; |
331 | const leda::graph* g; | |
7c673cae | 332 | |
f67539c2 | 333 | friend class iterator_core_access; |
7c673cae FG |
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; | |
f67539c2 | 342 | }; |
7c673cae FG |
343 | |
344 | } // namespace boost | |
345 | ||
f67539c2 TL |
346 | namespace boost |
347 | { | |
7c673cae | 348 | |
f67539c2 TL |
349 | //=========================================================================== |
350 | // functions for GRAPH<vtype,etype> | |
7c673cae | 351 | |
f67539c2 TL |
352 | template < class vtype, class etype > |
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 | { | |
7c673cae | 357 | return source(e); |
f67539c2 | 358 | } |
7c673cae | 359 | |
f67539c2 TL |
360 | template < class vtype, class etype > |
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 | { | |
7c673cae | 365 | return target(e); |
f67539c2 TL |
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 > | |
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 > | |
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 > | |
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 > | |
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 > | |
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 | |
435 | num_vertices(const leda::GRAPH< vtype, etype >& g) | |
436 | { | |
7c673cae | 437 | return g.number_of_nodes(); |
f67539c2 | 438 | } |
7c673cae | 439 | |
f67539c2 TL |
440 | template < class vtype, class etype > |
441 | typename graph_traits< leda::GRAPH< vtype, etype > >::edges_size_type num_edges( | |
442 | const leda::GRAPH< vtype, etype >& g) | |
443 | { | |
7c673cae | 444 | return g.number_of_edges(); |
f67539c2 TL |
445 | } |
446 | ||
447 | template < class vtype, class etype > | |
448 | typename graph_traits< leda::GRAPH< vtype, etype > >::degree_size_type | |
449 | out_degree( | |
450 | typename graph_traits< leda::GRAPH< vtype, etype > >::vertex_descriptor u, | |
451 | const leda::GRAPH< vtype, etype >& g) | |
452 | { | |
7c673cae | 453 | return g.outdeg(u); |
f67539c2 TL |
454 | } |
455 | ||
456 | template < class vtype, class etype > | |
457 | typename graph_traits< leda::GRAPH< vtype, etype > >::degree_size_type | |
458 | in_degree( | |
459 | typename graph_traits< leda::GRAPH< vtype, etype > >::vertex_descriptor u, | |
460 | const leda::GRAPH< vtype, etype >& g) | |
461 | { | |
7c673cae | 462 | return g.indeg(u); |
f67539c2 TL |
463 | } |
464 | ||
465 | template < class vtype, class etype > | |
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 | { | |
7c673cae | 470 | return g.outdeg(u) + g.indeg(u); |
f67539c2 | 471 | } |
7c673cae | 472 | |
f67539c2 TL |
473 | template < class vtype, class etype > |
474 | typename graph_traits< leda::GRAPH< vtype, etype > >::vertex_descriptor | |
475 | add_vertex(leda::GRAPH< vtype, etype >& g) | |
476 | { | |
7c673cae | 477 | return g.new_node(); |
f67539c2 | 478 | } |
7c673cae | 479 | |
f67539c2 TL |
480 | template < class vtype, class etype > |
481 | typename graph_traits< leda::GRAPH< vtype, etype > >::vertex_descriptor | |
482 | add_vertex(const vtype& vp, leda::GRAPH< vtype, etype >& g) | |
483 | { | |
7c673cae | 484 | return g.new_node(vp); |
f67539c2 TL |
485 | } |
486 | ||
487 | template < class vtype, class etype > | |
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 > | |
504 | void remove_vertex( | |
505 | typename graph_traits< leda::GRAPH< vtype, etype > >::vertex_descriptor u, | |
506 | leda::GRAPH< vtype, etype >& g) | |
507 | { | |
7c673cae | 508 | g.del_node(u); |
f67539c2 TL |
509 | } |
510 | ||
511 | template < class vtype, class etype > | |
512 | std::pair< | |
513 | typename graph_traits< leda::GRAPH< vtype, etype > >::edge_descriptor, | |
514 | bool > | |
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 | { | |
7c673cae | 520 | return std::make_pair(g.new_edge(u, v), true); |
f67539c2 TL |
521 | } |
522 | ||
523 | template < class vtype, class etype > | |
524 | std::pair< | |
525 | typename graph_traits< leda::GRAPH< vtype, etype > >::edge_descriptor, | |
526 | bool > | |
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 | { | |
7c673cae | 532 | return std::make_pair(g.new_edge(u, v, et), true); |
f67539c2 TL |
533 | } |
534 | ||
535 | template < class vtype, class etype > | |
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 > | |
549 | void remove_edge( | |
550 | typename graph_traits< leda::GRAPH< vtype, etype > >::edge_descriptor e, | |
551 | leda::GRAPH< vtype, etype >& g) | |
552 | { | |
7c673cae | 553 | g.del_edge(e); |
f67539c2 | 554 | } |
7c673cae | 555 | |
f67539c2 TL |
556 | //=========================================================================== |
557 | // functions for graph (non-templated version) | |
7c673cae | 558 | |
f67539c2 TL |
559 | graph_traits< leda::graph >::vertex_descriptor source( |
560 | graph_traits< leda::graph >::edge_descriptor e, const leda::graph& g) | |
561 | { | |
7c673cae | 562 | return source(e); |
f67539c2 | 563 | } |
7c673cae | 564 | |
f67539c2 TL |
565 | graph_traits< leda::graph >::vertex_descriptor target( |
566 | graph_traits< leda::graph >::edge_descriptor e, const leda::graph& g) | |
567 | { | |
7c673cae | 568 | return target(e); |
f67539c2 TL |
569 | } |
570 | ||
571 | inline std::pair< graph_traits< leda::graph >::vertex_iterator, | |
572 | graph_traits< leda::graph >::vertex_iterator > | |
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 > | |
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 > | |
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 > | |
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 > | |
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 | ||
613 | graph_traits< leda::graph >::vertices_size_type num_vertices( | |
7c673cae | 614 | const leda::graph& g) |
f67539c2 | 615 | { |
7c673cae | 616 | return g.number_of_nodes(); |
f67539c2 | 617 | } |
7c673cae | 618 | |
f67539c2 TL |
619 | graph_traits< leda::graph >::edges_size_type num_edges(const leda::graph& g) |
620 | { | |
7c673cae | 621 | return g.number_of_edges(); |
f67539c2 | 622 | } |
7c673cae | 623 | |
f67539c2 TL |
624 | graph_traits< leda::graph >::degree_size_type out_degree( |
625 | graph_traits< leda::graph >::vertex_descriptor u, const leda::graph& g) | |
626 | { | |
7c673cae | 627 | return g.outdeg(u); |
f67539c2 | 628 | } |
7c673cae | 629 | |
f67539c2 TL |
630 | graph_traits< leda::graph >::degree_size_type in_degree( |
631 | graph_traits< leda::graph >::vertex_descriptor u, const leda::graph& g) | |
632 | { | |
7c673cae | 633 | return g.indeg(u); |
f67539c2 | 634 | } |
7c673cae | 635 | |
f67539c2 TL |
636 | graph_traits< leda::graph >::degree_size_type degree( |
637 | graph_traits< leda::graph >::vertex_descriptor u, const leda::graph& g) | |
638 | { | |
7c673cae | 639 | return g.outdeg(u) + g.indeg(u); |
f67539c2 | 640 | } |
7c673cae | 641 | |
f67539c2 TL |
642 | graph_traits< leda::graph >::vertex_descriptor add_vertex(leda::graph& g) |
643 | { | |
7c673cae | 644 | return g.new_node(); |
f67539c2 TL |
645 | } |
646 | ||
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 | ||
656 | void remove_edge(graph_traits< leda::graph >::edge_descriptor e, leda::graph& g) | |
657 | { | |
7c673cae | 658 | g.del_edge(e); |
f67539c2 TL |
659 | } |
660 | ||
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 | ||
673 | void remove_vertex( | |
674 | graph_traits< leda::graph >::vertex_descriptor u, leda::graph& g) | |
675 | { | |
7c673cae | 676 | g.del_node(u); |
f67539c2 | 677 | } |
7c673cae | 678 | |
f67539c2 TL |
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 | } | |
7c673cae | 685 | |
f67539c2 TL |
686 | //=========================================================================== |
687 | // property maps for GRAPH<vtype,etype> | |
7c673cae | 688 | |
f67539c2 TL |
689 | class leda_graph_id_map : public put_get_helper< int, leda_graph_id_map > |
690 | { | |
691 | public: | |
7c673cae FG |
692 | typedef readable_property_map_tag category; |
693 | typedef int value_type; | |
694 | typedef int reference; | |
695 | typedef leda::node key_type; | |
f67539c2 TL |
696 | leda_graph_id_map() {} |
697 | template < class T > long operator[](T x) const { return x->id(); } | |
698 | }; | |
699 | template < class vtype, class etype > | |
700 | inline leda_graph_id_map get( | |
701 | vertex_index_t, const leda::GRAPH< vtype, etype >& g) | |
702 | { | |
7c673cae | 703 | return leda_graph_id_map(); |
f67539c2 TL |
704 | } |
705 | template < class vtype, class etype > | |
706 | inline leda_graph_id_map get(edge_index_t, const leda::GRAPH< vtype, etype >& g) | |
707 | { | |
7c673cae | 708 | return leda_graph_id_map(); |
f67539c2 | 709 | } |
7c673cae | 710 | |
f67539c2 TL |
711 | template < class Tag > struct leda_property_map |
712 | { | |
713 | }; | |
7c673cae | 714 | |
f67539c2 TL |
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; | |
7c673cae | 721 | }; |
f67539c2 TL |
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; | |
7c673cae | 729 | }; |
f67539c2 | 730 | }; |
7c673cae | 731 | |
f67539c2 TL |
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: | |
7c673cae FG |
737 | typedef Data value_type; |
738 | typedef DataRef reference; | |
739 | typedef void key_type; | |
740 | typedef lvalue_property_map_tag category; | |
f67539c2 TL |
741 | leda_graph_data_map(GraphPtr g) : m_g(g) {} |
742 | template < class NodeOrEdge > DataRef operator[](NodeOrEdge x) const | |
743 | { | |
744 | return (*m_g)[x]; | |
745 | } | |
746 | ||
747 | protected: | |
7c673cae | 748 | GraphPtr m_g; |
f67539c2 TL |
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; | |
7c673cae | 761 | }; |
f67539c2 TL |
762 | }; |
763 | template < class vtype, class etype > | |
764 | inline typename property_map< leda::GRAPH< vtype, etype >, vertex_all_t >::type | |
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; | |
7c673cae | 770 | return pmap_type(&g); |
f67539c2 TL |
771 | } |
772 | template < class vtype, class etype > | |
773 | inline typename property_map< leda::GRAPH< vtype, etype >, | |
774 | vertex_all_t >::const_type | |
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; | |
7c673cae | 779 | return pmap_type(&g); |
f67539c2 TL |
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; | |
7c673cae | 792 | }; |
f67539c2 TL |
793 | }; |
794 | template < class vtype, class etype > | |
795 | inline typename property_map< leda::GRAPH< vtype, etype >, edge_all_t >::type | |
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; | |
7c673cae | 801 | return pmap_type(&g); |
f67539c2 TL |
802 | } |
803 | template < class vtype, class etype > | |
804 | inline | |
805 | typename property_map< leda::GRAPH< vtype, etype >, edge_all_t >::const_type | |
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; | |
7c673cae | 810 | return pmap_type(&g); |
f67539c2 | 811 | } |
7c673cae | 812 | |
f67539c2 | 813 | // property map interface to the LEDA node_array class |
7c673cae | 814 | |
f67539c2 TL |
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: | |
7c673cae FG |
820 | typedef E value_type; |
821 | typedef ERef reference; | |
822 | typedef leda::node key_type; | |
823 | typedef lvalue_property_map_tag category; | |
f67539c2 | 824 | leda_node_property_map(NodeMapPtr a) : m_array(a) {} |
7c673cae | 825 | ERef operator[](leda::node n) const { return (*m_array)[n]; } |
f67539c2 TL |
826 | |
827 | protected: | |
7c673cae | 828 | NodeMapPtr m_array; |
f67539c2 TL |
829 | }; |
830 | template < class E > | |
831 | leda_node_property_map< E, const E&, const leda::node_array< E >* > | |
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; | |
7c673cae | 836 | return pmap_type(&a); |
f67539c2 TL |
837 | } |
838 | template < class E > | |
839 | leda_node_property_map< E, E&, leda::node_array< E >* > | |
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; | |
7c673cae | 843 | return pmap_type(&a); |
f67539c2 TL |
844 | } |
845 | ||
846 | template < class E > | |
847 | leda_node_property_map< E, const E&, const leda::node_map< E >* > | |
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; | |
7c673cae | 852 | return pmap_type(&a); |
f67539c2 TL |
853 | } |
854 | template < class E > | |
855 | leda_node_property_map< E, E&, leda::node_map< E >* > | |
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; | |
7c673cae | 859 | return pmap_type(&a); |
f67539c2 TL |
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; | |
7c673cae FG |
868 | typedef typename map_gen::type type; |
869 | typedef typename map_gen::const_type const_type; | |
f67539c2 TL |
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 | |
875 | get(PropertyTag p, const leda::GRAPH< vtype, etype >& g, const Key& key) | |
876 | { | |
7c673cae | 877 | return get(get(p, g), key); |
f67539c2 TL |
878 | } |
879 | ||
880 | template < class vtype, class etype, class PropertyTag, class Key, class 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; | |
7c673cae FG |
887 | Map pmap = get(p, g); |
888 | put(pmap, key, value); | |
f67539c2 | 889 | } |
7c673cae | 890 | |
f67539c2 | 891 | // property map interface to the LEDA edge_array class |
7c673cae | 892 | |
f67539c2 TL |
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: | |
7c673cae FG |
898 | typedef E value_type; |
899 | typedef ERef reference; | |
900 | typedef leda::edge key_type; | |
901 | typedef lvalue_property_map_tag category; | |
f67539c2 | 902 | leda_edge_property_map(EdgeMapPtr a) : m_array(a) {} |
7c673cae | 903 | ERef operator[](leda::edge n) const { return (*m_array)[n]; } |
f67539c2 TL |
904 | |
905 | protected: | |
7c673cae | 906 | EdgeMapPtr m_array; |
f67539c2 TL |
907 | }; |
908 | template < class E > | |
909 | leda_edge_property_map< E, const E&, const leda::edge_array< E >* > | |
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; | |
7c673cae | 914 | return pmap_type(&a); |
f67539c2 TL |
915 | } |
916 | template < class E > | |
917 | leda_edge_property_map< E, E&, leda::edge_array< E >* > | |
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; | |
7c673cae | 921 | return pmap_type(&a); |
f67539c2 TL |
922 | } |
923 | ||
924 | template < class E > | |
925 | leda_edge_property_map< E, const E&, const leda::edge_map< E >* > | |
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; | |
7c673cae | 930 | return pmap_type(&a); |
f67539c2 TL |
931 | } |
932 | template < class E > | |
933 | leda_edge_property_map< E, E&, leda::edge_map< E >* > | |
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; | |
7c673cae | 937 | return pmap_type(&a); |
f67539c2 | 938 | } |
7c673cae FG |
939 | |
940 | } // namespace boost | |
941 | ||
942 | #endif // BOOST_GRAPH_LEDA_HPP |