test/tsp_test.cc
author Peter Kovacs <kpeter@inf.elte.hu>
Fri, 08 Mar 2013 01:13:54 +0100
changeset 1046 387483bf0a56
parent 1035 07682e24c4e8
child 1092 dceba191c00d
permissions -rw-r--r--
Adjust image sizes in the documentation (#411)
kpeter@1035
     1
/* -*- mode: C++; indent-tabs-mode: nil; -*-
kpeter@1035
     2
 *
kpeter@1035
     3
 * This file is a part of LEMON, a generic C++ optimization library.
kpeter@1035
     4
 *
kpeter@1035
     5
 * Copyright (C) 2003-2010
kpeter@1035
     6
 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
kpeter@1035
     7
 * (Egervary Research Group on Combinatorial Optimization, EGRES).
kpeter@1035
     8
 *
kpeter@1035
     9
 * Permission to use, modify and distribute this software is granted
kpeter@1035
    10
 * provided that this copyright notice appears in all copies. For
kpeter@1035
    11
 * precise terms see the accompanying LICENSE file.
kpeter@1035
    12
 *
kpeter@1035
    13
 * This software is provided "AS IS" with no warranty of any kind,
kpeter@1035
    14
 * express or implied, and with no claim as to its suitability for any
kpeter@1035
    15
 * purpose.
kpeter@1035
    16
 *
kpeter@1035
    17
 */
kpeter@1035
    18
kpeter@1035
    19
#include <iostream>
kpeter@1035
    20
kpeter@1035
    21
#include <lemon/full_graph.h>
kpeter@1035
    22
#include <lemon/math.h>
kpeter@1035
    23
#include <lemon/maps.h>
kpeter@1035
    24
#include <lemon/random.h>
kpeter@1035
    25
#include <lemon/dim2.h>
kpeter@1035
    26
kpeter@1035
    27
#include <lemon/nearest_neighbor_tsp.h>
kpeter@1035
    28
#include <lemon/greedy_tsp.h>
kpeter@1035
    29
#include <lemon/insertion_tsp.h>
kpeter@1035
    30
#include <lemon/christofides_tsp.h>
kpeter@1035
    31
#include <lemon/opt2_tsp.h>
kpeter@1035
    32
kpeter@1035
    33
#include "test_tools.h"
kpeter@1035
    34
kpeter@1035
    35
using namespace lemon;
kpeter@1035
    36
kpeter@1035
    37
// // Tests checkMetricCost() function
kpeter@1035
    38
// void metricCostTest() {
kpeter@1035
    39
//   GRAPH_TYPEDEFS(FullGraph);
kpeter@1035
    40
//   FullGraph g(10);
kpeter@1035
    41
//   check(checkMetricCost(g, constMap<Edge>(0)), "Wrong checkMetricCost()");
kpeter@1035
    42
//   check(checkMetricCost(g, constMap<Edge>(1)), "Wrong checkMetricCost()");
kpeter@1035
    43
//   check(!checkMetricCost(g, constMap<Edge>(-1)), "Wrong checkMetricCost()");
kpeter@1035
    44
//   
kpeter@1035
    45
//   FullGraph::EdgeMap<float> cost(g);
kpeter@1035
    46
//   for (NodeIt u(g); u != INVALID; ++u) {
kpeter@1035
    47
//     for (NodeIt v(g); v != INVALID; ++v) {
kpeter@1035
    48
//       if (u == v) continue;
kpeter@1035
    49
//       float x1 = g.id(u), x2 = g.id(v);
kpeter@1035
    50
//       float y1 = x1 * x1, y2 = x2 * x2;
kpeter@1035
    51
//       cost[g.edge(u, v)] = std::sqrt((x2-x1)*(x2-x1) + (y2-y1)*(y2-y1));
kpeter@1035
    52
//     }
kpeter@1035
    53
//   }
kpeter@1035
    54
//   check(checkMetricCost(g, cost), "Wrong checkMetricCost()");
kpeter@1035
    55
//   float eps = Tolerance<float>::defaultEpsilon();
kpeter@1035
    56
//   cost[g.edge(g(0), g(9))] =
kpeter@1035
    57
//     cost[g.edge(g(0), g(8))] + cost[g.edge(g(8), g(9))] + eps * 2;
kpeter@1035
    58
//   check(!checkMetricCost(g, cost), "Wrong checkMetricCost()");
kpeter@1035
    59
//   check(checkMetricCost(g, cost, Tolerance<float>(eps * 4)),
kpeter@1035
    60
//     "Wrong checkMetricCost()");
kpeter@1035
    61
// }
kpeter@1035
    62
kpeter@1035
    63
// Checks tour validity
kpeter@1037
    64
template <typename Container>
kpeter@1037
    65
bool checkTour(const FullGraph &gr, const Container &p) {
kpeter@1035
    66
  FullGraph::NodeMap<bool> used(gr, false);
kpeter@1035
    67
  
kpeter@1037
    68
  int node_cnt = 0;
kpeter@1037
    69
  for (typename Container::const_iterator it = p.begin(); it != p.end(); ++it) {
kpeter@1037
    70
    FullGraph::Node node = *it;
kpeter@1037
    71
    if (used[node]) return false;
kpeter@1037
    72
    used[node] = true;
kpeter@1037
    73
    ++node_cnt;
kpeter@1035
    74
  }
kpeter@1035
    75
  
kpeter@1037
    76
  return (node_cnt == gr.nodeNum());
kpeter@1035
    77
}
kpeter@1035
    78
kpeter@1035
    79
// Checks tour validity
kpeter@1037
    80
bool checkTourPath(const FullGraph &gr, const Path<FullGraph> &p) {
kpeter@1035
    81
  FullGraph::NodeMap<bool> used(gr, false);
kpeter@1035
    82
  
kpeter@1035
    83
  if (!checkPath(gr, p)) return false;
kpeter@1035
    84
  if (gr.nodeNum() <= 1 && p.length() != 0) return false;
kpeter@1035
    85
  if (gr.nodeNum() > 1 && p.length() != gr.nodeNum()) return false;
kpeter@1035
    86
kpeter@1035
    87
  for (int i = 0; i < p.length(); ++i) {
kpeter@1035
    88
    if (used[gr.target(p.nth(i))]) return false;
kpeter@1035
    89
    used[gr.target(p.nth(i))] = true;
kpeter@1035
    90
  }
kpeter@1035
    91
  return true;
kpeter@1035
    92
}
kpeter@1035
    93
kpeter@1035
    94
// Checks tour cost
kpeter@1035
    95
template <typename CostMap>
kpeter@1035
    96
bool checkCost(const FullGraph &gr, const std::vector<FullGraph::Node> &p,
kpeter@1035
    97
               const CostMap &cost, typename CostMap::Value total)
kpeter@1035
    98
{
kpeter@1035
    99
  typedef typename CostMap::Value Cost;
kpeter@1035
   100
kpeter@1035
   101
  Cost s = 0;
kpeter@1035
   102
  for (int i = 0; i < int(p.size()) - 1; ++i)
kpeter@1035
   103
    s += cost[gr.edge(p[i], p[i+1])];
kpeter@1035
   104
  if (int(p.size()) >= 2)
kpeter@1035
   105
    s += cost[gr.edge(p.back(), p.front())];
kpeter@1035
   106
kpeter@1035
   107
  return !Tolerance<Cost>().different(s, total);
kpeter@1035
   108
}
kpeter@1035
   109
kpeter@1035
   110
// Checks tour cost
kpeter@1035
   111
template <typename CostMap>
kpeter@1035
   112
bool checkCost(const FullGraph &, const Path<FullGraph> &p,
kpeter@1035
   113
               const CostMap &cost, typename CostMap::Value total)
kpeter@1035
   114
{
kpeter@1035
   115
  typedef typename CostMap::Value Cost;
kpeter@1035
   116
kpeter@1035
   117
  Cost s = 0;
kpeter@1035
   118
  for (int i = 0; i < p.length(); ++i)
kpeter@1035
   119
    s += cost[p.nth(i)];
kpeter@1035
   120
kpeter@1035
   121
  return !Tolerance<Cost>().different(s, total);
kpeter@1035
   122
}
kpeter@1035
   123
kpeter@1035
   124
// Tests a TSP algorithm on small graphs
kpeter@1035
   125
template <typename TSP>
kpeter@1035
   126
void tspTestSmall(const std::string &alg_name) {
kpeter@1035
   127
  GRAPH_TYPEDEFS(FullGraph);
kpeter@1035
   128
kpeter@1035
   129
  for (int n = 0; n <= 5; ++n) {
kpeter@1035
   130
    FullGraph g(n);
kpeter@1035
   131
    unsigned nsize = n;
kpeter@1035
   132
    int esize = n <= 1 ? 0 : n;
kpeter@1035
   133
kpeter@1035
   134
    TSP alg(g, constMap<Edge, int>(1));
kpeter@1035
   135
kpeter@1035
   136
    check(alg.run() == esize, alg_name + ": Wrong total cost");
kpeter@1035
   137
    check(alg.tourCost() == esize, alg_name + ": Wrong total cost");
kpeter@1035
   138
kpeter@1037
   139
    std::list<Node> list1(nsize), list2;
kpeter@1037
   140
    std::vector<Node> vec1(nsize), vec2;
kpeter@1037
   141
    alg.tourNodes(list1.begin());
kpeter@1037
   142
    alg.tourNodes(vec1.begin());
kpeter@1037
   143
    alg.tourNodes(std::front_inserter(list2));
kpeter@1037
   144
    alg.tourNodes(std::back_inserter(vec2));
kpeter@1037
   145
    check(checkTour(g, alg.tourNodes()), alg_name + ": Wrong node sequence");
kpeter@1037
   146
    check(checkTour(g, list1), alg_name + ": Wrong node sequence");
kpeter@1037
   147
    check(checkTour(g, vec1), alg_name + ": Wrong node sequence");
kpeter@1037
   148
    check(checkTour(g, list2), alg_name + ": Wrong node sequence");
kpeter@1037
   149
    check(checkTour(g, vec2), alg_name + ": Wrong node sequence");
kpeter@1037
   150
    check(checkCost(g, vec1, constMap<Edge, int>(1), esize),
kpeter@1035
   151
      alg_name + ": Wrong tour cost");
kpeter@1035
   152
kpeter@1035
   153
    SimplePath<FullGraph> path;
kpeter@1035
   154
    alg.tour(path);
kpeter@1035
   155
    check(path.length() == esize, alg_name + ": Wrong tour");
kpeter@1037
   156
    check(checkTourPath(g, path), alg_name + ": Wrong tour");
kpeter@1035
   157
    check(checkCost(g, path, constMap<Edge, int>(1), esize),
kpeter@1035
   158
      alg_name + ": Wrong tour cost");
kpeter@1035
   159
  }
kpeter@1035
   160
}
kpeter@1035
   161
kpeter@1035
   162
// Tests a TSP algorithm on random graphs
kpeter@1035
   163
template <typename TSP>
kpeter@1035
   164
void tspTestRandom(const std::string &alg_name) {
kpeter@1035
   165
  GRAPH_TYPEDEFS(FullGraph);
kpeter@1035
   166
kpeter@1035
   167
  FullGraph g(20);
kpeter@1035
   168
  FullGraph::NodeMap<dim2::Point<double> > pos(g);
kpeter@1035
   169
  DoubleEdgeMap cost(g);
kpeter@1035
   170
kpeter@1035
   171
  TSP alg(g, cost);
kpeter@1035
   172
  Opt2Tsp<DoubleEdgeMap > opt2(g, cost);
kpeter@1035
   173
kpeter@1035
   174
  for (int i = 1; i <= 3; i++) {
kpeter@1035
   175
    for (NodeIt u(g); u != INVALID; ++u) {
kpeter@1035
   176
      pos[u] = dim2::Point<double>(rnd(), rnd());
kpeter@1035
   177
    }
kpeter@1035
   178
    for (NodeIt u(g); u != INVALID; ++u) {
kpeter@1035
   179
      for (NodeIt v(g); v != INVALID; ++v) {
kpeter@1035
   180
        if (u == v) continue;
kpeter@1035
   181
        cost[g.edge(u, v)] = (pos[u] - pos[v]).normSquare();
kpeter@1035
   182
      }
kpeter@1035
   183
    }
kpeter@1035
   184
    
kpeter@1035
   185
    check(alg.run() > 0, alg_name + ": Wrong total cost");
kpeter@1035
   186
kpeter@1035
   187
    std::vector<Node> vec;
kpeter@1037
   188
    alg.tourNodes(std::back_inserter(vec));
kpeter@1035
   189
    check(checkTour(g, vec), alg_name + ": Wrong node sequence");
kpeter@1035
   190
    check(checkCost(g, vec, cost, alg.tourCost()),
kpeter@1035
   191
      alg_name + ": Wrong tour cost");
kpeter@1035
   192
kpeter@1035
   193
    SimplePath<FullGraph> path;
kpeter@1035
   194
    alg.tour(path);
kpeter@1037
   195
    check(checkTourPath(g, path), alg_name + ": Wrong tour");
kpeter@1035
   196
    check(checkCost(g, path, cost, alg.tourCost()),
kpeter@1035
   197
      alg_name + ": Wrong tour cost");
kpeter@1035
   198
    
kpeter@1035
   199
    check(!Tolerance<double>().less(alg.tourCost(), opt2.run(alg.tourNodes())),
kpeter@1035
   200
      "2-opt improvement: Wrong total cost");
kpeter@1035
   201
    check(checkTour(g, opt2.tourNodes()),
kpeter@1035
   202
      "2-opt improvement: Wrong node sequence");
kpeter@1035
   203
    check(checkCost(g, opt2.tourNodes(), cost, opt2.tourCost()),
kpeter@1035
   204
      "2-opt improvement: Wrong tour cost");
kpeter@1035
   205
    
kpeter@1035
   206
    check(!Tolerance<double>().less(alg.tourCost(), opt2.run(path)),
kpeter@1035
   207
      "2-opt improvement: Wrong total cost");
kpeter@1035
   208
    check(checkTour(g, opt2.tourNodes()),
kpeter@1035
   209
      "2-opt improvement: Wrong node sequence");
kpeter@1035
   210
    check(checkCost(g, opt2.tourNodes(), cost, opt2.tourCost()),
kpeter@1035
   211
      "2-opt improvement: Wrong tour cost");
kpeter@1035
   212
  }
kpeter@1035
   213
}
kpeter@1035
   214
kpeter@1035
   215
// Algorithm class for Nearest Insertion 
kpeter@1035
   216
template <typename CM>
kpeter@1035
   217
class NearestInsertionTsp : public InsertionTsp<CM> {
kpeter@1035
   218
public:
kpeter@1035
   219
  NearestInsertionTsp(const FullGraph &gr, const CM &cost)
kpeter@1035
   220
    : InsertionTsp<CM>(gr, cost) {}
kpeter@1035
   221
  typename CM::Value run() {
kpeter@1035
   222
    return InsertionTsp<CM>::run(InsertionTsp<CM>::NEAREST);
kpeter@1035
   223
  }
kpeter@1035
   224
};
kpeter@1035
   225
kpeter@1035
   226
// Algorithm class for Farthest Insertion 
kpeter@1035
   227
template <typename CM>
kpeter@1035
   228
class FarthestInsertionTsp : public InsertionTsp<CM> {
kpeter@1035
   229
public:
kpeter@1035
   230
  FarthestInsertionTsp(const FullGraph &gr, const CM &cost)
kpeter@1035
   231
    : InsertionTsp<CM>(gr, cost) {}
kpeter@1035
   232
  typename CM::Value run() {
kpeter@1035
   233
    return InsertionTsp<CM>::run(InsertionTsp<CM>::FARTHEST);
kpeter@1035
   234
  }
kpeter@1035
   235
};
kpeter@1035
   236
kpeter@1035
   237
// Algorithm class for Cheapest Insertion 
kpeter@1035
   238
template <typename CM>
kpeter@1035
   239
class CheapestInsertionTsp : public InsertionTsp<CM> {
kpeter@1035
   240
public:
kpeter@1035
   241
  CheapestInsertionTsp(const FullGraph &gr, const CM &cost)
kpeter@1035
   242
    : InsertionTsp<CM>(gr, cost) {}
kpeter@1035
   243
  typename CM::Value run() {
kpeter@1035
   244
    return InsertionTsp<CM>::run(InsertionTsp<CM>::CHEAPEST);
kpeter@1035
   245
  }
kpeter@1035
   246
};
kpeter@1035
   247
kpeter@1035
   248
// Algorithm class for Random Insertion 
kpeter@1035
   249
template <typename CM>
kpeter@1035
   250
class RandomInsertionTsp : public InsertionTsp<CM> {
kpeter@1035
   251
public:
kpeter@1035
   252
  RandomInsertionTsp(const FullGraph &gr, const CM &cost)
kpeter@1035
   253
    : InsertionTsp<CM>(gr, cost) {}
kpeter@1035
   254
  typename CM::Value run() {
kpeter@1035
   255
    return InsertionTsp<CM>::run(InsertionTsp<CM>::RANDOM);
kpeter@1035
   256
  }
kpeter@1035
   257
};
kpeter@1035
   258
kpeter@1035
   259
int main() {
kpeter@1035
   260
  GRAPH_TYPEDEFS(FullGraph);
kpeter@1035
   261
kpeter@1035
   262
  // metricCostTest();
kpeter@1035
   263
kpeter@1035
   264
  tspTestSmall<NearestNeighborTsp<ConstMap<Edge, int> > >("Nearest Neighbor");
kpeter@1035
   265
  tspTestSmall<GreedyTsp<ConstMap<Edge, int> > >("Greedy");
kpeter@1035
   266
  tspTestSmall<NearestInsertionTsp<ConstMap<Edge, int> > >("Nearest Insertion");
kpeter@1035
   267
  tspTestSmall<FarthestInsertionTsp<ConstMap<Edge, int> > >("Farthest Insertion");
kpeter@1035
   268
  tspTestSmall<CheapestInsertionTsp<ConstMap<Edge, int> > >("Cheapest Insertion");
kpeter@1035
   269
  tspTestSmall<RandomInsertionTsp<ConstMap<Edge, int> > >("Random Insertion");
kpeter@1035
   270
  tspTestSmall<ChristofidesTsp<ConstMap<Edge, int> > >("Christofides");
kpeter@1035
   271
  tspTestSmall<Opt2Tsp<ConstMap<Edge, int> > >("2-opt");
kpeter@1035
   272
kpeter@1035
   273
  tspTestRandom<NearestNeighborTsp<DoubleEdgeMap > >("Nearest Neighbor");
kpeter@1035
   274
  tspTestRandom<GreedyTsp<DoubleEdgeMap > >("Greedy");
kpeter@1035
   275
  tspTestRandom<NearestInsertionTsp<DoubleEdgeMap > >("Nearest Insertion");
kpeter@1035
   276
  tspTestRandom<FarthestInsertionTsp<DoubleEdgeMap > >("Farthest Insertion");
kpeter@1035
   277
  tspTestRandom<CheapestInsertionTsp<DoubleEdgeMap > >("Cheapest Insertion");
kpeter@1035
   278
  tspTestRandom<RandomInsertionTsp<DoubleEdgeMap > >("Random Insertion");
kpeter@1035
   279
  tspTestRandom<ChristofidesTsp<DoubleEdgeMap > >("Christofides");
kpeter@1035
   280
  tspTestRandom<Opt2Tsp<DoubleEdgeMap > >("2-opt");
kpeter@1035
   281
kpeter@1035
   282
  return 0;
kpeter@1035
   283
}