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

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

Sorted usings and removed unused usings in entire solution (#1094)

File size: 13.0 KB
Line 
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;
25using HeuristicLab.Common;
26using HeuristicLab.Core;
27using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.Symbols;
28using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
29
30namespace HeuristicLab.Encodings.SymbolicExpressionTreeEncoding {
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>
37  [StorableClass]
38  [Item("DefaultSymbolicExpressionGrammar", "Represents a grammar that defines the syntax of symbolic expression trees.")]
39  public class DefaultSymbolicExpressionGrammar : Item, ISymbolicExpressionGrammar {
40
41    #region properties for separation between implementation and persistence
42    [Storable]
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 {
63        allowedChildSymbols = new Dictionary<string, List<List<string>>>();
64        foreach (var pair in value) {
65          allowedChildSymbols[pair.Key] = new List<List<string>>();
66          foreach (var entry in pair.Value) {
67            var hashSet = new List<string>();
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
83    private Dictionary<string, int> minSubTreeCount;
84    private Dictionary<string, int> maxSubTreeCount;
85    private Dictionary<string, List<List<string>>> allowedChildSymbols;
86    private Dictionary<string, Symbol> allSymbols;
87    [Storable]
88    private Symbol startSymbol;
89
90    public DefaultSymbolicExpressionGrammar()
91      : base() {
92      minSubTreeCount = new Dictionary<string, int>();
93      maxSubTreeCount = new Dictionary<string, int>();
94      allowedChildSymbols = new Dictionary<string, List<List<string>>>();
95      allSymbols = new Dictionary<string, Symbol>();
96
97      cachedMinExpressionLength = new Dictionary<string, int>();
98      cachedMaxExpressionLength = new Dictionary<string, int>();
99      cachedMinExpressionDepth = new Dictionary<string, int>();
100
101      startSymbol = new StartSymbol();
102      AddSymbol(startSymbol);
103      SetMinSubtreeCount(startSymbol, 1);
104      SetMaxSubtreeCount(startSymbol, 1);
105    }
106
107    //copy constructor for cloning
108    protected DefaultSymbolicExpressionGrammar(DefaultSymbolicExpressionGrammar copy)
109      : base() {
110      this.minSubTreeCount = new Dictionary<string, int>(copy.minSubTreeCount);
111      this.maxSubTreeCount = new Dictionary<string, int>(copy.maxSubTreeCount);
112
113      this.startSymbol = copy.startSymbol;
114      this.allowedChildSymbols = new Dictionary<string, List<List<string>>>();
115      foreach (var entry in copy.allowedChildSymbols) {
116        this.allowedChildSymbols[entry.Key] = new List<List<string>>(entry.Value.Count);
117        foreach (var set in entry.Value) {
118          this.allowedChildSymbols[entry.Key].Add(new List<string>(set));
119        }
120      }
121      this.allSymbols = new Dictionary<string, Symbol>(copy.allSymbols);
122
123      cachedMinExpressionLength = new Dictionary<string, int>();
124      cachedMaxExpressionLength = new Dictionary<string, int>();
125      cachedMinExpressionDepth = new Dictionary<string, int>();
126    }
127
128    [StorableConstructor]
129    protected DefaultSymbolicExpressionGrammar(bool deserializing)
130      : base(deserializing) {
131      cachedMinExpressionLength = new Dictionary<string, int>();
132      cachedMaxExpressionLength = new Dictionary<string, int>();
133      cachedMinExpressionDepth = new Dictionary<string, int>();
134    }
135
136    public void Clear() {
137      minSubTreeCount.Clear();
138      maxSubTreeCount.Clear();
139      allowedChildSymbols.Clear();
140      allSymbols.Clear();
141
142      cachedMaxExpressionLength.Clear();
143      cachedMinExpressionLength.Clear();
144      cachedMinExpressionDepth.Clear();
145
146      startSymbol = new StartSymbol();
147      AddSymbol(startSymbol);
148      SetMinSubtreeCount(startSymbol, 1);
149      SetMaxSubtreeCount(startSymbol, 1);
150    }
151
152    #region ISymbolicExpressionGrammar Members
153
154    public Symbol StartSymbol {
155      get { return startSymbol; }
156      set { startSymbol = value; }
157    }
158
159    public void AddSymbol(Symbol symbol) {
160      if (ContainsSymbol(symbol)) throw new ArgumentException("Symbol " + symbol + " is already defined.");
161      allSymbols.Add(symbol.Name, symbol);
162      allowedChildSymbols[symbol.Name] = new List<List<string>>();
163      ClearCaches();
164    }
165
166    public void RemoveSymbol(Symbol symbol) {
167      foreach (var parent in Symbols) {
168        for (int i = 0; i < GetMaxSubtreeCount(parent); i++)
169          if (IsAllowedChild(parent, symbol, i))
170            allowedChildSymbols[parent.Name][i].Remove(symbol.Name);
171      }
172      allSymbols.Remove(symbol.Name);
173      minSubTreeCount.Remove(symbol.Name);
174      maxSubTreeCount.Remove(symbol.Name);
175      allowedChildSymbols.Remove(symbol.Name);
176      ClearCaches();
177    }
178
179    public IEnumerable<Symbol> Symbols {
180      get { return allSymbols.Values.AsEnumerable(); }
181    }
182
183    public bool ContainsSymbol(Symbol symbol) {
184      return allSymbols.ContainsKey(symbol.Name);
185    }
186
187    public void SetAllowedChild(Symbol parent, Symbol child, int argumentIndex) {
188      if (!ContainsSymbol(parent)) throw new ArgumentException("Unknown symbol: " + parent, "parent");
189      if (!ContainsSymbol(child)) throw new ArgumentException("Unknown symbol: " + child, "child");
190      if (argumentIndex >= GetMaxSubtreeCount(parent)) throw new ArgumentException("Symbol " + parent + " can have only " + GetMaxSubtreeCount(parent) + " subtrees.");
191      allowedChildSymbols[parent.Name][argumentIndex].Add(child.Name);
192      ClearCaches();
193    }
194
195    public bool IsAllowedChild(Symbol parent, Symbol child, int argumentIndex) {
196      if (!ContainsSymbol(parent)) throw new ArgumentException("Unknown symbol: " + parent, "parent");
197      if (!ContainsSymbol(child)) throw new ArgumentException("Unknown symbol: " + child, "child");
198      if (argumentIndex >= GetMaxSubtreeCount(parent)) throw new ArgumentException("Symbol " + parent + " can have only " + GetMaxSubtreeCount(parent) + " subtrees.");
199      return allowedChildSymbols[parent.Name][argumentIndex].Contains(child.Name);
200    }
201
202    private Dictionary<string, int> cachedMinExpressionLength;
203    public int GetMinExpressionLength(Symbol symbol) {
204      if (!ContainsSymbol(symbol)) throw new ArgumentException("Unknown symbol: " + symbol);
205      if (!cachedMinExpressionLength.ContainsKey(symbol.Name)) {
206        cachedMinExpressionLength[symbol.Name] = int.MaxValue; // prevent infinite recursion
207        long sumOfMinExpressionLengths = 1 + (from argIndex in Enumerable.Range(0, GetMinSubtreeCount(symbol))
208                                              let minForSlot = (long)(from s in Symbols
209                                                                      where IsAllowedChild(symbol, s, argIndex)
210                                                                      select GetMinExpressionLength(s)).DefaultIfEmpty(0).Min()
211                                              select minForSlot).DefaultIfEmpty(0).Sum();
212
213        cachedMinExpressionLength[symbol.Name] = (int)Math.Min(sumOfMinExpressionLengths, int.MaxValue);
214      }
215      return cachedMinExpressionLength[symbol.Name];
216    }
217
218    private Dictionary<string, int> cachedMaxExpressionLength;
219    public int GetMaxExpressionLength(Symbol symbol) {
220      if (!ContainsSymbol(symbol)) throw new ArgumentException("Unknown symbol: " + symbol);
221      if (!cachedMaxExpressionLength.ContainsKey(symbol.Name)) {
222        cachedMaxExpressionLength[symbol.Name] = int.MaxValue; // prevent infinite recursion
223        long sumOfMaxTrees = 1 + (from argIndex in Enumerable.Range(0, GetMaxSubtreeCount(symbol))
224                                  let maxForSlot = (long)(from s in Symbols
225                                                          where IsAllowedChild(symbol, s, argIndex)
226                                                          select GetMaxExpressionLength(s)).DefaultIfEmpty(0).Max()
227                                  select maxForSlot).DefaultIfEmpty(0).Sum();
228        long limit = int.MaxValue;
229        cachedMaxExpressionLength[symbol.Name] = (int)Math.Min(sumOfMaxTrees, limit);
230      }
231      return cachedMaxExpressionLength[symbol.Name];
232    }
233
234    private Dictionary<string, int> cachedMinExpressionDepth;
235    public int GetMinExpressionDepth(Symbol symbol) {
236      if (!ContainsSymbol(symbol)) throw new ArgumentException("Unknown symbol: " + symbol);
237      if (!cachedMinExpressionDepth.ContainsKey(symbol.Name)) {
238        cachedMinExpressionDepth[symbol.Name] = int.MaxValue; // prevent infinite recursion
239        cachedMinExpressionDepth[symbol.Name] = 1 + (from argIndex in Enumerable.Range(0, GetMinSubtreeCount(symbol))
240                                                     let minForSlot = (from s in Symbols
241                                                                       where IsAllowedChild(symbol, s, argIndex)
242                                                                       select GetMinExpressionDepth(s)).DefaultIfEmpty(0).Min()
243                                                     select minForSlot).DefaultIfEmpty(0).Max();
244      }
245      return cachedMinExpressionDepth[symbol.Name];
246    }
247
248    public void SetMaxSubtreeCount(Symbol symbol, int nSubTrees) {
249      if (!ContainsSymbol(symbol)) throw new ArgumentException("Unknown symbol: " + symbol);
250      maxSubTreeCount[symbol.Name] = nSubTrees;
251      while (allowedChildSymbols[symbol.Name].Count <= nSubTrees)
252        allowedChildSymbols[symbol.Name].Add(new List<string>());
253      while (allowedChildSymbols[symbol.Name].Count > nSubTrees) {
254        allowedChildSymbols[symbol.Name].RemoveAt(allowedChildSymbols[symbol.Name].Count - 1);
255      }
256      ClearCaches();
257    }
258
259    public void SetMinSubtreeCount(Symbol symbol, int nSubTrees) {
260      if (!ContainsSymbol(symbol)) throw new ArgumentException("Unknown symbol: " + symbol);
261      minSubTreeCount[symbol.Name] = nSubTrees;
262      ClearCaches();
263    }
264
265    public int GetMinSubtreeCount(Symbol symbol) {
266      if (!ContainsSymbol(symbol)) throw new ArgumentException("Unknown symbol: " + symbol);
267      return minSubTreeCount[symbol.Name];
268    }
269
270    public int GetMaxSubtreeCount(Symbol symbol) {
271      if (!ContainsSymbol(symbol)) throw new ArgumentException("Unknown symbol: " + symbol);
272      return maxSubTreeCount[symbol.Name];
273    }
274
275    #endregion
276
277    private void ClearCaches() {
278      cachedMinExpressionLength.Clear();
279      cachedMaxExpressionLength.Clear();
280      cachedMinExpressionDepth.Clear();
281    }
282
283    public override IDeepCloneable Clone(Cloner cloner) {
284      DefaultSymbolicExpressionGrammar clone = new DefaultSymbolicExpressionGrammar(this);
285      cloner.RegisterClonedObject(this, clone);
286      return clone;
287    }
288  }
289}
Note: See TracBrowser for help on using the repository browser.