1.1 --- a/test/CMakeLists.txt Sun Jan 09 00:56:52 2011 +0100
1.2 +++ b/test/CMakeLists.txt Sun Jan 09 00:57:12 2011 +0100
1.3 @@ -44,6 +44,7 @@
1.4 random_test
1.5 suurballe_test
1.6 time_measure_test
1.7 + tsp_test
1.8 unionfind_test
1.9 )
1.10
2.1 --- a/test/Makefile.am Sun Jan 09 00:56:52 2011 +0100
2.2 +++ b/test/Makefile.am Sun Jan 09 00:57:12 2011 +0100
2.3 @@ -48,6 +48,7 @@
2.4 test/test_tools_fail \
2.5 test/test_tools_pass \
2.6 test/time_measure_test \
2.7 + test/tsp_test \
2.8 test/unionfind_test
2.9
2.10 test_test_tools_pass_DEPENDENCIES = demo
2.11 @@ -102,4 +103,5 @@
2.12 test_test_tools_fail_SOURCES = test/test_tools_fail.cc
2.13 test_test_tools_pass_SOURCES = test/test_tools_pass.cc
2.14 test_time_measure_test_SOURCES = test/time_measure_test.cc
2.15 +test_tsp_test_SOURCES = test/tsp_test.cc
2.16 test_unionfind_test_SOURCES = test/unionfind_test.cc
3.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
3.2 +++ b/test/tsp_test.cc Sun Jan 09 00:57:12 2011 +0100
3.3 @@ -0,0 +1,278 @@
3.4 +/* -*- mode: C++; indent-tabs-mode: nil; -*-
3.5 + *
3.6 + * This file is a part of LEMON, a generic C++ optimization library.
3.7 + *
3.8 + * Copyright (C) 2003-2010
3.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
3.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
3.11 + *
3.12 + * Permission to use, modify and distribute this software is granted
3.13 + * provided that this copyright notice appears in all copies. For
3.14 + * precise terms see the accompanying LICENSE file.
3.15 + *
3.16 + * This software is provided "AS IS" with no warranty of any kind,
3.17 + * express or implied, and with no claim as to its suitability for any
3.18 + * purpose.
3.19 + *
3.20 + */
3.21 +
3.22 +#include <iostream>
3.23 +
3.24 +#include <lemon/full_graph.h>
3.25 +#include <lemon/math.h>
3.26 +#include <lemon/maps.h>
3.27 +#include <lemon/random.h>
3.28 +#include <lemon/dim2.h>
3.29 +
3.30 +#include <lemon/nearest_neighbor_tsp.h>
3.31 +#include <lemon/greedy_tsp.h>
3.32 +#include <lemon/insertion_tsp.h>
3.33 +#include <lemon/christofides_tsp.h>
3.34 +#include <lemon/opt2_tsp.h>
3.35 +
3.36 +#include "test_tools.h"
3.37 +
3.38 +using namespace lemon;
3.39 +
3.40 +// // Tests checkMetricCost() function
3.41 +// void metricCostTest() {
3.42 +// GRAPH_TYPEDEFS(FullGraph);
3.43 +// FullGraph g(10);
3.44 +// check(checkMetricCost(g, constMap<Edge>(0)), "Wrong checkMetricCost()");
3.45 +// check(checkMetricCost(g, constMap<Edge>(1)), "Wrong checkMetricCost()");
3.46 +// check(!checkMetricCost(g, constMap<Edge>(-1)), "Wrong checkMetricCost()");
3.47 +//
3.48 +// FullGraph::EdgeMap<float> cost(g);
3.49 +// for (NodeIt u(g); u != INVALID; ++u) {
3.50 +// for (NodeIt v(g); v != INVALID; ++v) {
3.51 +// if (u == v) continue;
3.52 +// float x1 = g.id(u), x2 = g.id(v);
3.53 +// float y1 = x1 * x1, y2 = x2 * x2;
3.54 +// cost[g.edge(u, v)] = std::sqrt((x2-x1)*(x2-x1) + (y2-y1)*(y2-y1));
3.55 +// }
3.56 +// }
3.57 +// check(checkMetricCost(g, cost), "Wrong checkMetricCost()");
3.58 +// float eps = Tolerance<float>::defaultEpsilon();
3.59 +// cost[g.edge(g(0), g(9))] =
3.60 +// cost[g.edge(g(0), g(8))] + cost[g.edge(g(8), g(9))] + eps * 2;
3.61 +// check(!checkMetricCost(g, cost), "Wrong checkMetricCost()");
3.62 +// check(checkMetricCost(g, cost, Tolerance<float>(eps * 4)),
3.63 +// "Wrong checkMetricCost()");
3.64 +// }
3.65 +
3.66 +// Checks tour validity
3.67 +bool checkTour(const FullGraph &gr, const std::vector<FullGraph::Node> &p) {
3.68 + FullGraph::NodeMap<bool> used(gr, false);
3.69 +
3.70 + int nodes = 0;
3.71 + for (int i = 0; i < int(p.size()); ++i) {
3.72 + if (used[p[i]]) return false;
3.73 + used[p[i]] = true;
3.74 + ++nodes;
3.75 + }
3.76 +
3.77 + return (nodes == gr.nodeNum());
3.78 +}
3.79 +
3.80 +// Checks tour validity
3.81 +bool checkTour(const FullGraph &gr, const Path<FullGraph> &p) {
3.82 + FullGraph::NodeMap<bool> used(gr, false);
3.83 +
3.84 + if (!checkPath(gr, p)) return false;
3.85 + if (gr.nodeNum() <= 1 && p.length() != 0) return false;
3.86 + if (gr.nodeNum() > 1 && p.length() != gr.nodeNum()) return false;
3.87 +
3.88 + for (int i = 0; i < p.length(); ++i) {
3.89 + if (used[gr.target(p.nth(i))]) return false;
3.90 + used[gr.target(p.nth(i))] = true;
3.91 + }
3.92 + return true;
3.93 +}
3.94 +
3.95 +// Checks tour cost
3.96 +template <typename CostMap>
3.97 +bool checkCost(const FullGraph &gr, const std::vector<FullGraph::Node> &p,
3.98 + const CostMap &cost, typename CostMap::Value total)
3.99 +{
3.100 + typedef typename CostMap::Value Cost;
3.101 +
3.102 + Cost s = 0;
3.103 + for (int i = 0; i < int(p.size()) - 1; ++i)
3.104 + s += cost[gr.edge(p[i], p[i+1])];
3.105 + if (int(p.size()) >= 2)
3.106 + s += cost[gr.edge(p.back(), p.front())];
3.107 +
3.108 + return !Tolerance<Cost>().different(s, total);
3.109 +}
3.110 +
3.111 +// Checks tour cost
3.112 +template <typename CostMap>
3.113 +bool checkCost(const FullGraph &, const Path<FullGraph> &p,
3.114 + const CostMap &cost, typename CostMap::Value total)
3.115 +{
3.116 + typedef typename CostMap::Value Cost;
3.117 +
3.118 + Cost s = 0;
3.119 + for (int i = 0; i < p.length(); ++i)
3.120 + s += cost[p.nth(i)];
3.121 +
3.122 + return !Tolerance<Cost>().different(s, total);
3.123 +}
3.124 +
3.125 +// Tests a TSP algorithm on small graphs
3.126 +template <typename TSP>
3.127 +void tspTestSmall(const std::string &alg_name) {
3.128 + GRAPH_TYPEDEFS(FullGraph);
3.129 +
3.130 + for (int n = 0; n <= 5; ++n) {
3.131 + FullGraph g(n);
3.132 + unsigned nsize = n;
3.133 + int esize = n <= 1 ? 0 : n;
3.134 +
3.135 + TSP alg(g, constMap<Edge, int>(1));
3.136 +
3.137 + check(alg.run() == esize, alg_name + ": Wrong total cost");
3.138 + check(alg.tourCost() == esize, alg_name + ": Wrong total cost");
3.139 +
3.140 + std::list<Node> list;
3.141 + std::vector<Node> vec;
3.142 + alg.tourNodes(list);
3.143 + alg.tourNodes(vec);
3.144 + check(list.size() == nsize, alg_name + ": Wrong node sequence");
3.145 + check(vec.size() == nsize, alg_name + ": Wrong node sequence");
3.146 + check(alg.tourNodes().size() == nsize, alg_name + ": Wrong node sequence");
3.147 + check(checkTour(g, vec), alg_name + ": Wrong node sequence");
3.148 + check(checkCost(g, vec, constMap<Edge, int>(1), esize),
3.149 + alg_name + ": Wrong tour cost");
3.150 +
3.151 + SimplePath<FullGraph> path;
3.152 + alg.tour(path);
3.153 + check(path.length() == esize, alg_name + ": Wrong tour");
3.154 + check(checkTour(g, path), alg_name + ": Wrong tour");
3.155 + check(checkCost(g, path, constMap<Edge, int>(1), esize),
3.156 + alg_name + ": Wrong tour cost");
3.157 + }
3.158 +}
3.159 +
3.160 +// Tests a TSP algorithm on random graphs
3.161 +template <typename TSP>
3.162 +void tspTestRandom(const std::string &alg_name) {
3.163 + GRAPH_TYPEDEFS(FullGraph);
3.164 +
3.165 + FullGraph g(20);
3.166 + FullGraph::NodeMap<dim2::Point<double> > pos(g);
3.167 + DoubleEdgeMap cost(g);
3.168 +
3.169 + TSP alg(g, cost);
3.170 + Opt2Tsp<DoubleEdgeMap > opt2(g, cost);
3.171 +
3.172 + for (int i = 1; i <= 3; i++) {
3.173 + for (NodeIt u(g); u != INVALID; ++u) {
3.174 + pos[u] = dim2::Point<double>(rnd(), rnd());
3.175 + }
3.176 + for (NodeIt u(g); u != INVALID; ++u) {
3.177 + for (NodeIt v(g); v != INVALID; ++v) {
3.178 + if (u == v) continue;
3.179 + cost[g.edge(u, v)] = (pos[u] - pos[v]).normSquare();
3.180 + }
3.181 + }
3.182 +
3.183 + check(alg.run() > 0, alg_name + ": Wrong total cost");
3.184 +
3.185 + std::vector<Node> vec;
3.186 + alg.tourNodes(vec);
3.187 + check(checkTour(g, vec), alg_name + ": Wrong node sequence");
3.188 + check(checkCost(g, vec, cost, alg.tourCost()),
3.189 + alg_name + ": Wrong tour cost");
3.190 +
3.191 + SimplePath<FullGraph> path;
3.192 + alg.tour(path);
3.193 + check(checkTour(g, path), alg_name + ": Wrong tour");
3.194 + check(checkCost(g, path, cost, alg.tourCost()),
3.195 + alg_name + ": Wrong tour cost");
3.196 +
3.197 + check(!Tolerance<double>().less(alg.tourCost(), opt2.run(alg.tourNodes())),
3.198 + "2-opt improvement: Wrong total cost");
3.199 + check(checkTour(g, opt2.tourNodes()),
3.200 + "2-opt improvement: Wrong node sequence");
3.201 + check(checkCost(g, opt2.tourNodes(), cost, opt2.tourCost()),
3.202 + "2-opt improvement: Wrong tour cost");
3.203 +
3.204 + check(!Tolerance<double>().less(alg.tourCost(), opt2.run(path)),
3.205 + "2-opt improvement: Wrong total cost");
3.206 + check(checkTour(g, opt2.tourNodes()),
3.207 + "2-opt improvement: Wrong node sequence");
3.208 + check(checkCost(g, opt2.tourNodes(), cost, opt2.tourCost()),
3.209 + "2-opt improvement: Wrong tour cost");
3.210 + }
3.211 +}
3.212 +
3.213 +// Algorithm class for Nearest Insertion
3.214 +template <typename CM>
3.215 +class NearestInsertionTsp : public InsertionTsp<CM> {
3.216 +public:
3.217 + NearestInsertionTsp(const FullGraph &gr, const CM &cost)
3.218 + : InsertionTsp<CM>(gr, cost) {}
3.219 + typename CM::Value run() {
3.220 + return InsertionTsp<CM>::run(InsertionTsp<CM>::NEAREST);
3.221 + }
3.222 +};
3.223 +
3.224 +// Algorithm class for Farthest Insertion
3.225 +template <typename CM>
3.226 +class FarthestInsertionTsp : public InsertionTsp<CM> {
3.227 +public:
3.228 + FarthestInsertionTsp(const FullGraph &gr, const CM &cost)
3.229 + : InsertionTsp<CM>(gr, cost) {}
3.230 + typename CM::Value run() {
3.231 + return InsertionTsp<CM>::run(InsertionTsp<CM>::FARTHEST);
3.232 + }
3.233 +};
3.234 +
3.235 +// Algorithm class for Cheapest Insertion
3.236 +template <typename CM>
3.237 +class CheapestInsertionTsp : public InsertionTsp<CM> {
3.238 +public:
3.239 + CheapestInsertionTsp(const FullGraph &gr, const CM &cost)
3.240 + : InsertionTsp<CM>(gr, cost) {}
3.241 + typename CM::Value run() {
3.242 + return InsertionTsp<CM>::run(InsertionTsp<CM>::CHEAPEST);
3.243 + }
3.244 +};
3.245 +
3.246 +// Algorithm class for Random Insertion
3.247 +template <typename CM>
3.248 +class RandomInsertionTsp : public InsertionTsp<CM> {
3.249 +public:
3.250 + RandomInsertionTsp(const FullGraph &gr, const CM &cost)
3.251 + : InsertionTsp<CM>(gr, cost) {}
3.252 + typename CM::Value run() {
3.253 + return InsertionTsp<CM>::run(InsertionTsp<CM>::RANDOM);
3.254 + }
3.255 +};
3.256 +
3.257 +int main() {
3.258 + GRAPH_TYPEDEFS(FullGraph);
3.259 +
3.260 + // metricCostTest();
3.261 +
3.262 + tspTestSmall<NearestNeighborTsp<ConstMap<Edge, int> > >("Nearest Neighbor");
3.263 + tspTestSmall<GreedyTsp<ConstMap<Edge, int> > >("Greedy");
3.264 + tspTestSmall<NearestInsertionTsp<ConstMap<Edge, int> > >("Nearest Insertion");
3.265 + tspTestSmall<FarthestInsertionTsp<ConstMap<Edge, int> > >("Farthest Insertion");
3.266 + tspTestSmall<CheapestInsertionTsp<ConstMap<Edge, int> > >("Cheapest Insertion");
3.267 + tspTestSmall<RandomInsertionTsp<ConstMap<Edge, int> > >("Random Insertion");
3.268 + tspTestSmall<ChristofidesTsp<ConstMap<Edge, int> > >("Christofides");
3.269 + tspTestSmall<Opt2Tsp<ConstMap<Edge, int> > >("2-opt");
3.270 +
3.271 + tspTestRandom<NearestNeighborTsp<DoubleEdgeMap > >("Nearest Neighbor");
3.272 + tspTestRandom<GreedyTsp<DoubleEdgeMap > >("Greedy");
3.273 + tspTestRandom<NearestInsertionTsp<DoubleEdgeMap > >("Nearest Insertion");
3.274 + tspTestRandom<FarthestInsertionTsp<DoubleEdgeMap > >("Farthest Insertion");
3.275 + tspTestRandom<CheapestInsertionTsp<DoubleEdgeMap > >("Cheapest Insertion");
3.276 + tspTestRandom<RandomInsertionTsp<DoubleEdgeMap > >("Random Insertion");
3.277 + tspTestRandom<ChristofidesTsp<DoubleEdgeMap > >("Christofides");
3.278 + tspTestRandom<Opt2Tsp<DoubleEdgeMap > >("2-opt");
3.279 +
3.280 + return 0;
3.281 +}