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