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