Free cookie consent management tool by TermsFeed Policy Generator

source: trunk/sources/HeuristicLab.Functions/BakedFunctionTree.cs @ 519

Last change on this file since 519 was 519, checked in by gkronber, 16 years ago

implemented #259 (BakedFunctionTree should provide an appropriate ToString() method)

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