# HG changeset patch
# User Peter Kovacs <kpeter@inf.elte.hu>
# Date 1294531032 -3600
# Node ID 07682e24c4e8062ec5e7b937652ce9bcf82cbf7f
# Parent  ef200e268af2e361f17337a8535e52dc90a035fe
A detailed test file for TSP algorithms (#386)

diff -r ef200e268af2 -r 07682e24c4e8 test/CMakeLists.txt
--- a/test/CMakeLists.txt	Sun Jan 09 00:56:52 2011 +0100
+++ b/test/CMakeLists.txt	Sun Jan 09 00:57:12 2011 +0100
@@ -44,6 +44,7 @@
   random_test
   suurballe_test
   time_measure_test
+  tsp_test
   unionfind_test
 )
 
diff -r ef200e268af2 -r 07682e24c4e8 test/Makefile.am
--- a/test/Makefile.am	Sun Jan 09 00:56:52 2011 +0100
+++ b/test/Makefile.am	Sun Jan 09 00:57:12 2011 +0100
@@ -48,6 +48,7 @@
 	test/test_tools_fail \
 	test/test_tools_pass \
 	test/time_measure_test \
+	test/tsp_test \
 	test/unionfind_test
 
 test_test_tools_pass_DEPENDENCIES = demo
@@ -102,4 +103,5 @@
 test_test_tools_fail_SOURCES = test/test_tools_fail.cc
 test_test_tools_pass_SOURCES = test/test_tools_pass.cc
 test_time_measure_test_SOURCES = test/time_measure_test.cc
+test_tsp_test_SOURCES = test/tsp_test.cc
 test_unionfind_test_SOURCES = test/unionfind_test.cc
