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: * alpar@1092: * Copyright (C) 2003-2013 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 kpeter@1035: kpeter@1035: #include kpeter@1035: #include kpeter@1035: #include kpeter@1035: #include kpeter@1035: #include kpeter@1035: kpeter@1035: #include kpeter@1035: #include kpeter@1035: #include kpeter@1035: #include kpeter@1035: #include 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(0)), "Wrong checkMetricCost()"); kpeter@1035: // check(checkMetricCost(g, constMap(1)), "Wrong checkMetricCost()"); kpeter@1035: // check(!checkMetricCost(g, constMap(-1)), "Wrong checkMetricCost()"); alpar@1092: // kpeter@1035: // FullGraph::EdgeMap 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::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(eps * 4)), kpeter@1035: // "Wrong checkMetricCost()"); kpeter@1035: // } kpeter@1035: kpeter@1035: // Checks tour validity kpeter@1037: template kpeter@1037: bool checkTour(const FullGraph &gr, const Container &p) { kpeter@1035: FullGraph::NodeMap used(gr, false); alpar@1092: kpeter@1037: int node_cnt = 0; alpar@1093: for (typename Container::const_iterator it = p.begin(); it != p.end(); ++it) alpar@1093: { alpar@1093: FullGraph::Node node = *it; alpar@1093: if (used[node]) return false; alpar@1093: used[node] = true; alpar@1093: ++node_cnt; alpar@1093: } alpar@1092: kpeter@1037: return (node_cnt == gr.nodeNum()); kpeter@1035: } kpeter@1035: kpeter@1035: // Checks tour validity kpeter@1037: bool checkTourPath(const FullGraph &gr, const Path &p) { kpeter@1035: FullGraph::NodeMap used(gr, false); alpar@1092: 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 kpeter@1035: bool checkCost(const FullGraph &gr, const std::vector &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().different(s, total); kpeter@1035: } kpeter@1035: kpeter@1035: // Checks tour cost kpeter@1035: template kpeter@1035: bool checkCost(const FullGraph &, const Path &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().different(s, total); kpeter@1035: } kpeter@1035: kpeter@1035: // Tests a TSP algorithm on small graphs kpeter@1035: template 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: alpar@1115: ConstMap cost_map(1); alpar@1115: TSP alg(g, cost_map); 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@1037: std::list list1(nsize), list2; kpeter@1037: std::vector vec1(nsize), vec2; kpeter@1037: alg.tourNodes(list1.begin()); kpeter@1037: alg.tourNodes(vec1.begin()); kpeter@1037: alg.tourNodes(std::front_inserter(list2)); kpeter@1037: alg.tourNodes(std::back_inserter(vec2)); kpeter@1037: check(checkTour(g, alg.tourNodes()), alg_name + ": Wrong node sequence"); kpeter@1037: check(checkTour(g, list1), alg_name + ": Wrong node sequence"); kpeter@1037: check(checkTour(g, vec1), alg_name + ": Wrong node sequence"); kpeter@1037: check(checkTour(g, list2), alg_name + ": Wrong node sequence"); kpeter@1037: check(checkTour(g, vec2), alg_name + ": Wrong node sequence"); kpeter@1037: check(checkCost(g, vec1, constMap(1), esize), kpeter@1035: alg_name + ": Wrong tour cost"); kpeter@1035: kpeter@1035: SimplePath path; kpeter@1035: alg.tour(path); kpeter@1035: check(path.length() == esize, alg_name + ": Wrong tour"); kpeter@1037: check(checkTourPath(g, path), alg_name + ": Wrong tour"); kpeter@1035: check(checkCost(g, path, constMap(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 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 > pos(g); kpeter@1035: DoubleEdgeMap cost(g); kpeter@1035: kpeter@1035: TSP alg(g, cost); kpeter@1035: Opt2Tsp 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(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: } alpar@1092: kpeter@1035: check(alg.run() > 0, alg_name + ": Wrong total cost"); kpeter@1035: kpeter@1035: std::vector vec; kpeter@1037: alg.tourNodes(std::back_inserter(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 path; kpeter@1035: alg.tour(path); kpeter@1037: check(checkTourPath(g, path), alg_name + ": Wrong tour"); kpeter@1035: check(checkCost(g, path, cost, alg.tourCost()), kpeter@1035: alg_name + ": Wrong tour cost"); alpar@1092: kpeter@1035: check(!Tolerance().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"); alpar@1092: kpeter@1035: check(!Tolerance().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: alpar@1092: // Algorithm class for Nearest Insertion kpeter@1035: template kpeter@1035: class NearestInsertionTsp : public InsertionTsp { kpeter@1035: public: kpeter@1035: NearestInsertionTsp(const FullGraph &gr, const CM &cost) kpeter@1035: : InsertionTsp(gr, cost) {} kpeter@1035: typename CM::Value run() { kpeter@1035: return InsertionTsp::run(InsertionTsp::NEAREST); kpeter@1035: } kpeter@1035: }; kpeter@1035: alpar@1092: // Algorithm class for Farthest Insertion kpeter@1035: template kpeter@1035: class FarthestInsertionTsp : public InsertionTsp { kpeter@1035: public: kpeter@1035: FarthestInsertionTsp(const FullGraph &gr, const CM &cost) kpeter@1035: : InsertionTsp(gr, cost) {} kpeter@1035: typename CM::Value run() { kpeter@1035: return InsertionTsp::run(InsertionTsp::FARTHEST); kpeter@1035: } kpeter@1035: }; kpeter@1035: alpar@1092: // Algorithm class for Cheapest Insertion kpeter@1035: template kpeter@1035: class CheapestInsertionTsp : public InsertionTsp { kpeter@1035: public: kpeter@1035: CheapestInsertionTsp(const FullGraph &gr, const CM &cost) kpeter@1035: : InsertionTsp(gr, cost) {} kpeter@1035: typename CM::Value run() { kpeter@1035: return InsertionTsp::run(InsertionTsp::CHEAPEST); kpeter@1035: } kpeter@1035: }; kpeter@1035: alpar@1092: // Algorithm class for Random Insertion kpeter@1035: template kpeter@1035: class RandomInsertionTsp : public InsertionTsp { kpeter@1035: public: kpeter@1035: RandomInsertionTsp(const FullGraph &gr, const CM &cost) kpeter@1035: : InsertionTsp(gr, cost) {} kpeter@1035: typename CM::Value run() { kpeter@1035: return InsertionTsp::run(InsertionTsp::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 > >("Nearest Neighbor"); kpeter@1035: tspTestSmall > >("Greedy"); kpeter@1035: tspTestSmall > >("Nearest Insertion"); alpar@1093: tspTestSmall > > alpar@1093: ("Farthest Insertion"); alpar@1093: tspTestSmall > > alpar@1093: ("Cheapest Insertion"); kpeter@1035: tspTestSmall > >("Random Insertion"); kpeter@1035: tspTestSmall > >("Christofides"); kpeter@1035: tspTestSmall > >("2-opt"); kpeter@1035: kpeter@1035: tspTestRandom >("Nearest Neighbor"); kpeter@1035: tspTestRandom >("Greedy"); kpeter@1035: tspTestRandom >("Nearest Insertion"); kpeter@1035: tspTestRandom >("Farthest Insertion"); kpeter@1035: tspTestRandom >("Cheapest Insertion"); kpeter@1035: tspTestRandom >("Random Insertion"); kpeter@1035: tspTestRandom >("Christofides"); kpeter@1035: tspTestRandom >("2-opt"); kpeter@1035: kpeter@1035: return 0; kpeter@1035: }