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