Changeset 12288 for branches/LinearLinkage/HeuristicLab.Encodings.LinearLinkageEncoding/3.3/LinearLinkage.cs

Timestamp:

04/06/15 22:41:24 (9 years ago)

Author:

abeham

Message:

#2319:

• Changed encoding to represent linkages in LLE (as opposed to LLE-e)
• Added GraftManipulator
• Added repair procedure
• Improved performance of some crossovers

File:

• branches/LinearLinkage/HeuristicLab.Encodings.LinearLinkageEncoding/3.3/LinearLinkage.cs (modified) (7 diffs)

branches/LinearLinkage/HeuristicLab.Encodings.LinearLinkageEncoding/3.3/LinearLinkage.cs

@@ -29 +29 @@
 
 namespace HeuristicLab.Encodings.LinearLinkageEncoding {
-  [Item("LinearLinkage", "Represents an LLE-e grouping of items.")]
+  [Item("LinearLinkage", "Represents an LLE grouping of items.")]
   [StorableClass]
   public sealed class LinearLinkage : IntArray {
@@ -45 +45 @@
 
     /// <summary>
-    /// This method parses the encoded array and calculates the membership of each element to the groups.
-    /// It starts at the lowest element.
-    /// </summary>
-    /// <remarks>
-    /// Runtime complexity of this method is O(n) where n is the length of the array.
+    /// This method parses the encoded array and calculates the membership of
+    /// each element to the groups. It starts at the lowest element.
+    /// </summary>
+    /// <remarks>
+    /// Runtime complexity of this method is O(n) where n is the length of the
+    /// array.
     /// </remarks>
     /// <returns>An enumeration of all groups.</returns>
     public IEnumerable<List<int>> GetGroups() {
       var len = array.Length;
-      var dict = new Dictionary<int, List<int>>();
-      for (var i = 0; i < len; i++) {
-        var end = array[i];
-        if (end < i || end >= len || array[end] != end)
-          throw new ArgumentException("Array is malformed and does not represent a valid LLE-e encoding.");
-        List<int> list;
-        if (!dict.TryGetValue(end, out list))
-          dict.Add(end, new List<int>() { i });
-        else list.Add(i);
-      }
-      return dict.Values;
-      /* This code implements group extraction from LLE forward encoding
-       * var len = array.Length;
       var remaining = new HashSet<int>(Enumerable.Range(0, len));
       // iterate from lowest to highest index
@@ -85 +73 @@
         }
         yield return group;
-      }*/
-    }
-
-    /// <summary>
-    /// This method parses the encoded array and gathers all items that belong to the same group as element <paramref name="index"/>.
+      }
+    }
+
+    /// <summary>
+    /// This method parses the encoded array and gathers all items that
+    /// belong to the same group as element <paramref name="index"/>.
     /// </summary>
     /// <param name="index">The element whose group should be returned.</param>
-    /// <returns>The element at <paramref name="index"/> and all other elements in the same group.</returns>
+    /// <returns>The element at <paramref name="index"/> and all other
+    /// elements in the same group.</returns>
     public IEnumerable<int> GetGroup(int index) {
-      yield return index;
-      var gn = array[index];
-      for (var i = index + 1; i <= gn; i++) {
-        if (array[i] == gn) yield return i;
-      }
-      for (var i = index - 1; i >= 0; i++) {
-        if (array[i] == gn) yield return i;
-      }
-      /* This code implements group extraction from LLE forward encoding
       // return current element
       yield return index;
@@ -120 +101 @@
         next = prev;
         yield return next;
-      }*/
-    }
-
-    /// <summary>
-    /// 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"/>.
-    /// </summary>
-    /// <param name="index">The element from which items in the group should be returned.</param>
-    /// <returns>The element at <paramref name="index"/> and all subsequent elements in the same group.</returns>
+      }
+    }
+
+    /// <summary>
+    /// 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"/>.
+    /// </summary>
+    /// <param name="index">The element from which items in the group should
+    /// be returned.</param>
+    /// <returns>The element at <paramref name="index"/> and all subsequent
+    /// elements in the same group.</returns>
     public IEnumerable<int> GetGroupForward(int index) {
-      yield return index;
-      var gn = array[index];
-      for (var i = index + 1; i <= gn; i++) {
-        if (array[i] == gn) yield return i;
-      }
-      /* This code implements group extraction from LLE forward encoding
       yield return index;
       var next = array[index];
@@ -143 +122 @@
         prev = next;
         next = array[next];
-      } while (next != prev);*/
-    }
-
-    /// <summary>
-    /// This method translates 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>
+      } while (next != prev);
+    }
+
+    /// <summary>
+    /// This method translates 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 void SetGroups(IEnumerable<IEnumerable<int>> grouping) {
-      var len = array.Length;
-      var remaining = new HashSet<int>(Enumerable.Range(0, len));
-      foreach (var group in grouping) {
-        var max = -1;
-        foreach (var g in group.OrderByDescending(x => x)) {
-          if (max < 0) max = g;
-          array[g] = max;
-          remaining.Remove(g);
-        }
-      }
-      if (remaining.Count > 0)
-        throw new ArgumentException(string.Format("Elements are not assigned a group: {0}", string.Join(", ", remaining)));
-      /* This code implements group setting for LLE forward encoding
       var len = array.Length;
       var remaining = new HashSet<int>(Enumerable.Range(0, len));
@@ -182 +150 @@
       if (remaining.Count > 0)
         throw new ArgumentException(string.Format("Elements are not assigned a group: {0}", string.Join(", ", remaining)));
-       */
-    }
-
-    /// <summary>
-    /// Performs a check whether the array represents a valid LLE-e encoding.
-    /// </summary>
-    /// <remarks>
-    /// The runtime complexity of this method is O(n) where n is the length of the array.
+    }
+
+    /// <summary>
+    /// Performs a check whether the array represents a valid LLE encoding.
+    /// </summary>
+    /// <remarks>
+    /// The runtime complexity of this method is O(n) where n is the length of
+    /// the array.
     /// </remarks>
     /// <returns>True if the encoding is valid.</returns>
     public bool Validate() {
-      var len = array.Length;
-      for (var i = 0; i < len; i++) {
-        var end = array[i];
-        if (end < i || end >= len || array[end] != end)
-          return false;
-      }
-      return true;
-      /* This code implements group setting for LLE forward encoding
       var len = array.Length;
       var remaining = new HashSet<int>(Enumerable.Range(0, len));
@@ -215 +175 @@
         } while (next != prev);
       }
-      return remaining.Count == 0;*/
+      return remaining.Count == 0;
+    }
+
+    /// <summary>
+    /// This method flattens tree structures that may be present in groups.
+    /// 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 example: 6, 6, 7, 5, 5, 8, 8, 8, 9.
+    /// This results in the following tree structure for group 8:
+    ///      8
+    ///    /   \
+    ///   6     7
+    ///  / \
+    /// 1   2
+    /// After this operation the array will be 2, 3, 6, 5, 5, 7, 8, 8, 9.
+    /// </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.
+    /// 
+    /// The method assumes that there are no back links present.
+    /// </remarks>
+    public void LinearizeTreeStructures() {
+      // Step 1: Convert the array into LLE-e
+      var length = array.Length;
+      var groups = new Dictionary<int, int>();
+      for (var i = length - 1; i >= 0; i--) {
+        if (array[i] == i) groups[i] = i;
+        else array[i] = array[array[i]];
+      }
+      // Step 2: For all groups linearize the links
+      for (var i = length - 1; i >= 0; i--) {
+        if (array[i] == i) continue;
+        var g = array[i];
+        array[i] = groups[g];
+        groups[g] = i;
+      }
     }
   }