test/suurballe_test.cc
author Balazs Dezso <deba@inf.elte.hu>
Thu, 24 Jun 2010 09:27:53 +0200
changeset 891 bb70ad62c95f
parent 440 88ed40ad0d4f
child 854 9a7e4e606f83
child 1007 7e368d9b67f7
permissions -rw-r--r--
Fix critical bug in preflow (#372)

The wrong transition between the bound decrease and highest active
heuristics caused the bug. The last node chosen in bound decrease mode
is used in the first iteration in highest active mode.
     1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
     2  *
     3  * This file is a part of LEMON, a generic C++ optimization library.
     4  *
     5  * Copyright (C) 2003-2009
     6  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     7  * (Egervary Research Group on Combinatorial Optimization, EGRES).
     8  *
     9  * Permission to use, modify and distribute this software is granted
    10  * provided that this copyright notice appears in all copies. For
    11  * precise terms see the accompanying LICENSE file.
    12  *
    13  * This software is provided "AS IS" with no warranty of any kind,
    14  * express or implied, and with no claim as to its suitability for any
    15  * purpose.
    16  *
    17  */
    18 
    19 #include <iostream>
    20 
    21 #include <lemon/list_graph.h>
    22 #include <lemon/lgf_reader.h>
    23 #include <lemon/path.h>
    24 #include <lemon/suurballe.h>
    25 #include <lemon/concepts/digraph.h>
    26 
    27 #include "test_tools.h"
    28 
    29 using namespace lemon;
    30 
    31 char test_lgf[] =
    32   "@nodes\n"
    33   "label\n"
    34   "1\n"
    35   "2\n"
    36   "3\n"
    37   "4\n"
    38   "5\n"
    39   "6\n"
    40   "7\n"
    41   "8\n"
    42   "9\n"
    43   "10\n"
    44   "11\n"
    45   "12\n"
    46   "@arcs\n"
    47   "      length\n"
    48   " 1  2  70\n"
    49   " 1  3 150\n"
    50   " 1  4  80\n"
    51   " 2  8  80\n"
    52   " 3  5 140\n"
    53   " 4  6  60\n"
    54   " 4  7  80\n"
    55   " 4  8 110\n"
    56   " 5  7  60\n"
    57   " 5 11 120\n"
    58   " 6  3   0\n"
    59   " 6  9 140\n"
    60   " 6 10  90\n"
    61   " 7  1  30\n"
    62   " 8 12  60\n"
    63   " 9 12  50\n"
    64   "10 12  70\n"
    65   "10  2 100\n"
    66   "10  7  60\n"
    67   "11 10  20\n"
    68   "12 11  30\n"
    69   "@attributes\n"
    70   "source  1\n"
    71   "target 12\n"
    72   "@end\n";
    73 
    74 // Check the interface of Suurballe
    75 void checkSuurballeCompile()
    76 {
    77   typedef int VType;
    78   typedef concepts::Digraph Digraph;
    79 
    80   typedef Digraph::Node Node;
    81   typedef Digraph::Arc Arc;
    82   typedef concepts::ReadMap<Arc, VType> LengthMap;
    83   
    84   typedef Suurballe<Digraph, LengthMap> SuurballeType;
    85 
    86   Digraph g;
    87   Node n;
    88   Arc e;
    89   LengthMap len;
    90   SuurballeType::FlowMap flow(g);
    91   SuurballeType::PotentialMap pi(g);
    92 
    93   SuurballeType suurb_test(g, len);
    94   const SuurballeType& const_suurb_test = suurb_test;
    95 
    96   suurb_test
    97     .flowMap(flow)
    98     .potentialMap(pi);
    99 
   100   int k;
   101   k = suurb_test.run(n, n);
   102   k = suurb_test.run(n, n, k);
   103   suurb_test.init(n);
   104   k = suurb_test.findFlow(n);
   105   k = suurb_test.findFlow(n, k);
   106   suurb_test.findPaths();
   107   
   108   int f;
   109   VType c;
   110   c = const_suurb_test.totalLength();
   111   f = const_suurb_test.flow(e);
   112   const SuurballeType::FlowMap& fm =
   113     const_suurb_test.flowMap();
   114   c = const_suurb_test.potential(n);
   115   const SuurballeType::PotentialMap& pm =
   116     const_suurb_test.potentialMap();
   117   k = const_suurb_test.pathNum();
   118   Path<Digraph> p = const_suurb_test.path(k);
   119   
   120   ignore_unused_variable_warning(fm);
   121   ignore_unused_variable_warning(pm);
   122 }
   123 
   124 // Check the feasibility of the flow
   125 template <typename Digraph, typename FlowMap>
   126 bool checkFlow( const Digraph& gr, const FlowMap& flow,
   127                 typename Digraph::Node s, typename Digraph::Node t,
   128                 int value )
   129 {
   130   TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
   131   for (ArcIt e(gr); e != INVALID; ++e)
   132     if (!(flow[e] == 0 || flow[e] == 1)) return false;
   133 
   134   for (NodeIt n(gr); n != INVALID; ++n) {
   135     int sum = 0;
   136     for (OutArcIt e(gr, n); e != INVALID; ++e)
   137       sum += flow[e];
   138     for (InArcIt e(gr, n); e != INVALID; ++e)
   139       sum -= flow[e];
   140     if (n == s && sum != value) return false;
   141     if (n == t && sum != -value) return false;
   142     if (n != s && n != t && sum != 0) return false;
   143   }
   144 
   145   return true;
   146 }
   147 
   148 // Check the optimalitiy of the flow
   149 template < typename Digraph, typename CostMap,
   150            typename FlowMap, typename PotentialMap >
   151 bool checkOptimality( const Digraph& gr, const CostMap& cost,
   152                       const FlowMap& flow, const PotentialMap& pi )
   153 {
   154   // Check the "Complementary Slackness" optimality condition
   155   TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
   156   bool opt = true;
   157   for (ArcIt e(gr); e != INVALID; ++e) {
   158     typename CostMap::Value red_cost =
   159       cost[e] + pi[gr.source(e)] - pi[gr.target(e)];
   160     opt = (flow[e] == 0 && red_cost >= 0) ||
   161           (flow[e] == 1 && red_cost <= 0);
   162     if (!opt) break;
   163   }
   164   return opt;
   165 }
   166 
   167 // Check a path
   168 template <typename Digraph, typename Path>
   169 bool checkPath( const Digraph& gr, const Path& path,
   170                 typename Digraph::Node s, typename Digraph::Node t)
   171 {
   172   TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
   173   Node n = s;
   174   for (int i = 0; i < path.length(); ++i) {
   175     if (gr.source(path.nth(i)) != n) return false;
   176     n = gr.target(path.nth(i));
   177   }
   178   return n == t;
   179 }
   180 
   181 
   182 int main()
   183 {
   184   DIGRAPH_TYPEDEFS(ListDigraph);
   185 
   186   // Read the test digraph
   187   ListDigraph digraph;
   188   ListDigraph::ArcMap<int> length(digraph);
   189   Node s, t;
   190 
   191   std::istringstream input(test_lgf);
   192   DigraphReader<ListDigraph>(digraph, input).
   193     arcMap("length", length).
   194     node("source", s).
   195     node("target", t).
   196     run();
   197 
   198   // Find 2 paths
   199   {
   200     Suurballe<ListDigraph> suurballe(digraph, length);
   201     check(suurballe.run(s, t) == 2, "Wrong number of paths");
   202     check(checkFlow(digraph, suurballe.flowMap(), s, t, 2),
   203           "The flow is not feasible");
   204     check(suurballe.totalLength() == 510, "The flow is not optimal");
   205     check(checkOptimality(digraph, length, suurballe.flowMap(),
   206                           suurballe.potentialMap()),
   207           "Wrong potentials");
   208     for (int i = 0; i < suurballe.pathNum(); ++i)
   209       check(checkPath(digraph, suurballe.path(i), s, t), "Wrong path");
   210   }
   211 
   212   // Find 3 paths
   213   {
   214     Suurballe<ListDigraph> suurballe(digraph, length);
   215     check(suurballe.run(s, t, 3) == 3, "Wrong number of paths");
   216     check(checkFlow(digraph, suurballe.flowMap(), s, t, 3),
   217           "The flow is not feasible");
   218     check(suurballe.totalLength() == 1040, "The flow is not optimal");
   219     check(checkOptimality(digraph, length, suurballe.flowMap(),
   220                           suurballe.potentialMap()),
   221           "Wrong potentials");
   222     for (int i = 0; i < suurballe.pathNum(); ++i)
   223       check(checkPath(digraph, suurballe.path(i), s, t), "Wrong path");
   224   }
   225 
   226   // Find 5 paths (only 3 can be found)
   227   {
   228     Suurballe<ListDigraph> suurballe(digraph, length);
   229     check(suurballe.run(s, t, 5) == 3, "Wrong number of paths");
   230     check(checkFlow(digraph, suurballe.flowMap(), s, t, 3),
   231           "The flow is not feasible");
   232     check(suurballe.totalLength() == 1040, "The flow is not optimal");
   233     check(checkOptimality(digraph, length, suurballe.flowMap(),
   234                           suurballe.potentialMap()),
   235           "Wrong potentials");
   236     for (int i = 0; i < suurballe.pathNum(); ++i)
   237       check(checkPath(digraph, suurballe.path(i), s, t), "Wrong path");
   238   }
   239 
   240   return 0;
   241 }