1.1 --- a/lemon/preflow.h Wed Oct 17 18:56:08 2018 +0200
1.2 +++ b/lemon/preflow.h Wed Oct 17 18:56:32 2018 +0200
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 Wed Oct 17 18:56:08 2018 +0200
2.2 +++ b/test/max_flow_test.cc Wed Oct 17 18:56:32 2018 +0200
2.3 @@ -26,6 +26,7 @@
2.4 #include <lemon/concepts/maps.h>
2.5 #include <lemon/lgf_reader.h>
2.6 #include <lemon/elevator.h>
2.7 +#include <lemon/tolerance.h>
2.8
2.9 using namespace lemon;
2.10
2.11 @@ -65,6 +66,37 @@
2.12 "source 1\n"
2.13 "target 8\n";
2.14
2.15 +char test_lgf_float[] =
2.16 + "@nodes\n"
2.17 + "label\n"
2.18 + "0\n"
2.19 + "1\n"
2.20 + "2\n"
2.21 + "3\n"
2.22 + "4\n"
2.23 + "5\n"
2.24 + "6\n"
2.25 + "7\n"
2.26 + "8\n"
2.27 + "9\n"
2.28 + "@arcs\n"
2.29 + " capacity\n"
2.30 + "0 1 0.1\n"
2.31 + "0 2 0.1\n"
2.32 + "0 3 0.1\n"
2.33 + "1 4 0.1\n"
2.34 + "2 4 0.1\n"
2.35 + "3 4 0.1\n"
2.36 + "4 5 0.3\n"
2.37 + "5 6 0.1\n"
2.38 + "5 7 0.1\n"
2.39 + "5 8 0.1\n"
2.40 + "6 9 0.1\n"
2.41 + "7 9 0.1\n"
2.42 + "8 9 0.1\n"
2.43 + "@attributes\n"
2.44 + "source 0\n"
2.45 + "target 9\n";
2.46
2.47 // Checks the general interface of a max flow algorithm
2.48 template <typename GR, typename CAP>
2.49 @@ -165,8 +197,6 @@
2.50 typedef int Value;
2.51 typedef concepts::Digraph Digraph;
2.52 typedef concepts::ReadMap<Digraph::Arc, Value> CapMap;
2.53 - typedef Elevator<Digraph, Digraph::Node> Elev;
2.54 - typedef LinkedElevator<Digraph, Digraph::Node> LinkedElev;
2.55
2.56 Digraph g;
2.57 Digraph::Node n;
2.58 @@ -184,13 +214,13 @@
2.59
2.60
2.61 template <typename T>
2.62 -T cutValue (const SmartDigraph& g,
2.63 - const SmartDigraph::NodeMap<bool>& cut,
2.64 - const SmartDigraph::ArcMap<T>& cap) {
2.65 +T cutValue(const SmartDigraph& g,
2.66 + const SmartDigraph::NodeMap<bool>& cut,
2.67 + const SmartDigraph::ArcMap<T>& cap) {
2.68
2.69 - T c=0;
2.70 - for(SmartDigraph::ArcIt e(g); e!=INVALID; ++e) {
2.71 - if (cut[g.source(e)] && !cut[g.target(e)]) c+=cap[e];
2.72 + T c = 0;
2.73 + for (SmartDigraph::ArcIt e(g); e != INVALID; ++e) {
2.74 + if (cut[g.source(e)] && !cut[g.target(e)]) c += cap[e];
2.75 }
2.76 return c;
2.77 }
2.78 @@ -199,10 +229,11 @@
2.79 bool checkFlow(const SmartDigraph& g,
2.80 const SmartDigraph::ArcMap<T>& flow,
2.81 const SmartDigraph::ArcMap<T>& cap,
2.82 - SmartDigraph::Node s, SmartDigraph::Node t) {
2.83 + SmartDigraph::Node s, SmartDigraph::Node t,
2.84 + const Tolerance<T>& tol) {
2.85
2.86 for (SmartDigraph::ArcIt e(g); e != INVALID; ++e) {
2.87 - if (flow[e] < 0 || flow[e] > cap[e]) return false;
2.88 + if (tol.negative(flow[e]) || tol.less(cap[e], flow[e])) return false;
2.89 }
2.90
2.91 for (SmartDigraph::NodeIt n(g); n != INVALID; ++n) {
2.92 @@ -214,28 +245,29 @@
2.93 for (SmartDigraph::InArcIt e(g, n); e != INVALID; ++e) {
2.94 sum -= flow[e];
2.95 }
2.96 - if (sum != 0) return false;
2.97 + if (tol.nonZero(sum)) return false;
2.98 }
2.99 return true;
2.100 }
2.101
2.102 -void initFlowTest()
2.103 +void checkInitPreflow()
2.104 {
2.105 DIGRAPH_TYPEDEFS(SmartDigraph);
2.106
2.107 SmartDigraph g;
2.108 - SmartDigraph::ArcMap<int> cap(g),iflow(g);
2.109 - Node s=g.addNode(); Node t=g.addNode();
2.110 - Node n1=g.addNode(); Node n2=g.addNode();
2.111 + SmartDigraph::ArcMap<int> cap(g), iflow(g);
2.112 + Node s = g.addNode(); Node t = g.addNode();
2.113 + Node n1 = g.addNode(); Node n2 = g.addNode();
2.114 Arc a;
2.115 - a=g.addArc(s,n1); cap[a]=20; iflow[a]=20;
2.116 - a=g.addArc(n1,n2); cap[a]=10; iflow[a]=0;
2.117 - a=g.addArc(n2,t); cap[a]=20; iflow[a]=0;
2.118 + a = g.addArc(s, n1); cap[a] = 20; iflow[a] = 20;
2.119 + a = g.addArc(n1, n2); cap[a] = 10; iflow[a] = 0;
2.120 + a = g.addArc(n2, t); cap[a] = 20; iflow[a] = 0;
2.121
2.122 - Preflow<SmartDigraph> pre(g,cap,s,t);
2.123 + Preflow<SmartDigraph> pre(g, cap, s, t);
2.124 pre.init(iflow);
2.125 pre.startFirstPhase();
2.126 - check(pre.flowValue() == 10, "The incorrect max flow value.");
2.127 +
2.128 + check(pre.flowValue() == 10, "Incorrect max flow value.");
2.129 check(pre.minCut(s), "Wrong min cut (Node s).");
2.130 check(pre.minCut(n1), "Wrong min cut (Node n1).");
2.131 check(!pre.minCut(n2), "Wrong min cut (Node n2).");
2.132 @@ -243,7 +275,7 @@
2.133 }
2.134
2.135 template <typename MF, typename SF>
2.136 -void checkMaxFlowAlg() {
2.137 +void checkMaxFlowAlg(const char *input_lgf, typename MF::Value expected) {
2.138 typedef SmartDigraph Digraph;
2.139 DIGRAPH_TYPEDEFS(Digraph);
2.140
2.141 @@ -252,35 +284,36 @@
2.142 typedef CapMap FlowMap;
2.143 typedef BoolNodeMap CutMap;
2.144
2.145 + Tolerance<Value> tol;
2.146 +
2.147 Digraph g;
2.148 Node s, t;
2.149 CapMap cap(g);
2.150 - std::istringstream input(test_lgf);
2.151 - DigraphReader<Digraph>(g,input)
2.152 + std::istringstream input(input_lgf);
2.153 + DigraphReader<Digraph>(g, input)
2.154 .arcMap("capacity", cap)
2.155 - .node("source",s)
2.156 - .node("target",t)
2.157 + .node("source", s)
2.158 + .node("target", t)
2.159 .run();
2.160
2.161 MF max_flow(g, cap, s, t);
2.162 max_flow.run();
2.163
2.164 - check(checkFlow(g, max_flow.flowMap(), cap, s, t),
2.165 + check(!tol.different(expected, max_flow.flowValue()),
2.166 + "Incorrect max flow value.");
2.167 + check(checkFlow(g, max_flow.flowMap(), cap, s, t, tol),
2.168 "The flow is not feasible.");
2.169
2.170 CutMap min_cut(g);
2.171 max_flow.minCutMap(min_cut);
2.172 Value min_cut_value = cutValue(g, min_cut, cap);
2.173
2.174 - check(max_flow.flowValue() == min_cut_value,
2.175 - "The max flow value is not equal to the min cut value.");
2.176 + check(!tol.different(expected, min_cut_value),
2.177 + "Incorrect min cut value.");
2.178
2.179 FlowMap flow(g);
2.180 - for (ArcIt e(g); e != INVALID; ++e) flow[e] = max_flow.flowMap()[e];
2.181 -
2.182 - Value flow_value = max_flow.flowValue();
2.183 -
2.184 - for (ArcIt e(g); e != INVALID; ++e) cap[e] = 2 * cap[e];
2.185 + for (ArcIt e(g); e != INVALID; ++e) flow[e] = 13 * max_flow.flowMap()[e];
2.186 + for (ArcIt e(g); e != INVALID; ++e) cap[e] = 17 * cap[e];
2.187 max_flow.init(flow);
2.188
2.189 SF::startFirstPhase(max_flow); // start first phase of the algorithm
2.190 @@ -289,23 +322,24 @@
2.191 max_flow.minCutMap(min_cut1);
2.192 min_cut_value = cutValue(g, min_cut1, cap);
2.193
2.194 - check(max_flow.flowValue() == min_cut_value &&
2.195 - min_cut_value == 2 * flow_value,
2.196 - "The max flow value or the min cut value is wrong.");
2.197 + check(!tol.different(17 * expected, max_flow.flowValue()),
2.198 + "Incorrect max flow value.");
2.199 + check(!tol.different(17 * expected, min_cut_value),
2.200 + "Incorrect min cut value.");
2.201
2.202 SF::startSecondPhase(max_flow); // start second phase of the algorithm
2.203
2.204 - check(checkFlow(g, max_flow.flowMap(), cap, s, t),
2.205 + check(checkFlow(g, max_flow.flowMap(), cap, s, t, tol),
2.206 "The flow is not feasible.");
2.207
2.208 CutMap min_cut2(g);
2.209 max_flow.minCutMap(min_cut2);
2.210 min_cut_value = cutValue(g, min_cut2, cap);
2.211
2.212 - check(max_flow.flowValue() == min_cut_value &&
2.213 - min_cut_value == 2 * flow_value,
2.214 - "The max flow value or the min cut value was not doubled");
2.215 -
2.216 + check(!tol.different(17 * expected, max_flow.flowValue()),
2.217 + "Incorrect max flow value.");
2.218 + check(!tol.different(17 * expected, min_cut_value),
2.219 + "Incorrect min cut value.");
2.220
2.221 max_flow.flowMap(flow);
2.222
2.223 @@ -324,9 +358,9 @@
2.224
2.225 CutMap min_cut3(g);
2.226 max_flow.minCutMap(min_cut3);
2.227 - min_cut_value=cutValue(g, min_cut3, cap);
2.228 + min_cut_value = cutValue(g, min_cut3, cap);
2.229
2.230 - check(max_flow.flowValue() == min_cut_value,
2.231 + check(!tol.different(max_flow.flowValue(), min_cut_value),
2.232 "The max flow value or the min cut value is wrong.");
2.233 }
2.234
2.235 @@ -379,17 +413,28 @@
2.236 // Check Preflow
2.237 typedef Preflow<SmartDigraph, SmartDigraph::ArcMap<int> > PType1;
2.238 typedef Preflow<SmartDigraph, SmartDigraph::ArcMap<float> > PType2;
2.239 - checkMaxFlowAlg<PType1, PreflowStartFunctions<PType1> >();
2.240 - checkMaxFlowAlg<PType2, PreflowStartFunctions<PType2> >();
2.241 - initFlowTest();
2.242 + typedef Preflow<SmartDigraph, SmartDigraph::ArcMap<double> > PType3;
2.243 +
2.244 + checkMaxFlowAlg<PType1, PreflowStartFunctions<PType1> >(test_lgf, 13);
2.245 + checkMaxFlowAlg<PType2, PreflowStartFunctions<PType2> >(test_lgf, 13);
2.246 + checkMaxFlowAlg<PType3, PreflowStartFunctions<PType3> >(test_lgf, 13);
2.247 +
2.248 + checkMaxFlowAlg<PType2, PreflowStartFunctions<PType2> >(test_lgf_float, 0.3);
2.249 + checkMaxFlowAlg<PType3, PreflowStartFunctions<PType3> >(test_lgf_float, 0.3);
2.250 +
2.251 + checkInitPreflow();
2.252
2.253 // Check EdmondsKarp
2.254 typedef EdmondsKarp<SmartDigraph, SmartDigraph::ArcMap<int> > EKType1;
2.255 typedef EdmondsKarp<SmartDigraph, SmartDigraph::ArcMap<float> > EKType2;
2.256 - checkMaxFlowAlg<EKType1, GeneralStartFunctions<EKType1> >();
2.257 - checkMaxFlowAlg<EKType2, GeneralStartFunctions<EKType2> >();
2.258 + typedef EdmondsKarp<SmartDigraph, SmartDigraph::ArcMap<double> > EKType3;
2.259
2.260 - initFlowTest();
2.261 + checkMaxFlowAlg<EKType1, GeneralStartFunctions<EKType1> >(test_lgf, 13);
2.262 + checkMaxFlowAlg<EKType2, GeneralStartFunctions<EKType2> >(test_lgf, 13);
2.263 + checkMaxFlowAlg<EKType3, GeneralStartFunctions<EKType3> >(test_lgf, 13);
2.264 +
2.265 + checkMaxFlowAlg<EKType2, GeneralStartFunctions<EKType2> >(test_lgf_float, 0.3);
2.266 + checkMaxFlowAlg<EKType3, GeneralStartFunctions<EKType3> >(test_lgf_float, 0.3);
2.267
2.268 return 0;
2.269 }