Free cookie consent management tool by TermsFeed Policy Generator

# Changeset 12396

Ignore:
Timestamp:
05/21/15 16:30:14 (8 years ago)
Message:

Location:
Files:
7 edited

### Legend:

Unmodified
Removed

 r12288

 r12288 /// 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. /// Consider following 1-based index array: 6, 6, 7, 5, 5, 8, 8, 8, 9. /// This results in the following tree structure for group 8: ///      8 ///    /   \ ///   6     7 ///  / \ /// 1   2 ///  / \    | /// 1   2   3 /// After this operation the array will be 2, 3, 6, 5, 5, 7, 8, 8, 9. /// Representing a tree with one branch: 1 -> 2 -> 3 -> 6 -> 7 -> 8 /// /// /// 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 runtime complexity is O(n). /// /// The method assumes that there are no back links present. public void LinearizeTreeStructures() { // Step 1: Convert the array into LLE-e ToLLEeInplace(array); // Step 2: For all groups linearize the links FromLLEe(array); } /// /// Creates a copy of the underlying array and turns it into LLE-e. /// /// /// LLE-e is a special format where each element points to the /// ending item of a group. /// The LLE representation 2, 3, 5, 6, 5, 7, 8, 8 would become /// 5, 5, 5, 8, 5, 8, 8, 8 in LLE-e. /// /// This operation runs in O(n) time. /// /// An integer array in LLE-e representation public int[] ToLLEe() { var result = (int[])array.Clone(); ToLLEeInplace(result); return result; } private void ToLLEeInplace(int[] a) { var length = a.Length; for (var i = length - 1; i >= 0; i--) { if (array[i] == i) a[i] = i; else a[i] = a[a[i]]; } } /// /// Parses an LLE-e representation and modifies the underlying array /// so that it is in LLE representation. /// /// /// This operation runs in O(n) time, but requires additional memory /// in form of a dictionary. /// /// The LLE-e representation public void FromLLEe(int[] llee) { var length = array.Length; var groups = new Dictionary(); 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; if (llee[i] == i) { array[i] = i; groups[i] = i; } else { var g = llee[i]; array[i] = groups[g]; groups[g] = i; } } }

 r12288 using HeuristicLab.Common; using HeuristicLab.Core; using HeuristicLab.Data; using HeuristicLab.Parameters; using HeuristicLab.Persistence.Default.CompositeSerializers.Storable; public sealed class GraftManipulator : LinearLinkageManipulator { public IValueLookupParameter MaxGroupsParameter { get { return (IValueLookupParameter)Parameters["MaxGroups"]; } } [StorableConstructor] private GraftManipulator(bool deserializing) : base(deserializing) { } private GraftManipulator(GraftManipulator original, Cloner cloner) : base(original, cloner) { } public GraftManipulator() { Parameters.Add(new ValueLookupParameter("MaxGroups", "The maximum number of groups. If a value less or equal than 0 is used the number of groups is not limited.", new IntValue(-1))); } public GraftManipulator(int maxGroups) : this() { MaxGroupsParameter.Value = new IntValue(maxGroups); } public GraftManipulator() { } public override IDeepCloneable Clone(Cloner cloner) { } public static void Apply(IRandom random, LinearLinkage lle, int maxGroups) { public static void Apply(IRandom random, LinearLinkage lle) { int tries = lle.Length; var index = random.Next(lle.Length); tries--; } if (lle[index] != index) Apply(random, lle, maxGroups, index); if (lle[index] != index) Apply(random, lle, index); } public static void Apply(IRandom random, LinearLinkage lle, int maxGroups, int index) { public static void Apply(IRandom random, LinearLinkage lle, int index) { var groups = lle.Select((val, idx) => Tuple.Create(idx, val)) .Where(x => x.Item1 == x.Item2) protected override void Manipulate(IRandom random, LinearLinkage lle) { var maxGroups = MaxGroupsParameter.ActualValue.Value; Apply(random, lle, maxGroups <= 0 ? int.MaxValue : maxGroups); Apply(random, lle); } }