COIN-OR::LEMON - Graph Library

source: lemon/lemon/bits/graph_adaptor_extender.h @ 965:ece1f8a3052d

Last change on this file since 965:ece1f8a3052d was 965:ece1f8a3052d, checked in by Peter Kovacs <kpeter@…>, 10 years ago

Add missing UndirectedTags? (#364)

File size: 8.5 KB
RevLine 
[432]1/* -*- mode: C++; indent-tabs-mode: nil; -*-
[430]2 *
[432]3 * This file is a part of LEMON, a generic C++ optimization library.
[430]4 *
[463]5 * Copyright (C) 2003-2009
[430]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 {
[664]29    typedef _Digraph Parent;
30
[430]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))
[432]59        return Parent::target(e);
[430]60      else if(n==Parent::target(e))
[432]61        return Parent::source(e);
[430]62      else
[432]63        return INVALID;
[430]64    }
65
[432]66    class NodeIt : public Node {
[430]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) {
[432]75        _adaptor->first(static_cast<Node&>(*this));
[430]76      }
77
[432]78      NodeIt(const Adaptor& adaptor, const Node& node)
79        : Node(node), _adaptor(&adaptor) {}
[430]80
[432]81      NodeIt& operator++() {
82        _adaptor->next(*this);
83        return *this;
[430]84      }
85
86    };
87
88
[432]89    class ArcIt : public Arc {
[430]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) {
[432]98        _adaptor->first(static_cast<Arc&>(*this));
[430]99      }
100
[432]101      ArcIt(const Adaptor& adaptor, const Arc& e) :
102        Arc(e), _adaptor(&adaptor) { }
[430]103
[432]104      ArcIt& operator++() {
105        _adaptor->next(*this);
106        return *this;
[430]107      }
108
109    };
110
111
[432]112    class OutArcIt : public Arc {
[430]113      const Adaptor* _adaptor;
114    public:
115
116      OutArcIt() { }
117
118      OutArcIt(Invalid i) : Arc(i) { }
119
[432]120      OutArcIt(const Adaptor& adaptor, const Node& node)
121        : _adaptor(&adaptor) {
122        _adaptor->firstOut(*this, node);
[430]123      }
124
[432]125      OutArcIt(const Adaptor& adaptor, const Arc& arc)
126        : Arc(arc), _adaptor(&adaptor) {}
[430]127
[432]128      OutArcIt& operator++() {
129        _adaptor->nextOut(*this);
130        return *this;
[430]131      }
132
133    };
134
135
[432]136    class InArcIt : public Arc {
[430]137      const Adaptor* _adaptor;
138    public:
139
140      InArcIt() { }
141
142      InArcIt(Invalid i) : Arc(i) { }
143
[432]144      InArcIt(const Adaptor& adaptor, const Node& node)
145        : _adaptor(&adaptor) {
146        _adaptor->firstIn(*this, node);
[430]147      }
148
[432]149      InArcIt(const Adaptor& adaptor, const Arc& arc) :
150        Arc(arc), _adaptor(&adaptor) {}
[430]151
[432]152      InArcIt& operator++() {
153        _adaptor->nextIn(*this);
154        return *this;
[430]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
[432]175  template <typename _Graph>
[430]176  class GraphAdaptorExtender : public _Graph {
[664]177    typedef _Graph Parent;
178
[430]179  public:
[432]180
[430]181    typedef _Graph Graph;
182    typedef GraphAdaptorExtender Adaptor;
183
[965]184    typedef True UndirectedTag;
185
[430]186    typedef typename Parent::Node Node;
187    typedef typename Parent::Arc Arc;
188    typedef typename Parent::Edge Edge;
189
[432]190    // Graph extension
[430]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))
[432]218        return Parent::v(e);
[430]219      else if( n == Parent::v(e))
[432]220        return Parent::u(e);
[430]221      else
[432]222        return INVALID;
[430]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
[432]235    class NodeIt : public Node {
[430]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) {
[432]244        _adaptor->first(static_cast<Node&>(*this));
[430]245      }
246
[432]247      NodeIt(const Adaptor& adaptor, const Node& node)
248        : Node(node), _adaptor(&adaptor) {}
[430]249
[432]250      NodeIt& operator++() {
251        _adaptor->next(*this);
252        return *this;
[430]253      }
254
255    };
256
257
[432]258    class ArcIt : public Arc {
[430]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) {
[432]267        _adaptor->first(static_cast<Arc&>(*this));
[430]268      }
269
[432]270      ArcIt(const Adaptor& adaptor, const Arc& e) :
271        Arc(e), _adaptor(&adaptor) { }
[430]272
[432]273      ArcIt& operator++() {
274        _adaptor->next(*this);
275        return *this;
[430]276      }
277
278    };
279
280
[432]281    class OutArcIt : public Arc {
[430]282      const Adaptor* _adaptor;
283    public:
284
285      OutArcIt() { }
286
287      OutArcIt(Invalid i) : Arc(i) { }
288
[432]289      OutArcIt(const Adaptor& adaptor, const Node& node)
290        : _adaptor(&adaptor) {
291        _adaptor->firstOut(*this, node);
[430]292      }
293
[432]294      OutArcIt(const Adaptor& adaptor, const Arc& arc)
295        : Arc(arc), _adaptor(&adaptor) {}
[430]296
[432]297      OutArcIt& operator++() {
298        _adaptor->nextOut(*this);
299        return *this;
[430]300      }
301
302    };
303
304
[432]305    class InArcIt : public Arc {
[430]306      const Adaptor* _adaptor;
307    public:
308
309      InArcIt() { }
310
311      InArcIt(Invalid i) : Arc(i) { }
312
[432]313      InArcIt(const Adaptor& adaptor, const Node& node)
314        : _adaptor(&adaptor) {
315        _adaptor->firstIn(*this, node);
[430]316      }
317
[432]318      InArcIt(const Adaptor& adaptor, const Arc& arc) :
319        Arc(arc), _adaptor(&adaptor) {}
[430]320
[432]321      InArcIt& operator++() {
322        _adaptor->nextIn(*this);
323        return *this;
[430]324      }
325
326    };
327
[432]328    class EdgeIt : public Parent::Edge {
[430]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) {
[432]337        _adaptor->first(static_cast<Edge&>(*this));
[430]338      }
339
[432]340      EdgeIt(const Adaptor& adaptor, const Edge& e) :
341        Edge(e), _adaptor(&adaptor) { }
[430]342
[432]343      EdgeIt& operator++() {
344        _adaptor->next(*this);
345        return *this;
[430]346      }
347
348    };
349
[432]350    class IncEdgeIt : public Edge {
[430]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) {
[432]361        _adaptor->firstInc(static_cast<Edge&>(*this), direction, n);
[430]362      }
363
364      IncEdgeIt(const Adaptor& adaptor, const Edge &e, const Node &n)
[432]365        : _adaptor(&adaptor), Edge(e) {
366        direction = (_adaptor->u(e) == n);
[430]367      }
368
369      IncEdgeIt& operator++() {
[432]370        _adaptor->nextInc(*this, direction);
371        return *this;
[430]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
Note: See TracBrowser for help on using the repository browser.