Index: branches/HeuristicLab.DiversityAnalysis/HeuristicLab.Problems.TravelingSalesman/3.3/Analyzers/TSPPopulationDiversityAnalyzer.cs
===================================================================
--- branches/HeuristicLab.DiversityAnalysis/HeuristicLab.Problems.TravelingSalesman/3.3/Analyzers/TSPPopulationDiversityAnalyzer.cs	(revision 4420)
+++ branches/HeuristicLab.DiversityAnalysis/HeuristicLab.Problems.TravelingSalesman/3.3/Analyzers/TSPPopulationDiversityAnalyzer.cs	(revision 4420)
@@ -0,0 +1,199 @@
+﻿#region License Information
+/* HeuristicLab
+ * Copyright (C) 2002-2010 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 System.Linq;
+using HeuristicLab.Core;
+using HeuristicLab.Data;
+using HeuristicLab.Encodings.PermutationEncoding;
+using HeuristicLab.Operators;
+using HeuristicLab.Optimization;
+using HeuristicLab.Parameters;
+using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
+
+namespace HeuristicLab.Problems.TravelingSalesman {
+  /// <summary>
+  /// An operator for analyzing the diversity of a population of solutions for a Traveling Salesman Problems given in path representation using city coordinates.
+  /// </summary>
+  [Item("TSPPopulationDiversityAnalyzer", "An operator for analyzing the diversity of a population of solutions for a Traveling Salesman Problems given in path representation using city coordinates.")]
+  [StorableClass]
+  public sealed class TSPPopulationDiversityAnalyzer : SingleSuccessorOperator, IAnalyzer {
+
+    // TODO:
+    // - iterations sampling
+    // - decide whether old results shall be stored or disposed
+    // - view
+    // - check results for identical solutions
+
+    public ScopeTreeLookupParameter<Permutation> PermutationParameter {
+      get { return (ScopeTreeLookupParameter<Permutation>)Parameters["Permutation"]; }
+    }
+    public ScopeTreeLookupParameter<DoubleValue> QualityParameter {
+      get { return (ScopeTreeLookupParameter<DoubleValue>)Parameters["Quality"]; }
+    }
+    public LookupParameter<ItemList<DoubleMatrix>> SimilaritiesParameter {
+      get { return (LookupParameter<ItemList<DoubleMatrix>>)Parameters["Similarities"]; }
+    }
+    public LookupParameter<ItemList<DoubleArray>> MaximumSimilaritiesParameter {
+      get { return (LookupParameter<ItemList<DoubleArray>>)Parameters["MaximumSimilarities"]; }
+    }
+    public LookupParameter<ItemList<DoubleValue>> AverageMaximumSimilaritiesParameter {
+      get { return (LookupParameter<ItemList<DoubleValue>>)Parameters["AverageMaximumSimilarities"]; }
+    }
+    public LookupParameter<ItemList<DoubleValue>> AverageSimilaritiesParameter {
+      get { return (LookupParameter<ItemList<DoubleValue>>)Parameters["AverageSimilarities"]; }
+    }
+
+    [NonSerialized]
+    private int[] rxData, ryData;
+    [NonSerialized]
+    private Permutation lastX, lastY;
+
+    public TSPPopulationDiversityAnalyzer()
+      : base() {
+      Parameters.Add(new ScopeTreeLookupParameter<Permutation>("Permutation", "The TSP solutions given in path representation from which the best solution should be analyzed."));
+      Parameters.Add(new ScopeTreeLookupParameter<DoubleValue>("Quality", "The qualities of the TSP solutions which should be analyzed."));
+      Parameters.Add(new LookupParameter<ItemList<DoubleMatrix>>("Similarities", "The similarities of the TSP solutions which should be analyzed."));
+      Parameters.Add(new LookupParameter<ItemList<DoubleArray>>("MaximumSimilarities", "The maximum similarities of the TSP solutions which should be analyzed."));
+      Parameters.Add(new LookupParameter<ItemList<DoubleValue>>("AverageMaximumSimilarities", "The average maximum similarities of the TSP solutions which should be analyzed."));
+      Parameters.Add(new LookupParameter<ItemList<DoubleValue>>("AverageSimilarities", "The average similarities of the TSP solutions which should be analyzed."));
+      rxData = null;
+      ryData = null;
+      lastX = null;
+      lastY = null;
+    }
+
+    public override IOperation Apply() {
+
+      ItemArray<Permutation> permutations = PermutationParameter.ActualValue;
+      ItemArray<DoubleValue> qualities = QualityParameter.ActualValue;
+      Permutation[] permutationsArray = permutations.ToArray();
+      DoubleValue[] qualitiesArray = qualities.ToArray();
+      int cities = permutationsArray.Length;
+      #region sort permutations array
+      for (int i = 0; i < cities; i++) {
+        int minIndex = i;
+        for (int j = i + 1; j < cities; j++) {
+          if (qualitiesArray[j].Value < qualitiesArray[minIndex].Value)
+            minIndex = j;
+        }
+        if (minIndex != i) {
+          Permutation p = permutationsArray[i];
+          permutationsArray[i] = permutationsArray[minIndex];
+          permutationsArray[minIndex] = p;
+          DoubleValue d = qualitiesArray[i];
+          qualitiesArray[i] = qualitiesArray[minIndex];
+          qualitiesArray[minIndex] = d;
+        }
+      }
+      #endregion
+
+      DoubleMatrix similarities = new DoubleMatrix(cities, cities);
+      DoubleArray maxSimilarities = new DoubleArray(cities);
+      double avgSimilarity = 0;
+      int n = 0;
+      for (int i = 0; i < cities; i++) {
+        similarities[i, i] = 1;
+        // for (int j = (i + 1); j < cities; j++) {
+        for (int j = (i); j < cities; j++) {
+          double similarity = CalculateSimilarity(permutationsArray[i], permutationsArray[j]);
+          avgSimilarity += similarity;
+          n++;
+          similarities[i, j] = similarity;
+          similarities[j, i] = similarity;
+          if (maxSimilarities[i] < similarity)
+            maxSimilarities[i] = similarity;
+          if (maxSimilarities[j] < similarity)
+            maxSimilarities[j] = similarity;
+        }
+      }
+      DoubleValue averageMaximumSimilarity = new DoubleValue(maxSimilarities.Average());
+      DoubleValue averageSimilarity = new DoubleValue(avgSimilarity / n);
+
+      if (SimilaritiesParameter.ActualValue == null) {
+        SimilaritiesParameter.ActualValue = new ItemList<DoubleMatrix>();
+        MaximumSimilaritiesParameter.ActualValue = new ItemList<DoubleArray>();
+        AverageMaximumSimilaritiesParameter.ActualValue = new ItemList<DoubleValue>();
+        AverageSimilaritiesParameter.ActualValue = new ItemList<DoubleValue>();
+      }
+      SimilaritiesParameter.ActualValue.Add(similarities);
+      MaximumSimilaritiesParameter.ActualValue.Add(maxSimilarities);
+      AverageMaximumSimilaritiesParameter.ActualValue.Add(averageMaximumSimilarity);
+      AverageSimilaritiesParameter.ActualValue.Add(averageSimilarity);
+
+      return base.Apply();
+    }
+
+    private double CalculateSimilarity(Permutation x, Permutation y) {
+
+      int cities = x.Length;
+      if (rxData == null || rxData.Length != cities) {
+        rxData = new int[cities];
+        ryData = new int[cities];
+      }
+
+      if (x.Length != y.Length) throw new InvalidOperationException("ERROR in " + Name + ": Similarity can only be calculated between instances of an equal number of cities");
+      #region Performance savings when calling the function with at least one parameter identical to the last call
+      if (x == lastX) { // if Solution1 stayed the same
+        if (y != lastY) { // and Solution2 changed
+          for (int i = 0; i < y.Length; i++)
+            ryData[y[i]] = i;
+        }
+      } else {
+        if (y == lastX && x == lastY) { // if Solution1 and Solution2 were reversed the call before
+          int[] h = ryData;
+          ryData = rxData;
+          rxData = h;
+        } else if (y == lastX) { // or if just Solution1 is different now
+          ryData = rxData;
+          rxData = new int[x.Length];
+          for (int i = 0; i < x.Length; i++)
+            rxData[x[i]] = i;
+        } else if (x == lastY) { // or just Solution2 is different now
+          rxData = ryData;
+          ryData = new int[y.Length];
+          for (int i = 0; i < y.Length; i++)
+            ryData[y[i]] = i;
+        } else if (y != lastY) { // or none are the same
+          for (int i = 0; i < x.Length; i++) {
+            rxData[x[i]] = i;
+            ryData[y[i]] = i;
+          }
+        } else { // or just Solution2 is the same
+          for (int i = 0; i < x.Length; i++)
+            rxData[x[i]] = i;
+        }
+      }
+      lastX = x;
+      lastY = y;
+      #endregion
+      int similarEdges = 0;
+      for (int i = 1; i <= x.Length; i++) {
+        if (Math.Abs(ryData[x[(i < x.Length) ? (i) : (0)]] - ryData[x[i - 1]]) == 1
+          || Math.Abs(ryData[x[(i < x.Length) ? (i) : (0)]] - ryData[x[i - 1]]) == x.Length)
+          similarEdges++;
+      }
+      return (double)similarEdges / (double)x.Length;
+
+    }
+
+  }
+}
