Free cookie consent management tool by TermsFeed Policy Generator

source: branches/Ticket175Branch/HeuristicLab.Functions/BakedFunctionTree.cs @ 339

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

fixed serialization in plugin HeuristicLab.Functions (ticket #175)

File size: 12.2 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    private bool treesExpanded = false;
51    private List<IFunctionTree> subTrees;
52    private bool variablesExpanded = false;
53    private List<IVariable> variables;
54
55    public BakedFunctionTree() {
56      linearRepresentation = new List<LightWeightFunction>();
57    }
58
59    internal BakedFunctionTree(IFunction function)
60      : this() {
61      LightWeightFunction fun = new LightWeightFunction();
62      fun.functionType = function;
63      linearRepresentation.Add(fun);
64      treesExpanded = true;
65      subTrees = new List<IFunctionTree>();
66      variables = new List<IVariable>();
67      variablesExpanded = true;
68      foreach(IVariableInfo variableInfo in function.VariableInfos) {
69        if(variableInfo.Local) {
70          variables.Add((IVariable)function.GetVariable(variableInfo.FormalName).Clone());
71        }
72      }
73    }
74
75    internal BakedFunctionTree(IFunctionTree tree)
76      : this() {
77      LightWeightFunction fun = new LightWeightFunction();
78      fun.functionType = tree.Function;
79      linearRepresentation.Add(fun);
80      foreach(IVariable variable in tree.LocalVariables) {
81        IItem value = variable.Value;
82        fun.data.Add(GetDoubleValue(value));
83      }
84      foreach(IFunctionTree subTree in tree.SubTrees) {
85        AddSubTree(new BakedFunctionTree(subTree));
86      }
87    }
88
89    private double GetDoubleValue(IItem value) {
90      if(value is DoubleData) {
91        return ((DoubleData)value).Data;
92      } else if(value is ConstrainedDoubleData) {
93        return ((ConstrainedDoubleData)value).Data;
94      } else if(value is IntData) {
95        return ((IntData)value).Data;
96      } else if(value is ConstrainedIntData) {
97        return ((ConstrainedIntData)value).Data;
98      } else throw new NotSupportedException("Invalid datatype of local variable for GP");
99    }
100
101    private int BranchLength(int branchRoot) {
102      int arity = linearRepresentation[branchRoot].arity;
103      int length = 1;
104      for(int i = 0; i < arity; i++) {
105        length += BranchLength(branchRoot + length);
106      }
107      return length;
108    }
109
110    private void FlattenTrees() {
111      if(treesExpanded) {
112        linearRepresentation[0].arity = subTrees.Count;
113        foreach(BakedFunctionTree subTree in subTrees) {
114          subTree.FlattenVariables();
115          subTree.FlattenTrees();
116          linearRepresentation.AddRange(subTree.linearRepresentation);
117        }
118        treesExpanded = false;
119        subTrees = null;
120      }
121    }
122
123    private void FlattenVariables() {
124      if(variablesExpanded) {
125        linearRepresentation[0].data.Clear();
126        foreach(IVariable variable in variables) {
127          linearRepresentation[0].data.Add(GetDoubleValue(variable.Value));
128        }
129        variablesExpanded = false;
130        variables = null;
131      }
132    }
133
134    public int Size {
135      get {
136        if(treesExpanded) {
137          int size = 1;
138          foreach(BakedFunctionTree tree in subTrees) {
139            size += tree.Size;
140          }
141          return size;
142        } else
143        return linearRepresentation.Count;
144      }
145    }
146
147    public int Height {
148      get {
149        if(treesExpanded) {
150          int height = 0;
151          foreach(IFunctionTree subTree in subTrees) {
152            int curHeight = subTree.Height;
153            if(curHeight > height) height = curHeight;
154          }
155          return height+1;
156        } else {
157          int nextBranchStart;
158          return BranchHeight(0, out nextBranchStart);
159        }
160      }
161    }
162
163    private int BranchHeight(int branchStart, out int nextBranchStart) {
164      LightWeightFunction f = linearRepresentation[branchStart];
165      int height = 0;
166      branchStart++;
167      for(int i = 0; i < f.arity; i++) {
168        int curHeight = BranchHeight(branchStart, out nextBranchStart);
169        if(curHeight > height) height = curHeight;
170        branchStart = nextBranchStart;
171      }
172      nextBranchStart = branchStart;
173      return height + 1;
174    }
175
176    public IList<IFunctionTree> SubTrees {
177      get {
178        if(!treesExpanded) {
179          subTrees = new List<IFunctionTree>();
180          int arity = linearRepresentation[0].arity;
181          int branchIndex = 1;
182          for(int i = 0; i < arity; i++) {
183            BakedFunctionTree subTree = new BakedFunctionTree();
184            int length = BranchLength(branchIndex);
185            for(int j = branchIndex; j < branchIndex + length; j++) {
186              subTree.linearRepresentation.Add(linearRepresentation[j]);
187            }
188            branchIndex += length;
189            subTrees.Add(subTree);
190          }
191          treesExpanded = true;
192          linearRepresentation.RemoveRange(1, linearRepresentation.Count - 1);
193          linearRepresentation[0].arity = 0;
194        }
195        return subTrees;
196      }
197    }
198
199    public ICollection<IVariable> LocalVariables {
200      get {
201        if(!variablesExpanded) {
202          variables = new List<IVariable>();
203          IFunction function = Function;
204          int localVariableIndex = 0;
205          foreach(IVariableInfo variableInfo in function.VariableInfos) {
206            if(variableInfo.Local) {
207              IVariable clone = (IVariable)function.GetVariable(variableInfo.FormalName).Clone();
208              IItem value = clone.Value;
209              if(value is ConstrainedDoubleData) {
210                ((ConstrainedDoubleData)value).Data = linearRepresentation[0].data[localVariableIndex];
211              } else if(value is ConstrainedIntData) {
212                ((ConstrainedIntData)value).Data = (int)linearRepresentation[0].data[localVariableIndex];
213              } else if(value is DoubleData) {
214                ((DoubleData)value).Data = linearRepresentation[0].data[localVariableIndex];
215              } else if(value is IntData) {
216                ((IntData)value).Data = (int)linearRepresentation[0].data[localVariableIndex];
217              } else throw new NotSupportedException("Invalid local variable type for GP.");
218              variables.Add(clone);
219              localVariableIndex++;
220            }
221          }
222          variablesExpanded = true;
223          linearRepresentation[0].data.Clear();
224        }
225        return variables;
226      }
227    }
228
229    public IFunction Function {
230      get { return linearRepresentation[0].functionType; }
231    }
232
233    public IVariable GetLocalVariable(string name) {
234      foreach(IVariable var in LocalVariables) {
235        if(var.Name == name) return var;
236      }
237      return null;
238    }
239
240    public void AddVariable(IVariable variable) {
241      throw new NotSupportedException();
242    }
243
244    public void RemoveVariable(string name) {
245      throw new NotSupportedException();
246    }
247
248    public void AddSubTree(IFunctionTree tree) {
249      if(!treesExpanded) throw new InvalidOperationException();
250      subTrees.Add(tree);
251    }
252
253    public void InsertSubTree(int index, IFunctionTree tree) {
254      if(!treesExpanded) throw new InvalidOperationException();
255      subTrees.Insert(index, tree);
256    }
257
258    public void RemoveSubTree(int index) {
259      // sanity check
260      if(!treesExpanded) throw new InvalidOperationException();
261      subTrees.RemoveAt(index);
262    }
263
264    bool evaluatorReset = false;
265    public double Evaluate(Dataset dataset, int sampleIndex) {
266      FlattenVariables();
267      FlattenTrees();
268      if(!evaluatorReset) {
269        BakedTreeEvaluator.ResetEvaluator(linearRepresentation);
270        evaluatorReset = true;
271      }
272      return BakedTreeEvaluator.Evaluate(dataset, sampleIndex);
273    }
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}
Note: See TracBrowser for help on using the repository browser.