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 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 1based index array: 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 3


191  /// After this operation the array will be 2, 3, 6, 5, 5, 7, 8, 8, 9.


192  /// Representing a tree with one branch: 1 > 2 > 3 > 6 > 7 > 8


193  /// </summary>


194  /// <remarks>


195  /// The method first converts the array to LLEe format and then


196  /// linearizes the links. This requires two passes of the whole array


197  /// as well as a dictionary to hold the smallest index of each group.


198  /// The runtime complexity is O(n).


199  ///


200  /// The method assumes that there are no back links present.


201  /// </remarks>


202  public void LinearizeTreeStructures() {


203  // Step 1: Convert the array into LLEe


204  ToLLEeInplace(array);


205  // Step 2: For all groups linearize the links


206  FromLLEe(array);


207  }


208 


209  /// <summary>


210  /// Creates a copy of the underlying array and turns it into LLEe.


211  /// </summary>


212  /// <remarks>


213  /// LLEe is a special format where each element points to the


214  /// ending item of a group.


215  /// The LLE representation 2, 3, 5, 6, 5, 7, 8, 8 would become


216  /// 5, 5, 5, 8, 5, 8, 8, 8 in LLEe.


217  ///


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


219  /// </remarks>


220  /// <returns>An integer array in LLEe representation</returns>


221  public int[] ToLLEe() {


222  var result = (int[])array.Clone();


223  ToLLEeInplace(result);


224  return result;


225  }


226 


227  private void ToLLEeInplace(int[] a) {


228  var length = a.Length;


229  for (var i = length  1; i >= 0; i) {


230  if (array[i] == i) a[i] = i;


231  else a[i] = a[a[i]];


232  }


233  }


234 


235  /// <summary>


236  /// Parses an LLEe representation and modifies the underlying array


237  /// so that it is in LLE representation.


238  /// </summary>


239  /// <remarks>


240  /// This operation runs in O(n) time, but requires additional memory


241  /// in form of a dictionary.


242  /// </remarks>


243  /// <param name="llee">The LLEe representation</param>


244  public void FromLLEe(int[] llee) {


245  var length = array.Length;


246  var groups = new Dictionary<int, int>();


247  for (var i = length  1; i >= 0; i) {


248  if (llee[i] == i) {


249  array[i] = i;


250  groups[i] = i;


251  } else {


252  var g = llee[i];


253  array[i] = groups[g];


254  groups[g] = i;


255  }


256  }


257  }


258  }


259  }

