# HG changeset patch
# User alpar
# Date 1133253603 0
# Node ID eb6c34c76501175ee02e1f51d0b256cce775b69c
# Parent  0a14e1ae45a149ce13331a55f025354c051397bc
- tolerance.h added
- tolerance handler added to preflow (but not yet used!!).

diff -r 0a14e1ae45a1 -r eb6c34c76501 lemon/Makefile.am
--- a/lemon/Makefile.am	Mon Nov 28 11:14:59 2005 +0000
+++ b/lemon/Makefile.am	Tue Nov 29 08:40:03 2005 +0000
@@ -7,7 +7,8 @@
 
 libemon_la_SOURCES = \
 	lp_base.cc \
-	lp_skeleton.cc
+	lp_skeleton.cc \
+	base.cc 
 libemon_la_CXXFLAGS = $(GLPK_CFLAGS) $(CPLEX_CFLAGS)
 libemon_la_LDFLAGS = $(GLPK_LIBS) $(CPLEX_LIBS)
 
@@ -70,6 +71,7 @@
 	lemon_writer.h \
 	graph_reader.h \
 	graph_writer.h \
+	tolerance.h \
 	bits/alteration_notifier.h \
 	bits/array_map.h \
 	bits/default_map.h \
diff -r 0a14e1ae45a1 -r eb6c34c76501 lemon/base.cc
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/lemon/base.cc	Tue Nov 29 08:40:03 2005 +0000
@@ -0,0 +1,27 @@
+/* -*- C++ -*-
+ * lemon/base.cc - Part of LEMON, a generic C++ optimization library
+ *
+ * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
+ * (Egervary Research Group on Combinatorial Optimization, EGRES).
+ *
+ * Permission to use, modify and distribute this software is granted
+ * provided that this copyright notice appears in all copies. For
+ * precise terms see the accompanying LICENSE file.
+ *
+ * This software is provided "AS IS" with no warranty of any kind,
+ * express or implied, and with no claim as to its suitability for any
+ * purpose.
+ *
+ */
+
+///\file
+///\brief Some basic non inline function and static global data.
+
+#include<lemon/tolerance.h>
+#include<lemon/invalid.h>
+namespace lemon {
+
+  double Tolerance<double>::def_epsilon = 1e-10;
+  float Tolerance<float>::def_epsilon = 1e-4;
+
+} //namespace lemon
diff -r 0a14e1ae45a1 -r eb6c34c76501 lemon/preflow.h
--- a/lemon/preflow.h	Mon Nov 28 11:14:59 2005 +0000
+++ b/lemon/preflow.h	Tue Nov 29 08:40:03 2005 +0000
@@ -22,6 +22,7 @@
 
 #include <lemon/error.h>
 #include <lemon/invalid.h>
+#include <lemon/tolerance.h>
 #include <lemon/maps.h>
 #include <lemon/graph_utils.h>
 
@@ -61,7 +62,8 @@
   ///\todo Second template parameter is superfluous
   template <typename Graph, typename Num,
 	    typename CapacityMap=typename Graph::template EdgeMap<Num>,
-            typename FlowMap=typename Graph::template EdgeMap<Num> >
+            typename FlowMap=typename Graph::template EdgeMap<Num>,
+	    typename TOL=Tolerance<Num> >
   class Preflow {
   protected:
     typedef typename Graph::Node Node;
@@ -78,6 +80,9 @@
     Node _target;
     const CapacityMap* _capacity;
     FlowMap* _flow;
+
+    TOL surely;
+    
     int _node_num;      //the number of nodes of G
     
     typename Graph::template NodeMap<int> level;  
@@ -153,9 +158,11 @@
     ///calling \ref source, \ref target, \ref capacityMap and \ref
     ///flowMap, resp.
       Preflow(const Graph& _gr, Node _s, Node _t, 
-	      const CapacityMap& _cap, FlowMap& _f) :
+	      const CapacityMap& _cap, FlowMap& _f,
+	      const TOL &tol=TOL()) :
 	_g(&_gr), _source(_s), _target(_t), _capacity(&_cap),
