lemon/bits/graph_adaptor_extender.h
author Peter Kovacs <kpeter@inf.elte.hu>
Sun, 15 Nov 2009 19:57:02 +0100
changeset 787 c2230649a493
parent 580 2313edd0db0b
child 882 ece1f8a3052d
permissions -rw-r--r--
Various doc improvements (#331)

- Add notes to the graph classes about the time of
item counting.
- Clarify the doc for run() in BFS and DFS.
- Other improvements.
     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     typedef _Digraph Parent;
    30 
    31   public:
    32 
    33     typedef _Digraph Digraph;
    34     typedef DigraphAdaptorExtender Adaptor;
    35 
    36     // Base extensions
    37 
    38     typedef typename Parent::Node Node;
    39     typedef typename Parent::Arc Arc;
    40 
    41     int maxId(Node) const {
    42       return Parent::maxNodeId();
    43     }
    44 
    45     int maxId(Arc) const {
    46       return Parent::maxArcId();
    47     }
    48 
    49     Node fromId(int id, Node) const {
    50       return Parent::nodeFromId(id);
    51     }
    52 
    53     Arc fromId(int id, Arc) const {
    54       return Parent::arcFromId(id);
    55     }
    56 
    57     Node oppositeNode(const Node &n, const Arc &e) const {
    58       if (n == Parent::source(e))
    59         return Parent::target(e);
    60       else if(n==Parent::target(e))
    61         return Parent::source(e);
    62       else
    63         return INVALID;
    64     }
    65 
    66     class NodeIt : public Node {
    67       const Adaptor* _adaptor;
    68     public:
    69 
    70       NodeIt() {}
    71 
    72       NodeIt(Invalid i) : Node(i) { }
    73 
    74       explicit NodeIt(const Adaptor& adaptor) : _adaptor(&adaptor) {
    75         _adaptor->first(static_cast<Node&>(*this));
    76       }
    77 
    78       NodeIt(const Adaptor& adaptor, const Node& node)
    79         : Node(node), _adaptor(&adaptor) {}
    80 
    81       NodeIt& operator++() {
    82         _adaptor->next(*this);
    83         return *this;
    84       }
    85 
    86     };
    87 
    88 
    89     class ArcIt : public Arc {
    90       const Adaptor* _adaptor;
    91     public:
    92 
    93       ArcIt() { }
    94 
    95       ArcIt(Invalid i) : Arc(i) { }
    96 
    97       explicit ArcIt(const Adaptor& adaptor) : _adaptor(&adaptor) {
    98         _adaptor->first(static_cast<Arc&>(*this));
    99       }
   100 
   101       ArcIt(const Adaptor& adaptor, const Arc& e) :
   102         Arc(e), _adaptor(&adaptor) { }
   103 
   104       ArcIt& operator++() {
   105         _adaptor->next(*this);
   106         return *this;
   107       }
   108 
   109     };
   110 
   111 
   112     class OutArcIt : public Arc {
   113       const Adaptor* _adaptor;
   114     public:
   115 
   116       OutArcIt() { }
   117 
   118       OutArcIt(Invalid i) : Arc(i) { }
   119 
   120       OutArcIt(const Adaptor& adaptor, const Node& node)
   121         : _adaptor(&adaptor) {
   122         _adaptor->firstOut(*this, node);
   123       }
   124 
   125       OutArcIt(const Adaptor& adaptor, const Arc& arc)
   126         : Arc(arc), _adaptor(&adaptor) {}
   127 
   128       OutArcIt& operator++() {
   129         _adaptor->nextOut(*this);
   130         return *this;
   131       }
   132 
   133     };
   134 
   135 
   136     class InArcIt : public Arc {
   137       const Adaptor* _adaptor;
   138     public:
   139 
   140       InArcIt() { }
   141 
   142       InArcIt(Invalid i) : Arc(i) { }
   143 
   144       InArcIt(const Adaptor& adaptor, const Node& node)
   145         : _adaptor(&adaptor) {
   146         _adaptor->firstIn(*this, node);
   147       }
   148 
   149       InArcIt(const Adaptor& adaptor, const Arc& arc) :
   150         Arc(arc), _adaptor(&adaptor) {}
   151 
   152       InArcIt& operator++() {
   153         _adaptor->nextIn(*this);
   154         return *this;
   155       }
   156 
   157     };
   158 
   159     Node baseNode(const OutArcIt &e) const {
   160       return Parent::source(e);
   161     }
   162     Node runningNode(const OutArcIt &e) const {
   163       return Parent::target(e);
   164     }
   165 
   166     Node baseNode(const InArcIt &e) const {
   167       return Parent::target(e);
   168     }
   169     Node runningNode(const InArcIt &e) const {
   170       return Parent::source(e);
   171     }
   172 
   173   };
   174 
   175   template <typename _Graph>
   176   class GraphAdaptorExtender : public _Graph {
   177     typedef _Graph Parent;
   178 
   179   public:
   180 
   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