|
1 /* -*- C++ -*- |
|
2 * lemon/graph_extender.h - Part of LEMON, a generic C++ optimization library |
|
3 * |
|
4 * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi |
|
5 * Kutatocsoport (Egervary Research Group on Combinatorial Optimization, |
|
6 * EGRES). |
|
7 * |
|
8 * Permission to use, modify and distribute this software is granted |
|
9 * provided that this copyright notice appears in all copies. For |
|
10 * precise terms see the accompanying LICENSE file. |
|
11 * |
|
12 * This software is provided "AS IS" with no warranty of any kind, |
|
13 * express or implied, and with no claim as to its suitability for any |
|
14 * purpose. |
|
15 * |
|
16 */ |
|
17 |
|
18 #ifndef LEMON_GRAPH_EXTENDER_H |
|
19 #define LEMON_GRAPH_EXTENDER_H |
|
20 |
|
21 #include <lemon/invalid.h> |
|
22 |
|
23 namespace lemon { |
|
24 |
|
25 template <typename _Base> |
|
26 class GraphExtender : public _Base { |
|
27 public: |
|
28 |
|
29 typedef _Base Parent; |
|
30 typedef GraphExtender Graph; |
|
31 |
|
32 typedef typename Parent::Node Node; |
|
33 typedef typename Parent::Edge Edge; |
|
34 |
|
35 int maxId(Node) const { |
|
36 return Parent::maxNodeId(); |
|
37 } |
|
38 |
|
39 int maxId(Edge) const { |
|
40 return Parent::maxEdgeId(); |
|
41 } |
|
42 |
|
43 Node fromId(int id, Node) const { |
|
44 return Parent::nodeFromId(id); |
|
45 } |
|
46 |
|
47 Edge fromId(int id, Edge) const { |
|
48 return Parent::edgeFromId(id); |
|
49 } |
|
50 |
|
51 Node oppositeNode(const Node &n, const Edge &e) const { |
|
52 if (n == Parent::source(e)) |
|
53 return Parent::target(e); |
|
54 else if(n==Parent::target(e)) |
|
55 return Parent::source(e); |
|
56 else |
|
57 return INVALID; |
|
58 } |
|
59 |
|
60 }; |
|
61 |
|
62 template <typename _Base> |
|
63 class UndirGraphExtender : public _Base { |
|
64 typedef _Base Parent; |
|
65 typedef UndirGraphExtender Graph; |
|
66 |
|
67 public: |
|
68 |
|
69 typedef typename Parent::Edge UndirEdge; |
|
70 typedef typename Parent::Node Node; |
|
71 |
|
72 class Edge : public UndirEdge { |
|
73 friend class UndirGraphExtender; |
|
74 |
|
75 protected: |
|
76 // FIXME: Marci use opposite logic in his graph adaptors. It would |
|
77 // be reasonable to syncronize... |
|
78 bool forward; |
|
79 |
|
80 Edge(const UndirEdge &ue, bool _forward) : |
|
81 UndirEdge(ue), forward(_forward) {} |
|
82 |
|
83 public: |
|
84 Edge() {} |
|
85 |
|
86 /// Invalid edge constructor |
|
87 Edge(Invalid i) : UndirEdge(i), forward(true) {} |
|
88 |
|
89 bool operator==(const Edge &that) const { |
|
90 return forward==that.forward && UndirEdge(*this)==UndirEdge(that); |
|
91 } |
|
92 bool operator!=(const Edge &that) const { |
|
93 return forward!=that.forward || UndirEdge(*this)!=UndirEdge(that); |
|
94 } |
|
95 bool operator<(const Edge &that) const { |
|
96 return forward<that.forward || |
|
97 (!(that.forward<forward) && UndirEdge(*this)<UndirEdge(that)); |
|
98 } |
|
99 }; |
|
100 |
|
101 |
|
102 /// \brief Edge of opposite direction. |
|
103 /// |
|
104 /// Returns the Edge of opposite direction. |
|
105 Edge oppositeEdge(const Edge &e) const { |
|
106 return Edge(e,!e.forward); |
|
107 } |
|
108 |
|
109 public: |
|
110 /// \todo Shouldn't the "source" of an undirected edge be called "aNode" |
|
111 /// or something??? |
|
112 using Parent::source; |
|
113 |
|
114 /// Source of the given Edge. |
|
115 Node source(const Edge &e) const { |
|
116 return e.forward ? Parent::source(e) : Parent::target(e); |
|
117 } |
|
118 |
|
119 /// \todo Shouldn't the "target" of an undirected edge be called "bNode" |
|
120 /// or something??? |
|
121 using Parent::target; |
|
122 |
|
123 /// Target of the given Edge. |
|
124 Node target(const Edge &e) const { |
|
125 return e.forward ? Parent::target(e) : Parent::source(e); |
|
126 } |
|
127 |
|
128 Node oppositeNode(const Node &n, const UndirEdge &e) const { |
|
129 if( n == Parent::source(e)) |
|
130 return Parent::target(e); |
|
131 else if( n == Parent::target(e)) |
|
132 return Parent::source(e); |
|
133 else |
|
134 return INVALID; |
|
135 } |
|
136 |
|
137 /// \brief Directed edge from an undirected edge and a source node. |
|
138 /// |
|
139 /// Returns a (directed) Edge corresponding to the specified UndirEdge |
|
140 /// and source Node. |
|
141 /// |
|
142 Edge direct(const UndirEdge &ue, const Node &s) const { |
|
143 return Edge(ue, s == source(ue)); |
|
144 } |
|
145 |
|
146 /// \brief Directed edge from an undirected edge. |
|
147 /// |
|
148 /// Returns a directed edge corresponding to the specified UndirEdge. |
|
149 /// If the given bool is true the given undirected edge and the |
|
150 /// returned edge have the same source node. |
|
151 Edge direct(const UndirEdge &ue, bool d) const { |
|
152 return Edge(ue, d); |
|
153 } |
|
154 |
|
155 /// Returns whether the given directed edge is same orientation as the |
|
156 /// corresponding undirected edge. |
|
157 /// |
|
158 /// \todo reference to the corresponding point of the undirected graph |
|
159 /// concept. "What does the direction of an undirected edge mean?" |
|
160 bool direction(const Edge &e) const { return e.forward; } |
|
161 |
|
162 |
|
163 using Parent::first; |
|
164 void first(Edge &e) const { |
|
165 Parent::first(e); |
|
166 e.forward=true; |
|
167 } |
|
168 |
|
169 using Parent::next; |
|
170 void next(Edge &e) const { |
|
171 if( e.forward ) { |
|
172 e.forward = false; |
|
173 } |
|
174 else { |
|
175 Parent::next(e); |
|
176 e.forward = true; |
|
177 } |
|
178 } |
|
179 |
|
180 public: |
|
181 |
|
182 void firstOut(Edge &e, const Node &n) const { |
|
183 Parent::firstIn(e,n); |
|
184 if( UndirEdge(e) != INVALID ) { |
|
185 e.forward = false; |
|
186 } |
|
187 else { |
|
188 Parent::firstOut(e,n); |
|
189 e.forward = true; |
|
190 } |
|
191 } |
|
192 void nextOut(Edge &e) const { |
|
193 if( ! e.forward ) { |
|
194 Node n = Parent::target(e); |
|
195 Parent::nextIn(e); |
|
196 if( UndirEdge(e) == INVALID ) { |
|
197 Parent::firstOut(e, n); |
|
198 e.forward = true; |
|
199 } |
|
200 } |
|
201 else { |
|
202 Parent::nextOut(e); |
|
203 } |
|
204 } |
|
205 |
|
206 void firstIn(Edge &e, const Node &n) const { |
|
207 Parent::firstOut(e,n); |
|
208 if( UndirEdge(e) != INVALID ) { |
|
209 e.forward = false; |
|
210 } |
|
211 else { |
|
212 Parent::firstIn(e,n); |
|
213 e.forward = true; |
|
214 } |
|
215 } |
|
216 void nextIn(Edge &e) const { |
|
217 if( ! e.forward ) { |
|
218 Node n = Parent::source(e); |
|
219 Parent::nextOut(e); |
|
220 if( UndirEdge(e) == INVALID ) { |
|
221 Parent::firstIn(e, n); |
|
222 e.forward = true; |
|
223 } |
|
224 } |
|
225 else { |
|
226 Parent::nextIn(e); |
|
227 } |
|
228 } |
|
229 |
|
230 void firstInc(UndirEdge &e, const Node &n) const { |
|
231 Parent::firstOut(e, n); |
|
232 if (e != INVALID) return; |
|
233 Parent::firstIn(e, n); |
|
234 } |
|
235 void nextInc(UndirEdge &e, const Node &n) const { |
|
236 if (Parent::source(e) == n) { |
|
237 Parent::nextOut(e); |
|
238 if (e != INVALID) return; |
|
239 Parent::firstIn(e, n); |
|
240 } else { |
|
241 Parent::nextIn(e); |
|
242 } |
|
243 } |
|
244 |
|
245 void firstInc(UndirEdge &e, bool &d, const Node &n) const { |
|
246 d = true; |
|
247 Parent::firstOut(e, n); |
|
248 if (e != INVALID) return; |
|
249 d = false; |
|
250 Parent::firstIn(e, n); |
|
251 } |
|
252 void nextInc(UndirEdge &e, bool &d) const { |
|
253 if (d) { |
|
254 Node s = Parent::source(e); |
|
255 Parent::nextOut(e); |
|
256 if (e != INVALID) return; |
|
257 d = false; |
|
258 Parent::firstIn(e, s); |
|
259 } else { |
|
260 Parent::nextIn(e); |
|
261 } |
|
262 } |
|
263 |
|
264 // Miscellaneous stuff: |
|
265 |
|
266 /// \todo these methods (id, maxEdgeId) should be moved into separate |
|
267 /// Extender |
|
268 |
|
269 // using Parent::id; |
|
270 // Using "using" is not a good idea, cause it could be that there is |
|
271 // no "id" in Parent... |
|
272 |
|
273 int id(const Node &n) const { |
|
274 return Parent::id(n); |
|
275 } |
|
276 |
|
277 int id(const UndirEdge &e) const { |
|
278 return Parent::id(e); |
|
279 } |
|
280 |
|
281 int id(const Edge &e) const { |
|
282 return 2 * Parent::id(e) + int(e.forward); |
|
283 } |
|
284 |
|
285 int maxNodeId() const { |
|
286 return Parent::maxNodeId(); |
|
287 } |
|
288 |
|
289 int maxEdgeId() const { |
|
290 return 2 * Parent::maxEdgeId() + 1; |
|
291 } |
|
292 |
|
293 int maxUndirEdgeId() const { |
|
294 return Parent::maxEdgeId(); |
|
295 } |
|
296 |
|
297 int maxId(Node) const { |
|
298 return maxNodeId(); |
|
299 } |
|
300 |
|
301 int maxId(Edge) const { |
|
302 return maxEdgeId(); |
|
303 } |
|
304 int maxId(UndirEdge) const { |
|
305 return maxUndirEdgeId(); |
|
306 } |
|
307 |
|
308 int edgeNum() const { |
|
309 return 2 * Parent::edgeNum(); |
|
310 } |
|
311 |
|
312 int undirEdgeNum() const { |
|
313 return Parent::edgeNum(); |
|
314 } |
|
315 |
|
316 Node nodeFromId(int id) const { |
|
317 return Parent::nodeFromId(id); |
|
318 } |
|
319 |
|
320 Edge edgeFromId(int id) const { |
|
321 return direct(Parent::edgeFromId(id >> 1), bool(id & 1)); |
|
322 } |
|
323 |
|
324 UndirEdge undirEdgeFromId(int id) const { |
|
325 return Parent::edgeFromId(id >> 1); |
|
326 } |
|
327 |
|
328 Node fromId(int id, Node) const { |
|
329 return nodeFromId(id); |
|
330 } |
|
331 |
|
332 Edge fromId(int id, Edge) const { |
|
333 return edgeFromId(id); |
|
334 } |
|
335 |
|
336 UndirEdge fromId(int id, UndirEdge) const { |
|
337 return undirEdgeFromId(id); |
|
338 } |
|
339 |
|
340 |
|
341 Edge findEdge(Node source, Node target, Edge prev) const { |
|
342 if (prev == INVALID) { |
|
343 UndirEdge edge = Parent::findEdge(source, target); |
|
344 if (edge != INVALID) return direct(edge, true); |
|
345 edge = Parent::findEdge(target, source); |
|
346 if (edge != INVALID) return direct(edge, false); |
|
347 } else if (direction(prev)) { |
|
348 UndirEdge edge = Parent::findEdge(source, target, prev); |
|
349 if (edge != INVALID) return direct(edge, true); |
|
350 edge = Parent::findEdge(target, source); |
|
351 if (edge != INVALID) return direct(edge, false); |
|
352 } else { |
|
353 UndirEdge edge = Parent::findEdge(target, source, prev); |
|
354 if (edge != INVALID) return direct(edge, false); |
|
355 } |
|
356 return INVALID; |
|
357 } |
|
358 |
|
359 UndirEdge findUndirEdge(Node source, Node target, UndirEdge prev) const { |
|
360 if (prev == INVALID) { |
|
361 UndirEdge edge = Parent::findEdge(source, target); |
|
362 if (edge != INVALID) return edge; |
|
363 edge = Parent::findEdge(target, source); |
|
364 if (edge != INVALID) return edge; |
|
365 } else if (Parent::source(prev) == source) { |
|
366 UndirEdge edge = Parent::findEdge(source, target, prev); |
|
367 if (edge != INVALID) return edge; |
|
368 edge = Parent::findEdge(target, source); |
|
369 if (edge != INVALID) return edge; |
|
370 } else { |
|
371 UndirEdge edge = Parent::findEdge(target, source, prev); |
|
372 if (edge != INVALID) return edge; |
|
373 } |
|
374 return INVALID; |
|
375 } |
|
376 |
|
377 }; |
|
378 |
|
379 } |
|
380 |
|
381 #endif // LEMON_UNDIR_GRAPH_EXTENDER_H |