3 * This file is a part of LEMON, a generic C++ optimization library
5 * Copyright (C) 2003-2008
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
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.
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
21 ///\brief Classes for representing paths in digraphs.
23 ///\todo Iterators have obsolete style
25 #ifndef LEMON_CONCEPT_PATH_H
26 #define LEMON_CONCEPT_PATH_H
28 #include <lemon/bits/invalid.h>
29 #include <lemon/bits/utility.h>
30 #include <lemon/concept_check.h>
35 /// \addtogroup concept
38 /// \brief A skeleton structure for representing directed paths in
41 /// A skeleton structure for representing directed paths in a
43 /// \tparam _Digraph The digraph type in which the path is.
45 /// In a sense, the path can be treated as a list of arcs. The
46 /// lemon path type stores just this list. As a consequence it
47 /// cannot enumerate the nodes in the path and the zero length
48 /// paths cannot store the source.
50 template <typename _Digraph>
54 /// Type of the underlying digraph.
55 typedef _Digraph Digraph;
56 /// Arc type of the underlying digraph.
57 typedef typename Digraph::Arc Arc;
61 /// \brief Default constructor
64 /// \brief Template constructor
65 template <typename CPath>
66 Path(const CPath& cpath) {}
68 /// \brief Template assigment
69 template <typename CPath>
70 Path& operator=(const CPath& cpath) {}
72 /// Length of the path ie. the number of arcs in the path.
73 int length() const { return 0;}
75 /// Returns whether the path is empty.
76 bool empty() const { return true;}
78 /// Resets the path to an empty path.
81 /// \brief Lemon style iterator for path arcs
83 /// This class is used to iterate on the arcs of the paths.
86 /// Default constructor
88 /// Invalid constructor
90 /// Constructor for first arc
91 ArcIt(const Path &) {}
94 operator Arc() const { return INVALID; }
97 ArcIt& operator++() {return *this;}
99 /// Comparison operator
100 bool operator==(const ArcIt&) const {return true;}
101 /// Comparison operator
102 bool operator!=(const ArcIt&) const {return true;}
103 /// Comparison operator
104 bool operator<(const ArcIt&) const {return false;}
108 template <typename _Path>
119 typename _Path::ArcIt id, ii(INVALID), i(p);
122 typename Digraph::Arc ed = i;
128 ignore_unused_variable_warning(l);
129 ignore_unused_variable_warning(pp);
130 ignore_unused_variable_warning(e);
131 ignore_unused_variable_warning(id);
132 ignore_unused_variable_warning(ii);
133 ignore_unused_variable_warning(ed);
139 namespace _path_bits {
141 template <typename _Digraph, typename _Path, typename RevPathTag = void>
142 struct PathDumperConstraints {
147 typename _Path::ArcIt id, i(p);
150 typename _Digraph::Arc ed = i;
155 ignore_unused_variable_warning(l);
156 ignore_unused_variable_warning(e);
157 ignore_unused_variable_warning(id);
158 ignore_unused_variable_warning(ed);
163 template <typename _Digraph, typename _Path>
164 struct PathDumperConstraints<
166 typename enable_if<typename _Path::RevPathTag, void>::type
172 typename _Path::RevArcIt id, i(p);
175 typename _Digraph::Arc ed = i;
180 ignore_unused_variable_warning(l);
181 ignore_unused_variable_warning(e);
182 ignore_unused_variable_warning(id);
183 ignore_unused_variable_warning(ed);
191 /// \brief A skeleton structure for path dumpers.
193 /// A skeleton structure for path dumpers. The path dumpers are
194 /// the generalization of the paths. The path dumpers can
195 /// enumerate the arcs of the path wheter in forward or in
196 /// backward order. In most time these classes are not used
197 /// directly rather it used to assign a dumped class to a real
200 /// The main purpose of this concept is that the shortest path
201 /// algorithms can enumerate easily the arcs in reverse order.
202 /// If we would like to give back a real path from these
203 /// algorithms then we should create a temporarly path object. In
204 /// Lemon such algorithms gives back a path dumper what can
205 /// assigned to a real path and the dumpers can be implemented as
206 /// an adaptor class to the predecessor map.
208 /// \tparam _Digraph The digraph type in which the path is.
210 /// The paths can be constructed from any path type by a
211 /// template constructor or a template assignment operator.
213 template <typename _Digraph>
217 /// Type of the underlying digraph.
218 typedef _Digraph Digraph;
219 /// Arc type of the underlying digraph.
220 typedef typename Digraph::Arc Arc;
222 /// Length of the path ie. the number of arcs in the path.
223 int length() const { return 0;}
225 /// Returns whether the path is empty.
226 bool empty() const { return true;}
228 /// \brief Forward or reverse dumping
230 /// If the RevPathTag is defined and true then reverse dumping
231 /// is provided in the path dumper. In this case instead of the
232 /// ArcIt the RevArcIt iterator should be implemented in the
234 typedef False RevPathTag;
236 /// \brief Lemon style iterator for path arcs
238 /// This class is used to iterate on the arcs of the paths.
241 /// Default constructor
243 /// Invalid constructor
245 /// Constructor for first arc
246 ArcIt(const PathDumper&) {}
248 /// Conversion to Arc
249 operator Arc() const { return INVALID; }
252 ArcIt& operator++() {return *this;}
254 /// Comparison operator
255 bool operator==(const ArcIt&) const {return true;}
256 /// Comparison operator
257 bool operator!=(const ArcIt&) const {return true;}
258 /// Comparison operator
259 bool operator<(const ArcIt&) const {return false;}
263 /// \brief Lemon style iterator for path arcs
265 /// This class is used to iterate on the arcs of the paths in
266 /// reverse direction.
269 /// Default constructor
271 /// Invalid constructor
273 /// Constructor for first arc
274 RevArcIt(const PathDumper &) {}
276 /// Conversion to Arc
277 operator Arc() const { return INVALID; }
280 RevArcIt& operator++() {return *this;}
282 /// Comparison operator
283 bool operator==(const RevArcIt&) const {return true;}
284 /// Comparison operator
285 bool operator!=(const RevArcIt&) const {return true;}
286 /// Comparison operator
287 bool operator<(const RevArcIt&) const {return false;}
291 template <typename _Path>
294 function_requires<_path_bits::
295 PathDumperConstraints<Digraph, _Path> >();
307 #endif // LEMON_CONCEPT_PATH_H