test/suurballe_test.cc
author Alpar Juttner <alpar@cs.elte.hu>
Mon, 12 Apr 2010 16:52:48 +0200
branch1.1
changeset 973 290f3ca599d6
parent 463 88ed40ad0d4f
child 927 9a7e4e606f83
child 1081 f1398882a928
child 1171 7e368d9b67f7
permissions -rw-r--r--
Merge bugfix #366 to branch 1.1
alpar@463
     1
/* -*- mode: C++; indent-tabs-mode: nil; -*-
alpar@357
     2
 *
alpar@463
     3
 * This file is a part of LEMON, a generic C++ optimization library.
alpar@357
     4
 *
alpar@463
     5
 * Copyright (C) 2003-2009
alpar@357
     6
 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
alpar@357
     7
 * (Egervary Research Group on Combinatorial Optimization, EGRES).
alpar@357
     8
 *
alpar@357
     9
 * Permission to use, modify and distribute this software is granted
alpar@357
    10
 * provided that this copyright notice appears in all copies. For
alpar@357
    11
 * precise terms see the accompanying LICENSE file.
alpar@357
    12
 *
alpar@357
    13
 * This software is provided "AS IS" with no warranty of any kind,
alpar@357
    14
 * express or implied, and with no claim as to its suitability for any
alpar@357
    15
 * purpose.
alpar@357
    16
 *
alpar@357
    17
 */
alpar@357
    18
alpar@357
    19
#include <iostream>
alpar@357
    20
alpar@357
    21
#include <lemon/list_graph.h>
alpar@357
    22
#include <lemon/lgf_reader.h>
alpar@357
    23
#include <lemon/path.h>
alpar@357
    24
#include <lemon/suurballe.h>
kpeter@670
    25
#include <lemon/concepts/digraph.h>
alpar@357
    26
alpar@357
    27
#include "test_tools.h"
alpar@357
    28
alpar@357
    29
using namespace lemon;
alpar@357
    30
alpar@442
    31
char test_lgf[] =
alpar@442
    32
  "@nodes\n"
kpeter@670
    33
  "label\n"
kpeter@670
    34
  "1\n"
kpeter@670
    35
  "2\n"
kpeter@670
    36
  "3\n"
kpeter@670
    37
  "4\n"
kpeter@670
    38
  "5\n"
kpeter@670
    39
  "6\n"
kpeter@670
    40
  "7\n"
kpeter@670
    41
  "8\n"
kpeter@670
    42
  "9\n"
kpeter@670
    43
  "10\n"
kpeter@670
    44
  "11\n"
kpeter@670
    45
  "12\n"
alpar@442
    46
  "@arcs\n"
kpeter@670
    47
  "      length\n"
kpeter@670
    48
  " 1  2  70\n"
kpeter@670
    49
  " 1  3 150\n"
kpeter@670
    50
  " 1  4  80\n"
kpeter@670
    51
  " 2  8  80\n"
kpeter@670
    52
  " 3  5 140\n"
kpeter@670
    53
  " 4  6  60\n"
kpeter@670
    54
  " 4  7  80\n"
kpeter@670
    55
  " 4  8 110\n"
kpeter@670
    56
  " 5  7  60\n"
kpeter@670
    57
  " 5 11 120\n"
kpeter@670
    58
  " 6  3   0\n"
kpeter@670
    59
  " 6  9 140\n"
kpeter@670
    60
  " 6 10  90\n"
kpeter@670
    61
  " 7  1  30\n"
kpeter@670
    62
  " 8 12  60\n"
kpeter@670
    63
  " 9 12  50\n"
kpeter@670
    64
  "10 12  70\n"
kpeter@670
    65
  "10  2 100\n"
kpeter@670
    66
  "10  7  60\n"
kpeter@670
    67
  "11 10  20\n"
kpeter@670
    68
  "12 11  30\n"
alpar@442
    69
  "@attributes\n"
alpar@442
    70
  "source  1\n"
alpar@442
    71
  "target 12\n"
alpar@442
    72
  "@end\n";
alpar@442
    73
kpeter@670
    74
// Check the interface of Suurballe
kpeter@670
    75
