source: trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/Grammars/GrammarUtils.cs @ 14356

Last change on this file since 14356 was 14356, checked in by bburlacu, 3 years ago

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

File size: 7.9 KB
Line 
1#region License Information
2
3/* HeuristicLab
4 * Copyright (C) 2002-2016 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
24using System;
25using System.Collections.Generic;
26using System.Linq;
27namespace 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 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
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.Where(x => grammar.GetMinimumSubtreeCount(x) == 0))
80        minimumExpressionLengths[s.Name] = 1;
81
82      foreach (var topSymbol in grammar.GetTopmostSymbols()) {
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) {
87          long minLength = 1;
88          for (int argIndex = 0; argIndex < grammar.GetMinimumSubtreeCount(symbol); ++argIndex) {
89            long length = grammar.GetAllowedActiveSymbols(symbol, argIndex)
90              .Where(x => minimumExpressionLengths.ContainsKey(x.Name))
91              .Select(x => minimumExpressionLengths[x.Name]).DefaultIfEmpty(int.MaxValue).Min();
92            minLength += length;
93          }
94          int oldLength;
95          if (minimumExpressionLengths.TryGetValue(symbol.Name, out oldLength))
96            minLength = Math.Min(minLength, oldLength);
97          minimumExpressionLengths[symbol.Name] = (int)Math.Min(int.MaxValue, minLength);
98        }
99        // correction step for cycles
100        bool changed = true;
101        while (changed) {
102          changed = false;
103          foreach (var symbol in symbols) {
104            long minLength = Enumerable.Range(0, grammar.GetMinimumSubtreeCount(symbol))
105              .Sum(x => grammar.GetAllowedActiveSymbols(symbol, x)
106              .Select(s => (long)minimumExpressionLengths[s.Name]).DefaultIfEmpty(int.MaxValue).Min()) + 1;
107            if (minLength < minimumExpressionLengths[symbol.Name]) {
108              minimumExpressionLengths[symbol.Name] = (int)Math.Min(minLength, int.MaxValue);
109              changed = true;
110            }
111          }
112        }
113      }
114
115      //set minLength to int.MaxValue for all symbols that are not reacheable
116      foreach (var remainingSymbols in grammar.Symbols) {
117        if (!minimumExpressionLengths.ContainsKey(remainingSymbols.Name))
118          minimumExpressionLengths[remainingSymbols.Name] = int.MaxValue;
119      }
120    }
121
122    public static void CalculateMinimumExpressionDepth(ISymbolicExpressionGrammarBase grammar,
123      Dictionary<string, int> minimumExpressionDepths) {
124
125      minimumExpressionDepths.Clear();
126      //terminal symbols => minimum expression depth = 1
127      foreach (var s in grammar.Symbols.Where(s => grammar.GetMinimumSubtreeCount(s) == 0))
128        minimumExpressionDepths[s.Name] = 1;
129
130      foreach (var topSymbol in grammar.GetTopmostSymbols()) {
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) {
135          long minDepth = -1;
136          for (int argIndex = 0; argIndex < grammar.GetMinimumSubtreeCount(symbol); ++argIndex) {
137            long depth = grammar.GetAllowedActiveSymbols(symbol, argIndex)
138              .Where(x => minimumExpressionDepths.ContainsKey(x.Name))
139              .Select(x => (long)minimumExpressionDepths[x.Name]).DefaultIfEmpty(int.MaxValue).Min() + 1;
140            minDepth = Math.Max(minDepth, depth);
141          }
142          int oldDepth;
143          if (minimumExpressionDepths.TryGetValue(symbol.Name, out oldDepth))
144            minDepth = Math.Min(minDepth, oldDepth);
145          minimumExpressionDepths[symbol.Name] = (int)Math.Min(int.MaxValue, minDepth);
146        }
147        // correction step for cycles
148        bool changed = true;
149        while (changed) {
150          changed = false;
151          foreach (var symbol in symbols) {
152            long minDepth = Enumerable.Range(0, grammar.GetMinimumSubtreeCount(symbol))
153              .Max(x => grammar.GetAllowedActiveSymbols(symbol, x)
154              .Select(s => (long)minimumExpressionDepths[s.Name]).DefaultIfEmpty(int.MaxValue).Min()) + 1;
155            if (minDepth < minimumExpressionDepths[symbol.Name]) {
156              minimumExpressionDepths[symbol.Name] = (int)Math.Min(minDepth, int.MaxValue);
157              changed = true;
158            }
159          }
160        }
161      }
162
163      //set minDepth to int.Maxvalue for all symbols that are not reacheable
164      foreach (var remainingSymbols in grammar.Symbols) {
165        if (!minimumExpressionDepths.ContainsKey(remainingSymbols.Name))
166          minimumExpressionDepths[remainingSymbols.Name] = int.MaxValue;
167      }
168    }
169  }
170}
Note: See TracBrowser for help on using the repository browser.