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