1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
3 * This file is a part of LEMON, a generic C++ optimization library.
5 * Copyright (C) 2003-2013
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
9 * Permission to use, modify and distribute this software is granted
10 * provided that this copyright notice appears in all copies. For
11 * precise terms see the accompanying LICENSE file.
13 * This software is provided "AS IS" with no warranty of any kind,
14 * express or implied, and with no claim as to its suitability for any
21 #include "test_tools.h"
22 #include <lemon/smart_graph.h>
23 #include <lemon/preflow.h>
24 #include <lemon/edmonds_karp.h>
25 #include <lemon/concepts/digraph.h>
26 #include <lemon/concepts/maps.h>
27 #include <lemon/lgf_reader.h>
28 #include <lemon/elevator.h>
29 #include <lemon/tolerance.h>
31 using namespace lemon;
69 // Checks the general interface of a max flow algorithm
70 template <typename GR, typename CAP>
71 struct MaxFlowClassConcept
74 template <typename MF>
77 typedef typename GR::Node Node;
78 typedef typename GR::Arc Arc;
79 typedef typename CAP::Value Value;
80 typedef concepts::ReadWriteMap<Arc, Value> FlowMap;
81 typedef concepts::WriteMap<Node, bool> CutMap;
93 checkConcept<concepts::Digraph, GR>();
95 const Constraints& me = *this;
98 ::template SetFlowMap<FlowMap>
100 typedef typename MF::Create MaxFlowType2;
101 MaxFlowType max_flow(me.g, me.cap, me.n, me.n);
102 const MaxFlowType& const_max_flow = max_flow;
110 typename MaxFlowType::Tolerance tol = const_max_flow.tolerance();
111 max_flow.tolerance(tol);
117 v = const_max_flow.flowValue();
118 v = const_max_flow.flow(e);
119 const FlowMap& fm = const_max_flow.flowMap();
121 b = const_max_flow.minCut(n);
122 const_max_flow.minCutMap(cut);
124 ::lemon::ignore_unused_variable_warning(fm);
131 // Checks the specific parts of Preflow's interface
132 void checkPreflowCompile()
135 typedef concepts::Digraph Digraph;
136 typedef concepts::ReadMap<Digraph::Arc, Value> CapMap;
137 typedef Elevator<Digraph, Digraph::Node> Elev;
138 typedef LinkedElevator<Digraph, Digraph::Node> LinkedElev;
144 typedef Preflow<Digraph, CapMap>
146 ::SetStandardElevator<LinkedElev>
147 ::Create PreflowType;
148 PreflowType preflow_test(g, cap, n, n);
149 const PreflowType& const_preflow_test = preflow_test;
151 const PreflowType::Elevator& elev = const_preflow_test.elevator();
152 preflow_test.elevator(const_cast<PreflowType::Elevator&>(elev));
154 bool b = preflow_test.init(cap);
155 preflow_test.startFirstPhase();
156 preflow_test.startSecondPhase();
157 preflow_test.runMinCut();
159 ::lemon::ignore_unused_variable_warning(b);
162 // Checks the specific parts of EdmondsKarp's interface
163 void checkEdmondsKarpCompile()
166 typedef concepts::Digraph Digraph;
167 typedef concepts::ReadMap<Digraph::Arc, Value> CapMap;
173 EdmondsKarp<Digraph, CapMap> ek_test(g, cap, n, n);
176 bool b = ek_test.checkedInit(cap);
177 b = ek_test.augment();
180 ::lemon::ignore_unused_variable_warning(b);
184 template <typename T>
185 T cutValue(const SmartDigraph& g,
186 const SmartDigraph::NodeMap<bool>& cut,
187 const SmartDigraph::ArcMap<T>& cap) {
190 for (SmartDigraph::ArcIt e(g); e != INVALID; ++e) {
191 if (cut[g.source(e)] && !cut[g.target(e)]) c += cap[e];
196 template <typename T>
197 bool checkFlow(const SmartDigraph& g,
198 const SmartDigraph::ArcMap<T>& flow,
199 const SmartDigraph::ArcMap<T>& cap,
200 SmartDigraph::Node s, SmartDigraph::Node t,
201 const Tolerance<T>& tol) {
203 for (SmartDigraph::ArcIt e(g); e != INVALID; ++e) {
204 if (tol.negative(flow[e]) || tol.less(cap[e], flow[e])) return false;
207 for (SmartDigraph::NodeIt n(g); n != INVALID; ++n) {
208 if (n == s || n == t) continue;
210 for (SmartDigraph::OutArcIt e(g, n); e != INVALID; ++e) {
213 for (SmartDigraph::InArcIt e(g, n); e != INVALID; ++e) {
216 if (tol.nonZero(sum)) return false;
221 void checkInitPreflow()
223 DIGRAPH_TYPEDEFS(SmartDigraph);
226 SmartDigraph::ArcMap<int> cap(g), iflow(g);
227 Node s = g.addNode(); Node t = g.addNode();
228 Node n1 = g.addNode(); Node n2 = g.addNode();
230 a = g.addArc(s, n1); cap[a] = 20; iflow[a] = 20;
231 a = g.addArc(n1, n2); cap[a] = 10; iflow[a] = 0;
232 a = g.addArc(n2, t); cap[a] = 20; iflow[a] = 0;
234 Preflow<SmartDigraph> pre(g, cap, s, t);
236 pre.startFirstPhase();
238 check(pre.flowValue() == 10, "Incorrect max flow value.");
239 check(pre.minCut(s), "Wrong min cut (Node s).");
240 check(pre.minCut(n1), "Wrong min cut (Node n1).");
241 check(!pre.minCut(n2), "Wrong min cut (Node n2).");
242 check(!pre.minCut(t), "Wrong min cut (Node t).");
245 template <typename MF, typename SF>
246 void checkMaxFlowAlg(const char *input_lgf, typename MF::Value expected) {
247 typedef SmartDigraph Digraph;
248 DIGRAPH_TYPEDEFS(Digraph);
250 typedef typename MF::Value Value;
251 typedef Digraph::ArcMap<Value> CapMap;
252 typedef CapMap FlowMap;
253 typedef BoolNodeMap CutMap;
255 Tolerance<Value> tol;
260 std::istringstream input(input_lgf);
261 DigraphReader<Digraph>(g,input)
262 .arcMap("capacity", cap)
267 MF max_flow(g, cap, s, t);
270 check(!tol.different(expected, max_flow.flowValue()),
271 "Incorrect max flow value.");
272 check(checkFlow(g, max_flow.flowMap(), cap, s, t, tol),
273 "The flow is not feasible.");
276 max_flow.minCutMap(min_cut);
277 Value min_cut_value = cutValue(g, min_cut, cap);
279 check(!tol.different(expected, min_cut_value),
280 "Incorrect min cut value.");
283 for (ArcIt e(g); e != INVALID; ++e) flow[e] = max_flow.flowMap()[e];
284 for (ArcIt e(g); e != INVALID; ++e) cap[e] = 2 * cap[e];
287 SF::startFirstPhase(max_flow); // start first phase of the algorithm
290 max_flow.minCutMap(min_cut1);
291 min_cut_value = cutValue(g, min_cut1, cap);
293 check(!tol.different(2 * expected, max_flow.flowValue()),
294 "Incorrect max flow value.");
295 check(!tol.different(2 * expected, min_cut_value),
296 "Incorrect min cut value.");
298 SF::startSecondPhase(max_flow); // start second phase of the algorithm
300 check(checkFlow(g, max_flow.flowMap(), cap, s, t, tol),
301 "The flow is not feasible.");
304 max_flow.minCutMap(min_cut2);
305 min_cut_value = cutValue(g, min_cut2, cap);
307 check(!tol.different(2 * expected, max_flow.flowValue()),
308 "Incorrect max flow value.");
309 check(!tol.different(2 * expected, min_cut_value),
310 "Incorrect min cut value.");
312 max_flow.flowMap(flow);
316 if (tmp1 != INVALID) s = tmp1;
320 if (tmp2 != INVALID) t = tmp2;
328 max_flow.minCutMap(min_cut3);
329 min_cut_value = cutValue(g, min_cut3, cap);
331 check(!tol.different(max_flow.flowValue(), min_cut_value),
332 "The max flow value or the min cut value is wrong.");
335 // Struct for calling start functions of a general max flow algorithm
336 template <typename MF>
337 struct GeneralStartFunctions {
339 static void startFirstPhase(MF& mf) {
343 static void startSecondPhase(MF& mf) {
344 ::lemon::ignore_unused_variable_warning(mf);
349 // Struct for calling start functions of Preflow
350 template <typename MF>
351 struct PreflowStartFunctions {
353 static void startFirstPhase(MF& mf) {
354 mf.startFirstPhase();
357 static void startSecondPhase(MF& mf) {
358 mf.startSecondPhase();
365 typedef concepts::Digraph GR;
366 typedef concepts::ReadMap<GR::Arc, int> CM1;
367 typedef concepts::ReadMap<GR::Arc, double> CM2;
369 // Check the interface of Preflow
370 checkConcept< MaxFlowClassConcept<GR, CM1>,
371 Preflow<GR, CM1> >();
372 checkConcept< MaxFlowClassConcept<GR, CM2>,
373 Preflow<GR, CM2> >();
375 // Check the interface of EdmondsKarp
376 checkConcept< MaxFlowClassConcept<GR, CM1>,
377 EdmondsKarp<GR, CM1> >();
378 checkConcept< MaxFlowClassConcept<GR, CM2>,
379 EdmondsKarp<GR, CM2> >();
382 typedef Preflow<SmartDigraph, SmartDigraph::ArcMap<int> > PType1;
383 typedef Preflow<SmartDigraph, SmartDigraph::ArcMap<float> > PType2;
384 typedef Preflow<SmartDigraph, SmartDigraph::ArcMap<double> > PType3;
385 checkMaxFlowAlg<PType1, PreflowStartFunctions<PType1> >(test_lgf, 13);
386 checkMaxFlowAlg<PType2, PreflowStartFunctions<PType2> >(test_lgf, 13);
387 checkMaxFlowAlg<PType3, PreflowStartFunctions<PType3> >(test_lgf, 13);
392 typedef EdmondsKarp<SmartDigraph, SmartDigraph::ArcMap<int> > EKType1;
393 typedef EdmondsKarp<SmartDigraph, SmartDigraph::ArcMap<float> > EKType2;
394 typedef EdmondsKarp<SmartDigraph, SmartDigraph::ArcMap<double> > EKType3;
395 checkMaxFlowAlg<EKType1, GeneralStartFunctions<EKType1> >(test_lgf, 13);
396 checkMaxFlowAlg<EKType2, GeneralStartFunctions<EKType2> >(test_lgf, 13);
397 checkMaxFlowAlg<EKType3, GeneralStartFunctions<EKType3> >(test_lgf, 13);