test/suurballe_test.cc
changeset 528 88bd39ef7d98
parent 423 ff48c2738fb2
child 623 7c1324b35d89
equal deleted inserted replaced
2:d359e06e7366 3:88a8e6055304
     1 /* -*- C++ -*-
     1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
     2  *
     2  *
     3  * This file is a part of LEMON, a generic C++ optimization library
     3  * This file is a part of LEMON, a generic C++ optimization library.
     4  *
     4  *
     5  * Copyright (C) 2003-2008
     5  * Copyright (C) 2003-2009
     6  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     6  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     7  * (Egervary Research Group on Combinatorial Optimization, EGRES).
     7  * (Egervary Research Group on Combinatorial Optimization, EGRES).
     8  *
     8  *
     9  * Permission to use, modify and distribute this software is granted
     9  * Permission to use, modify and distribute this software is granted
    10  * provided that this copyright notice appears in all copies. For
    10  * provided that this copyright notice appears in all copies. For
    70   "target 12\n"
    70   "target 12\n"
    71   "@end\n";
    71   "@end\n";
    72 
    72 
    73 // Check the feasibility of the flow
    73 // Check the feasibility of the flow
    74 template <typename Digraph, typename FlowMap>
    74 template <typename Digraph, typename FlowMap>
    75 bool checkFlow( const Digraph& gr, const FlowMap& flow, 
    75 bool checkFlow( const Digraph& gr, const FlowMap& flow,
    76                 typename Digraph::Node s, typename Digraph::Node t,
    76                 typename Digraph::Node s, typename Digraph::Node t,
    77                 int value )
    77                 int value )
    78 {
    78 {
    79   TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
    79   TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
    80   for (ArcIt e(gr); e != INVALID; ++e)
    80   for (ArcIt e(gr); e != INVALID; ++e)
    93 
    93 
    94   return true;
    94   return true;
    95 }
    95 }
    96 
    96 
    97 // Check the optimalitiy of the flow
    97 // Check the optimalitiy of the flow
    98 template < typename Digraph, typename CostMap, 
    98 template < typename Digraph, typename CostMap,
    99            typename FlowMap, typename PotentialMap >
    99            typename FlowMap, typename PotentialMap >
   100 bool checkOptimality( const Digraph& gr, const CostMap& cost,
   100 bool checkOptimality( const Digraph& gr, const CostMap& cost,
   101                       const FlowMap& flow, const PotentialMap& pi )
   101                       const FlowMap& flow, const PotentialMap& pi )
   102 {
   102 {
   103   // Check the "Complementary Slackness" optimality condition
   103   // Check the "Complementary Slackness" optimality condition
   142   DigraphReader<ListDigraph>(digraph, input).
   142   DigraphReader<ListDigraph>(digraph, input).
   143     arcMap("cost", length).
   143     arcMap("cost", length).
   144     node("source", source).
   144     node("source", source).
   145     node("target", target).
   145     node("target", target).
   146     run();
   146     run();
   147   
   147 
   148   // Find 2 paths
   148   // Find 2 paths
   149   {
   149   {
   150     Suurballe<ListDigraph> suurballe(digraph, length, source, target);
   150     Suurballe<ListDigraph> suurballe(digraph, length, source, target);
   151     check(suurballe.run(2) == 2, "Wrong number of paths");
   151     check(suurballe.run(2) == 2, "Wrong number of paths");
   152     check(checkFlow(digraph, suurballe.flowMap(), source, target, 2),
   152     check(checkFlow(digraph, suurballe.flowMap(), source, target, 2),
   153           "The flow is not feasible");
   153           "The flow is not feasible");
   154     check(suurballe.totalLength() == 510, "The flow is not optimal");
   154     check(suurballe.totalLength() == 510, "The flow is not optimal");
   155     check(checkOptimality(digraph, length, suurballe.flowMap(), 
   155     check(checkOptimality(digraph, length, suurballe.flowMap(),
   156                           suurballe.potentialMap()),
   156                           suurballe.potentialMap()),
   157           "Wrong potentials");
   157           "Wrong potentials");
   158     for (int i = 0; i < suurballe.pathNum(); ++i)
   158     for (int i = 0; i < suurballe.pathNum(); ++i)
   159       check(checkPath(digraph, suurballe.path(i), source, target),
   159       check(checkPath(digraph, suurballe.path(i), source, target),
   160             "Wrong path");
   160             "Wrong path");
   165     Suurballe<ListDigraph> suurballe(digraph, length, source, target);
   165     Suurballe<ListDigraph> suurballe(digraph, length, source, target);
   166     check(suurballe.run(3) == 3, "Wrong number of paths");
   166     check(suurballe.run(3) == 3, "Wrong number of paths");
   167     check(checkFlow(digraph, suurballe.flowMap(), source, target, 3),
   167     check(checkFlow(digraph, suurballe.flowMap(), source, target, 3),
   168           "The flow is not feasible");
   168           "The flow is not feasible");
   169     check(suurballe.totalLength() == 1040, "The flow is not optimal");
   169     check(suurballe.totalLength() == 1040, "The flow is not optimal");
   170     check(checkOptimality(digraph, length, suurballe.flowMap(), 
   170     check(checkOptimality(digraph, length, suurballe.flowMap(),
   171                           suurballe.potentialMap()),
   171                           suurballe.potentialMap()),
   172           "Wrong potentials");
   172           "Wrong potentials");
   173     for (int i = 0; i < suurballe.pathNum(); ++i)
   173     for (int i = 0; i < suurballe.pathNum(); ++i)
   174       check(checkPath(digraph, suurballe.path(i), source, target),
   174       check(checkPath(digraph, suurballe.path(i), source, target),
   175             "Wrong path");
   175             "Wrong path");
   180     Suurballe<ListDigraph> suurballe(digraph, length, source, target);
   180     Suurballe<ListDigraph> suurballe(digraph, length, source, target);
   181     check(suurballe.run(5) == 3, "Wrong number of paths");
   181     check(suurballe.run(5) == 3, "Wrong number of paths");
   182     check(checkFlow(digraph, suurballe.flowMap(), source, target, 3),
   182     check(checkFlow(digraph, suurballe.flowMap(), source, target, 3),
   183           "The flow is not feasible");
   183           "The flow is not feasible");
   184     check(suurballe.totalLength() == 1040, "The flow is not optimal");
   184     check(suurballe.totalLength() == 1040, "The flow is not optimal");
   185     check(checkOptimality(digraph, length, suurballe.flowMap(), 
   185     check(checkOptimality(digraph, length, suurballe.flowMap(),
   186                           suurballe.potentialMap()),
   186                           suurballe.potentialMap()),
   187           "Wrong potentials");
   187           "Wrong potentials");
   188     for (int i = 0; i < suurballe.pathNum(); ++i)
   188     for (int i = 0; i < suurballe.pathNum(); ++i)
   189       check(checkPath(digraph, suurballe.path(i), source, target),
   189       check(checkPath(digraph, suurballe.path(i), source, target),
   190             "Wrong path");
   190             "Wrong path");