Free cookie consent management tool by TermsFeed Policy Generator

source: trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.3/DefaultSymbolicExpressionGrammar.cs @ 4746

Last change on this file since 4746 was 4722, checked in by swagner, 14 years ago

Merged cloning refactoring branch back into trunk (#922)

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