Free cookie consent management tool by TermsFeed Policy Generator

Ignore:
Timestamp:
10/23/16 19:50:36 (8 years ago)
Author:
bburlacu
Message:

#2685: Add correction step to account for grammar cycles. Update unit test/

File:
1 edited

Legend:

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

    r14354 r14355  
    6666                continue;
    6767
    68               if (visited.Add(childSymbol)) {
     68              if (visited.Add(childSymbol))
    6969                numberedSymbols.Add(Tuple.Create(childSymbol, ++index));
    70               }
    7170            }
    7271          }
     
    8887            minLength = Math.Min(minLength, oldLength);
    8988          minimumExpressionLengths[symbol.Name] = (int)Math.Min(int.MaxValue, minLength);
     89        }
     90        // correction step for cycles
     91        bool changed = true;
     92        while (changed) {
     93          changed = false;
     94          foreach (var symbol in numberedSymbols.Select(x => x.Item1)) {
     95            long minLength = Enumerable.Range(0, grammar.GetMinimumSubtreeCount(symbol))
     96              .Sum(x => grammar.GetAllowedChildSymbols(symbol, x)
     97              .Min(s => (long)minimumExpressionLengths[s.Name])) + 1;
     98            if (minLength < minimumExpressionLengths[symbol.Name]) {
     99              minimumExpressionLengths[symbol.Name] = (int)Math.Min(minLength, int.MaxValue);
     100              changed = true;
     101            }
     102          }
    90103        }
    91104      }
     
    121134                continue;
    122135
    123               if (visited.Add(childSymbol)) {
     136              if (visited.Add(childSymbol))
    124137                numberedSymbols.Add(Tuple.Create(childSymbol, ++index));
    125               }
    126138            }
    127139          }
     
    132144        // going bottom-up (reverse breadth order), we ensure depths are calculated bottom-up
    133145        foreach (var symbol in numberedSymbols.Select(x => x.Item1)) {
    134           long minDepth = int.MaxValue;
     146          long minDepth = -1;
    135147          for (int argIndex = 0; argIndex < grammar.GetMinimumSubtreeCount(symbol); ++argIndex) {
    136148            long depth = grammar.GetAllowedChildSymbols(symbol, argIndex)
    137149              .Where(x => minimumExpressionDepths.ContainsKey(x.Name))
    138               .Select(x => minimumExpressionDepths[x.Name]).DefaultIfEmpty(int.MaxValue).Min();
    139             minDepth = Math.Min(minDepth, depth + 1);
     150              .Select(x => (long)minimumExpressionDepths[x.Name]).DefaultIfEmpty(int.MaxValue).Min() + 1;
     151            minDepth = Math.Max(minDepth, depth);
    140152          }
    141153          int oldDepth;
     
    143155            minDepth = Math.Min(minDepth, oldDepth);
    144156          minimumExpressionDepths[symbol.Name] = (int)Math.Min(int.MaxValue, minDepth);
     157        }
     158        // correction step for cycles
     159        bool changed = true;
     160        while (changed) {
     161          changed = false;
     162          foreach (var symbol in numberedSymbols.Select(x => x.Item1)) {
     163            long minDepth = Enumerable.Range(0, grammar.GetMinimumSubtreeCount(symbol))
     164              .Max(x => grammar.GetAllowedChildSymbols(symbol, x)
     165              .Min(s => (long)minimumExpressionDepths[s.Name])) + 1;
     166            if (minDepth < minimumExpressionDepths[symbol.Name]) {
     167              minimumExpressionDepths[symbol.Name] = (int)Math.Min(minDepth, int.MaxValue);
     168              changed = true;
     169            }
     170          }
    145171        }
    146172      }
Note: See TracChangeset for help on using the changeset viewer.