1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/test/tsp_test.cc Wed Oct 17 19:14:07 2018 +0200
1.3 @@ -0,0 +1,287 @@
1.4 +/* -*- mode: C++; indent-tabs-mode: nil; -*-
1.5 + *
1.6 + * This file is a part of LEMON, a generic C++ optimization library.
1.7 + *
1.8 + * Copyright (C) 2003-2013
1.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
1.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
1.11 + *
1.12 + * Permission to use, modify and distribute this software is granted
1.13 + * provided that this copyright notice appears in all copies. For
1.14 + * precise terms see the accompanying LICENSE file.
1.15 + *
1.16 + * This software is provided "AS IS" with no warranty of any kind,
1.17 + * express or implied, and with no claim as to its suitability for any
1.18 + * purpose.
1.19 + *
1.20 + */
1.21 +
1.22 +#include <iostream>
1.23 +
1.24 +#include <lemon/full_graph.h>
1.25 +#include <lemon/math.h>
1.26 +#include <lemon/maps.h>
1.27 +#include <lemon/random.h>
1.28 +#include <lemon/dim2.h>
1.29 +
1.30 +#include <lemon/nearest_neighbor_tsp.h>
1.31 +#include <lemon/greedy_tsp.h>
1.32 +#include <lemon/insertion_tsp.h>
1.33 +#include <lemon/christofides_tsp.h>
1.34 +#include <lemon/opt2_tsp.h>
1.35 +
1.36 +#include "test_tools.h"
1.37 +
1.38 +using namespace lemon;
1.39 +
1.40 +// // Tests checkMetricCost() function
1.41 +// void metricCostTest() {
1.42 +// GRAPH_TYPEDEFS(FullGraph);
1.43 +// FullGraph g(10);
1.44 +// check(checkMetricCost(g, constMap<Edge>(0)), "Wrong checkMetricCost()");
1.45 +// check(checkMetricCost(g, constMap<Edge>(1)), "Wrong checkMetricCost()");
1.46 +// check(!checkMetricCost(g, constMap<Edge>(-1)), "Wrong checkMetricCost()");
1.47 +//
1.48 +// FullGraph::EdgeMap<float> cost(g);
1.49 +// for (NodeIt u(g); u != INVALID; ++u) {
1.50 +// for (NodeIt v(g); v != INVALID; ++v) {
1.51 +// if (u == v) continue;
1.52 +// float x1 = g.id(u), x2 = g.id(v);
1.53 +// float y1 = x1 * x1, y2 = x2 * x2;
1.54 +// cost[g.edge(u, v)] = std::sqrt((x2-x1)*(x2-x1) + (y2-y1)*(y2-y1));
1.55 +// }
1.56 +// }
1.57 +// check(checkMetricCost(g, cost), "Wrong checkMetricCost()");
1.58 +// float eps = Tolerance<float>::defaultEpsilon();
1.59 +// cost[g.edge(g(0), g(9))] =
1.60 +// cost[g.edge(g(0), g(8))] + cost[g.edge(g(8), g(9))] + eps * 2;
1.61 +// check(!checkMetricCost(g, cost), "Wrong checkMetricCost()");
1.62 +// check(checkMetricCost(g, cost, Tolerance<float>(eps * 4)),
1.63 +// "Wrong checkMetricCost()");
1.64 +// }
1.65 +
1.66 +// Checks tour validity
1.67 +template <typename Container>
1.68 +bool checkTour(const FullGraph &gr, const Container &p) {
1.69 + FullGraph::NodeMap<bool> used(gr, false);
1.70 +
1.71 + int node_cnt = 0;
1.72 + for (typename Container::const_iterator it = p.begin(); it != p.end(); ++it)
1.73 + {
1.74 + FullGraph::Node node = *it;
1.75 + if (used[node]) return false;
1.76 + used[node] = true;
1.77 + ++node_cnt;
1.78 + }
1.79 +
1.80 + return (node_cnt == gr.nodeNum());
1.81 +}
1.82 +
1.83 +// Checks tour validity
1.84 +bool checkTourPath(const FullGraph &gr, const Path<FullGraph> &p) {
1.85 + FullGraph::NodeMap<bool> used(gr, false);
1.86 +
1.87 + if (!checkPath(gr, p)) return false;
1.88 + if (gr.nodeNum() <= 1 && p.length() != 0) return false;
1.89 + if (gr.nodeNum() > 1 && p.length() != gr.nodeNum()) return false;
1.90 +
1.91 + for (int i = 0; i < p.length(); ++i) {
1.92 + if (used[gr.target(p.nth(i))]) return false;
1.93 + used[gr.target(p.nth(i))] = true;
1.94 + }
1.95 + return true;
1.96 +}
1.97 +
1.98 +// Checks tour cost
1.99 +template <typename CostMap>
1.100 +bool checkCost(const FullGraph &gr, const std::vector<FullGraph::Node> &p,
1.101 + const CostMap &cost, typename CostMap::Value total)
1.102 +{
1.103 + typedef typename CostMap::Value Cost;
1.104 +
1.105 + Cost s = 0;
1.106 + for (int i = 0; i < int(p.size()) - 1; ++i)
1.107 + s += cost[gr.edge(p[i], p[i+1])];
1.108 + if (int(p.size()) >= 2)
1.109 + s += cost[gr.edge(p.back(), p.front())];
1.110 +
1.111 + return !Tolerance<Cost>().different(s, total);
1.112 +}
1.113 +
1.114 +// Checks tour cost
1.115 +template <typename CostMap>
1.116 +bool checkCost(const FullGraph &, const Path<FullGraph> &p,
1.117 + const CostMap &cost, typename CostMap::Value total)
1.118 +{
1.119 + typedef typename CostMap::Value Cost;
1.120 +
1.121 + Cost s = 0;
1.122 + for (int i = 0; i < p.length(); ++i)
1.123 + s += cost[p.nth(i)];
1.124 +
1.125 + return !Tolerance<Cost>().different(s, total);
1.126 +}
1.127 +
1.128 +// Tests a TSP algorithm on small graphs
1.129 +template <typename TSP>
1.130 +void tspTestSmall(const std::string &alg_name) {
1.131 + GRAPH_TYPEDEFS(FullGraph);
1.132 +
1.133 + for (int n = 0; n <= 5; ++n) {
1.134 + FullGraph g(n);
1.135 + unsigned nsize = n;
1.136 + int esize = n <= 1 ? 0 : n;
1.137 +
1.138 + ConstMap<Edge, int> cost_map(1);
1.139 + TSP alg(g, cost_map);
1.140 +
1.141 + check(alg.run() == esize, alg_name + ": Wrong total cost");
1.142 + check(alg.tourCost() == esize, alg_name + ": Wrong total cost");
1.143 +
1.144 + std::list<Node> list1(nsize), list2;
1.145 + std::vector<Node> vec1(nsize), vec2;
1.146 + alg.tourNodes(list1.begin());
1.147 + alg.tourNodes(vec1.begin());
1.148 + alg.tourNodes(std::front_inserter(list2));
1.149 + alg.tourNodes(std::back_inserter(vec2));
1.150 + check(checkTour(g, alg.tourNodes()), alg_name + ": Wrong node sequence");
1.151 + check(checkTour(g, list1), alg_name + ": Wrong node sequence");
1.152 + check(checkTour(g, vec1), alg_name + ": Wrong node sequence");
1.153 + check(checkTour(g, list2), alg_name + ": Wrong node sequence");
1.154 + check(checkTour(g, vec2), alg_name + ": Wrong node sequence");
1.155 + check(checkCost(g, vec1, constMap<Edge, int>(1), esize),
1.156 + alg_name + ": Wrong tour cost");
1.157 +
1.158 + SimplePath<FullGraph> path;
1.159 + alg.tour(path);
1.160 + check(path.length() == esize, alg_name + ": Wrong tour");
1.161 + check(checkTourPath(g, path), alg_name + ": Wrong tour");
1.162 + check(checkCost(g, path, constMap<Edge, int>(1), esize),
1.163 + alg_name + ": Wrong tour cost");
1.164 + }
1.165 +}
1.166 +
1.167 +// Tests a TSP algorithm on random graphs
1.168 +template <typename TSP>
1.169 +void tspTestRandom(const std::string &alg_name) {
1.170 + GRAPH_TYPEDEFS(FullGraph);
1.171 +
1.172 + FullGraph g(20);
1.173 + FullGraph::NodeMap<dim2::Point<double> > pos(g);
1.174 + DoubleEdgeMap cost(g);
1.175 +
1.176 + TSP alg(g, cost);
1.177 + Opt2Tsp<DoubleEdgeMap > opt2(g, cost);
1.178 +
1.179 + for (int i = 1; i <= 3; i++) {
1.180 + for (NodeIt u(g); u != INVALID; ++u) {
1.181 + pos[u] = dim2::Point<double>(rnd(), rnd());
1.182 + }
1.183 + for (NodeIt u(g); u != INVALID; ++u) {
1.184 + for (NodeIt v(g); v != INVALID; ++v) {
1.185 + if (u == v) continue;
1.186 + cost[g.edge(u, v)] = (pos[u] - pos[v]).normSquare();
1.187 + }
1.188 + }
1.189 +
1.190 + check(alg.run() > 0, alg_name + ": Wrong total cost");
1.191 +
1.192 + std::vector<Node> vec;
1.193 + alg.tourNodes(std::back_inserter(vec));
1.194 + check(checkTour(g, vec), alg_name + ": Wrong node sequence");
1.195 + check(checkCost(g, vec, cost, alg.tourCost()),
1.196 + alg_name + ": Wrong tour cost");
1.197 +
1.198 + SimplePath<FullGraph> path;
1.199 + alg.tour(path);
1.200 + check(checkTourPath(g, path), alg_name + ": Wrong tour");
1.201 + check(checkCost(g, path, cost, alg.tourCost()),
1.202 + alg_name + ": Wrong tour cost");
1.203 +
1.204 + check(!Tolerance<double>().less(alg.tourCost(), opt2.run(alg.tourNodes())),
1.205 + "2-opt improvement: Wrong total cost");
1.206 + check(checkTour(g, opt2.tourNodes()),
1.207 + "2-opt improvement: Wrong node sequence");
1.208 + check(checkCost(g, opt2.tourNodes(), cost, opt2.tourCost()),
1.209 + "2-opt improvement: Wrong tour cost");
1.210 +
1.211 + check(!Tolerance<double>().less(alg.tourCost(), opt2.run(path)),
1.212 + "2-opt improvement: Wrong total cost");
1.213 + check(checkTour(g, opt2.tourNodes()),
1.214 + "2-opt improvement: Wrong node sequence");
1.215 + check(checkCost(g, opt2.tourNodes(), cost, opt2.tourCost()),
1.216 + "2-opt improvement: Wrong tour cost");
1.217 + }
1.218 +}
1.219 +
1.220 +// Algorithm class for Nearest Insertion
1.221 +template <typename CM>
1.222 +class NearestInsertionTsp : public InsertionTsp<CM> {
1.223 +public:
1.224 + NearestInsertionTsp(const FullGraph &gr, const CM &cost)
1.225 + : InsertionTsp<CM>(gr, cost) {}
1.226 + typename CM::Value run() {
1.227 + return InsertionTsp<CM>::run(InsertionTsp<CM>::NEAREST);
1.228 + }
1.229 +};
1.230 +
1.231 +// Algorithm class for Farthest Insertion
1.232 +template <typename CM>
1.233 +class FarthestInsertionTsp : public InsertionTsp<CM> {
1.234 +public:
1.235 + FarthestInsertionTsp(const FullGraph &gr, const CM &cost)
1.236 + : InsertionTsp<CM>(gr, cost) {}
1.237 + typename CM::Value run() {
1.238 + return InsertionTsp<CM>::run(InsertionTsp<CM>::FARTHEST);
1.239 + }
1.240 +};
1.241 +
1.242 +// Algorithm class for Cheapest Insertion
1.243 +template <typename CM>
1.244 +class CheapestInsertionTsp : public InsertionTsp<CM> {
1.245 +public:
1.246 + CheapestInsertionTsp(const FullGraph &gr, const CM &cost)
1.247 + : InsertionTsp<CM>(gr, cost) {}
1.248 + typename CM::Value run() {
1.249 + return InsertionTsp<CM>::run(InsertionTsp<CM>::CHEAPEST);
1.250 + }
1.251 +};
1.252 +
1.253 +// Algorithm class for Random Insertion
1.254 +template <typename CM>
1.255 +class RandomInsertionTsp : public InsertionTsp<CM> {
1.256 +public:
1.257 + RandomInsertionTsp(const FullGraph &gr, const CM &cost)
1.258 + : InsertionTsp<CM>(gr, cost) {}
1.259 + typename CM::Value run() {
1.260 + return InsertionTsp<CM>::run(InsertionTsp<CM>::RANDOM);
1.261 + }
1.262 +};
1.263 +
1.264 +int main() {
1.265 + GRAPH_TYPEDEFS(FullGraph);
1.266 +
1.267 + // metricCostTest();
1.268 +
1.269 + tspTestSmall<NearestNeighborTsp<ConstMap<Edge, int> > >("Nearest Neighbor");
1.270 + tspTestSmall<GreedyTsp<ConstMap<Edge, int> > >("Greedy");
1.271 + tspTestSmall<NearestInsertionTsp<ConstMap<Edge, int> > >("Nearest Insertion");
1.272 + tspTestSmall<FarthestInsertionTsp<ConstMap<Edge, int> > >
1.273 + ("Farthest Insertion");
1.274 + tspTestSmall<CheapestInsertionTsp<ConstMap<Edge, int> > >
1.275 + ("Cheapest Insertion");
1.276 + tspTestSmall<RandomInsertionTsp<ConstMap<Edge, int> > >("Random Insertion");
1.277 + tspTestSmall<ChristofidesTsp<ConstMap<Edge, int> > >("Christofides");
1.278 + tspTestSmall<Opt2Tsp<ConstMap<Edge, int> > >("2-opt");
1.279 +
1.280 + tspTestRandom<NearestNeighborTsp<DoubleEdgeMap > >("Nearest Neighbor");
1.281 + tspTestRandom<GreedyTsp<DoubleEdgeMap > >("Greedy");
1.282 + tspTestRandom<NearestInsertionTsp<DoubleEdgeMap > >("Nearest Insertion");
1.283 + tspTestRandom<FarthestInsertionTsp<DoubleEdgeMap > >("Farthest Insertion");
1.284 + tspTestRandom<CheapestInsertionTsp<DoubleEdgeMap > >("Cheapest Insertion");
1.285 + tspTestRandom<RandomInsertionTsp<DoubleEdgeMap > >("Random Insertion");
1.286 + tspTestRandom<ChristofidesTsp<DoubleEdgeMap > >("Christofides");
1.287 + tspTestRandom<Opt2Tsp<DoubleEdgeMap > >("2-opt");
1.288 +
1.289 + return 0;
1.290 +}