[12285] | 1 | #region License Information
|
---|
| 2 | /* HeuristicLab
|
---|
[14185] | 3 | * Copyright (C) 2002-2016 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
|
---|
[12285] | 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 |
|
---|
| 22 | using System;
|
---|
| 23 | using System.Collections.Generic;
|
---|
| 24 | using System.Linq;
|
---|
| 25 | using HeuristicLab.Common;
|
---|
| 26 | using HeuristicLab.Core;
|
---|
| 27 | using HeuristicLab.Data;
|
---|
| 28 | using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
|
---|
| 29 |
|
---|
| 30 | namespace HeuristicLab.Encodings.LinearLinkageEncoding {
|
---|
[12288] | 31 | [Item("LinearLinkage", "Represents an LLE grouping of items.")]
|
---|
[12285] | 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 |
|
---|
[14487] | 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 |
|
---|
[12285] | 101 | public override IDeepCloneable Clone(Cloner cloner) {
|
---|
| 102 | return new LinearLinkage(this, cloner);
|
---|
| 103 | }
|
---|
| 104 |
|
---|
| 105 | /// <summary>
|
---|
[12288] | 106 | /// This method parses the encoded array and calculates the membership of
|
---|
| 107 | /// each element to the groups. It starts at the lowest element.
|
---|
[12285] | 108 | /// </summary>
|
---|
| 109 | /// <remarks>
|
---|
[12288] | 110 | /// Runtime complexity of this method is O(n) where n is the length of the
|
---|
| 111 | /// array.
|
---|
[12285] | 112 | /// </remarks>
|
---|
| 113 | /// <returns>An enumeration of all groups.</returns>
|
---|
| 114 | public IEnumerable<List<int>> GetGroups() {
|
---|
| 115 | var len = array.Length;
|
---|
[14487] | 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];
|
---|
[12285] | 135 | // iterate from lowest to highest index
|
---|
| 136 | for (var i = 0; i < len; i++) {
|
---|
[14487] | 137 | if (used[i]) continue;
|
---|
[12285] | 138 | var group = new List<int> { i };
|
---|
[14487] | 139 | used[i] = true;
|
---|
[12285] | 140 | var next = array[i];
|
---|
[14487] | 141 | if (next < i || next >= len) {
|
---|
| 142 | throw new ArgumentException("Array is malformed and does not represent a valid LLE forward encoding.");
|
---|
[12285] | 143 | }
|
---|
[14487] | 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 | }
|
---|
[12285] | 152 | yield return group;
|
---|
[14487] | 153 | }*/
|
---|
[12285] | 154 | }
|
---|
| 155 |
|
---|
| 156 | /// <summary>
|
---|
[12701] | 157 | /// This method parses the encoded array and gathers all elements
|
---|
| 158 | /// that belong to the same group as element <paramref name="index"/>.
|
---|
[12285] | 159 | /// </summary>
|
---|
[12701] | 160 | /// <param name="index">The element whose group should be returned.
|
---|
| 161 | /// </param>
|
---|
[12288] | 162 | /// <returns>The element at <paramref name="index"/> and all other
|
---|
| 163 | /// elements in the same group.</returns>
|
---|
[12285] | 164 | public IEnumerable<int> GetGroup(int index) {
|
---|
[12701] | 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) {
|
---|
[12285] | 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>
|
---|
[12701] | 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.
|
---|
[12285] | 198 | /// </summary>
|
---|
[12701] | 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
|
---|
[12288] | 207 | /// elements in the same group.</returns>
|
---|
[12701] | 208 | public IEnumerable<int> GetGroupBackward(int index) {
|
---|
[12285] | 209 | yield return index;
|
---|
| 210 | var next = array[index];
|
---|
[12701] | 211 | // return preceding elements in group
|
---|
| 212 | for (var prev = index - 1; prev >= 0; prev--) {
|
---|
| 213 | if (array[prev] != next) continue;
|
---|
| 214 | next = prev;
|
---|
[12285] | 215 | yield return next;
|
---|
[12701] | 216 | }
|
---|
[12285] | 217 | }
|
---|
| 218 |
|
---|
| 219 | /// <summary>
|
---|
[12288] | 220 | /// This method translates an enumeration of groups into the underlying
|
---|
| 221 | /// array representation.
|
---|
[12285] | 222 | /// </summary>
|
---|
| 223 | /// <remarks>
|
---|
[12288] | 224 | /// Throws an ArgumentException when there is an element assigned to
|
---|
[12643] | 225 | /// multiple groups or elements that are not assigned to any group.
|
---|
[12285] | 226 | /// </remarks>
|
---|
[12288] | 227 | /// <param name="grouping">The grouping of the elements, each element must
|
---|
| 228 | /// be part of exactly one group.</param>
|
---|
[12285] | 229 | public void SetGroups(IEnumerable<IEnumerable<int>> grouping) {
|
---|
| 230 | var len = array.Length;
|
---|
[14487] | 231 | var used = new bool[len];
|
---|
[12285] | 232 | foreach (var group in grouping) {
|
---|
| 233 | var prev = -1;
|
---|
| 234 | foreach (var g in group.OrderBy(x => x)) {
|
---|
[14487] | 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");
|
---|
[12285] | 236 | if (prev >= 0) array[prev] = g;
|
---|
| 237 | prev = g;
|
---|
[14487] | 238 | if (used[prev]) {
|
---|
[12285] | 239 | throw new ArgumentException(string.Format("Element {0} is contained at least twice.", prev), "grouping");
|
---|
[14487] | 240 | }
|
---|
| 241 | used[prev] = true;
|
---|
[12285] | 242 | }
|
---|
[14487] | 243 | array[prev] = prev;
|
---|
[12285] | 244 | }
|
---|
[14487] | 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))));
|
---|
[12285] | 247 | }
|
---|
| 248 |
|
---|
| 249 | /// <summary>
|
---|
[12288] | 250 | /// Performs a check whether the array represents a valid LLE encoding.
|
---|
[12285] | 251 | /// </summary>
|
---|
| 252 | /// <remarks>
|
---|
[12288] | 253 | /// The runtime complexity of this method is O(n) where n is the length of
|
---|
| 254 | /// the array.
|
---|
[12285] | 255 | /// </remarks>
|
---|
| 256 | /// <returns>True if the encoding is valid.</returns>
|
---|
| 257 | public bool Validate() {
|
---|
[14487] | 258 | return Validate(array);
|
---|
| 259 | }
|
---|
| 260 |
|
---|
| 261 | private static bool Validate(int[] array) {
|
---|
[12285] | 262 | var len = array.Length;
|
---|
[14487] | 263 | var used = new bool[len];
|
---|
[12285] | 264 | for (var i = 0; i < len; i++) {
|
---|
[14487] | 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;
|
---|
[12285] | 271 | next = array[next];
|
---|
[14487] | 272 | }
|
---|
| 273 | if (curr!=next) return false;
|
---|
| 274 | used[curr] = true;
|
---|
[12285] | 275 | }
|
---|
[14487] | 276 | return true;
|
---|
[12285] | 277 | }
|
---|
[12288] | 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.
|
---|
[12396] | 283 | /// Consider following 1-based index array: 6, 6, 7, 5, 5, 8, 8, 8, 9.
|
---|
[12288] | 284 | /// This results in the following tree structure for group 8:
|
---|
| 285 | /// 8
|
---|
| 286 | /// / \
|
---|
| 287 | /// 6 7
|
---|
[12396] | 288 | /// / \ |
|
---|
| 289 | /// 1 2 3
|
---|
[12288] | 290 | /// After this operation the array will be 2, 3, 6, 5, 5, 7, 8, 8, 9.
|
---|
[12396] | 291 | /// Representing a tree with one branch: 1 -> 2 -> 3 -> 6 -> 7 -> 8
|
---|
[12288] | 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.
|
---|
[12396] | 297 | /// The runtime complexity is O(n).
|
---|
[12288] | 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
|
---|
[14487] | 303 | ToEndLinksInplace(array);
|
---|
[12396] | 304 | // Step 2: For all groups linearize the links
|
---|
[14487] | 305 | SetEndLinks(array);
|
---|
[12396] | 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>
|
---|
[14487] | 320 | public int[] ToEndLinks() {
|
---|
[12396] | 321 | var result = (int[])array.Clone();
|
---|
[14487] | 322 | ToEndLinksInplace(result);
|
---|
[12396] | 323 | return result;
|
---|
| 324 | }
|
---|
| 325 |
|
---|
[14487] | 326 | private static void ToEndLinksInplace(int[] array) {
|
---|
| 327 | var length = array.Length;
|
---|
[12396] | 328 | for (var i = length - 1; i >= 0; i--) {
|
---|
[14487] | 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 | }
|
---|
[12396] | 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
|
---|
[14487] | 344 | /// in form of a int[].
|
---|
[12396] | 345 | /// </remarks>
|
---|
| 346 | /// <param name="llee">The LLE-e representation</param>
|
---|
[14487] | 347 | public void SetEndLinks(int[] llee) {
|
---|
[12288] | 348 | var length = array.Length;
|
---|
[14487] | 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();
|
---|
[12288] | 354 | for (var i = length - 1; i >= 0; i--) {
|
---|
[14487] | 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;
|
---|
[12396] | 361 | } else {
|
---|
[14487] | 362 | throw new ArgumentException("Array is malformed and does not represent a valid LLE end encoding.", "llee");
|
---|
[12396] | 363 | }
|
---|
[12288] | 364 | }
|
---|
| 365 | }
|
---|
[12285] | 366 | }
|
---|
| 367 | }
|
---|