Free cookie consent management tool by TermsFeed Policy Generator

Changeset 14958


Ignore:
Timestamp:
05/10/17 15:44:17 (8 years ago)
Author:
mkommend
Message:

#2685: Merged r14340, r14341, r14342, r14352, r14353, r14354, r14355, r14356, r14357 into stable.

Location:
stable
Files:
7 edited
2 copied

Legend:

Unmodified
Added
Removed

  • stable

  • stable/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding

  • stable/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/Grammars/GrammarUtils.cs

    r14342 r14958  
    2525using System.Collections.Generic;
    2626using System.Linq;
    27 
    2827namespace HeuristicLab.Encodings.SymbolicExpressionTreeEncoding {
    2928  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    }
    3074
    3175    public static void CalculateMinimumExpressionLengths(ISymbolicExpressionGrammarBase grammar,
    3276      Dictionary<string, int> minimumExpressionLengths) {
    33 
    3477      minimumExpressionLengths.Clear();
    3578      //terminal symbols => minimum expression length = 1
    36       foreach (var s in grammar.Symbols.Where(s => grammar.GetMinimumSubtreeCount(s) == 0))
    37         minimumExpressionLengths[s.Name] = 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      }
    3885
    39       var symbolAdded = true;
    40       while (symbolAdded) {
    41         symbolAdded = false;
    42         foreach (var remainingSymbol in grammar.Symbols) {
    43           if (minimumExpressionLengths.ContainsKey(remainingSymbol.Name)) continue;
    44 
    45           var arguments = grammar.GetMinimumSubtreeCount(remainingSymbol);
    46           int minLength = 1;
    47 
    48           foreach (int argumentIndex in Enumerable.Range(0, arguments)) {
    49             var capturedMinimumLengths = minimumExpressionLengths;
    50             var childSymbols = grammar.GetAllowedChildSymbols(remainingSymbol, argumentIndex)
    51               .Where(c => c.InitialFrequency > 0.0 && capturedMinimumLengths.ContainsKey(c.Name));
    52 
    53             if (!childSymbols.Any()) {
    54               minLength = -1;
    55               break;
     86      foreach (var topSymbol in grammar.GetTopmostSymbols()) {
     87        // get all symbols below in reverse breadth order
     88        // this way we ensure lengths are calculated bottom-up
     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;
    56114            }
    57             var minLengthPerArgument = childSymbols.Min(c => capturedMinimumLengths[c.Name]);
    58             minLength += minLengthPerArgument;
    59           }
    60 
    61           if (minLength != -1) {
    62             minimumExpressionLengths[remainingSymbol.Name] = minLength;
    63             symbolAdded = true;
    64115          }
    65116        }
    66117      }
    67 
    68       //set minLength to int.Maxvalue for all symbols that are not reacheable
    69       foreach (var remainingSymbols in grammar.Symbols) {
    70         if (!minimumExpressionLengths.ContainsKey(remainingSymbols.Name))
    71           minimumExpressionLengths[remainingSymbols.Name] = int.MaxValue;
    72       }
    73118    }
    74 
    75119
    76120    public static void CalculateMinimumExpressionDepth(ISymbolicExpressionGrammarBase grammar,
    … …  
    79123      minimumExpressionDepths.Clear();
    80124      //terminal symbols => minimum expression depth = 1
    81       foreach (var s in grammar.Symbols.Where(s => grammar.GetMinimumSubtreeCount(s) == 0))
    82         minimumExpressionDepths[s.Name] = 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      }
    83131
    84       var symbolAdded = true;
    85       while (symbolAdded) {
    86         symbolAdded = false;
    87         foreach (var remainingSymbol in grammar.Symbols) {
    88           if (minimumExpressionDepths.ContainsKey(remainingSymbol.Name)) continue;
    89 
    90           var arguments = grammar.GetMinimumSubtreeCount(remainingSymbol);
    91           int minDepth = -1;
    92 
    93           foreach (int argumentIndex in Enumerable.Range(0, arguments)) {
    94             var capturedMinimumDepths = minimumExpressionDepths;
    95             var childSymbols = grammar.GetAllowedChildSymbols(remainingSymbol, argumentIndex)
    96               .Where(c => c.InitialFrequency > 0.0 && capturedMinimumDepths.ContainsKey(c.Name));
    97             if (!childSymbols.Any()) {
    98               minDepth = -1;
    99               break;
     132      foreach (var topSymbol in grammar.GetTopmostSymbols()) {
     133        // get all symbols below in reverse breadth order
     134        // this way we ensure lengths are calculated bottom-up
     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;
    100160            }
    101             var minDepthPerArgument = childSymbols.Min(c => capturedMinimumDepths[c.Name]);
    102             minDepth = Math.Max(minDepth, 1 + minDepthPerArgument);
    103           }
    104 
    105           if (minDepth != -1) {
    106             minimumExpressionDepths[remainingSymbol.Name] = minDepth;
    107             symbolAdded = true;
    108161          }
    109162        }
    110       }
    111 
    112       //set minDepth to int.Maxvalue for all symbols that are not reacheable
    113       foreach (var remainingSymbols in grammar.Symbols) {
    114         if (!minimumExpressionDepths.ContainsKey(remainingSymbols.Name))
    115           minimumExpressionDepths[remainingSymbols.Name] = int.MaxValue;
    116163      }
    117164    }

  • stable/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/Grammars/SymbolicExpressionGrammarBase.cs

    r14186 r14958  
    8282    protected SymbolicExpressionGrammarBase(bool deserializing)
    8383      : base(deserializing) {
    84       cachedMinExpressionLength = new Dictionary<string, int>();
    85       cachedMaxExpressionLength = new Dictionary<Tuple<string, int>, int>();
    86       cachedMinExpressionDepth = new Dictionary<string, int>();
    87       cachedMaxExpressionDepth = new Dictionary<string, int>();
    88 
    89       cachedIsAllowedChildSymbol = new Dictionary<Tuple<string, string>, bool>();
    90       cachedIsAllowedChildSymbolIndex = new Dictionary<Tuple<string, string, int>, bool>();
    9184
    9285      symbols = new Dictionary<string, ISymbol>();
    … …  
    10093    protected SymbolicExpressionGrammarBase(SymbolicExpressionGrammarBase original, Cloner cloner)
    10194      : base(original, cloner) {
    102       cachedMinExpressionLength = new Dictionary<string, int>();
    103       cachedMaxExpressionLength = new Dictionary<Tuple<string, int>, int>();
    104       cachedMinExpressionDepth = new Dictionary<string, int>();
    105       cachedMaxExpressionDepth = new Dictionary<string, int>();
    106 
    107       cachedIsAllowedChildSymbol = new Dictionary<Tuple<string, string>, bool>();
    108       cachedIsAllowedChildSymbolIndex = new Dictionary<Tuple<string, string, int>, bool>();
    10995
    11096      symbols = original.symbols.ToDictionary(x => x.Key, y => cloner.Clone(y.Value));
    … …  
    124110    protected SymbolicExpressionGrammarBase(string name, string description)
    125111      : base(name, description) {
    126       cachedMinExpressionLength = new Dictionary<string, int>();
    127       cachedMaxExpressionLength = new Dictionary<Tuple<string, int>, int>();
    128       cachedMinExpressionDepth = new Dictionary<string, int>();
    129       cachedMaxExpressionDepth = new Dictionary<string, int>();
    130 
    131       cachedIsAllowedChildSymbol = new Dictionary<Tuple<string, string>, bool>();
    132       cachedIsAllowedChildSymbolIndex = new Dictionary<Tuple<string, string, int>, bool>();
    133 
    134112      symbols = new Dictionary<string, ISymbol>();
    135113      symbolSubtreeCount = new Dictionary<string, Tuple<int, int>>();
    … …  
    322300    }
    323301
    324     private readonly Dictionary<Tuple<string, string>, bool> cachedIsAllowedChildSymbol;
     302    private readonly Dictionary<Tuple<string, string>, bool> cachedIsAllowedChildSymbol = new Dictionary<Tuple<string, string>, bool>();
    325303    public virtual bool IsAllowedChildSymbol(ISymbol parent, ISymbol child) {
    326304      if (allowedChildSymbols.Count == 0) return false;
    … …  
    352330    }
    353331
    354     private readonly Dictionary<Tuple<string, string, int>, bool> cachedIsAllowedChildSymbolIndex;
     332    private readonly Dictionary<Tuple<string, string, int>, bool> cachedIsAllowedChildSymbolIndex = new Dictionary<Tuple<string, string, int>, bool>();
    355333    public virtual bool IsAllowedChildSymbol(ISymbol parent, ISymbol child, int argumentIndex) {
    356334      if (!child.Enabled) return false;
    … …  
    412390    }
    413391
    414     private readonly Dictionary<string, int> cachedMinExpressionLength;
     392    private readonly Dictionary<string, int> cachedMinExpressionLength = new Dictionary<string, int>();
    415393    public int GetMinimumExpressionLength(ISymbol symbol) {
    416394      int res;
    … …  
    423401        if (cachedMinExpressionLength.TryGetValue(symbol.Name, out res)) return res;
    424402
    425         res = GetMinimumExpressionLengthRec(symbol);
    426         foreach (var entry in cachedMinExpressionLength.Where(e => e.Value >= int.MaxValue).ToList()) {
    427           if (entry.Key != symbol.Name) cachedMinExpressionLength.Remove(entry.Key);
    428         }
    429         return res;
    430       }
    431     }
    432 
    433     private int GetMinimumExpressionLengthRec(ISymbol symbol) {
    434       int temp;
    435       if (!cachedMinExpressionLength.TryGetValue(symbol.Name, out temp)) {
    436         cachedMinExpressionLength[symbol.Name] = int.MaxValue; // prevent infinite recursion
    437         long sumOfMinExpressionLengths = 1 + (from argIndex in Enumerable.Range(0, GetMinimumSubtreeCount(symbol))
    438                                               let minForSlot = (long)(from s in GetAllowedChildSymbols(symbol, argIndex)
    439                                                                       where s.InitialFrequency > 0.0
    440                                                                       select GetMinimumExpressionLengthRec(s)).DefaultIfEmpty(0).Min()
    441                                               select minForSlot).DefaultIfEmpty(0).Sum();
    442 
    443         cachedMinExpressionLength[symbol.Name] = (int)Math.Min(sumOfMinExpressionLengths, int.MaxValue);
     403        GrammarUtils.CalculateMinimumExpressionLengths(this, cachedMinExpressionLength);
    444404        return cachedMinExpressionLength[symbol.Name];
    445405      }
    446       return temp;
    447     }
    448 
    449     private readonly Dictionary<Tuple<string, int>, int> cachedMaxExpressionLength;
     406    }
     407
     408
     409    private readonly Dictionary<Tuple<string, int>, int> cachedMaxExpressionLength = new Dictionary<Tuple<string, int>, int>();
    450410    public int GetMaximumExpressionLength(ISymbol symbol, int maxDepth) {
    451411      int temp;
    … …  
    469429    }
    470430
    471     private readonly Dictionary<string, int> cachedMinExpressionDepth;
     431    private readonly Dictionary<string, int> cachedMinExpressionDepth = new Dictionary<string, int>();
    472432    public int GetMinimumExpressionDepth(ISymbol symbol) {
    473433      int res;
    … …  
    480440        if (cachedMinExpressionDepth.TryGetValue(symbol.Name, out res)) return res;
    481441
    482         res = GetMinimumExpressionDepthRec(symbol);
    483         foreach (var entry in cachedMinExpressionDepth.Where(e => e.Value >= int.MaxValue).ToList()) {
    484           if (entry.Key != symbol.Name) cachedMinExpressionDepth.Remove(entry.Key);
    485         }
    486         return res;
    487       }
    488     }
    489     private int GetMinimumExpressionDepthRec(ISymbol symbol) {
    490       int temp;
    491       if (!cachedMinExpressionDepth.TryGetValue(symbol.Name, out temp)) {
    492         cachedMinExpressionDepth[symbol.Name] = int.MaxValue; // prevent infinite recursion
    493         long minDepth = 1 + (from argIndex in Enumerable.Range(0, GetMinimumSubtreeCount(symbol))
    494                              let minForSlot = (long)(from s in GetAllowedChildSymbols(symbol, argIndex)
    495                                                      where s.InitialFrequency > 0.0
    496                                                      select GetMinimumExpressionDepthRec(s)).DefaultIfEmpty(0).Min()
    497                              select minForSlot).DefaultIfEmpty(0).Max();
    498         cachedMinExpressionDepth[symbol.Name] = (int)Math.Min(minDepth, int.MaxValue);
     442        GrammarUtils.CalculateMinimumExpressionDepth(this, cachedMinExpressionDepth);
    499443        return cachedMinExpressionDepth[symbol.Name];
    500444      }
    501       return temp;
    502     }
    503 
    504     private readonly Dictionary<string, int> cachedMaxExpressionDepth;
     445    }
     446
     447    private readonly Dictionary<string, int> cachedMaxExpressionDepth = new Dictionary<string, int>();
    505448    public int GetMaximumExpressionDepth(ISymbol symbol) {
    506449      int temp;

  • stable/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding-3.4.csproj

    r13278 r14958  
    129129    <Compile Include="ArchitectureManipulators\SubroutineDuplicater.cs" />
    130130    <Compile Include="ArchitectureManipulators\SymbolicExpressionTreeArchitectureManipulator.cs" />
     131    <Compile Include="Grammars\GrammarUtils.cs" />
    131132    <Compile Include="SymbolicExpressionTreeProblem.cs" />
    132133    <Compile Include="Compiler\Instruction.cs" />

  • stable/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/Symbols/SimpleSymbol.cs

    r14186 r14958  
    6161    }
    6262
     63    public SimpleSymbol(string name, int arity)
     64      : this(name, string.Empty, arity, arity) {
     65    }
     66
    6367    public SimpleSymbol(string name, string description, int minimumArity, int maximumArity)
    6468      : base(name, description) {

  • stable/HeuristicLab.Tests

  • stable/HeuristicLab.Tests/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding-3.4/GrammarsTest.cs

    r14342 r14958  
    3030    [TestProperty("Time", "short")]
    3131    public void MinimumExpressionLengthTest() {
    32       var grammar = CreateAbstractGrammar();
    33 
    34       var prs = grammar.ProgramRootSymbol;
    35       var a = grammar.Symbols.First(s => s.Name == "<a>");
    36       var b = grammar.Symbols.First(s => s.Name == "<b>");
    37 
    38       Assert.AreEqual(4, grammar.GetMinimumExpressionLength(prs));
    39       Assert.AreEqual(4, grammar.GetMinimumExpressionLength(a));
    40       Assert.AreEqual(3, grammar.GetMinimumExpressionLength(b));
     32      {
     33        var grammar = CreateTestGrammar1();
     34
     35        var prs = grammar.ProgramRootSymbol;
     36        var ss = grammar.StartSymbol;
     37        var x = grammar.Symbols.First(s => s.Name == "<x>");
     38
     39        Assert.AreEqual(8, grammar.GetMinimumExpressionLength(prs));
     40        Assert.AreEqual(7, grammar.GetMinimumExpressionLength(ss));
     41        Assert.AreEqual(6, grammar.GetMinimumExpressionLength(x));
     42      }
     43
     44      {
     45        var grammar = CreateTestGrammar2();
     46
     47        var prs = grammar.ProgramRootSymbol;
     48        var ss = grammar.StartSymbol;
     49        var x = grammar.Symbols.First(s => s.Name == "<x>");
     50
     51        Assert.AreEqual(13, grammar.GetMinimumExpressionLength(prs));
     52        Assert.AreEqual(12, grammar.GetMinimumExpressionLength(ss));
     53        Assert.AreEqual(11, grammar.GetMinimumExpressionLength(x));
     54      }
     55
     56      {
     57        var grammar = CreateTestGrammar3();
     58        var prs = grammar.ProgramRootSymbol;
     59        var ss = grammar.StartSymbol;
     60        var x = grammar.Symbols.First(s => s.Name == "<x>");
     61        Assert.AreEqual(int.MaxValue, grammar.GetMinimumExpressionLength(prs));
     62        Assert.AreEqual(int.MaxValue, grammar.GetMinimumExpressionLength(ss));
     63        Assert.AreEqual(int.MaxValue, grammar.GetMinimumExpressionLength(x));
     64      }
     65
     66      {
     67        var grammar = CreateTestGrammar4();
     68        var prs = grammar.ProgramRootSymbol;
     69        var ss = grammar.StartSymbol;
     70        var x = grammar.Symbols.First(s => s.Name == "<x>");
     71        var y = grammar.Symbols.First(s => s.Name == "<y>");
     72        Assert.AreEqual(int.MaxValue, grammar.GetMinimumExpressionLength(prs));
     73        Assert.AreEqual(int.MaxValue, grammar.GetMinimumExpressionLength(ss));
     74        Assert.AreEqual(int.MaxValue, grammar.GetMinimumExpressionLength(x));
     75        Assert.AreEqual(int.MaxValue, grammar.GetMinimumExpressionLength(y));
     76      }
     77
     78      {
     79        var grammar = CreateTestGrammar5();
     80        var prs = grammar.ProgramRootSymbol;
     81        var ss = grammar.StartSymbol;
     82        var x = grammar.Symbols.First(s => s.Name == "<x>");
     83        var y = grammar.Symbols.First(s => s.Name == "<y>");
     84        Assert.AreEqual(5, grammar.GetMinimumExpressionLength(prs));
     85        Assert.AreEqual(4, grammar.GetMinimumExpressionLength(ss));
     86        Assert.AreEqual(3, grammar.GetMinimumExpressionLength(x));
     87        Assert.AreEqual(2, grammar.GetMinimumExpressionLength(y));
     88      }
     89
     90      {
     91        var grammar = CreateTestGrammar6();
     92        var prs = grammar.ProgramRootSymbol;
     93        var ss = grammar.StartSymbol;
     94        var x = grammar.Symbols.First(s => s.Name == "<x>");
     95        var s_ = grammar.Symbols.First(s => s.Name == "<s>");
     96        var a = grammar.Symbols.First(s => s.Name == "<a>");
     97        var b = grammar.Symbols.First(s => s.Name == "<b>");
     98        var c = grammar.Symbols.First(s => s.Name == "<c>");
     99        var d = grammar.Symbols.First(s => s.Name == "<d>");
     100        Assert.AreEqual(4, grammar.GetMinimumExpressionLength(prs));
     101        Assert.AreEqual(3, grammar.GetMinimumExpressionLength(ss));
     102        Assert.AreEqual(2, grammar.GetMinimumExpressionLength(x));
     103        Assert.AreEqual(5, grammar.GetMinimumExpressionLength(s_));
     104        Assert.AreEqual(4, grammar.GetMinimumExpressionLength(a));
     105        Assert.AreEqual(3, grammar.GetMinimumExpressionLength(b));
     106        Assert.AreEqual(4, grammar.GetMinimumExpressionLength(c));
     107        Assert.AreEqual(3, grammar.GetMinimumExpressionLength(d));
     108      }
    41109    }
    42110
    … …  
    45113    [TestProperty("Time", "short")]
    46114    public void MinimumExpressionDepthTest() {
    47       var grammar = CreateAbstractGrammar();
    48 
    49       var prs = grammar.ProgramRootSymbol;
    50       var a = grammar.Symbols.First(s => s.Name == "<a>");
    51       var b = grammar.Symbols.First(s => s.Name == "<b>");
    52 
    53       Assert.AreEqual(4, grammar.GetMinimumExpressionDepth(prs));
    54       Assert.AreEqual(4, grammar.GetMinimumExpressionDepth(a));
    55       Assert.AreEqual(3, grammar.GetMinimumExpressionDepth(b));
    56     }
    57 
    58     private static ISymbolicExpressionGrammar CreateAbstractGrammar() {
     115      {
     116        var grammar = CreateTestGrammar1();
     117
     118        var prs = grammar.ProgramRootSymbol;
     119        var ss = grammar.StartSymbol;
     120        var a = grammar.Symbols.First(s => s.Name == "<a>");
     121        var b = grammar.Symbols.First(s => s.Name == "<b>");
     122        var c = grammar.Symbols.First(s => s.Name == "<c>");
     123        var d = grammar.Symbols.First(s => s.Name == "<d>");
     124        var x = grammar.Symbols.First(s => s.Name == "x");
     125        var y = grammar.Symbols.First(s => s.Name == "y");
     126
     127        Assert.AreEqual(5, grammar.GetMinimumExpressionDepth(prs));
     128        Assert.AreEqual(4, grammar.GetMinimumExpressionDepth(ss));
     129        Assert.AreEqual(5, grammar.GetMinimumExpressionDepth(a));
     130        Assert.AreEqual(4, grammar.GetMinimumExpressionDepth(b));
     131        Assert.AreEqual(3, grammar.GetMinimumExpressionDepth(c));
     132        Assert.AreEqual(2, grammar.GetMinimumExpressionDepth(d));
     133        Assert.AreEqual(1, grammar.GetMinimumExpressionDepth(x));
     134        Assert.AreEqual(1, grammar.GetMinimumExpressionDepth(y));
     135      }
     136
     137      {
     138        var grammar = CreateTestGrammar2();
     139
     140        var prs = grammar.ProgramRootSymbol;
     141        var ss = grammar.StartSymbol;
     142        var a = grammar.Symbols.First(s => s.Name == "<a>");
     143        var b = grammar.Symbols.First(s => s.Name == "<b>");
     144        var c = grammar.Symbols.First(s => s.Name == "<c>");
     145        var d = grammar.Symbols.First(s => s.Name == "<d>");
     146        var x = grammar.Symbols.First(s => s.Name == "x");
     147        var y = grammar.Symbols.First(s => s.Name == "y");
     148
     149        Assert.AreEqual(5, grammar.GetMinimumExpressionDepth(prs));
     150        Assert.AreEqual(4, grammar.GetMinimumExpressionDepth(ss));
     151        Assert.AreEqual(5, grammar.GetMinimumExpressionDepth(a));
     152        Assert.AreEqual(4, grammar.GetMinimumExpressionDepth(b));
     153        Assert.AreEqual(3, grammar.GetMinimumExpressionDepth(c));
     154        Assert.AreEqual(2, grammar.GetMinimumExpressionDepth(d));
     155        Assert.AreEqual(1, grammar.GetMinimumExpressionDepth(x));
     156        Assert.AreEqual(1, grammar.GetMinimumExpressionDepth(y));
     157      }
     158
     159      {
     160        var grammar = CreateTestGrammar3();
     161        var prs = grammar.ProgramRootSymbol;
     162        var ss = grammar.StartSymbol;
     163        var x = grammar.Symbols.First(s => s.Name == "<x>");
     164        Assert.AreEqual(int.MaxValue, grammar.GetMinimumExpressionDepth(prs));
     165        Assert.AreEqual(int.MaxValue, grammar.GetMinimumExpressionDepth(ss));
     166        Assert.AreEqual(int.MaxValue, grammar.GetMinimumExpressionDepth(x));
     167      }
     168
     169      {
     170        var grammar = CreateTestGrammar4();
     171        var prs = grammar.ProgramRootSymbol;
     172        var ss = grammar.StartSymbol;
     173        var x = grammar.Symbols.First(s => s.Name == "<x>");
     174        var y = grammar.Symbols.First(s => s.Name == "<y>");
     175        Assert.AreEqual(int.MaxValue, grammar.GetMinimumExpressionDepth(prs));
     176        Assert.AreEqual(int.MaxValue, grammar.GetMinimumExpressionDepth(ss));
     177        Assert.AreEqual(int.MaxValue, grammar.GetMinimumExpressionDepth(x));
     178        Assert.AreEqual(int.MaxValue, grammar.GetMinimumExpressionDepth(y));
     179      }
     180
     181      {
     182        var grammar = CreateTestGrammar5();
     183        var prs = grammar.ProgramRootSymbol;
     184        var ss = grammar.StartSymbol;
     185        var x = grammar.Symbols.First(s => s.Name == "<x>");
     186        var y = grammar.Symbols.First(s => s.Name == "<y>");
     187        Assert.AreEqual(5, grammar.GetMinimumExpressionDepth(prs));
     188        Assert.AreEqual(4, grammar.GetMinimumExpressionDepth(ss));
     189        Assert.AreEqual(3, grammar.GetMinimumExpressionDepth(x));
     190        Assert.AreEqual(2, grammar.GetMinimumExpressionDepth(y));
     191      }
     192
     193      {
     194        var grammar = CreateTestGrammar6();
     195        var prs = grammar.ProgramRootSymbol;
     196        var ss = grammar.StartSymbol;
     197        var x = grammar.Symbols.First(s => s.Name == "<x>");
     198        var s_ = grammar.Symbols.First(s => s.Name == "<s>");
     199        var a = grammar.Symbols.First(s => s.Name == "<a>");
     200        var b = grammar.Symbols.First(s => s.Name == "<b>");
     201        var c = grammar.Symbols.First(s => s.Name == "<c>");
     202        var d = grammar.Symbols.First(s => s.Name == "<d>");
     203        Assert.AreEqual(4, grammar.GetMinimumExpressionDepth(prs));
     204        Assert.AreEqual(3, grammar.GetMinimumExpressionDepth(ss));
     205        Assert.AreEqual(2, grammar.GetMinimumExpressionDepth(x));
     206        Assert.AreEqual(5, grammar.GetMinimumExpressionDepth(s_));
     207        Assert.AreEqual(4, grammar.GetMinimumExpressionDepth(a));
     208        Assert.AreEqual(3, grammar.GetMinimumExpressionDepth(b));
     209        Assert.AreEqual(4, grammar.GetMinimumExpressionDepth(c));
     210        Assert.AreEqual(3, grammar.GetMinimumExpressionDepth(d));
     211      }
     212    }
     213
     214    private static ISymbolicExpressionGrammar CreateTestGrammar1() {
     215      var grammar = new SimpleSymbolicExpressionGrammar();
     216      var x = new SimpleSymbol("<x>", 1);
     217      var z = new SimpleSymbol("<z>", 6);
     218      var a = new SimpleSymbol("<a>", 1);
     219      var b = new SimpleSymbol("<b>", 1);
     220      var c = new SimpleSymbol("<c>", 1);
     221      var d = new SimpleSymbol("<d>", 1);
     222
     223      var _x = new SimpleSymbol("x", 0);
     224      var _y = new SimpleSymbol("y", 0);
     225
     226      grammar.AddSymbol(x);
     227      grammar.AddSymbol(z);
     228      grammar.AddSymbol(a);
     229      grammar.AddSymbol(b);
     230      grammar.AddSymbol(c);
     231      grammar.AddSymbol(d);
     232      grammar.AddSymbol(_x);
     233      grammar.AddSymbol(_y);
     234
     235      grammar.AddAllowedChildSymbol(grammar.StartSymbol, x);
     236      //uncommenting the line below changes the minimum expression length for the symbol <x>
     237      grammar.AddAllowedChildSymbol(x, z);
     238      grammar.AddAllowedChildSymbol(z, _x);
     239      grammar.AddAllowedChildSymbol(x, a);
     240      grammar.AddAllowedChildSymbol(a, b);
     241      grammar.AddAllowedChildSymbol(b, c);
     242      grammar.AddAllowedChildSymbol(c, d);
     243      grammar.AddAllowedChildSymbol(d, _y);
     244
     245      return grammar;
     246    }
     247
     248    private static ISymbolicExpressionGrammar CreateTestGrammar2() {
     249      var grammar = new SimpleSymbolicExpressionGrammar();
     250      var x = new SimpleSymbol("<x>", 2);
     251      var z = new SimpleSymbol("<z>", 6);
     252      var a = new SimpleSymbol("<a>", 1);
     253      var b = new SimpleSymbol("<b>", 1);
     254      var c = new SimpleSymbol("<c>", 1);
     255      var d = new SimpleSymbol("<d>", 1);
     256
     257      var _x = new SimpleSymbol("x", 0);
     258      var _y = new SimpleSymbol("y", 0);
     259
     260      grammar.AddSymbol(x);
     261      grammar.AddSymbol(z);
     262      grammar.AddSymbol(a);
     263      grammar.AddSymbol(b);
     264      grammar.AddSymbol(c);
     265      grammar.AddSymbol(d);
     266      grammar.AddSymbol(_x);
     267      grammar.AddSymbol(_y);
     268
     269      grammar.AddAllowedChildSymbol(grammar.StartSymbol, x);
     270      //uncommenting the line below changes the minimum expression length for the symbol <x>
     271      grammar.AddAllowedChildSymbol(x, z);
     272      grammar.AddAllowedChildSymbol(z, _x);
     273      grammar.AddAllowedChildSymbol(x, a);
     274      grammar.AddAllowedChildSymbol(a, b);
     275      grammar.AddAllowedChildSymbol(b, c);
     276      grammar.AddAllowedChildSymbol(c, d);
     277      grammar.AddAllowedChildSymbol(d, _y);
     278
     279      return grammar;
     280    }
     281
     282    private static ISymbolicExpressionGrammar CreateTestGrammar3() {
     283      var grammar = new SimpleSymbolicExpressionGrammar();
     284      var x = new SimpleSymbol("<x>", 1);
     285
     286      grammar.AddSymbol(x);
     287
     288      grammar.AddAllowedChildSymbol(grammar.StartSymbol, x);
     289      grammar.AddAllowedChildSymbol(x, x);
     290      return grammar;
     291    }
     292
     293
     294    private static ISymbolicExpressionGrammar CreateTestGrammar4() {
     295      var grammar = new SimpleSymbolicExpressionGrammar();
     296      var x = new SimpleSymbol("<x>", 1);
     297      var y = new SimpleSymbol("<y>", 1);
     298
     299      grammar.AddSymbol(x);
     300      grammar.AddSymbol(y);
     301
     302      grammar.AddAllowedChildSymbol(grammar.StartSymbol, x);
     303      grammar.AddAllowedChildSymbol(x, x);
     304      grammar.AddAllowedChildSymbol(x, y);
     305      grammar.AddAllowedChildSymbol(y, x);
     306      grammar.AddAllowedChildSymbol(y, y);
     307      return grammar;
     308    }
     309
     310    private static ISymbolicExpressionGrammar CreateTestGrammar5() {
     311      var grammar = new SimpleSymbolicExpressionGrammar();
     312      var x = new SimpleSymbol("<x>", 1);
     313      var y = new SimpleSymbol("<y>", 1);
     314      var _x = new SimpleSymbol("x", 0);
     315
     316      grammar.AddSymbol(x);
     317      grammar.AddSymbol(y);
     318      grammar.AddSymbol(_x);
     319
     320      grammar.AddAllowedChildSymbol(grammar.StartSymbol, x);
     321      grammar.AddAllowedChildSymbol(x, x);
     322      grammar.AddAllowedChildSymbol(x, y);
     323      grammar.AddAllowedChildSymbol(y, x);
     324      grammar.AddAllowedChildSymbol(y, y);
     325      grammar.AddAllowedChildSymbol(y, _x);
     326      return grammar;
     327    }
     328
     329    private static ISymbolicExpressionGrammar CreateTestGrammar6() {
    59330      var grammar = new SimpleSymbolicExpressionGrammar();
    60331      var x = new SimpleSymbol("<x>", 1);

  • stable/HeuristicLab.Tests/HeuristicLab.Tests.csproj

    r14210 r14958  
    559559    <Compile Include="HeuristicLab.Encodings.SymbolicExpressionTreeEncoding-3.4\SubroutineDuplicaterTest.cs" />
    560560    <Compile Include="HeuristicLab.Encodings.SymbolicExpressionTreeEncoding-3.4\SubtreeCrossoverTest.cs" />
     561    <Compile Include="HeuristicLab.Encodings.SymbolicExpressionTreeEncoding-3.4\GrammarsTest.cs" />
    561562    <Compile Include="HeuristicLab.Encodings.SymbolicExpressionTreeEncoding-3.4\Util.cs" />
    562563    <Compile Include="HeuristicLab.Persistence-3.3\StorableAttributeTests.cs" />
Note: See TracChangeset for help on using the changeset viewer.