test/suurballe_test.cc
author Peter Kovacs <kpeter@inf.elte.hu>
Tue, 24 Mar 2009 00:18:25 +0100
changeset 604 8c3112a66878
parent 423 ff48c2738fb2
child 623 7c1324b35d89
permissions -rw-r--r--
Use XTI implementation instead of ATI in NetworkSimplex (#234)

XTI (eXtended Threaded Index) is an imporved version of the widely
known ATI (Augmented Threaded Index) method for storing and updating
the spanning tree structure in Network Simplex algorithms.

In the ATI data structure three indices are stored for each node:
predecessor, thread and depth. In the XTI data structure depth is
replaced by the number of successors and the last successor
(according to the thread index).
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@440
     5
 * Copyright (C) 2003-2009
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>
alpar@345
    25
alpar@345
    26
#include "test_tools.h"
alpar@345
    27
alpar@345
    28
using namespace lemon;
alpar@345
    29
alpar@423
    30
char test_lgf[] =
alpar@423
    31
  "@nodes\n"
alpar@423
    32
  "label supply1 supply2 supply3\n"
alpar@423
    33
  "1     0        20      27\n"
alpar@423
    34
  "2     0       -4        0\n"
alpar@423
    35
  "3     0        0        0\n"
alpar@423
    36
  "4     0        0        0\n"
alpar@423
    37
  "5     0        9        0\n"
alpar@423
    38
  "6     0       -6        0\n"
alpar@423
    39
  "7     0        0        0\n"
alpar@423
    40
  "8     0        0        0\n"
alpar@423
    41
  "9     0        3        0\n"
alpar@423
    42
  "10    0       -2        0\n"
alpar@423
    43
  "11    0        0        0\n"
alpar@423
    44
  "12    0       -20     -27\n"
alpar@423
    45
  "@arcs\n"
alpar@423
    46
  "      cost capacity lower1 lower2\n"
alpar@423
    47
  " 1  2  70  11       0      8\n"
alpar@423
    48
  " 1  3 150   3       0      1\n"
alpar@423
    49
  " 1  4  80  15       0      2\n"
alpar@423
    50
  " 2  8  80  12       0      0\n"
alpar@423
    51
  " 3  5 140   5       0      3\n"
alpar@423
    52
  " 4  6  60  10       0      1\n"
alpar@423
    53
  " 4  7  80   2       0      0\n"
alpar@423
    54
  " 4  8 110   3       0      0\n"
alpar@423
    55
  " 5  7  60  14       0      0\n"
alpar@423
    56
  " 5 11 120  12       0      0\n"
alpar@423
    57
  " 6  3   0   3       0      0\n"
alpar@423
    58
  " 6  9 140   4       0      0\n"
alpar@423
    59
  " 6 10  90   8       0      0\n"
alpar@423
    60
  " 7  1  30   5       0      0\n"
alpar@423
    61
  " 8 12  60  16       0      4\n"
alpar@423
    62
  " 9 12  50   6       0      0\n"
alpar@423
    63
  "10 12  70  13       0      5\n"
alpar@423
    64
  "10  2 100   7       0      0\n"
alpar@423
    65
  "10  7  60  10       0      0\n"
alpar@423
    66
  "11 10  20  14       0      6\n"
alpar@423
    67
  "12 11  30  10       0      0\n"
alpar@423
    68
  "@attributes\n"
alpar@423
    69
  "source  1\n"
alpar@423
    70
  "target 12\n"
alpar@423
    71
  "@end\n";
alpar@423
    72
kpeter@346
    73
// Check the feasibility of the flow
alpar@345
    74
template <typename Digraph, typename FlowMap>
alpar@440
    75
bool checkFlow( const Digraph& gr, const FlowMap& flow,
alpar@345
    76
                typename Digraph::Node s, typename Digraph::Node t,
alpar@345
    77
                int value )
alpar@345
    78
{
alpar@345
    79
  TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
alpar@345
    80
  for (ArcIt e(gr); e != INVALID; ++e)
alpar@345
    81
    if (!(flow[e] == 0 || flow[e] == 1)) return false;
alpar@345
    82
alpar@345
    83
  for (NodeIt n(gr); n != INVALID; ++n) {
alpar@345
    84
    int sum = 0;
alpar@345
    85
    for (OutArcIt e(gr, n); e != INVALID; ++e)
alpar@345
    86
      sum += flow[e];
alpar@345
    87
    for (InArcIt e(gr, n); e != INVALID; ++e)
alpar@345
    88
      sum -= flow[e];
alpar@345
    89
    if (n == s && sum != value) return false;
alpar@345
    90
    if (n == t && sum != -value) return false;
alpar@345
    91
    if (n != s && n != t && sum != 0) return false;
alpar@345
    92
  }
alpar@345
    93
alpar@345
    94
  return true;
alpar@345
    95
}
alpar@345
    96
kpeter@346
    97
// Check the optimalitiy of the flow
alpar@440
    98
template < typename Digraph, typename CostMap,
alpar@345
    99
           typename FlowMap, typename PotentialMap >
alpar@345
   100
bool checkOptimality( const Digraph& gr, const CostMap& cost,
alpar@345
   101
                      const FlowMap& flow, const PotentialMap& pi )
alpar@345
   102
{
kpeter@346
   103
  // Check the "Complementary Slackness" optimality condition
alpar@345
   104
  TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
alpar@345
   105
  bool opt = true;
alpar@345
   106
  for (ArcIt e(gr); e != INVALID; ++e) {
alpar@345
   107
    typename CostMap::Value red_cost =
alpar@345
   108
      cost[e] + pi[gr.source(e)] - pi[gr.target(e)];
alpar@345
   109
    opt = (flow[e] == 0 && red_cost >= 0) ||
alpar@345
   110
          (flow[e] == 1 && red_cost <= 0);
alpar@345
   111
    if (!opt) break;
alpar@345
   112
  }
alpar@345
   113
  return opt;
alpar@345
   114
}
alpar@345
   115
kpeter@346
   116
// Check a path
kpeter@346
   117
template <typename Digraph, typename Path>
alpar@345
   118
bool checkPath( const Digraph& gr, const Path& path,
alpar@345
   119
                typename Digraph::Node s, typename Digraph::Node t)
alpar@345
   120
{
kpeter@346
   121
  // Check the "Complementary Slackness" optimality condition
alpar@345
   122
  TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
alpar@345
   123
  Node n = s;
alpar@345
   124
  for (int i = 0; i < path.length(); ++i) {
alpar@345
   125
    if (gr.source(path.nth(i)) != n) return false;
alpar@345
   126
    n = gr.target(path.nth(i));
alpar@345
   127
  }
alpar@345
   128
  return n == t;
alpar@345
   129
}
alpar@345
   130
alpar@345
   131
alpar@345
   132
int main()
alpar@345
   133
{
alpar@345
   134
  DIGRAPH_TYPEDEFS(ListDigraph);
alpar@345
   135
kpeter@346
   136
  // Read the test digraph
alpar@345
   137
  ListDigraph digraph;
alpar@345
   138
  ListDigraph::ArcMap<int> length(digraph);
alpar@345
   139
  Node source, target;
alpar@345
   140
alpar@423
   141
  std::istringstream input(test_lgf);
alpar@345
   142
  DigraphReader<ListDigraph>(digraph, input).
alpar@345
   143
    arcMap("cost", length).
alpar@345
   144
    node("source", source).
alpar@345
   145
    node("target", target).
alpar@345
   146
    run();
alpar@440
   147
kpeter@346
   148
  // Find 2 paths
alpar@345
   149
  {
alpar@345
   150
    Suurballe<ListDigraph> suurballe(digraph, length, source, target);
alpar@345
   151
    check(suurballe.run(2) == 2, "Wrong number of paths");
alpar@345
   152
    check(checkFlow(digraph, suurballe.flowMap(), source, target, 2),
alpar@345
   153
          "The flow is not feasible");
alpar@345
   154
    check(suurballe.totalLength() == 510, "The flow is not optimal");
alpar@440
   155
    check(checkOptimality(digraph, length, suurballe.flowMap(),
alpar@345
   156
                          suurballe.potentialMap()),
alpar@345
   157
          "Wrong potentials");
alpar@345
   158
    for (int i = 0; i < suurballe.pathNum(); ++i)
alpar@345
   159
      check(checkPath(digraph, suurballe.path(i), source, target),
alpar@345
   160
            "Wrong path");
alpar@345
   161
  }
alpar@345
   162
kpeter@346
   163
  // Find 3 paths
alpar@345
   164
  {
alpar@345
   165
    Suurballe<ListDigraph> suurballe(digraph, length, source, target);
alpar@345
   166
    check(suurballe.run(3) == 3, "Wrong number of paths");
alpar@345
   167
    check(checkFlow(digraph, suurballe.flowMap(), source, target, 3),
alpar@345
   168
          "The flow is not feasible");
alpar@345
   169
    check(suurballe.totalLength() == 1040, "The flow is not optimal");
alpar@440
   170
    check(checkOptimality(digraph, length, suurballe.flowMap(),
alpar@345
   171
                          suurballe.potentialMap()),
alpar@345
   172
          "Wrong potentials");
alpar@345
   173
    for (int i = 0; i < suurballe.pathNum(); ++i)
alpar@345
   174
      check(checkPath(digraph, suurballe.path(i), source, target),
alpar@345
   175
            "Wrong path");
alpar@345
   176
  }
alpar@345
   177
kpeter@346
   178
  // Find 5 paths (only 3 can be found)
alpar@345
   179
  {
alpar@345
   180
    Suurballe<ListDigraph> suurballe(digraph, length, source, target);
alpar@345
   181
    check(suurballe.run(5) == 3, "Wrong number of paths");
alpar@345
   182
    check(checkFlow(digraph, suurballe.flowMap(), source, target, 3),
alpar@345
   183
          "The flow is not feasible");
alpar@345
   184
    check(suurballe.totalLength() == 1040, "The flow is not optimal");
alpar@440
   185
    check(checkOptimality(digraph, length, suurballe.flowMap(),
alpar@345
   186
                          suurballe.potentialMap()),
alpar@345
   187
          "Wrong potentials");
alpar@345
   188
    for (int i = 0; i < suurballe.pathNum(); ++i)
alpar@345
   189
      check(checkPath(digraph, suurballe.path(i), source, target),
alpar@345
   190
            "Wrong path");
alpar@345
   191
  }
alpar@345
   192
alpar@345
   193
  return 0;
alpar@345
   194
}