COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/bits/graph_adaptor_extender.h @ 2000:ebcc93ead7da

Last change on this file since 2000:ebcc93ead7da was 1996:5dc13b93f8b4, checked in by Balazs Dezso, 14 years ago

Some documentation arrangement modification

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