Main Page | Modules | Namespace List | Class Hierarchy | Alphabetical List | Class List | Directories | File List | Namespace Members | Class Members | File Members | Related Pages

undir_graph_extender.h

00001 /* -*- C++ -*-
00002  *
00003  * src/lemon/undir_graph_extender.h - Part of LEMON, a generic C++
00004  * optimization library
00005  *
00006  * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi
00007  * Kutatocsoport (Egervary Combinatorial Optimization Research Group,
00008  * EGRES).
00009  *
00010  * Permission to use, modify and distribute this software is granted
00011  * provided that this copyright notice appears in all copies. For
00012  * precise terms see the accompanying LICENSE file.
00013  *
00014  * This software is provided "AS IS" with no warranty of any kind,
00015  * express or implied, and with no claim as to its suitability for any
00016  * purpose.
00017  *
00018  */
00019 
00020 #ifndef LEMON_UNDIR_GRAPH_EXTENDER_H
00021 #define LEMON_UNDIR_GRAPH_EXTENDER_H
00022 
00023 #include <lemon/invalid.h>
00024 
00025 namespace lemon {
00026 
00027   template <typename _Base>
00028   class UndirGraphExtender : public _Base {
00029     typedef _Base Parent;
00030     typedef UndirGraphExtender Graph;
00031 
00032   public:
00033 
00034     typedef typename Parent::Edge UndirEdge;
00035     typedef typename Parent::Node Node;
00036 
00037     class Edge : public UndirEdge {
00038       friend class UndirGraphExtender;
00039 
00040     protected:
00041       // FIXME: Marci use opposite logic in his graph wrappers. It would
00042       // be reasonable to syncronize...
00043       bool forward;
00044 
00045     public:
00046       Edge() {}
00047 
00052       Edge(const UndirEdge &ue, bool _forward) :
00053         UndirEdge(ue), forward(_forward) {}
00054 
00060       Edge(const Graph &g, const UndirEdge &ue, const Node &n) :
00061         UndirEdge(ue) { forward = (g.source(ue) == n); }
00062 
00064       Edge(Invalid i) : UndirEdge(i), forward(true) {}
00065 
00066       bool operator==(const Edge &that) const {
00067         return forward==that.forward && UndirEdge(*this)==UndirEdge(that);
00068       }
00069       bool operator!=(const Edge &that) const {
00070         return forward!=that.forward || UndirEdge(*this)!=UndirEdge(that);
00071       }
00072       bool operator<(const Edge &that) const {
00073         return forward<that.forward ||
00074           (!(that.forward<forward) && UndirEdge(*this)<UndirEdge(that));
00075       }
00076     };
00077 
00078 
00082     Edge opposite(const Edge &e) const {
00083       return Edge(e,!e.forward);
00084     }
00085 
00086   protected:
00087 
00088     template <typename E>
00089     Node _dirSource(const E &e) const {
00090       return e.forward ? Parent::source(e) : Parent::target(e);
00091     }
00092 
00093     template <typename E>
00094     Node _dirTarget(const E &e) const {
00095       return e.forward ? Parent::target(e) : Parent::source(e);
00096     }
00097 
00098   public:
00101     using Parent::source;
00102 
00104     Node source(const Edge &e) const {
00105       return _dirSource(e);
00106     }
00107 
00110     using Parent::target;
00111 
00113     Node target(const Edge &e) const {
00114       return _dirTarget(e);
00115     }
00116 
00122     bool forward(const Edge &e) const { return e.forward; }
00123 
00124     Node oppositeNode(const Node &n, const UndirEdge &e) const {
00125       if( n == Parent::source(e))
00126         return Parent::target(e);
00127       else if( n == Parent::target(e))
00128         return Parent::source(e);
00129       else
00130         return INVALID;
00131     }
00132 
00141     Edge edgeWithSource(const UndirEdge &ue, const Node &s) const {
00142       return Edge(*this, eu, s);
00143     }
00144 
00145     using Parent::first;
00146     void first(Edge &e) const {
00147       Parent::first(e);
00148       e.forward=true;
00149     }
00150 
00151     using Parent::next;
00152     void next(Edge &e) const {
00153       if( e.forward ) {
00154         e.forward = false;
00155       }
00156       else {
00157         Parent::next(e);
00158         e.forward = true;
00159       }
00160     }
00161 
00162     
00163   protected:
00164 
00165     template <typename E>
00166     void _dirFirstOut(E &e, const Node &n) const {
00167       Parent::firstIn(e,n);
00168       if( UndirEdge(e) != INVALID ) {
00169         e.forward = false;
00170       }
00171       else {
00172         Parent::firstOut(e,n);
00173         e.forward = true;
00174       }
00175     }
00176     template <typename E>
00177     void _dirFirstIn(E &e, const Node &n) const {
00178       Parent::firstOut(e,n);
00179       if( UndirEdge(e) != INVALID ) {
00180         e.forward = false;
00181       }
00182       else {
00183         Parent::firstIn(e,n);
00184         e.forward = true;
00185       }
00186     }
00187 
00188     template <typename E>
00189     void _dirNextOut(E &e) const {
00190       if( ! e.forward ) {
00191         Node n = Parent::target(e);
00192         Parent::nextIn(e);
00193         if( UndirEdge(e) == INVALID ) {
00194           Parent::firstOut(e, n);
00195           e.forward = true;
00196         }
00197       }
00198       else {
00199         Parent::nextOut(e);
00200       }
00201     }
00202     template <typename E>
00203     void _dirNextIn(E &e) const {
00204       if( ! e.forward ) {
00205         Node n = Parent::source(e);
00206         Parent::nextOut(e);
00207         if( UndirEdge(e) == INVALID ) {
00208           Parent::firstIn(e, n);
00209           e.forward = true;
00210         }
00211       }
00212       else {
00213         Parent::nextIn(e);
00214       }
00215     }
00216 
00217   public:
00218 
00219     void firstOut(Edge &e, const Node &n) const {
00220       _dirFirstOut(e, n);
00221     }
00222     void firstIn(Edge &e, const Node &n) const {
00223       _dirFirstIn(e, n);
00224     }
00225 
00226     void nextOut(Edge &e) const {
00227       _dirNextOut(e);
00228     }
00229     void nextIn(Edge &e) const {
00230       _dirNextIn(e);
00231     }
00232 
00233     // Miscellaneous stuff:
00234 
00237 
00238     // using Parent::id;
00239     // Using "using" is not a good idea, cause it could be that there is
00240     // no "id" in Parent...
00241 
00242     int id(const Node &n) const {
00243       return Parent::id(n);
00244     }
00245 
00246     int id(const UndirEdge &e) const {
00247       return Parent::id(e);
00248     }
00249 
00250     int id(const Edge &e) const {
00251       return 2 * Parent::id(e) + int(e.forward);
00252     }
00253 
00254 
00255     int maxId(Node) const {
00256       return Parent::maxId(Node());
00257     }
00258 
00259     int maxId(Edge) const {
00260       return 2 * Parent::maxId(typename Parent::Edge()) + 1;
00261     }
00262     int maxId(UndirEdge) const {
00263       return Parent::maxId(typename Parent::Edge());
00264     }
00265 
00266 
00267     int edgeNum() const {
00268       return 2 * Parent::edgeNum();
00269     }
00270     int undirEdgeNum() const {
00271       return Parent::edgeNum();
00272     }
00273 
00274   };
00275 
00276 }
00277 
00278 #endif // LEMON_UNDIR_GRAPH_EXTENDER_H

Generated on Mon Feb 21 15:02:22 2005 for LEMON by  doxygen 1.4.1