Mercuriallemon / comparison
summary | shortlog | changelog | graph | tags | bookmarks | branches | files | changeset | file | latest | revisions | annotate | diff | comparison | raw | help
test/tsp_test.cc
changeset 1381 e0ccc1f0268f
parent 1205 d3dcc49e6403
child 1271 fb1c7da561ce
equal deleted inserted replaced
1:ddfb22e60b36 2:53badba99c6f 
     1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
 
     1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
 
     2  *
 
     2  *
 
     3  * This file is a part of LEMON, a generic C++ optimization library.
 
     3  * This file is a part of LEMON, a generic C++ optimization library.
 
     4  *
 
     4  *
 
     5  * Copyright (C) 2003-2010
 
     5  * Copyright (C) 2003-2013
 
     6  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 
     6  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 
     7  * (Egervary Research Group on Combinatorial Optimization, EGRES).
 
     7  * (Egervary Research Group on Combinatorial Optimization, EGRES).
 
     8  *
 
     8  *
 
     9  * Permission to use, modify and distribute this software is granted
 
     9  * Permission to use, modify and distribute this software is granted
 
    10  * provided that this copyright notice appears in all copies. For
 
    10  * provided that this copyright notice appears in all copies. For
 
    39 //   GRAPH_TYPEDEFS(FullGraph);
 
    39 //   GRAPH_TYPEDEFS(FullGraph);
 
    40 //   FullGraph g(10);
 
    40 //   FullGraph g(10);
 
    41 //   check(checkMetricCost(g, constMap<Edge>(0)), "Wrong checkMetricCost()");
 
    41 //   check(checkMetricCost(g, constMap<Edge>(0)), "Wrong checkMetricCost()");
 
    42 //   check(checkMetricCost(g, constMap<Edge>(1)), "Wrong checkMetricCost()");
 
    42 //   check(checkMetricCost(g, constMap<Edge>(1)), "Wrong checkMetricCost()");
 
    43 //   check(!checkMetricCost(g, constMap<Edge>(-1)), "Wrong checkMetricCost()");
 
    43 //   check(!checkMetricCost(g, constMap<Edge>(-1)), "Wrong checkMetricCost()");
 
    44 //   
    44 //
 
    45 //   FullGraph::EdgeMap<float> cost(g);
 
    45 //   FullGraph::EdgeMap<float> cost(g);
 
    46 //   for (NodeIt u(g); u != INVALID; ++u) {
 
    46 //   for (NodeIt u(g); u != INVALID; ++u) {
 
    47 //     for (NodeIt v(g); v != INVALID; ++v) {
 
    47 //     for (NodeIt v(g); v != INVALID; ++v) {
 
    48 //       if (u == v) continue;
 
    48 //       if (u == v) continue;
 
    49 //       float x1 = g.id(u), x2 = g.id(v);
 
    49 //       float x1 = g.id(u), x2 = g.id(v);
 
    62 
    62 
    63 // Checks tour validity
 
    63 // Checks tour validity
 
    64 template <typename Container>
 
    64 template <typename Container>
 
    65 bool checkTour(const FullGraph &gr, const Container &p) {
 
    65 bool checkTour(const FullGraph &gr, const Container &p) {
 
    66   FullGraph::NodeMap<bool> used(gr, false);
 
    66   FullGraph::NodeMap<bool> used(gr, false);
 
    67   
    67 
    68   int node_cnt = 0;
 
    68   int node_cnt = 0;
 
    69   for (typename Container::const_iterator it = p.begin(); it != p.end(); ++it) {
 
    69   for (typename Container::const_iterator it = p.begin(); it != p.end(); ++it) {
 
    70     FullGraph::Node node = *it;
 
    70     FullGraph::Node node = *it;
 
    71     if (used[node]) return false;
 
    71     if (used[node]) return false;
 
    72     used[node] = true;
 
    72     used[node] = true;
 
    73     ++node_cnt;
 
    73     ++node_cnt;
 
    74   }
 
    74   }
 
    75   
    75 
    76   return (node_cnt == gr.nodeNum());
 
    76   return (node_cnt == gr.nodeNum());
 
    77 }
 
    77 }
 
    78 
    78 
    79 // Checks tour validity
 
    79 // Checks tour validity
 
    80 bool checkTourPath(const FullGraph &gr, const Path<FullGraph> &p) {
 
    80 bool checkTourPath(const FullGraph &gr, const Path<FullGraph> &p) {
 
    81   FullGraph::NodeMap<bool> used(gr, false);
 
    81   FullGraph::NodeMap<bool> used(gr, false);
 
    82   
    82 
    83   if (!checkPath(gr, p)) return false;
 
    83   if (!checkPath(gr, p)) return false;
 
    84   if (gr.nodeNum() <= 1 && p.length() != 0) return false;
 
    84   if (gr.nodeNum() <= 1 && p.length() != 0) return false;
 
    85   if (gr.nodeNum() > 1 && p.length() != gr.nodeNum()) return false;
 
    85   if (gr.nodeNum() > 1 && p.length() != gr.nodeNum()) return false;
 
    86 
    86 
    87   for (int i = 0; i < p.length(); ++i) {
 
    87   for (int i = 0; i < p.length(); ++i) {
 
   179       for (NodeIt v(g); v != INVALID; ++v) {
 
   179       for (NodeIt v(g); v != INVALID; ++v) {
 
   180         if (u == v) continue;
 
   180         if (u == v) continue;
 
   181         cost[g.edge(u, v)] = (pos[u] - pos[v]).normSquare();
 
   181         cost[g.edge(u, v)] = (pos[u] - pos[v]).normSquare();
 
   182       }
 
   182       }
 
   183     }
 
   183     }
 
   184     
   184 
   185     check(alg.run() > 0, alg_name + ": Wrong total cost");
 
   185     check(alg.run() > 0, alg_name + ": Wrong total cost");
 
   186 
   186 
   187     std::vector<Node> vec;
 
   187     std::vector<Node> vec;
 
   188     alg.tourNodes(std::back_inserter(vec));
 
   188     alg.tourNodes(std::back_inserter(vec));
 
   189     check(checkTour(g, vec), alg_name + ": Wrong node sequence");
 
   189     check(checkTour(g, vec), alg_name + ": Wrong node sequence");
 
   193     SimplePath<FullGraph> path;
 
   193     SimplePath<FullGraph> path;
 
   194     alg.tour(path);
 
   194     alg.tour(path);
 
   195     check(checkTourPath(g, path), alg_name + ": Wrong tour");
 
   195     check(checkTourPath(g, path), alg_name + ": Wrong tour");
 
   196     check(checkCost(g, path, cost, alg.tourCost()),
 
   196     check(checkCost(g, path, cost, alg.tourCost()),
 
   197       alg_name + ": Wrong tour cost");
 
   197       alg_name + ": Wrong tour cost");
 
   198     
   198 
   199     check(!Tolerance<double>().less(alg.tourCost(), opt2.run(alg.tourNodes())),
 
   199     check(!Tolerance<double>().less(alg.tourCost(), opt2.run(alg.tourNodes())),
 
   200       "2-opt improvement: Wrong total cost");
 
   200       "2-opt improvement: Wrong total cost");
 
   201     check(checkTour(g, opt2.tourNodes()),
 
   201     check(checkTour(g, opt2.tourNodes()),
 
   202       "2-opt improvement: Wrong node sequence");
 
   202       "2-opt improvement: Wrong node sequence");
 
   203     check(checkCost(g, opt2.tourNodes(), cost, opt2.tourCost()),
 
   203     check(checkCost(g, opt2.tourNodes(), cost, opt2.tourCost()),
 
   204       "2-opt improvement: Wrong tour cost");
 
   204       "2-opt improvement: Wrong tour cost");
 
   205     
   205 
   206     check(!Tolerance<double>().less(alg.tourCost(), opt2.run(path)),
 
   206     check(!Tolerance<double>().less(alg.tourCost(), opt2.run(path)),
 
   207       "2-opt improvement: Wrong total cost");
 
   207       "2-opt improvement: Wrong total cost");
 
   208     check(checkTour(g, opt2.tourNodes()),
 
   208     check(checkTour(g, opt2.tourNodes()),
 
   209       "2-opt improvement: Wrong node sequence");
 
   209       "2-opt improvement: Wrong node sequence");
 
   210     check(checkCost(g, opt2.tourNodes(), cost, opt2.tourCost()),
 
   210     check(checkCost(g, opt2.tourNodes(), cost, opt2.tourCost()),
 
   211       "2-opt improvement: Wrong tour cost");
 
   211       "2-opt improvement: Wrong tour cost");
 
   212   }
 
   212   }
 
   213 }
 
   213 }
 
   214 
   214 
   215 // Algorithm class for Nearest Insertion 
   215 // Algorithm class for Nearest Insertion
 
   216 template <typename CM>
 
   216 template <typename CM>
 
   217 class NearestInsertionTsp : public InsertionTsp<CM> {
 
   217 class NearestInsertionTsp : public InsertionTsp<CM> {
 
   218 public:
 
   218 public:
 
   219   NearestInsertionTsp(const FullGraph &gr, const CM &cost)
 
   219   NearestInsertionTsp(const FullGraph &gr, const CM &cost)
 
   220     : InsertionTsp<CM>(gr, cost) {}
 
   220     : InsertionTsp<CM>(gr, cost) {}
 
   221   typename CM::Value run() {
 
   221   typename CM::Value run() {
 
   222     return InsertionTsp<CM>::run(InsertionTsp<CM>::NEAREST);
 
   222     return InsertionTsp<CM>::run(InsertionTsp<CM>::NEAREST);
 
   223   }
 
   223   }
 
   224 };
 
   224 };
 
   225 
   225 
   226 // Algorithm class for Farthest Insertion 
   226 // Algorithm class for Farthest Insertion
 
   227 template <typename CM>
 
   227 template <typename CM>
 
   228 class FarthestInsertionTsp : public InsertionTsp<CM> {
 
   228 class FarthestInsertionTsp : public InsertionTsp<CM> {
 
   229 public:
 
   229 public:
 
   230   FarthestInsertionTsp(const FullGraph &gr, const CM &cost)
 
   230   FarthestInsertionTsp(const FullGraph &gr, const CM &cost)
 
   231     : InsertionTsp<CM>(gr, cost) {}
 
   231     : InsertionTsp<CM>(gr, cost) {}
 
   232   typename CM::Value run() {
 
   232   typename CM::Value run() {
 
   233     return InsertionTsp<CM>::run(InsertionTsp<CM>::FARTHEST);
 
   233     return InsertionTsp<CM>::run(InsertionTsp<CM>::FARTHEST);
 
   234   }
 
   234   }
 
   235 };
 
   235 };
 
   236 
   236 
   237 // Algorithm class for Cheapest Insertion 
   237 // Algorithm class for Cheapest Insertion
 
   238 template <typename CM>
 
   238 template <typename CM>
 
   239 class CheapestInsertionTsp : public InsertionTsp<CM> {
 
   239 class CheapestInsertionTsp : public InsertionTsp<CM> {
 
   240 public:
 
   240 public:
 
   241   CheapestInsertionTsp(const FullGraph &gr, const CM &cost)
 
   241   CheapestInsertionTsp(const FullGraph &gr, const CM &cost)
 
   242     : InsertionTsp<CM>(gr, cost) {}
 
   242     : InsertionTsp<CM>(gr, cost) {}
 
   243   typename CM::Value run() {
 
   243   typename CM::Value run() {
 
   244     return InsertionTsp<CM>::run(InsertionTsp<CM>::CHEAPEST);
 
   244     return InsertionTsp<CM>::run(InsertionTsp<CM>::CHEAPEST);
 
   245   }
 
   245   }
 
   246 };
 
   246 };
 
   247 
   247 
   248 // Algorithm class for Random Insertion 
   248 // Algorithm class for Random Insertion
 
   249 template <typename CM>
 
   249 template <typename CM>
 
   250 class RandomInsertionTsp : public InsertionTsp<CM> {
 
   250 class RandomInsertionTsp : public InsertionTsp<CM> {
 
   251 public:
 
   251 public:
 
   252   RandomInsertionTsp(const FullGraph &gr, const CM &cost)
 
   252   RandomInsertionTsp(const FullGraph &gr, const CM &cost)
 
   253     : InsertionTsp<CM>(gr, cost) {}
 
   253     : InsertionTsp<CM>(gr, cost) {}
lemon