void checkSuurballeCompile()
kpeter@670
    76
{
kpeter@670
    77
  typedef int VType;
kpeter@670
    78
  typedef concepts::Digraph Digraph;
kpeter@670
    79
kpeter@670
    80
  typedef Digraph::Node Node;
kpeter@670
    81
  typedef Digraph::Arc Arc;
kpeter@670
    82
  typedef concepts::ReadMap<Arc, VType> LengthMap;
kpeter@670
    83
  
kpeter@670
    84
  typedef Suurballe<Digraph, LengthMap> SuurballeType;
kpeter@670
    85
kpeter@670
    86
  Digraph g;
kpeter@670
    87
  Node n;
kpeter@670
    88
  Arc e;
kpeter@670
    89
  LengthMap len;
kpeter@670
    90
  SuurballeType::FlowMap flow(g);
kpeter@670
    91
  SuurballeType::PotentialMap pi(g);
kpeter@670
    92
kpeter@670
    93
  SuurballeType suurb_test(g, len);
kpeter@670
    94
  const SuurballeType& const_suurb_test = suurb_test;
kpeter@670
    95
kpeter@670
    96
  suurb_test
kpeter@670
    97
    .flowMap(flow)
kpeter@670
    98
    .potentialMap(pi);
kpeter@670
    99
kpeter@670
   100
  int k;
kpeter@670
   101
  k = suurb_test.run(n, n);
kpeter@670
   102
  k = suurb_test.run(n, n, k);
kpeter@670
   103
  suurb_test.init(n);
kpeter@670
   104
  k = suurb_test.findFlow(n);
kpeter@670
   105
  k = suurb_test.findFlow(n, k);
kpeter@670
   106
  suurb_test.findPaths();
kpeter@670
   107
  
kpeter@670
   108
  int f;
kpeter@670
   109
  VType c;
kpeter@670
   110
  c = const_suurb_test.totalLength();
kpeter@670
   111
  f = const_suurb_test.flow(e);
kpeter@670
   112
  const SuurballeType::FlowMap& fm =
kpeter@670
   113
    const_suurb_test.flowMap();
kpeter@670
   114
  c = const_suurb_test.potential(n);
kpeter@670
   115
  const SuurballeType::PotentialMap& pm =
kpeter@670
   116
    const_suurb_test.potentialMap();
kpeter@670
   117
  k = const_suurb_test.pathNum();
kpeter@670
   118
  Path<Digraph> p = const_suurb_test.path(k);
kpeter@670
   119
  
kpeter@670
   120
  ignore_unused_variable_warning(fm);
kpeter@670
   121
  ignore_unused_variable_warning(pm);
kpeter@670
   122
}
kpeter@670
   123
kpeter@358
   124
// Check the feasibility of the flow
alpar@357
   125
template <typename Digraph, typename FlowMap>
alpar@463
   126
bool checkFlow( const Digraph& gr, const FlowMap& flow,
alpar@357
   127
                typename Digraph::Node s, typename Digraph::Node t,
alpar@357
   128
                int value )
alpar@357
   129
{
alpar@357
   130
  TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
alpar@357
   131
  for (ArcIt e(gr); e != INVALID; ++e)
alpar@357
   132
    if (!(flow[e] == 0 || flow[e] == 1)) return false;
alpar@357
   133
alpar@357
   134
  for (NodeIt n(gr); n != INVALID; ++n) {
alpar@357
   135
    int sum = 0;
alpar@357
   136
    for (OutArcIt e(gr, n); e != INVALID; ++e)
alpar@357
   137
      sum += flow[e];
alpar@357
   138
    for (InArcIt e(gr, n); e != INVALID; ++e)
alpar@357
   139
      sum -= flow[e];
alpar@357
   140
    if (n == s && sum != value) return false;
alpar@357
   141
    if (n == t && sum != -value) return false;
alpar@357
   142
    if (n != s && n != t && sum != 0) return false;
alpar@357
   143
  }
alpar@357
   144
alpar@357
   145
  return true;
alpar@357
   146
}
alpar@357
   147
kpeter@358
   148
// Check the optimalitiy of the flow
alpar@463
   149
template < typename Digraph, typename CostMap,
alpar@357
   150
           typename FlowMap, typename PotentialMap >
alpar@357
   151
bool checkOptimality( const Digraph& gr, const CostMap& cost,
alpar@357
   152
                      const FlowMap& flow, const PotentialMap& pi )
alpar@357
   153
{
kpeter@358
   154
  // Check the "Complementary Slackness" optimality condition
alpar@357
   155
  TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
alpar@357
   156
  bool opt = true;
alpar@357
   157
  for (ArcIt e(gr); e != INVALID; ++e) {
alpar@357
   158
    typename CostMap::Value red_cost =
alpar@357
   159
      cost[e] + pi[gr.source(e)] - pi[gr.target(e)];
alpar@357
   160
    opt = (flow[e] == 0 && red_cost >= 0) ||
alpar@357
   161
          (flow[e] == 1 && red_cost <= 0);
alpar@357
   162
    if (!opt) break;
alpar@357
   163
  }
alpar@357
   164
  return opt;
alpar@357
   165
}
alpar@357
   166
