source: branches/MemPRAlgorithm/HeuristicLab.Encodings.LinearLinkageEncoding/3.3/LinearLinkage.cs @ 14487

Last change on this file since 14487 was 14487, checked in by sraggl, 4 years ago

#2701 Merged with trunk to get new version of LinearLinkageEncoding
Improved MoveGenerator

File size: 13.7 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    /// <param name="lle">The LLE representation</param>
62    public static LinearLinkage FromForwardLinks(int[] lle) {
63      if (!Validate(lle)) {
64        throw new ArgumentException("Array is malformed and does not represent a valid LLE forward encoding.", "elements");
65      }
66      return new LinearLinkage(lle);
67    }
68
69    /// <summary>
70    /// Create a new LinearLinkage object by parsing an LLE-e representation
71    /// and modifing the underlying array so that it is in LLE representation.
72    /// </summary>
73    /// <remarks>
74    /// This operation runs in O(n) time, but requires additional memory
75    /// in form of a int[].
76    /// </remarks>
77    /// <param name="llee">The LLE-e representation</param>
78    /// <returns>LinearLinkage</returns>
79    public static LinearLinkage FromEndLinks(int[] llee) {
80      var result = new LinearLinkage(llee.Length);
81      result.SetEndLinks(llee);
82      return result;
83    }
84
85    /// <summary>
86    /// Create a new LinearLinkage object by translating
87    /// an enumeration of groups into the underlying array representation.
88    /// </summary>
89    /// <remarks>
90    /// Throws an ArgumentException when there is an element assigned to
91    /// multiple groups or elements that are not assigned to any group.
92    /// </remarks>
93    /// <param name="grouping">The grouping of the elements, each element must
94    /// be part of exactly one group.</param>
95    public static LinearLinkage FromGroups(int length, IEnumerable<IEnumerable<int>> grouping) {
96      var result = new LinearLinkage(length);
97      result.SetGroups(grouping);
98      return result;
99    }
100
101    public override IDeepCloneable Clone(Cloner cloner) {
102      return new LinearLinkage(this, cloner);
103    }
104
105    /// <summary>
106    /// This method parses the encoded array and calculates the membership of
107    /// each element to the groups. It starts at the lowest element.
108    /// </summary>
109    /// <remarks>
110    /// Runtime complexity of this method is O(n) where n is the length of the
111    /// array.
112    /// </remarks>
113    /// <returns>An enumeration of all groups.</returns>
114    public IEnumerable<List<int>> GetGroups() {
115      var len = array.Length;
116      var used = new bool[len];
117      for (var i = 0; i < len; i++) {
118        if (used[i]) continue;
119        var curr = i;
120        var next = array[curr];
121        var group = new List<int> { curr };
122        while (next > curr && next < len && !used[next]) {
123          used[curr] = true;
124          curr = next;
125          next = array[next];
126          group.Add(curr);
127        }
128        if (curr != next) throw new ArgumentException("Array is malformed and does not represent a valid LLE forward encoding.");
129        used[curr] = true;
130        yield return group;
131      }
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      }*/
154    }
155
156    /// <summary>
157    /// This method parses the encoded array and gathers all elements
158    /// that belong to the same group as element <paramref name="index"/>.
159    /// </summary>
160    /// <param name="index">The element whose group should be returned.
161    /// </param>
162    /// <returns>The element at <paramref name="index"/> and all other
163    /// elements in the same group.</returns>
164    public IEnumerable<int> GetGroup(int index) {
165      foreach (var n in GetGroupForward(index))
166        yield return n;
167      // the element index has already been yielded
168      foreach (var n in GetGroupBackward(index).Skip(1))
169        yield return n;
170    }
171
172    /// <summary>
173    /// This method parses the encoded array and gathers the element
174    /// <paramref name="index"/> as well as subsequent elements that
175    /// belong to the same group.
176    /// </summary>
177    /// <param name="index">The element from which subsequent (having a
178    /// larger number) elements in the group should be returned.
179    /// </param>
180    /// <returns>The element <paramref name="index"/> and all subsequent
181    /// elements in the same group.</returns>
182    public IEnumerable<int> GetGroupForward(int index) {
183      yield return index;
184      var next = array[index];
185      if (next == index) yield break;
186      int prev;
187      do {
188        yield return next;
189        prev = next;
190        next = array[next];
191      } while (next != prev);
192    }
193
194    /// <summary>
195    /// This method parses the encoded array and gathers the element
196    /// given <paramref name="index"/> as well as preceeding elements that
197    /// belong to the same group.
198    /// </summary>
199    /// <remarks>
200    /// Warning, this code has performance O(index) as the array has to
201    /// be fully traversed backwards from the given index.
202    /// </remarks>
203    /// <param name="index">The element from which preceeding (having a
204    /// smaller number) elements in the group should be returned.
205    /// </param>
206    /// <returns>The element <paramref name="index"/> and all preceeding
207    /// elements in the same group.</returns>
208    public IEnumerable<int> GetGroupBackward(int index) {
209      yield return index;
210      var next = array[index];
211      // return preceding elements in group
212      for (var prev = index - 1; prev >= 0; prev--) {
213        if (array[prev] != next) continue;
214        next = prev;
215        yield return next;
216      }
217    }
218
219    /// <summary>
220    /// This method translates an enumeration of groups into the underlying
221    /// array representation.
222    /// </summary>
223    /// <remarks>
224    /// Throws an ArgumentException when there is an element assigned to
225    /// multiple groups or elements that are not assigned to any group.
226    /// </remarks>
227    /// <param name="grouping">The grouping of the elements, each element must
228    /// be part of exactly one group.</param>
229    public void SetGroups(IEnumerable<IEnumerable<int>> grouping) {
230      var len = array.Length;
231      var used = new bool[len];
232      foreach (var group in grouping) {
233        var prev = -1;
234        foreach (var g in group.OrderBy(x => x)) {
235          if (g < prev || g >= len) throw new ArgumentException(string.Format("Element {0} is bigger than {1} or smaller than 0.", g, len - 1), "grouping");
236          if (prev >= 0) array[prev] = g;
237          prev = g;
238          if (used[prev]) {
239            throw new ArgumentException(string.Format("Element {0} is contained at least twice.", prev), "grouping");
240          }
241          used[prev] = true;
242        }
243        array[prev] = prev;
244      }
245      if (!used.All(x => x))
246        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))));
247    }
248
249    /// <summary>
250    /// Performs a check whether the array represents a valid LLE encoding.
251    /// </summary>
252    /// <remarks>
253    /// The runtime complexity of this method is O(n) where n is the length of
254    /// the array.
255    /// </remarks>
256    /// <returns>True if the encoding is valid.</returns>
257    public bool Validate() {
258      return Validate(array);
259    }
260
261    private static bool Validate(int[] array) {
262      var len = array.Length;
263      var used = new bool[len];
264      for (var i = 0; i < len; i++) {
265        if (used[i]) continue;
266        var curr = i;
267        var next = array[curr];
268        while (next > curr && next < len && !used[next]) {
269          used[curr] = true;
270          curr = next;
271          next = array[next];
272        }
273        if (curr!=next) return false;
274        used[curr] = true;
275      }
276      return true;
277    }
278
279    /// <summary>
280    /// This method flattens tree structures that may be present in groups.
281    /// These tree structures may be created by e.g. merging two groups by
282    /// 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
286    ///    /   \
287    ///   6     7
288    ///  / \    |
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
292    /// </summary>
293    /// <remarks>
294    /// The method first converts the array to LLE-e format and then
295    /// 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.
297    /// The runtime complexity is O(n).
298    ///
299    /// The method assumes that there are no back links present.
300    /// </remarks>
301    public void LinearizeTreeStructures() {
302      // Step 1: Convert the array into LLE-e
303      ToEndLinksInplace(array);
304      // Step 2: For all groups linearize the links
305      SetEndLinks(array);
306    }
307
308    /// <summary>
309    /// Creates a copy of the underlying array and turns it into LLE-e.
310    /// </summary>
311    /// <remarks>
312    /// LLE-e is a special format where each element points to the
313    /// 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.
316    ///
317    /// This operation runs in O(n) time.
318    /// </remarks>
319    /// <returns>An integer array in LLE-e representation</returns>
320    public int[] ToEndLinks() {
321      var result = (int[])array.Clone();
322      ToEndLinksInplace(result);
323      return result;
324    }
325
326    private static void ToEndLinksInplace(int[] array) {
327      var length = array.Length;
328      for (var i = length - 1; i >= 0; i--) {
329        var next = array[i];
330        if (next > i) {
331          array[i] = array[next];
332        } else if (next < i) {
333          throw new ArgumentException("Array is malformed and does not represent a valid LLE encoding.", "array");
334        }
335      }
336    }
337
338    /// <summary>
339    /// Parses an LLE-e representation and modifies the underlying array
340    /// so that it is in LLE representation.
341    /// </summary>
342    /// <remarks>
343    /// This operation runs in O(n) time, but requires additional memory
344    /// in form of a int[].
345    /// </remarks>
346    /// <param name="llee">The LLE-e representation</param>
347    public void SetEndLinks(int[] llee) {
348      var length = array.Length;
349      if (length != llee.Length) {
350        throw new ArgumentException(string.Format("Expected length {0} but length was {1}", length, llee.Length), "llee");
351      }
352      // If we are ok with mutating llee we can avoid this clone
353      var lookup = (int[])llee.Clone();
354      for (var i = length - 1; i >= 0; i--) {
355        var end = llee[i];
356        if (end == i) {
357          array[i] = end;
358        } else if (end > i && end < length) {
359          array[i] = lookup[end];
360          lookup[end] = i;
361        } else {
362          throw new ArgumentException("Array is malformed and does not represent a valid LLE end encoding.", "llee");
363        }
364      }
365    }
366  }
367}
Note: See TracBrowser for help on using the repository browser.