source: branches/MemPRAlgorithm/HeuristicLab.Encodings.LinearLinkageEncoding/3.4/LinearLinkage.cs @ 14492

Last change on this file since 14492 was 14492, checked in by abeham, 4 years ago

#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
File size: 15.9 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2016 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
4 *
5 * This file is part of HeuristicLab.
6 *
7 * HeuristicLab is free software: you can redistribute it and/or modify
8 * it under the terms of the GNU General Public License as published by
9 * the Free Software Foundation, either version 3 of the License, or
10 * (at your option) any later version.
11 *
12 * HeuristicLab is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15 * GNU General Public License for more details.
16 *
17 * You should have received a copy of the GNU General Public License
18 * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
19 */
20#endregion
21
22using System;
23using System.Collections.Generic;
24using System.Linq;
25using HeuristicLab.Common;
26using HeuristicLab.Core;
27using HeuristicLab.Data;
28using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
29
30namespace HeuristicLab.Encodings.LinearLinkageEncoding {
31  [Item("LinearLinkage", "Represents an LLE grouping of items.")]
32  [StorableClass]
33  public sealed class LinearLinkage : IntArray {
34
35    [StorableConstructor]
36    private LinearLinkage(bool deserializing) : base(deserializing) { }
37    private LinearLinkage(LinearLinkage original, Cloner cloner) : base(original, cloner) { }
38    public LinearLinkage() { }
39
40    private LinearLinkage(int length) : base(length) { }
41    private LinearLinkage(int[] elements) : base(elements) { }
42
43    /// <summary>
44    /// Create a new LinearLinkage object where every element is in a seperate group.
45    /// </summary>
46    public static LinearLinkage SingleElementGroups(int length) {
47      var elements = new int[length];
48      for (var i = 0; i < length; i++) {
49        elements[i] = i;
50      }
51      return new LinearLinkage(elements);
52    }
53
54    /// <summary>
55    /// Create a new LinearLinkage object from an int[] in LLE
56    /// </summary>
57    /// <remarks>
58    /// This operation checks if the argument is a well formed LLE
59    /// and throws an ArgumentException otherwise.
60    /// </remarks>
61    /// <exception cref="ArgumentException">If <paramref name="lle"/> does not represent a valid LLE array.</exception>
62    /// <param name="lle">The LLE representation</param>
63    /// <returns>The linear linkage encoding in LLE format (with forward-links).</returns>
64    public static LinearLinkage FromForwardLinks(int[] lle) {
65      if (!Validate(lle))
66        throw new ArgumentException("Array is malformed and does not represent a valid LLE forward encoding.", "elements");
67      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;
93    }
94
95    /// <summary>
96    /// Create a new LinearLinkage object by parsing an LLE-e representation
97    /// and modifing the underlying array so that it is in LLE representation.
98    /// </summary>
99    /// <remarks>
100    /// This operation runs in O(n) time, but requires additional memory
101    /// in form of a int[].
102    /// </remarks>
103    /// <param name="llee">The LLE-e representation</param>
104    /// <returns>The linear linkage encoding in LLE format (with forward-links).</returns>
105    public static LinearLinkage FromEndLinks(int[] llee) {
106      var result = new LinearLinkage(llee.Length);
107      result.SetEndLinks(llee);
108      return result;
109    }
110
111    /// <summary>
112    /// Create a new LinearLinkage object by translating
113    /// an enumeration of groups into the underlying array representation.
114    /// </summary>
115    /// <remarks>
116    /// Throws an ArgumentException when there is an element assigned to
117    /// multiple groups or elements that are not assigned to any group.
118    /// </remarks>
119    /// <param name="grouping">The grouping of the elements, each element must
120    /// be part of exactly one group.</param>
121    public static LinearLinkage FromGroups(int length, IEnumerable<IEnumerable<int>> grouping) {
122      var result = new LinearLinkage(length);
123      result.SetGroups(grouping);
124      return result;
125    }
126
127    public override IDeepCloneable Clone(Cloner cloner) {
128      return new LinearLinkage(this, cloner);
129    }
130
131    /// <summary>
132    /// This method parses the encoded array and calculates the membership of
133    /// each element to the groups. It starts at the lowest element.
134    /// </summary>
135    /// <remarks>
136    /// Runtime complexity of this method is O(n) where n is the length of the
137    /// array.
138    /// </remarks>
139    /// <exception cref="InvalidOperationException">If this object is not vaild LLE.</exception>
140    /// <returns>An enumeration of all groups.</returns>
141    public IEnumerable<List<int>> GetGroups() {
142      var len = array.Length;
143      var used = new bool[len];
144      for (var i = 0; i < len; i++) {
145        if (used[i]) continue;
146        var curr = i;
147        var next = array[curr];
148        var group = new List<int> { curr };
149        while (next > curr && next < len && !used[next]) {
150          used[curr] = true;
151          curr = next;
152          next = array[next];
153          group.Add(curr);
154        }
155        if (curr != next) throw new InvalidOperationException("Array is malformed and does not represent a valid LLE forward encoding.");
156        used[curr] = true;
157        yield return group;
158      }
159    }
160
161    /// <summary>
162    /// This method parses the encoded array and gathers all elements
163    /// that belong to the same group as element <paramref name="index"/>.
164    /// </summary>
165    /// <param name="index">The element whose group should be returned.
166    /// </param>
167    /// <returns>The element at <paramref name="index"/> and all other
168    /// elements in the same group.</returns>
169    public IEnumerable<int> GetGroup(int index) {
170      foreach (var n in GetGroupForward(index))
171        yield return n;
172      // the element index has already been yielded
173      foreach (var n in GetGroupBackward(index).Skip(1))
174        yield return n;
175    }
176
177    /// <summary>
178    /// This method parses the encoded array and gathers the element
179    /// <paramref name="index"/> as well as subsequent elements that
180    /// belong to the same group.
181    /// </summary>
182    /// <param name="index">The element from which subsequent (having a
183    /// larger number) elements in the group should be returned.
184    /// </param>
185    /// <returns>The element <paramref name="index"/> and all subsequent
186    /// elements in the same group.</returns>
187    public IEnumerable<int> GetGroupForward(int index) {
188      yield return index;
189      var next = array[index];
190      if (next == index) yield break;
191      int prev;
192      do {
193        yield return next;
194        prev = next;
195        next = array[next];
196      } while (next != prev);
197    }
198
199    /// <summary>
200    /// This method parses the encoded array and gathers the element
201    /// given <paramref name="index"/> as well as preceeding elements that
202    /// belong to the same group.
203    /// </summary>
204    /// <remarks>
205    /// Warning, this code has performance O(index) as the array has to
206    /// be fully traversed backwards from the given index.
207    /// </remarks>
208    /// <param name="index">The element from which preceeding (having a
209    /// smaller number) elements in the group should be returned.
210    /// </param>
211    /// <returns>The element <paramref name="index"/> and all preceeding
212    /// elements in the same group.</returns>
213    public IEnumerable<int> GetGroupBackward(int index) {
214      yield return index;
215      var next = array[index];
216      // return preceding elements in group
217      for (var prev = index - 1; prev >= 0; prev--) {
218        if (array[prev] != next) continue;
219        next = prev;
220        yield return next;
221      }
222    }
223
224    /// <summary>
225    /// This method translates an enumeration of groups into the underlying
226    /// array representation.
227    /// </summary>
228    /// <remarks>
229    /// Throws an ArgumentException when there is an element assigned to
230    /// multiple groups or elements that are not assigned to any group.
231    /// </remarks>
232    /// <param name="grouping">The grouping of the elements, each element must
233    /// 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>
238    public void SetGroups(IEnumerable<IEnumerable<int>> grouping) {
239      var len = array.Length;
240      var used = new bool[len];
241      foreach (var group in grouping) {
242        var prev = -1;
243        foreach (var g in group.OrderBy(x => x)) {
244          if (g < prev || g >= len) throw new ArgumentException(string.Format("Element {0} is bigger than {1} or smaller than 0.", g, len - 1), "grouping");
245          if (prev >= 0) array[prev] = g;
246          prev = g;
247          if (used[prev]) {
248            throw new ArgumentException(string.Format("Element {0} is contained at least twice.", prev), "grouping");
249          }
250          used[prev] = true;
251        }
252        array[prev] = prev;
253      }
254      if (!used.All(x => x))
255        throw new ArgumentException(string.Format("Elements are not assigned a group: {0}", string.Join(", ", used.Select((x, i) => new { x, i }).Where(x => !x.x).Select(x => x.i))));
256    }
257
258    /// <summary>
259    /// Performs a check whether the array represents a valid LLE encoding.
260    /// </summary>
261    /// <remarks>
262    /// The runtime complexity of this method is O(n) where n is the length of
263    /// the array.
264    /// </remarks>
265    /// <returns>True if the encoding is valid.</returns>
266    public bool Validate() {
267      return Validate(array);
268    }
269
270    private static bool Validate(int[] array) {
271      var len = array.Length;
272      var used = new bool[len];
273      for (var i = 0; i < len; i++) {
274        if (used[i]) continue;
275        var curr = i;
276        var next = array[curr];
277        while (next > curr && next < len && !used[next]) {
278          used[curr] = true;
279          curr = next;
280          next = array[next];
281        }
282        if (curr!=next) return false;
283        used[curr] = true;
284      }
285      return true;
286    }
287
288    /// <summary>
289    /// This method flattens tree structures that may be present in groups.
290    /// These tree structures may be created by e.g. merging two groups by
291    /// linking one end node to the end node of another.
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
295    ///    /   \
296    ///   5     6
297    ///  / \    |
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.
301    /// </summary>
302    /// <remarks>
303    /// The method first converts the array to LLE-e format and then
304    /// linearizes the links. This requires two passes of the whole array
305    /// as well as another copy of the underlying array.
306    /// The runtime complexity is O(n).
307    ///
308    /// The method assumes that there are no back links present.
309    /// </remarks>
310    public void LinearizeTreeStructures() {
311      // Step 1: Convert the array into LLE-e
312      ToEndLinksInplace(array);
313      // Step 2: For all groups linearize the links
314      SetEndLinks(array);
315    }
316
317    /// <summary>
318    /// Creates a copy of the underlying array and turns it into LLE-e.
319    /// </summary>
320    /// <remarks>
321    /// LLE-e is a special format where each element points to the
322    /// ending item of a group.
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.
325    ///
326    /// This operation runs in O(n) time.
327    /// </remarks>
328    /// <exception cref="ArgumentException">In case, this object does not
329    /// represent a valid LLE encoding.
330    /// </exception>
331    /// <returns>An integer array in LLE-e representation</returns>
332    public int[] ToEndLinks() {
333      var result = (int[])array.Clone();
334      ToEndLinksInplace(result);
335      return result;
336    }
337
338    private static void ToEndLinksInplace(int[] array) {
339      var length = array.Length;
340      for (var i = length - 1; i >= 0; i--) {
341        var next = array[i];
342        if (next > i) {
343          array[i] = array[next];
344        } else if (next < i) {
345          throw new ArgumentException("Array is malformed and does not represent a valid LLE encoding.", "array");
346        }
347      }
348    }
349
350    /// <summary>
351    /// Parses an LLE-e representation and modifies the underlying array
352    /// so that it is in LLE representation.
353    /// </summary>
354    /// <remarks>
355    /// This operation runs in O(n) time, but requires additional memory
356    /// in form of a int[].
357    /// </remarks>
358    /// <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>
363    public void SetEndLinks(int[] llee) {
364      var length = array.Length;
365      if (length != llee.Length) {
366        throw new ArgumentException(string.Format("Expected length {0} but length was {1}", length, llee.Length), "llee");
367      }
368      // If we are ok with mutating llee we can avoid this clone
369      var lookup = (int[])llee.Clone();
370      for (var i = length - 1; i >= 0; i--) {
371        var end = llee[i];
372        if (end == i) {
373          array[i] = end;
374        } else if (end > i && end < length) {
375          array[i] = lookup[end];
376          lookup[end] = i;
377        } else {
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;
407    }
408  }
409}
Note: See TracBrowser for help on using the repository browser.