COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/bits/iterable_graph_extender.h @ 1627:3fd1ba6e9872

Last change on this file since 1627:3fd1ba6e9872 was 1627:3fd1ba6e9872, checked in by Balazs Dezso, 14 years ago

Some modification on the undirected graph interface.
Doc improvments

File size: 6.0 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    /// \brief Base node of the iterator
122    ///
123    /// Returns the base node (ie. the source in this case) of the iterator
124    Node baseNode(const OutEdgeIt &e) const {
125      return Parent::source((Edge)e);
126    }
127    /// \brief Running node of the iterator
128    ///
129    /// Returns the running node (ie. the target in this case) of the
130    /// iterator
131    Node runningNode(const OutEdgeIt &e) const {
132      return Parent::target((Edge)e);
133    }
134
135    /// \brief Base node of the iterator
136    ///
137    /// Returns the base node (ie. the target in this case) of the iterator
138    Node baseNode(const InEdgeIt &e) const {
139      return Parent::target((Edge)e);
140    }
141    /// \brief Running node of the iterator
142    ///
143    /// Returns the running node (ie. the source in this case) of the
144    /// iterator
145    Node runningNode(const InEdgeIt &e) const {
146      return Parent::source((Edge)e);
147    }
148
149    using Parent::first;
150
151    /// \brief The opposite node on the given edge.
152    ///
153    /// Gives back the opposite on the given edge.
154    Node oppositeNode(const Node& n, const Edge& e) const {
155      if (Parent::source(e) == n) {
156        return Parent::target(e);
157      } else {
158        return Parent::source(e);
159      }
160    }
161
162  private:
163
164    // void first(NodeIt &) const;
165    // void first(EdgeIt &) const;
166    // void first(OutEdgeIt &) const;
167    // void first(InEdgeIt &) const;
168
169  };
170
171
172
173
174
175 
176  template <typename _Base>
177  class IterableUndirGraphExtender : public IterableGraphExtender<_Base> {
178  public:
179
180    /// Indicates that the graph is undirected.
181
182    ///\todo Better name?
183    ///
184    ///\bug Should it be here?
185    ///\bug Should be tested in the concept checker whether it is defined
186    ///correctly.
187    typedef True UndirTag;
188
189    typedef IterableGraphExtender<_Base> Parent;
190    typedef IterableUndirGraphExtender<_Base> Graph;
191    typedef typename Parent::Node Node;
192    typedef typename Parent::Edge Edge;
193    typedef typename Parent::UndirEdge UndirEdge;
194
195    class UndirEdgeIt : public Parent::UndirEdge {
196      const Graph* graph;
197    public:
198
199      UndirEdgeIt() { }
200
201      UndirEdgeIt(Invalid i) : UndirEdge(i) { }
202
203      explicit UndirEdgeIt(const Graph& _graph) : graph(&_graph) {
204        _graph.first(*static_cast<UndirEdge*>(this));
205      }
206
207      UndirEdgeIt(const Graph& _graph, const UndirEdge& e) :
208        UndirEdge(e), graph(&_graph) { }
209
210      UndirEdgeIt& operator++() {
211        graph->next(*this);
212        return *this;
213      }
214
215    };
216
217    class IncEdgeIt : public Parent::UndirEdge {
218      const Graph* graph;
219      bool forward;
220      friend class IterableUndirGraphExtender;
221      template <typename G>
222      friend class UndirGraphExtender;
223    public:
224
225      IncEdgeIt() { }
226
227      IncEdgeIt(Invalid i) : UndirEdge(i), forward(false) { }
228
229      IncEdgeIt(const Graph& _graph, const Node &n)
230        : graph(&_graph)
231      {
232        _graph._dirFirstOut(*this, n);
233      }
234
235      IncEdgeIt(const Graph& _graph, const UndirEdge &ue, const Node &n)
236        : graph(&_graph), UndirEdge(ue)
237      {
238        forward = (_graph.source(ue) == n);
239      }
240
241      IncEdgeIt& operator++() {
242        graph->_dirNextOut(*this);
243        return *this;
244      }
245    };
246
247    using Parent::baseNode;
248    using Parent::runningNode;
249
250    /// Base node of the iterator
251    ///
252    /// Returns the base node of the iterator
253    Node baseNode(const IncEdgeIt &e) const {
254      return _dirSource(e);
255    }
256    /// Running node of the iterator
257    ///
258    /// Returns the running node of the iterator
259    Node runningNode(const IncEdgeIt &e) const {
260      return _dirTarget(e);
261    }
262
263    /// \brief The opposite node on the given undirected edge.
264    ///
265    /// Gives back the opposite on the given undirected edge.
266    Node oppositeNode(const Node& n, const UndirEdge& e) const {
267      if (Parent::source(e) == n) {
268        return Parent::target(e);
269      } else {
270        return Parent::source(e);
271      }
272    }
273
274  };
275}
276
277#endif // LEMON_GRAPH_EXTENDER_H
Note: See TracBrowser for help on using the repository browser.