COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/lemon/bits/iterable_graph_extender.h @ 1307:d4acebef7276

Last change on this file since 1307:d4acebef7276 was 1307:d4acebef7276, checked in by Balazs Dezso, 20 years ago

Stuffs moved into bits

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