source: branches/HeuristicLab.Analysis.AlgorithmBehavior/AlgorithmBehaviorUnitTests/DistanceMatrixToPointsTest.cs @ 10573

#region License Information
/* HeuristicLab
 * Copyright (C) 2002-2013 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
 *
 * This file is part of HeuristicLab.
 *
 * HeuristicLab is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * HeuristicLab is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
 */
#endregion

using System;
using HeuristicLab.Analysis.AlgorithmBehavior.Analyzers;
using HeuristicLab.Common;
using HeuristicLab.Encodings.PermutationEncoding;
using HeuristicLab.Problems.TravelingSalesman;
using Microsoft.VisualStudio.TestTools.UnitTesting;

namespace AlgorithmBehaviorUnitTests {
  [TestClass]
  public class DistanceMatrixToPointsTest {
    [TestMethod]
    public void TestMetricMDSStatic() {
      int nrOfPoints = 3;
      int dim = 2;
      double[][] orgPoints = new double[nrOfPoints][];
      double[][] orgDm = new double[nrOfPoints][];
      double[][] newDm = new double[nrOfPoints][];
      double[][] newPoints = null;

      AllocArray(orgPoints, dim);
      AllocArray(orgDm, nrOfPoints);
      AllocArray(newDm, nrOfPoints);
      StaticPoints(orgPoints);
      CalculateDistanceMatrix(orgDm, orgPoints);

      newPoints = DistanceMatrixToPoints.MetricMDS(orgDm, dim, true);

      CalculateDistanceMatrix(newDm, newPoints);
      Console.WriteLine("orgDm:");
      PrintDM(orgDm);
      Console.WriteLine("newDm:");
      PrintDM(newDm);

      for (int i = 0; i < orgDm.Length; i++) {
        for (int j = 0; j < orgDm.Length; j++) {
          double diff = orgDm[i][j] - newDm[i][j];
          Assert.IsTrue(diff.IsAlmost(0.0));
        }
      }
    }

    [TestMethod]
    public void TestMetricMDSRandom() {
      int nrOfPoints = 30;
      int dim = 10;
      double[][] orgPoints = new double[nrOfPoints][];
      double[][] orgDm = new double[nrOfPoints][];
      double[][] newDm = new double[nrOfPoints][];
      double[][] newPoints = null;

      AllocArray(orgPoints, dim);
      AllocArray(orgDm, nrOfPoints);
      AllocArray(newDm, nrOfPoints);
      SamplePoints(orgPoints);
      CalculateDistanceMatrix(orgDm, orgPoints);

      newPoints = DistanceMatrixToPoints.MetricMDS(orgDm, dim);

      CalculateDistanceMatrix(newDm, newPoints);
      Console.WriteLine("orgDm:");
      PrintDM(orgDm);
      Console.WriteLine("newDm:");
      PrintDM(newDm);

      for (int i = 0; i < orgDm.Length; i++) {
        for (int j = 0; j < orgDm.Length; j++) {
          double diff = orgDm[i][j] - newDm[i][j];
          Assert.IsTrue(diff.IsAlmost(0.0));
        }
      }
    }

    [TestMethod]
    public void TestDistanceMatrixConversionStatic() {
      int nrOfPoints = 3;
      int dim = 2;
      double[][] orgPoints = new double[nrOfPoints][];
      double[][] orgDm = new double[nrOfPoints][];
      double[][] newDm = new double[nrOfPoints][];
      double[][] newPoints = null;

      AllocArray(orgPoints, dim);
      AllocArray(orgDm, nrOfPoints);
      AllocArray(newDm, nrOfPoints);
      StaticPoints(orgPoints);
      CalculateDistanceMatrix(orgDm, orgPoints);

      newPoints = DistanceMatrixToPoints.ConvertDistanceMatrixToPoints(orgDm);

      CalculateDistanceMatrix(newDm, newPoints);
      Console.WriteLine("orgDm:");
      PrintDM(orgDm);
      Console.WriteLine("newDm:");
      PrintDM(newDm);

      for (int i = 0; i < orgDm.Length; i++) {
        for (int j = 0; j < orgDm.Length; j++) {
          double diff = orgDm[i][j] - newDm[i][j];
          Assert.IsTrue(diff.IsAlmost(0.0));
        }
      }
    }

