COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/lemon/iterable_graph_extender.h @ 1021:fd1d073b6557

Last change on this file since 1021:fd1d073b6557 was 1021:fd1d073b6557, checked in by Mihaly Barasz, 16 years ago

Advances in UndirGraph?.

File size: 4.4 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    using Parent::first;
114
115  private:
116
117    /// \todo When (and if) we change the iterators concept to use operator*,
118    /// then the following shadowed methods will become superfluous.
119    /// But for now these are important safety measures.
120
121    void first(NodeIt &) const;
122    void first(EdgeIt &) const;
123    void first(OutEdgeIt &) const;
124    void first(InEdgeIt &) const;
125
126  };
127 
128  template <typename _Base>
129  class IterableUndirGraphExtender : public IterableGraphExtender<_Base> {
130  public:
131
132    typedef IterableGraphExtender<_Base> Parent;
133    typedef IterableUndirGraphExtender<_Base> Graph;
134    typedef typename Parent::Node Node;
135
136    typedef typename Parent::UndirEdge UndirEdge;
137
138    class UndirEdgeIt : public UndirEdge {
139      const Graph* graph;
140    public:
141
142      UndirEdgeIt() { }
143
144      UndirEdgeIt(Invalid i) : UndirEdge(i) { }
145
146      explicit UndirEdgeIt(const Graph& _graph) : graph(&_graph) {
147        _graph.first(*static_cast<UndirEdge*>(this));
148      }
149
150      UndirEdgeIt(const Graph& _graph, const UndirEdge& e) :
151        UndirEdge(e), graph(&_graph) { }
152
153      UndirEdgeIt& operator++() {
154        graph->next(*this);
155        return *this;
156      }
157
158    };
159
160    class UndirIncEdgeIt : public UndirEdge {
161      const Graph* graph;
162      bool forward;
163      friend class IterableUndirGraphExtender;
164      template <typename G>
165      friend class UndirGraphExtender;
166    public:
167
168      UndirIncEdgeIt() { }
169
170      UndirIncEdgeIt(Invalid i) : UndirEdge(i), forward(false) { }
171
172      explicit UndirIncEdgeIt(const Graph& _graph, const Node &n)
173        : graph(&_graph)
174      {
175        _graph._dirFirstOut(*this, n);
176      }
177
178      // FIXME: Do we need this type of constructor here?
179      // UndirIncEdgeIt(const Graph& _graph, const UndirEdge& e) :
180      //   UndirEdge(e), graph(&_graph) { }
181
182      UndirIncEdgeIt& operator++() {
183        graph->_dirNextOut(*this);
184        return *this;
185      }
186    };
187
188    Node source(const UndirIncEdgeIt &e) const {
189      return _dirSource(e);
190    }
191
192    /// \todo Shouldn't the "source" of an undirected edge be called "aNode"
193    /// or something???
194    using Parent::source;
195
196    /// Target of the given Edge.
197    Node target(const UndirIncEdgeIt &e) const {
198      return _dirTarget(e);
199    }
200
201    /// \todo Shouldn't the "target" of an undirected edge be called "bNode"
202    /// or something???
203    using Parent::target;
204
205  };
206}
207
208#endif // LEMON_GRAPH_EXTENDER_H
Note: See TracBrowser for help on using the repository browser.