[1035] | 1 | /* -*- mode: C++; indent-tabs-mode: nil; -*- |
---|
| 2 | * |
---|
| 3 | * This file is a part of LEMON, a generic C++ optimization library. |
---|
| 4 | * |
---|
| 5 | * Copyright (C) 2003-2010 |
---|
| 6 | * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport |
---|
| 7 | * (Egervary Research Group on Combinatorial Optimization, EGRES). |
---|
| 8 | * |
---|
| 9 | * Permission to use, modify and distribute this software is granted |
---|
| 10 | * provided that this copyright notice appears in all copies. For |
---|
| 11 | * precise terms see the accompanying LICENSE file. |
---|
| 12 | * |
---|
| 13 | * This software is provided "AS IS" with no warranty of any kind, |
---|
| 14 | * express or implied, and with no claim as to its suitability for any |
---|
| 15 | * purpose. |
---|
| 16 | * |
---|
| 17 | */ |
---|
| 18 | |
---|
| 19 | #include <iostream> |
---|
| 20 | |
---|
| 21 | #include <lemon/full_graph.h> |
---|
| 22 | #include <lemon/math.h> |
---|
| 23 | #include <lemon/maps.h> |
---|
| 24 | #include <lemon/random.h> |
---|
| 25 | #include <lemon/dim2.h> |
---|
| 26 | |
---|
| 27 | #include <lemon/nearest_neighbor_tsp.h> |
---|
| 28 | #include <lemon/greedy_tsp.h> |
---|
| 29 | #include <lemon/insertion_tsp.h> |
---|
| 30 | #include <lemon/christofides_tsp.h> |
---|
| 31 | #include <lemon/opt2_tsp.h> |
---|
| 32 | |
---|
| 33 | #include "test_tools.h" |
---|
| 34 | |
---|
| 35 | using namespace lemon; |
---|
| 36 | |
---|
| 37 | // // Tests checkMetricCost() function |
---|
| 38 | // void metricCostTest() { |
---|
| 39 | // GRAPH_TYPEDEFS(FullGraph); |
---|
| 40 | // FullGraph g(10); |
---|
| 41 | // check(checkMetricCost(g, constMap<Edge>(0)), "Wrong checkMetricCost()"); |
---|
| 42 | // check(checkMetricCost(g, constMap<Edge>(1)), "Wrong checkMetricCost()"); |
---|
| 43 | // check(!checkMetricCost(g, constMap<Edge>(-1)), "Wrong checkMetricCost()"); |
---|
| 44 | // |
---|
| 45 | // FullGraph::EdgeMap<float> cost(g); |
---|
| 46 | // for (NodeIt u(g); u != INVALID; ++u) { |
---|
| 47 | // for (NodeIt v(g); v != INVALID; ++v) { |
---|
| 48 | // if (u == v) continue; |
---|
| 49 | // float x1 = g.id(u), x2 = g.id(v); |
---|
| 50 | // float y1 = x1 * x1, y2 = x2 * x2; |
---|
| 51 | // cost[g.edge(u, v)] = std::sqrt((x2-x1)*(x2-x1) + (y2-y1)*(y2-y1)); |
---|
| 52 | // } |
---|
| 53 | // } |
---|
| 54 | // check(checkMetricCost(g, cost), "Wrong checkMetricCost()"); |
---|
| 55 | // float eps = Tolerance<float>::defaultEpsilon(); |
---|
| 56 | // cost[g.edge(g(0), g(9))] = |
---|
| 57 | // cost[g.edge(g(0), g(8))] + cost[g.edge(g(8), g(9))] + eps * 2; |
---|
| 58 | // check(!checkMetricCost(g, cost), "Wrong checkMetricCost()"); |
---|
| 59 | // check(checkMetricCost(g, cost, Tolerance<float>(eps * 4)), |
---|
| 60 | // "Wrong checkMetricCost()"); |
---|
| 61 | // } |
---|
| 62 | |
---|
| 63 | // Checks tour validity |
---|
| 64 | bool checkTour(const FullGraph &gr, const std::vector<FullGraph::Node> &p) { |
---|
| 65 | FullGraph::NodeMap<bool> used(gr, false); |
---|
| 66 | |
---|
| 67 | int nodes = 0; |
---|
| 68 | for (int i = 0; i < int(p.size()); ++i) { |
---|
| 69 | if (used[p[i]]) return false; |
---|
| 70 | used[p[i]] = true; |
---|
| 71 | ++nodes; |
---|
| 72 | } |
---|
| 73 | |
---|
| 74 | return (nodes == gr.nodeNum()); |
---|
| 75 | } |
---|
| 76 | |
---|
| 77 | // Checks tour validity |
---|
| 78 | bool checkTour(const FullGraph &gr, const Path<FullGraph> &p) { |
---|
| 79 | FullGraph::NodeMap<bool> used(gr, false); |
---|
| 80 | |
---|
| 81 | if (!checkPath(gr, p)) return false; |
---|
| 82 | if (gr.nodeNum() <= 1 && p.length() != 0) return false; |
---|
| 83 | if (gr.nodeNum() > 1 && p.length() != gr.nodeNum()) return false; |
---|
| 84 | |
---|
| 85 | for (int i = 0; i < p.length(); ++i) { |
---|
| 86 | if (used[gr.target(p.nth(i))]) return false; |
---|
| 87 | used[gr.target(p.nth(i))] = true; |
---|
| 88 | } |
---|
| 89 | return true; |
---|
| 90 | } |
---|
| 91 | |
---|
| 92 | // Checks tour cost |
---|
| 93 | template <typename CostMap> |
---|
| 94 | bool checkCost(const FullGraph &gr, const std::vector<FullGraph::Node> &p, |
---|
| 95 | const CostMap &cost, typename CostMap::Value total) |
---|
| 96 | { |
---|
| 97 | typedef typename CostMap::Value Cost; |
---|
| 98 | |
---|
| 99 | Cost s = 0; |
---|
| 100 | for (int i = 0; i < int(p.size()) - 1; ++i) |
---|
| 101 | s += cost[gr.edge(p[i], p[i+1])]; |
---|
| 102 | if (int(p.size()) >= 2) |
---|
| 103 | s += cost[gr.edge(p.back(), p.front())]; |
---|
| 104 | |
---|
| 105 | return !Tolerance<Cost>().different(s, total); |
---|
| 106 | } |
---|
| 107 | |
---|
| 108 | // Checks tour cost |
---|
| 109 | template <typename CostMap> |
---|
| 110 | bool checkCost(const FullGraph &, const Path<FullGraph> &p, |
---|
| 111 | const CostMap &cost, typename CostMap::Value total) |
---|
| 112 | { |
---|
| 113 | typedef typename CostMap::Value Cost; |
---|
| 114 | |
---|
| 115 | Cost s = 0; |
---|
| 116 | for (int i = 0; i < p.length(); ++i) |
---|
| 117 | s += cost[p.nth(i)]; |
---|
| 118 | |
---|
| 119 | return !Tolerance<Cost>().different(s, total); |
---|
| 120 | } |
---|
| 121 | |
---|
| 122 | // Tests a TSP algorithm on small graphs |
---|
| 123 | template <typename TSP> |
---|
| 124 | void tspTestSmall(const std::string &alg_name) { |
---|
| 125 | GRAPH_TYPEDEFS(FullGraph); |
---|
| 126 | |
---|
| 127 | for (int n = 0; n <= 5; ++n) { |
---|
| 128 | FullGraph g(n); |
---|
| 129 | unsigned nsize = n; |
---|
| 130 | int esize = n <= 1 ? 0 : n; |
---|
| 131 | |
---|
| 132 | TSP alg(g, constMap<Edge, int>(1)); |
---|
| 133 | |
---|
| 134 | check(alg.run() == esize, alg_name + ": Wrong total cost"); |
---|
| 135 | check(alg.tourCost() == esize, alg_name + ": Wrong total cost"); |
---|
| 136 | |
---|
| 137 | std::list<Node> list; |
---|
| 138 | std::vector<Node> vec; |
---|
| 139 | alg.tourNodes(list); |
---|
| 140 | alg.tourNodes(vec); |
---|
| 141 | check(list.size() == nsize, alg_name + ": Wrong node sequence"); |
---|
| 142 | check(vec.size() == nsize, alg_name + ": Wrong node sequence"); |
---|
| 143 | check(alg.tourNodes().size() == nsize, alg_name + ": Wrong node sequence"); |
---|
| 144 | check(checkTour(g, vec), alg_name + ": Wrong node sequence"); |
---|
| 145 | check(checkCost(g, vec, constMap<Edge, int>(1), esize), |
---|
| 146 | alg_name + ": Wrong tour cost"); |
---|
| 147 | |
---|
| 148 | SimplePath<FullGraph> path; |
---|
| 149 | alg.tour(path); |
---|
| 150 | check(path.length() == esize, alg_name + ": Wrong tour"); |
---|
| 151 | check(checkTour(g, path), alg_name + ": Wrong tour"); |
---|
| 152 | check(checkCost(g, path, constMap<Edge, int>(1), esize), |
---|
| 153 | alg_name + ": Wrong tour cost"); |
---|
| 154 | } |
---|
| 155 | } |
---|
| 156 | |
---|
| 157 | // Tests a TSP algorithm on random graphs |
---|
| 158 | template <typename TSP> |
---|
| 159 | void tspTestRandom(const std::string &alg_name) { |
---|
| 160 | GRAPH_TYPEDEFS(FullGraph); |
---|
| 161 | |
---|
| 162 | FullGraph g(20); |
---|
| 163 | FullGraph::NodeMap<dim2::Point<double> > pos(g); |
---|
| 164 | DoubleEdgeMap cost(g); |
---|
| 165 | |
---|
| 166 | TSP alg(g, cost); |
---|
| 167 | Opt2Tsp<DoubleEdgeMap > opt2(g, cost); |
---|
| 168 | |
---|
| 169 | for (int i = 1; i <= 3; i++) { |
---|
| 170 | for (NodeIt u(g); u != INVALID; ++u) { |
---|
| 171 | pos[u] = dim2::Point<double>(rnd(), rnd()); |
---|
| 172 | } |
---|
| 173 | for (NodeIt u(g); u != INVALID; ++u) { |
---|
| 174 | for (NodeIt v(g); v != INVALID; ++v) { |
---|
| 175 | if (u == v) continue; |
---|
| 176 | cost[g.edge(u, v)] = (pos[u] - pos[v]).normSquare(); |
---|
| 177 | } |
---|
| 178 | } |
---|
| 179 | |
---|
| 180 | check(alg.run() > 0, alg_name + ": Wrong total cost"); |
---|
| 181 | |
---|
| 182 | std::vector<Node> vec; |
---|
| 183 | alg.tourNodes(vec); |
---|
| 184 | check(checkTour(g, vec), alg_name + ": Wrong node sequence"); |
---|
| 185 | check(checkCost(g, vec, cost, alg.tourCost()), |
---|
| 186 | alg_name + ": Wrong tour cost"); |
---|
| 187 | |
---|
| 188 | SimplePath<FullGraph> path; |
---|
| 189 | alg.tour(path); |
---|
| 190 | check(checkTour(g, path), alg_name + ": Wrong tour"); |
---|
| 191 | check(checkCost(g, path, cost, alg.tourCost()), |
---|
| 192 | alg_name + ": Wrong tour cost"); |
---|
| 193 | |
---|
| 194 | check(!Tolerance<double>().less(alg.tourCost(), opt2.run(alg.tourNodes())), |
---|
| 195 | "2-opt improvement: Wrong total cost"); |
---|
| 196 | check(checkTour(g, opt2.tourNodes()), |
---|
| 197 | "2-opt improvement: Wrong node sequence"); |
---|
| 198 | check(checkCost(g, opt2.tourNodes(), cost, opt2.tourCost()), |
---|
| 199 | "2-opt improvement: Wrong tour cost"); |
---|
| 200 | |
---|
| 201 | check(!Tolerance<double>().less(alg.tourCost(), opt2.run(path)), |
---|
| 202 | "2-opt improvement: Wrong total cost"); |
---|
| 203 | check(checkTour(g, opt2.tourNodes()), |
---|
| 204 | "2-opt improvement: Wrong node sequence"); |
---|
| 205 | check(checkCost(g, opt2.tourNodes(), cost, opt2.tourCost()), |
---|
| 206 | "2-opt improvement: Wrong tour cost"); |
---|
| 207 | } |
---|
| 208 | } |
---|
| 209 | |
---|
| 210 | // Algorithm class for Nearest Insertion |
---|
| 211 | template <typename CM> |
---|
| 212 | class NearestInsertionTsp : public InsertionTsp<CM> { |
---|
| 213 | public: |
---|
| 214 | NearestInsertionTsp(const FullGraph &gr, const CM &cost) |
---|
| 215 | : InsertionTsp<CM>(gr, cost) {} |
---|
| 216 | typename CM::Value run() { |
---|
| 217 | return InsertionTsp<CM>::run(InsertionTsp<CM>::NEAREST); |
---|
| 218 | } |
---|
| 219 | }; |
---|
| 220 | |
---|
| 221 | // Algorithm class for Farthest Insertion |
---|
| 222 | template <typename CM> |
---|
| 223 | class FarthestInsertionTsp : public InsertionTsp<CM> { |
---|
| 224 | public: |
---|
| 225 | FarthestInsertionTsp(const FullGraph &gr, const CM &cost) |
---|
| 226 | : InsertionTsp<CM>(gr, cost) {} |
---|
| 227 | typename CM::Value run() { |
---|
| 228 | return InsertionTsp<CM>::run(InsertionTsp<CM>::FARTHEST); |
---|
| 229 | } |
---|
| 230 | }; |
---|
| 231 | |
---|
| 232 | // Algorithm class for Cheapest Insertion |
---|
| 233 | template <typename CM> |
---|
| 234 | class CheapestInsertionTsp : public InsertionTsp<CM> { |
---|
| 235 | public: |
---|
| 236 | CheapestInsertionTsp(const FullGraph &gr, const CM &cost) |
---|
| 237 | : InsertionTsp<CM>(gr, cost) {} |
---|
| 238 | typename CM::Value run() { |
---|
| 239 | return InsertionTsp<CM>::run(InsertionTsp<CM>::CHEAPEST); |
---|
| 240 | } |
---|
| 241 | }; |
---|
| 242 | |
---|
| 243 | // Algorithm class for Random Insertion |
---|
| 244 | template <typename CM> |
---|
| 245 | class RandomInsertionTsp : public InsertionTsp<CM> { |
---|
| 246 | public: |
---|
| 247 | RandomInsertionTsp(const FullGraph &gr, const CM &cost) |
---|
| 248 | : InsertionTsp<CM>(gr, cost) {} |
---|
| 249 | typename CM::Value run() { |
---|
| 250 | return InsertionTsp<CM>::run(InsertionTsp<CM>::RANDOM); |
---|
| 251 | } |
---|
| 252 | }; |
---|
| 253 | |
---|
| 254 | int main() { |
---|
| 255 | GRAPH_TYPEDEFS(FullGraph); |
---|
| 256 | |
---|
| 257 | // metricCostTest(); |
---|
| 258 | |
---|
| 259 | tspTestSmall<NearestNeighborTsp<ConstMap<Edge, int> > >("Nearest Neighbor"); |
---|
| 260 | tspTestSmall<GreedyTsp<ConstMap<Edge, int> > >("Greedy"); |
---|
| 261 | tspTestSmall<NearestInsertionTsp<ConstMap<Edge, int> > >("Nearest Insertion"); |
---|
| 262 | tspTestSmall<FarthestInsertionTsp<ConstMap<Edge, int> > >("Farthest Insertion"); |
---|
| 263 | tspTestSmall<CheapestInsertionTsp<ConstMap<Edge, int> > >("Cheapest Insertion"); |
---|
| 264 | tspTestSmall<RandomInsertionTsp<ConstMap<Edge, int> > >("Random Insertion"); |
---|
| 265 | tspTestSmall<ChristofidesTsp<ConstMap<Edge, int> > >("Christofides"); |
---|
| 266 | tspTestSmall<Opt2Tsp<ConstMap<Edge, int> > >("2-opt"); |
---|
| 267 | |
---|
| 268 | tspTestRandom<NearestNeighborTsp<DoubleEdgeMap > >("Nearest Neighbor"); |
---|
| 269 | tspTestRandom<GreedyTsp<DoubleEdgeMap > >("Greedy"); |
---|
| 270 | tspTestRandom<NearestInsertionTsp<DoubleEdgeMap > >("Nearest Insertion"); |
---|
| 271 | tspTestRandom<FarthestInsertionTsp<DoubleEdgeMap > >("Farthest Insertion"); |
---|
| 272 | tspTestRandom<CheapestInsertionTsp<DoubleEdgeMap > >("Cheapest Insertion"); |
---|
| 273 | tspTestRandom<RandomInsertionTsp<DoubleEdgeMap > >("Random Insertion"); |
---|
| 274 | tspTestRandom<ChristofidesTsp<DoubleEdgeMap > >("Christofides"); |
---|
| 275 | tspTestRandom<Opt2Tsp<DoubleEdgeMap > >("2-opt"); |
---|
| 276 | |
---|
| 277 | return 0; |
---|
| 278 | } |
---|