1  #region License Information


2 


3  /* HeuristicLab


4  * Copyright (C) 20022016 Heuristic and Evolutionary Algorithms Laboratory (HEAL)


5  *


6  * This file is part of HeuristicLab.


7  *


8  * HeuristicLab is free software: you can redistribute it and/or modify


9  * it under the terms of the GNU General Public License as published by


10  * the Free Software Foundation, either version 3 of the License, or


11  * (at your option) any later version.


12  *


13  * HeuristicLab is distributed in the hope that it will be useful,


14  * but WITHOUT ANY WARRANTY; without even the implied warranty of


15  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the


16  * GNU General Public License for more details.


17  *


18  * You should have received a copy of the GNU General Public License


19  * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.


20  */


21 


22  #endregion


23 


24  using System;


25  using System.Collections.Generic;


26  using System.Linq;


27  namespace HeuristicLab.Encodings.SymbolicExpressionTreeEncoding {


28  public static class GrammarUtils {


29  private static IEnumerable<ISymbol> GetTopmostSymbols(this ISymbolicExpressionGrammarBase grammar) {


30  // build parents list so we can find out the topmost symbol(s)


31  var parents = new Dictionary<ISymbol, List<ISymbol>>();


32  foreach (var symbol in grammar.Symbols.Where(x => grammar.GetMinimumSubtreeCount(x) > 0)) {


33  var minSubtreeCount = grammar.GetMinimumSubtreeCount(symbol);


34  for (int argIndex = 0; argIndex < minSubtreeCount; ++argIndex) {


35  foreach (var childSymbol in grammar.GetAllowedActiveSymbols(symbol, argIndex)) {


36  if (!parents.ContainsKey(childSymbol))


37  parents[childSymbol] = new List<ISymbol>();


38  parents[childSymbol].Add(symbol);


39  }


40  }


41  }


42  // the topmost symbols have no parents


43  return parents.Values.SelectMany(x => x).Distinct().Where(x => !parents.ContainsKey(x));


44  }


45 


46  private static IReadOnlyCollection<ISymbol> IterateBreadthReverse(this ISymbolicExpressionGrammarBase grammar, ISymbol topSymbol) {


47  // sort symbols in reverse breadth order (starting from the topSymbol)


48  // each symbol is visited only once (this avoids infinite recursion)


49  var symbols = new List<ISymbol> { topSymbol };


50  var visited = new HashSet<ISymbol> { topSymbol };


51  int i = 0;


52  while (i < symbols.Count) {


53  var symbol = symbols[i];


54  var minSubtreeCount = grammar.GetMinimumSubtreeCount(symbol);


55 


56  for (int argIndex = 0; argIndex < minSubtreeCount; ++argIndex) {


57  foreach (var childSymbol in grammar.GetAllowedActiveSymbols(symbol, argIndex)) {


58  if (grammar.GetMinimumSubtreeCount(childSymbol) == 0)


59  continue;


60 


61  if (visited.Add(childSymbol))


62  symbols.Add(childSymbol);


63  }


64  }


65  ++i;


66  }


67  symbols.Reverse();


68  return symbols;


69  }


70 


71  private static IEnumerable<ISymbol> GetAllowedActiveSymbols(this ISymbolicExpressionGrammarBase grammar, ISymbol symbol, int argIndex) {


72  return grammar.GetAllowedChildSymbols(symbol, argIndex).Where(s => s.InitialFrequency > 0);


73  }


74 


75  public static void CalculateMinimumExpressionLengths(ISymbolicExpressionGrammarBase grammar,


76  Dictionary<string, int> minimumExpressionLengths) {


77  minimumExpressionLengths.Clear();


78  //terminal symbols => minimum expression length = 1


79  foreach (var s in grammar.Symbols) {


80  if (grammar.GetMinimumSubtreeCount(s) == 0)


81  minimumExpressionLengths[s.Name] = 1;


82  else


83  minimumExpressionLengths[s.Name] = int.MaxValue;


84  }


85 


86  foreach (var topSymbol in grammar.GetTopmostSymbols()) {


87  // get all symbols below in reverse breadth order


88  // this way we ensure lengths are calculated bottomup


89  var symbols = grammar.IterateBreadthReverse(topSymbol);


90  foreach (var symbol in symbols) {


91  long minLength = 1;


92  for (int argIndex = 0; argIndex < grammar.GetMinimumSubtreeCount(symbol); ++argIndex) {


93  long length = grammar.GetAllowedActiveSymbols(symbol, argIndex)


94  .Where(x => minimumExpressionLengths.ContainsKey(x.Name))


95  .Select(x => minimumExpressionLengths[x.Name]).DefaultIfEmpty(int.MaxValue).Min();


96  minLength += length;


97  }


98  int oldLength;


99  if (minimumExpressionLengths.TryGetValue(symbol.Name, out oldLength))


100  minLength = Math.Min(minLength, oldLength);


101  minimumExpressionLengths[symbol.Name] = (int)Math.Min(int.MaxValue, minLength);


102  }


103  // correction step for cycles


104  bool changed = true;


105  while (changed) {


106  changed = false;


107  foreach (var symbol in symbols) {


108  long minLength = Enumerable.Range(0, grammar.GetMinimumSubtreeCount(symbol))


109  .Sum(x => grammar.GetAllowedActiveSymbols(symbol, x)


110  .Select(s => (long)minimumExpressionLengths[s.Name]).DefaultIfEmpty(int.MaxValue).Min()) + 1;


111  if (minLength < minimumExpressionLengths[symbol.Name]) {


112  minimumExpressionLengths[symbol.Name] = (int)Math.Min(minLength, int.MaxValue);


113  changed = true;


114  }


115  }


116  }


117  }


118  }


119 


120  public static void CalculateMinimumExpressionDepth(ISymbolicExpressionGrammarBase grammar,


121  Dictionary<string, int> minimumExpressionDepths) {


122 


123  minimumExpressionDepths.Clear();


124  //terminal symbols => minimum expression depth = 1


125  foreach (var s in grammar.Symbols) {


126  if (grammar.GetMinimumSubtreeCount(s) == 0)


127  minimumExpressionDepths[s.Name] = 1;


128  else


129  minimumExpressionDepths[s.Name] = int.MaxValue;


130  }


131 


132  foreach (var topSymbol in grammar.GetTopmostSymbols()) {


133  // get all symbols below in reverse breadth order


134  // this way we ensure lengths are calculated bottomup


135  var symbols = grammar.IterateBreadthReverse(topSymbol);


136  foreach (var symbol in symbols) {


137  long minDepth = 1;


138  for (int argIndex = 0; argIndex < grammar.GetMinimumSubtreeCount(symbol); ++argIndex) {


139  long depth = grammar.GetAllowedActiveSymbols(symbol, argIndex)


140  .Where(x => minimumExpressionDepths.ContainsKey(x.Name))


141  .Select(x => (long)minimumExpressionDepths[x.Name]).DefaultIfEmpty(int.MaxValue).Min() + 1;


142  minDepth = Math.Max(minDepth, depth);


143  }


144  int oldDepth;


145  if (minimumExpressionDepths.TryGetValue(symbol.Name, out oldDepth))


146  minDepth = Math.Min(minDepth, oldDepth);


147  minimumExpressionDepths[symbol.Name] = (int)Math.Min(int.MaxValue, minDepth);


148  }


149  // correction step for cycles


150  bool changed = true;


151  while (changed) {


152  changed = false;


153  foreach (var symbol in symbols) {


154  long minDepth = Enumerable.Range(0, grammar.GetMinimumSubtreeCount(symbol))


155  .Max(x => grammar.GetAllowedActiveSymbols(symbol, x)


156  .Select(s => (long)minimumExpressionDepths[s.Name]).DefaultIfEmpty(int.MaxValue).Min()) + 1;


157  if (minDepth < minimumExpressionDepths[symbol.Name]) {


158  minimumExpressionDepths[symbol.Name] = (int)Math.Min(minDepth, int.MaxValue);


159  changed = true;


160  }


161  }


162  }


163  }


164  }


165  }


166  }

