Changeset 14487


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

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

Location:
branches/MemPRAlgorithm
Files:
21 edited
2 copied

Legend:

Unmodified
Added
Removed
  • branches/MemPRAlgorithm/HeuristicLab 3.3.sln

    r14471 r14487  
    8080    {3B90F866-70F8-43EF-A541-51819D255B7B} = {3B90F866-70F8-43EF-A541-51819D255B7B}
    8181    {07486E68-1517-4B9D-A58D-A38E99AE71AB} = {07486E68-1517-4B9D-A58D-A38E99AE71AB}
    82     {BE698769-975A-429E-828C-72BB2B6182C8} = {BE698769-975A-429E-828C-72BB2B6182C8}
    8382    {4AE3FC69-C575-42D2-BC46-0FAD5850EFC5} = {4AE3FC69-C575-42D2-BC46-0FAD5850EFC5}
    8483    {56F9106A-079F-4C61-92F6-86A84C2D84B7} = {56F9106A-079F-4C61-92F6-86A84C2D84B7}
     
    423422Project("{FAE04EC0-301F-11D3-BF4B-00C04F79EFBC}") = "HeuristicLab.Algorithms.CMAEvolutionStrategy-3.4", "HeuristicLab.Algorithms.CMAEvolutionStrategy\3.4\HeuristicLab.Algorithms.CMAEvolutionStrategy-3.4.csproj", "{291010E4-2F4E-4D29-A795-753CFF293FDB}"
    424423EndProject
    425 Project("{FAE04EC0-301F-11D3-BF4B-00C04F79EFBC}") = "HeuristicLab.Encodings.LinearLinkageEncoding-3.3", "HeuristicLab.Encodings.LinearLinkageEncoding\3.3\HeuristicLab.Encodings.LinearLinkageEncoding-3.3.csproj", "{BE698769-975A-429E-828C-72BB2B6182C8}"
    426 EndProject
    427424Project("{FAE04EC0-301F-11D3-BF4B-00C04F79EFBC}") = "HeuristicLab.Problems.Orienteering-3.3", "HeuristicLab.Problems.Orienteering\3.3\HeuristicLab.Problems.Orienteering-3.3.csproj", "{D1EFA4CC-909F-41D5-9C1F-C3AF1957A372}"
    428425EndProject
     
    458455EndProject
    459456Project("{FAE04EC0-301F-11D3-BF4B-00C04F79EFBC}") = "HeuristicLab.Problems.Instances.DIMACS-3.3", "HeuristicLab.Problems.Instances.DIMACS\3.3\HeuristicLab.Problems.Instances.DIMACS-3.3.csproj", "{9943FF23-8619-459C-B84A-E7FBDCBA04E6}"
     457EndProject
     458Project("{FAE04EC0-301F-11D3-BF4B-00C04F79EFBC}") = "HeuristicLab.Encodings.LinearLinkageEncoding-3.4", "HeuristicLab.Encodings.LinearLinkageEncoding\3.3\HeuristicLab.Encodings.LinearLinkageEncoding-3.4.csproj", "{166507C9-EF26-4370-BB80-699742A29D4F}"
    460459EndProject
    461460Global
     
    20172016    {291010E4-2F4E-4D29-A795-753CFF293FDB}.Release|x86.ActiveCfg = Release|x86
    20182017    {291010E4-2F4E-4D29-A795-753CFF293FDB}.Release|x86.Build.0 = Release|x86
    2019     {BE698769-975A-429E-828C-72BB2B6182C8}.Debug|Any CPU.ActiveCfg = Debug|Any CPU
    2020     {BE698769-975A-429E-828C-72BB2B6182C8}.Debug|Any CPU.Build.0 = Debug|Any CPU
    2021     {BE698769-975A-429E-828C-72BB2B6182C8}.Debug|x64.ActiveCfg = Debug|x64
    2022     {BE698769-975A-429E-828C-72BB2B6182C8}.Debug|x64.Build.0 = Debug|x64
    2023     {BE698769-975A-429E-828C-72BB2B6182C8}.Debug|x86.ActiveCfg = Debug|x86
    2024     {BE698769-975A-429E-828C-72BB2B6182C8}.Debug|x86.Build.0 = Debug|x86
    2025     {BE698769-975A-429E-828C-72BB2B6182C8}.Release|Any CPU.ActiveCfg = Release|Any CPU
    2026     {BE698769-975A-429E-828C-72BB2B6182C8}.Release|Any CPU.Build.0 = Release|Any CPU
    2027     {BE698769-975A-429E-828C-72BB2B6182C8}.Release|x64.ActiveCfg = Release|x64
    2028     {BE698769-975A-429E-828C-72BB2B6182C8}.Release|x64.Build.0 = Release|x64
    2029     {BE698769-975A-429E-828C-72BB2B6182C8}.Release|x86.ActiveCfg = Release|x86
    2030     {BE698769-975A-429E-828C-72BB2B6182C8}.Release|x86.Build.0 = Release|x86
    20312018    {D1EFA4CC-909F-41D5-9C1F-C3AF1957A372}.Debug|Any CPU.ActiveCfg = Debug|Any CPU
    20322019    {D1EFA4CC-909F-41D5-9C1F-C3AF1957A372}.Debug|Any CPU.Build.0 = Debug|Any CPU
     
    22332220    {9943FF23-8619-459C-B84A-E7FBDCBA04E6}.Release|x86.ActiveCfg = Release|Any CPU
    22342221    {9943FF23-8619-459C-B84A-E7FBDCBA04E6}.Release|x86.Build.0 = Release|Any CPU
     2222    {166507C9-EF26-4370-BB80-699742A29D4F}.Debug|Any CPU.ActiveCfg = Debug|Any CPU
     2223    {166507C9-EF26-4370-BB80-699742A29D4F}.Debug|Any CPU.Build.0 = Debug|Any CPU
     2224    {166507C9-EF26-4370-BB80-699742A29D4F}.Debug|x64.ActiveCfg = Debug|x64
     2225    {166507C9-EF26-4370-BB80-699742A29D4F}.Debug|x64.Build.0 = Debug|x64
     2226    {166507C9-EF26-4370-BB80-699742A29D4F}.Debug|x86.ActiveCfg = Debug|x86
     2227    {166507C9-EF26-4370-BB80-699742A29D4F}.Debug|x86.Build.0 = Debug|x86
     2228    {166507C9-EF26-4370-BB80-699742A29D4F}.Release|Any CPU.ActiveCfg = Release|Any CPU
     2229    {166507C9-EF26-4370-BB80-699742A29D4F}.Release|Any CPU.Build.0 = Release|Any CPU
     2230    {166507C9-EF26-4370-BB80-699742A29D4F}.Release|x64.ActiveCfg = Release|x64
     2231    {166507C9-EF26-4370-BB80-699742A29D4F}.Release|x64.Build.0 = Release|x64
     2232    {166507C9-EF26-4370-BB80-699742A29D4F}.Release|x86.ActiveCfg = Release|x86
     2233    {166507C9-EF26-4370-BB80-699742A29D4F}.Release|x86.Build.0 = Release|x86
    22352234  EndGlobalSection
    22362235  GlobalSection(SolutionProperties) = preSolution
  • branches/MemPRAlgorithm/HeuristicLab.Algorithms.MemPR/3.3/HeuristicLab.Algorithms.MemPR-3.3.csproj

    r14466 r14487  
    162162      <Private>False</Private>
    163163    </ProjectReference>
    164     <ProjectReference Include="..\..\HeuristicLab.Encodings.LinearLinkageEncoding\3.3\HeuristicLab.Encodings.LinearLinkageEncoding-3.3.csproj">
    165       <Project>{BE698769-975A-429E-828C-72BB2B6182C8}</Project>
    166       <Name>HeuristicLab.Encodings.LinearLinkageEncoding-3.3</Name>
    167       <Private>False</Private>
     164    <ProjectReference Include="..\..\HeuristicLab.Encodings.LinearLinkageEncoding\3.3\HeuristicLab.Encodings.LinearLinkageEncoding-3.4.csproj">
     165      <Project>{166507c9-ef26-4370-bb80-699742a29d4f}</Project>
     166      <Name>HeuristicLab.Encodings.LinearLinkageEncoding-3.4</Name>
    168167    </ProjectReference>
    169168    <ProjectReference Include="..\..\HeuristicLab.Encodings.PermutationEncoding\3.3\HeuristicLab.Encodings.PermutationEncoding-3.3.csproj">
  • branches/MemPRAlgorithm/HeuristicLab.Algorithms.MemPR/3.3/LinearLinkage/LinearLinkageMemPR.cs

    r14484 r14487  
    250250      var p1 = p1Scope.Solution;
    251251      var p2 = p2Scope.Solution;
    252       var transfered = new bool[p1.Length];
    253       var subspace = new bool[p1.Length];
    254       var lleeChild = new int[p1.Length];
    255       var lleep1 = p1.ToLLEe();
    256       var lleep2 = p2.ToLLEe();
    257       for (var i = p1.Length - 1; i >= 0; i--) {
    258         // Step 1
    259         subspace[i] = p1[i] != p2[i];
    260         var p1IsEnd = p1[i] == i;
    261         var p2IsEnd = p2[i] == i;
    262         if (p1IsEnd & p2IsEnd) {
    263           transfered[i] = true;
    264         } else if (p1IsEnd | p2IsEnd) {
    265           transfered[i] = Context.Random.NextDouble() < 0.5;
    266         }
    267         lleeChild[i] = i;
    268 
    269         // Step 2
    270         if (transfered[i]) continue;
    271         var end1 = lleep1[i];
    272         var end2 = lleep2[i];
    273         var containsEnd1 = transfered[end1];
    274         var containsEnd2 = transfered[end2];
    275         if (containsEnd1 & containsEnd2) {
    276           if (Context.Random.NextDouble() < 0.5) {
    277             lleeChild[i] = end1;
    278           } else {
    279             lleeChild[i] = end2;
    280           }
    281         } else if (containsEnd1) {
    282           lleeChild[i] = end1;
    283         } else if (containsEnd2) {
    284           lleeChild[i] = end2;
    285         } else {
    286           if (Context.Random.NextDouble() < 0.5) {
    287             lleeChild[i] = lleeChild[p1[i]];
    288           } else {
    289             lleeChild[i] = lleeChild[p2[i]];
    290           }
    291         }
    292       }
    293       var child = new Encodings.LinearLinkageEncoding.LinearLinkage(lleeChild.Length);
    294       child.FromLLEe(lleeChild);
    295      
    296       return ToScope(child);
     252      return ToScope(GroupCrossover.Apply(Context.Random, p1, p2));
    297253    }
    298254
  • branches/MemPRAlgorithm/HeuristicLab.Algorithms.MemPR/3.3/LinearLinkage/SolutionModel/Univariate/UnivariateSolutionModel.cs

    r14466 r14487  
    6363    public Encodings.LinearLinkageEncoding.LinearLinkage Sample() {
    6464      var N = Frequencies.Rows;
    65       var centroid = new Encodings.LinearLinkageEncoding.LinearLinkage(N);
     65      var centroid = Encodings.LinearLinkageEncoding.LinearLinkage.SingleElementGroups(N);
    6666      var dict = new Dictionary<int, int>();
    6767      for (var i = N - 1; i >= 0; i--) {
  • 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/Creators/ExactGroupsLinearLinkageCreator.cs

    r14185 r14487  
    5656
    5757    public static LinearLinkage Apply(IRandom random, int length, int groups) {
    58       var solution = new LinearLinkage(length);
    5958      var groupNumbers = Enumerable.Range(0, length).Select(x => x % groups).Shuffle(random);
    6059      var grouping = Enumerable.Range(0, groups).Select(x => new List<int>()).ToList();
     
    6362        grouping[g].Add(idx++);
    6463
    65       solution.SetGroups(grouping);
    66       return solution;
     64      return LinearLinkage.FromGroups(length, grouping);
    6765    }
    6866
  • branches/MemPRAlgorithm/HeuristicLab.Encodings.LinearLinkageEncoding/3.3/Creators/MaxGroupsLinearLinkageCreator.cs

    r14185 r14487  
    5555
    5656    public static LinearLinkage Apply(IRandom random, int length, int maxGroups) {
    57       var solution = new LinearLinkage(length);
    5857      var groups = Enumerable.Range(0, length).Select(x => Tuple.Create(x, random.Next(maxGroups)))
    5958                                              .GroupBy(x => x.Item2)
    6059                                              .Select(x => x.Select(y => y.Item1).ToList());
    61       solution.SetGroups(groups);
    62       return solution;
     60      return LinearLinkage.FromGroups(length, groups);
    6361    }
    6462
  • branches/MemPRAlgorithm/HeuristicLab.Encodings.LinearLinkageEncoding/3.3/Creators/RandomLinearLinkageCreator.cs

    r14185 r14487  
    4141
    4242    public static LinearLinkage Apply(IRandom random, int length) {
    43       var solution = new LinearLinkage(length);
    4443      var groups = Enumerable.Range(0, length).Select(x => Tuple.Create(x, random.Next(length)))
    4544                                              .GroupBy(x => x.Item2)
    4645                                              .Select(x => x.Select(y => y.Item1).ToList());
    47       solution.SetGroups(groups);
    48       return solution;
     46      return LinearLinkage.FromGroups(length, groups);
    4947    }
    5048
  • branches/MemPRAlgorithm/HeuristicLab.Encodings.LinearLinkageEncoding/3.3/Crossovers/GreedyPartitionCrossover.cs

    r14185 r14487  
    4444    public static LinearLinkage Apply(IRandom random, ItemArray<LinearLinkage> parents) {
    4545      var len = parents[0].Length;
    46 
    47       var child = new LinearLinkage(len);
    4846      var childGroup = new List<HashSet<int>>();
    4947      var currentParent = random.Next(parents.Length);
     
    6967      } while (remaining);
    7068
    71       child.SetGroups(childGroup);
    72       return child;
     69      return LinearLinkage.FromGroups(len, childGroup);
    7370    }
    7471
  • branches/MemPRAlgorithm/HeuristicLab.Encodings.LinearLinkageEncoding/3.3/Crossovers/GroupCrossover.cs

    r14185 r14487  
    3939      return new GroupCrossover(this, cloner);
    4040    }
    41 
     41   
    4242    public static LinearLinkage Apply(IRandom random, LinearLinkage p1, LinearLinkage p2) {
    4343      var length = p1.Length;
    44       var child = new LinearLinkage(length);
    45       var endNodes = new HashSet<int>();
    46       for (var i = 0; i < length; i++) {
    47         if ((p1[i] == i && p2[i] == i)
    48           || ((p1[i] == i || p2[i] == i) && random.NextDouble() < 0.5)) {
    49           child[i] = i;
    50           endNodes.Add(i);
     44      var lleeP1 = p1.ToEndLinks();
     45      var lleeP2 = p2.ToEndLinks();
     46      var lleeChild = new int[length];
     47      var isTransfered = new bool[length];
     48
     49      for (var i = p1.Length - 1; i >= 0; i--) {
     50        lleeChild[i] = i;
     51
     52        // Step 1
     53        var isEndP1 = p1[i] == i;
     54        var isEndP2 = p2[i] == i;
     55        if (isEndP1 & isEndP2 || (isEndP1 | isEndP2 && random.NextDouble() < 0.5)) {
     56          isTransfered[i] = true;
     57          continue;
     58        }
     59
     60        // Step 2
     61        var end1 = lleeP1[i];
     62        var end2 = lleeP2[i];
     63
     64        if (isTransfered[end1] & isTransfered[end2]) {
     65          var end = random.NextDouble() < 0.5 ? end1 : end2;
     66          lleeChild[i] = end;
     67        } else if (isTransfered[end1]) {
     68          lleeChild[i] = end1;
     69        } else if (isTransfered[end2]) {
     70          lleeChild[i] = end2;
     71        } else {
     72          var next = random.NextDouble() < 0.5 ? p1[i] : p2[i];
     73          var end = lleeChild[next];
     74          lleeChild[i] = end;
    5175        }
    5276      }
    53       for (var i = 0; i < length; i++) {
    54         if (endNodes.Contains(i)) continue;
    55         var p1End = endNodes.Contains(p1[i]);
    56         var p2End = endNodes.Contains(p2[i]);
    57         if ((p1End && p2End) || (!p1End && !p2End)) {
    58           child[i] = random.NextDouble() < 0.5 ? p1[i] : p2[i];
    59         } else if (p1End) {
    60           child[i] = p1[i];
    61         } else {
    62           child[i] = p2[i];
    63         }
    64       }
    65       child.LinearizeTreeStructures();
    66       return child;
     77      return LinearLinkage.FromEndLinks(lleeChild);
    6778    }
    6879
  • branches/MemPRAlgorithm/HeuristicLab.Encodings.LinearLinkageEncoding/3.3/Crossovers/LowestIndexFirstCrossover.cs

    r14185 r14487  
    4343      var len = parents[0].Length;
    4444      var p = random.Next(parents.Length);
    45       var child = new LinearLinkage(len);
     45      var child = LinearLinkage.SingleElementGroups(len);
    4646      var remaining = new SortedSet<int>(Enumerable.Range(0, len));
    4747      do {
  • branches/MemPRAlgorithm/HeuristicLab.Encodings.LinearLinkageEncoding/3.3/Crossovers/LowestIndexMaxCrossover.cs

    r14185 r14487  
    4444    public static LinearLinkage Apply(IRandom random, ItemArray<LinearLinkage> parents) {
    4545      var len = parents[0].Length;
    46       var child = new LinearLinkage(len);
     46      var child = LinearLinkage.SingleElementGroups(len);
    4747      var remaining = new SortedSet<int>(Enumerable.Range(0, len));
    4848      do {
  • branches/MemPRAlgorithm/HeuristicLab.Encodings.LinearLinkageEncoding/3.3/Crossovers/SinglePointCrossover.cs

    r14185 r14487  
    4141    public static LinearLinkage Apply(IRandom random, LinearLinkage p1, LinearLinkage p2) {
    4242      var length = p1.Length;
    43       var child = new LinearLinkage(length);
     43      var child = LinearLinkage.SingleElementGroups(length);
    4444      var bp = random.Next(length - 1);
    4545      for (var i = 0; i <= bp; i++) child[i] = p1[i];
  • branches/MemPRAlgorithm/HeuristicLab.Encodings.LinearLinkageEncoding/3.3/HeuristicLab.Encodings.LinearLinkageEncoding-3.4.csproj

    r14475 r14487  
    55    <Configuration Condition=" '$(Configuration)' == '' ">Debug</Configuration>
    66    <Platform Condition=" '$(Platform)' == '' ">AnyCPU</Platform>
    7     <ProjectGuid>{BE698769-975A-429E-828C-72BB2B6182C8}</ProjectGuid>
     7    <ProjectGuid>{166507C9-EF26-4370-BB80-699742A29D4F}</ProjectGuid>
    88    <OutputType>Library</OutputType>
    99    <AppDesignerFolder>Properties</AppDesignerFolder>
     
    183183    <Compile Include="Moves\Swap\Swap2MoveMaker.cs" />
    184184    <Compile Include="ShakingOperators\LLEShakingOperator.cs" />
     185    <Compile Include="SimilarityCalculators\HammingSimilarityCalculator.cs" />
    185186    <None Include="HeuristicLab.snk" />
    186187    <None Include="Plugin.cs.frame" />
  • 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      }
  • branches/MemPRAlgorithm/HeuristicLab.Encodings.LinearLinkageEncoding/3.3/Moves/StaticAPI/MoveGenerator.cs

    r14477 r14487  
    4545            yield return new MergeMove(i, l.Key);
    4646          }
     47        } else {
     48          // Fourth: extract i into group of its own (exclude first, because of Second)
     49          yield return new ExtractMove(i, pred, next);
    4750        }
    4851      }
    49       if (!isFirst)
    50         // Fourth: extract i into group of its own (exclude first, because of Second)
    51         yield return new ExtractMove(i, pred, next);
     52       
    5253
    5354    }
  • branches/MemPRAlgorithm/HeuristicLab.Encodings.LinearLinkageEncoding/3.3/Plugin.cs.frame

    r14195 r14487  
    2323
    2424namespace HeuristicLab.Encodings.LinearLinkageEncoding {
    25   [Plugin("HeuristicLab.Encodings.LinearLinkageEncoding", "Provides data structures and operators for the linear linkage encoding (LLE).", "3.3.14.$WCREV$")]
    26   [PluginFile("HeuristicLab.Encodings.LinearLinkageEncoding-3.3.dll", PluginFileType.Assembly)]
     25  [Plugin("HeuristicLab.Encodings.LinearLinkageEncoding", "Provides data structures and operators for the linear linkage encoding (LLE).", "3.4.14.$WCREV$")]
     26  [PluginFile("HeuristicLab.Encodings.LinearLinkageEncoding-3.4.dll", PluginFileType.Assembly)]
    2727  [PluginDependency("HeuristicLab.Collections", "3.3")]
    2828  [PluginDependency("HeuristicLab.Common", "3.3")]
  • branches/MemPRAlgorithm/HeuristicLab.Encodings.LinearLinkageEncoding/3.3/Properties/AssemblyInfo.cs.frame

    r14195 r14487  
    5353// by using the '*' as shown below:
    5454// [assembly: AssemblyVersion("1.0.*")]
    55 [assembly: AssemblyVersion("3.3.0.0")]
    56 [assembly: AssemblyFileVersion("3.3.14.$WCREV$")]
     55[assembly: AssemblyVersion("3.4.0.0")]
     56[assembly: AssemblyFileVersion("3.4.14.$WCREV$")]
  • branches/MemPRAlgorithm/HeuristicLab.PluginInfrastructure/3.3/Manager/PluginValidator.cs

    r14185 r14487  
    260260        }
    261261        // ignore exceptions. Just don't yield a plugin description when an exception is thrown
    262         catch (FileNotFoundException) {
     262        catch (FileNotFoundException e) {
    263263        }
    264264        catch (FileLoadException) {
     
    468468        // if the dependency is already disabled we can ignore the cycle detection because we will disable the plugin anyway
    469469        // if following one of the dependencies recursively leads to a cycle then we also return
    470         if (dep == plugin || dep.PluginState == PluginState.Disabled || HasCycleInDependencies(plugin, dep.Dependencies)) return true;
     470        if (dep == plugin || dep.PluginState == PluginState.Disabled || HasCycleInDependencies(plugin, dep.Dependencies))
     471          return true;
    471472      }
    472473      // no cycle found and none of the direct and indirect dependencies is disabled
  • branches/MemPRAlgorithm/HeuristicLab.Problems.GraphColoring/3.3/GraphColoringProblem.cs

    r14471 r14487  
    114114      var fitFun = FitnessFunctionParameter.Value.Value;
    115115      var adjList = adjacencyListParameter.Value;
    116       var lle = individual.LinearLinkage(Encoding.Name).ToLLEe(); // LLE-e encoding uses the highest indexed member as group number
     116      var lle = individual.LinearLinkage(Encoding.Name).ToEndLinks(); // LLE-e encoding uses the highest indexed member as group number
    117117
    118118      switch (fitFun) {
     
    158158
    159159      var adjList = AdjacencyListParameter.Value;
    160       var lle = best.ToLLEe();
     160      var lle = best.ToEndLinks();
    161161      var conflicts = 0;
    162162      var colors = lle.Distinct().Count();
  • branches/MemPRAlgorithm/HeuristicLab.Problems.GraphColoring/3.3/HeuristicLab.Problems.GraphColoring-3.3.csproj

    r14471 r14487  
    8888      <Private>False</Private>
    8989    </ProjectReference>
    90     <ProjectReference Include="..\..\HeuristicLab.Encodings.LinearLinkageEncoding\3.3\HeuristicLab.Encodings.LinearLinkageEncoding-3.3.csproj">
    91       <Project>{be698769-975a-429e-828c-72bb2b6182c8}</Project>
    92       <Name>HeuristicLab.Encodings.LinearLinkageEncoding-3.3</Name>
    93       <Private>False</Private>
     90    <ProjectReference Include="..\..\HeuristicLab.Encodings.LinearLinkageEncoding\3.3\HeuristicLab.Encodings.LinearLinkageEncoding-3.4.csproj">
     91      <Project>{166507c9-ef26-4370-bb80-699742a29d4f}</Project>
     92      <Name>HeuristicLab.Encodings.LinearLinkageEncoding-3.4</Name>
    9493    </ProjectReference>
    9594    <ProjectReference Include="..\..\HeuristicLab.Operators\3.3\HeuristicLab.Operators-3.3.csproj">
  • branches/MemPRAlgorithm/HeuristicLab.Problems.Programmable/3.3/HeuristicLab.Problems.Programmable-3.3.csproj

    r12724 r14487  
    149149      <Name>HeuristicLab.Encodings.IntegerVectorEncoding-3.3</Name>
    150150    </ProjectReference>
    151     <ProjectReference Include="..\..\HeuristicLab.Encodings.LinearLinkageEncoding\3.3\HeuristicLab.Encodings.LinearLinkageEncoding-3.3.csproj">
    152       <Project>{be698769-975a-429e-828c-72bb2b6182c8}</Project>
    153       <Name>HeuristicLab.Encodings.LinearLinkageEncoding-3.3</Name>
    154       <Private>False</Private>
     151    <ProjectReference Include="..\..\HeuristicLab.Encodings.LinearLinkageEncoding\3.3\HeuristicLab.Encodings.LinearLinkageEncoding-3.4.csproj">
     152      <Project>{166507c9-ef26-4370-bb80-699742a29d4f}</Project>
     153      <Name>HeuristicLab.Encodings.LinearLinkageEncoding-3.4</Name>
    155154    </ProjectReference>
    156155    <ProjectReference Include="..\..\HeuristicLab.Encodings.PermutationEncoding\3.3\HeuristicLab.Encodings.PermutationEncoding-3.3.csproj">
Note: See TracChangeset for help on using the changeset viewer.