    [TestMethod]
    public void TestDistanceMatrixConversionDynamic() {
      int nrOfPoints = 30;
      int dim = 20;
      double[][] orgPoints = new double[nrOfPoints][];
      double[][] orgDm = new double[nrOfPoints][];
      double[][] newDm = new double[nrOfPoints][];
      double[][] newPoints = null;

      AllocArray(orgPoints, dim);
      AllocArray(orgDm, nrOfPoints);
      AllocArray(newDm, nrOfPoints);
      SamplePoints(orgPoints);
      CalculateDistanceMatrix(orgDm, orgPoints);

      newPoints = DistanceMatrixToPoints.ConvertDistanceMatrixToPoints(orgDm, dim);

      CalculateDistanceMatrix(newDm, newPoints);
      Console.WriteLine("orgDm:");
      PrintDM(orgDm);
      Console.WriteLine("newDm:");
      PrintDM(newDm);

      for (int i = 0; i < orgDm.Length; i++) {
        for (int j = 0; j < orgDm.Length; j++) {
          double diff = orgDm[i][j] - newDm[i][j];
          Assert.IsTrue(diff.IsAlmost(0.0));
        }
      }
    }

    [TestMethod]
    public void TestMetricMDSForPermutations() {
      int nrOfPoints = 30;
      int dim = 5;
      Permutation[] orgPoints = new Permutation[nrOfPoints];
      double[][] orgDm;
      double[][] newDm = new double[nrOfPoints][];
      double[][] newPoints = null;

      AllocArray(newDm, nrOfPoints);

      SamplePermutations(orgPoints, dim);
      orgDm = CalculateDistanceMatrixFromPermutations(orgPoints);

      newPoints = DistanceMatrixToPoints.MetricMDS(orgDm, dim);

      CalculateDistanceMatrix(newDm, newPoints);
      Console.WriteLine("orgDm:");
      PrintDM(orgDm);
      Console.WriteLine("newDm:");
      PrintDM(newDm);

      for (int i = 0; i < orgDm.Length; i++) {
        for (int j = 0; j < orgDm.Length; j++) {
          double diff = Math.Abs(orgDm[i][j] - newDm[i][j]);
          if (diff < 0.0000001) diff = 0.0;
          Assert.IsTrue(diff.IsAlmost(0.0));
        }
      }
    }

    [TestMethod]
    public void TestMetricMDSForPermutationsStatic() {
      int nrOfPoints = 10;
      int dim = 5;

      double[][] orgDm = StaticPermutationDM();
      double[][] newDm = new double[nrOfPoints][];
      double[][] newPoints = null;

      AllocArray(newDm, nrOfPoints);

      newPoints = DistanceMatrixToPoints.MetricMDS(orgDm, dim, false);

      CalculateDistanceMatrix(newDm, newPoints);
      Console.WriteLine("orgDm:");
      PrintDM(orgDm);
      Console.WriteLine("newDm:");
      PrintDM(newDm);

      double[][] resultDMFromR = StaticPermutationDMResult();

      for (int i = 0; i < orgDm.Length; i++) {
        for (int j = 0; j < orgDm.Length; j++) {
          double diff = Math.Abs(resultDMFromR[i][j] - Math.Round(newDm[i][j], 7));
          if (diff < 0.000001) diff = 0.0;
          Assert.IsTrue(diff.IsAlmost(0.0));

          diff = Math.Abs(orgDm[i][j] - newDm[i][j]);
          if (diff < 0.00000001) diff = 0.0;
          Assert.IsTrue(diff.IsAlmost(0.0));
        }
      }
    }

