COIN-OR::LEMON - Graph Library

source: lemon/lemon/bits/graph_adaptor_extender.h @ 665:b95898314e09

Last change on this file since 665:b95898314e09 was 664:4137ef9aacc6, checked in by Peter Kovacs <kpeter@…>, 15 years ago

Fix and uniform the usage of Graph and Parent typedefs (#268)

  • Rename Graph typedefs to GraphType? in the implementation of graph maps and MapExtender? to prevent conflicts (especially using VS). They are not public.
  • Make Parent typedefs private in all classes.
  • Replace Digraph with Graph in some places (fix faulty renamings of the script).
  • Use Graph and Digraph typedefs (more) consequently.
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    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      explicit NodeIt(const Adaptor& adaptor) : _adaptor(&adaptor) {
75        _adaptor->first(static_cast<Node&>(*this));
76      }
77
78      NodeIt(const Adaptor& adaptor, const Node& node)
79        : Node(node), _adaptor(&adaptor) {}
80
81      NodeIt& operator++() {
82        _adaptor->next(*this);
83        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      OutArcIt(const Adaptor& adaptor, const Node& node)
121        : _adaptor(&adaptor) {
122        _adaptor->firstOut(*this, node);
123      }
124
125      OutArcIt(const Adaptor& adaptor, const Arc& arc)
126        : Arc(arc), _adaptor(&adaptor) {}
127
128      OutArcIt& operator++() {
129        _adaptor->nextOut(*this);
130        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 typename Parent::Node Node;
185    typedef typename Parent::Arc Arc;
186    typedef typename Parent::Edge Edge;
187
188    // Graph extension
189
190    int maxId(Node) const {
191      return Parent::maxNodeId();
192    }
193
194    int maxId(Arc) const {
195      return Parent::maxArcId();
196    }
197
198    int maxId(Edge) const {
199      return Parent::maxEdgeId();
200    }
201
202    Node fromId(int id, Node) const {
203      return Parent::nodeFromId(id);
204    }
205
206    Arc fromId(int id, Arc) const {
207      return Parent::arcFromId(id);
208    }
209
210    Edge fromId(int id, Edge) const {
211      return Parent::edgeFromId(id);
212    }
213
214    Node oppositeNode(const Node &n, const Edge &e) const {
215      if( n == Parent::u(e))
216        return Parent::v(e);
217      else if( n == Parent::v(e))
218        return Parent::u(e);
219      else
220        return INVALID;
221    }
222
223    Arc oppositeArc(const Arc &a) const {
224      return Parent::direct(a, !Parent::direction(a));
225    }
226
227    using Parent::direct;
228    Arc direct(const Edge &e, const Node &s) const {
229      return Parent::direct(e, Parent::u(e) == s);
230    }
231
232
233    class NodeIt : public Node {
234      const Adaptor* _adaptor;
235    public:
236
237      NodeIt() {}
238
239      NodeIt(Invalid i) : Node(i) { }
240
241      explicit NodeIt(const Adaptor& adaptor) : _adaptor(&adaptor) {
242        _adaptor->first(static_cast<Node&>(*this));
243      }
244
245      NodeIt(const Adaptor& adaptor, const Node& node)
246        : Node(node), _adaptor(&adaptor) {}
247
248      NodeIt& operator++() {
249        _adaptor->next(*this);
250        return *this;
251      }
252
253    };
254
255
256    class ArcIt : public Arc {
257      const Adaptor* _adaptor;
258    public:
259
260      ArcIt() { }
261
262      ArcIt(Invalid i) : Arc(i) { }
263
264      explicit ArcIt(const Adaptor& adaptor) : _adaptor(&adaptor) {
265        _adaptor->first(static_cast<Arc&>(*this));
266      }
267
268      ArcIt(const Adaptor& adaptor, const Arc& e) :
269        Arc(e), _adaptor(&adaptor) { }
270
271      ArcIt& operator++() {
272        _adaptor->next(*this);
273        return *this;
274      }
275
276    };
277
278
279    class OutArcIt : public Arc {
280      const Adaptor* _adaptor;
281    public:
282
283      OutArcIt() { }
284
285      OutArcIt(Invalid i) : Arc(i) { }
286
287      OutArcIt(const Adaptor& adaptor, const Node& node)
288        : _adaptor(&adaptor) {
289        _adaptor->firstOut(*this, node);
290      }
291
292      OutArcIt(const Adaptor& adaptor, const Arc& arc)
293        : Arc(arc), _adaptor(&adaptor) {}
294
295      OutArcIt& operator++() {
296        _adaptor->nextOut(*this);
297        return *this;
298      }
299
300    };
301
302
303    class InArcIt : public Arc {
304      const Adaptor* _adaptor;
305    public:
306
307      InArcIt() { }
308
309      InArcIt(Invalid i) : Arc(i) { }
310
311      InArcIt(const Adaptor& adaptor, const Node& node)
312        : _adaptor(&adaptor) {
313        _adaptor->firstIn(*this, node);
314      }
315
316      InArcIt(const Adaptor& adaptor, const Arc& arc) :
317        Arc(arc), _adaptor(&adaptor) {}
318
319      InArcIt& operator++() {
320        _adaptor->nextIn(*this);
321        return *this;
322      }
323
324    };
325
326    class EdgeIt : public Parent::Edge {
327      const Adaptor* _adaptor;
328    public:
329
330      EdgeIt() { }
331
332      EdgeIt(Invalid i) : Edge(i) { }
333
334      explicit EdgeIt(const Adaptor& adaptor) : _adaptor(&adaptor) {
335        _adaptor->first(static_cast<Edge&>(*this));
336      }
337
338      EdgeIt(const Adaptor& adaptor, const Edge& e) :
339        Edge(e), _adaptor(&adaptor) { }
340
341      EdgeIt& operator++() {
342        _adaptor->next(*this);
343        return *this;
344      }
345
346    };
347
348    class IncEdgeIt : public Edge {
349      friend class GraphAdaptorExtender;
350      const Adaptor* _adaptor;
351      bool direction;
352    public:
353
354      IncEdgeIt() { }
355
356      IncEdgeIt(Invalid i) : Edge(i), direction(false) { }
357
358      IncEdgeIt(const Adaptor& adaptor, const Node &n) : _adaptor(&adaptor) {
359        _adaptor->firstInc(static_cast<Edge&>(*this), direction, n);
360      }
361
362      IncEdgeIt(const Adaptor& adaptor, const Edge &e, const Node &n)
363        : _adaptor(&adaptor), Edge(e) {
364        direction = (_adaptor->u(e) == n);
365      }
366
367      IncEdgeIt& operator++() {
368        _adaptor->nextInc(*this, direction);
369        return *this;
370      }
371    };
372
373    Node baseNode(const OutArcIt &a) const {
374      return Parent::source(a);
375    }
376    Node runningNode(const OutArcIt &a) const {
377      return Parent::target(a);
378    }
379
380    Node baseNode(const InArcIt &a) const {
381      return Parent::target(a);
382    }
383    Node runningNode(const InArcIt &a) const {
384      return Parent::source(a);
385    }
386
387    Node baseNode(const IncEdgeIt &e) const {
388      return e.direction ? Parent::u(e) : Parent::v(e);
389    }
390    Node runningNode(const IncEdgeIt &e) const {
391      return e.direction ? Parent::v(e) : Parent::u(e);
392    }
393
394  };
395
396}
397
398
399#endif
Note: See TracBrowser for help on using the repository browser.