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