    [TestMethod]
    public void TestMetricMDSForSmallDistances() {
      int nrOfPoints = 4;
      int dim = 2;
      double[][] orgPoints = new double[nrOfPoints][];
      double[][] orgDm = new double[nrOfPoints][];
      double[][] newDm = new double[nrOfPoints][];
      double[][] newPoints = null;

      AllocArray(orgPoints, dim);
      AllocArray(orgDm, nrOfPoints);
      AllocArray(newDm, nrOfPoints);
      SmallDiffStaticPoints(orgPoints);
      CalculateDistanceMatrix(orgDm, orgPoints);

      Console.WriteLine("orgDm:");
      PrintDM(orgDm);

      newPoints = DistanceMatrixToPoints.MetricMDS(orgDm, dim, false);

      CalculateDistanceMatrix(newDm, newPoints);
      Console.WriteLine("newDm:");
      PrintDM(newDm);

      for (int i = 0; i < orgDm.Length; i++) {
        for (int j = 0; j < orgDm.Length; j++) {
          double diff = Math.Abs(orgDm[i][j] - newDm[i][j]);
          if (diff < 0.00000001) diff = 0.0;
          Assert.IsTrue(diff.IsAlmost(0.0));
        }
      }
    }

    private static void SmallDiffStaticPoints(double[][] points) {
      points[0][0] = 1;
      points[0][1] = 1;

      points[1][0] = 1.03;
      points[1][1] = 1.2;

      points[2][0] = 1.05;
      points[2][1] = 1.01;

      points[3][0] = 1.5;
      points[3][1] = 1.1;
    }

    private static double[][] StaticPermutationDM() {
      double[][] dm = new double[10][];
      AllocArray(dm, 10);

      dm[0] = new[]
      {
        0, 1.09544511501033, 1.09544511501033, 0.894427190999916, 0.894427190999916, 1.09544511501033, 0.894427190999916,
        1.09544511501033, 0.894427190999916, 0.894427190999916
      };
      dm[1] = new[]
      {
        1.09544511501033, 0, 1.09544511501033, 1.4142135623731, 0.894427190999916, 1.09544511501033, 0.894427190999916,
        1.09544511501033, 0.894427190999916, 0.894427190999916
      };
      dm[2] = new[]
      {
        1.09544511501033, 1.09544511501033, 0, 0.894427190999916, 0.894427190999916, 1.09544511501033, 0.894427190999916,
        1.09544511501033, 0.894427190999916, 0.894427190999916
      };
      dm[3] = new[]
      {
        0.894427190999916, 1.4142135623731, 0.894427190999916, 0, 1.09544511501033, 0.894427190999916, 1.09544511501033,
        0.894427190999916, 1.09544511501033, 1.09544511501033
      };
      dm[4] = new[]
      {
        0.894427190999916, 0.894427190999916, 0.894427190999916, 1.09544511501033, 0, 0.894427190999916, 0,
        0.894427190999916, 1.09544511501033, 1.09544511501033
      };
      dm[5] = new[]
      {
        1.09544511501033, 1.09544511501033, 1.09544511501033, 0.894427190999916, 0.894427190999916, 0, 0.894427190999916,
        1.09544511501033, 0.894427190999916, 1.4142135623731
      };
      dm[6] = new[]
      {
        0.894427190999916, 0.894427190999916, 0.894427190999916, 1.09544511501033, 0, 0.894427190999916, 0,
        0.894427190999916, 1.09544511501033, 1.09544511501033
      };
      dm[7] = new[]
      {
        1.09544511501033, 1.09544511501033, 1.09544511501033, 0.894427190999916, 0.894427190999916, 1.09544511501033,
        0.894427190999916, 0, 1.4142135623731, 0.894427190999916
      };
      dm[8] = new[]
      {
        0.894427190999916, 0.894427190999916, 0.894427190999916, 1.09544511501033, 1.09544511501033, 0.894427190999916,
        1.09544511501033, 1.4142135623731, 0, 1.09544511501033
      };
      dm[9] = new[]
      {
        0.894427190999916, 0.894427190999916, 0.894427190999916, 1.09544511501033, 1.09544511501033, 1.4142135623731,
        1.09544511501033, 0.894427190999916, 1.09544511501033, 0
      };

      return dm;
    }

