COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/lemon/iterable_graph_extender.h @ 1106:0a7d604a9763

Last change on this file since 1106:0a7d604a9763 was 1030:c8a41699e613, checked in by Mihaly Barasz, 19 years ago

Undirected graph documentation and concept refinements.

  • quite a few bug fixes
  • concept::UndirGraph? is almost complete and looks quite good.
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 IncEdgeIt : 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      IncEdgeIt() { }
169
170      IncEdgeIt(Invalid i) : UndirEdge(i), forward(false) { }
171
172      explicit IncEdgeIt(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      // IncEdgeIt(const Graph& _graph, const Edge& e) :
180      //   UndirEdge(e), graph(&_graph), forward(_graph.forward(e)) { }
181      // or
182      // IncEdgeIt(const Graph& _graph, const Node& n,
183      //    Const UndirEdge &e) ... ?
184
185      IncEdgeIt& operator++() {
186        graph->_dirNextOut(*this);
187        return *this;
188      }
189    };
190
191    Node source(const IncEdgeIt &e) const {
192      return _dirSource(e);
193    }
194
195    /// \todo Shouldn't the "source" of an undirected edge be called "aNode"
196    /// or something???
197    using Parent::source;
198
199    /// Target of the given Edge.
200    Node target(const IncEdgeIt &e) const {
201      return _dirTarget(e);
202    }
203
204    /// \todo Shouldn't the "target" of an undirected edge be called "bNode"
205    /// or something???
206    using Parent::target;
207
208  };
209}
210
211#endif // LEMON_GRAPH_EXTENDER_H
Note: See TracBrowser for help on using the repository browser.