Free cookie consent management tool by TermsFeed Policy Generator

source: branches/HeuristicLab.ReingoldTilfordTreeLayout/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/SymbolicExpressionGrammarBase.cs @ 12319

Last change on this file since 12319 was 9456, checked in by swagner, 12 years ago

Updated copyright year and added some missing license headers (#1889)

File size: 21.1 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2013 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
39    #region properties for separation between implementation and persistence
40    [Storable(Name = "Symbols")]
41    private IEnumerable<ISymbol> StorableSymbols {
42      get { return symbols.Values.ToArray(); }
43      set { symbols = value.ToDictionary(sym => sym.Name); }
44    }
45
46    [Storable(Name = "SymbolSubtreeCount")]
47    private IEnumerable<KeyValuePair<ISymbol, Tuple<int, int>>> StorableSymbolSubtreeCount {
48      get { return symbolSubtreeCount.Select(x => new KeyValuePair<ISymbol, Tuple<int, int>>(GetSymbol(x.Key), x.Value)).ToArray(); }
49      set { symbolSubtreeCount = value.ToDictionary(x => x.Key.Name, x => x.Value); }
50    }
51
52    [Storable(Name = "AllowedChildSymbols")]
53    private IEnumerable<KeyValuePair<ISymbol, IEnumerable<ISymbol>>> StorableAllowedChildSymbols {
54      get { return allowedChildSymbols.Select(x => new KeyValuePair<ISymbol, IEnumerable<ISymbol>>(GetSymbol(x.Key), x.Value.Select(GetSymbol).ToArray())).ToArray(); }
55      set { allowedChildSymbols = value.ToDictionary(x => x.Key.Name, x => x.Value.Select(y => y.Name).ToList()); }
56    }
57
58    [Storable(Name = "AllowedChildSymbolsPerIndex")]
59    private IEnumerable<KeyValuePair<Tuple<ISymbol, int>, IEnumerable<ISymbol>>> StorableAllowedChildSymbolsPerIndex {
60      get { return allowedChildSymbolsPerIndex.Select(x => new KeyValuePair<Tuple<ISymbol, int>, IEnumerable<ISymbol>>(Tuple.Create<ISymbol, int>(GetSymbol(x.Key.Item1), x.Key.Item2), x.Value.Select(y => GetSymbol(y)).ToArray())).ToArray(); }
61      set { allowedChildSymbolsPerIndex = value.ToDictionary(x => Tuple.Create(x.Key.Item1.Name, x.Key.Item2), x => x.Value.Select(y => y.Name).ToList()); }
62    }
63    #endregion
64
65    private bool suppressEvents;
66    protected Dictionary<string, ISymbol> symbols;
67    protected Dictionary<string, Tuple<int, int>> symbolSubtreeCount;
68    protected Dictionary<string, List<string>> allowedChildSymbols;
69    protected Dictionary<Tuple<string, int>, List<string>> allowedChildSymbolsPerIndex;
70
71    public override bool CanChangeName {
72      get { return false; }
73    }
74    public override bool CanChangeDescription {
75      get { return false; }
76    }
77
78    [StorableConstructor]
79    protected SymbolicExpressionGrammarBase(bool deserializing)
80      : base(deserializing) {
81      cachedMinExpressionLength = new Dictionary<string, int>();
82      cachedMaxExpressionLength = new Dictionary<Tuple<string, int>, int>();
83      cachedMinExpressionDepth = new Dictionary<string, int>();
84      cachedMaxExpressionDepth = new Dictionary<string, int>();
85
86      cachedIsAllowedChildSymbol = new Dictionary<Tuple<string, string>, bool>();
87      cachedIsAllowedChildSymbolIndex = new Dictionary<Tuple<string, string, int>, bool>();
88
89      suppressEvents = false;
90    }
91
92    protected SymbolicExpressionGrammarBase(SymbolicExpressionGrammarBase original, Cloner cloner)
93      : base(original, cloner) {
94      cachedMinExpressionLength = new Dictionary<string, int>();
95      cachedMaxExpressionLength = new Dictionary<Tuple<string, int>, int>();
96      cachedMinExpressionDepth = new Dictionary<string, int>();
97      cachedMaxExpressionDepth = new Dictionary<string, int>();
98
99      cachedIsAllowedChildSymbol = new Dictionary<Tuple<string, string>, bool>();
100      cachedIsAllowedChildSymbolIndex = new Dictionary<Tuple<string, string, int>, bool>();
101
102      symbols = original.symbols.ToDictionary(x => x.Key, y => cloner.Clone(y.Value));
103      symbolSubtreeCount = new Dictionary<string, Tuple<int, int>>(original.symbolSubtreeCount);
104
105      allowedChildSymbols = new Dictionary<string, List<string>>();
106      foreach (var element in original.allowedChildSymbols)
107        allowedChildSymbols.Add(element.Key, new List<string>(element.Value));
108
109      allowedChildSymbolsPerIndex = new Dictionary<Tuple<string, int>, List<string>>();
110      foreach (var element in original.allowedChildSymbolsPerIndex)
111        allowedChildSymbolsPerIndex.Add(element.Key, new List<string>(element.Value));
112
113      suppressEvents = false;
114    }
115
116    protected SymbolicExpressionGrammarBase(string name, string description)
117      : base(name, description) {
118      cachedMinExpressionLength = new Dictionary<string, int>();
119      cachedMaxExpressionLength = new Dictionary<Tuple<string, int>, int>();
120      cachedMinExpressionDepth = new Dictionary<string, int>();
121      cachedMaxExpressionDepth = new Dictionary<string, int>();
122
123      cachedIsAllowedChildSymbol = new Dictionary<Tuple<string, string>, bool>();
124      cachedIsAllowedChildSymbolIndex = new Dictionary<Tuple<string, string, int>, bool>();
125
126      symbols = new Dictionary<string, ISymbol>();
127      symbolSubtreeCount = new Dictionary<string, Tuple<int, int>>();
128      allowedChildSymbols = new Dictionary<string, List<string>>();
129      allowedChildSymbolsPerIndex = new Dictionary<Tuple<string, int>, List<string>>();
130
131      suppressEvents = false;
132    }
133
134    #region protected grammar manipulation methods
135    protected virtual void AddSymbol(ISymbol symbol) {
136      if (ContainsSymbol(symbol)) throw new ArgumentException("Symbol " + symbol + " is already defined.");
137      foreach (var s in symbol.Flatten()) {
138        symbols.Add(s.Name, s);
139        int maxSubTreeCount = Math.Min(s.MinimumArity + 1, s.MaximumArity);
140        symbolSubtreeCount.Add(s.Name, Tuple.Create(s.MinimumArity, maxSubTreeCount));
141      }
142      ClearCaches();
143    }
144
145    protected virtual void RemoveSymbol(ISymbol symbol) {
146      foreach (var s in symbol.Flatten()) {
147        symbols.Remove(s.Name);
148        allowedChildSymbols.Remove(s.Name);
149        for (int i = 0; i < GetMaximumSubtreeCount(s); i++)
150          allowedChildSymbolsPerIndex.Remove(Tuple.Create(s.Name, i));
151        symbolSubtreeCount.Remove(s.Name);
152
153        foreach (var parent in Symbols) {
154          List<string> allowedChilds;
155          if (allowedChildSymbols.TryGetValue(parent.Name, out allowedChilds))
156            allowedChilds.Remove(s.Name);
157
158          for (int i = 0; i < GetMaximumSubtreeCount(parent); i++) {
159            if (allowedChildSymbolsPerIndex.TryGetValue(Tuple.Create(parent.Name, i), out allowedChilds))
160              allowedChilds.Remove(s.Name);
161          }
162        }
163        suppressEvents = true;
164        foreach (var groupSymbol in Symbols.OfType<GroupSymbol>())
165          groupSymbol.SymbolsCollection.Remove(symbol);
166        suppressEvents = false;
167      }
168      ClearCaches();
169    }
170
171    public virtual ISymbol GetSymbol(string symbolName) {
172      ISymbol symbol;
173      if (symbols.TryGetValue(symbolName, out symbol)) return symbol;
174      return null;
175    }
176
177    protected void AddAllowedChildSymbol(ISymbol parent, ISymbol child) {
178      bool changed = false;
179
180      foreach (ISymbol p in parent.Flatten().Where(p => !(p is GroupSymbol)))
181        changed |= AddAllowedChildSymbolToDictionaries(p, child);
182
183      if (changed) {
184        ClearCaches();
185        OnChanged();
186      }
187    }
188
189    private bool AddAllowedChildSymbolToDictionaries(ISymbol parent, ISymbol child) {
190      List<string> childSymbols;
191      if (!allowedChildSymbols.TryGetValue(parent.Name, out childSymbols)) {
192        childSymbols = new List<string>();
193        allowedChildSymbols.Add(parent.Name, childSymbols);
194      }
195      if (childSymbols.Contains(child.Name)) return false;
196
197      suppressEvents = true;
198      for (int argumentIndex = 0; argumentIndex < GetMaximumSubtreeCount(parent); argumentIndex++)
199        RemoveAllowedChildSymbol(parent, child, argumentIndex);
200      suppressEvents = false;
201
202      childSymbols.Add(child.Name);
203      return true;
204    }
205
206    protected void AddAllowedChildSymbol(ISymbol parent, ISymbol child, int argumentIndex) {
207      bool changed = false;
208
209      foreach (ISymbol p in parent.Flatten().Where(p => !(p is GroupSymbol)))
210        changed |= AddAllowedChildSymbolToDictionaries(p, child, argumentIndex);
211
212      if (changed) {
213        ClearCaches();
214        OnChanged();
215      }
216    }
217
218
219    private bool AddAllowedChildSymbolToDictionaries(ISymbol parent, ISymbol child, int argumentIndex) {
220      List<string> childSymbols;
221      if (!allowedChildSymbols.TryGetValue(parent.Name, out childSymbols)) {
222        childSymbols = new List<string>();
223        allowedChildSymbols.Add(parent.Name, childSymbols);
224      }
225      if (childSymbols.Contains(child.Name)) return false;
226
227
228      var key = Tuple.Create(parent.Name, argumentIndex);
229      if (!allowedChildSymbolsPerIndex.TryGetValue(key, out childSymbols)) {
230        childSymbols = new List<string>();
231        allowedChildSymbolsPerIndex.Add(key, childSymbols);
232      }
233
234      if (childSymbols.Contains(child.Name)) return false;
235
236      childSymbols.Add(child.Name);
237      return true;
238    }
239
240    protected void RemoveAllowedChildSymbol(ISymbol parent, ISymbol child) {
241      bool changed = false;
242      List<string> childSymbols;
243      if (allowedChildSymbols.TryGetValue(child.Name, out childSymbols)) {
244        changed |= childSymbols.Remove(child.Name);
245      }
246
247      for (int argumentIndex = 0; argumentIndex < GetMaximumSubtreeCount(parent); argumentIndex++) {
248        var key = Tuple.Create(parent.Name, argumentIndex);
249        if (allowedChildSymbolsPerIndex.TryGetValue(key, out childSymbols))
250          changed |= childSymbols.Remove(child.Name);
251      }
252
253      if (changed) {
254        ClearCaches();
255        OnChanged();
256      }
257    }
258
259    protected void RemoveAllowedChildSymbol(ISymbol parent, ISymbol child, int argumentIndex) {
260      bool changed = false;
261
262      suppressEvents = true;
263      List<string> childSymbols;
264      if (allowedChildSymbols.TryGetValue(parent.Name, out childSymbols)) {
265        if (childSymbols.Remove(child.Name)) {
266          for (int i = 0; i < GetMaximumSubtreeCount(parent); i++) {
267            if (i != argumentIndex) AddAllowedChildSymbol(parent, child, i);
268          }
269          changed = true;
270        }
271      }
272      suppressEvents = false;
273
274      var key = Tuple.Create(parent.Name, argumentIndex);
275      if (allowedChildSymbolsPerIndex.TryGetValue(key, out childSymbols))
276        changed |= childSymbols.Remove(child.Name);
277
278      if (changed) {
279        ClearCaches();
280        OnChanged();
281      }
282    }
283
284    protected void SetSubtreeCount(ISymbol symbol, int minimumSubtreeCount, int maximumSubtreeCount) {
285      var symbols = symbol.Flatten().Where(s => !(s is GroupSymbol));
286      if (symbols.Any(s => s.MinimumArity > minimumSubtreeCount)) throw new ArgumentException("Invalid minimum subtree count " + minimumSubtreeCount + " for " + symbol);
287      if (symbols.Any(s => s.MaximumArity < maximumSubtreeCount)) throw new ArgumentException("Invalid maximum subtree count " + maximumSubtreeCount + " for " + symbol);
288
289      foreach (ISymbol s in symbols)
290        SetSubTreeCountInDictionaries(s, minimumSubtreeCount, maximumSubtreeCount);
291
292      ClearCaches();
293      OnChanged();
294    }
295
296    private void SetSubTreeCountInDictionaries(ISymbol symbol, int minimumSubtreeCount, int maximumSubtreeCount) {
297      for (int i = maximumSubtreeCount; i < GetMaximumSubtreeCount(symbol); i++) {
298        var key = Tuple.Create(symbol.Name, i);
299        allowedChildSymbolsPerIndex.Remove(key);
300      }
301
302      symbolSubtreeCount[symbol.Name] = Tuple.Create(minimumSubtreeCount, maximumSubtreeCount);
303    }
304    #endregion
305
306    public virtual IEnumerable<ISymbol> Symbols {
307      get { return symbols.Values; }
308    }
309    public virtual IEnumerable<ISymbol> AllowedSymbols {
310      get { foreach (var s in Symbols) if (s.Enabled) yield return s; }
311    }
312    public virtual bool ContainsSymbol(ISymbol symbol) {
313      return symbols.ContainsKey(symbol.Name);
314    }
315
316    private readonly Dictionary<Tuple<string, string>, bool> cachedIsAllowedChildSymbol;
317    public virtual bool IsAllowedChildSymbol(ISymbol parent, ISymbol child) {
318      if (allowedChildSymbols.Count == 0) return false;
319      if (!child.Enabled) return false;
320
321      bool result;
322      var key = Tuple.Create(parent.Name, child.Name);
323      if (cachedIsAllowedChildSymbol.TryGetValue(key, out result)) return result;
324
325      List<string> temp;
326      if (allowedChildSymbols.TryGetValue(parent.Name, out temp)) {
327        //if (temp.Contains(child.Name)) return true;
328        if (temp.SelectMany(s => GetSymbol(s).Flatten()).Any(s => s.Name == child.Name)) {
329          cachedIsAllowedChildSymbol.Add(key, true);
330          return true;
331        }
332      }
333      cachedIsAllowedChildSymbol.Add(key, false);
334      return false;
335    }
336
337    private readonly Dictionary<Tuple<string, string, int>, bool> cachedIsAllowedChildSymbolIndex;
338    public virtual bool IsAllowedChildSymbol(ISymbol parent, ISymbol child, int argumentIndex) {
339      if (!child.Enabled) return false;
340      if (IsAllowedChildSymbol(parent, child)) return true;
341      if (allowedChildSymbolsPerIndex.Count == 0) return false;
342
343      bool result;
344      var key = Tuple.Create(parent.Name, child.Name, argumentIndex);
345      if (cachedIsAllowedChildSymbolIndex.TryGetValue(key, out result)) return result;
346
347      List<string> temp;
348      if (allowedChildSymbolsPerIndex.TryGetValue(Tuple.Create(parent.Name, argumentIndex), out temp)) {
349        if (temp.SelectMany(s => GetSymbol(s).Flatten()).Any(s => s.Name == child.Name)) {
350          cachedIsAllowedChildSymbolIndex.Add(key, true);
351          return true;
352        }
353      }
354      cachedIsAllowedChildSymbolIndex.Add(key, false);
355      return false;
356    }
357
358    public IEnumerable<ISymbol> GetAllowedChildSymbols(ISymbol parent) {
359      foreach (ISymbol child in AllowedSymbols) {
360        if (IsAllowedChildSymbol(parent, child)) yield return child;
361      }
362    }
363
364    public IEnumerable<ISymbol> GetAllowedChildSymbols(ISymbol parent, int argumentIndex) {
365      foreach (ISymbol child in AllowedSymbols) {
366        if (IsAllowedChildSymbol(parent, child, argumentIndex)) yield return child;
367      }
368    }
369
370    public virtual int GetMinimumSubtreeCount(ISymbol symbol) {
371      return symbolSubtreeCount[symbol.Name].Item1;
372    }
373    public virtual int GetMaximumSubtreeCount(ISymbol symbol) {
374      return symbolSubtreeCount[symbol.Name].Item2;
375    }
376
377    protected void ClearCaches() {
378      cachedMinExpressionLength.Clear();
379      cachedMaxExpressionLength.Clear();
380      cachedMinExpressionDepth.Clear();
381      cachedMaxExpressionDepth.Clear();
382
383      cachedIsAllowedChildSymbol.Clear();
384      cachedIsAllowedChildSymbolIndex.Clear();
385    }
386
387    private readonly Dictionary<string, int> cachedMinExpressionLength;
388    public int GetMinimumExpressionLength(ISymbol symbol) {
389      int res;
390      if (cachedMinExpressionLength.TryGetValue(symbol.Name, out res))
391        return res;
392
393      res = GetMinimumExpressionLengthRec(symbol);
394      foreach (var entry in cachedMinExpressionLength.Where(e => e.Value >= int.MaxValue).ToList()) {
395        if (entry.Key != symbol.Name) cachedMinExpressionLength.Remove(entry.Key);
396      }
397      return res;
398    }
399
400    private int GetMinimumExpressionLengthRec(ISymbol symbol) {
401      int temp;
402      if (!cachedMinExpressionLength.TryGetValue(symbol.Name, out temp)) {
403        cachedMinExpressionLength[symbol.Name] = int.MaxValue; // prevent infinite recursion
404        long sumOfMinExpressionLengths = 1 + (from argIndex in Enumerable.Range(0, GetMinimumSubtreeCount(symbol))
405                                              let minForSlot = (long)(from s in GetAllowedChildSymbols(symbol, argIndex)
406                                                                      where s.InitialFrequency > 0.0
407                                                                      select GetMinimumExpressionLengthRec(s)).DefaultIfEmpty(0).Min()
408                                              select minForSlot).DefaultIfEmpty(0).Sum();
409
410        cachedMinExpressionLength[symbol.Name] = (int)Math.Min(sumOfMinExpressionLengths, int.MaxValue);
411        return cachedMinExpressionLength[symbol.Name];
412      }
413      return temp;
414    }
415
416    private readonly Dictionary<Tuple<string, int>, int> cachedMaxExpressionLength;
417    public int GetMaximumExpressionLength(ISymbol symbol, int maxDepth) {
418      int temp;
419      var key = Tuple.Create(symbol.Name, maxDepth);
420      if (!cachedMaxExpressionLength.TryGetValue(key, out temp)) {
421        cachedMaxExpressionLength[key] = int.MaxValue; // prevent infinite recursion
422        long sumOfMaxTrees = 1 + (from argIndex in Enumerable.Range(0, GetMaximumSubtreeCount(symbol))
423                                  let maxForSlot = (long)(from s in GetAllowedChildSymbols(symbol, argIndex)
424                                                          where s.InitialFrequency > 0.0
425                                                          where GetMinimumExpressionDepth(s) < maxDepth
426                                                          select GetMaximumExpressionLength(s, maxDepth - 1)).DefaultIfEmpty(0).Max()
427                                  select maxForSlot).DefaultIfEmpty(0).Sum();
428        cachedMaxExpressionLength[key] = (int)Math.Min(sumOfMaxTrees, int.MaxValue);
429        return cachedMaxExpressionLength[key];
430      }
431      return temp;
432    }
433
434    private readonly Dictionary<string, int> cachedMinExpressionDepth;
435    public int GetMinimumExpressionDepth(ISymbol symbol) {
436      int res;
437      if (cachedMinExpressionDepth.TryGetValue(symbol.Name, out res))
438        return res;
439
440      res = GetMinimumExpressionDepthRec(symbol);
441      foreach (var entry in cachedMinExpressionDepth.Where(e => e.Value >= int.MaxValue).ToList()) {
442        if (entry.Key != symbol.Name) cachedMinExpressionDepth.Remove(entry.Key);
443      }
444      return res;
445    }
446    private int GetMinimumExpressionDepthRec(ISymbol symbol) {
447      int temp;
448      if (!cachedMinExpressionDepth.TryGetValue(symbol.Name, out temp)) {
449        cachedMinExpressionDepth[symbol.Name] = int.MaxValue; // prevent infinite recursion
450        long minDepth = 1 + (from argIndex in Enumerable.Range(0, GetMinimumSubtreeCount(symbol))
451                             let minForSlot = (long)(from s in GetAllowedChildSymbols(symbol, argIndex)
452                                                     where s.InitialFrequency > 0.0
453                                                     select GetMinimumExpressionDepthRec(s)).DefaultIfEmpty(0).Min()
454                             select minForSlot).DefaultIfEmpty(0).Max();
455        cachedMinExpressionDepth[symbol.Name] = (int)Math.Min(minDepth, int.MaxValue);
456        return cachedMinExpressionDepth[symbol.Name];
457      }
458      return temp;
459    }
460
461    private readonly Dictionary<string, int> cachedMaxExpressionDepth;
462    public int GetMaximumExpressionDepth(ISymbol symbol) {
463      int temp;
464      if (!cachedMaxExpressionDepth.TryGetValue(symbol.Name, out temp)) {
465        cachedMaxExpressionDepth[symbol.Name] = int.MaxValue;
466        long maxDepth = 1 + (from argIndex in Enumerable.Range(0, GetMaximumSubtreeCount(symbol))
467                             let maxForSlot = (long)(from s in GetAllowedChildSymbols(symbol, argIndex)
468                                                     where s.InitialFrequency > 0.0
469                                                     select GetMaximumExpressionDepth(s)).DefaultIfEmpty(0).Max()
470                             select maxForSlot).DefaultIfEmpty(0).Max();
471        cachedMaxExpressionDepth[symbol.Name] = (int)Math.Min(maxDepth, int.MaxValue);
472        return cachedMaxExpressionDepth[symbol.Name];
473      }
474      return temp;
475    }
476
477    public event EventHandler Changed;
478    protected virtual void OnChanged() {
479      if (suppressEvents) return;
480      var handler = Changed;
481      if (handler != null) Changed(this, EventArgs.Empty);
482    }
483  }
484}
Note: See TracBrowser for help on using the repository browser.