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@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@209
|
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@209
|
71 |
bool operator==(const RevArcIt& e) const {
|
alpar@209
|
72 |
return current == e.current;
|
alpar@100
|
73 |
}
|
alpar@100
|
74 |
|
alpar@100
|
75 |
bool operator!=(const RevArcIt& e) const {
|
alpar@209
|
76 |
return current != e.current;
|
alpar@100
|
77 |
}
|
alpar@100
|
78 |
|
alpar@209
|
79 |
bool operator<(const RevArcIt& e) const {
|
alpar@209
|
80 |
return current < e.current;
|
alpar@100
|
81 |
}
|
alpar@209
|
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@209
|
104 |
PredMatrixMapPath(const Digraph& _digraph,
|
alpar@100
|
105 |
const PredMatrixMap& _predMatrixMap,
|
alpar@209
|
106 |
typename Digraph::Node _source,
|
alpar@100
|
107 |
typename Digraph::Node _target)
|
alpar@209
|
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@209
|
130 |
RevArcIt(const PredMatrixMapPath& _path)
|
alpar@100
|
131 |
: path(&_path), current(_path.target) {
|
alpar@209
|
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@209
|
141 |
current =
|
alpar@100
|
142 |
path->digraph.source(path->predMatrixMap(path->source, current));
|
alpar@209
|
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@209
|
148 |
bool operator==(const RevArcIt& e) const {
|
alpar@209
|
149 |
return current == e.current;
|
alpar@100
|
150 |
}
|
alpar@100
|
151 |
|
alpar@100
|
152 |
bool operator!=(const RevArcIt& e) const {
|
alpar@209
|
153 |
return current != e.current;
|
alpar@100
|
154 |
}
|
alpar@100
|
155 |
|
alpar@209
|
156 |
bool operator<(const RevArcIt& e) const {
|
alpar@209
|
157 |
return current < e.current;
|
alpar@100
|
158 |
}
|
alpar@209
|
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
|