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  using HEAL.Fossil;


28 


29  namespace HeuristicLab.Encodings.PermutationEncoding {


30  [NonDiscoverableType]


31  [StorableType("9e0bdbda0d764032bc69f5acbbfd5d37")]


32  public class PermutationEqualityComparer : EqualityComparer<Permutation> {


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


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


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


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


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


38  switch (x.PermutationType) {


39  case PermutationTypes.Absolute:


40  return EqualsAbsolute(x, y);


41  case PermutationTypes.RelativeDirected:


42  return EqualsRelative(x, y, true);


43  case PermutationTypes.RelativeUndirected:


44  return EqualsRelative(x, y, false);


45  default:


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


47  }


48  }


49 


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


51  return x.SequenceEqual(y);


52  }


53 


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


55  int[] edgesX = CalculateEdgesVector(x);


56  int[] edgesY = CalculateEdgesVector(y);


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


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


59  return false;


60  return true;


61  }


62 


63  private int[] CalculateEdgesVector(Permutation permutation) {


64  // transform path representation into adjacency representation


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


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


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


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


69  return edgesVector;


70  }


71 


72  public override int GetHashCode(Permutation obj) {


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


74  return GenerateHashString(obj).GetHashCode();


75  }


76 


77  private string GenerateHashString(Permutation p) {


78  StringBuilder sb = new StringBuilder();


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


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


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


82  } else {


83  int i = 0;


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


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


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


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


88  } else {


89  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


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


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


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


93  }


94  }


95  }


96  return sb.ToString();


97  }


98  }


99  }

