COIN-OR::LEMON - Graph Library

source: lemon-1.2/lemon/bits/graph_adaptor_extender.h @ 415:4b6112235fad

Last change on this file since 415:4b6112235fad was 414:05357da973ce, checked in by Balazs Dezso <deba@…>, 11 years ago

Port graph adaptors from svn -r3498 (#67)

File size: 9.6 KB
Line 
1/* -*- C++ -*-
2 *
3 * This file is a part of LEMON, a generic C++ optimization library
4 *
5 * Copyright (C) 2003-2008
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
25#include <lemon/bits/default_map.h>
26
27
28///\ingroup digraphbits
29///\file
30///\brief Extenders for the digraph adaptor types
31namespace lemon {
32
33  /// \ingroup digraphbits
34  ///
35  /// \brief Extender for the DigraphAdaptors
36  template <typename _Digraph>
37  class DigraphAdaptorExtender : public _Digraph {
38  public:
39
40    typedef _Digraph Parent;
41    typedef _Digraph Digraph;
42    typedef DigraphAdaptorExtender Adaptor;
43
44    // Base extensions
45
46    typedef typename Parent::Node Node;
47    typedef typename Parent::Arc Arc;
48
49    int maxId(Node) const {
50      return Parent::maxNodeId();
51    }
52
53    int maxId(Arc) const {
54      return Parent::maxArcId();
55    }
56
57    Node fromId(int id, Node) const {
58      return Parent::nodeFromId(id);
59    }
60
61    Arc fromId(int id, Arc) const {
62      return Parent::arcFromId(id);
63    }
64
65    Node oppositeNode(const Node &n, const Arc &e) const {
66      if (n == Parent::source(e))
67        return Parent::target(e);
68      else if(n==Parent::target(e))
69        return Parent::source(e);
70      else
71        return INVALID;
72    }
73
74    class NodeIt : public Node {
75      const Adaptor* _adaptor;
76    public:
77
78      NodeIt() {}
79
80      NodeIt(Invalid i) : Node(i) { }
81
82      explicit NodeIt(const Adaptor& adaptor) : _adaptor(&adaptor) {
83        _adaptor->first(static_cast<Node&>(*this));
84      }
85
86      NodeIt(const Adaptor& adaptor, const Node& node)
87        : Node(node), _adaptor(&adaptor) {}
88
89      NodeIt& operator++() {
90        _adaptor->next(*this);
91        return *this;
92      }
93
94    };
95
96
97    class ArcIt : public Arc {
98      const Adaptor* _adaptor;
99    public:
100
101      ArcIt() { }
102
103      ArcIt(Invalid i) : Arc(i) { }
104
105      explicit ArcIt(const Adaptor& adaptor) : _adaptor(&adaptor) {
106        _adaptor->first(static_cast<Arc&>(*this));
107      }
108
109      ArcIt(const Adaptor& adaptor, const Arc& e) :
110        Arc(e), _adaptor(&adaptor) { }
111
112      ArcIt& operator++() {
113        _adaptor->next(*this);
114        return *this;
115      }
116
117    };
118
119
120    class OutArcIt : public Arc {
121      const Adaptor* _adaptor;
122    public:
123
124      OutArcIt() { }
125
126      OutArcIt(Invalid i) : Arc(i) { }
127
128      OutArcIt(const Adaptor& adaptor, const Node& node)
129        : _adaptor(&adaptor) {
130        _adaptor->firstOut(*this, node);
131      }
132
133      OutArcIt(const Adaptor& adaptor, const Arc& arc)
134        : Arc(arc), _adaptor(&adaptor) {}
135
136      OutArcIt& operator++() {
137        _adaptor->nextOut(*this);
138        return *this;
139      }
140
141    };
142
143
144    class InArcIt : public Arc {
145      const Adaptor* _adaptor;
146    public:
147
148      InArcIt() { }
149
150      InArcIt(Invalid i) : Arc(i) { }
151
152      InArcIt(const Adaptor& adaptor, const Node& node)
153        : _adaptor(&adaptor) {
154        _adaptor->firstIn(*this, node);
155      }
156
157      InArcIt(const Adaptor& adaptor, const Arc& arc) :
158        Arc(arc), _adaptor(&adaptor) {}
159
160      InArcIt& operator++() {
161        _adaptor->nextIn(*this);
162        return *this;
163      }
164
165    };
166
167    /// \brief Base node of the iterator
168    ///
169    /// Returns the base node (ie. the source in this case) of the iterator
170    Node baseNode(const OutArcIt &e) const {
171      return Parent::source(e);
172    }
173    /// \brief Running node of the iterator
174    ///
175    /// Returns the running node (ie. the target in this case) of the
176    /// iterator
177    Node runningNode(const OutArcIt &e) const {
178      return Parent::target(e);
179    }
180
181    /// \brief Base node of the iterator
182    ///
183    /// Returns the base node (ie. the target in this case) of the iterator
184    Node baseNode(const InArcIt &e) const {
185      return Parent::target(e);
186    }
187    /// \brief Running node of the iterator
188    ///
189    /// Returns the running node (ie. the source in this case) of the
190    /// iterator
191    Node runningNode(const InArcIt &e) const {
192      return Parent::source(e);
193    }
194
195  };
196
197
198  /// \ingroup digraphbits
199  ///
200  /// \brief Extender for the GraphAdaptors
201  template <typename _Graph>
202  class GraphAdaptorExtender : public _Graph {
203  public:
204   
205    typedef _Graph Parent;
206    typedef _Graph Graph;
207    typedef GraphAdaptorExtender Adaptor;
208
209    typedef typename Parent::Node Node;
210    typedef typename Parent::Arc Arc;
211    typedef typename Parent::Edge Edge;
212
213    // Graph extension   
214
215    int maxId(Node) const {
216      return Parent::maxNodeId();
217    }
218
219    int maxId(Arc) const {
220      return Parent::maxArcId();
221    }
222
223    int maxId(Edge) const {
224      return Parent::maxEdgeId();
225    }
226
227    Node fromId(int id, Node) const {
228      return Parent::nodeFromId(id);
229    }
230
231    Arc fromId(int id, Arc) const {
232      return Parent::arcFromId(id);
233    }
234
235    Edge fromId(int id, Edge) const {
236      return Parent::edgeFromId(id);
237    }
238
239    Node oppositeNode(const Node &n, const Edge &e) const {
240      if( n == Parent::u(e))
241        return Parent::v(e);
242      else if( n == Parent::v(e))
243        return Parent::u(e);
244      else
245        return INVALID;
246    }
247
248    Arc oppositeArc(const Arc &a) const {
249      return Parent::direct(a, !Parent::direction(a));
250    }
251
252    using Parent::direct;
253    Arc direct(const Edge &e, const Node &s) const {
254      return Parent::direct(e, Parent::u(e) == s);
255    }
256
257
258    class NodeIt : public Node {
259      const Adaptor* _adaptor;
260    public:
261
262      NodeIt() {}
263
264      NodeIt(Invalid i) : Node(i) { }
265
266      explicit NodeIt(const Adaptor& adaptor) : _adaptor(&adaptor) {
267        _adaptor->first(static_cast<Node&>(*this));
268      }
269
270      NodeIt(const Adaptor& adaptor, const Node& node)
271        : Node(node), _adaptor(&adaptor) {}
272
273      NodeIt& operator++() {
274        _adaptor->next(*this);
275        return *this;
276      }
277
278    };
279
280
281    class ArcIt : public Arc {
282      const Adaptor* _adaptor;
283    public:
284
285      ArcIt() { }
286
287      ArcIt(Invalid i) : Arc(i) { }
288
289      explicit ArcIt(const Adaptor& adaptor) : _adaptor(&adaptor) {
290        _adaptor->first(static_cast<Arc&>(*this));
291      }
292
293      ArcIt(const Adaptor& adaptor, const Arc& e) :
294        Arc(e), _adaptor(&adaptor) { }
295
296      ArcIt& operator++() {
297        _adaptor->next(*this);
298        return *this;
299      }
300
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
328    class InArcIt : public Arc {
329      const Adaptor* _adaptor;
330    public:
331
332      InArcIt() { }
333
334      InArcIt(Invalid i) : Arc(i) { }
335
336      InArcIt(const Adaptor& adaptor, const Node& node)
337        : _adaptor(&adaptor) {
338        _adaptor->firstIn(*this, node);
339      }
340
341      InArcIt(const Adaptor& adaptor, const Arc& arc) :
342        Arc(arc), _adaptor(&adaptor) {}
343
344      InArcIt& operator++() {
345        _adaptor->nextIn(*this);
346        return *this;
347      }
348
349    };
350
351    class EdgeIt : public Parent::Edge {
352      const Adaptor* _adaptor;
353    public:
354
355      EdgeIt() { }
356
357      EdgeIt(Invalid i) : Edge(i) { }
358
359      explicit EdgeIt(const Adaptor& adaptor) : _adaptor(&adaptor) {
360        _adaptor->first(static_cast<Edge&>(*this));
361      }
362
363      EdgeIt(const Adaptor& adaptor, const Edge& e) :
364        Edge(e), _adaptor(&adaptor) { }
365
366      EdgeIt& operator++() {
367        _adaptor->next(*this);
368        return *this;
369      }
370
371    };
372
373    class IncEdgeIt : public Edge {
374      friend class GraphAdaptorExtender;
375      const Adaptor* _adaptor;
376      bool direction;
377    public:
378
379      IncEdgeIt() { }
380
381      IncEdgeIt(Invalid i) : Edge(i), direction(false) { }
382
383      IncEdgeIt(const Adaptor& adaptor, const Node &n) : _adaptor(&adaptor) {
384        _adaptor->firstInc(static_cast<Edge&>(*this), direction, n);
385      }
386
387      IncEdgeIt(const Adaptor& adaptor, const Edge &e, const Node &n)
388        : _adaptor(&adaptor), Edge(e) {
389        direction = (_adaptor->u(e) == n);
390      }
391
392      IncEdgeIt& operator++() {
393        _adaptor->nextInc(*this, direction);
394        return *this;
395      }
396    };
397
398    /// \brief Base node of the iterator
399    ///
400    /// Returns the base node (ie. the source in this case) of the iterator
401    Node baseNode(const OutArcIt &a) const {
402      return Parent::source(a);
403    }
404    /// \brief Running node of the iterator
405    ///
406    /// Returns the running node (ie. the target in this case) of the
407    /// iterator
408    Node runningNode(const OutArcIt &a) const {
409      return Parent::target(a);
410    }
411
412    /// \brief Base node of the iterator
413    ///
414    /// Returns the base node (ie. the target in this case) of the iterator
415    Node baseNode(const InArcIt &a) const {
416      return Parent::target(a);
417    }
418    /// \brief Running node of the iterator
419    ///
420    /// Returns the running node (ie. the source in this case) of the
421    /// iterator
422    Node runningNode(const InArcIt &a) const {
423      return Parent::source(a);
424    }
425
426    /// Base node of the iterator
427    ///
428    /// Returns the base node of the iterator
429    Node baseNode(const IncEdgeIt &e) const {
430      return e.direction ? Parent::u(e) : Parent::v(e);
431    }
432    /// Running node of the iterator
433    ///
434    /// Returns the running node of the iterator
435    Node runningNode(const IncEdgeIt &e) const {
436      return e.direction ? Parent::v(e) : Parent::u(e);
437    }
438
439  };
440
441}
442
443
444#endif
Note: See TracBrowser for help on using the repository browser.