Free cookie consent management tool by TermsFeed Policy Generator

source: branches/plugins/HeuristicLab.Functions/3.2/BakedFunctionTree.cs @ 652

Last change on this file since 652 was 652, checked in by gkronber, 16 years ago
  • added a solution to compile old plugin versions
  • fixed plugin references and
  • added script to generate AssemblyInfos with SubWCRev

(ticket #177)

File size: 12.3 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2008 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 System.Text;
26using HeuristicLab.Core;
27using HeuristicLab.DataAnalysis;
28using HeuristicLab.Data;
29using System.Xml;
30using System.Globalization;
31
32namespace HeuristicLab.Functions {
33
34  class LightWeightFunction {
35    public int arity = 0;
36    public IFunction functionType;
37    public List<double> data = new List<double>();
38
39    public LightWeightFunction Clone() {
40      LightWeightFunction clone = new LightWeightFunction();
41      clone.arity = arity;
42      clone.functionType = functionType;
43      clone.data.AddRange(data);
44      return clone;
45    }
46  }
47
48  class BakedFunctionTree : ItemBase, IFunctionTree {
49    private List<LightWeightFunction> linearRepresentation;
50    internal List<LightWeightFunction> LinearRepresentation {
51      get {
52        FlattenVariables();
53        FlattenTrees();
54        return linearRepresentation;
55      }
56    }
57    private bool treesExpanded = false;
58    private List<IFunctionTree> subTrees;
59    private bool variablesExpanded = false;
60    private List<IVariable> variables;
61
62    public BakedFunctionTree() {
63      linearRepresentation = new List<LightWeightFunction>();
64    }
65
66    internal BakedFunctionTree(IFunction function)
67      : this() {
68      LightWeightFunction fun = new LightWeightFunction();
69      fun.functionType = function;
70      linearRepresentation.Add(fun);
71      treesExpanded = true;
72      subTrees = new List<IFunctionTree>();
73      variables = new List<IVariable>();
74      variablesExpanded = true;
75      foreach(IVariableInfo variableInfo in function.VariableInfos) {
76        if(variableInfo.Local) {
77          variables.Add((IVariable)function.GetVariable(variableInfo.FormalName).Clone());
78        }
79      }
80    }
81
82    internal BakedFunctionTree(IFunctionTree tree)
83      : this() {
84      LightWeightFunction fun = new LightWeightFunction();
85      fun.functionType = tree.Function;
86      linearRepresentation.Add(fun);
87      foreach(IVariable variable in tree.LocalVariables) {
88        IItem value = variable.Value;
89        fun.data.Add(GetDoubleValue(value));
90      }
91      foreach(IFunctionTree subTree in tree.SubTrees) {
92        AddSubTree(new BakedFunctionTree(subTree));
93      }
94    }
95
96    private double GetDoubleValue(IItem value) {
97      if(value is DoubleData) {
98        return ((DoubleData)value).Data;
99      } else if(value is ConstrainedDoubleData) {
100        return ((ConstrainedDoubleData)value).Data;
101      } else if(value is IntData) {
102        return ((IntData)value).Data;
103      } else if(value is ConstrainedIntData) {
104        return ((ConstrainedIntData)value).Data;
105      } else throw new NotSupportedException("Invalid datatype of local variable for GP");
106    }
107
108    private int BranchLength(int branchRoot) {
109      int arity = linearRepresentation[branchRoot].arity;
110      int length = 1;
111      for(int i = 0; i < arity; i++) {
112        length += BranchLength(branchRoot + length);
113      }
114      return length;
115    }
116
117    private void FlattenTrees() {
118      if(treesExpanded) {
119        linearRepresentation[0].arity = subTrees.Count;
120        foreach(BakedFunctionTree subTree in subTrees) {
121          subTree.FlattenVariables();
122          subTree.FlattenTrees();
123          linearRepresentation.AddRange(subTree.linearRepresentation);
124        }
125        treesExpanded = false;
126        subTrees = null;
127      }
128    }
129
130    private void FlattenVariables() {
131      if(variablesExpanded) {
132        linearRepresentation[0].data.Clear();
133        foreach(IVariable variable in variables) {
134          linearRepresentation[0].data.Add(GetDoubleValue(variable.Value));
135        }
136        variablesExpanded = false;
137        variables = null;
138      }
139    }
140
141    public int Size {
142      get {
143        if(treesExpanded) {
144          int size = 1;
145          foreach(BakedFunctionTree tree in subTrees) {
146            size += tree.Size;
147          }
148          return size;
149        } else
150        return linearRepresentation.Count;
151      }
152    }
153
154    public int Height {
155      get {
156        if(treesExpanded) {
157          int height = 0;
158          foreach(IFunctionTree subTree in subTrees) {
159            int curHeight = subTree.Height;
160            if(curHeight > height) height = curHeight;
161          }
162          return height+1;
163        } else {
164          int nextBranchStart;
165          return BranchHeight(0, out nextBranchStart);
166        }
167      }
168    }
169
170    private int BranchHeight(int branchStart, out int nextBranchStart) {
171      LightWeightFunction f = linearRepresentation[branchStart];
172      int height = 0;
173      branchStart++;
174      for(int i = 0; i < f.arity; i++) {
175        int curHeight = BranchHeight(branchStart, out nextBranchStart);
176        if(curHeight > height) height = curHeight;
177        branchStart = nextBranchStart;
178      }
179      nextBranchStart = branchStart;
180      return height + 1;
181    }
182
183    public IList<IFunctionTree> SubTrees {
184      get {
185        if(!treesExpanded) {
186          subTrees = new List<IFunctionTree>();
187          int arity = linearRepresentation[0].arity;
188          int branchIndex = 1;
189          for(int i = 0; i < arity; i++) {
190            BakedFunctionTree subTree = new BakedFunctionTree();
191            int length = BranchLength(branchIndex);
192            for(int j = branchIndex; j < branchIndex + length; j++) {
193              subTree.linearRepresentation.Add(linearRepresentation[j]);
194            }
195            branchIndex += length;
196            subTrees.Add(subTree);
197          }
198          treesExpanded = true;
199          linearRepresentation.RemoveRange(1, linearRepresentation.Count - 1);
200          linearRepresentation[0].arity = 0;
201        }
202        return subTrees;
203      }
204    }
205
206    public ICollection<IVariable> LocalVariables {
207      get {
208        if(!variablesExpanded) {
209          variables = new List<IVariable>();
210          IFunction function = Function;
211          int localVariableIndex = 0;
212          foreach(IVariableInfo variableInfo in function.VariableInfos) {
213            if(variableInfo.Local) {
214              IVariable clone = (IVariable)function.GetVariable(variableInfo.FormalName).Clone();
215              IItem value = clone.Value;
216              if(value is ConstrainedDoubleData) {
217                ((ConstrainedDoubleData)value).Data = linearRepresentation[0].data[localVariableIndex];
218              } else if(value is ConstrainedIntData) {
219                ((ConstrainedIntData)value).Data = (int)linearRepresentation[0].data[localVariableIndex];
220              } else if(value is DoubleData) {
221                ((DoubleData)value).Data = linearRepresentation[0].data[localVariableIndex];
222              } else if(value is IntData) {
223                ((IntData)value).Data = (int)linearRepresentation[0].data[localVariableIndex];
224              } else throw new NotSupportedException("Invalid local variable type for GP.");
225              variables.Add(clone);
226              localVariableIndex++;
227            }
228          }
229          variablesExpanded = true;
230          linearRepresentation[0].data.Clear();
231        }
232        return variables;
233      }
234    }
235
236    public IFunction Function {
237      get { return linearRepresentation[0].functionType; }
238    }
239
240    public IVariable GetLocalVariable(string name) {
241      foreach(IVariable var in LocalVariables) {
242        if(var.Name == name) return var;
243      }
244      return null;
245    }
246
247    public void AddVariable(IVariable variable) {
248      throw new NotSupportedException();
249    }
250
251    public void RemoveVariable(string name) {
252      throw new NotSupportedException();
253    }
254
255    public void AddSubTree(IFunctionTree tree) {
256      if(!treesExpanded) throw new InvalidOperationException();
257      subTrees.Add(tree);
258    }
259
260    public void InsertSubTree(int index, IFunctionTree tree) {
261      if(!treesExpanded) throw new InvalidOperationException();
262      subTrees.Insert(index, tree);
263    }
264
265    public void RemoveSubTree(int index) {
266      // sanity check
267      if(!treesExpanded) throw new InvalidOperationException();
268      subTrees.RemoveAt(index);
269    }
270
271    public IEvaluator CreateEvaluator() {
272      return new BakedTreeEvaluator();
273    }
274
275    public override XmlNode GetXmlNode(string name, XmlDocument document, IDictionary<Guid, IStorable> persistedObjects) {
276      FlattenVariables();
277      FlattenTrees();
278      XmlNode node = base.GetXmlNode(name, document, persistedObjects);
279      XmlNode linearRepresentationNode = document.CreateElement("LinearRepresentation");
280      foreach(LightWeightFunction f in linearRepresentation) {
281        XmlNode entryNode = PersistenceManager.Persist("FunctionType", f.functionType, document, persistedObjects);
282        XmlAttribute arityAttribute = document.CreateAttribute("Arity");
283        arityAttribute.Value = f.arity+"";
284        entryNode.Attributes.Append(arityAttribute);
285        if(f.data.Count > 0) {
286          XmlAttribute dataAttribute = document.CreateAttribute("Data");
287          dataAttribute.Value = GetString(f.data);
288          entryNode.Attributes.Append(dataAttribute);
289        }
290        linearRepresentationNode.AppendChild(entryNode);
291      }
292
293      node.AppendChild(linearRepresentationNode);
294      return node;
295    }
296
297    public override void Populate(XmlNode node, IDictionary<Guid, IStorable> restoredObjects) {
298      base.Populate(node, restoredObjects);
299      XmlNode linearRepresentationNode = node.SelectSingleNode("LinearRepresentation");
300      foreach(XmlNode entryNode in linearRepresentationNode.ChildNodes) {
301        LightWeightFunction f = new LightWeightFunction();
302        f.arity = int.Parse(entryNode.Attributes["Arity"].Value, CultureInfo.InvariantCulture);
303        if(entryNode.Attributes["Data"]!=null)
304          f.data = GetList<double>(entryNode.Attributes["Data"].Value, s => double.Parse(s, CultureInfo.InvariantCulture));
305        f.functionType = (IFunction)PersistenceManager.Restore(entryNode, restoredObjects);
306        linearRepresentation.Add(f);
307      }
308      treesExpanded = false;
309      variablesExpanded = false;
310    }
311
312    private string GetString(IEnumerable<double> xs) {
313      StringBuilder builder = new StringBuilder();
314      foreach(double x in xs) {
315        builder.Append(x.ToString("r", CultureInfo.InvariantCulture) + "; ");
316      }
317      if(builder.Length > 0) builder.Remove(builder.Length - 2, 2);
318      return builder.ToString();
319    }
320
321    private List<T> GetList<T>(string s, Converter<string, T> converter) {
322      List<T> result = new List<T>();
323      string[] tokens = s.Split(new char[] { ';', ' ' }, StringSplitOptions.RemoveEmptyEntries);
324      foreach(string token in tokens) {
325        T x = converter(token.Trim());
326        result.Add(x);
327      }
328      return result;
329    }
330
331    public override object Clone(IDictionary<Guid, object> clonedObjects) {
332      BakedFunctionTree clone = new BakedFunctionTree();
333      // in case the user (de)serialized the tree between evaluation and selection we have to flatten the tree again.
334      if(treesExpanded) FlattenTrees();
335      if(variablesExpanded) FlattenVariables();
336      foreach(LightWeightFunction f in linearRepresentation) {
337        clone.linearRepresentation.Add(f.Clone());
338      }
339      return clone;
340    }
341
342    public override IView CreateView() {
343      return new FunctionTreeView(this);
344    }
345
346    public override string ToString() {
347      SymbolicExpressionExporter exporter = new SymbolicExpressionExporter();
348      exporter.Visit(this);
349      return exporter.GetStringRepresentation();
350    }
351  }
352}
Note: See TracBrowser for help on using the repository browser.