-	_flow(&_f), _node_num(countNodes(_gr)), level(_gr), excess(_gr,0), 
+	_flow(&_f), surely(tol),
+	_node_num(countNodes(_gr)), level(_gr), excess(_gr,0), 
 	flow_prop(NO_FLOW), status(AFTER_NOTHING) { 
 	if ( _source==_target )
 	  throw InvalidArgument();
diff -r 0a14e1ae45a1 -r eb6c34c76501 lemon/tolerance.h
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/lemon/tolerance.h	Tue Nov 29 08:40:03 2005 +0000
@@ -0,0 +1,257 @@
+/* -*- C++ -*-
+ * lemon/tolerance.h - Part of LEMON, a generic C++ optimization library
+ *
+ * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
+ * (Egervary Research Group on Combinatorial Optimization, EGRES).
+ *
+ * Permission to use, modify and distribute this software is granted
+ * provided that this copyright notice appears in all copies. For
+ * precise terms see the accompanying LICENSE file.
+ *
+ * This software is provided "AS IS" with no warranty of any kind,
+ * express or implied, and with no claim as to its suitability for any
+ * purpose.
+ *
+ */
+
+#ifndef LEMON_TOLERANCE_H
+#define LEMON_TOLERANCE_H
+
+///\ingroup misc
+///\file
+///\brief A basic tool to handle the anomalies of calculation with
+///floating point numbers.
+///
+///\todo It should be in a module like "Basic tools"
+
+
+namespace lemon {
+
+  /// \addtogroup misc
+  /// @{
+  
+  ///\brief A class to provide a basic way to
+  ///handle the comparison of numbers that are obtained
+  ///as a result of a probably inexact computation.
+  ///
+  ///Tolerance is a class to provide a basic way to
+  ///handle the comparison of numbers that are obtained
+  ///as a result of a probably inexact computation.
+  ///
+  ///This is an abstract class, it should be specialized for all numerical
+  ///data types. These specialized classes like \ref Tolerance<double>
+  ///may offer additional tuning parameters.
+  ///
+  ///\sa Tolerance<float>
+  ///\sa Tolerance<double>
+  ///\sa Tolerance<int>
+  ///\sa Tolerance<long long int>
+
+  template<class T>
+  class Tolerance
+  {
+  public:
+    typedef T Value;
+
+    ///\name Comparisons
+    ///The concept is that these bool functions return with \c true only if
+    ///the related comparisons hold even if some numerical error appeared
+    ///during the computations.
+
+    ///@{
+
+    ///Returns \c true if \c a is \e surely strictly less than \c b
+    static bool less(Value a,Value b) {return false;}
+    ///Returns \c true if \c a is \e surely different from \c b
+    static bool different(Value a,Value b) {return false;}
+    ///Returns \c true if \c a is \e surely positive
+    static bool positive(Value a) {return false;}
+    ///Returns \c true if \c a is \e surely negative
+    static bool negative(Value a) {return false;}
+    ///Returns \c true if \c a is \e surely non-zero
+    static bool nonZero(Value a) {return false;}
+
+    ///@}
+
+    ///Returns the zero value.
+    static Value zero() {return T();}
+
+    //   static bool finite(Value a) {}
+    //   static Value big() {}
+    //   static Value negativeBig() {}
+  };
+
+
+  ///Double specialization of \ref Tolerance.
+
+  ///Double specialization of \ref Tolerance.
+  ///\sa Tolerance
+  ///\relates Tolerance
+  template<>
+  class Tolerance<double>
+  {
+    static double def_epsilon;
+    double _epsilon;
+  public:
+    ///\e
+    typedef double Value;
+
+    ///Constructor setting the epsilon tolerance to the default value.
+    Tolerance() : _epsilon(def_epsilon) {}
+    ///Constructor setting the epsilon tolerance.
+    Tolerance(double e) : _epsilon(e) {}
+
+    ///Return the epsilon value.
+    Value epsilon() {return _epsilon;}
+    ///Set the epsilon value.
+    void epsilon(Value e) {_epsilon=e;}
+
+    ///Return the default epsilon value.
+    static Value defaultEpsilon() {return def_epsilon;}
+    ///Set the default epsilon value.
+    static void defaultEpsilon(Value e) {def_epsilon=e;}
+
+    ///\name Comparisons
+    ///See class Tolerance for more details.
+
+    ///@{
+
+    ///Returns \c true if \c a is \e surely strictly less than \c b
+    bool less(Value a,Value b) {return a+_epsilon<b;}
+    ///Returns \c true if \c a is \e surely different from \c b
+    bool different(Value a,Value b) { return less(a,b)||less(b,a); }
+    ///Returns \c true if \c a is \e surely positive
+    bool positive(Value a) { return _epsilon<a; }
+    ///Returns \c true if \c a is \e surely negative
+    bool negative(Value a) { return -_epsilon>a; }
+    ///Returns \c true if \c a is \e surely non-zero
+    Value nonZero(Value a) { return positive(a)||negative(a); };
+
+    ///@}
+
+    ///Returns zero
+    static Value zero() {return 0;}
+  };
+
+  ///Float specialization of \ref Tolerance.
+
+  ///Float specialization of \ref Tolerance.
+  ///\sa Tolerance
+  ///\relates Tolerance
+  template<>
+  class Tolerance<float>
+  {
+    static float def_epsilon;
+    float _epsilon;
+  public:
+    ///\e
+    typedef float Value;
+
+    ///Constructor setting the epsilon tolerance to the default value.
+    Tolerance() : _epsilon(def_epsilon) {}
+    ///Constructor setting the epsilon tolerance.
+    Tolerance(float e) : _epsilon(e) {}
+
+    ///Return the epsilon value.
+    Value epsilon() {return _epsilon;}
+    ///Set the epsilon value.
+    void epsilon(Value e) {_epsilon=e;}
+
+    ///Return the default epsilon value.
+    static Value defaultEpsilon() {return def_epsilon;}
+    ///Set the default epsilon value.
+    static void defaultEpsilon(Value e) {def_epsilon=e;}
+
+    ///\name Comparisons
+    ///See class Tolerance for more details.
+
+    ///@{
+
+    ///Returns \c true if \c a is \e surely strictly less than \c b
+    bool less(Value a,Value b) {return a+_epsilon<b;}
+    ///Returns \c true if \c a is \e surely different from \c b
+    bool different(Value a,Value b) { return less(a,b)||less(b,a); }
+    ///Returns \c true if \c a is \e surely positive
+    bool positive(Value a) { return _epsilon<a; }
+    ///Returns \c true if \c a is \e surely negative
+    bool negative(Value a) { return -_epsilon>a; }
+    ///Returns \c true if \c a is \e surely non-zero
+    Value nonZero(Value a) { return positive(a)||negative(a); };
+
+    ///@}
+
+    ///Returns zero
+    static Value zero() {return 0;}
+  };
+
+  ///Integer specialization of \ref Tolerance.
+
+  ///Integer specialization of \ref Tolerance.
+  ///\sa Tolerance
+  template<>
+  class Tolerance<int>
+  {
+  public:
+    ///\e
+    typedef int Value;
+
+    ///\name Comparisons
+    ///See \ref Tolerance for more details.
+
+    ///@{
+
+    ///Returns \c true if \c a is \e surely strictly less than \c b
+    static bool less(Value a,Value b) { return a<b;}
+    ///Returns \c true if \c a is \e surely different from \c b
+    static bool different(Value a,Value b) { return a!=b; }
+    ///Returns \c true if \c a is \e surely positive
+    static bool positive(Value a) { return 0<a; }
+    ///Returns \c true if \c a is \e surely negative
+    static bool negative(Value a) { return 0>a; }
+    ///Returns \c true if \c a is \e surely non-zero
+    static Value nonZero(Value a) { return a!=0;};
+
+    ///@}
+
+    ///Returns zero
+    static Value zero() {return 0;}
+  };
+
+  ///Long long integer specialization of \ref Tolerance.
+
+  ///Long long integer specialization of \ref Tolerance.
+  ///\sa Tolerance
+  template<>
+  class Tolerance<long long int>
+  {
+  public:
+    ///\e
+    typedef long long int Value;
+
+    ///\name Comparisons
+    ///See \ref Tolerance for more details.
+
+    ///@{
+
+    ///Returns \c true if \c a is \e surely strictly less than \c b
+    static bool less(Value a,Value b) { return a<b;}
+    ///Returns \c true if \c a is \e surely different from \c b
+    static bool different(Value a,Value b) { return a!=b; }
+    ///Returns \c true if \c a is \e surely positive
+    static bool positive(Value a) { return 0<a; }
+    ///Returns \c true if \c a is \e surely negative
+    static bool negative(Value a) { return 0>a; }
+    ///Returns \c true if \c a is \e surely non-zero
+    static Value nonZero(Value a) { return a!=0;};
+
+    ///@}
+
+    ///Returns zero
+    static Value zero() {return 0;}
+  };
+
+  /// @}
+
+} //namespace lemon
+
+#endif //LEMON_TOLERANCE_H