1  #region License Information


2  /* HeuristicLab


3  * Copyright (C) 20022019 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 


22  using System;


23  using System.Collections.Generic;


24  using System.Linq;


25  using System.Text;


26  using HeuristicLab.PluginInfrastructure;


27 


28  namespace HeuristicLab.Encodings.PermutationEncoding {


29  [NonDiscoverableType]


30  public class PermutationEqualityComparer : EqualityComparer<Permutation> {


31  public override bool Equals(Permutation x, Permutation y) {


32  if (ReferenceEquals(x, y)) return true;


33  if (x == null  y == null) return false;


34  if (x.Length != y.Length) return false;


35  if (x.PermutationType != y.PermutationType) return false;


36  switch (x.PermutationType) {


37  case PermutationTypes.Absolute:


38  return EqualsAbsolute(x, y);


39  case PermutationTypes.RelativeDirected:


40  return EqualsRelative(x, y, true);


41  case PermutationTypes.RelativeUndirected:


42  return EqualsRelative(x, y, false);


43  default:


44  throw new InvalidOperationException("unknown permutation type");


45  }


46  }


47 


48  private bool EqualsAbsolute(Permutation x, Permutation y) {


49  return x.SequenceEqual(y);


50  }


51 


52  private bool EqualsRelative(Permutation x, Permutation y, bool directed) {


53  int[] edgesX = CalculateEdgesVector(x);


54  int[] edgesY = CalculateEdgesVector(y);


55  for (int i = 0; i < x.Length; i++)


56  if ((edgesX[i] != edgesY[i]) && (directed  edgesX[edgesY[i]] != i))


57  return false;


58  return true;


59  }


60 


61  private int[] CalculateEdgesVector(Permutation permutation) {


62  // transform path representation into adjacency representation


63  int[] edgesVector = new int[permutation.Length];


64  for (int i = 0; i < permutation.Length  1; i++)


65  edgesVector[permutation[i]] = permutation[i + 1];


66  edgesVector[permutation[permutation.Length  1]] = permutation[0];


67  return edgesVector;


68  }


69 


70  public override int GetHashCode(Permutation obj) {


71  if (obj == null) throw new ArgumentNullException("obj", "PermutationEqualityComparer: Cannot compute hash value of null.");


72  return GenerateHashString(obj).GetHashCode();


73  }


74 


75  private string GenerateHashString(Permutation p) {


76  StringBuilder sb = new StringBuilder();


77  if (p.PermutationType == PermutationTypes.Absolute) {


78  for (int i = 0; i < p.Length; i++)


79  sb.Append(p[i].ToString() + ";");


80  } else {


81  int i = 0;


82  while (p[i] != 0) i++; // always start at element 0


83  if (p.PermutationType == PermutationTypes.RelativeDirected) {


84  for (int j = 0; j < p.Length; j++)


85  sb.Append(p.GetCircular(i + j).ToString() + ";");


86  } else {


87  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


88  for (int j = 0; j < p.Length; j++) {


89  if (goLeft) sb.Append(p.GetCircular(i  j).ToString() + ";");


90  else sb.Append(p.GetCircular(i + j).ToString() + ";");


91  }


92  }


93  }


94  return sb.ToString();


95  }


96  }


97  }

