test/suurballe_test.cc
author Peter Kovacs <kpeter@inf.elte.hu>
Fri, 16 Oct 2009 09:35:46 +0200
changeset 857 abb95d48e89e
parent 854 9a7e4e606f83
child 858 9f6ed854d409
permissions -rw-r--r--
Add traits class + named parameters to Suurballe (#323)

The following types can be modified using named parameters:
- FlowMap
- PotentialMap
- Path
- Heap + HeapCrossRef
     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   // Find 2 paths
   209   {
   210     Suurballe<ListDigraph> suurballe(digraph, length);
   211     check(suurballe.run(s, t) == 2, "Wrong number of paths");
   212     check(checkFlow(digraph, suurballe.flowMap(), s, t, 2),
   213           "The flow is not feasible");
   214     check(suurballe.totalLength() == 510, "The flow is not optimal");
   215     check(checkOptimality(digraph, length, suurballe.flowMap(),
   216                           suurballe.potentialMap()),
   217           "Wrong potentials");
   218     for (int i = 0; i < suurballe.pathNum(); ++i)
   219       check(checkPath(digraph, suurballe.path(i), s, t), "Wrong path");
   220   }
   221 
   222   // Find 3 paths
   223   {
   224     Suurballe<ListDigraph> suurballe(digraph, length);
   225     check(suurballe.run(s, t, 3) == 3, "Wrong number of paths");
   226     check(checkFlow(digraph, suurballe.flowMap(), s, t, 3),
   227           "The flow is not feasible");
   228     check(suurballe.totalLength() == 1040, "The flow is not optimal");
   229     check(checkOptimality(digraph, length, suurballe.flowMap(),
   230                           suurballe.potentialMap()),
   231           "Wrong potentials");
   232     for (int i = 0; i < suurballe.pathNum(); ++i)
   233       check(checkPath(digraph, suurballe.path(i), s, t), "Wrong path");
   234   }
   235 
   236   // Find 5 paths (only 3 can be found)
   237   {
   238     Suurballe<ListDigraph> suurballe(digraph, length);
   239     check(suurballe.run(s, t, 5) == 3, "Wrong number of paths");
   240     check(checkFlow(digraph, suurballe.flowMap(), s, t, 3),
   241           "The flow is not feasible");
   242     check(suurballe.totalLength() == 1040, "The flow is not optimal");
   243     check(checkOptimality(digraph, length, suurballe.flowMap(),
   244                           suurballe.potentialMap()),
   245           "Wrong potentials");
   246     for (int i = 0; i < suurballe.pathNum(); ++i)
   247       check(checkPath(digraph, suurballe.path(i), s, t), "Wrong path");
   248   }
   249 
   250   return 0;
   251 }