lemon/path.h
author Alpar Juttner <alpar@cs.elte.hu>
Thu, 04 Aug 2011 22:00:57 +0200
changeset 924 3dcb45a871c3
parent 503 41bdb4d6c8c3
child 784 1a7fe3bef514
child 802 994c7df296c9
permissions -rw-r--r--
Update the AUTHORS file
alpar@209
     1
/* -*- mode: C++; indent-tabs-mode: nil; -*-
alpar@96
     2
 *
alpar@209
     3
 * This file is a part of LEMON, a generic C++ optimization library.
alpar@96
     4
 *
alpar@96
     5
 * Copyright (C) 2003-2008
alpar@96
     6
 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
alpar@96
     7
 * (Egervary Research Group on Combinatorial Optimization, EGRES).
alpar@96
     8
 *
alpar@96
     9
 * Permission to use, modify and distribute this software is granted
alpar@96
    10
 * provided that this copyright notice appears in all copies. For
alpar@96
    11
 * precise terms see the accompanying LICENSE file.
alpar@96
    12
 *
alpar@96
    13
 * This software is provided "AS IS" with no warranty of any kind,
alpar@96
    14
 * express or implied, and with no claim as to its suitability for any
alpar@96
    15
 * purpose.
alpar@96
    16
 *
alpar@96
    17
 */
alpar@96
    18
alpar@96
    19
///\ingroup paths
alpar@96
    20
///\file
alpar@96
    21
///\brief Classes for representing paths in digraphs.
alpar@96
    22
///
alpar@96
    23
alpar@96
    24
#ifndef LEMON_PATH_H
alpar@96
    25
#define LEMON_PATH_H
alpar@96
    26
alpar@96
    27
#include <vector>
alpar@96
    28
#include <algorithm>
alpar@96
    29
alpar@96
    30
#include <lemon/error.h>
deba@220
    31
#include <lemon/core.h>
alpar@100
    32
#include <lemon/concepts/path.h>
alpar@96
    33
alpar@96
    34
