COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/bits/iterable_graph_extender.h @ 1563:0853ed07a677

Last change on this file since 1563:0853ed07a677 was 1448:0274acee0e35, checked in by Alpar Juttner, 19 years ago

UndirTag? added to the graphs

File size: 5.7 KB
Line 
1// -*- c++ -*-
2#ifndef LEMON_ITERABLE_GRAPH_EXTENDER_H
3#define LEMON_ITERABLE_GRAPH_EXTENDER_H
4
5#include <lemon/invalid.h>
6#include <lemon/utility.h>
7
8namespace lemon {
9 
10  template <typename _Base>
11  class IterableGraphExtender : public _Base {
12  public:
13
14    /// Indicates that the graph is undirected.
15
16    ///\todo Better name?
17    ///
18    ///\bug Should it be here?
19    typedef False UndirTag;
20
21    typedef _Base Parent;
22    typedef IterableGraphExtender<_Base> Graph;
23
24    typedef typename Parent::Node Node;
25    typedef typename Parent::Edge Edge;
26
27
28    class NodeIt : public Node {
29      const Graph* graph;
30    public:
31
32      NodeIt() {}
33
34      NodeIt(Invalid i) : Node(i) { }
35
36      explicit NodeIt(const Graph& _graph) : graph(&_graph) {
37        _graph.first(*static_cast<Node*>(this));
38      }
39
40      NodeIt(const Graph& _graph, const Node& node)
41        : Node(node), graph(&_graph) {}
42
43      NodeIt& operator++() {
44        graph->next(*this);
45        return *this;
46      }
47
48    };
49
50
51    class EdgeIt : public Edge {
52      const Graph* graph;
53    public:
54
55      EdgeIt() { }
56
57      EdgeIt(Invalid i) : Edge(i) { }
58
59      explicit EdgeIt(const Graph& _graph) : graph(&_graph) {
60        _graph.first(*static_cast<Edge*>(this));
61      }
62
63      EdgeIt(const Graph& _graph, const Edge& e) :
64        Edge(e), graph(&_graph) { }
65
66      EdgeIt& operator++() {
67        graph->next(*this);
68        return *this;
69      }
70
71    };
72
73
74    class OutEdgeIt : public Edge {
75      const Graph* graph;
76    public:
77
78      OutEdgeIt() { }
79
80      OutEdgeIt(Invalid i) : Edge(i) { }
81
82      OutEdgeIt(const Graph& _graph, const Node& node)
83        : graph(&_graph) {
84        _graph.firstOut(*this, node);
85      }
86
87      OutEdgeIt(const Graph& _graph, const Edge& edge)
88        : Edge(edge), graph(&_graph) {}
89
90      OutEdgeIt& operator++() {
91        graph->nextOut(*this);
92        return *this;
93      }
94
95    };
96
97
98    class InEdgeIt : public Edge {
99      const Graph* graph;
100    public:
101
102      InEdgeIt() { }
103
104      InEdgeIt(Invalid i) : Edge(i) { }
105
106      InEdgeIt(const Graph& _graph, const Node& node)
107        : graph(&_graph) {
108        _graph.firstIn(*this, node);
109      }
110
111      InEdgeIt(const Graph& _graph, const Edge& edge) :
112        Edge(edge), graph(&_graph) {}
113
114      InEdgeIt& operator++() {
115        graph->nextIn(*this);
116        return *this;
117      }
118
119    };
120
121    /// Base node of the iterator
122    ///
123    /// Returns the base node (ie. the source in this case) of the iterator
124    ///
125    /// \todo Document in the concept!
126    Node baseNode(const OutEdgeIt &e) const {
127      return source(e);
128    }
129    /// Running node of the iterator
130    ///
131    /// Returns the running node (ie. the target in this case) of the
132    /// iterator
133    ///
134    /// \todo Document in the concept!
135    Node runningNode(const OutEdgeIt &e) const {
136      return target(e);
137    }
138
139    /// Base node of the iterator
140    ///
141    /// Returns the base node (ie. the target in this case) of the iterator
142    ///
143    /// \todo Document in the concept!
144    Node baseNode(const InEdgeIt &e) const {
145      return target(e);
146    }
147    /// Running node of the iterator
148    ///
149    /// Returns the running node (ie. the source in this case) of the
150    /// iterator
151    ///
152    /// \todo Document in the concept!
153    Node runningNode(const InEdgeIt &e) const {
154      return source(e);
155    }
156
157    using Parent::first;
158
159  private:
160
161    // /// \todo When (and if) we change the iterators concept to use operator*,
162    // /// then the following shadowed methods will become superfluous.
163    // /// But for now these are important safety measures.
164
165    // void first(NodeIt &) const;
166    // void first(EdgeIt &) const;
167    // void first(OutEdgeIt &) const;
168    // void first(InEdgeIt &) const;
169
170  };
171
172
173
174
175
176 
177  template <typename _Base>
178  class IterableUndirGraphExtender : public IterableGraphExtender<_Base> {
179  public:
180
181    /// Indicates that the graph is undirected.
182
183    ///\todo Better name?
184    ///
185    ///\bug Should it be here?
186    ///\bug Should be tested in the concept checker whether it is defined
187    ///correctly.
188    typedef True UndirTag;
189
190    typedef IterableGraphExtender<_Base> Parent;
191    typedef IterableUndirGraphExtender<_Base> Graph;
192    typedef typename Parent::Node Node;
193
194    typedef typename Parent::UndirEdge UndirEdge;
195
196    class UndirEdgeIt : public Parent::UndirEdge {
197      const Graph* graph;
198    public:
199
200      UndirEdgeIt() { }
201
202      UndirEdgeIt(Invalid i) : UndirEdge(i) { }
203
204      explicit UndirEdgeIt(const Graph& _graph) : graph(&_graph) {
205        _graph.first(*static_cast<UndirEdge*>(this));
206      }
207
208      UndirEdgeIt(const Graph& _graph, const UndirEdge& e) :
209        UndirEdge(e), graph(&_graph) { }
210
211      UndirEdgeIt& operator++() {
212        graph->next(*this);
213        return *this;
214      }
215
216    };
217
218    class IncEdgeIt : public Parent::UndirEdge {
219      const Graph* graph;
220      bool forward;
221      friend class IterableUndirGraphExtender;
222      template <typename G>
223      friend class UndirGraphExtender;
224    public:
225
226      IncEdgeIt() { }
227
228      IncEdgeIt(Invalid i) : UndirEdge(i), forward(false) { }
229
230      IncEdgeIt(const Graph& _graph, const Node &n)
231        : graph(&_graph)
232      {
233        _graph._dirFirstOut(*this, n);
234      }
235
236      IncEdgeIt(const Graph& _graph, const UndirEdge &ue, const Node &n)
237        : graph(&_graph), UndirEdge(ue)
238      {
239        forward = (_graph.source(ue) == n);
240      }
241
242      IncEdgeIt& operator++() {
243        graph->_dirNextOut(*this);
244        return *this;
245      }
246    };
247
248    using Parent::baseNode;
249    using Parent::runningNode;
250
251    /// Base node of the iterator
252    ///
253    /// Returns the base node of the iterator
254    Node baseNode(const IncEdgeIt &e) const {
255      return _dirSource(e);
256    }
257    /// Running node of the iterator
258    ///
259    /// Returns the running node of the iterator
260    Node runningNode(const IncEdgeIt &e) const {
261      return _dirTarget(e);
262    }
263
264  };
265}
266
267#endif // LEMON_GRAPH_EXTENDER_H
Note: See TracBrowser for help on using the repository browser.