00001
00002 #ifndef LEMON_ITERABLE_GRAPH_EXTENDER_H
00003 #define LEMON_ITERABLE_GRAPH_EXTENDER_H
00004
00005 #include <lemon/invalid.h>
00006
00007 namespace lemon {
00008
00009 template <typename _Base>
00010 class IterableGraphExtender : public _Base {
00011 public:
00012
00013 typedef _Base Parent;
00014 typedef IterableGraphExtender<_Base> Graph;
00015
00016 typedef typename Parent::Node Node;
00017 typedef typename Parent::Edge Edge;
00018
00019
00020 class NodeIt : public Node {
00021 const Graph* graph;
00022 public:
00023
00024 NodeIt() {}
00025
00026 NodeIt(Invalid i) : Node(i) { }
00027
00028 explicit NodeIt(const Graph& _graph) : graph(&_graph) {
00029 _graph.first(*static_cast<Node*>(this));
00030 }
00031
00032 NodeIt(const Graph& _graph, const Node& node)
00033 : Node(node), graph(&_graph) {}
00034
00035 NodeIt& operator++() {
00036 graph->next(*this);
00037 return *this;
00038 }
00039
00040 };
00041
00042
00043 class EdgeIt : public Edge {
00044 const Graph* graph;
00045 public:
00046
00047 EdgeIt() { }
00048
00049 EdgeIt(Invalid i) : Edge(i) { }
00050
00051 explicit EdgeIt(const Graph& _graph) : graph(&_graph) {
00052 _graph.first(*static_cast<Edge*>(this));
00053 }
00054
00055 EdgeIt(const Graph& _graph, const Edge& e) :
00056 Edge(e), graph(&_graph) { }
00057
00058 EdgeIt& operator++() {
00059 graph->next(*this);
00060 return *this;
00061 }
00062
00063 };
00064
00065
00066 class OutEdgeIt : public Edge {
00067 const Graph* graph;
00068 public:
00069
00070 OutEdgeIt() { }
00071
00072 OutEdgeIt(Invalid i) : Edge(i) { }
00073
00074 OutEdgeIt(const Graph& _graph, const Node& node)
00075 : graph(&_graph) {
00076 _graph.firstOut(*this, node);
00077 }
00078
00079 OutEdgeIt(const Graph& _graph, const Edge& edge)
00080 : Edge(edge), graph(&_graph) {}
00081
00082 OutEdgeIt& operator++() {
00083 graph->nextOut(*this);
00084 return *this;
00085 }
00086
00087 };
00088
00089
00090 class InEdgeIt : public Edge {
00091 const Graph* graph;
00092 public:
00093
00094 InEdgeIt() { }
00095
00096 InEdgeIt(Invalid i) : Edge(i) { }
00097
00098 InEdgeIt(const Graph& _graph, const Node& node)
00099 : graph(&_graph) {
00100 _graph.firstIn(*this, node);
00101 }
00102
00103 InEdgeIt(const Graph& _graph, const Edge& edge) :
00104 Edge(edge), graph(&_graph) {}
00105
00106 InEdgeIt& operator++() {
00107 graph->nextIn(*this);
00108 return *this;
00109 }
00110
00111 };
00112
00118 Node baseNode(const OutEdgeIt &e) const {
00119 return source(e);
00120 }
00127 Node runningNode(const OutEdgeIt &e) const {
00128 return target(e);
00129 }
00130
00136 Node baseNode(const InEdgeIt &e) const {
00137 return target(e);
00138 }
00145 Node runningNode(const InEdgeIt &e) const {
00146 return source(e);
00147 }
00148
00149 using Parent::first;
00150
00151 private:
00152
00156
00157 void first(NodeIt &) const;
00158 void first(EdgeIt &) const;
00159 void first(OutEdgeIt &) const;
00160 void first(InEdgeIt &) const;
00161
00162 };
00163
00164
00165
00166
00167
00168
00169 template <typename _Base>
00170 class IterableUndirGraphExtender : public IterableGraphExtender<_Base> {
00171 public:
00172
00173 typedef IterableGraphExtender<_Base> Parent;
00174 typedef IterableUndirGraphExtender<_Base> Graph;
00175 typedef typename Parent::Node Node;
00176
00177 typedef typename Parent::UndirEdge UndirEdge;
00178
00179 class UndirEdgeIt : public UndirEdge {
00180 const Graph* graph;
00181 public:
00182
00183 UndirEdgeIt() { }
00184
00185 UndirEdgeIt(Invalid i) : UndirEdge(i) { }
00186
00187 explicit UndirEdgeIt(const Graph& _graph) : graph(&_graph) {
00188 _graph.first(*static_cast<UndirEdge*>(this));
00189 }
00190
00191 UndirEdgeIt(const Graph& _graph, const UndirEdge& e) :
00192 UndirEdge(e), graph(&_graph) { }
00193
00194 UndirEdgeIt& operator++() {
00195 graph->next(*this);
00196 return *this;
00197 }
00198
00199 };
00200
00201 class IncEdgeIt : public UndirEdge {
00202 const Graph* graph;
00203 bool forward;
00204 friend class IterableUndirGraphExtender;
00205 template <typename G>
00206 friend class UndirGraphExtender;
00207 public:
00208
00209 IncEdgeIt() { }
00210
00211 IncEdgeIt(Invalid i) : UndirEdge(i), forward(false) { }
00212
00213 IncEdgeIt(const Graph& _graph, const Node &n)
00214 : graph(&_graph)
00215 {
00216 _graph._dirFirstOut(*this, n);
00217 }
00218
00219 IncEdgeIt(const Graph& _graph, const UndirEdge &ue, const Node &n)
00220 : graph(&_graph), UndirEdge(ue)
00221 {
00222 forward = (_graph.source(ue) == n);
00223 }
00224
00225 IncEdgeIt& operator++() {
00226 graph->_dirNextOut(*this);
00227 return *this;
00228 }
00229 };
00230
00231 using Parent::baseNode;
00232 using Parent::runningNode;
00233
00237 Node baseNode(const IncEdgeIt &e) const {
00238 return _dirSource(e);
00239 }
00243 Node runningNode(const IncEdgeIt &e) const {
00244 return _dirTarget(e);
00245 }
00246
00247 };
00248 }
00249
00250 #endif // LEMON_GRAPH_EXTENDER_H