Free cookie consent management tool by TermsFeed Policy Generator

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

Last change on this file since 5695 was 5695, checked in by mkommend, 12 years ago

#1418: Implemented persistence of grammars. Currently it does not work, because the Tuple type is not serializable (see #1442).

File size: 13.6 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    [Storable(Name = "Symbols")]
40    private IEnumerable<ISymbol> StorableSymbols {
41      get { return symbols.Values.ToArray(); }
42      set { symbols = value.ToDictionary(sym => sym.Name); }
43    }
44
45    [Storable(Name = "SymbolSubtreeCount")]
46    private IEnumerable<KeyValuePair<ISymbol, Tuple<int, int>>> StorableSymbolSubtreeCount {
47      get { return symbolSubtreeCount.Select(x => new KeyValuePair<ISymbol, Tuple<int, int>>(GetSymbol(x.Key), x.Value)).ToArray(); }
48      set { symbolSubtreeCount = value.ToDictionary(x => x.Key.Name, x => x.Value); }
49    }
50
51    [Storable(Name = "AllowedChildSymbols")]
52    private IEnumerable<KeyValuePair<ISymbol, IEnumerable<ISymbol>>> StorableAllowedChildSymbols {
53      get { return allowedChildSymbols.Select(x => new KeyValuePair<ISymbol, IEnumerable<ISymbol>>(GetSymbol(x.Key), x.Value.Select(y => GetSymbol(y)))).ToArray(); ; }
54      set { allowedChildSymbols = value.ToDictionary(x => x.Key.Name, x => x.Value.Select(y => y.Name).ToList()); }
55    }
56
57    [Storable(Name = "AllowedChildSymbolsPerIndex")]
58    private IEnumerable<KeyValuePair<Tuple<ISymbol, int>, IEnumerable<ISymbol>>> StorableAllowedChildSymbolsPerIndex {
59      get { return allowedChildSymbolsPerIndex.Select(x => new KeyValuePair<Tuple<ISymbol, int>, IEnumerable<ISymbol>>(Tuple.Create(GetSymbol(x.Key.Item1), x.Key.Item2), x.Value.Select(y => GetSymbol(y)))).ToArray(); }
60      set { allowedChildSymbolsPerIndex = value.ToDictionary(x => Tuple.Create(x.Key.Item1.Name, x.Key.Item2), x => x.Value.Select(y => y.Name).ToList()); }
61    }
62    #endregion
63
64    protected Dictionary<string, ISymbol> symbols;
65    protected Dictionary<string, Tuple<int, int>> symbolSubtreeCount;
66    protected Dictionary<string, List<string>> allowedChildSymbols;
67    protected Dictionary<Tuple<string, int>, List<string>> allowedChildSymbolsPerIndex;
68
69    public override bool CanChangeName {
70      get { return false; }
71    }
72    public override bool CanChangeDescription {
73      get { return false; }
74    }
75
76    [StorableConstructor]
77    protected SymbolicExpressionGrammarBase(bool deserializing)
78      : base(deserializing) {
79      cachedMinExpressionLength = new Dictionary<string, int>();
80      cachedMaxExpressionLength = new Dictionary<string, int>();
81      cachedMinExpressionDepth = new Dictionary<string, int>();
82    }
83    protected SymbolicExpressionGrammarBase(SymbolicExpressionGrammarBase original, Cloner cloner)
84      : base(original, cloner) {
85      cachedMinExpressionLength = new Dictionary<string, int>();
86      cachedMaxExpressionLength = new Dictionary<string, int>();
87      cachedMinExpressionDepth = new Dictionary<string, int>();
88
89      symbolSubtreeCount = new Dictionary<string, Tuple<int, int>>(original.symbolSubtreeCount);
90      symbols = new Dictionary<string, ISymbol>(original.symbols);
91
92      allowedChildSymbols = new Dictionary<string, List<string>>();
93      foreach (var element in original.allowedChildSymbols)
94        allowedChildSymbols.Add(element.Key, new List<string>(element.Value));
95
96      allowedChildSymbolsPerIndex = new Dictionary<Tuple<string, int>, List<string>>();
97      foreach (var element in original.allowedChildSymbolsPerIndex)
98        allowedChildSymbolsPerIndex.Add(element.Key, new List<string>(element.Value));
99    }
100
101    protected SymbolicExpressionGrammarBase(string name, string description)
102      : base(name, description) {
103      cachedMinExpressionLength = new Dictionary<string, int>();
104      cachedMaxExpressionLength = new Dictionary<string, int>();
105      cachedMinExpressionDepth = new Dictionary<string, int>();
106
107      symbols = new Dictionary<string, ISymbol>();
108      symbolSubtreeCount = new Dictionary<string, Tuple<int, int>>();
109      allowedChildSymbols = new Dictionary<string, List<string>>();
110      allowedChildSymbolsPerIndex = new Dictionary<Tuple<string, int>, List<string>>();
111    }
112
113    #region protected grammar manipulation methods
114    protected void AddSymbol(ISymbol symbol) {
115      if (ContainsSymbol(symbol)) throw new ArgumentException("Symbol " + symbol + " is already defined.");
116      symbols.Add(symbol.Name, symbol);
117      symbolSubtreeCount.Add(symbol.Name, Tuple.Create(0, 0));
118      ClearCaches();
119    }
120
121    protected void RemoveSymbol(ISymbol symbol) {
122      symbols.Remove(symbol.Name);
123      allowedChildSymbols.Remove(symbol.Name);
124      for (int i = 0; i < GetMaximumSubtreeCount(symbol); i++)
125        allowedChildSymbolsPerIndex.Remove(Tuple.Create(symbol.Name, i));
126      symbolSubtreeCount.Remove(symbol.Name);
127
128
129      foreach (var parent in Symbols) {
130        List<string> allowedChilds;
131        if (allowedChildSymbols.TryGetValue(parent.Name, out allowedChilds))
132          allowedChilds.Remove(symbol.Name);
133
134        for (int i = 0; i < GetMaximumSubtreeCount(parent); i++) {
135          if (allowedChildSymbolsPerIndex.TryGetValue(Tuple.Create(parent.Name, i), out allowedChilds))
136            allowedChilds.Remove(symbol.Name);
137        }
138      }
139      ClearCaches();
140    }
141
142    public virtual ISymbol GetSymbol(string symbolName) {
143      ISymbol symbol;
144      if (symbols.TryGetValue(symbolName, out symbol)) return symbol;
145      return null;
146    }
147
148    protected void AddAllowedChildSymbol(ISymbol parent, ISymbol child) {
149      List<string> childSymbols;
150      if (!allowedChildSymbols.TryGetValue(parent.Name, out childSymbols)) {
151        childSymbols = new List<string>();
152        allowedChildSymbols.Add(parent.Name, childSymbols);
153      }
154      childSymbols.Add(child.Name);
155      ClearCaches();
156    }
157
158    protected void AddAllowedChildSymbol(ISymbol parent, ISymbol child, int argumentIndex) {
159      var key = Tuple.Create(parent.Name, argumentIndex);
160      List<string> childSymbols;
161      if (!allowedChildSymbolsPerIndex.TryGetValue(key, out childSymbols)) {
162        childSymbols = new List<string>();
163        allowedChildSymbolsPerIndex.Add(key, childSymbols);
164      }
165
166      childSymbols.Add(child.Name);
167      ClearCaches();
168    }
169
170    protected void RemoveAllowedChildSymbol(ISymbol parent, ISymbol child) {
171      allowedChildSymbols[parent.Name].Remove(child.Name);
172      ClearCaches();
173    }
174
175    protected void RemoveAllowedChildSymbol(ISymbol parent, ISymbol child, int argumentIndex) {
176      var key = Tuple.Create(parent.Name, argumentIndex);
177      allowedChildSymbolsPerIndex[key].Remove(child.Name);
178      ClearCaches();
179    }
180
181    protected void SetSubtreeCount(ISymbol symbol, int minimumSubtreeCount, int maximumSubtreeCount) {
182      for (int i = GetMaximumSubtreeCount(symbol) - 1; i >= maximumSubtreeCount; i--) {
183        var key = Tuple.Create(symbol.Name, i);
184        allowedChildSymbolsPerIndex.Remove(key);
185      }
186
187      symbolSubtreeCount[symbol.Name] = Tuple.Create(minimumSubtreeCount, maximumSubtreeCount);
188      ClearCaches();
189    }
190    #endregion
191
192    #region ISymbolicExpressionGrammarBase Members
193    public virtual IEnumerable<ISymbol> Symbols {
194      get { return symbols.Values; }
195    }
196    public virtual IEnumerable<ISymbol> AllowedSymbols {
197      get { return Symbols.Where(s => !s.InitialFrequency.IsAlmost(0.0)); }
198    }
199    public virtual bool ContainsSymbol(ISymbol symbol) {
200      return symbols.ContainsKey(symbol.Name);
201    }
202
203    public virtual bool IsAllowedChildSymbol(ISymbol parent, ISymbol child) {
204      List<string> temp;
205      if (allowedChildSymbols.TryGetValue(parent.Name, out temp))
206        if (temp.Contains(child.Name)) return true;
207      return false;
208    }
209
210    public virtual bool IsAllowedChildSymbol(ISymbol parent, ISymbol child, int argumentIndex) {
211      List<string> temp;
212      if (allowedChildSymbols.TryGetValue(parent.Name, out temp))
213        if (temp.Contains(child.Name)) return true;
214
215      var key = Tuple.Create(parent.Name, argumentIndex);
216      if (allowedChildSymbolsPerIndex.TryGetValue(key, out temp))
217        return temp.Contains(child.Name);
218      return false;
219    }
220
221    public virtual IEnumerable<ISymbol> GetAllowedChildSymbols(ISymbol parent) {
222      return from s in Symbols where IsAllowedChildSymbol(parent, s) select s;
223    }
224
225    public virtual IEnumerable<ISymbol> GetAllowedChildSymbols(ISymbol parent, int argumentIndex) {
226      var result = Enumerable.Empty<string>();
227
228      List<string> temp;
229      if (allowedChildSymbols.TryGetValue(parent.Name, out temp))
230        result = result.Union(temp);
231      var key = Tuple.Create(parent.Name, argumentIndex);
232      if (allowedChildSymbolsPerIndex.TryGetValue(key, out temp))
233        result = result.Union(temp);
234
235      return result.Select(x => GetSymbol(x));
236    }
237
238    public virtual int GetMinimumSubtreeCount(ISymbol symbol) {
239      return symbolSubtreeCount[symbol.Name].Item1;
240    }
241    public virtual int GetMaximumSubtreeCount(ISymbol symbol) {
242      return symbolSubtreeCount[symbol.Name].Item2;
243    }
244
245
246    private void ClearCaches() {
247      cachedMinExpressionLength.Clear();
248      cachedMaxExpressionLength.Clear();
249      cachedMinExpressionDepth.Clear();
250    }
251
252    private Dictionary<string, int> cachedMinExpressionLength;
253    public int GetMinimumExpressionLength(ISymbol symbol) {
254      int temp;
255      if (!cachedMinExpressionLength.TryGetValue(symbol.Name, out temp)) {
256        cachedMinExpressionLength[symbol.Name] = int.MaxValue; // prevent infinite recursion
257        long sumOfMinExpressionLengths = 1 + (from argIndex in Enumerable.Range(0, GetMinimumSubtreeCount(symbol))
258                                              let minForSlot = (long)(from s in Symbols
259                                                                      where IsAllowedChildSymbol(symbol, s, argIndex)
260                                                                      select GetMinimumExpressionLength(s)).DefaultIfEmpty(0).Min()
261                                              select minForSlot).DefaultIfEmpty(0).Sum();
262
263        cachedMinExpressionLength[symbol.Name] = (int)Math.Min(sumOfMinExpressionLengths, int.MaxValue);
264        return cachedMinExpressionLength[symbol.Name];
265      }
266      return temp;
267    }
268
269    private Dictionary<string, int> cachedMaxExpressionLength;
270    public int GetMaximumExpressionLength(ISymbol symbol) {
271      int temp;
272      if (!cachedMaxExpressionLength.TryGetValue(symbol.Name, out temp)) {
273        cachedMaxExpressionLength[symbol.Name] = int.MaxValue; // prevent infinite recursion
274        long sumOfMaxTrees = 1 + (from argIndex in Enumerable.Range(0, GetMaximumSubtreeCount(symbol))
275                                  let maxForSlot = (long)(from s in Symbols
276                                                          where IsAllowedChildSymbol(symbol, s, argIndex)
277                                                          select GetMaximumExpressionLength(s)).DefaultIfEmpty(0).Max()
278                                  select maxForSlot).DefaultIfEmpty(0).Sum();
279        long limit = int.MaxValue;
280        cachedMaxExpressionLength[symbol.Name] = (int)Math.Min(sumOfMaxTrees, limit);
281        return cachedMaxExpressionLength[symbol.Name];
282      }
283      return temp;
284    }
285
286    private Dictionary<string, int> cachedMinExpressionDepth;
287    public int GetMinimumExpressionDepth(ISymbol symbol) {
288      int temp;
289      if (!cachedMinExpressionDepth.TryGetValue(symbol.Name, out temp)) {
290        cachedMinExpressionDepth[symbol.Name] = int.MaxValue; // prevent infinite recursion
291        cachedMinExpressionDepth[symbol.Name] = 1 + (from argIndex in Enumerable.Range(0, GetMinimumSubtreeCount(symbol))
292                                                     let minForSlot = (from s in Symbols
293                                                                       where IsAllowedChildSymbol(symbol, s, argIndex)
294                                                                       select GetMinimumExpressionDepth(s)).DefaultIfEmpty(0).Min()
295                                                     select minForSlot).DefaultIfEmpty(0).Max();
296        return cachedMinExpressionDepth[symbol.Name];
297      }
298      return temp;
299    }
300    #endregion
301  }
302}
Note: See TracBrowser for help on using the repository browser.