test/suurballe_test.cc
author Alpar Juttner <alpar@cs.elte.hu>
Tue, 16 Mar 2010 21:27:35 +0100
changeset 874 d8ea85825e02
parent 857 abb95d48e89e
child 877 141f9c0db4a3
permissions -rw-r--r--
Merge #314
     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 #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   c = const_suurb_test.totalLength();
   121   f = const_suurb_test.flow(e);
   122   const SuurballeType::FlowMap& fm =
   123     const_suurb_test.flowMap();
   124   c = const_suurb_test.potential(n);
   125   const SuurballeType::PotentialMap& pm =
   126     const_suurb_test.potentialMap();
   127   k = const_suurb_test.pathNum();
   128   Path<Digraph> p = const_suurb_test.path(k);
   129   
   130   ignore_unused_variable_warning(fm);
   131   ignore_unused_variable_warning(pm);
   132 }
   133 
   134 // Check the feasibility of the flow
   135 template <typename Digraph, typename FlowMap>
   136 bool checkFlow( const Digraph& gr, const FlowMap& flow,
   137                 typename Digraph::Node s, typename Digraph::Node t,
   138                 int value )
   139 {
   140   TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
   141   for (ArcIt e(gr); e != INVALID; ++e)
   142     if (!(flow[e] == 0 || flow[e] == 1)) return false;
   143 
   144   for (NodeIt n(gr); n != INVALID; ++n) {
   145     int sum = 0;
   146     for (OutArcIt e(gr, n); e != INVALID; ++e)
   147       sum += flow[e];
   148     for (InArcIt e(gr, n); e != INVALID; ++e)
   149       sum -= flow[e];
   150     if (n == s && sum != value) return false;
   151     if (n == t && sum != -value) return false;
   152     if (n != s && n != t && sum != 0) return false;
   153   }
   154 
   155   return true;
   156 }
   157 
   158 // Check the optimalitiy of the flow
   159 template < typename Digraph, typename CostMap,
   160            typename FlowMap, typename PotentialMap >
   161 bool checkOptimality( const Digraph& gr, const CostMap& cost,
   162                       const FlowMap& flow, const PotentialMap& pi )
   163 {
   164   // Check the "Complementary Slackness" optimality condition
   165   TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
   166   bool opt = true;
   167   for (ArcIt e(gr); e != INVALID; ++e) {
   168     typename CostMap::Value red_cost =
   169       cost[e] + pi[gr.source(e)] - pi[gr.target(e)];
   170     opt = (flow[e] == 0 && red_cost >= 0) ||
   171           (flow[e] == 1 && red_cost <= 0);
   172     if (!opt) break;
   173   }
   174   return opt;
   175 }
   176 
   177 // Check a path
   178 template <typename Digraph, typename Path>
   179 bool checkPath( const Digraph& gr, const Path& path,
   180                 typename Digraph::Node s, typename Digraph::Node t)
   181 {
   182   TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
   183   Node n = s;
   184   for (int i = 0; i < path.length(); ++i) {
   185     if (gr.source(path.nth(i)) != n) return false;
   186     n = gr.target(path.nth(i));
   187   }
   188   return n == t;
   189 }
   190 
   191 
   192 int main()
   193 {
   194   DIGRAPH_TYPEDEFS(ListDigraph);
   195 
   196   // Read the test digraph
   197   ListDigraph digraph;
   198   ListDigraph::ArcMap<int> length(digraph);
   199   Node s, t;
   200 
   201   std::istringstream input(test_lgf);
   202   DigraphReader<ListDigraph>(digraph, input).
   203     arcMap("length", length).
   204     node("source", s).
   205     node("target", t).
   206     run();
   207 
   208   // Check run()
   209   {
   210     Suurballe<ListDigraph> suurballe(digraph, length);
   211     
   212     // Find 2 paths
   213     check(suurballe.run(s, t) == 2, "Wrong number of paths");
   214     check(checkFlow(digraph, suurballe.flowMap(), s, t, 2),
   215           "The flow is not feasible");
   216     check(suurballe.totalLength() == 510, "The flow is not optimal");
   217     check(checkOptimality(digraph, length, suurballe.flowMap(),
   218                           suurballe.potentialMap()),
   219           "Wrong potentials");
   220     for (int i = 0; i < suurballe.pathNum(); ++i)
   221       check(checkPath(digraph, suurballe.path(i), s, t), "Wrong path");
   222    
   223     // Find 3 paths
   224     check(suurballe.run(s, t, 3) == 3, "Wrong number of paths");
   225     check(checkFlow(digraph, suurballe.flowMap(), s, t, 3),
   226           "The flow is not feasible");
   227     check(suurballe.totalLength() == 1040, "The flow is not optimal");
   228     check(checkOptimality(digraph, length, suurballe.flowMap(),
   229                           suurballe.potentialMap()),
   230           "Wrong potentials");
   231     for (int i = 0; i < suurballe.pathNum(); ++i)
   232       check(checkPath(digraph, suurballe.path(i), s, t), "Wrong path");
   233     
   234     // Find 5 paths (only 3 can be found)
   235     check(suurballe.run(s, t, 5) == 3, "Wrong number of paths");
   236     check(checkFlow(digraph, suurballe.flowMap(), s, t, 3),
   237           "The flow is not feasible");
   238     check(suurballe.totalLength() == 1040, "The flow is not optimal");
   239     check(checkOptimality(digraph, length, suurballe.flowMap(),
   240                           suurballe.potentialMap()),
   241           "Wrong potentials");
   242     for (int i = 0; i < suurballe.pathNum(); ++i)
   243       check(checkPath(digraph, suurballe.path(i), s, t), "Wrong path");
   244   }
   245   
   246   // Check fullInit() + start()
   247   {
   248     Suurballe<ListDigraph> suurballe(digraph, length);
   249     suurballe.fullInit(s);
   250     
   251     // Find 2 paths
   252     check(suurballe.start(t) == 2, "Wrong number of paths");
   253     check(suurballe.totalLength() == 510, "The flow is not optimal");
   254 
   255     // Find 3 paths
   256     check(suurballe.start(t, 3) == 3, "Wrong number of paths");
   257     check(suurballe.totalLength() == 1040, "The flow is not optimal");
   258 
   259     // Find 5 paths (only 3 can be found)
   260     check(suurballe.start(t, 5) == 3, "Wrong number of paths");
   261     check(suurballe.totalLength() == 1040, "The flow is not optimal");
   262   }
   263 
   264   return 0;
   265 }