kpeter@358
   167
// Check a path
kpeter@358
   168
template <typename Digraph, typename Path>
alpar@357
   169
bool checkPath( const Digraph& gr, const Path& path,
alpar@357
   170
                typename Digraph::Node s, typename Digraph::Node t)
alpar@357
   171
{
alpar@357
   172
  TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
alpar@357
   173
  Node n = s;
alpar@357
   174
  for (int i = 0; i < path.length(); ++i) {
alpar@357
   175
    if (gr.source(path.nth(i)) != n) return false;
alpar@357
   176
    n = gr.target(path.nth(i));
alpar@357
   177
  }
alpar@357
   178
  return n == t;
alpar@357
   179
}
alpar@357
   180
alpar@357
   181
alpar@357
   182
int main()
alpar@357
   183
{
alpar@357
   184
  DIGRAPH_TYPEDEFS(ListDigraph);
alpar@357
   185
kpeter@358
   186
  // Read the test digraph
alpar@357
   187
  ListDigraph digraph;
alpar@357
   188
  ListDigraph::ArcMap<int> length(digraph);
kpeter@670
   189
  Node s, t;
alpar@357
   190
alpar@442
   191
  std::istringstream input(test_lgf);
alpar@357
   192
  DigraphReader<ListDigraph>(digraph, input).
kpeter@670
   193
    arcMap("length", length).
kpeter@670
   194
    node("source", s).
kpeter@670
   195
    node("target", t).
alpar@357
   196
    run();
alpar@463
   197
kpeter@358
   198
  // Find 2 paths
alpar@357
   199
  {
kpeter@670
   200
    Suurballe<ListDigraph> suurballe(digraph, length);
kpeter@670
   201
    check(suurballe.run(s, t) == 2, "Wrong number of paths");
kpeter@670
   202
    check(checkFlow(digraph, suurballe.flowMap(), s, t, 2),
alpar@357
   203
          "The flow is not feasible");
alpar@357
   204
    check(suurballe.totalLength() == 510, "The flow is not optimal");
alpar@463
   205
    check(checkOptimality(digraph, length, suurballe.flowMap(),
alpar@357
   206
                          suurballe.potentialMap()),
alpar@357
   207
          "Wrong potentials");
alpar@357
   208
    for (int i = 0; i < suurballe.pathNum(); ++i)
kpeter@670
   209
      check(checkPath(digraph, suurballe.path(i), s, t), "Wrong path");
alpar@357
   210
  }
alpar@357
   211
kpeter@358
   212
  // Find 3 paths
alpar@357
   213
  {
kpeter@670
   214
    Suurballe<ListDigraph> suurballe(digraph, length);
kpeter@670
   215
    check(suurballe.run(s, t, 3) == 3, "Wrong number of paths");
kpeter@670
   216
    check(checkFlow(digraph, suurballe.flowMap(), s, t, 3),
alpar@357
   217
          "The flow is not feasible");
alpar@357
   218
    check(suurballe.totalLength() == 1040, "The flow is not optimal");
alpar@463
   219
    check(checkOptimality(digraph, length, suurballe.flowMap(),
alpar@357
   220
                          suurballe.potentialMap()),
alpar@357
   221
          "Wrong potentials");
alpar@357
   222
    for (int i = 0; i < suurballe.pathNum(); ++i)
kpeter@670
   223
      check(checkPath(digraph, suurballe.path(i), s, t), "Wrong path");
alpar@357
   224
  }
alpar@357
   225
kpeter@358
   226
  // Find 5 paths (only 3 can be found)
alpar@357
   227
  {
kpeter@670
   228
    Suurballe<ListDigraph> suurballe(digraph, length);
kpeter@670
   229
    check(suurballe.run(s, t, 5) == 3, "Wrong number of paths");
kpeter@670
   230
    check(checkFlow(digraph, suurballe.flowMap(), s, t, 3),
alpar@357
   231
          "The flow is not feasible");
alpar@357
   232
    check(suurballe.totalLength() == 1040, "The flow is not optimal");
alpar@463
   233
    check(checkOptimality(digraph, length, suurballe.flowMap(),
alpar@357
   234
                          suurballe.potentialMap()),
alpar@357
   235
          "Wrong potentials");
alpar@357
   236
    for (int i = 0; i < suurballe.pathNum(); ++i)
kpeter@670
   237
      check(checkPath(digraph, suurballe.path(i), s, t), "Wrong path");
alpar@357
   238
  }
alpar@357
   239
alpar@357
   240
  return 0;
alpar@357
   241
}