diff -r ef200e268af2 -r 07682e24c4e8 test/tsp_test.cc
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/test/tsp_test.cc	Sun Jan 09 00:57:12 2011 +0100
@@ -0,0 +1,278 @@
+/* -*- mode: C++; indent-tabs-mode: nil; -*-
+ *
+ * This file is a part of LEMON, a generic C++ optimization library.
+ *
+ * Copyright (C) 2003-2010
+ * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
+ * (Egervary Research Group on Combinatorial Optimization, EGRES).
+ *
+ * Permission to use, modify and distribute this software is granted
+ * provided that this copyright notice appears in all copies. For
+ * precise terms see the accompanying LICENSE file.
+ *
+ * This software is provided "AS IS" with no warranty of any kind,
+ * express or implied, and with no claim as to its suitability for any
+ * purpose.
+ *
+ */
+
+#include <iostream>
+
+#include <lemon/full_graph.h>
+#include <lemon/math.h>
+#include <lemon/maps.h>
+#include <lemon/random.h>
+#include <lemon/dim2.h>
+
+#include <lemon/nearest_neighbor_tsp.h>
+#include <lemon/greedy_tsp.h>
+#include <lemon/insertion_tsp.h>
+#include <lemon/christofides_tsp.h>
+#include <lemon/opt2_tsp.h>
+
+#include "test_tools.h"
+
+using namespace lemon;
+
+// // Tests checkMetricCost() function
+// void metricCostTest() {
+//   GRAPH_TYPEDEFS(FullGraph);
+//   FullGraph g(10);
+//   check(checkMetricCost(g, constMap<Edge>(0)), "Wrong checkMetricCost()");
+//   check(checkMetricCost(g, constMap<Edge>(1)), "Wrong checkMetricCost()");
+//   check(!checkMetricCost(g, constMap<Edge>(-1)), "Wrong checkMetricCost()");
+//   
+//   FullGraph::EdgeMap<float> cost(g);
+//   for (NodeIt u(g); u != INVALID; ++u) {
+//     for (NodeIt v(g); v != INVALID; ++v) {
+//       if (u == v) continue;
+//       float x1 = g.id(u), x2 = g.id(v);
+//       float y1 = x1 * x1, y2 = x2 * x2;
+//       cost[g.edge(u, v)] = std::sqrt((x2-x1)*(x2-x1) + (y2-y1)*(y2-y1));
+//     }
+//   }
+//   check(checkMetricCost(g, cost), "Wrong checkMetricCost()");
+//   float eps = Tolerance<float>::defaultEpsilon();
+//   cost[g.edge(g(0), g(9))] =
+//     cost[g.edge(g(0), g(8))] + cost[g.edge(g(8), g(9))] + eps * 2;
+//   check(!checkMetricCost(g, cost), "Wrong checkMetricCost()");
+//   check(checkMetricCost(g, cost, Tolerance<float>(eps * 4)),
+//     "Wrong checkMetricCost()");
+// }
+
+// Checks tour validity
+bool checkTour(const FullGraph &gr, const std::vector<FullGraph::Node> &p) {
+  FullGraph::NodeMap<bool> used(gr, false);
+  
+  int nodes = 0;
+  for (int i = 0; i < int(p.size()); ++i) {
+    if (used[p[i]]) return false;
+    used[p[i]] = true;
+    ++nodes;
+  }
+  
+  return (nodes == gr.nodeNum());
+}
+
+// Checks tour validity
+bool checkTour(const FullGraph &gr, const Path<FullGraph> &p) {
+  FullGraph::NodeMap<bool> used(gr, false);
+  
+  if (!checkPath(gr, p)) return false;
+  if (gr.nodeNum() <= 1 && p.length() != 0) return false;
+  if (gr.nodeNum() > 1 && p.length() != gr.nodeNum()) return false;
+
+  for (int i = 0; i < p.length(); ++i) {
+    if (used[gr.target(p.nth(i))]) return false;
+    used[gr.target(p.nth(i))] = true;
+  }
+  return true;
+}
+
+// Checks tour cost
+template <typename CostMap>
+bool checkCost(const FullGraph &gr, const std::vector<FullGraph::Node> &p,
+               const CostMap &cost, typename CostMap::Value total)
+{
+  typedef typename CostMap::Value Cost;
+
+  Cost s = 0;
+  for (int i = 0; i < int(p.size()) - 1; ++i)
+    s += cost[gr.edge(p[i], p[i+1])];
+  if (int(p.size()) >= 2)
+    s += cost[gr.edge(p.back(), p.front())];
+
+  return !Tolerance<Cost>().different(s, total);
+}
+
+// Checks tour cost
+template <typename CostMap>
+bool checkCost(const FullGraph &, const Path<FullGraph> &p,
+               const CostMap &cost, typename CostMap::Value total)
+{
+  typedef typename CostMap::Value Cost;
+
+  Cost s = 0;
+  for (int i = 0; i < p.length(); ++i)
+    s += cost[p.nth(i)];
+
+  return !Tolerance<Cost>().different(s, total);
+}
+
+// Tests a TSP algorithm on small graphs
+template <typename TSP>
+void tspTestSmall(const std::string &alg_name) {
+  GRAPH_TYPEDEFS(FullGraph);
+
+  for (int n = 0; n <= 5; ++n) {
+    FullGraph g(n);
+    unsigned nsize = n;
+    int esize = n <= 1 ? 0 : n;
+
+    TSP alg(g, constMap<Edge, int>(1));
+
+    check(alg.run() == esize, alg_name + ": Wrong total cost");
+    check(alg.tourCost() == esize, alg_name + ": Wrong total cost");
+
+    std::list<Node> list;
+    std::vector<Node> vec;
+    alg.tourNodes(list);
+    alg.tourNodes(vec);
+    check(list.size() == nsize, alg_name + ": Wrong node sequence");
+    check(vec.size() == nsize,  alg_name + ": Wrong node sequence");
+    check(alg.tourNodes().size() == nsize, alg_name + ": Wrong node sequence");
+    check(checkTour(g, vec), alg_name + ": Wrong node sequence");
+    check(checkCost(g, vec, constMap<Edge, int>(1), esize),
+      alg_name + ": Wrong tour cost");
+
+    SimplePath<FullGraph> path;
+    alg.tour(path);
+    check(path.length() == esize, alg_name + ": Wrong tour");
+    check(checkTour(g, path), alg_name + ": Wrong tour");
+    check(checkCost(g, path, constMap<Edge, int>(1), esize),
+      alg_name + ": Wrong tour cost");
+  }
+}
+
+// Tests a TSP algorithm on random graphs
+template <typename TSP>
+void tspTestRandom(const std::string &alg_name) {
+  GRAPH_TYPEDEFS(FullGraph);
+
+  FullGraph g(20);
+  FullGraph::NodeMap<dim2::Point<double> > pos(g);
+  DoubleEdgeMap cost(g);
+
+  TSP alg(g, cost);
+  Opt2Tsp<DoubleEdgeMap > opt2(g, cost);
+
+  for (int i = 1; i <= 3; i++) {
+    for (NodeIt u(g); u != INVALID; ++u) {
+      pos[u] = dim2::Point<double>(rnd(), rnd());
+    }
+    for (NodeIt u(g); u != INVALID; ++u) {
+      for (NodeIt v(g); v != INVALID; ++v) {
+        if (u == v) continue;
+        cost[g.edge(u, v)] = (pos[u] - pos[v]).normSquare();
+      }
+    }
+    
+    check(alg.run() > 0, alg_name + ": Wrong total cost");
+
+    std::vector<Node> vec;
+    alg.tourNodes(vec);
+    check(checkTour(g, vec), alg_name + ": Wrong node sequence");
+    check(checkCost(g, vec, cost, alg.tourCost()),
+      alg_name + ": Wrong tour cost");
+
+    SimplePath<FullGraph> path;
+    alg.tour(path);
+    check(checkTour(g, path), alg_name + ": Wrong tour");
+    check(checkCost(g, path, cost, alg.tourCost()),
+      alg_name + ": Wrong tour cost");
+    
+    check(!Tolerance<double>().less(alg.tourCost(), opt2.run(alg.tourNodes())),
+      "2-opt improvement: Wrong total cost");
+    check(checkTour(g, opt2.tourNodes()),
+      "2-opt improvement: Wrong node sequence");
+    check(checkCost(g, opt2.tourNodes(), cost, opt2.tourCost()),
+      "2-opt improvement: Wrong tour cost");
+    
+    check(!Tolerance<double>().less(alg.tourCost(), opt2.run(path)),
+      "2-opt improvement: Wrong total cost");
+    check(checkTour(g, opt2.tourNodes()),
+      "2-opt improvement: Wrong node sequence");
+    check(checkCost(g, opt2.tourNodes(), cost, opt2.tourCost()),
+      "2-opt improvement: Wrong tour cost");
+  }
+}
+
+// Algorithm class for Nearest Insertion 
+template <typename CM>
+class NearestInsertionTsp : public InsertionTsp<CM> {
+public:
+  NearestInsertionTsp(const FullGraph &gr, const CM &cost)
+    : InsertionTsp<CM>(gr, cost) {}
+  typename CM::Value run() {
+    return InsertionTsp<CM>::run(InsertionTsp<CM>::NEAREST);
+  }
+};
+
+// Algorithm class for Farthest Insertion 
+template <typename CM>
+class FarthestInsertionTsp : public InsertionTsp<CM> {
+public:
+  FarthestInsertionTsp(const FullGraph &gr, const CM &cost)
+    : InsertionTsp<CM>(gr, cost) {}
+  typename CM::Value run() {
+    return InsertionTsp<CM>::run(InsertionTsp<CM>::FARTHEST);
+  }
+};
+
+// Algorithm class for Cheapest Insertion 
+template <typename CM>
+class CheapestInsertionTsp : public InsertionTsp<CM> {
+public:
+  CheapestInsertionTsp(const FullGraph &gr, const CM &cost)
+    : InsertionTsp<CM>(gr, cost) {}
+  typename CM::Value run() {
+    return InsertionTsp<CM>::run(InsertionTsp<CM>::CHEAPEST);
+  }
+};
+
+// Algorithm class for Random Insertion 
+template <typename CM>
+class RandomInsertionTsp : public InsertionTsp<CM> {
+public:
+  RandomInsertionTsp(const FullGraph &gr, const CM &cost)
+    : InsertionTsp<CM>(gr, cost) {}
+  typename CM::Value run() {
+    return InsertionTsp<CM>::run(InsertionTsp<CM>::RANDOM);
+  }
+};
+
+int main() {
+  GRAPH_TYPEDEFS(FullGraph);
+
+  // metricCostTest();
+
+  tspTestSmall<NearestNeighborTsp<ConstMap<Edge, int> > >("Nearest Neighbor");
+  tspTestSmall<GreedyTsp<ConstMap<Edge, int> > >("Greedy");
+  tspTestSmall<NearestInsertionTsp<ConstMap<Edge, int> > >("Nearest Insertion");
+  tspTestSmall<FarthestInsertionTsp<ConstMap<Edge, int> > >("Farthest Insertion");
+  tspTestSmall<CheapestInsertionTsp<ConstMap<Edge, int> > >("Cheapest Insertion");
+  tspTestSmall<RandomInsertionTsp<ConstMap<Edge, int> > >("Random Insertion");
+  tspTestSmall<ChristofidesTsp<ConstMap<Edge, int> > >("Christofides");
+  tspTestSmall<Opt2Tsp<ConstMap<Edge, int> > >("2-opt");
+
+  tspTestRandom<NearestNeighborTsp<DoubleEdgeMap > >("Nearest Neighbor");
+  tspTestRandom<GreedyTsp<DoubleEdgeMap > >("Greedy");
+  tspTestRandom<NearestInsertionTsp<DoubleEdgeMap > >("Nearest Insertion");
+  tspTestRandom<FarthestInsertionTsp<DoubleEdgeMap > >("Farthest Insertion");
+  tspTestRandom<CheapestInsertionTsp<DoubleEdgeMap > >("Cheapest Insertion");
+  tspTestRandom<RandomInsertionTsp<DoubleEdgeMap > >("Random Insertion");
+  tspTestRandom<ChristofidesTsp<DoubleEdgeMap > >("Christofides");
+  tspTestRandom<Opt2Tsp<DoubleEdgeMap > >("2-opt");
+
+  return 0;
+}