Changeset 16692 for branches/2521_ProblemRefactoring/HeuristicLab.Encodings.LinearLinkageEncoding

branches/2521_ProblemRefactoring

Property svn:ignore

old	new
24	24	protoc.exe
25	25	obj
	26	.vs

Property svn:mergeinfo changed

/branches/Async (added)	merged: 13329,13349,13354-13355,13401,15065,15190,15204,15212,15215-15216,15232,15280-15281,15284,15286
/branches/symbreg-factors-2650 (added)	merged: 14232-14233,14237-14243,14248-14249,14251,14259,14266,14276-14277,14330-14331,14339,14351,14399,14401-14403,14421,14449,14497-14499,14501-14502,14534-14535,14539-14542,14554,14560,14589,14591-14592,14615,14693,14701,14715-14717,14719-14720,14751-14756,14758-14766,14812-14815,14823-14825
/stable	merged: 14190,15587-15588
/trunk/sources (added)	merged: 13392-13393,13395,13397,13402,13406,13411,13413-13415,13419-13420,13425,13427-13430,13433-13434,13438-13442,13445-13447,13450,13458,13471,13473-13474,13484,13491,13494,13498-13504,13507-13514,13516-13517,13525-13526,13529,13534-13535,13539-13540,13549-13550,13552,13560,13566-13567,13570-13573,13579-13582,13584-13586,13592-13593,13597,13614,13616,13621,13626-13629,13635,13644-13646,13648,13650-13655,13657-13662,13666,13669-13671,13675-13684,13690-13693,13695,13697-13705,13707-13709,13711,13715,13721,13724,13746,13760-13761,13764-13766,13779,13784-13786,13796,13800-13802,13807,13813,13826,13838,13863,13869,13889-13891,13895,13898-13901,13916-13917,13921-13922,13925,13932-13935,13938-13939,13941-13942,13958,13963-13964,13975,13978,13983-13987,13992-13993,13998,14000-14001,14007-14008,14011,14015-14017,14024-14026,14032,14034,14036-14037,14056-14057,14071,14078,14082-14083,14094-14096,14098-14100,14102-14103,14106-14107,14109-14110,14118,14120-14122,14124-14127,14129-14132,14135-14137,14140,14142,14144,14150,14152,14155-14160,14162-14164,14167-14169,14171,14174-14175,14177-14179,14181,14185,14187,14189,14191,14195-14196,14198,14200,14202-14209,14221-14224,14226-14230,14234-14236,14244-14247,14250,14255-14258,14260,14267-14268,14270-14273,14282,14284-14300,14307,14314-14316,14319,14322,14332,14340-14350,14352-14358,14367-14369,14371-14372,14376,14378,14381-14382,14384,14388,14390-14391,14393-14394,14396,14400,14405,14407-14408,14412,14418,14422-14423,14425,14432-14439,14443,14457-14458,14463-14465,14468-14469,14475-14476,14478-14479,14481-14483,14486,14493-14494,14504,14506-14509,14516-14517,14519,14522-14523,14527-14529,14531-14533,14548,14553,14561,14582,14597,14623,14630,14636-14638,14640-14641,14647,14651-14652,14654,14656,14659-14660,14662-14663,14672,14685,14687,14692,14697,14706,14708-14709,14718,14721-14722,14726,14732,14734,14737-14738,14740,14748-14750,14769-14770,14772-14775,14779-14781,14786,14789-14791,14793,14805,14809-14810,14817,14819-14820,14826-14832,14839-14843,14845-14847,14851-14854,14857,14860-14865,14871,14877,14882,14886,14889-14890,14899,14901,14904,14911-14912,14916,14918,14936-14938,14943-14951,14955,14971,14978-14979,14982,14984,14987,14992,14995,15002-15010,15013,15015-15016,15023-15024,15026,15029,15040,15042,15044,15046-15054,15058,15067-15077,15079-15080,15083-15088,15091-15096,15098-15099,15102-15107,15110-15114,15119-15126,15129,15135,15139,15156-15158,15160,15162-15169,15172-15173,15178-15181,15184-15185,15187,15191-15192,15194,15198,15201,15203,15205-15211,15213-15214,15221-15228,15230,15233-15236,15240-15241,15246-15248,15264-15266,15271,15276,15287-15288,15295,15299-15302,15312,15325-15327,15329,15335-15336,15339,15357-15358,15361,15367-15368,15370-15372,15376,15383,15388,15390,15395-15398,15400,15402,15408-15409,15419,15427,15447-15448,15452,15461,15464,15478,15480-15481,15483,15486,15498-15499,15502,15505,15513,15517-15518,15532,15534,15545,15548,15551,15556,15560,15566,15581,15583,15589-15591,15594,15596,15598,15607,15610-15611,15619,15621-15623,15626,15637-15638,15645,15665,15667,15672-15674

branches/2521_ProblemRefactoring/HeuristicLab.Encodings.LinearLinkageEncoding/3.4/Creators/ExactGroupsLinearLinkageCreator.cs

