Free cookie consent management tool by TermsFeed Policy Generator

Ignore:
Timestamp:
10/24/16 10:17:43 (8 years ago)
Author:
bburlacu
Message:

#2685: Fix exception with symbols with no children (sequence contains no elements), factor out common code in separate methods.

File:
1 edited

Legend:

Unmodified
Added
Removed

  • trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/Grammars/GrammarUtils.cs

    r14355 r14356  
    3333        var minSubtreeCount = grammar.GetMinimumSubtreeCount(symbol);
    3434        for (int argIndex = 0; argIndex < minSubtreeCount; ++argIndex) {
    35           foreach (var childSymbol in grammar.GetAllowedChildSymbols(symbol, argIndex)) {
     35          foreach (var childSymbol in grammar.GetAllowedActiveSymbols(symbol, argIndex)) {
    3636            if (!parents.ContainsKey(childSymbol))
    3737              parents[childSymbol] = new List<ISymbol>();
    … …  
    4444    }
    4545
     46    private static IEnumerable<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 numberedSymbols = new List<Tuple<ISymbol, int>> { Tuple.Create(topSymbol, 0) };
     50      var visited = new HashSet<ISymbol> { topSymbol };
     51      int i = 0, index = 0;
     52      while (i < numberedSymbols.Count) {
     53        var symbol = numberedSymbols[i].Item1;
     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              numberedSymbols.Add(Tuple.Create(childSymbol, ++index));
     63          }
     64        }
     65        ++i;
     66      }
     67      numberedSymbols.Reverse();
     68      return numberedSymbols.Select(x => x.Item1);
     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
    4675    public static void CalculateMinimumExpressionLengths(ISymbolicExpressionGrammarBase grammar,
    4776      Dictionary<string, int> minimumExpressionLengths) {
    4877      minimumExpressionLengths.Clear();
    4978      //terminal symbols => minimum expression length = 1
    50       foreach (var symbol in grammar.Symbols.Where(x => grammar.GetMinimumSubtreeCount(x) == 0))
    51         minimumExpressionLengths.Add(symbol.Name, 1);
     79      foreach (var s in grammar.Symbols.Where(x => grammar.GetMinimumSubtreeCount(x) == 0))
     80        minimumExpressionLengths[s.Name] = 1;
    5281
    5382      foreach (var topSymbol in grammar.GetTopmostSymbols()) {
    54         // sort symbols in reverse breadth order (starting from the topSymbol)
    55         // each symbol is visited only once (this avoids infinite recursion)
    56         var numberedSymbols = new List<Tuple<ISymbol, int>> { Tuple.Create(topSymbol, 0) };
    57         var visited = new HashSet<ISymbol> { topSymbol };
    58         int i = 0, index = 0;
    59         while (i < numberedSymbols.Count) {
    60           var symbol = numberedSymbols[i].Item1;
    61           var minSubtreeCount = grammar.GetMinimumSubtreeCount(symbol);
    62 
    63           for (int argIndex = 0; argIndex < minSubtreeCount; ++argIndex) {
    64             foreach (var childSymbol in grammar.GetAllowedChildSymbols(symbol, argIndex)) {
    65               if (grammar.GetMinimumSubtreeCount(childSymbol) == 0)
    66                 continue;
    67 
    68               if (visited.Add(childSymbol))
    69                 numberedSymbols.Add(Tuple.Create(childSymbol, ++index));
    70             }
    71           }
    72           ++i;
    73         }
    74         numberedSymbols.Reverse(); // sort descending by index
    75 
    76         // going bottom-up (reverse breadth order), we ensure lengths are calculated bottom-up
    77         foreach (var symbol in numberedSymbols.Select(x => x.Item1)) {
     83        // get all symbols below in reverse breadth order
     84        // this way we ensure lengths are calculated bottom-up
     85        var symbols = grammar.IterateBreadthReverse(topSymbol).ToList();
     86        foreach (var symbol in symbols) {
    7887          long minLength = 1;
    7988          for (int argIndex = 0; argIndex < grammar.GetMinimumSubtreeCount(symbol); ++argIndex) {
    80             long length = grammar.GetAllowedChildSymbols(symbol, argIndex)
     89            long length = grammar.GetAllowedActiveSymbols(symbol, argIndex)
    8190              .Where(x => minimumExpressionLengths.ContainsKey(x.Name))
    8291              .Select(x => minimumExpressionLengths[x.Name]).DefaultIfEmpty(int.MaxValue).Min();
    … …  
    92101        while (changed) {
    93102          changed = false;
    94           foreach (var symbol in numberedSymbols.Select(x => x.Item1)) {
     103          foreach (var symbol in symbols) {
    95104            long minLength = Enumerable.Range(0, grammar.GetMinimumSubtreeCount(symbol))
    96               .Sum(x => grammar.GetAllowedChildSymbols(symbol, x)
    97               .Min(s => (long)minimumExpressionLengths[s.Name])) + 1;
     105              .Sum(x => grammar.GetAllowedActiveSymbols(symbol, x)
     106              .Select(s => (long)minimumExpressionLengths[s.Name]).DefaultIfEmpty(int.MaxValue).Min()) + 1;
    98107            if (minLength < minimumExpressionLengths[symbol.Name]) {
    99108              minimumExpressionLengths[symbol.Name] = (int)Math.Min(minLength, int.MaxValue);
    … …  
    120129
    121130      foreach (var topSymbol in grammar.GetTopmostSymbols()) {
    122         // sort symbols in reverse breadth order (starting from the topSymbol)
    123         // each symbol is visited only once (this avoids infinite recursion)
    124         var numberedSymbols = new List<Tuple<ISymbol, int>> { Tuple.Create(topSymbol, 0) };
    125         var visited = new HashSet<ISymbol> { topSymbol };
    126         int i = 0, index = 0;
    127         while (i < numberedSymbols.Count) {
    128           var symbol = numberedSymbols[i].Item1;
    129           var minSubtreeCount = grammar.GetMinimumSubtreeCount(symbol);
    130 
    131           for (int argIndex = 0; argIndex < minSubtreeCount; ++argIndex) {
    132             foreach (var childSymbol in grammar.GetAllowedChildSymbols(symbol, argIndex)) {
    133               if (grammar.GetMinimumSubtreeCount(childSymbol) == 0)
    134                 continue;
    135 
    136               if (visited.Add(childSymbol))
    137                 numberedSymbols.Add(Tuple.Create(childSymbol, ++index));
    138             }
    139           }
    140           ++i;
    141         }
    142         numberedSymbols.Reverse(); // sort descending by index
    143 
    144         // going bottom-up (reverse breadth order), we ensure depths are calculated bottom-up
    145         foreach (var symbol in numberedSymbols.Select(x => x.Item1)) {
     131        // get all symbols below in reverse breadth order
     132        // this way we ensure lengths are calculated bottom-up
     133        var symbols = grammar.IterateBreadthReverse(topSymbol).ToList();
     134        foreach (var symbol in symbols) {
    146135          long minDepth = -1;
    147136          for (int argIndex = 0; argIndex < grammar.GetMinimumSubtreeCount(symbol); ++argIndex) {
    148             long depth = grammar.GetAllowedChildSymbols(symbol, argIndex)
     137            long depth = grammar.GetAllowedActiveSymbols(symbol, argIndex)
    149138              .Where(x => minimumExpressionDepths.ContainsKey(x.Name))
    150139              .Select(x => (long)minimumExpressionDepths[x.Name]).DefaultIfEmpty(int.MaxValue).Min() + 1;
    … …  
    160149        while (changed) {
    161150          changed = false;
    162           foreach (var symbol in numberedSymbols.Select(x => x.Item1)) {
     151          foreach (var symbol in symbols) {
    163152            long minDepth = Enumerable.Range(0, grammar.GetMinimumSubtreeCount(symbol))
    164               .Max(x => grammar.GetAllowedChildSymbols(symbol, x)
    165               .Min(s => (long)minimumExpressionDepths[s.Name])) + 1;
     153              .Max(x => grammar.GetAllowedActiveSymbols(symbol, x)
     154              .Select(s => (long)minimumExpressionDepths[s.Name]).DefaultIfEmpty(int.MaxValue).Min()) + 1;
    166155            if (minDepth < minimumExpressionDepths[symbol.Name]) {
    167156              minimumExpressionDepths[symbol.Name] = (int)Math.Min(minDepth, int.MaxValue);
Note: See TracChangeset for help on using the changeset viewer.