iterable_graph_extender.h

00001 /* -*- C++ -*-
00002  *
00003  * This file is a part of LEMON, a generic C++ optimization library
00004  *
00005  * Copyright (C) 2003-2006
00006  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
00007  * (Egervary Research Group on Combinatorial Optimization, EGRES).
00008  *
00009  * Permission to use, modify and distribute this software is granted
00010  * provided that this copyright notice appears in all copies. For
00011  * precise terms see the accompanying LICENSE file.
00012  *
00013  * This software is provided "AS IS" with no warranty of any kind,
00014  * express or implied, and with no claim as to its suitability for any
00015  * purpose.
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     // void first(NodeIt &) const;
00182     // void first(EdgeIt &) const;
00183     // void first(OutEdgeIt &) const;
00184     // void first(InEdgeIt &) const;
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

Generated on Fri Feb 3 18:35:50 2006 for LEMON by  doxygen 1.4.6