test/suurballe_test.cc
author Peter Kovacs <kpeter@inf.elte.hu>
Thu, 12 Nov 2009 23:29:42 +0100
changeset 808 9c428bb2b105
parent 440 88ed40ad0d4f
child 854 9a7e4e606f83
child 1007 7e368d9b67f7
permissions -rw-r--r--
Port CostScaling from SVN -r3524 (#180)
     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 }