COIN-OR::LEMON - Graph Library

source: lemon/lemon/bits/graph_adaptor_extender.h @ 627:2313edd0db0b

Last change on this file since 627:2313edd0db0b was 627:2313edd0db0b, checked in by Peter Kovacs <kpeter@…>, 15 years ago

Standard graph maps are required to be reference maps (#190)

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