1  #region License Information


2  /* HeuristicLab


3  * Copyright (C) 20022015 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 


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 {


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 1based 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 LLEe 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 LLEe


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 LLEe.


225  /// </summary>


226  /// <remarks>


227  /// LLEe 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 LLEe.


231  ///


232  /// This operation runs in O(n) time.


233  /// </remarks>


234  /// <returns>An integer array in LLEe 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 LLEe 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 LLEe 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  }

