source: trunk/sources/HeuristicLab.Encodings.PermutationEncoding/3.3/PermutationEqualityComparer.cs @ 15067

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

#2730:

  • Unified implementation of all equality comparers and similarity calculators in BinaryVector, IntegerVector, RealVector, Permutation, and LinearLinkage encodings
  • Added Euclidean distance-based similarity calculators for real and integer vectors using a transformation function with scaling parameter
File size: 3.9 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2016 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.Collections.Generic;
24using System.Linq;
25using System.Text;
26using HeuristicLab.PluginInfrastructure;
27
28namespace HeuristicLab.Encodings.PermutationEncoding {
29  [NonDiscoverableType]
30  public class PermutationEqualityComparer : EqualityComparer<Permutation> {
31    public override bool Equals(Permutation x, Permutation y) {
32      if (x == null && y == null) return true;
33      if (x == null || y == null) return false;
34      if (ReferenceEquals(x, y)) return true;
35      if (x.Length != y.Length) return false;
36      if (x.PermutationType != y.PermutationType) return false;
37      switch (x.PermutationType) {
38        case PermutationTypes.Absolute:
39          return EqualsAbsolute(x, y);
40        case PermutationTypes.RelativeDirected:
41          return EqualsRelative(x, y, true);
42        case PermutationTypes.RelativeUndirected:
43          return EqualsRelative(x, y, false);
44        default:
45          throw new InvalidOperationException("unknown permutation type");
46      }
47    }
48
49    private bool EqualsAbsolute(Permutation x, Permutation y) {
50      return x.SequenceEqual(y);
51    }
52
53    private bool EqualsRelative(Permutation x, Permutation y, bool directed) {
54      int[] edgesX = CalculateEdgesVector(x);
55      int[] edgesY = CalculateEdgesVector(y);
56      for (int i = 0; i < x.Length; i++)
57        if ((edgesX[i] != edgesY[i]) && (directed || edgesX[edgesY[i]] != i))
58          return false;
59      return true;
60    }
61
62    private int[] CalculateEdgesVector(Permutation permutation) {
63      // transform path representation into adjacency representation
64      int[] edgesVector = new int[permutation.Length];
65      for (int i = 0; i < permutation.Length - 1; i++)
66        edgesVector[permutation[i]] = permutation[i + 1];
67      edgesVector[permutation[permutation.Length - 1]] = permutation[0];
68      return edgesVector;
69    }
70
71    public override int GetHashCode(Permutation obj) {
72      if (obj == null) throw new ArgumentNullException("obj", "PermutationEqualityComparer: Cannot compute hash value of null.");
73      return GenerateHashString(obj).GetHashCode();
74    }
75
76    private string GenerateHashString(Permutation p) {
77      StringBuilder sb = new StringBuilder();
78      if (p.PermutationType == PermutationTypes.Absolute) {
79        for (int i = 0; i < p.Length; i++)
80          sb.Append(p[i].ToString() + ";");
81      } else {
82        int i = 0;
83        while (p[i] != 0) i++; // always start at element 0
84        if (p.PermutationType == PermutationTypes.RelativeDirected) {
85          for (int j = 0; j < p.Length; j++)
86            sb.Append(p.GetCircular(i + j).ToString() + ";");
87        } else {
88          bool goLeft = p.GetCircular(i - 1) < p.GetCircular(i + 1); // go in direction of the lowest edge so that the total inversion and its original return the same hash code
89          for (int j = 0; j < p.Length; j++) {
90            if (goLeft) sb.Append(p.GetCircular(i - j).ToString() + ";");
91            else sb.Append(p.GetCircular(i + j).ToString() + ";");
92          }
93        }
94      }
95      return sb.ToString();
96    }
97  }
98}
Note: See TracBrowser for help on using the repository browser.