alpar@96
|
1 |
/* -*- C++ -*-
|
alpar@96
|
2 |
*
|
alpar@96
|
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 concept
|
alpar@96
|
20 |
///\file
|
alpar@96
|
21 |
///\brief Classes for representing paths in digraphs.
|
alpar@96
|
22 |
///
|
alpar@96
|
23 |
///\todo Iterators have obsolete style
|
alpar@96
|
24 |
|
alpar@96
|
25 |
#ifndef LEMON_CONCEPT_PATH_H
|
alpar@96
|
26 |
#define LEMON_CONCEPT_PATH_H
|
alpar@96
|
27 |
|
alpar@96
|
28 |
#include <lemon/bits/invalid.h>
|
alpar@96
|
29 |
#include <lemon/bits/utility.h>
|
alpar@96
|
30 |
#include <lemon/concept_check.h>
|
alpar@96
|
31 |
|
alpar@96
|
32 |
namespace lemon {
|
alpar@96
|
33 |
namespace concepts {
|
alpar@96
|
34 |
|
alpar@96
|
35 |
/// \addtogroup concept
|
alpar@96
|
36 |
/// @{
|
alpar@96
|
37 |
|
alpar@96
|
38 |
/// \brief A skeleton structure for representing directed paths in
|
alpar@96
|
39 |
/// a digraph.
|
alpar@96
|
40 |
///
|
alpar@96
|
41 |
/// A skeleton structure for representing directed paths in a
|
alpar@96
|
42 |
/// digraph.
|
alpar@96
|
43 |
/// \param _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@96
|
46 |
/// lemon path type stores just this list. As a consequence it
|
alpar@96
|
47 |
/// cannot enumerate the nodes in the path and the zero length
|
alpar@96
|
48 |
/// paths cannot store the source.
|
alpar@96
|
49 |
///
|
alpar@96
|
50 |
template <typename _Digraph>
|
alpar@96
|
51 |
class Path {
|
alpar@96
|
52 |
public:
|
alpar@96
|
53 |
|
alpar@96
|
54 |
/// Type of the underlying digraph.
|
alpar@96
|
55 |
typedef _Digraph Digraph;
|
alpar@96
|
56 |
/// Arc type of the underlying digraph.
|
alpar@96
|
57 |
typedef typename Digraph::Arc Arc;
|
alpar@96
|
58 |
|
alpar@96
|
59 |
class ArcIt;
|
alpar@96
|
60 |
|
alpar@96
|
61 |
/// \brief Default constructor
|
alpar@96
|
62 |
Path() {}
|
alpar@96
|
63 |
|
alpar@96
|
64 |
/// \brief Template constructor
|
alpar@96
|
65 |
template <typename CPath>
|
alpar@96
|
66 |
Path(const CPath& cpath) {}
|
alpar@96
|
67 |
|
alpar@96
|
68 |
/// \brief Template assigment
|
alpar@96
|
69 |
template <typename CPath>
|
alpar@96
|
70 |
Path& operator=(const CPath& cpath) {}
|
alpar@96
|
71 |
|
alpar@96
|
72 |
/// Length of the path ie. the number of arcs in the path.
|
alpar@96
|
73 |
int length() const { return 0;}
|
alpar@96
|
74 |
|
alpar@96
|
75 |
/// Returns whether the path is empty.
|
alpar@96
|
76 |
bool empty() const { return true;}
|
alpar@96
|
77 |
|
alpar@96
|
78 |
/// Resets the path to an empty path.
|
alpar@96
|
79 |
void clear() {}
|
alpar@96
|
80 |
|
alpar@96
|
81 |
/// \brief Lemon style iterator for path arcs
|
alpar@96
|
82 |
///
|
alpar@96
|
83 |
/// This class is used to iterate on the arcs of the paths.
|
alpar@96
|
84 |
class ArcIt {
|
alpar@96
|
85 |
public:
|
alpar@96
|
86 |
/// Default constructor
|
alpar@96
|
87 |
ArcIt() {}
|
alpar@96
|
88 |
/// Invalid constructor
|
alpar@96
|
89 |
ArcIt(Invalid) {}
|
alpar@96
|
90 |
/// Constructor for first arc
|
alpar@96
|
91 |
ArcIt(const Path &) {}
|
alpar@96
|
92 |
|
alpar@96
|
93 |
/// Conversion to Arc
|
alpar@96
|
94 |
operator Arc() const { return INVALID; }
|
alpar@96
|
95 |
|
alpar@96
|
96 |
/// Next arc
|
alpar@96
|
97 |
ArcIt& operator++() {return *this;}
|
alpar@96
|
98 |
|
alpar@96
|
99 |
/// Comparison operator
|
alpar@96
|
100 |
bool operator==(const ArcIt&) const {return true;}
|
alpar@96
|
101 |
/// Comparison operator
|
alpar@96
|
102 |
bool operator!=(const ArcIt&) const {return true;}
|
alpar@96
|
103 |
/// Comparison operator
|
alpar@96
|
104 |
bool operator<(const ArcIt&) const {return false;}
|
alpar@96
|
105 |
|
alpar@96
|
106 |
};
|
alpar@96
|
107 |
|
alpar@96
|
108 |
template <typename _Path>
|
alpar@96
|
109 |
struct Constraints {
|
alpar@96
|
110 |
void constraints() {
|
alpar@96
|
111 |
Path<Digraph> pc;
|
alpar@96
|
112 |
_Path p, pp(pc);
|
alpar@96
|
113 |
int l = p.length();
|
alpar@96
|
114 |
int e = p.empty();
|
alpar@96
|
115 |
p.clear();
|
alpar@96
|
116 |
|
alpar@96
|
117 |
p = pc;
|
alpar@96
|
118 |
|
alpar@96
|
119 |
typename _Path::ArcIt id, ii(INVALID), i(p);
|
alpar@96
|
120 |
|
alpar@96
|
121 |
++i;
|
alpar@96
|
122 |
typename Digraph::Arc ed = i;
|
alpar@96
|
123 |
|
alpar@96
|
124 |
e = (i == ii);
|
alpar@96
|
125 |
e = (i != ii);
|
alpar@96
|
126 |
e = (i < ii);
|
alpar@96
|
127 |
|
alpar@96
|
128 |
ignore_unused_variable_warning(l);
|
alpar@96
|
129 |
ignore_unused_variable_warning(pp);
|
alpar@96
|
130 |
ignore_unused_variable_warning(e);
|
alpar@96
|
131 |
ignore_unused_variable_warning(id);
|
alpar@96
|
132 |
ignore_unused_variable_warning(ii);
|
alpar@96
|
133 |
ignore_unused_variable_warning(ed);
|
alpar@96
|
134 |
}
|
alpar@96
|
135 |
};
|
alpar@96
|
136 |
|
alpar@96
|
137 |
};
|
alpar@96
|
138 |
|
alpar@96
|
139 |
namespace _path_bits {
|
alpar@96
|
140 |
|
alpar@96
|
141 |
template <typename _Digraph, typename _Path, typename RevPathTag = void>
|
alpar@96
|
142 |
struct PathDumperConstraints {
|
alpar@96
|
143 |
void constraints() {
|
alpar@96
|
144 |
int l = p.length();
|
alpar@96
|
145 |
int e = p.empty();
|
alpar@96
|
146 |
|
alpar@96
|
147 |
typename _Path::ArcIt id, i(p);
|
alpar@96
|
148 |
|
alpar@96
|
149 |
++i;
|
alpar@96
|
150 |
typename _Digraph::Arc ed = i;
|
alpar@96
|
151 |
|
alpar@96
|
152 |
e = (i == INVALID);
|
alpar@96
|
153 |
e = (i != INVALID);
|
alpar@96
|
154 |
|
alpar@96
|
155 |
ignore_unused_variable_warning(l);
|
alpar@96
|
156 |
ignore_unused_variable_warning(e);
|
alpar@96
|
157 |
ignore_unused_variable_warning(id);
|
alpar@96
|
158 |
ignore_unused_variable_warning(ed);
|
alpar@96
|
159 |
}
|
alpar@96
|
160 |
_Path& p;
|
alpar@96
|
161 |
};
|
alpar@96
|
162 |
|
alpar@96
|
163 |
template <typename _Digraph, typename _Path>
|
alpar@96
|
164 |
struct PathDumperConstraints<
|
alpar@96
|
165 |
_Digraph, _Path,
|
alpar@96
|
166 |
typename enable_if<typename _Path::RevPathTag, void>::type
|
alpar@96
|
167 |
> {
|
alpar@96
|
168 |
void constraints() {
|
alpar@96
|
169 |
int l = p.length();
|
alpar@96
|
170 |
int e = p.empty();
|
alpar@96
|
171 |
|
alpar@96
|
172 |
typename _Path::RevArcIt id, i(p);
|
alpar@96
|
173 |
|
alpar@96
|
174 |
++i;
|
alpar@96
|
175 |
typename _Digraph::Arc ed = i;
|
alpar@96
|
176 |
|
alpar@96
|
177 |
e = (i == INVALID);
|
alpar@96
|
178 |
e = (i != INVALID);
|
alpar@96
|
179 |
|
alpar@96
|
180 |
ignore_unused_variable_warning(l);
|
alpar@96
|
181 |
ignore_unused_variable_warning(e);
|
alpar@96
|
182 |
ignore_unused_variable_warning(id);
|
alpar@96
|
183 |
ignore_unused_variable_warning(ed);
|
alpar@96
|
184 |
}
|
alpar@96
|
185 |
_Path& p;
|
alpar@96
|
186 |
};
|
alpar@96
|
187 |
|
alpar@96
|
188 |
}
|
alpar@96
|
189 |
|
alpar@96
|
190 |
|
alpar@96
|
191 |
/// \brief A skeleton structure for path dumpers.
|
alpar@96
|
192 |
///
|
alpar@96
|
193 |
/// A skeleton structure for path dumpers. The path dumpers are
|
alpar@96
|
194 |
/// the generalization of the paths. The path dumpers can
|
alpar@96
|
195 |
/// enumerate the arcs of the path wheter in forward or in
|
alpar@96
|
196 |
/// backward order. In most time these classes are not used
|
alpar@96
|
197 |
/// directly rather it used to assign a dumped class to a real
|
alpar@96
|
198 |
/// path type.
|
alpar@96
|
199 |
///
|
alpar@96
|
200 |
/// The main purpose of this concept is that the shortest path
|
alpar@96
|
201 |
/// algorithms can enumerate easily the arcs in reverse order.
|
alpar@96
|
202 |
/// If we would like to give back a real path from these
|
alpar@96
|
203 |
/// algorithms then we should create a temporarly path object. In
|
alpar@96
|
204 |
/// Lemon such algorithms gives back a path dumper what can
|
alpar@96
|
205 |
/// assigned to a real path and the dumpers can be implemented as
|
alpar@96
|
206 |
/// an adaptor class to the predecessor map.
|
alpar@96
|
207 |
|
alpar@96
|
208 |
/// \param _Digraph The digraph type in which the path is.
|
alpar@96
|
209 |
///
|
alpar@96
|
210 |
/// The paths can be constructed from any path type by a
|
alpar@96
|
211 |
/// template constructor or a template assignment operator.
|
alpar@96
|
212 |
///
|
alpar@96
|
213 |
template <typename _Digraph>
|
alpar@96
|
214 |
class PathDumper {
|
alpar@96
|
215 |
public:
|
alpar@96
|
216 |
|
alpar@96
|
217 |
/// Type of the underlying digraph.
|
alpar@96
|
218 |
typedef _Digraph Digraph;
|
alpar@96
|
219 |
/// Arc type of the underlying digraph.
|
alpar@96
|
220 |
typedef typename Digraph::Arc Arc;
|
alpar@96
|
221 |
|
alpar@96
|
222 |
/// Length of the path ie. the number of arcs in the path.
|
alpar@96
|
223 |
int length() const { return 0;}
|
alpar@96
|
224 |
|
alpar@96
|
225 |
/// Returns whether the path is empty.
|
alpar@96
|
226 |
bool empty() const { return true;}
|
alpar@96
|
227 |
|
alpar@96
|
228 |
/// \brief Forward or reverse dumping
|
alpar@96
|
229 |
///
|
alpar@96
|
230 |
/// If the RevPathTag is defined and true then reverse dumping
|
alpar@96
|
231 |
/// is provided in the path dumper. In this case instead of the
|
alpar@96
|
232 |
/// ArcIt the RevArcIt iterator should be implemented in the
|
alpar@96
|
233 |
/// dumper.
|
alpar@96
|
234 |
typedef False RevPathTag;
|
alpar@96
|
235 |
|
alpar@96
|
236 |
/// \brief Lemon style iterator for path arcs
|
alpar@96
|
237 |
///
|
alpar@96
|
238 |
/// This class is used to iterate on the arcs of the paths.
|
alpar@96
|
239 |
class ArcIt {
|
alpar@96
|
240 |
public:
|
alpar@96
|
241 |
/// Default constructor
|
alpar@96
|
242 |
ArcIt() {}
|
alpar@96
|
243 |
/// Invalid constructor
|
alpar@96
|
244 |
ArcIt(Invalid) {}
|
alpar@96
|
245 |
/// Constructor for first arc
|
alpar@96
|
246 |
ArcIt(const PathDumper&) {}
|
alpar@96
|
247 |
|
alpar@96
|
248 |
/// Conversion to Arc
|
alpar@96
|
249 |
operator Arc() const { return INVALID; }
|
alpar@96
|
250 |
|
alpar@96
|
251 |
/// Next arc
|
alpar@96
|
252 |
ArcIt& operator++() {return *this;}
|
alpar@96
|
253 |
|
alpar@96
|
254 |
/// Comparison operator
|
alpar@96
|
255 |
bool operator==(const ArcIt&) const {return true;}
|
alpar@96
|
256 |
/// Comparison operator
|
alpar@96
|
257 |
bool operator!=(const ArcIt&) const {return true;}
|
alpar@96
|
258 |
/// Comparison operator
|
alpar@96
|
259 |
bool operator<(const ArcIt&) const {return false;}
|
alpar@96
|
260 |
|
alpar@96
|
261 |
};
|
alpar@96
|
262 |
|
alpar@96
|
263 |
/// \brief Lemon style iterator for path arcs
|
alpar@96
|
264 |
///
|
alpar@96
|
265 |
/// This class is used to iterate on the arcs of the paths in
|
alpar@96
|
266 |
/// reverse direction.
|
alpar@96
|
267 |
class RevArcIt {
|
alpar@96
|
268 |
public:
|
alpar@96
|
269 |
/// Default constructor
|
alpar@96
|
270 |
RevArcIt() {}
|
alpar@96
|
271 |
/// Invalid constructor
|
alpar@96
|
272 |
RevArcIt(Invalid) {}
|
alpar@96
|
273 |
/// Constructor for first arc
|
alpar@96
|
274 |
RevArcIt(const PathDumper &) {}
|
alpar@96
|
275 |
|
alpar@96
|
276 |
/// Conversion to Arc
|
alpar@96
|
277 |
operator Arc() const { return INVALID; }
|
alpar@96
|
278 |
|
alpar@96
|
279 |
/// Next arc
|
alpar@96
|
280 |
RevArcIt& operator++() {return *this;}
|
alpar@96
|
281 |
|
alpar@96
|
282 |
/// Comparison operator
|
alpar@96
|
283 |
bool operator==(const RevArcIt&) const {return true;}
|
alpar@96
|
284 |
/// Comparison operator
|
alpar@96
|
285 |
bool operator!=(const RevArcIt&) const {return true;}
|
alpar@96
|
286 |
/// Comparison operator
|
alpar@96
|
287 |
bool operator<(const RevArcIt&) const {return false;}
|
alpar@96
|
288 |
|
alpar@96
|
289 |
};
|
alpar@96
|
290 |
|
alpar@96
|
291 |
template <typename _Path>
|
alpar@96
|
292 |
struct Constraints {
|
alpar@96
|
293 |
void constraints() {
|
alpar@96
|
294 |
function_requires<_path_bits::
|
alpar@96
|
295 |
PathDumperConstraints<Digraph, _Path> >();
|
alpar@96
|
296 |
}
|
alpar@96
|
297 |
};
|
alpar@96
|
298 |
|
alpar@96
|
299 |
};
|
alpar@96
|
300 |
|
alpar@96
|
301 |
|
alpar@96
|
302 |
///@}
|
alpar@96
|
303 |
}
|
alpar@96
|
304 |
|
alpar@96
|
305 |
} // namespace lemon
|
alpar@96
|
306 |
|
alpar@96
|
307 |
#endif // LEMON_CONCEPT_PATH_H
|