Changeset 12288 for branches/LinearLinkage/HeuristicLab.Encodings.LinearLinkageEncoding/3.3/LinearLinkage.cs
- Timestamp:
- 04/06/15 22:41:24 (9 years ago)
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
branches/LinearLinkage/HeuristicLab.Encodings.LinearLinkageEncoding/3.3/LinearLinkage.cs
r12285 r12288 29 29 30 30 namespace HeuristicLab.Encodings.LinearLinkageEncoding { 31 [Item("LinearLinkage", "Represents an LLE -egrouping of items.")]31 [Item("LinearLinkage", "Represents an LLE grouping of items.")] 32 32 [StorableClass] 33 33 public sealed class LinearLinkage : IntArray { … … 45 45 46 46 /// <summary> 47 /// This method parses the encoded array and calculates the membership of each element to the groups. 48 /// It starts at the lowest element. 49 /// </summary> 50 /// <remarks> 51 /// Runtime complexity of this method is O(n) where n is the length of the array. 47 /// This method parses the encoded array and calculates the membership of 48 /// each element to the groups. It starts at the lowest element. 49 /// </summary> 50 /// <remarks> 51 /// Runtime complexity of this method is O(n) where n is the length of the 52 /// array. 52 53 /// </remarks> 53 54 /// <returns>An enumeration of all groups.</returns> 54 55 public IEnumerable<List<int>> GetGroups() { 55 56 var len = array.Length; 56 var dict = new Dictionary<int, List<int>>();57 for (var i = 0; i < len; i++) {58 var end = array[i];59 if (end < i || end >= len || array[end] != end)60 throw new ArgumentException("Array is malformed and does not represent a valid LLE-e encoding.");61 List<int> list;62 if (!dict.TryGetValue(end, out list))63 dict.Add(end, new List<int>() { i });64 else list.Add(i);65 }66 return dict.Values;67 /* This code implements group extraction from LLE forward encoding68 * var len = array.Length;69 57 var remaining = new HashSet<int>(Enumerable.Range(0, len)); 70 58 // iterate from lowest to highest index … … 85 73 } 86 74 yield return group; 87 }*/ 88 } 89 90 /// <summary> 91 /// This method parses the encoded array and gathers all items that belong to the same group as element <paramref name="index"/>. 75 } 76 } 77 78 /// <summary> 79 /// This method parses the encoded array and gathers all items that 80 /// belong to the same group as element <paramref name="index"/>. 92 81 /// </summary> 93 82 /// <param name="index">The element whose group should be returned.</param> 94 /// <returns>The element at <paramref name="index"/> and all other elements in the same group.</returns> 83 /// <returns>The element at <paramref name="index"/> and all other 84 /// elements in the same group.</returns> 95 85 public IEnumerable<int> GetGroup(int index) { 96 yield return index;97 var gn = array[index];98 for (var i = index + 1; i <= gn; i++) {99 if (array[i] == gn) yield return i;100 }101 for (var i = index - 1; i >= 0; i++) {102 if (array[i] == gn) yield return i;103 }104 /* This code implements group extraction from LLE forward encoding105 86 // return current element 106 87 yield return index; … … 120 101 next = prev; 121 102 yield return next; 122 }*/ 123 } 124 125 /// <summary> 126 /// This method parses the encoded array and gathers the item itself as well as subsequent items that belong to the same group as element <paramref name="index"/>. 127 /// </summary> 128 /// <param name="index">The element from which items in the group should be returned.</param> 129 /// <returns>The element at <paramref name="index"/> and all subsequent elements in the same group.</returns> 103 } 104 } 105 106 /// <summary> 107 /// This method parses the encoded array and gathers the item itself as 108 /// well as subsequent items that belong to the same group as element 109 /// <paramref name="index"/>. 110 /// </summary> 111 /// <param name="index">The element from which items in the group should 112 /// be returned.</param> 113 /// <returns>The element at <paramref name="index"/> and all subsequent 114 /// elements in the same group.</returns> 130 115 public IEnumerable<int> GetGroupForward(int index) { 131 yield return index;132 var gn = array[index];133 for (var i = index + 1; i <= gn; i++) {134 if (array[i] == gn) yield return i;135 }136 /* This code implements group extraction from LLE forward encoding137 116 yield return index; 138 117 var next = array[index]; … … 143 122 prev = next; 144 123 next = array[next]; 145 } while (next != prev);*/ 146 } 147 148 /// <summary> 149 /// This method translates an enumeration of groups into the underlying array representation. 150 /// </summary> 151 /// <remarks> 152 /// Throws an ArgumentException when there is an element assigned to multiple groups or elements that 153 /// are not assigned to any group. 154 /// </remarks> 155 /// <param name="grouping">The grouping of the elements, each element must be part of exactly one group.</param> 124 } while (next != prev); 125 } 126 127 /// <summary> 128 /// This method translates an enumeration of groups into the underlying 129 /// array representation. 130 /// </summary> 131 /// <remarks> 132 /// Throws an ArgumentException when there is an element assigned to 133 /// multiple groups or elements that are not assigned to any group. 134 /// </remarks> 135 /// <param name="grouping">The grouping of the elements, each element must 136 /// be part of exactly one group.</param> 156 137 public void SetGroups(IEnumerable<IEnumerable<int>> grouping) { 157 var len = array.Length;158 var remaining = new HashSet<int>(Enumerable.Range(0, len));159 foreach (var group in grouping) {160 var max = -1;161 foreach (var g in group.OrderByDescending(x => x)) {162 if (max < 0) max = g;163 array[g] = max;164 remaining.Remove(g);165 }166 }167 if (remaining.Count > 0)168 throw new ArgumentException(string.Format("Elements are not assigned a group: {0}", string.Join(", ", remaining)));169 /* This code implements group setting for LLE forward encoding170 138 var len = array.Length; 171 139 var remaining = new HashSet<int>(Enumerable.Range(0, len)); … … 182 150 if (remaining.Count > 0) 183 151 throw new ArgumentException(string.Format("Elements are not assigned a group: {0}", string.Join(", ", remaining))); 184 */185 } 186 187 /// <summary>188 /// Performs a check whether the array represents a valid LLE-e encoding.189 /// < /summary>190 /// <remarks>191 /// The runtime complexity of this method is O(n) where n is the length ofthe array.152 } 153 154 /// <summary> 155 /// Performs a check whether the array represents a valid LLE encoding. 156 /// </summary> 157 /// <remarks> 158 /// The runtime complexity of this method is O(n) where n is the length of 159 /// the array. 192 160 /// </remarks> 193 161 /// <returns>True if the encoding is valid.</returns> 194 162 public bool Validate() { 195 var len = array.Length;196 for (var i = 0; i < len; i++) {197 var end = array[i];198 if (end < i || end >= len || array[end] != end)199 return false;200 }201 return true;202 /* This code implements group setting for LLE forward encoding203 163 var len = array.Length; 204 164 var remaining = new HashSet<int>(Enumerable.Range(0, len)); … … 215 175 } while (next != prev); 216 176 } 217 return remaining.Count == 0;*/ 177 return remaining.Count == 0; 178 } 179 180 /// <summary> 181 /// This method flattens tree structures that may be present in groups. 182 /// These tree structures may be created by e.g. merging two groups by 183 /// linking one end node to the end node of another. 184 /// Consider following example: 6, 6, 7, 5, 5, 8, 8, 8, 9. 185 /// This results in the following tree structure for group 8: 186 /// 8 187 /// / \ 188 /// 6 7 189 /// / \ 190 /// 1 2 191 /// After this operation the array will be 2, 3, 6, 5, 5, 7, 8, 8, 9. 192 /// </summary> 193 /// <remarks> 194 /// The method first converts the array to LLE-e format and then 195 /// linearizes the links. This requires two passes of the whole array 196 /// as well as a dictionary to hold the smallest index of each group. 197 /// 198 /// The method assumes that there are no back links present. 199 /// </remarks> 200 public void LinearizeTreeStructures() { 201 // Step 1: Convert the array into LLE-e 202 var length = array.Length; 203 var groups = new Dictionary<int, int>(); 204 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; 214 } 218 215 } 219 216 }
Note: See TracChangeset
for help on using the changeset viewer.