1.1 --- a/lemon/Makefile.am Mon Nov 28 11:14:59 2005 +0000
1.2 +++ b/lemon/Makefile.am Tue Nov 29 08:40:03 2005 +0000
1.3 @@ -7,7 +7,8 @@
1.4
1.5 libemon_la_SOURCES = \
1.6 lp_base.cc \
1.7 - lp_skeleton.cc
1.8 + lp_skeleton.cc \
1.9 + base.cc
1.10 libemon_la_CXXFLAGS = $(GLPK_CFLAGS) $(CPLEX_CFLAGS)
1.11 libemon_la_LDFLAGS = $(GLPK_LIBS) $(CPLEX_LIBS)
1.12
1.13 @@ -70,6 +71,7 @@
1.14 lemon_writer.h \
1.15 graph_reader.h \
1.16 graph_writer.h \
1.17 + tolerance.h \
1.18 bits/alteration_notifier.h \
1.19 bits/array_map.h \
1.20 bits/default_map.h \
2.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
2.2 +++ b/lemon/base.cc Tue Nov 29 08:40:03 2005 +0000
2.3 @@ -0,0 +1,27 @@
2.4 +/* -*- C++ -*-
2.5 + * lemon/base.cc - Part of LEMON, a generic C++ optimization library
2.6 + *
2.7 + * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
2.8 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
2.9 + *
2.10 + * Permission to use, modify and distribute this software is granted
2.11 + * provided that this copyright notice appears in all copies. For
2.12 + * precise terms see the accompanying LICENSE file.
2.13 + *
2.14 + * This software is provided "AS IS" with no warranty of any kind,
2.15 + * express or implied, and with no claim as to its suitability for any
2.16 + * purpose.
2.17 + *
2.18 + */
2.19 +
2.20 +///\file
2.21 +///\brief Some basic non inline function and static global data.
2.22 +
2.23 +#include<lemon/tolerance.h>
2.24 +#include<lemon/invalid.h>
2.25 +namespace lemon {
2.26 +
2.27 + double Tolerance<double>::def_epsilon = 1e-10;
2.28 + float Tolerance<float>::def_epsilon = 1e-4;
2.29 +
2.30 +} //namespace lemon
3.1 --- a/lemon/preflow.h Mon Nov 28 11:14:59 2005 +0000
3.2 +++ b/lemon/preflow.h Tue Nov 29 08:40:03 2005 +0000
3.3 @@ -22,6 +22,7 @@
3.4
3.5 #include <lemon/error.h>
3.6 #include <lemon/invalid.h>
3.7 +#include <lemon/tolerance.h>
3.8 #include <lemon/maps.h>
3.9 #include <lemon/graph_utils.h>
3.10
3.11 @@ -61,7 +62,8 @@
3.12 ///\todo Second template parameter is superfluous
3.13 template <typename Graph, typename Num,
3.14 typename CapacityMap=typename Graph::template EdgeMap<Num>,
3.15 - typename FlowMap=typename Graph::template EdgeMap<Num> >
3.16 + typename FlowMap=typename Graph::template EdgeMap<Num>,
3.17 + typename TOL=Tolerance<Num> >
3.18 class Preflow {
3.19 protected:
3.20 typedef typename Graph::Node Node;
3.21 @@ -78,6 +80,9 @@
3.22 Node _target;
3.23 const CapacityMap* _capacity;
3.24 FlowMap* _flow;
3.25 +
3.26 + TOL surely;
3.27 +
3.28 int _node_num; //the number of nodes of G
3.29
3.30 typename Graph::template NodeMap<int> level;
3.31 @@ -153,9 +158,11 @@
3.32 ///calling \ref source, \ref target, \ref capacityMap and \ref
3.33 ///flowMap, resp.
3.34 Preflow(const Graph& _gr, Node _s, Node _t,
3.35 - const CapacityMap& _cap, FlowMap& _f) :
3.36 + const CapacityMap& _cap, FlowMap& _f,
3.37 + const TOL &tol=TOL()) :
3.38 _g(&_gr), _source(_s), _target(_t), _capacity(&_cap),
3.39 - _flow(&_f), _node_num(countNodes(_gr)), level(_gr), excess(_gr,0),
3.40 + _flow(&_f), surely(tol),
3.41 + _node_num(countNodes(_gr)), level(_gr), excess(_gr,0),
3.42 flow_prop(NO_FLOW), status(AFTER_NOTHING) {
3.43 if ( _source==_target )
3.44 throw InvalidArgument();
4.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
4.2 +++ b/lemon/tolerance.h Tue Nov 29 08:40:03 2005 +0000
4.3 @@ -0,0 +1,257 @@
4.4 +/* -*- C++ -*-
4.5 + * lemon/tolerance.h - Part of LEMON, a generic C++ optimization library
4.6 + *
4.7 + * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
4.8 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
4.9 + *
4.10 + * Permission to use, modify and distribute this software is granted
4.11 + * provided that this copyright notice appears in all copies. For
4.12 + * precise terms see the accompanying LICENSE file.
4.13 + *
4.14 + * This software is provided "AS IS" with no warranty of any kind,
4.15 + * express or implied, and with no claim as to its suitability for any
4.16 + * purpose.
4.17 + *
4.18 + */
4.19 +
4.20 +#ifndef LEMON_TOLERANCE_H
4.21 +#define LEMON_TOLERANCE_H
4.22 +
4.23 +///\ingroup misc
4.24 +///\file
4.25 +///\brief A basic tool to handle the anomalies of calculation with
4.26 +///floating point numbers.
4.27 +///
4.28 +///\todo It should be in a module like "Basic tools"
4.29 +
4.30 +
4.31 +namespace lemon {
4.32 +
4.33 + /// \addtogroup misc
4.34 + /// @{
4.35 +
4.36 + ///\brief A class to provide a basic way to
4.37 + ///handle the comparison of numbers that are obtained
4.38 + ///as a result of a probably inexact computation.
4.39 + ///
4.40 + ///Tolerance is a class to provide a basic way to
4.41 + ///handle the comparison of numbers that are obtained
4.42 + ///as a result of a probably inexact computation.
4.43 + ///
4.44 + ///This is an abstract class, it should be specialized for all numerical
4.45 + ///data types. These specialized classes like \ref Tolerance<double>
4.46 + ///may offer additional tuning parameters.
4.47 + ///
4.48 + ///\sa Tolerance<float>
4.49 + ///\sa Tolerance<double>
4.50 + ///\sa Tolerance<int>
4.51 + ///\sa Tolerance<long long int>
4.52 +
4.53 + template<class T>
4.54 + class Tolerance
4.55 + {
4.56 + public:
4.57 + typedef T Value;
4.58 +
4.59 + ///\name Comparisons
4.60 + ///The concept is that these bool functions return with \c true only if
4.61 + ///the related comparisons hold even if some numerical error appeared
4.62 + ///during the computations.
4.63 +
4.64 + ///@{
4.65 +
4.66 + ///Returns \c true if \c a is \e surely strictly less than \c b
4.67 + static bool less(Value a,Value b) {return false;}
4.68 + ///Returns \c true if \c a is \e surely different from \c b
4.69 + static bool different(Value a,Value b) {return false;}
4.70 + ///Returns \c true if \c a is \e surely positive
4.71 + static bool positive(Value a) {return false;}
4.72 + ///Returns \c true if \c a is \e surely negative
4.73 + static bool negative(Value a) {return false;}
4.74 + ///Returns \c true if \c a is \e surely non-zero
4.75 + static bool nonZero(Value a) {return false;}
4.76 +
4.77 + ///@}
4.78 +
4.79 + ///Returns the zero value.
4.80 + static Value zero() {return T();}
4.81 +
4.82 + // static bool finite(Value a) {}
4.83 + // static Value big() {}
4.84 + // static Value negativeBig() {}
4.85 + };
4.86 +
4.87 +
4.88 + ///Double specialization of \ref Tolerance.
4.89 +
4.90 + ///Double specialization of \ref Tolerance.
4.91 + ///\sa Tolerance
4.92 + ///\relates Tolerance
4.93 + template<>
4.94 + class Tolerance<double>
4.95 + {
4.96 + static double def_epsilon;
4.97 + double _epsilon;
4.98 + public:
4.99 + ///\e
4.100 + typedef double Value;
4.101 +
4.102 + ///Constructor setting the epsilon tolerance to the default value.
4.103 + Tolerance() : _epsilon(def_epsilon) {}
4.104 + ///Constructor setting the epsilon tolerance.
4.105 + Tolerance(double e) : _epsilon(e) {}
4.106 +
4.107 + ///Return the epsilon value.
4.108 + Value epsilon() {return _epsilon;}
4.109 + ///Set the epsilon value.
4.110 + void epsilon(Value e) {_epsilon=e;}
4.111 +
4.112 + ///Return the default epsilon value.
4.113 + static Value defaultEpsilon() {return def_epsilon;}
4.114 + ///Set the default epsilon value.
4.115 + static void defaultEpsilon(Value e) {def_epsilon=e;}
4.116 +
4.117 + ///\name Comparisons
4.118 + ///See class Tolerance for more details.
4.119 +
4.120 + ///@{
4.121 +
4.122 + ///Returns \c true if \c a is \e surely strictly less than \c b
4.123 + bool less(Value a,Value b) {return a+_epsilon<b;}
4.124 + ///Returns \c true if \c a is \e surely different from \c b
4.125 + bool different(Value a,Value b) { return less(a,b)||less(b,a); }
4.126 + ///Returns \c true if \c a is \e surely positive
4.127 + bool positive(Value a) { return _epsilon<a; }
4.128 + ///Returns \c true if \c a is \e surely negative
4.129 + bool negative(Value a) { return -_epsilon>a; }
4.130 + ///Returns \c true if \c a is \e surely non-zero
4.131 + Value nonZero(Value a) { return positive(a)||negative(a); };
4.132 +
4.133 + ///@}
4.134 +
4.135 + ///Returns zero
4.136 + static Value zero() {return 0;}
4.137 + };
4.138 +
4.139 + ///Float specialization of \ref Tolerance.
4.140 +
4.141 + ///Float specialization of \ref Tolerance.
4.142 + ///\sa Tolerance
4.143 + ///\relates Tolerance
4.144 + template<>
4.145 + class Tolerance<float>
4.146 + {
4.147 + static float def_epsilon;
4.148 + float _epsilon;
4.149 + public:
4.150 + ///\e
4.151 + typedef float Value;
4.152 +
4.153 + ///Constructor setting the epsilon tolerance to the default value.
4.154 + Tolerance() : _epsilon(def_epsilon) {}
4.155 + ///Constructor setting the epsilon tolerance.
4.156 + Tolerance(float e) : _epsilon(e) {}
4.157 +
4.158 + ///Return the epsilon value.
4.159 + Value epsilon() {return _epsilon;}
4.160 + ///Set the epsilon value.
4.161 + void epsilon(Value e) {_epsilon=e;}
4.162 +
4.163 + ///Return the default epsilon value.
4.164 + static Value defaultEpsilon() {return def_epsilon;}
4.165 + ///Set the default epsilon value.
4.166 + static void defaultEpsilon(Value e) {def_epsilon=e;}
4.167 +
4.168 + ///\name Comparisons
4.169 + ///See class Tolerance for more details.
4.170 +
4.171 + ///@{
4.172 +
4.173 + ///Returns \c true if \c a is \e surely strictly less than \c b
4.174 + bool less(Value a,Value b) {return a+_epsilon<b;}
4.175 + ///Returns \c true if \c a is \e surely different from \c b
4.176 + bool different(Value a,Value b) { return less(a,b)||less(b,a); }
4.177 + ///Returns \c true if \c a is \e surely positive
4.178 + bool positive(Value a) { return _epsilon<a; }
4.179 + ///Returns \c true if \c a is \e surely negative
4.180 + bool negative(Value a) { return -_epsilon>a; }
4.181 + ///Returns \c true if \c a is \e surely non-zero
4.182 + Value nonZero(Value a) { return positive(a)||negative(a); };
4.183 +
4.184 + ///@}
4.185 +
4.186 + ///Returns zero
4.187 + static Value zero() {return 0;}
4.188 + };
4.189 +
4.190 + ///Integer specialization of \ref Tolerance.
4.191 +
4.192 + ///Integer specialization of \ref Tolerance.
4.193 + ///\sa Tolerance
4.194 + template<>
4.195 + class Tolerance<int>
4.196 + {
4.197 + public:
4.198 + ///\e
4.199 + typedef int Value;
4.200 +
4.201 + ///\name Comparisons
4.202 + ///See \ref Tolerance for more details.
4.203 +
4.204 + ///@{
4.205 +
4.206 + ///Returns \c true if \c a is \e surely strictly less than \c b
4.207 + static bool less(Value a,Value b) { return a<b;}
4.208 + ///Returns \c true if \c a is \e surely different from \c b
4.209 + static bool different(Value a,Value b) { return a!=b; }
4.210 + ///Returns \c true if \c a is \e surely positive
4.211 + static bool positive(Value a) { return 0<a; }
4.212 + ///Returns \c true if \c a is \e surely negative
4.213 + static bool negative(Value a) { return 0>a; }
4.214 + ///Returns \c true if \c a is \e surely non-zero
4.215 + static Value nonZero(Value a) { return a!=0;};
4.216 +
4.217 + ///@}
4.218 +
4.219 + ///Returns zero
4.220 + static Value zero() {return 0;}
4.221 + };
4.222 +
4.223 + ///Long long integer specialization of \ref Tolerance.
4.224 +
4.225 + ///Long long integer specialization of \ref Tolerance.
4.226 + ///\sa Tolerance
4.227 + template<>
4.228 + class Tolerance<long long int>
4.229 + {
4.230 + public:
4.231 + ///\e
4.232 + typedef long long int Value;
4.233 +
4.234 + ///\name Comparisons
4.235 + ///See \ref Tolerance for more details.
4.236 +
4.237 + ///@{
4.238 +
4.239 + ///Returns \c true if \c a is \e surely strictly less than \c b
4.240 + static bool less(Value a,Value b) { return a<b;}
4.241 + ///Returns \c true if \c a is \e surely different from \c b
4.242 + static bool different(Value a,Value b) { return a!=b; }
4.243 + ///Returns \c true if \c a is \e surely positive
4.244 + static bool positive(Value a) { return 0<a; }
4.245 + ///Returns \c true if \c a is \e surely negative
4.246 + static bool negative(Value a) { return 0>a; }
4.247 + ///Returns \c true if \c a is \e surely non-zero
4.248 + static Value nonZero(Value a) { return a!=0;};
4.249 +
4.250 + ///@}
4.251 +
4.252 + ///Returns zero
4.253 + static Value zero() {return 0;}
4.254 + };
4.255 +
4.256 + /// @}
4.257 +
4.258 +} //namespace lemon
4.259 +
4.260 +#endif //LEMON_TOLERANCE_H