test/suurballe_test.cc
author Alpar Juttner <alpar@cs.elte.hu>
Fri, 09 Aug 2013 14:01:24 +0200
branch1.1
changeset 1267 bd24650d5cd2
parent 1172 c18ed26f016c
parent 1257 3e711ee55d31
permissions -rw-r--r--
Merge bugfix #439 to branch 1.1
     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-2011
     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   ::lemon::ignore_unused_variable_warning(f,c);
   111 
   112   c = const_suurb_test.totalLength();
   113   f = const_suurb_test.flow(e);
   114   const SuurballeType::FlowMap& fm =
   115     const_suurb_test.flowMap();
   116   c = const_suurb_test.potential(n);
   117   const SuurballeType::PotentialMap& pm =
   118     const_suurb_test.potentialMap();
   119   k = const_suurb_test.pathNum();
   120   Path<Digraph> p = const_suurb_test.path(k);
   121 
   122   ::lemon::ignore_unused_variable_warning(fm);
   123   ::lemon::ignore_unused_variable_warning(pm);
   124 }
   125 
   126 // Check the feasibility of the flow
   127 template <typename Digraph, typename FlowMap>
   128 bool checkFlow( const Digraph& gr, const FlowMap& flow,
   129                 typename Digraph::Node s, typename Digraph::Node t,
   130                 int value )
   131 {
   132   TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
   133   for (ArcIt e(gr); e != INVALID; ++e)
   134     if (!(flow[e] == 0 || flow[e] == 1)) return false;
   135 
   136   for (NodeIt n(gr); n != INVALID; ++n) {
   137     int sum = 0;
   138     for (OutArcIt e(gr, n); e != INVALID; ++e)
   139       sum += flow[e];
   140     for (InArcIt e(gr, n); e != INVALID; ++e)
   141       sum -= flow[e];
   142     if (n == s && sum != value) return false;
   143     if (n == t && sum != -value) return false;
   144     if (n != s && n != t && sum != 0) return false;
   145   }
   146 
   147   return true;
   148 }
   149 
   150 // Check the optimalitiy of the flow
   151 template < typename Digraph, typename CostMap,
   152            typename FlowMap, typename PotentialMap >
   153 bool checkOptimality( const Digraph& gr, const CostMap& cost,
   154                       const FlowMap& flow, const PotentialMap& pi )
   155 {
   156   // Check the "Complementary Slackness" optimality condition
   157   TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
   158   bool opt = true;
   159   for (ArcIt e(gr); e != INVALID; ++e) {
   160     typename CostMap::Value red_cost =
   161       cost[e] + pi[gr.source(e)] - pi[gr.target(e)];
   162     opt = (flow[e] == 0 && red_cost >= 0) ||
   163           (flow[e] == 1 && red_cost <= 0);
   164     if (!opt) break;
   165   }
   166   return opt;
   167 }
   168 
   169 // Check a path
   170 template <typename Digraph, typename Path>
   171 bool checkPath( const Digraph& gr, const Path& path,
   172                 typename Digraph::Node s, typename Digraph::Node t)
   173 {
   174   TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
   175   Node n = s;
   176   for (int i = 0; i < path.length(); ++i) {
   177     if (gr.source(path.nth(i)) != n) return false;
   178     n = gr.target(path.nth(i));
   179   }
   180   return n == t;
   181 }
   182 
   183 
   184 int main()
   185 {
   186   DIGRAPH_TYPEDEFS(ListDigraph);
   187 
   188   // Read the test digraph
   189   ListDigraph digraph;
   190   ListDigraph::ArcMap<int> length(digraph);
   191   Node s, t;
   192 
   193   std::istringstream input(test_lgf);
   194   DigraphReader<ListDigraph>(digraph, input).
   195     arcMap("length", length).
   196     node("source", s).
   197     node("target", t).
   198     run();
   199 
   200   // Find 2 paths
   201   {
   202     Suurballe<ListDigraph> suurballe(digraph, length);
   203     check(suurballe.run(s, t) == 2, "Wrong number of paths");
   204     check(checkFlow(digraph, suurballe.flowMap(), s, t, 2),
   205           "The flow is not feasible");
   206     check(suurballe.totalLength() == 510, "The flow is not optimal");
   207     check(checkOptimality(digraph, length, suurballe.flowMap(),
   208                           suurballe.potentialMap()),
   209           "Wrong potentials");
   210     for (int i = 0; i < suurballe.pathNum(); ++i)
   211       check(checkPath(digraph, suurballe.path(i), s, t), "Wrong path");
   212   }
   213 
   214   // Find 3 paths
   215   {
   216     Suurballe<ListDigraph> suurballe(digraph, length);
   217     check(suurballe.run(s, t, 3) == 3, "Wrong number of paths");
   218     check(checkFlow(digraph, suurballe.flowMap(), s, t, 3),
   219           "The flow is not feasible");
   220     check(suurballe.totalLength() == 1040, "The flow is not optimal");
   221     check(checkOptimality(digraph, length, suurballe.flowMap(),
   222                           suurballe.potentialMap()),
   223           "Wrong potentials");
   224     for (int i = 0; i < suurballe.pathNum(); ++i)
   225       check(checkPath(digraph, suurballe.path(i), s, t), "Wrong path");
   226   }
   227 
   228   // Find 5 paths (only 3 can be found)
   229   {
   230     Suurballe<ListDigraph> suurballe(digraph, length);
   231     check(suurballe.run(s, t, 5) == 3, "Wrong number of paths");
   232     check(checkFlow(digraph, suurballe.flowMap(), s, t, 3),
   233           "The flow is not feasible");
   234     check(suurballe.totalLength() == 1040, "The flow is not optimal");
   235     check(checkOptimality(digraph, length, suurballe.flowMap(),
   236                           suurballe.potentialMap()),
   237           "Wrong potentials");
   238     for (int i = 0; i < suurballe.pathNum(); ++i)
   239       check(checkPath(digraph, suurballe.path(i), s, t), "Wrong path");
   240   }
   241 
   242   return 0;
   243 }