source: branches/2915-AbsoluteSymbol/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Converters/TreeSimplifier.cs @ 16240

Last change on this file since 16240 was 16240, checked in by gkronber, 10 months ago

#2915: merged changes in the trunk up to current HEAD (r15951:16232) into the branch

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