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

Last change on this file since 14339 was 14339, checked in by gkronber, 6 years ago

#2650: fixed bug in simplification of factor symbols

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