test/suurballe_test.cc
author Peter Kovacs <kpeter@inf.elte.hu>
Fri, 17 Apr 2009 09:54:14 +0200
changeset 640 7ac52d6a268e
parent 442 ff48c2738fb2
child 670 7c1324b35d89
permissions -rw-r--r--
Extend and modify the interface of matching algorithms (#265)

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