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

Last change on this file since 12288 was 12288, checked in by abeham, 7 years ago

#2319:

  • Changed encoding to represent linkages in LLE (as opposed to LLE-e)
  • Added GraftManipulator
  • Added repair procedure
  • Improved performance of some crossovers
File size: 7.9 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 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 items that
80    /// belong to the same group as element <paramref name="index"/>.
81    /// </summary>
82    /// <param name="index">The element whose group should be returned.</param>
83    /// <returns>The element at <paramref name="index"/> and all other
84    /// elements in the same group.</returns>
85    public IEnumerable<int> GetGroup(int index) {
86      // return current element
87      yield return index;
88      var next = array[index];
89      if (next == index) yield break;
90      int prev;
91      // return succeeding elements in group
92      do {
93        yield return next;
94        prev = next;
95        next = array[next];
96      } while (next != prev);
97      next = array[index];
98      // return preceding elements in group
99      for (prev = index - 1; prev >= 0; prev--) {
100        if (array[prev] != next) continue;
101        next = prev;
102        yield return next;
103      }
104    }
105
106    /// <summary>
107    /// This method parses the encoded array and gathers the item itself as
108    /// well as subsequent items that belong to the same group as element
109    /// <paramref name="index"/>.
110    /// </summary>
111    /// <param name="index">The element from which items in the group should
112    /// be returned.</param>
113    /// <returns>The element at <paramref name="index"/> and all subsequent
114    /// elements in the same group.</returns>
115    public IEnumerable<int> GetGroupForward(int index) {
116      yield return index;
117      var next = array[index];
118      if (next == index) yield break;
119      int prev;
120      do {
121        yield return next;
122        prev = next;
123        next = array[next];
124      } while (next != prev);
125    }
126
127    /// <summary>
128    /// This method translates an enumeration of groups into the underlying
129    /// array representation.
130    /// </summary>
131    /// <remarks>
132    /// Throws an ArgumentException when there is an element assigned to
133    /// multiple groups or elements that  are not assigned to any group.
134    /// </remarks>
135    /// <param name="grouping">The grouping of the elements, each element must
136    /// be part of exactly one group.</param>
137    public void SetGroups(IEnumerable<IEnumerable<int>> grouping) {
138      var len = array.Length;
139      var remaining = new HashSet<int>(Enumerable.Range(0, len));
140      foreach (var group in grouping) {
141        var prev = -1;
142        foreach (var g in group.OrderBy(x => x)) {
143          if (prev >= 0) array[prev] = g;
144          prev = g;
145          if (!remaining.Remove(prev))
146            throw new ArgumentException(string.Format("Element {0} is contained at least twice.", prev), "grouping");
147        }
148        if (prev >= 0) array[prev] = prev;
149      }
150      if (remaining.Count > 0)
151        throw new ArgumentException(string.Format("Elements are not assigned a group: {0}", string.Join(", ", remaining)));
152    }
153
154    /// <summary>
155    /// Performs a check whether the array represents a valid LLE encoding.
156    /// </summary>
157    /// <remarks>
158    /// The runtime complexity of this method is O(n) where n is the length of
159    /// the array.
160    /// </remarks>
161    /// <returns>True if the encoding is valid.</returns>
162    public bool Validate() {
163      var len = array.Length;
164      var remaining = new HashSet<int>(Enumerable.Range(0, len));
165      for (var i = 0; i < len; i++) {
166        if (!remaining.Contains(i)) continue;
167        remaining.Remove(i);
168        var next = array[i];
169        if (next == i) continue;
170        int prev;
171        do {
172          if (!remaining.Remove(next)) return false;
173          prev = next;
174          next = array[next];
175        } while (next != prev);
176      }
177      return remaining.Count == 0;
178    }
179
180    /// <summary>
181    /// This method flattens tree structures that may be present in groups.
182    /// These tree structures may be created by e.g. merging two groups by
183    /// linking one end node to the end node of another.
184    /// Consider following example: 6, 6, 7, 5, 5, 8, 8, 8, 9.
185    /// This results in the following tree structure for group 8:
186    ///      8
187    ///    /   \
188    ///   6     7
189    ///  / \
190    /// 1   2
191    /// After this operation the array will be 2, 3, 6, 5, 5, 7, 8, 8, 9.
192    /// </summary>
193    /// <remarks>
194    /// The method first converts the array to LLE-e format and then
195    /// linearizes the links. This requires two passes of the whole array
196    /// as well as a dictionary to hold the smallest index of each group.
197    ///
198    /// The method assumes that there are no back links present.
199    /// </remarks>
200    public void LinearizeTreeStructures() {
201      // Step 1: Convert the array into LLE-e
202      var length = array.Length;
203      var groups = new Dictionary<int, int>();
204      for (var i = length - 1; i >= 0; i--) {
205        if (array[i] == i) groups[i] = i;
206        else array[i] = array[array[i]];
207      }
208      // Step 2: For all groups linearize the links
209      for (var i = length - 1; i >= 0; i--) {
210        if (array[i] == i) continue;
211        var g = array[i];
212        array[i] = groups[g];
213        groups[g] = i;
214      }
215    }
216  }
217}
Note: See TracBrowser for help on using the repository browser.