alpar@345: /* -*- C++ -*- alpar@345: * alpar@345: * This file is a part of LEMON, a generic C++ optimization library alpar@345: * alpar@345: * Copyright (C) 2003-2008 alpar@345: * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport alpar@345: * (Egervary Research Group on Combinatorial Optimization, EGRES). alpar@345: * alpar@345: * Permission to use, modify and distribute this software is granted alpar@345: * provided that this copyright notice appears in all copies. For alpar@345: * precise terms see the accompanying LICENSE file. alpar@345: * alpar@345: * This software is provided "AS IS" with no warranty of any kind, alpar@345: * express or implied, and with no claim as to its suitability for any alpar@345: * purpose. alpar@345: * alpar@345: */ alpar@345: alpar@345: #include alpar@345: #include alpar@345: alpar@345: #include alpar@345: #include alpar@345: #include alpar@345: #include alpar@345: alpar@345: #include "test_tools.h" alpar@345: alpar@345: using namespace lemon; alpar@345: kpeter@346: // Check the feasibility of the flow alpar@345: template alpar@345: bool checkFlow( const Digraph& gr, const FlowMap& flow, alpar@345: typename Digraph::Node s, typename Digraph::Node t, alpar@345: int value ) alpar@345: { alpar@345: TEMPLATE_DIGRAPH_TYPEDEFS(Digraph); alpar@345: for (ArcIt e(gr); e != INVALID; ++e) alpar@345: if (!(flow[e] == 0 || flow[e] == 1)) return false; alpar@345: alpar@345: for (NodeIt n(gr); n != INVALID; ++n) { alpar@345: int sum = 0; alpar@345: for (OutArcIt e(gr, n); e != INVALID; ++e) alpar@345: sum += flow[e]; alpar@345: for (InArcIt e(gr, n); e != INVALID; ++e) alpar@345: sum -= flow[e]; alpar@345: if (n == s && sum != value) return false; alpar@345: if (n == t && sum != -value) return false; alpar@345: if (n != s && n != t && sum != 0) return false; alpar@345: } alpar@345: alpar@345: return true; alpar@345: } alpar@345: kpeter@346: // Check the optimalitiy of the flow alpar@345: template < typename Digraph, typename CostMap, alpar@345: typename FlowMap, typename PotentialMap > alpar@345: bool checkOptimality( const Digraph& gr, const CostMap& cost, alpar@345: const FlowMap& flow, const PotentialMap& pi ) alpar@345: { kpeter@346: // Check the "Complementary Slackness" optimality condition alpar@345: TEMPLATE_DIGRAPH_TYPEDEFS(Digraph); alpar@345: bool opt = true; alpar@345: for (ArcIt e(gr); e != INVALID; ++e) { alpar@345: typename CostMap::Value red_cost = alpar@345: cost[e] + pi[gr.source(e)] - pi[gr.target(e)]; alpar@345: opt = (flow[e] == 0 && red_cost >= 0) || alpar@345: (flow[e] == 1 && red_cost <= 0); alpar@345: if (!opt) break; alpar@345: } alpar@345: return opt; alpar@345: } alpar@345: kpeter@346: // Check a path kpeter@346: template alpar@345: bool checkPath( const Digraph& gr, const Path& path, alpar@345: typename Digraph::Node s, typename Digraph::Node t) alpar@345: { kpeter@346: // Check the "Complementary Slackness" optimality condition alpar@345: TEMPLATE_DIGRAPH_TYPEDEFS(Digraph); alpar@345: Node n = s; alpar@345: for (int i = 0; i < path.length(); ++i) { alpar@345: if (gr.source(path.nth(i)) != n) return false; alpar@345: n = gr.target(path.nth(i)); alpar@345: } alpar@345: return n == t; alpar@345: } alpar@345: alpar@345: alpar@345: int main() alpar@345: { alpar@345: DIGRAPH_TYPEDEFS(ListDigraph); alpar@345: kpeter@346: // Read the test digraph alpar@345: ListDigraph digraph; alpar@345: ListDigraph::ArcMap length(digraph); alpar@345: Node source, target; alpar@345: alpar@345: std::string fname; alpar@345: if(getenv("srcdir")) alpar@345: fname = std::string(getenv("srcdir")); alpar@345: else fname = "."; alpar@345: fname += "/test/min_cost_flow_test.lgf"; alpar@345: alpar@345: std::ifstream input(fname.c_str()); alpar@345: check(input, "Input file '" << fname << "' not found"); alpar@345: DigraphReader(digraph, input). alpar@345: arcMap("cost", length). alpar@345: node("source", source). alpar@345: node("target", target). alpar@345: run(); alpar@345: input.close(); alpar@345: kpeter@346: // Find 2 paths alpar@345: { alpar@345: Suurballe suurballe(digraph, length, source, target); alpar@345: check(suurballe.run(2) == 2, "Wrong number of paths"); alpar@345: check(checkFlow(digraph, suurballe.flowMap(), source, target, 2), alpar@345: "The flow is not feasible"); alpar@345: check(suurballe.totalLength() == 510, "The flow is not optimal"); alpar@345: check(checkOptimality(digraph, length, suurballe.flowMap(), alpar@345: suurballe.potentialMap()), alpar@345: "Wrong potentials"); alpar@345: for (int i = 0; i < suurballe.pathNum(); ++i) alpar@345: check(checkPath(digraph, suurballe.path(i), source, target), alpar@345: "Wrong path"); alpar@345: } alpar@345: kpeter@346: // Find 3 paths alpar@345: { alpar@345: Suurballe suurballe(digraph, length, source, target); alpar@345: check(suurballe.run(3) == 3, "Wrong number of paths"); alpar@345: check(checkFlow(digraph, suurballe.flowMap(), source, target, 3), alpar@345: "The flow is not feasible"); alpar@345: check(suurballe.totalLength() == 1040, "The flow is not optimal"); alpar@345: check(checkOptimality(digraph, length, suurballe.flowMap(), alpar@345: suurballe.potentialMap()), alpar@345: "Wrong potentials"); alpar@345: for (int i = 0; i < suurballe.pathNum(); ++i) alpar@345: check(checkPath(digraph, suurballe.path(i), source, target), alpar@345: "Wrong path"); alpar@345: } alpar@345: kpeter@346: // Find 5 paths (only 3 can be found) alpar@345: { alpar@345: Suurballe suurballe(digraph, length, source, target); alpar@345: check(suurballe.run(5) == 3, "Wrong number of paths"); alpar@345: check(checkFlow(digraph, suurballe.flowMap(), source, target, 3), alpar@345: "The flow is not feasible"); alpar@345: check(suurballe.totalLength() == 1040, "The flow is not optimal"); alpar@345: check(checkOptimality(digraph, length, suurballe.flowMap(), alpar@345: suurballe.potentialMap()), alpar@345: "Wrong potentials"); alpar@345: for (int i = 0; i < suurballe.pathNum(); ++i) alpar@345: check(checkPath(digraph, suurballe.path(i), source, target), alpar@345: "Wrong path"); alpar@345: } alpar@345: alpar@345: return 0; alpar@345: }