#region License Information
/* HeuristicLab
* Copyright (C) 2002-2011 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
*
* This file is part of HeuristicLab.
*
* HeuristicLab is free software: you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation, either version 3 of the License, or
* (at your option) any later version.
*
* HeuristicLab is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with HeuristicLab. If not, see .
*/
#endregion
using System;
using System.Collections.Generic;
using System.Linq;
using HeuristicLab.Common;
using HeuristicLab.Core;
using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
namespace HeuristicLab.Encodings.SymbolicExpressionTreeEncoding {
///
/// The default symbolic expression grammar stores symbols and syntactic constraints for symbols.
/// Symbols are treated as equvivalent if they have the same name.
/// Syntactic constraints limit the number of allowed sub trees for a node with a symbol and which symbols are allowed
/// in the sub-trees of a symbol (can be specified for each sub-tree index separately).
///
[StorableClass]
[Item("DefaultSymbolicExpressionGrammar", "Represents a grammar that defines the syntax of symbolic expression trees.")]
public abstract class DefaultSymbolicExpressionGrammar : Item, ISymbolicExpressionTreeGrammar {
#region properties for separation between implementation and persistence
[Storable]
private IEnumerable> MinSubTreeCount {
get { return minSubTreeCount.AsEnumerable(); }
set { minSubTreeCount = value.ToDictionary(x => x.Key, x => x.Value); }
}
[Storable]
private IEnumerable> MaxSubTreeCount {
get { return maxSubTreeCount.AsEnumerable(); }
set { maxSubTreeCount = value.ToDictionary(x => x.Key, x => x.Value); }
}
[Storable]
private IEnumerable>>> AllowedChildSymbols {
get {
return (from parentEntry in allowedChildSymbols
let setEnumeration = parentEntry.Value.Select(set => set.AsEnumerable()).ToList()
select new KeyValuePair>>(parentEntry.Key, setEnumeration))
.ToList();
}
set {
allowedChildSymbols = new Dictionary>>();
foreach (var pair in value) {
allowedChildSymbols[pair.Key] = new List>();
foreach (var entry in pair.Value) {
var hashSet = new List();
foreach (string child in entry) {
hashSet.Add(child);
}
allowedChildSymbols[pair.Key].Add(hashSet);
}
}
}
}
[Storable]
private IEnumerable> AllSymbols {
get { return allSymbols.AsEnumerable(); }
set { allSymbols = value.ToDictionary(x => x.Key, x => x.Value); }
}
#endregion
private Dictionary minSubTreeCount;
private Dictionary maxSubTreeCount;
private Dictionary>> allowedChildSymbols;
private Dictionary allSymbols;
[Storable]
private ISymbol startSymbol;
[StorableConstructor]
protected DefaultSymbolicExpressionGrammar(bool deserializing)
: base(deserializing) {
cachedMinExpressionLength = new Dictionary();
cachedMaxExpressionLength = new Dictionary();
cachedMinExpressionDepth = new Dictionary();
}
// cloning ctor
protected DefaultSymbolicExpressionGrammar(DefaultSymbolicExpressionGrammar original, Cloner cloner)
: base(original, cloner) {
this.cachedMinExpressionLength = new Dictionary();
this.cachedMaxExpressionLength = new Dictionary();
this.cachedMinExpressionDepth = new Dictionary();
minSubTreeCount = new Dictionary(original.minSubTreeCount);
maxSubTreeCount = new Dictionary(original.maxSubTreeCount);
allSymbols = new Dictionary();
foreach (ISymbol symbol in original.allSymbols.Values.Select(s => cloner.Clone(s)))
allSymbols.Add(symbol.Name, symbol);
startSymbol = cloner.Clone(original.startSymbol);
allowedChildSymbols = new Dictionary>>();
foreach (var entry in original.allowedChildSymbols) {
allowedChildSymbols[entry.Key] = new List>(entry.Value.Count);
foreach (var set in entry.Value) {
allowedChildSymbols[entry.Key].Add(new List(set));
}
}
}
protected DefaultSymbolicExpressionGrammar()
: base() {
this.minSubTreeCount = new Dictionary();
this.maxSubTreeCount = new Dictionary();
this.allowedChildSymbols = new Dictionary>>();
this.allSymbols = new Dictionary();
this.cachedMinExpressionLength = new Dictionary();
this.cachedMaxExpressionLength = new Dictionary();
this.cachedMinExpressionDepth = new Dictionary();
this.startSymbol = new StartSymbol();
this.AddSymbol(startSymbol);
this.SetMinSubtreeCount(startSymbol, 1);
this.SetMaxSubtreeCount(startSymbol, 1);
}
protected DefaultSymbolicExpressionGrammar(ISymbolicExpressionTreeGrammar grammar)
: base() {
Cloner cloner = new Cloner();
this.cachedMinExpressionLength = new Dictionary();
this.cachedMaxExpressionLength = new Dictionary();
this.cachedMinExpressionDepth = new Dictionary();
this.minSubTreeCount = new Dictionary();
this.maxSubTreeCount = new Dictionary();
this.allowedChildSymbols = new Dictionary>>();
this.allSymbols = new Dictionary();
this.StartSymbol = (ISymbol)cloner.Clone(grammar.StartSymbol);
foreach (ISymbol symbol in grammar.Symbols) {
ISymbol clonedSymbol = (ISymbol)cloner.Clone(symbol);
this.AddSymbol(clonedSymbol);
this.SetMinSubtreeCount(clonedSymbol, grammar.GetMinSubtreeCount(symbol));
this.SetMaxSubtreeCount(clonedSymbol, grammar.GetMaxSubtreeCount(symbol));
}
foreach (ISymbol parent in grammar.Symbols) {
for (int i = 0; i < grammar.GetMaxSubtreeCount(parent); i++) {
foreach (ISymbol child in grammar.Symbols) {
if (grammar.IsAllowedChild(parent, child, i)) {
this.SetAllowedChild((ISymbol)cloner.Clone(parent), (ISymbol)cloner.Clone(child), i);
}
}
}
}
}
public void Clear() {
minSubTreeCount.Clear();
maxSubTreeCount.Clear();
allowedChildSymbols.Clear();
allSymbols.Clear();
cachedMaxExpressionLength.Clear();
cachedMinExpressionLength.Clear();
cachedMinExpressionDepth.Clear();
startSymbol = new StartSymbol();
AddSymbol(startSymbol);
SetMinSubtreeCount(startSymbol, 1);
SetMaxSubtreeCount(startSymbol, 1);
}
#region ISymbolicExpressionGrammar Members
public ISymbol StartSymbol {
get { return startSymbol; }
set { startSymbol = value; }
}
public void AddSymbol(ISymbol symbol) {
if (ContainsSymbol(symbol)) throw new ArgumentException("Symbol " + symbol + " is already defined.");
allSymbols.Add(symbol.Name, symbol);
allowedChildSymbols[symbol.Name] = new List>();
ClearCaches();
}
public void RemoveSymbol(ISymbol symbol) {
foreach (var parent in Symbols) {
for (int i = 0; i < GetMaxSubtreeCount(parent); i++)
if (IsAllowedChild(parent, symbol, i))
allowedChildSymbols[parent.Name][i].Remove(symbol.Name);
}
allSymbols.Remove(symbol.Name);
minSubTreeCount.Remove(symbol.Name);
maxSubTreeCount.Remove(symbol.Name);
allowedChildSymbols.Remove(symbol.Name);
ClearCaches();
}
public IEnumerable Symbols {
get { return allSymbols.Values.AsEnumerable(); }
}
public bool ContainsSymbol(ISymbol symbol) {
return allSymbols.ContainsKey(symbol.Name);
}
public void SetAllowedChild(ISymbol parent, ISymbol child, int argumentIndex) {
if (!ContainsSymbol(parent)) throw new ArgumentException("Unknown symbol: " + parent, "parent");
if (!ContainsSymbol(child)) throw new ArgumentException("Unknown symbol: " + child, "child");
if (argumentIndex >= GetMaxSubtreeCount(parent)) throw new ArgumentException("Symbol " + parent + " can have only " + GetMaxSubtreeCount(parent) + " subtrees.");
allowedChildSymbols[parent.Name][argumentIndex].Add(child.Name);
ClearCaches();
}
public bool IsAllowedChild(ISymbol parent, ISymbol child, int argumentIndex) {
if (!ContainsSymbol(parent)) throw new ArgumentException("Unknown symbol: " + parent, "parent");
if (!ContainsSymbol(child)) throw new ArgumentException("Unknown symbol: " + child, "child");
if (argumentIndex >= GetMaxSubtreeCount(parent)) throw new ArgumentException("Symbol " + parent + " can have only " + GetMaxSubtreeCount(parent) + " subtrees.");
return allowedChildSymbols[parent.Name][argumentIndex].Contains(child.Name);
}
public IEnumerable GetAllowedSymbols(ISymbol parent, int argumentIndex) {
return allowedChildSymbols[parent.Name][argumentIndex].Select(x => allSymbols[x]);
}
private Dictionary cachedMinExpressionLength;
public int GetMinExpressionLength(ISymbol symbol) {
if (!ContainsSymbol(symbol)) throw new ArgumentException("Unknown symbol: " + symbol);
if (!cachedMinExpressionLength.ContainsKey(symbol.Name)) {
cachedMinExpressionLength[symbol.Name] = int.MaxValue; // prevent infinite recursion
long sumOfMinExpressionLengths = 1 + (from argIndex in Enumerable.Range(0, GetMinSubtreeCount(symbol))
let minForSlot = (long)(from s in Symbols
where IsAllowedChild(symbol, s, argIndex)
select GetMinExpressionLength(s)).DefaultIfEmpty(0).Min()
select minForSlot).DefaultIfEmpty(0).Sum();
cachedMinExpressionLength[symbol.Name] = (int)Math.Min(sumOfMinExpressionLengths, int.MaxValue);
}
return cachedMinExpressionLength[symbol.Name];
}
private Dictionary cachedMaxExpressionLength;
public int GetMaxExpressionLength(ISymbol symbol) {
if (!ContainsSymbol(symbol)) throw new ArgumentException("Unknown symbol: " + symbol);
if (!cachedMaxExpressionLength.ContainsKey(symbol.Name)) {
cachedMaxExpressionLength[symbol.Name] = int.MaxValue; // prevent infinite recursion
long sumOfMaxTrees = 1 + (from argIndex in Enumerable.Range(0, GetMaxSubtreeCount(symbol))
let maxForSlot = (long)(from s in Symbols
where IsAllowedChild(symbol, s, argIndex)
select GetMaxExpressionLength(s)).DefaultIfEmpty(0).Max()
select maxForSlot).DefaultIfEmpty(0).Sum();
long limit = int.MaxValue;
cachedMaxExpressionLength[symbol.Name] = (int)Math.Min(sumOfMaxTrees, limit);
}
return cachedMaxExpressionLength[symbol.Name];
}
private Dictionary cachedMinExpressionDepth;
public int GetMinExpressionDepth(ISymbol symbol) {
if (!ContainsSymbol(symbol)) throw new ArgumentException("Unknown symbol: " + symbol);
if (!cachedMinExpressionDepth.ContainsKey(symbol.Name)) {
cachedMinExpressionDepth[symbol.Name] = int.MaxValue; // prevent infinite recursion
cachedMinExpressionDepth[symbol.Name] = 1 + (from argIndex in Enumerable.Range(0, GetMinSubtreeCount(symbol))
let minForSlot = (from s in Symbols
where IsAllowedChild(symbol, s, argIndex)
select GetMinExpressionDepth(s)).DefaultIfEmpty(0).Min()
select minForSlot).DefaultIfEmpty(0).Max();
}
return cachedMinExpressionDepth[symbol.Name];
}
public void SetMaxSubtreeCount(ISymbol symbol, int nSubTrees) {
if (!ContainsSymbol(symbol)) throw new ArgumentException("Unknown symbol: " + symbol);
maxSubTreeCount[symbol.Name] = nSubTrees;
while (allowedChildSymbols[symbol.Name].Count <= nSubTrees)
allowedChildSymbols[symbol.Name].Add(new List());
while (allowedChildSymbols[symbol.Name].Count > nSubTrees) {
allowedChildSymbols[symbol.Name].RemoveAt(allowedChildSymbols[symbol.Name].Count - 1);
}
ClearCaches();
}
public void SetMinSubtreeCount(ISymbol symbol, int nSubTrees) {
if (!ContainsSymbol(symbol)) throw new ArgumentException("Unknown symbol: " + symbol);
minSubTreeCount[symbol.Name] = nSubTrees;
ClearCaches();
}
public int GetMinSubtreeCount(ISymbol symbol) {
if (!ContainsSymbol(symbol)) throw new ArgumentException("Unknown symbol: " + symbol);
return minSubTreeCount[symbol.Name];
}
public int GetMaxSubtreeCount(ISymbol symbol) {
if (!ContainsSymbol(symbol)) throw new ArgumentException("Unknown symbol: " + symbol);
return maxSubTreeCount[symbol.Name];
}
#endregion
private void ClearCaches() {
cachedMinExpressionLength.Clear();
cachedMaxExpressionLength.Clear();
cachedMinExpressionDepth.Clear();
}
protected void InitializeShallowClone(DefaultSymbolicExpressionGrammar original) {
minSubTreeCount = new Dictionary(original.minSubTreeCount);
maxSubTreeCount = new Dictionary(original.maxSubTreeCount);
allSymbols = new Dictionary(original.allSymbols);
startSymbol = original.startSymbol;
allowedChildSymbols = new Dictionary>>(original.allowedChildSymbols.Count);
foreach (var entry in original.allowedChildSymbols) {
allowedChildSymbols[entry.Key] = new List>(entry.Value.Count);
foreach (var set in entry.Value) {
allowedChildSymbols[entry.Key].Add(new List(set));
}
}
}
}
}