Changeset 7872

Timestamp:

05/22/12 17:38:36 (12 years ago)

Author:

svonolfe

Message:

Moved distance measure to helper class (#1782)

Location:

trunk/sources

Files:

• HeuristicLab.Problems.Instances.TSPLIB/3.3/TSPLIBCVRPInstanceProvider.cs (modified) (1 diff)
• HeuristicLab.Problems.Instances.TSPLIB/3.3/TSPLIBTSPInstanceProvider.cs (modified) (1 diff)
• HeuristicLab.Problems.Instances/3.3/HeuristicLab.Problems.Instances-3.3.csproj (modified) (1 diff)
• HeuristicLab.Problems.Instances/3.3/Types/DistanceHelper.cs (added)
• HeuristicLab.Problems.Instances/3.3/Types/TSPData.cs (modified) (3 diffs)
• HeuristicLab.Problems.Instances/3.3/Types/VRP (added)
• HeuristicLab.Problems.Instances/3.3/Types/VRP/CVRPData.cs (moved) (moved from trunk/sources/HeuristicLab.Problems.Instances/3.3/Types/CVRPData.cs) (3 diffs)
• HeuristicLab.Problems.Instances/3.3/Types/VRP/IVRPData.cs (added)
• HeuristicLab.Problems.TravelingSalesman/3.3/TravelingSalesmanProblem.cs (modified) (3 diffs)

trunk/sources/HeuristicLab.Problems.Instances.TSPLIB/3.3/TSPLIBCVRPInstanceProvider.cs

@@ -46 +46 @@
       switch (parser.EdgeWeightType) {
         case TSPLIBEdgeWeightTypes.ATT:
-          instance.DistanceMeasure = CVRPDistanceMeasure.Att; break;
+          instance.DistanceMeasure = DistanceMeasure.Att; break;
         case TSPLIBEdgeWeightTypes.CEIL_2D:
-          instance.DistanceMeasure = CVRPDistanceMeasure.UpperEuclidean; break;
+          instance.DistanceMeasure = DistanceMeasure.UpperEuclidean; break;
         case TSPLIBEdgeWeightTypes.EUC_2D:
         case TSPLIBEdgeWeightTypes.EUC_3D:
-          instance.DistanceMeasure = CVRPDistanceMeasure.RoundedEuclidean; break;
+          instance.DistanceMeasure = DistanceMeasure.RoundedEuclidean; break;
         case TSPLIBEdgeWeightTypes.EXPLICIT:
-          instance.DistanceMeasure = CVRPDistanceMeasure.Direct; break;
+          instance.DistanceMeasure = DistanceMeasure.Direct; break;
         case TSPLIBEdgeWeightTypes.GEO:
-          instance.DistanceMeasure = CVRPDistanceMeasure.Geo; break;
+          instance.DistanceMeasure = DistanceMeasure.Geo; break;
         case TSPLIBEdgeWeightTypes.MAN_2D:
         case TSPLIBEdgeWeightTypes.MAN_3D:
-          instance.DistanceMeasure = CVRPDistanceMeasure.Manhattan; break;
+          instance.DistanceMeasure = DistanceMeasure.Manhattan; break;
         case TSPLIBEdgeWeightTypes.MAX_2D:
         case TSPLIBEdgeWeightTypes.MAX_3D:
-          instance.DistanceMeasure = CVRPDistanceMeasure.Maximum; break;
+          instance.DistanceMeasure = DistanceMeasure.Maximum; break;
         default:
           throw new InvalidDataException("The given edge weight is not supported by HeuristicLab.");

trunk/sources/HeuristicLab.Problems.Instances.TSPLIB/3.3/TSPLIBTSPInstanceProvider.cs

@@ -46 +46 @@
       switch (parser.EdgeWeightType) {
         case TSPLIBEdgeWeightTypes.ATT:
-          instance.DistanceMeasure = TSPDistanceMeasure.Att; break;
+          instance.DistanceMeasure = DistanceMeasure.Att; break;
         case TSPLIBEdgeWeightTypes.CEIL_2D:
-          instance.DistanceMeasure = TSPDistanceMeasure.UpperEuclidean; break;
+          instance.DistanceMeasure = DistanceMeasure.UpperEuclidean; break;
         case TSPLIBEdgeWeightTypes.EUC_2D:
-          instance.DistanceMeasure = TSPDistanceMeasure.RoundedEuclidean; break;
+          instance.DistanceMeasure = DistanceMeasure.RoundedEuclidean; break;
         case TSPLIBEdgeWeightTypes.EUC_3D:
           throw new InvalidDataException("3D coordinates are not supported.");
         case TSPLIBEdgeWeightTypes.EXPLICIT:
-          instance.DistanceMeasure = TSPDistanceMeasure.Direct; break;
+          instance.DistanceMeasure = DistanceMeasure.Direct; break;
         case TSPLIBEdgeWeightTypes.GEO:
-          instance.DistanceMeasure = TSPDistanceMeasure.Geo; break;
+          instance.DistanceMeasure = DistanceMeasure.Geo; break;
         case TSPLIBEdgeWeightTypes.MAN_2D:
-          instance.DistanceMeasure = TSPDistanceMeasure.Manhattan; break;
+          instance.DistanceMeasure = DistanceMeasure.Manhattan; break;
         case TSPLIBEdgeWeightTypes.MAN_3D:
           throw new InvalidDataException("3D coordinates are not supported.");
         case TSPLIBEdgeWeightTypes.MAX_2D:
-          instance.DistanceMeasure = TSPDistanceMeasure.Maximum; break;
+          instance.DistanceMeasure = DistanceMeasure.Maximum; break;
         case TSPLIBEdgeWeightTypes.MAX_3D:
           throw new InvalidDataException("3D coordinates are not supported.");

trunk/sources/HeuristicLab.Problems.Instances/3.3/HeuristicLab.Problems.Instances-3.3.csproj

@@ -117 +117 @@
     <Compile Include="Types\CTAPData.cs" />
     <Compile Include="IDataDescriptor.cs" />
-    <Compile Include="Types\CVRPData.cs" />
+    <Compile Include="Types\DistanceHelper.cs" />
+    <Compile Include="Types\VRP\CVRPData.cs" />
     <Compile Include="Types\GQAPData.cs" />
+    <Compile Include="Types\VRP\IVRPData.cs" />
     <Compile Include="Types\QAPData.cs" />
     <Compile Include="Types\TSPData.cs" />

trunk/sources/HeuristicLab.Problems.Instances/3.3/Types/TSPData.cs

@@ -23 +23 @@
 
 namespace HeuristicLab.Problems.Instances {
-  public enum TSPDistanceMeasure { Direct, Euclidean, RoundedEuclidean, UpperEuclidean, Geo, Manhattan, Maximum, Att };
-
   /// <summary>
   /// Describes instances of the Traveling Salesman Problem (TSP).
@@ -45 +43 @@
     /// Specifies the distance measure that is to be used.
     /// </summary>
-    public TSPDistanceMeasure DistanceMeasure { get; set; }
+    public DistanceMeasure DistanceMeasure { get; set; }
     /// <summary>
     /// Optional! The distances are given in form of a distance matrix.
@@ -81 +79 @@
     /// <returns>A full distance matrix between all cities.</returns>
     public double[,] GetDistanceMatrix() {
-      if (Distances != null) return Distances;
-      Distances = new double[Dimension, Dimension];
-      for (int i = 0; i < Dimension - 1; i++)
-        for (int j = i + 1; j < Dimension; j++) {
-          Distances[i, j] = GetDistance(i, j);
-          Distances[j, i] = Distances[i, j];
-        }
-      return Distances;
+      return DistanceHelper.GetDistanceMatrix(DistanceMeasure, Coordinates, Distances, Dimension);
     }
-
-    #region Private Helpers
-    private double GetDistance(int i, int j) {
-      switch (DistanceMeasure) {
-        case TSPDistanceMeasure.Att:
-          return AttDistance(Coordinates[i, 0], Coordinates[i, 1], Coordinates[j, 0], Coordinates[j, 1]);
-        case TSPDistanceMeasure.Direct:
-          return Distances[i, j];
-        case TSPDistanceMeasure.Euclidean:
-          return EuclideanDistance(Coordinates[i, 0], Coordinates[i, 1], Coordinates[j, 0], Coordinates[j, 1]);
-        case TSPDistanceMeasure.Geo:
-          return GeoDistance(Coordinates[i, 0], Coordinates[i, 1], Coordinates[j, 0], Coordinates[j, 1]);
-        case TSPDistanceMeasure.Manhattan:
-          return ManhattanDistance(Coordinates[i, 0], Coordinates[i, 1], Coordinates[j, 0], Coordinates[j, 1]);
-        case TSPDistanceMeasure.Maximum:
-          return MaximumDistance(Coordinates[i, 0], Coordinates[i, 1], Coordinates[j, 0], Coordinates[j, 1]);
-        case TSPDistanceMeasure.RoundedEuclidean:
-          return Math.Round(EuclideanDistance(Coordinates[i, 0], Coordinates[i, 1], Coordinates[j, 0], Coordinates[j, 1]));
-        case TSPDistanceMeasure.UpperEuclidean:
-          return Math.Ceiling(EuclideanDistance(Coordinates[i, 0], Coordinates[i, 1], Coordinates[j, 0], Coordinates[j, 1]));
-        default:
-          throw new InvalidOperationException("Distance measure is not known.");
-      }
-    }
-
-    private double AttDistance(double x1, double y1, double x2, double y2) {
-      return Math.Ceiling(Math.Sqrt(((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2)) / 10.0));
-    }
-
-    private double EuclideanDistance(double x1, double y1, double x2, double y2) {
-      return Math.Sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
-    }
-
-    private const double PI = 3.141592;
-    private const double RADIUS = 6378.388;
-    private double GeoDistance(double x1, double y1, double x2, double y2) {
-      double latitude1, longitude1, latitude2, longitude2;
-      double q1, q2, q3;
-      double length;
-
-      latitude1 = ConvertToRadian(x1);
-      longitude1 = ConvertToRadian(y1);
-      latitude2 = ConvertToRadian(x2);
-      longitude2 = ConvertToRadian(y2);
-
-      q1 = Math.Cos(longitude1 - longitude2);
-      q2 = Math.Cos(latitude1 - latitude2);
-      q3 = Math.Cos(latitude1 + latitude2);
-
-      length = (int)(RADIUS * Math.Acos(0.5 * ((1.0 + q1) * q2 - (1.0 - q1) * q3)) + 1.0);
-      return (length);
-    }
-
-    private double ConvertToRadian(double x) {
-      return PI * (Math.Truncate(x) + 5.0 * (x - Math.Truncate(x)) / 3.0) / 180.0;
-    }
-
-    private double ManhattanDistance(double x1, double y1, double x2, double y2) {
-      return Math.Round(Math.Abs(x1 - x2) + Math.Abs(y1 - y2), MidpointRounding.AwayFromZero);
-    }
-
-    private double MaximumDistance(double x1, double y1, double x2, double y2) {
-      return Math.Max(Math.Round(Math.Abs(x1 - x2), MidpointRounding.AwayFromZero), Math.Round(Math.Abs(y1 - y2), MidpointRounding.AwayFromZero));
-    }
-    #endregion
   }
 }

trunk/sources/HeuristicLab.Problems.Instances/3.3/Types/VRP/CVRPData.cs

@@ -22 +22 @@
 
 namespace HeuristicLab.Problems.Instances {
-  public enum CVRPDistanceMeasure { Direct, Euclidean, RoundedEuclidean, UpperEuclidean, Geo, Manhattan, Maximum, Att };
-
   /// <summary>
   /// Describes instances of the Capacitated Vehicle Routing Problem (CVRP).
   /// </summary>
-  public class CVRPData {
+  public class CVRPData: IVRPData {
     /// <summary>
     /// The name of the instance
@@ -45 +43 @@
     ///the coordinates if no <see cref="Distances"/> is given.
     /// </summary>
-    public CVRPDistanceMeasure DistanceMeasure { get; set; }
+    public DistanceMeasure DistanceMeasure { get; set; }
     /// <summary>
     /// Optional! The maximum number of vehicles that can be used.
@@ -90 +88 @@
     /// </summary>
     public double? BestKnownQuality { get; set; }
+
+    /// <summary>
+    /// If only the coordinates are given, can calculate the distance matrix.
+    /// </summary>
+    /// <returns>A full distance matrix between all cities.</returns>
+    public double[,] GetDistanceMatrix() {
+      return DistanceHelper.GetDistanceMatrix(DistanceMeasure, Coordinates, Distances, Dimension);
+    }
   }
 }

trunk/sources/HeuristicLab.Problems.TravelingSalesman/3.3/TravelingSalesmanProblem.cs

@@ -347 +347 @@
       if (data.Coordinates == null && data.Distances == null)
         throw new System.IO.InvalidDataException("The given instance specifies neither coordinates nor distances!");
-      if (data.Dimension > DistanceMatrixSizeLimit && (data.DistanceMeasure == TSPDistanceMeasure.Att
-        || data.DistanceMeasure == TSPDistanceMeasure.Manhattan
-        || data.DistanceMeasure == TSPDistanceMeasure.Maximum
-        || data.DistanceMeasure == TSPDistanceMeasure.UpperEuclidean))
+      if (data.Dimension > DistanceMatrixSizeLimit && (data.DistanceMeasure == DistanceMeasure.Att
+        || data.DistanceMeasure == DistanceMeasure.Manhattan
+        || data.DistanceMeasure == DistanceMeasure.Maximum
+        || data.DistanceMeasure == DistanceMeasure.UpperEuclidean))
         throw new System.IO.InvalidDataException("The given instance uses an unsupported distance measure and is too large for using a distance matrix.");
       if (data.Coordinates != null && data.Coordinates.GetLength(1) != 2)
@@ -363 +363 @@
 
       TSPEvaluator evaluator;
-      if (data.DistanceMeasure == TSPDistanceMeasure.Att
-        || data.DistanceMeasure == TSPDistanceMeasure.Manhattan
-        || data.DistanceMeasure == TSPDistanceMeasure.Maximum
-        || data.DistanceMeasure == TSPDistanceMeasure.UpperEuclidean) {
+      if (data.DistanceMeasure == DistanceMeasure.Att
+        || data.DistanceMeasure == DistanceMeasure.Manhattan
+        || data.DistanceMeasure == DistanceMeasure.Maximum
+        || data.DistanceMeasure == DistanceMeasure.UpperEuclidean) {
         evaluator = new TSPDistanceMatrixEvaluator();
         UseDistanceMatrix = new BoolValue(true);
         DistanceMatrix = new DistanceMatrix(data.GetDistanceMatrix());
-      } else if (data.DistanceMeasure == TSPDistanceMeasure.Direct && data.Distances != null) {
+      } else if (data.DistanceMeasure == DistanceMeasure.Direct && data.Distances != null) {
         evaluator = new TSPDistanceMatrixEvaluator();
         UseDistanceMatrix = new BoolValue(true);
@@ -378 +378 @@
         UseDistanceMatrix = new BoolValue(data.Dimension <= DistanceMatrixSizeLimit);
         switch (data.DistanceMeasure) {
-          case TSPDistanceMeasure.Euclidean:
+          case DistanceMeasure.Euclidean:
             evaluator = new TSPEuclideanPathEvaluator();
             break;
-          case TSPDistanceMeasure.RoundedEuclidean:
+          case DistanceMeasure.RoundedEuclidean:
             evaluator = new TSPRoundedEuclideanPathEvaluator();
             break;
-          case TSPDistanceMeasure.Geo:
+          case DistanceMeasure.Geo:
             evaluator = new TSPGeoPathEvaluator();
             break;