Free cookie consent management tool by TermsFeed Policy Generator

Ignore:
Timestamp:
04/16/10 12:12:29 (14 years ago)
Author:
gkronber
Message:

Changed way the grammar is stored in tree nodes to make it more efficient and fixed bugs in symbolic expression tree operators. #290 (Implement ADFs)

File:
1 edited

Legend:

Unmodified
Added
Removed

  • trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.3/DefaultSymbolicExpressionGrammar.cs

    r3360 r3369  
    3030
    3131namespace HeuristicLab.Encodings.SymbolicExpressionTreeEncoding {
     32  /// <summary>
     33  /// The default symbolic expression grammar stores symbols and syntactic constraints for symbols.
     34  /// Symbols are treated as equvivalent if they have the same name.
     35  /// Syntactic constraints limit the number of allowed sub trees for a node with a symbol and which symbols are allowed
     36  /// in the sub-trees of a symbol (can be specified for each sub-tree index separately).
     37  /// </summary>
    3238  [StorableClass]
    3339  [Item("DefaultSymbolicExpressionGrammar", "Represents a grammar that defines the syntax of symbolic expression trees.")]
    … …  
    4046    private Dictionary<string, List<HashSet<string>>> allowedChildSymbols;
    4147    [Storable]
    42     private HashSet<Symbol> allSymbols;
     48    private Dictionary<string, Symbol> allSymbols;
    4349
    4450    public DefaultSymbolicExpressionGrammar()
    … …  
    6672      maxSubTreeCount = new Dictionary<string, int>();
    6773      allowedChildSymbols = new Dictionary<string, List<HashSet<string>>>();
    68       allSymbols = new HashSet<Symbol>();
     74      allSymbols = new Dictionary<string, Symbol>();
    6975      cachedMinExpressionLength = new Dictionary<string, int>();
    7076      cachedMaxExpressionLength = new Dictionary<string, int>();
    … …  
    7480
    7581    public void AddSymbol(Symbol symbol) {
    76       if (allSymbols.Any(s => s.Name == symbol.Name)) throw new ArgumentException("Symbol " + symbol + " is already defined.");
    77       allSymbols.Add(symbol);
     82      if (ContainsSymbol(symbol)) throw new ArgumentException("Symbol " + symbol + " is already defined.");
     83      allSymbols.Add(symbol.Name, symbol);
    7884      allowedChildSymbols[symbol.Name] = new List<HashSet<string>>();
    7985      ClearCaches();
    … …  
    8692            allowedChildSymbols[parent.Name][i].Remove(symbol.Name);
    8793      }
    88       allSymbols.RemoveWhere(s => s.Name == symbol.Name);
     94      allSymbols.Remove(symbol.Name);
    8995      minSubTreeCount.Remove(symbol.Name);
    9096      maxSubTreeCount.Remove(symbol.Name);
    … …  
    94100
    95101    public IEnumerable<Symbol> Symbols {
    96       get { return allSymbols.AsEnumerable(); }
     102      get { return allSymbols.Values.AsEnumerable(); }
     103    }
     104
     105    public bool ContainsSymbol(Symbol symbol) {
     106      return allSymbols.ContainsKey(symbol.Name);
    97107    }
    98108
    99109    public void SetAllowedChild(Symbol parent, Symbol child, int argumentIndex) {
    100       if (!allSymbols.Any(s => s.Name == parent.Name)) throw new ArgumentException("Unknown symbol: " + parent, "parent");
    101       if (!allSymbols.Any(s => s.Name == child.Name)) throw new ArgumentException("Unknown symbol: " + child, "child");
     110      if (!ContainsSymbol(parent)) throw new ArgumentException("Unknown symbol: " + parent, "parent");
     111      if (!ContainsSymbol(child)) throw new ArgumentException("Unknown symbol: " + child, "child");
    102112      if (argumentIndex >= GetMaxSubtreeCount(parent)) throw new ArgumentException("Symbol " + parent + " can have only " + GetMaxSubtreeCount(parent) + " subtrees.");
    103113      allowedChildSymbols[parent.Name][argumentIndex].Add(child.Name);
    … …  
    106116
    107117    public bool IsAllowedChild(Symbol parent, Symbol child, int argumentIndex) {
    108       if (!allSymbols.Any(s => s.Name == parent.Name)) throw new ArgumentException("Unknown symbol: " + parent, "parent");
    109       if (!allSymbols.Any(s => s.Name == child.Name)) throw new ArgumentException("Unknown symbol: " + child, "child");
     118      if (!ContainsSymbol(parent)) throw new ArgumentException("Unknown symbol: " + parent, "parent");
     119      if (!ContainsSymbol(child)) throw new ArgumentException("Unknown symbol: " + child, "child");
    110120      if (argumentIndex >= GetMaxSubtreeCount(parent)) throw new ArgumentException("Symbol " + parent + " can have only " + GetMaxSubtreeCount(parent) + " subtrees.");
    111       if (allowedChildSymbols.ContainsKey(parent.Name)) return allowedChildSymbols[parent.Name][argumentIndex].Contains(child.Name);
    112       return false;
     121      return allowedChildSymbols[parent.Name][argumentIndex].Contains(child.Name);
    113122    }
    114123
    115124    private Dictionary<string, int> cachedMinExpressionLength;
    116125    public int GetMinExpressionLength(Symbol symbol) {
    117       if (!allSymbols.Any(s => s.Name == symbol.Name)) throw new ArgumentException("Unknown symbol: " + symbol);
     126      if (!ContainsSymbol(symbol)) throw new ArgumentException("Unknown symbol: " + symbol);
    118127      if (!cachedMinExpressionLength.ContainsKey(symbol.Name)) {
    119128        cachedMinExpressionLength[symbol.Name] = int.MaxValue; // prevent infinite recursion
    120129        long sumOfMinExpressionLengths = 1 + (from argIndex in Enumerable.Range(0, GetMinSubtreeCount(symbol))
    121                                               let minForSlot = (long)(from s in allSymbols
     130                                              let minForSlot = (long)(from s in Symbols
    122131                                                                      where IsAllowedChild(symbol, s, argIndex)
    123132                                                                      select GetMinExpressionLength(s)).DefaultIfEmpty(0).Min()
    … …  
    131140    private Dictionary<string, int> cachedMaxExpressionLength;
    132141    public int GetMaxExpressionLength(Symbol symbol) {
    133       if (!allSymbols.Any(s => s.Name == symbol.Name)) throw new ArgumentException("Unknown symbol: " + symbol);
     142      if (!ContainsSymbol(symbol)) throw new ArgumentException("Unknown symbol: " + symbol);
    134143      if (!cachedMaxExpressionLength.ContainsKey(symbol.Name)) {
    135144        cachedMaxExpressionLength[symbol.Name] = int.MaxValue; // prevent infinite recursion
    136145        long sumOfMaxTrees = 1 + (from argIndex in Enumerable.Range(0, GetMaxSubtreeCount(symbol))
    137                                   let maxForSlot = (long)(from s in allSymbols
     146                                  let maxForSlot = (long)(from s in Symbols
    138147                                                          where IsAllowedChild(symbol, s, argIndex)
    139148                                                          select GetMaxExpressionLength(s)).DefaultIfEmpty(0).Max()
    … …  
    147156    private Dictionary<string, int> cachedMinExpressionDepth;
    148157    public int GetMinExpressionDepth(Symbol symbol) {
    149       if (!allSymbols.Any(s => s.Name == symbol.Name)) throw new ArgumentException("Unknown symbol: " + symbol);
     158      if (!ContainsSymbol(symbol)) throw new ArgumentException("Unknown symbol: " + symbol);
    150159      if (!cachedMinExpressionDepth.ContainsKey(symbol.Name)) {
    151160        cachedMinExpressionDepth[symbol.Name] = int.MaxValue; // prevent infinite recursion
    152161        cachedMinExpressionDepth[symbol.Name] = 1 + (from argIndex in Enumerable.Range(0, GetMinSubtreeCount(symbol))
    153                                                      let minForSlot = (from s in allSymbols
     162                                                     let minForSlot = (from s in Symbols
    154163                                                                       where IsAllowedChild(symbol, s, argIndex)
    155164                                                                       select GetMinExpressionDepth(s)).DefaultIfEmpty(0).Min()
    … …  
    160169
    161170    public void SetMaxSubtreeCount(Symbol symbol, int nSubTrees) {
    162       if (!allSymbols.Any(s => s.Name == symbol.Name)) throw new ArgumentException("Unknown symbol: " + symbol);
     171      if (!ContainsSymbol(symbol)) throw new ArgumentException("Unknown symbol: " + symbol);
    163172      maxSubTreeCount[symbol.Name] = nSubTrees;
    164173      while (allowedChildSymbols[symbol.Name].Count <= nSubTrees)
    … …  
    171180
    172181    public void SetMinSubtreeCount(Symbol symbol, int nSubTrees) {
    173       if (!allSymbols.Any(s => s.Name == symbol.Name)) throw new ArgumentException("Unknown symbol: " + symbol);
     182      if (!ContainsSymbol(symbol)) throw new ArgumentException("Unknown symbol: " + symbol);
    174183      minSubTreeCount[symbol.Name] = nSubTrees;
    175184      ClearCaches();
    … …  
    177186
    178187    public int GetMinSubtreeCount(Symbol symbol) {
    179       if (!allSymbols.Any(s => s.Name == symbol.Name)) throw new ArgumentException("Unknown symbol: " + symbol);
     188      if (!ContainsSymbol(symbol)) throw new ArgumentException("Unknown symbol: " + symbol);
    180189      return minSubTreeCount[symbol.Name];
    181190    }
    182191
    183192    public int GetMaxSubtreeCount(Symbol symbol) {
    184       if (!allSymbols.Any(s => s.Name == symbol.Name)) throw new ArgumentException("Unknown symbol: " + symbol);
     193      if (!ContainsSymbol(symbol)) throw new ArgumentException("Unknown symbol: " + symbol);
    185194      return maxSubTreeCount[symbol.Name];
    186195    }
    … …  
    193202      cachedMinExpressionDepth.Clear();
    194203    }
    195 
    196     //private void symbol_ToStringChanged(object sender, EventArgs e) {
    197     //  OnToStringChanged();
    198     //}
    199 
    200     //private bool IsValidExpression(SymbolicExpressionTreeNode root) {
    201     //  if (root.SubTrees.Count < root.GetMinSubtreeCount()) return false;
    202     //  else if (root.SubTrees.Count > root.GetMaxSubtreeCount()) return false;
    203     //  else for (int i = 0; i < root.SubTrees.Count; i++) {
    204     //      if (!root.GetAllowedSymbols(i).Select(x => x.Name).Contains(root.SubTrees[i].Symbol.Name)) return false;
    205     //      if (!IsValidExpression(root.SubTrees[i])) return false;
    206     //    }
    207     //  return true;
    208     //}
    209204
    210205    public override IDeepCloneable Clone(Cloner cloner) {
    … …  
    220215        }
    221216      }
    222       clone.allSymbols = new HashSet<Symbol>(allSymbols);
     217      clone.allSymbols = new Dictionary<string, Symbol>(allSymbols);
    223218      return clone;
    224219    }
Note: See TracChangeset for help on using the changeset viewer.