COIN-OR::LEMON - Graph Library

source: lemon/lemon/bits/graph_adaptor_extender.h @ 1336:0759d974de81

Last change on this file since 1336:0759d974de81 was 1336:0759d974de81, checked in by Gabor Gevay <ggab90@…>, 6 years ago

STL style iterators (#325)

For

  • graph types,
  • graph adaptors,
  • paths,
  • iterable maps,
  • LP rows/cols and
  • active nodes is BellmanFord?
File size: 9.8 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-2013
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    LemonRangeWrapper1<NodeIt, Adaptor> nodes() {
89      return LemonRangeWrapper1<NodeIt, Adaptor>(*this);
90    }
91
92    class ArcIt : public Arc {
93      const Adaptor* _adaptor;
94    public:
95
96      ArcIt() { }
97
98      ArcIt(Invalid i) : Arc(i) { }
99
100      explicit ArcIt(const Adaptor& adaptor) : _adaptor(&adaptor) {
101        _adaptor->first(static_cast<Arc&>(*this));
102      }
103
104      ArcIt(const Adaptor& adaptor, const Arc& e) :
105        Arc(e), _adaptor(&adaptor) { }
106
107      ArcIt& operator++() {
108        _adaptor->next(*this);
109        return *this;
110      }
111
112    };
113
114    LemonRangeWrapper1<ArcIt, Adaptor> arcs() {
115      return LemonRangeWrapper1<ArcIt, Adaptor>(*this);
116    }
117
118
119    class OutArcIt : public Arc {
120      const Adaptor* _adaptor;
121    public:
122
123      OutArcIt() { }
124
125      OutArcIt(Invalid i) : Arc(i) { }
126
127      OutArcIt(const Adaptor& adaptor, const Node& node)
128        : _adaptor(&adaptor) {
129        _adaptor->firstOut(*this, node);
130      }
131
132      OutArcIt(const Adaptor& adaptor, const Arc& arc)
133        : Arc(arc), _adaptor(&adaptor) {}
134
135      OutArcIt& operator++() {
136        _adaptor->nextOut(*this);
137        return *this;
138      }
139
140    };
141
142    LemonRangeWrapper2<OutArcIt, Adaptor, Node> outArcs(const Node& u) const {
143      return LemonRangeWrapper2<OutArcIt, Adaptor, Node>(*this, u);
144    }
145
146
147    class InArcIt : public Arc {
148      const Adaptor* _adaptor;
149    public:
150
151      InArcIt() { }
152
153      InArcIt(Invalid i) : Arc(i) { }
154
155      InArcIt(const Adaptor& adaptor, const Node& node)
156        : _adaptor(&adaptor) {
157        _adaptor->firstIn(*this, node);
158      }
159
160      InArcIt(const Adaptor& adaptor, const Arc& arc) :
161        Arc(arc), _adaptor(&adaptor) {}
162
163      InArcIt& operator++() {
164        _adaptor->nextIn(*this);
165        return *this;
166      }
167
168    };
169
170    LemonRangeWrapper2<InArcIt, Adaptor, Node> inArcs(const Node& u) const {
171      return LemonRangeWrapper2<InArcIt, Adaptor, Node>(*this, u);
172    }
173
174    Node baseNode(const OutArcIt &e) const {
175      return Parent::source(e);
176    }
177    Node runningNode(const OutArcIt &e) const {
178      return Parent::target(e);
179    }
180
181    Node baseNode(const InArcIt &e) const {
182      return Parent::target(e);
183    }
184    Node runningNode(const InArcIt &e) const {
185      return Parent::source(e);
186    }
187
188  };
189
190  template <typename _Graph>
191  class GraphAdaptorExtender : public _Graph {
192    typedef _Graph Parent;
193
194  public:
195
196    typedef _Graph Graph;
197    typedef GraphAdaptorExtender Adaptor;
198
199    typedef True UndirectedTag;
200
201    typedef typename Parent::Node Node;
202    typedef typename Parent::Arc Arc;
203    typedef typename Parent::Edge Edge;
204
205    // Graph extension
206
207    int maxId(Node) const {
208      return Parent::maxNodeId();
209    }
210
211    int maxId(Arc) const {
212      return Parent::maxArcId();
213    }
214
215    int maxId(Edge) const {
216      return Parent::maxEdgeId();
217    }
218
219    Node fromId(int id, Node) const {
220      return Parent::nodeFromId(id);
221    }
222
223    Arc fromId(int id, Arc) const {
224      return Parent::arcFromId(id);
225    }
226
227    Edge fromId(int id, Edge) const {
228      return Parent::edgeFromId(id);
229    }
230
231    Node oppositeNode(const Node &n, const Edge &e) const {
232      if( n == Parent::u(e))
233        return Parent::v(e);
234      else if( n == Parent::v(e))
235        return Parent::u(e);
236      else
237        return INVALID;
238    }
239
240    Arc oppositeArc(const Arc &a) const {
241      return Parent::direct(a, !Parent::direction(a));
242    }
243
244    using Parent::direct;
245    Arc direct(const Edge &e, const Node &s) const {
246      return Parent::direct(e, Parent::u(e) == s);
247    }
248
249
250    class NodeIt : public Node {
251      const Adaptor* _adaptor;
252    public:
253
254      NodeIt() {}
255
256      NodeIt(Invalid i) : Node(i) { }
257
258      explicit NodeIt(const Adaptor& adaptor) : _adaptor(&adaptor) {
259        _adaptor->first(static_cast<Node&>(*this));
260      }
261
262      NodeIt(const Adaptor& adaptor, const Node& node)
263        : Node(node), _adaptor(&adaptor) {}
264
265      NodeIt& operator++() {
266        _adaptor->next(*this);
267        return *this;
268      }
269
270    };
271
272    LemonRangeWrapper1<NodeIt, Adaptor> nodes() {
273      return LemonRangeWrapper1<NodeIt, Adaptor>(*this);
274    }
275
276
277    class ArcIt : public Arc {
278      const Adaptor* _adaptor;
279    public:
280
281      ArcIt() { }
282
283      ArcIt(Invalid i) : Arc(i) { }
284
285      explicit ArcIt(const Adaptor& adaptor) : _adaptor(&adaptor) {
286        _adaptor->first(static_cast<Arc&>(*this));
287      }
288
289      ArcIt(const Adaptor& adaptor, const Arc& e) :
290        Arc(e), _adaptor(&adaptor) { }
291
292      ArcIt& operator++() {
293        _adaptor->next(*this);
294        return *this;
295      }
296
297    };
298
299    LemonRangeWrapper1<ArcIt, Adaptor> arcs() {
300      return LemonRangeWrapper1<ArcIt, Adaptor>(*this);
301    }
302
303
304    class OutArcIt : public Arc {
305      const Adaptor* _adaptor;
306    public:
307
308      OutArcIt() { }
309
310      OutArcIt(Invalid i) : Arc(i) { }
311
312      OutArcIt(const Adaptor& adaptor, const Node& node)
313        : _adaptor(&adaptor) {
314        _adaptor->firstOut(*this, node);
315      }
316
317      OutArcIt(const Adaptor& adaptor, const Arc& arc)
318        : Arc(arc), _adaptor(&adaptor) {}
319
320      OutArcIt& operator++() {
321        _adaptor->nextOut(*this);
322        return *this;
323      }
324
325    };
326
327    LemonRangeWrapper2<OutArcIt, Adaptor, Node> outArcs(const Node& u) const {
328      return LemonRangeWrapper2<OutArcIt, Adaptor, Node>(*this, u);
329    }
330
331
332    class InArcIt : public Arc {
333      const Adaptor* _adaptor;
334    public:
335
336      InArcIt() { }
337
338      InArcIt(Invalid i) : Arc(i) { }
339
340      InArcIt(const Adaptor& adaptor, const Node& node)
341        : _adaptor(&adaptor) {
342        _adaptor->firstIn(*this, node);
343      }
344
345      InArcIt(const Adaptor& adaptor, const Arc& arc) :
346        Arc(arc), _adaptor(&adaptor) {}
347
348      InArcIt& operator++() {
349        _adaptor->nextIn(*this);
350        return *this;
351      }
352
353    };
354
355    LemonRangeWrapper2<InArcIt, Adaptor, Node> inArcs(const Node& u) const {
356      return LemonRangeWrapper2<InArcIt, Adaptor, Node>(*this, u);
357    }
358
359    class EdgeIt : public Parent::Edge {
360      const Adaptor* _adaptor;
361    public:
362
363      EdgeIt() { }
364
365      EdgeIt(Invalid i) : Edge(i) { }
366
367      explicit EdgeIt(const Adaptor& adaptor) : _adaptor(&adaptor) {
368        _adaptor->first(static_cast<Edge&>(*this));
369      }
370
371      EdgeIt(const Adaptor& adaptor, const Edge& e) :
372        Edge(e), _adaptor(&adaptor) { }
373
374      EdgeIt& operator++() {
375        _adaptor->next(*this);
376        return *this;
377      }
378
379    };
380
381    LemonRangeWrapper1<EdgeIt, Adaptor> edges() {
382      return LemonRangeWrapper1<EdgeIt, Adaptor>(*this);
383    }
384
385
386    class IncEdgeIt : public Edge {
387      friend class GraphAdaptorExtender;
388      const Adaptor* _adaptor;
389      bool direction;
390    public:
391
392      IncEdgeIt() { }
393
394      IncEdgeIt(Invalid i) : Edge(i), direction(false) { }
395
396      IncEdgeIt(const Adaptor& adaptor, const Node &n) : _adaptor(&adaptor) {
397        _adaptor->firstInc(static_cast<Edge&>(*this), direction, n);
398      }
399
400      IncEdgeIt(const Adaptor& adaptor, const Edge &e, const Node &n)
401        : _adaptor(&adaptor), Edge(e) {
402        direction = (_adaptor->u(e) == n);
403      }
404
405      IncEdgeIt& operator++() {
406        _adaptor->nextInc(*this, direction);
407        return *this;
408      }
409    };
410
411    LemonRangeWrapper2<IncEdgeIt, Adaptor, Node> incEdges(const Node& u) const {
412      return LemonRangeWrapper2<IncEdgeIt, Adaptor, Node>(*this, u);
413    }
414
415
416    Node baseNode(const OutArcIt &a) const {
417      return Parent::source(a);
418    }
419    Node runningNode(const OutArcIt &a) const {
420      return Parent::target(a);
421    }
422
423    Node baseNode(const InArcIt &a) const {
424      return Parent::target(a);
425    }
426    Node runningNode(const InArcIt &a) const {
427      return Parent::source(a);
428    }
429
430    Node baseNode(const IncEdgeIt &e) const {
431      return e.direction ? Parent::u(e) : Parent::v(e);
432    }
433    Node runningNode(const IncEdgeIt &e) const {
434      return e.direction ? Parent::v(e) : Parent::u(e);
435    }
436
437  };
438
439}
440
441
442#endif
Note: See TracBrowser for help on using the repository browser.