Redesigned CapacityScaling algorithm with almost the same interface.
The new version does not use the ResidualGraphAdaptor for performance reasons.
Scaling can be enabled and disabled with a parameter of the run() function.
3 * This file is a part of LEMON, a generic C++ optimization library
5 * Copyright (C) 2003-2007
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
19 #ifndef LEMON_TOLERANCE_H
20 #define LEMON_TOLERANCE_H
24 ///\brief A basic tool to handle the anomalies of calculation with
25 ///floating point numbers.
27 ///\todo It should be in a module like "Basic tools"
35 ///\brief A class to provide a basic way to
36 ///handle the comparison of numbers that are obtained
37 ///as a result of a probably inexact computation.
39 ///Tolerance is a class to provide a basic way to
40 ///handle the comparison of numbers that are obtained
41 ///as a result of a probably inexact computation.
43 ///This is an abstract class, it should be specialized for all numerical
44 ///data types. These specialized classes like \ref Tolerance\<double\>
45 ///may offer additional tuning parameters.
47 ///\sa Tolerance<float>
48 ///\sa Tolerance<double>
49 ///\sa Tolerance<long double>
51 ///\sa Tolerance<long long int>
52 ///\sa Tolerance<unsigned int>
53 ///\sa Tolerance<unsigned long long int>
62 ///The concept is that these bool functions return with \c true only if
63 ///the related comparisons hold even if some numerical error appeared
64 ///during the computations.
68 ///Returns \c true if \c a is \e surely strictly less than \c b
69 static bool less(Value a,Value b) {return false;}
70 ///Returns \c true if \c a is \e surely different from \c b
71 static bool different(Value a,Value b) {return false;}
72 ///Returns \c true if \c a is \e surely positive
73 static bool positive(Value a) {return false;}
74 ///Returns \c true if \c a is \e surely negative
75 static bool negative(Value a) {return false;}
76 ///Returns \c true if \c a is \e surely non-zero
77 static bool nonZero(Value a) {return false;}
81 ///Returns the zero value.
82 static Value zero() {return T();}
84 // static bool finite(Value a) {}
85 // static Value big() {}
86 // static Value negativeBig() {}
90 ///Float specialization of \ref Tolerance.
92 ///Float specialization of \ref Tolerance.
96 class Tolerance<float>
98 static float def_epsilon;
104 ///Constructor setting the epsilon tolerance to the default value.
105 Tolerance() : _epsilon(def_epsilon) {}
106 ///Constructor setting the epsilon tolerance.
107 Tolerance(float e) : _epsilon(e) {}
109 ///Return the epsilon value.
110 Value epsilon() const {return _epsilon;}
111 ///Set the epsilon value.
112 void epsilon(Value e) {_epsilon=e;}
114 ///Return the default epsilon value.
115 static Value defaultEpsilon() {return def_epsilon;}
116 ///Set the default epsilon value.
117 static void defaultEpsilon(Value e) {def_epsilon=e;}
120 ///See class Tolerance for more details.
124 ///Returns \c true if \c a is \e surely strictly less than \c b
125 bool less(Value a,Value b) const {return a+_epsilon<b;}
126 ///Returns \c true if \c a is \e surely different from \c b
127 bool different(Value a,Value b) const { return less(a,b)||less(b,a); }
128 ///Returns \c true if \c a is \e surely positive
129 bool positive(Value a) const { return _epsilon<a; }
130 ///Returns \c true if \c a is \e surely negative
131 bool negative(Value a) const { return -_epsilon>a; }
132 ///Returns \c true if \c a is \e surely non-zero
133 bool nonZero(Value a) const { return positive(a)||negative(a); };
138 static Value zero() {return 0;}
141 ///Double specialization of \ref Tolerance.
143 ///Double specialization of \ref Tolerance.
145 ///\relates Tolerance
147 class Tolerance<double>
149 static double def_epsilon;
153 typedef double Value;
155 ///Constructor setting the epsilon tolerance to the default value.
156 Tolerance() : _epsilon(def_epsilon) {}
157 ///Constructor setting the epsilon tolerance.
158 Tolerance(double e) : _epsilon(e) {}
160 ///Return the epsilon value.
161 Value epsilon() const {return _epsilon;}
162 ///Set the epsilon value.
163 void epsilon(Value e) {_epsilon=e;}
165 ///Return the default epsilon value.
166 static Value defaultEpsilon() {return def_epsilon;}
167 ///Set the default epsilon value.
168 static void defaultEpsilon(Value e) {def_epsilon=e;}
171 ///See class Tolerance for more details.
175 ///Returns \c true if \c a is \e surely strictly less than \c b
176 bool less(Value a,Value b) const {return a+_epsilon<b;}
177 ///Returns \c true if \c a is \e surely different from \c b
178 bool different(Value a,Value b) const { return less(a,b)||less(b,a); }
179 ///Returns \c true if \c a is \e surely positive
180 bool positive(Value a) const { return _epsilon<a; }
181 ///Returns \c true if \c a is \e surely negative
182 bool negative(Value a) const { return -_epsilon>a; }
183 ///Returns \c true if \c a is \e surely non-zero
184 bool nonZero(Value a) const { return positive(a)||negative(a); };
189 static Value zero() {return 0;}
192 ///Long double specialization of \ref Tolerance.
194 ///Long double specialization of \ref Tolerance.
196 ///\relates Tolerance
198 class Tolerance<long double>
200 static long double def_epsilon;
201 long double _epsilon;
204 typedef long double Value;
206 ///Constructor setting the epsilon tolerance to the default value.
207 Tolerance() : _epsilon(def_epsilon) {}
208 ///Constructor setting the epsilon tolerance.
209 Tolerance(long double e) : _epsilon(e) {}
211 ///Return the epsilon value.
212 Value epsilon() const {return _epsilon;}
213 ///Set the epsilon value.
214 void epsilon(Value e) {_epsilon=e;}
216 ///Return the default epsilon value.
217 static Value defaultEpsilon() {return def_epsilon;}
218 ///Set the default epsilon value.
219 static void defaultEpsilon(Value e) {def_epsilon=e;}
222 ///See class Tolerance for more details.
226 ///Returns \c true if \c a is \e surely strictly less than \c b
227 bool less(Value a,Value b) const {return a+_epsilon<b;}
228 ///Returns \c true if \c a is \e surely different from \c b
229 bool different(Value a,Value b) const { return less(a,b)||less(b,a); }
230 ///Returns \c true if \c a is \e surely positive
231 bool positive(Value a) const { return _epsilon<a; }
232 ///Returns \c true if \c a is \e surely negative
233 bool negative(Value a) const { return -_epsilon>a; }
234 ///Returns \c true if \c a is \e surely non-zero
235 bool nonZero(Value a) const { return positive(a)||negative(a); };
240 static Value zero() {return 0;}
243 ///Integer specialization of \ref Tolerance.
245 ///Integer specialization of \ref Tolerance.
255 ///See \ref Tolerance for more details.
259 ///Returns \c true if \c a is \e surely strictly less than \c b
260 static bool less(Value a,Value b) { return a<b;}
261 ///Returns \c true if \c a is \e surely different from \c b
262 static bool different(Value a,Value b) { return a!=b; }
263 ///Returns \c true if \c a is \e surely positive
264 static bool positive(Value a) { return 0<a; }
265 ///Returns \c true if \c a is \e surely negative
266 static bool negative(Value a) { return 0>a; }
267 ///Returns \c true if \c a is \e surely non-zero
268 static bool nonZero(Value a) { return a!=0; };
273 static Value zero() {return 0;}
276 ///Unsigned integer specialization of \ref Tolerance.
278 ///Unsigned integer specialization of \ref Tolerance.
281 class Tolerance<unsigned int>
285 typedef unsigned int Value;
288 ///See \ref Tolerance for more details.
292 ///Returns \c true if \c a is \e surely strictly less than \c b
293 static bool less(Value a,Value b) { return a<b;}
294 ///Returns \c true if \c a is \e surely different from \c b
295 static bool different(Value a,Value b) { return a!=b; }
296 ///Returns \c true if \c a is \e surely positive
297 static bool positive(Value a) { return 0<a; }
298 ///Returns \c true if \c a is \e surely negative
299 static bool negative(Value) { return false; }
300 ///Returns \c true if \c a is \e surely non-zero
301 static bool nonZero(Value a) { return a!=0; };
306 static Value zero() {return 0;}
310 ///Long integer specialization of \ref Tolerance.
312 ///Long integer specialization of \ref Tolerance.
315 class Tolerance<long int>
319 typedef long int Value;
322 ///See \ref Tolerance for more details.
326 ///Returns \c true if \c a is \e surely strictly less than \c b
327 static bool less(Value a,Value b) { return a<b;}
328 ///Returns \c true if \c a is \e surely different from \c b
329 static bool different(Value a,Value b) { return a!=b; }
330 ///Returns \c true if \c a is \e surely positive
331 static bool positive(Value a) { return 0<a; }
332 ///Returns \c true if \c a is \e surely negative
333 static bool negative(Value a) { return 0>a; }
334 ///Returns \c true if \c a is \e surely non-zero
335 static bool nonZero(Value a) { return a!=0;};
340 static Value zero() {return 0;}
343 ///Unsigned long integer specialization of \ref Tolerance.
345 ///Unsigned long integer specialization of \ref Tolerance.
348 class Tolerance<unsigned long int>
352 typedef unsigned long int Value;
355 ///See \ref Tolerance for more details.
359 ///Returns \c true if \c a is \e surely strictly less than \c b
360 static bool less(Value a,Value b) { return a<b;}
361 ///Returns \c true if \c a is \e surely different from \c b
362 static bool different(Value a,Value b) { return a!=b; }
363 ///Returns \c true if \c a is \e surely positive
364 static bool positive(Value a) { return 0<a; }
365 ///Returns \c true if \c a is \e surely negative
366 static bool negative(Value) { return false; }
367 ///Returns \c true if \c a is \e surely non-zero
368 static bool nonZero(Value a) { return a!=0;};
373 static Value zero() {return 0;}
376 #if defined __GNUC__ && !defined __STRICT_ANSI__
378 ///Long long integer specialization of \ref Tolerance.
380 ///Long long integer specialization of \ref Tolerance.
381 ///\warning This class (more exactly, type <tt>long long</tt>)
382 ///is not ansi compatible.
385 class Tolerance<long long int>
389 typedef long long int Value;
392 ///See \ref Tolerance for more details.
396 ///Returns \c true if \c a is \e surely strictly less than \c b
397 static bool less(Value a,Value b) { return a<b;}
398 ///Returns \c true if \c a is \e surely different from \c b
399 static bool different(Value a,Value b) { return a!=b; }
400 ///Returns \c true if \c a is \e surely positive
401 static bool positive(Value a) { return 0<a; }
402 ///Returns \c true if \c a is \e surely negative
403 static bool negative(Value a) { return 0>a; }
404 ///Returns \c true if \c a is \e surely non-zero
405 static bool nonZero(Value a) { return a!=0;};
410 static Value zero() {return 0;}
413 ///Unsigned long long integer specialization of \ref Tolerance.
415 ///Unsigned long long integer specialization of \ref Tolerance.
416 ///\warning This class (more exactly, type <tt>unsigned long long</tt>)
417 ///is not ansi compatible.
420 class Tolerance<unsigned long long int>
424 typedef unsigned long long int Value;
427 ///See \ref Tolerance for more details.
431 ///Returns \c true if \c a is \e surely strictly less than \c b
432 static bool less(Value a,Value b) { return a<b;}
433 ///Returns \c true if \c a is \e surely different from \c b
434 static bool different(Value a,Value b) { return a!=b; }
435 ///Returns \c true if \c a is \e surely positive
436 static bool positive(Value a) { return 0<a; }
437 ///Returns \c true if \c a is \e surely negative
438 static bool negative(Value) { return false; }
439 ///Returns \c true if \c a is \e surely non-zero
440 static bool nonZero(Value a) { return a!=0;};
445 static Value zero() {return 0;}
454 #endif //LEMON_TOLERANCE_H