Changeset 9444 for branches/HivePerformance/sources/HeuristicLab.Problems.TravelingSalesman/3.3/SimilarityCalculators/TSPSimilarityCalculator.cs

Timestamp:

05/06/13 12:30:18 (11 years ago)

Author:

pfleck

Message:

#2030
Switched Text encoding to Mtom encoding for better performance for binary data.
Merged trunk into branch.

Location:

branches/HivePerformance/sources

Files:

• . (modified) (1 prop)
• HeuristicLab.Problems.TravelingSalesman/3.3/SimilarityCalculators/TSPSimilarityCalculator.cs (modified) (2 diffs)

branches/HivePerformance/sources/HeuristicLab.Problems.TravelingSalesman/3.3/SimilarityCalculators/TSPSimilarityCalculator.cs

@@ -73 +73 @@
 
     private static double CalculateRelativeDirected(Permutation left, Permutation right) {
-      int[] edges = new int[right.Length];
-      for (int i = 0; i < right.Length; i++)
-        edges[right[i]] = right[(i + 1) % right.Length];
+      int[] edgesR = CalculateEdgesVector(right);
+      int[] edgesL = CalculateEdgesVector(left);
 
       double similarity = 0.0;
-      for (int i = 0; i < left.Length; i++)
-        if (left[(i + 1) % left.Length] == edges[left[i]]) similarity++;
+      for (int i = 0; i < left.Length; i++) {
+        if (edgesL[i] == edgesR[i]) similarity++;
+      }
 
       return similarity / left.Length;
@@ -85 +85 @@
 
     private static double CalculateRelativeUndirected(Permutation left, Permutation right) {
-      int[,] edges = new int[right.Length, 2];
-      for (int i = 0; i < right.Length; i++) {
-        edges[right[i], 0] = right[(i + 1) % right.Length];
-        edges[right[i], 1] = right[(i - 1 + right.Length) % right.Length];
-      }
+      int[] edgesR = CalculateEdgesVector(right);
+      int[] edgesL = CalculateEdgesVector(left);
 
       double similarity = 0.0;
       for (int i = 0; i < left.Length; i++) {
-        int targetCity = left[(i + 1) % left.Length];
-        if (targetCity == edges[left[i], 0] || targetCity == edges[left[i], 1])
+        if ((edgesL[i] == edgesR[i]) || (edgesL[edgesR[i]] == i))
           similarity++;
       }
 
       return similarity / left.Length;
+    }
+
+    private static int[] CalculateEdgesVector(Permutation permutation) {
+      // transform path representation into adjacency representation
+      int[] edgesVector = new int[permutation.Length];
+      for (int i = 0; i < permutation.Length - 1; i++)
+        edgesVector[permutation[i]] = permutation[i + 1];
+      edgesVector[permutation[permutation.Length - 1]] = permutation[0];
+      return edgesVector;
     }