1 /* -*- C++ -*- |
|
2 * |
|
3 * This file is a part of LEMON, a generic C++ optimization library |
|
4 * |
|
5 * Copyright (C) 2003-2006 |
|
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport |
|
7 * (Egervary Research Group on Combinatorial Optimization, EGRES). |
|
8 * |
|
9 * Permission to use, modify and distribute this software is granted |
|
10 * provided that this copyright notice appears in all copies. For |
|
11 * precise terms see the accompanying LICENSE file. |
|
12 * |
|
13 * This software is provided "AS IS" with no warranty of any kind, |
|
14 * express or implied, and with no claim as to its suitability for any |
|
15 * purpose. |
|
16 * |
|
17 */ |
|
18 |
|
19 #ifndef LEMON_ITERABLE_GRAPH_EXTENDER_H |
|
20 #define LEMON_ITERABLE_GRAPH_EXTENDER_H |
|
21 |
|
22 #include <lemon/invalid.h> |
|
23 #include <lemon/utility.h> |
|
24 |
|
25 namespace lemon { |
|
26 |
|
27 template <typename _Base> |
|
28 class IterableGraphExtender : public _Base { |
|
29 public: |
|
30 |
|
31 /// Indicates that the graph is undirected. |
|
32 |
|
33 ///\todo Better name? |
|
34 /// |
|
35 ///\bug Should it be here? |
|
36 typedef False UTag; |
|
37 |
|
38 typedef _Base Parent; |
|
39 typedef IterableGraphExtender<_Base> Graph; |
|
40 |
|
41 typedef typename Parent::Node Node; |
|
42 typedef typename Parent::Edge Edge; |
|
43 |
|
44 |
|
45 class NodeIt : public Node { |
|
46 const Graph* graph; |
|
47 public: |
|
48 |
|
49 NodeIt() {} |
|
50 |
|
51 NodeIt(Invalid i) : Node(i) { } |
|
52 |
|
53 explicit NodeIt(const Graph& _graph) : graph(&_graph) { |
|
54 _graph.first(*static_cast<Node*>(this)); |
|
55 } |
|
56 |
|
57 NodeIt(const Graph& _graph, const Node& node) |
|
58 : Node(node), graph(&_graph) {} |
|
59 |
|
60 NodeIt& operator++() { |
|
61 graph->next(*this); |
|
62 return *this; |
|
63 } |
|
64 |
|
65 }; |
|
66 |
|
67 |
|
68 class EdgeIt : public Edge { |
|
69 const Graph* graph; |
|
70 public: |
|
71 |
|
72 EdgeIt() { } |
|
73 |
|
74 EdgeIt(Invalid i) : Edge(i) { } |
|
75 |
|
76 explicit EdgeIt(const Graph& _graph) : graph(&_graph) { |
|
77 _graph.first(*static_cast<Edge*>(this)); |
|
78 } |
|
79 |
|
80 EdgeIt(const Graph& _graph, const Edge& e) : |
|
81 Edge(e), graph(&_graph) { } |
|
82 |
|
83 EdgeIt& operator++() { |
|
84 graph->next(*this); |
|
85 return *this; |
|
86 } |
|
87 |
|
88 }; |
|
89 |
|
90 |
|
91 class OutEdgeIt : public Edge { |
|
92 const Graph* graph; |
|
93 public: |
|
94 |
|
95 OutEdgeIt() { } |
|
96 |
|
97 OutEdgeIt(Invalid i) : Edge(i) { } |
|
98 |
|
99 OutEdgeIt(const Graph& _graph, const Node& node) |
|
100 : graph(&_graph) { |
|
101 _graph.firstOut(*this, node); |
|
102 } |
|
103 |
|
104 OutEdgeIt(const Graph& _graph, const Edge& edge) |
|
105 : Edge(edge), graph(&_graph) {} |
|
106 |
|
107 OutEdgeIt& operator++() { |
|
108 graph->nextOut(*this); |
|
109 return *this; |
|
110 } |
|
111 |
|
112 }; |
|
113 |
|
114 |
|
115 class InEdgeIt : public Edge { |
|
116 const Graph* graph; |
|
117 public: |
|
118 |
|
119 InEdgeIt() { } |
|
120 |
|
121 InEdgeIt(Invalid i) : Edge(i) { } |
|
122 |
|
123 InEdgeIt(const Graph& _graph, const Node& node) |
|
124 : graph(&_graph) { |
|
125 _graph.firstIn(*this, node); |
|
126 } |
|
127 |
|
128 InEdgeIt(const Graph& _graph, const Edge& edge) : |
|
129 Edge(edge), graph(&_graph) {} |
|
130 |
|
131 InEdgeIt& operator++() { |
|
132 graph->nextIn(*this); |
|
133 return *this; |
|
134 } |
|
135 |
|
136 }; |
|
137 |
|
138 /// \brief Base node of the iterator |
|
139 /// |
|
140 /// Returns the base node (ie. the source in this case) of the iterator |
|
141 Node baseNode(const OutEdgeIt &e) const { |
|
142 return Parent::source((Edge)e); |
|
143 } |
|
144 /// \brief Running node of the iterator |
|
145 /// |
|
146 /// Returns the running node (ie. the target in this case) of the |
|
147 /// iterator |
|
148 Node runningNode(const OutEdgeIt &e) const { |
|
149 return Parent::target((Edge)e); |
|
150 } |
|
151 |
|
152 /// \brief Base node of the iterator |
|
153 /// |
|
154 /// Returns the base node (ie. the target in this case) of the iterator |
|
155 Node baseNode(const InEdgeIt &e) const { |
|
156 return Parent::target((Edge)e); |
|
157 } |
|
158 /// \brief Running node of the iterator |
|
159 /// |
|
160 /// Returns the running node (ie. the source in this case) of the |
|
161 /// iterator |
|
162 Node runningNode(const InEdgeIt &e) const { |
|
163 return Parent::source((Edge)e); |
|
164 } |
|
165 |
|
166 using Parent::first; |
|
167 |
|
168 /// \brief The opposite node on the given edge. |
|
169 /// |
|
170 /// Gives back the opposite on the given edge. |
|
171 Node oppositeNode(const Node& n, const Edge& e) const { |
|
172 if (Parent::source(e) == n) { |
|
173 return Parent::target(e); |
|
174 } else { |
|
175 return Parent::source(e); |
|
176 } |
|
177 } |
|
178 |
|
179 private: |
|
180 |
|
181 // void first(NodeIt &) const; |
|
182 // void first(EdgeIt &) const; |
|
183 // void first(OutEdgeIt &) const; |
|
184 // void first(InEdgeIt &) const; |
|
185 |
|
186 }; |
|
187 |
|
188 |
|
189 |
|
190 |
|
191 |
|
192 |
|
193 template <typename _Base> |
|
194 class IterableUGraphExtender : public IterableGraphExtender<_Base> { |
|
195 public: |
|
196 |
|
197 /// Indicates that the graph is undirected. |
|
198 |
|
199 ///\todo Better name? |
|
200 /// |
|
201 ///\bug Should it be here? |
|
202 ///\bug Should be tested in the concept checker whether it is defined |
|
203 ///correctly. |
|
204 typedef True UTag; |
|
205 |
|
206 typedef IterableGraphExtender<_Base> Parent; |
|
207 typedef IterableUGraphExtender<_Base> Graph; |
|
208 typedef typename Parent::Node Node; |
|
209 typedef typename Parent::Edge Edge; |
|
210 typedef typename Parent::UEdge UEdge; |
|
211 |
|
212 class UEdgeIt : public Parent::UEdge { |
|
213 const Graph* graph; |
|
214 public: |
|
215 |
|
216 UEdgeIt() { } |
|
217 |
|
218 UEdgeIt(Invalid i) : UEdge(i) { } |
|
219 |
|
220 explicit UEdgeIt(const Graph& _graph) : graph(&_graph) { |
|
221 _graph.first(*static_cast<UEdge*>(this)); |
|
222 } |
|
223 |
|
224 UEdgeIt(const Graph& _graph, const UEdge& e) : |
|
225 UEdge(e), graph(&_graph) { } |
|
226 |
|
227 UEdgeIt& operator++() { |
|
228 graph->next(*this); |
|
229 return *this; |
|
230 } |
|
231 |
|
232 }; |
|
233 |
|
234 class IncEdgeIt : public Parent::UEdge { |
|
235 const Graph* graph; |
|
236 bool direction; |
|
237 friend class IterableUGraphExtender; |
|
238 public: |
|
239 |
|
240 IncEdgeIt() { } |
|
241 |
|
242 IncEdgeIt(Invalid i) : UEdge(i), direction(false) { } |
|
243 |
|
244 IncEdgeIt(const Graph& _graph, const Node &n) : graph(&_graph) { |
|
245 _graph.firstInc(*this, direction, n); |
|
246 } |
|
247 |
|
248 IncEdgeIt(const Graph& _graph, const UEdge &ue, const Node &n) |
|
249 : graph(&_graph), UEdge(ue) { |
|
250 direction = (_graph.source(ue) == n); |
|
251 } |
|
252 |
|
253 IncEdgeIt& operator++() { |
|
254 graph->nextInc(*this, direction); |
|
255 return *this; |
|
256 } |
|
257 }; |
|
258 |
|
259 using Parent::baseNode; |
|
260 using Parent::runningNode; |
|
261 |
|
262 /// Base node of the iterator |
|
263 /// |
|
264 /// Returns the base node of the iterator |
|
265 Node baseNode(const IncEdgeIt &e) const { |
|
266 return e.direction ? source(e) : target(e); |
|
267 } |
|
268 /// Running node of the iterator |
|
269 /// |
|
270 /// Returns the running node of the iterator |
|
271 Node runningNode(const IncEdgeIt &e) const { |
|
272 return e.direction ? target(e) : source(e); |
|
273 } |
|
274 |
|
275 /// \brief The opposite node on the given undirected edge. |
|
276 /// |
|
277 /// Gives back the opposite on the given undirected edge. |
|
278 Node oppositeNode(const Node& n, const UEdge& e) const { |
|
279 if (Parent::source(e) == n) { |
|
280 return Parent::target(e); |
|
281 } else { |
|
282 return Parent::source(e); |
|
283 } |
|
284 } |
|
285 |
|
286 }; |
|
287 |
|
288 |
|
289 template <typename _Base> |
|
290 class IterableBpUGraphExtender : public _Base { |
|
291 public: |
|
292 typedef _Base Parent; |
|
293 typedef IterableBpUGraphExtender Graph; |
|
294 |
|
295 typedef typename Parent::Node Node; |
|
296 typedef typename Parent::ANode ANode; |
|
297 typedef typename Parent::BNode BNode; |
|
298 typedef typename Parent::Edge Edge; |
|
299 typedef typename Parent::UEdge UEdge; |
|
300 |
|
301 class NodeIt : public Node { |
|
302 const Graph* graph; |
|
303 public: |
|
304 |
|
305 NodeIt() { } |
|
306 |
|
307 NodeIt(Invalid i) : Node(INVALID) { } |
|
308 |
|
309 explicit NodeIt(const Graph& _graph) : graph(&_graph) { |
|
310 graph->first(static_cast<Node&>(*this)); |
|
311 } |
|
312 |
|
313 NodeIt(const Graph& _graph, const Node& node) |
|
314 : Node(node), graph(&_graph) { } |
|
315 |
|
316 NodeIt& operator++() { |
|
317 graph->next(*this); |
|
318 return *this; |
|
319 } |
|
320 |
|
321 }; |
|
322 |
|
323 class ANodeIt : public Node { |
|
324 friend class IterableBpUGraphExtender; |
|
325 const Graph* graph; |
|
326 public: |
|
327 |
|
328 ANodeIt() { } |
|
329 |
|
330 ANodeIt(Invalid i) : Node(INVALID) { } |
|
331 |
|
332 explicit ANodeIt(const Graph& _graph) : graph(&_graph) { |
|
333 graph->firstANode(static_cast<Node&>(*this)); |
|
334 } |
|
335 |
|
336 ANodeIt(const Graph& _graph, const Node& node) |
|
337 : Node(node), graph(&_graph) {} |
|
338 |
|
339 ANodeIt& operator++() { |
|
340 graph->nextANode(*this); |
|
341 return *this; |
|
342 } |
|
343 }; |
|
344 |
|
345 class BNodeIt : public Node { |
|
346 friend class IterableBpUGraphExtender; |
|
347 const Graph* graph; |
|
348 public: |
|
349 |
|
350 BNodeIt() { } |
|
351 |
|
352 BNodeIt(Invalid i) : Node(INVALID) { } |
|
353 |
|
354 explicit BNodeIt(const Graph& _graph) : graph(&_graph) { |
|
355 graph->firstBNode(static_cast<Node&>(*this)); |
|
356 } |
|
357 |
|
358 BNodeIt(const Graph& _graph, const Node& node) |
|
359 : Node(node), graph(&_graph) {} |
|
360 |
|
361 BNodeIt& operator++() { |
|
362 graph->nextBNode(*this); |
|
363 return *this; |
|
364 } |
|
365 }; |
|
366 |
|
367 class EdgeIt : public Edge { |
|
368 friend class IterableBpUGraphExtender; |
|
369 const Graph* graph; |
|
370 public: |
|
371 |
|
372 EdgeIt() { } |
|
373 |
|
374 EdgeIt(Invalid i) : Edge(INVALID) { } |
|
375 |
|
376 explicit EdgeIt(const Graph& _graph) : graph(&_graph) { |
|
377 graph->first(static_cast<Edge&>(*this)); |
|
378 } |
|
379 |
|
380 EdgeIt(const Graph& _graph, const Edge& edge) |
|
381 : Edge(edge), graph(&_graph) { } |
|
382 |
|
383 EdgeIt& operator++() { |
|
384 graph->next(*this); |
|
385 return *this; |
|
386 } |
|
387 |
|
388 }; |
|
389 |
|
390 class UEdgeIt : public UEdge { |
|
391 friend class IterableBpUGraphExtender; |
|
392 const Graph* graph; |
|
393 public: |
|
394 |
|
395 UEdgeIt() { } |
|
396 |
|
397 UEdgeIt(Invalid i) : UEdge(INVALID) { } |
|
398 |
|
399 explicit UEdgeIt(const Graph& _graph) : graph(&_graph) { |
|
400 graph->first(static_cast<UEdge&>(*this)); |
|
401 } |
|
402 |
|
403 UEdgeIt(const Graph& _graph, const UEdge& edge) |
|
404 : UEdge(edge), graph(&_graph) { } |
|
405 |
|
406 UEdgeIt& operator++() { |
|
407 graph->next(*this); |
|
408 return *this; |
|
409 } |
|
410 }; |
|
411 |
|
412 class OutEdgeIt : public Edge { |
|
413 friend class IterableBpUGraphExtender; |
|
414 const Graph* graph; |
|
415 public: |
|
416 |
|
417 OutEdgeIt() { } |
|
418 |
|
419 OutEdgeIt(Invalid i) : Edge(i) { } |
|
420 |
|
421 OutEdgeIt(const Graph& _graph, const Node& node) |
|
422 : graph(&_graph) { |
|
423 graph->firstOut(*this, node); |
|
424 } |
|
425 |
|
426 OutEdgeIt(const Graph& _graph, const Edge& edge) |
|
427 : Edge(edge), graph(&_graph) {} |
|
428 |
|
429 OutEdgeIt& operator++() { |
|
430 graph->nextOut(*this); |
|
431 return *this; |
|
432 } |
|
433 |
|
434 }; |
|
435 |
|
436 |
|
437 class InEdgeIt : public Edge { |
|
438 friend class IterableBpUGraphExtender; |
|
439 const Graph* graph; |
|
440 public: |
|
441 |
|
442 InEdgeIt() { } |
|
443 |
|
444 InEdgeIt(Invalid i) : Edge(i) { } |
|
445 |
|
446 InEdgeIt(const Graph& _graph, const Node& node) |
|
447 : graph(&_graph) { |
|
448 graph->firstIn(*this, node); |
|
449 } |
|
450 |
|
451 InEdgeIt(const Graph& _graph, const Edge& edge) : |
|
452 Edge(edge), graph(&_graph) {} |
|
453 |
|
454 InEdgeIt& operator++() { |
|
455 graph->nextIn(*this); |
|
456 return *this; |
|
457 } |
|
458 |
|
459 }; |
|
460 |
|
461 /// \brief Base node of the iterator |
|
462 /// |
|
463 /// Returns the base node (ie. the source in this case) of the iterator |
|
464 Node baseNode(const OutEdgeIt &e) const { |
|
465 return Parent::source((Edge&)e); |
|
466 } |
|
467 /// \brief Running node of the iterator |
|
468 /// |
|
469 /// Returns the running node (ie. the target in this case) of the |
|
470 /// iterator |
|
471 Node runningNode(const OutEdgeIt &e) const { |
|
472 return Parent::target((Edge&)e); |
|
473 } |
|
474 |
|
475 /// \brief Base node of the iterator |
|
476 /// |
|
477 /// Returns the base node (ie. the target in this case) of the iterator |
|
478 Node baseNode(const InEdgeIt &e) const { |
|
479 return Parent::target((Edge&)e); |
|
480 } |
|
481 /// \brief Running node of the iterator |
|
482 /// |
|
483 /// Returns the running node (ie. the source in this case) of the |
|
484 /// iterator |
|
485 Node runningNode(const InEdgeIt &e) const { |
|
486 return Parent::source((Edge&)e); |
|
487 } |
|
488 |
|
489 class IncEdgeIt : public Parent::UEdge { |
|
490 friend class IterableBpUGraphExtender; |
|
491 const Graph* graph; |
|
492 bool direction; |
|
493 public: |
|
494 |
|
495 IncEdgeIt() { } |
|
496 |
|
497 IncEdgeIt(Invalid i) : UEdge(i), direction(true) { } |
|
498 |
|
499 IncEdgeIt(const Graph& _graph, const Node &n) : graph(&_graph) { |
|
500 graph->firstInc(*this, direction, n); |
|
501 } |
|
502 |
|
503 IncEdgeIt(const Graph& _graph, const UEdge &ue, const Node &n) |
|
504 : graph(&_graph), UEdge(ue) { |
|
505 direction = (graph->source(ue) == n); |
|
506 } |
|
507 |
|
508 IncEdgeIt& operator++() { |
|
509 graph->nextInc(*this, direction); |
|
510 return *this; |
|
511 } |
|
512 }; |
|
513 |
|
514 |
|
515 /// Base node of the iterator |
|
516 /// |
|
517 /// Returns the base node of the iterator |
|
518 Node baseNode(const IncEdgeIt &e) const { |
|
519 return e.direction ? source(e) : target(e); |
|
520 } |
|
521 |
|
522 /// Running node of the iterator |
|
523 /// |
|
524 /// Returns the running node of the iterator |
|
525 Node runningNode(const IncEdgeIt &e) const { |
|
526 return e.direction ? target(e) : source(e); |
|
527 } |
|
528 |
|
529 }; |
|
530 |
|
531 } |
|
532 |
|
533 #endif // LEMON_GRAPH_EXTENDER_H |
|