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 Flow, typename Cost>
85 template <typename MCF>
88 checkConcept<concepts::Digraph, GR>();
96 .boundMaps(lower, upper)
102 const typename MCF::FlowMap &fm = mcf.flowMap();
103 const typename MCF::PotentialMap &pm = mcf.potentialMap();
106 double x = mcf.template totalCost<double>();
108 v = mcf.potential(n);
110 mcf.potentialMap(pot);
112 ignore_unused_variable_warning(fm);
113 ignore_unused_variable_warning(pm);
114 ignore_unused_variable_warning(x);
117 typedef typename GR::Node Node;
118 typedef typename GR::Arc Arc;
119 typedef concepts::ReadMap<Node, Flow> NM;
120 typedef concepts::ReadMap<Arc, Flow> FAM;
121 typedef concepts::ReadMap<Arc, Cost> CAM;
134 typename MCF::FlowMap &flow;
135 typename MCF::PotentialMap &pot;
141 // Check the feasibility of the given flow (primal soluiton)
142 template < typename GR, typename LM, typename UM,
143 typename SM, typename FM >
144 bool checkFlow( const GR& gr, const LM& lower, const UM& upper,
145 const SM& supply, const FM& flow )
147 TEMPLATE_DIGRAPH_TYPEDEFS(GR);
149 for (ArcIt e(gr); e != INVALID; ++e) {
150 if (flow[e] < lower[e] || flow[e] > upper[e]) return false;
153 for (NodeIt n(gr); n != INVALID; ++n) {
154 typename SM::Value sum = 0;
155 for (OutArcIt e(gr, n); e != INVALID; ++e)
157 for (InArcIt e(gr, n); e != INVALID; ++e)
159 if (sum != supply[n]) return false;
165 // Check the feasibility of the given potentials (dual soluiton)
166 // using the "Complementary Slackness" optimality condition
167 template < typename GR, typename LM, typename UM,
168 typename CM, typename FM, typename PM >
169 bool checkPotential( const GR& gr, const LM& lower, const UM& upper,
170 const CM& cost, const FM& flow, const PM& pi )
172 TEMPLATE_DIGRAPH_TYPEDEFS(GR);
175 for (ArcIt e(gr); opt && e != INVALID; ++e) {
176 typename CM::Value red_cost =
177 cost[e] + pi[gr.source(e)] - pi[gr.target(e)];
178 opt = red_cost == 0 ||
179 (red_cost > 0 && flow[e] == lower[e]) ||
180 (red_cost < 0 && flow[e] == upper[e]);
185 // Run a minimum cost flow algorithm and check the results
186 template < typename MCF, typename GR,
187 typename LM, typename UM,
188 typename CM, typename SM >
189 void checkMcf( const MCF& mcf, bool mcf_result,
190 const GR& gr, const LM& lower, const UM& upper,
191 const CM& cost, const SM& supply,
192 bool result, typename CM::Value total,
193 const std::string &test_id = "" )
195 check(mcf_result == result, "Wrong result " + test_id);
197 check(checkFlow(gr, lower, upper, supply, mcf.flowMap()),
198 "The flow is not feasible " + test_id);
199 check(mcf.totalCost() == total, "The flow is not optimal " + test_id);
200 check(checkPotential(gr, lower, upper, cost, mcf.flowMap(),
202 "Wrong potentials " + test_id);
208 // Check the interfaces
212 // TODO: This typedef should be enabled if the standard maps are
213 // reference maps in the graph concepts (See #190).
215 //typedef concepts::Digraph GR;
216 typedef ListDigraph GR;
218 checkConcept< McfClassConcept<GR, Flow, Cost>,
219 NetworkSimplex<GR, Flow, Cost> >();
222 // Run various MCF tests
223 typedef ListDigraph Digraph;
224 DIGRAPH_TYPEDEFS(ListDigraph);
226 // Read the test digraph
228 Digraph::ArcMap<int> c(gr), l1(gr), l2(gr), u(gr);
229 Digraph::NodeMap<int> s1(gr), s2(gr), s3(gr);
230 ConstMap<Arc, int> cc(1), cu(std::numeric_limits<int>::max());
233 std::istringstream input(test_lgf);
234 DigraphReader<Digraph>(gr, input)
246 // A. Test NetworkSimplex with the default pivot rule
248 NetworkSimplex<Digraph> mcf(gr);
250 mcf.upperMap(u).costMap(c);
251 checkMcf(mcf, mcf.supplyMap(s1).run(),
252 gr, l1, u, c, s1, true, 5240, "#A1");
253 checkMcf(mcf, mcf.stSupply(v, w, 27).run(),
254 gr, l1, u, c, s2, true, 7620, "#A2");
256 checkMcf(mcf, mcf.supplyMap(s1).run(),
257 gr, l2, u, c, s1, true, 5970, "#A3");
258 checkMcf(mcf, mcf.stSupply(v, w, 27).run(),
259 gr, l2, u, c, s2, true, 8010, "#A4");
261 checkMcf(mcf, mcf.supplyMap(s1).run(),
262 gr, l1, cu, cc, s1, true, 74, "#A5");
263 checkMcf(mcf, mcf.lowerMap(l2).stSupply(v, w, 27).run(),
264 gr, l2, cu, cc, s2, true, 94, "#A6");
266 checkMcf(mcf, mcf.run(),
267 gr, l1, cu, cc, s3, true, 0, "#A7");
268 checkMcf(mcf, mcf.boundMaps(l2, u).run(),
269 gr, l2, u, cc, s3, false, 0, "#A8");
272 // B. Test NetworkSimplex with each pivot rule
274 NetworkSimplex<Digraph> mcf(gr);
275 mcf.supplyMap(s1).costMap(c).capacityMap(u).lowerMap(l2);
277 checkMcf(mcf, mcf.run(NetworkSimplex<Digraph>::FIRST_ELIGIBLE),
278 gr, l2, u, c, s1, true, 5970, "#B1");
279 checkMcf(mcf, mcf.run(NetworkSimplex<Digraph>::BEST_ELIGIBLE),
280 gr, l2, u, c, s1, true, 5970, "#B2");
281 checkMcf(mcf, mcf.run(NetworkSimplex<Digraph>::BLOCK_SEARCH),
282 gr, l2, u, c, s1, true, 5970, "#B3");
283 checkMcf(mcf, mcf.run(NetworkSimplex<Digraph>::CANDIDATE_LIST),
284 gr, l2, u, c, s1, true, 5970, "#B4");
285 checkMcf(mcf, mcf.run(NetworkSimplex<Digraph>::ALTERING_LIST),
286 gr, l2, u, c, s1, true, 5970, "#B5");