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@623: #include kpeter@857: #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@623: "label\n" kpeter@623: "1\n" kpeter@623: "2\n" kpeter@623: "3\n" kpeter@623: "4\n" kpeter@623: "5\n" kpeter@623: "6\n" kpeter@623: "7\n" kpeter@623: "8\n" kpeter@623: "9\n" kpeter@623: "10\n" kpeter@623: "11\n" kpeter@623: "12\n" alpar@423: "@arcs\n" kpeter@623: " length\n" kpeter@623: " 1 2 70\n" kpeter@623: " 1 3 150\n" kpeter@623: " 1 4 80\n" kpeter@623: " 2 8 80\n" kpeter@623: " 3 5 140\n" kpeter@623: " 4 6 60\n" kpeter@623: " 4 7 80\n" kpeter@623: " 4 8 110\n" kpeter@623: " 5 7 60\n" kpeter@623: " 5 11 120\n" kpeter@623: " 6 3 0\n" kpeter@623: " 6 9 140\n" kpeter@623: " 6 10 90\n" kpeter@623: " 7 1 30\n" kpeter@623: " 8 12 60\n" kpeter@623: " 9 12 50\n" kpeter@623: "10 12 70\n" kpeter@623: "10 2 100\n" kpeter@623: "10 7 60\n" kpeter@623: "11 10 20\n" kpeter@623: "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@623: // Check the interface of Suurballe kpeter@623: void checkSuurballeCompile() kpeter@623: { kpeter@623: typedef int VType; kpeter@623: typedef concepts::Digraph Digraph; kpeter@623: kpeter@623: typedef Digraph::Node Node; kpeter@623: typedef Digraph::Arc Arc; kpeter@623: typedef concepts::ReadMap LengthMap; kpeter@623: kpeter@857: typedef Suurballe ST; kpeter@857: typedef Suurballe kpeter@857: ::SetFlowMap kpeter@857: ::SetPotentialMap kpeter@857: ::SetPath > kpeter@857: ::SetHeap > > kpeter@857: ::Create SuurballeType; kpeter@623: kpeter@623: Digraph g; kpeter@623: Node n; kpeter@623: Arc e; kpeter@623: LengthMap len; kpeter@623: SuurballeType::FlowMap flow(g); kpeter@623: SuurballeType::PotentialMap pi(g); kpeter@623: kpeter@623: SuurballeType suurb_test(g, len); kpeter@623: const SuurballeType& const_suurb_test = suurb_test; kpeter@623: kpeter@623: suurb_test kpeter@623: .flowMap(flow) kpeter@623: .potentialMap(pi); kpeter@623: kpeter@623: int k; kpeter@623: k = suurb_test.run(n, n); kpeter@623: k = suurb_test.run(n, n, k); kpeter@623: suurb_test.init(n); kpeter@854: suurb_test.fullInit(n); kpeter@854: suurb_test.start(n); kpeter@854: suurb_test.start(n, k); kpeter@623: k = suurb_test.findFlow(n); kpeter@623: k = suurb_test.findFlow(n, k); kpeter@623: suurb_test.findPaths(); kpeter@623: kpeter@623: int f; kpeter@623: VType c; kpeter@623: c = const_suurb_test.totalLength(); kpeter@623: f = const_suurb_test.flow(e); kpeter@623: const SuurballeType::FlowMap& fm = kpeter@623: const_suurb_test.flowMap(); kpeter@623: c = const_suurb_test.potential(n); kpeter@623: const SuurballeType::PotentialMap& pm = kpeter@623: const_suurb_test.potentialMap(); kpeter@623: k = const_suurb_test.pathNum(); kpeter@623: Path p = const_suurb_test.path(k); kpeter@623: kpeter@623: ignore_unused_variable_warning(fm); kpeter@623: ignore_unused_variable_warning(pm); kpeter@623: } kpeter@623: 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@623: Node s, t; alpar@345: alpar@423: std::istringstream input(test_lgf); alpar@345: DigraphReader(digraph, input). kpeter@623: arcMap("length", length). kpeter@623: node("source", s). kpeter@623: node("target", t). alpar@345: run(); alpar@440: kpeter@346: // Find 2 paths alpar@345: { kpeter@623: Suurballe suurballe(digraph, length); kpeter@623: check(suurballe.run(s, t) == 2, "Wrong number of paths"); kpeter@623: 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@623: check(checkPath(digraph, suurballe.path(i), s, t), "Wrong path"); alpar@345: } alpar@345: kpeter@346: // Find 3 paths alpar@345: { kpeter@623: Suurballe suurballe(digraph, length); kpeter@623: check(suurballe.run(s, t, 3) == 3, "Wrong number of paths"); kpeter@623: 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@623: 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@623: Suurballe suurballe(digraph, length); kpeter@623: check(suurballe.run(s, t, 5) == 3, "Wrong number of paths"); kpeter@623: 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@623: check(checkPath(digraph, suurballe.path(i), s, t), "Wrong path"); alpar@345: } alpar@345: alpar@345: return 0; alpar@345: }