lemon/bits/graph_adaptor_extender.h
author Peter Kovacs <kpeter@inf.elte.hu>
Fri, 09 Jan 2009 12:43:52 +0100
changeset 450 14bb8812b8af
parent 414 05357da973ce
child 440 88ed40ad0d4f
child 453 c246659c8b19
permissions -rw-r--r--
Add creator functions for Residual and Residual::ResidualCapacity (#67)
     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-2008
     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 #include <lemon/bits/default_map.h>
    26 
    27 namespace lemon {
    28 
    29   template <typename _Digraph>
    30   class DigraphAdaptorExtender : public _Digraph {
    31   public:
    32 
    33     typedef _Digraph Parent;
    34     typedef _Digraph Digraph;
    35     typedef DigraphAdaptorExtender Adaptor;
    36 
    37     // Base extensions
    38 
    39     typedef typename Parent::Node Node;
    40     typedef typename Parent::Arc Arc;
    41 
    42     int maxId(Node) const {
    43       return Parent::maxNodeId();
    44     }
    45 
    46     int maxId(Arc) const {
    47       return Parent::maxArcId();
    48     }
    49 
    50     Node fromId(int id, Node) const {
    51       return Parent::nodeFromId(id);
    52     }
    53 
    54     Arc fromId(int id, Arc) const {
    55       return Parent::arcFromId(id);
    56     }
    57 
    58     Node oppositeNode(const Node &n, const Arc &e) const {
    59       if (n == Parent::source(e))
    60         return Parent::target(e);
    61       else if(n==Parent::target(e))
    62         return Parent::source(e);
    63       else
    64         return INVALID;
    65     }
    66 
    67     class NodeIt : public Node {
    68       const Adaptor* _adaptor;
    69     public:
    70 
    71       NodeIt() {}
    72 
    73       NodeIt(Invalid i) : Node(i) { }
    74 
    75       explicit NodeIt(const Adaptor& adaptor) : _adaptor(&adaptor) {
    76         _adaptor->first(static_cast<Node&>(*this));
    77       }
    78 
    79       NodeIt(const Adaptor& adaptor, const Node& node)
    80         : Node(node), _adaptor(&adaptor) {}
    81 
    82       NodeIt& operator++() {
    83         _adaptor->next(*this);
    84         return *this;
    85       }
    86 
    87     };
    88 
    89 
    90     class ArcIt : public Arc {
    91       const Adaptor* _adaptor;
    92     public:
    93 
    94       ArcIt() { }
    95 
    96       ArcIt(Invalid i) : Arc(i) { }
    97 
    98       explicit ArcIt(const Adaptor& adaptor) : _adaptor(&adaptor) {
    99         _adaptor->first(static_cast<Arc&>(*this));
   100       }
   101 
   102       ArcIt(const Adaptor& adaptor, const Arc& e) :
   103         Arc(e), _adaptor(&adaptor) { }
   104 
   105       ArcIt& operator++() {
   106         _adaptor->next(*this);
   107         return *this;
   108       }
   109 
   110     };
   111 
   112 
   113     class OutArcIt : public Arc {
   114       const Adaptor* _adaptor;
   115     public:
   116 
   117       OutArcIt() { }
   118 
   119       OutArcIt(Invalid i) : Arc(i) { }
   120 
   121       OutArcIt(const Adaptor& adaptor, const Node& node)
   122         : _adaptor(&adaptor) {
   123         _adaptor->firstOut(*this, node);
   124       }
   125 
   126       OutArcIt(const Adaptor& adaptor, const Arc& arc)
   127         : Arc(arc), _adaptor(&adaptor) {}
   128 
   129       OutArcIt& operator++() {
   130         _adaptor->nextOut(*this);
   131         return *this;
   132       }
   133 
   134     };
   135 
   136 
   137     class InArcIt : public Arc {
   138       const Adaptor* _adaptor;
   139     public:
   140 
   141       InArcIt() { }
   142 
   143       InArcIt(Invalid i) : Arc(i) { }
   144 
   145       InArcIt(const Adaptor& adaptor, const Node& node)
   146         : _adaptor(&adaptor) {
   147         _adaptor->firstIn(*this, node);
   148       }
   149 
   150       InArcIt(const Adaptor& adaptor, const Arc& arc) :
   151         Arc(arc), _adaptor(&adaptor) {}
   152 
   153       InArcIt& operator++() {
   154         _adaptor->nextIn(*this);
   155         return *this;
   156       }
   157 
   158     };
   159 
   160     Node baseNode(const OutArcIt &e) const {
   161       return Parent::source(e);
   162     }
   163     Node runningNode(const OutArcIt &e) const {
   164       return Parent::target(e);
   165     }
   166 
   167     Node baseNode(const InArcIt &e) const {
   168       return Parent::target(e);
   169     }
   170     Node runningNode(const InArcIt &e) const {
   171       return Parent::source(e);
   172     }
   173 
   174   };
   175 
   176 
   177   /// \ingroup digraphbits
   178   ///
   179   /// \brief Extender for the GraphAdaptors
   180   template <typename _Graph>
   181   class GraphAdaptorExtender : public _Graph {
   182   public:
   183 
   184     typedef _Graph Parent;
   185     typedef _Graph Graph;
   186     typedef GraphAdaptorExtender Adaptor;
   187 
   188     typedef typename Parent::Node Node;
   189     typedef typename Parent::Arc Arc;
   190     typedef typename Parent::Edge Edge;
   191 
   192     // Graph extension
   193 
   194     int maxId(Node) const {
   195       return Parent::maxNodeId();
   196     }
   197 
   198     int maxId(Arc) const {
   199       return Parent::maxArcId();
   200     }
   201 
   202     int maxId(Edge) const {
   203       return Parent::maxEdgeId();
   204     }
   205 
   206     Node fromId(int id, Node) const {
   207       return Parent::nodeFromId(id);
   208     }
   209 
   210     Arc fromId(int id, Arc) const {
   211       return Parent::arcFromId(id);
   212     }
   213 
   214     Edge fromId(int id, Edge) const {
   215       return Parent::edgeFromId(id);
   216     }
   217 
   218     Node oppositeNode(const Node &n, const Edge &e) const {
   219       if( n == Parent::u(e))
   220         return Parent::v(e);
   221       else if( n == Parent::v(e))
   222         return Parent::u(e);
   223       else
   224         return INVALID;
   225     }
   226 
   227     Arc oppositeArc(const Arc &a) const {
   228       return Parent::direct(a, !Parent::direction(a));
   229     }
   230 
   231     using Parent::direct;
   232     Arc direct(const Edge &e, const Node &s) const {
   233       return Parent::direct(e, Parent::u(e) == s);
   234     }
   235 
   236 
   237     class NodeIt : public Node {
   238       const Adaptor* _adaptor;
   239     public:
   240 
   241       NodeIt() {}
   242 
   243       NodeIt(Invalid i) : Node(i) { }
   244 
   245       explicit NodeIt(const Adaptor& adaptor) : _adaptor(&adaptor) {
   246         _adaptor->first(static_cast<Node&>(*this));
   247       }
   248 
   249       NodeIt(const Adaptor& adaptor, const Node& node)
   250         : Node(node), _adaptor(&adaptor) {}
   251 
   252       NodeIt& operator++() {
   253         _adaptor->next(*this);
   254         return *this;
   255       }
   256 
   257     };
   258 
   259 
   260     class ArcIt : public Arc {
   261       const Adaptor* _adaptor;
   262     public:
   263 
   264       ArcIt() { }
   265 
   266       ArcIt(Invalid i) : Arc(i) { }
   267 
   268       explicit ArcIt(const Adaptor& adaptor) : _adaptor(&adaptor) {
   269         _adaptor->first(static_cast<Arc&>(*this));
   270       }
   271 
   272       ArcIt(const Adaptor& adaptor, const Arc& e) :
   273         Arc(e), _adaptor(&adaptor) { }
   274 
   275       ArcIt& operator++() {
   276         _adaptor->next(*this);
   277         return *this;
   278       }
   279 
   280     };
   281 
   282 
   283     class OutArcIt : public Arc {
   284       const Adaptor* _adaptor;
   285     public:
   286 
   287       OutArcIt() { }
   288 
   289       OutArcIt(Invalid i) : Arc(i) { }
   290 
   291       OutArcIt(const Adaptor& adaptor, const Node& node)
   292         : _adaptor(&adaptor) {
   293         _adaptor->firstOut(*this, node);
   294       }
   295 
   296       OutArcIt(const Adaptor& adaptor, const Arc& arc)
   297         : Arc(arc), _adaptor(&adaptor) {}
   298 
   299       OutArcIt& operator++() {
   300         _adaptor->nextOut(*this);
   301         return *this;
   302       }
   303 
   304     };
   305 
   306 
   307     class InArcIt : public Arc {
   308       const Adaptor* _adaptor;
   309     public:
   310 
   311       InArcIt() { }
   312 
   313       InArcIt(Invalid i) : Arc(i) { }
   314 
   315       InArcIt(const Adaptor& adaptor, const Node& node)
   316         : _adaptor(&adaptor) {
   317         _adaptor->firstIn(*this, node);
   318       }
   319 
   320       InArcIt(const Adaptor& adaptor, const Arc& arc) :
   321         Arc(arc), _adaptor(&adaptor) {}
   322 
   323       InArcIt& operator++() {
   324         _adaptor->nextIn(*this);
   325         return *this;
   326       }
   327 
   328     };
   329 
   330     class EdgeIt : public Parent::Edge {
   331       const Adaptor* _adaptor;
   332     public:
   333 
   334       EdgeIt() { }
   335 
   336       EdgeIt(Invalid i) : Edge(i) { }
   337 
   338       explicit EdgeIt(const Adaptor& adaptor) : _adaptor(&adaptor) {
   339         _adaptor->first(static_cast<Edge&>(*this));
   340       }
   341 
   342       EdgeIt(const Adaptor& adaptor, const Edge& e) :
   343         Edge(e), _adaptor(&adaptor) { }
   344 
   345       EdgeIt& operator++() {
   346         _adaptor->next(*this);
   347         return *this;
   348       }
   349 
   350     };
   351 
   352     class IncEdgeIt : public Edge {
   353       friend class GraphAdaptorExtender;
   354       const Adaptor* _adaptor;
   355       bool direction;
   356     public:
   357 
   358       IncEdgeIt() { }
   359 
   360       IncEdgeIt(Invalid i) : Edge(i), direction(false) { }
   361 
   362       IncEdgeIt(const Adaptor& adaptor, const Node &n) : _adaptor(&adaptor) {
   363         _adaptor->firstInc(static_cast<Edge&>(*this), direction, n);
   364       }
   365 
   366       IncEdgeIt(const Adaptor& adaptor, const Edge &e, const Node &n)
   367         : _adaptor(&adaptor), Edge(e) {
   368         direction = (_adaptor->u(e) == n);
   369       }
   370 
   371       IncEdgeIt& operator++() {
   372         _adaptor->nextInc(*this, direction);
   373         return *this;
   374       }
   375     };
   376 
   377     Node baseNode(const OutArcIt &a) const {
   378       return Parent::source(a);
   379     }
   380     Node runningNode(const OutArcIt &a) const {
   381       return Parent::target(a);
   382     }
   383 
   384     Node baseNode(const InArcIt &a) const {
   385       return Parent::target(a);
   386     }
   387     Node runningNode(const InArcIt &a) const {
   388       return Parent::source(a);
   389     }
   390 
   391     Node baseNode(const IncEdgeIt &e) const {
   392       return e.direction ? Parent::u(e) : Parent::v(e);
   393     }
   394     Node runningNode(const IncEdgeIt &e) const {
   395       return e.direction ? Parent::v(e) : Parent::u(e);
   396     }
   397 
   398   };
   399 
   400 }
   401 
   402 
   403 #endif