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_GRAPH_EXTENDER_H
00020 #define LEMON_GRAPH_EXTENDER_H
00021 
00022 #include <lemon/invalid.h>
00023 #include <lemon/error.h>
00024 
00025 namespace lemon {
00026 
00027   template <typename _Base>
00028   class GraphExtender : public _Base {
00029   public:
00030 
00031     typedef _Base Parent;
00032     typedef GraphExtender Graph;
00033 
00034     typedef typename Parent::Node Node;
00035     typedef typename Parent::Edge Edge;
00036 
00037     int maxId(Node) const {
00038       return Parent::maxNodeId();
00039     }
00040 
00041     int maxId(Edge) const {
00042       return Parent::maxEdgeId();
00043     }
00044 
00045     Node fromId(int id, Node) const {
00046       return Parent::nodeFromId(id);
00047     }
00048 
00049     Edge fromId(int id, Edge) const {
00050       return Parent::edgeFromId(id);
00051     }
00052 
00053     Node oppositeNode(const Node &n, const Edge &e) const {
00054       if (n == Parent::source(e))
00055         return Parent::target(e);
00056       else if(n==Parent::target(e))
00057         return Parent::source(e);
00058       else
00059         return INVALID;
00060     }
00061 
00062   };
00063 
00064   template <typename _Base>
00065   class UGraphExtender : public _Base {
00066     typedef _Base Parent;
00067     typedef UGraphExtender Graph;
00068 
00069   public:
00070 
00071     typedef typename Parent::Edge UEdge;
00072     typedef typename Parent::Node Node;
00073 
00074     class Edge : public UEdge {
00075       friend class UGraphExtender;
00076 
00077     protected:
00078       // FIXME: Marci use opposite logic in his graph adaptors. It would
00079       // be reasonable to syncronize...
00080       bool forward;
00081 
00082       Edge(const UEdge &ue, bool _forward) :
00083         UEdge(ue), forward(_forward) {}
00084 
00085     public:
00086       Edge() {}
00087 
00089       Edge(Invalid i) : UEdge(i), forward(true) {}
00090 
00091       bool operator==(const Edge &that) const {
00092         return forward==that.forward && UEdge(*this)==UEdge(that);
00093       }
00094       bool operator!=(const Edge &that) const {
00095         return forward!=that.forward || UEdge(*this)!=UEdge(that);
00096       }
00097       bool operator<(const Edge &that) const {
00098         return forward<that.forward ||
00099           (!(that.forward<forward) && UEdge(*this)<UEdge(that));
00100       }
00101     };
00102 
00103 
00107     Edge oppositeEdge(const Edge &e) const {
00108       return Edge(e,!e.forward);
00109     }
00110 
00111   public:
00114     using Parent::source;
00115 
00117     Node source(const Edge &e) const {
00118       return e.forward ? Parent::source(e) : Parent::target(e);
00119     }
00120 
00123     using Parent::target;
00124 
00126     Node target(const Edge &e) const {
00127       return e.forward ? Parent::target(e) : Parent::source(e);
00128     }
00129 
00130     Node oppositeNode(const Node &n, const UEdge &e) const {
00131       if( n == Parent::source(e))
00132         return Parent::target(e);
00133       else if( n == Parent::target(e))
00134         return Parent::source(e);
00135       else
00136         return INVALID;
00137     }
00138 
00144     Edge direct(const UEdge &ue, const Node &s) const {
00145       return Edge(ue, s == source(ue));
00146     }
00147 
00153     Edge direct(const UEdge &ue, bool d) const {
00154       return Edge(ue, d);
00155     }
00156 
00162     bool direction(const Edge &e) const { return e.forward; }
00163 
00164 
00165     using Parent::first;
00166     void first(Edge &e) const {
00167       Parent::first(e);
00168       e.forward=true;
00169     }
00170 
00171     using Parent::next;
00172     void next(Edge &e) const {
00173       if( e.forward ) {
00174         e.forward = false;
00175       }
00176       else {
00177         Parent::next(e);
00178         e.forward = true;
00179       }
00180     }
00181 
00182   public:
00183 
00184     void firstOut(Edge &e, const Node &n) const {
00185       Parent::firstIn(e,n);
00186       if( UEdge(e) != INVALID ) {
00187         e.forward = false;
00188       }
00189       else {
00190         Parent::firstOut(e,n);
00191         e.forward = true;
00192       }
00193     }
00194     void nextOut(Edge &e) const {
00195       if( ! e.forward ) {
00196         Node n = Parent::target(e);
00197         Parent::nextIn(e);
00198         if( UEdge(e) == INVALID ) {
00199           Parent::firstOut(e, n);
00200           e.forward = true;
00201         }
00202       }
00203       else {
00204         Parent::nextOut(e);
00205       }
00206     }
00207 
00208     void firstIn(Edge &e, const Node &n) const {
00209       Parent::firstOut(e,n);
00210       if( UEdge(e) != INVALID ) {
00211         e.forward = false;
00212       }
00213       else {
00214         Parent::firstIn(e,n);
00215         e.forward = true;
00216       }
00217     }
00218     void nextIn(Edge &e) const {
00219       if( ! e.forward ) {
00220         Node n = Parent::source(e);
00221         Parent::nextOut(e);
00222         if( UEdge(e) == INVALID ) {
00223           Parent::firstIn(e, n);
00224           e.forward = true;
00225         }
00226       }
00227       else {
00228         Parent::nextIn(e);
00229       }
00230     }
00231 
00232     void firstInc(UEdge &e, const Node &n) const {
00233       Parent::firstOut(e, n);
00234       if (e != INVALID) return;
00235       Parent::firstIn(e, n);
00236     }
00237     void nextInc(UEdge &e, const Node &n) const {
00238       if (Parent::source(e) == n) {
00239         Parent::nextOut(e);
00240         if (e != INVALID) return;
00241         Parent::firstIn(e, n);
00242       } else {
00243         Parent::nextIn(e);
00244       }
00245     }
00246 
00247     void firstInc(UEdge &e, bool &d, const Node &n) const {
00248       d = true;
00249       Parent::firstOut(e, n);
00250       if (e != INVALID) return;
00251       d = false;
00252       Parent::firstIn(e, n);
00253     }
00254     void nextInc(UEdge &e, bool &d) const {
00255       if (d) {
00256         Node s = Parent::source(e);
00257         Parent::nextOut(e);
00258         if (e != INVALID) return;
00259         d = false;
00260         Parent::firstIn(e, s);
00261       } else {
00262         Parent::nextIn(e);
00263       }
00264     }
00265 
00266     // Miscellaneous stuff:
00267 
00270 
00271     // using Parent::id;
00272     // Using "using" is not a good idea, cause it could be that there is
00273     // no "id" in Parent...
00274 
00275     int id(const Node &n) const {
00276       return Parent::id(n);
00277     }
00278 
00279     int id(const UEdge &e) const {
00280       return Parent::id(e);
00281     }
00282 
00283     int id(const Edge &e) const {
00284       return 2 * Parent::id(e) + int(e.forward);
00285     }
00286 
00287     int maxNodeId() const {
00288       return Parent::maxNodeId();
00289     }
00290 
00291     int maxEdgeId() const {
00292       return 2 * Parent::maxEdgeId() + 1;
00293     }
00294 
00295     int maxUEdgeId() const {
00296       return Parent::maxEdgeId();
00297     }
00298 
00299     int maxId(Node) const {
00300       return maxNodeId();
00301     }
00302 
00303     int maxId(Edge) const {
00304       return maxEdgeId();
00305     }
00306     int maxId(UEdge) const {
00307       return maxUEdgeId();
00308     }
00309 
00310     int edgeNum() const {
00311       return 2 * Parent::edgeNum();
00312     }
00313 
00314     int uEdgeNum() const {
00315       return Parent::edgeNum();
00316     }
00317 
00318     Node nodeFromId(int id) const {
00319       return Parent::nodeFromId(id);
00320     }
00321 
00322     Edge edgeFromId(int id) const {
00323       return direct(Parent::edgeFromId(id >> 1), bool(id & 1));
00324     }
00325 
00326     UEdge uEdgeFromId(int id) const {
00327       return Parent::edgeFromId(id >> 1);
00328     }
00329 
00330     Node fromId(int id, Node) const {
00331       return nodeFromId(id);
00332     }
00333 
00334     Edge fromId(int id, Edge) const {
00335       return edgeFromId(id);
00336     }
00337 
00338     UEdge fromId(int id, UEdge) const {
00339       return uEdgeFromId(id);
00340     }
00341 
00342 
00343     Edge findEdge(Node source, Node target, Edge prev) const {
00344       if (prev == INVALID) {
00345         UEdge edge = Parent::findEdge(source, target);
00346         if (edge != INVALID) return direct(edge, true);
00347         edge = Parent::findEdge(target, source);
00348         if (edge != INVALID) return direct(edge, false);
00349       } else if (direction(prev)) {
00350         UEdge edge = Parent::findEdge(source, target, prev);
00351         if (edge != INVALID) return direct(edge, true);
00352         edge = Parent::findEdge(target, source);
00353         if (edge != INVALID) return direct(edge, false);        
00354       } else {
00355         UEdge edge = Parent::findEdge(target, source, prev);
00356         if (edge != INVALID) return direct(edge, false);              
00357       }
00358       return INVALID;
00359     }
00360 
00361     UEdge findUEdge(Node source, Node target, UEdge prev) const {
00362       if (prev == INVALID) {
00363         UEdge edge = Parent::findEdge(source, target);
00364         if (edge != INVALID) return edge;
00365         edge = Parent::findEdge(target, source);
00366         if (edge != INVALID) return edge;
00367       } else if (Parent::source(prev) == source) {
00368         UEdge edge = Parent::findEdge(source, target, prev);
00369         if (edge != INVALID) return edge;
00370         edge = Parent::findEdge(target, source);
00371         if (edge != INVALID) return edge;       
00372       } else {
00373         UEdge edge = Parent::findEdge(target, source, prev);
00374         if (edge != INVALID) return edge;             
00375       }
00376       return INVALID;
00377     }
00378 
00379   };
00380 
00381 
00382   template <typename _Base>
00383   class BpUGraphExtender : public _Base {
00384   public:
00385     typedef _Base Parent;
00386     typedef BpUGraphExtender Graph;
00387 
00388     typedef typename Parent::Node Node;
00389     typedef typename Parent::Edge UEdge;
00390 
00391     using Parent::first;
00392     using Parent::next;
00393 
00394     using Parent::id;
00395 
00396     Node source(const UEdge& edge) const {
00397       return aNode(edge);
00398     }
00399     Node target(const UEdge& edge) const {
00400       return bNode(edge);
00401     }
00402 
00403     void firstInc(UEdge& edge, bool& direction, const Node& node) const {
00404       if (Parent::aNode(node)) {
00405         Parent::firstOut(edge, node);
00406         direction = true;
00407       } else {
00408         Parent::firstIn(edge, node);
00409         direction = static_cast<UEdge&>(edge) == INVALID;
00410       }
00411     }
00412     void nextInc(UEdge& edge, bool& direction) const {
00413       if (direction) {
00414         Parent::nextOut(edge);
00415       } else {
00416         Parent::nextIn(edge);
00417         if (edge == INVALID) direction = true;
00418       }
00419     }
00420 
00421     int maxUEdgeId() const {
00422       return Parent::maxEdgeId();
00423     }
00424 
00425     UEdge uEdgeFromId(int id) const {
00426       return Parent::edgeFromId(id);
00427     }
00428 
00429     class Edge : public UEdge {
00430       friend class BpUGraphExtender;
00431     protected:
00432       bool forward;
00433 
00434       Edge(const UEdge& edge, bool _forward)
00435         : UEdge(edge), forward(_forward) {}
00436 
00437     public:
00438       Edge() {}
00439       Edge (Invalid) : UEdge(INVALID), forward(true) {}
00440       bool operator==(const Edge& i) const {
00441         return UEdge::operator==(i) && forward == i.forward;
00442       }
00443       bool operator!=(const Edge& i) const {
00444         return UEdge::operator!=(i) || forward != i.forward;
00445       }
00446       bool operator<(const Edge& i) const {
00447         return UEdge::operator<(i) || 
00448           (!(i.forward<forward) && UEdge(*this)<UEdge(i));
00449       }
00450     };
00451 
00452     void first(Edge& edge) const {
00453       Parent::first(static_cast<UEdge&>(edge));
00454       edge.forward = true;
00455     }
00456 
00457     void next(Edge& edge) const {
00458       if (!edge.forward) {
00459         Parent::next(static_cast<UEdge&>(edge));
00460       }
00461       edge.forward = !edge.forward;
00462     }
00463 
00464     void firstOut(Edge& edge, const Node& node) const {
00465       if (Parent::aNode(node)) {
00466         Parent::firstOut(edge, node);
00467         edge.forward = true;
00468       } else {
00469         Parent::firstIn(edge, node);
00470         edge.forward = static_cast<UEdge&>(edge) == INVALID;
00471       }
00472     }
00473     void nextOut(Edge& edge) const {
00474       if (edge.forward) {
00475         Parent::nextOut(edge);
00476       } else {
00477         Parent::nextIn(edge);
00478         edge.forward = static_cast<UEdge&>(edge) == INVALID;
00479       }
00480     }
00481 
00482     void firstIn(Edge& edge, const Node& node) const {
00483       if (Parent::bNode(node)) {
00484         Parent::firstIn(edge, node);
00485         edge.forward = true;    
00486       } else {
00487         Parent::firstOut(edge, node);
00488         edge.forward = static_cast<UEdge&>(edge) == INVALID;
00489       }
00490     }
00491     void nextIn(Edge& edge) const {
00492       if (edge.forward) {
00493         Parent::nextIn(edge);
00494       } else {
00495         Parent::nextOut(edge);
00496         edge.forward = static_cast<UEdge&>(edge) == INVALID;
00497       }
00498     }
00499 
00500     Node source(const Edge& edge) const {
00501       return edge.forward ? Parent::aNode(edge) : Parent::bNode(edge);
00502     }
00503     Node target(const Edge& edge) const {
00504       return edge.forward ? Parent::bNode(edge) : Parent::aNode(edge);
00505     }
00506 
00507     bool direction(const Edge& edge) const {
00508       return edge.forward;
00509     }
00510 
00511     Edge direct(const UEdge& edge, const Node& node) const {
00512       return Edge(edge, node == Parent::source(edge));
00513     }
00514 
00515     Edge direct(const UEdge& edge, bool direction) const {
00516       return Edge(edge, direction);
00517     }
00518 
00519     Node oppositeNode(const UEdge& edge, const Node& node) const {
00520       return source(edge) == node ? 
00521         target(edge) : source(edge);
00522     }
00523 
00524     Edge oppositeEdge(const Edge& edge) const {
00525       return Edge(edge, !edge.forward);
00526     }
00527 
00528     int id(const Edge& edge) const {
00529       return (Parent::id(edge) << 1) + (edge.forward ? 0 : 1);
00530     }
00531     Edge edgeFromId(int id) const {
00532       return Edge(Parent::fromId(id >> 1, UEdge()), (id & 1) == 0);
00533     }
00534     int maxEdgeId() const {
00535       return (Parent::maxId(UEdge()) << 1) + 1;
00536     }
00537 
00538     class ANode : public Node {
00539       friend class BpUGraphExtender;
00540     public:
00541       ANode() {}
00542       ANode(const Node& node) : Node(node) {
00543         LEMON_ASSERT(Parent::aNode(node) || node == INVALID, 
00544                      typename Parent::NodeSetError());
00545       }
00546       ANode(Invalid) : Node(INVALID) {}
00547     };
00548 
00549     void first(ANode& node) const {
00550       Parent::firstANode(static_cast<Node&>(node));
00551     }
00552     void next(ANode& node) const {
00553       Parent::nextANode(static_cast<Node&>(node));
00554     }
00555 
00556     int id(const ANode& node) const {
00557       return Parent::aNodeId(node);
00558     }
00559 
00560     class BNode : public Node {
00561       friend class BpUGraphExtender;
00562     public:
00563       BNode() {}
00564       BNode(const Node& node) : Node(node) {
00565         LEMON_ASSERT(Parent::bNode(node) || node == INVALID,
00566                      typename Parent::NodeSetError());
00567       }
00568       BNode(Invalid) : Node(INVALID) {}
00569     };
00570 
00571     void first(BNode& node) const {
00572       Parent::firstBNode(static_cast<Node&>(node));
00573     }
00574     void next(BNode& node) const {
00575       Parent::nextBNode(static_cast<Node&>(node));
00576     }
00577   
00578     int id(const BNode& node) const {
00579       return Parent::aNodeId(node);
00580     }
00581 
00582 
00583 
00584     int maxId(Node) const {
00585       return Parent::maxNodeId();
00586     }
00587     int maxId(BNode) const {
00588       return Parent::maxBNodeId();
00589     }
00590     int maxId(ANode) const {
00591       return Parent::maxANodeId();
00592     }
00593     int maxId(Edge) const {
00594       return maxEdgeId();
00595     }
00596     int maxId(UEdge) const {
00597       return maxUEdgeId();
00598     }
00599 
00600 
00601     Node fromId(int id, Node) const {
00602       return Parent::nodeFromId(id);
00603     }
00604     ANode fromId(int id, ANode) const {
00605       return Parent::fromANodeId(id);
00606     }
00607     BNode fromId(int id, BNode) const {
00608       return Parent::fromBNodeId(id);
00609     }
00610     Edge fromId(int id, Edge) const {
00611       return edgeFromId(id);
00612     }
00613     UEdge fromId(int id, UEdge) const {
00614       return uEdgeFromId(id);
00615     }
00616 
00617   };
00618 
00619 }
00620 
00621 #endif // LEMON_UNDIR_GRAPH_EXTENDER_H

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