1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
3 * This file is a part of LEMON, a generic C++ optimization library.
5 * Copyright (C) 2003-2009
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
22 #include <lemon/list_graph.h>
23 #include <lemon/lgf_reader.h>
25 #include <lemon/network_simplex.h>
27 #include <lemon/concepts/digraph.h>
28 #include <lemon/concept_check.h>
30 #include "test_tools.h"
32 using namespace lemon;
36 "label sup1 sup2 sup3\n"
51 " cost cap low1 low2\n"
79 // Check the interface of an MCF algorithm
80 template <typename GR, typename Value>
85 template <typename MCF>
88 checkConcept<concepts::Digraph, GR>();
92 b = mcf.lowerMap(lower)
95 .boundMaps(lower, upper)
101 const typename MCF::FlowMap &fm = mcf.flowMap();
102 const typename MCF::PotentialMap &pm = mcf.potentialMap();
105 double x = mcf.template totalCost<double>();
107 v = mcf.potential(n);
109 mcf.potentialMap(pot);
111 ignore_unused_variable_warning(fm);
112 ignore_unused_variable_warning(pm);
113 ignore_unused_variable_warning(x);
116 typedef typename GR::Node Node;
117 typedef typename GR::Arc Arc;
118 typedef concepts::ReadMap<Node, Value> NM;
119 typedef concepts::ReadMap<Arc, Value> AM;
132 typename MCF::FlowMap &flow;
133 typename MCF::PotentialMap &pot;
139 // Check the feasibility of the given flow (primal soluiton)
140 template < typename GR, typename LM, typename UM,
141 typename SM, typename FM >
142 bool checkFlow( const GR& gr, const LM& lower, const UM& upper,
143 const SM& supply, const FM& flow )
145 TEMPLATE_DIGRAPH_TYPEDEFS(GR);
147 for (ArcIt e(gr); e != INVALID; ++e) {
148 if (flow[e] < lower[e] || flow[e] > upper[e]) return false;
151 for (NodeIt n(gr); n != INVALID; ++n) {
152 typename SM::Value sum = 0;
153 for (OutArcIt e(gr, n); e != INVALID; ++e)
155 for (InArcIt e(gr, n); e != INVALID; ++e)
157 if (sum != supply[n]) return false;
163 // Check the feasibility of the given potentials (dual soluiton)
164 // using the "Complementary Slackness" optimality condition
165 template < typename GR, typename LM, typename UM,
166 typename CM, typename FM, typename PM >
167 bool checkPotential( const GR& gr, const LM& lower, const UM& upper,
168 const CM& cost, const FM& flow, const PM& pi )
170 TEMPLATE_DIGRAPH_TYPEDEFS(GR);
173 for (ArcIt e(gr); opt && e != INVALID; ++e) {
174 typename CM::Value red_cost =
175 cost[e] + pi[gr.source(e)] - pi[gr.target(e)];
176 opt = red_cost == 0 ||
177 (red_cost > 0 && flow[e] == lower[e]) ||
178 (red_cost < 0 && flow[e] == upper[e]);
183 // Run a minimum cost flow algorithm and check the results
184 template < typename MCF, typename GR,
185 typename LM, typename UM,
186 typename CM, typename SM >
187 void checkMcf( const MCF& mcf, bool mcf_result,
188 const GR& gr, const LM& lower, const UM& upper,
189 const CM& cost, const SM& supply,
190 bool result, typename CM::Value total,
191 const std::string &test_id = "" )
193 check(mcf_result == result, "Wrong result " + test_id);
195 check(checkFlow(gr, lower, upper, supply, mcf.flowMap()),
196 "The flow is not feasible " + test_id);
197 check(mcf.totalCost() == total, "The flow is not optimal " + test_id);
198 check(checkPotential(gr, lower, upper, cost, mcf.flowMap(),
200 "Wrong potentials " + test_id);
206 // Check the interfaces
209 // TODO: This typedef should be enabled if the standard maps are
210 // reference maps in the graph concepts (See #190).
212 //typedef concepts::Digraph GR;
213 typedef ListDigraph GR;
215 checkConcept< McfClassConcept<GR, Value>,
216 NetworkSimplex<GR, Value> >();
219 // Run various MCF tests
220 typedef ListDigraph Digraph;
221 DIGRAPH_TYPEDEFS(ListDigraph);
223 // Read the test digraph
225 Digraph::ArcMap<int> c(gr), l1(gr), l2(gr), u(gr);
226 Digraph::NodeMap<int> s1(gr), s2(gr), s3(gr);
227 ConstMap<Arc, int> cc(1), cu(std::numeric_limits<int>::max());
230 std::istringstream input(test_lgf);
231 DigraphReader<Digraph>(gr, input)
243 // A. Test NetworkSimplex with the default pivot rule
245 NetworkSimplex<Digraph> mcf1(gr), mcf2(gr), mcf3(gr), mcf4(gr),
246 mcf5(gr), mcf6(gr), mcf7(gr), mcf8(gr);
248 checkMcf(mcf1, mcf1.upperMap(u).costMap(c).supplyMap(s1).run(),
249 gr, l1, u, c, s1, true, 5240, "#A1");
250 checkMcf(mcf2, mcf2.upperMap(u).costMap(c).stSupply(v, w, 27).run(),
251 gr, l1, u, c, s2, true, 7620, "#A2");
252 checkMcf(mcf3, mcf3.boundMaps(l2, u).costMap(c).supplyMap(s1).run(),
253 gr, l2, u, c, s1, true, 5970, "#A3");
254 checkMcf(mcf4, mcf4.boundMaps(l2, u).costMap(c).stSupply(v, w, 27).run(),
255 gr, l2, u, c, s2, true, 8010, "#A4");
256 checkMcf(mcf5, mcf5.supplyMap(s1).run(),
257 gr, l1, cu, cc, s1, true, 74, "#A5");
258 checkMcf(mcf6, mcf6.stSupply(v, w, 27).lowerMap(l2).run(),
259 gr, l2, cu, cc, s2, true, 94, "#A6");
260 checkMcf(mcf7, mcf7.run(),
261 gr, l1, cu, cc, s3, true, 0, "#A7");
262 checkMcf(mcf8, mcf8.boundMaps(l2, u).run(),
263 gr, l2, u, cc, s3, false, 0, "#A8");
266 // B. Test NetworkSimplex with each pivot rule
268 NetworkSimplex<Digraph> mcf1(gr), mcf2(gr), mcf3(gr), mcf4(gr), mcf5(gr);
269 NetworkSimplex<Digraph>::PivotRule pr;
271 pr = NetworkSimplex<Digraph>::FIRST_ELIGIBLE;
272 checkMcf(mcf1, mcf1.boundMaps(l2, u).costMap(c).supplyMap(s1).run(pr),
273 gr, l2, u, c, s1, true, 5970, "#B1");
274 pr = NetworkSimplex<Digraph>::BEST_ELIGIBLE;
275 checkMcf(mcf2, mcf2.boundMaps(l2, u).costMap(c).supplyMap(s1).run(pr),
276 gr, l2, u, c, s1, true, 5970, "#B2");
277 pr = NetworkSimplex<Digraph>::BLOCK_SEARCH;
278 checkMcf(mcf3, mcf3.boundMaps(l2, u).costMap(c).supplyMap(s1).run(pr),
279 gr, l2, u, c, s1, true, 5970, "#B3");
280 pr = NetworkSimplex<Digraph>::CANDIDATE_LIST;
281 checkMcf(mcf4, mcf4.boundMaps(l2, u).costMap(c).supplyMap(s1).run(pr),
282 gr, l2, u, c, s1, true, 5970, "#B4");
283 pr = NetworkSimplex<Digraph>::ALTERING_LIST;
284 checkMcf(mcf5, mcf5.boundMaps(l2, u).costMap(c).supplyMap(s1).run(pr),
285 gr, l2, u, c, s1, true, 5970, "#B5");