source: branches/symbreg-factors-2650/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/SymbolicDataAnalysisExpressionTreeSimplifier.cs @ 14535

Last change on this file since 14535 was 14535, checked in by gkronber, 5 years ago

#2650 worked on simplifier

File size: 55.0 KB
Line 
1#region License Information
2
3/* HeuristicLab
4 * Copyright (C) 2002-2016 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
5 *
6 * This file is part of HeuristicLab.
7 *
8 * HeuristicLab is free software: you can redistribute it and/or modify
9 * it under the terms of the GNU General Public License as published by
10 * the Free Software Foundation, either version 3 of the License, or
11 * (at your option) any later version.
12 *
13 * HeuristicLab is distributed in the hope that it will be useful,
14 * but WITHOUT ANY WARRANTY; without even the implied warranty of
15 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
16 * GNU General Public License for more details.
17 *
18 * You should have received a copy of the GNU General Public License
19 * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
20 */
21
22#endregion
23
24using System;
25using System.Collections.Generic;
26using System.Linq;
27using HeuristicLab.Common;
28using HeuristicLab.Core;
29using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
30
31namespace HeuristicLab.Problems.DataAnalysis.Symbolic {
32  /// <summary>
33  /// Simplifier for symbolic expressions
34  /// </summary>
35  public class SymbolicDataAnalysisExpressionTreeSimplifier {
36    private Addition addSymbol = new Addition();
37    private Multiplication mulSymbol = new Multiplication();
38    private Division divSymbol = new Division();
39    private Constant constSymbol = new Constant();
40    private Variable varSymbol = new Variable();
41    private Logarithm logSymbol = new Logarithm();
42    private Exponential expSymbol = new Exponential();
43    private Root rootSymbol = new Root();
44    private Square sqrSymbol = new Square();
45    private SquareRoot sqrtSymbol = new SquareRoot();
46    private Power powSymbol = new Power();
47    private Sine sineSymbol = new Sine();
48    private Cosine cosineSymbol = new Cosine();
49    private Tangent tanSymbol = new Tangent();
50    private IfThenElse ifThenElseSymbol = new IfThenElse();
51    private And andSymbol = new And();
52    private Or orSymbol = new Or();
53    private Not notSymbol = new Not();
54    private GreaterThan gtSymbol = new GreaterThan();
55    private LessThan ltSymbol = new LessThan();
56    private Integral integralSymbol = new Integral();
57    private LaggedVariable laggedVariableSymbol = new LaggedVariable();
58    private TimeLag timeLagSymbol = new TimeLag();
59
60    public ISymbolicExpressionTree Simplify(ISymbolicExpressionTree originalTree) {
61      var clone = (ISymbolicExpressionTreeNode)originalTree.Root.Clone();
62      // macro expand (initially no argument trees)
63      var macroExpandedTree = MacroExpand(clone, clone.GetSubtree(0), new List<ISymbolicExpressionTreeNode>());
64      ISymbolicExpressionTreeNode rootNode = (new ProgramRootSymbol()).CreateTreeNode();
65      rootNode.AddSubtree(GetSimplifiedTree(macroExpandedTree));
66      return new SymbolicExpressionTree(rootNode);
67    }
68
69    // the argumentTrees list contains already expanded trees used as arguments for invocations
70    private ISymbolicExpressionTreeNode MacroExpand(ISymbolicExpressionTreeNode root, ISymbolicExpressionTreeNode node,
71      IList<ISymbolicExpressionTreeNode> argumentTrees) {
72      List<ISymbolicExpressionTreeNode> subtrees = new List<ISymbolicExpressionTreeNode>(node.Subtrees);
73      while(node.SubtreeCount > 0) node.RemoveSubtree(0);
74      if(node.Symbol is InvokeFunction) {
75        var invokeSym = node.Symbol as InvokeFunction;
76        var defunNode = FindFunctionDefinition(root, invokeSym.FunctionName);
77        var macroExpandedArguments = new List<ISymbolicExpressionTreeNode>();
78        foreach(var subtree in subtrees) {
79          macroExpandedArguments.Add(MacroExpand(root, subtree, argumentTrees));
80        }
81        return MacroExpand(root, defunNode, macroExpandedArguments);
82      } else if(node.Symbol is Argument) {
83        var argSym = node.Symbol as Argument;
84        // return the correct argument sub-tree (already macro-expanded)
85        return (SymbolicExpressionTreeNode)argumentTrees[argSym.ArgumentIndex].Clone();
86      } else {
87        // recursive application
88        foreach(var subtree in subtrees) {
89          node.AddSubtree(MacroExpand(root, subtree, argumentTrees));
90        }
91        return node;
92      }
93    }
94
95    private ISymbolicExpressionTreeNode FindFunctionDefinition(ISymbolicExpressionTreeNode root, string functionName) {
96      foreach(var subtree in root.Subtrees.OfType<DefunTreeNode>()) {
97        if(subtree.FunctionName == functionName) return subtree.GetSubtree(0);
98      }
99
100      throw new ArgumentException("Definition of function " + functionName + " not found.");
101    }
102
103    #region symbol predicates
104
105    // arithmetic
106    private bool IsDivision(ISymbolicExpressionTreeNode node) {
107      return node.Symbol is Division;
108    }
109
110    private bool IsMultiplication(ISymbolicExpressionTreeNode node) {
111      return node.Symbol is Multiplication;
112    }
113
114    private bool IsSubtraction(ISymbolicExpressionTreeNode node) {
115      return node.Symbol is Subtraction;
116    }
117
118    private bool IsAddition(ISymbolicExpressionTreeNode node) {
119      return node.Symbol is Addition;
120    }
121
122    private bool IsAverage(ISymbolicExpressionTreeNode node) {
123      return node.Symbol is Average;
124    }
125
126    // exponential
127    private bool IsLog(ISymbolicExpressionTreeNode node) {
128      return node.Symbol is Logarithm;
129    }
130
131    private bool IsExp(ISymbolicExpressionTreeNode node) {
132      return node.Symbol is Exponential;
133    }
134
135    private bool IsRoot(ISymbolicExpressionTreeNode node) {
136      return node.Symbol is Root;
137    }
138
139    private bool IsSquare(ISymbolicExpressionTreeNode node) {
140      return node.Symbol is Square;
141    }
142
143    private bool IsSquareRoot(ISymbolicExpressionTreeNode node) {
144      return node.Symbol is SquareRoot;
145    }
146
147    private bool IsPower(ISymbolicExpressionTreeNode node) {
148      return node.Symbol is Power;
149    }
150
151    // trigonometric
152    private bool IsSine(ISymbolicExpressionTreeNode node) {
153      return node.Symbol is Sine;
154    }
155
156    private bool IsCosine(ISymbolicExpressionTreeNode node) {
157      return node.Symbol is Cosine;
158    }
159
160    private bool IsTangent(ISymbolicExpressionTreeNode node) {
161      return node.Symbol is Tangent;
162    }
163
164    // boolean
165    private bool IsIfThenElse(ISymbolicExpressionTreeNode node) {
166      return node.Symbol is IfThenElse;
167    }
168
169    private bool IsAnd(ISymbolicExpressionTreeNode node) {
170      return node.Symbol is And;
171    }
172
173    private bool IsOr(ISymbolicExpressionTreeNode node) {
174      return node.Symbol is Or;
175    }
176
177    private bool IsNot(ISymbolicExpressionTreeNode node) {
178      return node.Symbol is Not;
179    }
180
181    // comparison
182    private bool IsGreaterThan(ISymbolicExpressionTreeNode node) {
183      return node.Symbol is GreaterThan;
184    }
185
186    private bool IsLessThan(ISymbolicExpressionTreeNode node) {
187      return node.Symbol is LessThan;
188    }
189
190    private bool IsBoolean(ISymbolicExpressionTreeNode node) {
191      return
192        node.Symbol is GreaterThan ||
193        node.Symbol is LessThan ||
194        node.Symbol is And ||
195        node.Symbol is Or;
196    }
197
198    // terminals
199    private bool IsVariable(ISymbolicExpressionTreeNode node) {
200      return node.Symbol is Variable;
201    }
202
203    private bool IsVariableBase(ISymbolicExpressionTreeNode node) {
204      return node is VariableTreeNodeBase;
205    }
206
207    private bool IsFactor(ISymbolicExpressionTreeNode node) {
208      return node is FactorVariableTreeNode;
209    }
210
211    private bool IsBinFactor(ISymbolicExpressionTreeNode node) {
212      return node is BinaryFactorVariableTreeNode;
213    }
214
215    private bool IsConstant(ISymbolicExpressionTreeNode node) {
216      return node.Symbol is Constant;
217    }
218
219    // dynamic
220    private bool IsTimeLag(ISymbolicExpressionTreeNode node) {
221      return node.Symbol is TimeLag;
222    }
223
224    private bool IsIntegral(ISymbolicExpressionTreeNode node) {
225      return node.Symbol is Integral;
226    }
227
228    #endregion
229
230    /// <summary>
231    /// Creates a new simplified tree
232    /// </summary>
233    /// <param name="original"></param>
234    /// <returns></returns>
235    public ISymbolicExpressionTreeNode GetSimplifiedTree(ISymbolicExpressionTreeNode original) {
236      if(IsConstant(original) || IsVariableBase(original)) {
237        return (ISymbolicExpressionTreeNode)original.Clone();
238      } else if(IsAddition(original)) {
239        return SimplifyAddition(original);
240      } else if(IsSubtraction(original)) {
241        return SimplifySubtraction(original);
242      } else if(IsMultiplication(original)) {
243        return SimplifyMultiplication(original);
244      } else if(IsDivision(original)) {
245        return SimplifyDivision(original);
246      } else if(IsAverage(original)) {
247        return SimplifyAverage(original);
248      } else if(IsLog(original)) {
249        return SimplifyLog(original);
250      } else if(IsExp(original)) {
251        return SimplifyExp(original);
252      } else if(IsSquare(original)) {
253        return SimplifySquare(original);
254      } else if(IsSquareRoot(original)) {
255        return SimplifySquareRoot(original);
256      } else if(IsPower(original)) {
257        return SimplifyPower(original);
258      } else if(IsRoot(original)) {
259        return SimplifyRoot(original);
260      } else if(IsSine(original)) {
261        return SimplifySine(original);
262      } else if(IsCosine(original)) {
263        return SimplifyCosine(original);
264      } else if(IsTangent(original)) {
265        return SimplifyTangent(original);
266      } else if(IsIfThenElse(original)) {
267        return SimplifyIfThenElse(original);
268      } else if(IsGreaterThan(original)) {
269        return SimplifyGreaterThan(original);
270      } else if(IsLessThan(original)) {
271        return SimplifyLessThan(original);
272      } else if(IsAnd(original)) {
273        return SimplifyAnd(original);
274      } else if(IsOr(original)) {
275        return SimplifyOr(original);
276      } else if(IsNot(original)) {
277        return SimplifyNot(original);
278      } else if(IsTimeLag(original)) {
279        return SimplifyTimeLag(original);
280      } else if(IsIntegral(original)) {
281        return SimplifyIntegral(original);
282      } else {
283        return SimplifyAny(original);
284      }
285    }
286
287    #region specific simplification routines
288
289    private ISymbolicExpressionTreeNode SimplifyAny(ISymbolicExpressionTreeNode original) {
290      // can't simplify this function but simplify all subtrees
291      List<ISymbolicExpressionTreeNode> subtrees = new List<ISymbolicExpressionTreeNode>(original.Subtrees);
292      while(original.Subtrees.Count() > 0) original.RemoveSubtree(0);
293      var clone = (SymbolicExpressionTreeNode)original.Clone();
294      List<ISymbolicExpressionTreeNode> simplifiedSubtrees = new List<ISymbolicExpressionTreeNode>();
295      foreach(var subtree in subtrees) {
296        simplifiedSubtrees.Add(GetSimplifiedTree(subtree));
297        original.AddSubtree(subtree);
298      }
299      foreach(var simplifiedSubtree in simplifiedSubtrees) {
300        clone.AddSubtree(simplifiedSubtree);
301      }
302      if(simplifiedSubtrees.TrueForAll(t => IsConstant(t))) {
303        SimplifyConstantExpression(clone);
304      }
305      return clone;
306    }
307
308    private ISymbolicExpressionTreeNode SimplifyConstantExpression(ISymbolicExpressionTreeNode original) {
309      // not yet implemented
310      return original;
311    }
312
313    private ISymbolicExpressionTreeNode SimplifyAverage(ISymbolicExpressionTreeNode original) {
314      if(original.Subtrees.Count() == 1) {
315        return GetSimplifiedTree(original.GetSubtree(0));
316      } else {
317        // simplify expressions x0..xn
318        // make sum(x0..xn) / n
319        var sum = original.Subtrees
320          .Select(GetSimplifiedTree)
321          .Aggregate(MakeSum);
322        return MakeFraction(sum, MakeConstant(original.Subtrees.Count()));
323      }
324    }
325
326    private ISymbolicExpressionTreeNode SimplifyDivision(ISymbolicExpressionTreeNode original) {
327      if(original.Subtrees.Count() == 1) {
328        return Invert(GetSimplifiedTree(original.GetSubtree(0)));
329      } else {
330        // simplify expressions x0..xn
331        // make multiplication (x0 * 1/(x1 * x1 * .. * xn))
332        var first = original.GetSubtree(0);
333        var second = original.GetSubtree(1);
334        var remaining = original.Subtrees.Skip(2);
335        return
336          MakeProduct(GetSimplifiedTree(first),
337            Invert(remaining.Aggregate(GetSimplifiedTree(second), (a, b) => MakeProduct(a, GetSimplifiedTree(b)))));
338      }
339    }
340
341    private ISymbolicExpressionTreeNode SimplifyMultiplication(ISymbolicExpressionTreeNode original) {
342      if(original.Subtrees.Count() == 1) {
343        return GetSimplifiedTree(original.GetSubtree(0));
344      } else {
345        return original.Subtrees
346          .Select(GetSimplifiedTree)
347          .Aggregate(MakeProduct);
348      }
349    }
350
351    private ISymbolicExpressionTreeNode SimplifySubtraction(ISymbolicExpressionTreeNode original) {
352      if(original.Subtrees.Count() == 1) {
353        return Negate(GetSimplifiedTree(original.GetSubtree(0)));
354      } else {
355        // simplify expressions x0..xn
356        // make addition (x0,-x1..-xn)
357        var first = original.Subtrees.First();
358        var remaining = original.Subtrees.Skip(1);
359        return remaining.Aggregate(GetSimplifiedTree(first), (a, b) => MakeSum(a, Negate(GetSimplifiedTree(b))));
360      }
361    }
362
363    private ISymbolicExpressionTreeNode SimplifyAddition(ISymbolicExpressionTreeNode original) {
364      if(original.Subtrees.Count() == 1) {
365        return GetSimplifiedTree(original.GetSubtree(0));
366      } else {
367        // simplify expression x0..xn
368        // make addition (x0..xn)
369        return original.Subtrees
370          .Select(GetSimplifiedTree)
371          .Aggregate(MakeSum);
372      }
373    }
374
375    private ISymbolicExpressionTreeNode SimplifyNot(ISymbolicExpressionTreeNode original) {
376      return MakeNot(GetSimplifiedTree(original.GetSubtree(0)));
377    }
378
379    private ISymbolicExpressionTreeNode SimplifyOr(ISymbolicExpressionTreeNode original) {
380      return original.Subtrees
381        .Select(GetSimplifiedTree)
382        .Aggregate(MakeOr);
383    }
384
385    private ISymbolicExpressionTreeNode SimplifyAnd(ISymbolicExpressionTreeNode original) {
386      return original.Subtrees
387        .Select(GetSimplifiedTree)
388        .Aggregate(MakeAnd);
389    }
390
391    private ISymbolicExpressionTreeNode SimplifyLessThan(ISymbolicExpressionTreeNode original) {
392      return MakeLessThan(GetSimplifiedTree(original.GetSubtree(0)), GetSimplifiedTree(original.GetSubtree(1)));
393    }
394
395    private ISymbolicExpressionTreeNode SimplifyGreaterThan(ISymbolicExpressionTreeNode original) {
396      return MakeGreaterThan(GetSimplifiedTree(original.GetSubtree(0)), GetSimplifiedTree(original.GetSubtree(1)));
397    }
398
399    private ISymbolicExpressionTreeNode SimplifyIfThenElse(ISymbolicExpressionTreeNode original) {
400      return MakeIfThenElse(GetSimplifiedTree(original.GetSubtree(0)), GetSimplifiedTree(original.GetSubtree(1)),
401        GetSimplifiedTree(original.GetSubtree(2)));
402    }
403
404    private ISymbolicExpressionTreeNode SimplifyTangent(ISymbolicExpressionTreeNode original) {
405      return MakeTangent(GetSimplifiedTree(original.GetSubtree(0)));
406    }
407
408    private ISymbolicExpressionTreeNode SimplifyCosine(ISymbolicExpressionTreeNode original) {
409      return MakeCosine(GetSimplifiedTree(original.GetSubtree(0)));
410    }
411
412    private ISymbolicExpressionTreeNode SimplifySine(ISymbolicExpressionTreeNode original) {
413      return MakeSine(GetSimplifiedTree(original.GetSubtree(0)));
414    }
415
416    private ISymbolicExpressionTreeNode SimplifyExp(ISymbolicExpressionTreeNode original) {
417      return MakeExp(GetSimplifiedTree(original.GetSubtree(0)));
418    }
419
420    private ISymbolicExpressionTreeNode SimplifySquare(ISymbolicExpressionTreeNode original) {
421      return MakeSquare(GetSimplifiedTree(original.GetSubtree(0)));
422    }
423
424    private ISymbolicExpressionTreeNode SimplifySquareRoot(ISymbolicExpressionTreeNode original) {
425      return MakeSquareRoot(GetSimplifiedTree(original.GetSubtree(0)));
426    }
427
428    private ISymbolicExpressionTreeNode SimplifyLog(ISymbolicExpressionTreeNode original) {
429      return MakeLog(GetSimplifiedTree(original.GetSubtree(0)));
430    }
431
432    private ISymbolicExpressionTreeNode SimplifyRoot(ISymbolicExpressionTreeNode original) {
433      return MakeRoot(GetSimplifiedTree(original.GetSubtree(0)), GetSimplifiedTree(original.GetSubtree(1)));
434    }
435
436    private ISymbolicExpressionTreeNode SimplifyPower(ISymbolicExpressionTreeNode original) {
437      return MakePower(GetSimplifiedTree(original.GetSubtree(0)), GetSimplifiedTree(original.GetSubtree(1)));
438    }
439
440    private ISymbolicExpressionTreeNode SimplifyTimeLag(ISymbolicExpressionTreeNode original) {
441      var laggedTreeNode = original as ILaggedTreeNode;
442      var simplifiedSubtree = GetSimplifiedTree(original.GetSubtree(0));
443      if(!ContainsVariableCondition(simplifiedSubtree)) {
444        return AddLagToDynamicNodes(simplifiedSubtree, laggedTreeNode.Lag);
445      } else {
446        return MakeTimeLag(simplifiedSubtree, laggedTreeNode.Lag);
447      }
448    }
449
450    private ISymbolicExpressionTreeNode SimplifyIntegral(ISymbolicExpressionTreeNode original) {
451      var laggedTreeNode = original as ILaggedTreeNode;
452      var simplifiedSubtree = GetSimplifiedTree(original.GetSubtree(0));
453      if(IsConstant(simplifiedSubtree)) {
454        return GetSimplifiedTree(MakeProduct(simplifiedSubtree, MakeConstant(-laggedTreeNode.Lag)));
455      } else {
456        return MakeIntegral(simplifiedSubtree, laggedTreeNode.Lag);
457      }
458    }
459
460    #endregion
461
462    #region low level tree restructuring
463
464    private ISymbolicExpressionTreeNode MakeTimeLag(ISymbolicExpressionTreeNode subtree, int lag) {
465      if(lag == 0) return subtree;
466      if(IsConstant(subtree)) return subtree;
467      var lagNode = (LaggedTreeNode)timeLagSymbol.CreateTreeNode();
468      lagNode.Lag = lag;
469      lagNode.AddSubtree(subtree);
470      return lagNode;
471    }
472
473    private ISymbolicExpressionTreeNode MakeIntegral(ISymbolicExpressionTreeNode subtree, int lag) {
474      if(lag == 0) return subtree;
475      else if(lag == -1 || lag == 1) {
476        return MakeSum(subtree, AddLagToDynamicNodes((ISymbolicExpressionTreeNode)subtree.Clone(), lag));
477      } else {
478        var node = (LaggedTreeNode)integralSymbol.CreateTreeNode();
479        node.Lag = lag;
480        node.AddSubtree(subtree);
481        return node;
482      }
483    }
484
485    private ISymbolicExpressionTreeNode MakeNot(ISymbolicExpressionTreeNode t) {
486      if(IsConstant(t)) {
487        var constNode = t as ConstantTreeNode;
488        if(constNode.Value > 0) return MakeConstant(-1.0);
489        else return MakeConstant(1.0);
490      } else if(IsNot(t)) {
491        return t.GetSubtree(0);
492      } else if(!IsBoolean(t)) {
493        var gtNode = gtSymbol.CreateTreeNode();
494        gtNode.AddSubtree(t);
495        gtNode.AddSubtree(MakeConstant(0.0));
496        var notNode = notSymbol.CreateTreeNode();
497        notNode.AddSubtree(gtNode);
498        return notNode;
499      } else {
500        var notNode = notSymbol.CreateTreeNode();
501        notNode.AddSubtree(t);
502        return notNode;
503      }
504    }
505
506    private ISymbolicExpressionTreeNode MakeOr(ISymbolicExpressionTreeNode a, ISymbolicExpressionTreeNode b) {
507      if(IsConstant(a) && IsConstant(b)) {
508        var constA = a as ConstantTreeNode;
509        var constB = b as ConstantTreeNode;
510        if(constA.Value > 0.0 || constB.Value > 0.0) {
511          return MakeConstant(1.0);
512        } else {
513          return MakeConstant(-1.0);
514        }
515      } else if(IsConstant(a)) {
516        return MakeOr(b, a);
517      } else if(IsConstant(b)) {
518        var constT = b as ConstantTreeNode;
519        if(constT.Value > 0.0) {
520          // boolean expression is necessarily true
521          return MakeConstant(1.0);
522        } else {
523          // the constant value has no effect on the result of the boolean condition so we can drop the constant term
524          var orNode = orSymbol.CreateTreeNode();
525          orNode.AddSubtree(a);
526          return orNode;
527        }
528      } else {
529        var orNode = orSymbol.CreateTreeNode();
530        orNode.AddSubtree(a);
531        orNode.AddSubtree(b);
532        return orNode;
533      }
534    }
535
536    private ISymbolicExpressionTreeNode MakeAnd(ISymbolicExpressionTreeNode a, ISymbolicExpressionTreeNode b) {
537      if(IsConstant(a) && IsConstant(b)) {
538        var constA = a as ConstantTreeNode;
539        var constB = b as ConstantTreeNode;
540        if(constA.Value > 0.0 && constB.Value > 0.0) {
541          return MakeConstant(1.0);
542        } else {
543          return MakeConstant(-1.0);
544        }
545      } else if(IsConstant(a)) {
546        return MakeAnd(b, a);
547      } else if(IsConstant(b)) {
548        var constB = b as ConstantTreeNode;
549        if(constB.Value > 0.0) {
550          // the constant value has no effect on the result of the boolean condition so we can drop the constant term
551          var andNode = andSymbol.CreateTreeNode();
552          andNode.AddSubtree(a);
553          return andNode;
554        } else {
555          // boolean expression is necessarily false
556          return MakeConstant(-1.0);
557        }
558      } else {
559        var andNode = andSymbol.CreateTreeNode();
560        andNode.AddSubtree(a);
561        andNode.AddSubtree(b);
562        return andNode;
563      }
564    }
565
566    private ISymbolicExpressionTreeNode MakeLessThan(ISymbolicExpressionTreeNode leftSide,
567      ISymbolicExpressionTreeNode rightSide) {
568      if(IsConstant(leftSide) && IsConstant(rightSide)) {
569        var lsConst = leftSide as ConstantTreeNode;
570        var rsConst = rightSide as ConstantTreeNode;
571        if(lsConst.Value < rsConst.Value) return MakeConstant(1.0);
572        else return MakeConstant(-1.0);
573      } else {
574        var ltNode = ltSymbol.CreateTreeNode();
575        ltNode.AddSubtree(leftSide);
576        ltNode.AddSubtree(rightSide);
577        return ltNode;
578      }
579    }
580
581    private ISymbolicExpressionTreeNode MakeGreaterThan(ISymbolicExpressionTreeNode leftSide,
582      ISymbolicExpressionTreeNode rightSide) {
583      if(IsConstant(leftSide) && IsConstant(rightSide)) {
584        var lsConst = leftSide as ConstantTreeNode;
585        var rsConst = rightSide as ConstantTreeNode;
586        if(lsConst.Value > rsConst.Value) return MakeConstant(1.0);
587        else return MakeConstant(-1.0);
588      } else {
589        var gtNode = gtSymbol.CreateTreeNode();
590        gtNode.AddSubtree(leftSide);
591        gtNode.AddSubtree(rightSide);
592        return gtNode;
593      }
594    }
595
596    private ISymbolicExpressionTreeNode MakeIfThenElse(ISymbolicExpressionTreeNode condition,
597      ISymbolicExpressionTreeNode trueBranch, ISymbolicExpressionTreeNode falseBranch) {
598      if(IsConstant(condition)) {
599        var constT = condition as ConstantTreeNode;
600        if(constT.Value > 0.0) return trueBranch;
601        else return falseBranch;
602      } else {
603        var ifNode = ifThenElseSymbol.CreateTreeNode();
604        if(IsBoolean(condition)) {
605          ifNode.AddSubtree(condition);
606        } else {
607          var gtNode = gtSymbol.CreateTreeNode();
608          gtNode.AddSubtree(condition);
609          gtNode.AddSubtree(MakeConstant(0.0));
610          ifNode.AddSubtree(gtNode);
611        }
612        ifNode.AddSubtree(trueBranch);
613        ifNode.AddSubtree(falseBranch);
614        return ifNode;
615      }
616    }
617
618    private ISymbolicExpressionTreeNode MakeSine(ISymbolicExpressionTreeNode node) {
619      if(IsConstant(node)) {
620        var constT = node as ConstantTreeNode;
621        return MakeConstant(Math.Sin(constT.Value));
622      } else if(IsFactor(node)) {
623        var factor = node as FactorVariableTreeNode;
624        return MakeFactor(factor.Symbol, factor.VariableName, factor.Weights.Select(Math.Sin));
625      } else if(IsBinFactor(node)) {
626        var binFactor = node as BinaryFactorVariableTreeNode;
627        return MakeBinFactor(binFactor.Symbol, binFactor.VariableName, binFactor.VariableValue, Math.Sin(binFactor.Weight));
628      } else {
629        var sineNode = sineSymbol.CreateTreeNode();
630        sineNode.AddSubtree(node);
631        return sineNode;
632      }
633    }
634
635    private ISymbolicExpressionTreeNode MakeTangent(ISymbolicExpressionTreeNode node) {
636      if(IsConstant(node)) {
637        var constT = node as ConstantTreeNode;
638        return MakeConstant(Math.Tan(constT.Value));
639      } else if(IsFactor(node)) {
640        var factor = node as FactorVariableTreeNode;
641        return MakeFactor(factor.Symbol, factor.VariableName, factor.Weights.Select(Math.Tan));
642      } else if(IsBinFactor(node)) {
643        var binFactor = node as BinaryFactorVariableTreeNode;
644        return MakeBinFactor(binFactor.Symbol, binFactor.VariableName, binFactor.VariableValue, Math.Tan(binFactor.Weight));
645      } else {
646        var tanNode = tanSymbol.CreateTreeNode();
647        tanNode.AddSubtree(node);
648        return tanNode;
649      }
650    }
651
652    private ISymbolicExpressionTreeNode MakeCosine(ISymbolicExpressionTreeNode node) {
653      if(IsConstant(node)) {
654        var constT = node as ConstantTreeNode;
655        return MakeConstant(Math.Cos(constT.Value));
656      } else if(IsFactor(node)) {
657        var factor = node as FactorVariableTreeNode;
658        return MakeFactor(factor.Symbol, factor.VariableName, factor.Weights.Select(Math.Cos));
659      } else if(IsBinFactor(node)) {
660        var binFactor = node as BinaryFactorVariableTreeNode;
661        return MakeBinFactor(binFactor.Symbol, binFactor.VariableName, binFactor.VariableValue, Math.Cos(binFactor.Weight));
662      } else {
663        var cosNode = cosineSymbol.CreateTreeNode();
664        cosNode.AddSubtree(node);
665        return cosNode;
666      }
667    }
668
669    private ISymbolicExpressionTreeNode MakeExp(ISymbolicExpressionTreeNode node) {
670      if(IsConstant(node)) {
671        var constT = node as ConstantTreeNode;
672        return MakeConstant(Math.Exp(constT.Value));
673      } else if(IsFactor(node)) {
674        var factNode = node as FactorVariableTreeNode;
675        return MakeFactor(factNode.Symbol, factNode.VariableName, factNode.Weights.Select(w => Math.Exp(w)));
676      } else if(IsBinFactor(node)) {
677        var binFactor = node as BinaryFactorVariableTreeNode;
678        return MakeBinFactor(binFactor.Symbol, binFactor.VariableName, binFactor.VariableValue, Math.Exp(binFactor.Weight));
679      } else if(IsLog(node)) {
680        return node.GetSubtree(0);
681      } else if(IsAddition(node)) {
682        return node.Subtrees.Select(s => MakeExp(s)).Aggregate((s, t) => MakeProduct(s, t));
683      } else if(IsSubtraction(node)) {
684        return node.Subtrees.Select(s => MakeExp(s)).Aggregate((s, t) => MakeProduct(s, Negate(t)));
685      } else {
686        var expNode = expSymbol.CreateTreeNode();
687        expNode.AddSubtree(node);
688        return expNode;
689      }
690    }
691    private ISymbolicExpressionTreeNode MakeLog(ISymbolicExpressionTreeNode node) {
692      if(IsConstant(node)) {
693        var constT = node as ConstantTreeNode;
694        return MakeConstant(Math.Log(constT.Value));
695      } else if(IsFactor(node)) {
696        var factNode = node as FactorVariableTreeNode;
697        return MakeFactor(factNode.Symbol, factNode.VariableName, factNode.Weights.Select(w => Math.Log(w)));
698      } else if(IsBinFactor(node)) {
699        var binFactor = node as BinaryFactorVariableTreeNode;
700        return MakeBinFactor(binFactor.Symbol, binFactor.VariableName, binFactor.VariableValue, Math.Log(binFactor.Weight));
701      } else if(IsExp(node)) {
702        return node.GetSubtree(0);
703      } else if(IsSquareRoot(node)) {
704        return MakeFraction(MakeLog(node.GetSubtree(0)), MakeConstant(2.0));
705      } else {
706        var logNode = logSymbol.CreateTreeNode();
707        logNode.AddSubtree(node);
708        return logNode;
709      }
710    }
711
712    private ISymbolicExpressionTreeNode MakeSquare(ISymbolicExpressionTreeNode node) {
713      if(IsConstant(node)) {
714        var constT = node as ConstantTreeNode;
715        return MakeConstant(constT.Value * constT.Value);
716      } else if(IsFactor(node)) {
717        var factNode = node as FactorVariableTreeNode;
718        return MakeFactor(factNode.Symbol, factNode.VariableName, factNode.Weights.Select(w => w * w));
719      } else if(IsBinFactor(node)) {
720        var binFactor = node as BinaryFactorVariableTreeNode;
721        return MakeBinFactor(binFactor.Symbol, binFactor.VariableName, binFactor.VariableValue, binFactor.Weight * binFactor.Weight);
722      } else if(IsSquareRoot(node)) {
723        return node.GetSubtree(0);
724      } else {
725        var sqrNode = sqrSymbol.CreateTreeNode();
726        sqrNode.AddSubtree(node);
727        return sqrNode;
728      }
729    }
730
731    private ISymbolicExpressionTreeNode MakeSquareRoot(ISymbolicExpressionTreeNode node) {
732      if(IsConstant(node)) {
733        var constT = node as ConstantTreeNode;
734        return MakeConstant(Math.Sqrt(constT.Value));
735      } else if(IsFactor(node)) {
736        var factNode = node as FactorVariableTreeNode;
737        return MakeFactor(factNode.Symbol, factNode.VariableName, factNode.Weights.Select(w => Math.Sqrt(w)));
738      } else if(IsBinFactor(node)) {
739        var binFactor = node as BinaryFactorVariableTreeNode;
740        return MakeBinFactor(binFactor.Symbol, binFactor.VariableName, binFactor.VariableValue, Math.Sqrt(binFactor.Weight));
741      } else if(IsSquare(node)) {
742        return node.GetSubtree(0);
743      } else {
744        var sqrtNode = sqrtSymbol.CreateTreeNode();
745        sqrtNode.AddSubtree(node);
746        return sqrtNode;
747      }
748    }
749
750    private ISymbolicExpressionTreeNode MakeRoot(ISymbolicExpressionTreeNode a, ISymbolicExpressionTreeNode b) {
751      if(IsConstant(a) && IsConstant(b)) {
752        var constA = a as ConstantTreeNode;
753        var constB = b as ConstantTreeNode;
754        return MakeConstant(Math.Pow(constA.Value, 1.0 / Math.Round(constB.Value)));
755      } else if(IsFactor(a) && IsConstant(b)) {
756        var factNode = a as FactorVariableTreeNode;
757        var constNode = b as ConstantTreeNode;
758        return MakeFactor(factNode.Symbol, factNode.VariableName,
759          factNode.Weights.Select(w => Math.Pow(w, 1.0 / Math.Round(constNode.Value))));
760      } else if(IsBinFactor(a) && IsConstant(b)) {
761        var binFactor = a as BinaryFactorVariableTreeNode;
762        var constNode = b as ConstantTreeNode;
763        return MakeBinFactor(binFactor.Symbol, binFactor.VariableName, binFactor.VariableValue, Math.Pow(binFactor.Weight, 1.0 / Math.Round(constNode.Value)));
764      } else if(IsConstant(a) && IsFactor(b)) {
765        var constNode = a as ConstantTreeNode;
766        var factNode = b as FactorVariableTreeNode;
767        return MakeFactor(factNode.Symbol, factNode.VariableName, factNode.Weights.Select(w => Math.Pow(constNode.Value, 1.0 / Math.Round(w))));
768      } else if(IsConstant(a) && IsBinFactor(b)) {
769        var constNode = a as ConstantTreeNode;
770        var factNode = b as BinaryFactorVariableTreeNode;
771        return MakeBinFactor(factNode.Symbol, factNode.VariableName, factNode.VariableValue, Math.Pow(constNode.Value, 1.0 / Math.Round(factNode.Weight)));
772      } else if(IsFactor(a) && IsFactor(b) && AreSameTypeAndVariable(a, b)) {
773        var node0 = a as FactorVariableTreeNode;
774        var node1 = b as FactorVariableTreeNode;
775        return MakeFactor(node0.Symbol, node0.VariableName, node0.Weights.Zip(node1.Weights, (u, v) => Math.Pow(u, 1.0 / Math.Round(v))));
776      } else if(IsConstant(b)) {
777        var constB = b as ConstantTreeNode;
778        var constBValue = Math.Round(constB.Value);
779        if(constBValue.IsAlmost(1.0)) {
780          return a;
781        } else if(constBValue.IsAlmost(0.0)) {
782          return MakeConstant(1.0);
783        } else if(constBValue.IsAlmost(-1.0)) {
784          return MakeFraction(MakeConstant(1.0), a);
785        } else if(constBValue < 0) {
786          var rootNode = rootSymbol.CreateTreeNode();
787          rootNode.AddSubtree(a);
788          rootNode.AddSubtree(MakeConstant(-1.0 * constBValue));
789          return MakeFraction(MakeConstant(1.0), rootNode);
790        } else {
791          var rootNode = rootSymbol.CreateTreeNode();
792          rootNode.AddSubtree(a);
793          rootNode.AddSubtree(MakeConstant(constBValue));
794          return rootNode;
795        }
796      } else {
797        var rootNode = rootSymbol.CreateTreeNode();
798        rootNode.AddSubtree(a);
799        rootNode.AddSubtree(b);
800        return rootNode;
801      }
802    }
803
804
805    private ISymbolicExpressionTreeNode MakePower(ISymbolicExpressionTreeNode a, ISymbolicExpressionTreeNode b) {
806      if(IsConstant(a) && IsConstant(b)) {
807        var constA = a as ConstantTreeNode;
808        var constB = b as ConstantTreeNode;
809        return MakeConstant(Math.Pow(constA.Value, Math.Round(constB.Value)));
810      } else if(IsFactor(a) && IsConstant(b)) {
811        var factNode = a as FactorVariableTreeNode;
812        var constNode = b as ConstantTreeNode;
813        return MakeFactor(factNode.Symbol, factNode.VariableName, factNode.Weights.Select(w => Math.Pow(w, Math.Round(constNode.Value))));
814      } else if(IsBinFactor(a) && IsConstant(b)) {
815        var binFactor = a as BinaryFactorVariableTreeNode;
816        var constNode = b as ConstantTreeNode;
817        return MakeBinFactor(binFactor.Symbol, binFactor.VariableName, binFactor.VariableValue, Math.Pow(binFactor.Weight, Math.Round(constNode.Value)));
818      } else if(IsConstant(a) && IsFactor(b)) {
819        var constNode = a as ConstantTreeNode;
820        var factNode = b as FactorVariableTreeNode;
821        return MakeFactor(factNode.Symbol, factNode.VariableName, factNode.Weights.Select(w => Math.Pow(constNode.Value, Math.Round(w))));
822      } else if(IsConstant(a) && IsBinFactor(b)) {
823        var constNode = a as ConstantTreeNode;
824        var factNode = b as BinaryFactorVariableTreeNode;
825        return MakeBinFactor(factNode.Symbol, factNode.VariableName, factNode.VariableValue, Math.Pow(constNode.Value, Math.Round(factNode.Weight)));
826      } else if(IsFactor(a) && IsFactor(b) && AreSameTypeAndVariable(a, b)) {
827        var node0 = a as FactorVariableTreeNode;
828        var node1 = b as FactorVariableTreeNode;
829        return MakeFactor(node0.Symbol, node0.VariableName, node0.Weights.Zip(node1.Weights, (u, v) => Math.Pow(u, Math.Round(v))));
830      } else if(IsConstant(b)) {
831        var constB = b as ConstantTreeNode;
832        double exponent = Math.Round(constB.Value);
833        if(exponent.IsAlmost(0.0)) {
834          return MakeConstant(1.0);
835        } else if(exponent.IsAlmost(1.0)) {
836          return a;
837        } else if(exponent.IsAlmost(-1.0)) {
838          return MakeFraction(MakeConstant(1.0), a);
839        } else if(exponent < 0) {
840          var powNode = powSymbol.CreateTreeNode();
841          powNode.AddSubtree(a);
842          powNode.AddSubtree(MakeConstant(-1.0 * exponent));
843          return MakeFraction(MakeConstant(1.0), powNode);
844        } else {
845          var powNode = powSymbol.CreateTreeNode();
846          powNode.AddSubtree(a);
847          powNode.AddSubtree(MakeConstant(exponent));
848          return powNode;
849        }
850      } else {
851        var powNode = powSymbol.CreateTreeNode();
852        powNode.AddSubtree(a);
853        powNode.AddSubtree(b);
854        return powNode;
855      }
856    }
857
858
859    // MakeFraction, MakeProduct and MakeSum take two already simplified trees and create a new simplified tree
860    private ISymbolicExpressionTreeNode MakeFraction(ISymbolicExpressionTreeNode a, ISymbolicExpressionTreeNode b) {
861      if(IsConstant(a) && IsConstant(b)) {
862        // fold constants
863        return MakeConstant(((ConstantTreeNode)a).Value / ((ConstantTreeNode)b).Value);
864      } else if((IsConstant(a) && !((ConstantTreeNode)a).Value.IsAlmost(1.0))) {
865        return MakeFraction(MakeConstant(1.0), MakeProduct(b, Invert(a)));
866      } else if(IsVariableBase(a) && IsConstant(b)) {
867        // merge constant values into variable weights
868        var constB = ((ConstantTreeNode)b).Value;
869        ((VariableTreeNodeBase)a).Weight /= constB;
870        return a;
871      } else if(IsFactor(a) && IsConstant(b)) {
872        var factNode = a as FactorVariableTreeNode;
873        var constNode = b as ConstantTreeNode;
874        return MakeFactor(factNode.Symbol, factNode.VariableName, factNode.Weights.Select(w => w / constNode.Value));
875      } else if(IsBinFactor(a) && IsConstant(b)) {
876        var factNode = a as BinaryFactorVariableTreeNode;
877        var constNode = b as ConstantTreeNode;
878        return MakeBinFactor(factNode.Symbol, factNode.VariableName, factNode.VariableValue, factNode.Weight / constNode.Value);
879      } else if(IsFactor(a) && IsFactor(b) && AreSameTypeAndVariable(a, b)) {
880        var node0 = a as FactorVariableTreeNode;
881        var node1 = b as FactorVariableTreeNode;
882        return MakeFactor(node0.Symbol, node0.VariableName, node0.Weights.Zip(node1.Weights, (u, v) => u / v));
883      } else if(IsFactor(a)) {
884        return MakeFraction(MakeConstant(1.0), MakeProduct(b, Invert(a)));
885      } else if(IsVariableBase(a) && IsVariableBase(b) && AreSameTypeAndVariable(a, b) && !IsBinFactor(b)) {
886        // cancel variables (not allowed for bin factors because of division by zero)
887        var aVar = a as VariableTreeNode;
888        var bVar = b as VariableTreeNode;
889        return MakeConstant(aVar.Weight / bVar.Weight);
890      } else if(IsAddition(a) && IsConstant(b)) {
891        return a.Subtrees
892          .Select(x => GetSimplifiedTree(x))
893          .Select(x => MakeFraction(x, b))
894          .Aggregate((c, d) => MakeSum(c, d));
895      } else if(IsMultiplication(a) && IsConstant(b)) {
896        return MakeProduct(a, Invert(b));
897      } else if(IsDivision(a) && IsConstant(b)) {
898        // (a1 / a2) / c => (a1 / (a2 * c))
899        return MakeFraction(a.GetSubtree(0), MakeProduct(a.GetSubtree(1), b));
900      } else if(IsDivision(a) && IsDivision(b)) {
901        // (a1 / a2) / (b1 / b2) =>
902        return MakeFraction(MakeProduct(a.GetSubtree(0), b.GetSubtree(1)), MakeProduct(a.GetSubtree(1), b.GetSubtree(0)));
903      } else if(IsDivision(a)) {
904        // (a1 / a2) / b => (a1 / (a2 * b))
905        return MakeFraction(a.GetSubtree(0), MakeProduct(a.GetSubtree(1), b));
906      } else if(IsDivision(b)) {
907        // a / (b1 / b2) => (a * b2) / b1
908        return MakeFraction(MakeProduct(a, b.GetSubtree(1)), b.GetSubtree(0));
909      } else {
910        var div = divSymbol.CreateTreeNode();
911        div.AddSubtree(a);
912        div.AddSubtree(b);
913        return div;
914      }
915    }
916
917    private ISymbolicExpressionTreeNode MakeSum(ISymbolicExpressionTreeNode a, ISymbolicExpressionTreeNode b) {
918      if(IsConstant(a) && IsConstant(b)) {
919        // fold constants
920        ((ConstantTreeNode)a).Value += ((ConstantTreeNode)b).Value;
921        return a;
922      } else if(IsConstant(a)) {
923        // c + x => x + c
924        // b is not constant => make sure constant is on the right
925        return MakeSum(b, a);
926      } else if(IsConstant(b) && ((ConstantTreeNode)b).Value.IsAlmost(0.0)) {
927        // x + 0 => x
928        return a;
929      } else if(IsFactor(a) && IsConstant(b)) {
930        var factNode = a as FactorVariableTreeNode;
931        var constNode = b as ConstantTreeNode;
932        return MakeFactor(factNode.Symbol, factNode.VariableName, factNode.Weights.Select((w) => w + constNode.Value));
933      } else if(IsFactor(a) && IsFactor(b) && AreSameTypeAndVariable(a, b)) {
934        var node0 = a as FactorVariableTreeNode;
935        var node1 = b as FactorVariableTreeNode;
936        return MakeFactor(node0.Symbol, node0.VariableName, node0.Weights.Zip(node1.Weights, (u, v) => u + v));
937      } else if(IsAddition(a) && IsAddition(b)) {
938        // merge additions
939        var add = addSymbol.CreateTreeNode();
940        // add all sub trees except for the last
941        for(int i = 0; i < a.Subtrees.Count() - 1; i++) add.AddSubtree(a.GetSubtree(i));
942        for(int i = 0; i < b.Subtrees.Count() - 1; i++) add.AddSubtree(b.GetSubtree(i));
943        if(IsConstant(a.Subtrees.Last()) && IsConstant(b.Subtrees.Last())) {
944          add.AddSubtree(MakeSum(a.Subtrees.Last(), b.Subtrees.Last()));
945        } else if(IsConstant(a.Subtrees.Last())) {
946          add.AddSubtree(b.Subtrees.Last());
947          add.AddSubtree(a.Subtrees.Last());
948        } else {
949          add.AddSubtree(a.Subtrees.Last());
950          add.AddSubtree(b.Subtrees.Last());
951        }
952        MergeVariablesInSum(add);
953        if(add.Subtrees.Count() == 1) {
954          return add.GetSubtree(0);
955        } else {
956          return add;
957        }
958      } else if(IsAddition(b)) {
959        return MakeSum(b, a);
960      } else if(IsAddition(a) && IsConstant(b)) {
961        // a is an addition and b is a constant => append b to a and make sure the constants are merged
962        var add = addSymbol.CreateTreeNode();
963        // add all sub trees except for the last
964        for(int i = 0; i < a.Subtrees.Count() - 1; i++) add.AddSubtree(a.GetSubtree(i));
965        if(IsConstant(a.Subtrees.Last()))
966          add.AddSubtree(MakeSum(a.Subtrees.Last(), b));
967        else {
968          add.AddSubtree(a.Subtrees.Last());
969          add.AddSubtree(b);
970        }
971        return add;
972      } else if(IsAddition(a)) {
973        // a is already an addition => append b
974        var add = addSymbol.CreateTreeNode();
975        add.AddSubtree(b);
976        foreach(var subtree in a.Subtrees) {
977          add.AddSubtree(subtree);
978        }
979        MergeVariablesInSum(add);
980        if(add.Subtrees.Count() == 1) {
981          return add.GetSubtree(0);
982        } else {
983          return add;
984        }
985      } else {
986        var add = addSymbol.CreateTreeNode();
987        add.AddSubtree(a);
988        add.AddSubtree(b);
989        MergeVariablesInSum(add);
990        if(add.Subtrees.Count() == 1) {
991          return add.GetSubtree(0);
992        } else {
993          return add;
994        }
995      }
996    }
997
998    // makes sure variable symbols in sums are combined
999    private void MergeVariablesInSum(ISymbolicExpressionTreeNode sum) {
1000      var subtrees = new List<ISymbolicExpressionTreeNode>(sum.Subtrees);
1001      while(sum.Subtrees.Any()) sum.RemoveSubtree(0);
1002      var groupedVarNodes = from node in subtrees.OfType<IVariableTreeNode>()
1003                            where node.SubtreeCount == 0
1004                            group node by GroupId(node) into g
1005                            select g;
1006      var constant = (from node in subtrees.OfType<ConstantTreeNode>()
1007                      select node.Value).DefaultIfEmpty(0.0).Sum();
1008      var unchangedSubtrees = subtrees.Where(t => t.SubtreeCount > 0 || !(t is IVariableTreeNode) && !(t is ConstantTreeNode));
1009
1010      foreach(var variableNodeGroup in groupedVarNodes) {
1011        var firstNode = variableNodeGroup.First();
1012        if(firstNode is VariableTreeNodeBase) {
1013          var representative = firstNode as VariableTreeNodeBase;
1014          var weightSum = variableNodeGroup.Cast<VariableTreeNodeBase>().Select(t => t.Weight).Sum();
1015          representative.Weight = weightSum;
1016          sum.AddSubtree(representative);
1017        } else if(firstNode is FactorVariableTreeNode) {
1018          var representative = firstNode as FactorVariableTreeNode;
1019          foreach(var node in variableNodeGroup.Skip(1).Cast<FactorVariableTreeNode>()) {
1020            for(int j = 0; j < representative.Weights.Length; j++) {
1021              representative.Weights[j] += node.Weights[j];
1022            }
1023          }
1024          for(int j = 0; j < representative.Weights.Length; j++) {
1025            representative.Weights[j] += constant;
1026          }
1027          sum.AddSubtree(representative);
1028        }
1029      }
1030      foreach(var unchangedSubtree in unchangedSubtrees)
1031        sum.AddSubtree(unchangedSubtree);
1032      if(!constant.IsAlmost(0.0)) {
1033        sum.AddSubtree(MakeConstant(constant));
1034      }
1035    }
1036
1037    // nodes referencing variables can be grouped if they have
1038    private string GroupId(IVariableTreeNode node) {
1039      var binaryFactorNode = node as BinaryFactorVariableTreeNode;
1040      var factorNode = node as FactorVariableTreeNode;
1041      var variableNode = node as VariableTreeNode;
1042      var laggedVarNode = node as LaggedVariableTreeNode;
1043      if(variableNode != null) {
1044        return "var " + variableNode.VariableName;
1045      } else if(binaryFactorNode != null) {
1046        return "binfactor " + binaryFactorNode.VariableName + " " + binaryFactorNode.VariableValue;
1047      } else if(factorNode != null) {
1048        return "factor " + factorNode.VariableName;
1049      } else if(laggedVarNode != null) {
1050        return "lagged " + laggedVarNode.VariableName + " " + laggedVarNode.Lag;
1051      } else {
1052        throw new NotSupportedException();
1053      }
1054    }
1055
1056
1057    private ISymbolicExpressionTreeNode MakeProduct(ISymbolicExpressionTreeNode a, ISymbolicExpressionTreeNode b) {
1058      if(IsConstant(a) && IsConstant(b)) {
1059        // fold constants
1060        ((ConstantTreeNode)a).Value *= ((ConstantTreeNode)b).Value;
1061        return a;
1062      } else if(IsConstant(a)) {
1063        // a * $ => $ * a
1064        return MakeProduct(b, a);
1065      } else if(IsFactor(a) && IsFactor(b) && AreSameTypeAndVariable(a, b)) {
1066        var node0 = a as FactorVariableTreeNode;
1067        var node1 = b as FactorVariableTreeNode;
1068        return MakeFactor(node0.Symbol, node0.VariableName, node0.Weights.Zip(node1.Weights, (u, v) => u * v));
1069      } else if(IsBinFactor(a) && IsBinFactor(b) && AreSameTypeAndVariable(a, b)) {
1070        var node0 = a as BinaryFactorVariableTreeNode;
1071        var node1 = b as BinaryFactorVariableTreeNode;
1072        return MakeBinFactor(node0.Symbol, node0.VariableName, node0.VariableValue, node0.Weight * node1.Weight);
1073      } else if(IsFactor(a) && IsConstant(b)) {
1074        var node0 = a as FactorVariableTreeNode;
1075        var node1 = b as ConstantTreeNode;
1076        return MakeFactor(node0.Symbol, node0.VariableName, node0.Weights.Select(w => w * node1.Value));
1077      } else if(IsBinFactor(a) && IsConstant(b)) {
1078        var node0 = a as BinaryFactorVariableTreeNode;
1079        var node1 = b as ConstantTreeNode;
1080        return MakeBinFactor(node0.Symbol, node0.VariableName, node0.VariableValue, node0.Weight * node1.Value);
1081      } else if(IsConstant(b) && ((ConstantTreeNode)b).Value.IsAlmost(1.0)) {
1082        // $ * 1.0 => $
1083        return a;
1084      } else if(IsConstant(b) && IsVariableBase(a)) {
1085        // multiply constants into variables weights
1086        ((VariableTreeNodeBase)a).Weight *= ((ConstantTreeNode)b).Value;
1087        return a;
1088      } else if(IsConstant(b) && IsAddition(a) ||
1089          IsFactor(b) && IsAddition(a)) {
1090        // multiply constants into additions
1091        return a.Subtrees.Select(x => MakeProduct(x, b)).Aggregate((c, d) => MakeSum(c, d));
1092      } else if(IsDivision(a) && IsDivision(b)) {
1093        // (a1 / a2) * (b1 / b2) => (a1 * b1) / (a2 * b2)
1094        return MakeFraction(MakeProduct(a.GetSubtree(0), b.GetSubtree(0)), MakeProduct(a.GetSubtree(1), b.GetSubtree(1)));
1095      } else if(IsDivision(a)) {
1096        // (a1 / a2) * b => (a1 * b) / a2
1097        return MakeFraction(MakeProduct(a.GetSubtree(0), b), a.GetSubtree(1));
1098      } else if(IsDivision(b)) {
1099        // a * (b1 / b2) => (b1 * a) / b2
1100        return MakeFraction(MakeProduct(b.GetSubtree(0), a), b.GetSubtree(1));
1101      } else if(IsMultiplication(a) && IsMultiplication(b)) {
1102        // merge multiplications (make sure constants are merged)
1103        var mul = mulSymbol.CreateTreeNode();
1104        for(int i = 0; i < a.Subtrees.Count(); i++) mul.AddSubtree(a.GetSubtree(i));
1105        for(int i = 0; i < b.Subtrees.Count(); i++) mul.AddSubtree(b.GetSubtree(i));
1106        MergeVariablesAndConstantsInProduct(mul);
1107        return mul;
1108      } else if(IsMultiplication(b)) {
1109        return MakeProduct(b, a);
1110      } else if(IsMultiplication(a)) {
1111        // a is already an multiplication => append b
1112        a.AddSubtree(b);
1113        MergeVariablesAndConstantsInProduct(a);
1114        return a;
1115      } else {
1116        var mul = mulSymbol.CreateTreeNode();
1117        mul.AddSubtree(a);
1118        mul.AddSubtree(b);
1119        MergeVariablesAndConstantsInProduct(mul);
1120        return mul;
1121      }
1122    }
1123
1124    #endregion
1125
1126    #region helper functions
1127
1128    private bool ContainsVariableCondition(ISymbolicExpressionTreeNode node) {
1129      if(node.Symbol is VariableCondition) return true;
1130      foreach(var subtree in node.Subtrees)
1131        if(ContainsVariableCondition(subtree)) return true;
1132      return false;
1133    }
1134
1135    private ISymbolicExpressionTreeNode AddLagToDynamicNodes(ISymbolicExpressionTreeNode node, int lag) {
1136      var laggedTreeNode = node as ILaggedTreeNode;
1137      var variableNode = node as VariableTreeNode;
1138      var variableConditionNode = node as VariableConditionTreeNode;
1139      if(laggedTreeNode != null)
1140        laggedTreeNode.Lag += lag;
1141      else if(variableNode != null) {
1142        var laggedVariableNode = (LaggedVariableTreeNode)laggedVariableSymbol.CreateTreeNode();
1143        laggedVariableNode.Lag = lag;
1144        laggedVariableNode.VariableName = variableNode.VariableName;
1145        return laggedVariableNode;
1146      } else if(variableConditionNode != null) {
1147        throw new NotSupportedException("Removal of time lags around variable condition symbols is not allowed.");
1148      }
1149      var subtrees = new List<ISymbolicExpressionTreeNode>(node.Subtrees);
1150      while(node.SubtreeCount > 0) node.RemoveSubtree(0);
1151      foreach(var subtree in subtrees) {
1152        node.AddSubtree(AddLagToDynamicNodes(subtree, lag));
1153      }
1154      return node;
1155    }
1156
1157    private bool AreSameTypeAndVariable(ISymbolicExpressionTreeNode a, ISymbolicExpressionTreeNode b) {
1158      return GroupId((IVariableTreeNode)a) == GroupId((IVariableTreeNode)b);
1159    }
1160
1161    // helper to combine the constant factors in products and to combine variables (powers of 2, 3...)
1162    private void MergeVariablesAndConstantsInProduct(ISymbolicExpressionTreeNode prod) {
1163      var subtrees = new List<ISymbolicExpressionTreeNode>(prod.Subtrees);
1164      while(prod.Subtrees.Any()) prod.RemoveSubtree(0);
1165      var groupedVarNodes = from node in subtrees.OfType<IVariableTreeNode>()
1166                            where node.SubtreeCount == 0
1167                            group node by GroupId(node) into g
1168                            orderby g.Count()
1169                            select g;
1170      var constantProduct = (from node in subtrees.OfType<VariableTreeNodeBase>()
1171                             select node.Weight)
1172        .Concat(from node in subtrees.OfType<ConstantTreeNode>()
1173                select node.Value)
1174        .DefaultIfEmpty(1.0)
1175        .Aggregate((c1, c2) => c1 * c2);
1176
1177      var unchangedSubtrees = from tree in subtrees
1178                              where tree.SubtreeCount > 0 || !(tree is IVariableTreeNode) && !(tree is ConstantTreeNode)
1179                              select tree;
1180
1181      foreach(var variableNodeGroup in groupedVarNodes) {
1182        var firstNode = variableNodeGroup.First();
1183        if(firstNode is VariableTreeNodeBase) {
1184          var representative = (VariableTreeNodeBase)firstNode;
1185          representative.Weight = 1.0;
1186          if(variableNodeGroup.Count() > 1) {
1187            var poly = mulSymbol.CreateTreeNode();
1188            for(int p = 0; p < variableNodeGroup.Count(); p++) {
1189              poly.AddSubtree((ISymbolicExpressionTreeNode)representative.Clone());
1190            }
1191            prod.AddSubtree(poly);
1192          } else {
1193            prod.AddSubtree(representative);
1194          }
1195        } else if(firstNode is FactorVariableTreeNode) {
1196          var representative = (FactorVariableTreeNode)firstNode;
1197          foreach(var node in variableNodeGroup.Skip(1).Cast<FactorVariableTreeNode>()) {
1198            for(int j = 0; j < representative.Weights.Length; j++) {
1199              representative.Weights[j] *= node.Weights[j];
1200            }
1201          }
1202          for(int j = 0; j < representative.Weights.Length; j++) {
1203            representative.Weights[j] *= constantProduct;
1204          }
1205          constantProduct = 1.0;
1206          // if the product already contains a factor it is not necessary to multiply a constant below
1207          prod.AddSubtree(representative);
1208        }
1209      }
1210
1211      foreach(var unchangedSubtree in unchangedSubtrees)
1212        prod.AddSubtree(unchangedSubtree);
1213
1214      if(!constantProduct.IsAlmost(1.0)) {
1215        prod.AddSubtree(MakeConstant(constantProduct));
1216      }
1217    }
1218
1219
1220    /// <summary>
1221    /// x => x * -1
1222    /// Doesn't create new trees and manipulates x
1223    /// </summary>
1224    /// <param name="x"></param>
1225    /// <returns>-x</returns>
1226    private ISymbolicExpressionTreeNode Negate(ISymbolicExpressionTreeNode x) {
1227      if(IsConstant(x)) {
1228        ((ConstantTreeNode)x).Value *= -1;
1229      } else if(IsVariableBase(x)) {
1230        var variableTree = (VariableTreeNodeBase)x;
1231        variableTree.Weight *= -1.0;
1232      } else if(IsFactor(x)) {
1233        var factorNode = (FactorVariableTreeNode)x;
1234        for(int i = 0; i < factorNode.Weights.Length; i++) factorNode.Weights[i] *= -1;
1235      } else if(IsBinFactor(x)) {
1236        var factorNode = (BinaryFactorVariableTreeNode)x;
1237        factorNode.Weight *= -1;
1238      } else if(IsAddition(x)) {
1239        // (x0 + x1 + .. + xn) * -1 => (-x0 + -x1 + .. + -xn)       
1240        var subtrees = new List<ISymbolicExpressionTreeNode>(x.Subtrees);
1241        while(x.Subtrees.Any()) x.RemoveSubtree(0);
1242        foreach(var subtree in subtrees) {
1243          x.AddSubtree(Negate(subtree));
1244        }
1245      } else if(IsMultiplication(x) || IsDivision(x)) {
1246        // x0 * x1 * .. * xn * -1 => x0 * x1 * .. * -xn
1247        var lastSubTree = x.Subtrees.Last();
1248        x.RemoveSubtree(x.SubtreeCount - 1);
1249        x.AddSubtree(Negate(lastSubTree)); // last is maybe a constant, prefer to negate the constant
1250      } else {
1251        // any other function
1252        return MakeProduct(x, MakeConstant(-1));
1253      }
1254      return x;
1255    }
1256
1257    /// <summary>
1258    /// x => 1/x
1259    /// Doesn't create new trees and manipulates x
1260    /// </summary>
1261    /// <param name="x"></param>
1262    /// <returns></returns>
1263    private ISymbolicExpressionTreeNode Invert(ISymbolicExpressionTreeNode x) {
1264      if(IsConstant(x)) {
1265        return MakeConstant(1.0 / ((ConstantTreeNode)x).Value);
1266      } else if(IsFactor(x)) {
1267        var factorNode = (FactorVariableTreeNode)x;
1268        for(int i = 0; i < factorNode.Weights.Length; i++) factorNode.Weights[i] = 1.0 / factorNode.Weights[i];
1269        return factorNode;
1270      } else if(IsDivision(x)) {
1271        return MakeFraction(x.GetSubtree(1), x.GetSubtree(0));
1272      } else {
1273        // any other function
1274        return MakeFraction(MakeConstant(1), x);
1275      }
1276    }
1277
1278    private ISymbolicExpressionTreeNode MakeConstant(double value) {
1279      ConstantTreeNode constantTreeNode = (ConstantTreeNode)(constSymbol.CreateTreeNode());
1280      constantTreeNode.Value = value;
1281      return constantTreeNode;
1282    }
1283
1284    private ISymbolicExpressionTreeNode MakeFactor(FactorVariable sy, string variableName, IEnumerable<double> weights) {
1285      var tree = (FactorVariableTreeNode)sy.CreateTreeNode();
1286      tree.VariableName = variableName;
1287      tree.Weights = weights.ToArray();
1288      return tree;
1289    }
1290    private ISymbolicExpressionTreeNode MakeBinFactor(BinaryFactorVariable sy, string variableName, string variableValue, double weight) {
1291      var tree = (BinaryFactorVariableTreeNode)sy.CreateTreeNode();
1292      tree.VariableName = variableName;
1293      tree.VariableValue = variableValue;
1294      tree.Weight = weight;
1295      return tree;
1296    }
1297
1298
1299    #endregion
1300  }
1301}
Note: See TracBrowser for help on using the repository browser.