COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/bits/iterable_graph_extender.h @ 1744:51d5d41e15b1

Last change on this file since 1744:51d5d41e15b1 was 1704:467d7927a901, checked in by Balazs Dezso, 18 years ago

findUndirEdge, ConUndirEdgeIt?
some modification in the undir graph extenders

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 direction;
220      friend class IterableUndirGraphExtender;
221    public:
222
223      IncEdgeIt() { }
224
225      IncEdgeIt(Invalid i) : UndirEdge(i), direction(false) { }
226
227      IncEdgeIt(const Graph& _graph, const Node &n) : graph(&_graph) {
228        _graph.firstInc(*this, direction, n);
229      }
230
231      IncEdgeIt(const Graph& _graph, const UndirEdge &ue, const Node &n)
232        : graph(&_graph), UndirEdge(ue) {
233        direction = (_graph.source(ue) == n);
234      }
235
236      IncEdgeIt& operator++() {
237        graph->nextInc(*this, direction);
238        return *this;
239      }
240    };
241
242    using Parent::baseNode;
243    using Parent::runningNode;
244
245    /// Base node of the iterator
246    ///
247    /// Returns the base node of the iterator
248    Node baseNode(const IncEdgeIt &e) const {
249      return e.direction ? source(e) : target(e);
250    }
251    /// Running node of the iterator
252    ///
253    /// Returns the running node of the iterator
254    Node runningNode(const IncEdgeIt &e) const {
255      return e.direction ? target(e) : source(e);
256    }
257
258    /// \brief The opposite node on the given undirected edge.
259    ///
260    /// Gives back the opposite on the given undirected edge.
261    Node oppositeNode(const Node& n, const UndirEdge& e) const {
262      if (Parent::source(e) == n) {
263        return Parent::target(e);
264      } else {
265        return Parent::source(e);
266      }
267    }
268
269  };
270}
271
272#endif // LEMON_GRAPH_EXTENDER_H
Note: See TracBrowser for help on using the repository browser.