source: trunk/sources/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Converters/TreeSimplifier.cs @ 14390

Last change on this file since 14390 was 14390, checked in by gkronber, 4 years ago

#2697:

  • renaming of folder "Transformation" to "Converters" to distinguish between transformations for variables (from data preprocessing) and classes for transformation of trees.
  • renamed SymbolicDataAnalysisExpressionTreeSimplifier -> TreeSimplifier
  • Implemented a converter to create a linar model as a symbolic expression tree
File size: 43.1 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2016 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 HeuristicLab.Common;
26using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
27
28namespace HeuristicLab.Problems.DataAnalysis.Symbolic {
29  /// <summary>
30  /// Simplifier for symbolic expressions
31  /// </summary>
32  public class TreeSimplifier {
33    private Addition addSymbol = new Addition();
34    private Subtraction subSymbol = new Subtraction();
35    private Multiplication mulSymbol = new Multiplication();
36    private Division divSymbol = new Division();
37    private Constant constSymbol = new Constant();
38    private Variable varSymbol = new Variable();
39    private Logarithm logSymbol = new Logarithm();
40    private Exponential expSymbol = new Exponential();
41    private Root rootSymbol = new Root();
42    private Square sqrSymbol = new Square();
43    private SquareRoot sqrtSymbol = new SquareRoot();
44    private Power powSymbol = new Power();
45    private Sine sineSymbol = new Sine();
46    private Cosine cosineSymbol = new Cosine();
47    private Tangent tanSymbol = new Tangent();
48    private IfThenElse ifThenElseSymbol = new IfThenElse();
49    private And andSymbol = new And();
50    private Or orSymbol = new Or();
51    private Not notSymbol = new Not();
52    private GreaterThan gtSymbol = new GreaterThan();
53    private LessThan ltSymbol = new LessThan();
54    private Integral integralSymbol = new Integral();
55    private LaggedVariable laggedVariableSymbol = new LaggedVariable();
56    private TimeLag timeLagSymbol = new TimeLag();
57
58    public ISymbolicExpressionTree Simplify(ISymbolicExpressionTree originalTree) {
59      var clone = (ISymbolicExpressionTreeNode)originalTree.Root.Clone();
60      // macro expand (initially no argument trees)
61      var macroExpandedTree = MacroExpand(clone, clone.GetSubtree(0), new List<ISymbolicExpressionTreeNode>());
62      ISymbolicExpressionTreeNode rootNode = (new ProgramRootSymbol()).CreateTreeNode();
63      rootNode.AddSubtree(GetSimplifiedTree(macroExpandedTree));
64      return new SymbolicExpressionTree(rootNode);
65    }
66
67    // the argumentTrees list contains already expanded trees used as arguments for invocations
68    private ISymbolicExpressionTreeNode MacroExpand(ISymbolicExpressionTreeNode root, ISymbolicExpressionTreeNode node, IList<ISymbolicExpressionTreeNode> argumentTrees) {
69      List<ISymbolicExpressionTreeNode> subtrees = new List<ISymbolicExpressionTreeNode>(node.Subtrees);
70      while (node.SubtreeCount > 0) node.RemoveSubtree(0);
71      if (node.Symbol is InvokeFunction) {
72        var invokeSym = node.Symbol as InvokeFunction;
73        var defunNode = FindFunctionDefinition(root, invokeSym.FunctionName);
74        var macroExpandedArguments = new List<ISymbolicExpressionTreeNode>();
75        foreach (var subtree in subtrees) {
76          macroExpandedArguments.Add(MacroExpand(root, subtree, argumentTrees));
77        }
78        return MacroExpand(root, defunNode, macroExpandedArguments);
79      } else if (node.Symbol is Argument) {
80        var argSym = node.Symbol as Argument;
81        // return the correct argument sub-tree (already macro-expanded)
82        return (SymbolicExpressionTreeNode)argumentTrees[argSym.ArgumentIndex].Clone();
83      } else {
84        // recursive application
85        foreach (var subtree in subtrees) {
86          node.AddSubtree(MacroExpand(root, subtree, argumentTrees));
87        }
88        return node;
89      }
90    }
91
92    private ISymbolicExpressionTreeNode FindFunctionDefinition(ISymbolicExpressionTreeNode root, string functionName) {
93      foreach (var subtree in root.Subtrees.OfType<DefunTreeNode>()) {
94        if (subtree.FunctionName == functionName) return subtree.GetSubtree(0);
95      }
96
97      throw new ArgumentException("Definition of function " + functionName + " not found.");
98    }
99
100
101    #region symbol predicates
102    // arithmetic
103    private bool IsDivision(ISymbolicExpressionTreeNode node) {
104      return node.Symbol is Division;
105    }
106
107    private bool IsMultiplication(ISymbolicExpressionTreeNode node) {
108      return node.Symbol is Multiplication;
109    }
110
111    private bool IsSubtraction(ISymbolicExpressionTreeNode node) {
112      return node.Symbol is Subtraction;
113    }
114
115    private bool IsAddition(ISymbolicExpressionTreeNode node) {
116      return node.Symbol is Addition;
117    }
118
119    private bool IsAverage(ISymbolicExpressionTreeNode node) {
120      return node.Symbol is Average;
121    }
122    // exponential
123    private bool IsLog(ISymbolicExpressionTreeNode node) {
124      return node.Symbol is Logarithm;
125    }
126    private bool IsExp(ISymbolicExpressionTreeNode node) {
127      return node.Symbol is Exponential;
128    }
129    private bool IsRoot(ISymbolicExpressionTreeNode node) {
130      return node.Symbol is Root;
131    }
132    private bool IsSquare(ISymbolicExpressionTreeNode node) {
133      return node.Symbol is Square;
134    }
135    private bool IsSquareRoot(ISymbolicExpressionTreeNode node) {
136      return node.Symbol is SquareRoot;
137    }
138    private bool IsPower(ISymbolicExpressionTreeNode node) {
139      return node.Symbol is Power;
140    }
141    // trigonometric
142    private bool IsSine(ISymbolicExpressionTreeNode node) {
143      return node.Symbol is Sine;
144    }
145    private bool IsCosine(ISymbolicExpressionTreeNode node) {
146      return node.Symbol is Cosine;
147    }
148    private bool IsTangent(ISymbolicExpressionTreeNode node) {
149      return node.Symbol is Tangent;
150    }
151    // boolean
152    private bool IsIfThenElse(ISymbolicExpressionTreeNode node) {
153      return node.Symbol is IfThenElse;
154    }
155    private bool IsAnd(ISymbolicExpressionTreeNode node) {
156      return node.Symbol is And;
157    }
158    private bool IsOr(ISymbolicExpressionTreeNode node) {
159      return node.Symbol is Or;
160    }
161    private bool IsNot(ISymbolicExpressionTreeNode node) {
162      return node.Symbol is Not;
163    }
164    // comparison
165    private bool IsGreaterThan(ISymbolicExpressionTreeNode node) {
166      return node.Symbol is GreaterThan;
167    }
168    private bool IsLessThan(ISymbolicExpressionTreeNode node) {
169      return node.Symbol is LessThan;
170    }
171
172    private bool IsBoolean(ISymbolicExpressionTreeNode node) {
173      return
174        node.Symbol is GreaterThan ||
175        node.Symbol is LessThan ||
176        node.Symbol is And ||
177        node.Symbol is Or;
178    }
179
180    // terminals
181    private bool IsVariable(ISymbolicExpressionTreeNode node) {
182      return node.Symbol is Variable;
183    }
184
185    private bool IsConstant(ISymbolicExpressionTreeNode node) {
186      return node.Symbol is Constant;
187    }
188
189    // dynamic
190    private bool IsTimeLag(ISymbolicExpressionTreeNode node) {
191      return node.Symbol is TimeLag;
192    }
193    private bool IsIntegral(ISymbolicExpressionTreeNode node) {
194      return node.Symbol is Integral;
195    }
196
197    #endregion
198
199    /// <summary>
200    /// Creates a new simplified tree
201    /// </summary>
202    /// <param name="original"></param>
203    /// <returns></returns>
204    public ISymbolicExpressionTreeNode GetSimplifiedTree(ISymbolicExpressionTreeNode original) {
205      if (IsConstant(original) || IsVariable(original)) {
206        return (ISymbolicExpressionTreeNode)original.Clone();
207      } else if (IsAddition(original)) {
208        return SimplifyAddition(original);
209      } else if (IsSubtraction(original)) {
210        return SimplifySubtraction(original);
211      } else if (IsMultiplication(original)) {
212        return SimplifyMultiplication(original);
213      } else if (IsDivision(original)) {
214        return SimplifyDivision(original);
215      } else if (IsAverage(original)) {
216        return SimplifyAverage(original);
217      } else if (IsLog(original)) {
218        return SimplifyLog(original);
219      } else if (IsExp(original)) {
220        return SimplifyExp(original);
221      } else if (IsSquare(original)) {
222        return SimplifySquare(original);
223      } else if (IsSquareRoot(original)) {
224        return SimplifySquareRoot(original);
225      } else if (IsPower(original)) {
226        return SimplifyPower(original);
227      } else if (IsRoot(original)) {
228        return SimplifyRoot(original);
229      } else if (IsSine(original)) {
230        return SimplifySine(original);
231      } else if (IsCosine(original)) {
232        return SimplifyCosine(original);
233      } else if (IsTangent(original)) {
234        return SimplifyTangent(original);
235      } else if (IsIfThenElse(original)) {
236        return SimplifyIfThenElse(original);
237      } else if (IsGreaterThan(original)) {
238        return SimplifyGreaterThan(original);
239      } else if (IsLessThan(original)) {
240        return SimplifyLessThan(original);
241      } else if (IsAnd(original)) {
242        return SimplifyAnd(original);
243      } else if (IsOr(original)) {
244        return SimplifyOr(original);
245      } else if (IsNot(original)) {
246        return SimplifyNot(original);
247      } else if (IsTimeLag(original)) {
248        return SimplifyTimeLag(original);
249      } else if (IsIntegral(original)) {
250        return SimplifyIntegral(original);
251      } else {
252        return SimplifyAny(original);
253      }
254    }
255
256
257    #region specific simplification routines
258    private ISymbolicExpressionTreeNode SimplifyAny(ISymbolicExpressionTreeNode original) {
259      // can't simplify this function but simplify all subtrees
260      List<ISymbolicExpressionTreeNode> subtrees = new List<ISymbolicExpressionTreeNode>(original.Subtrees);
261      while (original.Subtrees.Count() > 0) original.RemoveSubtree(0);
262      var clone = (SymbolicExpressionTreeNode)original.Clone();
263      List<ISymbolicExpressionTreeNode> simplifiedSubtrees = new List<ISymbolicExpressionTreeNode>();
264      foreach (var subtree in subtrees) {
265        simplifiedSubtrees.Add(GetSimplifiedTree(subtree));
266        original.AddSubtree(subtree);
267      }
268      foreach (var simplifiedSubtree in simplifiedSubtrees) {
269        clone.AddSubtree(simplifiedSubtree);
270      }
271      if (simplifiedSubtrees.TrueForAll(t => IsConstant(t))) {
272        SimplifyConstantExpression(clone);
273      }
274      return clone;
275    }
276
277    private ISymbolicExpressionTreeNode SimplifyConstantExpression(ISymbolicExpressionTreeNode original) {
278      // not yet implemented
279      return original;
280    }
281
282    private ISymbolicExpressionTreeNode SimplifyAverage(ISymbolicExpressionTreeNode original) {
283      if (original.Subtrees.Count() == 1) {
284        return GetSimplifiedTree(original.GetSubtree(0));
285      } else {
286        // simplify expressions x0..xn
287        // make sum(x0..xn) / n
288        var sum = original.Subtrees
289          .Select(GetSimplifiedTree)
290          .Aggregate(MakeSum);
291        return MakeFraction(sum, MakeConstant(original.Subtrees.Count()));
292      }
293    }
294
295    private ISymbolicExpressionTreeNode SimplifyDivision(ISymbolicExpressionTreeNode original) {
296      if (original.Subtrees.Count() == 1) {
297        return Invert(GetSimplifiedTree(original.GetSubtree(0)));
298      } else {
299        // simplify expressions x0..xn
300        // make multiplication (x0 * 1/(x1 * x1 * .. * xn))
301        var first = original.GetSubtree(0);
302        var second = original.GetSubtree(1);
303        var remaining = original.Subtrees.Skip(2);
304        return
305          MakeProduct(GetSimplifiedTree(first), Invert(remaining.Aggregate(GetSimplifiedTree(second), (a, b) => MakeProduct(a, GetSimplifiedTree(b)))));
306      }
307    }
308
309    private ISymbolicExpressionTreeNode SimplifyMultiplication(ISymbolicExpressionTreeNode original) {
310      if (original.Subtrees.Count() == 1) {
311        return GetSimplifiedTree(original.GetSubtree(0));
312      } else {
313        return original.Subtrees
314          .Select(GetSimplifiedTree)
315          .Aggregate(MakeProduct);
316      }
317    }
318
319    private ISymbolicExpressionTreeNode SimplifySubtraction(ISymbolicExpressionTreeNode original) {
320      if (original.Subtrees.Count() == 1) {
321        return Negate(GetSimplifiedTree(original.GetSubtree(0)));
322      } else {
323        // simplify expressions x0..xn
324        // make addition (x0,-x1..-xn)
325        var first = original.Subtrees.First();
326        var remaining = original.Subtrees.Skip(1);
327        return remaining.Aggregate(GetSimplifiedTree(first), (a, b) => MakeSum(a, Negate(GetSimplifiedTree(b))));
328      }
329    }
330
331    private ISymbolicExpressionTreeNode SimplifyAddition(ISymbolicExpressionTreeNode original) {
332      if (original.Subtrees.Count() == 1) {
333        return GetSimplifiedTree(original.GetSubtree(0));
334      } else {
335        // simplify expression x0..xn
336        // make addition (x0..xn)
337        return original.Subtrees
338          .Select(GetSimplifiedTree)
339          .Aggregate(MakeSum);
340      }
341    }
342
343    private ISymbolicExpressionTreeNode SimplifyNot(ISymbolicExpressionTreeNode original) {
344      return MakeNot(GetSimplifiedTree(original.GetSubtree(0)));
345    }
346    private ISymbolicExpressionTreeNode SimplifyOr(ISymbolicExpressionTreeNode original) {
347      return original.Subtrees
348        .Select(GetSimplifiedTree)
349        .Aggregate(MakeOr);
350    }
351    private ISymbolicExpressionTreeNode SimplifyAnd(ISymbolicExpressionTreeNode original) {
352      return original.Subtrees
353        .Select(GetSimplifiedTree)
354        .Aggregate(MakeAnd);
355    }
356    private ISymbolicExpressionTreeNode SimplifyLessThan(ISymbolicExpressionTreeNode original) {
357      return MakeLessThan(GetSimplifiedTree(original.GetSubtree(0)), GetSimplifiedTree(original.GetSubtree(1)));
358    }
359    private ISymbolicExpressionTreeNode SimplifyGreaterThan(ISymbolicExpressionTreeNode original) {
360      return MakeGreaterThan(GetSimplifiedTree(original.GetSubtree(0)), GetSimplifiedTree(original.GetSubtree(1)));
361    }
362    private ISymbolicExpressionTreeNode SimplifyIfThenElse(ISymbolicExpressionTreeNode original) {
363      return MakeIfThenElse(GetSimplifiedTree(original.GetSubtree(0)), GetSimplifiedTree(original.GetSubtree(1)), GetSimplifiedTree(original.GetSubtree(2)));
364    }
365    private ISymbolicExpressionTreeNode SimplifyTangent(ISymbolicExpressionTreeNode original) {
366      return MakeTangent(GetSimplifiedTree(original.GetSubtree(0)));
367    }
368    private ISymbolicExpressionTreeNode SimplifyCosine(ISymbolicExpressionTreeNode original) {
369      return MakeCosine(GetSimplifiedTree(original.GetSubtree(0)));
370    }
371    private ISymbolicExpressionTreeNode SimplifySine(ISymbolicExpressionTreeNode original) {
372      return MakeSine(GetSimplifiedTree(original.GetSubtree(0)));
373    }
374    private ISymbolicExpressionTreeNode SimplifyExp(ISymbolicExpressionTreeNode original) {
375      return MakeExp(GetSimplifiedTree(original.GetSubtree(0)));
376    }
377    private ISymbolicExpressionTreeNode SimplifySquare(ISymbolicExpressionTreeNode original) {
378      return MakeSquare(GetSimplifiedTree(original.GetSubtree(0)));
379    }
380    private ISymbolicExpressionTreeNode SimplifySquareRoot(ISymbolicExpressionTreeNode original) {
381      return MakeSquareRoot(GetSimplifiedTree(original.GetSubtree(0)));
382    }
383
384    private ISymbolicExpressionTreeNode SimplifyLog(ISymbolicExpressionTreeNode original) {
385      return MakeLog(GetSimplifiedTree(original.GetSubtree(0)));
386    }
387    private ISymbolicExpressionTreeNode SimplifyRoot(ISymbolicExpressionTreeNode original) {
388      return MakeRoot(GetSimplifiedTree(original.GetSubtree(0)), GetSimplifiedTree(original.GetSubtree(1)));
389    }
390
391    private ISymbolicExpressionTreeNode SimplifyPower(ISymbolicExpressionTreeNode original) {
392      return MakePower(GetSimplifiedTree(original.GetSubtree(0)), GetSimplifiedTree(original.GetSubtree(1)));
393    }
394    private ISymbolicExpressionTreeNode SimplifyTimeLag(ISymbolicExpressionTreeNode original) {
395      var laggedTreeNode = original as ILaggedTreeNode;
396      var simplifiedSubtree = GetSimplifiedTree(original.GetSubtree(0));
397      if (!ContainsVariableCondition(simplifiedSubtree)) {
398        return AddLagToDynamicNodes(simplifiedSubtree, laggedTreeNode.Lag);
399      } else {
400        return MakeTimeLag(simplifiedSubtree, laggedTreeNode.Lag);
401      }
402    }
403    private ISymbolicExpressionTreeNode SimplifyIntegral(ISymbolicExpressionTreeNode original) {
404      var laggedTreeNode = original as ILaggedTreeNode;
405      var simplifiedSubtree = GetSimplifiedTree(original.GetSubtree(0));
406      if (IsConstant(simplifiedSubtree)) {
407        return GetSimplifiedTree(MakeProduct(simplifiedSubtree, MakeConstant(-laggedTreeNode.Lag)));
408      } else {
409        return MakeIntegral(simplifiedSubtree, laggedTreeNode.Lag);
410      }
411    }
412
413    #endregion
414
415    #region low level tree restructuring
416    private ISymbolicExpressionTreeNode MakeTimeLag(ISymbolicExpressionTreeNode subtree, int lag) {
417      if (lag == 0) return subtree;
418      if (IsConstant(subtree)) return subtree;
419      var lagNode = (LaggedTreeNode)timeLagSymbol.CreateTreeNode();
420      lagNode.Lag = lag;
421      lagNode.AddSubtree(subtree);
422      return lagNode;
423    }
424
425    private ISymbolicExpressionTreeNode MakeIntegral(ISymbolicExpressionTreeNode subtree, int lag) {
426      if (lag == 0) return subtree;
427      else if (lag == -1 || lag == 1) {
428        return MakeSum(subtree, AddLagToDynamicNodes((ISymbolicExpressionTreeNode)subtree.Clone(), lag));
429      } else {
430        var node = (LaggedTreeNode)integralSymbol.CreateTreeNode();
431        node.Lag = lag;
432        node.AddSubtree(subtree);
433        return node;
434      }
435    }
436
437    private ISymbolicExpressionTreeNode MakeNot(ISymbolicExpressionTreeNode t) {
438      if (IsConstant(t)) {
439        var constNode = t as ConstantTreeNode;
440        if (constNode.Value > 0) return MakeConstant(-1.0);
441        else return MakeConstant(1.0);
442      } else if (IsNot(t)) {
443        return t.GetSubtree(0);
444      } else if (!IsBoolean(t)) {
445        var gtNode = gtSymbol.CreateTreeNode();
446        gtNode.AddSubtree(t); gtNode.AddSubtree(MakeConstant(0.0));
447        var notNode = notSymbol.CreateTreeNode();
448        notNode.AddSubtree(gtNode);
449        return notNode;
450      } else {
451        var notNode = notSymbol.CreateTreeNode();
452        notNode.AddSubtree(t);
453        return notNode;
454      }
455    }
456
457    private ISymbolicExpressionTreeNode MakeOr(ISymbolicExpressionTreeNode a, ISymbolicExpressionTreeNode b) {
458      if (IsConstant(a) && IsConstant(b)) {
459        var constA = a as ConstantTreeNode;
460        var constB = b as ConstantTreeNode;
461        if (constA.Value > 0.0 || constB.Value > 0.0) {
462          return MakeConstant(1.0);
463        } else {
464          return MakeConstant(-1.0);
465        }
466      } else if (IsConstant(a)) {
467        return MakeOr(b, a);
468      } else if (IsConstant(b)) {
469        var constT = b as ConstantTreeNode;
470        if (constT.Value > 0.0) {
471          // boolean expression is necessarily true
472          return MakeConstant(1.0);
473        } else {
474          // the constant value has no effect on the result of the boolean condition so we can drop the constant term
475          var orNode = orSymbol.CreateTreeNode();
476          orNode.AddSubtree(a);
477          return orNode;
478        }
479      } else {
480        var orNode = orSymbol.CreateTreeNode();
481        orNode.AddSubtree(a);
482        orNode.AddSubtree(b);
483        return orNode;
484      }
485    }
486    private ISymbolicExpressionTreeNode MakeAnd(ISymbolicExpressionTreeNode a, ISymbolicExpressionTreeNode b) {
487      if (IsConstant(a) && IsConstant(b)) {
488        var constA = a as ConstantTreeNode;
489        var constB = b as ConstantTreeNode;
490        if (constA.Value > 0.0 && constB.Value > 0.0) {
491          return MakeConstant(1.0);
492        } else {
493          return MakeConstant(-1.0);
494        }
495      } else if (IsConstant(a)) {
496        return MakeAnd(b, a);
497      } else if (IsConstant(b)) {
498        var constB = b as ConstantTreeNode;
499        if (constB.Value > 0.0) {
500          // the constant value has no effect on the result of the boolean condition so we can drop the constant term
501          var andNode = andSymbol.CreateTreeNode();
502          andNode.AddSubtree(a);
503          return andNode;
504        } else {
505          // boolean expression is necessarily false
506          return MakeConstant(-1.0);
507        }
508      } else {
509        var andNode = andSymbol.CreateTreeNode();
510        andNode.AddSubtree(a);
511        andNode.AddSubtree(b);
512        return andNode;
513      }
514    }
515    private ISymbolicExpressionTreeNode MakeLessThan(ISymbolicExpressionTreeNode leftSide, ISymbolicExpressionTreeNode rightSide) {
516      if (IsConstant(leftSide) && IsConstant(rightSide)) {
517        var lsConst = leftSide as ConstantTreeNode;
518        var rsConst = rightSide as ConstantTreeNode;
519        if (lsConst.Value < rsConst.Value) return MakeConstant(1.0);
520        else return MakeConstant(-1.0);
521      } else {
522        var ltNode = ltSymbol.CreateTreeNode();
523        ltNode.AddSubtree(leftSide);
524        ltNode.AddSubtree(rightSide);
525        return ltNode;
526      }
527    }
528    private ISymbolicExpressionTreeNode MakeGreaterThan(ISymbolicExpressionTreeNode leftSide, ISymbolicExpressionTreeNode rightSide) {
529      if (IsConstant(leftSide) && IsConstant(rightSide)) {
530        var lsConst = leftSide as ConstantTreeNode;
531        var rsConst = rightSide as ConstantTreeNode;
532        if (lsConst.Value > rsConst.Value) return MakeConstant(1.0);
533        else return MakeConstant(-1.0);
534      } else {
535        var gtNode = gtSymbol.CreateTreeNode();
536        gtNode.AddSubtree(leftSide);
537        gtNode.AddSubtree(rightSide);
538        return gtNode;
539      }
540    }
541    private ISymbolicExpressionTreeNode MakeIfThenElse(ISymbolicExpressionTreeNode condition, ISymbolicExpressionTreeNode trueBranch, ISymbolicExpressionTreeNode falseBranch) {
542      if (IsConstant(condition)) {
543        var constT = condition as ConstantTreeNode;
544        if (constT.Value > 0.0) return trueBranch;
545        else return falseBranch;
546      } else {
547        var ifNode = ifThenElseSymbol.CreateTreeNode();
548        if (IsBoolean(condition)) {
549          ifNode.AddSubtree(condition);
550        } else {
551          var gtNode = gtSymbol.CreateTreeNode();
552          gtNode.AddSubtree(condition); gtNode.AddSubtree(MakeConstant(0.0));
553          ifNode.AddSubtree(gtNode);
554        }
555        ifNode.AddSubtree(trueBranch);
556        ifNode.AddSubtree(falseBranch);
557        return ifNode;
558      }
559    }
560
561    private ISymbolicExpressionTreeNode MakeSine(ISymbolicExpressionTreeNode node) {
562      if (IsConstant(node)) {
563        var constT = node as ConstantTreeNode;
564        return MakeConstant(Math.Sin(constT.Value));
565      } else {
566        var sineNode = sineSymbol.CreateTreeNode();
567        sineNode.AddSubtree(node);
568        return sineNode;
569      }
570    }
571    private ISymbolicExpressionTreeNode MakeTangent(ISymbolicExpressionTreeNode node) {
572      if (IsConstant(node)) {
573        var constT = node as ConstantTreeNode;
574        return MakeConstant(Math.Tan(constT.Value));
575      } else {
576        var tanNode = tanSymbol.CreateTreeNode();
577        tanNode.AddSubtree(node);
578        return tanNode;
579      }
580    }
581    private ISymbolicExpressionTreeNode MakeCosine(ISymbolicExpressionTreeNode node) {
582      if (IsConstant(node)) {
583        var constT = node as ConstantTreeNode;
584        return MakeConstant(Math.Cos(constT.Value));
585      } else {
586        var cosNode = cosineSymbol.CreateTreeNode();
587        cosNode.AddSubtree(node);
588        return cosNode;
589      }
590    }
591    private ISymbolicExpressionTreeNode MakeExp(ISymbolicExpressionTreeNode node) {
592      if (IsConstant(node)) {
593        var constT = node as ConstantTreeNode;
594        return MakeConstant(Math.Exp(constT.Value));
595      } else if (IsLog(node)) {
596        return node.GetSubtree(0);
597      } else if (IsAddition(node)) {
598        return node.Subtrees.Select(s => MakeExp(s)).Aggregate((s, t) => MakeProduct(s, t));
599      } else if (IsSubtraction(node)) {
600        return node.Subtrees.Select(s => MakeExp(s)).Aggregate((s, t) => MakeProduct(s, Negate(t)));
601      } else {
602        var expNode = expSymbol.CreateTreeNode();
603        expNode.AddSubtree(node);
604        return expNode;
605      }
606    }
607
608    private ISymbolicExpressionTreeNode MakeSquare(ISymbolicExpressionTreeNode node) {
609      if (IsConstant(node)) {
610        var constT = node as ConstantTreeNode;
611        return MakeConstant(constT.Value * constT.Value);
612      } else if (IsSquareRoot(node)) {
613        return node.GetSubtree(0);
614      } else {
615        var sqrNode = sqrSymbol.CreateTreeNode();
616        sqrNode.AddSubtree(node);
617        return sqrNode;
618      }
619    }
620    private ISymbolicExpressionTreeNode MakeSquareRoot(ISymbolicExpressionTreeNode node) {
621      if (IsConstant(node)) {
622        var constT = node as ConstantTreeNode;
623        return MakeConstant(Math.Sqrt(constT.Value));
624      } else if (IsSquare(node)) {
625        return node.GetSubtree(0);
626      } else {
627        var sqrtNode = sqrtSymbol.CreateTreeNode();
628        sqrtNode.AddSubtree(node);
629        return sqrtNode;
630      }
631    }
632
633    private ISymbolicExpressionTreeNode MakeLog(ISymbolicExpressionTreeNode node) {
634      if (IsConstant(node)) {
635        var constT = node as ConstantTreeNode;
636        return MakeConstant(Math.Log(constT.Value));
637      } else if (IsExp(node)) {
638        return node.GetSubtree(0);
639      } else if (IsSquareRoot(node)) {
640        return MakeFraction(MakeLog(node.GetSubtree(0)), MakeConstant(2.0));
641      } else {
642        var logNode = logSymbol.CreateTreeNode();
643        logNode.AddSubtree(node);
644        return logNode;
645      }
646    }
647    private ISymbolicExpressionTreeNode MakeRoot(ISymbolicExpressionTreeNode a, ISymbolicExpressionTreeNode b) {
648      if (IsConstant(a) && IsConstant(b)) {
649        var constA = a as ConstantTreeNode;
650        var constB = b as ConstantTreeNode;
651        return MakeConstant(Math.Pow(constA.Value, 1.0 / Math.Round(constB.Value)));
652      } else if (IsConstant(b)) {
653        var constB = b as ConstantTreeNode;
654        var constBValue = Math.Round(constB.Value);
655        if (constBValue.IsAlmost(1.0)) {
656          return a;
657        } else if (constBValue.IsAlmost(0.0)) {
658          return MakeConstant(1.0);
659        } else if (constBValue.IsAlmost(-1.0)) {
660          return MakeFraction(MakeConstant(1.0), a);
661        } else if (constBValue < 0) {
662          var rootNode = rootSymbol.CreateTreeNode();
663          rootNode.AddSubtree(a);
664          rootNode.AddSubtree(MakeConstant(-1.0 * constBValue));
665          return MakeFraction(MakeConstant(1.0), rootNode);
666        } else {
667          var rootNode = rootSymbol.CreateTreeNode();
668          rootNode.AddSubtree(a);
669          rootNode.AddSubtree(MakeConstant(constBValue));
670          return rootNode;
671        }
672      } else {
673        var rootNode = rootSymbol.CreateTreeNode();
674        rootNode.AddSubtree(a);
675        rootNode.AddSubtree(b);
676        return rootNode;
677      }
678    }
679    private ISymbolicExpressionTreeNode MakePower(ISymbolicExpressionTreeNode a, ISymbolicExpressionTreeNode b) {
680      if (IsConstant(a) && IsConstant(b)) {
681        var constA = a as ConstantTreeNode;
682        var constB = b as ConstantTreeNode;
683        return MakeConstant(Math.Pow(constA.Value, Math.Round(constB.Value)));
684      } else if (IsConstant(b)) {
685        var constB = b as ConstantTreeNode;
686        double exponent = Math.Round(constB.Value);
687        if (exponent.IsAlmost(0.0)) {
688          return MakeConstant(1.0);
689        } else if (exponent.IsAlmost(1.0)) {
690          return a;
691        } else if (exponent.IsAlmost(-1.0)) {
692          return MakeFraction(MakeConstant(1.0), a);
693        } else if (exponent < 0) {
694          var powNode = powSymbol.CreateTreeNode();
695          powNode.AddSubtree(a);
696          powNode.AddSubtree(MakeConstant(-1.0 * exponent));
697          return MakeFraction(MakeConstant(1.0), powNode);
698        } else {
699          var powNode = powSymbol.CreateTreeNode();
700          powNode.AddSubtree(a);
701          powNode.AddSubtree(MakeConstant(exponent));
702          return powNode;
703        }
704      } else {
705        var powNode = powSymbol.CreateTreeNode();
706        powNode.AddSubtree(a);
707        powNode.AddSubtree(b);
708        return powNode;
709      }
710    }
711
712
713    // MakeFraction, MakeProduct and MakeSum take two already simplified trees and create a new simplified tree
714    private ISymbolicExpressionTreeNode MakeFraction(ISymbolicExpressionTreeNode a, ISymbolicExpressionTreeNode b) {
715      if (IsConstant(a) && IsConstant(b)) {
716        // fold constants
717        return MakeConstant(((ConstantTreeNode)a).Value / ((ConstantTreeNode)b).Value);
718      }
719      if (IsConstant(a) && !((ConstantTreeNode)a).Value.IsAlmost(1.0)) {
720        return MakeFraction(MakeConstant(1.0), MakeProduct(b, Invert(a)));
721      } else if (IsVariable(a) && IsConstant(b)) {
722        // merge constant values into variable weights
723        var constB = ((ConstantTreeNode)b).Value;
724        ((VariableTreeNode)a).Weight /= constB;
725        return a;
726      } else if (IsVariable(a) && IsVariable(b) && AreSameVariable(a, b)) {
727        // cancel variables
728        var aVar = a as VariableTreeNode;
729        var bVar = b as VariableTreeNode;
730        return MakeConstant(aVar.Weight / bVar.Weight);
731      } else if (IsAddition(a) && IsConstant(b)) {
732        return a.Subtrees
733          .Select(x => GetSimplifiedTree(x))
734         .Select(x => MakeFraction(x, b))
735         .Aggregate((c, d) => MakeSum(c, d));
736      } else if (IsMultiplication(a) && IsConstant(b)) {
737        return MakeProduct(a, Invert(b));
738      } else if (IsDivision(a) && IsConstant(b)) {
739        // (a1 / a2) / c => (a1 / (a2 * c))
740        return MakeFraction(a.GetSubtree(0), MakeProduct(a.GetSubtree(1), b));
741      } else if (IsDivision(a) && IsDivision(b)) {
742        // (a1 / a2) / (b1 / b2) =>
743        return MakeFraction(MakeProduct(a.GetSubtree(0), b.GetSubtree(1)), MakeProduct(a.GetSubtree(1), b.GetSubtree(0)));
744      } else if (IsDivision(a)) {
745        // (a1 / a2) / b => (a1 / (a2 * b))
746        return MakeFraction(a.GetSubtree(0), MakeProduct(a.GetSubtree(1), b));
747      } else if (IsDivision(b)) {
748        // a / (b1 / b2) => (a * b2) / b1
749        return MakeFraction(MakeProduct(a, b.GetSubtree(1)), b.GetSubtree(0));
750      } else {
751        var div = divSymbol.CreateTreeNode();
752        div.AddSubtree(a);
753        div.AddSubtree(b);
754        return div;
755      }
756    }
757
758    private ISymbolicExpressionTreeNode MakeSum(ISymbolicExpressionTreeNode a, ISymbolicExpressionTreeNode b) {
759      if (IsConstant(a) && IsConstant(b)) {
760        // fold constants
761        ((ConstantTreeNode)a).Value += ((ConstantTreeNode)b).Value;
762        return a;
763      } else if (IsConstant(a)) {
764        // c + x => x + c
765        // b is not constant => make sure constant is on the right
766        return MakeSum(b, a);
767      } else if (IsConstant(b) && ((ConstantTreeNode)b).Value.IsAlmost(0.0)) {
768        // x + 0 => x
769        return a;
770      } else if (IsAddition(a) && IsAddition(b)) {
771        // merge additions
772        var add = addSymbol.CreateTreeNode();
773        // add all sub trees except for the last
774        for (int i = 0; i < a.Subtrees.Count() - 1; i++) add.AddSubtree(a.GetSubtree(i));
775        for (int i = 0; i < b.Subtrees.Count() - 1; i++) add.AddSubtree(b.GetSubtree(i));
776        if (IsConstant(a.Subtrees.Last()) && IsConstant(b.Subtrees.Last())) {
777          add.AddSubtree(MakeSum(a.Subtrees.Last(), b.Subtrees.Last()));
778        } else if (IsConstant(a.Subtrees.Last())) {
779          add.AddSubtree(b.Subtrees.Last());
780          add.AddSubtree(a.Subtrees.Last());
781        } else {
782          add.AddSubtree(a.Subtrees.Last());
783          add.AddSubtree(b.Subtrees.Last());
784        }
785        MergeVariablesInSum(add);
786        if (add.Subtrees.Count() == 1) {
787          return add.GetSubtree(0);
788        } else {
789          return add;
790        }
791      } else if (IsAddition(b)) {
792        return MakeSum(b, a);
793      } else if (IsAddition(a) && IsConstant(b)) {
794        // a is an addition and b is a constant => append b to a and make sure the constants are merged
795        var add = addSymbol.CreateTreeNode();
796        // add all sub trees except for the last
797        for (int i = 0; i < a.Subtrees.Count() - 1; i++) add.AddSubtree(a.GetSubtree(i));
798        if (IsConstant(a.Subtrees.Last()))
799          add.AddSubtree(MakeSum(a.Subtrees.Last(), b));
800        else {
801          add.AddSubtree(a.Subtrees.Last());
802          add.AddSubtree(b);
803        }
804        return add;
805      } else if (IsAddition(a)) {
806        // a is already an addition => append b
807        var add = addSymbol.CreateTreeNode();
808        add.AddSubtree(b);
809        foreach (var subtree in a.Subtrees) {
810          add.AddSubtree(subtree);
811        }
812        MergeVariablesInSum(add);
813        if (add.Subtrees.Count() == 1) {
814          return add.GetSubtree(0);
815        } else {
816          return add;
817        }
818      } else {
819        var add = addSymbol.CreateTreeNode();
820        add.AddSubtree(a);
821        add.AddSubtree(b);
822        MergeVariablesInSum(add);
823        if (add.Subtrees.Count() == 1) {
824          return add.GetSubtree(0);
825        } else {
826          return add;
827        }
828      }
829    }
830
831    // makes sure variable symbols in sums are combined
832    // possible improvement: combine sums of products where the products only reference the same variable
833    private void MergeVariablesInSum(ISymbolicExpressionTreeNode sum) {
834      var subtrees = new List<ISymbolicExpressionTreeNode>(sum.Subtrees);
835      while (sum.Subtrees.Any()) sum.RemoveSubtree(0);
836      var groupedVarNodes = from node in subtrees.OfType<VariableTreeNode>()
837                            let lag = (node is LaggedVariableTreeNode) ? ((LaggedVariableTreeNode)node).Lag : 0
838                            group node by node.VariableName + lag into g
839                            select g;
840      var unchangedSubtrees = subtrees.Where(t => !(t is VariableTreeNode));
841
842      foreach (var variableNodeGroup in groupedVarNodes) {
843        var weightSum = variableNodeGroup.Select(t => t.Weight).Sum();
844        var representative = variableNodeGroup.First();
845        representative.Weight = weightSum;
846        sum.AddSubtree(representative);
847      }
848      foreach (var unchangedSubtree in unchangedSubtrees)
849        sum.AddSubtree(unchangedSubtree);
850    }
851
852
853    private ISymbolicExpressionTreeNode MakeProduct(ISymbolicExpressionTreeNode a, ISymbolicExpressionTreeNode b) {
854      if (IsConstant(a) && IsConstant(b)) {
855        // fold constants
856        ((ConstantTreeNode)a).Value *= ((ConstantTreeNode)b).Value;
857        return a;
858      } else if (IsConstant(a)) {
859        // a * $ => $ * a
860        return MakeProduct(b, a);
861      } else if (IsConstant(b) && ((ConstantTreeNode)b).Value.IsAlmost(1.0)) {
862        // $ * 1.0 => $
863        return a;
864      } else if (IsConstant(b) && IsVariable(a)) {
865        // multiply constants into variables weights
866        ((VariableTreeNode)a).Weight *= ((ConstantTreeNode)b).Value;
867        return a;
868      } else if (IsConstant(b) && IsAddition(a)) {
869        // multiply constants into additions
870        return a.Subtrees.Select(x => MakeProduct(x, b)).Aggregate((c, d) => MakeSum(c, d));
871      } else if (IsDivision(a) && IsDivision(b)) {
872        // (a1 / a2) * (b1 / b2) => (a1 * b1) / (a2 * b2)
873        return MakeFraction(MakeProduct(a.GetSubtree(0), b.GetSubtree(0)), MakeProduct(a.GetSubtree(1), b.GetSubtree(1)));
874      } else if (IsDivision(a)) {
875        // (a1 / a2) * b => (a1 * b) / a2
876        return MakeFraction(MakeProduct(a.GetSubtree(0), b), a.GetSubtree(1));
877      } else if (IsDivision(b)) {
878        // a * (b1 / b2) => (b1 * a) / b2
879        return MakeFraction(MakeProduct(b.GetSubtree(0), a), b.GetSubtree(1));
880      } else if (IsMultiplication(a) && IsMultiplication(b)) {
881        // merge multiplications (make sure constants are merged)
882        var mul = mulSymbol.CreateTreeNode();
883        for (int i = 0; i < a.Subtrees.Count(); i++) mul.AddSubtree(a.GetSubtree(i));
884        for (int i = 0; i < b.Subtrees.Count(); i++) mul.AddSubtree(b.GetSubtree(i));
885        MergeVariablesAndConstantsInProduct(mul);
886        return mul;
887      } else if (IsMultiplication(b)) {
888        return MakeProduct(b, a);
889      } else if (IsMultiplication(a)) {
890        // a is already an multiplication => append b
891        a.AddSubtree(b);
892        MergeVariablesAndConstantsInProduct(a);
893        return a;
894      } else {
895        var mul = mulSymbol.CreateTreeNode();
896        mul.AddSubtree(a);
897        mul.AddSubtree(b);
898        MergeVariablesAndConstantsInProduct(mul);
899        return mul;
900      }
901    }
902    #endregion
903
904
905    #region helper functions
906    private bool ContainsVariableCondition(ISymbolicExpressionTreeNode node) {
907      if (node.Symbol is VariableCondition) return true;
908      foreach (var subtree in node.Subtrees)
909        if (ContainsVariableCondition(subtree)) return true;
910      return false;
911    }
912
913    private ISymbolicExpressionTreeNode AddLagToDynamicNodes(ISymbolicExpressionTreeNode node, int lag) {
914      var laggedTreeNode = node as ILaggedTreeNode;
915      var variableNode = node as VariableTreeNode;
916      var variableConditionNode = node as VariableConditionTreeNode;
917      if (laggedTreeNode != null)
918        laggedTreeNode.Lag += lag;
919      else if (variableNode != null) {
920        var laggedVariableNode = (LaggedVariableTreeNode)laggedVariableSymbol.CreateTreeNode();
921        laggedVariableNode.Lag = lag;
922        laggedVariableNode.VariableName = variableNode.VariableName;
923        return laggedVariableNode;
924      } else if (variableConditionNode != null) {
925        throw new NotSupportedException("Removal of time lags around variable condition symbols is not allowed.");
926      }
927      var subtrees = new List<ISymbolicExpressionTreeNode>(node.Subtrees);
928      while (node.SubtreeCount > 0) node.RemoveSubtree(0);
929      foreach (var subtree in subtrees) {
930        node.AddSubtree(AddLagToDynamicNodes(subtree, lag));
931      }
932      return node;
933    }
934
935    private bool AreSameVariable(ISymbolicExpressionTreeNode a, ISymbolicExpressionTreeNode b) {
936      var aLaggedVar = a as LaggedVariableTreeNode;
937      var bLaggedVar = b as LaggedVariableTreeNode;
938      if (aLaggedVar != null && bLaggedVar != null) {
939        return aLaggedVar.VariableName == bLaggedVar.VariableName &&
940          aLaggedVar.Lag == bLaggedVar.Lag;
941      }
942      var aVar = a as VariableTreeNode;
943      var bVar = b as VariableTreeNode;
944      if (aVar != null && bVar != null) {
945        return aVar.VariableName == bVar.VariableName;
946      }
947      return false;
948    }
949
950    // helper to combine the constant factors in products and to combine variables (powers of 2, 3...)
951    private void MergeVariablesAndConstantsInProduct(ISymbolicExpressionTreeNode prod) {
952      var subtrees = new List<ISymbolicExpressionTreeNode>(prod.Subtrees);
953      while (prod.Subtrees.Any()) prod.RemoveSubtree(0);
954      var groupedVarNodes = from node in subtrees.OfType<VariableTreeNode>()
955                            let lag = (node is LaggedVariableTreeNode) ? ((LaggedVariableTreeNode)node).Lag : 0
956                            group node by node.VariableName + lag into g
957                            orderby g.Count()
958                            select g;
959      var constantProduct = (from node in subtrees.OfType<VariableTreeNode>()
960                             select node.Weight)
961                            .Concat(from node in subtrees.OfType<ConstantTreeNode>()
962                                    select node.Value)
963                            .DefaultIfEmpty(1.0)
964                            .Aggregate((c1, c2) => c1 * c2);
965
966      var unchangedSubtrees = from tree in subtrees
967                              where !(tree is VariableTreeNode)
968                              where !(tree is ConstantTreeNode)
969                              select tree;
970
971      foreach (var variableNodeGroup in groupedVarNodes) {
972        var representative = variableNodeGroup.First();
973        representative.Weight = 1.0;
974        if (variableNodeGroup.Count() > 1) {
975          var poly = mulSymbol.CreateTreeNode();
976          for (int p = 0; p < variableNodeGroup.Count(); p++) {
977            poly.AddSubtree((ISymbolicExpressionTreeNode)representative.Clone());
978          }
979          prod.AddSubtree(poly);
980        } else {
981          prod.AddSubtree(representative);
982        }
983      }
984
985      foreach (var unchangedSubtree in unchangedSubtrees)
986        prod.AddSubtree(unchangedSubtree);
987
988      if (!constantProduct.IsAlmost(1.0)) {
989        prod.AddSubtree(MakeConstant(constantProduct));
990      }
991    }
992
993
994    /// <summary>
995    /// x => x * -1
996    /// Doesn't create new trees and manipulates x
997    /// </summary>
998    /// <param name="x"></param>
999    /// <returns>-x</returns>
1000    private ISymbolicExpressionTreeNode Negate(ISymbolicExpressionTreeNode x) {
1001      if (IsConstant(x)) {
1002        ((ConstantTreeNode)x).Value *= -1;
1003      } else if (IsVariable(x)) {
1004        var variableTree = (VariableTreeNode)x;
1005        variableTree.Weight *= -1.0;
1006      } else if (IsAddition(x)) {
1007        // (x0 + x1 + .. + xn) * -1 => (-x0 + -x1 + .. + -xn)       
1008        var subtrees = new List<ISymbolicExpressionTreeNode>(x.Subtrees);
1009        while (x.Subtrees.Any()) x.RemoveSubtree(0);
1010        foreach (var subtree in subtrees) {
1011          x.AddSubtree(Negate(subtree));
1012        }
1013      } else if (IsMultiplication(x) || IsDivision(x)) {
1014        // x0 * x1 * .. * xn * -1 => x0 * x1 * .. * -xn
1015        var lastSubTree = x.Subtrees.Last();
1016        x.RemoveSubtree(x.SubtreeCount - 1);
1017        x.AddSubtree(Negate(lastSubTree)); // last is maybe a constant, prefer to negate the constant
1018      } else {
1019        // any other function
1020        return MakeProduct(x, MakeConstant(-1));
1021      }
1022      return x;
1023    }
1024
1025    /// <summary>
1026    /// x => 1/x
1027    /// Doesn't create new trees and manipulates x
1028    /// </summary>
1029    /// <param name="x"></param>
1030    /// <returns></returns>
1031    private ISymbolicExpressionTreeNode Invert(ISymbolicExpressionTreeNode x) {
1032      if (IsConstant(x)) {
1033        return MakeConstant(1.0 / ((ConstantTreeNode)x).Value);
1034      } else if (IsDivision(x)) {
1035        return MakeFraction(x.GetSubtree(1), x.GetSubtree(0));
1036      } else {
1037        // any other function
1038        return MakeFraction(MakeConstant(1), x);
1039      }
1040    }
1041
1042    private ISymbolicExpressionTreeNode MakeConstant(double value) {
1043      ConstantTreeNode constantTreeNode = (ConstantTreeNode)(constSymbol.CreateTreeNode());
1044      constantTreeNode.Value = value;
1045      return constantTreeNode;
1046    }
1047
1048    private ISymbolicExpressionTreeNode MakeVariable(double weight, string name) {
1049      var tree = (VariableTreeNode)varSymbol.CreateTreeNode();
1050      tree.Weight = weight;
1051      tree.VariableName = name;
1052      return tree;
1053    }
1054    #endregion
1055  }
1056}
Note: See TracBrowser for help on using the repository browser.