namespace lemon {
alpar@96
    35
alpar@96
    36
  /// \addtogroup paths
alpar@96
    37
  /// @{
alpar@96
    38
alpar@96
    39
alpar@96
    40
  /// \brief A structure for representing directed paths in a digraph.
alpar@96
    41
  ///
alpar@96
    42
  /// A structure for representing directed path in a digraph.
kpeter@157
    43
  /// \tparam _Digraph The digraph type in which the path is.
alpar@96
    44
  ///
alpar@96
    45
  /// In a sense, the path can be treated as a list of arcs. The
alpar@97
    46
  /// lemon path type stores just this list. As a consequence, it
alpar@97
    47
  /// cannot enumerate the nodes of the path and the source node of
alpar@97
    48
  /// a zero length path is undefined.
alpar@96
    49
  ///
alpar@96
    50
  /// This implementation is a back and front insertable and erasable
alpar@96
    51
  /// path type. It can be indexed in O(1) time. The front and back
alpar@97
    52
  /// insertion and erase is done in O(1) (amortized) time. The
alpar@97
    53
  /// implementation uses two vectors for storing the front and back
alpar@97
    54
  /// insertions.
alpar@96
    55
  template <typename _Digraph>
alpar@96
    56
  class Path {
alpar@96
    57
  public:
alpar@96
    58
alpar@96
    59
    typedef _Digraph Digraph;
alpar@96
    60
    typedef typename Digraph::Arc Arc;
alpar@96
    61
alpar@96
    62
    /// \brief Default constructor
alpar@96
    63
    ///
alpar@96
    64
    /// Default constructor
alpar@96
    65
    Path() {}
alpar@96
    66
alpar@96
    67
    /// \brief Template copy constructor
alpar@96
    68
    ///
alpar@97
    69
    /// This constuctor initializes the path from any other path type.
alpar@97
    70
    /// It simply makes a copy of the given path.
alpar@96
    71
    template <typename CPath>
alpar@96
    72
    Path(const CPath& cpath) {
kpeter@505
    73
      pathCopy(cpath, *this);
alpar@96
    74
    }
alpar@96
    75
alpar@96
    76
    /// \brief Template copy assignment
alpar@96
    77
    ///
alpar@97
    78
    /// This operator makes a copy of a path of any other type.
alpar@96
    79
    template <typename CPath>
alpar@96
    80
    Path& operator=(const CPath& cpath) {
kpeter@505
    81
      pathCopy(cpath, *this);
alpar@96
    82
      return *this;
alpar@96
    83
    }
alpar@96
    84
ladanyi@236
    85
    /// \brief LEMON style iterator for path arcs
alpar@96
    86
    ///
alpar@96
    87
    /// This class is used to iterate on the arcs of the paths.
alpar@96
    88
    class ArcIt {
alpar@96
    89
      friend class Path;
alpar@96
    90
    public:
alpar@96
    91
      /// \brief Default constructor
alpar@96
    92
      ArcIt() {}
alpar@96
    93
      /// \brief Invalid constructor
alpar@96
    94
      ArcIt(Invalid) : path(0), idx(-1) {}
alpar@97
    95
      /// \brief Initializate the iterator to the first arc of path
alpar@209
    96
      ArcIt(const Path &_path)
alpar@96
    97
        : path(&_path), idx(_path.empty() ? -1 : 0) {}
alpar@96
    98
alpar@96
    99
    private:
alpar@96
   100
alpar@209
   101
      ArcIt(const Path &_path, int _idx)
alpar@96
   102
        : path(&_path), idx(_idx) {}
alpar@96
   103
alpar@96
   104
    public:
alpar@96
   105
alpar@96
   106
      /// \brief Conversion to Arc
alpar@96
   107
      operator const Arc&() const {
alpar@96
   108
        return path->nth(idx);
alpar@96
   109
      }
alpar@96
   110
alpar@96
   111
      /// \brief Next arc
alpar@209
   112
      ArcIt& operator++() {
alpar@96
   113
        ++idx;
alpar@209
   114
        if (idx >= path->length()) idx = -1;
alpar@209
   115
        return *this;
alpar@96
   116
      }
alpar@96
   117
alpar@96
   118
      /// \brief Comparison operator
alpar@96
   119
      bool operator==(const ArcIt& e) const { return idx==e.idx; }
alpar@96
   120
      /// \brief Comparison operator
alpar@96
   121
      bool operator!=(const ArcIt& e) const { return idx!=e.idx; }
alpar@96
   122
      /// \brief Comparison operator
alpar@96
   123
      bool operator<(const ArcIt& e) const { return idx<e.idx; }
alpar@96
   124
alpar@96
   125
    private:
alpar@96
   126
      const Path *path;
alpar@96
   127
      int idx;
alpar@96
   128
    };
alpar@96
   129
alpar@96
   130
    /// \brief Length of the path.
alpar@96
   131
    int length() const { return head.size() + tail.size(); }
alpar@97
   132
    /// \brief Return whether the path is empty.
alpar@96
   133
    bool empty() const { return head.empty() && tail.empty(); }
alpar@96
   134
alpar@97
   135
    /// \brief Reset the path to an empty one.
alpar@96
   136
    void clear() { head.clear(); tail.clear(); }
alpar@96
   137
alpar@97
   138
    /// \brief The nth arc.
alpar@96
   139
    ///
alpar@96
   140
    /// \pre n is in the [0..length() - 1] range
alpar@96
   141
    const Arc& nth(int n) const {
alpar@96
   142
      return n < int(head.size()) ? *(head.rbegin() + n) :
alpar@96
   143
        *(tail.begin() + (n - head.size()));
alpar@96
   144
    }
alpar@96
   145
alpar@97
   146
    /// \brief Initialize arc iterator to point to the nth arc
alpar@96
   147
    ///
alpar@96
   148
    /// \pre n is in the [0..length() - 1] range
alpar@96
   149
    ArcIt nthIt(int n) const {
alpar@96
   150
      return ArcIt(*this, n);
alpar@96
   151
    }
alpar@96
   152
alpar@97
   153
    /// \brief The first arc of the path
alpar@96
   154
    const Arc& front() const {
alpar@96
   155
      return head.empty() ? tail.front() : head.back();
alpar@96
   156
    }
alpar@96
   157
alpar@96
   158
    /// \brief Add a new arc before the current path
alpar@96
   159
    void addFront(const Arc& arc) {
alpar@96
   160
      head.push_back(arc);
alpar@96
   161
    }
alpar@96
   162
alpar@96
   163
    /// \brief Erase the first arc of the path
alpar@96
   164
    void eraseFront() {
alpar@96
   165
      if (!head.empty()) {
alpar@96
   166
        head.pop_back();
alpar@96
   167
      } else {
alpar@96
   168
        head.clear();
alpar@96
   169
        int halfsize = tail.size() / 2;
alpar@96
   170
        head.resize(halfsize);
alpar@96
   171
        std::copy(tail.begin() + 1, tail.begin() + halfsize + 1,
alpar@96
   172
                  head.rbegin());
alpar@96
   173
        std::copy(tail.begin() + halfsize + 1, tail.end(), tail.begin());
alpar@96
   174
        tail.resize(tail.size() - halfsize - 1);
alpar@96
   175
      }
alpar@96
   176
    }
alpar@96
   177
alpar@97
   178
    /// \brief The last arc of the path
alpar@96
   179
    const Arc& back() const {
alpar@96
   180
      return tail.empty() ? head.front() : tail.back();
alpar@96
   181
    }
alpar@96
   182
alpar@96
   183
    /// \brief Add a new arc behind the current path
alpar@96
   184
    void addBack(const Arc& arc) {
alpar@96
   185
      tail.push_back(arc);
alpar@96
   186
    }
alpar@96
   187
alpar@96
   188
    /// \brief Erase the last arc of the path
alpar@96
   189
    void eraseBack() {
alpar@96
   190
      if (!tail.empty()) {
alpar@96
   191
        tail.pop_back();
alpar@96
   192
      } else {
alpar@96
   193
        int halfsize = head.size() / 2;
alpar@96
   194
        tail.resize(halfsize);
alpar@96
   195
        std::copy(head.begin() + 1, head.begin() + halfsize + 1,
alpar@96
   196
                  tail.rbegin());
alpar@96
   197
        std::copy(head.begin() + halfsize + 1, head.end(), head.begin());
alpar@96
   198
        head.resize(head.size() - halfsize - 1);
alpar@96
   199
      }
alpar@96
   200
    }
alpar@96
   201
alpar@96
   202
    typedef True BuildTag;
alpar@96
   203
alpar@96
   204
    template <typename CPath>
alpar@96
   205
    void build(const CPath& path) {
alpar@96
   206
      int len = path.length();
alpar@96
   207
      tail.reserve(len);
alpar@96
   208
      for (typename CPath::ArcIt it(path); it != INVALID; ++it) {
alpar@96
   209
        tail.push_back(it);
alpar@96
   210
      }
alpar@96
   211
    }
alpar@96
   212
alpar@96
   213
    template <typename CPath>
alpar@96
   214
    void buildRev(const CPath& path) {
alpar@96
   215
      int len = path.length();
alpar@96
   216
      head.reserve(len);
alpar@96
   217
      for (typename CPath::RevArcIt it(path); it != INVALID; ++it) {
alpar@96
   218
        head.push_back(it);
alpar@96
   219
      }
alpar@96
   220
    }
alpar@96
   221
alpar@96
   222
  protected:
alpar@96
   223
    typedef std::vector<Arc> Container;
alpar@96
   224
    Container head, tail;
alpar@96
   225
alpar@96
   226
  };
alpar@96
   227
alpar@96
   228
  /// \brief A structure for representing directed paths in a digraph.
alpar@96
   229
  ///
alpar@96
   230
  /// A structure for representing directed path in a digraph.
kpeter@157
   231
  /// \tparam _Digraph The digraph type in which the path is.
alpar@96
   232
  ///
alpar@96
   233
  /// In a sense, the path can be treated as a list of arcs. The
alpar@96
   234
  /// lemon path type stores just this list. As a consequence it
alpar@96
   235
  /// cannot enumerate the nodes in the path and the zero length paths
alpar@96
   236
  /// cannot store the source.
alpar@96
   237
  ///
alpar@96
   238
  /// This implementation is a just back insertable and erasable path
alpar@96
   239
  /// type. It can be indexed in O(1) time. The back insertion and
alpar@96
   240
  /// erasure is amortized O(1) time. This implementation is faster
alpar@96
   241
  /// then the \c Path type because it use just one vector for the
alpar@96
   242
  /// arcs.
alpar@96
   243
  template <typename _Digraph>
alpar@96
   244
  class SimplePath {
alpar@96
   245
  public:
alpar@96
   246
alpar@96
   247
    typedef _Digraph Digraph;
alpar@96
   248
    typedef typename Digraph::Arc Arc;
alpar@96
   249
alpar@96
   250
    /// \brief Default constructor
alpar@96
   251
    ///
alpar@96
   252
    /// Default constructor
alpar@96
   253
    SimplePath() {}
alpar@96
   254
alpar@96
   255
    /// \brief Template copy constructor
alpar@96
   256
    ///
alpar@96
   257
    /// This path can be initialized with any other path type. It just
alpar@96
   258
    /// makes a copy of the given path.
alpar@96
   259
    template <typename CPath>
alpar@96
   260
    SimplePath(const CPath& cpath) {
kpeter@505
   261
      pathCopy(cpath, *this);
alpar@96
   262
    }
alpar@96
   263
alpar@96
   264
    /// \brief Template copy assignment
alpar@96
   265
    ///
alpar@96
   266
    /// This path can be initialized with any other path type. It just
alpar@96
   267
    /// makes a copy of the given path.
alpar@96
   268
    template <typename CPath>
alpar@96
   269
    SimplePath& operator=(const CPath& cpath) {
kpeter@505
   270
      pathCopy(cpath, *this);
alpar@96
   271
      return *this;
alpar@96
   272
    }
alpar@96
   273
alpar@96
   274
    /// \brief Iterator class to iterate on the arcs of the paths
alpar@96
   275
    ///
alpar@96
   276
    /// This class is used to iterate on the arcs of the paths
alpar@96
   277
    ///
alpar@96
   278
    /// Of course it converts to Digraph::Arc
alpar@96
   279
    class ArcIt {
alpar@96
   280
      friend class SimplePath;
alpar@96
   281
    public:
alpar@96
   282
      /// Default constructor
alpar@96
   283
      ArcIt() {}
alpar@96
   284
      /// Invalid constructor
alpar@96
   285
      ArcIt(Invalid) : path(0), idx(-1) {}
alpar@96
   286
      /// \brief Initializate the constructor to the first arc of path
alpar@209
   287
      ArcIt(const SimplePath &_path)
alpar@96
   288
        : path(&_path), idx(_path.empty() ? -1 : 0) {}
alpar@96
   289
alpar@96
   290
    private:
alpar@96
   291
alpar@96
   292
      /// Constructor with starting point
alpar@209
   293
      ArcIt(const SimplePath &_path, int _idx)
alpar@96
   294
        : idx(_idx), path(&_path) {}
alpar@96
   295
alpar@96
   296
    public:
alpar@96
   297
alpar@96
   298
      ///Conversion to Digraph::Arc
alpar@96
   299
      operator const Arc&() const {
alpar@96
   300
        return path->nth(idx);
alpar@96
   301
      }
alpar@96
   302
alpar@96
   303
      /// Next arc
alpar@209
   304
      ArcIt& operator++() {
alpar@96
   305
        ++idx;
alpar@209
   306
        if (idx >= path->length()) idx = -1;
alpar@209
   307
        return *this;
alpar@96
   308
      }
alpar@96
   309
alpar@96
   310
      /// Comparison operator
alpar@96
   311
      bool operator==(const ArcIt& e) const { return idx==e.idx; }
alpar@96
   312
      /// Comparison operator
alpar@96
   313
      bool operator!=(const ArcIt& e) const { return idx!=e.idx; }
alpar@96
   314
      /// Comparison operator
alpar@96
   315
      bool operator<(const ArcIt& e) const { return idx<e.idx; }
alpar@96
   316
alpar@96
   317
    private:
alpar@96
   318
      const SimplePath *path;
alpar@96
   319
      int idx;
alpar@96
   320
    };
alpar@96
   321
alpar@96
   322
    /// \brief Length of the path.
alpar@96
   323
    int length() const { return data.size(); }
alpar@97
   324
    /// \brief Return true if the path is empty.
alpar@96
   325
    bool empty() const { return data.empty(); }
alpar@96
   326
alpar@97
   327
    /// \brief Reset the path to an empty one.
alpar@96
   328
    void clear() { data.clear(); }
alpar@96
   329
alpar@97
   330
    /// \brief The nth arc.
alpar@96
   331
    ///
alpar@96
   332
    /// \pre n is in the [0..length() - 1] range
alpar@96
   333
    const Arc& nth(int n) const {
alpar@96
   334
      return data[n];
alpar@96
   335
    }
alpar@96
   336
alpar@96
   337
    /// \brief  Initializes arc iterator to point to the nth arc.
alpar@96
   338
    ArcIt nthIt(int n) const {
alpar@96
   339
      return ArcIt(*this, n);
alpar@96
   340
    }
alpar@96
   341
alpar@97
   342
    /// \brief The first arc of the path.
alpar@96
   343
    const Arc& front() const {
alpar@96
   344
      return data.front();
alpar@96
   345
    }
alpar@96
   346
alpar@97
   347
    /// \brief The last arc of the path.
alpar@96
   348
    const Arc& back() const {
alpar@96
   349
      return data.back();
alpar@96
   350
    }
alpar@96
   351
alpar@96
   352
    /// \brief Add a new arc behind the current path.
alpar@96
   353
    void addBack(const Arc& arc) {
alpar@96
   354
      data.push_back(arc);
alpar@96
   355
    }
alpar@96
   356
alpar@96
   357
    /// \brief Erase the last arc of the path
alpar@96
   358
    void eraseBack() {
alpar@96
   359
      data.pop_back();
alpar@96
   360
    }
alpar@96
   361
alpar@96
   362
    typedef True BuildTag;
alpar@96
   363
alpar@96
   364
    template <typename CPath>
alpar@96
   365
    void build(const CPath& path) {
alpar@96
   366
      int len = path.length();
alpar@96
   367
      data.resize(len);
alpar@96
   368
      int index = 0;
alpar@96
   369
      for (typename CPath::ArcIt it(path); it != INVALID; ++it) {
alpar@96
   370
        data[index] = it;;
alpar@96
   371
        ++index;
alpar@96
   372
      }
alpar@96
   373
    }
alpar@96
   374
alpar@96
   375
    template <typename CPath>
alpar@96
   376
    void buildRev(const CPath& path) {
alpar@96
   377
      int len = path.length();
alpar@96
   378
      data.resize(len);
alpar@96
   379
      int index = len;
alpar@96
   380
      for (typename CPath::RevArcIt it(path); it != INVALID; ++it) {
alpar@96
   381
        --index;
alpar@96
   382
        data[index] = it;;
alpar@96
   383
      }
alpar@96
   384
    }
alpar@96
   385
alpar@96
   386
  protected:
alpar@96
   387
    typedef std::vector<Arc> Container;
alpar@96
   388
    Container data;
alpar@96
   389
alpar@96
   390
  };
alpar@96
   391
alpar@96
   392
  /// \brief A structure for representing directed paths in a digraph.
alpar@96
   393
  ///
alpar@96
   394
  /// A structure for representing directed path in a digraph.
kpeter@157
   395
  /// \tparam _Digraph The digraph type in which the path is.
alpar@96
   396
  ///
alpar@96
   397
  /// In a sense, the path can be treated as a list of arcs. The
alpar@96
   398
  /// lemon path type stores just this list. As a consequence it
alpar@96
   399
  /// cannot enumerate the nodes in the path and the zero length paths
alpar@96
   400
  /// cannot store the source.
alpar@96
   401
  ///
alpar@96
   402
  /// This implementation is a back and front insertable and erasable
alpar@96
   403
  /// path type. It can be indexed in O(k) time, where k is the rank
alpar@96
   404
  /// of the arc in the path. The length can be computed in O(n)
alpar@96
   405
  /// time. The front and back insertion and erasure is O(1) time
alpar@96
   406
  /// and it can be splited and spliced in O(1) time.
alpar@96
   407
  template <typename _Digraph>
alpar@96
   408
  class ListPath {
alpar@96
   409
  public:
alpar@96
   410
alpar@96
   411
    typedef _Digraph Digraph;
alpar@96
   412
    typedef typename Digraph::Arc Arc;
alpar@96
   413
alpar@96
   414
  protected:
alpar@96
   415
alpar@209
   416
    // the std::list<> is incompatible
alpar@96
   417
    // hard to create invalid iterator
alpar@96
   418
    struct Node {
alpar@96
   419
      Arc arc;
alpar@96
   420
      Node *next, *prev;
alpar@96
   421
    };
alpar@96
   422
alpar@96
   423
    Node *first, *last;
alpar@96
   424
alpar@96
   425
    std::allocator<Node> alloc;
alpar@96
   426
alpar@96
   427
  public:
alpar@209
   428
alpar@96
   429
    /// \brief Default constructor
alpar@96
   430
    ///
alpar@96
   431
    /// Default constructor
alpar@96
   432
    ListPath() : first(0), last(0) {}
alpar@96
   433
alpar@96
   434
    /// \brief Template copy constructor
alpar@96
   435
    ///
alpar@96
   436
    /// This path can be initialized with any other path type. It just
alpar@96
   437
    /// makes a copy of the given path.
alpar@96
   438
    template <typename CPath>
alpar@96
   439
    ListPath(const CPath& cpath) : first(0), last(0) {
kpeter@505
   440
      pathCopy(cpath, *this);
alpar@96
   441
    }
alpar@96
   442
alpar@96
   443
    /// \brief Destructor of the path
alpar@96
   444
    ///
alpar@96
   445
    /// Destructor of the path
alpar@96
   446
    ~ListPath() {
alpar@96
   447
      clear();
alpar@96
   448
    }
alpar@96
   449
alpar@96
   450
    /// \brief Template copy assignment
alpar@96
   451
    ///
alpar@96
   452
    /// This path can be initialized with any other path type. It just
alpar@96
   453
    /// makes a copy of the given path.
alpar@96
   454
    template <typename CPath>
alpar@96
   455
    ListPath& operator=(const CPath& cpath) {
kpeter@505
   456
      pathCopy(cpath, *this);
alpar@96
   457
      return *this;
alpar@96
   458
    }
alpar@96
   459
alpar@96
   460
    /// \brief Iterator class to iterate on the arcs of the paths
alpar@96
   461
    ///
alpar@96
   462
    /// This class is used to iterate on the arcs of the paths
alpar@96
   463
    ///
alpar@96
   464
    /// Of course it converts to Digraph::Arc
alpar@96
   465
    class ArcIt {
alpar@96
   466
      friend class ListPath;
alpar@96
   467
    public:
alpar@96
   468
      /// Default constructor
alpar@96
   469
      ArcIt() {}
alpar@96
   470
      /// Invalid constructor
alpar@96
   471
      ArcIt(Invalid) : path(0), node(0) {}
alpar@96
   472
      /// \brief Initializate the constructor to the first arc of path
alpar@209
   473
      ArcIt(const ListPath &_path)
alpar@96
   474
        : path(&_path), node(_path.first) {}
alpar@96
   475
alpar@96
   476
    protected:
alpar@96
   477
alpar@209
   478
      ArcIt(const ListPath &_path, Node *_node)
alpar@96
   479
        : path(&_path), node(_node) {}
alpar@96
   480
alpar@96
   481
alpar@96
   482
    public:
alpar@96
   483
alpar@96
   484
      ///Conversion to Digraph::Arc
alpar@96
   485
      operator const Arc&() const {
alpar@96
   486
        return node->arc;
alpar@96
   487
      }
alpar@96
   488
alpar@96
   489
      /// Next arc
alpar@209
   490
      ArcIt& operator++() {
alpar@96
   491
        node = node->next;
alpar@209
   492
        return *this;
alpar@96
   493
      }
alpar@96
   494
alpar@96
   495
      /// Comparison operator
alpar@96
   496
      bool operator==(const ArcIt& e) const { return node==e.node; }
alpar@96
   497
      /// Comparison operator
alpar@96
   498
      bool operator!=(const ArcIt& e) const { return node!=e.node; }
alpar@96
   499
      /// Comparison operator
alpar@96
   500
      bool operator<(const ArcIt& e) const { return node<e.node; }
alpar@96
   501
alpar@96
   502
    private:
alpar@96
   503
      const ListPath *path;
alpar@96
   504
      Node *node;
alpar@96
   505
    };
alpar@96
   506
alpar@97
   507
    /// \brief The nth arc.
alpar@96
   508
    ///
alpar@97
   509
    /// This function looks for the nth arc in O(n) time.
alpar@96
   510
    /// \pre n is in the [0..length() - 1] range
alpar@96
   511
    const Arc& nth(int n) const {
alpar@96
   512
      Node *node = first;
alpar@96
   513
      for (int i = 0; i < n; ++i) {
alpar@96
   514
        node = node->next;
alpar@96
   515
      }
alpar@96
   516
      return node->arc;
alpar@96
   517
    }
alpar@96
   518
alpar@96
   519
    /// \brief Initializes arc iterator to point to the nth arc.
alpar@96
   520
    ArcIt nthIt(int n) const {
alpar@96
   521
      Node *node = first;
alpar@96
   522
      for (int i = 0; i < n; ++i) {
alpar@96
   523
        node = node->next;
alpar@96
   524
      }
alpar@96
   525
      return ArcIt(*this, node);
alpar@96
   526
    }
alpar@96
   527
alpar@96
   528
    /// \brief Length of the path.
alpar@96
   529
    int length() const {
alpar@96
   530
      int len = 0;
alpar@96
   531
      Node *node = first;
alpar@96
   532
      while (node != 0) {
alpar@96
   533
        node = node->next;
alpar@96
   534
        ++len;
alpar@96
   535
      }
alpar@96
   536
      return len;
alpar@96
   537
    }
alpar@96
   538
alpar@97
   539
    /// \brief Return true if the path is empty.
alpar@96
   540
    bool empty() const { return first == 0; }
alpar@96
   541
alpar@97
   542
    /// \brief Reset the path to an empty one.
alpar@96
   543
    void clear() {
alpar@96
   544
      while (first != 0) {
alpar@96
   545
        last = first->next;
alpar@96
   546
        alloc.destroy(first);
alpar@96
   547
        alloc.deallocate(first, 1);
alpar@96
   548
        first = last;
alpar@96
   549
      }
alpar@96
   550
    }
alpar@96
   551
alpar@97
   552
    /// \brief The first arc of the path
alpar@96
   553
    const Arc& front() const {
alpar@96
   554
      return first->arc;
alpar@96
   555
    }
alpar@96
   556
alpar@96
   557
    /// \brief Add a new arc before the current path
alpar@96
   558
    void addFront(const Arc& arc) {
alpar@96
   559
      Node *node = alloc.allocate(1);
alpar@96
   560
      alloc.construct(node, Node());
alpar@96
   561
      node->prev = 0;
alpar@96
   562
      node->next = first;
alpar@96
   563
      node->arc = arc;
alpar@96
   564
      if (first) {
alpar@96
   565
        first->prev = node;
alpar@96
   566
        first = node;
alpar@96
   567
      } else {
alpar@96
   568
        first = last = node;
alpar@96
   569
      }
alpar@96
   570
    }
alpar@96
   571
alpar@96
   572
    /// \brief Erase the first arc of the path
alpar@96
   573
    void eraseFront() {
alpar@96
   574
      Node *node = first;
alpar@96
   575
      first = first->next;
alpar@96
   576
      if (first) {
alpar@96
   577
        first->prev = 0;
alpar@96
   578
      } else {
alpar@96
   579
        last = 0;
alpar@96
   580
      }
alpar@96
   581
      alloc.destroy(node);
alpar@96
   582
      alloc.deallocate(node, 1);
alpar@96
   583
    }
alpar@96
   584
alpar@97
   585
    /// \brief The last arc of the path.
alpar@96
   586
    const Arc& back() const {
alpar@96
   587
      return last->arc;
alpar@96
   588
    }
alpar@96
   589
alpar@96
   590
    /// \brief Add a new arc behind the current path.
alpar@96
   591
    void addBack(const Arc& arc) {
alpar@96
   592
      Node *node = alloc.allocate(1);
alpar@96
   593
      alloc.construct(node, Node());
alpar@96
   594
      node->next = 0;
alpar@96
   595
      node->prev = last;
alpar@96
   596
      node->arc = arc;
alpar@96
   597
      if (last) {
alpar@96
   598
        last->next = node;
alpar@96
   599
        last = node;
alpar@96
   600
      } else {
alpar@96
   601
        last = first = node;
alpar@96
   602
      }
alpar@96
   603
    }
alpar@96
   604
alpar@96
   605
    /// \brief Erase the last arc of the path
alpar@96
   606
    void eraseBack() {
alpar@96
   607
      Node *node = last;
alpar@96
   608
      last = last->prev;
alpar@96
   609
      if (last) {
alpar@96
   610
        last->next = 0;
alpar@96
   611
      } else {
alpar@96
   612
        first = 0;
alpar@96
   613
      }
alpar@96
   614
      alloc.destroy(node);
alpar@96
   615
      alloc.deallocate(node, 1);
alpar@96
   616
    }
alpar@96
   617
alpar@97
   618
    /// \brief Splice a path to the back of the current path.
alpar@96
   619
    ///
alpar@97
   620
    /// It splices \c tpath to the back of the current path and \c
alpar@96
   621
    /// tpath becomes empty. The time complexity of this function is
alpar@96
   622
    /// O(1).
alpar@96
   623
    void spliceBack(ListPath& tpath) {
alpar@96
   624
      if (first) {
alpar@96
   625
        if (tpath.first) {
alpar@96
   626
          last->next = tpath.first;
alpar@96
   627
          tpath.first->prev = last;
alpar@96
   628
          last = tpath.last;
alpar@96
   629
        }
alpar@96
   630
      } else {
alpar@96
   631
        first = tpath.first;
alpar@96
   632
        last = tpath.last;
alpar@96
   633
      }
alpar@96
   634
      tpath.first = tpath.last = 0;
alpar@96
   635
    }
alpar@96
   636
alpar@97
   637
    /// \brief Splice a path to the front of the current path.
alpar@96
   638
    ///
alpar@97
   639
    /// It splices \c tpath before the current path and \c tpath
alpar@96
   640
    /// becomes empty. The time complexity of this function
alpar@96
   641
    /// is O(1).
alpar@96
   642
    void spliceFront(ListPath& tpath) {
alpar@96
   643
      if (first) {
alpar@96
   644
        if (tpath.first) {
alpar@96
   645
          first->prev = tpath.last;
alpar@96
   646
          tpath.last->next = first;
alpar@96
   647
          first = tpath.first;
alpar@96
   648
        }
alpar@96
   649
      } else {
alpar@96
   650
        first = tpath.first;
alpar@96
   651
        last = tpath.last;
alpar@96
   652
      }
alpar@96
   653
      tpath.first = tpath.last = 0;
alpar@96
   654
    }
alpar@96
   655
alpar@97
   656
    /// \brief Splice a path into the current path.
alpar@96
   657
    ///
alpar@96
   658
    /// It splices the \c tpath into the current path before the
alpar@96
   659
    /// position of \c it iterator and \c tpath becomes empty. The
alpar@97
   660
    /// time complexity of this function is O(1). If the \c it is
alpar@97
   661
    /// \c INVALID then it will splice behind the current path.
alpar@96
   662
    void splice(ArcIt it, ListPath& tpath) {
alpar@96
   663
      if (it.node) {
alpar@96
   664
        if (tpath.first) {
alpar@96
   665
          tpath.first->prev = it.node->prev;
alpar@96
   666
          if (it.node->prev) {
alpar@96
   667
            it.node->prev->next = tpath.first;
alpar@96
   668
          } else {
alpar@96
   669
            first = tpath.first;
alpar@96
   670
          }
alpar@96
   671
          it.node->prev = tpath.last;
alpar@96
   672
          tpath.last->next = it.node;
alpar@96
   673
        }
alpar@96
   674
      } else {
alpar@96
   675
        if (first) {
alpar@96
   676
          if (tpath.first) {
alpar@96
   677
            last->next = tpath.first;
alpar@96
   678
            tpath.first->prev = last;
alpar@96
   679
            last = tpath.last;
alpar@96
   680
          }
alpar@96
   681
        } else {
alpar@96
   682
          first = tpath.first;
alpar@96
   683
          last = tpath.last;
alpar@96
   684
        }
alpar@96
   685
      }
alpar@96
   686
      tpath.first = tpath.last = 0;
alpar@96
   687
    }
alpar@96
   688
alpar@97
   689
    /// \brief Split the current path.
alpar@96
   690
    ///
alpar@97
   691
    /// It splits the current path into two parts. The part before
alpar@97
   692
    /// the iterator \c it will remain in the current path and the part
alpar@97
   693
    /// starting with
alpar@97
   694
    /// \c it will put into \c tpath. If \c tpath have arcs
alpar@97
   695
    /// before the operation they are removed first.  The time
alpar@97
   696
    /// complexity of this function is O(1) plus the the time of emtying
alpar@97
   697
    /// \c tpath. If \c it is \c INVALID then it just clears \c tpath
alpar@96
   698
    void split(ArcIt it, ListPath& tpath) {
alpar@96
   699
      tpath.clear();
alpar@96
   700
      if (it.node) {
alpar@96
   701
        tpath.first = it.node;
alpar@96
   702
        tpath.last = last;
alpar@96
   703
        if (it.node->prev) {
alpar@96
   704
          last = it.node->prev;
alpar@96
   705
          last->next = 0;
alpar@96
   706
        } else {
alpar@96
   707
          first = last = 0;
alpar@96
   708
        }
alpar@96
   709
        it.node->prev = 0;
alpar@96
   710
      }
alpar@96
   711
    }
alpar@96
   712
alpar@96
   713
alpar@96
   714
    typedef True BuildTag;
alpar@96
   715
alpar@96
   716
    template <typename CPath>
alpar@96
   717
    void build(const CPath& path) {
alpar@96
   718
      for (typename CPath::ArcIt it(path); it != INVALID; ++it) {
alpar@96
   719
        addBack(it);
alpar@96
   720
      }
alpar@96
   721
    }
alpar@96
   722
alpar@96
   723
    template <typename CPath>
alpar@96
   724
    void buildRev(const CPath& path) {
alpar@96
   725
      for (typename CPath::RevArcIt it(path); it != INVALID; ++it) {
alpar@96
   726
        addFront(it);
alpar@96
   727
      }
alpar@96
   728
    }
alpar@96
   729
alpar@96
   730
  };
alpar@96
   731
alpar@96
   732
  /// \brief A structure for representing directed paths in a digraph.
alpar@96
   733
  ///
alpar@96
   734
  /// A structure for representing directed path in a digraph.
kpeter@157
   735
  /// \tparam _Digraph The digraph type in which the path is.
alpar@96
   736
  ///
alpar@96
   737
  /// In a sense, the path can be treated as a list of arcs. The
alpar@96
   738
  /// lemon path type stores just this list. As a consequence it
alpar@97
   739
  /// cannot enumerate the nodes in the path and the source node of
alpar@97
   740
  /// a zero length path is undefined.
alpar@96
   741
  ///
alpar@97
   742
  /// This implementation is completly static, i.e. it can be copy constucted
alpar@97
   743
  /// or copy assigned from another path, but otherwise it cannot be
alpar@97
   744
  /// modified.
alpar@97
   745
  ///
alpar@97
   746
  /// Being the the most memory efficient path type in LEMON,
alpar@97
   747
  /// it is intented to be
alpar@97
   748
  /// used when you want to store a large number of paths.
alpar@96
   749
  template <typename _Digraph>
alpar@96
   750
  class StaticPath {
alpar@96
   751
  public:
alpar@96
   752
alpar@96
   753
    typedef _Digraph Digraph;
alpar@96
   754
    typedef typename Digraph::Arc Arc;
alpar@96
   755
alpar@96
   756
    /// \brief Default constructor
alpar@96
   757
    ///
alpar@96
   758
    /// Default constructor
alpar@96
   759
    StaticPath() : len(0), arcs(0) {}
alpar@209
   760
alpar@96
   761
    /// \brief Template copy constructor
alpar@96
   762
    ///
alpar@97
   763
    /// This path can be initialized from any other path type.
alpar@96
   764
    template <typename CPath>
alpar@96
   765
    StaticPath(const CPath& cpath) : arcs(0) {
kpeter@505
   766
      pathCopy(cpath, *this);
alpar@96
   767
    }
alpar@96
   768
alpar@96
   769
    /// \brief Destructor of the path
alpar@96
   770
    ///
alpar@96
   771
    /// Destructor of the path
alpar@96
   772
    ~StaticPath() {
alpar@96
   773
      if (arcs) delete[] arcs;
alpar@96
   774
    }
alpar@96
   775
alpar@96
   776
    /// \brief Template copy assignment
alpar@96
   777
    ///
alpar@97
   778
    /// This path can be made equal to any other path type. It simply
alpar@96
   779
    /// makes a copy of the given path.
alpar@96
   780
    template <typename CPath>
alpar@96
   781
    StaticPath& operator=(const CPath& cpath) {
kpeter@505
   782
      pathCopy(cpath, *this);
alpar@96
   783
      return *this;
alpar@96
   784
    }
alpar@96
   785
alpar@96
   786
    /// \brief Iterator class to iterate on the arcs of the paths
alpar@96
   787
    ///
alpar@96
   788
    /// This class is used to iterate on the arcs of the paths
alpar@96
   789
    ///
alpar@96
   790
    /// Of course it converts to Digraph::Arc
alpar@96
   791
    class ArcIt {
alpar@96
   792
      friend class StaticPath;
alpar@96
   793
    public:
alpar@96
   794
      /// Default constructor
alpar@96
   795
      ArcIt() {}
alpar@96
   796
      /// Invalid constructor
alpar@96
   797
      ArcIt(Invalid) : path(0), idx(-1) {}
alpar@96
   798
      /// Initializate the constructor to the first arc of path
alpar@209
   799
      ArcIt(const StaticPath &_path)
alpar@96
   800
        : path(&_path), idx(_path.empty() ? -1 : 0) {}
alpar@96
   801
alpar@96
   802
    private:
alpar@96
   803
alpar@96
   804
      /// Constructor with starting point
alpar@209
   805
      ArcIt(const StaticPath &_path, int _idx)
alpar@96
   806
        : idx(_idx), path(&_path) {}
alpar@96
   807
alpar@96
   808
    public:
alpar@96
   809
alpar@96
   810
      ///Conversion to Digraph::Arc
alpar@96
   811
      operator const Arc&() const {
alpar@96
   812
        return path->nth(idx);
alpar@96
   813
      }
alpar@96
   814
alpar@96
   815
      /// Next arc
alpar@209
   816
      ArcIt& operator++() {
alpar@96
   817
        ++idx;
alpar@209
   818
        if (idx >= path->length()) idx = -1;
alpar@209
   819
        return *this;
alpar@96
   820
      }
alpar@96
   821
alpar@96
   822
      /// Comparison operator
alpar@96
   823
      bool operator==(const ArcIt& e) const { return idx==e.idx; }
alpar@96
   824
      /// Comparison operator
alpar@96
   825
      bool operator!=(const ArcIt& e) const { return idx!=e.idx; }
alpar@96
   826
      /// Comparison operator
alpar@96
   827
      bool operator<(const ArcIt& e) const { return idx<e.idx; }
alpar@96
   828
alpar@96
   829
    private:
alpar@96
   830
      const StaticPath *path;
alpar@96
   831
      int idx;
alpar@96
   832
    };
alpar@96
   833
alpar@97
   834
    /// \brief The nth arc.
alpar@96
   835
    ///
alpar@96
   836
    /// \pre n is in the [0..length() - 1] range
alpar@96
   837
    const Arc& nth(int n) const {
alpar@96
   838
      return arcs[n];
alpar@96
   839
    }
alpar@96
   840
alpar@97
   841
    /// \brief The arc iterator pointing to the nth arc.
alpar@96
   842
    ArcIt nthIt(int n) const {
alpar@96
   843
      return ArcIt(*this, n);
alpar@96
   844
    }
alpar@96
   845
alpar@97
   846
    /// \brief The length of the path.
alpar@96
   847
    int length() const { return len; }
alpar@96
   848
alpar@97
   849
    /// \brief Return true when the path is empty.
alpar@96
   850
    int empty() const { return len == 0; }
alpar@96
   851
kpeter@313
   852
    /// \brief Erase all arcs in the digraph.
alpar@96
   853
    void clear() {
alpar@96
   854
      len = 0;
alpar@96
   855
      if (arcs) delete[] arcs;
alpar@96
   856
      arcs = 0;
alpar@96
   857
    }
alpar@96
   858
alpar@97
   859
    /// \brief The first arc of the path.
alpar@96
   860
    const Arc& front() const {
alpar@96
   861
      return arcs[0];
alpar@96
   862
    }
alpar@96
   863
alpar@97
   864
    /// \brief The last arc of the path.
alpar@96
   865
    const Arc& back() const {
alpar@96
   866
      return arcs[len - 1];
alpar@96
   867
    }
alpar@96
   868
alpar@96
   869
alpar@96
   870
    typedef True BuildTag;
alpar@96
   871
alpar@96
   872
    template <typename CPath>
alpar@96
   873
    void build(const CPath& path) {
alpar@96
   874
      len = path.length();
alpar@96
   875
      arcs = new Arc[len];
alpar@96
   876
      int index = 0;
alpar@96
   877
      for (typename CPath::ArcIt it(path); it != INVALID; ++it) {
alpar@96
   878
        arcs[index] = it;
alpar@96
   879
        ++index;
alpar@96
   880
      }
alpar@96
   881
    }
alpar@96
   882
alpar@96
   883
    template <typename CPath>
alpar@96
   884
    void buildRev(const CPath& path) {
alpar@96
   885
      len = path.length();
alpar@96
   886
      arcs = new Arc[len];
alpar@96
   887
      int index = len;
alpar@96
   888
      for (typename CPath::RevArcIt it(path); it != INVALID; ++it) {
alpar@96
   889
        --index;
alpar@96
   890
        arcs[index] = it;
alpar@96
   891
      }
alpar@96
   892
    }
alpar@96
   893
alpar@96
   894
  private:
alpar@96
   895
    int len;
alpar@96
   896
    Arc* arcs;
alpar@96
   897
  };
alpar@96
   898
alpar@98
   899
  ///////////////////////////////////////////////////////////////////////
alpar@98
   900
  // Additional utilities
alpar@98
   901
  ///////////////////////////////////////////////////////////////////////
alpar@98
   902
alpar@98
   903
  namespace _path_bits {
alpar@98
   904
alpar@98
   905
    template <typename Path, typename Enable = void>
deba@144
   906
    struct RevPathTagIndicator {
alpar@98
   907
      static const bool value = false;
alpar@98
   908
    };
alpar@98
   909
deba@144
   910
    template <typename Path>
deba@144
   911
    struct RevPathTagIndicator<
alpar@209
   912
      Path,
deba@144
   913
      typename enable_if<typename Path::RevPathTag, void>::type
deba@144
   914
      > {
deba@144
   915
      static const bool value = true;
deba@144
   916
    };
deba@144
   917
deba@144
   918
    template <typename Path, typename Enable = void>
deba@144
   919
    struct BuildTagIndicator {
deba@144
   920
      static const bool value = false;
deba@144
   921
    };
deba@144
   922
deba@144
   923
    template <typename Path>
deba@144
   924
    struct BuildTagIndicator<
alpar@209
   925
      Path,
deba@144
   926
      typename enable_if<typename Path::BuildTag, void>::type
alpar@98
   927
    > {
alpar@98
   928
      static const bool value = true;
alpar@98
   929
    };
alpar@98
   930
kpeter@505
   931
    template <typename From, typename To,
kpeter@505
   932
              bool buildEnable = BuildTagIndicator<To>::value>
kpeter@487
   933
    struct PathCopySelectorForward {
kpeter@505
   934
      static void copy(const From& from, To& to) {
kpeter@505
   935
        to.clear();
kpeter@505
   936
        for (typename From::ArcIt it(from); it != INVALID; ++it) {
kpeter@505
   937
          to.addBack(it);
alpar@98
   938
        }
alpar@98
   939
      }
alpar@98
   940
    };
alpar@98
   941
kpeter@505
   942
    template <typename From, typename To>
kpeter@505
   943
    struct PathCopySelectorForward<From, To, true> {
kpeter@505
   944
      static void copy(const From& from, To& to) {
kpeter@505
   945
        to.clear();
kpeter@505
   946
        to.build(from);
kpeter@487
   947
      }
kpeter@487
   948
    };
kpeter@487
   949
kpeter@505
   950
    template <typename From, typename To,
kpeter@505
   951
              bool buildEnable = BuildTagIndicator<To>::value>
kpeter@487
   952
    struct PathCopySelectorBackward {
kpeter@505
   953
      static void copy(const From& from, To& to) {
kpeter@505
   954
        to.clear();
kpeter@505
   955
        for (typename From::RevArcIt it(from); it != INVALID; ++it) {
kpeter@505
   956
          to.addFront(it);
alpar@98
   957
        }
alpar@98
   958
      }
alpar@98
   959
    };
alpar@98
   960
kpeter@505
   961
    template <typename From, typename To>
kpeter@505
   962
    struct PathCopySelectorBackward<From, To, true> {
kpeter@505
   963
      static void copy(const From& from, To& to) {
kpeter@505
   964
        to.clear();
kpeter@505
   965
        to.buildRev(from);
alpar@98
   966
      }
alpar@98
   967
    };
alpar@98
   968
kpeter@487
   969
    
kpeter@505
   970
    template <typename From, typename To,
kpeter@505
   971
              bool revEnable = RevPathTagIndicator<From>::value>
kpeter@487
   972
    struct PathCopySelector {
kpeter@505
   973
      static void copy(const From& from, To& to) {
kpeter@505
   974
        PathCopySelectorForward<From, To>::copy(from, to);
kpeter@487
   975
      }      
kpeter@487
   976
    };
kpeter@487
   977
kpeter@505
   978
    template <typename From, typename To>
kpeter@505
   979
    struct PathCopySelector<From, To, true> {
kpeter@505
   980
      static void copy(const From& from, To& to) {
kpeter@505
   981
        PathCopySelectorBackward<From, To>::copy(from, to);
kpeter@487
   982
      }      
kpeter@487
   983
    };
kpeter@487
   984
alpar@98
   985
  }
alpar@98
   986
alpar@98
   987
alpar@98
   988
  /// \brief Make a copy of a path.
alpar@98
   989
  ///
kpeter@505
   990
  /// This function makes a copy of a path.
kpeter@505
   991
  template <typename From, typename To>
kpeter@505
   992
  void pathCopy(const From& from, To& to) {
kpeter@505
   993
    checkConcept<concepts::PathDumper<typename From::Digraph>, From>();
kpeter@505
   994
    _path_bits::PathCopySelector<From, To>::copy(from, to);
kpeter@505
   995
  }
kpeter@505
   996
kpeter@505
   997
  /// \brief Deprecated version of \ref pathCopy().
kpeter@505
   998
  ///
kpeter@505
   999
  /// Deprecated version of \ref pathCopy() (only for reverse compatibility).
kpeter@505
  1000
  template <typename To, typename From>
kpeter@505
  1001
  void copyPath(To& to, const From& from) {
kpeter@505
  1002
    pathCopy(from, to);
alpar@98
  1003
  }
alpar@98
  1004
alpar@98
  1005
  /// \brief Check the consistency of a path.
alpar@98
  1006
  ///
alpar@98
  1007
  /// This function checks that the target of each arc is the same
alpar@209
  1008
  /// as the source of the next one.
alpar@209
  1009
  ///
alpar@98
  1010
  template <typename Digraph, typename Path>
alpar@98
  1011
  bool checkPath(const Digraph& digraph, const Path& path) {
alpar@98
  1012
    typename Path::ArcIt it(path);
alpar@98
  1013
    if (it == INVALID) return true;
alpar@98
  1014
    typename Digraph::Node node = digraph.target(it);
alpar@98
  1015
    ++it;
alpar@98
  1016
    while (it != INVALID) {
alpar@98
  1017
      if (digraph.source(it) != node) return false;
alpar@98
  1018
      node = digraph.target(it);
alpar@98
  1019
      ++it;
alpar@98
  1020
    }
alpar@98
  1021
    return true;
alpar@98
  1022
  }
alpar@98
  1023
alpar@98
  1024
  /// \brief The source of a path
alpar@98
  1025
  ///
kpeter@503
  1026
  /// This function returns the source node of the given path.
kpeter@503
  1027
  /// If the path is empty, then it returns \c INVALID.
alpar@98
  1028
  template <typename Digraph, typename Path>
alpar@98
  1029
  typename Digraph::Node pathSource(const Digraph& digraph, const Path& path) {
kpeter@503
  1030
    return path.empty() ? INVALID : digraph.source(path.front());
alpar@98
  1031
  }
alpar@98
  1032
alpar@98
  1033
  /// \brief The target of a path
alpar@98
  1034
  ///
kpeter@503
  1035
  /// This function returns the target node of the given path.
kpeter@503
  1036
  /// If the path is empty, then it returns \c INVALID.
alpar@98
  1037
  template <typename Digraph, typename Path>
alpar@98
  1038
  typename Digraph::Node pathTarget(const Digraph& digraph, const Path& path) {
kpeter@503
  1039
    return path.empty() ? INVALID : digraph.target(path.back());
alpar@98
  1040
  }
alpar@98
  1041
alpar@98
  1042
  /// \brief Class which helps to iterate through the nodes of a path
alpar@98
  1043
  ///
alpar@98
  1044
  /// In a sense, the path can be treated as a list of arcs. The
alpar@98
  1045
  /// lemon path type stores only this list. As a consequence, it
alpar@98
  1046
  /// cannot enumerate the nodes in the path and the zero length paths
alpar@98
  1047
  /// cannot have a source node.
alpar@98
  1048
  ///
alpar@98
  1049
  /// This class implements the node iterator of a path structure. To
alpar@98
  1050
  /// provide this feature, the underlying digraph should be passed to
alpar@98
  1051
  /// the constructor of the iterator.
alpar@98
  1052
  template <typename Path>
alpar@98
  1053
  class PathNodeIt {
alpar@98
  1054
  private:
alpar@98
  1055
    const typename Path::Digraph *_digraph;
alpar@98
  1056
    typename Path::ArcIt _it;
alpar@98
  1057
    typename Path::Digraph::Node _nd;
alpar@98
  1058
alpar@98
  1059
  public:
alpar@98
  1060
alpar@98
  1061
    typedef typename Path::Digraph Digraph;
alpar@98
  1062
    typedef typename Digraph::Node Node;
alpar@209
  1063
alpar@98
  1064
    /// Default constructor
alpar@98
  1065
    PathNodeIt() {}
alpar@98
  1066
    /// Invalid constructor
alpar@209
  1067
    PathNodeIt(Invalid)
alpar@98
  1068
      : _digraph(0), _it(INVALID), _nd(INVALID) {}
alpar@98
  1069
    /// Constructor
alpar@209
  1070
    PathNodeIt(const Digraph& digraph, const Path& path)
alpar@98
  1071
      : _digraph(&digraph), _it(path) {
alpar@98
  1072
      _nd = (_it != INVALID ? _digraph->source(_it) : INVALID);
alpar@98
  1073
    }
alpar@98
  1074
    /// Constructor
alpar@209
  1075
    PathNodeIt(const Digraph& digraph, const Path& path, const Node& src)
alpar@98
  1076
      : _digraph(&digraph), _it(path), _nd(src) {}
alpar@98
  1077
alpar@98
  1078
    ///Conversion to Digraph::Node
alpar@98
  1079
    operator Node() const {
alpar@98
  1080
      return _nd;
alpar@98
  1081
    }
alpar@98
  1082
alpar@98
  1083
    /// Next node
alpar@98
  1084
    PathNodeIt& operator++() {
alpar@98
  1085
      if (_it == INVALID) _nd = INVALID;
alpar@98
  1086
      else {
alpar@209
  1087
        _nd = _digraph->target(_it);
alpar@209
  1088
        ++_it;
alpar@98
  1089
      }
alpar@98
  1090
      return *this;
alpar@98
  1091
    }
alpar@98
  1092
alpar@98
  1093
    /// Comparison operator
alpar@209
  1094
    bool operator==(const PathNodeIt& n) const {
alpar@209
  1095
      return _it == n._it && _nd == n._nd;
alpar@98
  1096
    }
alpar@98
  1097
    /// Comparison operator
alpar@209
  1098
    bool operator!=(const PathNodeIt& n) const {
alpar@209
  1099
      return _it != n._it || _nd != n._nd;
alpar@98
  1100
    }
alpar@98
  1101
    /// Comparison operator
alpar@209
  1102
    bool operator<(const PathNodeIt& n) const {
alpar@98
  1103
      return (_it < n._it && _nd != INVALID);
alpar@98
  1104
    }
alpar@209
  1105
alpar@98
  1106
  };
alpar@209
  1107
alpar@96
  1108
  ///@}
alpar@96
  1109
alpar@96
  1110
} // namespace lemon
alpar@96
  1111
alpar@96
  1112
#endif // LEMON_PATH_H