COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/bits/graph_adaptor_extender.h @ 1979:c2992fd74dad

Last change on this file since 1979:c2992fd74dad was 1979:c2992fd74dad, checked in by Balazs Dezso, 14 years ago

Mergeing extendermerge branch
Changes:

the extender system
resize for static size graph
UGraphExtender => UndirectGraphExtender?

UGraphExtenders with changed meaning

Some UGraphExtender /SubUGraphExtenders, DirectUGraphExtender/
GridGraph? => GridUGraph
radix sort to ansi compatible

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