Free cookie consent management tool by TermsFeed Policy Generator

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

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

#2521: working on TSP refactoring

File size: 8.9 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.ComponentModel;
24using HEAL.Attic;
25using HeuristicLab.Common;
26using HeuristicLab.Core;
27using HeuristicLab.Data;
28using HeuristicLab.Encodings.PermutationEncoding;
29
30namespace HeuristicLab.Problems.TravelingSalesman {
31  [StorableType("1a9bf60c-b6a6-4c95-8e99-5a2dec0ee892")]
32  public interface ITSPData : IItem {
33    double GetDistance(int fromCity, int toCity);
34    ITSPSolution GetSolution(Permutation tspTour, double tourLength);
35  }
36
37  [Item("Matrix-based TSP Data", "TSP that is representd by a distance matrix.")]
38  [StorableType("4df58a35-679d-4414-b815-9450ae100823")]
39  public sealed class MatrixTSPData : Item, ITSPData, INotifyPropertyChanged {
40
41    [Storable]
42    public DoubleMatrix Matrix { get; private set; }
43
44    [Storable]
45    private DoubleMatrix displayCoordinates;
46    public DoubleMatrix DisplayCoordinates {
47      get => displayCoordinates;
48      set {
49        if (displayCoordinates == value) return;
50        displayCoordinates = value;
51        OnPropertyChanged(nameof(DisplayCoordinates));
52      }
53    }
54
55    [StorableConstructor]
56    private MatrixTSPData(StorableConstructorFlag _) : base(_) { }
57    private MatrixTSPData(MatrixTSPData original, Cloner cloner) : base(original, cloner) {
58      Matrix = original.Matrix;
59      displayCoordinates = cloner.Clone(original.displayCoordinates);
60    }
61    public MatrixTSPData() {
62      Matrix = new DoubleMatrix(new double[0, 0], @readonly: true);
63      DisplayCoordinates = null;
64    }
65    public MatrixTSPData(double[,] matrix, double[,] coordinates = null) {
66      Matrix = new DoubleMatrix(matrix, @readonly: true);
67      if (coordinates != null) DisplayCoordinates = new DoubleMatrix(coordinates);
68      if (DisplayCoordinates != null && DisplayCoordinates.Columns != 2)
69        throw new ArgumentException("Argument must have exactly two columns.", nameof(coordinates));
70      if (DisplayCoordinates != null && DisplayCoordinates.Rows != Matrix.Rows)
71        throw new ArgumentException("Unequal number of rows in " + nameof(matrix) + " and " + nameof(coordinates) + ".");
72    }
73
74    public ITSPSolution GetSolution(Permutation tour, double tourLength) {
75      return new TSPSolution(DisplayCoordinates, tour, new DoubleValue(tourLength));
76    }
77
78    public override IDeepCloneable Clone(Cloner cloner) {
79      return new MatrixTSPData(this, cloner);
80    }
81
82    public void SetMatrix(double[,] matrix, double[,] coordinates = null) {
83      Matrix = new DoubleMatrix(matrix, @readonly: true);
84      OnPropertyChanged(nameof(Matrix));
85      if (coordinates == null) DisplayCoordinates = null;
86      else DisplayCoordinates = new DoubleMatrix(coordinates);
87      if (DisplayCoordinates != null && DisplayCoordinates.Columns != 2)
88        throw new ArgumentException("Argument must have exactly two columns.", nameof(coordinates));
89      if (DisplayCoordinates != null && DisplayCoordinates.Rows != Matrix.Rows)
90        throw new ArgumentException("Unequal number of rows in " + nameof(matrix) + " and " + nameof(coordinates) + ".");
91    }
92
93    public void SetMatrix(DoubleMatrix matrix, DoubleMatrix coordinates = null) {
94      Matrix = (DoubleMatrix)matrix.AsReadOnly();
95      OnPropertyChanged(nameof(Matrix));
96      DisplayCoordinates = (DoubleMatrix)coordinates?.Clone();
97      if (DisplayCoordinates != null && DisplayCoordinates.Columns != 2)
98        throw new ArgumentException("Argument must have exactly two columns.", nameof(coordinates));
99      if (DisplayCoordinates != null && DisplayCoordinates.Rows != Matrix.Rows)
100        throw new ArgumentException("Unequal number of rows in " + nameof(matrix) + " and " + nameof(coordinates) + ".");
101    }
102
103    public double GetDistance(int fromCity, int toCity) => Matrix[fromCity, toCity];
104
105
106    public event PropertyChangedEventHandler PropertyChanged;
107    private void OnPropertyChanged(string property) {
108      PropertyChanged?.Invoke(this, new PropertyChangedEventArgs(property));
109    }
110  }
111
112  [Item("Coordinates-based TSP Data", "TSP that is represented by coordinates of locations.")]
113  [StorableType("3955d07a-d43c-4a01-9505-d2effb1ea865")]
114  public abstract class CoordinatesTSPData : Item, ITSPData {
115    [Storable]
116    public DoubleMatrix Coordinates { get; set; }
117
118    [StorableConstructor]
119    protected CoordinatesTSPData(StorableConstructorFlag _) : base(_) { }
120    protected CoordinatesTSPData(CoordinatesTSPData original, Cloner cloner) : base(original, cloner) {
121      Coordinates = cloner.Clone(original.Coordinates);
122    }
123    protected CoordinatesTSPData() : base() {
124      Coordinates = new DoubleMatrix();
125    }
126    protected CoordinatesTSPData(double[,] coordinates) : base() {
127      if (coordinates == null) throw new ArgumentNullException(nameof(coordinates));
128      if (coordinates.GetLength(1) != 2) throw new ArgumentException("Argument must have exactly two columns.", nameof(coordinates));
129      Coordinates = new DoubleMatrix(coordinates);
130    }
131
132    public double GetDistance(int fromCity, int toCity) {
133      return GetDistance(Coordinates[fromCity, 0], Coordinates[fromCity, 1],
134        Coordinates[toCity, 0], Coordinates[toCity, 1]);
135    }
136
137    public abstract double GetDistance(double fromX, double fromY, double toX, double toY);
138
139    public ITSPSolution GetSolution(Permutation tour, double tourLength) {
140      return new TSPSolution(Coordinates, tour, new DoubleValue(tourLength));
141    }
142  }
143
144  [Item("Euclidean TSP Data", "TSP that is represented by coordinates in an Euclidean plane.")]
145  [StorableType("4bf58348-cd98-46c5-a4c0-55f486ca88b4")]
146  public sealed class EuclideanTSPData : CoordinatesTSPData {
147    public enum RoundingMode { None, Midpoint, Ceiling }
148
149    [Storable]
150    public RoundingMode Rounding { get; set; }
151
152    [StorableConstructor]
153    private EuclideanTSPData(StorableConstructorFlag _) : base(_) { }
154    private EuclideanTSPData(EuclideanTSPData original, Cloner cloner) : base(original, cloner) {
155      Rounding = original.Rounding;
156    }
157    public EuclideanTSPData() : base() { }
158    public EuclideanTSPData(double[,] coordinates) : base(coordinates) { }
159
160    public override IDeepCloneable Clone(Cloner cloner) {
161      return new EuclideanTSPData(this, cloner);
162    }
163
164    public override double GetDistance(double fromX, double fromY, double toX, double toY) {
165      var dist = Math.Sqrt((fromX - toX) * (fromX - toX) + (fromY - toY) * (fromY - toY));
166      switch (Rounding) {
167        case RoundingMode.None: return dist;
168        case RoundingMode.Midpoint: return Math.Round(dist);
169        case RoundingMode.Ceiling: return Math.Ceiling(dist);
170        default: throw new InvalidOperationException("Unknown rounding mode " + Rounding);
171      }
172    }
173  }
174
175  [Item("Geo TSP Data", "TSP that is represented by geo coordinates.")]
176  [StorableType("4bf58348-cd98-46c5-a4c0-55f486ca88b4")]
177  public sealed class GeoTSPData : CoordinatesTSPData {
178    public const double PI = 3.141592;
179    public const double RADIUS = 6378.388;
180
181    [StorableConstructor]
182    private GeoTSPData(StorableConstructorFlag _) : base(_) { }
183    private GeoTSPData(GeoTSPData original, Cloner cloner) : base(original, cloner) { }
184    public GeoTSPData() : base() { }
185    public GeoTSPData(double[,] coordinates) : base(coordinates) { }
186
187    public override IDeepCloneable Clone(Cloner cloner) {
188      return new GeoTSPData(this, cloner);
189    }
190
191    public override double GetDistance(double fromX, double fromY, double toX, double toY) {
192      double latitude1, longitude1, latitude2, longitude2;
193      double q1, q2, q3;
194      double length;
195
196      latitude1 = ConvertToRadian(fromX);
197      longitude1 = ConvertToRadian(fromY);
198      latitude2 = ConvertToRadian(toX);
199      longitude2 = ConvertToRadian(toY);
200
201      q1 = Math.Cos(longitude1 - longitude2);
202      q2 = Math.Cos(latitude1 - latitude2);
203      q3 = Math.Cos(latitude1 + latitude2);
204
205      length = (int)(RADIUS * Math.Acos(0.5 * ((1.0 + q1) * q2 - (1.0 - q1) * q3)) + 1.0);
206      return (length);
207    }
208
209    private double ConvertToRadian(double x) {
210      return PI * (Math.Truncate(x) + 5.0 * (x - Math.Truncate(x)) / 3.0) / 180.0;
211    }
212  }
213}
Note: See TracBrowser for help on using the repository browser.