Ignore:
Timestamp:
12/14/16 10:16:50 (4 years ago)
Author:
sraggl
Message:

#2701 Merged with trunk to get new version of LinearLinkageEncoding
Improved MoveGenerator

Location:
branches/MemPRAlgorithm/HeuristicLab.Encodings.LinearLinkageEncoding
Files:
2 edited

Legend:

Unmodified
Added
Removed
  • branches/MemPRAlgorithm/HeuristicLab.Encodings.LinearLinkageEncoding

    • Property svn:mergeinfo set to (toggle deleted branches)
      /branches/crossvalidation-2434/HeuristicLab.Encodings.LinearLinkageEncodingmergedeligible
      /stable/HeuristicLab.Encodings.LinearLinkageEncodingmergedeligible
      /trunk/sources/HeuristicLab.Encodings.LinearLinkageEncodingmergedeligible
      /branches/1721-RandomForestPersistence/HeuristicLab.Encodings.LinearLinkageEncoding10321-10322
      /branches/Algorithms.GradientDescent/HeuristicLab.Encodings.LinearLinkageEncoding5516-5520
      /branches/Benchmarking/sources/HeuristicLab.Encodings.LinearLinkageEncoding6917-7005
      /branches/CloningRefactoring/HeuristicLab.Encodings.LinearLinkageEncoding4656-4721
      /branches/CodeEditor/HeuristicLab.Encodings.LinearLinkageEncoding11700-11806
      /branches/DataAnalysis Refactoring/HeuristicLab.Encodings.LinearLinkageEncoding5471-5808
      /branches/DataAnalysis SolutionEnsembles/HeuristicLab.Encodings.LinearLinkageEncoding5815-6180
      /branches/DataAnalysis/HeuristicLab.Encodings.LinearLinkageEncoding4458-4459,​4462,​4464
      /branches/DataPreprocessing/HeuristicLab.Encodings.LinearLinkageEncoding10085-11101
      /branches/GP.Grammar.Editor/HeuristicLab.Encodings.LinearLinkageEncoding6284-6795
      /branches/GP.Symbols (TimeLag, Diff, Integral)/HeuristicLab.Encodings.LinearLinkageEncoding5060
      /branches/HLScript/HeuristicLab.Encodings.LinearLinkageEncoding10331-10358
      /branches/HeuristicLab.DatasetRefactor/sources/HeuristicLab.Encodings.LinearLinkageEncoding11570-12508
      /branches/HeuristicLab.Problems.DataAnalysis.Trading/HeuristicLab.Encodings.LinearLinkageEncoding6123-9799
      /branches/HeuristicLab.Problems.Orienteering/HeuristicLab.Encodings.LinearLinkageEncoding11130-12721
      /branches/HiveStatistics/sources/HeuristicLab.Encodings.LinearLinkageEncoding12440-12877
      /branches/LogResidualEvaluator/HeuristicLab.Encodings.LinearLinkageEncoding10202-10483
      /branches/NET40/sources/HeuristicLab.Encodings.LinearLinkageEncoding5138-5162
      /branches/NSGA-II Changes/HeuristicLab.Encodings.LinearLinkageEncoding12033-12122
      /branches/ParallelEngine/HeuristicLab.Encodings.LinearLinkageEncoding5175-5192
      /branches/ProblemInstancesRegressionAndClassification/HeuristicLab.Encodings.LinearLinkageEncoding7568-7810
      /branches/QAPAlgorithms/HeuristicLab.Encodings.LinearLinkageEncoding6350-6627
      /branches/Restructure trunk solution/HeuristicLab.Encodings.LinearLinkageEncoding6828
      /branches/RuntimeOptimizer/HeuristicLab.Encodings.LinearLinkageEncoding8943-9078
      /branches/ScatterSearch (trunk integration)/HeuristicLab.Encodings.LinearLinkageEncoding7787-8333
      /branches/SlaveShutdown/HeuristicLab.Encodings.LinearLinkageEncoding8944-8956
      /branches/SpectralKernelForGaussianProcesses/HeuristicLab.Encodings.LinearLinkageEncoding10204-10479
      /branches/SuccessProgressAnalysis/HeuristicLab.Encodings.LinearLinkageEncoding5370-5682
      /branches/Trunk/HeuristicLab.Encodings.LinearLinkageEncoding6829-6865
      /branches/UnloadJobs/HeuristicLab.Encodings.LinearLinkageEncoding9168-9215
      /branches/VNS/HeuristicLab.Encodings.LinearLinkageEncoding5594-5752
      /branches/histogram/HeuristicLab.Encodings.LinearLinkageEncoding5959-6341
  • branches/MemPRAlgorithm/HeuristicLab.Encodings.LinearLinkageEncoding/3.3/LinearLinkage.cs

    r14185 r14487  
    3737    private LinearLinkage(LinearLinkage original, Cloner cloner) : base(original, cloner) { }
    3838    public LinearLinkage() { }
    39     public LinearLinkage(int length) : base(length) { }
    40     public LinearLinkage(int[] elements) : base(elements) { }
     39
     40    private LinearLinkage(int length) : base(length) { }
     41    private LinearLinkage(int[] elements) : base(elements) { }
     42
     43    /// <summary>
     44    /// Create a new LinearLinkage object where every element is in a seperate group.
     45    /// </summary>
     46    public static LinearLinkage SingleElementGroups(int length) {
     47      var elements = new int[length];
     48      for (var i = 0; i < length; i++) {
     49        elements[i] = i;
     50      }
     51      return new LinearLinkage(elements);
     52    }
     53
     54    /// <summary>
     55    /// Create a new LinearLinkage object from an int[] in LLE
     56    /// </summary>
     57    /// <remarks>
     58    /// This operation checks if the argument is a well formed LLE
     59    /// and throws an ArgumentException otherwise.
     60    /// </remarks>
     61    /// <param name="lle">The LLE representation</param>
     62    public static LinearLinkage FromForwardLinks(int[] lle) {
     63      if (!Validate(lle)) {
     64        throw new ArgumentException("Array is malformed and does not represent a valid LLE forward encoding.", "elements");
     65      }
     66      return new LinearLinkage(lle);
     67    }
     68
     69    /// <summary>
     70    /// Create a new LinearLinkage object by parsing an LLE-e representation
     71    /// and modifing the underlying array so that it is in LLE representation.
     72    /// </summary>
     73    /// <remarks>
     74    /// This operation runs in O(n) time, but requires additional memory
     75    /// in form of a int[].
     76    /// </remarks>
     77    /// <param name="llee">The LLE-e representation</param>
     78    /// <returns>LinearLinkage</returns>
     79    public static LinearLinkage FromEndLinks(int[] llee) {
     80      var result = new LinearLinkage(llee.Length);
     81      result.SetEndLinks(llee);
     82      return result;
     83    }
     84
     85    /// <summary>
     86    /// Create a new LinearLinkage object by translating
     87    /// an enumeration of groups into the underlying array representation.
     88    /// </summary>
     89    /// <remarks>
     90    /// Throws an ArgumentException when there is an element assigned to
     91    /// multiple groups or elements that are not assigned to any group.
     92    /// </remarks>
     93    /// <param name="grouping">The grouping of the elements, each element must
     94    /// be part of exactly one group.</param>
     95    public static LinearLinkage FromGroups(int length, IEnumerable<IEnumerable<int>> grouping) {
     96      var result = new LinearLinkage(length);
     97      result.SetGroups(grouping);
     98      return result;
     99    }
    41100
    42101    public override IDeepCloneable Clone(Cloner cloner) {
     
    55114    public IEnumerable<List<int>> GetGroups() {
    56115      var len = array.Length;
    57       var remaining = new HashSet<int>(Enumerable.Range(0, len));
     116      var used = new bool[len];
     117      for (var i = 0; i < len; i++) {
     118        if (used[i]) continue;
     119        var curr = i;
     120        var next = array[curr];
     121        var group = new List<int> { curr };
     122        while (next > curr && next < len && !used[next]) {
     123          used[curr] = true;
     124          curr = next;
     125          next = array[next];
     126          group.Add(curr);
     127        }
     128        if (curr != next) throw new ArgumentException("Array is malformed and does not represent a valid LLE forward encoding.");
     129        used[curr] = true;
     130        yield return group;
     131      }
     132      /*
     133      var len = array.Length;
     134      var used = new bool[len];
    58135      // iterate from lowest to highest index
    59136      for (var i = 0; i < len; i++) {
    60         if (!remaining.Contains(i)) continue;
     137        if (used[i]) continue;
    61138        var group = new List<int> { i };
    62         remaining.Remove(i);
     139        used[i] = true;
    63140        var next = array[i];
    64         if (next != i) {
    65           int prev;
    66           do {
    67             group.Add(next);
    68             if (!remaining.Remove(next))
    69               throw new ArgumentException("Array is malformed and does not represent a valid LLE forward encoding.");
    70             prev = next;
    71             next = array[next];
    72           } while (next != prev);
     141        if (next < i || next >= len) {
     142          throw new ArgumentException("Array is malformed and does not represent a valid LLE forward encoding.");
     143        }
     144        while (next != array[next]) {
     145          if (next < 0 || next >= len || used[next]) {
     146            throw new ArgumentException("Array is malformed and does not represent a valid LLE forward encoding.");
     147          }
     148          group.Add(next);
     149          used[next] = true;
     150          next = array[next];
    73151        }
    74152        yield return group;
    75       }
     153      }*/
    76154    }
    77155
     
    151229    public void SetGroups(IEnumerable<IEnumerable<int>> grouping) {
    152230      var len = array.Length;
    153       var remaining = new HashSet<int>(Enumerable.Range(0, len));
     231      var used = new bool[len];
    154232      foreach (var group in grouping) {
    155233        var prev = -1;
    156234        foreach (var g in group.OrderBy(x => x)) {
     235          if (g < prev || g >= len) throw new ArgumentException(string.Format("Element {0} is bigger than {1} or smaller than 0.", g, len - 1), "grouping");
    157236          if (prev >= 0) array[prev] = g;
    158237          prev = g;
    159           if (!remaining.Remove(prev))
     238          if (used[prev]) {
    160239            throw new ArgumentException(string.Format("Element {0} is contained at least twice.", prev), "grouping");
    161         }
    162         if (prev >= 0) array[prev] = prev;
    163       }
    164       if (remaining.Count > 0)
    165         throw new ArgumentException(string.Format("Elements are not assigned a group: {0}", string.Join(", ", remaining)));
     240          }
     241          used[prev] = true;
     242        }
     243        array[prev] = prev;
     244      }
     245      if (!used.All(x => x))
     246        throw new ArgumentException(string.Format("Elements are not assigned a group: {0}", string.Join(", ", used.Select((x, i) => new { x, i }).Where(x => !x.x).Select(x => x.i))));
    166247    }
    167248
     
    175256    /// <returns>True if the encoding is valid.</returns>
    176257    public bool Validate() {
     258      return Validate(array);
     259    }
     260
     261    private static bool Validate(int[] array) {
    177262      var len = array.Length;
    178       var remaining = new HashSet<int>(Enumerable.Range(0, len));
     263      var used = new bool[len];
    179264      for (var i = 0; i < len; i++) {
    180         if (!remaining.Contains(i)) continue;
    181         remaining.Remove(i);
    182         var next = array[i];
    183         if (next == i) continue;
    184         int prev;
    185         do {
    186           if (!remaining.Remove(next)) return false;
    187           prev = next;
     265        if (used[i]) continue;
     266        var curr = i;
     267        var next = array[curr];
     268        while (next > curr && next < len && !used[next]) {
     269          used[curr] = true;
     270          curr = next;
    188271          next = array[next];
    189         } while (next != prev);
    190       }
    191       return remaining.Count == 0;
     272        }
     273        if (curr!=next) return false;
     274        used[curr] = true;
     275      }
     276      return true;
    192277    }
    193278
     
    216301    public void LinearizeTreeStructures() {
    217302      // Step 1: Convert the array into LLE-e
    218       ToLLEeInplace(array);
     303      ToEndLinksInplace(array);
    219304      // Step 2: For all groups linearize the links
    220       FromLLEe(array);
     305      SetEndLinks(array);
    221306    }
    222307
     
    233318    /// </remarks>
    234319    /// <returns>An integer array in LLE-e representation</returns>
    235     public int[] ToLLEe() {
     320    public int[] ToEndLinks() {
    236321      var result = (int[])array.Clone();
    237       ToLLEeInplace(result);
     322      ToEndLinksInplace(result);
    238323      return result;
    239324    }
    240325
    241     private void ToLLEeInplace(int[] a) {
    242       var length = a.Length;
     326    private static void ToEndLinksInplace(int[] array) {
     327      var length = array.Length;
    243328      for (var i = length - 1; i >= 0; i--) {
    244         if (array[i] == i) a[i] = i;
    245         else a[i] = a[a[i]];
     329        var next = array[i];
     330        if (next > i) {
     331          array[i] = array[next];
     332        } else if (next < i) {
     333          throw new ArgumentException("Array is malformed and does not represent a valid LLE encoding.", "array");
     334        }
    246335      }
    247336    }
     
    253342    /// <remarks>
    254343    /// This operation runs in O(n) time, but requires additional memory
    255     /// in form of a dictionary.
     344    /// in form of a int[].
    256345    /// </remarks>
    257346    /// <param name="llee">The LLE-e representation</param>
    258     public void FromLLEe(int[] llee) {
     347    public void SetEndLinks(int[] llee) {
    259348      var length = array.Length;
    260       var groups = new Dictionary<int, int>();
     349      if (length != llee.Length) {
     350        throw new ArgumentException(string.Format("Expected length {0} but length was {1}", length, llee.Length), "llee");
     351      }
     352      // If we are ok with mutating llee we can avoid this clone
     353      var lookup = (int[])llee.Clone();
    261354      for (var i = length - 1; i >= 0; i--) {
    262         if (llee[i] == i) {
    263           array[i] = i;
    264           groups[i] = i;
     355        var end = llee[i];
     356        if (end == i) {
     357          array[i] = end;
     358        } else if (end > i && end < length) {
     359          array[i] = lookup[end];
     360          lookup[end] = i;
    265361        } else {
    266           var g = llee[i];
    267           array[i] = groups[g];
    268           groups[g] = i;
     362          throw new ArgumentException("Array is malformed and does not represent a valid LLE end encoding.", "llee");
    269363        }
    270364      }
Note: See TracChangeset for help on using the changeset viewer.