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
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 {
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))
[432]58        return Parent::target(e);
[430]59      else if(n==Parent::target(e))
[432]60        return Parent::source(e);
[430]61      else
[432]62        return INVALID;
[430]63    }
64
[432]65    class NodeIt : public Node {
[430]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) {
[432]74        _adaptor->first(static_cast<Node&>(*this));
[430]75      }
76
[432]77      NodeIt(const Adaptor& adaptor, const Node& node)
78        : Node(node), _adaptor(&adaptor) {}
[430]79
[432]80      NodeIt& operator++() {
81        _adaptor->next(*this);
82        return *this;
[430]83      }
84
85    };
86
87
[432]88    class ArcIt : public Arc {
[430]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) {
[432]97        _adaptor->first(static_cast<Arc&>(*this));
[430]98      }
99
[432]100      ArcIt(const Adaptor& adaptor, const Arc& e) :
101        Arc(e), _adaptor(&adaptor) { }
[430]102
[432]103      ArcIt& operator++() {
104        _adaptor->next(*this);
105        return *this;
[430]106      }
107
108    };
109
110
[432]111    class OutArcIt : public Arc {
[430]112      const Adaptor* _adaptor;
113    public:
114
115      OutArcIt() { }
116
117      OutArcIt(Invalid i) : Arc(i) { }
118
[432]119      OutArcIt(const Adaptor& adaptor, const Node& node)
120        : _adaptor(&adaptor) {
121        _adaptor->firstOut(*this, node);
[430]122      }
123
[432]124      OutArcIt(const Adaptor& adaptor, const Arc& arc)
125        : Arc(arc), _adaptor(&adaptor) {}
[430]126
[432]127      OutArcIt& operator++() {
128        _adaptor->nextOut(*this);
129        return *this;
[430]130      }
131
132    };
133
134
[432]135    class InArcIt : public Arc {
[430]136      const Adaptor* _adaptor;
137    public:
138
139      InArcIt() { }
140
141      InArcIt(Invalid i) : Arc(i) { }
142
[432]143      InArcIt(const Adaptor& adaptor, const Node& node)
144        : _adaptor(&adaptor) {
145        _adaptor->firstIn(*this, node);
[430]146      }
147
[432]148      InArcIt(const Adaptor& adaptor, const Arc& arc) :
149        Arc(arc), _adaptor(&adaptor) {}
[430]150
[432]151      InArcIt& operator++() {
152        _adaptor->nextIn(*this);
153        return *this;
[430]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
[432]174  template <typename _Graph>
[430]175  class GraphAdaptorExtender : public _Graph {
176  public:
[432]177
[430]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
[432]186    // Graph extension
[430]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))
[432]214        return Parent::v(e);
[430]215      else if( n == Parent::v(e))
[432]216        return Parent::u(e);
[430]217      else
[432]218        return INVALID;
[430]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
[432]231    class NodeIt : public Node {
[430]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) {
[432]240        _adaptor->first(static_cast<Node&>(*this));
[430]241      }
242
[432]243      NodeIt(const Adaptor& adaptor, const Node& node)
244        : Node(node), _adaptor(&adaptor) {}
[430]245
[432]246      NodeIt& operator++() {
247        _adaptor->next(*this);
248        return *this;
[430]249      }
250
251    };
252
253
[432]254    class ArcIt : public Arc {
[430]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) {
[432]263        _adaptor->first(static_cast<Arc&>(*this));
[430]264      }
265
[432]266      ArcIt(const Adaptor& adaptor, const Arc& e) :
267        Arc(e), _adaptor(&adaptor) { }
[430]268
[432]269      ArcIt& operator++() {
270        _adaptor->next(*this);
271        return *this;
[430]272      }
273
274    };
275
276
[432]277    class OutArcIt : public Arc {
[430]278      const Adaptor* _adaptor;
279    public:
280
281      OutArcIt() { }
282
283      OutArcIt(Invalid i) : Arc(i) { }
284
[432]285      OutArcIt(const Adaptor& adaptor, const Node& node)
286        : _adaptor(&adaptor) {
287        _adaptor->firstOut(*this, node);
[430]288      }
289
[432]290      OutArcIt(const Adaptor& adaptor, const Arc& arc)
291        : Arc(arc), _adaptor(&adaptor) {}
[430]292
[432]293      OutArcIt& operator++() {
294        _adaptor->nextOut(*this);
295        return *this;
[430]296      }
297
298    };
299
300
[432]301    class InArcIt : public Arc {
[430]302      const Adaptor* _adaptor;
303    public:
304
305      InArcIt() { }
306
307      InArcIt(Invalid i) : Arc(i) { }
308
[432]309      InArcIt(const Adaptor& adaptor, const Node& node)
310        : _adaptor(&adaptor) {
311        _adaptor->firstIn(*this, node);
[430]312      }
313
[432]314      InArcIt(const Adaptor& adaptor, const Arc& arc) :
315        Arc(arc), _adaptor(&adaptor) {}
[430]316
[432]317      InArcIt& operator++() {
318        _adaptor->nextIn(*this);
319        return *this;
[430]320      }
321
322    };
323
[432]324    class EdgeIt : public Parent::Edge {
[430]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) {
[432]333        _adaptor->first(static_cast<Edge&>(*this));
[430]334      }
335
[432]336      EdgeIt(const Adaptor& adaptor, const Edge& e) :
337        Edge(e), _adaptor(&adaptor) { }
[430]338
[432]339      EdgeIt& operator++() {
340        _adaptor->next(*this);
341        return *this;
[430]342      }
343
344    };
345
[432]346    class IncEdgeIt : public Edge {
[430]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) {
[432]357        _adaptor->firstInc(static_cast<Edge&>(*this), direction, n);
[430]358      }
359
360      IncEdgeIt(const Adaptor& adaptor, const Edge &e, const Node &n)
[432]361        : _adaptor(&adaptor), Edge(e) {
362        direction = (_adaptor->u(e) == n);
[430]363      }
364
365      IncEdgeIt& operator++() {
[432]366        _adaptor->nextInc(*this, direction);
367        return *this;
[430]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.