00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019 #ifndef LEMON_ITERABLE_GRAPH_EXTENDER_H
00020 #define LEMON_ITERABLE_GRAPH_EXTENDER_H
00021
00022 #include <lemon/invalid.h>
00023 #include <lemon/utility.h>
00024
00025 namespace lemon {
00026
00027 template <typename _Base>
00028 class IterableGraphExtender : public _Base {
00029 public:
00030
00032
00036 typedef False UTag;
00037
00038 typedef _Base Parent;
00039 typedef IterableGraphExtender<_Base> Graph;
00040
00041 typedef typename Parent::Node Node;
00042 typedef typename Parent::Edge Edge;
00043
00044
00045 class NodeIt : public Node {
00046 const Graph* graph;
00047 public:
00048
00049 NodeIt() {}
00050
00051 NodeIt(Invalid i) : Node(i) { }
00052
00053 explicit NodeIt(const Graph& _graph) : graph(&_graph) {
00054 _graph.first(*static_cast<Node*>(this));
00055 }
00056
00057 NodeIt(const Graph& _graph, const Node& node)
00058 : Node(node), graph(&_graph) {}
00059
00060 NodeIt& operator++() {
00061 graph->next(*this);
00062 return *this;
00063 }
00064
00065 };
00066
00067
00068 class EdgeIt : public Edge {
00069 const Graph* graph;
00070 public:
00071
00072 EdgeIt() { }
00073
00074 EdgeIt(Invalid i) : Edge(i) { }
00075
00076 explicit EdgeIt(const Graph& _graph) : graph(&_graph) {
00077 _graph.first(*static_cast<Edge*>(this));
00078 }
00079
00080 EdgeIt(const Graph& _graph, const Edge& e) :
00081 Edge(e), graph(&_graph) { }
00082
00083 EdgeIt& operator++() {
00084 graph->next(*this);
00085 return *this;
00086 }
00087
00088 };
00089
00090
00091 class OutEdgeIt : public Edge {
00092 const Graph* graph;
00093 public:
00094
00095 OutEdgeIt() { }
00096
00097 OutEdgeIt(Invalid i) : Edge(i) { }
00098
00099 OutEdgeIt(const Graph& _graph, const Node& node)
00100 : graph(&_graph) {
00101 _graph.firstOut(*this, node);
00102 }
00103
00104 OutEdgeIt(const Graph& _graph, const Edge& edge)
00105 : Edge(edge), graph(&_graph) {}
00106
00107 OutEdgeIt& operator++() {
00108 graph->nextOut(*this);
00109 return *this;
00110 }
00111
00112 };
00113
00114
00115 class InEdgeIt : public Edge {
00116 const Graph* graph;
00117 public:
00118
00119 InEdgeIt() { }
00120
00121 InEdgeIt(Invalid i) : Edge(i) { }
00122
00123 InEdgeIt(const Graph& _graph, const Node& node)
00124 : graph(&_graph) {
00125 _graph.firstIn(*this, node);
00126 }
00127
00128 InEdgeIt(const Graph& _graph, const Edge& edge) :
00129 Edge(edge), graph(&_graph) {}
00130
00131 InEdgeIt& operator++() {
00132 graph->nextIn(*this);
00133 return *this;
00134 }
00135
00136 };
00137
00141 Node baseNode(const OutEdgeIt &e) const {
00142 return Parent::source((Edge)e);
00143 }
00148 Node runningNode(const OutEdgeIt &e) const {
00149 return Parent::target((Edge)e);
00150 }
00151
00155 Node baseNode(const InEdgeIt &e) const {
00156 return Parent::target((Edge)e);
00157 }
00162 Node runningNode(const InEdgeIt &e) const {
00163 return Parent::source((Edge)e);
00164 }
00165
00166 using Parent::first;
00167
00171 Node oppositeNode(const Node& n, const Edge& e) const {
00172 if (Parent::source(e) == n) {
00173 return Parent::target(e);
00174 } else {
00175 return Parent::source(e);
00176 }
00177 }
00178
00179 private:
00180
00181
00182
00183
00184
00185
00186 };
00187
00188
00189
00190
00191
00192
00193 template <typename _Base>
00194 class IterableUGraphExtender : public IterableGraphExtender<_Base> {
00195 public:
00196
00198
00204 typedef True UTag;
00205
00206 typedef IterableGraphExtender<_Base> Parent;
00207 typedef IterableUGraphExtender<_Base> Graph;
00208 typedef typename Parent::Node Node;
00209 typedef typename Parent::Edge Edge;
00210 typedef typename Parent::UEdge UEdge;
00211
00212 class UEdgeIt : public Parent::UEdge {
00213 const Graph* graph;
00214 public:
00215
00216 UEdgeIt() { }
00217
00218 UEdgeIt(Invalid i) : UEdge(i) { }
00219
00220 explicit UEdgeIt(const Graph& _graph) : graph(&_graph) {
00221 _graph.first(*static_cast<UEdge*>(this));
00222 }
00223
00224 UEdgeIt(const Graph& _graph, const UEdge& e) :
00225 UEdge(e), graph(&_graph) { }
00226
00227 UEdgeIt& operator++() {
00228 graph->next(*this);
00229 return *this;
00230 }
00231
00232 };
00233
00234 class IncEdgeIt : public Parent::UEdge {
00235 const Graph* graph;
00236 bool direction;
00237 friend class IterableUGraphExtender;
00238 public:
00239
00240 IncEdgeIt() { }
00241
00242 IncEdgeIt(Invalid i) : UEdge(i), direction(false) { }
00243
00244 IncEdgeIt(const Graph& _graph, const Node &n) : graph(&_graph) {
00245 _graph.firstInc(*this, direction, n);
00246 }
00247
00248 IncEdgeIt(const Graph& _graph, const UEdge &ue, const Node &n)
00249 : graph(&_graph), UEdge(ue) {
00250 direction = (_graph.source(ue) == n);
00251 }
00252
00253 IncEdgeIt& operator++() {
00254 graph->nextInc(*this, direction);
00255 return *this;
00256 }
00257 };
00258
00259 using Parent::baseNode;
00260 using Parent::runningNode;
00261
00265 Node baseNode(const IncEdgeIt &e) const {
00266 return e.direction ? source(e) : target(e);
00267 }
00271 Node runningNode(const IncEdgeIt &e) const {
00272 return e.direction ? target(e) : source(e);
00273 }
00274
00278 Node oppositeNode(const Node& n, const UEdge& e) const {
00279 if (Parent::source(e) == n) {
00280 return Parent::target(e);
00281 } else {
00282 return Parent::source(e);
00283 }
00284 }
00285
00286 };
00287
00288
00289 template <typename _Base>
00290 class IterableBpUGraphExtender : public _Base {
00291 public:
00292 typedef _Base Parent;
00293 typedef IterableBpUGraphExtender Graph;
00294
00295 typedef typename Parent::Node Node;
00296 typedef typename Parent::ANode ANode;
00297 typedef typename Parent::BNode BNode;
00298 typedef typename Parent::Edge Edge;
00299 typedef typename Parent::UEdge UEdge;
00300
00301 class NodeIt : public Node {
00302 const Graph* graph;
00303 public:
00304
00305 NodeIt() { }
00306
00307 NodeIt(Invalid i) : Node(INVALID) { }
00308
00309 explicit NodeIt(const Graph& _graph) : graph(&_graph) {
00310 graph->first(static_cast<Node&>(*this));
00311 }
00312
00313 NodeIt(const Graph& _graph, const Node& node)
00314 : Node(node), graph(&_graph) { }
00315
00316 NodeIt& operator++() {
00317 graph->next(*this);
00318 return *this;
00319 }
00320
00321 };
00322
00323 class ANodeIt : public Node {
00324 friend class IterableBpUGraphExtender;
00325 const Graph* graph;
00326 public:
00327
00328 ANodeIt() { }
00329
00330 ANodeIt(Invalid i) : Node(INVALID) { }
00331
00332 explicit ANodeIt(const Graph& _graph) : graph(&_graph) {
00333 graph->firstANode(static_cast<Node&>(*this));
00334 }
00335
00336 ANodeIt(const Graph& _graph, const Node& node)
00337 : Node(node), graph(&_graph) {}
00338
00339 ANodeIt& operator++() {
00340 graph->nextANode(*this);
00341 return *this;
00342 }
00343 };
00344
00345 class BNodeIt : public Node {
00346 friend class IterableBpUGraphExtender;
00347 const Graph* graph;
00348 public:
00349
00350 BNodeIt() { }
00351
00352 BNodeIt(Invalid i) : Node(INVALID) { }
00353
00354 explicit BNodeIt(const Graph& _graph) : graph(&_graph) {
00355 graph->firstBNode(static_cast<Node&>(*this));
00356 }
00357
00358 BNodeIt(const Graph& _graph, const Node& node)
00359 : Node(node), graph(&_graph) {}
00360
00361 BNodeIt& operator++() {
00362 graph->nextBNode(*this);
00363 return *this;
00364 }
00365 };
00366
00367 class EdgeIt : public Edge {
00368 friend class IterableBpUGraphExtender;
00369 const Graph* graph;
00370 public:
00371
00372 EdgeIt() { }
00373
00374 EdgeIt(Invalid i) : Edge(INVALID) { }
00375
00376 explicit EdgeIt(const Graph& _graph) : graph(&_graph) {
00377 graph->first(static_cast<Edge&>(*this));
00378 }
00379
00380 EdgeIt(const Graph& _graph, const Edge& edge)
00381 : Edge(edge), graph(&_graph) { }
00382
00383 EdgeIt& operator++() {
00384 graph->next(*this);
00385 return *this;
00386 }
00387
00388 };
00389
00390 class UEdgeIt : public UEdge {
00391 friend class IterableBpUGraphExtender;
00392 const Graph* graph;
00393 public:
00394
00395 UEdgeIt() { }
00396
00397 UEdgeIt(Invalid i) : UEdge(INVALID) { }
00398
00399 explicit UEdgeIt(const Graph& _graph) : graph(&_graph) {
00400 graph->first(static_cast<UEdge&>(*this));
00401 }
00402
00403 UEdgeIt(const Graph& _graph, const UEdge& edge)
00404 : UEdge(edge), graph(&_graph) { }
00405
00406 UEdgeIt& operator++() {
00407 graph->next(*this);
00408 return *this;
00409 }
00410 };
00411
00412 class OutEdgeIt : public Edge {
00413 friend class IterableBpUGraphExtender;
00414 const Graph* graph;
00415 public:
00416
00417 OutEdgeIt() { }
00418
00419 OutEdgeIt(Invalid i) : Edge(i) { }
00420
00421 OutEdgeIt(const Graph& _graph, const Node& node)
00422 : graph(&_graph) {
00423 graph->firstOut(*this, node);
00424 }
00425
00426 OutEdgeIt(const Graph& _graph, const Edge& edge)
00427 : Edge(edge), graph(&_graph) {}
00428
00429 OutEdgeIt& operator++() {
00430 graph->nextOut(*this);
00431 return *this;
00432 }
00433
00434 };
00435
00436
00437 class InEdgeIt : public Edge {
00438 friend class IterableBpUGraphExtender;
00439 const Graph* graph;
00440 public:
00441
00442 InEdgeIt() { }
00443
00444 InEdgeIt(Invalid i) : Edge(i) { }
00445
00446 InEdgeIt(const Graph& _graph, const Node& node)
00447 : graph(&_graph) {
00448 graph->firstIn(*this, node);
00449 }
00450
00451 InEdgeIt(const Graph& _graph, const Edge& edge) :
00452 Edge(edge), graph(&_graph) {}
00453
00454 InEdgeIt& operator++() {
00455 graph->nextIn(*this);
00456 return *this;
00457 }
00458
00459 };
00460
00464 Node baseNode(const OutEdgeIt &e) const {
00465 return Parent::source((Edge&)e);
00466 }
00471 Node runningNode(const OutEdgeIt &e) const {
00472 return Parent::target((Edge&)e);
00473 }
00474
00478 Node baseNode(const InEdgeIt &e) const {
00479 return Parent::target((Edge&)e);
00480 }
00485 Node runningNode(const InEdgeIt &e) const {
00486 return Parent::source((Edge&)e);
00487 }
00488
00489 class IncEdgeIt : public Parent::UEdge {
00490 friend class IterableBpUGraphExtender;
00491 const Graph* graph;
00492 bool direction;
00493 public:
00494
00495 IncEdgeIt() { }
00496
00497 IncEdgeIt(Invalid i) : UEdge(i), direction(true) { }
00498
00499 IncEdgeIt(const Graph& _graph, const Node &n) : graph(&_graph) {
00500 graph->firstInc(*this, direction, n);
00501 }
00502
00503 IncEdgeIt(const Graph& _graph, const UEdge &ue, const Node &n)
00504 : graph(&_graph), UEdge(ue) {
00505 direction = (graph->source(ue) == n);
00506 }
00507
00508 IncEdgeIt& operator++() {
00509 graph->nextInc(*this, direction);
00510 return *this;
00511 }
00512 };
00513
00514
00518 Node baseNode(const IncEdgeIt &e) const {
00519 return e.direction ? source(e) : target(e);
00520 }
00521
00525 Node runningNode(const IncEdgeIt &e) const {
00526 return e.direction ? target(e) : source(e);
00527 }
00528
00529 };
00530
00531 }
00532
00533 #endif // LEMON_GRAPH_EXTENDER_H