Free cookie consent management tool by TermsFeed Policy Generator

source: branches/DataAnalysis Refactoring/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/SymbolicExpressionGrammarBase.cs @ 5691

Last change on this file since 5691 was 5688, checked in by mkommend, 13 years ago

#1418: Added names and descriptions to grammars and adapted their view.

File size: 12.1 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2011 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
4 *
5 * This file is part of HeuristicLab.
6 *
7 * HeuristicLab is free software: you can redistribute it and/or modify
8 * it under the terms of the GNU General Public License as published by
9 * the Free Software Foundation, either version 3 of the License, or
10 * (at your option) any later version.
11 *
12 * HeuristicLab is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15 * GNU General Public License for more details.
16 *
17 * You should have received a copy of the GNU General Public License
18 * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
19 */
20#endregion
21
22using System;
23using System.Collections.Generic;
24using System.Linq;
25using HeuristicLab.Common;
26using HeuristicLab.Core;
27using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
28
29namespace HeuristicLab.Encodings.SymbolicExpressionTreeEncoding {
30  /// <summary>
31  /// The default symbolic expression grammar stores symbols and syntactic constraints for symbols.
32  /// Symbols are treated as equvivalent if they have the same name.
33  /// Syntactic constraints limit the number of allowed sub trees for a node with a symbol and which symbols are allowed
34  /// in the sub-trees of a symbol (can be specified for each sub-tree index separately).
35  /// </summary>
36  [StorableClass]
37  public abstract class SymbolicExpressionGrammarBase : NamedItem, ISymbolicExpressionGrammarBase {
38    #region properties for separation between implementation and persistence
39
40    //TODO implement storable properties;
41
42    #endregion
43
44    protected Dictionary<string, ISymbol> symbols;
45    protected Dictionary<string, Tuple<int, int>> symbolSubTreeCount;
46    protected Dictionary<string, List<string>> allowedChildSymbols;
47    protected Dictionary<Tuple<string, int>, List<string>> allowedChildSymbolsPerIndex;
48
49    public override bool CanChangeName {
50      get { return false; }
51    }
52    public override bool CanChangeDescription {
53      get { return false; }
54    }
55
56    [StorableConstructor]
57    protected SymbolicExpressionGrammarBase(bool deserializing)
58      : base(deserializing) {
59      cachedMinExpressionLength = new Dictionary<string, int>();
60      cachedMaxExpressionLength = new Dictionary<string, int>();
61      cachedMinExpressionDepth = new Dictionary<string, int>();
62    }
63    protected SymbolicExpressionGrammarBase(SymbolicExpressionGrammarBase original, Cloner cloner)
64      : base(original, cloner) {
65      cachedMinExpressionLength = new Dictionary<string, int>();
66      cachedMaxExpressionLength = new Dictionary<string, int>();
67      cachedMinExpressionDepth = new Dictionary<string, int>();
68
69      symbolSubTreeCount = new Dictionary<string, Tuple<int, int>>(original.symbolSubTreeCount);
70      symbols = new Dictionary<string, ISymbol>(original.symbols);
71
72      allowedChildSymbols = new Dictionary<string, List<string>>();
73      foreach (var element in original.allowedChildSymbols)
74        allowedChildSymbols.Add(element.Key, new List<string>(element.Value));
75
76      allowedChildSymbolsPerIndex = new Dictionary<Tuple<string, int>, List<string>>();
77      foreach (var element in original.allowedChildSymbolsPerIndex)
78        allowedChildSymbolsPerIndex.Add(element.Key, new List<string>(element.Value));
79    }
80
81    protected SymbolicExpressionGrammarBase(string name, string description)
82      : base(name, description) {
83      cachedMinExpressionLength = new Dictionary<string, int>();
84      cachedMaxExpressionLength = new Dictionary<string, int>();
85      cachedMinExpressionDepth = new Dictionary<string, int>();
86
87      symbols = new Dictionary<string, ISymbol>();
88      symbolSubTreeCount = new Dictionary<string, Tuple<int, int>>();
89      allowedChildSymbols = new Dictionary<string, List<string>>();
90      allowedChildSymbolsPerIndex = new Dictionary<Tuple<string, int>, List<string>>();
91    }
92
93    #region protected grammar manipulation methods
94    protected void AddSymbol(ISymbol symbol) {
95      if (ContainsSymbol(symbol)) throw new ArgumentException("Symbol " + symbol + " is already defined.");
96      symbols.Add(symbol.Name, symbol);
97      symbolSubTreeCount.Add(symbol.Name, Tuple.Create(0, 0));
98      ClearCaches();
99    }
100
101    protected void RemoveSymbol(ISymbol symbol) {
102      symbols.Remove(symbol.Name);
103      allowedChildSymbols.Remove(symbol.Name);
104      for (int i = 0; i < GetMaximumSubtreeCount(symbol); i++)
105        allowedChildSymbolsPerIndex.Remove(Tuple.Create(symbol.Name, i));
106      symbolSubTreeCount.Remove(symbol.Name);
107
108
109      foreach (var parent in Symbols) {
110        List<string> allowedChilds;
111        if (allowedChildSymbols.TryGetValue(parent.Name, out allowedChilds))
112          allowedChilds.Remove(symbol.Name);
113
114        for (int i = 0; i < GetMaximumSubtreeCount(parent); i++) {
115          if (allowedChildSymbolsPerIndex.TryGetValue(Tuple.Create(parent.Name, i), out allowedChilds))
116            allowedChilds.Remove(symbol.Name);
117        }
118      }
119      ClearCaches();
120    }
121
122    public virtual ISymbol GetSymbol(string symbolName) {
123      ISymbol symbol;
124      if (symbols.TryGetValue(symbolName, out symbol)) return symbol;
125      return null;
126    }
127
128    protected void AddAllowedChildSymbol(ISymbol parent, ISymbol child) {
129      List<string> childSymbols;
130      if (!allowedChildSymbols.TryGetValue(parent.Name, out childSymbols)) {
131        childSymbols = new List<string>();
132        allowedChildSymbols.Add(parent.Name, childSymbols);
133      }
134      childSymbols.Add(child.Name);
135      ClearCaches();
136    }
137
138    protected void AddAllowedChildSymbol(ISymbol parent, ISymbol child, int argumentIndex) {
139      var key = Tuple.Create(parent.Name, argumentIndex);
140      List<string> childSymbols;
141      if (!allowedChildSymbolsPerIndex.TryGetValue(key, out childSymbols)) {
142        childSymbols = new List<string>();
143        allowedChildSymbolsPerIndex.Add(key, childSymbols);
144      }
145
146      childSymbols.Add(child.Name);
147      ClearCaches();
148    }
149
150    protected void RemoveAllowedChildSymbol(ISymbol parent, ISymbol child) {
151      allowedChildSymbols[parent.Name].Remove(child.Name);
152      ClearCaches();
153    }
154
155    protected void RemoveAllowedChildSymbol(ISymbol parent, ISymbol child, int argumentIndex) {
156      var key = Tuple.Create(parent.Name, argumentIndex);
157      allowedChildSymbolsPerIndex[key].Remove(child.Name);
158      ClearCaches();
159    }
160
161    protected void SetSubtreeCount(ISymbol symbol, int minimumSubtreeCount, int maximumSubtreeCount) {
162      for (int i = GetMaximumSubtreeCount(symbol) - 1; i >= maximumSubtreeCount; i--) {
163        var key = Tuple.Create(symbol.Name, i);
164        allowedChildSymbolsPerIndex.Remove(key);
165      }
166
167      symbolSubTreeCount[symbol.Name] = Tuple.Create(minimumSubtreeCount, maximumSubtreeCount);
168      ClearCaches();
169    }
170    #endregion
171
172    #region ISymbolicExpressionGrammarBase Members
173    public virtual IEnumerable<ISymbol> Symbols {
174      get { return symbols.Values; }
175    }
176    public virtual IEnumerable<ISymbol> AllowedSymbols {
177      get { return Symbols.Where(s => !s.InitialFrequency.IsAlmost(0.0)); }
178    }
179    public virtual bool ContainsSymbol(ISymbol symbol) {
180      return symbols.ContainsKey(symbol.Name);
181    }
182
183    public virtual bool IsAllowedChildSymbol(ISymbol parent, ISymbol child) {
184      List<string> temp;
185      if (allowedChildSymbols.TryGetValue(parent.Name, out temp))
186        if (temp.Contains(child.Name)) return true;
187      return false;
188    }
189
190    public virtual bool IsAllowedChildSymbol(ISymbol parent, ISymbol child, int argumentIndex) {
191      List<string> temp;
192      if (allowedChildSymbols.TryGetValue(parent.Name, out temp))
193        if (temp.Contains(child.Name)) return true;
194
195      var key = Tuple.Create(parent.Name, argumentIndex);
196      if (allowedChildSymbolsPerIndex.TryGetValue(key, out temp))
197        return temp.Contains(child.Name);
198      return false;
199    }
200
201    public virtual IEnumerable<ISymbol> GetAllowedChildSymbols(ISymbol parent) {
202      return from s in Symbols where IsAllowedChildSymbol(parent, s) select s;
203    }
204
205    public virtual IEnumerable<ISymbol> GetAllowedChildSymbols(ISymbol parent, int argumentIndex) {
206      var result = Enumerable.Empty<string>();
207
208      List<string> temp;
209      if (allowedChildSymbols.TryGetValue(parent.Name, out temp))
210        result = result.Union(temp);
211      var key = Tuple.Create(parent.Name, argumentIndex);
212      if (allowedChildSymbolsPerIndex.TryGetValue(key, out temp))
213        result = result.Union(temp);
214
215      return result.Select(x => GetSymbol(x));
216    }
217
218    public virtual int GetMinimumSubtreeCount(ISymbol symbol) {
219      return symbolSubTreeCount[symbol.Name].Item1;
220    }
221    public virtual int GetMaximumSubtreeCount(ISymbol symbol) {
222      return symbolSubTreeCount[symbol.Name].Item2;
223    }
224
225
226    private void ClearCaches() {
227      cachedMinExpressionLength.Clear();
228      cachedMaxExpressionLength.Clear();
229      cachedMinExpressionDepth.Clear();
230    }
231
232    private Dictionary<string, int> cachedMinExpressionLength;
233    public int GetMinimumExpressionLength(ISymbol symbol) {
234      int temp;
235      if (!cachedMinExpressionLength.TryGetValue(symbol.Name, out temp)) {
236        cachedMinExpressionLength[symbol.Name] = int.MaxValue; // prevent infinite recursion
237        long sumOfMinExpressionLengths = 1 + (from argIndex in Enumerable.Range(0, GetMinimumSubtreeCount(symbol))
238                                              let minForSlot = (long)(from s in Symbols
239                                                                      where IsAllowedChildSymbol(symbol, s, argIndex)
240                                                                      select GetMinimumExpressionLength(s)).DefaultIfEmpty(0).Min()
241                                              select minForSlot).DefaultIfEmpty(0).Sum();
242
243        cachedMinExpressionLength[symbol.Name] = (int)Math.Min(sumOfMinExpressionLengths, int.MaxValue);
244        return cachedMinExpressionLength[symbol.Name];
245      }
246      return temp;
247    }
248
249    private Dictionary<string, int> cachedMaxExpressionLength;
250    public int GetMaximumExpressionLength(ISymbol symbol) {
251      int temp;
252      if (!cachedMaxExpressionLength.TryGetValue(symbol.Name, out temp)) {
253        cachedMaxExpressionLength[symbol.Name] = int.MaxValue; // prevent infinite recursion
254        long sumOfMaxTrees = 1 + (from argIndex in Enumerable.Range(0, GetMaximumSubtreeCount(symbol))
255                                  let maxForSlot = (long)(from s in Symbols
256                                                          where IsAllowedChildSymbol(symbol, s, argIndex)
257                                                          select GetMaximumExpressionLength(s)).DefaultIfEmpty(0).Max()
258                                  select maxForSlot).DefaultIfEmpty(0).Sum();
259        long limit = int.MaxValue;
260        cachedMaxExpressionLength[symbol.Name] = (int)Math.Min(sumOfMaxTrees, limit);
261        return cachedMaxExpressionLength[symbol.Name];
262      }
263      return temp;
264    }
265
266    private Dictionary<string, int> cachedMinExpressionDepth;
267    public int GetMinimumExpressionDepth(ISymbol symbol) {
268      int temp;
269      if (!cachedMinExpressionDepth.TryGetValue(symbol.Name, out temp)) {
270        cachedMinExpressionDepth[symbol.Name] = int.MaxValue; // prevent infinite recursion
271        cachedMinExpressionDepth[symbol.Name] = 1 + (from argIndex in Enumerable.Range(0, GetMinimumSubtreeCount(symbol))
272                                                     let minForSlot = (from s in Symbols
273                                                                       where IsAllowedChildSymbol(symbol, s, argIndex)
274                                                                       select GetMinimumExpressionDepth(s)).DefaultIfEmpty(0).Min()
275                                                     select minForSlot).DefaultIfEmpty(0).Max();
276        return cachedMinExpressionDepth[symbol.Name];
277      }
278      return temp;
279    }
280    #endregion
281  }
282}
Note: See TracBrowser for help on using the repository browser.