Free cookie consent management tool by TermsFeed Policy Generator

source: trunk/sources/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Converters/TreeSimplifier.cs @ 14871

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

#2697: applied r14390, r14391, r14393, r14394, r14396 again (resolving conflicts)

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