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>();
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, Value> NM;
120 typedef concepts::ReadMap<Arc, Value> AM;
133 typename MCF::FlowMap &flow;
134 typename MCF::PotentialMap &pot;
140 // Check the feasibility of the given flow (primal soluiton)
141 template < typename GR, typename LM, typename UM,
142 typename SM, typename FM >
143 bool checkFlow( const GR& gr, const LM& lower, const UM& upper,
144 const SM& supply, const FM& flow )
146 TEMPLATE_DIGRAPH_TYPEDEFS(GR);
148 for (ArcIt e(gr); e != INVALID; ++e) {
149 if (flow[e] < lower[e] || flow[e] > upper[e]) return false;
152 for (NodeIt n(gr); n != INVALID; ++n) {
153 typename SM::Value sum = 0;
154 for (OutArcIt e(gr, n); e != INVALID; ++e)
156 for (InArcIt e(gr, n); e != INVALID; ++e)
158 if (sum != supply[n]) return false;
164 // Check the feasibility of the given potentials (dual soluiton)
165 // using the "Complementary Slackness" optimality condition
166 template < typename GR, typename LM, typename UM,
167 typename CM, typename FM, typename PM >
168 bool checkPotential( const GR& gr, const LM& lower, const UM& upper,
169 const CM& cost, const FM& flow, const PM& pi )
171 TEMPLATE_DIGRAPH_TYPEDEFS(GR);
174 for (ArcIt e(gr); opt && e != INVALID; ++e) {
175 typename CM::Value red_cost =
176 cost[e] + pi[gr.source(e)] - pi[gr.target(e)];
177 opt = red_cost == 0 ||
178 (red_cost > 0 && flow[e] == lower[e]) ||
179 (red_cost < 0 && flow[e] == upper[e]);
184 // Run a minimum cost flow algorithm and check the results
185 template < typename MCF, typename GR,
186 typename LM, typename UM,
187 typename CM, typename SM >
188 void checkMcf( const MCF& mcf, bool mcf_result,
189 const GR& gr, const LM& lower, const UM& upper,
190 const CM& cost, const SM& supply,
191 bool result, typename CM::Value total,
192 const std::string &test_id = "" )
194 check(mcf_result == result, "Wrong result " + test_id);
196 check(checkFlow(gr, lower, upper, supply, mcf.flowMap()),
197 "The flow is not feasible " + test_id);
198 check(mcf.totalCost() == total, "The flow is not optimal " + test_id);
199 check(checkPotential(gr, lower, upper, cost, mcf.flowMap(),
201 "Wrong potentials " + test_id);
207 // Check the interfaces
210 // TODO: This typedef should be enabled if the standard maps are
211 // reference maps in the graph concepts (See #190).
213 //typedef concepts::Digraph GR;
214 typedef ListDigraph GR;
216 checkConcept< McfClassConcept<GR, Value>,
217 NetworkSimplex<GR, Value> >();
220 // Run various MCF tests
221 typedef ListDigraph Digraph;
222 DIGRAPH_TYPEDEFS(ListDigraph);
224 // Read the test digraph
226 Digraph::ArcMap<int> c(gr), l1(gr), l2(gr), u(gr);
227 Digraph::NodeMap<int> s1(gr), s2(gr), s3(gr);
228 ConstMap<Arc, int> cc(1), cu(std::numeric_limits<int>::max());
231 std::istringstream input(test_lgf);
232 DigraphReader<Digraph>(gr, input)
244 // A. Test NetworkSimplex with the default pivot rule
246 NetworkSimplex<Digraph> mcf(gr);
248 mcf.upperMap(u).costMap(c);
249 checkMcf(mcf, mcf.supplyMap(s1).run(),
250 gr, l1, u, c, s1, true, 5240, "#A1");
251 checkMcf(mcf, mcf.stSupply(v, w, 27).run(),
252 gr, l1, u, c, s2, true, 7620, "#A2");
254 checkMcf(mcf, mcf.supplyMap(s1).run(),
255 gr, l2, u, c, s1, true, 5970, "#A3");
256 checkMcf(mcf, mcf.stSupply(v, w, 27).run(),
257 gr, l2, u, c, s2, true, 8010, "#A4");
259 checkMcf(mcf, mcf.supplyMap(s1).run(),
260 gr, l1, cu, cc, s1, true, 74, "#A5");
261 checkMcf(mcf, mcf.lowerMap(l2).stSupply(v, w, 27).run(),
262 gr, l2, cu, cc, s2, true, 94, "#A6");
264 checkMcf(mcf, mcf.run(),
265 gr, l1, cu, cc, s3, true, 0, "#A7");
266 checkMcf(mcf, mcf.boundMaps(l2, u).run(),
267 gr, l2, u, cc, s3, false, 0, "#A8");
270 // B. Test NetworkSimplex with each pivot rule
272 NetworkSimplex<Digraph> mcf(gr);
273 mcf.supplyMap(s1).costMap(c).capacityMap(u).lowerMap(l2);
275 checkMcf(mcf, mcf.run(NetworkSimplex<Digraph>::FIRST_ELIGIBLE),
276 gr, l2, u, c, s1, true, 5970, "#B1");
277 checkMcf(mcf, mcf.run(NetworkSimplex<Digraph>::BEST_ELIGIBLE),
278 gr, l2, u, c, s1, true, 5970, "#B2");
279 checkMcf(mcf, mcf.run(NetworkSimplex<Digraph>::BLOCK_SEARCH),
280 gr, l2, u, c, s1, true, 5970, "#B3");
281 checkMcf(mcf, mcf.run(NetworkSimplex<Digraph>::CANDIDATE_LIST),
282 gr, l2, u, c, s1, true, 5970, "#B4");
283 checkMcf(mcf, mcf.run(NetworkSimplex<Digraph>::ALTERING_LIST),
284 gr, l2, u, c, s1, true, 5970, "#B5");