Changeset 12396 for branches/LinearLinkage/HeuristicLab.Encodings.LinearLinkageEncoding/3.3/LinearLinkage.cs
 Timestamp:
 05/21/15 16:30:14 (7 years ago)
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

branches/LinearLinkage/HeuristicLab.Encodings.LinearLinkageEncoding/3.3/LinearLinkage.cs
r12288 r12396 182 182 /// These tree structures may be created by e.g. merging two groups by 183 183 /// linking one end node to the end node of another. 184 /// Consider following example: 6, 6, 7, 5, 5, 8, 8, 8, 9.184 /// Consider following 1based index array: 6, 6, 7, 5, 5, 8, 8, 8, 9. 185 185 /// This results in the following tree structure for group 8: 186 186 /// 8 187 187 /// / \ 188 188 /// 6 7 189 /// / \ 190 /// 1 2 189 /// / \  190 /// 1 2 3 191 191 /// After this operation the array will be 2, 3, 6, 5, 5, 7, 8, 8, 9. 192 /// Representing a tree with one branch: 1 > 2 > 3 > 6 > 7 > 8 192 193 /// </summary> 193 194 /// <remarks> … … 195 196 /// linearizes the links. This requires two passes of the whole array 196 197 /// as well as a dictionary to hold the smallest index of each group. 198 /// The runtime complexity is O(n). 197 199 /// 198 200 /// The method assumes that there are no back links present. … … 200 202 public void LinearizeTreeStructures() { 201 203 // Step 1: Convert the array into LLEe 204 ToLLEeInplace(array); 205 // Step 2: For all groups linearize the links 206 FromLLEe(array); 207 } 208 209 /// <summary> 210 /// Creates a copy of the underlying array and turns it into LLEe. 211 /// </summary> 212 /// <remarks> 213 /// LLEe is a special format where each element points to the 214 /// ending item of a group. 215 /// The LLE representation 2, 3, 5, 6, 5, 7, 8, 8 would become 216 /// 5, 5, 5, 8, 5, 8, 8, 8 in LLEe. 217 /// 218 /// This operation runs in O(n) time. 219 /// </remarks> 220 /// <returns>An integer array in LLEe representation</returns> 221 public int[] ToLLEe() { 222 var result = (int[])array.Clone(); 223 ToLLEeInplace(result); 224 return result; 225 } 226 227 private void ToLLEeInplace(int[] a) { 228 var length = a.Length; 229 for (var i = length  1; i >= 0; i) { 230 if (array[i] == i) a[i] = i; 231 else a[i] = a[a[i]]; 232 } 233 } 234 235 /// <summary> 236 /// Parses an LLEe representation and modifies the underlying array 237 /// so that it is in LLE representation. 238 /// </summary> 239 /// <remarks> 240 /// This operation runs in O(n) time, but requires additional memory 241 /// in form of a dictionary. 242 /// </remarks> 243 /// <param name="llee">The LLEe representation</param> 244 public void FromLLEe(int[] llee) { 202 245 var length = array.Length; 203 246 var groups = new Dictionary<int, int>(); 204 247 for (var i = length  1; i >= 0; i) { 205 if (array[i] == i) groups[i] = i; 206 else array[i] = array[array[i]]; 207 } 208 // Step 2: For all groups linearize the links 209 for (var i = length  1; i >= 0; i) { 210 if (array[i] == i) continue; 211 var g = array[i]; 212 array[i] = groups[g]; 213 groups[g] = i; 248 if (llee[i] == i) { 249 array[i] = i; 250 groups[i] = i; 251 } else { 252 var g = llee[i]; 253 array[i] = groups[g]; 254 groups[g] = i; 255 } 214 256 } 215 257 }
Note: See TracChangeset
for help on using the changeset viewer.