lemon: comparison test/tsp

equal deleted inserted replaced

-:ddfb22e60b36
+:53badba99c6f
 /* -*- mode: C++; indent-tabs-mode: nil; -*-
 *
 * This file is a part of LEMON, a generic C++ optimization library.
 *
-* Copyright (C) 2003-2010
+* Copyright (C) 2003-2013
 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 * (Egervary Research Group on Combinatorial Optimization, EGRES).
 *
 * Permission to use, modify and distribute this software is granted
 * provided that this copyright notice appears in all copies. For
 //   GRAPH_TYPEDEFS(FullGraph);
 //   FullGraph g(10);
 //   check(checkMetricCost(g, constMap<Edge>(0)), "Wrong checkMetricCost()");
 //   check(checkMetricCost(g, constMap<Edge>(1)), "Wrong checkMetricCost()");
 //   check(!checkMetricCost(g, constMap<Edge>(-1)), "Wrong checkMetricCost()");
 //
 //   FullGraph::EdgeMap<float> cost(g);
 //   for (NodeIt u(g); u != INVALID; ++u) {
 //     for (NodeIt v(g); v != INVALID; ++v) {
 //       if (u == v) continue;
 //       float x1 = g.id(u), x2 = g.id(v);
 // Checks tour validity
 template <typename Container>
 bool checkTour(const FullGraph &gr, const Container &p) {
 FullGraph::NodeMap<bool> used(gr, false);
 int node_cnt = 0;
 for (typename Container::const_iterator it = p.begin(); it != p.end(); ++it) {
 FullGraph::Node node = *it;
 if (used[node]) return false;
 used[node] = true;
 ++node_cnt;
 }
 return (node_cnt == gr.nodeNum());
 }
 // Checks tour validity
 bool checkTourPath(const FullGraph &gr, const Path<FullGraph> &p) {
 FullGraph::NodeMap<bool> used(gr, false);
 if (!checkPath(gr, p)) return false;
 if (gr.nodeNum() <= 1 && p.length() != 0) return false;
 if (gr.nodeNum() > 1 && p.length() != gr.nodeNum()) return false;
 for (int i = 0; i < p.length(); ++i) {
 for (NodeIt v(g); v != INVALID; ++v) {
 if (u == v) continue;
 cost[g.edge(u, v)] = (pos[u] - pos[v]).normSquare();
 }
 }
 check(alg.run() > 0, alg_name + ": Wrong total cost");
 std::vector<Node> vec;
 alg.tourNodes(std::back_inserter(vec));
 check(checkTour(g, vec), alg_name + ": Wrong node sequence");
 SimplePath<FullGraph> path;
 alg.tour(path);
 check(checkTourPath(g, path), alg_name + ": Wrong tour");
 check(checkCost(g, path, cost, alg.tourCost()),
 alg_name + ": Wrong tour cost");
 check(!Tolerance<double>().less(alg.tourCost(), opt2.run(alg.tourNodes())),
 "2-opt improvement: Wrong total cost");
 check(checkTour(g, opt2.tourNodes()),
 "2-opt improvement: Wrong node sequence");
 check(checkCost(g, opt2.tourNodes(), cost, opt2.tourCost()),
 "2-opt improvement: Wrong tour cost");
 check(!Tolerance<double>().less(alg.tourCost(), opt2.run(path)),
 "2-opt improvement: Wrong total cost");
 check(checkTour(g, opt2.tourNodes()),
 "2-opt improvement: Wrong node sequence");
 check(checkCost(g, opt2.tourNodes(), cost, opt2.tourCost()),
 "2-opt improvement: Wrong tour cost");
 }
 }
 // Algorithm class for Nearest Insertion
 template <typename CM>
 class NearestInsertionTsp : public InsertionTsp<CM> {
 public:
 NearestInsertionTsp(const FullGraph &gr, const CM &cost)
 : InsertionTsp<CM>(gr, cost) {}
 typename CM::Value run() {
 return InsertionTsp<CM>::run(InsertionTsp<CM>::NEAREST);
 }
 };
 // Algorithm class for Farthest Insertion
 template <typename CM>
 class FarthestInsertionTsp : public InsertionTsp<CM> {
 public:
 FarthestInsertionTsp(const FullGraph &gr, const CM &cost)
 : InsertionTsp<CM>(gr, cost) {}
 typename CM::Value run() {
 return InsertionTsp<CM>::run(InsertionTsp<CM>::FARTHEST);
 }
 };
 // Algorithm class for Cheapest Insertion
 template <typename CM>
 class CheapestInsertionTsp : public InsertionTsp<CM> {
 public:
 CheapestInsertionTsp(const FullGraph &gr, const CM &cost)
 : InsertionTsp<CM>(gr, cost) {}
 typename CM::Value run() {
 return InsertionTsp<CM>::run(InsertionTsp<CM>::CHEAPEST);
 }
 };
 // Algorithm class for Random Insertion
 template <typename CM>
 class RandomInsertionTsp : public InsertionTsp<CM> {
 public:
 RandomInsertionTsp(const FullGraph &gr, const CM &cost)
 : InsertionTsp<CM>(gr, cost) {}

changeset 1270	dceba191c00d
parent 1205	d3dcc49e6403
child 1271	fb1c7da561ce