lemon/bits/graph_adaptor_extender.h
author Gabor Gevay <ggab90@gmail.com>
Sun, 05 Jan 2014 22:24:56 +0100
changeset 1336 0759d974de81
parent 1270 dceba191c00d
child 1337 4add05447ca0
permissions -rw-r--r--
STL style iterators (#325)

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