COIN-OR::LEMON - Graph Library

source: lemon/test/tsp_test.cc @ 1271:fb1c7da561ce

Last change on this file since 1271:fb1c7da561ce was 1271:fb1c7da561ce, checked in by Alpar Juttner <alpar@…>, 6 years ago

Remove long lines (from all but one file)

File size: 9.2 KB
RevLine 
[1203]1/* -*- mode: C++; indent-tabs-mode: nil; -*-
2 *
3 * This file is a part of LEMON, a generic C++ optimization library.
4 *
[1270]5 * Copyright (C) 2003-2013
[1203]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()");
[1270]44//
[1203]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
[1205]64template <typename Container>
65bool checkTour(const FullGraph &gr, const Container &p) {
[1203]66  FullGraph::NodeMap<bool> used(gr, false);
[1270]67
[1205]68  int node_cnt = 0;
[1271]69  for (typename Container::const_iterator it = p.begin(); it != p.end(); ++it)
70    {
71      FullGraph::Node node = *it;
72      if (used[node]) return false;
73      used[node] = true;
74      ++node_cnt;
75    }
[1270]76
[1205]77  return (node_cnt == gr.nodeNum());
[1203]78}
79
80// Checks tour validity
[1205]81bool checkTourPath(const FullGraph &gr, const Path<FullGraph> &p) {
[1203]82  FullGraph::NodeMap<bool> used(gr, false);
[1270]83
[1203]84  if (!checkPath(gr, p)) return false;
85  if (gr.nodeNum() <= 1 && p.length() != 0) return false;
86  if (gr.nodeNum() > 1 && p.length() != gr.nodeNum()) return false;
87
88  for (int i = 0; i < p.length(); ++i) {
89    if (used[gr.target(p.nth(i))]) return false;
90    used[gr.target(p.nth(i))] = true;
91  }
92  return true;
93}
94
95// Checks tour cost
96template <typename CostMap>
97bool checkCost(const FullGraph &gr, const std::vector<FullGraph::Node> &p,
98               const CostMap &cost, typename CostMap::Value total)
99{
100  typedef typename CostMap::Value Cost;
101
102  Cost s = 0;
103  for (int i = 0; i < int(p.size()) - 1; ++i)
104    s += cost[gr.edge(p[i], p[i+1])];
105  if (int(p.size()) >= 2)
106    s += cost[gr.edge(p.back(), p.front())];
107
108  return !Tolerance<Cost>().different(s, total);
109}
110
111// Checks tour cost
112template <typename CostMap>
113bool checkCost(const FullGraph &, const Path<FullGraph> &p,
114               const CostMap &cost, typename CostMap::Value total)
115{
116  typedef typename CostMap::Value Cost;
117
118  Cost s = 0;
119  for (int i = 0; i < p.length(); ++i)
120    s += cost[p.nth(i)];
121
122  return !Tolerance<Cost>().different(s, total);
123}
124
125// Tests a TSP algorithm on small graphs
126template <typename TSP>
127void tspTestSmall(const std::string &alg_name) {
128  GRAPH_TYPEDEFS(FullGraph);
129
130  for (int n = 0; n <= 5; ++n) {
131    FullGraph g(n);
132    unsigned nsize = n;
133    int esize = n <= 1 ? 0 : n;
134
135    TSP alg(g, constMap<Edge, int>(1));
136
137    check(alg.run() == esize, alg_name + ": Wrong total cost");
138    check(alg.tourCost() == esize, alg_name + ": Wrong total cost");
139
[1205]140    std::list<Node> list1(nsize), list2;
141    std::vector<Node> vec1(nsize), vec2;
142    alg.tourNodes(list1.begin());
143    alg.tourNodes(vec1.begin());
144    alg.tourNodes(std::front_inserter(list2));
145    alg.tourNodes(std::back_inserter(vec2));
146    check(checkTour(g, alg.tourNodes()), alg_name + ": Wrong node sequence");
147    check(checkTour(g, list1), alg_name + ": Wrong node sequence");
148    check(checkTour(g, vec1), alg_name + ": Wrong node sequence");
149    check(checkTour(g, list2), alg_name + ": Wrong node sequence");
150    check(checkTour(g, vec2), alg_name + ": Wrong node sequence");
151    check(checkCost(g, vec1, constMap<Edge, int>(1), esize),
[1203]152      alg_name + ": Wrong tour cost");
153
154    SimplePath<FullGraph> path;
155    alg.tour(path);
156    check(path.length() == esize, alg_name + ": Wrong tour");
[1205]157    check(checkTourPath(g, path), alg_name + ": Wrong tour");
[1203]158    check(checkCost(g, path, constMap<Edge, int>(1), esize),
159      alg_name + ": Wrong tour cost");
160  }
161}
162
163// Tests a TSP algorithm on random graphs
164template <typename TSP>
165void tspTestRandom(const std::string &alg_name) {
166  GRAPH_TYPEDEFS(FullGraph);
167
168  FullGraph g(20);
169  FullGraph::NodeMap<dim2::Point<double> > pos(g);
170  DoubleEdgeMap cost(g);
171
172  TSP alg(g, cost);
173  Opt2Tsp<DoubleEdgeMap > opt2(g, cost);
174
175  for (int i = 1; i <= 3; i++) {
176    for (NodeIt u(g); u != INVALID; ++u) {
177      pos[u] = dim2::Point<double>(rnd(), rnd());
178    }
179    for (NodeIt u(g); u != INVALID; ++u) {
180      for (NodeIt v(g); v != INVALID; ++v) {
181        if (u == v) continue;
182        cost[g.edge(u, v)] = (pos[u] - pos[v]).normSquare();
183      }
184    }
[1270]185
[1203]186    check(alg.run() > 0, alg_name + ": Wrong total cost");
187
188    std::vector<Node> vec;
[1205]189    alg.tourNodes(std::back_inserter(vec));
[1203]190    check(checkTour(g, vec), alg_name + ": Wrong node sequence");
191    check(checkCost(g, vec, cost, alg.tourCost()),
192      alg_name + ": Wrong tour cost");
193
194    SimplePath<FullGraph> path;
195    alg.tour(path);
[1205]196    check(checkTourPath(g, path), alg_name + ": Wrong tour");
[1203]197    check(checkCost(g, path, cost, alg.tourCost()),
198      alg_name + ": Wrong tour cost");
[1270]199
[1203]200    check(!Tolerance<double>().less(alg.tourCost(), opt2.run(alg.tourNodes())),
201      "2-opt improvement: Wrong total cost");
202    check(checkTour(g, opt2.tourNodes()),
203      "2-opt improvement: Wrong node sequence");
204    check(checkCost(g, opt2.tourNodes(), cost, opt2.tourCost()),
205      "2-opt improvement: Wrong tour cost");
[1270]206
[1203]207    check(!Tolerance<double>().less(alg.tourCost(), opt2.run(path)),
208      "2-opt improvement: Wrong total cost");
209    check(checkTour(g, opt2.tourNodes()),
210      "2-opt improvement: Wrong node sequence");
211    check(checkCost(g, opt2.tourNodes(), cost, opt2.tourCost()),
212      "2-opt improvement: Wrong tour cost");
213  }
214}
215
[1270]216// Algorithm class for Nearest Insertion
[1203]217template <typename CM>
218class NearestInsertionTsp : public InsertionTsp<CM> {
219public:
220  NearestInsertionTsp(const FullGraph &gr, const CM &cost)
221    : InsertionTsp<CM>(gr, cost) {}
222  typename CM::Value run() {
223    return InsertionTsp<CM>::run(InsertionTsp<CM>::NEAREST);
224  }
225};
226
[1270]227// Algorithm class for Farthest Insertion
[1203]228template <typename CM>
229class FarthestInsertionTsp : public InsertionTsp<CM> {
230public:
231  FarthestInsertionTsp(const FullGraph &gr, const CM &cost)
232    : InsertionTsp<CM>(gr, cost) {}
233  typename CM::Value run() {
234    return InsertionTsp<CM>::run(InsertionTsp<CM>::FARTHEST);
235  }
236};
237
[1270]238// Algorithm class for Cheapest Insertion
[1203]239template <typename CM>
240class CheapestInsertionTsp : public InsertionTsp<CM> {
241public:
242  CheapestInsertionTsp(const FullGraph &gr, const CM &cost)
243    : InsertionTsp<CM>(gr, cost) {}
244  typename CM::Value run() {
245    return InsertionTsp<CM>::run(InsertionTsp<CM>::CHEAPEST);
246  }
247};
248
[1270]249// Algorithm class for Random Insertion
[1203]250template <typename CM>
251class RandomInsertionTsp : public InsertionTsp<CM> {
252public:
253  RandomInsertionTsp(const FullGraph &gr, const CM &cost)
254    : InsertionTsp<CM>(gr, cost) {}
255  typename CM::Value run() {
256    return InsertionTsp<CM>::run(InsertionTsp<CM>::RANDOM);
257  }
258};
259
260int main() {
261  GRAPH_TYPEDEFS(FullGraph);
262
263  // metricCostTest();
264
265  tspTestSmall<NearestNeighborTsp<ConstMap<Edge, int> > >("Nearest Neighbor");
266  tspTestSmall<GreedyTsp<ConstMap<Edge, int> > >("Greedy");
267  tspTestSmall<NearestInsertionTsp<ConstMap<Edge, int> > >("Nearest Insertion");
[1271]268  tspTestSmall<FarthestInsertionTsp<ConstMap<Edge, int> > >
269    ("Farthest Insertion");
270  tspTestSmall<CheapestInsertionTsp<ConstMap<Edge, int> > >
271    ("Cheapest Insertion");
[1203]272  tspTestSmall<RandomInsertionTsp<ConstMap<Edge, int> > >("Random Insertion");
273  tspTestSmall<ChristofidesTsp<ConstMap<Edge, int> > >("Christofides");
274  tspTestSmall<Opt2Tsp<ConstMap<Edge, int> > >("2-opt");
275
276  tspTestRandom<NearestNeighborTsp<DoubleEdgeMap > >("Nearest Neighbor");
277  tspTestRandom<GreedyTsp<DoubleEdgeMap > >("Greedy");
278  tspTestRandom<NearestInsertionTsp<DoubleEdgeMap > >("Nearest Insertion");
279  tspTestRandom<FarthestInsertionTsp<DoubleEdgeMap > >("Farthest Insertion");
280  tspTestRandom<CheapestInsertionTsp<DoubleEdgeMap > >("Cheapest Insertion");
281  tspTestRandom<RandomInsertionTsp<DoubleEdgeMap > >("Random Insertion");
282  tspTestRandom<ChristofidesTsp<DoubleEdgeMap > >("Christofides");
283  tspTestRandom<Opt2Tsp<DoubleEdgeMap > >("2-opt");
284
285  return 0;
286}
Note: See TracBrowser for help on using the repository browser.