COIN-OR::LEMON - Graph Library

source: lemon-main/test/tsp_test.cc @ 1035:07682e24c4e8

Last change on this file since 1035:07682e24c4e8 was 1035:07682e24c4e8, checked in by Peter Kovacs <kpeter@…>, 14 years ago

A detailed test file for TSP algorithms (#386)

File size: 8.9 KB
Line 
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
35using 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
64bool 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
78bool 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
93template <typename CostMap>
94bool 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
109template <typename CostMap>
110bool 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
123template <typename TSP>
124void 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
158template <typename TSP>
159void 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
211template <typename CM>
212class NearestInsertionTsp : public InsertionTsp<CM> {
213public:
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
222template <typename CM>
223class FarthestInsertionTsp : public InsertionTsp<CM> {
224public:
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
233template <typename CM>
234class CheapestInsertionTsp : public InsertionTsp<CM> {
235public:
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
244template <typename CM>
245class RandomInsertionTsp : public InsertionTsp<CM> {
246public:
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
254int 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}
Note: See TracBrowser for help on using the repository browser.