COIN-OR::LEMON - Graph Library

source: lemon/lemon/bits/graph_adaptor_extender.h @ 451:09e416d35896

Last change on this file since 451:09e416d35896 was 432:76287c8caa26, checked in by Balazs Dezso <deba@…>, 15 years ago

Reorganication of graph adaptors and doc improvements (#67)

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