alpar@463: /* -*- mode: C++; indent-tabs-mode: nil; -*- alpar@357: * alpar@463: * This file is a part of LEMON, a generic C++ optimization library. alpar@357: * alpar@1270: * Copyright (C) 2003-2013 alpar@357: * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport alpar@357: * (Egervary Research Group on Combinatorial Optimization, EGRES). alpar@357: * alpar@357: * Permission to use, modify and distribute this software is granted alpar@357: * provided that this copyright notice appears in all copies. For alpar@357: * precise terms see the accompanying LICENSE file. alpar@357: * alpar@357: * This software is provided "AS IS" with no warranty of any kind, alpar@357: * express or implied, and with no claim as to its suitability for any alpar@357: * purpose. alpar@357: * alpar@357: */ alpar@357: alpar@357: #include alpar@357: alpar@357: #include alpar@357: #include alpar@357: #include alpar@357: #include kpeter@670: #include kpeter@931: #include alpar@357: alpar@357: #include "test_tools.h" alpar@357: alpar@357: using namespace lemon; alpar@357: alpar@442: char test_lgf[] = alpar@442: "@nodes\n" kpeter@670: "label\n" kpeter@670: "1\n" kpeter@670: "2\n" kpeter@670: "3\n" kpeter@670: "4\n" kpeter@670: "5\n" kpeter@670: "6\n" kpeter@670: "7\n" kpeter@670: "8\n" kpeter@670: "9\n" kpeter@670: "10\n" kpeter@670: "11\n" kpeter@670: "12\n" alpar@442: "@arcs\n" kpeter@670: " length\n" kpeter@670: " 1 2 70\n" kpeter@670: " 1 3 150\n" kpeter@670: " 1 4 80\n" kpeter@670: " 2 8 80\n" kpeter@670: " 3 5 140\n" kpeter@670: " 4 6 60\n" kpeter@670: " 4 7 80\n" kpeter@670: " 4 8 110\n" kpeter@670: " 5 7 60\n" kpeter@670: " 5 11 120\n" kpeter@670: " 6 3 0\n" kpeter@670: " 6 9 140\n" kpeter@670: " 6 10 90\n" kpeter@670: " 7 1 30\n" kpeter@670: " 8 12 60\n" kpeter@670: " 9 12 50\n" kpeter@670: "10 12 70\n" kpeter@670: "10 2 100\n" kpeter@670: "10 7 60\n" kpeter@670: "11 10 20\n" kpeter@670: "12 11 30\n" alpar@442: "@attributes\n" alpar@442: "source 1\n" alpar@442: "target 12\n" alpar@442: "@end\n"; alpar@442: kpeter@670: // Check the interface of Suurballe kpeter@670: void checkSuurballeCompile() kpeter@670: { kpeter@670: typedef int VType; kpeter@670: typedef concepts::Digraph Digraph; kpeter@670: kpeter@670: typedef Digraph::Node Node; kpeter@670: typedef Digraph::Arc Arc; kpeter@670: typedef concepts::ReadMap LengthMap; alpar@956: kpeter@931: typedef Suurballe ST; kpeter@931: typedef Suurballe kpeter@931: ::SetFlowMap kpeter@931: ::SetPotentialMap kpeter@931: ::SetPath > kpeter@931: ::SetHeap > > kpeter@931: ::Create SuurballeType; kpeter@670: kpeter@670: Digraph g; kpeter@670: Node n; kpeter@670: Arc e; kpeter@670: LengthMap len; kpeter@670: SuurballeType::FlowMap flow(g); kpeter@670: SuurballeType::PotentialMap pi(g); kpeter@670: kpeter@670: SuurballeType suurb_test(g, len); kpeter@670: const SuurballeType& const_suurb_test = suurb_test; kpeter@670: kpeter@670: suurb_test kpeter@670: .flowMap(flow) kpeter@670: .potentialMap(pi); kpeter@670: kpeter@670: int k; kpeter@670: k = suurb_test.run(n, n); kpeter@670: k = suurb_test.run(n, n, k); kpeter@670: suurb_test.init(n); kpeter@927: suurb_test.fullInit(n); kpeter@927: suurb_test.start(n); kpeter@927: suurb_test.start(n, k); kpeter@670: k = suurb_test.findFlow(n); kpeter@670: k = suurb_test.findFlow(n, k); kpeter@670: suurb_test.findPaths(); alpar@956: kpeter@670: int f; kpeter@670: VType c; alpar@1257: ::lemon::ignore_unused_variable_warning(f,c); alpar@1171: kpeter@670: c = const_suurb_test.totalLength(); kpeter@670: f = const_suurb_test.flow(e); kpeter@670: const SuurballeType::FlowMap& fm = kpeter@670: const_suurb_test.flowMap(); kpeter@670: c = const_suurb_test.potential(n); kpeter@670: const SuurballeType::PotentialMap& pm = kpeter@670: const_suurb_test.potentialMap(); kpeter@670: k = const_suurb_test.pathNum(); kpeter@670: Path p = const_suurb_test.path(k); alpar@956: alpar@1257: ::lemon::ignore_unused_variable_warning(fm); alpar@1257: ::lemon::ignore_unused_variable_warning(pm); kpeter@670: } kpeter@670: kpeter@358: // Check the feasibility of the flow alpar@357: template alpar@463: bool checkFlow( const Digraph& gr, const FlowMap& flow, alpar@357: typename Digraph::Node s, typename Digraph::Node t, alpar@357: int value ) alpar@357: { alpar@357: TEMPLATE_DIGRAPH_TYPEDEFS(Digraph); alpar@357: for (ArcIt e(gr); e != INVALID; ++e) alpar@357: if (!(flow[e] == 0 || flow[e] == 1)) return false; alpar@357: alpar@357: for (NodeIt n(gr); n != INVALID; ++n) { alpar@357: int sum = 0; alpar@357: for (OutArcIt e(gr, n); e != INVALID; ++e) alpar@357: sum += flow[e]; alpar@357: for (InArcIt e(gr, n); e != INVALID; ++e) alpar@357: sum -= flow[e]; alpar@357: if (n == s && sum != value) return false; alpar@357: if (n == t && sum != -value) return false; alpar@357: if (n != s && n != t && sum != 0) return false; alpar@357: } alpar@357: alpar@357: return true; alpar@357: } alpar@357: kpeter@358: // Check the optimalitiy of the flow alpar@463: template < typename Digraph, typename CostMap, alpar@357: typename FlowMap, typename PotentialMap > alpar@357: bool checkOptimality( const Digraph& gr, const CostMap& cost, alpar@357: const FlowMap& flow, const PotentialMap& pi ) alpar@357: { kpeter@358: // Check the "Complementary Slackness" optimality condition alpar@357: TEMPLATE_DIGRAPH_TYPEDEFS(Digraph); alpar@357: bool opt = true; alpar@357: for (ArcIt e(gr); e != INVALID; ++e) { alpar@357: typename CostMap::Value red_cost = alpar@357: cost[e] + pi[gr.source(e)] - pi[gr.target(e)]; alpar@357: opt = (flow[e] == 0 && red_cost >= 0) || alpar@357: (flow[e] == 1 && red_cost <= 0); alpar@357: if (!opt) break; alpar@357: } alpar@357: return opt; alpar@357: } alpar@357: kpeter@358: // Check a path kpeter@358: template alpar@357: bool checkPath( const Digraph& gr, const Path& path, alpar@357: typename Digraph::Node s, typename Digraph::Node t) alpar@357: { alpar@357: TEMPLATE_DIGRAPH_TYPEDEFS(Digraph); alpar@357: Node n = s; alpar@357: for (int i = 0; i < path.length(); ++i) { alpar@357: if (gr.source(path.nth(i)) != n) return false; alpar@357: n = gr.target(path.nth(i)); alpar@357: } alpar@357: return n == t; alpar@357: } alpar@357: alpar@357: alpar@357: int main() alpar@357: { alpar@357: DIGRAPH_TYPEDEFS(ListDigraph); alpar@357: kpeter@358: // Read the test digraph alpar@357: ListDigraph digraph; alpar@357: ListDigraph::ArcMap length(digraph); kpeter@670: Node s, t; alpar@357: alpar@442: std::istringstream input(test_lgf); alpar@357: DigraphReader(digraph, input). kpeter@670: arcMap("length", length). kpeter@670: node("source", s). kpeter@670: node("target", t). alpar@357: run(); alpar@463: kpeter@932: // Check run() alpar@357: { kpeter@670: Suurballe suurballe(digraph, length); alpar@956: kpeter@932: // Find 2 paths kpeter@670: check(suurballe.run(s, t) == 2, "Wrong number of paths"); kpeter@670: check(checkFlow(digraph, suurballe.flowMap(), s, t, 2), alpar@357: "The flow is not feasible"); alpar@357: check(suurballe.totalLength() == 510, "The flow is not optimal"); alpar@463: check(checkOptimality(digraph, length, suurballe.flowMap(), alpar@357: suurballe.potentialMap()), alpar@357: "Wrong potentials"); alpar@357: for (int i = 0; i < suurballe.pathNum(); ++i) kpeter@670: check(checkPath(digraph, suurballe.path(i), s, t), "Wrong path"); alpar@357: kpeter@932: // Find 3 paths kpeter@670: check(suurballe.run(s, t, 3) == 3, "Wrong number of paths"); kpeter@670: check(checkFlow(digraph, suurballe.flowMap(), s, t, 3), alpar@357: "The flow is not feasible"); alpar@357: check(suurballe.totalLength() == 1040, "The flow is not optimal"); alpar@463: check(checkOptimality(digraph, length, suurballe.flowMap(), alpar@357: suurballe.potentialMap()), alpar@357: "Wrong potentials"); alpar@357: for (int i = 0; i < suurballe.pathNum(); ++i) kpeter@670: check(checkPath(digraph, suurballe.path(i), s, t), "Wrong path"); alpar@357: kpeter@932: // Find 5 paths (only 3 can be found) kpeter@670: check(suurballe.run(s, t, 5) == 3, "Wrong number of paths"); kpeter@670: check(checkFlow(digraph, suurballe.flowMap(), s, t, 3), alpar@357: "The flow is not feasible"); alpar@357: check(suurballe.totalLength() == 1040, "The flow is not optimal"); alpar@463: check(checkOptimality(digraph, length, suurballe.flowMap(), alpar@357: suurballe.potentialMap()), alpar@357: "Wrong potentials"); alpar@357: for (int i = 0; i < suurballe.pathNum(); ++i) kpeter@670: check(checkPath(digraph, suurballe.path(i), s, t), "Wrong path"); alpar@357: } alpar@357: kpeter@932: // Check fullInit() + start() kpeter@932: { kpeter@932: Suurballe suurballe(digraph, length); kpeter@932: suurballe.fullInit(s); alpar@956: kpeter@932: // Find 2 paths kpeter@932: check(suurballe.start(t) == 2, "Wrong number of paths"); kpeter@932: check(suurballe.totalLength() == 510, "The flow is not optimal"); kpeter@932: kpeter@932: // Find 3 paths kpeter@932: check(suurballe.start(t, 3) == 3, "Wrong number of paths"); kpeter@932: check(suurballe.totalLength() == 1040, "The flow is not optimal"); kpeter@932: kpeter@932: // Find 5 paths (only 3 can be found) kpeter@932: check(suurballe.start(t, 5) == 3, "Wrong number of paths"); kpeter@932: check(suurballe.totalLength() == 1040, "The flow is not optimal"); kpeter@932: } kpeter@670: alpar@357: return 0; alpar@357: }