source: branches/HeuristicLab.DataAnalysis.Symbolic.LinearInterpreter/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/SymbolicDataAnalysisExpressionTreeSimplifier.cs @ 9732

Last change on this file since 9732 was 9732, checked in by bburlacu, 6 years ago

#2021: Merged trunk changes for HeuristicLab.Encodings.SymbolicExpressionTreeEncoding and HeuristicLab.Problems.DataAnalysis.Symbolic. Replaced prefix iteration of nodes in the linear interpretation with breadth iteration for simplified logic and extra performance. Reversed unnecessary changes to other projects.

File size: 43.2 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2013 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 SymbolicDataAnalysisExpressionTreeSimplifier {
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(x => GetSimplifiedTree(x))
290          .Aggregate((a, b) => MakeSum(a, b));
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 simplifiedTrees = original.Subtrees.Select(x => GetSimplifiedTree(x));
302        return
303          MakeProduct(simplifiedTrees.First(), Invert(simplifiedTrees.Skip(1).Aggregate((a, b) => MakeProduct(a, b))));
304      }
305    }
306
307    private ISymbolicExpressionTreeNode SimplifyMultiplication(ISymbolicExpressionTreeNode original) {
308      if (original.Subtrees.Count() == 1) {
309        return GetSimplifiedTree(original.GetSubtree(0));
310      } else {
311        return original.Subtrees
312          .Select(x => GetSimplifiedTree(x))
313          .Aggregate((a, b) => MakeProduct(a, b));
314      }
315    }
316
317    private ISymbolicExpressionTreeNode SimplifySubtraction(ISymbolicExpressionTreeNode original) {
318      if (original.Subtrees.Count() == 1) {
319        return Negate(GetSimplifiedTree(original.GetSubtree(0)));
320      } else {
321        // simplify expressions x0..xn
322        // make addition (x0,-x1..-xn)
323        var simplifiedTrees = original.Subtrees.Select(x => GetSimplifiedTree(x));
324        return simplifiedTrees.Take(1)
325          .Concat(simplifiedTrees.Skip(1).Select(x => Negate(x)))
326          .Aggregate((a, b) => MakeSum(a, b));
327      }
328    }
329
330    private ISymbolicExpressionTreeNode SimplifyAddition(ISymbolicExpressionTreeNode original) {
331      if (original.Subtrees.Count() == 1) {
332        return GetSimplifiedTree(original.GetSubtree(0));
333      } else {
334        // simplify expression x0..xn
335        // make addition (x0..xn)
336        return original.Subtrees
337          .Select(x => GetSimplifiedTree(x))
338          .Aggregate((a, b) => MakeSum(a, b));
339      }
340    }
341
342    private ISymbolicExpressionTreeNode SimplifyNot(ISymbolicExpressionTreeNode original) {
343      return MakeNot(GetSimplifiedTree(original.GetSubtree(0)));
344    }
345    private ISymbolicExpressionTreeNode SimplifyOr(ISymbolicExpressionTreeNode original) {
346      return original.Subtrees
347        .Select(x => GetSimplifiedTree(x))
348        .Aggregate((a, b) => MakeOr(a, b));
349    }
350    private ISymbolicExpressionTreeNode SimplifyAnd(ISymbolicExpressionTreeNode original) {
351      return original.Subtrees
352        .Select(x => GetSimplifiedTree(x))
353        .Aggregate((a, b) => MakeAnd(a, b));
354    }
355    private ISymbolicExpressionTreeNode SimplifyLessThan(ISymbolicExpressionTreeNode original) {
356      return MakeLessThan(GetSimplifiedTree(original.GetSubtree(0)), GetSimplifiedTree(original.GetSubtree(1)));
357    }
358    private ISymbolicExpressionTreeNode SimplifyGreaterThan(ISymbolicExpressionTreeNode original) {
359      return MakeGreaterThan(GetSimplifiedTree(original.GetSubtree(0)), GetSimplifiedTree(original.GetSubtree(1)));
360    }
361    private ISymbolicExpressionTreeNode SimplifyIfThenElse(ISymbolicExpressionTreeNode original) {
362      return MakeIfThenElse(GetSimplifiedTree(original.GetSubtree(0)), GetSimplifiedTree(original.GetSubtree(1)), GetSimplifiedTree(original.GetSubtree(2)));
363    }
364    private ISymbolicExpressionTreeNode SimplifyTangent(ISymbolicExpressionTreeNode original) {
365      return MakeTangent(GetSimplifiedTree(original.GetSubtree(0)));
366    }
367    private ISymbolicExpressionTreeNode SimplifyCosine(ISymbolicExpressionTreeNode original) {
368      return MakeCosine(GetSimplifiedTree(original.GetSubtree(0)));
369    }
370    private ISymbolicExpressionTreeNode SimplifySine(ISymbolicExpressionTreeNode original) {
371      return MakeSine(GetSimplifiedTree(original.GetSubtree(0)));
372    }
373    private ISymbolicExpressionTreeNode SimplifyExp(ISymbolicExpressionTreeNode original) {
374      return MakeExp(GetSimplifiedTree(original.GetSubtree(0)));
375    }
376    private ISymbolicExpressionTreeNode SimplifySquare(ISymbolicExpressionTreeNode original) {
377      return MakeSquare(GetSimplifiedTree(original.GetSubtree(0)));
378    }
379    private ISymbolicExpressionTreeNode SimplifySquareRoot(ISymbolicExpressionTreeNode original) {
380      return MakeSquareRoot(GetSimplifiedTree(original.GetSubtree(0)));
381    }
382
383    private ISymbolicExpressionTreeNode SimplifyLog(ISymbolicExpressionTreeNode original) {
384      return MakeLog(GetSimplifiedTree(original.GetSubtree(0)));
385    }
386    private ISymbolicExpressionTreeNode SimplifyRoot(ISymbolicExpressionTreeNode original) {
387      return MakeRoot(GetSimplifiedTree(original.GetSubtree(0)), GetSimplifiedTree(original.GetSubtree(1)));
388    }
389
390    private ISymbolicExpressionTreeNode SimplifyPower(ISymbolicExpressionTreeNode original) {
391      return MakePower(GetSimplifiedTree(original.GetSubtree(0)), GetSimplifiedTree(original.GetSubtree(1)));
392    }
393    private ISymbolicExpressionTreeNode SimplifyTimeLag(ISymbolicExpressionTreeNode original) {
394      var laggedTreeNode = original as ILaggedTreeNode;
395      var simplifiedSubtree = GetSimplifiedTree(original.GetSubtree(0));
396      if (!ContainsVariableCondition(simplifiedSubtree)) {
397        return AddLagToDynamicNodes(simplifiedSubtree, laggedTreeNode.Lag);
398      } else {
399        return MakeTimeLag(simplifiedSubtree, laggedTreeNode.Lag);
400      }
401    }
402    private ISymbolicExpressionTreeNode SimplifyIntegral(ISymbolicExpressionTreeNode original) {
403      var laggedTreeNode = original as ILaggedTreeNode;
404      var simplifiedSubtree = GetSimplifiedTree(original.GetSubtree(0));
405      if (IsConstant(simplifiedSubtree)) {
406        return GetSimplifiedTree(MakeProduct(simplifiedSubtree, MakeConstant(-laggedTreeNode.Lag)));
407      } else {
408        return MakeIntegral(simplifiedSubtree, laggedTreeNode.Lag);
409      }
410    }
411
412    #endregion
413
414    #region low level tree restructuring
415    private ISymbolicExpressionTreeNode MakeTimeLag(ISymbolicExpressionTreeNode subtree, int lag) {
416      if (lag == 0) return subtree;
417      if (IsConstant(subtree)) return subtree;
418      var lagNode = (LaggedTreeNode)timeLagSymbol.CreateTreeNode();
419      lagNode.Lag = lag;
420      lagNode.AddSubtree(subtree);
421      return lagNode;
422    }
423
424    private ISymbolicExpressionTreeNode MakeIntegral(ISymbolicExpressionTreeNode subtree, int lag) {
425      if (lag == 0) return subtree;
426      else if (lag == -1 || lag == 1) {
427        return MakeSum(subtree, AddLagToDynamicNodes((ISymbolicExpressionTreeNode)subtree.Clone(), lag));
428      } else {
429        var node = (LaggedTreeNode)integralSymbol.CreateTreeNode();
430        node.Lag = lag;
431        node.AddSubtree(subtree);
432        return node;
433      }
434    }
435
436    private ISymbolicExpressionTreeNode MakeNot(ISymbolicExpressionTreeNode t) {
437      if (IsConstant(t)) {
438        var constNode = t as ConstantTreeNode;
439        if (constNode.Value > 0) return MakeConstant(-1.0);
440        else return MakeConstant(1.0);
441      } else if (IsNot(t)) {
442        return t.GetSubtree(0);
443      } else if (!IsBoolean(t)) {
444        var gtNode = gtSymbol.CreateTreeNode();
445        gtNode.AddSubtree(t); gtNode.AddSubtree(MakeConstant(0.0));
446        var notNode = notSymbol.CreateTreeNode();
447        notNode.AddSubtree(gtNode);
448        return notNode;
449      } else {
450        var notNode = notSymbol.CreateTreeNode();
451        notNode.AddSubtree(t);
452        return notNode;
453      }
454    }
455
456    private ISymbolicExpressionTreeNode MakeOr(ISymbolicExpressionTreeNode a, ISymbolicExpressionTreeNode b) {
457      if (IsConstant(a) && IsConstant(b)) {
458        var constA = a as ConstantTreeNode;
459        var constB = b as ConstantTreeNode;
460        if (constA.Value > 0.0 || constB.Value > 0.0) {
461          return MakeConstant(1.0);
462        } else {
463          return MakeConstant(-1.0);
464        }
465      } else if (IsConstant(a)) {
466        return MakeOr(b, a);
467      } else if (IsConstant(b)) {
468        var constT = b as ConstantTreeNode;
469        if (constT.Value > 0.0) {
470          // boolean expression is necessarily true
471          return MakeConstant(1.0);
472        } else {
473          // the constant value has no effect on the result of the boolean condition so we can drop the constant term
474          var orNode = orSymbol.CreateTreeNode();
475          orNode.AddSubtree(a);
476          return orNode;
477        }
478      } else {
479        var orNode = orSymbol.CreateTreeNode();
480        orNode.AddSubtree(a);
481        orNode.AddSubtree(b);
482        return orNode;
483      }
484    }
485    private ISymbolicExpressionTreeNode MakeAnd(ISymbolicExpressionTreeNode a, ISymbolicExpressionTreeNode b) {
486      if (IsConstant(a) && IsConstant(b)) {
487        var constA = a as ConstantTreeNode;
488        var constB = b as ConstantTreeNode;
489        if (constA.Value > 0.0 && constB.Value > 0.0) {
490          return MakeConstant(1.0);
491        } else {
492          return MakeConstant(-1.0);
493        }
494      } else if (IsConstant(a)) {
495        return MakeAnd(b, a);
496      } else if (IsConstant(b)) {
497        var constB = b as ConstantTreeNode;
498        if (constB.Value > 0.0) {
499          // the constant value has no effect on the result of the boolean condition so we can drop the constant term
500          var andNode = andSymbol.CreateTreeNode();
501          andNode.AddSubtree(a);
502          return andNode;
503        } else {
504          // boolean expression is necessarily false
505          return MakeConstant(-1.0);
506        }
507      } else {
508        var andNode = andSymbol.CreateTreeNode();
509        andNode.AddSubtree(a);
510        andNode.AddSubtree(b);
511        return andNode;
512      }
513    }
514    private ISymbolicExpressionTreeNode MakeLessThan(ISymbolicExpressionTreeNode leftSide, ISymbolicExpressionTreeNode rightSide) {
515      if (IsConstant(leftSide) && IsConstant(rightSide)) {
516        var lsConst = leftSide as ConstantTreeNode;
517        var rsConst = rightSide as ConstantTreeNode;
518        if (lsConst.Value < rsConst.Value) return MakeConstant(1.0);
519        else return MakeConstant(-1.0);
520      } else {
521        var ltNode = ltSymbol.CreateTreeNode();
522        ltNode.AddSubtree(leftSide);
523        ltNode.AddSubtree(rightSide);
524        return ltNode;
525      }
526    }
527    private ISymbolicExpressionTreeNode MakeGreaterThan(ISymbolicExpressionTreeNode leftSide, ISymbolicExpressionTreeNode rightSide) {
528      if (IsConstant(leftSide) && IsConstant(rightSide)) {
529        var lsConst = leftSide as ConstantTreeNode;
530        var rsConst = rightSide as ConstantTreeNode;
531        if (lsConst.Value > rsConst.Value) return MakeConstant(1.0);
532        else return MakeConstant(-1.0);
533      } else {
534        var gtNode = gtSymbol.CreateTreeNode();
535        gtNode.AddSubtree(leftSide);
536        gtNode.AddSubtree(rightSide);
537        return gtNode;
538      }
539    }
540    private ISymbolicExpressionTreeNode MakeIfThenElse(ISymbolicExpressionTreeNode condition, ISymbolicExpressionTreeNode trueBranch, ISymbolicExpressionTreeNode falseBranch) {
541      if (IsConstant(condition)) {
542        var constT = condition as ConstantTreeNode;
543        if (constT.Value > 0.0) return trueBranch;
544        else return falseBranch;
545      } else {
546        var ifNode = ifThenElseSymbol.CreateTreeNode();
547        if (IsBoolean(condition)) {
548          ifNode.AddSubtree(condition);
549        } else {
550          var gtNode = gtSymbol.CreateTreeNode();
551          gtNode.AddSubtree(condition); gtNode.AddSubtree(MakeConstant(0.0));
552          ifNode.AddSubtree(gtNode);
553        }
554        ifNode.AddSubtree(trueBranch);
555        ifNode.AddSubtree(falseBranch);
556        return ifNode;
557      }
558    }
559
560    private ISymbolicExpressionTreeNode MakeSine(ISymbolicExpressionTreeNode node) {
561      if (IsConstant(node)) {
562        var constT = node as ConstantTreeNode;
563        return MakeConstant(Math.Sin(constT.Value));
564      } else {
565        var sineNode = sineSymbol.CreateTreeNode();
566        sineNode.AddSubtree(node);
567        return sineNode;
568      }
569    }
570    private ISymbolicExpressionTreeNode MakeTangent(ISymbolicExpressionTreeNode node) {
571      if (IsConstant(node)) {
572        var constT = node as ConstantTreeNode;
573        return MakeConstant(Math.Tan(constT.Value));
574      } else {
575        var tanNode = tanSymbol.CreateTreeNode();
576        tanNode.AddSubtree(node);
577        return tanNode;
578      }
579    }
580    private ISymbolicExpressionTreeNode MakeCosine(ISymbolicExpressionTreeNode node) {
581      if (IsConstant(node)) {
582        var constT = node as ConstantTreeNode;
583        return MakeConstant(Math.Cos(constT.Value));
584      } else {
585        var cosNode = cosineSymbol.CreateTreeNode();
586        cosNode.AddSubtree(node);
587        return cosNode;
588      }
589    }
590    private ISymbolicExpressionTreeNode MakeExp(ISymbolicExpressionTreeNode node) {
591      if (IsConstant(node)) {
592        var constT = node as ConstantTreeNode;
593        return MakeConstant(Math.Exp(constT.Value));
594      } else if (IsLog(node)) {
595        return node.GetSubtree(0);
596      } else if (IsAddition(node)) {
597        return node.Subtrees.Select(s => MakeExp(s)).Aggregate((s, t) => MakeProduct(s, t));
598      } else if (IsSubtraction(node)) {
599        return node.Subtrees.Select(s => MakeExp(s)).Aggregate((s, t) => MakeProduct(s, Negate(t)));
600      } else {
601        var expNode = expSymbol.CreateTreeNode();
602        expNode.AddSubtree(node);
603        return expNode;
604      }
605    }
606
607    private ISymbolicExpressionTreeNode MakeSquare(ISymbolicExpressionTreeNode node) {
608      if (IsConstant(node)) {
609        var constT = node as ConstantTreeNode;
610        return MakeConstant(constT.Value * constT.Value);
611      } else if (IsSquareRoot(node)) {
612        return node.GetSubtree(0);
613      } else {
614        var sqrNode = sqrSymbol.CreateTreeNode();
615        sqrNode.AddSubtree(node);
616        return sqrNode;
617      }
618    }
619    private ISymbolicExpressionTreeNode MakeSquareRoot(ISymbolicExpressionTreeNode node) {
620      if (IsConstant(node)) {
621        var constT = node as ConstantTreeNode;
622        return MakeConstant(Math.Sqrt(constT.Value));
623      } else if (IsSquare(node)) {
624        return node.GetSubtree(0);
625      } else {
626        var sqrtNode = sqrtSymbol.CreateTreeNode();
627        sqrtNode.AddSubtree(node);
628        return sqrtNode;
629      }
630    }
631
632    private ISymbolicExpressionTreeNode MakeLog(ISymbolicExpressionTreeNode node) {
633      if (IsConstant(node)) {
634        var constT = node as ConstantTreeNode;
635        return MakeConstant(Math.Log(constT.Value));
636      } else if (IsExp(node)) {
637        return node.GetSubtree(0);
638      } else if (IsSquareRoot(node)) {
639        return MakeFraction(MakeLog(node.GetSubtree(0)), MakeConstant(2.0));
640      } else {
641        var logNode = logSymbol.CreateTreeNode();
642        logNode.AddSubtree(node);
643        return logNode;
644      }
645    }
646    private ISymbolicExpressionTreeNode MakeRoot(ISymbolicExpressionTreeNode a, ISymbolicExpressionTreeNode b) {
647      if (IsConstant(a) && IsConstant(b)) {
648        var constA = a as ConstantTreeNode;
649        var constB = b as ConstantTreeNode;
650        return MakeConstant(Math.Pow(constA.Value, 1.0 / Math.Round(constB.Value)));
651      } else if (IsConstant(b)) {
652        var constB = b as ConstantTreeNode;
653        var constBValue = Math.Round(constB.Value);
654        if (constBValue.IsAlmost(1.0)) {
655          return a;
656        } else if (constBValue.IsAlmost(0.0)) {
657          return MakeConstant(1.0);
658        } else if (constBValue.IsAlmost(-1.0)) {
659          return MakeFraction(MakeConstant(1.0), a);
660        } else if (constBValue < 0) {
661          var rootNode = rootSymbol.CreateTreeNode();
662          rootNode.AddSubtree(a);
663          rootNode.AddSubtree(MakeConstant(-1.0 * constBValue));
664          return MakeFraction(MakeConstant(1.0), rootNode);
665        } else {
666          var rootNode = rootSymbol.CreateTreeNode();
667          rootNode.AddSubtree(a);
668          rootNode.AddSubtree(MakeConstant(constBValue));
669          return rootNode;
670        }
671      } else {
672        var rootNode = rootSymbol.CreateTreeNode();
673        rootNode.AddSubtree(a);
674        rootNode.AddSubtree(b);
675        return rootNode;
676      }
677    }
678    private ISymbolicExpressionTreeNode MakePower(ISymbolicExpressionTreeNode a, ISymbolicExpressionTreeNode b) {
679      if (IsConstant(a) && IsConstant(b)) {
680        var constA = a as ConstantTreeNode;
681        var constB = b as ConstantTreeNode;
682        return MakeConstant(Math.Pow(constA.Value, Math.Round(constB.Value)));
683      } else if (IsConstant(b)) {
684        var constB = b as ConstantTreeNode;
685        double exponent = Math.Round(constB.Value);
686        if (exponent.IsAlmost(0.0)) {
687          return MakeConstant(1.0);
688        } else if (exponent.IsAlmost(1.0)) {
689          return a;
690        } else if (exponent.IsAlmost(-1.0)) {
691          return MakeFraction(MakeConstant(1.0), a);
692        } else if (exponent < 0) {
693          var powNode = powSymbol.CreateTreeNode();
694          powNode.AddSubtree(a);
695          powNode.AddSubtree(MakeConstant(-1.0 * exponent));
696          return MakeFraction(MakeConstant(1.0), powNode);
697        } else {
698          var powNode = powSymbol.CreateTreeNode();
699          powNode.AddSubtree(a);
700          powNode.AddSubtree(MakeConstant(exponent));
701          return powNode;
702        }
703      } else {
704        var powNode = powSymbol.CreateTreeNode();
705        powNode.AddSubtree(a);
706        powNode.AddSubtree(b);
707        return powNode;
708      }
709    }
710
711
712    // MakeFraction, MakeProduct and MakeSum take two already simplified trees and create a new simplified tree
713    private ISymbolicExpressionTreeNode MakeFraction(ISymbolicExpressionTreeNode a, ISymbolicExpressionTreeNode b) {
714      if (IsConstant(a) && IsConstant(b)) {
715        // fold constants
716        return MakeConstant(((ConstantTreeNode)a).Value / ((ConstantTreeNode)b).Value);
717      } if (IsConstant(a) && !((ConstantTreeNode)a).Value.IsAlmost(1.0)) {
718        return MakeFraction(MakeConstant(1.0), MakeProduct(b, Invert(a)));
719      } else if (IsVariable(a) && IsConstant(b)) {
720        // merge constant values into variable weights
721        var constB = ((ConstantTreeNode)b).Value;
722        ((VariableTreeNode)a).Weight /= constB;
723        return a;
724      } else if (IsVariable(a) && IsVariable(b) && AreSameVariable(a, b)) {
725        // cancel variables
726        var aVar = a as VariableTreeNode;
727        var bVar = b as VariableTreeNode;
728        return MakeConstant(aVar.Weight / bVar.Weight);
729      } else if (IsAddition(a) && IsConstant(b)) {
730        return a.Subtrees
731          .Select(x => GetSimplifiedTree(x))
732         .Select(x => MakeFraction(x, b))
733         .Aggregate((c, d) => MakeSum(c, d));
734      } else if (IsMultiplication(a) && IsConstant(b)) {
735        return MakeProduct(a, Invert(b));
736      } else if (IsDivision(a) && IsConstant(b)) {
737        // (a1 / a2) / c => (a1 / (a2 * c))
738        return MakeFraction(a.GetSubtree(0), MakeProduct(a.GetSubtree(1), b));
739      } else if (IsDivision(a) && IsDivision(b)) {
740        // (a1 / a2) / (b1 / b2) =>
741        return MakeFraction(MakeProduct(a.GetSubtree(0), b.GetSubtree(1)), MakeProduct(a.GetSubtree(1), b.GetSubtree(0)));
742      } else if (IsDivision(a)) {
743        // (a1 / a2) / b => (a1 / (a2 * b))
744        return MakeFraction(a.GetSubtree(0), MakeProduct(a.GetSubtree(1), b));
745      } else if (IsDivision(b)) {
746        // a / (b1 / b2) => (a * b2) / b1
747        return MakeFraction(MakeProduct(a, b.GetSubtree(1)), b.GetSubtree(0));
748      } else {
749        var div = divSymbol.CreateTreeNode();
750        div.AddSubtree(a);
751        div.AddSubtree(b);
752        return div;
753      }
754    }
755
756    private ISymbolicExpressionTreeNode MakeSum(ISymbolicExpressionTreeNode a, ISymbolicExpressionTreeNode b) {
757      if (IsConstant(a) && IsConstant(b)) {
758        // fold constants
759        ((ConstantTreeNode)a).Value += ((ConstantTreeNode)b).Value;
760        return a;
761      } else if (IsConstant(a)) {
762        // c + x => x + c
763        // b is not constant => make sure constant is on the right
764        return MakeSum(b, a);
765      } else if (IsConstant(b) && ((ConstantTreeNode)b).Value.IsAlmost(0.0)) {
766        // x + 0 => x
767        return a;
768      } else if (IsAddition(a) && IsAddition(b)) {
769        // merge additions
770        var add = addSymbol.CreateTreeNode();
771        // add all sub trees except for the last
772        for (int i = 0; i < a.Subtrees.Count() - 1; i++) add.AddSubtree(a.GetSubtree(i));
773        for (int i = 0; i < b.Subtrees.Count() - 1; i++) add.AddSubtree(b.GetSubtree(i));
774        if (IsConstant(a.Subtrees.Last()) && IsConstant(b.Subtrees.Last())) {
775          add.AddSubtree(MakeSum(a.Subtrees.Last(), b.Subtrees.Last()));
776        } else if (IsConstant(a.Subtrees.Last())) {
777          add.AddSubtree(b.Subtrees.Last());
778          add.AddSubtree(a.Subtrees.Last());
779        } else {
780          add.AddSubtree(a.Subtrees.Last());
781          add.AddSubtree(b.Subtrees.Last());
782        }
783        MergeVariablesInSum(add);
784        if (add.Subtrees.Count() == 1) {
785          return add.GetSubtree(0);
786        } else {
787          return add;
788        }
789      } else if (IsAddition(b)) {
790        return MakeSum(b, a);
791      } else if (IsAddition(a) && IsConstant(b)) {
792        // a is an addition and b is a constant => append b to a and make sure the constants are merged
793        var add = addSymbol.CreateTreeNode();
794        // add all sub trees except for the last
795        for (int i = 0; i < a.Subtrees.Count() - 1; i++) add.AddSubtree(a.GetSubtree(i));
796        if (IsConstant(a.Subtrees.Last()))
797          add.AddSubtree(MakeSum(a.Subtrees.Last(), b));
798        else {
799          add.AddSubtree(a.Subtrees.Last());
800          add.AddSubtree(b);
801        }
802        return add;
803      } else if (IsAddition(a)) {
804        // a is already an addition => append b
805        var add = addSymbol.CreateTreeNode();
806        add.AddSubtree(b);
807        foreach (var subtree in a.Subtrees) {
808          add.AddSubtree(subtree);
809        }
810        MergeVariablesInSum(add);
811        if (add.Subtrees.Count() == 1) {
812          return add.GetSubtree(0);
813        } else {
814          return add;
815        }
816      } else {
817        var add = addSymbol.CreateTreeNode();
818        add.AddSubtree(a);
819        add.AddSubtree(b);
820        MergeVariablesInSum(add);
821        if (add.Subtrees.Count() == 1) {
822          return add.GetSubtree(0);
823        } else {
824          return add;
825        }
826      }
827    }
828
829    // makes sure variable symbols in sums are combined
830    // possible improvement: combine sums of products where the products only reference the same variable
831    private void MergeVariablesInSum(ISymbolicExpressionTreeNode sum) {
832      var subtrees = new List<ISymbolicExpressionTreeNode>(sum.Subtrees);
833      while (sum.Subtrees.Count() > 0) sum.RemoveSubtree(0);
834      var groupedVarNodes = from node in subtrees.OfType<VariableTreeNode>()
835                            let lag = (node is LaggedVariableTreeNode) ? ((LaggedVariableTreeNode)node).Lag : 0
836                            group node by node.VariableName + lag into g
837                            select g;
838      var unchangedSubtrees = subtrees.Where(t => !(t is VariableTreeNode));
839
840      foreach (var variableNodeGroup in groupedVarNodes) {
841        var weightSum = variableNodeGroup.Select(t => t.Weight).Sum();
842        var representative = variableNodeGroup.First();
843        representative.Weight = weightSum;
844        sum.AddSubtree(representative);
845      }
846      foreach (var unchangedSubtree in unchangedSubtrees)
847        sum.AddSubtree(unchangedSubtree);
848    }
849
850
851    private ISymbolicExpressionTreeNode MakeProduct(ISymbolicExpressionTreeNode a, ISymbolicExpressionTreeNode b) {
852      if (IsConstant(a) && IsConstant(b)) {
853        // fold constants
854        ((ConstantTreeNode)a).Value *= ((ConstantTreeNode)b).Value;
855        return a;
856      } else if (IsConstant(a)) {
857        // a * $ => $ * a
858        return MakeProduct(b, a);
859      } else if (IsConstant(b) && ((ConstantTreeNode)b).Value.IsAlmost(1.0)) {
860        // $ * 1.0 => $
861        return a;
862      } else if (IsConstant(b) && IsVariable(a)) {
863        // multiply constants into variables weights
864        ((VariableTreeNode)a).Weight *= ((ConstantTreeNode)b).Value;
865        return a;
866      } else if (IsConstant(b) && IsAddition(a)) {
867        // multiply constants into additions
868        return a.Subtrees.Select(x => MakeProduct(x, b)).Aggregate((c, d) => MakeSum(c, d));
869      } else if (IsDivision(a) && IsDivision(b)) {
870        // (a1 / a2) * (b1 / b2) => (a1 * b1) / (a2 * b2)
871        return MakeFraction(MakeProduct(a.GetSubtree(0), b.GetSubtree(0)), MakeProduct(a.GetSubtree(1), b.GetSubtree(1)));
872      } else if (IsDivision(a)) {
873        // (a1 / a2) * b => (a1 * b) / a2
874        return MakeFraction(MakeProduct(a.GetSubtree(0), b), a.GetSubtree(1));
875      } else if (IsDivision(b)) {
876        // a * (b1 / b2) => (b1 * a) / b2
877        return MakeFraction(MakeProduct(b.GetSubtree(0), a), b.GetSubtree(1));
878      } else if (IsMultiplication(a) && IsMultiplication(b)) {
879        // merge multiplications (make sure constants are merged)
880        var mul = mulSymbol.CreateTreeNode();
881        for (int i = 0; i < a.Subtrees.Count(); i++) mul.AddSubtree(a.GetSubtree(i));
882        for (int i = 0; i < b.Subtrees.Count(); i++) mul.AddSubtree(b.GetSubtree(i));
883        MergeVariablesAndConstantsInProduct(mul);
884        return mul;
885      } else if (IsMultiplication(b)) {
886        return MakeProduct(b, a);
887      } else if (IsMultiplication(a)) {
888        // a is already an multiplication => append b
889        a.AddSubtree(b);
890        MergeVariablesAndConstantsInProduct(a);
891        return a;
892      } else {
893        var mul = mulSymbol.CreateTreeNode();
894        mul.AddSubtree(a);
895        mul.AddSubtree(b);
896        MergeVariablesAndConstantsInProduct(mul);
897        return mul;
898      }
899    }
900    #endregion
901
902
903    #region helper functions
904    private bool ContainsVariableCondition(ISymbolicExpressionTreeNode node) {
905      if (node.Symbol is VariableCondition) return true;
906      foreach (var subtree in node.Subtrees)
907        if (ContainsVariableCondition(subtree)) return true;
908      return false;
909    }
910
911    private ISymbolicExpressionTreeNode AddLagToDynamicNodes(ISymbolicExpressionTreeNode node, int lag) {
912      var laggedTreeNode = node as ILaggedTreeNode;
913      var variableNode = node as VariableTreeNode;
914      var variableConditionNode = node as VariableConditionTreeNode;
915      if (laggedTreeNode != null)
916        laggedTreeNode.Lag += lag;
917      else if (variableNode != null) {
918        var laggedVariableNode = (LaggedVariableTreeNode)laggedVariableSymbol.CreateTreeNode();
919        laggedVariableNode.Lag = lag;
920        laggedVariableNode.VariableName = variableNode.VariableName;
921        return laggedVariableNode;
922      } else if (variableConditionNode != null) {
923        throw new NotSupportedException("Removal of time lags around variable condition symbols is not allowed.");
924      }
925      var subtrees = new List<ISymbolicExpressionTreeNode>(node.Subtrees);
926      while (node.SubtreeCount > 0) node.RemoveSubtree(0);
927      foreach (var subtree in subtrees) {
928        node.AddSubtree(AddLagToDynamicNodes(subtree, lag));
929      }
930      return node;
931    }
932
933    private bool AreSameVariable(ISymbolicExpressionTreeNode a, ISymbolicExpressionTreeNode b) {
934      var aLaggedVar = a as LaggedVariableTreeNode;
935      var bLaggedVar = b as LaggedVariableTreeNode;
936      if (aLaggedVar != null && bLaggedVar != null) {
937        return aLaggedVar.VariableName == bLaggedVar.VariableName &&
938          aLaggedVar.Lag == bLaggedVar.Lag;
939      }
940      var aVar = a as VariableTreeNode;
941      var bVar = b as VariableTreeNode;
942      if (aVar != null && bVar != null) {
943        return aVar.VariableName == bVar.VariableName;
944      }
945      return false;
946    }
947
948    // helper to combine the constant factors in products and to combine variables (powers of 2, 3...)
949    private void MergeVariablesAndConstantsInProduct(ISymbolicExpressionTreeNode prod) {
950      var subtrees = new List<ISymbolicExpressionTreeNode>(prod.Subtrees);
951      while (prod.Subtrees.Count() > 0) prod.RemoveSubtree(0);
952      var groupedVarNodes = from node in subtrees.OfType<VariableTreeNode>()
953                            let lag = (node is LaggedVariableTreeNode) ? ((LaggedVariableTreeNode)node).Lag : 0
954                            group node by node.VariableName + lag into g
955                            orderby g.Count()
956                            select g;
957      var constantProduct = (from node in subtrees.OfType<VariableTreeNode>()
958                             select node.Weight)
959                            .Concat(from node in subtrees.OfType<ConstantTreeNode>()
960                                    select node.Value)
961                            .DefaultIfEmpty(1.0)
962                            .Aggregate((c1, c2) => c1 * c2);
963
964      var unchangedSubtrees = from tree in subtrees
965                              where !(tree is VariableTreeNode)
966                              where !(tree is ConstantTreeNode)
967                              select tree;
968
969      foreach (var variableNodeGroup in groupedVarNodes) {
970        var representative = variableNodeGroup.First();
971        representative.Weight = 1.0;
972        if (variableNodeGroup.Count() > 1) {
973          var poly = mulSymbol.CreateTreeNode();
974          for (int p = 0; p < variableNodeGroup.Count(); p++) {
975            poly.AddSubtree((ISymbolicExpressionTreeNode)representative.Clone());
976          }
977          prod.AddSubtree(poly);
978        } else {
979          prod.AddSubtree(representative);
980        }
981      }
982
983      foreach (var unchangedSubtree in unchangedSubtrees)
984        prod.AddSubtree(unchangedSubtree);
985
986      if (!constantProduct.IsAlmost(1.0)) {
987        prod.AddSubtree(MakeConstant(constantProduct));
988      }
989    }
990
991
992    /// <summary>
993    /// x => x * -1
994    /// Doesn't create new trees and manipulates x
995    /// </summary>
996    /// <param name="x"></param>
997    /// <returns>-x</returns>
998    private ISymbolicExpressionTreeNode Negate(ISymbolicExpressionTreeNode x) {
999      if (IsConstant(x)) {
1000        ((ConstantTreeNode)x).Value *= -1;
1001      } else if (IsVariable(x)) {
1002        var variableTree = (VariableTreeNode)x;
1003        variableTree.Weight *= -1.0;
1004      } else if (IsAddition(x)) {
1005        // (x0 + x1 + .. + xn) * -1 => (-x0 + -x1 + .. + -xn)       
1006        List<ISymbolicExpressionTreeNode> subtrees = new List<ISymbolicExpressionTreeNode>(x.Subtrees);
1007        while (x.Subtrees.Count() > 0) x.RemoveSubtree(0);
1008        foreach (var subtree in subtrees) {
1009          x.AddSubtree(Negate(subtree));
1010        }
1011      } else if (IsMultiplication(x) || IsDivision(x)) {
1012        // x0 * x1 * .. * xn * -1 => x0 * x1 * .. * -xn
1013        var lastSubTree = x.Subtrees.Last();
1014        x.RemoveSubtree(x.SubtreeCount - 1);
1015        x.AddSubtree(Negate(lastSubTree)); // last is maybe a constant, prefer to negate the constant
1016      } else {
1017        // any other function
1018        return MakeProduct(x, MakeConstant(-1));
1019      }
1020      return x;
1021    }
1022
1023    /// <summary>
1024    /// x => 1/x
1025    /// Doesn't create new trees and manipulates x
1026    /// </summary>
1027    /// <param name="x"></param>
1028    /// <returns></returns>
1029    private ISymbolicExpressionTreeNode Invert(ISymbolicExpressionTreeNode x) {
1030      if (IsConstant(x)) {
1031        return MakeConstant(1.0 / ((ConstantTreeNode)x).Value);
1032      } else if (IsDivision(x)) {
1033        return MakeFraction(x.GetSubtree(1), x.GetSubtree(0));
1034      } else {
1035        // any other function
1036        return MakeFraction(MakeConstant(1), x);
1037      }
1038    }
1039
1040    private ISymbolicExpressionTreeNode MakeConstant(double value) {
1041      ConstantTreeNode constantTreeNode = (ConstantTreeNode)(constSymbol.CreateTreeNode());
1042      constantTreeNode.Value = value;
1043      return constantTreeNode;
1044    }
1045
1046    private ISymbolicExpressionTreeNode MakeVariable(double weight, string name) {
1047      var tree = (VariableTreeNode)varSymbol.CreateTreeNode();
1048      tree.Weight = weight;
1049      tree.VariableName = name;
1050      return tree;
1051    }
1052    #endregion
1053  }
1054}
Note: See TracBrowser for help on using the repository browser.