1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
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.
24 #ifndef LEMON_CONCEPT_PATH_H
25 #define LEMON_CONCEPT_PATH_H
27 #include <lemon/core.h>
28 #include <lemon/concept_check.h>
33 /// \addtogroup concept
36 /// \brief A skeleton structure for representing directed paths in
39 /// A skeleton structure for representing directed paths in a
41 /// \tparam _Digraph The digraph type in which the path is.
43 /// In a sense, the path can be treated as a list of arcs. The
44 /// lemon path type stores just this list. As a consequence it
45 /// cannot enumerate the nodes in the path and the zero length
46 /// paths cannot store the source.
48 template <typename _Digraph>
52 /// Type of the underlying digraph.
53 typedef _Digraph Digraph;
54 /// Arc type of the underlying digraph.
55 typedef typename Digraph::Arc Arc;
59 /// \brief Default constructor
62 /// \brief Template constructor
63 template <typename CPath>
64 Path(const CPath& cpath) {}
66 /// \brief Template assigment
67 template <typename CPath>
68 Path& operator=(const CPath& cpath) {}
70 /// Length of the path ie. the number of arcs in the path.
71 int length() const { return 0;}
73 /// Returns whether the path is empty.
74 bool empty() const { return true;}
76 /// Resets the path to an empty path.
79 /// \brief LEMON style iterator for path arcs
81 /// This class is used to iterate on the arcs of the paths.
84 /// Default constructor
86 /// Invalid constructor
88 /// Constructor for first arc
89 ArcIt(const Path &) {}
92 operator Arc() const { return INVALID; }
95 ArcIt& operator++() {return *this;}
97 /// Comparison operator
98 bool operator==(const ArcIt&) const {return true;}
99 /// Comparison operator
100 bool operator!=(const ArcIt&) const {return true;}
101 /// Comparison operator
102 bool operator<(const ArcIt&) const {return false;}
106 template <typename _Path>
117 typename _Path::ArcIt id, ii(INVALID), i(p);
120 typename Digraph::Arc ed = i;
126 ignore_unused_variable_warning(l);
127 ignore_unused_variable_warning(pp);
128 ignore_unused_variable_warning(e);
129 ignore_unused_variable_warning(id);
130 ignore_unused_variable_warning(ii);
131 ignore_unused_variable_warning(ed);
137 namespace _path_bits {
139 template <typename _Digraph, typename _Path, typename RevPathTag = void>
140 struct PathDumperConstraints {
145 typename _Path::ArcIt id, i(p);
148 typename _Digraph::Arc ed = i;
153 ignore_unused_variable_warning(l);
154 ignore_unused_variable_warning(e);
155 ignore_unused_variable_warning(id);
156 ignore_unused_variable_warning(ed);
161 template <typename _Digraph, typename _Path>
162 struct PathDumperConstraints<
164 typename enable_if<typename _Path::RevPathTag, void>::type
170 typename _Path::RevArcIt id, i(p);
173 typename _Digraph::Arc ed = i;
178 ignore_unused_variable_warning(l);
179 ignore_unused_variable_warning(e);
180 ignore_unused_variable_warning(id);
181 ignore_unused_variable_warning(ed);
189 /// \brief A skeleton structure for path dumpers.
191 /// A skeleton structure for path dumpers. The path dumpers are
192 /// the generalization of the paths. The path dumpers can
193 /// enumerate the arcs of the path wheter in forward or in
194 /// backward order. In most time these classes are not used
195 /// directly rather it used to assign a dumped class to a real
198 /// The main purpose of this concept is that the shortest path
199 /// algorithms can enumerate easily the arcs in reverse order.
200 /// If we would like to give back a real path from these
201 /// algorithms then we should create a temporarly path object. In
202 /// LEMON such algorithms gives back a path dumper what can
203 /// assigned to a real path and the dumpers can be implemented as
204 /// an adaptor class to the predecessor map.
206 /// \tparam _Digraph The digraph type in which the path is.
208 /// The paths can be constructed from any path type by a
209 /// template constructor or a template assignment operator.
211 template <typename _Digraph>
215 /// Type of the underlying digraph.
216 typedef _Digraph Digraph;
217 /// Arc type of the underlying digraph.
218 typedef typename Digraph::Arc Arc;
220 /// Length of the path ie. the number of arcs in the path.
221 int length() const { return 0;}
223 /// Returns whether the path is empty.
224 bool empty() const { return true;}
226 /// \brief Forward or reverse dumping
228 /// If the RevPathTag is defined and true then reverse dumping
229 /// is provided in the path dumper. In this case instead of the
230 /// ArcIt the RevArcIt iterator should be implemented in the
232 typedef False RevPathTag;
234 /// \brief LEMON style iterator for path arcs
236 /// This class is used to iterate on the arcs of the paths.
239 /// Default constructor
241 /// Invalid constructor
243 /// Constructor for first arc
244 ArcIt(const PathDumper&) {}
246 /// Conversion to Arc
247 operator Arc() const { return INVALID; }
250 ArcIt& operator++() {return *this;}
252 /// Comparison operator
253 bool operator==(const ArcIt&) const {return true;}
254 /// Comparison operator
255 bool operator!=(const ArcIt&) const {return true;}
256 /// Comparison operator
257 bool operator<(const ArcIt&) const {return false;}
261 /// \brief LEMON style iterator for path arcs
263 /// This class is used to iterate on the arcs of the paths in
264 /// reverse direction.
267 /// Default constructor
269 /// Invalid constructor
271 /// Constructor for first arc
272 RevArcIt(const PathDumper &) {}
274 /// Conversion to Arc
275 operator Arc() const { return INVALID; }
278 RevArcIt& operator++() {return *this;}
280 /// Comparison operator
281 bool operator==(const RevArcIt&) const {return true;}
282 /// Comparison operator
283 bool operator!=(const RevArcIt&) const {return true;}
284 /// Comparison operator
285 bool operator<(const RevArcIt&) const {return false;}
289 template <typename _Path>
292 function_requires<_path_bits::
293 PathDumperConstraints<Digraph, _Path> >();
305 #endif // LEMON_CONCEPT_PATH_H