lemon/bits/path_dump.h
author Balazs Dezso <deba@inf.elte.hu>
Thu, 03 Jul 2008 12:40:04 +0200
changeset 188 70694e6bdcac
child 209 765619b7cbb2
permissions -rw-r--r--
New skip*() functions in (Dig|G)raphReader
alpar@100
     1
/* -*- C++ -*-
alpar@100
     2
 *
alpar@100
     3
 * This file is a part of LEMON, a generic C++ optimization library
alpar@100
     4
 *
alpar@100
     5
 * Copyright (C) 2003-2008
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
alpar@100
    19
#ifndef LEMON_BITS_PRED_MAP_PATH_H
alpar@100
    20
#define LEMON_BITS_PRED_MAP_PATH_H
alpar@100
    21
alpar@100
    22
namespace lemon {
alpar@100
    23
alpar@100
    24
  template <typename _Digraph, typename _PredMap>
alpar@100
    25
  class PredMapPath {
alpar@100
    26
  public:
alpar@100
    27
    typedef True RevPathTag;
alpar@100
    28
alpar@100
    29
    typedef _Digraph Digraph;
alpar@100
    30
    typedef typename Digraph::Arc Arc;
alpar@100
    31
    typedef _PredMap PredMap;
alpar@100
    32
alpar@100
    33
    PredMapPath(const Digraph& _digraph, const PredMap& _predMap,
alpar@100
    34
                typename Digraph::Node _target)
alpar@100
    35
      : digraph(_digraph), predMap(_predMap), target(_target) {}
alpar@100
    36
alpar@100
    37
    int length() const {
alpar@100
    38
      int len = 0;
alpar@100
    39
      typename Digraph::Node node = target;
alpar@100
    40
      typename Digraph::Arc arc;
alpar@100
    41
      while ((arc = predMap[node]) != INVALID) {
alpar@100
    42
        node = digraph.source(arc);
alpar@100
    43
        ++len;
alpar@100
    44
      }
alpar@100
    45
      return len;
alpar@100
    46
    }
alpar@100
    47
alpar@100
    48
    bool empty() const {
alpar@100
    49
      return predMap[target] != INVALID;
alpar@100
    50
    }
alpar@100
    51
alpar@100
    52
    class RevArcIt {
alpar@100
    53
    public:
alpar@100
    54
      RevArcIt() {}
alpar@100
    55
      RevArcIt(Invalid) : path(0), current(INVALID) {}
alpar@100
    56
      RevArcIt(const PredMapPath& _path) 
alpar@100
    57
        : path(&_path), current(_path.target) {
alpar@100
    58
        if (path->predMap[current] == INVALID) current = INVALID;
alpar@100
    59
      }
alpar@100
    60
alpar@100
    61
      operator const typename Digraph::Arc() const {
alpar@100
    62
        return path->predMap[current];
alpar@100
    63
      }
alpar@100
    64
alpar@100
    65
      RevArcIt& operator++() {
alpar@100
    66
        current = path->digraph.source(path->predMap[current]);
alpar@100
    67
        if (path->predMap[current] == INVALID) current = INVALID;
alpar@100
    68
        return *this;
alpar@100
    69
      }
alpar@100
    70
alpar@100
    71
      bool operator==(const RevArcIt& e) const { 
alpar@100
    72
        return current == e.current; 
alpar@100
    73
      }
alpar@100
    74
alpar@100
    75
      bool operator!=(const RevArcIt& e) const {
alpar@100
    76
        return current != e.current; 
alpar@100
    77
      }
alpar@100
    78
alpar@100
    79
      bool operator<(const RevArcIt& e) const { 
alpar@100
    80
        return current < e.current; 
alpar@100
    81
      }
alpar@100
    82
      
alpar@100
    83
    private:
alpar@100
    84
      const PredMapPath* path;
alpar@100
    85
      typename Digraph::Node current;
alpar@100
    86
    };
alpar@100
    87
alpar@100
    88
  private:
alpar@100
    89
    const Digraph& digraph;
alpar@100
    90
    const PredMap& predMap;
alpar@100
    91
    typename Digraph::Node target;
alpar@100
    92
  };
alpar@100
    93
alpar@100
    94
alpar@100
    95
  template <typename _Digraph, typename _PredMatrixMap>
alpar@100
    96
  class PredMatrixMapPath {
alpar@100
    97
  public:
alpar@100
    98
    typedef True RevPathTag;
alpar@100
    99
alpar@100
   100
    typedef _Digraph Digraph;
alpar@100
   101
    typedef typename Digraph::Arc Arc;
alpar@100
   102
    typedef _PredMatrixMap PredMatrixMap;
alpar@100
   103
alpar@100
   104
    PredMatrixMapPath(const Digraph& _digraph, 
alpar@100
   105
                      const PredMatrixMap& _predMatrixMap,
alpar@100
   106
                      typename Digraph::Node _source, 
alpar@100
   107
                      typename Digraph::Node _target)
alpar@100
   108
      : digraph(_digraph), predMatrixMap(_predMatrixMap), 
alpar@100
   109
        source(_source), target(_target) {}
alpar@100
   110
alpar@100
   111
    int length() const {
alpar@100
   112
      int len = 0;
alpar@100
   113
      typename Digraph::Node node = target;
alpar@100
   114
      typename Digraph::Arc arc;
alpar@100
   115
      while ((arc = predMatrixMap(source, node)) != INVALID) {
alpar@100
   116
        node = digraph.source(arc);
alpar@100
   117
        ++len;
alpar@100
   118
      }
alpar@100
   119
      return len;
alpar@100
   120
    }
alpar@100
   121
alpar@100
   122
    bool empty() const {
alpar@100
   123
      return source != target;
alpar@100
   124
    }
alpar@100
   125
alpar@100
   126
    class RevArcIt {
alpar@100
   127
    public:
alpar@100
   128
      RevArcIt() {}
alpar@100
   129
      RevArcIt(Invalid) : path(0), current(INVALID) {}
alpar@100
   130
      RevArcIt(const PredMatrixMapPath& _path) 
alpar@100
   131
        : path(&_path), current(_path.target) {
alpar@100
   132
        if (path->predMatrixMap(path->source, current) == INVALID) 
alpar@100
   133
          current = INVALID;
alpar@100
   134
      }
alpar@100
   135
alpar@100
   136
      operator const typename Digraph::Arc() const {
alpar@100
   137
        return path->predMatrixMap(path->source, current);
alpar@100
   138
      }
alpar@100
   139
alpar@100
   140
      RevArcIt& operator++() {
alpar@100
   141
        current = 
alpar@100
   142
          path->digraph.source(path->predMatrixMap(path->source, current));
alpar@100
   143
        if (path->predMatrixMap(path->source, current) == INVALID) 
alpar@100
   144
          current = INVALID;
alpar@100
   145
        return *this;
alpar@100
   146
      }
alpar@100
   147
alpar@100
   148
      bool operator==(const RevArcIt& e) const { 
alpar@100
   149
        return current == e.current; 
alpar@100
   150
      }
alpar@100
   151
alpar@100
   152
      bool operator!=(const RevArcIt& e) const {
alpar@100
   153
        return current != e.current; 
alpar@100
   154
      }
alpar@100
   155
alpar@100
   156
      bool operator<(const RevArcIt& e) const { 
alpar@100
   157
        return current < e.current; 
alpar@100
   158
      }
alpar@100
   159
      
alpar@100
   160
    private:
alpar@100
   161
      const PredMatrixMapPath* path;
alpar@100
   162
      typename Digraph::Node current;
alpar@100
   163
    };
alpar@100
   164
alpar@100
   165
  private:
alpar@100
   166
    const Digraph& digraph;
alpar@100
   167
    const PredMatrixMap& predMatrixMap;
alpar@100
   168
    typename Digraph::Node source;
alpar@100
   169
    typename Digraph::Node target;
alpar@100
   170
  };
alpar@100
   171
alpar@100
   172
}
alpar@100
   173
alpar@100
   174
#endif