lemon/bits/graph_adaptor_extender.h
author Balazs Dezso <deba@inf.elte.hu>
Sun, 30 Nov 2008 19:00:30 +0100
changeset 415 4b6112235fad
child 416 76287c8caa26
permissions -rw-r--r--
Improvements in graph adaptors (#67)

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