Free cookie consent management tool by TermsFeed Policy Generator

source: branches/2521_ProblemRefactoring/HeuristicLab.Problems.TravelingSalesman/3.3/TSPData.cs @ 17529

Last change on this file since 17529 was 17529, checked in by abeham, 4 years ago

#2521: some fixes and reusing handling of distance measure as defined in TSP

File size: 16.2 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) Heuristic and Evolutionary Algorithms Laboratory (HEAL)
4 *
5 * This file is part of HeuristicLab.
6 *
7 * HeuristicLab is free software: you can redistribute it and/or modify
8 * it under the terms of the GNU General Public License as published by
9 * the Free Software Foundation, either version 3 of the License, or
10 * (at your option) any later version.
11 *
12 * HeuristicLab is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15 * GNU General Public License for more details.
16 *
17 * You should have received a copy of the GNU General Public License
18 * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
19 */
20#endregion
21
22using System;
23using System.Collections.Generic;
24using HEAL.Attic;
25using HeuristicLab.Common;
26using HeuristicLab.Core;
27using HeuristicLab.Data;
28using HeuristicLab.Encodings.PermutationEncoding;
29using HeuristicLab.Problems.Instances;
30
31namespace HeuristicLab.Problems.TravelingSalesman {
32  [StorableType("1a9bf60c-b6a6-4c95-8e99-5a2dec0ee892")]
33  public interface ITSPData : INamedItem {
34    int Cities { get; }
35
36    double GetDistance(int fromCity, int toCity);
37    double GetPathDistance(IEnumerable<int> path, bool closed = true);
38    ITSPSolution GetSolution(Permutation tspTour, double tourLength);
39    TSPData Export();
40  }
41
42  [Item("Matrix-based TSP Data", "TSP that is representd by a distance matrix.")]
43  [StorableType("4df58a35-679d-4414-b815-9450ae100823")]
44  public sealed class MatrixTSPData : NamedItem, ITSPData {
45    [Storable] public DoubleMatrix Matrix { get; private set; }
46    [Storable] public DoubleMatrix DisplayCoordinates { get; private set; }
47
48    public int Cities => Matrix.Rows;
49
50    [StorableConstructor]
51    private  MatrixTSPData(StorableConstructorFlag _) : base(_) { }
52    private MatrixTSPData(MatrixTSPData original, Cloner cloner) : base(original, cloner) {
53      Matrix = original.Matrix;
54      DisplayCoordinates = original.DisplayCoordinates;
55    }
56    public MatrixTSPData() {
57      Name = TSPDefaultInstance.Name;
58      Matrix = TSPDefaultInstance.Distances;
59      DisplayCoordinates = TSPDefaultInstance.Coordinates;
60    }
61    public MatrixTSPData(string name, double[,] matrix, double[,] coordinates = null) {
62      if (coordinates != null && coordinates.GetLength(1) != 2)
63        throw new ArgumentException("Argument must have exactly two columns.", nameof(coordinates));
64      if (coordinates != null && coordinates.GetLength(0) != matrix.GetLength(0))
65        throw new ArgumentException("Unequal number of rows in " + nameof(matrix) + " and " + nameof(coordinates) + ".");
66      Name = name;
67      Matrix = new DoubleMatrix(matrix, @readonly: true);
68      if (coordinates != null) DisplayCoordinates = new DoubleMatrix(coordinates, @readonly: true);
69    }
70    public MatrixTSPData(string name, DoubleMatrix matrix, DoubleMatrix coordinates = null) {
71      if (coordinates != null && coordinates.Columns != 2)
72        throw new ArgumentException("Argument must have exactly two columns.", nameof(coordinates));
73      if (coordinates != null && coordinates.Rows != matrix.Rows)
74        throw new ArgumentException("Unequal number of rows in " + nameof(matrix) + " and " + nameof(coordinates) + ".");
75      Name = name;
76      Matrix = matrix.AsReadOnly();
77      DisplayCoordinates = coordinates?.AsReadOnly();
78    }
79
80    public ITSPSolution GetSolution(Permutation tour, double tourLength) {
81      return new TSPSolution(this, tour, new DoubleValue(tourLength));
82    }
83
84    public override IDeepCloneable Clone(Cloner cloner) {
85      return new MatrixTSPData(this, cloner);
86    }
87
88    public double GetDistance(int fromCity, int toCity) => Matrix[fromCity, toCity];
89    public double GetPathDistance(IEnumerable<int> path, bool closed = true) {
90      var iter = path.GetEnumerator();
91      if (!iter.MoveNext()) return 0;
92      var start = iter.Current;
93      var prev = start;
94      var distance = 0.0;
95      while (iter.MoveNext()) {
96        var cur = iter.Current;
97        distance += Matrix[prev, cur];
98        prev = cur;
99      }
100      if (closed) distance += Matrix[prev, start];
101      return distance;
102    }
103    public TSPData Export() {
104      return new TSPData() {
105        Name = name,
106        Description = description,
107        Coordinates = DisplayCoordinates?.CloneAsMatrix(),
108        Dimension = Matrix.Rows,
109        DistanceMeasure = DistanceMeasure.Direct,
110        Distances = Matrix.CloneAsMatrix()
111      };
112    }
113  }
114
115  [Item("Coordinates-based TSP Data", "TSP that is represented by coordinates of locations.")]
116  [StorableType("3955d07a-d43c-4a01-9505-d2effb1ea865")]
117  public abstract class CoordinatesTSPData : NamedItem, ITSPData {
118    [Storable] public DoubleMatrix Coordinates { get; protected set; }
119
120    public int Cities => Coordinates.Rows;
121
122    [StorableConstructor]
123    protected CoordinatesTSPData(StorableConstructorFlag _) : base(_) { }
124    protected CoordinatesTSPData(CoordinatesTSPData original, Cloner cloner) : base(original, cloner) {
125      Coordinates = original.Coordinates;
126    }
127    protected CoordinatesTSPData() : base() {
128      Name = TSPDefaultInstance.Name;
129      Coordinates = TSPDefaultInstance.Coordinates;
130    }
131    protected CoordinatesTSPData(string name, double[,] coordinates) : base() {
132      if (coordinates == null) throw new ArgumentNullException(nameof(coordinates));
133      if (coordinates.GetLength(1) != 2) throw new ArgumentException("Argument must have exactly two columns.", nameof(coordinates));
134      Name = name;
135      Coordinates = new DoubleMatrix(coordinates, @readonly: true);
136    }
137    protected CoordinatesTSPData(string name, DoubleMatrix coordinates) : base() {
138      if (coordinates == null) throw new ArgumentNullException(nameof(coordinates));
139      if (coordinates.Columns != 2) throw new ArgumentException("Argument must have exactly two columns.", nameof(coordinates));
140      Name = name;
141      Coordinates = coordinates.AsReadOnly();
142    }
143
144    public double GetDistance(int fromCity, int toCity) {
145      return GetDistance(Coordinates[fromCity, 0], Coordinates[fromCity, 1],
146        Coordinates[toCity, 0], Coordinates[toCity, 1]);
147    }
148
149    public abstract double GetDistance(double fromX, double fromY, double toX, double toY);
150    public double GetPathDistance(IEnumerable<int> path, bool closed = true) {
151      var iter = path.GetEnumerator();
152      if (!iter.MoveNext()) return 0;
153      var start = iter.Current;
154      var prev = start;
155      var distance = 0.0;
156      while (iter.MoveNext()) {
157        var cur = iter.Current;
158        distance += GetDistance(prev, cur);
159        prev = cur;
160      }
161      if (closed) distance += GetDistance(prev, start);
162      return distance;
163    }
164
165    public double[,] CalculateDistanceMatrix() {
166      var matrix = new double[Cities, Cities];
167      for (var i = 0; i < Cities; i++) {
168        for (var j = 0; j < Cities; j++) {
169          matrix[i, j] = GetDistance(i, j);
170        }
171      }
172      return matrix;
173    }
174
175    public virtual ITSPSolution GetSolution(Permutation tour, double tourLength) {
176      return new TSPSolution(this, tour, new DoubleValue(tourLength));
177    }
178
179    public abstract TSPData Export();
180  }
181
182  [Item("Euclidean TSP Data", "TSP that is represented by coordinates in an Euclidean plane.")]
183  [StorableType("4bf58348-cd98-46c5-a4c0-55f486ca88b4")]
184  public sealed class EuclideanTSPData : CoordinatesTSPData {
185    [StorableType("be274140-e289-4125-ae3e-8c2f1d942f94")]
186    public enum DistanceRounding { None, Midpoint, Ceiling }
187
188    [Storable] public DistanceRounding Rounding { get; private set; }
189
190    [StorableConstructor]
191    private EuclideanTSPData(StorableConstructorFlag _) : base(_) { }
192    private EuclideanTSPData(EuclideanTSPData original, Cloner cloner) : base(original, cloner) {
193      Rounding = original.Rounding;
194    }
195    public EuclideanTSPData()
196      : base() {
197      Rounding = DistanceRounding.Midpoint;
198    }
199    public EuclideanTSPData(string name, double[,] coordinates, DistanceRounding rounding = DistanceRounding.None)
200      : base(name, coordinates) {
201      Rounding = rounding;
202    }
203    public EuclideanTSPData(string name, DoubleMatrix coordinates, DistanceRounding rounding = DistanceRounding.None)
204      : base(name, coordinates) {
205      Rounding = rounding;
206    }
207
208    public override IDeepCloneable Clone(Cloner cloner) {
209      return new EuclideanTSPData(this, cloner);
210    }
211
212    public override double GetDistance(double fromX, double fromY, double toX, double toY) {
213      var dist = DistanceHelper.EuclideanDistance(fromX, fromY, toX, toY);
214      switch (Rounding) {
215        case DistanceRounding.None: return dist;
216        case DistanceRounding.Midpoint: return Math.Round(dist);
217        case DistanceRounding.Ceiling: return Math.Ceiling(dist);
218        default: throw new InvalidOperationException("Unknown rounding mode " + Rounding);
219      }
220    }
221
222    public override TSPData Export() {
223      var data = new TSPData() {
224        Name = name,
225        Description = description,
226        Coordinates = Coordinates.CloneAsMatrix(),
227        Dimension = Coordinates.Rows
228      };
229      switch (Rounding) {
230        case DistanceRounding.None: data.DistanceMeasure = DistanceMeasure.Euclidean; break;
231        case DistanceRounding.Midpoint: data.DistanceMeasure = DistanceMeasure.RoundedEuclidean; break;
232        case DistanceRounding.Ceiling: data.DistanceMeasure = DistanceMeasure.UpperEuclidean; break;
233      }
234      return data;
235    }
236  }
237
238  [Item("Geo TSP Data", "TSP that is represented by geo coordinates.")]
239  [StorableType("dc859a89-e6c2-4af3-a3b6-9aa3041b14a9")]
240  public sealed class GeoTSPData : CoordinatesTSPData {
241    [StorableConstructor]
242    private GeoTSPData(StorableConstructorFlag _) : base(_) { }
243    private GeoTSPData(GeoTSPData original, Cloner cloner) : base(original, cloner) { }
244    public GeoTSPData() : base() { }
245    public GeoTSPData(string name, double[,] coordinates) : base(name, coordinates) { }
246    public GeoTSPData(string name, DoubleMatrix coordinates) : base(name, coordinates) { }
247
248    public override IDeepCloneable Clone(Cloner cloner) {
249      return new GeoTSPData(this, cloner);
250    }
251
252    public override double GetDistance(double fromX, double fromY, double toX, double toY) {
253      return DistanceHelper.GeoDistance(fromX, fromY, toX, toY);
254    }
255
256    public override TSPData Export() {
257      return new TSPData() {
258        Name = name,
259        Description = description,
260        Coordinates = Coordinates.CloneAsMatrix(),
261        Dimension = Coordinates.Rows,
262        DistanceMeasure = DistanceMeasure.Geo
263      };
264    }
265  }
266
267  [Item("ATT TSP Data", "TSP that is represented by ATT coordinates.")]
268  [StorableType("d7a0add3-6ec1-42e0-b1d7-b6454694d485")]
269  public sealed class AttTSPData : CoordinatesTSPData {
270    [StorableConstructor]
271    private AttTSPData(StorableConstructorFlag _) : base(_) { }
272    private AttTSPData(AttTSPData original, Cloner cloner) : base(original, cloner) { }
273    public AttTSPData() : base() { }
274    public AttTSPData(string name, double[,] coordinates) : base(name, coordinates) { }
275    public AttTSPData(string name, DoubleMatrix coordinates) : base(name, coordinates) { }
276
277    public override IDeepCloneable Clone(Cloner cloner) {
278      return new AttTSPData(this, cloner);
279    }
280
281    public override double GetDistance(double fromX, double fromY, double toX, double toY) {
282      return DistanceHelper.AttDistance(fromX, fromY, toX, toY);
283    }
284
285    public override TSPData Export() {
286      return new TSPData() {
287        Name = name,
288        Description = description,
289        Coordinates = Coordinates.CloneAsMatrix(),
290        Dimension = Coordinates.Rows,
291        DistanceMeasure = DistanceMeasure.Att
292      };
293    }
294  }
295
296  [Item("Manhattan TSP Data", "TSP that is represented by Manhattan coordinates.")]
297  [StorableType("5f1ef9e2-cbd1-400e-8f87-6855f091fc9e")]
298  public sealed class ManhattanTSPData : CoordinatesTSPData {
299    [StorableConstructor]
300    private ManhattanTSPData(StorableConstructorFlag _) : base(_) { }
301    private ManhattanTSPData(ManhattanTSPData original, Cloner cloner) : base(original, cloner) { }
302    public ManhattanTSPData() : base() { }
303    public ManhattanTSPData(string name, double[,] coordinates) : base(name, coordinates) { }
304    public ManhattanTSPData(string name, DoubleMatrix coordinates) : base(name, coordinates) { }
305
306    public override IDeepCloneable Clone(Cloner cloner) {
307      return new ManhattanTSPData(this, cloner);
308    }
309
310    public override double GetDistance(double fromX, double fromY, double toX, double toY) {
311      return DistanceHelper.ManhattanDistance(fromX, fromY, toX, toY);
312    }
313
314    public override TSPData Export() {
315      return new TSPData() {
316        Name = name,
317        Description = description,
318        Coordinates = Coordinates.CloneAsMatrix(),
319        Dimension = Coordinates.Rows,
320        DistanceMeasure = DistanceMeasure.Manhattan
321      };
322    }
323  }
324
325  [Item("Manhattan TSP Data", "TSP that is represented by the maximum absolute distance in either x or y coordinates.")]
326  [StorableType("c6294a6c-fe62-4906-9765-4bc306d3e4a8")]
327  public sealed class MaximumTSPData : CoordinatesTSPData {
328    [StorableConstructor]
329    private MaximumTSPData(StorableConstructorFlag _) : base(_) { }
330    private MaximumTSPData(MaximumTSPData original, Cloner cloner) : base(original, cloner) { }
331    public MaximumTSPData() : base() { }
332    public MaximumTSPData(string name, double[,] coordinates) : base(name, coordinates) { }
333    public MaximumTSPData(string name, DoubleMatrix coordinates) : base(name, coordinates) { }
334
335    public override IDeepCloneable Clone(Cloner cloner) {
336      return new MaximumTSPData(this, cloner);
337    }
338
339    public override double GetDistance(double fromX, double fromY, double toX, double toY) {
340      return DistanceHelper.MaximumDistance(fromX, fromY, toX, toY);
341    }
342
343    public override TSPData Export() {
344      return new TSPData() {
345        Name = name,
346        Description = description,
347        Coordinates = Coordinates.CloneAsMatrix(),
348        Dimension = Coordinates.Rows,
349        DistanceMeasure = DistanceMeasure.Maximum
350      };
351    }
352  }
353
354  internal static class TSPDefaultInstance {
355    internal static readonly DoubleMatrix Distances = new DoubleMatrix(new double[,] {
356{ 0, 100, 200, 300, 100, 141, 224, 316, 200, 224, 283, 361, 300, 316, 361, 424 },
357{ 100, 0, 100, 200, 141, 100, 141, 224, 224, 200, 224, 283, 316, 300, 316, 361 },
358{ 200, 100, 0, 100, 224, 141, 100, 141, 283, 224, 200, 224, 361, 316, 300, 316 },
359{ 300, 200, 100, 0, 316, 224, 141, 100, 361, 283, 224, 200, 424, 361, 316, 300 },
360{ 100, 141, 224, 316, 0, 100, 200, 300, 100, 141, 224, 316, 200, 224, 283, 361 },
361{ 141, 100, 141, 224, 100, 0, 100, 200, 141, 100, 141, 224, 224, 200, 224, 283 },
362{ 224, 141, 100, 141, 200, 100, 0, 100, 224, 141, 100, 141, 283, 224, 200, 224 },
363{ 316, 224, 141, 100, 300, 200, 100, 0, 316, 224, 141, 100, 361, 283, 224, 200 },
364{ 200, 224, 283, 361, 100, 141, 224, 316, 0, 100, 200, 300, 100, 141, 224, 316 },
365{ 224, 200, 224, 283, 141, 100, 141, 224, 100, 0, 100, 200, 141, 100, 141, 224 },
366{ 283, 224, 200, 224, 224, 141, 100, 141, 200, 100, 0, 100, 224, 141, 100, 141 },
367{ 361, 283, 224, 200, 316, 224, 141, 100, 300, 200, 100, 0, 316, 224, 141, 100 },
368{ 300, 316, 361, 424, 200, 224, 283, 361, 100, 141, 224, 316, 0, 100, 200, 300 },
369{ 316, 300, 316, 361, 224, 200, 224, 283, 141, 100, 141, 224, 100, 0, 100, 200 },
370{ 361, 316, 300, 316, 283, 224, 200, 224, 224, 141, 100, 141, 200, 100, 0, 100 },
371{ 424, 361, 316, 300, 361, 283, 224, 200, 316, 224, 141, 100, 300, 200, 100, 0 },
372}, @readonly: true);
373    internal static readonly DoubleMatrix Coordinates = new DoubleMatrix(new double[,] {
374{ 100, 100 }, { 100, 200 }, { 100, 300 }, { 100, 400 },
375{ 200, 100 }, { 200, 200 }, { 200, 300 }, { 200, 400 },
376{ 300, 100 }, { 300, 200 }, { 300, 300 }, { 300, 400 },
377{ 400, 100 }, { 400, 200 }, { 400, 300 }, { 400, 400 }
378}, @readonly: true);
379    internal static readonly string Name = "HL TSP Default";
380  }
381}
Note: See TracBrowser for help on using the repository browser.