lemon/bits/path_dump.h
author Peter Kovacs <kpeter@inf.elte.hu>
Fri, 24 Apr 2009 12:22:06 +0200
changeset 613 b1811c363299
parent 519 c786cd201266
child 887 ca4059d63236
permissions -rw-r--r--
Bug fix in NetworkSimplex (#234)
alpar@209
     1
/* -*- mode: C++; indent-tabs-mode: nil; -*-
alpar@100
     2
 *
alpar@209
     3
 * This file is a part of LEMON, a generic C++ optimization library.
alpar@100
     4
 *
alpar@440
     5
 * Copyright (C) 2003-2009
alpar@100
     6
 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
alpar@100
     7
 * (Egervary Research Group on Combinatorial Optimization, EGRES).
alpar@100
     8
 *
alpar@100
     9
 * Permission to use, modify and distribute this software is granted
alpar@100
    10
 * provided that this copyright notice appears in all copies. For
alpar@100
    11
 * precise terms see the accompanying LICENSE file.
alpar@100
    12
 *
alpar@100
    13
 * This software is provided "AS IS" with no warranty of any kind,
alpar@100
    14
 * express or implied, and with no claim as to its suitability for any
alpar@100
    15
 * purpose.
alpar@100
    16
 *
alpar@100
    17
 */
alpar@100
    18
deba@529
    19
#ifndef LEMON_BITS_PATH_DUMP_H
deba@529
    20
#define LEMON_BITS_PATH_DUMP_H
alpar@100
    21
deba@519
    22
#include <lemon/core.h>
deba@519
    23
#include <lemon/concept_check.h>
deba@519
    24
alpar@100
    25
namespace lemon {
alpar@100
    26
alpar@100
    27
  template <typename _Digraph, typename _PredMap>
alpar@100
    28
  class PredMapPath {
alpar@100
    29
  public:
alpar@100
    30
    typedef True RevPathTag;
alpar@100
    31
alpar@100
    32
    typedef _Digraph Digraph;
alpar@100
    33
    typedef typename Digraph::Arc Arc;
alpar@100
    34
    typedef _PredMap PredMap;
alpar@100
    35
alpar@100
    36
    PredMapPath(const Digraph& _digraph, const PredMap& _predMap,
alpar@100
    37
                typename Digraph::Node _target)
alpar@100
    38
      : digraph(_digraph), predMap(_predMap), target(_target) {}
alpar@100
    39
alpar@100
    40
    int length() const {
alpar@100
    41
      int len = 0;
alpar@100
    42
      typename Digraph::Node node = target;
alpar@100
    43
      typename Digraph::Arc arc;
alpar@100
    44
      while ((arc = predMap[node]) != INVALID) {
alpar@100
    45
        node = digraph.source(arc);
alpar@100
    46
        ++len;
alpar@100
    47
      }
alpar@100
    48
      return len;
alpar@100
    49
    }
alpar@100
    50
alpar@100
    51
    bool empty() const {
alpar@100
    52
      return predMap[target] != INVALID;
alpar@100
    53
    }
alpar@100
    54
alpar@100
    55
    class RevArcIt {
alpar@100
    56
    public:
alpar@100
    57
      RevArcIt() {}
alpar@100
    58
      RevArcIt(Invalid) : path(0), current(INVALID) {}
alpar@209
    59
      RevArcIt(const PredMapPath& _path)
alpar@100
    60
        : path(&_path), current(_path.target) {
alpar@100
    61
        if (path->predMap[current] == INVALID) current = INVALID;
alpar@100
    62
      }
alpar@100
    63
alpar@100
    64
      operator const typename Digraph::Arc() const {
alpar@100
    65
        return path->predMap[current];
alpar@100
    66
      }
alpar@100
    67
alpar@100
    68
      RevArcIt& operator++() {
alpar@100
    69
        current = path->digraph.source(path->predMap[current]);
alpar@100
    70
        if (path->predMap[current] == INVALID) current = INVALID;
alpar@100
    71
        return *this;
alpar@100
    72
      }
alpar@100
    73
alpar@209
    74
      bool operator==(const RevArcIt& e) const {
alpar@209
    75
        return current == e.current;
alpar@100
    76
      }
alpar@100
    77
alpar@100
    78
      bool operator!=(const RevArcIt& e) const {
alpar@209
    79
        return current != e.current;
alpar@100
    80
      }
alpar@100
    81
alpar@209
    82
      bool operator<(const RevArcIt& e) const {
alpar@209
    83
        return current < e.current;
alpar@100
    84
      }
alpar@209
    85
alpar@100
    86
    private:
alpar@100
    87
      const PredMapPath* path;
alpar@100
    88
      typename Digraph::Node current;
alpar@100
    89
    };
alpar@100
    90
alpar@100
    91
  private:
alpar@100
    92
    const Digraph& digraph;
alpar@100
    93
    const PredMap& predMap;
alpar@100
    94
    typename Digraph::Node target;
alpar@100
    95
  };
alpar@100
    96
alpar@100
    97
alpar@100
    98
  template <typename _Digraph, typename _PredMatrixMap>
alpar@100
    99
  class PredMatrixMapPath {
alpar@100
   100
  public:
alpar@100
   101
    typedef True RevPathTag;
alpar@100
   102
alpar@100
   103
    typedef _Digraph Digraph;
alpar@100
   104
    typedef typename Digraph::Arc Arc;
alpar@100
   105
    typedef _PredMatrixMap PredMatrixMap;
alpar@100
   106
alpar@209
   107
    PredMatrixMapPath(const Digraph& _digraph,
alpar@100
   108
                      const PredMatrixMap& _predMatrixMap,
alpar@209
   109
                      typename Digraph::Node _source,
alpar@100
   110
                      typename Digraph::Node _target)
alpar@209
   111
      : digraph(_digraph), predMatrixMap(_predMatrixMap),
alpar@100
   112
        source(_source), target(_target) {}
alpar@100
   113
alpar@100
   114
    int length() const {
alpar@100
   115
      int len = 0;
alpar@100
   116
      typename Digraph::Node node = target;
alpar@100
   117
      typename Digraph::Arc arc;
alpar@100
   118
      while ((arc = predMatrixMap(source, node)) != INVALID) {
alpar@100
   119
        node = digraph.source(arc);
alpar@100
   120
        ++len;
alpar@100
   121
      }
alpar@100
   122
      return len;
alpar@100
   123
    }
alpar@100
   124
alpar@100
   125
    bool empty() const {
alpar@100
   126
      return source != target;
alpar@100
   127
    }
alpar@100
   128
alpar@100
   129
    class RevArcIt {
alpar@100
   130
    public:
alpar@100
   131
      RevArcIt() {}
alpar@100
   132
      RevArcIt(Invalid) : path(0), current(INVALID) {}
alpar@209
   133
      RevArcIt(const PredMatrixMapPath& _path)
alpar@100
   134
        : path(&_path), current(_path.target) {
alpar@209
   135
        if (path->predMatrixMap(path->source, current) == INVALID)
alpar@100
   136
          current = INVALID;
alpar@100
   137
      }
alpar@100
   138
alpar@100
   139
      operator const typename Digraph::Arc() const {
alpar@100
   140
        return path->predMatrixMap(path->source, current);
alpar@100
   141
      }
alpar@100
   142
alpar@100
   143
      RevArcIt& operator++() {
alpar@209
   144
        current =
alpar@100
   145
          path->digraph.source(path->predMatrixMap(path->source, current));
alpar@209
   146
        if (path->predMatrixMap(path->source, current) == INVALID)
alpar@100
   147
          current = INVALID;
alpar@100
   148
        return *this;
alpar@100
   149
      }
alpar@100
   150
alpar@209
   151
      bool operator==(const RevArcIt& e) const {
alpar@209
   152
        return current == e.current;
alpar@100
   153
      }
alpar@100
   154
alpar@100
   155
      bool operator!=(const RevArcIt& e) const {
alpar@209
   156
        return current != e.current;
alpar@100
   157
      }
alpar@100
   158
alpar@209
   159
      bool operator<(const RevArcIt& e) const {
alpar@209
   160
        return current < e.current;
alpar@100
   161
      }
alpar@209
   162
alpar@100
   163
    private:
alpar@100
   164
      const PredMatrixMapPath* path;
alpar@100
   165
      typename Digraph::Node current;
alpar@100
   166
    };
alpar@100
   167
alpar@100
   168
  private:
alpar@100
   169
    const Digraph& digraph;
alpar@100
   170
    const PredMatrixMap& predMatrixMap;
alpar@100
   171
    typename Digraph::Node source;
alpar@100
   172
    typename Digraph::Node target;
alpar@100
   173
  };
alpar@100
   174
alpar@100
   175
}
alpar@100
   176
alpar@100
   177
#endif