source: trunk/sources/HeuristicLab.Encodings.LinearLinkageEncoding/3.3/LinearLinkage.cs @ 14185

Last change on this file since 14185 was 14185, checked in by swagner, 4 years ago

#2526: Updated year of copyrights in license headers

File size: 10.0 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    public LinearLinkage(int length) : base(length) { }
40    public LinearLinkage(int[] elements) : base(elements) { }
41
42    public override IDeepCloneable Clone(Cloner cloner) {
43      return new LinearLinkage(this, cloner);
44    }
45
46    /// <summary>
47    /// This method parses the encoded array and calculates the membership of
48    /// each element to the groups. It starts at the lowest element.
49    /// </summary>
50    /// <remarks>
51    /// Runtime complexity of this method is O(n) where n is the length of the
52    /// array.
53    /// </remarks>
54    /// <returns>An enumeration of all groups.</returns>
55    public IEnumerable<List<int>> GetGroups() {
56      var len = array.Length;
57      var remaining = new HashSet<int>(Enumerable.Range(0, len));
58      // iterate from lowest to highest index
59      for (var i = 0; i < len; i++) {
60        if (!remaining.Contains(i)) continue;
61        var group = new List<int> { i };
62        remaining.Remove(i);
63        var next = array[i];
64        if (next != i) {
65          int prev;
66          do {
67            group.Add(next);
68            if (!remaining.Remove(next))
69              throw new ArgumentException("Array is malformed and does not represent a valid LLE forward encoding.");
70            prev = next;
71            next = array[next];
72          } while (next != prev);
73        }
74        yield return group;
75      }
76    }
77
78    /// <summary>
79    /// This method parses the encoded array and gathers all elements
80    /// that belong to the same group as element <paramref name="index"/>.
81    /// </summary>
82    /// <param name="index">The element whose group should be returned.
83    /// </param>
84    /// <returns>The element at <paramref name="index"/> and all other
85    /// elements in the same group.</returns>
86    public IEnumerable<int> GetGroup(int index) {
87      foreach (var n in GetGroupForward(index))
88        yield return n;
89      // the element index has already been yielded
90      foreach (var n in GetGroupBackward(index).Skip(1))
91        yield return n;
92    }
93
94    /// <summary>
95    /// This method parses the encoded array and gathers the element
96    /// <paramref name="index"/> as well as subsequent elements that
97    /// belong to the same group.
98    /// </summary>
99    /// <param name="index">The element from which subsequent (having a
100    /// larger number) elements in the group should be returned.
101    /// </param>
102    /// <returns>The element <paramref name="index"/> and all subsequent
103    /// elements in the same group.</returns>
104    public IEnumerable<int> GetGroupForward(int index) {
105      yield return index;
106      var next = array[index];
107      if (next == index) yield break;
108      int prev;
109      do {
110        yield return next;
111        prev = next;
112        next = array[next];
113      } while (next != prev);
114    }
115
116    /// <summary>
117    /// This method parses the encoded array and gathers the element
118    /// given <paramref name="index"/> as well as preceeding elements that
119    /// belong to the same group.
120    /// </summary>
121    /// <remarks>
122    /// Warning, this code has performance O(index) as the array has to
123    /// be fully traversed backwards from the given index.
124    /// </remarks>
125    /// <param name="index">The element from which preceeding (having a
126    /// smaller number) elements in the group should be returned.
127    /// </param>
128    /// <returns>The element <paramref name="index"/> and all preceeding
129    /// elements in the same group.</returns>
130    public IEnumerable<int> GetGroupBackward(int index) {
131      yield return index;
132      var next = array[index];
133      // return preceding elements in group
134      for (var prev = index - 1; prev >= 0; prev--) {
135        if (array[prev] != next) continue;
136        next = prev;
137        yield return next;
138      }
139    }
140
141    /// <summary>
142    /// This method translates an enumeration of groups into the underlying
143    /// array representation.
144    /// </summary>
145    /// <remarks>
146    /// Throws an ArgumentException when there is an element assigned to
147    /// multiple groups or elements that are not assigned to any group.
148    /// </remarks>
149    /// <param name="grouping">The grouping of the elements, each element must
150    /// be part of exactly one group.</param>
151    public void SetGroups(IEnumerable<IEnumerable<int>> grouping) {
152      var len = array.Length;
153      var remaining = new HashSet<int>(Enumerable.Range(0, len));
154      foreach (var group in grouping) {
155        var prev = -1;
156        foreach (var g in group.OrderBy(x => x)) {
157          if (prev >= 0) array[prev] = g;
158          prev = g;
159          if (!remaining.Remove(prev))
160            throw new ArgumentException(string.Format("Element {0} is contained at least twice.", prev), "grouping");
161        }
162        if (prev >= 0) array[prev] = prev;
163      }
164      if (remaining.Count > 0)
165        throw new ArgumentException(string.Format("Elements are not assigned a group: {0}", string.Join(", ", remaining)));
166    }
167
168    /// <summary>
169    /// Performs a check whether the array represents a valid LLE encoding.
170    /// </summary>
171    /// <remarks>
172    /// The runtime complexity of this method is O(n) where n is the length of
173    /// the array.
174    /// </remarks>
175    /// <returns>True if the encoding is valid.</returns>
176    public bool Validate() {
177      var len = array.Length;
178      var remaining = new HashSet<int>(Enumerable.Range(0, len));
179      for (var i = 0; i < len; i++) {
180        if (!remaining.Contains(i)) continue;
181        remaining.Remove(i);
182        var next = array[i];
183        if (next == i) continue;
184        int prev;
185        do {
186          if (!remaining.Remove(next)) return false;
187          prev = next;
188          next = array[next];
189        } while (next != prev);
190      }
191      return remaining.Count == 0;
192    }
193
194    /// <summary>
195    /// This method flattens tree structures that may be present in groups.
196    /// These tree structures may be created by e.g. merging two groups by
197    /// linking one end node to the end node of another.
198    /// Consider following 1-based index array: 6, 6, 7, 5, 5, 8, 8, 8, 9.
199    /// This results in the following tree structure for group 8:
200    ///      8
201    ///    /   \
202    ///   6     7
203    ///  / \    |
204    /// 1   2   3
205    /// After this operation the array will be 2, 3, 6, 5, 5, 7, 8, 8, 9.
206    /// Representing a tree with one branch: 1 -> 2 -> 3 -> 6 -> 7 -> 8
207    /// </summary>
208    /// <remarks>
209    /// The method first converts the array to LLE-e format and then
210    /// linearizes the links. This requires two passes of the whole array
211    /// as well as a dictionary to hold the smallest index of each group.
212    /// The runtime complexity is O(n).
213    ///
214    /// The method assumes that there are no back links present.
215    /// </remarks>
216    public void LinearizeTreeStructures() {
217      // Step 1: Convert the array into LLE-e
218      ToLLEeInplace(array);
219      // Step 2: For all groups linearize the links
220      FromLLEe(array);
221    }
222
223    /// <summary>
224    /// Creates a copy of the underlying array and turns it into LLE-e.
225    /// </summary>
226    /// <remarks>
227    /// LLE-e is a special format where each element points to the
228    /// ending item of a group.
229    /// The LLE representation 2, 3, 5, 6, 5, 7, 8, 8 would become
230    /// 5, 5, 5, 8, 5, 8, 8, 8 in LLE-e.
231    ///
232    /// This operation runs in O(n) time.
233    /// </remarks>
234    /// <returns>An integer array in LLE-e representation</returns>
235    public int[] ToLLEe() {
236      var result = (int[])array.Clone();
237      ToLLEeInplace(result);
238      return result;
239    }
240
241    private void ToLLEeInplace(int[] a) {
242      var length = a.Length;
243      for (var i = length - 1; i >= 0; i--) {
244        if (array[i] == i) a[i] = i;
245        else a[i] = a[a[i]];
246      }
247    }
248
249    /// <summary>
250    /// Parses an LLE-e representation and modifies the underlying array
251    /// so that it is in LLE representation.
252    /// </summary>
253    /// <remarks>
254    /// This operation runs in O(n) time, but requires additional memory
255    /// in form of a dictionary.
256    /// </remarks>
257    /// <param name="llee">The LLE-e representation</param>
258    public void FromLLEe(int[] llee) {
259      var length = array.Length;
260      var groups = new Dictionary<int, int>();
261      for (var i = length - 1; i >= 0; i--) {
262        if (llee[i] == i) {
263          array[i] = i;
264          groups[i] = i;
265        } else {
266          var g = llee[i];
267          array[i] = groups[g];
268          groups[g] = i;
269        }
270      }
271    }
272  }
273}
Note: See TracBrowser for help on using the repository browser.