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