Free cookie consent management tool by TermsFeed Policy Generator

Ignore:
Timestamp:
12/14/16 20:45:46 (7 years ago)
Author:
abeham
Message:

#2701:

  • Updated LLE encoding
    • Made folder for version 3.4
    • Added conversion from and to LLE-b representation (back-links)
    • Updated moves and movegenerator to replace bidirectionaldictionary with LLE-b representation
  • Updated MemPR (linear linkage)
    • Updated tabu walk
  • Added test for conversion between LLE-e and LLE and LLE-b and LLE
  • Updated test for move apply/undo and added test for applying in sequence
Location:
branches/MemPRAlgorithm/HeuristicLab.Encodings.LinearLinkageEncoding/3.4
Files:
1 deleted
8 edited
1 moved

Legend:

Unmodified
Added
Removed

  • branches/MemPRAlgorithm/HeuristicLab.Encodings.LinearLinkageEncoding/3.4/HeuristicLab.Encodings.LinearLinkageEncoding-3.4.csproj

    r14487 r14492  
    176176    <Compile Include="Manipulators\MergeGroupManipulator.cs" />
    177177    <Compile Include="Manipulators\MultiLLEManipulator.cs" />
     178    <Compile Include="Moves\ExtractMove.cs" />
     179    <Compile Include="Moves\MergeMove.cs" />
     180    <Compile Include="Moves\Move.cs" />
     181    <Compile Include="Moves\ShiftMove.cs" />
     182    <Compile Include="Moves\SplitMove.cs" />
     183    <Compile Include="Moves\StaticAPI\MoveGenerator.cs" />
    178184    <Compile Include="Moves\Swap\ExhaustiveSwap2MoveGenerator.cs" />
    179185    <Compile Include="Moves\Swap\StochasticSwap2MultiMoveGenerator.cs" />

  • branches/MemPRAlgorithm/HeuristicLab.Encodings.LinearLinkageEncoding/3.4/LinearLinkage.cs

    r14487 r14492  
    5959    /// and throws an ArgumentException otherwise.
    6060    /// </remarks>
     61    /// <exception cref="ArgumentException">If <paramref name="lle"/> does not represent a valid LLE array.</exception>
    6162    /// <param name="lle">The LLE representation</param>
     63    /// <returns>The linear linkage encoding in LLE format (with forward-links).</returns>
    6264    public static LinearLinkage FromForwardLinks(int[] lle) {
    63       if (!Validate(lle)) {
     65      if (!Validate(lle))
    6466        throw new ArgumentException("Array is malformed and does not represent a valid LLE forward encoding.", "elements");
    65       }
    6667      return new LinearLinkage(lle);
     68    }
     69
     70    /// <summary>
     71    /// Create a new LinearLinkage object by parsing a LLE-b representation
     72    /// and modifing the underlying array so that it is in LLE representation.
     73    /// </summary>
     74    /// <remarks>
     75    /// This operation runs in O(n) time, the parameter <paramref name="lleb"/> is not modified.
     76    /// </remarks>
     77    /// <exception cref="ArgumentException">If <paramref name="lleb"/> does not represent a valid LLE-b array.</exception>
     78    /// <param name="lleb">The LLE-b representation (LLE with back-links)</param>
     79    /// <returns>The linear linkage encoding in LLE format (with forward-links).</returns>
     80    public static LinearLinkage FromBackLinks(int[] lleb) {
     81      var result = new LinearLinkage(lleb.Length);
     82      for (var i = lleb.Length - 1; i > 0; i--) {
     83        if (lleb[i] == i) {
     84          if (result[i] == 0) result[i] = i;
     85          continue;
     86        }
     87        result[lleb[i]] = i;
     88        if (result[i] == 0) result[i] = i;
     89      }
     90      if (!Validate(result.array))
     91        throw new ArgumentException("Array is malformed and does not represent a valid LLE-b encoding (with back-links).", "lleb");
     92      return result;
    6793    }
    6894
    … …  
    76102    /// </remarks>
    77103    /// <param name="llee">The LLE-e representation</param>
    78     /// <returns>LinearLinkage</returns>
     104    /// <returns>The linear linkage encoding in LLE format (with forward-links).</returns>
    79105    public static LinearLinkage FromEndLinks(int[] llee) {
    80106      var result = new LinearLinkage(llee.Length);
    … …  
    111137    /// array.
    112138    /// </remarks>
     139    /// <exception cref="InvalidOperationException">If this object is not vaild LLE.</exception>
    113140    /// <returns>An enumeration of all groups.</returns>
    114141    public IEnumerable<List<int>> GetGroups() {
    … …  
    126153          group.Add(curr);
    127154        }
    128         if (curr != next) throw new ArgumentException("Array is malformed and does not represent a valid LLE forward encoding.");
     155        if (curr != next) throw new InvalidOperationException("Array is malformed and does not represent a valid LLE forward encoding.");
    129156        used[curr] = true;
    130157        yield return group;
    131158      }
    132       /*
    133       var len = array.Length;
    134       var used = new bool[len];
    135       // iterate from lowest to highest index
    136       for (var i = 0; i < len; i++) {
    137         if (used[i]) continue;
    138         var group = new List<int> { i };
    139         used[i] = true;
    140         var next = array[i];
    141         if (next < i || next >= len) {
    142           throw new ArgumentException("Array is malformed and does not represent a valid LLE forward encoding.");
    143         }
    144         while (next != array[next]) {
    145           if (next < 0 || next >= len || used[next]) {
    146             throw new ArgumentException("Array is malformed and does not represent a valid LLE forward encoding.");
    147           }
    148           group.Add(next);
    149           used[next] = true;
    150           next = array[next];
    151         }
    152         yield return group;
    153       }*/
    154159    }
    155160
    … …  
    227232    /// <param name="grouping">The grouping of the elements, each element must
    228233    /// be part of exactly one group.</param>
     234    /// <exception cref="ArgumentException">If <paramref name="grouping"/> cannot be converted
     235    /// to a valid LLE representation. For instance, because elements are too big or too small,
     236    /// or they're contained in multiple groups, or there are elements not assigned to any group.
     237    /// </exception>
    229238    public void SetGroups(IEnumerable<IEnumerable<int>> grouping) {
    230239      var len = array.Length;
    … …  
    281290    /// These tree structures may be created by e.g. merging two groups by
    282291    /// linking one end node to the end node of another.
    283     /// Consider following 1-based index array: 6, 6, 7, 5, 5, 8, 8, 8, 9.
    284     /// This results in the following tree structure for group 8:
    285     ///      8
     292    /// Consider following array: 5, 5, 6, 4, 4, 7, 7, 7, 8.
     293    /// This results in the following tree structure for group 7:
     294    ///      7
    286295    ///    /   \
    287     ///   6     7
     296    ///   5     6
    288297    ///  / \    |
    289     /// 1   2   3
    290     /// After this operation the array will be 2, 3, 6, 5, 5, 7, 8, 8, 9.
    291     /// Representing a tree with one branch: 1 -> 2 -> 3 -> 6 -> 7 -> 8
     298    /// 0   1   2
     299    /// After this operation the array will be 1, 2, 5, 4, 4, 6, 7, 7, 8.
     300    /// Representing a tree with one branch: 0 -> 1 -> 2 -> 5 -> 6 -> 7.
    292301    /// </summary>
    293302    /// <remarks>
    294303    /// The method first converts the array to LLE-e format and then
    295304    /// linearizes the links. This requires two passes of the whole array
    296     /// as well as a dictionary to hold the smallest index of each group.
     305    /// as well as another copy of the underlying array.
    297306    /// The runtime complexity is O(n).
    298307    ///
    … …  
    312321    /// LLE-e is a special format where each element points to the
    313322    /// ending item of a group.
    314     /// The LLE representation 2, 3, 5, 6, 5, 7, 8, 8 would become
    315     /// 5, 5, 5, 8, 5, 8, 8, 8 in LLE-e.
     323    /// The LLE representation 1, 2, 4, 5, 4, 6, 7, 7 would become
     324    /// 4, 4, 4, 7, 4, 7, 7, 7 in LLE-e.
    316325    ///
    317326    /// This operation runs in O(n) time.
    318327    /// </remarks>
     328    /// <exception cref="ArgumentException">In case, this object does not
     329    /// represent a valid LLE encoding.
     330    /// </exception>
    319331    /// <returns>An integer array in LLE-e representation</returns>
    320332    public int[] ToEndLinks() {
    … …  
    345357    /// </remarks>
    346358    /// <param name="llee">The LLE-e representation</param>
     359    /// <exception cref="ArgumentException">
     360    /// If <paramref name="llee"/> does not contain a valid LLE-e representation or
     361    /// has a different length to the given instance.
     362    /// </exception>
    347363    public void SetEndLinks(int[] llee) {
    348364      var length = array.Length;
    … …  
    360376          lookup[end] = i;
    361377        } else {
    362           throw new ArgumentException("Array is malformed and does not represent a valid LLE end encoding.", "llee");
    363         }
    364       }
     378          throw new ArgumentException("Array is malformed and does not represent a valid LLE-e end encoding.", "llee");
     379        }
     380      }
     381    }
     382
     383    /// <summary>
     384    /// Creates a copy of the underlying array and turns it into LLE-b.
     385    /// </summary>
     386    /// <remarks>
     387    /// LLE-b is a special format where each element points to the
     388    /// predecessor instead of the successor.
     389    /// The LLE representation 1, 2, 4, 5, 4, 6, 7, 7
     390    /// would become           0, 0, 1, 3, 2, 3, 5, 6 in LLE-b.
     391    ///
     392    /// This operation runs in O(n) time.
     393    /// </remarks>
     394    /// <returns>An integer array in LLE-b representation</returns>
     395    public int[] ToBackLinks() {
     396      var result = new int[array.Length];
     397      var zeroLink = array[0];
     398      for (var i = 0; i < array.Length; i++) {
     399        if (array[i] == i) {
     400          if (result[i] == 0 && i != zeroLink) result[i] = i;
     401          continue;
     402        }
     403        result[array[i]] = i;
     404        if (result[i] == 0 && i != zeroLink) result[i] = i;
     405      }
     406      return result;
    365407    }
    366408  }

  • branches/MemPRAlgorithm/HeuristicLab.Encodings.LinearLinkageEncoding/3.4/Moves/ExtractMove.cs

    r14477 r14492  
    2121
    2222using System;
    23 using HeuristicLab.Collections;
    2423
    2524namespace HeuristicLab.Encodings.LinearLinkageEncoding {
    … …  
    4140        || lle[Item] != NextItem)
    4241        throw new ArgumentException("Move conditions have changed!");
    43       if (!IsFirst)
    44         lle[PreviousItem] = IsLast ? PreviousItem : NextItem;
     42      if (!IsFirst) lle[PreviousItem] = IsLast ? PreviousItem : NextItem;
    4543      lle[Item] = Item;
    4644    }
    … …  
    5149        throw new ArgumentException("Move conditions have changed, cannot undo move.");
    5250
    53       if (!IsFirst)
    54         lle[PreviousItem] = Item;
     51      if (!IsFirst) lle[PreviousItem] = Item;
    5552      lle[Item] = NextItem;
    5653    }
    5754
    58     public override void UpdateLinks(BidirectionalDictionary<int, int> links) {
    59       if (!IsFirst) {
    60         links.RemoveBySecond(Item);
    61         links.SetByFirst(PreviousItem, IsLast ? PreviousItem : NextItem);
    62       }
     55    public override void ApplyToLLEb(int[] lleb) {
     56      if (!IsLast) lleb[NextItem] = IsFirst ? NextItem : PreviousItem;
     57      lleb[Item] = Item;
    6358    }
    6459  }

  • branches/MemPRAlgorithm/HeuristicLab.Encodings.LinearLinkageEncoding/3.4/Moves/MergeMove.cs

    r14477 r14492  
    2121
    2222using System;
    23 using HeuristicLab.Collections;
    2423
    2524namespace HeuristicLab.Encodings.LinearLinkageEncoding {
    … …  
    2726
    2827    public int LastItemOfOtherGroup { get; private set; }
    29     private int nextItemOfOtherGroup; // undo information
    3028
    3129    public MergeMove(int item, int lastOfOther) {
    3230      Item = item;
    3331      LastItemOfOtherGroup = lastOfOther;
    34       nextItemOfOtherGroup = -1;
    3532    }
    3633
    3734    public override void Apply(LinearLinkage lle) {
    3835      if (lle[LastItemOfOtherGroup] != LastItemOfOtherGroup) throw new ArgumentException("Move conditions have changed, group does not terminate at " + LastItemOfOtherGroup);
    39       nextItemOfOtherGroup = lle[LastItemOfOtherGroup];
    4036      lle[LastItemOfOtherGroup] = Item;
    4137    }
    … …  
    4339    public override void Undo(LinearLinkage lle) {
    4440      if (lle[LastItemOfOtherGroup] != Item) throw new ArgumentException("Move conditions have changed, groups are no longer linked between " + LastItemOfOtherGroup + " and " + Item);
    45       if (nextItemOfOtherGroup < 0) throw new InvalidOperationException("Cannot undo move that has not been applied first.");
    46       lle[LastItemOfOtherGroup] = nextItemOfOtherGroup;
     41      lle[LastItemOfOtherGroup] = LastItemOfOtherGroup;
    4742    }
    4843
    49     public override void UpdateLinks(BidirectionalDictionary<int, int> links) {
    50       if (nextItemOfOtherGroup < 0) throw new InvalidOperationException("Cannot update links for move that has not been applied first.");
    51       links.RemoveBySecond(nextItemOfOtherGroup);
     44    public override void ApplyToLLEb(int[] lleb) {
     45      lleb[Item] = LastItemOfOtherGroup;
    5246    }
    5347  }

  • branches/MemPRAlgorithm/HeuristicLab.Encodings.LinearLinkageEncoding/3.4/Moves/Move.cs

    r14477 r14492  
    2929    public abstract void Undo(LinearLinkage lle);
    3030
    31     public abstract void UpdateLinks(BidirectionalDictionary<int, int> links);
     31    public abstract void ApplyToLLEb(int[] lleb);
    3232  }
    3333}

  • branches/MemPRAlgorithm/HeuristicLab.Encodings.LinearLinkageEncoding/3.4/Moves/ShiftMove.cs

    r14477 r14492  
    6565    }
    6666
    67     public override void UpdateLinks(BidirectionalDictionary<int, int> links) {
    68       links.RemoveBySecond(Item);
    69       links.SetByFirst(PreviousItemOfNewGroup, Item);
    70       if (!IsFirst) links.SetByFirst(PreviousItemOfOldGroup, IsLast ? PreviousItemOfOldGroup : NextItemOfOldGroup);
     67    public override void ApplyToLLEb(int[] lleb) {
     68      if (!IsLast)
     69        lleb[NextItemOfOldGroup] = IsFirst ? NextItemOfOldGroup : PreviousItemOfOldGroup;
     70      lleb[Item] = PreviousItemOfNewGroup;
     71      if (!NewGroupClosed)
     72        lleb[NextItemOfNewGroup] = Item;
    7173    }
    7274  }

  • branches/MemPRAlgorithm/HeuristicLab.Encodings.LinearLinkageEncoding/3.4/Moves/SplitMove.cs

    r14477 r14492  
    2121
    2222using System;
    23 using HeuristicLab.Collections;
    2423
    2524namespace HeuristicLab.Encodings.LinearLinkageEncoding {
    … …  
    4544    }
    4645
    47     public override void UpdateLinks(BidirectionalDictionary<int, int> links) {
    48       // nothing has to be done
     46    public override void ApplyToLLEb(int[] lleb) {
     47      if (nextItem < 0) throw new InvalidOperationException("Cannot undo move that has not been applied first to LLE.");
     48      lleb[nextItem] = nextItem;
    4949    }
    5050  }

  • branches/MemPRAlgorithm/HeuristicLab.Encodings.LinearLinkageEncoding/3.4/Moves/StaticAPI/MoveGenerator.cs

    r14487 r14492  
    2626namespace HeuristicLab.Encodings.LinearLinkageEncoding {
    2727  public static class MoveGenerator {
    28     public static IEnumerable<Move> GenerateForItem(int i, int next, BidirectionalDictionary<int, int> links) {
    29       var pred = -1;
    30       var isFirst = !links.TryGetBySecond(i, out pred);
     28    public static IEnumerable<Move> GenerateForItem(int i, List<int> groupItems, LinearLinkage lle, int[] lleb) {
     29      var pred = lleb[i];
     30      var next = lle[i];
     31      var isFirst = pred == i;
    3132      var isLast = next == i;
    3233
    3334      // First: shift i into each previous group
    34       foreach (var l in links.Where(x => x.Value != i)) {
    35         yield return new ShiftMove(i, isFirst ? i : pred, l.Key, next, l.Value);
     35      foreach (var m in groupItems.Where(x => lle[x] != i)) {
     36        yield return new ShiftMove(i, pred, m, next, lle[m]);
    3637      }
    3738
    … …  
    4243        if (isFirst) {
    4344          // Third: merge with closed groups
    44           foreach (var l in links.Where(x => x.Key == x.Value)) {
    45             yield return new MergeMove(i, l.Key);
     45          foreach (var m in groupItems.Where(x => lle[x] == x)) {
     46            yield return new MergeMove(i, m);
    4647          }
    4748        } else {
    48           // Fourth: extract i into group of its own (exclude first, because of Second)
     49          // Fourth: extract i into group of its own (exclude first and last, because of SplitMove)
    4950          yield return new ExtractMove(i, pred, next);
    5051        }
    … …  
    5556
    5657    public static IEnumerable<Move> Generate(LinearLinkage lle) {
    57       var links = new BidirectionalDictionary<int, int>();
     58      var groupItems = new List<int>();
     59      var lleb = lle.ToBackLinks();
    5860      for (var i = 0; i < lle.Length; i++) {
    59         foreach (var move in GenerateForItem(i, lle[i], links))
     61        foreach (var move in GenerateForItem(i, groupItems, lle, lleb))
    6062          yield return move;
    61         links.RemoveBySecond(i);
    62         links.Add(i, lle[i]);
     63        if (lleb[i] != i)
     64          groupItems.Remove(lleb[i]);
     65        groupItems.Add(i);
    6366      }
    6467    }
Note: See TracChangeset for help on using the changeset viewer.