alpar@440: /* -*- mode: C++; indent-tabs-mode: nil; -*- alpar@345: * alpar@440: * This file is a part of LEMON, a generic C++ optimization library. alpar@345: * alpar@440: * Copyright (C) 2003-2009 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: alpar@345: #include alpar@345: #include alpar@345: #include alpar@345: #include kpeter@615: #include alpar@345: alpar@345: #include "test_tools.h" alpar@345: alpar@345: using namespace lemon; alpar@345: alpar@423: char test_lgf[] = alpar@423: "@nodes\n" kpeter@615: "label\n" kpeter@615: "1\n" kpeter@615: "2\n" kpeter@615: "3\n" kpeter@615: "4\n" kpeter@615: "5\n" kpeter@615: "6\n" kpeter@615: "7\n" kpeter@615: "8\n" kpeter@615: "9\n" kpeter@615: "10\n" kpeter@615: "11\n" kpeter@615: "12\n" alpar@423: "@arcs\n" kpeter@615: " length\n" kpeter@615: " 1 2 70\n" kpeter@615: " 1 3 150\n" kpeter@615: " 1 4 80\n" kpeter@615: " 2 8 80\n" kpeter@615: " 3 5 140\n" kpeter@615: " 4 6 60\n" kpeter@615: " 4 7 80\n" kpeter@615: " 4 8 110\n" kpeter@615: " 5 7 60\n" kpeter@615: " 5 11 120\n" kpeter@615: " 6 3 0\n" kpeter@615: " 6 9 140\n" kpeter@615: " 6 10 90\n" kpeter@615: " 7 1 30\n" kpeter@615: " 8 12 60\n" kpeter@615: " 9 12 50\n" kpeter@615: "10 12 70\n" kpeter@615: "10 2 100\n" kpeter@615: "10 7 60\n" kpeter@615: "11 10 20\n" kpeter@615: "12 11 30\n" alpar@423: "@attributes\n" alpar@423: "source 1\n" alpar@423: "target 12\n" alpar@423: "@end\n"; alpar@423: kpeter@615: // Check the interface of Suurballe kpeter@615: void checkSuurballeCompile() kpeter@615: { kpeter@615: typedef int VType; kpeter@615: typedef concepts::Digraph Digraph; kpeter@615: kpeter@615: typedef Digraph::Node Node; kpeter@615: typedef Digraph::Arc Arc; kpeter@615: typedef concepts::ReadMap LengthMap; kpeter@615: kpeter@615: typedef Suurballe SuurballeType; kpeter@615: kpeter@615: Digraph g; kpeter@615: Node n; kpeter@615: Arc e; kpeter@615: LengthMap len; kpeter@615: SuurballeType::FlowMap flow(g); kpeter@615: SuurballeType::PotentialMap pi(g); kpeter@615: kpeter@615: SuurballeType suurb_test(g, len); kpeter@615: const SuurballeType& const_suurb_test = suurb_test; kpeter@615: kpeter@615: suurb_test kpeter@615: .flowMap(flow) kpeter@615: .potentialMap(pi); kpeter@615: kpeter@615: int k; kpeter@615: k = suurb_test.run(n, n); kpeter@615: k = suurb_test.run(n, n, k); kpeter@615: suurb_test.init(n); kpeter@615: k = suurb_test.findFlow(n); kpeter@615: k = suurb_test.findFlow(n, k); kpeter@615: suurb_test.findPaths(); kpeter@615: kpeter@615: int f; kpeter@615: VType c; kpeter@615: c = const_suurb_test.totalLength(); kpeter@615: f = const_suurb_test.flow(e); kpeter@615: const SuurballeType::FlowMap& fm = kpeter@615: const_suurb_test.flowMap(); kpeter@615: c = const_suurb_test.potential(n); kpeter@615: const SuurballeType::PotentialMap& pm = kpeter@615: const_suurb_test.potentialMap(); kpeter@615: k = const_suurb_test.pathNum(); kpeter@615: Path p = const_suurb_test.path(k); kpeter@615: kpeter@615: ignore_unused_variable_warning(fm); kpeter@615: ignore_unused_variable_warning(pm); kpeter@615: } kpeter@615: kpeter@346: // Check the feasibility of the flow alpar@345: template alpar@440: 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@440: 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: { 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); kpeter@615: Node s, t; alpar@345: alpar@423: std::istringstream input(test_lgf); alpar@345: DigraphReader(digraph, input). kpeter@615: arcMap("length", length). kpeter@615: node("source", s). kpeter@615: node("target", t). alpar@345: run(); alpar@440: kpeter@346: // Find 2 paths alpar@345: { kpeter@615: Suurballe suurballe(digraph, length); kpeter@615: check(suurballe.run(s, t) == 2, "Wrong number of paths"); kpeter@615: check(checkFlow(digraph, suurballe.flowMap(), s, t, 2), alpar@345: "The flow is not feasible"); alpar@345: check(suurballe.totalLength() == 510, "The flow is not optimal"); alpar@440: check(checkOptimality(digraph, length, suurballe.flowMap(), alpar@345: suurballe.potentialMap()), alpar@345: "Wrong potentials"); alpar@345: for (int i = 0; i < suurballe.pathNum(); ++i) kpeter@615: check(checkPath(digraph, suurballe.path(i), s, t), "Wrong path"); alpar@345: } alpar@345: kpeter@346: // Find 3 paths alpar@345: { kpeter@615: Suurballe suurballe(digraph, length); kpeter@615: check(suurballe.run(s, t, 3) == 3, "Wrong number of paths"); kpeter@615: check(checkFlow(digraph, suurballe.flowMap(), s, t, 3), alpar@345: "The flow is not feasible"); alpar@345: check(suurballe.totalLength() == 1040, "The flow is not optimal"); alpar@440: check(checkOptimality(digraph, length, suurballe.flowMap(), alpar@345: suurballe.potentialMap()), alpar@345: "Wrong potentials"); alpar@345: for (int i = 0; i < suurballe.pathNum(); ++i) kpeter@615: check(checkPath(digraph, suurballe.path(i), s, t), "Wrong path"); alpar@345: } alpar@345: kpeter@346: // Find 5 paths (only 3 can be found) alpar@345: { kpeter@615: Suurballe suurballe(digraph, length); kpeter@615: check(suurballe.run(s, t, 5) == 3, "Wrong number of paths"); kpeter@615: check(checkFlow(digraph, suurballe.flowMap(), s, t, 3), alpar@345: "The flow is not feasible"); alpar@345: check(suurballe.totalLength() == 1040, "The flow is not optimal"); alpar@440: check(checkOptimality(digraph, length, suurballe.flowMap(), alpar@345: suurballe.potentialMap()), alpar@345: "Wrong potentials"); alpar@345: for (int i = 0; i < suurballe.pathNum(); ++i) kpeter@615: check(checkPath(digraph, suurballe.path(i), s, t), "Wrong path"); alpar@345: } alpar@345: alpar@345: return 0; alpar@345: }