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

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

#2650: extended simplifier to pass all new unit tests for factors and binary factors

File size: 57.1 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        // cos(0) = 1 see similar case for Exp(binfactor)
662        return MakeSum(MakeBinFactor(binFactor.Symbol, binFactor.VariableName, binFactor.VariableValue, Math.Cos(binFactor.Weight) - 1),
663          MakeConstant(1.0));
664      } else {
665        var cosNode = cosineSymbol.CreateTreeNode();
666        cosNode.AddSubtree(node);
667        return cosNode;
668      }
669    }
670
671    private ISymbolicExpressionTreeNode MakeExp(ISymbolicExpressionTreeNode node) {
672      if(IsConstant(node)) {
673        var constT = node as ConstantTreeNode;
674        return MakeConstant(Math.Exp(constT.Value));
675      } else if(IsFactor(node)) {
676        var factNode = node as FactorVariableTreeNode;
677        return MakeFactor(factNode.Symbol, factNode.VariableName, factNode.Weights.Select(w => Math.Exp(w)));
678      } else if(IsBinFactor(node)) {
679        // exp( binfactor w val=a) = if(val=a) exp(w) else exp(0) = binfactor( (exp(w) - 1) val a) + 1
680        var binFactor = node as BinaryFactorVariableTreeNode;
681        return
682          MakeSum(MakeBinFactor(binFactor.Symbol, binFactor.VariableName, binFactor.VariableValue, Math.Exp(binFactor.Weight) - 1), MakeConstant(1.0));
683      } else if(IsLog(node)) {
684        return node.GetSubtree(0);
685      } else if(IsAddition(node)) {
686        return node.Subtrees.Select(s => MakeExp(s)).Aggregate((s, t) => MakeProduct(s, t));
687      } else if(IsSubtraction(node)) {
688        return node.Subtrees.Select(s => MakeExp(s)).Aggregate((s, t) => MakeProduct(s, Negate(t)));
689      } else {
690        var expNode = expSymbol.CreateTreeNode();
691        expNode.AddSubtree(node);
692        return expNode;
693      }
694    }
695    private ISymbolicExpressionTreeNode MakeLog(ISymbolicExpressionTreeNode node) {
696      if(IsConstant(node)) {
697        var constT = node as ConstantTreeNode;
698        return MakeConstant(Math.Log(constT.Value));
699      } else if(IsFactor(node)) {
700        var factNode = node as FactorVariableTreeNode;
701        return MakeFactor(factNode.Symbol, factNode.VariableName, factNode.Weights.Select(w => Math.Log(w)));
702      } else if(IsExp(node)) {
703        return node.GetSubtree(0);
704      } else if(IsSquareRoot(node)) {
705        return MakeFraction(MakeLog(node.GetSubtree(0)), MakeConstant(2.0));
706      } else {
707        var logNode = logSymbol.CreateTreeNode();
708        logNode.AddSubtree(node);
709        return logNode;
710      }
711    }
712
713    private ISymbolicExpressionTreeNode MakeSquare(ISymbolicExpressionTreeNode node) {
714      if(IsConstant(node)) {
715        var constT = node as ConstantTreeNode;
716        return MakeConstant(constT.Value * constT.Value);
717      } else if(IsFactor(node)) {
718        var factNode = node as FactorVariableTreeNode;
719        return MakeFactor(factNode.Symbol, factNode.VariableName, factNode.Weights.Select(w => w * w));
720      } else if(IsBinFactor(node)) {
721        var binFactor = node as BinaryFactorVariableTreeNode;
722        return MakeBinFactor(binFactor.Symbol, binFactor.VariableName, binFactor.VariableValue, binFactor.Weight * binFactor.Weight);
723      } else if(IsSquareRoot(node)) {
724        return node.GetSubtree(0);
725      } else {
726        var sqrNode = sqrSymbol.CreateTreeNode();
727        sqrNode.AddSubtree(node);
728        return sqrNode;
729      }
730    }
731
732    private ISymbolicExpressionTreeNode MakeSquareRoot(ISymbolicExpressionTreeNode node) {
733      if(IsConstant(node)) {
734        var constT = node as ConstantTreeNode;
735        return MakeConstant(Math.Sqrt(constT.Value));
736      } else if(IsFactor(node)) {
737        var factNode = node as FactorVariableTreeNode;
738        return MakeFactor(factNode.Symbol, factNode.VariableName, factNode.Weights.Select(w => Math.Sqrt(w)));
739      } else if(IsBinFactor(node)) {
740        var binFactor = node as BinaryFactorVariableTreeNode;
741        return MakeBinFactor(binFactor.Symbol, binFactor.VariableName, binFactor.VariableValue, Math.Sqrt(binFactor.Weight));
742      } else if(IsSquare(node)) {
743        return node.GetSubtree(0);
744      } else {
745        var sqrtNode = sqrtSymbol.CreateTreeNode();
746        sqrtNode.AddSubtree(node);
747        return sqrtNode;
748      }
749    }
750
751    private ISymbolicExpressionTreeNode MakeRoot(ISymbolicExpressionTreeNode a, ISymbolicExpressionTreeNode b) {
752      if(IsConstant(a) && IsConstant(b)) {
753        var constA = a as ConstantTreeNode;
754        var constB = b as ConstantTreeNode;
755        return MakeConstant(Math.Pow(constA.Value, 1.0 / Math.Round(constB.Value)));
756      } else if(IsFactor(a) && IsConstant(b)) {
757        var factNode = a as FactorVariableTreeNode;
758        var constNode = b as ConstantTreeNode;
759        return MakeFactor(factNode.Symbol, factNode.VariableName,
760          factNode.Weights.Select(w => Math.Pow(w, 1.0 / Math.Round(constNode.Value))));
761      } else if(IsBinFactor(a) && IsConstant(b)) {
762        var binFactor = a as BinaryFactorVariableTreeNode;
763        var constNode = b as ConstantTreeNode;
764        return MakeBinFactor(binFactor.Symbol, binFactor.VariableName, binFactor.VariableValue, Math.Pow(binFactor.Weight, 1.0 / Math.Round(constNode.Value)));
765      } else if(IsConstant(a) && IsFactor(b)) {
766        var constNode = a as ConstantTreeNode;
767        var factNode = b as FactorVariableTreeNode;
768        return MakeFactor(factNode.Symbol, factNode.VariableName, factNode.Weights.Select(w => Math.Pow(constNode.Value, 1.0 / Math.Round(w))));
769      } else if(IsConstant(a) && IsBinFactor(b)) {
770        var constNode = a as ConstantTreeNode;
771        var factNode = b as BinaryFactorVariableTreeNode;
772        return MakeBinFactor(factNode.Symbol, factNode.VariableName, factNode.VariableValue, Math.Pow(constNode.Value, 1.0 / Math.Round(factNode.Weight)));
773      } else if(IsFactor(a) && IsFactor(b) && AreSameTypeAndVariable(a, b)) {
774        var node0 = a as FactorVariableTreeNode;
775        var node1 = b as FactorVariableTreeNode;
776        return MakeFactor(node0.Symbol, node0.VariableName, node0.Weights.Zip(node1.Weights, (u, v) => Math.Pow(u, 1.0 / Math.Round(v))));
777      } else if(IsConstant(b)) {
778        var constB = b as ConstantTreeNode;
779        var constBValue = Math.Round(constB.Value);
780        if(constBValue.IsAlmost(1.0)) {
781          return a;
782        } else if(constBValue.IsAlmost(0.0)) {
783          return MakeConstant(1.0);
784        } else if(constBValue.IsAlmost(-1.0)) {
785          return MakeFraction(MakeConstant(1.0), a);
786        } else if(constBValue < 0) {
787          var rootNode = rootSymbol.CreateTreeNode();
788          rootNode.AddSubtree(a);
789          rootNode.AddSubtree(MakeConstant(-1.0 * constBValue));
790          return MakeFraction(MakeConstant(1.0), rootNode);
791        } else {
792          var rootNode = rootSymbol.CreateTreeNode();
793          rootNode.AddSubtree(a);
794          rootNode.AddSubtree(MakeConstant(constBValue));
795          return rootNode;
796        }
797      } else {
798        var rootNode = rootSymbol.CreateTreeNode();
799        rootNode.AddSubtree(a);
800        rootNode.AddSubtree(b);
801        return rootNode;
802      }
803    }
804
805
806    private ISymbolicExpressionTreeNode MakePower(ISymbolicExpressionTreeNode a, ISymbolicExpressionTreeNode b) {
807      if(IsConstant(a) && IsConstant(b)) {
808        var constA = a as ConstantTreeNode;
809        var constB = b as ConstantTreeNode;
810        return MakeConstant(Math.Pow(constA.Value, Math.Round(constB.Value)));
811      } else if(IsFactor(a) && IsConstant(b)) {
812        var factNode = a as FactorVariableTreeNode;
813        var constNode = b as ConstantTreeNode;
814        return MakeFactor(factNode.Symbol, factNode.VariableName, factNode.Weights.Select(w => Math.Pow(w, Math.Round(constNode.Value))));
815      } else if(IsBinFactor(a) && IsConstant(b)) {
816        var binFactor = a as BinaryFactorVariableTreeNode;
817        var constNode = b as ConstantTreeNode;
818        return MakeBinFactor(binFactor.Symbol, binFactor.VariableName, binFactor.VariableValue, Math.Pow(binFactor.Weight, Math.Round(constNode.Value)));
819      } else if(IsConstant(a) && IsFactor(b)) {
820        var constNode = a as ConstantTreeNode;
821        var factNode = b as FactorVariableTreeNode;
822        return MakeFactor(factNode.Symbol, factNode.VariableName, factNode.Weights.Select(w => Math.Pow(constNode.Value, Math.Round(w))));
823      } else if(IsConstant(a) && IsBinFactor(b)) {
824        var constNode = a as ConstantTreeNode;
825        var factNode = b as BinaryFactorVariableTreeNode;
826        return MakeBinFactor(factNode.Symbol, factNode.VariableName, factNode.VariableValue, Math.Pow(constNode.Value, Math.Round(factNode.Weight)));
827      } else if(IsFactor(a) && IsFactor(b) && AreSameTypeAndVariable(a, b)) {
828        var node0 = a as FactorVariableTreeNode;
829        var node1 = b as FactorVariableTreeNode;
830        return MakeFactor(node0.Symbol, node0.VariableName, node0.Weights.Zip(node1.Weights, (u, v) => Math.Pow(u, Math.Round(v))));
831      } else if(IsConstant(b)) {
832        var constB = b as ConstantTreeNode;
833        double exponent = Math.Round(constB.Value);
834        if(exponent.IsAlmost(0.0)) {
835          return MakeConstant(1.0);
836        } else if(exponent.IsAlmost(1.0)) {
837          return a;
838        } else if(exponent.IsAlmost(-1.0)) {
839          return MakeFraction(MakeConstant(1.0), a);
840        } else if(exponent < 0) {
841          var powNode = powSymbol.CreateTreeNode();
842          powNode.AddSubtree(a);
843          powNode.AddSubtree(MakeConstant(-1.0 * exponent));
844          return MakeFraction(MakeConstant(1.0), powNode);
845        } else {
846          var powNode = powSymbol.CreateTreeNode();
847          powNode.AddSubtree(a);
848          powNode.AddSubtree(MakeConstant(exponent));
849          return powNode;
850        }
851      } else {
852        var powNode = powSymbol.CreateTreeNode();
853        powNode.AddSubtree(a);
854        powNode.AddSubtree(b);
855        return powNode;
856      }
857    }
858
859
860    // MakeFraction, MakeProduct and MakeSum take two already simplified trees and create a new simplified tree
861    private ISymbolicExpressionTreeNode MakeFraction(ISymbolicExpressionTreeNode a, ISymbolicExpressionTreeNode b) {
862      if(IsConstant(a) && IsConstant(b)) {
863        // fold constants
864        return MakeConstant(((ConstantTreeNode)a).Value / ((ConstantTreeNode)b).Value);
865      } else if((IsConstant(a) && !((ConstantTreeNode)a).Value.IsAlmost(1.0))) {
866        return MakeFraction(MakeConstant(1.0), MakeProduct(b, Invert(a)));
867      } else if(IsVariableBase(a) && IsConstant(b)) {
868        // merge constant values into variable weights
869        var constB = ((ConstantTreeNode)b).Value;
870        ((VariableTreeNodeBase)a).Weight /= constB;
871        return a;
872      } else if(IsFactor(a) && IsConstant(b)) {
873        var factNode = a as FactorVariableTreeNode;
874        var constNode = b as ConstantTreeNode;
875        return MakeFactor(factNode.Symbol, factNode.VariableName, factNode.Weights.Select(w => w / constNode.Value));
876      } else if(IsBinFactor(a) && IsConstant(b)) {
877        var factNode = a as BinaryFactorVariableTreeNode;
878        var constNode = b as ConstantTreeNode;
879        return MakeBinFactor(factNode.Symbol, factNode.VariableName, factNode.VariableValue, factNode.Weight / constNode.Value);
880      } else if(IsFactor(a) && IsFactor(b) && AreSameTypeAndVariable(a, b)) {
881        var node0 = a as FactorVariableTreeNode;
882        var node1 = b as FactorVariableTreeNode;
883        return MakeFactor(node0.Symbol, node0.VariableName, node0.Weights.Zip(node1.Weights, (u, v) => u / v));
884      } else if(IsFactor(a) && IsBinFactor(b) && ((IVariableTreeNode)a).VariableName == ((IVariableTreeNode)b).VariableName) {
885        var node0 = a as FactorVariableTreeNode;
886        var node1 = b as BinaryFactorVariableTreeNode;
887        var varValues = node0.Symbol.GetVariableValues(node0.VariableName).ToArray();
888        var wi = Array.IndexOf(varValues, node1.VariableValue);
889        if(wi < 0) throw new ArgumentException();
890        var newWeighs = new double[varValues.Length];
891        node0.Weights.CopyTo(newWeighs, 0);
892        for(int i = 0; i < newWeighs.Length; i++)
893          if(wi == i) newWeighs[i] /= node1.Weight;
894          else newWeighs[i] /= 0.0;
895        return MakeFactor(node0.Symbol, node0.VariableName, newWeighs);
896      } else if(IsFactor(a)) {
897        return MakeFraction(MakeConstant(1.0), MakeProduct(b, Invert(a)));
898      } else if(IsVariableBase(a) && IsVariableBase(b) && AreSameTypeAndVariable(a, b) && !IsBinFactor(b)) {
899        // cancel variables (not allowed for bin factors because of division by zero)
900        var aVar = a as VariableTreeNode;
901        var bVar = b as VariableTreeNode;
902        return MakeConstant(aVar.Weight / bVar.Weight);
903      } else if(IsAddition(a) && IsConstant(b)) {
904        return a.Subtrees
905          .Select(x => GetSimplifiedTree(x))
906          .Select(x => MakeFraction(x, b))
907          .Aggregate((c, d) => MakeSum(c, d));
908      } else if(IsMultiplication(a) && IsConstant(b)) {
909        return MakeProduct(a, Invert(b));
910      } else if(IsDivision(a) && IsConstant(b)) {
911        // (a1 / a2) / c => (a1 / (a2 * c))
912        return MakeFraction(a.GetSubtree(0), MakeProduct(a.GetSubtree(1), b));
913      } else if(IsDivision(a) && IsDivision(b)) {
914        // (a1 / a2) / (b1 / b2) =>
915        return MakeFraction(MakeProduct(a.GetSubtree(0), b.GetSubtree(1)), MakeProduct(a.GetSubtree(1), b.GetSubtree(0)));
916      } else if(IsDivision(a)) {
917        // (a1 / a2) / b => (a1 / (a2 * b))
918        return MakeFraction(a.GetSubtree(0), MakeProduct(a.GetSubtree(1), b));
919      } else if(IsDivision(b)) {
920        // a / (b1 / b2) => (a * b2) / b1
921        return MakeFraction(MakeProduct(a, b.GetSubtree(1)), b.GetSubtree(0));
922      } else {
923        var div = divSymbol.CreateTreeNode();
924        div.AddSubtree(a);
925        div.AddSubtree(b);
926        return div;
927      }
928    }
929
930    private ISymbolicExpressionTreeNode MakeSum(ISymbolicExpressionTreeNode a, ISymbolicExpressionTreeNode b) {
931      if(IsConstant(a) && IsConstant(b)) {
932        // fold constants
933        ((ConstantTreeNode)a).Value += ((ConstantTreeNode)b).Value;
934        return a;
935      } else if(IsConstant(a)) {
936        // c + x => x + c
937        // b is not constant => make sure constant is on the right
938        return MakeSum(b, a);
939      } else if(IsConstant(b) && ((ConstantTreeNode)b).Value.IsAlmost(0.0)) {
940        // x + 0 => x
941        return a;
942      } else if(IsFactor(a) && IsConstant(b)) {
943        var factNode = a as FactorVariableTreeNode;
944        var constNode = b as ConstantTreeNode;
945        return MakeFactor(factNode.Symbol, factNode.VariableName, factNode.Weights.Select((w) => w + constNode.Value));
946      } else if(IsFactor(a) && IsFactor(b) && AreSameTypeAndVariable(a, b)) {
947        var node0 = a as FactorVariableTreeNode;
948        var node1 = b as FactorVariableTreeNode;
949        return MakeFactor(node0.Symbol, node0.VariableName, node0.Weights.Zip(node1.Weights, (u, v) => u + v));
950      } else if(IsBinFactor(a) && IsFactor(b)) {
951        return MakeSum(b, a);
952      } else if(IsFactor(a) && IsBinFactor(b) &&
953        ((IVariableTreeNode)a).VariableName == ((IVariableTreeNode)b).VariableName) {
954        var node0 = a as FactorVariableTreeNode;
955        var node1 = b as BinaryFactorVariableTreeNode;
956        var varValues = node0.Symbol.GetVariableValues(node0.VariableName).ToArray();
957        var wi = Array.IndexOf(varValues, node1.VariableValue);
958        if(wi < 0) throw new ArgumentException();
959        var newWeighs = new double[varValues.Length];
960        node0.Weights.CopyTo(newWeighs, 0);
961        newWeighs[wi] += node1.Weight;
962        return MakeFactor(node0.Symbol, node0.VariableName, newWeighs);
963      } else if(IsAddition(a) && IsAddition(b)) {
964        // merge additions
965        var add = addSymbol.CreateTreeNode();
966        // add all sub trees except for the last
967        for(int i = 0; i < a.Subtrees.Count() - 1; i++) add.AddSubtree(a.GetSubtree(i));
968        for(int i = 0; i < b.Subtrees.Count() - 1; i++) add.AddSubtree(b.GetSubtree(i));
969        if(IsConstant(a.Subtrees.Last()) && IsConstant(b.Subtrees.Last())) {
970          add.AddSubtree(MakeSum(a.Subtrees.Last(), b.Subtrees.Last()));
971        } else if(IsConstant(a.Subtrees.Last())) {
972          add.AddSubtree(b.Subtrees.Last());
973          add.AddSubtree(a.Subtrees.Last());
974        } else {
975          add.AddSubtree(a.Subtrees.Last());
976          add.AddSubtree(b.Subtrees.Last());
977        }
978        MergeVariablesInSum(add);
979        if(add.Subtrees.Count() == 1) {
980          return add.GetSubtree(0);
981        } else {
982          return add;
983        }
984      } else if(IsAddition(b)) {
985        return MakeSum(b, a);
986      } else if(IsAddition(a) && IsConstant(b)) {
987        // a is an addition and b is a constant => append b to a and make sure the constants are merged
988        var add = addSymbol.CreateTreeNode();
989        // add all sub trees except for the last
990        for(int i = 0; i < a.Subtrees.Count() - 1; i++) add.AddSubtree(a.GetSubtree(i));
991        if(IsConstant(a.Subtrees.Last()))
992          add.AddSubtree(MakeSum(a.Subtrees.Last(), b));
993        else {
994          add.AddSubtree(a.Subtrees.Last());
995          add.AddSubtree(b);
996        }
997        return add;
998      } else if(IsAddition(a)) {
999        // a is already an addition => append b
1000        var add = addSymbol.CreateTreeNode();
1001        add.AddSubtree(b);
1002        foreach(var subtree in a.Subtrees) {
1003          add.AddSubtree(subtree);
1004        }
1005        MergeVariablesInSum(add);
1006        if(add.Subtrees.Count() == 1) {
1007          return add.GetSubtree(0);
1008        } else {
1009          return add;
1010        }
1011      } else {
1012        var add = addSymbol.CreateTreeNode();
1013        add.AddSubtree(a);
1014        add.AddSubtree(b);
1015        MergeVariablesInSum(add);
1016        if(add.Subtrees.Count() == 1) {
1017          return add.GetSubtree(0);
1018        } else {
1019          return add;
1020        }
1021      }
1022    }
1023
1024    // makes sure variable symbols in sums are combined
1025    private void MergeVariablesInSum(ISymbolicExpressionTreeNode sum) {
1026      var subtrees = new List<ISymbolicExpressionTreeNode>(sum.Subtrees);
1027      while(sum.Subtrees.Any()) sum.RemoveSubtree(0);
1028      var groupedVarNodes = from node in subtrees.OfType<IVariableTreeNode>()
1029                            where node.SubtreeCount == 0
1030                            group node by GroupId(node) into g
1031                            select g;
1032      var constant = (from node in subtrees.OfType<ConstantTreeNode>()
1033                      select node.Value).DefaultIfEmpty(0.0).Sum();
1034      var unchangedSubtrees = subtrees.Where(t => t.SubtreeCount > 0 || !(t is IVariableTreeNode) && !(t is ConstantTreeNode));
1035
1036      foreach(var variableNodeGroup in groupedVarNodes) {
1037        var firstNode = variableNodeGroup.First();
1038        if(firstNode is VariableTreeNodeBase) {
1039          var representative = firstNode as VariableTreeNodeBase;
1040          var weightSum = variableNodeGroup.Cast<VariableTreeNodeBase>().Select(t => t.Weight).Sum();
1041          representative.Weight = weightSum;
1042          sum.AddSubtree(representative);
1043        } else if(firstNode is FactorVariableTreeNode) {
1044          var representative = firstNode as FactorVariableTreeNode;
1045          foreach(var node in variableNodeGroup.Skip(1).Cast<FactorVariableTreeNode>()) {
1046            for(int j = 0; j < representative.Weights.Length; j++) {
1047              representative.Weights[j] += node.Weights[j];
1048            }
1049          }
1050          for(int j = 0; j < representative.Weights.Length; j++) {
1051            representative.Weights[j] += constant;
1052          }
1053          sum.AddSubtree(representative);
1054        }
1055      }
1056      foreach(var unchangedSubtree in unchangedSubtrees)
1057        sum.AddSubtree(unchangedSubtree);
1058      if(!constant.IsAlmost(0.0)) {
1059        sum.AddSubtree(MakeConstant(constant));
1060      }
1061    }
1062
1063    // nodes referencing variables can be grouped if they have
1064    private string GroupId(IVariableTreeNode node) {
1065      var binaryFactorNode = node as BinaryFactorVariableTreeNode;
1066      var factorNode = node as FactorVariableTreeNode;
1067      var variableNode = node as VariableTreeNode;
1068      var laggedVarNode = node as LaggedVariableTreeNode;
1069      if(variableNode != null) {
1070        return "var " + variableNode.VariableName;
1071      } else if(binaryFactorNode != null) {
1072        return "binfactor " + binaryFactorNode.VariableName + " " + binaryFactorNode.VariableValue;
1073      } else if(factorNode != null) {
1074        return "factor " + factorNode.VariableName;
1075      } else if(laggedVarNode != null) {
1076        return "lagged " + laggedVarNode.VariableName + " " + laggedVarNode.Lag;
1077      } else {
1078        throw new NotSupportedException();
1079      }
1080    }
1081
1082
1083    private ISymbolicExpressionTreeNode MakeProduct(ISymbolicExpressionTreeNode a, ISymbolicExpressionTreeNode b) {
1084      if(IsConstant(a) && IsConstant(b)) {
1085        // fold constants
1086        ((ConstantTreeNode)a).Value *= ((ConstantTreeNode)b).Value;
1087        return a;
1088      } else if(IsConstant(a)) {
1089        // a * $ => $ * a
1090        return MakeProduct(b, a);
1091      } else if(IsFactor(a) && IsFactor(b) && AreSameTypeAndVariable(a, b)) {
1092        var node0 = a as FactorVariableTreeNode;
1093        var node1 = b as FactorVariableTreeNode;
1094        return MakeFactor(node0.Symbol, node0.VariableName, node0.Weights.Zip(node1.Weights, (u, v) => u * v));
1095      } else if(IsBinFactor(a) && IsBinFactor(b) && AreSameTypeAndVariable(a, b)) {
1096        var node0 = a as BinaryFactorVariableTreeNode;
1097        var node1 = b as BinaryFactorVariableTreeNode;
1098        return MakeBinFactor(node0.Symbol, node0.VariableName, node0.VariableValue, node0.Weight * node1.Weight);
1099      } else if(IsFactor(a) && IsConstant(b)) {
1100        var node0 = a as FactorVariableTreeNode;
1101        var node1 = b as ConstantTreeNode;
1102        return MakeFactor(node0.Symbol, node0.VariableName, node0.Weights.Select(w => w * node1.Value));
1103      } else if(IsBinFactor(a) && IsConstant(b)) {
1104        var node0 = a as BinaryFactorVariableTreeNode;
1105        var node1 = b as ConstantTreeNode;
1106        return MakeBinFactor(node0.Symbol, node0.VariableName, node0.VariableValue, node0.Weight * node1.Value);
1107      } else if(IsBinFactor(a) && IsFactor(b)) {
1108        return MakeProduct(b, a);
1109      } else if(IsFactor(a) && IsBinFactor(b) &&
1110        ((IVariableTreeNode)a).VariableName == ((IVariableTreeNode)b).VariableName) {
1111        var node0 = a as FactorVariableTreeNode;
1112        var node1 = b as BinaryFactorVariableTreeNode;
1113        var varValues = node0.Symbol.GetVariableValues(node0.VariableName).ToArray();
1114        var wi = Array.IndexOf(varValues, node1.VariableValue);
1115        if(wi < 0) throw new ArgumentException();
1116        return MakeBinFactor(node1.Symbol, node1.VariableName, node1.VariableValue, node1.Weight * node0.Weights[wi]);
1117      } else if(IsConstant(b) && ((ConstantTreeNode)b).Value.IsAlmost(1.0)) {
1118        // $ * 1.0 => $
1119        return a;
1120      } else if(IsConstant(b) && IsVariableBase(a)) {
1121        // multiply constants into variables weights
1122        ((VariableTreeNodeBase)a).Weight *= ((ConstantTreeNode)b).Value;
1123        return a;
1124      } else if(IsConstant(b) && IsAddition(a) ||
1125          IsFactor(b) && IsAddition(a)) {
1126        // multiply constants into additions
1127        return a.Subtrees.Select(x => MakeProduct(x, b)).Aggregate((c, d) => MakeSum(c, d));
1128      } else if(IsDivision(a) && IsDivision(b)) {
1129        // (a1 / a2) * (b1 / b2) => (a1 * b1) / (a2 * b2)
1130        return MakeFraction(MakeProduct(a.GetSubtree(0), b.GetSubtree(0)), MakeProduct(a.GetSubtree(1), b.GetSubtree(1)));
1131      } else if(IsDivision(a)) {
1132        // (a1 / a2) * b => (a1 * b) / a2
1133        return MakeFraction(MakeProduct(a.GetSubtree(0), b), a.GetSubtree(1));
1134      } else if(IsDivision(b)) {
1135        // a * (b1 / b2) => (b1 * a) / b2
1136        return MakeFraction(MakeProduct(b.GetSubtree(0), a), b.GetSubtree(1));
1137      } else if(IsMultiplication(a) && IsMultiplication(b)) {
1138        // merge multiplications (make sure constants are merged)
1139        var mul = mulSymbol.CreateTreeNode();
1140        for(int i = 0; i < a.Subtrees.Count(); i++) mul.AddSubtree(a.GetSubtree(i));
1141        for(int i = 0; i < b.Subtrees.Count(); i++) mul.AddSubtree(b.GetSubtree(i));
1142        MergeVariablesAndConstantsInProduct(mul);
1143        return mul;
1144      } else if(IsMultiplication(b)) {
1145        return MakeProduct(b, a);
1146      } else if(IsMultiplication(a)) {
1147        // a is already an multiplication => append b
1148        a.AddSubtree(b);
1149        MergeVariablesAndConstantsInProduct(a);
1150        return a;
1151      } else {
1152        var mul = mulSymbol.CreateTreeNode();
1153        mul.AddSubtree(a);
1154        mul.AddSubtree(b);
1155        MergeVariablesAndConstantsInProduct(mul);
1156        return mul;
1157      }
1158    }
1159
1160    #endregion
1161
1162    #region helper functions
1163
1164    private bool ContainsVariableCondition(ISymbolicExpressionTreeNode node) {
1165      if(node.Symbol is VariableCondition) return true;
1166      foreach(var subtree in node.Subtrees)
1167        if(ContainsVariableCondition(subtree)) return true;
1168      return false;
1169    }
1170
1171    private ISymbolicExpressionTreeNode AddLagToDynamicNodes(ISymbolicExpressionTreeNode node, int lag) {
1172      var laggedTreeNode = node as ILaggedTreeNode;
1173      var variableNode = node as VariableTreeNode;
1174      var variableConditionNode = node as VariableConditionTreeNode;
1175      if(laggedTreeNode != null)
1176        laggedTreeNode.Lag += lag;
1177      else if(variableNode != null) {
1178        var laggedVariableNode = (LaggedVariableTreeNode)laggedVariableSymbol.CreateTreeNode();
1179        laggedVariableNode.Lag = lag;
1180        laggedVariableNode.VariableName = variableNode.VariableName;
1181        return laggedVariableNode;
1182      } else if(variableConditionNode != null) {
1183        throw new NotSupportedException("Removal of time lags around variable condition symbols is not allowed.");
1184      }
1185      var subtrees = new List<ISymbolicExpressionTreeNode>(node.Subtrees);
1186      while(node.SubtreeCount > 0) node.RemoveSubtree(0);
1187      foreach(var subtree in subtrees) {
1188        node.AddSubtree(AddLagToDynamicNodes(subtree, lag));
1189      }
1190      return node;
1191    }
1192
1193    private bool AreSameTypeAndVariable(ISymbolicExpressionTreeNode a, ISymbolicExpressionTreeNode b) {
1194      return GroupId((IVariableTreeNode)a) == GroupId((IVariableTreeNode)b);
1195    }
1196
1197    // helper to combine the constant factors in products and to combine variables (powers of 2, 3...)
1198    private void MergeVariablesAndConstantsInProduct(ISymbolicExpressionTreeNode prod) {
1199      var subtrees = new List<ISymbolicExpressionTreeNode>(prod.Subtrees);
1200      while(prod.Subtrees.Any()) prod.RemoveSubtree(0);
1201      var groupedVarNodes = from node in subtrees.OfType<IVariableTreeNode>()
1202                            where node.SubtreeCount == 0
1203                            group node by GroupId(node) into g
1204                            orderby g.Count()
1205                            select g;
1206      var constantProduct = (from node in subtrees.OfType<VariableTreeNodeBase>()
1207                             select node.Weight)
1208        .Concat(from node in subtrees.OfType<ConstantTreeNode>()
1209                select node.Value)
1210        .DefaultIfEmpty(1.0)
1211        .Aggregate((c1, c2) => c1 * c2);
1212
1213      var unchangedSubtrees = from tree in subtrees
1214                              where tree.SubtreeCount > 0 || !(tree is IVariableTreeNode) && !(tree is ConstantTreeNode)
1215                              select tree;
1216
1217      foreach(var variableNodeGroup in groupedVarNodes) {
1218        var firstNode = variableNodeGroup.First();
1219        if(firstNode is VariableTreeNodeBase) {
1220          var representative = (VariableTreeNodeBase)firstNode;
1221          representative.Weight = 1.0;
1222          if(variableNodeGroup.Count() > 1) {
1223            var poly = mulSymbol.CreateTreeNode();
1224            for(int p = 0; p < variableNodeGroup.Count(); p++) {
1225              poly.AddSubtree((ISymbolicExpressionTreeNode)representative.Clone());
1226            }
1227            prod.AddSubtree(poly);
1228          } else {
1229            prod.AddSubtree(representative);
1230          }
1231        } else if(firstNode is FactorVariableTreeNode) {
1232          var representative = (FactorVariableTreeNode)firstNode;
1233          foreach(var node in variableNodeGroup.Skip(1).Cast<FactorVariableTreeNode>()) {
1234            for(int j = 0; j < representative.Weights.Length; j++) {
1235              representative.Weights[j] *= node.Weights[j];
1236            }
1237          }
1238          for(int j = 0; j < representative.Weights.Length; j++) {
1239            representative.Weights[j] *= constantProduct;
1240          }
1241          constantProduct = 1.0;
1242          // if the product already contains a factor it is not necessary to multiply a constant below
1243          prod.AddSubtree(representative);
1244        }
1245      }
1246
1247      foreach(var unchangedSubtree in unchangedSubtrees)
1248        prod.AddSubtree(unchangedSubtree);
1249
1250      if(!constantProduct.IsAlmost(1.0)) {
1251        prod.AddSubtree(MakeConstant(constantProduct));
1252      }
1253    }
1254
1255
1256    /// <summary>
1257    /// x => x * -1
1258    /// Doesn't create new trees and manipulates x
1259    /// </summary>
1260    /// <param name="x"></param>
1261    /// <returns>-x</returns>
1262    private ISymbolicExpressionTreeNode Negate(ISymbolicExpressionTreeNode x) {
1263      if(IsConstant(x)) {
1264        ((ConstantTreeNode)x).Value *= -1;
1265      } else if(IsVariableBase(x)) {
1266        var variableTree = (VariableTreeNodeBase)x;
1267        variableTree.Weight *= -1.0;
1268      } else if(IsFactor(x)) {
1269        var factorNode = (FactorVariableTreeNode)x;
1270        for(int i = 0; i < factorNode.Weights.Length; i++) factorNode.Weights[i] *= -1;
1271      } else if(IsBinFactor(x)) {
1272        var factorNode = (BinaryFactorVariableTreeNode)x;
1273        factorNode.Weight *= -1;
1274      } else if(IsAddition(x)) {
1275        // (x0 + x1 + .. + xn) * -1 => (-x0 + -x1 + .. + -xn)       
1276        var subtrees = new List<ISymbolicExpressionTreeNode>(x.Subtrees);
1277        while(x.Subtrees.Any()) x.RemoveSubtree(0);
1278        foreach(var subtree in subtrees) {
1279          x.AddSubtree(Negate(subtree));
1280        }
1281      } else if(IsMultiplication(x) || IsDivision(x)) {
1282        // x0 * x1 * .. * xn * -1 => x0 * x1 * .. * -xn
1283        var lastSubTree = x.Subtrees.Last();
1284        x.RemoveSubtree(x.SubtreeCount - 1);
1285        x.AddSubtree(Negate(lastSubTree)); // last is maybe a constant, prefer to negate the constant
1286      } else {
1287        // any other function
1288        return MakeProduct(x, MakeConstant(-1));
1289      }
1290      return x;
1291    }
1292
1293    /// <summary>
1294    /// x => 1/x
1295    /// Doesn't create new trees and manipulates x
1296    /// </summary>
1297    /// <param name="x"></param>
1298    /// <returns></returns>
1299    private ISymbolicExpressionTreeNode Invert(ISymbolicExpressionTreeNode x) {
1300      if(IsConstant(x)) {
1301        return MakeConstant(1.0 / ((ConstantTreeNode)x).Value);
1302      } else if(IsFactor(x)) {
1303        var factorNode = (FactorVariableTreeNode)x;
1304        for(int i = 0; i < factorNode.Weights.Length; i++) factorNode.Weights[i] = 1.0 / factorNode.Weights[i];
1305        return factorNode;
1306      } else if(IsDivision(x)) {
1307        return MakeFraction(x.GetSubtree(1), x.GetSubtree(0));
1308      } else {
1309        // any other function
1310        return MakeFraction(MakeConstant(1), x);
1311      }
1312    }
1313
1314    private ISymbolicExpressionTreeNode MakeConstant(double value) {
1315      ConstantTreeNode constantTreeNode = (ConstantTreeNode)(constSymbol.CreateTreeNode());
1316      constantTreeNode.Value = value;
1317      return constantTreeNode;
1318    }
1319
1320    private ISymbolicExpressionTreeNode MakeFactor(FactorVariable sy, string variableName, IEnumerable<double> weights) {
1321      var tree = (FactorVariableTreeNode)sy.CreateTreeNode();
1322      tree.VariableName = variableName;
1323      tree.Weights = weights.ToArray();
1324      return tree;
1325    }
1326    private ISymbolicExpressionTreeNode MakeBinFactor(BinaryFactorVariable sy, string variableName, string variableValue, double weight) {
1327      var tree = (BinaryFactorVariableTreeNode)sy.CreateTreeNode();
1328      tree.VariableName = variableName;
1329      tree.VariableValue = variableValue;
1330      tree.Weight = weight;
1331      return tree;
1332    }
1333
1334
1335    #endregion
1336  }
1337}
Note: See TracBrowser for help on using the repository browser.