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