test/suurballe_test.cc
author Alpar Juttner <alpar@cs.elte.hu>
Wed, 28 Nov 2012 11:54:43 +0100
changeset 970 d216e1c8b3fa
parent 877 141f9c0db4a3
parent 969 7e368d9b67f7
child 983 8b2d4e5d96e4
permissions -rw-r--r--
Merge #453 to branches >=1.2
     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-2010
     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 #include <lemon/concepts/heap.h>
    27 
    28 #include "test_tools.h"
    29 
    30 using namespace lemon;
    31 
    32 char test_lgf[] =
    33   "@nodes\n"
    34   "label\n"
    35   "1\n"
    36   "2\n"
    37   "3\n"
    38   "4\n"
    39   "5\n"
    40   "6\n"
    41   "7\n"
    42   "8\n"
    43   "9\n"
    44   "10\n"
    45   "11\n"
    46   "12\n"
    47   "@arcs\n"
    48   "      length\n"
    49   " 1  2  70\n"
    50   " 1  3 150\n"
    51   " 1  4  80\n"
    52   " 2  8  80\n"
    53   " 3  5 140\n"
    54   " 4  6  60\n"
    55   " 4  7  80\n"
    56   " 4  8 110\n"
    57   " 5  7  60\n"
    58   " 5 11 120\n"
    59   " 6  3   0\n"
    60   " 6  9 140\n"
    61   " 6 10  90\n"
    62   " 7  1  30\n"
    63   " 8 12  60\n"
    64   " 9 12  50\n"
    65   "10 12  70\n"
    66   "10  2 100\n"
    67   "10  7  60\n"
    68   "11 10  20\n"
    69   "12 11  30\n"
    70   "@attributes\n"
    71   "source  1\n"
    72   "target 12\n"
    73   "@end\n";
    74 
    75 // Check the interface of Suurballe
    76 void checkSuurballeCompile()
    77 {
    78   typedef int VType;
    79   typedef concepts::Digraph Digraph;
    80 
    81   typedef Digraph::Node Node;
    82   typedef Digraph::Arc Arc;
    83   typedef concepts::ReadMap<Arc, VType> LengthMap;
    84 
    85   typedef Suurballe<Digraph, LengthMap> ST;
    86   typedef Suurballe<Digraph, LengthMap>
    87     ::SetFlowMap<ST::FlowMap>
    88     ::SetPotentialMap<ST::PotentialMap>
    89     ::SetPath<SimplePath<Digraph> >
    90     ::SetHeap<concepts::Heap<VType, Digraph::NodeMap<int> > >
    91     ::Create SuurballeType;
    92 
    93   Digraph g;
    94   Node n;
    95   Arc e;
    96   LengthMap len;
    97   SuurballeType::FlowMap flow(g);
    98   SuurballeType::PotentialMap pi(g);
    99 
   100   SuurballeType suurb_test(g, len);
   101   const SuurballeType& const_suurb_test = suurb_test;
   102 
   103   suurb_test
   104     .flowMap(flow)
   105     .potentialMap(pi);
   106 
   107   int k;
   108   k = suurb_test.run(n, n);
   109   k = suurb_test.run(n, n, k);
   110   suurb_test.init(n);
   111   suurb_test.fullInit(n);
   112   suurb_test.start(n);
   113   suurb_test.start(n, k);
   114   k = suurb_test.findFlow(n);
   115   k = suurb_test.findFlow(n, k);
   116   suurb_test.findPaths();
   117 
   118   int f;
   119   VType c;
   120   ignore_unused_variable_warning(f,c);
   121 
   122   c = const_suurb_test.totalLength();
   123   f = const_suurb_test.flow(e);
   124   const SuurballeType::FlowMap& fm =
   125     const_suurb_test.flowMap();
   126   c = const_suurb_test.potential(n);
   127   const SuurballeType::PotentialMap& pm =
   128     const_suurb_test.potentialMap();
   129   k = const_suurb_test.pathNum();
   130   Path<Digraph> p = const_suurb_test.path(k);
   131 
   132   ignore_unused_variable_warning(fm);
   133   ignore_unused_variable_warning(pm);
   134 }
   135 
   136 // Check the feasibility of the flow
   137 template <typename Digraph, typename FlowMap>
   138 bool checkFlow( const Digraph& gr, const FlowMap& flow,
   139                 typename Digraph::Node s, typename Digraph::Node t,
   140                 int value )
   141 {
   142   TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
   143   for (ArcIt e(gr); e != INVALID; ++e)
   144     if (!(flow[e] == 0 || flow[e] == 1)) return false;
   145 
   146   for (NodeIt n(gr); n != INVALID; ++n) {
   147     int sum = 0;
   148     for (OutArcIt e(gr, n); e != INVALID; ++e)
   149       sum += flow[e];
   150     for (InArcIt e(gr, n); e != INVALID; ++e)
   151       sum -= flow[e];
   152     if (n == s && sum != value) return false;
   153     if (n == t && sum != -value) return false;
   154     if (n != s && n != t && sum != 0) return false;
   155   }
   156 
   157   return true;
   158 }
   159 
   160 // Check the optimalitiy of the flow
   161 template < typename Digraph, typename CostMap,
   162            typename FlowMap, typename PotentialMap >
   163 bool checkOptimality( const Digraph& gr, const CostMap& cost,
   164                       const FlowMap& flow, const PotentialMap& pi )
   165 {
   166   // Check the "Complementary Slackness" optimality condition
   167   TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
   168   bool opt = true;
   169   for (ArcIt e(gr); e != INVALID; ++e) {
   170     typename CostMap::Value red_cost =
   171       cost[e] + pi[gr.source(e)] - pi[gr.target(e)];
   172     opt = (flow[e] == 0 && red_cost >= 0) ||
   173           (flow[e] == 1 && red_cost <= 0);
   174     if (!opt) break;
   175   }
   176   return opt;
   177 }
   178 
   179 // Check a path
   180 template <typename Digraph, typename Path>
   181 bool checkPath( const Digraph& gr, const Path& path,
   182                 typename Digraph::Node s, typename Digraph::Node t)
   183 {
   184   TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
   185   Node n = s;
   186   for (int i = 0; i < path.length(); ++i) {
   187     if (gr.source(path.nth(i)) != n) return false;
   188     n = gr.target(path.nth(i));
   189   }
   190   return n == t;
   191 }
   192 
   193 
   194 int main()
   195 {
   196   DIGRAPH_TYPEDEFS(ListDigraph);
   197 
   198   // Read the test digraph
   199   ListDigraph digraph;
   200   ListDigraph::ArcMap<int> length(digraph);
   201   Node s, t;
   202 
   203   std::istringstream input(test_lgf);
   204   DigraphReader<ListDigraph>(digraph, input).
   205     arcMap("length", length).
   206     node("source", s).
   207     node("target", t).
   208     run();
   209 
   210   // Check run()
   211   {
   212     Suurballe<ListDigraph> suurballe(digraph, length);
   213 
   214     // Find 2 paths
   215     check(suurballe.run(s, t) == 2, "Wrong number of paths");
   216     check(checkFlow(digraph, suurballe.flowMap(), s, t, 2),
   217           "The flow is not feasible");
   218     check(suurballe.totalLength() == 510, "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     // Find 3 paths
   226     check(suurballe.run(s, t, 3) == 3, "Wrong number of paths");
   227     check(checkFlow(digraph, suurballe.flowMap(), s, t, 3),
   228           "The flow is not feasible");
   229     check(suurballe.totalLength() == 1040, "The flow is not optimal");
   230     check(checkOptimality(digraph, length, suurballe.flowMap(),
   231                           suurballe.potentialMap()),
   232           "Wrong potentials");
   233     for (int i = 0; i < suurballe.pathNum(); ++i)
   234       check(checkPath(digraph, suurballe.path(i), s, t), "Wrong path");
   235 
   236     // Find 5 paths (only 3 can be found)
   237     check(suurballe.run(s, t, 5) == 3, "Wrong number of paths");
   238     check(checkFlow(digraph, suurballe.flowMap(), s, t, 3),
   239           "The flow is not feasible");
   240     check(suurballe.totalLength() == 1040, "The flow is not optimal");
   241     check(checkOptimality(digraph, length, suurballe.flowMap(),
   242                           suurballe.potentialMap()),
   243           "Wrong potentials");
   244     for (int i = 0; i < suurballe.pathNum(); ++i)
   245       check(checkPath(digraph, suurballe.path(i), s, t), "Wrong path");
   246   }
   247 
   248   // Check fullInit() + start()
   249   {
   250     Suurballe<ListDigraph> suurballe(digraph, length);
   251     suurballe.fullInit(s);
   252 
   253     // Find 2 paths
   254     check(suurballe.start(t) == 2, "Wrong number of paths");
   255     check(suurballe.totalLength() == 510, "The flow is not optimal");
   256 
   257     // Find 3 paths
   258     check(suurballe.start(t, 3) == 3, "Wrong number of paths");
   259     check(suurballe.totalLength() == 1040, "The flow is not optimal");
   260 
   261     // Find 5 paths (only 3 can be found)
   262     check(suurballe.start(t, 5) == 3, "Wrong number of paths");
   263     check(suurballe.totalLength() == 1040, "The flow is not optimal");
   264   }
   265 
   266   return 0;
   267 }