1 /* -*- mode: C++; indent-tabs-mode: nil; -*- |
|
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_BASE_EXTENDER_H |
|
20 #define LEMON_BITS_BASE_EXTENDER_H |
|
21 |
|
22 #include <lemon/core.h> |
|
23 #include <lemon/error.h> |
|
24 |
|
25 #include <lemon/bits/map_extender.h> |
|
26 #include <lemon/bits/default_map.h> |
|
27 |
|
28 #include <lemon/concept_check.h> |
|
29 #include <lemon/concepts/maps.h> |
|
30 |
|
31 //\ingroup digraphbits |
|
32 //\file |
|
33 //\brief Extenders for the digraph types |
|
34 namespace lemon { |
|
35 |
|
36 // \ingroup digraphbits |
|
37 // |
|
38 // \brief BaseDigraph to BaseGraph extender |
|
39 template <typename Base> |
|
40 class UndirDigraphExtender : public Base { |
|
41 |
|
42 public: |
|
43 |
|
44 typedef Base Parent; |
|
45 typedef typename Parent::Arc Edge; |
|
46 typedef typename Parent::Node Node; |
|
47 |
|
48 typedef True UndirectedTag; |
|
49 |
|
50 class Arc : public Edge { |
|
51 friend class UndirDigraphExtender; |
|
52 |
|
53 protected: |
|
54 bool forward; |
|
55 |
|
56 Arc(const Edge &ue, bool _forward) : |
|
57 Edge(ue), forward(_forward) {} |
|
58 |
|
59 public: |
|
60 Arc() {} |
|
61 |
|
62 // Invalid arc constructor |
|
63 Arc(Invalid i) : Edge(i), forward(true) {} |
|
64 |
|
65 bool operator==(const Arc &that) const { |
|
66 return forward==that.forward && Edge(*this)==Edge(that); |
|
67 } |
|
68 bool operator!=(const Arc &that) const { |
|
69 return forward!=that.forward || Edge(*this)!=Edge(that); |
|
70 } |
|
71 bool operator<(const Arc &that) const { |
|
72 return forward<that.forward || |
|
73 (!(that.forward<forward) && Edge(*this)<Edge(that)); |
|
74 } |
|
75 }; |
|
76 |
|
77 // First node of the edge |
|
78 Node u(const Edge &e) const { |
|
79 return Parent::source(e); |
|
80 } |
|
81 |
|
82 // Source of the given arc |
|
83 Node source(const Arc &e) const { |
|
84 return e.forward ? Parent::source(e) : Parent::target(e); |
|
85 } |
|
86 |
|
87 // Second node of the edge |
|
88 Node v(const Edge &e) const { |
|
89 return Parent::target(e); |
|
90 } |
|
91 |
|
92 // Target of the given arc |
|
93 Node target(const Arc &e) const { |
|
94 return e.forward ? Parent::target(e) : Parent::source(e); |
|
95 } |
|
96 |
|
97 // \brief Directed arc from an edge. |
|
98 // |
|
99 // Returns a directed arc corresponding to the specified edge. |
|
100 // If the given bool is true, the first node of the given edge and |
|
101 // the source node of the returned arc are the same. |
|
102 static Arc direct(const Edge &e, bool d) { |
|
103 return Arc(e, d); |
|
104 } |
|
105 |
|
106 // Returns whether the given directed arc has the same orientation |
|
107 // as the corresponding edge. |
|
108 static bool direction(const Arc &a) { return a.forward; } |
|
109 |
|
110 using Parent::first; |
|
111 using Parent::next; |
|
112 |
|
113 void first(Arc &e) const { |
|
114 Parent::first(e); |
|
115 e.forward=true; |
|
116 } |
|
117 |
|
118 void next(Arc &e) const { |
|
119 if( e.forward ) { |
|
120 e.forward = false; |
|
121 } |
|
122 else { |
|
123 Parent::next(e); |
|
124 e.forward = true; |
|
125 } |
|
126 } |
|
127 |
|
128 void firstOut(Arc &e, const Node &n) const { |
|
129 Parent::firstIn(e,n); |
|
130 if( Edge(e) != INVALID ) { |
|
131 e.forward = false; |
|
132 } |
|
133 else { |
|
134 Parent::firstOut(e,n); |
|
135 e.forward = true; |
|
136 } |
|
137 } |
|
138 void nextOut(Arc &e) const { |
|
139 if( ! e.forward ) { |
|
140 Node n = Parent::target(e); |
|
141 Parent::nextIn(e); |
|
142 if( Edge(e) == INVALID ) { |
|
143 Parent::firstOut(e, n); |
|
144 e.forward = true; |
|
145 } |
|
146 } |
|
147 else { |
|
148 Parent::nextOut(e); |
|
149 } |
|
150 } |
|
151 |
|
152 void firstIn(Arc &e, const Node &n) const { |
|
153 Parent::firstOut(e,n); |
|
154 if( Edge(e) != INVALID ) { |
|
155 e.forward = false; |
|
156 } |
|
157 else { |
|
158 Parent::firstIn(e,n); |
|
159 e.forward = true; |
|
160 } |
|
161 } |
|
162 void nextIn(Arc &e) const { |
|
163 if( ! e.forward ) { |
|
164 Node n = Parent::source(e); |
|
165 Parent::nextOut(e); |
|
166 if( Edge(e) == INVALID ) { |
|
167 Parent::firstIn(e, n); |
|
168 e.forward = true; |
|
169 } |
|
170 } |
|
171 else { |
|
172 Parent::nextIn(e); |
|
173 } |
|
174 } |
|
175 |
|
176 void firstInc(Edge &e, bool &d, const Node &n) const { |
|
177 d = true; |
|
178 Parent::firstOut(e, n); |
|
179 if (e != INVALID) return; |
|
180 d = false; |
|
181 Parent::firstIn(e, n); |
|
182 } |
|
183 |
|
184 void nextInc(Edge &e, bool &d) const { |
|
185 if (d) { |
|
186 Node s = Parent::source(e); |
|
187 Parent::nextOut(e); |
|
188 if (e != INVALID) return; |
|
189 d = false; |
|
190 Parent::firstIn(e, s); |
|
191 } else { |
|
192 Parent::nextIn(e); |
|
193 } |
|
194 } |
|
195 |
|
196 Node nodeFromId(int ix) const { |
|
197 return Parent::nodeFromId(ix); |
|
198 } |
|
199 |
|
200 Arc arcFromId(int ix) const { |
|
201 return direct(Parent::arcFromId(ix >> 1), bool(ix & 1)); |
|
202 } |
|
203 |
|
204 Edge edgeFromId(int ix) const { |
|
205 return Parent::arcFromId(ix); |
|
206 } |
|
207 |
|
208 int id(const Node &n) const { |
|
209 return Parent::id(n); |
|
210 } |
|
211 |
|
212 int id(const Edge &e) const { |
|
213 return Parent::id(e); |
|
214 } |
|
215 |
|
216 int id(const Arc &e) const { |
|
217 return 2 * Parent::id(e) + int(e.forward); |
|
218 } |
|
219 |
|
220 int maxNodeId() const { |
|
221 return Parent::maxNodeId(); |
|
222 } |
|
223 |
|
224 int maxArcId() const { |
|
225 return 2 * Parent::maxArcId() + 1; |
|
226 } |
|
227 |
|
228 int maxEdgeId() const { |
|
229 return Parent::maxArcId(); |
|
230 } |
|
231 |
|
232 int arcNum() const { |
|
233 return 2 * Parent::arcNum(); |
|
234 } |
|
235 |
|
236 int edgeNum() const { |
|
237 return Parent::arcNum(); |
|
238 } |
|
239 |
|
240 Arc findArc(Node s, Node t, Arc p = INVALID) const { |
|
241 if (p == INVALID) { |
|
242 Edge arc = Parent::findArc(s, t); |
|
243 if (arc != INVALID) return direct(arc, true); |
|
244 arc = Parent::findArc(t, s); |
|
245 if (arc != INVALID) return direct(arc, false); |
|
246 } else if (direction(p)) { |
|
247 Edge arc = Parent::findArc(s, t, p); |
|
248 if (arc != INVALID) return direct(arc, true); |
|
249 arc = Parent::findArc(t, s); |
|
250 if (arc != INVALID) return direct(arc, false); |
|
251 } else { |
|
252 Edge arc = Parent::findArc(t, s, p); |
|
253 if (arc != INVALID) return direct(arc, false); |
|
254 } |
|
255 return INVALID; |
|
256 } |
|
257 |
|
258 Edge findEdge(Node s, Node t, Edge p = INVALID) const { |
|
259 if (s != t) { |
|
260 if (p == INVALID) { |
|
261 Edge arc = Parent::findArc(s, t); |
|
262 if (arc != INVALID) return arc; |
|
263 arc = Parent::findArc(t, s); |
|
264 if (arc != INVALID) return arc; |
|
265 } else if (Parent::s(p) == s) { |
|
266 Edge arc = Parent::findArc(s, t, p); |
|
267 if (arc != INVALID) return arc; |
|
268 arc = Parent::findArc(t, s); |
|
269 if (arc != INVALID) return arc; |
|
270 } else { |
|
271 Edge arc = Parent::findArc(t, s, p); |
|
272 if (arc != INVALID) return arc; |
|
273 } |
|
274 } else { |
|
275 return Parent::findArc(s, t, p); |
|
276 } |
|
277 return INVALID; |
|
278 } |
|
279 }; |
|
280 |
|
281 template <typename Base> |
|
282 class BidirBpGraphExtender : public Base { |
|
283 public: |
|
284 typedef Base Parent; |
|
285 typedef BidirBpGraphExtender Digraph; |
|
286 |
|
287 typedef typename Parent::Node Node; |
|
288 typedef typename Parent::Edge Edge; |
|
289 |
|
290 |
|
291 using Parent::first; |
|
292 using Parent::next; |
|
293 |
|
294 using Parent::id; |
|
295 |
|
296 class Red : public Node { |
|
297 friend class BidirBpGraphExtender; |
|
298 public: |
|
299 Red() {} |
|
300 Red(const Node& node) : Node(node) { |
|
301 LEMON_DEBUG(Parent::red(node) || node == INVALID, |
|
302 typename Parent::NodeSetError()); |
|
303 } |
|
304 Red& operator=(const Node& node) { |
|
305 LEMON_DEBUG(Parent::red(node) || node == INVALID, |
|
306 typename Parent::NodeSetError()); |
|
307 Node::operator=(node); |
|
308 return *this; |
|
309 } |
|
310 Red(Invalid) : Node(INVALID) {} |
|
311 Red& operator=(Invalid) { |
|
312 Node::operator=(INVALID); |
|
313 return *this; |
|
314 } |
|
315 }; |
|
316 |
|
317 void first(Red& node) const { |
|
318 Parent::firstRed(static_cast<Node&>(node)); |
|
319 } |
|
320 void next(Red& node) const { |
|
321 Parent::nextRed(static_cast<Node&>(node)); |
|
322 } |
|
323 |
|
324 int id(const Red& node) const { |
|
325 return Parent::redId(node); |
|
326 } |
|
327 |
|
328 class Blue : public Node { |
|
329 friend class BidirBpGraphExtender; |
|
330 public: |
|
331 Blue() {} |
|
332 Blue(const Node& node) : Node(node) { |
|
333 LEMON_DEBUG(Parent::blue(node) || node == INVALID, |
|
334 typename Parent::NodeSetError()); |
|
335 } |
|
336 Blue& operator=(const Node& node) { |
|
337 LEMON_DEBUG(Parent::blue(node) || node == INVALID, |
|
338 typename Parent::NodeSetError()); |
|
339 Node::operator=(node); |
|
340 return *this; |
|
341 } |
|
342 Blue(Invalid) : Node(INVALID) {} |
|
343 Blue& operator=(Invalid) { |
|
344 Node::operator=(INVALID); |
|
345 return *this; |
|
346 } |
|
347 }; |
|
348 |
|
349 void first(Blue& node) const { |
|
350 Parent::firstBlue(static_cast<Node&>(node)); |
|
351 } |
|
352 void next(Blue& node) const { |
|
353 Parent::nextBlue(static_cast<Node&>(node)); |
|
354 } |
|
355 |
|
356 int id(const Blue& node) const { |
|
357 return Parent::redId(node); |
|
358 } |
|
359 |
|
360 Node source(const Edge& arc) const { |
|
361 return red(arc); |
|
362 } |
|
363 Node target(const Edge& arc) const { |
|
364 return blue(arc); |
|
365 } |
|
366 |
|
367 void firstInc(Edge& arc, bool& dir, const Node& node) const { |
|
368 if (Parent::red(node)) { |
|
369 Parent::firstFromRed(arc, node); |
|
370 dir = true; |
|
371 } else { |
|
372 Parent::firstFromBlue(arc, node); |
|
373 dir = static_cast<Edge&>(arc) == INVALID; |
|
374 } |
|
375 } |
|
376 void nextInc(Edge& arc, bool& dir) const { |
|
377 if (dir) { |
|
378 Parent::nextFromRed(arc); |
|
379 } else { |
|
380 Parent::nextFromBlue(arc); |
|
381 if (arc == INVALID) dir = true; |
|
382 } |
|
383 } |
|
384 |
|
385 class Arc : public Edge { |
|
386 friend class BidirBpGraphExtender; |
|
387 protected: |
|
388 bool forward; |
|
389 |
|
390 Arc(const Edge& arc, bool _forward) |
|
391 : Edge(arc), forward(_forward) {} |
|
392 |
|
393 public: |
|
394 Arc() {} |
|
395 Arc (Invalid) : Edge(INVALID), forward(true) {} |
|
396 bool operator==(const Arc& i) const { |
|
397 return Edge::operator==(i) && forward == i.forward; |
|
398 } |
|
399 bool operator!=(const Arc& i) const { |
|
400 return Edge::operator!=(i) || forward != i.forward; |
|
401 } |
|
402 bool operator<(const Arc& i) const { |
|
403 return Edge::operator<(i) || |
|
404 (!(i.forward<forward) && Edge(*this)<Edge(i)); |
|
405 } |
|
406 }; |
|
407 |
|
408 void first(Arc& arc) const { |
|
409 Parent::first(static_cast<Edge&>(arc)); |
|
410 arc.forward = true; |
|
411 } |
|
412 |
|
413 void next(Arc& arc) const { |
|
414 if (!arc.forward) { |
|
415 Parent::next(static_cast<Edge&>(arc)); |
|
416 } |
|
417 arc.forward = !arc.forward; |
|
418 } |
|
419 |
|
420 void firstOut(Arc& arc, const Node& node) const { |
|
421 if (Parent::red(node)) { |
|
422 Parent::firstFromRed(arc, node); |
|
423 arc.forward = true; |
|
424 } else { |
|
425 Parent::firstFromBlue(arc, node); |
|
426 arc.forward = static_cast<Edge&>(arc) == INVALID; |
|
427 } |
|
428 } |
|
429 void nextOut(Arc& arc) const { |
|
430 if (arc.forward) { |
|
431 Parent::nextFromRed(arc); |
|
432 } else { |
|
433 Parent::nextFromBlue(arc); |
|
434 arc.forward = static_cast<Edge&>(arc) == INVALID; |
|
435 } |
|
436 } |
|
437 |
|
438 void firstIn(Arc& arc, const Node& node) const { |
|
439 if (Parent::blue(node)) { |
|
440 Parent::firstFromBlue(arc, node); |
|
441 arc.forward = true; |
|
442 } else { |
|
443 Parent::firstFromRed(arc, node); |
|
444 arc.forward = static_cast<Edge&>(arc) == INVALID; |
|
445 } |
|
446 } |
|
447 void nextIn(Arc& arc) const { |
|
448 if (arc.forward) { |
|
449 Parent::nextFromBlue(arc); |
|
450 } else { |
|
451 Parent::nextFromRed(arc); |
|
452 arc.forward = static_cast<Edge&>(arc) == INVALID; |
|
453 } |
|
454 } |
|
455 |
|
456 Node source(const Arc& arc) const { |
|
457 return arc.forward ? Parent::red(arc) : Parent::blue(arc); |
|
458 } |
|
459 Node target(const Arc& arc) const { |
|
460 return arc.forward ? Parent::blue(arc) : Parent::red(arc); |
|
461 } |
|
462 |
|
463 int id(const Arc& arc) const { |
|
464 return (Parent::id(static_cast<const Edge&>(arc)) << 1) + |
|
465 (arc.forward ? 0 : 1); |
|
466 } |
|
467 Arc arcFromId(int ix) const { |
|
468 return Arc(Parent::fromEdgeId(ix >> 1), (ix & 1) == 0); |
|
469 } |
|
470 int maxArcId() const { |
|
471 return (Parent::maxEdgeId() << 1) + 1; |
|
472 } |
|
473 |
|
474 bool direction(const Arc& arc) const { |
|
475 return arc.forward; |
|
476 } |
|
477 |
|
478 Arc direct(const Edge& arc, bool dir) const { |
|
479 return Arc(arc, dir); |
|
480 } |
|
481 |
|
482 int arcNum() const { |
|
483 return 2 * Parent::edgeNum(); |
|
484 } |
|
485 |
|
486 int edgeNum() const { |
|
487 return Parent::edgeNum(); |
|
488 } |
|
489 |
|
490 |
|
491 }; |
|
492 } |
|
493 |
|
494 #endif |
|