Free cookie consent management tool by TermsFeed Policy Generator

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

Last change on this file since 14354 was 14354, checked in by bburlacu, 7 years ago

#2685: Revert accidental commit.

File size: 7.2 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.GetAllowedChildSymbols(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    public static void CalculateMinimumExpressionLengths(ISymbolicExpressionGrammarBase grammar,
47      Dictionary<string, int> minimumExpressionLengths) {
48      minimumExpressionLengths.Clear();
49      //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);
52
53      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          }
73          ++i;
74        }
75        numberedSymbols.Reverse(); // sort descending by index
76
77        // going bottom-up (reverse breadth order), we ensure lengths are calculated bottom-up
78        foreach (var symbol in numberedSymbols.Select(x => x.Item1)) {
79          long minLength = 1;
80          for (int argIndex = 0; argIndex < grammar.GetMinimumSubtreeCount(symbol); ++argIndex) {
81            long length = grammar.GetAllowedChildSymbols(symbol, argIndex)
82              .Where(x => minimumExpressionLengths.ContainsKey(x.Name))
83              .Select(x => minimumExpressionLengths[x.Name]).DefaultIfEmpty(int.MaxValue).Min();
84            minLength += length;
85          }
86          int oldLength;
87          if (minimumExpressionLengths.TryGetValue(symbol.Name, out oldLength))
88            minLength = Math.Min(minLength, oldLength);
89          minimumExpressionLengths[symbol.Name] = (int)Math.Min(int.MaxValue, minLength);
90        }
91      }
92
93      //set minLength to int.MaxValue for all symbols that are not reacheable
94      foreach (var remainingSymbols in grammar.Symbols) {
95        if (!minimumExpressionLengths.ContainsKey(remainingSymbols.Name))
96          minimumExpressionLengths[remainingSymbols.Name] = int.MaxValue;
97      }
98    }
99
100    public static void CalculateMinimumExpressionDepth(ISymbolicExpressionGrammarBase grammar,
101      Dictionary<string, int> minimumExpressionDepths) {
102
103      minimumExpressionDepths.Clear();
104      //terminal symbols => minimum expression depth = 1
105      foreach (var s in grammar.Symbols.Where(s => grammar.GetMinimumSubtreeCount(s) == 0))
106        minimumExpressionDepths[s.Name] = 1;
107
108      foreach (var topSymbol in grammar.GetTopmostSymbols()) {
109        // sort symbols in reverse breadth order (starting from the topSymbol)
110        // each symbol is visited only once (this avoids infinite recursion)
111        var numberedSymbols = new List<Tuple<ISymbol, int>> { Tuple.Create(topSymbol, 0) };
112        var visited = new HashSet<ISymbol> { topSymbol };
113        int i = 0, index = 0;
114        while (i < numberedSymbols.Count) {
115          var symbol = numberedSymbols[i].Item1;
116          var minSubtreeCount = grammar.GetMinimumSubtreeCount(symbol);
117
118          for (int argIndex = 0; argIndex < minSubtreeCount; ++argIndex) {
119            foreach (var childSymbol in grammar.GetAllowedChildSymbols(symbol, argIndex)) {
120              if (grammar.GetMinimumSubtreeCount(childSymbol) == 0)
121                continue;
122
123              if (visited.Add(childSymbol)) {
124                numberedSymbols.Add(Tuple.Create(childSymbol, ++index));
125              }
126            }
127          }
128          ++i;
129        }
130        numberedSymbols.Reverse(); // sort descending by index
131
132        // going bottom-up (reverse breadth order), we ensure depths are calculated bottom-up
133        foreach (var symbol in numberedSymbols.Select(x => x.Item1)) {
134          long minDepth = int.MaxValue;
135          for (int argIndex = 0; argIndex < grammar.GetMinimumSubtreeCount(symbol); ++argIndex) {
136            long depth = grammar.GetAllowedChildSymbols(symbol, argIndex)
137              .Where(x => minimumExpressionDepths.ContainsKey(x.Name))
138              .Select(x => minimumExpressionDepths[x.Name]).DefaultIfEmpty(int.MaxValue).Min();
139            minDepth = Math.Min(minDepth, depth + 1);
140          }
141          int oldDepth;
142          if (minimumExpressionDepths.TryGetValue(symbol.Name, out oldDepth))
143            minDepth = Math.Min(minDepth, oldDepth);
144          minimumExpressionDepths[symbol.Name] = (int)Math.Min(int.MaxValue, minDepth);
145        }
146      }
147
148      //set minDepth to int.Maxvalue for all symbols that are not reacheable
149      foreach (var remainingSymbols in grammar.Symbols) {
150        if (!minimumExpressionDepths.ContainsKey(remainingSymbols.Name))
151          minimumExpressionDepths[remainingSymbols.Name] = int.MaxValue;
152      }
153    }
154  }
155}
Note: See TracBrowser for help on using the repository browser.