1.1 --- a/lemon/preflow.h Thu Mar 22 18:56:26 2018 +0100
1.2 +++ b/lemon/preflow.h Thu Mar 22 18:56:47 2018 +0100
1.3 @@ -476,7 +476,7 @@
1.4 /// Initializes the internal data structures and sets the initial
1.5 /// flow to the given \c flowMap. The \c flowMap should contain a
1.6 /// flow or at least a preflow, i.e. at each node excluding the
1.7 - /// source node the incoming flow should greater or equal to the
1.8 + /// source node the incoming flow should be greater or equal to the
1.9 /// outgoing flow.
1.10 /// \return \c false if the given \c flowMap is not a preflow.
1.11 template <typename FlowMap>
1.12 @@ -495,7 +495,7 @@
1.13 for (OutArcIt e(_graph, n); e != INVALID; ++e) {
1.14 excess -= (*_flow)[e];
1.15 }
1.16 - if (excess < 0 && n != _source) return false;
1.17 + if (_tolerance.negative(excess) && n != _source) return false;
1.18 (*_excess)[n] = excess;
1.19 }
1.20
1.21 @@ -639,7 +639,7 @@
1.22
1.23 (*_excess)[n] = excess;
1.24
1.25 - if (excess != 0) {
1.26 + if (_tolerance.nonZero(excess)) {
1.27 if (new_level + 1 < _level->maxLevel()) {
1.28 _level->liftHighestActive(new_level + 1);
1.29 } else {
1.30 @@ -720,7 +720,7 @@
1.31
1.32 (*_excess)[n] = excess;
1.33
1.34 - if (excess != 0) {
1.35 + if (_tolerance.nonZero(excess)) {
1.36 if (new_level + 1 < _level->maxLevel()) {
1.37 _level->liftActiveOn(level, new_level + 1);
1.38 } else {
1.39 @@ -791,7 +791,7 @@
1.40 for (NodeIt n(_graph); n != INVALID; ++n) {
1.41 if (!reached[n]) {
1.42 _level->dirtyTopButOne(n);
1.43 - } else if ((*_excess)[n] > 0 && _target != n) {
1.44 + } else if (_tolerance.positive((*_excess)[n]) && _target != n) {
1.45 _level->activate(n);
1.46 }
1.47 }
1.48 @@ -852,7 +852,7 @@
1.49
1.50 (*_excess)[n] = excess;
1.51
1.52 - if (excess != 0) {
1.53 + if (_tolerance.nonZero(excess)) {
1.54 if (new_level + 1 < _level->maxLevel()) {
1.55 _level->liftHighestActive(new_level + 1);
1.56 } else {
2.1 --- a/test/max_flow_test.cc Thu Mar 22 18:56:26 2018 +0100
2.2 +++ b/test/max_flow_test.cc Thu Mar 22 18:56:47 2018 +0100
2.3 @@ -66,6 +66,38 @@
2.4 "source 1\n"
2.5 "target 8\n";
2.6
2.7 +char test_lgf_float[] =
2.8 + "@nodes\n"
2.9 + "label\n"
2.10 + "0\n"
2.11 + "1\n"
2.12 + "2\n"
2.13 + "3\n"
2.14 + "4\n"
2.15 + "5\n"
2.16 + "6\n"
2.17 + "7\n"
2.18 + "8\n"
2.19 + "9\n"
2.20 + "@arcs\n"
2.21 + " capacity\n"
2.22 + "0 1 0.1\n"
2.23 + "0 2 0.1\n"
2.24 + "0 3 0.1\n"
2.25 + "1 4 0.1\n"
2.26 + "2 4 0.1\n"
2.27 + "3 4 0.1\n"
2.28 + "4 5 0.3\n"
2.29 + "5 6 0.1\n"
2.30 + "5 7 0.1\n"
2.31 + "5 8 0.1\n"
2.32 + "6 9 0.1\n"
2.33 + "7 9 0.1\n"
2.34 + "8 9 0.1\n"
2.35 + "@attributes\n"
2.36 + "source 0\n"
2.37 + "target 9\n";
2.38 +
2.39 // Checks the general interface of a max flow algorithm
2.40 template <typename GR, typename CAP>
2.41 struct MaxFlowClassConcept
2.42 @@ -258,10 +290,10 @@
2.43 Node s, t;
2.44 CapMap cap(g);
2.45 std::istringstream input(input_lgf);
2.46 - DigraphReader<Digraph>(g,input)
2.47 + DigraphReader<Digraph>(g, input)
2.48 .arcMap("capacity", cap)
2.49 - .node("source",s)
2.50 - .node("target",t)
2.51 + .node("source", s)
2.52 + .node("target", t)
2.53 .run();
2.54
2.55 MF max_flow(g, cap, s, t);
2.56 @@ -280,8 +312,8 @@
2.57 "Incorrect min cut value.");
2.58
2.59 FlowMap flow(g);
2.60 - for (ArcIt e(g); e != INVALID; ++e) flow[e] = max_flow.flowMap()[e];
2.61 - for (ArcIt e(g); e != INVALID; ++e) cap[e] = 2 * cap[e];
2.62 + for (ArcIt e(g); e != INVALID; ++e) flow[e] = 13 * max_flow.flowMap()[e];
2.63 + for (ArcIt e(g); e != INVALID; ++e) cap[e] = 17 * cap[e];
2.64 max_flow.init(flow);
2.65
2.66 SF::startFirstPhase(max_flow); // start first phase of the algorithm
2.67 @@ -290,9 +322,9 @@
2.68 max_flow.minCutMap(min_cut1);
2.69 min_cut_value = cutValue(g, min_cut1, cap);
2.70
2.71 - check(!tol.different(2 * expected, max_flow.flowValue()),
2.72 + check(!tol.different(17 * expected, max_flow.flowValue()),
2.73 "Incorrect max flow value.");
2.74 - check(!tol.different(2 * expected, min_cut_value),
2.75 + check(!tol.different(17 * expected, min_cut_value),
2.76 "Incorrect min cut value.");
2.77
2.78 SF::startSecondPhase(max_flow); // start second phase of the algorithm
2.79 @@ -304,9 +336,9 @@
2.80 max_flow.minCutMap(min_cut2);
2.81 min_cut_value = cutValue(g, min_cut2, cap);
2.82
2.83 - check(!tol.different(2 * expected, max_flow.flowValue()),
2.84 + check(!tol.different(17 * expected, max_flow.flowValue()),
2.85 "Incorrect max flow value.");
2.86 - check(!tol.different(2 * expected, min_cut_value),
2.87 + check(!tol.different(17 * expected, min_cut_value),
2.88 "Incorrect min cut value.");
2.89
2.90 max_flow.flowMap(flow);
2.91 @@ -382,19 +414,27 @@
2.92 typedef Preflow<SmartDigraph, SmartDigraph::ArcMap<int> > PType1;
2.93 typedef Preflow<SmartDigraph, SmartDigraph::ArcMap<float> > PType2;
2.94 typedef Preflow<SmartDigraph, SmartDigraph::ArcMap<double> > PType3;
2.95 +
2.96 checkMaxFlowAlg<PType1, PreflowStartFunctions<PType1> >(test_lgf, 13);
2.97 checkMaxFlowAlg<PType2, PreflowStartFunctions<PType2> >(test_lgf, 13);
2.98 checkMaxFlowAlg<PType3, PreflowStartFunctions<PType3> >(test_lgf, 13);
2.99
2.100 + checkMaxFlowAlg<PType2, PreflowStartFunctions<PType2> >(test_lgf_float, 0.3);
2.101 + checkMaxFlowAlg<PType3, PreflowStartFunctions<PType3> >(test_lgf_float, 0.3);
2.102 +
2.103 checkInitPreflow();
2.104
2.105 // Check EdmondsKarp
2.106 typedef EdmondsKarp<SmartDigraph, SmartDigraph::ArcMap<int> > EKType1;
2.107 typedef EdmondsKarp<SmartDigraph, SmartDigraph::ArcMap<float> > EKType2;
2.108 typedef EdmondsKarp<SmartDigraph, SmartDigraph::ArcMap<double> > EKType3;
2.109 +
2.110 checkMaxFlowAlg<EKType1, GeneralStartFunctions<EKType1> >(test_lgf, 13);
2.111 checkMaxFlowAlg<EKType2, GeneralStartFunctions<EKType2> >(test_lgf, 13);
2.112 checkMaxFlowAlg<EKType3, GeneralStartFunctions<EKType3> >(test_lgf, 13);
2.113
2.114 + checkMaxFlowAlg<EKType2, GeneralStartFunctions<EKType2> >(test_lgf_float, 0.3);
2.115 + checkMaxFlowAlg<EKType3, GeneralStartFunctions<EKType3> >(test_lgf_float, 0.3);
2.116 +
2.117 return 0;
2.118 }