Changeset 14487 for branches/MemPRAlgorithm/HeuristicLab.Encodings.LinearLinkageEncoding/3.3/LinearLinkage.cs
- Timestamp:
- 12/14/16 10:16:50 (7 years ago)
- 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.LinearLinkageEncoding merged eligible /stable/HeuristicLab.Encodings.LinearLinkageEncoding merged eligible /trunk/sources/HeuristicLab.Encodings.LinearLinkageEncoding merged eligible /branches/1721-RandomForestPersistence/HeuristicLab.Encodings.LinearLinkageEncoding 10321-10322 /branches/Algorithms.GradientDescent/HeuristicLab.Encodings.LinearLinkageEncoding 5516-5520 /branches/Benchmarking/sources/HeuristicLab.Encodings.LinearLinkageEncoding 6917-7005 /branches/CloningRefactoring/HeuristicLab.Encodings.LinearLinkageEncoding 4656-4721 /branches/CodeEditor/HeuristicLab.Encodings.LinearLinkageEncoding 11700-11806 /branches/DataAnalysis Refactoring/HeuristicLab.Encodings.LinearLinkageEncoding 5471-5808 /branches/DataAnalysis SolutionEnsembles/HeuristicLab.Encodings.LinearLinkageEncoding 5815-6180 /branches/DataAnalysis/HeuristicLab.Encodings.LinearLinkageEncoding 4458-4459,4462,4464 /branches/DataPreprocessing/HeuristicLab.Encodings.LinearLinkageEncoding 10085-11101 /branches/GP.Grammar.Editor/HeuristicLab.Encodings.LinearLinkageEncoding 6284-6795 /branches/GP.Symbols (TimeLag, Diff, Integral)/HeuristicLab.Encodings.LinearLinkageEncoding 5060 /branches/HLScript/HeuristicLab.Encodings.LinearLinkageEncoding 10331-10358 /branches/HeuristicLab.DatasetRefactor/sources/HeuristicLab.Encodings.LinearLinkageEncoding 11570-12508 /branches/HeuristicLab.Problems.DataAnalysis.Trading/HeuristicLab.Encodings.LinearLinkageEncoding 6123-9799 /branches/HeuristicLab.Problems.Orienteering/HeuristicLab.Encodings.LinearLinkageEncoding 11130-12721 /branches/HiveStatistics/sources/HeuristicLab.Encodings.LinearLinkageEncoding 12440-12877 /branches/LogResidualEvaluator/HeuristicLab.Encodings.LinearLinkageEncoding 10202-10483 /branches/NET40/sources/HeuristicLab.Encodings.LinearLinkageEncoding 5138-5162 /branches/NSGA-II Changes/HeuristicLab.Encodings.LinearLinkageEncoding 12033-12122 /branches/ParallelEngine/HeuristicLab.Encodings.LinearLinkageEncoding 5175-5192 /branches/ProblemInstancesRegressionAndClassification/HeuristicLab.Encodings.LinearLinkageEncoding 7568-7810 /branches/QAPAlgorithms/HeuristicLab.Encodings.LinearLinkageEncoding 6350-6627 /branches/Restructure trunk solution/HeuristicLab.Encodings.LinearLinkageEncoding 6828 /branches/RuntimeOptimizer/HeuristicLab.Encodings.LinearLinkageEncoding 8943-9078 /branches/ScatterSearch (trunk integration)/HeuristicLab.Encodings.LinearLinkageEncoding 7787-8333 /branches/SlaveShutdown/HeuristicLab.Encodings.LinearLinkageEncoding 8944-8956 /branches/SpectralKernelForGaussianProcesses/HeuristicLab.Encodings.LinearLinkageEncoding 10204-10479 /branches/SuccessProgressAnalysis/HeuristicLab.Encodings.LinearLinkageEncoding 5370-5682 /branches/Trunk/HeuristicLab.Encodings.LinearLinkageEncoding 6829-6865 /branches/UnloadJobs/HeuristicLab.Encodings.LinearLinkageEncoding 9168-9215 /branches/VNS/HeuristicLab.Encodings.LinearLinkageEncoding 5594-5752 /branches/histogram/HeuristicLab.Encodings.LinearLinkageEncoding 5959-6341
-
Property
svn:mergeinfo
set to
(toggle deleted branches)
-
branches/MemPRAlgorithm/HeuristicLab.Encodings.LinearLinkageEncoding/3.3/LinearLinkage.cs
r14185 r14487 37 37 private LinearLinkage(LinearLinkage original, Cloner cloner) : base(original, cloner) { } 38 38 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 } 41 100 42 101 public override IDeepCloneable Clone(Cloner cloner) { … … 55 114 public IEnumerable<List<int>> GetGroups() { 56 115 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]; 58 135 // iterate from lowest to highest index 59 136 for (var i = 0; i < len; i++) { 60 if ( !remaining.Contains(i)) continue;137 if (used[i]) continue; 61 138 var group = new List<int> { i }; 62 remaining.Remove(i);139 used[i] = true; 63 140 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]; 73 151 } 74 152 yield return group; 75 } 153 }*/ 76 154 } 77 155 … … 151 229 public void SetGroups(IEnumerable<IEnumerable<int>> grouping) { 152 230 var len = array.Length; 153 var remaining = new HashSet<int>(Enumerable.Range(0, len));231 var used = new bool[len]; 154 232 foreach (var group in grouping) { 155 233 var prev = -1; 156 234 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"); 157 236 if (prev >= 0) array[prev] = g; 158 237 prev = g; 159 if ( !remaining.Remove(prev))238 if (used[prev]) { 160 239 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)))); 166 247 } 167 248 … … 175 256 /// <returns>True if the encoding is valid.</returns> 176 257 public bool Validate() { 258 return Validate(array); 259 } 260 261 private static bool Validate(int[] array) { 177 262 var len = array.Length; 178 var remaining = new HashSet<int>(Enumerable.Range(0, len));263 var used = new bool[len]; 179 264 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; 188 271 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; 192 277 } 193 278 … … 216 301 public void LinearizeTreeStructures() { 217 302 // Step 1: Convert the array into LLE-e 218 To LLEeInplace(array);303 ToEndLinksInplace(array); 219 304 // Step 2: For all groups linearize the links 220 FromLLEe(array);305 SetEndLinks(array); 221 306 } 222 307 … … 233 318 /// </remarks> 234 319 /// <returns>An integer array in LLE-e representation</returns> 235 public int[] To LLEe() {320 public int[] ToEndLinks() { 236 321 var result = (int[])array.Clone(); 237 To LLEeInplace(result);322 ToEndLinksInplace(result); 238 323 return result; 239 324 } 240 325 241 private void ToLLEeInplace(int[] a) {242 var length = a .Length;326 private static void ToEndLinksInplace(int[] array) { 327 var length = array.Length; 243 328 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 } 246 335 } 247 336 } … … 253 342 /// <remarks> 254 343 /// This operation runs in O(n) time, but requires additional memory 255 /// in form of a dictionary.344 /// in form of a int[]. 256 345 /// </remarks> 257 346 /// <param name="llee">The LLE-e representation</param> 258 public void FromLLEe(int[] llee) {347 public void SetEndLinks(int[] llee) { 259 348 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(); 261 354 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; 265 361 } 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"); 269 363 } 270 364 }
Note: See TracChangeset
for help on using the changeset viewer.