    private static double[][] StaticPermutationDMResult() {
      double[][] dm = new double[10][];
      AllocArray(dm, 10);

      dm[0] = new[]
      {
        0.0000000,1.0954451,1.0954451,0.8944272,8.944272e-01,1.0954451,8.944272e-01,1.0954451,0.8944272,0.8944272
      };
      dm[1] = new[]
      {
        1.0954451,0.0000000,1.0954451,1.4142136,8.944272e-01,1.0954451,8.944272e-01,1.0954451,0.8944272,0.8944272        
      };
      dm[2] = new[]
      {
        1.0954451,1.0954451,0.0000000,0.8944272,8.944272e-01,1.0954451,8.944272e-01,1.0954451,0.8944272,0.8944272
      };
      dm[3] = new[]
      {
        0.8944272,1.4142136,0.8944272,0.0000000,1.095445e+00,0.8944272,1.095445e+00,0.8944272,1.0954451,1.0954451        
      };
      dm[4] = new[]
      {
        0.8944272,0.8944272,0.8944272,1.0954451,0.000000e+00,0.8944272,4.331115e-16,0.8944272,1.0954451,1.0954451
      };
      dm[5] = new[]
      {
        1.0954451,1.0954451,1.0954451,0.8944272,8.944272e-01,0.0000000,8.944272e-01,1.0954451,0.8944272,1.4142136  
      };
      dm[6] = new[]
      {
        0.8944272,0.8944272,0.8944272,1.0954451,4.331115e-16,0.8944272,0.000000e+00,0.8944272,1.0954451,1.0954451        
      };
      dm[7] = new[]
      {
        1.0954451,1.0954451,1.0954451,0.8944272,8.944272e-01,1.0954451,8.944272e-01,0.0000000,1.4142136,0.8944272
      };
      dm[8] = new[]
      {
        0.8944272,0.8944272,0.8944272,1.0954451,1.095445e+00,0.8944272,1.095445e+00,1.4142136,0.0000000,1.0954451       
      };
      dm[9] = new[]
      {
        0.8944272,0.8944272,0.8944272,1.0954451,1.095445e+00,1.4142136,1.095445e+00,0.8944272,1.0954451,0.0000000       
      };

      return dm;
    }

    private static void PrintDM(double[][] dm) {
      for (int i = 0; i < dm.Length; i++) {
        for (int j = 0; j < dm.Length; j++) {
          Console.Write(dm[i][j] + " ");
        }
        Console.WriteLine();
      }
    }

    private static void SamplePoints(double[][] points) {
      Random rand = new Random();

      for (int i = 0; i < points.Length; i++) {
        for (int j = 0; j < points[i].Length; j++) {
          points[i][j] = rand.NextDouble() * 100;
        }
      }
    }

    private static void SamplePermutations(Permutation[] points, int dim) {
      var rand = new HeuristicLab.Random.FastRandom();

      for (int i = 0; i < points.Length; i++) {
        var p = new Permutation(PermutationTypes.RelativeUndirected, dim, rand);
        points[i] = p;
      }
    }

    private static void StaticPoints(double[][] points) {
      points[0][0] = 2;
      points[0][1] = 1;

      points[1][0] = 5;
      points[1][1] = 5;

      points[2][0] = 3;
      points[2][1] = 7;
    }

    private static void CalculateDistanceMatrix(double[][] dm, double[][] points) {
      for (int i = 0; i < points.Length; i++) {
        for (int j = 0; j < points.Length; j++) {
          dm[i][j] = points[i].EuclideanDistance(points[j]);
        }
      }
    }

    private static double[][] CalculateDistanceMatrixFromPermutations(Permutation[] points) {
      double[][] tmpDm = new double[points.Length][];
      AllocArray(tmpDm, points.Length);

      for (int i = 0; i < points.Length; i++) {
        for (int j = 0; j < points.Length; j++) {
          double diversity = TSPSimilarityCalculator.CalculateSimilarity(points[i], points[j]);
          tmpDm[i][j] = diversity;
        }
      }

      return DistanceMatrixToPoints.TransformToDistances(tmpDm);
    }

    private static void AllocArray(double[][] arr, int size) {
      for (int i = 0; i < arr.Length; i++) {
        arr[i] = new double[size];
      }
    }
  }
}