lemon/bits/graph_adaptor_extender.h
author Peter Kovacs <kpeter@inf.elte.hu>
Fri, 24 Apr 2009 12:22:06 +0200
changeset 613 b1811c363299
parent 455 5a1e9fdcfd3a
child 617 4137ef9aacc6
permissions -rw-r--r--
Bug fix in NetworkSimplex (#234)
     1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
     2  *
     3  * This file is a part of LEMON, a generic C++ optimization library.
     4  *
     5  * Copyright (C) 2003-2009
     6  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     7  * (Egervary Research Group on Combinatorial Optimization, EGRES).
     8  *
     9  * Permission to use, modify and distribute this software is granted
    10  * provided that this copyright notice appears in all copies. For
    11  * precise terms see the accompanying LICENSE file.
    12  *
    13  * This software is provided "AS IS" with no warranty of any kind,
    14  * express or implied, and with no claim as to its suitability for any
    15  * purpose.
    16  *
    17  */
    18 
    19 #ifndef LEMON_BITS_GRAPH_ADAPTOR_EXTENDER_H
    20 #define LEMON_BITS_GRAPH_ADAPTOR_EXTENDER_H
    21 
    22 #include <lemon/core.h>
    23 #include <lemon/error.h>
    24 
    25 namespace lemon {
    26 
    27   template <typename _Digraph>
    28   class DigraphAdaptorExtender : public _Digraph {
    29   public:
    30 
    31     typedef _Digraph Parent;
    32     typedef _Digraph Digraph;
    33     typedef DigraphAdaptorExtender Adaptor;
    34 
    35     // Base extensions
    36 
    37     typedef typename Parent::Node Node;
    38     typedef typename Parent::Arc Arc;
    39 
    40     int maxId(Node) const {
    41       return Parent::maxNodeId();
    42     }
    43 
    44     int maxId(Arc) const {
    45       return Parent::maxArcId();
    46     }
    47 
    48     Node fromId(int id, Node) const {
    49       return Parent::nodeFromId(id);
    50     }
    51 
    52     Arc fromId(int id, Arc) const {
    53       return Parent::arcFromId(id);
    54     }
    55 
    56     Node oppositeNode(const Node &n, const Arc &e) const {
    57       if (n == Parent::source(e))
    58         return Parent::target(e);
    59       else if(n==Parent::target(e))
    60         return Parent::source(e);
    61       else
    62         return INVALID;
    63     }
    64 
    65     class NodeIt : public Node {
    66       const Adaptor* _adaptor;
    67     public:
    68 
    69       NodeIt() {}
    70 
    71       NodeIt(Invalid i) : Node(i) { }
    72 
    73       explicit NodeIt(const Adaptor& adaptor) : _adaptor(&adaptor) {
    74         _adaptor->first(static_cast<Node&>(*this));
    75       }
    76 
    77       NodeIt(const Adaptor& adaptor, const Node& node)
    78         : Node(node), _adaptor(&adaptor) {}
    79 
    80       NodeIt& operator++() {
    81         _adaptor->next(*this);
    82         return *this;
    83       }
    84 
    85     };
    86 
    87 
    88     class ArcIt : public Arc {
    89       const Adaptor* _adaptor;
    90     public:
    91 
    92       ArcIt() { }
    93 
    94       ArcIt(Invalid i) : Arc(i) { }
    95 
    96       explicit ArcIt(const Adaptor& adaptor) : _adaptor(&adaptor) {
    97         _adaptor->first(static_cast<Arc&>(*this));
    98       }
    99 
   100       ArcIt(const Adaptor& adaptor, const Arc& e) :
   101         Arc(e), _adaptor(&adaptor) { }
   102 
   103       ArcIt& operator++() {
   104         _adaptor->next(*this);
   105         return *this;
   106       }
   107 
   108     };
   109 
   110 
   111     class OutArcIt : public Arc {
   112       const Adaptor* _adaptor;
   113     public:
   114 
   115       OutArcIt() { }
   116 
   117       OutArcIt(Invalid i) : Arc(i) { }
   118 
   119       OutArcIt(const Adaptor& adaptor, const Node& node)
   120         : _adaptor(&adaptor) {
   121         _adaptor->firstOut(*this, node);
   122       }
   123 
   124       OutArcIt(const Adaptor& adaptor, const Arc& arc)
   125         : Arc(arc), _adaptor(&adaptor) {}
   126 
   127       OutArcIt& operator++() {
   128         _adaptor->nextOut(*this);
   129         return *this;
   130       }
   131 
   132     };
   133 
   134 
   135     class InArcIt : public Arc {
   136       const Adaptor* _adaptor;
   137     public:
   138 
   139       InArcIt() { }
   140 
   141       InArcIt(Invalid i) : Arc(i) { }
   142 
   143       InArcIt(const Adaptor& adaptor, const Node& node)
   144         : _adaptor(&adaptor) {
   145         _adaptor->firstIn(*this, node);
   146       }
   147 
   148       InArcIt(const Adaptor& adaptor, const Arc& arc) :
   149         Arc(arc), _adaptor(&adaptor) {}
   150 
   151       InArcIt& operator++() {
   152         _adaptor->nextIn(*this);
   153         return *this;
   154       }
   155 
   156     };
   157 
   158     Node baseNode(const OutArcIt &e) const {
   159       return Parent::source(e);
   160     }
   161     Node runningNode(const OutArcIt &e) const {
   162       return Parent::target(e);
   163     }
   164 
   165     Node baseNode(const InArcIt &e) const {
   166       return Parent::target(e);
   167     }
   168     Node runningNode(const InArcIt &e) const {
   169       return Parent::source(e);
   170     }
   171 
   172   };
   173 
   174   template <typename _Graph>
   175   class GraphAdaptorExtender : public _Graph {
   176   public:
   177 
   178     typedef _Graph Parent;
   179     typedef _Graph Graph;
   180     typedef GraphAdaptorExtender Adaptor;
   181 
   182     typedef typename Parent::Node Node;
   183     typedef typename Parent::Arc Arc;
   184     typedef typename Parent::Edge Edge;
   185 
   186     // Graph extension
   187 
   188     int maxId(Node) const {
   189       return Parent::maxNodeId();
   190     }
   191 
   192     int maxId(Arc) const {
   193       return Parent::maxArcId();
   194     }
   195 
   196     int maxId(Edge) const {
   197       return Parent::maxEdgeId();
   198     }
   199 
   200     Node fromId(int id, Node) const {
   201       return Parent::nodeFromId(id);
   202     }
   203 
   204     Arc fromId(int id, Arc) const {
   205       return Parent::arcFromId(id);
   206     }
   207 
   208     Edge fromId(int id, Edge) const {
   209       return Parent::edgeFromId(id);
   210     }
   211 
   212     Node oppositeNode(const Node &n, const Edge &e) const {
   213       if( n == Parent::u(e))
   214         return Parent::v(e);
   215       else if( n == Parent::v(e))
   216         return Parent::u(e);
   217       else
   218         return INVALID;
   219     }
   220 
   221     Arc oppositeArc(const Arc &a) const {
   222       return Parent::direct(a, !Parent::direction(a));
   223     }
   224 
   225     using Parent::direct;
   226     Arc direct(const Edge &e, const Node &s) const {
   227       return Parent::direct(e, Parent::u(e) == s);
   228     }
   229 
   230 
   231     class NodeIt : public Node {
   232       const Adaptor* _adaptor;
   233     public:
   234 
   235       NodeIt() {}
   236 
   237       NodeIt(Invalid i) : Node(i) { }
   238 
   239       explicit NodeIt(const Adaptor& adaptor) : _adaptor(&adaptor) {
   240         _adaptor->first(static_cast<Node&>(*this));
   241       }
   242 
   243       NodeIt(const Adaptor& adaptor, const Node& node)
   244         : Node(node), _adaptor(&adaptor) {}
   245 
   246       NodeIt& operator++() {
   247         _adaptor->next(*this);
   248         return *this;
   249       }
   250 
   251     };
   252 
   253 
   254     class ArcIt : public Arc {
   255       const Adaptor* _adaptor;
   256     public:
   257 
   258       ArcIt() { }
   259 
   260       ArcIt(Invalid i) : Arc(i) { }
   261 
   262       explicit ArcIt(const Adaptor& adaptor) : _adaptor(&adaptor) {
   263         _adaptor->first(static_cast<Arc&>(*this));
   264       }
   265 
   266       ArcIt(const Adaptor& adaptor, const Arc& e) :
   267         Arc(e), _adaptor(&adaptor) { }
   268 
   269       ArcIt& operator++() {
   270         _adaptor->next(*this);
   271         return *this;
   272       }
   273 
   274     };
   275 
   276 
   277     class OutArcIt : public Arc {
   278       const Adaptor* _adaptor;
   279     public:
   280 
   281       OutArcIt() { }
   282 
   283       OutArcIt(Invalid i) : Arc(i) { }
   284 
   285       OutArcIt(const Adaptor& adaptor, const Node& node)
   286         : _adaptor(&adaptor) {
   287         _adaptor->firstOut(*this, node);
   288       }
   289 
   290       OutArcIt(const Adaptor& adaptor, const Arc& arc)
   291         : Arc(arc), _adaptor(&adaptor) {}
   292 
   293       OutArcIt& operator++() {
   294         _adaptor->nextOut(*this);
   295         return *this;
   296       }
   297 
   298     };
   299 
   300 
   301     class InArcIt : public Arc {
   302       const Adaptor* _adaptor;
   303     public:
   304 
   305       InArcIt() { }
   306 
   307       InArcIt(Invalid i) : Arc(i) { }
   308 
   309       InArcIt(const Adaptor& adaptor, const Node& node)
   310         : _adaptor(&adaptor) {
   311         _adaptor->firstIn(*this, node);
   312       }
   313 
   314       InArcIt(const Adaptor& adaptor, const Arc& arc) :
   315         Arc(arc), _adaptor(&adaptor) {}
   316 
   317       InArcIt& operator++() {
   318         _adaptor->nextIn(*this);
   319         return *this;
   320       }
   321 
   322     };
   323 
   324     class EdgeIt : public Parent::Edge {
   325       const Adaptor* _adaptor;
   326     public:
   327 
   328       EdgeIt() { }
   329 
   330       EdgeIt(Invalid i) : Edge(i) { }
   331 
   332       explicit EdgeIt(const Adaptor& adaptor) : _adaptor(&adaptor) {
   333         _adaptor->first(static_cast<Edge&>(*this));
   334       }
   335 
   336       EdgeIt(const Adaptor& adaptor, const Edge& e) :
   337         Edge(e), _adaptor(&adaptor) { }
   338 
   339       EdgeIt& operator++() {
   340         _adaptor->next(*this);
   341         return *this;
   342       }
   343 
   344     };
   345 
   346     class IncEdgeIt : public Edge {
   347       friend class GraphAdaptorExtender;
   348       const Adaptor* _adaptor;
   349       bool direction;
   350     public:
   351 
   352       IncEdgeIt() { }
   353 
   354       IncEdgeIt(Invalid i) : Edge(i), direction(false) { }
   355 
   356       IncEdgeIt(const Adaptor& adaptor, const Node &n) : _adaptor(&adaptor) {
   357         _adaptor->firstInc(static_cast<Edge&>(*this), direction, n);
   358       }
   359 
   360       IncEdgeIt(const Adaptor& adaptor, const Edge &e, const Node &n)
   361         : _adaptor(&adaptor), Edge(e) {
   362         direction = (_adaptor->u(e) == n);
   363       }
   364 
   365       IncEdgeIt& operator++() {
   366         _adaptor->nextInc(*this, direction);
   367         return *this;
   368       }
   369     };
   370 
   371     Node baseNode(const OutArcIt &a) const {
   372       return Parent::source(a);
   373     }
   374     Node runningNode(const OutArcIt &a) const {
   375       return Parent::target(a);
   376     }
   377 
   378     Node baseNode(const InArcIt &a) const {
   379       return Parent::target(a);
   380     }
   381     Node runningNode(const InArcIt &a) const {
   382       return Parent::source(a);
   383     }
   384 
   385     Node baseNode(const IncEdgeIt &e) const {
   386       return e.direction ? Parent::u(e) : Parent::v(e);
   387     }
   388     Node runningNode(const IncEdgeIt &e) const {
   389       return e.direction ? Parent::v(e) : Parent::u(e);
   390     }
   391 
   392   };
   393 
   394 }
   395 
   396 
   397 #endif