Free cookie consent management tool by TermsFeed Policy Generator

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

Last change on this file since 12285 was 12285, checked in by abeham, 8 years ago

#2319: Added branch for linear linkage encoding (LLE-e)

File size: 8.4 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2015 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-e 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 each element to the groups.
48    /// 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 array.
52    /// </remarks>
53    /// <returns>An enumeration of all groups.</returns>
54    public IEnumerable<List<int>> GetGroups() {
55      var len = array.Length;
56      var dict = new Dictionary<int, List<int>>();
57      for (var i = 0; i < len; i++) {
58        var end = array[i];
59        if (end < i || end >= len || array[end] != end)
60          throw new ArgumentException("Array is malformed and does not represent a valid LLE-e encoding.");
61        List<int> list;
62        if (!dict.TryGetValue(end, out list))
63          dict.Add(end, new List<int>() { i });
64        else list.Add(i);
65      }
66      return dict.Values;
67      /* This code implements group extraction from LLE forward encoding
68       * var len = array.Length;
69      var remaining = new HashSet<int>(Enumerable.Range(0, len));
70      // iterate from lowest to highest index
71      for (var i = 0; i < len; i++) {
72        if (!remaining.Contains(i)) continue;
73        var group = new List<int> { i };
74        remaining.Remove(i);
75        var next = array[i];
76        if (next != i) {
77          int prev;
78          do {
79            group.Add(next);
80            if (!remaining.Remove(next))
81              throw new ArgumentException("Array is malformed and does not represent a valid LLE forward encoding.");
82            prev = next;
83            next = array[next];
84          } while (next != prev);
85        }
86        yield return group;
87      }*/
88    }
89
90    /// <summary>
91    /// This method parses the encoded array and gathers all items that belong to the same group as element <paramref name="index"/>.
92    /// </summary>
93    /// <param name="index">The element whose group should be returned.</param>
94    /// <returns>The element at <paramref name="index"/> and all other elements in the same group.</returns>
95    public IEnumerable<int> GetGroup(int index) {
96      yield return index;
97      var gn = array[index];
98      for (var i = index + 1; i <= gn; i++) {
99        if (array[i] == gn) yield return i;
100      }
101      for (var i = index - 1; i >= 0; i++) {
102        if (array[i] == gn) yield return i;
103      }
104      /* This code implements group extraction from LLE forward encoding
105      // return current element
106      yield return index;
107      var next = array[index];
108      if (next == index) yield break;
109      int prev;
110      // return succeeding elements in group
111      do {
112        yield return next;
113        prev = next;
114        next = array[next];
115      } while (next != prev);
116      next = array[index];
117      // return preceding elements in group
118      for (prev = index - 1; prev >= 0; prev--) {
119        if (array[prev] != next) continue;
120        next = prev;
121        yield return next;
122      }*/
123    }
124
125    /// <summary>
126    /// This method parses the encoded array and gathers the item itself as well as subsequent items that belong to the same group as element <paramref name="index"/>.
127    /// </summary>
128    /// <param name="index">The element from which items in the group should be returned.</param>
129    /// <returns>The element at <paramref name="index"/> and all subsequent elements in the same group.</returns>
130    public IEnumerable<int> GetGroupForward(int index) {
131      yield return index;
132      var gn = array[index];
133      for (var i = index + 1; i <= gn; i++) {
134        if (array[i] == gn) yield return i;
135      }
136      /* This code implements group extraction from LLE forward encoding
137      yield return index;
138      var next = array[index];
139      if (next == index) yield break;
140      int prev;
141      do {
142        yield return next;
143        prev = next;
144        next = array[next];
145      } while (next != prev);*/
146    }
147
148    /// <summary>
149    /// This method translates an enumeration of groups into the underlying array representation.
150    /// </summary>
151    /// <remarks>
152    /// Throws an ArgumentException when there is an element assigned to multiple groups or elements that
153    /// are not assigned to any group.
154    /// </remarks>
155    /// <param name="grouping">The grouping of the elements, each element must be part of exactly one group.</param>
156    public void SetGroups(IEnumerable<IEnumerable<int>> grouping) {
157      var len = array.Length;
158      var remaining = new HashSet<int>(Enumerable.Range(0, len));
159      foreach (var group in grouping) {
160        var max = -1;
161        foreach (var g in group.OrderByDescending(x => x)) {
162          if (max < 0) max = g;
163          array[g] = max;
164          remaining.Remove(g);
165        }
166      }
167      if (remaining.Count > 0)
168        throw new ArgumentException(string.Format("Elements are not assigned a group: {0}", string.Join(", ", remaining)));
169      /* This code implements group setting for LLE forward encoding
170      var len = array.Length;
171      var remaining = new HashSet<int>(Enumerable.Range(0, len));
172      foreach (var group in grouping) {
173        var prev = -1;
174        foreach (var g in group.OrderBy(x => x)) {
175          if (prev >= 0) array[prev] = g;
176          prev = g;
177          if (!remaining.Remove(prev))
178            throw new ArgumentException(string.Format("Element {0} is contained at least twice.", prev), "grouping");
179        }
180        if (prev >= 0) array[prev] = prev;
181      }
182      if (remaining.Count > 0)
183        throw new ArgumentException(string.Format("Elements are not assigned a group: {0}", string.Join(", ", remaining)));
184       */
185    }
186
187    /// <summary>
188    /// Performs a check whether the array represents a valid LLE-e encoding.
189    /// </summary>
190    /// <remarks>
191    /// The runtime complexity of this method is O(n) where n is the length of the array.
192    /// </remarks>
193    /// <returns>True if the encoding is valid.</returns>
194    public bool Validate() {
195      var len = array.Length;
196      for (var i = 0; i < len; i++) {
197        var end = array[i];
198        if (end < i || end >= len || array[end] != end)
199          return false;
200      }
201      return true;
202      /* This code implements group setting for LLE forward encoding
203      var len = array.Length;
204      var remaining = new HashSet<int>(Enumerable.Range(0, len));
205      for (var i = 0; i < len; i++) {
206        if (!remaining.Contains(i)) continue;
207        remaining.Remove(i);
208        var next = array[i];
209        if (next == i) continue;
210        int prev;
211        do {
212          if (!remaining.Remove(next)) return false;
213          prev = next;
214          next = array[next];
215        } while (next != prev);
216      }
217      return remaining.Count == 0;*/
218    }
219  }
220}
Note: See TracBrowser for help on using the repository browser.