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>
30 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) {
202 for (SmartDigraph::ArcIt e(g); e != INVALID; ++e) {
203 if (flow[e] < 0 || flow[e] > cap[e]) return false;
206 for (SmartDigraph::NodeIt n(g); n != INVALID; ++n) {
207 if (n == s || n == t) continue;
209 for (SmartDigraph::OutArcIt e(g, n); e != INVALID; ++e) {
212 for (SmartDigraph::InArcIt e(g, n); e != INVALID; ++e) {
215 if (sum != 0) return false;
220 void checkInitPreflow()
222 DIGRAPH_TYPEDEFS(SmartDigraph);
225 SmartDigraph::ArcMap<int> cap(g), iflow(g);
226 Node s = g.addNode(); Node t = g.addNode();
227 Node n1 = g.addNode(); Node n2 = g.addNode();
229 a = g.addArc(s, n1); cap[a] = 20; iflow[a] = 20;
230 a = g.addArc(n1, n2); cap[a] = 10; iflow[a] = 0;
231 a = g.addArc(n2, t); cap[a] = 20; iflow[a] = 0;
233 Preflow<SmartDigraph> pre(g, cap, s, t);
235 pre.startFirstPhase();
237 check(pre.flowValue() == 10, "Incorrect max flow value.");
238 check(pre.minCut(s), "Wrong min cut (Node s).");
239 check(pre.minCut(n1), "Wrong min cut (Node n1).");
240 check(!pre.minCut(n2), "Wrong min cut (Node n2).");
241 check(!pre.minCut(t), "Wrong min cut (Node t).");
244 template <typename MF, typename SF>
245 void checkMaxFlowAlg() {
246 typedef SmartDigraph Digraph;
247 DIGRAPH_TYPEDEFS(Digraph);
249 typedef typename MF::Value Value;
250 typedef Digraph::ArcMap<Value> CapMap;
251 typedef CapMap FlowMap;
252 typedef BoolNodeMap CutMap;
257 std::istringstream input(test_lgf);
258 DigraphReader<Digraph>(g,input)
259 .arcMap("capacity", cap)
264 MF max_flow(g, cap, s, t);
267 check(checkFlow(g, max_flow.flowMap(), cap, s, t),
268 "The flow is not feasible.");
271 max_flow.minCutMap(min_cut);
272 Value min_cut_value = cutValue(g, min_cut, cap);
274 check(max_flow.flowValue() == min_cut_value,
275 "The max flow value is not equal to the min cut value.");
278 for (ArcIt e(g); e != INVALID; ++e) flow[e] = max_flow.flowMap()[e];
280 Value flow_value = max_flow.flowValue();
282 for (ArcIt e(g); e != INVALID; ++e) cap[e] = 2 * cap[e];
285 SF::startFirstPhase(max_flow); // start first phase of the algorithm
288 max_flow.minCutMap(min_cut1);
289 min_cut_value = cutValue(g, min_cut1, cap);
291 check(max_flow.flowValue() == min_cut_value &&
292 min_cut_value == 2 * flow_value,
293 "The max flow value or the min cut value is wrong.");
295 SF::startSecondPhase(max_flow); // start second phase of the algorithm
297 check(checkFlow(g, max_flow.flowMap(), cap, s, t),
298 "The flow is not feasible.");
301 max_flow.minCutMap(min_cut2);
302 min_cut_value = cutValue(g, min_cut2, cap);
304 check(max_flow.flowValue() == min_cut_value &&
305 min_cut_value == 2 * flow_value,
306 "The max flow value or the min cut value was not doubled.");
308 max_flow.flowMap(flow);
312 if (tmp1 != INVALID) s = tmp1;
316 if (tmp2 != INVALID) t = tmp2;
324 max_flow.minCutMap(min_cut3);
325 min_cut_value = cutValue(g, min_cut3, cap);
327 check(max_flow.flowValue() == min_cut_value,
328 "The max flow value or the min cut value is wrong.");
331 // Struct for calling start functions of a general max flow algorithm
332 template <typename MF>
333 struct GeneralStartFunctions {
335 static void startFirstPhase(MF& mf) {
339 static void startSecondPhase(MF& mf) {
340 ::lemon::ignore_unused_variable_warning(mf);
345 // Struct for calling start functions of Preflow
346 template <typename MF>
347 struct PreflowStartFunctions {
349 static void startFirstPhase(MF& mf) {
350 mf.startFirstPhase();
353 static void startSecondPhase(MF& mf) {
354 mf.startSecondPhase();
361 typedef concepts::Digraph GR;
362 typedef concepts::ReadMap<GR::Arc, int> CM1;
363 typedef concepts::ReadMap<GR::Arc, double> CM2;
365 // Check the interface of Preflow
366 checkConcept< MaxFlowClassConcept<GR, CM1>,
367 Preflow<GR, CM1> >();
368 checkConcept< MaxFlowClassConcept<GR, CM2>,
369 Preflow<GR, CM2> >();
371 // Check the interface of EdmondsKarp
372 checkConcept< MaxFlowClassConcept<GR, CM1>,
373 EdmondsKarp<GR, CM1> >();
374 checkConcept< MaxFlowClassConcept<GR, CM2>,
375 EdmondsKarp<GR, CM2> >();
378 typedef Preflow<SmartDigraph, SmartDigraph::ArcMap<int> > PType1;
379 typedef Preflow<SmartDigraph, SmartDigraph::ArcMap<float> > PType2;
380 checkMaxFlowAlg<PType1, PreflowStartFunctions<PType1> >();
381 checkMaxFlowAlg<PType2, PreflowStartFunctions<PType2> >();
386 typedef EdmondsKarp<SmartDigraph, SmartDigraph::ArcMap<int> > EKType1;
387 typedef EdmondsKarp<SmartDigraph, SmartDigraph::ArcMap<float> > EKType2;
388 checkMaxFlowAlg<EKType1, GeneralStartFunctions<EKType1> >();
389 checkMaxFlowAlg<EKType2, GeneralStartFunctions<EKType2> >();