Free cookie consent management tool by TermsFeed Policy Generator

source: branches/DataAnalysis Refactoring/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/DefaultSymbolicExpressionGrammar.cs @ 5551

Last change on this file since 5551 was 5529, checked in by gkronber, 14 years ago

#1418 Removed grammar specific members from ISymbolicExpressionTreeNode interface.

File size: 15.2 KB
RevLine 
[3294]1#region License Information
2/* HeuristicLab
[5445]3 * Copyright (C) 2002-2011 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
[3294]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;
[3376]25using HeuristicLab.Common;
[3294]26using HeuristicLab.Core;
27using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
28
29namespace HeuristicLab.Encodings.SymbolicExpressionTreeEncoding {
[3369]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>
[3294]36  [StorableClass]
37  [Item("DefaultSymbolicExpressionGrammar", "Represents a grammar that defines the syntax of symbolic expression trees.")]
[5499]38  public abstract class DefaultSymbolicExpressionGrammar : Item, ISymbolicExpressionTreeGrammar {
[3541]39
40    #region properties for separation between implementation and persistence
[3294]41    [Storable]
[3541]42    private IEnumerable<KeyValuePair<string, int>> MinSubTreeCount {
43      get { return minSubTreeCount.AsEnumerable(); }
44      set { minSubTreeCount = value.ToDictionary(x => x.Key, x => x.Value); }
45    }
46
47    [Storable]
48    private IEnumerable<KeyValuePair<string, int>> MaxSubTreeCount {
49      get { return maxSubTreeCount.AsEnumerable(); }
50      set { maxSubTreeCount = value.ToDictionary(x => x.Key, x => x.Value); }
51    }
52
53    [Storable]
54    private IEnumerable<KeyValuePair<string, IEnumerable<IEnumerable<string>>>> AllowedChildSymbols {
55      get {
56        return (from parentEntry in allowedChildSymbols
57                let setEnumeration = parentEntry.Value.Select(set => set.AsEnumerable()).ToList()
58                select new KeyValuePair<string, IEnumerable<IEnumerable<string>>>(parentEntry.Key, setEnumeration))
59                .ToList();
60      }
61      set {
[3993]62        allowedChildSymbols = new Dictionary<string, List<List<string>>>();
[3541]63        foreach (var pair in value) {
[3993]64          allowedChildSymbols[pair.Key] = new List<List<string>>();
[3541]65          foreach (var entry in pair.Value) {
[3993]66            var hashSet = new List<string>();
[3541]67            foreach (string child in entry) {
68              hashSet.Add(child);
69            }
70            allowedChildSymbols[pair.Key].Add(hashSet);
71          }
72        }
73      }
74    }
75    [Storable]
[5510]76    private IEnumerable<KeyValuePair<string, ISymbol>> AllSymbols {
[3541]77      get { return allSymbols.AsEnumerable(); }
78      set { allSymbols = value.ToDictionary(x => x.Key, x => x.Value); }
79    }
80    #endregion
81
[3294]82    private Dictionary<string, int> minSubTreeCount;
83    private Dictionary<string, int> maxSubTreeCount;
[3993]84    private Dictionary<string, List<List<string>>> allowedChildSymbols;
[5510]85    private Dictionary<string, ISymbol> allSymbols;
[3294]86    [Storable]
[5510]87    private ISymbol startSymbol;
[3294]88
[4722]89    [StorableConstructor]
90    protected DefaultSymbolicExpressionGrammar(bool deserializing)
91      : base(deserializing) {
92      cachedMinExpressionLength = new Dictionary<string, int>();
93      cachedMaxExpressionLength = new Dictionary<string, int>();
94      cachedMinExpressionDepth = new Dictionary<string, int>();
95    }
96    // cloning ctor
97    protected DefaultSymbolicExpressionGrammar(DefaultSymbolicExpressionGrammar original, Cloner cloner)
98      : base(original, cloner) {
99      this.cachedMinExpressionLength = new Dictionary<string, int>();
100      this.cachedMaxExpressionLength = new Dictionary<string, int>();
101      this.cachedMinExpressionDepth = new Dictionary<string, int>();
102      minSubTreeCount = new Dictionary<string, int>(original.minSubTreeCount);
103      maxSubTreeCount = new Dictionary<string, int>(original.maxSubTreeCount);
104
[5510]105      allSymbols = new Dictionary<string, ISymbol>();
106      foreach (ISymbol symbol in original.allSymbols.Values.Select(s => cloner.Clone(s)))
[4722]107        allSymbols.Add(symbol.Name, symbol);
108
[5510]109      startSymbol = cloner.Clone<ISymbol>(original.startSymbol);
[4722]110      allowedChildSymbols = new Dictionary<string, List<List<string>>>();
111      foreach (var entry in original.allowedChildSymbols) {
112        allowedChildSymbols[entry.Key] = new List<List<string>>(entry.Value.Count);
113        foreach (var set in entry.Value) {
114          allowedChildSymbols[entry.Key].Add(new List<string>(set));
115        }
116      }
117    }
[4262]118    protected DefaultSymbolicExpressionGrammar()
[3294]119      : base() {
[4249]120      this.minSubTreeCount = new Dictionary<string, int>();
121      this.maxSubTreeCount = new Dictionary<string, int>();
122      this.allowedChildSymbols = new Dictionary<string, List<List<string>>>();
[5510]123      this.allSymbols = new Dictionary<string, ISymbol>();
[4249]124      this.cachedMinExpressionLength = new Dictionary<string, int>();
125      this.cachedMaxExpressionLength = new Dictionary<string, int>();
126      this.cachedMinExpressionDepth = new Dictionary<string, int>();
[3993]127
[4249]128      this.startSymbol = new StartSymbol();
129      this.AddSymbol(startSymbol);
130      this.SetMinSubtreeCount(startSymbol, 1);
131      this.SetMaxSubtreeCount(startSymbol, 1);
[3338]132    }
[3294]133
[5499]134    protected DefaultSymbolicExpressionGrammar(ISymbolicExpressionTreeGrammar grammar)
[4068]135      : base() {
[4249]136      Cloner cloner = new Cloner();
137      this.cachedMinExpressionLength = new Dictionary<string, int>();
138      this.cachedMaxExpressionLength = new Dictionary<string, int>();
139      this.cachedMinExpressionDepth = new Dictionary<string, int>();
[4068]140
[4249]141      this.minSubTreeCount = new Dictionary<string, int>();
142      this.maxSubTreeCount = new Dictionary<string, int>();
[3993]143      this.allowedChildSymbols = new Dictionary<string, List<List<string>>>();
[5510]144      this.allSymbols = new Dictionary<string, ISymbol>();
[4249]145
[5510]146      this.StartSymbol = (ISymbol)cloner.Clone(grammar.StartSymbol);
[4249]147
[5510]148      foreach (ISymbol symbol in grammar.Symbols) {
149        ISymbol clonedSymbol = (ISymbol)cloner.Clone(symbol);
[4249]150        this.AddSymbol(clonedSymbol);
151        this.SetMinSubtreeCount(clonedSymbol, grammar.GetMinSubtreeCount(symbol));
152        this.SetMaxSubtreeCount(clonedSymbol, grammar.GetMaxSubtreeCount(symbol));
153      }
154
[5510]155      foreach (ISymbol parent in grammar.Symbols) {
[4249]156        for (int i = 0; i < grammar.GetMaxSubtreeCount(parent); i++) {
[5510]157          foreach (ISymbol child in grammar.Symbols) {
[4249]158            if (grammar.IsAllowedChild(parent, child, i)) {
[5510]159              this.SetAllowedChild((ISymbol)cloner.Clone(parent), (ISymbol)cloner.Clone(child), i);
[4249]160            }
161          }
[3993]162        }
163      }
164    }
165
166    public void Clear() {
167      minSubTreeCount.Clear();
168      maxSubTreeCount.Clear();
169      allowedChildSymbols.Clear();
170      allSymbols.Clear();
171
172      cachedMaxExpressionLength.Clear();
173      cachedMinExpressionLength.Clear();
174      cachedMinExpressionDepth.Clear();
175
176      startSymbol = new StartSymbol();
177      AddSymbol(startSymbol);
178      SetMinSubtreeCount(startSymbol, 1);
179      SetMaxSubtreeCount(startSymbol, 1);
180    }
181
[3338]182    #region ISymbolicExpressionGrammar Members
[5510]183    public ISymbol StartSymbol {
[3338]184      get { return startSymbol; }
185      set { startSymbol = value; }
[3294]186    }
187
[5510]188    public void AddSymbol(ISymbol symbol) {
[3369]189      if (ContainsSymbol(symbol)) throw new ArgumentException("Symbol " + symbol + " is already defined.");
190      allSymbols.Add(symbol.Name, symbol);
[3993]191      allowedChildSymbols[symbol.Name] = new List<List<string>>();
[3294]192      ClearCaches();
193    }
194
[5510]195    public void RemoveSymbol(ISymbol symbol) {
[3360]196      foreach (var parent in Symbols) {
197        for (int i = 0; i < GetMaxSubtreeCount(parent); i++)
198          if (IsAllowedChild(parent, symbol, i))
199            allowedChildSymbols[parent.Name][i].Remove(symbol.Name);
200      }
[3369]201      allSymbols.Remove(symbol.Name);
[3338]202      minSubTreeCount.Remove(symbol.Name);
203      maxSubTreeCount.Remove(symbol.Name);
204      allowedChildSymbols.Remove(symbol.Name);
[3294]205      ClearCaches();
206    }
207
[5510]208    public IEnumerable<ISymbol> Symbols {
[3369]209      get { return allSymbols.Values.AsEnumerable(); }
[3294]210    }
211
[5510]212    public bool ContainsSymbol(ISymbol symbol) {
[3369]213      return allSymbols.ContainsKey(symbol.Name);
214    }
215
[5510]216    public void SetAllowedChild(ISymbol parent, ISymbol child, int argumentIndex) {
[3369]217      if (!ContainsSymbol(parent)) throw new ArgumentException("Unknown symbol: " + parent, "parent");
218      if (!ContainsSymbol(child)) throw new ArgumentException("Unknown symbol: " + child, "child");
[3338]219      if (argumentIndex >= GetMaxSubtreeCount(parent)) throw new ArgumentException("Symbol " + parent + " can have only " + GetMaxSubtreeCount(parent) + " subtrees.");
220      allowedChildSymbols[parent.Name][argumentIndex].Add(child.Name);
221      ClearCaches();
[3294]222    }
223
[5510]224    public bool IsAllowedChild(ISymbol parent, ISymbol child, int argumentIndex) {
[3369]225      if (!ContainsSymbol(parent)) throw new ArgumentException("Unknown symbol: " + parent, "parent");
226      if (!ContainsSymbol(child)) throw new ArgumentException("Unknown symbol: " + child, "child");
[3338]227      if (argumentIndex >= GetMaxSubtreeCount(parent)) throw new ArgumentException("Symbol " + parent + " can have only " + GetMaxSubtreeCount(parent) + " subtrees.");
[3369]228      return allowedChildSymbols[parent.Name][argumentIndex].Contains(child.Name);
[3294]229    }
230
[5529]231    public IEnumerable<ISymbol> GetAllowedSymbols(ISymbol parent, int argumentIndex) {
232      return allowedChildSymbols[parent.Name][argumentIndex].Select(x => allSymbols[x]);
233    }
234
[3338]235    private Dictionary<string, int> cachedMinExpressionLength;
[5510]236    public int GetMinExpressionLength(ISymbol symbol) {
[3369]237      if (!ContainsSymbol(symbol)) throw new ArgumentException("Unknown symbol: " + symbol);
[3338]238      if (!cachedMinExpressionLength.ContainsKey(symbol.Name)) {
239        cachedMinExpressionLength[symbol.Name] = int.MaxValue; // prevent infinite recursion
240        long sumOfMinExpressionLengths = 1 + (from argIndex in Enumerable.Range(0, GetMinSubtreeCount(symbol))
[3369]241                                              let minForSlot = (long)(from s in Symbols
[3338]242                                                                      where IsAllowedChild(symbol, s, argIndex)
243                                                                      select GetMinExpressionLength(s)).DefaultIfEmpty(0).Min()
244                                              select minForSlot).DefaultIfEmpty(0).Sum();
[3294]245
[3338]246        cachedMinExpressionLength[symbol.Name] = (int)Math.Min(sumOfMinExpressionLengths, int.MaxValue);
[3294]247      }
[3338]248      return cachedMinExpressionLength[symbol.Name];
[3294]249    }
250
[3338]251    private Dictionary<string, int> cachedMaxExpressionLength;
[5510]252    public int GetMaxExpressionLength(ISymbol symbol) {
[3369]253      if (!ContainsSymbol(symbol)) throw new ArgumentException("Unknown symbol: " + symbol);
[3338]254      if (!cachedMaxExpressionLength.ContainsKey(symbol.Name)) {
255        cachedMaxExpressionLength[symbol.Name] = int.MaxValue; // prevent infinite recursion
256        long sumOfMaxTrees = 1 + (from argIndex in Enumerable.Range(0, GetMaxSubtreeCount(symbol))
[3369]257                                  let maxForSlot = (long)(from s in Symbols
[3338]258                                                          where IsAllowedChild(symbol, s, argIndex)
259                                                          select GetMaxExpressionLength(s)).DefaultIfEmpty(0).Max()
[3294]260                                  select maxForSlot).DefaultIfEmpty(0).Sum();
261        long limit = int.MaxValue;
[3338]262        cachedMaxExpressionLength[symbol.Name] = (int)Math.Min(sumOfMaxTrees, limit);
[3294]263      }
[3338]264      return cachedMaxExpressionLength[symbol.Name];
[3294]265    }
266
[3338]267    private Dictionary<string, int> cachedMinExpressionDepth;
[5510]268    public int GetMinExpressionDepth(ISymbol symbol) {
[3369]269      if (!ContainsSymbol(symbol)) throw new ArgumentException("Unknown symbol: " + symbol);
[3338]270      if (!cachedMinExpressionDepth.ContainsKey(symbol.Name)) {
271        cachedMinExpressionDepth[symbol.Name] = int.MaxValue; // prevent infinite recursion
272        cachedMinExpressionDepth[symbol.Name] = 1 + (from argIndex in Enumerable.Range(0, GetMinSubtreeCount(symbol))
[3369]273                                                     let minForSlot = (from s in Symbols
[3338]274                                                                       where IsAllowedChild(symbol, s, argIndex)
275                                                                       select GetMinExpressionDepth(s)).DefaultIfEmpty(0).Min()
276                                                     select minForSlot).DefaultIfEmpty(0).Max();
[3294]277      }
[3338]278      return cachedMinExpressionDepth[symbol.Name];
[3294]279    }
280
[5510]281    public void SetMaxSubtreeCount(ISymbol symbol, int nSubTrees) {
[3369]282      if (!ContainsSymbol(symbol)) throw new ArgumentException("Unknown symbol: " + symbol);
[3338]283      maxSubTreeCount[symbol.Name] = nSubTrees;
284      while (allowedChildSymbols[symbol.Name].Count <= nSubTrees)
[3993]285        allowedChildSymbols[symbol.Name].Add(new List<string>());
[3338]286      while (allowedChildSymbols[symbol.Name].Count > nSubTrees) {
287        allowedChildSymbols[symbol.Name].RemoveAt(allowedChildSymbols[symbol.Name].Count - 1);
288      }
289      ClearCaches();
[3294]290    }
291
[5510]292    public void SetMinSubtreeCount(ISymbol symbol, int nSubTrees) {
[3369]293      if (!ContainsSymbol(symbol)) throw new ArgumentException("Unknown symbol: " + symbol);
[3338]294      minSubTreeCount[symbol.Name] = nSubTrees;
295      ClearCaches();
[3294]296    }
297
[5510]298    public int GetMinSubtreeCount(ISymbol symbol) {
[3369]299      if (!ContainsSymbol(symbol)) throw new ArgumentException("Unknown symbol: " + symbol);
[3338]300      return minSubTreeCount[symbol.Name];
[3294]301    }
302
[5510]303    public int GetMaxSubtreeCount(ISymbol symbol) {
[3369]304      if (!ContainsSymbol(symbol)) throw new ArgumentException("Unknown symbol: " + symbol);
[3338]305      return maxSubTreeCount[symbol.Name];
[3294]306    }
[3338]307    #endregion
308
309    private void ClearCaches() {
310      cachedMinExpressionLength.Clear();
311      cachedMaxExpressionLength.Clear();
312      cachedMinExpressionDepth.Clear();
[3294]313    }
314
[4722]315    protected void InitializeShallowClone(DefaultSymbolicExpressionGrammar original) {
316      minSubTreeCount = new Dictionary<string, int>(original.minSubTreeCount);
317      maxSubTreeCount = new Dictionary<string, int>(original.maxSubTreeCount);
[4249]318
[5510]319      allSymbols = new Dictionary<string, ISymbol>(original.allSymbols);
[4722]320      startSymbol = original.startSymbol;
321      allowedChildSymbols = new Dictionary<string, List<List<string>>>(original.allowedChildSymbols.Count);
322      foreach (var entry in original.allowedChildSymbols) {
323        allowedChildSymbols[entry.Key] = new List<List<string>>(entry.Value.Count);
[4249]324        foreach (var set in entry.Value) {
[4722]325          allowedChildSymbols[entry.Key].Add(new List<string>(set));
[4249]326        }
327      }
[3294]328    }
329  }
330}
Note: See TracBrowser for help on using the repository browser.