|
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 } |