1  using System;


2  using System.Collections.Generic;


3  using System.Linq;


4  using System.Text;


5  using HeuristicLab.Core;


6  using HeuristicLab.Common.Resources;


7  using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;


8  using HeuristicLab.Common;


9  using HeuristicLab.Encodings.BinaryVectorEncoding;


10  using HeuristicLab.Encodings.PermutationEncoding;


11  using System.Drawing;


12 


13  namespace HeuristicLab.Analysis.FitnessLandscape.DistanceCalculators {


14 


15  [Item("PermutationDistanceCalculator", "Calculates the distance of two permutations")]


16  [StorableClass]


17  public class PermutationDistanceCalculator : NamedItem, IItemDistanceCalculator {


18 


19  #region Properties


20 


21  public override bool CanChangeName { get { return false; } }


22  public override bool CanChangeDescription { get { return false; } }


23  public static new Image StaticItemImage { get { return VSImageLibrary.Function; } }


24 


25  #endregion


26 


27  #region Construction & Cloning


28 


29  [StorableConstructor]


30  protected PermutationDistanceCalculator(bool deserializing) : base(deserializing) { }


31 


32  protected PermutationDistanceCalculator(PermutationDistanceCalculator original, Cloner cloner)


33  : base(original, cloner) {


34  }


35 


36  public PermutationDistanceCalculator() {


37  name = ItemName;


38  description = ItemDescription;


39  }


40 


41  public override IDeepCloneable Clone(Cloner cloner) {


42  return new PermutationDistanceCalculator(this, cloner);


43  }


44 


45  #endregion


46 


47  #region IItemDistanceCalculator Members


48 


49  public Type ItemType {


50  get { return typeof(Permutation); }


51  }


52 


53  public double Distance(IItem x, IItem y) {


54  Permutation a = (Permutation)x;


55  Permutation b = (Permutation)y;


56  if (a.PermutationType != b.PermutationType)


57  throw new InvalidOperationException("Cannot compare two permutations of different type");


58  if (a.Length != b.Length)


59  throw new InvalidOperationException("Cannot compare vectors of different lengths");


60  switch (a.PermutationType) {


61  case PermutationTypes.Absolute: return AbsoluteDistance(a, b);


62  case PermutationTypes.RelativeDirected: return RelativeDistance(a, b);


63  case PermutationTypes.RelativeUndirected: return RelativeDistance(a, b);


64  default: throw new NotImplementedException("Unknown permutation type " + a.PermutationType);


65  }


66  }


67 


68  private double AbsoluteDistance(Permutation a, Permutation b) {


69  int mismatches = 0;


70  for (int i = 0; i<a.Length; i++) {


71  if (a[i] != b[i])


72  mismatches++;


73  }


74  return (double)mismatches;


75  }


76 


77  private double RelativeDistance(Permutation a, Permutation b) {


78  HashSet<Point> edges = new HashSet<Point>();


79  for (int i = 0; i < a.Length; i++)


80  edges.Add(GetEdge(a, i));


81  int nCommonEdges = 0;


82  for (int i = 0; i < b.Length; i++) {


83  if (edges.Contains(GetEdge(b, i)))


84  nCommonEdges++;


85  }


86  return Math.Max(a.Length, b.Length)  nCommonEdges;


87  }


88 


89  private static Point GetEdge(Permutation a, int index) {


90  int start = a[index];


91  int end = a[(index + 1)%a.Length];


92  switch (a.PermutationType) {


93  case PermutationTypes.RelativeDirected: return new Point(start, end);


94  case PermutationTypes.RelativeUndirected: return new Point(Math.Min(start, end), Math.Max(start, end));


95  default: throw new ArgumentException("cannot derive edge from nonrelative permutation type");


96  }


97  }


98 


99  #endregion


100  }


101  }

