lemon/bits/graph_adaptor_extender.h
author Peter Kovacs <kpeter@inf.elte.hu>
Mon, 12 Jan 2009 08:18:04 +0100
changeset 465 2b5496c62ccd
parent 440 88ed40ad0d4f
parent 453 c246659c8b19
child 580 2313edd0db0b
permissions -rw-r--r--
Rename graph_adaptor_test.cc to adaptors_test.cc (#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-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 #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   template <typename _Graph>
   177   class GraphAdaptorExtender : public _Graph {
   178   public:
   179 
   180     typedef _Graph Parent;
   181     typedef _Graph Graph;
   182     typedef GraphAdaptorExtender Adaptor;
   183 
   184     typedef typename Parent::Node Node;
   185     typedef typename Parent::Arc Arc;
   186     typedef typename Parent::Edge Edge;
   187 
   188     // Graph extension
   189 
   190     int maxId(Node) const {
   191       return Parent::maxNodeId();
   192     }
   193 
   194     int maxId(Arc) const {
   195       return Parent::maxArcId();
   196     }
   197 
   198     int maxId(Edge) const {
   199       return Parent::maxEdgeId();
   200     }
   201 
   202     Node fromId(int id, Node) const {
   203       return Parent::nodeFromId(id);
   204     }
   205 
   206     Arc fromId(int id, Arc) const {
   207       return Parent::arcFromId(id);
   208     }
   209 
   210     Edge fromId(int id, Edge) const {
   211       return Parent::edgeFromId(id);
   212     }
   213 
   214     Node oppositeNode(const Node &n, const Edge &e) const {
   215       if( n == Parent::u(e))
   216         return Parent::v(e);
   217       else if( n == Parent::v(e))
   218         return Parent::u(e);
   219       else
   220         return INVALID;
   221     }
   222 
   223     Arc oppositeArc(const Arc &a) const {
   224       return Parent::direct(a, !Parent::direction(a));
   225     }
   226 
   227     using Parent::direct;
   228     Arc direct(const Edge &e, const Node &s) const {
   229       return Parent::direct(e, Parent::u(e) == s);
   230     }
   231 
   232 
   233     class NodeIt : public Node {
   234       const Adaptor* _adaptor;
   235     public:
   236 
   237       NodeIt() {}
   238 
   239       NodeIt(Invalid i) : Node(i) { }
   240 
   241       explicit NodeIt(const Adaptor& adaptor) : _adaptor(&adaptor) {
   242         _adaptor->first(static_cast<Node&>(*this));
   243       }
   244 
   245       NodeIt(const Adaptor& adaptor, const Node& node)
   246         : Node(node), _adaptor(&adaptor) {}
   247 
   248       NodeIt& operator++() {
   249         _adaptor->next(*this);
   250         return *this;
   251       }
   252 
   253     };
   254 
   255 
   256     class ArcIt : public Arc {
   257       const Adaptor* _adaptor;
   258     public:
   259 
   260       ArcIt() { }
   261 
   262       ArcIt(Invalid i) : Arc(i) { }
   263 
   264       explicit ArcIt(const Adaptor& adaptor) : _adaptor(&adaptor) {
   265         _adaptor->first(static_cast<Arc&>(*this));
   266       }
   267 
   268       ArcIt(const Adaptor& adaptor, const Arc& e) :
   269         Arc(e), _adaptor(&adaptor) { }
   270 
   271       ArcIt& operator++() {
   272         _adaptor->next(*this);
   273         return *this;
   274       }
   275 
   276     };
   277 
   278 
   279     class OutArcIt : public Arc {
   280       const Adaptor* _adaptor;
   281     public:
   282 
   283       OutArcIt() { }
   284 
   285       OutArcIt(Invalid i) : Arc(i) { }
   286 
   287       OutArcIt(const Adaptor& adaptor, const Node& node)
   288         : _adaptor(&adaptor) {
   289         _adaptor->firstOut(*this, node);
   290       }
   291 
   292       OutArcIt(const Adaptor& adaptor, const Arc& arc)
   293         : Arc(arc), _adaptor(&adaptor) {}
   294 
   295       OutArcIt& operator++() {
   296         _adaptor->nextOut(*this);
   297         return *this;
   298       }
   299 
   300     };
   301 
   302 
   303     class InArcIt : public Arc {
   304       const Adaptor* _adaptor;
   305     public:
   306 
   307       InArcIt() { }
   308 
   309       InArcIt(Invalid i) : Arc(i) { }
   310 
   311       InArcIt(const Adaptor& adaptor, const Node& node)
   312         : _adaptor(&adaptor) {
   313         _adaptor->firstIn(*this, node);
   314       }
   315 
   316       InArcIt(const Adaptor& adaptor, const Arc& arc) :
   317         Arc(arc), _adaptor(&adaptor) {}
   318 
   319       InArcIt& operator++() {
   320         _adaptor->nextIn(*this);
   321         return *this;
   322       }
   323 
   324     };
   325 
   326     class EdgeIt : public Parent::Edge {
   327       const Adaptor* _adaptor;
   328     public:
   329 
   330       EdgeIt() { }
   331 
   332       EdgeIt(Invalid i) : Edge(i) { }
   333 
   334       explicit EdgeIt(const Adaptor& adaptor) : _adaptor(&adaptor) {
   335         _adaptor->first(static_cast<Edge&>(*this));
   336       }
   337 
   338       EdgeIt(const Adaptor& adaptor, const Edge& e) :
   339         Edge(e), _adaptor(&adaptor) { }
   340 
   341       EdgeIt& operator++() {
   342         _adaptor->next(*this);
   343         return *this;
   344       }
   345 
   346     };
   347 
   348     class IncEdgeIt : public Edge {
   349       friend class GraphAdaptorExtender;
   350       const Adaptor* _adaptor;
   351       bool direction;
   352     public:
   353 
   354       IncEdgeIt() { }
   355 
   356       IncEdgeIt(Invalid i) : Edge(i), direction(false) { }
   357 
   358       IncEdgeIt(const Adaptor& adaptor, const Node &n) : _adaptor(&adaptor) {
   359         _adaptor->firstInc(static_cast<Edge&>(*this), direction, n);
   360       }
   361 
   362       IncEdgeIt(const Adaptor& adaptor, const Edge &e, const Node &n)
   363         : _adaptor(&adaptor), Edge(e) {
   364         direction = (_adaptor->u(e) == n);
   365       }
   366 
   367       IncEdgeIt& operator++() {
   368         _adaptor->nextInc(*this, direction);
   369         return *this;
   370       }
   371     };
   372 
   373     Node baseNode(const OutArcIt &a) const {
   374       return Parent::source(a);
   375     }
   376     Node runningNode(const OutArcIt &a) const {
   377       return Parent::target(a);
   378     }
   379 
   380     Node baseNode(const InArcIt &a) const {
   381       return Parent::target(a);
   382     }
   383     Node runningNode(const InArcIt &a) const {
   384       return Parent::source(a);
   385     }
   386 
   387     Node baseNode(const IncEdgeIt &e) const {
   388       return e.direction ? Parent::u(e) : Parent::v(e);
   389     }
   390     Node runningNode(const IncEdgeIt &e) const {
   391       return e.direction ? Parent::v(e) : Parent::u(e);
   392     }
   393 
   394   };
   395 
   396 }
   397 
   398 
   399 #endif