Free cookie consent management tool by TermsFeed Policy Generator

source: stable/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/Grammars/GrammarUtils.cs @ 17106

Last change on this file since 17106 was 17097, checked in by mkommend, 5 years ago

#2520: Merged 16565 - 16579 into stable.

File size: 7.4 KB
Line 
1#region License Information
2
3/* HeuristicLab
4 * Copyright (C) 2002-2019 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 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 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;
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 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;
160            }
161          }
162        }
163      }
164    }
165  }
166}
Note: See TracBrowser for help on using the repository browser.