-                      r12650
+                      r16692
 #region License Information
 /* HeuristicLab
  * Copyright (C) 2002-2015 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
+ * Copyright (C) 2002-2018 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
+ *
  * This file is part of HeuristicLab.
 …
     public static LinearLinkage Apply(IRandom random, int length, int groups) {
-      var solution = new LinearLinkage(length);
       var groupNumbers = Enumerable.Range(0, length).Select(x => x % groups).Shuffle(random);
       var grouping = Enumerable.Range(0, groups).Select(x => new List<int>()).ToList();
 …
         grouping[g].Add(idx++);
+      solution.SetGroups(grouping);
+      return solution;
+      return LinearLinkage.FromGroups(length, grouping);
+    }

branches/2521_ProblemRefactoring/HeuristicLab.Encodings.LinearLinkageEncoding/3.4/Creators/MaxGroupsLinearLinkageCreator.cs

-                      r12650
+                      r16692
 #region License Information
 /* HeuristicLab
  * Copyright (C) 2002-2015 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
+ * Copyright (C) 2002-2018 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
+ *
  * This file is part of HeuristicLab.
 …
     public static LinearLinkage Apply(IRandom random, int length, int maxGroups) {
-      var solution = new LinearLinkage(length);
       var groups = Enumerable.Range(0, length).Select(x => Tuple.Create(x, random.Next(maxGroups)))
                                               .GroupBy(x => x.Item2)
                                               .Select(x => x.Select(y => y.Item1).ToList());
+      solution.SetGroups(groups);
+      return solution;
+      return LinearLinkage.FromGroups(length, groups);
+    }

branches/2521_ProblemRefactoring/HeuristicLab.Encodings.LinearLinkageEncoding/3.4/Creators/RandomLinearLinkageCreator.cs

-                      r12650
+                      r16692
 #region License Information
 /* HeuristicLab
  * Copyright (C) 2002-2015 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
+ * Copyright (C) 2002-2018 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
+ *
  * This file is part of HeuristicLab.
 …
     public static LinearLinkage Apply(IRandom random, int length) {
-      var solution = new LinearLinkage(length);
       var groups = Enumerable.Range(0, length).Select(x => Tuple.Create(x, random.Next(length)))
                                               .GroupBy(x => x.Item2)
                                               .Select(x => x.Select(y => y.Item1).ToList());
+      solution.SetGroups(groups);
+      return solution;
+      return LinearLinkage.FromGroups(length, groups);
+    }

branches/2521_ProblemRefactoring/HeuristicLab.Encodings.LinearLinkageEncoding/3.4/Crossovers/GreedyPartitionCrossover.cs

-                      r12285
+                      r16692
 #region License Information
 /* HeuristicLab
  * Copyright (C) 2002-2015 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
+ * Copyright (C) 2002-2018 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
+ *
  * This file is part of HeuristicLab.
 …
     public static LinearLinkage Apply(IRandom random, ItemArray<LinearLinkage> parents) {
       var len = parents[0].Length;
-      var child = new LinearLinkage(len);
       var childGroup = new List<HashSet<int>>();
       var currentParent = random.Next(parents.Length);
 …
       } while (remaining);
+      child.SetGroups(childGroup);
+      return child;
+      return LinearLinkage.FromGroups(len, childGroup);
+    }

branches/2521_ProblemRefactoring/HeuristicLab.Encodings.LinearLinkageEncoding/3.4/Crossovers/GroupCrossover.cs

-                      r12650
+                      r16692
 #region License Information
 /* HeuristicLab
  * Copyright (C) 2002-2015 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
+ * Copyright (C) 2002-2018 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
+ *
  * This file is part of HeuristicLab.
 …
       return new GroupCrossover(this, cloner);
+    }
     public static LinearLinkage Apply(IRandom random, LinearLinkage p1, LinearLinkage p2) {
       var length = p1.Length;
+      var child = new LinearLinkage(length);
+      var endNodes = new HashSet<int>();
+      for (var i = 0; i < length; i++) {
+        if ((p1[i] == i && p2[i] == i)
+          || ((p1[i] == i || p2[i] == i) && random.NextDouble() < 0.5)) {
+          child[i] = i;
+          endNodes.Add(i);
+      var lleeP1 = p1.ToEndLinks();
+      var lleeP2 = p2.ToEndLinks();
+      var lleeChild = new int[length];
+      var isTransfered = new bool[length];
+      for (var i = p1.Length - 1; i >= 0; i--) {
+        lleeChild[i] = i;
+        // Step 1
+        var isEndP1 = p1[i] == i;
+        var isEndP2 = p2[i] == i;
+        if (isEndP1 & isEndP2 || (isEndP1 | isEndP2 && random.NextDouble() < 0.5)) {
+          isTransfered[i] = true;
+          continue;
+        }
+        // Step 2
+        var end1 = lleeP1[i];
+        var end2 = lleeP2[i];
+        if (isTransfered[end1] & isTransfered[end2]) {
+          var end = random.NextDouble() < 0.5 ? end1 : end2;
+          lleeChild[i] = end;
+        } else if (isTransfered[end1]) {
+          lleeChild[i] = end1;
+        } else if (isTransfered[end2]) {
+          lleeChild[i] = end2;
+        } else {
+          var next = random.NextDouble() < 0.5 ? p1[i] : p2[i];
+          var end = lleeChild[next];
+          lleeChild[i] = end;
+        }
+      }
+      for (var i = 0; i < length; i++) {
+        if (endNodes.Contains(i)) continue;
+        var p1End = endNodes.Contains(p1[i]);
+        var p2End = endNodes.Contains(p2[i]);
+        if ((p1End && p2End) || (!p1End && !p2End)) {
+          child[i] = random.NextDouble() < 0.5 ? p1[i] : p2[i];
+        } else if (p1End) {
+          child[i] = p1[i];
+        } else {
+          child[i] = p2[i];
+        }
+      }
+      child.LinearizeTreeStructures();
+      return child;
+      return LinearLinkage.FromEndLinks(lleeChild);
+    }

branches/2521_ProblemRefactoring/HeuristicLab.Encodings.LinearLinkageEncoding/3.4/Crossovers/LowestIndexFirstCrossover.cs

-                      r12288
+                      r16692
 #region License Information
 /* HeuristicLab
  * Copyright (C) 2002-2015 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
+ * Copyright (C) 2002-2018 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
+ *
  * This file is part of HeuristicLab.
 …
       var len = parents[0].Length;
       var p = random.Next(parents.Length);
       var child = new LinearLinkage(len);
+      var child = LinearLinkage.SingleElementGroups(len);
       var remaining = new SortedSet<int>(Enumerable.Range(0, len));
       do {

branches/2521_ProblemRefactoring/HeuristicLab.Encodings.LinearLinkageEncoding/3.4/Crossovers/LowestIndexMaxCrossover.cs

-                      r12288
+                      r16692
 #region License Information
 /* HeuristicLab
  * Copyright (C) 2002-2015 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
+ * Copyright (C) 2002-2018 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
+ *
  * This file is part of HeuristicLab.
 …
     public static LinearLinkage Apply(IRandom random, ItemArray<LinearLinkage> parents) {
       var len = parents[0].Length;
       var child = new LinearLinkage(len);
+      var child = LinearLinkage.SingleElementGroups(len);
       var remaining = new SortedSet<int>(Enumerable.Range(0, len));
       do {

branches/2521_ProblemRefactoring/HeuristicLab.Encodings.LinearLinkageEncoding/3.4/Crossovers/MultiLLECrossover.cs

r12701	r16692
1	1	#region License Information
2	2	/* HeuristicLab
3		* Copyright (C) 2002-2015 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
	3	* Copyright (C) 2002-2018 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
4	4	*
5	5	* This file is part of HeuristicLab.

branches/2521_ProblemRefactoring/HeuristicLab.Encodings.LinearLinkageEncoding/3.4/Crossovers/SinglePointCrossover.cs

-                      r12650
+                      r16692
 #region License Information
 /* HeuristicLab
  * Copyright (C) 2002-2015 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
+ * Copyright (C) 2002-2018 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
+ *
  * This file is part of HeuristicLab.
 …
     public static LinearLinkage Apply(IRandom random, LinearLinkage p1, LinearLinkage p2) {
       var length = p1.Length;
       var child = new LinearLinkage(length);
+      var child = LinearLinkage.SingleElementGroups(length);
       var bp = random.Next(length - 1);
       for (var i = 0; i <= bp; i++) child[i] = p1[i];

branches/2521_ProblemRefactoring/HeuristicLab.Encodings.LinearLinkageEncoding/3.4/Interfaces/ILinearLinkageCreator.cs

r13372	r16692
1	1	#region License Information
2	2	/* HeuristicLab
3		* Copyright (C) 2002-2015 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
	3	* Copyright (C) 2002-2018 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
4	4	*
5	5	* This file is part of HeuristicLab.

branches/2521_ProblemRefactoring/HeuristicLab.Encodings.LinearLinkageEncoding/3.4/Interfaces/ILinearLinkageCrossover.cs

r12650	r16692
1	1	#region License Information
2	2	/* HeuristicLab
3		* Copyright (C) 2002-2015 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
	3	* Copyright (C) 2002-2018 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
4	4	*
5	5	* This file is part of HeuristicLab.

branches/2521_ProblemRefactoring/HeuristicLab.Encodings.LinearLinkageEncoding/3.4/Interfaces/ILinearLinkageManipulator.cs

r12650	r16692
1	1	#region License Information
2	2	/* HeuristicLab
3		* Copyright (C) 2002-2015 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
	3	* Copyright (C) 2002-2018 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
4	4	*
5	5	* This file is part of HeuristicLab.

branches/2521_ProblemRefactoring/HeuristicLab.Encodings.LinearLinkageEncoding/3.4/Interfaces/ILinearLinkageMoveOperator.cs

r12650	r16692
1	1	#region License Information
2	2	/* HeuristicLab
3		* Copyright (C) 2002-2015 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
	3	* Copyright (C) 2002-2018 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
4	4	*
5	5	* This file is part of HeuristicLab.

branches/2521_ProblemRefactoring/HeuristicLab.Encodings.LinearLinkageEncoding/3.4/Interfaces/ILinearLinkageOperator.cs

r12650	r16692
1	1	#region License Information
2	2	/* HeuristicLab
3		* Copyright (C) 2002-2015 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
	3	* Copyright (C) 2002-2018 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
4	4	*
5	5	* This file is part of HeuristicLab.

branches/2521_ProblemRefactoring/HeuristicLab.Encodings.LinearLinkageEncoding/3.4/Interfaces/ILinearLinkageShakingOperator.cs

r12650	r16692
1	1	#region License Information
2	2	/* HeuristicLab
3		* Copyright (C) 2002-2015 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
	3	* Copyright (C) 2002-2018 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
4	4	*
5	5	* This file is part of HeuristicLab.

branches/2521_ProblemRefactoring/HeuristicLab.Encodings.LinearLinkageEncoding/3.4/Interfaces/ILinearLinkageSwap2MoveOperator.cs

r12650	r16692
1	1	#region License Information
2	2	/* HeuristicLab
3		* Copyright (C) 2002-2015 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
	3	* Copyright (C) 2002-2018 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
4	4	*
5	5	* This file is part of HeuristicLab.

branches/2521_ProblemRefactoring/HeuristicLab.Encodings.LinearLinkageEncoding/3.4/LinearLinkage.cs

-                      r13372
+                      r16692
 #region License Information
 /* HeuristicLab
  * Copyright (C) 2002-2015 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
+ * Copyright (C) 2002-2018 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
+ *
  * This file is part of HeuristicLab.
 …
     private LinearLinkage(LinearLinkage original, Cloner cloner) : base(original, cloner) { }
     public LinearLinkage() { }
+    public LinearLinkage(int length) : base(length) { }
+    public LinearLinkage(int[] elements) : base(elements) { }
+    private LinearLinkage(int length) : base(length) { }
+    private LinearLinkage(int[] elements) : base(elements) { }
+    /// <summary>
+    /// Create a new LinearLinkage object where every element is in a seperate group.
+    /// </summary>
+    public static LinearLinkage SingleElementGroups(int length) {
+      var elements = new int[length];
+      for (var i = 0; i < length; i++) {
+        elements[i] = i;
+      }
+      return new LinearLinkage(elements);
+    }
+    /// <summary>
+    /// Create a new LinearLinkage object from an int[] in LLE
+    /// </summary>
+    /// <remarks>
+    /// This operation checks if the argument is a well formed LLE
+    /// and throws an ArgumentException otherwise.
+    /// </remarks>
+    /// <exception cref="ArgumentException">If <paramref name="lle"/> does not represent a valid LLE array.</exception>
+    /// <param name="lle">The LLE representation</param>
+    /// <returns>The linear linkage encoding in LLE format (with forward-links).</returns>
+    public static LinearLinkage FromForwardLinks(int[] lle) {
+      if (!Validate(lle))
+        throw new ArgumentException("Array is malformed and does not represent a valid LLE forward encoding.", "elements");
+      return new LinearLinkage(lle);
+    }
+    /// <summary>
+    /// Create a new LinearLinkage object by parsing a LLE-b representation
+    /// and modifing the underlying array so that it is in LLE representation.
+    /// </summary>
+    /// <remarks>
+    /// This operation runs in O(n) time, the parameter <paramref name="lleb"/> is not modified.
+    /// </remarks>
+    /// <exception cref="ArgumentException">If <paramref name="lleb"/> does not represent a valid LLE-b array.</exception>
+    /// <param name="lleb">The LLE-b representation (LLE with back-links)</param>
+    /// <returns>The linear linkage encoding in LLE format (with forward-links).</returns>
+    public static LinearLinkage FromBackLinks(int[] lleb) {
+      var result = new LinearLinkage(lleb.Length);
+      for (var i = lleb.Length - 1; i > 0; i--) {
+        if (lleb[i] == i) {
+          if (result[i] == 0) result[i] = i;
+          continue;
+        }
+        result[lleb[i]] = i;
+        if (result[i] == 0) result[i] = i;
+      }
+      if (!Validate(result.array))
+        throw new ArgumentException("Array is malformed and does not represent a valid LLE-b encoding (with back-links).", "lleb");
+      return result;
+    }
+    /// <summary>
+    /// Create a new LinearLinkage object by parsing an LLE-e representation
+    /// and modifing the underlying array so that it is in LLE representation.
+    /// </summary>
+    /// <remarks>
+    /// This operation runs in O(n) time, but requires additional memory
+    /// in form of a int[].
+    /// </remarks>
+    /// <param name="llee">The LLE-e representation</param>
+    /// <returns>The linear linkage encoding in LLE format (with forward-links).</returns>
+    public static LinearLinkage FromEndLinks(int[] llee) {
+      var result = new LinearLinkage(llee.Length);
+      result.SetEndLinks(llee);
+      return result;
+    }
+    /// <summary>
+    /// Create a new LinearLinkage object by translating
+    /// an enumeration of groups into the underlying array representation.
+    /// </summary>
+    /// <remarks>
+    /// Throws an ArgumentException when there is an element assigned to
+    /// multiple groups or elements that are not assigned to any group.
+    /// </remarks>
+    /// <param name="grouping">The grouping of the elements, each element must
+    /// be part of exactly one group.</param>
+    public static LinearLinkage FromGroups(int length, IEnumerable<IEnumerable<int>> grouping) {
+      var result = new LinearLinkage(length);
+      result.SetGroups(grouping);
+      return result;
+    }
     public override IDeepCloneable Clone(Cloner cloner) {
 …
     /// array.
     /// </remarks>
+    /// <exception cref="InvalidOperationException">If this object is not vaild LLE.</exception>
     /// <returns>An enumeration of all groups.</returns>
     public IEnumerable<List<int>> GetGroups() {
       var len = array.Length;
+      var remaining = new HashSet<int>(Enumerable.Range(0, len));
+      // iterate from lowest to highest index
+      var used = new bool[len];
       for (var i = 0; i < len; i++) {
+        if (!remaining.Contains(i)) continue;
+        var group = new List<int> { i };
+        remaining.Remove(i);
+        var next = array[i];
+        if (next != i) {
+          int prev;
+          do {
+            group.Add(next);
+            if (!remaining.Remove(next))
+              throw new ArgumentException("Array is malformed and does not represent a valid LLE forward encoding.");
+            prev = next;
+            next = array[next];
+          } while (next != prev);
+        }
+        if (used[i]) continue;
+        var curr = i;
+        var next = array[curr];
+        var group = new List<int> { curr };
+        while (next > curr && next < len && !used[next]) {
+          used[curr] = true;
+          curr = next;
+          next = array[next];
+          group.Add(curr);
+        }
+        if (curr != next) throw new InvalidOperationException("Array is malformed and does not represent a valid LLE forward encoding.");
+        used[curr] = true;
         yield return group;
+      }
 …
     /// <param name="grouping">The grouping of the elements, each element must
     /// be part of exactly one group.</param>
+    /// <exception cref="ArgumentException">If <paramref name="grouping"/> cannot be converted
+    /// to a valid LLE representation. For instance, because elements are too big or too small,
+    /// or they're contained in multiple groups, or there are elements not assigned to any group.
+    /// </exception>
     public void SetGroups(IEnumerable<IEnumerable<int>> grouping) {
       var len = array.Length;
       var remaining = new HashSet<int>(Enumerable.Range(0, len));
+      var used = new bool[len];
       foreach (var group in grouping) {
         var prev = -1;
         foreach (var g in group.OrderBy(x => x)) {
+          if (g < prev || g >= len) throw new ArgumentException(string.Format("Element {0} is bigger than {1} or smaller than 0.", g, len - 1), "grouping");
           if (prev >= 0) array[prev] = g;
           prev = g;
           if (!remaining.Remove(prev))
+          if (used[prev]) {
             throw new ArgumentException(string.Format("Element {0} is contained at least twice.", prev), "grouping");
+        }
+        if (prev >= 0) array[prev] = prev;
+      }
+      if (remaining.Count > 0)
+        throw new ArgumentException(string.Format("Elements are not assigned a group: {0}", string.Join(", ", remaining)));
+          }
+          used[prev] = true;
+        }
+        array[prev] = prev;
+      }
+      if (!used.All(x => x))
+        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))));
+    }
 …
     /// <returns>True if the encoding is valid.</returns>
     public bool Validate() {
+      return Validate(array);
+    }
+    private static bool Validate(int[] array) {
       var len = array.Length;
       var remaining = new HashSet<int>(Enumerable.Range(0, len));
+      var used = new bool[len];
       for (var i = 0; i < len; i++) {
+        if (!remaining.Contains(i)) continue;
+        remaining.Remove(i);
+        var next = array[i];
+        if (next == i) continue;
+        int prev;
+        do {
+          if (!remaining.Remove(next)) return false;
+          prev = next;
+        if (used[i]) continue;
+        var curr = i;
+        var next = array[curr];
+        while (next > curr && next < len && !used[next]) {
+          used[curr] = true;
+          curr = next;
           next = array[next];
+        } while (next != prev);
+      }
+      return remaining.Count == 0;
+        }
+        if (curr != next) return false;
+        used[curr] = true;
+      }
+      return true;
+    }
 …
     /// These tree structures may be created by e.g. merging two groups by
     /// linking one end node to the end node of another.
     /// Consider following 1-based index array: 6, 6, 7, 5, 5, 8, 8, 8, 9.
     /// This results in the following tree structure for group 8:
     ///      8
+    /// Consider following array: 5, 5, 6, 4, 4, 7, 7, 7, 8.
+    /// This results in the following tree structure for group 7:
+    ///      7
     ///    /   \
     ///   6     7
+    ///   5     6
     ///  / \    |
     /// 1   2   3
     /// After this operation the array will be 2, 3, 6, 5, 5, 7, 8, 8, 9.
     /// Representing a tree with one branch: 1 -> 2 -> 3 -> 6 -> 7 -> 8
+    /// 0   1   2
+    /// After this operation the array will be 1, 2, 5, 4, 4, 6, 7, 7, 8.
+    /// Representing a tree with one branch: 0 -> 1 -> 2 -> 5 -> 6 -> 7.
     /// </summary>
     /// <remarks>
     /// The method first converts the array to LLE-e format and then
     /// linearizes the links. This requires two passes of the whole array
     /// as well as a dictionary to hold the smallest index of each group.
+    /// as well as another copy of the underlying array.
     /// The runtime complexity is O(n).
     ///
 …
     public void LinearizeTreeStructures() {
       // Step 1: Convert the array into LLE-e
       ToLLEeInplace(array);
+      ToEndLinksInplace(array);
       // Step 2: For all groups linearize the links
       FromLLEe(array);
+      SetEndLinks(array);
+    }
 …
     /// LLE-e is a special format where each element points to the
     /// ending item of a group.
     /// The LLE representation 2, 3, 5, 6, 5, 7, 8, 8 would become
     /// 5, 5, 5, 8, 5, 8, 8, 8 in LLE-e.
+    /// The LLE representation 1, 2, 4, 5, 4, 6, 7, 7 would become
+    /// 4, 4, 4, 7, 4, 7, 7, 7 in LLE-e.
     ///
     /// This operation runs in O(n) time.
     /// </remarks>
+    /// <exception cref="ArgumentException">In case, this object does not
+    /// represent a valid LLE encoding.
+    /// </exception>
     /// <returns>An integer array in LLE-e representation</returns>
     public int[] ToLLEe() {
+    public int[] ToEndLinks() {
       var result = (int[])array.Clone();
       ToLLEeInplace(result);
+      ToEndLinksInplace(result);
       return result;
+    }
     private void ToLLEeInplace(int[] a) {
       var length = a.Length;
+    private static void ToEndLinksInplace(int[] array) {
+      var length = array.Length;
       for (var i = length - 1; i >= 0; i--) {
+        if (array[i] == i) a[i] = i;
+        else a[i] = a[a[i]];
+        var next = array[i];
+        if (next > i) {
+          array[i] = array[next];
+        } else if (next < i) {
+          throw new ArgumentException("Array is malformed and does not represent a valid LLE encoding.", "array");
+        }
+      }
+    }
 …
     /// <remarks>
     /// This operation runs in O(n) time, but requires additional memory
     /// in form of a dictionary.
+    /// in form of a int[].
     /// </remarks>
     /// <param name="llee">The LLE-e representation</param>
+    public void FromLLEe(int[] llee) {
+    /// <exception cref="ArgumentException">
+    /// If <paramref name="llee"/> does not contain a valid LLE-e representation or
+    /// has a different length to the given instance.
+    /// </exception>
+    public void SetEndLinks(int[] llee) {
       var length = array.Length;
+      var groups = new Dictionary<int, int>();
+      if (length != llee.Length) {
+        throw new ArgumentException(string.Format("Expected length {0} but length was {1}", length, llee.Length), "llee");
+      }
+      // If we are ok with mutating llee we can avoid this clone
+      var lookup = (int[])llee.Clone();
       for (var i = length - 1; i >= 0; i--) {
+        if (llee[i] == i) {
+          array[i] = i;
+          groups[i] = i;
+        var end = llee[i];
+        if (end == i) {
+          array[i] = end;
+        } else if (end > i && end < length) {
+          array[i] = lookup[end];
+          lookup[end] = i;
         } else {
+          var g = llee[i];
+          array[i] = groups[g];
+          groups[g] = i;
+        }
+      }
+          throw new ArgumentException("Array is malformed and does not represent a valid LLE-e end encoding.", "llee");
+        }
+      }
+    }
+    /// <summary>
+    /// Creates a copy of the underlying array and turns it into LLE-b.
+    /// </summary>
+    /// <remarks>
+    /// LLE-b is a special format where each element points to the
+    /// predecessor instead of the successor.
+    /// The LLE representation 1, 2, 4, 5, 4, 6, 7, 7
+    /// would become           0, 0, 1, 3, 2, 3, 5, 6 in LLE-b.
+    ///
+    /// This operation runs in O(n) time.
+    /// </remarks>
+    /// <returns>An integer array in LLE-b representation</returns>
+    public int[] ToBackLinks() {
+      var result = new int[array.Length];
+      var zeroLink = array[0];
+      for (var i = 0; i < array.Length; i++) {
+        if (array[i] == i) {
+          if (result[i] == 0 && i != zeroLink) result[i] = i;
+          continue;
+        }
+        result[array[i]] = i;
+        if (result[i] == 0 && i != zeroLink) result[i] = i;
+      }
+      return result;
+    }
+  }

branches/2521_ProblemRefactoring/HeuristicLab.Encodings.LinearLinkageEncoding/3.4/LinearLinkageCreator.cs

r12288	r16692
1	1	#region License Information
2	2	/* HeuristicLab
3		* Copyright (C) 2002-2015 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
	3	* Copyright (C) 2002-2018 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
4	4	*
5	5	* This file is part of HeuristicLab.

branches/2521_ProblemRefactoring/HeuristicLab.Encodings.LinearLinkageEncoding/3.4/LinearLinkageCrossover.cs

r12285	r16692
1	1	#region License Information
2	2	/* HeuristicLab
3		* Copyright (C) 2002-2015 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
	3	* Copyright (C) 2002-2018 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
4	4	*
5	5	* This file is part of HeuristicLab.

branches/2521_ProblemRefactoring/HeuristicLab.Encodings.LinearLinkageEncoding/3.4/LinearLinkageEncoding.cs

r13396	r16692
1	1	#region License Information
2	2	/* HeuristicLab
3		* Copyright (C) 2002-2015 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
	3	* Copyright (C) 2002-2018 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
4	4	*
5	5	* This file is part of HeuristicLab.

branches/2521_ProblemRefactoring/HeuristicLab.Encodings.LinearLinkageEncoding/3.4/LinearLinkageManipulator.cs

r12288	r16692
1	1	#region License Information
2	2	/* HeuristicLab
3		* Copyright (C) 2002-2015 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
	3	* Copyright (C) 2002-2018 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
4	4	*
5	5	* This file is part of HeuristicLab.

branches/2521_ProblemRefactoring/HeuristicLab.Encodings.LinearLinkageEncoding/3.4/Manipulators/GraftManipulator.cs

r12396	r16692
1	1	#region License Information
2	2	/* HeuristicLab
3		* Copyright (C) 2002-2015 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
	3	* Copyright (C) 2002-2018 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
4	4	*
5	5	* This file is part of HeuristicLab.

branches/2521_ProblemRefactoring/HeuristicLab.Encodings.LinearLinkageEncoding/3.4/Manipulators/MergeGroupManipulator.cs

r12396	r16692
1	1	#region License Information
2	2	/* HeuristicLab
3		* Copyright (C) 2002-2015 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
	3	* Copyright (C) 2002-2018 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
4	4	*
5	5	* This file is part of HeuristicLab.

branches/2521_ProblemRefactoring/HeuristicLab.Encodings.LinearLinkageEncoding/3.4/Manipulators/MoveItemManipulator.cs

r12396	r16692
1	1	#region License Information
2	2	/* HeuristicLab
3		* Copyright (C) 2002-2015 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
	3	* Copyright (C) 2002-2018 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
4	4	*
5	5	* This file is part of HeuristicLab.

branches/2521_ProblemRefactoring/HeuristicLab.Encodings.LinearLinkageEncoding/3.4/Manipulators/MultiLLEManipulator.cs

r12743	r16692
1	1	#region License Information
2	2	/* HeuristicLab
3		* Copyright (C) 2002-2015 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
	3	* Copyright (C) 2002-2018 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
4	4	*
5	5	* This file is part of HeuristicLab.

branches/2521_ProblemRefactoring/HeuristicLab.Encodings.LinearLinkageEncoding/3.4/Manipulators/SplitGroupManipulator.cs

r12396	r16692
1	1	#region License Information
2	2	/* HeuristicLab
3		* Copyright (C) 2002-2015 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
	3	* Copyright (C) 2002-2018 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
4	4	*
5	5	* This file is part of HeuristicLab.

branches/2521_ProblemRefactoring/HeuristicLab.Encodings.LinearLinkageEncoding/3.4/Manipulators/SwapItemManipulator.cs

r12396	r16692
1	1	#region License Information
2	2	/* HeuristicLab
3		* Copyright (C) 2002-2015 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
	3	* Copyright (C) 2002-2018 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
4	4	*
5	5	* This file is part of HeuristicLab.

branches/2521_ProblemRefactoring/HeuristicLab.Encodings.LinearLinkageEncoding/3.4/Moves/Swap/ExhaustiveSwap2MoveGenerator.cs

-                      r12643
+                      r16692
 #region License Information
 /* HeuristicLab
  * Copyright (C) 2002-2015 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
+ * Copyright (C) 2002-2018 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
+ *
  * This file is part of HeuristicLab.
 …
 namespace HeuristicLab.Encodings.LinearLinkageEncoding {
   [Item("ExhaustiveSwap2MoveGenerator", "Generates all possible swap-2 moves from a given permutation.")]
+  [Item("ExhaustiveSwap2MoveGenerator", "Generates all possible swap-2 moves from a given lle grouping.")]
   [StorableClass]
   public class ExhaustiveSwap2MoveGenerator : Swap2MoveGenerator, IExhaustiveMoveGenerator {

branches/2521_ProblemRefactoring/HeuristicLab.Encodings.LinearLinkageEncoding/3.4/Moves/Swap/StochasticSwap2MultiMoveGenerator.cs

r12643	r16692
1	1	#region License Information
2	2	/* HeuristicLab
3		* Copyright (C) 2002-2015 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
	3	* Copyright (C) 2002-2018 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
4	4	*
5	5	* This file is part of HeuristicLab.

branches/2521_ProblemRefactoring/HeuristicLab.Encodings.LinearLinkageEncoding/3.4/Moves/Swap/StochasticSwap2SingleMoveGenerator.cs

-                      r12643
+                      r16692
 #region License Information
 /* HeuristicLab
  * Copyright (C) 2002-2015 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
+ * Copyright (C) 2002-2018 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
+ *
  * This file is part of HeuristicLab.
 …
 namespace HeuristicLab.Encodings.LinearLinkageEncoding {
   [Item("StochasticSwap2SingleMoveGenerator", "Randomly samples a single from all possible swap-2 moves from a given grouping.")]
+  [Item("StochasticSwap2SingleMoveGenerator", "Randomly samples a single from all possible swap-2 moves from a given lle grouping.")]
   [StorableClass]
   public class StochasticSwap2SingleMoveGenerator : Swap2MoveGenerator, IStochasticOperator, ISingleMoveGenerator {

branches/2521_ProblemRefactoring/HeuristicLab.Encodings.LinearLinkageEncoding/3.4/Moves/Swap/Swap2Move.cs

r12643	r16692
1	1	#region License Information
2	2	/* HeuristicLab
3		* Copyright (C) 2002-2015 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
	3	* Copyright (C) 2002-2018 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
4	4	*
5	5	* This file is part of HeuristicLab.

branches/2521_ProblemRefactoring/HeuristicLab.Encodings.LinearLinkageEncoding/3.4/Moves/Swap/Swap2MoveGenerator.cs

r12643	r16692
1	1	#region License Information
2	2	/* HeuristicLab
3		* Copyright (C) 2002-2015 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
	3	* Copyright (C) 2002-2018 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
4	4	*
5	5	* This file is part of HeuristicLab.

branches/2521_ProblemRefactoring/HeuristicLab.Encodings.LinearLinkageEncoding/3.4/Moves/Swap/Swap2MoveMaker.cs

r12643	r16692
1	1	#region License Information
2	2	/* HeuristicLab
3		* Copyright (C) 2002-2015 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
	3	* Copyright (C) 2002-2018 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
4	4	*
5	5	* This file is part of HeuristicLab.

branches/2521_ProblemRefactoring/HeuristicLab.Encodings.LinearLinkageEncoding/3.4/Plugin.cs.frame

-                      r13321
+                      r16692
 #region License Information
 /* HeuristicLab
  * Copyright (C) 2002-2015 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
+ * Copyright (C) 2002-2018 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
+ *
  * This file is part of HeuristicLab.
 …
 namespace HeuristicLab.Encodings.LinearLinkageEncoding {
   [Plugin("HeuristicLab.Encodings.LinearLinkageEncoding", "Provides data structures and operators for the linear linkage encoding (LLE).", "3.3.13.$WCREV$")]
   [PluginFile("HeuristicLab.Encodings.LinearLinkageEncoding-3.3.dll", PluginFileType.Assembly)]
+  [Plugin("HeuristicLab.Encodings.LinearLinkageEncoding", "Provides data structures and operators for the linear linkage encoding (LLE).", "3.4.14.$WCREV$")]
+  [PluginFile("HeuristicLab.Encodings.LinearLinkageEncoding-3.4.dll", PluginFileType.Assembly)]
   [PluginDependency("HeuristicLab.Collections", "3.3")]
   [PluginDependency("HeuristicLab.Common", "3.3")]

branches/2521_ProblemRefactoring/HeuristicLab.Encodings.LinearLinkageEncoding/3.4/Properties/AssemblyInfo.cs.frame

-                      r13321
+                      r16692
 #region License Information
 /* HeuristicLab
  * Copyright (C) 2002-2015 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
+ * Copyright (C) 2002-2018 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
+ *
  * This file is part of HeuristicLab.
 …
 [assembly: AssemblyCompany("HEAL")]
 [assembly: AssemblyProduct("HeuristicLab")]
 [assembly: AssemblyCopyright("(c) 2002-2015 HEAL")]
+[assembly: AssemblyCopyright("(c) 2002-2018 HEAL")]
 [assembly: AssemblyTrademark("")]
 [assembly: AssemblyCulture("")]
 …
 // by using the '*' as shown below:
 // [assembly: AssemblyVersion("1.0.*")]
 [assembly: AssemblyVersion("3.3.0.0")]
 [assembly: AssemblyFileVersion("3.3.13.$WCREV$")]
+[assembly: AssemblyVersion("3.4.0.0")]
+[assembly: AssemblyFileVersion("3.4.14.$WCREV$")]

branches/2521_ProblemRefactoring/HeuristicLab.Encodings.LinearLinkageEncoding/3.4/ShakingOperators/LLEShakingOperator.cs

r12650	r16692
1	1	#region License Information
2	2	/* HeuristicLab
3		* Copyright (C) 2002-2015 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
	3	* Copyright (C) 2002-2018 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
4	4	*
5	5	* This file is part of HeuristicLab.

Context Navigation

Legend:

Download in other formats: