Ignore:
Timestamp:
05/21/15 16:30:14 (7 years ago)
Author:
abeham
Message:

#2319: Added SinglePointCrossover

File:
1 edited

Legend:

Unmodified
Added
Removed
  • branches/LinearLinkage/HeuristicLab.Encodings.LinearLinkageEncoding/3.3/LinearLinkage.cs

    r12288 r12396  
    182182    /// These tree structures may be created by e.g. merging two groups by
    183183    /// 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 1-based index array: 6, 6, 7, 5, 5, 8, 8, 8, 9.
    185185    /// This results in the following tree structure for group 8:
    186186    ///      8
    187187    ///    /   \
    188188    ///   6     7
    189     ///  / \
    190     /// 1   2
     189    ///  / \    |
     190    /// 1   2   3
    191191    /// 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
    192193    /// </summary>
    193194    /// <remarks>
     
    195196    /// linearizes the links. This requires two passes of the whole array
    196197    /// as well as a dictionary to hold the smallest index of each group.
     198    /// The runtime complexity is O(n).
    197199    ///
    198200    /// The method assumes that there are no back links present.
     
    200202    public void LinearizeTreeStructures() {
    201203      // Step 1: Convert the array into LLE-e
     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 LLE-e.
     211    /// </summary>
     212    /// <remarks>
     213    /// LLE-e 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 LLE-e.
     217    ///
     218    /// This operation runs in O(n) time.
     219    /// </remarks>
     220    /// <returns>An integer array in LLE-e 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 LLE-e 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 LLE-e representation</param>
     244    public void FromLLEe(int[] llee) {
    202245      var length = array.Length;
    203246      var groups = new Dictionary<int, int>();
    204247      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        }
    214256      }
    215257    }
Note: See TracChangeset for help on using the changeset viewer.