Free cookie consent management tool by TermsFeed Policy Generator

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

Last change on this file since 17533 was 17533, checked in by abeham, 2 years ago

#2521: Unified architecture

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