Free cookie consent management tool by TermsFeed Policy Generator

source: branches/3040_VectorBasedGP/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Converters/VectorTreeSimplifier.cs @ 17603

Last change on this file since 17603 was 17603, checked in by pfleck, 4 years ago

#3040

  • Added additive simplification rules for stdev and variance symbols.
  • Extended simplifications of constants to simplification of all scalar-nodes for aggregation symbols.
File size: 82.4 KB
Line 
1#region License Information
2
3/* HeuristicLab
4 * Copyright (C) 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 VectorTreeSimplifier {
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 AnalyticQuotient aqSymbol = new AnalyticQuotient();
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    private static readonly Sum sumSymbol = new Sum();
62    private static readonly Mean meanSymbol = new Mean();
63    private static readonly Length lengthSymbol = new Length();
64    private static readonly StandardDeviation standardDeviationSymbol = new StandardDeviation();
65    private static readonly Variance varianceSymbol = new Variance();
66
67    private readonly SymbolicDataAnalysisExpressionTreeVectorInterpreter interpreter;
68    private readonly IDataAnalysisProblemData problemData;
69
70    public VectorTreeSimplifier(SymbolicDataAnalysisExpressionTreeVectorInterpreter interpreter, IDataAnalysisProblemData problemData) {
71      this.interpreter = interpreter;
72      this.problemData = problemData;
73    }
74
75    public ISymbolicExpressionTree Simplify(ISymbolicExpressionTree originalTree) {
76      var clone = (ISymbolicExpressionTreeNode)originalTree.Root.Clone();
77      // macro expand (initially no argument trees)
78      var macroExpandedTree = MacroExpand(clone, clone.GetSubtree(0), new List<ISymbolicExpressionTreeNode>());
79      ISymbolicExpressionTreeNode rootNode = (new ProgramRootSymbol()).CreateTreeNode();
80      rootNode.AddSubtree(GetSimplifiedTree(macroExpandedTree));
81
82#if DEBUG
83      // check that each node is only referenced once
84      var nodes = rootNode.IterateNodesPrefix().ToArray();
85      foreach (var n in nodes) if (nodes.Count(ni => ni == n) > 1) throw new InvalidOperationException();
86#endif
87      return new SymbolicExpressionTree(rootNode);
88    }
89
90    // the argumentTrees list contains already expanded trees used as arguments for invocations
91    private static ISymbolicExpressionTreeNode MacroExpand(ISymbolicExpressionTreeNode root, ISymbolicExpressionTreeNode node,
92      IList<ISymbolicExpressionTreeNode> argumentTrees) {
93      List<ISymbolicExpressionTreeNode> subtrees = new List<ISymbolicExpressionTreeNode>(node.Subtrees);
94      while (node.SubtreeCount > 0) node.RemoveSubtree(0);
95      if (node.Symbol is InvokeFunction) {
96        var invokeSym = node.Symbol as InvokeFunction;
97        var defunNode = FindFunctionDefinition(root, invokeSym.FunctionName);
98        var macroExpandedArguments = new List<ISymbolicExpressionTreeNode>();
99        foreach (var subtree in subtrees) {
100          macroExpandedArguments.Add(MacroExpand(root, subtree, argumentTrees));
101        }
102        return MacroExpand(root, defunNode, macroExpandedArguments);
103      } else if (node.Symbol is Argument) {
104        var argSym = node.Symbol as Argument;
105        // return the correct argument sub-tree (already macro-expanded)
106        return (SymbolicExpressionTreeNode)argumentTrees[argSym.ArgumentIndex].Clone();
107      } else {
108        // recursive application
109        foreach (var subtree in subtrees) {
110          node.AddSubtree(MacroExpand(root, subtree, argumentTrees));
111        }
112        return node;
113      }
114    }
115
116    private static ISymbolicExpressionTreeNode FindFunctionDefinition(ISymbolicExpressionTreeNode root, string functionName) {
117      foreach (var subtree in root.Subtrees.OfType<DefunTreeNode>()) {
118        if (subtree.FunctionName == functionName) return subtree.GetSubtree(0);
119      }
120
121      throw new ArgumentException("Definition of function " + functionName + " not found.");
122    }
123
124    #region symbol predicates
125
126    // arithmetic
127    private static bool IsDivision(ISymbolicExpressionTreeNode node) {
128      return node.Symbol is Division;
129    }
130
131    private static bool IsMultiplication(ISymbolicExpressionTreeNode node) {
132      return node.Symbol is Multiplication;
133    }
134
135    private static bool IsSubtraction(ISymbolicExpressionTreeNode node) {
136      return node.Symbol is Subtraction;
137    }
138
139    private static bool IsAddition(ISymbolicExpressionTreeNode node) {
140      return node.Symbol is Addition;
141    }
142
143    private static bool IsAverage(ISymbolicExpressionTreeNode node) {
144      return node.Symbol is Average;
145    }
146
147    private static bool IsAbsolute(ISymbolicExpressionTreeNode node) {
148      return node.Symbol is Absolute;
149    }
150
151    // exponential
152    private static bool IsLog(ISymbolicExpressionTreeNode node) {
153      return node.Symbol is Logarithm;
154    }
155
156    private static bool IsExp(ISymbolicExpressionTreeNode node) {
157      return node.Symbol is Exponential;
158    }
159
160    private static bool IsRoot(ISymbolicExpressionTreeNode node) {
161      return node.Symbol is Root;
162    }
163
164    private static bool IsSquare(ISymbolicExpressionTreeNode node) {
165      return node.Symbol is Square;
166    }
167
168    private static bool IsSquareRoot(ISymbolicExpressionTreeNode node) {
169      return node.Symbol is SquareRoot;
170    }
171
172    private static bool IsCube(ISymbolicExpressionTreeNode node) {
173      return node.Symbol is Cube;
174    }
175
176    private static bool IsCubeRoot(ISymbolicExpressionTreeNode node) {
177      return node.Symbol is CubeRoot;
178    }
179
180    private static bool IsPower(ISymbolicExpressionTreeNode node) {
181      return node.Symbol is Power;
182    }
183
184    // trigonometric
185    private static bool IsSine(ISymbolicExpressionTreeNode node) {
186      return node.Symbol is Sine;
187    }
188
189    private static bool IsCosine(ISymbolicExpressionTreeNode node) {
190      return node.Symbol is Cosine;
191    }
192
193    private static bool IsTangent(ISymbolicExpressionTreeNode node) {
194      return node.Symbol is Tangent;
195    }
196
197    private static bool IsAnalyticalQuotient(ISymbolicExpressionTreeNode node) {
198      return node.Symbol is AnalyticQuotient;
199    }
200
201    // boolean
202    private static bool IsIfThenElse(ISymbolicExpressionTreeNode node) {
203      return node.Symbol is IfThenElse;
204    }
205
206    private static bool IsAnd(ISymbolicExpressionTreeNode node) {
207      return node.Symbol is And;
208    }
209
210    private static bool IsOr(ISymbolicExpressionTreeNode node) {
211      return node.Symbol is Or;
212    }
213
214    private static bool IsNot(ISymbolicExpressionTreeNode node) {
215      return node.Symbol is Not;
216    }
217
218    // comparison
219    private static bool IsGreaterThan(ISymbolicExpressionTreeNode node) {
220      return node.Symbol is GreaterThan;
221    }
222
223    private static bool IsLessThan(ISymbolicExpressionTreeNode node) {
224      return node.Symbol is LessThan;
225    }
226
227    private static bool IsBoolean(ISymbolicExpressionTreeNode node) {
228      return
229        node.Symbol is GreaterThan ||
230        node.Symbol is LessThan ||
231        node.Symbol is And ||
232        node.Symbol is Or;
233    }
234
235    // terminals
236    private static bool IsVariable(ISymbolicExpressionTreeNode node) {
237      return node.Symbol is Variable;
238    }
239
240    private static bool IsVariableBase(ISymbolicExpressionTreeNode node) {
241      return node is VariableTreeNodeBase;
242    }
243
244    private static bool IsFactor(ISymbolicExpressionTreeNode node) {
245      return node is FactorVariableTreeNode;
246    }
247
248    private static bool IsBinFactor(ISymbolicExpressionTreeNode node) {
249      return node is BinaryFactorVariableTreeNode;
250    }
251
252    private static bool IsConstant(ISymbolicExpressionTreeNode node) {
253      return node.Symbol is Constant;
254    }
255
256    // dynamic
257    private static bool IsTimeLag(ISymbolicExpressionTreeNode node) {
258      return node.Symbol is TimeLag;
259    }
260
261    private static bool IsIntegral(ISymbolicExpressionTreeNode node) {
262      return node.Symbol is Integral;
263    }
264
265    private static bool IsSum(ISymbolicExpressionTreeNode node) {
266      return node.Symbol is Sum;
267    }
268
269    private static bool IsMean(ISymbolicExpressionTreeNode node) {
270      return node.Symbol is Mean;
271    }
272
273    private static bool IsLength(ISymbolicExpressionTreeNode node) {
274      return node.Symbol is Length;
275    }
276
277    private static bool IsStandardDeviation(ISymbolicExpressionTreeNode node) {
278      return node.Symbol is StandardDeviation;
279    }
280
281    private static bool IsVariance(ISymbolicExpressionTreeNode node) {
282      return node.Symbol is Variance;
283    }
284    #endregion
285
286    #region type predicates
287    public bool IsScalarNode(ISymbolicExpressionTreeNode node) {
288      var results = interpreter.EvaluateNode(node, problemData.Dataset, problemData.TrainingIndices);
289      return results.All(r => r.IsScalar);
290    }
291    public bool IsVectorNode(ISymbolicExpressionTreeNode node) {
292      var results = interpreter.EvaluateNode(node, problemData.Dataset, problemData.TrainingIndices);
293      return results.All(r => r.IsVector);
294    }
295    #endregion
296
297    /// <summary>
298    /// Creates a new simplified tree
299    /// </summary>
300    /// <param name="original"></param>
301    /// <returns></returns>
302    public ISymbolicExpressionTreeNode GetSimplifiedTree(ISymbolicExpressionTreeNode original) {
303      if (IsConstant(original) || IsVariableBase(original)) {
304        return (ISymbolicExpressionTreeNode)original.Clone();
305      } else if (IsAbsolute(original)) {
306        return SimplifyAbsolute(original);
307      } else if (IsAddition(original)) {
308        return SimplifyAddition(original);
309      } else if (IsSubtraction(original)) {
310        return SimplifySubtraction(original);
311      } else if (IsMultiplication(original)) {
312        return SimplifyMultiplication(original);
313      } else if (IsDivision(original)) {
314        return SimplifyDivision(original);
315      } else if (IsAverage(original)) {
316        return SimplifyAverage(original);
317      } else if (IsLog(original)) {
318        return SimplifyLog(original);
319      } else if (IsExp(original)) {
320        return SimplifyExp(original);
321      } else if (IsSquare(original)) {
322        return SimplifySquare(original);
323      } else if (IsSquareRoot(original)) {
324        return SimplifySquareRoot(original);
325      } else if (IsCube(original)) {
326        return SimplifyCube(original);
327      } else if (IsCubeRoot(original)) {
328        return SimplifyCubeRoot(original);
329      } else if (IsPower(original)) {
330        return SimplifyPower(original);
331      } else if (IsRoot(original)) {
332        return SimplifyRoot(original);
333      } else if (IsSine(original)) {
334        return SimplifySine(original);
335      } else if (IsCosine(original)) {
336        return SimplifyCosine(original);
337      } else if (IsTangent(original)) {
338        return SimplifyTangent(original);
339      } else if (IsAnalyticalQuotient(original)) {
340        return SimplifyAnalyticalQuotient(original);
341      } else if (IsIfThenElse(original)) {
342        return SimplifyIfThenElse(original);
343      } else if (IsGreaterThan(original)) {
344        return SimplifyGreaterThan(original);
345      } else if (IsLessThan(original)) {
346        return SimplifyLessThan(original);
347      } else if (IsAnd(original)) {
348        return SimplifyAnd(original);
349      } else if (IsOr(original)) {
350        return SimplifyOr(original);
351      } else if (IsNot(original)) {
352        return SimplifyNot(original);
353      } else if (IsTimeLag(original)) {
354        return SimplifyTimeLag(original);
355      } else if (IsIntegral(original)) {
356        return SimplifyIntegral(original);
357      } else if (IsSum(original)) {
358        return SimplifySumAggregation(original);
359      } else if (IsMean(original)) {
360        return SimplifyMeanAggregation(original);
361      } else if (IsLength(original)) {
362        return SimplifyLengthAggregation(original);
363      } else if (IsStandardDeviation(original)) {
364        return SimplifyStandardDeviationAggregation(original);
365      } else if (IsVariance(original)) {
366        return SimplifyVarianceAggregation(original);
367      } else {
368        return SimplifyAny(original);
369      }
370    }
371
372    #region specific simplification routines
373
374    private ISymbolicExpressionTreeNode SimplifyAny(ISymbolicExpressionTreeNode original) {
375      // can't simplify this function but simplify all subtrees
376      List<ISymbolicExpressionTreeNode> subtrees = new List<ISymbolicExpressionTreeNode>(original.Subtrees);
377      while (original.Subtrees.Count() > 0) original.RemoveSubtree(0);
378      var clone = (SymbolicExpressionTreeNode)original.Clone();
379      List<ISymbolicExpressionTreeNode> simplifiedSubtrees = new List<ISymbolicExpressionTreeNode>();
380      foreach (var subtree in subtrees) {
381        simplifiedSubtrees.Add(GetSimplifiedTree(subtree));
382        original.AddSubtree(subtree);
383      }
384      foreach (var simplifiedSubtree in simplifiedSubtrees) {
385        clone.AddSubtree(simplifiedSubtree);
386      }
387      if (simplifiedSubtrees.TrueForAll(t => IsConstant(t))) {
388        SimplifyConstantExpression(clone);
389      }
390      return clone;
391    }
392
393    private ISymbolicExpressionTreeNode SimplifyConstantExpression(ISymbolicExpressionTreeNode original) {
394      // not yet implemented
395      return original;
396    }
397
398    private ISymbolicExpressionTreeNode SimplifyAverage(ISymbolicExpressionTreeNode original) {
399      if (original.Subtrees.Count() == 1) {
400        return GetSimplifiedTree(original.GetSubtree(0));
401      } else {
402        // simplify expressions x0..xn
403        // make sum(x0..xn) / n
404        var sum = original.Subtrees
405          .Select(GetSimplifiedTree)
406          .Aggregate(MakeSum);
407        return MakeFraction(sum, MakeConstant(original.Subtrees.Count()));
408      }
409    }
410
411    private ISymbolicExpressionTreeNode SimplifyDivision(ISymbolicExpressionTreeNode original) {
412      if (original.Subtrees.Count() == 1) {
413        return Invert(GetSimplifiedTree(original.GetSubtree(0)));
414      } else {
415        // simplify expressions x0..xn
416        // make multiplication (x0 * 1/(x1 * x1 * .. * xn))
417        var first = original.GetSubtree(0);
418        var second = original.GetSubtree(1);
419        var remaining = original.Subtrees.Skip(2);
420        return
421          MakeProduct(GetSimplifiedTree(first),
422            Invert(remaining.Aggregate(GetSimplifiedTree(second), (a, b) => MakeProduct(a, GetSimplifiedTree(b)))));
423      }
424    }
425
426    private ISymbolicExpressionTreeNode SimplifyMultiplication(ISymbolicExpressionTreeNode original) {
427      if (original.Subtrees.Count() == 1) {
428        return GetSimplifiedTree(original.GetSubtree(0));
429      } else {
430        return original.Subtrees
431          .Select(GetSimplifiedTree)
432          .Aggregate(MakeProduct);
433      }
434    }
435
436    private ISymbolicExpressionTreeNode SimplifySubtraction(ISymbolicExpressionTreeNode original) {
437      if (original.Subtrees.Count() == 1) {
438        return Negate(GetSimplifiedTree(original.GetSubtree(0)));
439      } else {
440        // simplify expressions x0..xn
441        // make addition (x0,-x1..-xn)
442        var first = original.Subtrees.First();
443        var remaining = original.Subtrees.Skip(1);
444        return remaining.Aggregate(GetSimplifiedTree(first), (a, b) => MakeSum(a, Negate(GetSimplifiedTree(b))));
445      }
446    }
447
448    private ISymbolicExpressionTreeNode SimplifyAddition(ISymbolicExpressionTreeNode original) {
449      if (original.Subtrees.Count() == 1) {
450        return GetSimplifiedTree(original.GetSubtree(0));
451      } else {
452        // simplify expression x0..xn
453        // make addition (x0..xn)
454        return original.Subtrees
455          .Select(GetSimplifiedTree)
456          .Aggregate(MakeSum);
457      }
458    }
459
460    private ISymbolicExpressionTreeNode SimplifyAbsolute(ISymbolicExpressionTreeNode original) {
461      return MakeAbs(GetSimplifiedTree(original.GetSubtree(0)));
462    }
463
464    private ISymbolicExpressionTreeNode SimplifyNot(ISymbolicExpressionTreeNode original) {
465      return MakeNot(GetSimplifiedTree(original.GetSubtree(0)));
466    }
467
468    private ISymbolicExpressionTreeNode SimplifyOr(ISymbolicExpressionTreeNode original) {
469      return original.Subtrees
470        .Select(GetSimplifiedTree)
471        .Aggregate(MakeOr);
472    }
473
474    private ISymbolicExpressionTreeNode SimplifyAnd(ISymbolicExpressionTreeNode original) {
475      return original.Subtrees
476        .Select(GetSimplifiedTree)
477        .Aggregate(MakeAnd);
478    }
479
480    private ISymbolicExpressionTreeNode SimplifyLessThan(ISymbolicExpressionTreeNode original) {
481      return MakeLessThan(GetSimplifiedTree(original.GetSubtree(0)), GetSimplifiedTree(original.GetSubtree(1)));
482    }
483
484    private ISymbolicExpressionTreeNode SimplifyGreaterThan(ISymbolicExpressionTreeNode original) {
485      return MakeGreaterThan(GetSimplifiedTree(original.GetSubtree(0)), GetSimplifiedTree(original.GetSubtree(1)));
486    }
487
488    private ISymbolicExpressionTreeNode SimplifyIfThenElse(ISymbolicExpressionTreeNode original) {
489      return MakeIfThenElse(GetSimplifiedTree(original.GetSubtree(0)), GetSimplifiedTree(original.GetSubtree(1)),
490        GetSimplifiedTree(original.GetSubtree(2)));
491    }
492
493    private ISymbolicExpressionTreeNode SimplifyTangent(ISymbolicExpressionTreeNode original) {
494      return MakeTangent(GetSimplifiedTree(original.GetSubtree(0)));
495    }
496
497    private ISymbolicExpressionTreeNode SimplifyCosine(ISymbolicExpressionTreeNode original) {
498      return MakeCosine(GetSimplifiedTree(original.GetSubtree(0)));
499    }
500
501    private ISymbolicExpressionTreeNode SimplifySine(ISymbolicExpressionTreeNode original) {
502      return MakeSine(GetSimplifiedTree(original.GetSubtree(0)));
503    }
504
505    private ISymbolicExpressionTreeNode SimplifyExp(ISymbolicExpressionTreeNode original) {
506      return MakeExp(GetSimplifiedTree(original.GetSubtree(0)));
507    }
508
509    private ISymbolicExpressionTreeNode SimplifySquare(ISymbolicExpressionTreeNode original) {
510      return MakeSquare(GetSimplifiedTree(original.GetSubtree(0)));
511    }
512
513    private ISymbolicExpressionTreeNode SimplifySquareRoot(ISymbolicExpressionTreeNode original) {
514      return MakeSquareRoot(GetSimplifiedTree(original.GetSubtree(0)));
515    }
516    private ISymbolicExpressionTreeNode SimplifyCube(ISymbolicExpressionTreeNode original) {
517      return MakeCube(GetSimplifiedTree(original.GetSubtree(0)));
518    }
519
520    private ISymbolicExpressionTreeNode SimplifyCubeRoot(ISymbolicExpressionTreeNode original) {
521      return MakeCubeRoot(GetSimplifiedTree(original.GetSubtree(0)));
522    }
523
524    private ISymbolicExpressionTreeNode SimplifyLog(ISymbolicExpressionTreeNode original) {
525      return MakeLog(GetSimplifiedTree(original.GetSubtree(0)));
526    }
527
528    private ISymbolicExpressionTreeNode SimplifyRoot(ISymbolicExpressionTreeNode original) {
529      return MakeRoot(GetSimplifiedTree(original.GetSubtree(0)), GetSimplifiedTree(original.GetSubtree(1)));
530    }
531
532    private ISymbolicExpressionTreeNode SimplifyPower(ISymbolicExpressionTreeNode original) {
533      return MakePower(GetSimplifiedTree(original.GetSubtree(0)), GetSimplifiedTree(original.GetSubtree(1)));
534    }
535
536    private ISymbolicExpressionTreeNode SimplifyAnalyticalQuotient(ISymbolicExpressionTreeNode original) {
537      return MakeAnalyticalQuotient(GetSimplifiedTree(original.GetSubtree(0)), GetSimplifiedTree(original.GetSubtree(1)));
538    }
539
540    private ISymbolicExpressionTreeNode SimplifyTimeLag(ISymbolicExpressionTreeNode original) {
541      var laggedTreeNode = original as ILaggedTreeNode;
542      var simplifiedSubtree = GetSimplifiedTree(original.GetSubtree(0));
543      if (!ContainsVariableCondition(simplifiedSubtree)) {
544        return AddLagToDynamicNodes(simplifiedSubtree, laggedTreeNode.Lag);
545      } else {
546        return MakeTimeLag(simplifiedSubtree, laggedTreeNode.Lag);
547      }
548    }
549
550    private ISymbolicExpressionTreeNode SimplifyIntegral(ISymbolicExpressionTreeNode original) {
551      var laggedTreeNode = original as ILaggedTreeNode;
552      var simplifiedSubtree = GetSimplifiedTree(original.GetSubtree(0));
553      if (IsConstant(simplifiedSubtree)) {
554        return GetSimplifiedTree(MakeProduct(simplifiedSubtree, MakeConstant(-laggedTreeNode.Lag)));
555      } else {
556        return MakeIntegral(simplifiedSubtree, laggedTreeNode.Lag);
557      }
558    }
559
560    private ISymbolicExpressionTreeNode SimplifySumAggregation(ISymbolicExpressionTreeNode original) {
561      return MakeSumAggregation(GetSimplifiedTree(original.GetSubtree(0)));
562    }
563
564    private ISymbolicExpressionTreeNode SimplifyMeanAggregation(ISymbolicExpressionTreeNode original) {
565      return MakeMeanAggregation(GetSimplifiedTree(original.GetSubtree(0)));
566    }
567
568    private ISymbolicExpressionTreeNode SimplifyLengthAggregation(ISymbolicExpressionTreeNode original) {
569      return MakeLengthAggregation(GetSimplifiedTree(original.GetSubtree(0)));
570    }
571
572    private ISymbolicExpressionTreeNode SimplifyStandardDeviationAggregation(ISymbolicExpressionTreeNode original) {
573      return MakeStandardDeviationAggregation(GetSimplifiedTree(original.GetSubtree(0)));
574    }
575
576    private ISymbolicExpressionTreeNode SimplifyVarianceAggregation(ISymbolicExpressionTreeNode original) {
577      return MakeVarianceAggregation(GetSimplifiedTree(original.GetSubtree(0)));
578    }
579    #endregion
580
581    #region low level tree restructuring
582
583    private ISymbolicExpressionTreeNode MakeTimeLag(ISymbolicExpressionTreeNode subtree, int lag) {
584      if (lag == 0) return subtree;
585      if (IsConstant(subtree)) return subtree;
586      var lagNode = (LaggedTreeNode)timeLagSymbol.CreateTreeNode();
587      lagNode.Lag = lag;
588      lagNode.AddSubtree(subtree);
589      return lagNode;
590    }
591
592    private ISymbolicExpressionTreeNode MakeIntegral(ISymbolicExpressionTreeNode subtree, int lag) {
593      if (lag == 0) return subtree;
594      else if (lag == -1 || lag == 1) {
595        return MakeSum(subtree, AddLagToDynamicNodes((ISymbolicExpressionTreeNode)subtree.Clone(), lag));
596      } else {
597        var node = (LaggedTreeNode)integralSymbol.CreateTreeNode();
598        node.Lag = lag;
599        node.AddSubtree(subtree);
600        return node;
601      }
602    }
603
604    private ISymbolicExpressionTreeNode MakeNot(ISymbolicExpressionTreeNode t) {
605      if (IsConstant(t)) {
606        var constNode = t as ConstantTreeNode;
607        if (constNode.Value > 0) return MakeConstant(-1.0);
608        else return MakeConstant(1.0);
609      } else if (IsNot(t)) {
610        return t.GetSubtree(0);
611      } else if (!IsBoolean(t)) {
612        var gtNode = gtSymbol.CreateTreeNode();
613        gtNode.AddSubtree(t);
614        gtNode.AddSubtree(MakeConstant(0.0));
615        var notNode = notSymbol.CreateTreeNode();
616        notNode.AddSubtree(gtNode);
617        return notNode;
618      } else {
619        var notNode = notSymbol.CreateTreeNode();
620        notNode.AddSubtree(t);
621        return notNode;
622      }
623    }
624
625    private ISymbolicExpressionTreeNode MakeOr(ISymbolicExpressionTreeNode a, ISymbolicExpressionTreeNode b) {
626      if (IsConstant(a) && IsConstant(b)) {
627        var constA = a as ConstantTreeNode;
628        var constB = b as ConstantTreeNode;
629        if (constA.Value > 0.0 || constB.Value > 0.0) {
630          return MakeConstant(1.0);
631        } else {
632          return MakeConstant(-1.0);
633        }
634      } else if (IsConstant(a)) {
635        return MakeOr(b, a);
636      } else if (IsConstant(b)) {
637        var constT = b as ConstantTreeNode;
638        if (constT.Value > 0.0) {
639          // boolean expression is necessarily true
640          return MakeConstant(1.0);
641        } else {
642          // the constant value has no effect on the result of the boolean condition so we can drop the constant term
643          var orNode = orSymbol.CreateTreeNode();
644          orNode.AddSubtree(a);
645          return orNode;
646        }
647      } else {
648        var orNode = orSymbol.CreateTreeNode();
649        orNode.AddSubtree(a);
650        orNode.AddSubtree(b);
651        return orNode;
652      }
653    }
654
655    private ISymbolicExpressionTreeNode MakeAnd(ISymbolicExpressionTreeNode a, ISymbolicExpressionTreeNode b) {
656      if (IsConstant(a) && IsConstant(b)) {
657        var constA = a as ConstantTreeNode;
658        var constB = b as ConstantTreeNode;
659        if (constA.Value > 0.0 && constB.Value > 0.0) {
660          return MakeConstant(1.0);
661        } else {
662          return MakeConstant(-1.0);
663        }
664      } else if (IsConstant(a)) {
665        return MakeAnd(b, a);
666      } else if (IsConstant(b)) {
667        var constB = b as ConstantTreeNode;
668        if (constB.Value > 0.0) {
669          // the constant value has no effect on the result of the boolean condition so we can drop the constant term
670          var andNode = andSymbol.CreateTreeNode();
671          andNode.AddSubtree(a);
672          return andNode;
673        } else {
674          // boolean expression is necessarily false
675          return MakeConstant(-1.0);
676        }
677      } else {
678        var andNode = andSymbol.CreateTreeNode();
679        andNode.AddSubtree(a);
680        andNode.AddSubtree(b);
681        return andNode;
682      }
683    }
684
685    private ISymbolicExpressionTreeNode MakeLessThan(ISymbolicExpressionTreeNode leftSide,
686      ISymbolicExpressionTreeNode rightSide) {
687      if (IsConstant(leftSide) && IsConstant(rightSide)) {
688        var lsConst = leftSide as ConstantTreeNode;
689        var rsConst = rightSide as ConstantTreeNode;
690        if (lsConst.Value < rsConst.Value) return MakeConstant(1.0);
691        else return MakeConstant(-1.0);
692      } else {
693        var ltNode = ltSymbol.CreateTreeNode();
694        ltNode.AddSubtree(leftSide);
695        ltNode.AddSubtree(rightSide);
696        return ltNode;
697      }
698    }
699
700    private ISymbolicExpressionTreeNode MakeGreaterThan(ISymbolicExpressionTreeNode leftSide,
701      ISymbolicExpressionTreeNode rightSide) {
702      if (IsConstant(leftSide) && IsConstant(rightSide)) {
703        var lsConst = leftSide as ConstantTreeNode;
704        var rsConst = rightSide as ConstantTreeNode;
705        if (lsConst.Value > rsConst.Value) return MakeConstant(1.0);
706        else return MakeConstant(-1.0);
707      } else {
708        var gtNode = gtSymbol.CreateTreeNode();
709        gtNode.AddSubtree(leftSide);
710        gtNode.AddSubtree(rightSide);
711        return gtNode;
712      }
713    }
714
715    private ISymbolicExpressionTreeNode MakeIfThenElse(ISymbolicExpressionTreeNode condition,
716      ISymbolicExpressionTreeNode trueBranch, ISymbolicExpressionTreeNode falseBranch) {
717      if (IsConstant(condition)) {
718        var constT = condition as ConstantTreeNode;
719        if (constT.Value > 0.0) return trueBranch;
720        else return falseBranch;
721      } else {
722        var ifNode = ifThenElseSymbol.CreateTreeNode();
723        if (IsBoolean(condition)) {
724          ifNode.AddSubtree(condition);
725        } else {
726          var gtNode = gtSymbol.CreateTreeNode();
727          gtNode.AddSubtree(condition);
728          gtNode.AddSubtree(MakeConstant(0.0));
729          ifNode.AddSubtree(gtNode);
730        }
731        ifNode.AddSubtree(trueBranch);
732        ifNode.AddSubtree(falseBranch);
733        return ifNode;
734      }
735    }
736
737    private ISymbolicExpressionTreeNode MakeSine(ISymbolicExpressionTreeNode node) {
738      if (IsConstant(node)) {
739        var constT = node as ConstantTreeNode;
740        return MakeConstant(Math.Sin(constT.Value));
741      } else if (IsFactor(node)) {
742        var factor = node as FactorVariableTreeNode;
743        return MakeFactor(factor.Symbol, factor.VariableName, factor.Weights.Select(Math.Sin));
744      } else if (IsBinFactor(node)) {
745        var binFactor = node as BinaryFactorVariableTreeNode;
746        return MakeBinFactor(binFactor.Symbol, binFactor.VariableName, binFactor.VariableValue, Math.Sin(binFactor.Weight));
747      } else {
748        var sineNode = sineSymbol.CreateTreeNode();
749        sineNode.AddSubtree(node);
750        return sineNode;
751      }
752    }
753
754    private ISymbolicExpressionTreeNode MakeTangent(ISymbolicExpressionTreeNode node) {
755      if (IsConstant(node)) {
756        var constT = node as ConstantTreeNode;
757        return MakeConstant(Math.Tan(constT.Value));
758      } else if (IsFactor(node)) {
759        var factor = node as FactorVariableTreeNode;
760        return MakeFactor(factor.Symbol, factor.VariableName, factor.Weights.Select(Math.Tan));
761      } else if (IsBinFactor(node)) {
762        var binFactor = node as BinaryFactorVariableTreeNode;
763        return MakeBinFactor(binFactor.Symbol, binFactor.VariableName, binFactor.VariableValue, Math.Tan(binFactor.Weight));
764      } else {
765        var tanNode = tanSymbol.CreateTreeNode();
766        tanNode.AddSubtree(node);
767        return tanNode;
768      }
769    }
770
771    private ISymbolicExpressionTreeNode MakeCosine(ISymbolicExpressionTreeNode node) {
772      if (IsConstant(node)) {
773        var constT = node as ConstantTreeNode;
774        return MakeConstant(Math.Cos(constT.Value));
775      } else if (IsFactor(node)) {
776        var factor = node as FactorVariableTreeNode;
777        return MakeFactor(factor.Symbol, factor.VariableName, factor.Weights.Select(Math.Cos));
778      } else if (IsBinFactor(node)) {
779        var binFactor = node as BinaryFactorVariableTreeNode;
780        // cos(0) = 1 see similar case for Exp(binfactor)
781        return MakeSum(MakeBinFactor(binFactor.Symbol, binFactor.VariableName, binFactor.VariableValue, Math.Cos(binFactor.Weight) - 1),
782          MakeConstant(1.0));
783      } else {
784        var cosNode = cosineSymbol.CreateTreeNode();
785        cosNode.AddSubtree(node);
786        return cosNode;
787      }
788    }
789
790    private ISymbolicExpressionTreeNode MakeExp(ISymbolicExpressionTreeNode node) {
791      if (IsConstant(node)) {
792        var constT = node as ConstantTreeNode;
793        return MakeConstant(Math.Exp(constT.Value));
794      } else if (IsFactor(node)) {
795        var factNode = node as FactorVariableTreeNode;
796        return MakeFactor(factNode.Symbol, factNode.VariableName, factNode.Weights.Select(w => Math.Exp(w)));
797      } else if (IsBinFactor(node)) {
798        // exp( binfactor w val=a) = if(val=a) exp(w) else exp(0) = binfactor( (exp(w) - 1) val a) + 1
799        var binFactor = node as BinaryFactorVariableTreeNode;
800        return
801          MakeSum(MakeBinFactor(binFactor.Symbol, binFactor.VariableName, binFactor.VariableValue, Math.Exp(binFactor.Weight) - 1), MakeConstant(1.0));
802      } else if (IsLog(node)) {
803        return node.GetSubtree(0);
804      } else if (IsAddition(node)) {
805        return node.Subtrees.Select(s => MakeExp(s)).Aggregate((s, t) => MakeProduct(s, t));
806      } else if (IsSubtraction(node)) {
807        return node.Subtrees.Select(s => MakeExp(s)).Aggregate((s, t) => MakeProduct(s, Negate(t)));
808      } else {
809        var expNode = expSymbol.CreateTreeNode();
810        expNode.AddSubtree(node);
811        return expNode;
812      }
813    }
814    private ISymbolicExpressionTreeNode MakeLog(ISymbolicExpressionTreeNode node) {
815      if (IsConstant(node)) {
816        var constT = node as ConstantTreeNode;
817        return MakeConstant(Math.Log(constT.Value));
818      } else if (IsFactor(node)) {
819        var factNode = node as FactorVariableTreeNode;
820        return MakeFactor(factNode.Symbol, factNode.VariableName, factNode.Weights.Select(w => Math.Log(w)));
821      } else if (IsExp(node)) {
822        return node.GetSubtree(0);
823      } else if (IsSquareRoot(node)) {
824        return MakeFraction(MakeLog(node.GetSubtree(0)), MakeConstant(2.0));
825      } else {
826        var logNode = logSymbol.CreateTreeNode();
827        logNode.AddSubtree(node);
828        return logNode;
829      }
830    }
831
832    private ISymbolicExpressionTreeNode MakeSquare(ISymbolicExpressionTreeNode node) {
833      if (IsConstant(node)) {
834        var constT = node as ConstantTreeNode;
835        return MakeConstant(constT.Value * constT.Value);
836      } else if (IsFactor(node)) {
837        var factNode = node as FactorVariableTreeNode;
838        return MakeFactor(factNode.Symbol, factNode.VariableName, factNode.Weights.Select(w => w * w));
839      } else if (IsBinFactor(node)) {
840        var binFactor = node as BinaryFactorVariableTreeNode;
841        return MakeBinFactor(binFactor.Symbol, binFactor.VariableName, binFactor.VariableValue, binFactor.Weight * binFactor.Weight);
842      } else if (IsSquareRoot(node)) {
843        return node.GetSubtree(0);
844      } else if (IsMultiplication(node)) {
845        // sqr( x * y ) = sqr(x) * sqr(y)
846        var mulNode = mulSymbol.CreateTreeNode();
847        foreach (var subtree in node.Subtrees) {
848          mulNode.AddSubtree(MakeSquare(subtree));
849        }
850        return mulNode;
851      } else if (IsAbsolute(node)) {
852        return MakeSquare(node.GetSubtree(0)); // sqr(abs(x)) = sqr(x)
853      } else if (IsExp(node)) {
854        return MakeExp(MakeProduct(node.GetSubtree(0), MakeConstant(2.0))); // sqr(exp(x)) = exp(2x)
855      } else if (IsCube(node)) {
856        return MakePower(node.GetSubtree(0), MakeConstant(6));
857      } else {
858        var sqrNode = sqrSymbol.CreateTreeNode();
859        sqrNode.AddSubtree(node);
860        return sqrNode;
861      }
862    }
863
864    private ISymbolicExpressionTreeNode MakeCube(ISymbolicExpressionTreeNode node) {
865      if (IsConstant(node)) {
866        var constT = node as ConstantTreeNode;
867        return MakeConstant(constT.Value * constT.Value * constT.Value);
868      } else if (IsFactor(node)) {
869        var factNode = node as FactorVariableTreeNode;
870        return MakeFactor(factNode.Symbol, factNode.VariableName, factNode.Weights.Select(w => w * w * w));
871      } else if (IsBinFactor(node)) {
872        var binFactor = node as BinaryFactorVariableTreeNode;
873        return MakeBinFactor(binFactor.Symbol, binFactor.VariableName, binFactor.VariableValue, binFactor.Weight * binFactor.Weight * binFactor.Weight);
874      } else if (IsCubeRoot(node)) {
875        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
876      } else if (IsExp(node)) {
877        return MakeExp(MakeProduct(node.GetSubtree(0), MakeConstant(3)));
878      } else if (IsSquare(node)) {
879        return MakePower(node.GetSubtree(0), MakeConstant(6));
880      } else {
881        var cubeNode = cubeSymbol.CreateTreeNode();
882        cubeNode.AddSubtree(node);
883        return cubeNode;
884      }
885    }
886
887    private ISymbolicExpressionTreeNode MakeAbs(ISymbolicExpressionTreeNode node) {
888      if (IsConstant(node)) {
889        var constT = node as ConstantTreeNode;
890        return MakeConstant(Math.Abs(constT.Value));
891      } else if (IsFactor(node)) {
892        var factNode = node as FactorVariableTreeNode;
893        return MakeFactor(factNode.Symbol, factNode.VariableName, factNode.Weights.Select(w => Math.Abs(w)));
894      } else if (IsBinFactor(node)) {
895        var binFactor = node as BinaryFactorVariableTreeNode;
896        return MakeBinFactor(binFactor.Symbol, binFactor.VariableName, binFactor.VariableValue, Math.Abs(binFactor.Weight));
897      } else if (IsSquare(node) || IsExp(node) || IsSquareRoot(node) || IsCubeRoot(node)) {
898        return node; // abs(sqr(x)) = sqr(x), abs(exp(x)) = exp(x) ...
899      } else if (IsMultiplication(node)) {
900        var mul = mulSymbol.CreateTreeNode();
901        foreach (var st in node.Subtrees) {
902          mul.AddSubtree(MakeAbs(st));
903        }
904        return mul;
905      } else if (IsDivision(node)) {
906        var div = divSymbol.CreateTreeNode();
907        foreach (var st in node.Subtrees) {
908          div.AddSubtree(MakeAbs(st));
909        }
910        return div;
911      } else {
912        var absNode = absSymbol.CreateTreeNode();
913        absNode.AddSubtree(node);
914        return absNode;
915      }
916    }
917
918    // constant folding only
919    private ISymbolicExpressionTreeNode MakeAnalyticalQuotient(ISymbolicExpressionTreeNode a, ISymbolicExpressionTreeNode b) {
920      if (IsConstant(b)) {
921        var c = b as ConstantTreeNode;
922        return MakeFraction(a, MakeConstant(Math.Sqrt(1.0 + c.Value * c.Value)));
923      } else if (IsFactor(b)) {
924        var factNode = b as FactorVariableTreeNode;
925        return MakeFraction(a, MakeFactor(factNode.Symbol, factNode.VariableName, factNode.Weights.Select(w => Math.Sqrt(1.0 + w * w))));
926      } else if (IsBinFactor(b)) {
927        var binFactor = b as BinaryFactorVariableTreeNode;
928        return MakeFraction(a, MakeBinFactor(binFactor.Symbol, binFactor.VariableName, binFactor.VariableValue, Math.Sqrt(1.0 + binFactor.Weight * binFactor.Weight)));
929      } else {
930        var aqNode = aqSymbol.CreateTreeNode();
931        aqNode.AddSubtree(a);
932        aqNode.AddSubtree(b);
933        return aqNode;
934      }
935    }
936
937    private ISymbolicExpressionTreeNode MakeSquareRoot(ISymbolicExpressionTreeNode node) {
938      if (IsConstant(node)) {
939        var constT = node as ConstantTreeNode;
940        return MakeConstant(Math.Sqrt(constT.Value));
941      } else if (IsFactor(node)) {
942        var factNode = node as FactorVariableTreeNode;
943        return MakeFactor(factNode.Symbol, factNode.VariableName, factNode.Weights.Select(w => Math.Sqrt(w)));
944      } else if (IsBinFactor(node)) {
945        var binFactor = node as BinaryFactorVariableTreeNode;
946        return MakeBinFactor(binFactor.Symbol, binFactor.VariableName, binFactor.VariableValue, Math.Sqrt(binFactor.Weight));
947      } else if (IsSquare(node)) {
948        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
949      } else {
950        var sqrtNode = sqrtSymbol.CreateTreeNode();
951        sqrtNode.AddSubtree(node);
952        return sqrtNode;
953      }
954    }
955
956    private ISymbolicExpressionTreeNode MakeCubeRoot(ISymbolicExpressionTreeNode node) {
957      if (IsConstant(node)) {
958        var constT = node as ConstantTreeNode;
959        return MakeConstant(Math.Pow(constT.Value, 1.0 / 3.0));
960      } else if (IsFactor(node)) {
961        var factNode = node as FactorVariableTreeNode;
962        return MakeFactor(factNode.Symbol, factNode.VariableName, factNode.Weights.Select(w => Math.Pow(w, 1.0 / 3.0)));
963      } else if (IsBinFactor(node)) {
964        var binFactor = node as BinaryFactorVariableTreeNode;
965        return MakeBinFactor(binFactor.Symbol, binFactor.VariableName, binFactor.VariableValue, Math.Sqrt(Math.Pow(binFactor.Weight, 1.0 / 3.0)));
966      } else if (IsCube(node)) {
967        return node.GetSubtree(0);
968      } else {
969        var cubeRootNode = cubeRootSymbol.CreateTreeNode();
970        cubeRootNode.AddSubtree(node);
971        return cubeRootNode;
972      }
973    }
974
975    private ISymbolicExpressionTreeNode MakeRoot(ISymbolicExpressionTreeNode a, ISymbolicExpressionTreeNode b) {
976      if (IsConstant(a) && IsConstant(b)) {
977        var constA = a as ConstantTreeNode;
978        var constB = b as ConstantTreeNode;
979        return MakeConstant(Math.Pow(constA.Value, 1.0 / Math.Round(constB.Value)));
980      } else if (IsFactor(a) && IsConstant(b)) {
981        var factNode = a as FactorVariableTreeNode;
982        var constNode = b as ConstantTreeNode;
983        return MakeFactor(factNode.Symbol, factNode.VariableName,
984          factNode.Weights.Select(w => Math.Pow(w, 1.0 / Math.Round(constNode.Value))));
985      } else if (IsBinFactor(a) && IsConstant(b)) {
986        var binFactor = a as BinaryFactorVariableTreeNode;
987        var constNode = b as ConstantTreeNode;
988        return MakeBinFactor(binFactor.Symbol, binFactor.VariableName, binFactor.VariableValue, Math.Pow(binFactor.Weight, 1.0 / Math.Round(constNode.Value)));
989      } else if (IsConstant(a) && IsFactor(b)) {
990        var constNode = a as ConstantTreeNode;
991        var factNode = b as FactorVariableTreeNode;
992        return MakeFactor(factNode.Symbol, factNode.VariableName, factNode.Weights.Select(w => Math.Pow(constNode.Value, 1.0 / Math.Round(w))));
993      } else if (IsConstant(a) && IsBinFactor(b)) {
994        var constNode = a as ConstantTreeNode;
995        var factNode = b as BinaryFactorVariableTreeNode;
996        return MakeBinFactor(factNode.Symbol, factNode.VariableName, factNode.VariableValue, Math.Pow(constNode.Value, 1.0 / Math.Round(factNode.Weight)));
997      } else if (IsFactor(a) && IsFactor(b) && AreSameTypeAndVariable(a, b)) {
998        var node0 = a as FactorVariableTreeNode;
999        var node1 = b as FactorVariableTreeNode;
1000        return MakeFactor(node0.Symbol, node0.VariableName, node0.Weights.Zip(node1.Weights, (u, v) => Math.Pow(u, 1.0 / Math.Round(v))));
1001      } else if (IsConstant(b)) {
1002        var constB = b as ConstantTreeNode;
1003        var constBValue = Math.Round(constB.Value);
1004        if (constBValue.IsAlmost(1.0)) {
1005          return a;
1006        } else if (constBValue.IsAlmost(0.0)) {
1007          return MakeConstant(1.0);
1008        } else if (constBValue.IsAlmost(-1.0)) {
1009          return MakeFraction(MakeConstant(1.0), a);
1010        } else if (constBValue < 0) {
1011          var rootNode = rootSymbol.CreateTreeNode();
1012          rootNode.AddSubtree(a);
1013          rootNode.AddSubtree(MakeConstant(-1.0 * constBValue));
1014          return MakeFraction(MakeConstant(1.0), rootNode);
1015        } else {
1016          var rootNode = rootSymbol.CreateTreeNode();
1017          rootNode.AddSubtree(a);
1018          rootNode.AddSubtree(MakeConstant(constBValue));
1019          return rootNode;
1020        }
1021      } else {
1022        var rootNode = rootSymbol.CreateTreeNode();
1023        rootNode.AddSubtree(a);
1024        rootNode.AddSubtree(b);
1025        return rootNode;
1026      }
1027    }
1028
1029
1030    private ISymbolicExpressionTreeNode MakePower(ISymbolicExpressionTreeNode a, ISymbolicExpressionTreeNode b) {
1031      if (IsConstant(a) && IsConstant(b)) {
1032        var constA = a as ConstantTreeNode;
1033        var constB = b as ConstantTreeNode;
1034        return MakeConstant(Math.Pow(constA.Value, Math.Round(constB.Value)));
1035      } else if (IsFactor(a) && IsConstant(b)) {
1036        var factNode = a as FactorVariableTreeNode;
1037        var constNode = b as ConstantTreeNode;
1038        return MakeFactor(factNode.Symbol, factNode.VariableName, factNode.Weights.Select(w => Math.Pow(w, Math.Round(constNode.Value))));
1039      } else if (IsBinFactor(a) && IsConstant(b)) {
1040        var binFactor = a as BinaryFactorVariableTreeNode;
1041        var constNode = b as ConstantTreeNode;
1042        return MakeBinFactor(binFactor.Symbol, binFactor.VariableName, binFactor.VariableValue, Math.Pow(binFactor.Weight, Math.Round(constNode.Value)));
1043      } else if (IsConstant(a) && IsFactor(b)) {
1044        var constNode = a as ConstantTreeNode;
1045        var factNode = b as FactorVariableTreeNode;
1046        return MakeFactor(factNode.Symbol, factNode.VariableName, factNode.Weights.Select(w => Math.Pow(constNode.Value, Math.Round(w))));
1047      } else if (IsConstant(a) && IsBinFactor(b)) {
1048        var constNode = a as ConstantTreeNode;
1049        var factNode = b as BinaryFactorVariableTreeNode;
1050        return MakeBinFactor(factNode.Symbol, factNode.VariableName, factNode.VariableValue, Math.Pow(constNode.Value, Math.Round(factNode.Weight)));
1051      } else if (IsFactor(a) && IsFactor(b) && AreSameTypeAndVariable(a, b)) {
1052        var node0 = a as FactorVariableTreeNode;
1053        var node1 = b as FactorVariableTreeNode;
1054        return MakeFactor(node0.Symbol, node0.VariableName, node0.Weights.Zip(node1.Weights, (u, v) => Math.Pow(u, Math.Round(v))));
1055      } else if (IsConstant(b)) {
1056        var constB = b as ConstantTreeNode;
1057        double exponent = Math.Round(constB.Value);
1058        if (exponent.IsAlmost(0.0)) {
1059          return MakeConstant(1.0);
1060        } else if (exponent.IsAlmost(1.0)) {
1061          return a;
1062        } else if (exponent.IsAlmost(-1.0)) {
1063          return MakeFraction(MakeConstant(1.0), a);
1064        } else if (exponent < 0) {
1065          var powNode = powSymbol.CreateTreeNode();
1066          powNode.AddSubtree(a);
1067          powNode.AddSubtree(MakeConstant(-1.0 * exponent));
1068          return MakeFraction(MakeConstant(1.0), powNode);
1069        } else {
1070          var powNode = powSymbol.CreateTreeNode();
1071          powNode.AddSubtree(a);
1072          powNode.AddSubtree(MakeConstant(exponent));
1073          return powNode;
1074        }
1075      } else {
1076        var powNode = powSymbol.CreateTreeNode();
1077        powNode.AddSubtree(a);
1078        powNode.AddSubtree(b);
1079        return powNode;
1080      }
1081    }
1082
1083
1084    // MakeFraction, MakeProduct and MakeSum take two already simplified trees and create a new simplified tree
1085    private ISymbolicExpressionTreeNode MakeFraction(ISymbolicExpressionTreeNode a, ISymbolicExpressionTreeNode b) {
1086      if (IsConstant(a) && IsConstant(b)) {
1087        // fold constants
1088        return MakeConstant(((ConstantTreeNode)a).Value / ((ConstantTreeNode)b).Value);
1089      } else if ((IsConstant(a) && !((ConstantTreeNode)a).Value.IsAlmost(1.0))) {
1090        return MakeFraction(MakeConstant(1.0), MakeProduct(b, Invert(a)));
1091      } else if (IsVariableBase(a) && IsConstant(b)) {
1092        // merge constant values into variable weights
1093        var constB = ((ConstantTreeNode)b).Value;
1094        ((VariableTreeNodeBase)a).Weight /= constB;
1095        return a;
1096      } else if (IsFactor(a) && IsConstant(b)) {
1097        var factNode = a as FactorVariableTreeNode;
1098        var constNode = b as ConstantTreeNode;
1099        return MakeFactor(factNode.Symbol, factNode.VariableName, factNode.Weights.Select(w => w / constNode.Value));
1100      } else if (IsBinFactor(a) && IsConstant(b)) {
1101        var factNode = a as BinaryFactorVariableTreeNode;
1102        var constNode = b as ConstantTreeNode;
1103        return MakeBinFactor(factNode.Symbol, factNode.VariableName, factNode.VariableValue, factNode.Weight / constNode.Value);
1104      } else if (IsFactor(a) && IsFactor(b) && AreSameTypeAndVariable(a, b)) {
1105        var node0 = a as FactorVariableTreeNode;
1106        var node1 = b as FactorVariableTreeNode;
1107        return MakeFactor(node0.Symbol, node0.VariableName, node0.Weights.Zip(node1.Weights, (u, v) => u / v));
1108      } else if (IsFactor(a) && IsBinFactor(b) && ((IVariableTreeNode)a).VariableName == ((IVariableTreeNode)b).VariableName) {
1109        var node0 = a as FactorVariableTreeNode;
1110        var node1 = b as BinaryFactorVariableTreeNode;
1111        var varValues = node0.Symbol.GetVariableValues(node0.VariableName).ToArray();
1112        var wi = Array.IndexOf(varValues, node1.VariableValue);
1113        if (wi < 0) throw new ArgumentException();
1114        var newWeighs = new double[varValues.Length];
1115        node0.Weights.CopyTo(newWeighs, 0);
1116        for (int i = 0; i < newWeighs.Length; i++)
1117          if (wi == i) newWeighs[i] /= node1.Weight;
1118          else newWeighs[i] /= 0.0;
1119        return MakeFactor(node0.Symbol, node0.VariableName, newWeighs);
1120      } else if (IsFactor(a)) {
1121        return MakeFraction(MakeConstant(1.0), MakeProduct(b, Invert(a)));
1122      } else if (IsVariableBase(a) && IsVariableBase(b) && AreSameTypeAndVariable(a, b) && !IsBinFactor(b)) {
1123        // cancel variables (not allowed for bin factors because of division by zero)
1124        var aVar = a as VariableTreeNode;
1125        var bVar = b as VariableTreeNode;
1126        return MakeConstant(aVar.Weight / bVar.Weight);
1127      } else if (IsAddition(a) && IsConstant(b)) {
1128        return a.Subtrees
1129          .Select(x => GetSimplifiedTree(x))
1130          .Select(x => MakeFraction(x, GetSimplifiedTree(b)))
1131          .Aggregate((c, d) => MakeSum(c, d));
1132      } else if (IsMultiplication(a) && IsConstant(b)) {
1133        return MakeProduct(a, Invert(b));
1134      } else if (IsDivision(a) && IsConstant(b)) {
1135        // (a1 / a2) / c => (a1 / (a2 * c))
1136        return MakeFraction(a.GetSubtree(0), MakeProduct(a.GetSubtree(1), b));
1137      } else if (IsDivision(a) && IsDivision(b)) {
1138        // (a1 / a2) / (b1 / b2) =>
1139        return MakeFraction(MakeProduct(a.GetSubtree(0), b.GetSubtree(1)), MakeProduct(a.GetSubtree(1), b.GetSubtree(0)));
1140      } else if (IsDivision(a)) {
1141        // (a1 / a2) / b => (a1 / (a2 * b))
1142        return MakeFraction(a.GetSubtree(0), MakeProduct(a.GetSubtree(1), b));
1143      } else if (IsDivision(b)) {
1144        // a / (b1 / b2) => (a * b2) / b1
1145        return MakeFraction(MakeProduct(a, b.GetSubtree(1)), b.GetSubtree(0));
1146      } else if (IsAnalyticalQuotient(a)) {
1147        return MakeAnalyticalQuotient(a.GetSubtree(0), MakeProduct(a.GetSubtree(1), b));
1148      } else {
1149        var div = divSymbol.CreateTreeNode();
1150        div.AddSubtree(a);
1151        div.AddSubtree(b);
1152        return div;
1153      }
1154    }
1155
1156    private ISymbolicExpressionTreeNode MakeSum(ISymbolicExpressionTreeNode a, ISymbolicExpressionTreeNode b) {
1157      if (IsConstant(a) && IsConstant(b)) {
1158        // fold constants
1159        ((ConstantTreeNode)a).Value += ((ConstantTreeNode)b).Value;
1160        return a;
1161      } else if (IsConstant(a)) {
1162        // c + x => x + c
1163        // b is not constant => make sure constant is on the right
1164        return MakeSum(b, a);
1165      } else if (IsConstant(b) && ((ConstantTreeNode)b).Value.IsAlmost(0.0)) {
1166        // x + 0 => x
1167        return a;
1168      } else if (IsFactor(a) && IsConstant(b)) {
1169        var factNode = a as FactorVariableTreeNode;
1170        var constNode = b as ConstantTreeNode;
1171        return MakeFactor(factNode.Symbol, factNode.VariableName, factNode.Weights.Select((w) => w + constNode.Value));
1172      } else if (IsFactor(a) && IsFactor(b) && AreSameTypeAndVariable(a, b)) {
1173        var node0 = a as FactorVariableTreeNode;
1174        var node1 = b as FactorVariableTreeNode;
1175        return MakeFactor(node0.Symbol, node0.VariableName, node0.Weights.Zip(node1.Weights, (u, v) => u + v));
1176      } else if (IsBinFactor(a) && IsFactor(b)) {
1177        return MakeSum(b, a);
1178      } else if (IsFactor(a) && IsBinFactor(b) &&
1179        ((IVariableTreeNode)a).VariableName == ((IVariableTreeNode)b).VariableName) {
1180        var node0 = a as FactorVariableTreeNode;
1181        var node1 = b as BinaryFactorVariableTreeNode;
1182        var varValues = node0.Symbol.GetVariableValues(node0.VariableName).ToArray();
1183        var wi = Array.IndexOf(varValues, node1.VariableValue);
1184        if (wi < 0) throw new ArgumentException();
1185        var newWeighs = new double[varValues.Length];
1186        node0.Weights.CopyTo(newWeighs, 0);
1187        newWeighs[wi] += node1.Weight;
1188        return MakeFactor(node0.Symbol, node0.VariableName, newWeighs);
1189      } else if (IsAddition(a) && IsAddition(b)) {
1190        // merge additions
1191        var add = addSymbol.CreateTreeNode();
1192        // add all sub trees except for the last
1193        for (int i = 0; i < a.Subtrees.Count() - 1; i++) add.AddSubtree(a.GetSubtree(i));
1194        for (int i = 0; i < b.Subtrees.Count() - 1; i++) add.AddSubtree(b.GetSubtree(i));
1195        if (IsConstant(a.Subtrees.Last()) && IsConstant(b.Subtrees.Last())) {
1196          add.AddSubtree(MakeSum(a.Subtrees.Last(), b.Subtrees.Last()));
1197        } else if (IsConstant(a.Subtrees.Last())) {
1198          add.AddSubtree(b.Subtrees.Last());
1199          add.AddSubtree(a.Subtrees.Last());
1200        } else {
1201          add.AddSubtree(a.Subtrees.Last());
1202          add.AddSubtree(b.Subtrees.Last());
1203        }
1204        MergeVariablesInSum(add);
1205        if (add.Subtrees.Count() == 1) {
1206          return add.GetSubtree(0);
1207        } else {
1208          return add;
1209        }
1210      } else if (IsAddition(b)) {
1211        return MakeSum(b, a);
1212      } else if (IsAddition(a) && IsConstant(b)) {
1213        // a is an addition and b is a constant => append b to a and make sure the constants are merged
1214        var add = addSymbol.CreateTreeNode();
1215        // add all sub trees except for the last
1216        for (int i = 0; i < a.Subtrees.Count() - 1; i++) add.AddSubtree(a.GetSubtree(i));
1217        if (IsConstant(a.Subtrees.Last()))
1218          add.AddSubtree(MakeSum(a.Subtrees.Last(), b));
1219        else {
1220          add.AddSubtree(a.Subtrees.Last());
1221          add.AddSubtree(b);
1222        }
1223        return add;
1224      } else if (IsAddition(a)) {
1225        // a is already an addition => append b
1226        var add = addSymbol.CreateTreeNode();
1227        add.AddSubtree(b);
1228        foreach (var subtree in a.Subtrees) {
1229          add.AddSubtree(subtree);
1230        }
1231        MergeVariablesInSum(add);
1232        if (add.Subtrees.Count() == 1) {
1233          return add.GetSubtree(0);
1234        } else {
1235          return add;
1236        }
1237      } else {
1238        var add = addSymbol.CreateTreeNode();
1239        add.AddSubtree(a);
1240        add.AddSubtree(b);
1241        MergeVariablesInSum(add);
1242        if (add.Subtrees.Count() == 1) {
1243          return add.GetSubtree(0);
1244        } else {
1245          return add;
1246        }
1247      }
1248    }
1249
1250    // makes sure variable symbols in sums are combined
1251    private void MergeVariablesInSum(ISymbolicExpressionTreeNode sum) {
1252      var subtrees = new List<ISymbolicExpressionTreeNode>(sum.Subtrees);
1253      while (sum.Subtrees.Any()) sum.RemoveSubtree(0);
1254      var groupedVarNodes = from node in subtrees.OfType<IVariableTreeNode>()
1255                            where node.SubtreeCount == 0
1256                            group node by GroupId(node) into g
1257                            select g;
1258      var constant = (from node in subtrees.OfType<ConstantTreeNode>()
1259                      select node.Value).DefaultIfEmpty(0.0).Sum();
1260      var unchangedSubtrees = subtrees.Where(t => t.SubtreeCount > 0 || !(t is IVariableTreeNode) && !(t is ConstantTreeNode));
1261
1262      foreach (var variableNodeGroup in groupedVarNodes) {
1263        var firstNode = variableNodeGroup.First();
1264        if (firstNode is VariableTreeNodeBase) {
1265          var representative = firstNode as VariableTreeNodeBase;
1266          var weightSum = variableNodeGroup.Cast<VariableTreeNodeBase>().Select(t => t.Weight).Sum();
1267          representative.Weight = weightSum;
1268          sum.AddSubtree(representative);
1269        } else if (firstNode is FactorVariableTreeNode) {
1270          var representative = firstNode as FactorVariableTreeNode;
1271          foreach (var node in variableNodeGroup.Skip(1).Cast<FactorVariableTreeNode>()) {
1272            for (int j = 0; j < representative.Weights.Length; j++) {
1273              representative.Weights[j] += node.Weights[j];
1274            }
1275          }
1276          sum.AddSubtree(representative);
1277        }
1278      }
1279      foreach (var unchangedSubtree in unchangedSubtrees)
1280        sum.AddSubtree(unchangedSubtree);
1281      if (!constant.IsAlmost(0.0)) {
1282        sum.AddSubtree(MakeConstant(constant));
1283      }
1284    }
1285
1286    // nodes referencing variables can be grouped if they have
1287    private string GroupId(IVariableTreeNode node) {
1288      var binaryFactorNode = node as BinaryFactorVariableTreeNode;
1289      var factorNode = node as FactorVariableTreeNode;
1290      var variableNode = node as VariableTreeNode;
1291      var laggedVarNode = node as LaggedVariableTreeNode;
1292      if (variableNode != null) {
1293        return "var " + variableNode.VariableName;
1294      } else if (binaryFactorNode != null) {
1295        return "binfactor " + binaryFactorNode.VariableName + " " + binaryFactorNode.VariableValue;
1296      } else if (factorNode != null) {
1297        return "factor " + factorNode.VariableName;
1298      } else if (laggedVarNode != null) {
1299        return "lagged " + laggedVarNode.VariableName + " " + laggedVarNode.Lag;
1300      } else {
1301        throw new NotSupportedException();
1302      }
1303    }
1304
1305
1306    private ISymbolicExpressionTreeNode MakeProduct(ISymbolicExpressionTreeNode a, ISymbolicExpressionTreeNode b) {
1307      if (IsConstant(a) && IsConstant(b)) {
1308        // fold constants
1309        return MakeConstant(((ConstantTreeNode)a).Value * ((ConstantTreeNode)b).Value);
1310      } else if (IsConstant(a)) {
1311        // a * $ => $ * a
1312        return MakeProduct(b, a);
1313      } else if (IsFactor(a) && IsFactor(b) && AreSameTypeAndVariable(a, b)) {
1314        var node0 = a as FactorVariableTreeNode;
1315        var node1 = b as FactorVariableTreeNode;
1316        return MakeFactor(node0.Symbol, node0.VariableName, node0.Weights.Zip(node1.Weights, (u, v) => u * v));
1317      } else if (IsBinFactor(a) && IsBinFactor(b) && AreSameTypeAndVariable(a, b)) {
1318        var node0 = a as BinaryFactorVariableTreeNode;
1319        var node1 = b as BinaryFactorVariableTreeNode;
1320        return MakeBinFactor(node0.Symbol, node0.VariableName, node0.VariableValue, node0.Weight * node1.Weight);
1321      } else if (IsFactor(a) && IsConstant(b)) {
1322        var node0 = a as FactorVariableTreeNode;
1323        var node1 = b as ConstantTreeNode;
1324        return MakeFactor(node0.Symbol, node0.VariableName, node0.Weights.Select(w => w * node1.Value));
1325      } else if (IsBinFactor(a) && IsConstant(b)) {
1326        var node0 = a as BinaryFactorVariableTreeNode;
1327        var node1 = b as ConstantTreeNode;
1328        return MakeBinFactor(node0.Symbol, node0.VariableName, node0.VariableValue, node0.Weight * node1.Value);
1329      } else if (IsBinFactor(a) && IsFactor(b)) {
1330        return MakeProduct(b, a);
1331      } else if (IsFactor(a) && IsBinFactor(b) &&
1332        ((IVariableTreeNode)a).VariableName == ((IVariableTreeNode)b).VariableName) {
1333        var node0 = a as FactorVariableTreeNode;
1334        var node1 = b as BinaryFactorVariableTreeNode;
1335        var varValues = node0.Symbol.GetVariableValues(node0.VariableName).ToArray();
1336        var wi = Array.IndexOf(varValues, node1.VariableValue);
1337        if (wi < 0) throw new ArgumentException();
1338        return MakeBinFactor(node1.Symbol, node1.VariableName, node1.VariableValue, node1.Weight * node0.Weights[wi]);
1339      } else if (IsConstant(b) && ((ConstantTreeNode)b).Value.IsAlmost(1.0)) {
1340        // $ * 1.0 => $
1341        return a;
1342      } else if (IsConstant(b) && ((ConstantTreeNode)b).Value.IsAlmost(0.0)) {
1343        return MakeConstant(0);
1344      } else if (IsConstant(b) && IsVariableBase(a)) {
1345        // multiply constants into variables weights
1346        ((VariableTreeNodeBase)a).Weight *= ((ConstantTreeNode)b).Value;
1347        return a;
1348      } else if (IsConstant(b) && IsAddition(a) ||
1349          IsFactor(b) && IsAddition(a) ||
1350          IsBinFactor(b) && IsAddition(a)) {
1351        // multiply constants into additions
1352        return a.Subtrees.Select(x => MakeProduct(GetSimplifiedTree(x), GetSimplifiedTree(b))).Aggregate((c, d) => MakeSum(c, d));
1353      } else if (IsDivision(a) && IsDivision(b)) {
1354        // (a1 / a2) * (b1 / b2) => (a1 * b1) / (a2 * b2)
1355        return MakeFraction(MakeProduct(a.GetSubtree(0), b.GetSubtree(0)), MakeProduct(a.GetSubtree(1), b.GetSubtree(1)));
1356      } else if (IsDivision(a)) {
1357        // (a1 / a2) * b => (a1 * b) / a2
1358        return MakeFraction(MakeProduct(a.GetSubtree(0), b), a.GetSubtree(1));
1359      } else if (IsDivision(b)) {
1360        // a * (b1 / b2) => (b1 * a) / b2
1361        return MakeFraction(MakeProduct(b.GetSubtree(0), a), b.GetSubtree(1));
1362      } else if (IsMultiplication(a) && IsMultiplication(b)) {
1363        // merge multiplications (make sure constants are merged)
1364        var mul = mulSymbol.CreateTreeNode();
1365        for (int i = 0; i < a.Subtrees.Count(); i++) mul.AddSubtree(a.GetSubtree(i));
1366        for (int i = 0; i < b.Subtrees.Count(); i++) mul.AddSubtree(b.GetSubtree(i));
1367        MergeVariablesAndConstantsInProduct(mul);
1368        return mul;
1369      } else if (IsMultiplication(b)) {
1370        return MakeProduct(b, a);
1371      } else if (IsMultiplication(a)) {
1372        // a is already an multiplication => append b
1373        a.AddSubtree(GetSimplifiedTree(b));
1374        MergeVariablesAndConstantsInProduct(a);
1375        return a;
1376      } else if (IsAbsolute(a) && IsAbsolute(b)) {
1377        return MakeAbs(MakeProduct(a.GetSubtree(0), b.GetSubtree(0)));
1378      } else if (IsAbsolute(a) && IsConstant(b)) {
1379        var constNode = b as ConstantTreeNode;
1380        var posF = Math.Abs(constNode.Value);
1381        if (constNode.Value > 0) {
1382          return MakeAbs(MakeProduct(a.GetSubtree(0), MakeConstant(posF)));
1383        } else {
1384          var mul = mulSymbol.CreateTreeNode();
1385          mul.AddSubtree(MakeAbs(MakeProduct(a.GetSubtree(0), MakeConstant(posF))));
1386          mul.AddSubtree(MakeConstant(-1.0));
1387          return mul;
1388        }
1389      } else if (IsAnalyticalQuotient(a)) {
1390        return MakeAnalyticalQuotient(MakeProduct(a.GetSubtree(0), b), a.GetSubtree(1));
1391      } else {
1392        var mul = mulSymbol.CreateTreeNode();
1393        mul.AddSubtree(a);
1394        mul.AddSubtree(b);
1395        MergeVariablesAndConstantsInProduct(mul);
1396        return mul;
1397      }
1398    }
1399
1400    private ISymbolicExpressionTreeNode MakeSumAggregation(ISymbolicExpressionTreeNode node) {
1401      if (IsScalarNode(node)) {
1402        return node;
1403      } else if (IsAddition(node) || IsSubtraction(node)) {
1404        var terms = node.Subtrees;
1405        if (IsSubtraction(node)) terms = InvertNodes(terms, Negate);
1406
1407        var scalarTerms = terms.Where(IsScalarNode).ToList();
1408        var remainingTerms = terms.Except(scalarTerms).ToList();
1409
1410        if (scalarTerms.Any() && remainingTerms.Any()) {
1411          var scalarNode = scalarTerms.Aggregate(MakeSum);
1412          var vectorNode = remainingTerms.Aggregate(MakeSum);
1413
1414          var lengthNode = MakeLengthAggregation((ISymbolicExpressionTreeNode)vectorNode.Clone());
1415          var scalarMulNode = MakeProduct(scalarNode, lengthNode);
1416
1417          var sumNode = MakeSumAggregation(vectorNode);
1418
1419          return MakeSum(scalarMulNode, sumNode);
1420        } else if (scalarTerms.Any()) {
1421          var scalarNode = scalarTerms.Aggregate(MakeSum);
1422          return scalarNode;
1423        } else if (remainingTerms.Any()) {
1424          var vectorNode = remainingTerms.Aggregate(MakeSum);
1425          var sumNode = sumSymbol.CreateTreeNode();
1426          sumNode.AddSubtree(vectorNode);
1427          return sumNode;
1428        } else
1429          throw new InvalidOperationException("Addition does not contain any terms to simplify.");
1430      } else if (IsMultiplication(node) || IsDivision(node)) {
1431        var factors = node.Subtrees;
1432        if (IsDivision(node)) factors = InvertNodes(factors, Invert);
1433
1434        var scalarFactors = factors.Where(IsScalarNode).ToList();
1435        var remainingFactors = factors.Except(scalarFactors).ToList();
1436
1437        if (scalarFactors.Any() && remainingFactors.Any()) {
1438          var scalarNode = scalarFactors.Aggregate(MakeProduct);
1439          var vectorNode = remainingFactors.Aggregate(MakeProduct);
1440
1441          var sumNode = MakeSumAggregation(vectorNode);
1442
1443          return MakeProduct(scalarNode, sumNode);
1444        } else if (scalarFactors.Any()) {
1445          var scalarNode = scalarFactors.Aggregate(MakeProduct);
1446          return scalarNode;
1447        } else if (remainingFactors.Any()) {
1448          var vectorNode = remainingFactors.Aggregate(MakeProduct);
1449          var sumNode = sumSymbol.CreateTreeNode();
1450          sumNode.AddSubtree(vectorNode);
1451          return sumNode;
1452        } else
1453          throw new InvalidOperationException("Multiplication does not contain any terms to simplify.");
1454      } else if (IsVariableBase(node)) { // weight is like multiplication
1455        var variableNode = (VariableTreeNodeBase)node;
1456        var weight = variableNode.Weight;
1457        variableNode.Weight = 1.0;
1458        var sumNode = sumSymbol.CreateTreeNode();
1459        sumNode.AddSubtree(node);
1460        return MakeProduct(MakeConstant(weight), sumNode);
1461      } else {
1462        var sumNode = sumSymbol.CreateTreeNode();
1463        sumNode.AddSubtree(node);
1464        return sumNode;
1465      }
1466    }
1467
1468    private ISymbolicExpressionTreeNode MakeMeanAggregation(ISymbolicExpressionTreeNode node) {
1469      if (IsScalarNode(node)) {
1470        return node;
1471      } else if (IsAddition(node) || IsSubtraction(node)) {
1472        var terms = node.Subtrees;
1473        if (IsSubtraction(node)) terms = InvertNodes(terms, Negate);
1474
1475        var scalarTerms = terms.Where(IsScalarNode).ToList();
1476        var remainingTerms = terms.Except(scalarTerms).ToList();
1477
1478        if (scalarTerms.Any() && remainingTerms.Any()) {
1479          var scalarNode = scalarTerms.Aggregate(MakeSum);
1480          var vectorNode = remainingTerms.Aggregate(MakeSum);
1481
1482          var meanNode = MakeMeanAggregation(vectorNode);
1483
1484          return MakeSum(scalarNode, meanNode);
1485        } else if (scalarTerms.Any()) {
1486          var scalarNode = scalarTerms.Aggregate(MakeSum);
1487          return scalarNode;
1488        } else if (remainingTerms.Any()) {
1489          var vectorNode = remainingTerms.Aggregate(MakeSum);
1490          var meanNode = meanSymbol.CreateTreeNode();
1491          meanNode.AddSubtree(vectorNode);
1492          return meanNode;
1493        } else
1494          throw new InvalidOperationException("Addition does not contain any terms to simplify.");
1495      } else if (IsMultiplication(node) || IsDivision(node)) {
1496        var factors = node.Subtrees;
1497        if (IsDivision(node)) factors = InvertNodes(factors, Invert);
1498
1499        var scalarFactors = factors.Where(IsScalarNode).ToList();
1500        var remainingFactors = factors.Except(scalarFactors).ToList();
1501
1502        if (scalarFactors.Any() && remainingFactors.Any()) {
1503          var scalarNode = scalarFactors.Aggregate(MakeProduct);
1504          var vectorNode = remainingFactors.Aggregate(MakeProduct);
1505
1506          var meanNode = MakeMeanAggregation(vectorNode);
1507
1508          return MakeProduct(scalarNode, meanNode);
1509        } else if (scalarFactors.Any()) {
1510          var scalarNode = scalarFactors.Aggregate(MakeProduct);
1511          return scalarNode;
1512        } else if (remainingFactors.Any()) {
1513          var vectorNode = remainingFactors.Aggregate(MakeProduct);
1514          var meanNode = meanSymbol.CreateTreeNode();
1515          meanNode.AddSubtree(vectorNode);
1516          return meanNode;
1517        } else
1518          throw new InvalidOperationException("Multiplication does not contain any terms to simplify.");
1519      } else if (IsVariableBase(node)) { // weight is like multiplication
1520        var variableNode = (VariableTreeNodeBase)node;
1521        var weight = variableNode.Weight;
1522        variableNode.Weight = 1.0;
1523        var meanNode = meanSymbol.CreateTreeNode();
1524        meanNode.AddSubtree(node);
1525        return MakeProduct(MakeConstant(weight), meanNode);
1526      } else {
1527        var meanNode = meanSymbol.CreateTreeNode();
1528        meanNode.AddSubtree(node);
1529        return meanNode;
1530      }
1531    }
1532
1533    private ISymbolicExpressionTreeNode MakeLengthAggregation(ISymbolicExpressionTreeNode node) {
1534      if (IsScalarNode(node)) {
1535        return MakeConstant(1.0);
1536      } else if (IsAddition(node) || IsSubtraction(node)) {
1537        var terms = node.Subtrees;
1538        if (IsSubtraction(node)) terms = InvertNodes(terms, Negate);
1539
1540        var scalarTerms = terms.Where(IsScalarNode).ToList();
1541        var remainingTerms = terms.Except(scalarTerms).ToList();
1542
1543        if (remainingTerms.Any()) {
1544          var vectorNode = remainingTerms.Aggregate(MakeSum);
1545
1546          var lengthNode = lengthSymbol.CreateTreeNode();
1547          lengthNode.AddSubtree(vectorNode);
1548
1549          return lengthNode;
1550        } else if (scalarTerms.Any()) {
1551          return MakeConstant(1.0);
1552        } else
1553          throw new InvalidOperationException("Addition does not contain any terms to simplify.");
1554      } else if (IsMultiplication(node) || IsDivision(node)) {
1555        var factors = node.Subtrees;
1556        if (IsDivision(node)) factors = InvertNodes(factors, Invert);
1557
1558        var scalarFactors = factors.Where(IsScalarNode).ToList();
1559        var remainingFactors = factors.Except(scalarFactors).ToList();
1560
1561        if (remainingFactors.Any()) {
1562          var vectorNode = remainingFactors.Aggregate(MakeProduct);
1563
1564          var lengthNode = lengthSymbol.CreateTreeNode();
1565          lengthNode.AddSubtree(vectorNode);
1566
1567          return lengthNode;
1568        } else if (scalarFactors.Any()) {
1569          return MakeConstant(1.0);
1570        } else
1571          throw new InvalidOperationException("Multiplication does not contain any terms to simplify.");
1572      } else if (IsVariableBase(node)) { // weight is like multiplication
1573        var variableNode = (VariableTreeNodeBase)node;
1574        variableNode.Weight = 1.0;
1575        var lengthNode = lengthSymbol.CreateTreeNode();
1576        lengthNode.AddSubtree(node);
1577        return lengthNode;
1578      } else {
1579        var lengthNode = lengthSymbol.CreateTreeNode();
1580        lengthNode.AddSubtree(node);
1581        return lengthNode;
1582      }
1583    }
1584
1585    private ISymbolicExpressionTreeNode MakeStandardDeviationAggregation(ISymbolicExpressionTreeNode node) {
1586      if (IsScalarNode(node)) {
1587        return MakeConstant(0.0);
1588      } else if (IsAddition(node) || IsSubtraction(node)) { // scalars drop out
1589        var terms = node.Subtrees;
1590
1591        var scalarTerms = terms.Where(IsScalarNode).ToList();
1592        var remainingTerms = terms.Except(scalarTerms).ToList();
1593
1594        if (remainingTerms.Any()) {
1595          var vectorNode = remainingTerms.Aggregate(MakeSum);
1596
1597          var stdevNode = standardDeviationSymbol.CreateTreeNode();
1598          stdevNode.AddSubtree(vectorNode);
1599
1600          return stdevNode;
1601        } else if (scalarTerms.Any()) {
1602          return MakeConstant(0.0);
1603        } else
1604          throw new InvalidOperationException("Addition does not contain any terms to simplify.");
1605      } else if (IsMultiplication(node) || IsDivision(node)) {
1606        var factors = node.Subtrees;
1607        if (IsDivision(node)) factors = InvertNodes(factors, Invert);
1608
1609        var scalarFactors = factors.Where(IsScalarNode).ToList();
1610        var remainingFactors = factors.Except(scalarFactors).ToList();
1611
1612        if (scalarFactors.Any() && remainingFactors.Any()) {
1613          var scalarNode = scalarFactors.Aggregate(MakeProduct);
1614          var vectorNode = remainingFactors.Aggregate(MakeProduct);
1615
1616          var stdevNode = MakeStandardDeviationAggregation(vectorNode);
1617
1618          return MakeProduct(scalarNode, stdevNode);
1619        } else if (scalarFactors.Any()) {
1620          var scalarNode = scalarFactors.Aggregate(MakeProduct);
1621          return scalarNode;
1622        } else if (remainingFactors.Any()) {
1623          var vectorNode = remainingFactors.Aggregate(MakeProduct);
1624          var stdevNode = standardDeviationSymbol.CreateTreeNode();
1625          stdevNode.AddSubtree(vectorNode);
1626          return stdevNode;
1627        } else
1628          throw new InvalidOperationException("Multiplication does not contain any terms to simplify.");
1629      } else if (IsVariableBase(node)) { // weight is like multiplication
1630        var variableNode = (VariableTreeNodeBase)node;
1631        var weight = variableNode.Weight;
1632        variableNode.Weight = 1.0;
1633        var stdevNode = standardDeviationSymbol.CreateTreeNode();
1634        stdevNode.AddSubtree(node);
1635        return MakeProduct(MakeConstant(weight), stdevNode);
1636      } else {
1637        var stdevNode = standardDeviationSymbol.CreateTreeNode();
1638        stdevNode.AddSubtree(node);
1639        return stdevNode;
1640      }
1641    }
1642
1643    private ISymbolicExpressionTreeNode MakeVarianceAggregation(ISymbolicExpressionTreeNode node) {
1644      if (IsScalarNode(node)) {
1645        return MakeConstant(0.0);
1646      } else if (IsAddition(node) || IsSubtraction(node)) { // scalars drop out
1647        var terms = node.Subtrees;
1648
1649        var scalarTerms = terms.Where(IsScalarNode).ToList();
1650        var remainingTerms = terms.Except(scalarTerms).ToList();
1651
1652        if (remainingTerms.Any()) {
1653          var vectorNode = remainingTerms.Aggregate(MakeSum);
1654
1655          var varNode = varianceSymbol.CreateTreeNode();
1656          varNode.AddSubtree(vectorNode);
1657
1658          return varNode;
1659        } else if (scalarTerms.Any()) {
1660          return MakeConstant(0.0);
1661        } else
1662          throw new InvalidOperationException("Addition does not contain any terms to simplify.");
1663      } else if (IsMultiplication(node) || IsDivision(node)) {
1664        var factors = node.Subtrees;
1665        if (IsDivision(node)) factors = InvertNodes(factors, Invert);
1666
1667        var scalarFactors = factors.Where(IsScalarNode).ToList();
1668        var remainingFactors = factors.Except(scalarFactors).ToList();
1669
1670        if (scalarFactors.Any() && remainingFactors.Any()) {
1671          var scalarNode = scalarFactors.Aggregate(MakeProduct);
1672          var vectorNode = remainingFactors.Aggregate(MakeProduct);
1673
1674          var varNode = MakeVarianceAggregation(vectorNode);
1675
1676          return MakeProduct(MakeSquare(scalarNode), varNode);
1677        } else if (scalarFactors.Any()) {
1678          var scalarNode = scalarFactors.Aggregate(MakeProduct);
1679          return MakeSquare(scalarNode);
1680        } else if (remainingFactors.Any()) {
1681          var vectorNode = remainingFactors.Aggregate(MakeProduct);
1682          var varNode = varianceSymbol.CreateTreeNode();
1683          varNode.AddSubtree(vectorNode);
1684          return varNode;
1685        } else
1686          throw new InvalidOperationException("Multiplication does not contain any terms to simplify.");
1687      } else if (IsVariableBase(node)) { // weight is like multiplication
1688        var variableNode = (VariableTreeNodeBase)node;
1689        var weight = variableNode.Weight;
1690        variableNode.Weight = 1.0;
1691        var varNode = varianceSymbol.CreateTreeNode();
1692        varNode.AddSubtree(node);
1693        return MakeProduct(MakeSquare(MakeConstant(weight)), varNode);
1694      } else {
1695        var varNode = varianceSymbol.CreateTreeNode();
1696        varNode.AddSubtree(node);
1697        return varNode;
1698      }
1699    }
1700    #endregion
1701
1702    #region helper functions
1703
1704    private bool ContainsVariableCondition(ISymbolicExpressionTreeNode node) {
1705      if (node.Symbol is VariableCondition) return true;
1706      foreach (var subtree in node.Subtrees)
1707        if (ContainsVariableCondition(subtree)) return true;
1708      return false;
1709    }
1710
1711    private ISymbolicExpressionTreeNode AddLagToDynamicNodes(ISymbolicExpressionTreeNode node, int lag) {
1712      var laggedTreeNode = node as ILaggedTreeNode;
1713      var variableNode = node as VariableTreeNode;
1714      var variableConditionNode = node as VariableConditionTreeNode;
1715      if (laggedTreeNode != null)
1716        laggedTreeNode.Lag += lag;
1717      else if (variableNode != null) {
1718        var laggedVariableNode = (LaggedVariableTreeNode)laggedVariableSymbol.CreateTreeNode();
1719        laggedVariableNode.Lag = lag;
1720        laggedVariableNode.VariableName = variableNode.VariableName;
1721        return laggedVariableNode;
1722      } else if (variableConditionNode != null) {
1723        throw new NotSupportedException("Removal of time lags around variable condition symbols is not allowed.");
1724      }
1725      var subtrees = new List<ISymbolicExpressionTreeNode>(node.Subtrees);
1726      while (node.SubtreeCount > 0) node.RemoveSubtree(0);
1727      foreach (var subtree in subtrees) {
1728        node.AddSubtree(AddLagToDynamicNodes(subtree, lag));
1729      }
1730      return node;
1731    }
1732
1733    private bool AreSameTypeAndVariable(ISymbolicExpressionTreeNode a, ISymbolicExpressionTreeNode b) {
1734      return GroupId((IVariableTreeNode)a) == GroupId((IVariableTreeNode)b);
1735    }
1736
1737    // helper to combine the constant factors in products and to combine variables (powers of 2, 3...)
1738    private void MergeVariablesAndConstantsInProduct(ISymbolicExpressionTreeNode prod) {
1739      var subtrees = new List<ISymbolicExpressionTreeNode>(prod.Subtrees);
1740      while (prod.Subtrees.Any()) prod.RemoveSubtree(0);
1741      var groupedVarNodes = from node in subtrees.OfType<IVariableTreeNode>()
1742                            where node.SubtreeCount == 0
1743                            group node by GroupId(node) into g
1744                            orderby g.Count()
1745                            select g;
1746      var constantProduct = (from node in subtrees.OfType<VariableTreeNodeBase>()
1747                             select node.Weight)
1748        .Concat(from node in subtrees.OfType<ConstantTreeNode>()
1749                select node.Value)
1750        .DefaultIfEmpty(1.0)
1751        .Aggregate((c1, c2) => c1 * c2);
1752
1753      var unchangedSubtrees = from tree in subtrees
1754                              where tree.SubtreeCount > 0 || !(tree is IVariableTreeNode) && !(tree is ConstantTreeNode)
1755                              select tree;
1756
1757      foreach (var variableNodeGroup in groupedVarNodes) {
1758        var firstNode = variableNodeGroup.First();
1759        if (firstNode is VariableTreeNodeBase) {
1760          var representative = (VariableTreeNodeBase)firstNode;
1761          representative.Weight = 1.0;
1762          if (variableNodeGroup.Count() > 1) {
1763            var poly = mulSymbol.CreateTreeNode();
1764            for (int p = 0; p < variableNodeGroup.Count(); p++) {
1765              poly.AddSubtree((ISymbolicExpressionTreeNode)representative.Clone());
1766            }
1767            prod.AddSubtree(poly);
1768          } else {
1769            prod.AddSubtree(representative);
1770          }
1771        } else if (firstNode is FactorVariableTreeNode) {
1772          var representative = (FactorVariableTreeNode)firstNode;
1773          foreach (var node in variableNodeGroup.Skip(1).Cast<FactorVariableTreeNode>()) {
1774            for (int j = 0; j < representative.Weights.Length; j++) {
1775              representative.Weights[j] *= node.Weights[j];
1776            }
1777          }
1778          for (int j = 0; j < representative.Weights.Length; j++) {
1779            representative.Weights[j] *= constantProduct;
1780          }
1781          constantProduct = 1.0;
1782          // if the product already contains a factor it is not necessary to multiply a constant below
1783          prod.AddSubtree(representative);
1784        }
1785      }
1786
1787      foreach (var unchangedSubtree in unchangedSubtrees)
1788        prod.AddSubtree(unchangedSubtree);
1789
1790      if (!constantProduct.IsAlmost(1.0)) {
1791        prod.AddSubtree(MakeConstant(constantProduct));
1792      }
1793    }
1794
1795
1796    /// <summary>
1797    /// x => x * -1
1798    /// Is only used in cases where it is not necessary to create new tree nodes. Manipulates x directly.
1799    /// </summary>
1800    /// <param name="x"></param>
1801    /// <returns>-x</returns>
1802    private ISymbolicExpressionTreeNode Negate(ISymbolicExpressionTreeNode x) {
1803      if (IsConstant(x)) {
1804        ((ConstantTreeNode)x).Value *= -1;
1805      } else if (IsVariableBase(x)) {
1806        var variableTree = (VariableTreeNodeBase)x;
1807        variableTree.Weight *= -1.0;
1808      } else if (IsFactor(x)) {
1809        var factorNode = (FactorVariableTreeNode)x;
1810        for (int i = 0; i < factorNode.Weights.Length; i++) factorNode.Weights[i] *= -1;
1811      } else if (IsBinFactor(x)) {
1812        var factorNode = (BinaryFactorVariableTreeNode)x;
1813        factorNode.Weight *= -1;
1814      } else if (IsAddition(x)) {
1815        // (x0 + x1 + .. + xn) * -1 => (-x0 + -x1 + .. + -xn)       
1816        var subtrees = new List<ISymbolicExpressionTreeNode>(x.Subtrees);
1817        while (x.Subtrees.Any()) x.RemoveSubtree(0);
1818        foreach (var subtree in subtrees) {
1819          x.AddSubtree(Negate(subtree));
1820        }
1821      } else if (IsMultiplication(x) || IsDivision(x)) {
1822        // x0 * x1 * .. * xn * -1 => x0 * x1 * .. * -xn
1823        var lastSubTree = x.Subtrees.Last();
1824        x.RemoveSubtree(x.SubtreeCount - 1);
1825        x.AddSubtree(Negate(lastSubTree)); // last is maybe a constant, prefer to negate the constant
1826      } else {
1827        // any other function
1828        return MakeProduct(x, MakeConstant(-1));
1829      }
1830      return x;
1831    }
1832
1833    /// <summary>
1834    /// x => 1/x
1835    /// Must create new tree nodes
1836    /// </summary>
1837    /// <param name="x"></param>
1838    /// <returns></returns>
1839    private ISymbolicExpressionTreeNode Invert(ISymbolicExpressionTreeNode x) {
1840      if (IsConstant(x)) {
1841        return MakeConstant(1.0 / ((ConstantTreeNode)x).Value);
1842      } else if (IsFactor(x)) {
1843        var factorNode = (FactorVariableTreeNode)x;
1844        return MakeFactor(factorNode.Symbol, factorNode.VariableName, factorNode.Weights.Select(w => 1.0 / w));
1845      } else if (IsDivision(x)) {
1846        return MakeFraction(x.GetSubtree(1), x.GetSubtree(0));
1847      } else {
1848        // any other function
1849        return MakeFraction(MakeConstant(1), x);
1850      }
1851    }
1852
1853    private static ISymbolicExpressionTreeNode MakeConstant(double value) {
1854      ConstantTreeNode constantTreeNode = (ConstantTreeNode)(constSymbol.CreateTreeNode());
1855      constantTreeNode.Value = value;
1856      return constantTreeNode;
1857    }
1858
1859    private static ISymbolicExpressionTreeNode MakeFactor(FactorVariable sy, string variableName, IEnumerable<double> weights) {
1860      var tree = (FactorVariableTreeNode)sy.CreateTreeNode();
1861      tree.VariableName = variableName;
1862      tree.Weights = weights.ToArray();
1863      return tree;
1864    }
1865    private static ISymbolicExpressionTreeNode MakeBinFactor(BinaryFactorVariable sy, string variableName, string variableValue, double weight) {
1866      var tree = (BinaryFactorVariableTreeNode)sy.CreateTreeNode();
1867      tree.VariableName = variableName;
1868      tree.VariableValue = variableValue;
1869      tree.Weight = weight;
1870      return tree;
1871    }
1872    private static IEnumerable<ISymbolicExpressionTreeNode> InvertNodes(IEnumerable<ISymbolicExpressionTreeNode> nodes, Func<ISymbolicExpressionTreeNode, ISymbolicExpressionTreeNode> invertFunc) {
1873      if (nodes.Count() == 1)
1874        return nodes.Select(invertFunc);
1875      var first = nodes.First().ToEnumerable();
1876      var remaining = nodes.Skip(1).Select(invertFunc);
1877      return first.Concat(remaining);
1878    }
1879
1880    #endregion
1881  }
1882}
Note: See TracBrowser for help on using the repository browser.