alpar@399
|
1 |
/* -*- mode: C++; indent-tabs-mode: nil; -*-
|
alpar@399
|
2 |
*
|
alpar@399
|
3 |
* This file is a part of LEMON, a generic C++ optimization library.
|
alpar@399
|
4 |
*
|
alpar@440
|
5 |
* Copyright (C) 2003-2009
|
alpar@399
|
6 |
* Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
|
alpar@399
|
7 |
* (Egervary Research Group on Combinatorial Optimization, EGRES).
|
alpar@399
|
8 |
*
|
alpar@399
|
9 |
* Permission to use, modify and distribute this software is granted
|
alpar@399
|
10 |
* provided that this copyright notice appears in all copies. For
|
alpar@399
|
11 |
* precise terms see the accompanying LICENSE file.
|
alpar@399
|
12 |
*
|
alpar@399
|
13 |
* This software is provided "AS IS" with no warranty of any kind,
|
alpar@399
|
14 |
* express or implied, and with no claim as to its suitability for any
|
alpar@399
|
15 |
* purpose.
|
alpar@399
|
16 |
*
|
alpar@399
|
17 |
*/
|
alpar@399
|
18 |
|
alpar@399
|
19 |
#ifndef LEMON_CIRCULATION_H
|
alpar@399
|
20 |
#define LEMON_CIRCULATION_H
|
alpar@399
|
21 |
|
alpar@399
|
22 |
#include <lemon/tolerance.h>
|
alpar@399
|
23 |
#include <lemon/elevator.h>
|
kpeter@622
|
24 |
#include <limits>
|
alpar@399
|
25 |
|
alpar@399
|
26 |
///\ingroup max_flow
|
alpar@399
|
27 |
///\file
|
kpeter@402
|
28 |
///\brief Push-relabel algorithm for finding a feasible circulation.
|
alpar@399
|
29 |
///
|
alpar@399
|
30 |
namespace lemon {
|
alpar@399
|
31 |
|
alpar@399
|
32 |
/// \brief Default traits class of Circulation class.
|
alpar@399
|
33 |
///
|
alpar@399
|
34 |
/// Default traits class of Circulation class.
|
kpeter@610
|
35 |
///
|
kpeter@610
|
36 |
/// \tparam GR Type of the digraph the algorithm runs on.
|
kpeter@610
|
37 |
/// \tparam LM The type of the lower bound map.
|
kpeter@610
|
38 |
/// \tparam UM The type of the upper bound (capacity) map.
|
kpeter@610
|
39 |
/// \tparam SM The type of the supply map.
|
kpeter@503
|
40 |
template <typename GR, typename LM,
|
kpeter@610
|
41 |
typename UM, typename SM>
|
alpar@399
|
42 |
struct CirculationDefaultTraits {
|
alpar@399
|
43 |
|
kpeter@402
|
44 |
/// \brief The type of the digraph the algorithm runs on.
|
kpeter@503
|
45 |
typedef GR Digraph;
|
alpar@399
|
46 |
|
kpeter@610
|
47 |
/// \brief The type of the lower bound map.
|
alpar@399
|
48 |
///
|
kpeter@610
|
49 |
/// The type of the map that stores the lower bounds on the arcs.
|
kpeter@610
|
50 |
/// It must conform to the \ref concepts::ReadMap "ReadMap" concept.
|
kpeter@610
|
51 |
typedef LM LowerMap;
|
alpar@399
|
52 |
|
kpeter@610
|
53 |
/// \brief The type of the upper bound (capacity) map.
|
alpar@399
|
54 |
///
|
kpeter@610
|
55 |
/// The type of the map that stores the upper bounds (capacities)
|
kpeter@610
|
56 |
/// on the arcs.
|
kpeter@610
|
57 |
/// It must conform to the \ref concepts::ReadMap "ReadMap" concept.
|
kpeter@610
|
58 |
typedef UM UpperMap;
|
alpar@399
|
59 |
|
kpeter@610
|
60 |
/// \brief The type of supply map.
|
alpar@399
|
61 |
///
|
kpeter@610
|
62 |
/// The type of the map that stores the signed supply values of the
|
kpeter@610
|
63 |
/// nodes.
|
kpeter@610
|
64 |
/// It must conform to the \ref concepts::ReadMap "ReadMap" concept.
|
kpeter@610
|
65 |
typedef SM SupplyMap;
|
alpar@399
|
66 |
|
kpeter@641
|
67 |
/// \brief The type of the flow and supply values.
|
kpeter@641
|
68 |
typedef typename SupplyMap::Value Value;
|
alpar@399
|
69 |
|
kpeter@402
|
70 |
/// \brief The type of the map that stores the flow values.
|
alpar@399
|
71 |
///
|
kpeter@402
|
72 |
/// The type of the map that stores the flow values.
|
kpeter@610
|
73 |
/// It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap"
|
kpeter@610
|
74 |
/// concept.
|
kpeter@641
|
75 |
typedef typename Digraph::template ArcMap<Value> FlowMap;
|
alpar@399
|
76 |
|
alpar@399
|
77 |
/// \brief Instantiates a FlowMap.
|
alpar@399
|
78 |
///
|
alpar@399
|
79 |
/// This function instantiates a \ref FlowMap.
|
kpeter@610
|
80 |
/// \param digraph The digraph for which we would like to define
|
alpar@399
|
81 |
/// the flow map.
|
alpar@399
|
82 |
static FlowMap* createFlowMap(const Digraph& digraph) {
|
alpar@399
|
83 |
return new FlowMap(digraph);
|
alpar@399
|
84 |
}
|
alpar@399
|
85 |
|
kpeter@402
|
86 |
/// \brief The elevator type used by the algorithm.
|
alpar@399
|
87 |
///
|
kpeter@402
|
88 |
/// The elevator type used by the algorithm.
|
alpar@399
|
89 |
///
|
alpar@399
|
90 |
/// \sa Elevator
|
alpar@399
|
91 |
/// \sa LinkedElevator
|
alpar@399
|
92 |
typedef lemon::Elevator<Digraph, typename Digraph::Node> Elevator;
|
alpar@399
|
93 |
|
alpar@399
|
94 |
/// \brief Instantiates an Elevator.
|
alpar@399
|
95 |
///
|
kpeter@402
|
96 |
/// This function instantiates an \ref Elevator.
|
kpeter@610
|
97 |
/// \param digraph The digraph for which we would like to define
|
alpar@399
|
98 |
/// the elevator.
|
alpar@399
|
99 |
/// \param max_level The maximum level of the elevator.
|
alpar@399
|
100 |
static Elevator* createElevator(const Digraph& digraph, int max_level) {
|
alpar@399
|
101 |
return new Elevator(digraph, max_level);
|
alpar@399
|
102 |
}
|
alpar@399
|
103 |
|
alpar@399
|
104 |
/// \brief The tolerance used by the algorithm
|
alpar@399
|
105 |
///
|
alpar@399
|
106 |
/// The tolerance used by the algorithm to handle inexact computation.
|
kpeter@641
|
107 |
typedef lemon::Tolerance<Value> Tolerance;
|
alpar@399
|
108 |
|
alpar@399
|
109 |
};
|
alpar@399
|
110 |
|
kpeter@402
|
111 |
/**
|
kpeter@402
|
112 |
\brief Push-relabel algorithm for the network circulation problem.
|
alpar@399
|
113 |
|
alpar@399
|
114 |
\ingroup max_flow
|
kpeter@610
|
115 |
This class implements a push-relabel algorithm for the \e network
|
kpeter@610
|
116 |
\e circulation problem.
|
kpeter@402
|
117 |
It is to find a feasible circulation when lower and upper bounds
|
kpeter@610
|
118 |
are given for the flow values on the arcs and lower bounds are
|
kpeter@610
|
119 |
given for the difference between the outgoing and incoming flow
|
kpeter@610
|
120 |
at the nodes.
|
kpeter@402
|
121 |
|
alpar@399
|
122 |
The exact formulation of this problem is the following.
|
kpeter@622
|
123 |
Let \f$G=(V,A)\f$ be a digraph, \f$lower: A\rightarrow\mathbf{R}\f$
|
kpeter@622
|
124 |
\f$upper: A\rightarrow\mathbf{R}\cup\{\infty\}\f$ denote the lower and
|
kpeter@622
|
125 |
upper bounds on the arcs, for which \f$lower(uv) \leq upper(uv)\f$
|
kpeter@610
|
126 |
holds for all \f$uv\in A\f$, and \f$sup: V\rightarrow\mathbf{R}\f$
|
kpeter@610
|
127 |
denotes the signed supply values of the nodes.
|
kpeter@610
|
128 |
If \f$sup(u)>0\f$, then \f$u\f$ is a supply node with \f$sup(u)\f$
|
kpeter@610
|
129 |
supply, if \f$sup(u)<0\f$, then \f$u\f$ is a demand node with
|
kpeter@610
|
130 |
\f$-sup(u)\f$ demand.
|
kpeter@622
|
131 |
A feasible circulation is an \f$f: A\rightarrow\mathbf{R}\f$
|
kpeter@610
|
132 |
solution of the following problem.
|
kpeter@402
|
133 |
|
kpeter@610
|
134 |
\f[ \sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu)
|
kpeter@610
|
135 |
\geq sup(u) \quad \forall u\in V, \f]
|
kpeter@610
|
136 |
\f[ lower(uv) \leq f(uv) \leq upper(uv) \quad \forall uv\in A. \f]
|
kpeter@610
|
137 |
|
kpeter@610
|
138 |
The sum of the supply values, i.e. \f$\sum_{u\in V} sup(u)\f$ must be
|
kpeter@610
|
139 |
zero or negative in order to have a feasible solution (since the sum
|
kpeter@610
|
140 |
of the expressions on the left-hand side of the inequalities is zero).
|
kpeter@610
|
141 |
It means that the total demand must be greater or equal to the total
|
kpeter@610
|
142 |
supply and all the supplies have to be carried out from the supply nodes,
|
kpeter@610
|
143 |
but there could be demands that are not satisfied.
|
kpeter@610
|
144 |
If \f$\sum_{u\in V} sup(u)\f$ is zero, then all the supply/demand
|
kpeter@610
|
145 |
constraints have to be satisfied with equality, i.e. all demands
|
kpeter@610
|
146 |
have to be satisfied and all supplies have to be used.
|
kpeter@610
|
147 |
|
kpeter@610
|
148 |
If you need the opposite inequalities in the supply/demand constraints
|
kpeter@610
|
149 |
(i.e. the total demand is less than the total supply and all the demands
|
kpeter@610
|
150 |
have to be satisfied while there could be supplies that are not used),
|
kpeter@610
|
151 |
then you could easily transform the problem to the above form by reversing
|
kpeter@610
|
152 |
the direction of the arcs and taking the negative of the supply values
|
kpeter@610
|
153 |
(e.g. using \ref ReverseDigraph and \ref NegMap adaptors).
|
kpeter@610
|
154 |
|
kpeter@622
|
155 |
This algorithm either calculates a feasible circulation, or provides
|
kpeter@622
|
156 |
a \ref barrier() "barrier", which prooves that a feasible soultion
|
kpeter@622
|
157 |
cannot exist.
|
kpeter@622
|
158 |
|
kpeter@610
|
159 |
Note that this algorithm also provides a feasible solution for the
|
kpeter@610
|
160 |
\ref min_cost_flow "minimum cost flow problem".
|
kpeter@402
|
161 |
|
kpeter@503
|
162 |
\tparam GR The type of the digraph the algorithm runs on.
|
kpeter@610
|
163 |
\tparam LM The type of the lower bound map. The default
|
kpeter@503
|
164 |
map type is \ref concepts::Digraph::ArcMap "GR::ArcMap<int>".
|
kpeter@610
|
165 |
\tparam UM The type of the upper bound (capacity) map.
|
kpeter@610
|
166 |
The default map type is \c LM.
|
kpeter@610
|
167 |
\tparam SM The type of the supply map. The default map type is
|
kpeter@503
|
168 |
\ref concepts::Digraph::NodeMap "GR::NodeMap<UM::Value>".
|
alpar@399
|
169 |
*/
|
kpeter@402
|
170 |
#ifdef DOXYGEN
|
kpeter@503
|
171 |
template< typename GR,
|
kpeter@503
|
172 |
typename LM,
|
kpeter@503
|
173 |
typename UM,
|
kpeter@610
|
174 |
typename SM,
|
kpeter@503
|
175 |
typename TR >
|
kpeter@402
|
176 |
#else
|
kpeter@503
|
177 |
template< typename GR,
|
kpeter@503
|
178 |
typename LM = typename GR::template ArcMap<int>,
|
kpeter@503
|
179 |
typename UM = LM,
|
kpeter@610
|
180 |
typename SM = typename GR::template NodeMap<typename UM::Value>,
|
kpeter@610
|
181 |
typename TR = CirculationDefaultTraits<GR, LM, UM, SM> >
|
kpeter@402
|
182 |
#endif
|
alpar@399
|
183 |
class Circulation {
|
kpeter@402
|
184 |
public:
|
alpar@399
|
185 |
|
kpeter@402
|
186 |
///The \ref CirculationDefaultTraits "traits class" of the algorithm.
|
kpeter@503
|
187 |
typedef TR Traits;
|
kpeter@402
|
188 |
///The type of the digraph the algorithm runs on.
|
alpar@399
|
189 |
typedef typename Traits::Digraph Digraph;
|
kpeter@641
|
190 |
///The type of the flow and supply values.
|
kpeter@641
|
191 |
typedef typename Traits::Value Value;
|
alpar@399
|
192 |
|
kpeter@610
|
193 |
///The type of the lower bound map.
|
kpeter@610
|
194 |
typedef typename Traits::LowerMap LowerMap;
|
kpeter@610
|
195 |
///The type of the upper bound (capacity) map.
|
kpeter@610
|
196 |
typedef typename Traits::UpperMap UpperMap;
|
kpeter@610
|
197 |
///The type of the supply map.
|
kpeter@610
|
198 |
typedef typename Traits::SupplyMap SupplyMap;
|
kpeter@402
|
199 |
///The type of the flow map.
|
alpar@399
|
200 |
typedef typename Traits::FlowMap FlowMap;
|
kpeter@402
|
201 |
|
kpeter@402
|
202 |
///The type of the elevator.
|
alpar@399
|
203 |
typedef typename Traits::Elevator Elevator;
|
kpeter@402
|
204 |
///The type of the tolerance.
|
alpar@399
|
205 |
typedef typename Traits::Tolerance Tolerance;
|
alpar@399
|
206 |
|
kpeter@402
|
207 |
private:
|
kpeter@402
|
208 |
|
kpeter@402
|
209 |
TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
|
alpar@399
|
210 |
|
alpar@399
|
211 |
const Digraph &_g;
|
alpar@399
|
212 |
int _node_num;
|
alpar@399
|
213 |
|
kpeter@610
|
214 |
const LowerMap *_lo;
|
kpeter@610
|
215 |
const UpperMap *_up;
|
kpeter@610
|
216 |
const SupplyMap *_supply;
|
alpar@399
|
217 |
|
alpar@399
|
218 |
FlowMap *_flow;
|
alpar@399
|
219 |
bool _local_flow;
|
alpar@399
|
220 |
|
alpar@399
|
221 |
Elevator* _level;
|
alpar@399
|
222 |
bool _local_level;
|
alpar@399
|
223 |
|
kpeter@641
|
224 |
typedef typename Digraph::template NodeMap<Value> ExcessMap;
|
alpar@399
|
225 |
ExcessMap* _excess;
|
alpar@399
|
226 |
|
alpar@399
|
227 |
Tolerance _tol;
|
alpar@399
|
228 |
int _el;
|
alpar@399
|
229 |
|
alpar@399
|
230 |
public:
|
alpar@399
|
231 |
|
alpar@399
|
232 |
typedef Circulation Create;
|
alpar@399
|
233 |
|
kpeter@402
|
234 |
///\name Named Template Parameters
|
alpar@399
|
235 |
|
alpar@399
|
236 |
///@{
|
alpar@399
|
237 |
|
kpeter@559
|
238 |
template <typename T>
|
alpar@401
|
239 |
struct SetFlowMapTraits : public Traits {
|
kpeter@559
|
240 |
typedef T FlowMap;
|
alpar@399
|
241 |
static FlowMap *createFlowMap(const Digraph&) {
|
alpar@399
|
242 |
LEMON_ASSERT(false, "FlowMap is not initialized");
|
alpar@399
|
243 |
return 0; // ignore warnings
|
alpar@399
|
244 |
}
|
alpar@399
|
245 |
};
|
alpar@399
|
246 |
|
alpar@399
|
247 |
/// \brief \ref named-templ-param "Named parameter" for setting
|
alpar@399
|
248 |
/// FlowMap type
|
alpar@399
|
249 |
///
|
alpar@399
|
250 |
/// \ref named-templ-param "Named parameter" for setting FlowMap
|
kpeter@402
|
251 |
/// type.
|
kpeter@559
|
252 |
template <typename T>
|
alpar@401
|
253 |
struct SetFlowMap
|
kpeter@610
|
254 |
: public Circulation<Digraph, LowerMap, UpperMap, SupplyMap,
|
kpeter@559
|
255 |
SetFlowMapTraits<T> > {
|
kpeter@610
|
256 |
typedef Circulation<Digraph, LowerMap, UpperMap, SupplyMap,
|
kpeter@559
|
257 |
SetFlowMapTraits<T> > Create;
|
alpar@399
|
258 |
};
|
alpar@399
|
259 |
|
kpeter@559
|
260 |
template <typename T>
|
alpar@401
|
261 |
struct SetElevatorTraits : public Traits {
|
kpeter@559
|
262 |
typedef T Elevator;
|
alpar@399
|
263 |
static Elevator *createElevator(const Digraph&, int) {
|
alpar@399
|
264 |
LEMON_ASSERT(false, "Elevator is not initialized");
|
alpar@399
|
265 |
return 0; // ignore warnings
|
alpar@399
|
266 |
}
|
alpar@399
|
267 |
};
|
alpar@399
|
268 |
|
alpar@399
|
269 |
/// \brief \ref named-templ-param "Named parameter" for setting
|
alpar@399
|
270 |
/// Elevator type
|
alpar@399
|
271 |
///
|
alpar@399
|
272 |
/// \ref named-templ-param "Named parameter" for setting Elevator
|
kpeter@402
|
273 |
/// type. If this named parameter is used, then an external
|
kpeter@402
|
274 |
/// elevator object must be passed to the algorithm using the
|
kpeter@402
|
275 |
/// \ref elevator(Elevator&) "elevator()" function before calling
|
kpeter@402
|
276 |
/// \ref run() or \ref init().
|
kpeter@402
|
277 |
/// \sa SetStandardElevator
|
kpeter@559
|
278 |
template <typename T>
|
alpar@401
|
279 |
struct SetElevator
|
kpeter@610
|
280 |
: public Circulation<Digraph, LowerMap, UpperMap, SupplyMap,
|
kpeter@559
|
281 |
SetElevatorTraits<T> > {
|
kpeter@610
|
282 |
typedef Circulation<Digraph, LowerMap, UpperMap, SupplyMap,
|
kpeter@559
|
283 |
SetElevatorTraits<T> > Create;
|
alpar@399
|
284 |
};
|
alpar@399
|
285 |
|
kpeter@559
|
286 |
template <typename T>
|
alpar@401
|
287 |
struct SetStandardElevatorTraits : public Traits {
|
kpeter@559
|
288 |
typedef T Elevator;
|
alpar@399
|
289 |
static Elevator *createElevator(const Digraph& digraph, int max_level) {
|
alpar@399
|
290 |
return new Elevator(digraph, max_level);
|
alpar@399
|
291 |
}
|
alpar@399
|
292 |
};
|
alpar@399
|
293 |
|
alpar@399
|
294 |
/// \brief \ref named-templ-param "Named parameter" for setting
|
kpeter@402
|
295 |
/// Elevator type with automatic allocation
|
alpar@399
|
296 |
///
|
alpar@399
|
297 |
/// \ref named-templ-param "Named parameter" for setting Elevator
|
kpeter@402
|
298 |
/// type with automatic allocation.
|
kpeter@402
|
299 |
/// The Elevator should have standard constructor interface to be
|
kpeter@402
|
300 |
/// able to automatically created by the algorithm (i.e. the
|
kpeter@402
|
301 |
/// digraph and the maximum level should be passed to it).
|
kpeter@402
|
302 |
/// However an external elevator object could also be passed to the
|
kpeter@402
|
303 |
/// algorithm with the \ref elevator(Elevator&) "elevator()" function
|
kpeter@402
|
304 |
/// before calling \ref run() or \ref init().
|
kpeter@402
|
305 |
/// \sa SetElevator
|
kpeter@559
|
306 |
template <typename T>
|
alpar@401
|
307 |
struct SetStandardElevator
|
kpeter@610
|
308 |
: public Circulation<Digraph, LowerMap, UpperMap, SupplyMap,
|
kpeter@559
|
309 |
SetStandardElevatorTraits<T> > {
|
kpeter@610
|
310 |
typedef Circulation<Digraph, LowerMap, UpperMap, SupplyMap,
|
kpeter@559
|
311 |
SetStandardElevatorTraits<T> > Create;
|
alpar@399
|
312 |
};
|
alpar@399
|
313 |
|
alpar@399
|
314 |
/// @}
|
alpar@399
|
315 |
|
alpar@399
|
316 |
protected:
|
alpar@399
|
317 |
|
alpar@399
|
318 |
Circulation() {}
|
alpar@399
|
319 |
|
alpar@399
|
320 |
public:
|
alpar@399
|
321 |
|
kpeter@610
|
322 |
/// Constructor.
|
alpar@399
|
323 |
|
alpar@399
|
324 |
/// The constructor of the class.
|
kpeter@610
|
325 |
///
|
kpeter@610
|
326 |
/// \param graph The digraph the algorithm runs on.
|
kpeter@610
|
327 |
/// \param lower The lower bounds for the flow values on the arcs.
|
kpeter@610
|
328 |
/// \param upper The upper bounds (capacities) for the flow values
|
kpeter@610
|
329 |
/// on the arcs.
|
kpeter@610
|
330 |
/// \param supply The signed supply values of the nodes.
|
kpeter@610
|
331 |
Circulation(const Digraph &graph, const LowerMap &lower,
|
kpeter@610
|
332 |
const UpperMap &upper, const SupplyMap &supply)
|
kpeter@610
|
333 |
: _g(graph), _lo(&lower), _up(&upper), _supply(&supply),
|
kpeter@610
|
334 |
_flow(NULL), _local_flow(false), _level(NULL), _local_level(false),
|
kpeter@610
|
335 |
_excess(NULL) {}
|
alpar@399
|
336 |
|
kpeter@402
|
337 |
/// Destructor.
|
alpar@399
|
338 |
~Circulation() {
|
alpar@399
|
339 |
destroyStructures();
|
alpar@399
|
340 |
}
|
alpar@399
|
341 |
|
kpeter@402
|
342 |
|
alpar@399
|
343 |
private:
|
alpar@399
|
344 |
|
kpeter@622
|
345 |
bool checkBoundMaps() {
|
kpeter@622
|
346 |
for (ArcIt e(_g);e!=INVALID;++e) {
|
kpeter@622
|
347 |
if (_tol.less((*_up)[e], (*_lo)[e])) return false;
|
kpeter@622
|
348 |
}
|
kpeter@622
|
349 |
return true;
|
kpeter@622
|
350 |
}
|
kpeter@622
|
351 |
|
alpar@399
|
352 |
void createStructures() {
|
alpar@399
|
353 |
_node_num = _el = countNodes(_g);
|
alpar@399
|
354 |
|
alpar@399
|
355 |
if (!_flow) {
|
alpar@399
|
356 |
_flow = Traits::createFlowMap(_g);
|
alpar@399
|
357 |
_local_flow = true;
|
alpar@399
|
358 |
}
|
alpar@399
|
359 |
if (!_level) {
|
alpar@399
|
360 |
_level = Traits::createElevator(_g, _node_num);
|
alpar@399
|
361 |
_local_level = true;
|
alpar@399
|
362 |
}
|
alpar@399
|
363 |
if (!_excess) {
|
alpar@399
|
364 |
_excess = new ExcessMap(_g);
|
alpar@399
|
365 |
}
|
alpar@399
|
366 |
}
|
alpar@399
|
367 |
|
alpar@399
|
368 |
void destroyStructures() {
|
alpar@399
|
369 |
if (_local_flow) {
|
alpar@399
|
370 |
delete _flow;
|
alpar@399
|
371 |
}
|
alpar@399
|
372 |
if (_local_level) {
|
alpar@399
|
373 |
delete _level;
|
alpar@399
|
374 |
}
|
alpar@399
|
375 |
if (_excess) {
|
alpar@399
|
376 |
delete _excess;
|
alpar@399
|
377 |
}
|
alpar@399
|
378 |
}
|
alpar@399
|
379 |
|
alpar@399
|
380 |
public:
|
alpar@399
|
381 |
|
kpeter@610
|
382 |
/// Sets the lower bound map.
|
alpar@399
|
383 |
|
kpeter@610
|
384 |
/// Sets the lower bound map.
|
kpeter@402
|
385 |
/// \return <tt>(*this)</tt>
|
kpeter@610
|
386 |
Circulation& lowerMap(const LowerMap& map) {
|
alpar@399
|
387 |
_lo = ↦
|
alpar@399
|
388 |
return *this;
|
alpar@399
|
389 |
}
|
alpar@399
|
390 |
|
kpeter@610
|
391 |
/// Sets the upper bound (capacity) map.
|
alpar@399
|
392 |
|
kpeter@610
|
393 |
/// Sets the upper bound (capacity) map.
|
kpeter@402
|
394 |
/// \return <tt>(*this)</tt>
|
kpeter@622
|
395 |
Circulation& upperMap(const UpperMap& map) {
|
alpar@399
|
396 |
_up = ↦
|
alpar@399
|
397 |
return *this;
|
alpar@399
|
398 |
}
|
alpar@399
|
399 |
|
kpeter@610
|
400 |
/// Sets the supply map.
|
alpar@399
|
401 |
|
kpeter@610
|
402 |
/// Sets the supply map.
|
kpeter@402
|
403 |
/// \return <tt>(*this)</tt>
|
kpeter@610
|
404 |
Circulation& supplyMap(const SupplyMap& map) {
|
kpeter@610
|
405 |
_supply = ↦
|
alpar@399
|
406 |
return *this;
|
alpar@399
|
407 |
}
|
alpar@399
|
408 |
|
kpeter@402
|
409 |
/// \brief Sets the flow map.
|
kpeter@402
|
410 |
///
|
alpar@399
|
411 |
/// Sets the flow map.
|
kpeter@402
|
412 |
/// If you don't use this function before calling \ref run() or
|
kpeter@402
|
413 |
/// \ref init(), an instance will be allocated automatically.
|
kpeter@402
|
414 |
/// The destructor deallocates this automatically allocated map,
|
kpeter@402
|
415 |
/// of course.
|
kpeter@402
|
416 |
/// \return <tt>(*this)</tt>
|
alpar@399
|
417 |
Circulation& flowMap(FlowMap& map) {
|
alpar@399
|
418 |
if (_local_flow) {
|
alpar@399
|
419 |
delete _flow;
|
alpar@399
|
420 |
_local_flow = false;
|
alpar@399
|
421 |
}
|
alpar@399
|
422 |
_flow = ↦
|
alpar@399
|
423 |
return *this;
|
alpar@399
|
424 |
}
|
alpar@399
|
425 |
|
kpeter@402
|
426 |
/// \brief Sets the elevator used by algorithm.
|
alpar@399
|
427 |
///
|
kpeter@402
|
428 |
/// Sets the elevator used by algorithm.
|
kpeter@402
|
429 |
/// If you don't use this function before calling \ref run() or
|
kpeter@402
|
430 |
/// \ref init(), an instance will be allocated automatically.
|
kpeter@402
|
431 |
/// The destructor deallocates this automatically allocated elevator,
|
kpeter@402
|
432 |
/// of course.
|
kpeter@402
|
433 |
/// \return <tt>(*this)</tt>
|
alpar@399
|
434 |
Circulation& elevator(Elevator& elevator) {
|
alpar@399
|
435 |
if (_local_level) {
|
alpar@399
|
436 |
delete _level;
|
alpar@399
|
437 |
_local_level = false;
|
alpar@399
|
438 |
}
|
alpar@399
|
439 |
_level = &elevator;
|
alpar@399
|
440 |
return *this;
|
alpar@399
|
441 |
}
|
alpar@399
|
442 |
|
kpeter@402
|
443 |
/// \brief Returns a const reference to the elevator.
|
alpar@399
|
444 |
///
|
kpeter@402
|
445 |
/// Returns a const reference to the elevator.
|
kpeter@402
|
446 |
///
|
kpeter@402
|
447 |
/// \pre Either \ref run() or \ref init() must be called before
|
kpeter@402
|
448 |
/// using this function.
|
kpeter@420
|
449 |
const Elevator& elevator() const {
|
alpar@399
|
450 |
return *_level;
|
alpar@399
|
451 |
}
|
alpar@399
|
452 |
|
kpeter@689
|
453 |
/// \brief Sets the tolerance used by the algorithm.
|
kpeter@402
|
454 |
///
|
kpeter@689
|
455 |
/// Sets the tolerance object used by the algorithm.
|
kpeter@689
|
456 |
/// \return <tt>(*this)</tt>
|
kpeter@688
|
457 |
Circulation& tolerance(const Tolerance& tolerance) {
|
alpar@399
|
458 |
_tol = tolerance;
|
alpar@399
|
459 |
return *this;
|
alpar@399
|
460 |
}
|
alpar@399
|
461 |
|
kpeter@402
|
462 |
/// \brief Returns a const reference to the tolerance.
|
alpar@399
|
463 |
///
|
kpeter@689
|
464 |
/// Returns a const reference to the tolerance object used by
|
kpeter@689
|
465 |
/// the algorithm.
|
alpar@399
|
466 |
const Tolerance& tolerance() const {
|
kpeter@688
|
467 |
return _tol;
|
alpar@399
|
468 |
}
|
alpar@399
|
469 |
|
kpeter@402
|
470 |
/// \name Execution Control
|
kpeter@402
|
471 |
/// The simplest way to execute the algorithm is to call \ref run().\n
|
kpeter@402
|
472 |
/// If you need more control on the initial solution or the execution,
|
kpeter@402
|
473 |
/// first you have to call one of the \ref init() functions, then
|
kpeter@402
|
474 |
/// the \ref start() function.
|
alpar@399
|
475 |
|
alpar@399
|
476 |
///@{
|
alpar@399
|
477 |
|
alpar@399
|
478 |
/// Initializes the internal data structures.
|
alpar@399
|
479 |
|
kpeter@402
|
480 |
/// Initializes the internal data structures and sets all flow values
|
kpeter@402
|
481 |
/// to the lower bound.
|
alpar@399
|
482 |
void init()
|
alpar@399
|
483 |
{
|
kpeter@622
|
484 |
LEMON_DEBUG(checkBoundMaps(),
|
kpeter@622
|
485 |
"Upper bounds must be greater or equal to the lower bounds");
|
kpeter@622
|
486 |
|
alpar@399
|
487 |
createStructures();
|
alpar@399
|
488 |
|
alpar@399
|
489 |
for(NodeIt n(_g);n!=INVALID;++n) {
|
alpar@611
|
490 |
(*_excess)[n] = (*_supply)[n];
|
alpar@399
|
491 |
}
|
alpar@399
|
492 |
|
alpar@399
|
493 |
for (ArcIt e(_g);e!=INVALID;++e) {
|
alpar@399
|
494 |
_flow->set(e, (*_lo)[e]);
|
kpeter@581
|
495 |
(*_excess)[_g.target(e)] += (*_flow)[e];
|
kpeter@581
|
496 |
(*_excess)[_g.source(e)] -= (*_flow)[e];
|
alpar@399
|
497 |
}
|
alpar@399
|
498 |
|
alpar@399
|
499 |
// global relabeling tested, but in general case it provides
|
alpar@399
|
500 |
// worse performance for random digraphs
|
alpar@399
|
501 |
_level->initStart();
|
alpar@399
|
502 |
for(NodeIt n(_g);n!=INVALID;++n)
|
alpar@399
|
503 |
_level->initAddItem(n);
|
alpar@399
|
504 |
_level->initFinish();
|
alpar@399
|
505 |
for(NodeIt n(_g);n!=INVALID;++n)
|
alpar@399
|
506 |
if(_tol.positive((*_excess)[n]))
|
alpar@399
|
507 |
_level->activate(n);
|
alpar@399
|
508 |
}
|
alpar@399
|
509 |
|
kpeter@402
|
510 |
/// Initializes the internal data structures using a greedy approach.
|
alpar@399
|
511 |
|
kpeter@402
|
512 |
/// Initializes the internal data structures using a greedy approach
|
kpeter@402
|
513 |
/// to construct the initial solution.
|
alpar@399
|
514 |
void greedyInit()
|
alpar@399
|
515 |
{
|
kpeter@622
|
516 |
LEMON_DEBUG(checkBoundMaps(),
|
kpeter@622
|
517 |
"Upper bounds must be greater or equal to the lower bounds");
|
kpeter@622
|
518 |
|
alpar@399
|
519 |
createStructures();
|
alpar@399
|
520 |
|
alpar@399
|
521 |
for(NodeIt n(_g);n!=INVALID;++n) {
|
alpar@611
|
522 |
(*_excess)[n] = (*_supply)[n];
|
alpar@399
|
523 |
}
|
alpar@399
|
524 |
|
alpar@399
|
525 |
for (ArcIt e(_g);e!=INVALID;++e) {
|
kpeter@622
|
526 |
if (!_tol.less(-(*_excess)[_g.target(e)], (*_up)[e])) {
|
alpar@399
|
527 |
_flow->set(e, (*_up)[e]);
|
kpeter@581
|
528 |
(*_excess)[_g.target(e)] += (*_up)[e];
|
kpeter@581
|
529 |
(*_excess)[_g.source(e)] -= (*_up)[e];
|
kpeter@622
|
530 |
} else if (_tol.less(-(*_excess)[_g.target(e)], (*_lo)[e])) {
|
alpar@399
|
531 |
_flow->set(e, (*_lo)[e]);
|
kpeter@581
|
532 |
(*_excess)[_g.target(e)] += (*_lo)[e];
|
kpeter@581
|
533 |
(*_excess)[_g.source(e)] -= (*_lo)[e];
|
alpar@399
|
534 |
} else {
|
kpeter@641
|
535 |
Value fc = -(*_excess)[_g.target(e)];
|
alpar@399
|
536 |
_flow->set(e, fc);
|
kpeter@581
|
537 |
(*_excess)[_g.target(e)] = 0;
|
kpeter@581
|
538 |
(*_excess)[_g.source(e)] -= fc;
|
alpar@399
|
539 |
}
|
alpar@399
|
540 |
}
|
alpar@399
|
541 |
|
alpar@399
|
542 |
_level->initStart();
|
alpar@399
|
543 |
for(NodeIt n(_g);n!=INVALID;++n)
|
alpar@399
|
544 |
_level->initAddItem(n);
|
alpar@399
|
545 |
_level->initFinish();
|
alpar@399
|
546 |
for(NodeIt n(_g);n!=INVALID;++n)
|
alpar@399
|
547 |
if(_tol.positive((*_excess)[n]))
|
alpar@399
|
548 |
_level->activate(n);
|
alpar@399
|
549 |
}
|
alpar@399
|
550 |
|
kpeter@402
|
551 |
///Executes the algorithm
|
alpar@399
|
552 |
|
kpeter@402
|
553 |
///This function executes the algorithm.
|
kpeter@402
|
554 |
///
|
kpeter@402
|
555 |
///\return \c true if a feasible circulation is found.
|
alpar@399
|
556 |
///
|
alpar@399
|
557 |
///\sa barrier()
|
kpeter@402
|
558 |
///\sa barrierMap()
|
alpar@399
|
559 |
bool start()
|
alpar@399
|
560 |
{
|
alpar@399
|
561 |
|
alpar@399
|
562 |
Node act;
|
alpar@399
|
563 |
Node bact=INVALID;
|
alpar@399
|
564 |
Node last_activated=INVALID;
|
alpar@399
|
565 |
while((act=_level->highestActive())!=INVALID) {
|
alpar@399
|
566 |
int actlevel=(*_level)[act];
|
alpar@399
|
567 |
int mlevel=_node_num;
|
kpeter@641
|
568 |
Value exc=(*_excess)[act];
|
alpar@399
|
569 |
|
alpar@399
|
570 |
for(OutArcIt e(_g,act);e!=INVALID; ++e) {
|
alpar@399
|
571 |
Node v = _g.target(e);
|
kpeter@641
|
572 |
Value fc=(*_up)[e]-(*_flow)[e];
|
alpar@399
|
573 |
if(!_tol.positive(fc)) continue;
|
alpar@399
|
574 |
if((*_level)[v]<actlevel) {
|
alpar@399
|
575 |
if(!_tol.less(fc, exc)) {
|
alpar@399
|
576 |
_flow->set(e, (*_flow)[e] + exc);
|
kpeter@581
|
577 |
(*_excess)[v] += exc;
|
alpar@399
|
578 |
if(!_level->active(v) && _tol.positive((*_excess)[v]))
|
alpar@399
|
579 |
_level->activate(v);
|
kpeter@581
|
580 |
(*_excess)[act] = 0;
|
alpar@399
|
581 |
_level->deactivate(act);
|
alpar@399
|
582 |
goto next_l;
|
alpar@399
|
583 |
}
|
alpar@399
|
584 |
else {
|
alpar@399
|
585 |
_flow->set(e, (*_up)[e]);
|
kpeter@581
|
586 |
(*_excess)[v] += fc;
|
alpar@399
|
587 |
if(!_level->active(v) && _tol.positive((*_excess)[v]))
|
alpar@399
|
588 |
_level->activate(v);
|
alpar@399
|
589 |
exc-=fc;
|
alpar@399
|
590 |
}
|
alpar@399
|
591 |
}
|
alpar@399
|
592 |
else if((*_level)[v]<mlevel) mlevel=(*_level)[v];
|
alpar@399
|
593 |
}
|
alpar@399
|
594 |
for(InArcIt e(_g,act);e!=INVALID; ++e) {
|
alpar@399
|
595 |
Node v = _g.source(e);
|
kpeter@641
|
596 |
Value fc=(*_flow)[e]-(*_lo)[e];
|
alpar@399
|
597 |
if(!_tol.positive(fc)) continue;
|
alpar@399
|
598 |
if((*_level)[v]<actlevel) {
|
alpar@399
|
599 |
if(!_tol.less(fc, exc)) {
|
alpar@399
|
600 |
_flow->set(e, (*_flow)[e] - exc);
|
kpeter@581
|
601 |
(*_excess)[v] += exc;
|
alpar@399
|
602 |
if(!_level->active(v) && _tol.positive((*_excess)[v]))
|
alpar@399
|
603 |
_level->activate(v);
|
kpeter@581
|
604 |
(*_excess)[act] = 0;
|
alpar@399
|
605 |
_level->deactivate(act);
|
alpar@399
|
606 |
goto next_l;
|
alpar@399
|
607 |
}
|
alpar@399
|
608 |
else {
|
alpar@399
|
609 |
_flow->set(e, (*_lo)[e]);
|
kpeter@581
|
610 |
(*_excess)[v] += fc;
|
alpar@399
|
611 |
if(!_level->active(v) && _tol.positive((*_excess)[v]))
|
alpar@399
|
612 |
_level->activate(v);
|
alpar@399
|
613 |
exc-=fc;
|
alpar@399
|
614 |
}
|
alpar@399
|
615 |
}
|
alpar@399
|
616 |
else if((*_level)[v]<mlevel) mlevel=(*_level)[v];
|
alpar@399
|
617 |
}
|
alpar@399
|
618 |
|
kpeter@581
|
619 |
(*_excess)[act] = exc;
|
alpar@399
|
620 |
if(!_tol.positive(exc)) _level->deactivate(act);
|
alpar@399
|
621 |
else if(mlevel==_node_num) {
|
alpar@399
|
622 |
_level->liftHighestActiveToTop();
|
alpar@399
|
623 |
_el = _node_num;
|
alpar@399
|
624 |
return false;
|
alpar@399
|
625 |
}
|
alpar@399
|
626 |
else {
|
alpar@399
|
627 |
_level->liftHighestActive(mlevel+1);
|
alpar@399
|
628 |
if(_level->onLevel(actlevel)==0) {
|
alpar@399
|
629 |
_el = actlevel;
|
alpar@399
|
630 |
return false;
|
alpar@399
|
631 |
}
|
alpar@399
|
632 |
}
|
alpar@399
|
633 |
next_l:
|
alpar@399
|
634 |
;
|
alpar@399
|
635 |
}
|
alpar@399
|
636 |
return true;
|
alpar@399
|
637 |
}
|
alpar@399
|
638 |
|
kpeter@402
|
639 |
/// Runs the algorithm.
|
alpar@399
|
640 |
|
kpeter@402
|
641 |
/// This function runs the algorithm.
|
kpeter@402
|
642 |
///
|
kpeter@402
|
643 |
/// \return \c true if a feasible circulation is found.
|
kpeter@402
|
644 |
///
|
kpeter@402
|
645 |
/// \note Apart from the return value, c.run() is just a shortcut of
|
kpeter@402
|
646 |
/// the following code.
|
alpar@399
|
647 |
/// \code
|
kpeter@402
|
648 |
/// c.greedyInit();
|
kpeter@402
|
649 |
/// c.start();
|
alpar@399
|
650 |
/// \endcode
|
alpar@399
|
651 |
bool run() {
|
alpar@399
|
652 |
greedyInit();
|
alpar@399
|
653 |
return start();
|
alpar@399
|
654 |
}
|
alpar@399
|
655 |
|
alpar@399
|
656 |
/// @}
|
alpar@399
|
657 |
|
alpar@399
|
658 |
/// \name Query Functions
|
kpeter@402
|
659 |
/// The results of the circulation algorithm can be obtained using
|
kpeter@402
|
660 |
/// these functions.\n
|
kpeter@402
|
661 |
/// Either \ref run() or \ref start() should be called before
|
kpeter@402
|
662 |
/// using them.
|
alpar@399
|
663 |
|
alpar@399
|
664 |
///@{
|
alpar@399
|
665 |
|
kpeter@641
|
666 |
/// \brief Returns the flow value on the given arc.
|
kpeter@402
|
667 |
///
|
kpeter@641
|
668 |
/// Returns the flow value on the given arc.
|
kpeter@402
|
669 |
///
|
kpeter@402
|
670 |
/// \pre Either \ref run() or \ref init() must be called before
|
kpeter@402
|
671 |
/// using this function.
|
kpeter@641
|
672 |
Value flow(const Arc& arc) const {
|
kpeter@402
|
673 |
return (*_flow)[arc];
|
kpeter@402
|
674 |
}
|
kpeter@402
|
675 |
|
kpeter@402
|
676 |
/// \brief Returns a const reference to the flow map.
|
kpeter@402
|
677 |
///
|
kpeter@402
|
678 |
/// Returns a const reference to the arc map storing the found flow.
|
kpeter@402
|
679 |
///
|
kpeter@402
|
680 |
/// \pre Either \ref run() or \ref init() must be called before
|
kpeter@402
|
681 |
/// using this function.
|
kpeter@420
|
682 |
const FlowMap& flowMap() const {
|
kpeter@402
|
683 |
return *_flow;
|
kpeter@402
|
684 |
}
|
kpeter@402
|
685 |
|
alpar@399
|
686 |
/**
|
kpeter@402
|
687 |
\brief Returns \c true if the given node is in a barrier.
|
kpeter@402
|
688 |
|
alpar@399
|
689 |
Barrier is a set \e B of nodes for which
|
kpeter@402
|
690 |
|
kpeter@610
|
691 |
\f[ \sum_{uv\in A: u\in B} upper(uv) -
|
kpeter@610
|
692 |
\sum_{uv\in A: v\in B} lower(uv) < \sum_{v\in B} sup(v) \f]
|
kpeter@402
|
693 |
|
kpeter@402
|
694 |
holds. The existence of a set with this property prooves that a
|
kpeter@402
|
695 |
feasible circualtion cannot exist.
|
kpeter@402
|
696 |
|
kpeter@402
|
697 |
This function returns \c true if the given node is in the found
|
kpeter@402
|
698 |
barrier. If a feasible circulation is found, the function
|
kpeter@402
|
699 |
gives back \c false for every node.
|
kpeter@402
|
700 |
|
kpeter@402
|
701 |
\pre Either \ref run() or \ref init() must be called before
|
kpeter@402
|
702 |
using this function.
|
kpeter@402
|
703 |
|
kpeter@402
|
704 |
\sa barrierMap()
|
alpar@399
|
705 |
\sa checkBarrier()
|
alpar@399
|
706 |
*/
|
kpeter@420
|
707 |
bool barrier(const Node& node) const
|
kpeter@402
|
708 |
{
|
kpeter@402
|
709 |
return (*_level)[node] >= _el;
|
kpeter@402
|
710 |
}
|
kpeter@402
|
711 |
|
kpeter@402
|
712 |
/// \brief Gives back a barrier.
|
kpeter@402
|
713 |
///
|
kpeter@402
|
714 |
/// This function sets \c bar to the characteristic vector of the
|
kpeter@402
|
715 |
/// found barrier. \c bar should be a \ref concepts::WriteMap "writable"
|
kpeter@402
|
716 |
/// node map with \c bool (or convertible) value type.
|
kpeter@402
|
717 |
///
|
kpeter@402
|
718 |
/// If a feasible circulation is found, the function gives back an
|
kpeter@402
|
719 |
/// empty set, so \c bar[v] will be \c false for all nodes \c v.
|
kpeter@402
|
720 |
///
|
kpeter@402
|
721 |
/// \note This function calls \ref barrier() for each node,
|
kpeter@559
|
722 |
/// so it runs in O(n) time.
|
kpeter@402
|
723 |
///
|
kpeter@402
|
724 |
/// \pre Either \ref run() or \ref init() must be called before
|
kpeter@402
|
725 |
/// using this function.
|
kpeter@402
|
726 |
///
|
kpeter@402
|
727 |
/// \sa barrier()
|
kpeter@402
|
728 |
/// \sa checkBarrier()
|
kpeter@402
|
729 |
template<class BarrierMap>
|
kpeter@420
|
730 |
void barrierMap(BarrierMap &bar) const
|
alpar@399
|
731 |
{
|
alpar@399
|
732 |
for(NodeIt n(_g);n!=INVALID;++n)
|
alpar@399
|
733 |
bar.set(n, (*_level)[n] >= _el);
|
alpar@399
|
734 |
}
|
alpar@399
|
735 |
|
alpar@399
|
736 |
/// @}
|
alpar@399
|
737 |
|
alpar@399
|
738 |
/// \name Checker Functions
|
kpeter@402
|
739 |
/// The feasibility of the results can be checked using
|
kpeter@402
|
740 |
/// these functions.\n
|
kpeter@402
|
741 |
/// Either \ref run() or \ref start() should be called before
|
kpeter@402
|
742 |
/// using them.
|
alpar@399
|
743 |
|
alpar@399
|
744 |
///@{
|
alpar@399
|
745 |
|
kpeter@402
|
746 |
///Check if the found flow is a feasible circulation
|
kpeter@402
|
747 |
|
kpeter@402
|
748 |
///Check if the found flow is a feasible circulation,
|
kpeter@402
|
749 |
///
|
kpeter@420
|
750 |
bool checkFlow() const {
|
alpar@399
|
751 |
for(ArcIt e(_g);e!=INVALID;++e)
|
alpar@399
|
752 |
if((*_flow)[e]<(*_lo)[e]||(*_flow)[e]>(*_up)[e]) return false;
|
alpar@399
|
753 |
for(NodeIt n(_g);n!=INVALID;++n)
|
alpar@399
|
754 |
{
|
kpeter@641
|
755 |
Value dif=-(*_supply)[n];
|
alpar@399
|
756 |
for(InArcIt e(_g,n);e!=INVALID;++e) dif-=(*_flow)[e];
|
alpar@399
|
757 |
for(OutArcIt e(_g,n);e!=INVALID;++e) dif+=(*_flow)[e];
|
alpar@399
|
758 |
if(_tol.negative(dif)) return false;
|
alpar@399
|
759 |
}
|
alpar@399
|
760 |
return true;
|
alpar@399
|
761 |
}
|
alpar@399
|
762 |
|
alpar@399
|
763 |
///Check whether or not the last execution provides a barrier
|
alpar@399
|
764 |
|
kpeter@402
|
765 |
///Check whether or not the last execution provides a barrier.
|
alpar@399
|
766 |
///\sa barrier()
|
kpeter@402
|
767 |
///\sa barrierMap()
|
kpeter@420
|
768 |
bool checkBarrier() const
|
alpar@399
|
769 |
{
|
kpeter@641
|
770 |
Value delta=0;
|
kpeter@641
|
771 |
Value inf_cap = std::numeric_limits<Value>::has_infinity ?
|
kpeter@641
|
772 |
std::numeric_limits<Value>::infinity() :
|
kpeter@641
|
773 |
std::numeric_limits<Value>::max();
|
alpar@399
|
774 |
for(NodeIt n(_g);n!=INVALID;++n)
|
alpar@399
|
775 |
if(barrier(n))
|
kpeter@610
|
776 |
delta-=(*_supply)[n];
|
alpar@399
|
777 |
for(ArcIt e(_g);e!=INVALID;++e)
|
alpar@399
|
778 |
{
|
alpar@399
|
779 |
Node s=_g.source(e);
|
alpar@399
|
780 |
Node t=_g.target(e);
|
kpeter@622
|
781 |
if(barrier(s)&&!barrier(t)) {
|
kpeter@622
|
782 |
if (_tol.less(inf_cap - (*_up)[e], delta)) return false;
|
kpeter@622
|
783 |
delta+=(*_up)[e];
|
kpeter@622
|
784 |
}
|
alpar@399
|
785 |
else if(barrier(t)&&!barrier(s)) delta-=(*_lo)[e];
|
alpar@399
|
786 |
}
|
alpar@399
|
787 |
return _tol.negative(delta);
|
alpar@399
|
788 |
}
|
alpar@399
|
789 |
|
alpar@399
|
790 |
/// @}
|
alpar@399
|
791 |
|
alpar@399
|
792 |
};
|
alpar@399
|
793 |
|
alpar@399
|
794 |
}
|
alpar@399
|
795 |
|
alpar@399
|
796 |
#endif
|