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() {
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(test_lgf);
261 DigraphReader<Digraph>(g,input)
262 .arcMap("capacity", cap)
267 MF max_flow(g, cap, s, t);
270 check(checkFlow(g, max_flow.flowMap(), cap, s, t, tol),
271 "The flow is not feasible.");
274 max_flow.minCutMap(min_cut);
275 Value min_cut_value = cutValue(g, min_cut, cap);
277 check(!tol.different(max_flow.flowValue(), min_cut_value),
278 "The max flow value is not equal to the min cut value.");
281 for (ArcIt e(g); e != INVALID; ++e) flow[e] = max_flow.flowMap()[e];
283 Value flow_value = max_flow.flowValue();
285 for (ArcIt e(g); e != INVALID; ++e) cap[e] = 2 * cap[e];
288 SF::startFirstPhase(max_flow); // start first phase of the algorithm
291 max_flow.minCutMap(min_cut1);
292 min_cut_value = cutValue(g, min_cut1, cap);
294 check(!tol.different(max_flow.flowValue(), min_cut_value) &&
295 !tol.different(min_cut_value, 2 * flow_value),
296 "The max flow value or the min cut value is wrong.");
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(max_flow.flowValue(), min_cut_value) &&
308 !tol.different(min_cut_value, 2 * flow_value),
309 "The max flow value or the min cut value was not doubled.");
311 max_flow.flowMap(flow);
315 if (tmp1 != INVALID) s = tmp1;
319 if (tmp2 != INVALID) t = tmp2;
327 max_flow.minCutMap(min_cut3);
328 min_cut_value = cutValue(g, min_cut3, cap);
330 check(!tol.different(max_flow.flowValue(), min_cut_value),
331 "The max flow value or the min cut value is wrong.");
334 // Struct for calling start functions of a general max flow algorithm
335 template <typename MF>
336 struct GeneralStartFunctions {
338 static void startFirstPhase(MF& mf) {
342 static void startSecondPhase(MF& mf) {
343 ::lemon::ignore_unused_variable_warning(mf);
348 // Struct for calling start functions of Preflow
349 template <typename MF>
350 struct PreflowStartFunctions {
352 static void startFirstPhase(MF& mf) {
353 mf.startFirstPhase();
356 static void startSecondPhase(MF& mf) {
357 mf.startSecondPhase();
364 typedef concepts::Digraph GR;
365 typedef concepts::ReadMap<GR::Arc, int> CM1;
366 typedef concepts::ReadMap<GR::Arc, double> CM2;
368 // Check the interface of Preflow
369 checkConcept< MaxFlowClassConcept<GR, CM1>,
370 Preflow<GR, CM1> >();
371 checkConcept< MaxFlowClassConcept<GR, CM2>,
372 Preflow<GR, CM2> >();
374 // Check the interface of EdmondsKarp
375 checkConcept< MaxFlowClassConcept<GR, CM1>,
376 EdmondsKarp<GR, CM1> >();
377 checkConcept< MaxFlowClassConcept<GR, CM2>,
378 EdmondsKarp<GR, CM2> >();
381 typedef Preflow<SmartDigraph, SmartDigraph::ArcMap<int> > PType1;
382 typedef Preflow<SmartDigraph, SmartDigraph::ArcMap<float> > PType2;
383 checkMaxFlowAlg<PType1, PreflowStartFunctions<PType1> >();
384 checkMaxFlowAlg<PType2, PreflowStartFunctions<PType2> >();
389 typedef EdmondsKarp<SmartDigraph, SmartDigraph::ArcMap<int> > EKType1;
390 typedef EdmondsKarp<SmartDigraph, SmartDigraph::ArcMap<float> > EKType2;
391 checkMaxFlowAlg<EKType1, GeneralStartFunctions<EKType1> >();
392 checkMaxFlowAlg<EKType2, GeneralStartFunctions<EKType2> >();