Changeset 1169:8db773f19586 in lemon-main

Timestamp:

03/22/18 18:56:47 (7 years ago)

Author:

Peter Kovacs <kpeter@…>

Branch:

default

Children:

1172:0fdf84c79bc1, 1176:2e0c2c25d63e

Phase:

public

Message:

Fix tolerance usage in Preflow algorithm (#608)

Files:

• lemon/preflow.h (modified) (6 diffs)
• test/max_flow_test.cc (modified) (7 diffs)

lemon/preflow.h

@@ -477 +477 @@
     /// flow to the given \c flowMap. The \c flowMap should contain a
     /// flow or at least a preflow, i.e. at each node excluding the
-    /// source node the incoming flow should greater or equal to the
+    /// source node the incoming flow should be greater or equal to the
     /// outgoing flow.
     /// \return \c false if the given \c flowMap is not a preflow.
@@ -496 +496 @@
           excess -= (*_flow)[e];
         }
-        if (excess < 0 && n != _source) return false;
+        if (_tolerance.negative(excess) && n != _source) return false;
         (*_excess)[n] = excess;
       }
@@ -640 +640 @@
           (*_excess)[n] = excess;
 
-          if (excess != 0) {
+          if (_tolerance.nonZero(excess)) {
             if (new_level + 1 < _level->maxLevel()) {
               _level->liftHighestActive(new_level + 1);
@@ -721 +721 @@
           (*_excess)[n] = excess;
 
-          if (excess != 0) {
+          if (_tolerance.nonZero(excess)) {
             if (new_level + 1 < _level->maxLevel()) {
               _level->liftActiveOn(level, new_level + 1);
@@ -792 +792 @@
         if (!reached[n]) {
           _level->dirtyTopButOne(n);
-        } else if ((*_excess)[n] > 0 && _target != n) {
+        } else if (_tolerance.positive((*_excess)[n]) && _target != n) {
           _level->activate(n);
         }
@@ -853 +853 @@
         (*_excess)[n] = excess;
 
-        if (excess != 0) {
+        if (_tolerance.nonZero(excess)) {
           if (new_level + 1 < _level->maxLevel()) {
             _level->liftHighestActive(new_level + 1);

test/max_flow_test.cc

@@ -67 +67 @@
   "target 8\n";
 
+char test_lgf_float[] =
+  "@nodes\n"
+  "label\n"
+  "0\n"
+  "1\n"
+  "2\n"
+  "3\n"
+  "4\n"
+  "5\n"
+  "6\n"
+  "7\n"
+  "8\n"
+  "9\n"
+  "@arcs\n"
+  "      capacity\n"
+  "0 1 0.1\n"
+  "0 2 0.1\n"
+  "0 3 0.1\n"
+  "1 4 0.1\n"
+  "2 4 0.1\n"
+  "3 4 0.1\n"
+  "4 5 0.3\n"
+  "5 6 0.1\n"
+  "5 7 0.1\n"
+  "5 8 0.1\n"
+  "6 9 0.1\n"
+  "7 9 0.1\n"
+  "8 9 0.1\n"
+  "@attributes\n"
+  "source 0\n"
+  "target 9\n";
+
 // Checks the general interface of a max flow algorithm
 template <typename GR, typename CAP>
@@ -259 +291 @@
   CapMap cap(g);
   std::istringstream input(input_lgf);
-  DigraphReader<Digraph>(g,input)
+  DigraphReader<Digraph>(g, input)
       .arcMap("capacity", cap)
-      .node("source",s)
-      .node("target",t)
+      .node("source", s)
+      .node("target", t)
       .run();
 
@@ -281 +313 @@
 
   FlowMap flow(g);
-  for (ArcIt e(g); e != INVALID; ++e) flow[e] = max_flow.flowMap()[e];
-  for (ArcIt e(g); e != INVALID; ++e) cap[e] = 2 * cap[e];
+  for (ArcIt e(g); e != INVALID; ++e) flow[e] = 13 * max_flow.flowMap()[e];
+  for (ArcIt e(g); e != INVALID; ++e) cap[e] = 17 * cap[e];
   max_flow.init(flow);
 
@@ -291 +323 @@
   min_cut_value = cutValue(g, min_cut1, cap);
 
-  check(!tol.different(2 * expected, max_flow.flowValue()),
+  check(!tol.different(17 * expected, max_flow.flowValue()),
         "Incorrect max flow value.");
-  check(!tol.different(2 * expected, min_cut_value),
+  check(!tol.different(17 * expected, min_cut_value),
         "Incorrect min cut value.");
 
@@ -305 +337 @@
   min_cut_value = cutValue(g, min_cut2, cap);
 
-  check(!tol.different(2 * expected, max_flow.flowValue()),
+  check(!tol.different(17 * expected, max_flow.flowValue()),
         "Incorrect max flow value.");
-  check(!tol.different(2 * expected, min_cut_value),
+  check(!tol.different(17 * expected, min_cut_value),
         "Incorrect min cut value.");
 
@@ -383 +415 @@
   typedef Preflow<SmartDigraph, SmartDigraph::ArcMap<float> > PType2;
   typedef Preflow<SmartDigraph, SmartDigraph::ArcMap<double> > PType3;
+
   checkMaxFlowAlg<PType1, PreflowStartFunctions<PType1> >(test_lgf, 13);
   checkMaxFlowAlg<PType2, PreflowStartFunctions<PType2> >(test_lgf, 13);
   checkMaxFlowAlg<PType3, PreflowStartFunctions<PType3> >(test_lgf, 13);
+
+  checkMaxFlowAlg<PType2, PreflowStartFunctions<PType2> >(test_lgf_float, 0.3);
+  checkMaxFlowAlg<PType3, PreflowStartFunctions<PType3> >(test_lgf_float, 0.3);
 
   checkInitPreflow();
@@ -393 +429 @@
   typedef EdmondsKarp<SmartDigraph, SmartDigraph::ArcMap<float> > EKType2;
   typedef EdmondsKarp<SmartDigraph, SmartDigraph::ArcMap<double> > EKType3;
+
   checkMaxFlowAlg<EKType1, GeneralStartFunctions<EKType1> >(test_lgf, 13);
   checkMaxFlowAlg<EKType2, GeneralStartFunctions<EKType2> >(test_lgf, 13);
   checkMaxFlowAlg<EKType3, GeneralStartFunctions<EKType3> >(test_lgf, 13);
 
+  checkMaxFlowAlg<EKType2, GeneralStartFunctions<EKType2> >(test_lgf_float, 0.3);
+  checkMaxFlowAlg<EKType3, GeneralStartFunctions<EKType3> >(test_lgf_float, 0.3);
+
   return 0;
 }