1.1 --- a/test/max_flow_test.cc Wed Oct 17 18:56:08 2018 +0200
1.2 +++ b/test/max_flow_test.cc Wed Oct 17 18:56:32 2018 +0200
1.3 @@ -26,6 +26,7 @@
1.4 #include <lemon/concepts/maps.h>
1.5 #include <lemon/lgf_reader.h>
1.6 #include <lemon/elevator.h>
1.7 +#include <lemon/tolerance.h>
1.8
1.9 using namespace lemon;
1.10
1.11 @@ -65,6 +66,37 @@
1.12 "source 1\n"
1.13 "target 8\n";
1.14
1.15 +char test_lgf_float[] =
1.16 + "@nodes\n"
1.17 + "label\n"
1.18 + "0\n"
1.19 + "1\n"
1.20 + "2\n"
1.21 + "3\n"
1.22 + "4\n"
1.23 + "5\n"
1.24 + "6\n"
1.25 + "7\n"
1.26 + "8\n"
1.27 + "9\n"
1.28 + "@arcs\n"
1.29 + " capacity\n"
1.30 + "0 1 0.1\n"
1.31 + "0 2 0.1\n"
1.32 + "0 3 0.1\n"
1.33 + "1 4 0.1\n"
1.34 + "2 4 0.1\n"
1.35 + "3 4 0.1\n"
1.36 + "4 5 0.3\n"
1.37 + "5 6 0.1\n"
1.38 + "5 7 0.1\n"
1.39 + "5 8 0.1\n"
1.40 + "6 9 0.1\n"
1.41 + "7 9 0.1\n"
1.42 + "8 9 0.1\n"
1.43 + "@attributes\n"
1.44 + "source 0\n"
1.45 + "target 9\n";
1.46
1.47 // Checks the general interface of a max flow algorithm
1.48 template <typename GR, typename CAP>
1.49 @@ -165,8 +197,6 @@
1.50 typedef int Value;
1.51 typedef concepts::Digraph Digraph;
1.52 typedef concepts::ReadMap<Digraph::Arc, Value> CapMap;
1.53 - typedef Elevator<Digraph, Digraph::Node> Elev;
1.54 - typedef LinkedElevator<Digraph, Digraph::Node> LinkedElev;
1.55
1.56 Digraph g;
1.57 Digraph::Node n;
1.58 @@ -184,13 +214,13 @@
1.59
1.60
1.61 template <typename T>
1.62 -T cutValue (const SmartDigraph& g,
1.63 - const SmartDigraph::NodeMap<bool>& cut,
1.64 - const SmartDigraph::ArcMap<T>& cap) {
1.65 +T cutValue(const SmartDigraph& g,
1.66 + const SmartDigraph::NodeMap<bool>& cut,
1.67 + const SmartDigraph::ArcMap<T>& cap) {
1.68
1.69 - T c=0;
1.70 - for(SmartDigraph::ArcIt e(g); e!=INVALID; ++e) {
1.71 - if (cut[g.source(e)] && !cut[g.target(e)]) c+=cap[e];
1.72 + T c = 0;
1.73 + for (SmartDigraph::ArcIt e(g); e != INVALID; ++e) {
1.74 + if (cut[g.source(e)] && !cut[g.target(e)]) c += cap[e];
1.75 }
1.76 return c;
1.77 }
1.78 @@ -199,10 +229,11 @@
1.79 bool checkFlow(const SmartDigraph& g,
1.80 const SmartDigraph::ArcMap<T>& flow,
1.81 const SmartDigraph::ArcMap<T>& cap,
1.82 - SmartDigraph::Node s, SmartDigraph::Node t) {
1.83 + SmartDigraph::Node s, SmartDigraph::Node t,
1.84 + const Tolerance<T>& tol) {
1.85
1.86 for (SmartDigraph::ArcIt e(g); e != INVALID; ++e) {
1.87 - if (flow[e] < 0 || flow[e] > cap[e]) return false;
1.88 + if (tol.negative(flow[e]) || tol.less(cap[e], flow[e])) return false;
1.89 }
1.90
1.91 for (SmartDigraph::NodeIt n(g); n != INVALID; ++n) {
1.92 @@ -214,28 +245,29 @@
1.93 for (SmartDigraph::InArcIt e(g, n); e != INVALID; ++e) {
1.94 sum -= flow[e];
1.95 }
1.96 - if (sum != 0) return false;
1.97 + if (tol.nonZero(sum)) return false;
1.98 }
1.99 return true;
1.100 }
1.101
1.102 -void initFlowTest()
1.103 +void checkInitPreflow()
1.104 {
1.105 DIGRAPH_TYPEDEFS(SmartDigraph);
1.106
1.107 SmartDigraph g;
1.108 - SmartDigraph::ArcMap<int> cap(g),iflow(g);
1.109 - Node s=g.addNode(); Node t=g.addNode();
1.110 - Node n1=g.addNode(); Node n2=g.addNode();
1.111 + SmartDigraph::ArcMap<int> cap(g), iflow(g);
1.112 + Node s = g.addNode(); Node t = g.addNode();
1.113 + Node n1 = g.addNode(); Node n2 = g.addNode();
1.114 Arc a;
1.115 - a=g.addArc(s,n1); cap[a]=20; iflow[a]=20;
1.116 - a=g.addArc(n1,n2); cap[a]=10; iflow[a]=0;
1.117 - a=g.addArc(n2,t); cap[a]=20; iflow[a]=0;
1.118 + a = g.addArc(s, n1); cap[a] = 20; iflow[a] = 20;
1.119 + a = g.addArc(n1, n2); cap[a] = 10; iflow[a] = 0;
1.120 + a = g.addArc(n2, t); cap[a] = 20; iflow[a] = 0;
1.121
1.122 - Preflow<SmartDigraph> pre(g,cap,s,t);
1.123 + Preflow<SmartDigraph> pre(g, cap, s, t);
1.124 pre.init(iflow);
1.125 pre.startFirstPhase();
1.126 - check(pre.flowValue() == 10, "The incorrect max flow value.");
1.127 +
1.128 + check(pre.flowValue() == 10, "Incorrect max flow value.");
1.129 check(pre.minCut(s), "Wrong min cut (Node s).");
1.130 check(pre.minCut(n1), "Wrong min cut (Node n1).");
1.131 check(!pre.minCut(n2), "Wrong min cut (Node n2).");
1.132 @@ -243,7 +275,7 @@
1.133 }
1.134
1.135 template <typename MF, typename SF>
1.136 -void checkMaxFlowAlg() {
1.137 +void checkMaxFlowAlg(const char *input_lgf, typename MF::Value expected) {
1.138 typedef SmartDigraph Digraph;
1.139 DIGRAPH_TYPEDEFS(Digraph);
1.140
1.141 @@ -252,35 +284,36 @@
1.142 typedef CapMap FlowMap;
1.143 typedef BoolNodeMap CutMap;
1.144
1.145 + Tolerance<Value> tol;
1.146 +
1.147 Digraph g;
1.148 Node s, t;
1.149 CapMap cap(g);
1.150 - std::istringstream input(test_lgf);
1.151 - DigraphReader<Digraph>(g,input)
1.152 + std::istringstream input(input_lgf);
1.153 + DigraphReader<Digraph>(g, input)
1.154 .arcMap("capacity", cap)
1.155 - .node("source",s)
1.156 - .node("target",t)
1.157 + .node("source", s)
1.158 + .node("target", t)
1.159 .run();
1.160
1.161 MF max_flow(g, cap, s, t);
1.162 max_flow.run();
1.163
1.164 - check(checkFlow(g, max_flow.flowMap(), cap, s, t),
1.165 + check(!tol.different(expected, max_flow.flowValue()),
1.166 + "Incorrect max flow value.");
1.167 + check(checkFlow(g, max_flow.flowMap(), cap, s, t, tol),
1.168 "The flow is not feasible.");
1.169
1.170 CutMap min_cut(g);
1.171 max_flow.minCutMap(min_cut);
1.172 Value min_cut_value = cutValue(g, min_cut, cap);
1.173
1.174 - check(max_flow.flowValue() == min_cut_value,
1.175 - "The max flow value is not equal to the min cut value.");
1.176 + check(!tol.different(expected, min_cut_value),
1.177 + "Incorrect min cut value.");
1.178
1.179 FlowMap flow(g);
1.180 - for (ArcIt e(g); e != INVALID; ++e) flow[e] = max_flow.flowMap()[e];
1.181 -
1.182 - Value flow_value = max_flow.flowValue();
1.183 -
1.184 - for (ArcIt e(g); e != INVALID; ++e) cap[e] = 2 * cap[e];
1.185 + for (ArcIt e(g); e != INVALID; ++e) flow[e] = 13 * max_flow.flowMap()[e];
1.186 + for (ArcIt e(g); e != INVALID; ++e) cap[e] = 17 * cap[e];
1.187 max_flow.init(flow);
1.188
1.189 SF::startFirstPhase(max_flow); // start first phase of the algorithm
1.190 @@ -289,23 +322,24 @@
1.191 max_flow.minCutMap(min_cut1);
1.192 min_cut_value = cutValue(g, min_cut1, cap);
1.193
1.194 - check(max_flow.flowValue() == min_cut_value &&
1.195 - min_cut_value == 2 * flow_value,
1.196 - "The max flow value or the min cut value is wrong.");
1.197 + check(!tol.different(17 * expected, max_flow.flowValue()),
1.198 + "Incorrect max flow value.");
1.199 + check(!tol.different(17 * expected, min_cut_value),
1.200 + "Incorrect min cut value.");
1.201
1.202 SF::startSecondPhase(max_flow); // start second phase of the algorithm
1.203
1.204 - check(checkFlow(g, max_flow.flowMap(), cap, s, t),
1.205 + check(checkFlow(g, max_flow.flowMap(), cap, s, t, tol),
1.206 "The flow is not feasible.");
1.207
1.208 CutMap min_cut2(g);
1.209 max_flow.minCutMap(min_cut2);
1.210 min_cut_value = cutValue(g, min_cut2, cap);
1.211
1.212 - check(max_flow.flowValue() == min_cut_value &&
1.213 - min_cut_value == 2 * flow_value,
1.214 - "The max flow value or the min cut value was not doubled");
1.215 -
1.216 + check(!tol.different(17 * expected, max_flow.flowValue()),
1.217 + "Incorrect max flow value.");
1.218 + check(!tol.different(17 * expected, min_cut_value),
1.219 + "Incorrect min cut value.");
1.220
1.221 max_flow.flowMap(flow);
1.222
1.223 @@ -324,9 +358,9 @@
1.224
1.225 CutMap min_cut3(g);
1.226 max_flow.minCutMap(min_cut3);
1.227 - min_cut_value=cutValue(g, min_cut3, cap);
1.228 + min_cut_value = cutValue(g, min_cut3, cap);
1.229
1.230 - check(max_flow.flowValue() == min_cut_value,
1.231 + check(!tol.different(max_flow.flowValue(), min_cut_value),
1.232 "The max flow value or the min cut value is wrong.");
1.233 }
1.234
1.235 @@ -379,17 +413,28 @@
1.236 // Check Preflow
1.237 typedef Preflow<SmartDigraph, SmartDigraph::ArcMap<int> > PType1;
1.238 typedef Preflow<SmartDigraph, SmartDigraph::ArcMap<float> > PType2;
1.239 - checkMaxFlowAlg<PType1, PreflowStartFunctions<PType1> >();
1.240 - checkMaxFlowAlg<PType2, PreflowStartFunctions<PType2> >();
1.241 - initFlowTest();
1.242 + typedef Preflow<SmartDigraph, SmartDigraph::ArcMap<double> > PType3;
1.243 +
1.244 + checkMaxFlowAlg<PType1, PreflowStartFunctions<PType1> >(test_lgf, 13);
1.245 + checkMaxFlowAlg<PType2, PreflowStartFunctions<PType2> >(test_lgf, 13);
1.246 + checkMaxFlowAlg<PType3, PreflowStartFunctions<PType3> >(test_lgf, 13);
1.247 +
1.248 + checkMaxFlowAlg<PType2, PreflowStartFunctions<PType2> >(test_lgf_float, 0.3);
1.249 + checkMaxFlowAlg<PType3, PreflowStartFunctions<PType3> >(test_lgf_float, 0.3);
1.250 +
1.251 + checkInitPreflow();
1.252
1.253 // Check EdmondsKarp
1.254 typedef EdmondsKarp<SmartDigraph, SmartDigraph::ArcMap<int> > EKType1;
1.255 typedef EdmondsKarp<SmartDigraph, SmartDigraph::ArcMap<float> > EKType2;
1.256 - checkMaxFlowAlg<EKType1, GeneralStartFunctions<EKType1> >();
1.257 - checkMaxFlowAlg<EKType2, GeneralStartFunctions<EKType2> >();
1.258 + typedef EdmondsKarp<SmartDigraph, SmartDigraph::ArcMap<double> > EKType3;
1.259
1.260 - initFlowTest();
1.261 + checkMaxFlowAlg<EKType1, GeneralStartFunctions<EKType1> >(test_lgf, 13);
1.262 + checkMaxFlowAlg<EKType2, GeneralStartFunctions<EKType2> >(test_lgf, 13);
1.263 + checkMaxFlowAlg<EKType3, GeneralStartFunctions<EKType3> >(test_lgf, 13);
1.264 +
1.265 + checkMaxFlowAlg<EKType2, GeneralStartFunctions<EKType2> >(test_lgf_float, 0.3);
1.266 + checkMaxFlowAlg<EKType3, GeneralStartFunctions<EKType3> >(test_lgf_float, 0.3);
1.267
1.268 return 0;
1.269 }