COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/bits/iterable_graph_extender.h @ 1956:a055123339d5

Last change on this file since 1956:a055123339d5 was 1956:a055123339d5, checked in by Alpar Juttner, 14 years ago

Unified copyright notices

File size: 12.0 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_ITERABLE_GRAPH_EXTENDER_H
20#define LEMON_ITERABLE_GRAPH_EXTENDER_H
21
22#include <lemon/invalid.h>
23#include <lemon/utility.h>
24
25namespace lemon {
26 
27  template <typename _Base>
28  class IterableGraphExtender : public _Base {
29  public:
30
31    /// Indicates that the graph is undirected.
32
33    ///\todo Better name?
34    ///
35    ///\bug Should it be here?
36    typedef False UTag;
37
38    typedef _Base Parent;
39    typedef IterableGraphExtender<_Base> Graph;
40
41    typedef typename Parent::Node Node;
42    typedef typename Parent::Edge Edge;
43
44
45    class NodeIt : public Node {
46      const Graph* graph;
47    public:
48
49      NodeIt() {}
50
51      NodeIt(Invalid i) : Node(i) { }
52
53      explicit NodeIt(const Graph& _graph) : graph(&_graph) {
54        _graph.first(*static_cast<Node*>(this));
55      }
56
57      NodeIt(const Graph& _graph, const Node& node)
58        : Node(node), graph(&_graph) {}
59
60      NodeIt& operator++() {
61        graph->next(*this);
62        return *this;
63      }
64
65    };
66
67
68    class EdgeIt : public Edge {
69      const Graph* graph;
70    public:
71
72      EdgeIt() { }
73
74      EdgeIt(Invalid i) : Edge(i) { }
75
76      explicit EdgeIt(const Graph& _graph) : graph(&_graph) {
77        _graph.first(*static_cast<Edge*>(this));
78      }
79
80      EdgeIt(const Graph& _graph, const Edge& e) :
81        Edge(e), graph(&_graph) { }
82
83      EdgeIt& operator++() {
84        graph->next(*this);
85        return *this;
86      }
87
88    };
89
90
91    class OutEdgeIt : public Edge {
92      const Graph* graph;
93    public:
94
95      OutEdgeIt() { }
96
97      OutEdgeIt(Invalid i) : Edge(i) { }
98
99      OutEdgeIt(const Graph& _graph, const Node& node)
100        : graph(&_graph) {
101        _graph.firstOut(*this, node);
102      }
103
104      OutEdgeIt(const Graph& _graph, const Edge& edge)
105        : Edge(edge), graph(&_graph) {}
106
107      OutEdgeIt& operator++() {
108        graph->nextOut(*this);
109        return *this;
110      }
111
112    };
113
114
115    class InEdgeIt : public Edge {
116      const Graph* graph;
117    public:
118
119      InEdgeIt() { }
120
121      InEdgeIt(Invalid i) : Edge(i) { }
122
123      InEdgeIt(const Graph& _graph, const Node& node)
124        : graph(&_graph) {
125        _graph.firstIn(*this, node);
126      }
127
128      InEdgeIt(const Graph& _graph, const Edge& edge) :
129        Edge(edge), graph(&_graph) {}
130
131      InEdgeIt& operator++() {
132        graph->nextIn(*this);
133        return *this;
134      }
135
136    };
137
138    /// \brief Base node of the iterator
139    ///
140    /// Returns the base node (ie. the source in this case) of the iterator
141    Node baseNode(const OutEdgeIt &e) const {
142      return Parent::source((Edge)e);
143    }
144    /// \brief Running node of the iterator
145    ///
146    /// Returns the running node (ie. the target in this case) of the
147    /// iterator
148    Node runningNode(const OutEdgeIt &e) const {
149      return Parent::target((Edge)e);
150    }
151
152    /// \brief Base node of the iterator
153    ///
154    /// Returns the base node (ie. the target in this case) of the iterator
155    Node baseNode(const InEdgeIt &e) const {
156      return Parent::target((Edge)e);
157    }
158    /// \brief Running node of the iterator
159    ///
160    /// Returns the running node (ie. the source in this case) of the
161    /// iterator
162    Node runningNode(const InEdgeIt &e) const {
163      return Parent::source((Edge)e);
164    }
165
166    using Parent::first;
167
168    /// \brief The opposite node on the given edge.
169    ///
170    /// Gives back the opposite on the given edge.
171    Node oppositeNode(const Node& n, const Edge& e) const {
172      if (Parent::source(e) == n) {
173        return Parent::target(e);
174      } else {
175        return Parent::source(e);
176      }
177    }
178
179  private:
180
181    // void first(NodeIt &) const;
182    // void first(EdgeIt &) const;
183    // void first(OutEdgeIt &) const;
184    // void first(InEdgeIt &) const;
185
186  };
187
188
189
190
191
192 
193  template <typename _Base>
194  class IterableUGraphExtender : public IterableGraphExtender<_Base> {
195  public:
196
197    /// Indicates that the graph is undirected.
198
199    ///\todo Better name?
200    ///
201    ///\bug Should it be here?
202    ///\bug Should be tested in the concept checker whether it is defined
203    ///correctly.
204    typedef True UTag;
205
206    typedef IterableGraphExtender<_Base> Parent;
207    typedef IterableUGraphExtender<_Base> Graph;
208    typedef typename Parent::Node Node;
209    typedef typename Parent::Edge Edge;
210    typedef typename Parent::UEdge UEdge;
211
212    class UEdgeIt : public Parent::UEdge {
213      const Graph* graph;
214    public:
215
216      UEdgeIt() { }
217
218      UEdgeIt(Invalid i) : UEdge(i) { }
219
220      explicit UEdgeIt(const Graph& _graph) : graph(&_graph) {
221        _graph.first(*static_cast<UEdge*>(this));
222      }
223
224      UEdgeIt(const Graph& _graph, const UEdge& e) :
225        UEdge(e), graph(&_graph) { }
226
227      UEdgeIt& operator++() {
228        graph->next(*this);
229        return *this;
230      }
231
232    };
233
234    class IncEdgeIt : public Parent::UEdge {
235      const Graph* graph;
236      bool direction;
237      friend class IterableUGraphExtender;
238    public:
239
240      IncEdgeIt() { }
241
242      IncEdgeIt(Invalid i) : UEdge(i), direction(false) { }
243
244      IncEdgeIt(const Graph& _graph, const Node &n) : graph(&_graph) {
245        _graph.firstInc(*this, direction, n);
246      }
247
248      IncEdgeIt(const Graph& _graph, const UEdge &ue, const Node &n)
249        : graph(&_graph), UEdge(ue) {
250        direction = (_graph.source(ue) == n);
251      }
252
253      IncEdgeIt& operator++() {
254        graph->nextInc(*this, direction);
255        return *this;
256      }
257    };
258
259    using Parent::baseNode;
260    using Parent::runningNode;
261
262    /// Base node of the iterator
263    ///
264    /// Returns the base node of the iterator
265    Node baseNode(const IncEdgeIt &e) const {
266      return e.direction ? source(e) : target(e);
267    }
268    /// Running node of the iterator
269    ///
270    /// Returns the running node of the iterator
271    Node runningNode(const IncEdgeIt &e) const {
272      return e.direction ? target(e) : source(e);
273    }
274
275    /// \brief The opposite node on the given undirected edge.
276    ///
277    /// Gives back the opposite on the given undirected edge.
278    Node oppositeNode(const Node& n, const UEdge& e) const {
279      if (Parent::source(e) == n) {
280        return Parent::target(e);
281      } else {
282        return Parent::source(e);
283      }
284    }
285
286  };
287
288
289  template <typename _Base>
290  class IterableBpUGraphExtender : public _Base {
291  public:
292    typedef _Base Parent;
293    typedef IterableBpUGraphExtender Graph;
294   
295    typedef typename Parent::Node Node;
296    typedef typename Parent::ANode ANode;
297    typedef typename Parent::BNode BNode;
298    typedef typename Parent::Edge Edge;
299    typedef typename Parent::UEdge UEdge;
300 
301    class NodeIt : public Node {
302      const Graph* graph;
303    public:
304   
305      NodeIt() { }
306   
307      NodeIt(Invalid i) : Node(INVALID) { }
308   
309      explicit NodeIt(const Graph& _graph) : graph(&_graph) {
310        graph->first(static_cast<Node&>(*this));
311      }
312
313      NodeIt(const Graph& _graph, const Node& node)
314        : Node(node), graph(&_graph) { }
315   
316      NodeIt& operator++() {
317        graph->next(*this);
318        return *this;
319      }
320
321    };
322
323    class ANodeIt : public Node {
324      friend class IterableBpUGraphExtender;
325      const Graph* graph;
326    public:
327   
328      ANodeIt() { }
329   
330      ANodeIt(Invalid i) : Node(INVALID) { }
331   
332      explicit ANodeIt(const Graph& _graph) : graph(&_graph) {
333        graph->firstANode(static_cast<Node&>(*this));
334      }
335
336      ANodeIt(const Graph& _graph, const Node& node)
337        : Node(node), graph(&_graph) {}
338   
339      ANodeIt& operator++() {
340        graph->nextANode(*this);
341        return *this;
342      }
343    };
344
345    class BNodeIt : public Node {
346      friend class IterableBpUGraphExtender;
347      const Graph* graph;
348    public:
349   
350      BNodeIt() { }
351   
352      BNodeIt(Invalid i) : Node(INVALID) { }
353   
354      explicit BNodeIt(const Graph& _graph) : graph(&_graph) {
355        graph->firstBNode(static_cast<Node&>(*this));
356      }
357
358      BNodeIt(const Graph& _graph, const Node& node)
359        : Node(node), graph(&_graph) {}
360   
361      BNodeIt& operator++() {
362        graph->nextBNode(*this);
363        return *this;
364      }
365    };
366
367    class EdgeIt : public Edge {
368      friend class IterableBpUGraphExtender;
369      const Graph* graph;
370    public:
371   
372      EdgeIt() { }
373   
374      EdgeIt(Invalid i) : Edge(INVALID) { }
375   
376      explicit EdgeIt(const Graph& _graph) : graph(&_graph) {
377        graph->first(static_cast<Edge&>(*this));
378      }
379
380      EdgeIt(const Graph& _graph, const Edge& edge)
381        : Edge(edge), graph(&_graph) { }
382   
383      EdgeIt& operator++() {
384        graph->next(*this);
385        return *this;
386      }
387
388    };
389
390    class UEdgeIt : public UEdge {
391      friend class IterableBpUGraphExtender;
392      const Graph* graph;
393    public:
394   
395      UEdgeIt() { }
396   
397      UEdgeIt(Invalid i) : UEdge(INVALID) { }
398   
399      explicit UEdgeIt(const Graph& _graph) : graph(&_graph) {
400        graph->first(static_cast<UEdge&>(*this));
401      }
402
403      UEdgeIt(const Graph& _graph, const UEdge& edge)
404        : UEdge(edge), graph(&_graph) { }
405   
406      UEdgeIt& operator++() {
407        graph->next(*this);
408        return *this;
409      }
410    };
411
412    class OutEdgeIt : public Edge {
413      friend class IterableBpUGraphExtender;
414      const Graph* graph;
415    public:
416   
417      OutEdgeIt() { }
418   
419      OutEdgeIt(Invalid i) : Edge(i) { }
420   
421      OutEdgeIt(const Graph& _graph, const Node& node)
422        : graph(&_graph) {
423        graph->firstOut(*this, node);
424      }
425   
426      OutEdgeIt(const Graph& _graph, const Edge& edge)
427        : Edge(edge), graph(&_graph) {}
428   
429      OutEdgeIt& operator++() {
430        graph->nextOut(*this);
431        return *this;
432      }
433
434    };
435
436
437    class InEdgeIt : public Edge {
438      friend class IterableBpUGraphExtender;
439      const Graph* graph;
440    public:
441   
442      InEdgeIt() { }
443   
444      InEdgeIt(Invalid i) : Edge(i) { }
445   
446      InEdgeIt(const Graph& _graph, const Node& node)
447        : graph(&_graph) {
448        graph->firstIn(*this, node);
449      }
450   
451      InEdgeIt(const Graph& _graph, const Edge& edge) :
452        Edge(edge), graph(&_graph) {}
453   
454      InEdgeIt& operator++() {
455        graph->nextIn(*this);
456        return *this;
457      }
458
459    };
460 
461    /// \brief Base node of the iterator
462    ///
463    /// Returns the base node (ie. the source in this case) of the iterator
464    Node baseNode(const OutEdgeIt &e) const {
465      return Parent::source((Edge&)e);
466    }
467    /// \brief Running node of the iterator
468    ///
469    /// Returns the running node (ie. the target in this case) of the
470    /// iterator
471    Node runningNode(const OutEdgeIt &e) const {
472      return Parent::target((Edge&)e);
473    }
474 
475    /// \brief Base node of the iterator
476    ///
477    /// Returns the base node (ie. the target in this case) of the iterator
478    Node baseNode(const InEdgeIt &e) const {
479      return Parent::target((Edge&)e);
480    }
481    /// \brief Running node of the iterator
482    ///
483    /// Returns the running node (ie. the source in this case) of the
484    /// iterator
485    Node runningNode(const InEdgeIt &e) const {
486      return Parent::source((Edge&)e);
487    }
488 
489    class IncEdgeIt : public Parent::UEdge {
490      friend class IterableBpUGraphExtender;
491      const Graph* graph;
492      bool direction;
493    public:
494   
495      IncEdgeIt() { }
496   
497      IncEdgeIt(Invalid i) : UEdge(i), direction(true) { }
498   
499      IncEdgeIt(const Graph& _graph, const Node &n) : graph(&_graph) {
500        graph->firstInc(*this, direction, n);
501      }
502
503      IncEdgeIt(const Graph& _graph, const UEdge &ue, const Node &n)
504        : graph(&_graph), UEdge(ue) {
505        direction = (graph->source(ue) == n);
506      }
507
508      IncEdgeIt& operator++() {
509        graph->nextInc(*this, direction);
510        return *this;
511      }
512    };
513 
514
515    /// Base node of the iterator
516    ///
517    /// Returns the base node of the iterator
518    Node baseNode(const IncEdgeIt &e) const {
519      return e.direction ? source(e) : target(e);
520    }
521
522    /// Running node of the iterator
523    ///
524    /// Returns the running node of the iterator
525    Node runningNode(const IncEdgeIt &e) const {
526      return e.direction ? target(e) : source(e);
527    }
528 
529  };
530
531}
532
533#endif // LEMON_GRAPH_EXTENDER_H
Note: See TracBrowser for help on using the repository browser.