/* -*- mode: C++; indent-tabs-mode: nil; -*- * * This file is a part of LEMON, a generic C++ optimization library. * * Copyright (C) 2003-2010 * 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 * precise terms see the accompanying LICENSE file. * * This software is provided "AS IS" with no warranty of any kind, * express or implied, and with no claim as to its suitability for any * purpose. * */ #include #include #include #include #include #include #include #include #include #include #include #include "test_tools.h" using namespace lemon; // // Tests checkMetricCost() function // void metricCostTest() { // GRAPH_TYPEDEFS(FullGraph); // FullGraph g(10); // check(checkMetricCost(g, constMap(0)), "Wrong checkMetricCost()"); // check(checkMetricCost(g, constMap(1)), "Wrong checkMetricCost()"); // check(!checkMetricCost(g, constMap(-1)), "Wrong checkMetricCost()"); // // FullGraph::EdgeMap 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); // float y1 = x1 * x1, y2 = x2 * x2; // cost[g.edge(u, v)] = std::sqrt((x2-x1)*(x2-x1) + (y2-y1)*(y2-y1)); // } // } // check(checkMetricCost(g, cost), "Wrong checkMetricCost()"); // float eps = Tolerance::defaultEpsilon(); // cost[g.edge(g(0), g(9))] = // cost[g.edge(g(0), g(8))] + cost[g.edge(g(8), g(9))] + eps * 2; // check(!checkMetricCost(g, cost), "Wrong checkMetricCost()"); // check(checkMetricCost(g, cost, Tolerance(eps * 4)), // "Wrong checkMetricCost()"); // } // Checks tour validity template bool checkTour(const FullGraph &gr, const Container &p) { FullGraph::NodeMap 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 &p) { FullGraph::NodeMap 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) { if (used[gr.target(p.nth(i))]) return false; used[gr.target(p.nth(i))] = true; } return true; } // Checks tour cost template bool checkCost(const FullGraph &gr, const std::vector &p, const CostMap &cost, typename CostMap::Value total) { typedef typename CostMap::Value Cost; Cost s = 0; for (int i = 0; i < int(p.size()) - 1; ++i) s += cost[gr.edge(p[i], p[i+1])]; if (int(p.size()) >= 2) s += cost[gr.edge(p.back(), p.front())]; return !Tolerance().different(s, total); } // Checks tour cost template bool checkCost(const FullGraph &, const Path &p, const CostMap &cost, typename CostMap::Value total) { typedef typename CostMap::Value Cost; Cost s = 0; for (int i = 0; i < p.length(); ++i) s += cost[p.nth(i)]; return !Tolerance().different(s, total); } // Tests a TSP algorithm on small graphs template void tspTestSmall(const std::string &alg_name) { GRAPH_TYPEDEFS(FullGraph); for (int n = 0; n <= 5; ++n) { FullGraph g(n); unsigned nsize = n; int esize = n <= 1 ? 0 : n; TSP alg(g, constMap(1)); check(alg.run() == esize, alg_name + ": Wrong total cost"); check(alg.tourCost() == esize, alg_name + ": Wrong total cost"); std::list list1(nsize), list2; std::vector vec1(nsize), vec2; alg.tourNodes(list1.begin()); alg.tourNodes(vec1.begin()); alg.tourNodes(std::front_inserter(list2)); alg.tourNodes(std::back_inserter(vec2)); check(checkTour(g, alg.tourNodes()), alg_name + ": Wrong node sequence"); check(checkTour(g, list1), alg_name + ": Wrong node sequence"); check(checkTour(g, vec1), alg_name + ": Wrong node sequence"); check(checkTour(g, list2), alg_name + ": Wrong node sequence"); check(checkTour(g, vec2), alg_name + ": Wrong node sequence"); check(checkCost(g, vec1, constMap(1), esize), alg_name + ": Wrong tour cost"); SimplePath path; alg.tour(path); check(path.length() == esize, alg_name + ": Wrong tour"); check(checkTourPath(g, path), alg_name + ": Wrong tour"); check(checkCost(g, path, constMap(1), esize), alg_name + ": Wrong tour cost"); } } // Tests a TSP algorithm on random graphs template void tspTestRandom(const std::string &alg_name) { GRAPH_TYPEDEFS(FullGraph); FullGraph g(20); FullGraph::NodeMap > pos(g); DoubleEdgeMap cost(g); TSP alg(g, cost); Opt2Tsp opt2(g, cost); for (int i = 1; i <= 3; i++) { for (NodeIt u(g); u != INVALID; ++u) { pos[u] = dim2::Point(rnd(), rnd()); } for (NodeIt u(g); u != INVALID; ++u) { 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 vec; alg.tourNodes(std::back_inserter(vec)); check(checkTour(g, vec), alg_name + ": Wrong node sequence"); check(checkCost(g, vec, cost, alg.tourCost()), alg_name + ": Wrong tour cost"); SimplePath 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().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().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 class NearestInsertionTsp : public InsertionTsp { public: NearestInsertionTsp(const FullGraph &gr, const CM &cost) : InsertionTsp(gr, cost) {} typename CM::Value run() { return InsertionTsp::run(InsertionTsp::NEAREST); } }; // Algorithm class for Farthest Insertion template class FarthestInsertionTsp : public InsertionTsp { public: FarthestInsertionTsp(const FullGraph &gr, const CM &cost) : InsertionTsp(gr, cost) {} typename CM::Value run() { return InsertionTsp::run(InsertionTsp::FARTHEST); } }; // Algorithm class for Cheapest Insertion template class CheapestInsertionTsp : public InsertionTsp { public: CheapestInsertionTsp(const FullGraph &gr, const CM &cost) : InsertionTsp(gr, cost) {} typename CM::Value run() { return InsertionTsp::run(InsertionTsp::CHEAPEST); } }; // Algorithm class for Random Insertion template class RandomInsertionTsp : public InsertionTsp { public: RandomInsertionTsp(const FullGraph &gr, const CM &cost) : InsertionTsp(gr, cost) {} typename CM::Value run() { return InsertionTsp::run(InsertionTsp::RANDOM); } }; int main() { GRAPH_TYPEDEFS(FullGraph); // metricCostTest(); tspTestSmall > >("Nearest Neighbor"); tspTestSmall > >("Greedy"); tspTestSmall > >("Nearest Insertion"); tspTestSmall > >("Farthest Insertion"); tspTestSmall > >("Cheapest Insertion"); tspTestSmall > >("Random Insertion"); tspTestSmall > >("Christofides"); tspTestSmall > >("2-opt"); tspTestRandom >("Nearest Neighbor"); tspTestRandom >("Greedy"); tspTestRandom >("Nearest Insertion"); tspTestRandom >("Farthest Insertion"); tspTestRandom >("Cheapest Insertion"); tspTestRandom >("Random Insertion"); tspTestRandom >("Christofides"); tspTestRandom >("2-opt"); return 0; }