Free cookie consent management tool by TermsFeed Policy Generator

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

Last change on this file since 14259 was 14259, checked in by gkronber, 8 years ago

#2650: added support for factor variables to Excel formatter and Excel exporter as well as to the Latex formatter and consequently the mathematical representation view.

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