COIN-OR::LEMON - Graph Library

source: lemon-1.2/lemon/bits/path_dump.h @ 209:765619b7cbb2

Last change on this file since 209:765619b7cbb2 was 209:765619b7cbb2, checked in by Alpar Juttner <alpar@…>, 16 years ago

Apply unify-sources.sh to the source tree

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