|
1 /* -*- C++ -*- |
|
2 * |
|
3 * This file is a part of LEMON, a generic C++ optimization library |
|
4 * |
|
5 * Copyright (C) 2003-2008 |
|
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_BITS_GRAPH_ADAPTOR_EXTENDER_H |
|
20 #define LEMON_BITS_GRAPH_ADAPTOR_EXTENDER_H |
|
21 |
|
22 #include <lemon/core.h> |
|
23 #include <lemon/error.h> |
|
24 |
|
25 #include <lemon/bits/default_map.h> |
|
26 |
|
27 |
|
28 ///\ingroup digraphbits |
|
29 ///\file |
|
30 ///\brief Extenders for the digraph adaptor types |
|
31 namespace lemon { |
|
32 |
|
33 /// \ingroup digraphbits |
|
34 /// |
|
35 /// \brief Extender for the DigraphAdaptors |
|
36 template <typename _Digraph> |
|
37 class DigraphAdaptorExtender : public _Digraph { |
|
38 public: |
|
39 |
|
40 typedef _Digraph Parent; |
|
41 typedef _Digraph Digraph; |
|
42 typedef DigraphAdaptorExtender Adaptor; |
|
43 |
|
44 // Base extensions |
|
45 |
|
46 typedef typename Parent::Node Node; |
|
47 typedef typename Parent::Arc Arc; |
|
48 |
|
49 int maxId(Node) const { |
|
50 return Parent::maxNodeId(); |
|
51 } |
|
52 |
|
53 int maxId(Arc) const { |
|
54 return Parent::maxArcId(); |
|
55 } |
|
56 |
|
57 Node fromId(int id, Node) const { |
|
58 return Parent::nodeFromId(id); |
|
59 } |
|
60 |
|
61 Arc fromId(int id, Arc) const { |
|
62 return Parent::arcFromId(id); |
|
63 } |
|
64 |
|
65 Node oppositeNode(const Node &n, const Arc &e) const { |
|
66 if (n == Parent::source(e)) |
|
67 return Parent::target(e); |
|
68 else if(n==Parent::target(e)) |
|
69 return Parent::source(e); |
|
70 else |
|
71 return INVALID; |
|
72 } |
|
73 |
|
74 class NodeIt : public Node { |
|
75 const Adaptor* _adaptor; |
|
76 public: |
|
77 |
|
78 NodeIt() {} |
|
79 |
|
80 NodeIt(Invalid i) : Node(i) { } |
|
81 |
|
82 explicit NodeIt(const Adaptor& adaptor) : _adaptor(&adaptor) { |
|
83 _adaptor->first(static_cast<Node&>(*this)); |
|
84 } |
|
85 |
|
86 NodeIt(const Adaptor& adaptor, const Node& node) |
|
87 : Node(node), _adaptor(&adaptor) {} |
|
88 |
|
89 NodeIt& operator++() { |
|
90 _adaptor->next(*this); |
|
91 return *this; |
|
92 } |
|
93 |
|
94 }; |
|
95 |
|
96 |
|
97 class ArcIt : public Arc { |
|
98 const Adaptor* _adaptor; |
|
99 public: |
|
100 |
|
101 ArcIt() { } |
|
102 |
|
103 ArcIt(Invalid i) : Arc(i) { } |
|
104 |
|
105 explicit ArcIt(const Adaptor& adaptor) : _adaptor(&adaptor) { |
|
106 _adaptor->first(static_cast<Arc&>(*this)); |
|
107 } |
|
108 |
|
109 ArcIt(const Adaptor& adaptor, const Arc& e) : |
|
110 Arc(e), _adaptor(&adaptor) { } |
|
111 |
|
112 ArcIt& operator++() { |
|
113 _adaptor->next(*this); |
|
114 return *this; |
|
115 } |
|
116 |
|
117 }; |
|
118 |
|
119 |
|
120 class OutArcIt : public Arc { |
|
121 const Adaptor* _adaptor; |
|
122 public: |
|
123 |
|
124 OutArcIt() { } |
|
125 |
|
126 OutArcIt(Invalid i) : Arc(i) { } |
|
127 |
|
128 OutArcIt(const Adaptor& adaptor, const Node& node) |
|
129 : _adaptor(&adaptor) { |
|
130 _adaptor->firstOut(*this, node); |
|
131 } |
|
132 |
|
133 OutArcIt(const Adaptor& adaptor, const Arc& arc) |
|
134 : Arc(arc), _adaptor(&adaptor) {} |
|
135 |
|
136 OutArcIt& operator++() { |
|
137 _adaptor->nextOut(*this); |
|
138 return *this; |
|
139 } |
|
140 |
|
141 }; |
|
142 |
|
143 |
|
144 class InArcIt : public Arc { |
|
145 const Adaptor* _adaptor; |
|
146 public: |
|
147 |
|
148 InArcIt() { } |
|
149 |
|
150 InArcIt(Invalid i) : Arc(i) { } |
|
151 |
|
152 InArcIt(const Adaptor& adaptor, const Node& node) |
|
153 : _adaptor(&adaptor) { |
|
154 _adaptor->firstIn(*this, node); |
|
155 } |
|
156 |
|
157 InArcIt(const Adaptor& adaptor, const Arc& arc) : |
|
158 Arc(arc), _adaptor(&adaptor) {} |
|
159 |
|
160 InArcIt& operator++() { |
|
161 _adaptor->nextIn(*this); |
|
162 return *this; |
|
163 } |
|
164 |
|
165 }; |
|
166 |
|
167 /// \brief Base node of the iterator |
|
168 /// |
|
169 /// Returns the base node (ie. the source in this case) of the iterator |
|
170 Node baseNode(const OutArcIt &e) const { |
|
171 return Parent::source(e); |
|
172 } |
|
173 /// \brief Running node of the iterator |
|
174 /// |
|
175 /// Returns the running node (ie. the target in this case) of the |
|
176 /// iterator |
|
177 Node runningNode(const OutArcIt &e) const { |
|
178 return Parent::target(e); |
|
179 } |
|
180 |
|
181 /// \brief Base node of the iterator |
|
182 /// |
|
183 /// Returns the base node (ie. the target in this case) of the iterator |
|
184 Node baseNode(const InArcIt &e) const { |
|
185 return Parent::target(e); |
|
186 } |
|
187 /// \brief Running node of the iterator |
|
188 /// |
|
189 /// Returns the running node (ie. the source in this case) of the |
|
190 /// iterator |
|
191 Node runningNode(const InArcIt &e) const { |
|
192 return Parent::source(e); |
|
193 } |
|
194 |
|
195 }; |
|
196 |
|
197 |
|
198 /// \ingroup digraphbits |
|
199 /// |
|
200 /// \brief Extender for the GraphAdaptors |
|
201 template <typename _Graph> |
|
202 class GraphAdaptorExtender : public _Graph { |
|
203 public: |
|
204 |
|
205 typedef _Graph Parent; |
|
206 typedef _Graph Graph; |
|
207 typedef GraphAdaptorExtender Adaptor; |
|
208 |
|
209 typedef typename Parent::Node Node; |
|
210 typedef typename Parent::Arc Arc; |
|
211 typedef typename Parent::Edge Edge; |
|
212 |
|
213 // Graph extension |
|
214 |
|
215 int maxId(Node) const { |
|
216 return Parent::maxNodeId(); |
|
217 } |
|
218 |
|
219 int maxId(Arc) const { |
|
220 return Parent::maxArcId(); |
|
221 } |
|
222 |
|
223 int maxId(Edge) const { |
|
224 return Parent::maxEdgeId(); |
|
225 } |
|
226 |
|
227 Node fromId(int id, Node) const { |
|
228 return Parent::nodeFromId(id); |
|
229 } |
|
230 |
|
231 Arc fromId(int id, Arc) const { |
|
232 return Parent::arcFromId(id); |
|
233 } |
|
234 |
|
235 Edge fromId(int id, Edge) const { |
|
236 return Parent::edgeFromId(id); |
|
237 } |
|
238 |
|
239 Node oppositeNode(const Node &n, const Edge &e) const { |
|
240 if( n == Parent::u(e)) |
|
241 return Parent::v(e); |
|
242 else if( n == Parent::v(e)) |
|
243 return Parent::u(e); |
|
244 else |
|
245 return INVALID; |
|
246 } |
|
247 |
|
248 Arc oppositeArc(const Arc &a) const { |
|
249 return Parent::direct(a, !Parent::direction(a)); |
|
250 } |
|
251 |
|
252 using Parent::direct; |
|
253 Arc direct(const Edge &e, const Node &s) const { |
|
254 return Parent::direct(e, Parent::u(e) == s); |
|
255 } |
|
256 |
|
257 |
|
258 class NodeIt : public Node { |
|
259 const Adaptor* _adaptor; |
|
260 public: |
|
261 |
|
262 NodeIt() {} |
|
263 |
|
264 NodeIt(Invalid i) : Node(i) { } |
|
265 |
|
266 explicit NodeIt(const Adaptor& adaptor) : _adaptor(&adaptor) { |
|
267 _adaptor->first(static_cast<Node&>(*this)); |
|
268 } |
|
269 |
|
270 NodeIt(const Adaptor& adaptor, const Node& node) |
|
271 : Node(node), _adaptor(&adaptor) {} |
|
272 |
|
273 NodeIt& operator++() { |
|
274 _adaptor->next(*this); |
|
275 return *this; |
|
276 } |
|
277 |
|
278 }; |
|
279 |
|
280 |
|
281 class ArcIt : public Arc { |
|
282 const Adaptor* _adaptor; |
|
283 public: |
|
284 |
|
285 ArcIt() { } |
|
286 |
|
287 ArcIt(Invalid i) : Arc(i) { } |
|
288 |
|
289 explicit ArcIt(const Adaptor& adaptor) : _adaptor(&adaptor) { |
|
290 _adaptor->first(static_cast<Arc&>(*this)); |
|
291 } |
|
292 |
|
293 ArcIt(const Adaptor& adaptor, const Arc& e) : |
|
294 Arc(e), _adaptor(&adaptor) { } |
|
295 |
|
296 ArcIt& operator++() { |
|
297 _adaptor->next(*this); |
|
298 return *this; |
|
299 } |
|
300 |
|
301 }; |
|
302 |
|
303 |
|
304 class OutArcIt : public Arc { |
|
305 const Adaptor* _adaptor; |
|
306 public: |
|
307 |
|
308 OutArcIt() { } |
|
309 |
|
310 OutArcIt(Invalid i) : Arc(i) { } |
|
311 |
|
312 OutArcIt(const Adaptor& adaptor, const Node& node) |
|
313 : _adaptor(&adaptor) { |
|
314 _adaptor->firstOut(*this, node); |
|
315 } |
|
316 |
|
317 OutArcIt(const Adaptor& adaptor, const Arc& arc) |
|
318 : Arc(arc), _adaptor(&adaptor) {} |
|
319 |
|
320 OutArcIt& operator++() { |
|
321 _adaptor->nextOut(*this); |
|
322 return *this; |
|
323 } |
|
324 |
|
325 }; |
|
326 |
|
327 |
|
328 class InArcIt : public Arc { |
|
329 const Adaptor* _adaptor; |
|
330 public: |
|
331 |
|
332 InArcIt() { } |
|
333 |
|
334 InArcIt(Invalid i) : Arc(i) { } |
|
335 |
|
336 InArcIt(const Adaptor& adaptor, const Node& node) |
|
337 : _adaptor(&adaptor) { |
|
338 _adaptor->firstIn(*this, node); |
|
339 } |
|
340 |
|
341 InArcIt(const Adaptor& adaptor, const Arc& arc) : |
|
342 Arc(arc), _adaptor(&adaptor) {} |
|
343 |
|
344 InArcIt& operator++() { |
|
345 _adaptor->nextIn(*this); |
|
346 return *this; |
|
347 } |
|
348 |
|
349 }; |
|
350 |
|
351 class EdgeIt : public Parent::Edge { |
|
352 const Adaptor* _adaptor; |
|
353 public: |
|
354 |
|
355 EdgeIt() { } |
|
356 |
|
357 EdgeIt(Invalid i) : Edge(i) { } |
|
358 |
|
359 explicit EdgeIt(const Adaptor& adaptor) : _adaptor(&adaptor) { |
|
360 _adaptor->first(static_cast<Edge&>(*this)); |
|
361 } |
|
362 |
|
363 EdgeIt(const Adaptor& adaptor, const Edge& e) : |
|
364 Edge(e), _adaptor(&adaptor) { } |
|
365 |
|
366 EdgeIt& operator++() { |
|
367 _adaptor->next(*this); |
|
368 return *this; |
|
369 } |
|
370 |
|
371 }; |
|
372 |
|
373 class IncEdgeIt : public Edge { |
|
374 friend class GraphAdaptorExtender; |
|
375 const Adaptor* _adaptor; |
|
376 bool direction; |
|
377 public: |
|
378 |
|
379 IncEdgeIt() { } |
|
380 |
|
381 IncEdgeIt(Invalid i) : Edge(i), direction(false) { } |
|
382 |
|
383 IncEdgeIt(const Adaptor& adaptor, const Node &n) : _adaptor(&adaptor) { |
|
384 _adaptor->firstInc(static_cast<Edge&>(*this), direction, n); |
|
385 } |
|
386 |
|
387 IncEdgeIt(const Adaptor& adaptor, const Edge &e, const Node &n) |
|
388 : _adaptor(&adaptor), Edge(e) { |
|
389 direction = (_adaptor->u(e) == n); |
|
390 } |
|
391 |
|
392 IncEdgeIt& operator++() { |
|
393 _adaptor->nextInc(*this, direction); |
|
394 return *this; |
|
395 } |
|
396 }; |
|
397 |
|
398 /// \brief Base node of the iterator |
|
399 /// |
|
400 /// Returns the base node (ie. the source in this case) of the iterator |
|
401 Node baseNode(const OutArcIt &a) const { |
|
402 return Parent::source(a); |
|
403 } |
|
404 /// \brief Running node of the iterator |
|
405 /// |
|
406 /// Returns the running node (ie. the target in this case) of the |
|
407 /// iterator |
|
408 Node runningNode(const OutArcIt &a) const { |
|
409 return Parent::target(a); |
|
410 } |
|
411 |
|
412 /// \brief Base node of the iterator |
|
413 /// |
|
414 /// Returns the base node (ie. the target in this case) of the iterator |
|
415 Node baseNode(const InArcIt &a) const { |
|
416 return Parent::target(a); |
|
417 } |
|
418 /// \brief Running node of the iterator |
|
419 /// |
|
420 /// Returns the running node (ie. the source in this case) of the |
|
421 /// iterator |
|
422 Node runningNode(const InArcIt &a) const { |
|
423 return Parent::source(a); |
|
424 } |
|
425 |
|
426 /// Base node of the iterator |
|
427 /// |
|
428 /// Returns the base node of the iterator |
|
429 Node baseNode(const IncEdgeIt &e) const { |
|
430 return e.direction ? Parent::u(e) : Parent::v(e); |
|
431 } |
|
432 /// Running node of the iterator |
|
433 /// |
|
434 /// Returns the running node of the iterator |
|
435 Node runningNode(const IncEdgeIt &e) const { |
|
436 return e.direction ? Parent::v(e) : Parent::u(e); |
|
437 } |
|
438 |
|
439 }; |
|
440 |
|
441 } |
|
442 |
|
443 |
|
444 #endif |