External flow and potential maps can be used in MinCostMaxFlow.
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 graphs.
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 /// \param _Graph The graph type in which the path is.
45 /// In a sense, the path can be treated as a list of edges. 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 _Graph>
54 /// Type of the underlying graph.
56 /// Edge type of the underlying graph.
57 typedef typename Graph::Edge Edge;
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 edges 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 edges
83 /// This class is used to iterate on the edges of the paths.
86 /// Default constructor
88 /// Invalid constructor
90 /// Constructor for first edge
91 EdgeIt(const Path &) {}
93 /// Conversion to Edge
94 operator Edge() const { return INVALID; }
97 EdgeIt& operator++() {return *this;}
99 /// Comparison operator
100 bool operator==(const EdgeIt&) const {return true;}
101 /// Comparison operator
102 bool operator!=(const EdgeIt&) const {return true;}
103 /// Comparison operator
104 bool operator<(const EdgeIt&) const {return false;}
108 template <typename _Path>
119 typename _Path::EdgeIt id, ii(INVALID), i(p);
122 typename Graph::Edge 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 _Graph, typename _Path, typename RevPathTag = void>
142 struct PathDumperConstraints {
147 typename _Path::EdgeIt id, i(p);
150 typename _Graph::Edge 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 _Graph, typename _Path>
164 struct PathDumperConstraints<
166 typename enable_if<typename _Path::RevPathTag, void>::type
172 typename _Path::RevEdgeIt id, i(p);
175 typename _Graph::Edge 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 edges 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 edges 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 /// \param _Graph The graph 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 _Graph>
217 /// Type of the underlying graph.
218 typedef _Graph Graph;
219 /// Edge type of the underlying graph.
220 typedef typename Graph::Edge Edge;
222 /// Length of the path ie. the number of edges 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 /// EdgeIt the RevEdgeIt iterator should be implemented in the
234 typedef False RevPathTag;
236 /// \brief Lemon style iterator for path edges
238 /// This class is used to iterate on the edges of the paths.
241 /// Default constructor
243 /// Invalid constructor
245 /// Constructor for first edge
246 EdgeIt(const PathDumper&) {}
248 /// Conversion to Edge
249 operator Edge() const { return INVALID; }
252 EdgeIt& operator++() {return *this;}
254 /// Comparison operator
255 bool operator==(const EdgeIt&) const {return true;}
256 /// Comparison operator
257 bool operator!=(const EdgeIt&) const {return true;}
258 /// Comparison operator
259 bool operator<(const EdgeIt&) const {return false;}
263 /// \brief Lemon style iterator for path edges
265 /// This class is used to iterate on the edges of the paths in
266 /// reverse direction.
269 /// Default constructor
271 /// Invalid constructor
272 RevEdgeIt(Invalid) {}
273 /// Constructor for first edge
274 RevEdgeIt(const PathDumper &) {}
276 /// Conversion to Edge
277 operator Edge() const { return INVALID; }
280 RevEdgeIt& operator++() {return *this;}
282 /// Comparison operator
283 bool operator==(const RevEdgeIt&) const {return true;}
284 /// Comparison operator
285 bool operator!=(const RevEdgeIt&) const {return true;}
286 /// Comparison operator
287 bool operator<(const RevEdgeIt&) const {return false;}
291 template <typename _Path>
294 function_requires<_path_bits::
295 PathDumperConstraints<Graph, _Path> >();
307 #endif // LEMON_CONCEPT_PATH_H