Free cookie consent management tool by TermsFeed Policy Generator

source: trunk/sources/HeuristicLab.Problems.DataAnalysis/3.3/Symbolic/SymbolicSimplifier.cs @ 5455

Last change on this file since 5455 was 5455, checked in by gkronber, 12 years ago

#1227 Merged changesets r4878 and r4880 from branch into trunk.

File size: 32.3 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2011 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
4 *
5 * This file is part of HeuristicLab.
6 *
7 * HeuristicLab is free software: you can redistribute it and/or modify
8 * it under the terms of the GNU General Public License as published by
9 * the Free Software Foundation, either version 3 of the License, or
10 * (at your option) any later version.
11 *
12 * HeuristicLab is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15 * GNU General Public License for more details.
16 *
17 * You should have received a copy of the GNU General Public License
18 * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
19 */
20#endregion
21
22using System;
23using System.Collections.Generic;
24using System.Diagnostics;
25using System.Linq;
26using HeuristicLab.Common;
27using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
28using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.Symbols;
29using HeuristicLab.Problems.DataAnalysis.Symbolic.Symbols;
30
31namespace HeuristicLab.Problems.DataAnalysis.Symbolic {
32  /// <summary>
33  /// Simplistic simplifier for arithmetic expressions
34  /// </summary>
35  public class SymbolicSimplifier {
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 Sine sineSymbol = new Sine();
44    private Cosine cosineSymbol = new Cosine();
45    private Tangent tanSymbol = new Tangent();
46    private IfThenElse ifThenElseSymbol = new IfThenElse();
47    private And andSymbol = new And();
48    private Or orSymbol = new Or();
49    private Not notSymbol = new Not();
50    private GreaterThan gtSymbol = new GreaterThan();
51    private LessThan ltSymbol = new LessThan();
52
53    public SymbolicExpressionTree Simplify(SymbolicExpressionTree originalTree) {
54      var clone = (SymbolicExpressionTreeNode)originalTree.Root.Clone();
55      // macro expand (initially no argument trees)
56      var macroExpandedTree = MacroExpand(clone, clone.SubTrees[0], new List<SymbolicExpressionTreeNode>());
57      SymbolicExpressionTreeNode rootNode = (new ProgramRootSymbol()).CreateTreeNode();
58      rootNode.AddSubTree(GetSimplifiedTree(macroExpandedTree));
59      return new SymbolicExpressionTree(rootNode);
60    }
61
62    // the argumentTrees list contains already expanded trees used as arguments for invocations
63    private SymbolicExpressionTreeNode MacroExpand(SymbolicExpressionTreeNode root, SymbolicExpressionTreeNode node, IList<SymbolicExpressionTreeNode> argumentTrees) {
64      List<SymbolicExpressionTreeNode> subtrees = new List<SymbolicExpressionTreeNode>(node.SubTrees);
65      while (node.SubTrees.Count > 0) node.RemoveSubTree(0);
66      if (node.Symbol is InvokeFunction) {
67        var invokeSym = node.Symbol as InvokeFunction;
68        var defunNode = FindFunctionDefinition(root, invokeSym.FunctionName);
69        var macroExpandedArguments = new List<SymbolicExpressionTreeNode>();
70        foreach (var subtree in subtrees) {
71          macroExpandedArguments.Add(MacroExpand(root, subtree, argumentTrees));
72        }
73        return MacroExpand(root, defunNode, macroExpandedArguments);
74      } else if (node.Symbol is Argument) {
75        var argSym = node.Symbol as Argument;
76        // return the correct argument sub-tree (already macro-expanded)
77        return (SymbolicExpressionTreeNode)argumentTrees[argSym.ArgumentIndex].Clone();
78      } else {
79        // recursive application
80        foreach (var subtree in subtrees) {
81          node.AddSubTree(MacroExpand(root, subtree, argumentTrees));
82        }
83        return node;
84      }
85    }
86
87    private SymbolicExpressionTreeNode FindFunctionDefinition(SymbolicExpressionTreeNode root, string functionName) {
88      foreach (var subtree in root.SubTrees.OfType<DefunTreeNode>()) {
89        if (subtree.FunctionName == functionName) return subtree.SubTrees[0];
90      }
91
92      throw new ArgumentException("Definition of function " + functionName + " not found.");
93    }
94
95
96    #region symbol predicates
97    // arithmetic
98    private bool IsDivision(SymbolicExpressionTreeNode node) {
99      return node.Symbol is Division;
100    }
101
102    private bool IsMultiplication(SymbolicExpressionTreeNode node) {
103      return node.Symbol is Multiplication;
104    }
105
106    private bool IsSubtraction(SymbolicExpressionTreeNode node) {
107      return node.Symbol is Subtraction;
108    }
109
110    private bool IsAddition(SymbolicExpressionTreeNode node) {
111      return node.Symbol is Addition;
112    }
113
114    private bool IsAverage(SymbolicExpressionTreeNode node) {
115      return node.Symbol is Average;
116    }
117    // exponential
118    private bool IsLog(SymbolicExpressionTreeNode node) {
119      return node.Symbol is Logarithm;
120    }
121    private bool IsExp(SymbolicExpressionTreeNode node) {
122      return node.Symbol is Exponential;
123    }
124    // trigonometric
125    private bool IsSine(SymbolicExpressionTreeNode node) {
126      return node.Symbol is Sine;
127    }
128    private bool IsCosine(SymbolicExpressionTreeNode node) {
129      return node.Symbol is Cosine;
130    }
131    private bool IsTangent(SymbolicExpressionTreeNode node) {
132      return node.Symbol is Tangent;
133    }
134    // boolean
135    private bool IsIfThenElse(SymbolicExpressionTreeNode node) {
136      return node.Symbol is IfThenElse;
137    }
138    private bool IsAnd(SymbolicExpressionTreeNode node) {
139      return node.Symbol is And;
140    }
141    private bool IsOr(SymbolicExpressionTreeNode node) {
142      return node.Symbol is Or;
143    }
144    private bool IsNot(SymbolicExpressionTreeNode node) {
145      return node.Symbol is Not;
146    }
147    // comparison
148    private bool IsGreaterThan(SymbolicExpressionTreeNode node) {
149      return node.Symbol is GreaterThan;
150    }
151    private bool IsLessThan(SymbolicExpressionTreeNode node) {
152      return node.Symbol is LessThan;
153    }
154
155    // terminals
156    private bool IsVariable(SymbolicExpressionTreeNode node) {
157      return node.Symbol is Variable;
158    }
159
160    private bool IsConstant(SymbolicExpressionTreeNode node) {
161      return node.Symbol is Constant;
162    }
163
164    #endregion
165
166    /// <summary>
167    /// Creates a new simplified tree
168    /// </summary>
169    /// <param name="original"></param>
170    /// <returns></returns>
171    public SymbolicExpressionTreeNode GetSimplifiedTree(SymbolicExpressionTreeNode original) {
172      if (IsConstant(original) || IsVariable(original)) {
173        return (SymbolicExpressionTreeNode)original.Clone();
174      } else if (IsAddition(original)) {
175        return SimplifyAddition(original);
176      } else if (IsSubtraction(original)) {
177        return SimplifySubtraction(original);
178      } else if (IsMultiplication(original)) {
179        return SimplifyMultiplication(original);
180      } else if (IsDivision(original)) {
181        return SimplifyDivision(original);
182      } else if (IsAverage(original)) {
183        return SimplifyAverage(original);
184      } else if (IsLog(original)) {
185        return SimplifyLog(original);
186      } else if (IsExp(original)) {
187        return SimplifyExp(original);
188      } else if (IsSine(original)) {
189        return SimplifySine(original);
190      } else if (IsCosine(original)) {
191        return SimplifyCosine(original);
192      } else if (IsTangent(original)) {
193        return SimplifyTangent(original);
194      } else if (IsIfThenElse(original)) {
195        return SimplifyIfThenElse(original);
196      } else if (IsGreaterThan(original)) {
197        return SimplifyGreaterThan(original);
198      } else if (IsLessThan(original)) {
199        return SimplifyLessThan(original);
200      } else if (IsAnd(original)) {
201        return SimplifyAnd(original);
202      } else if (IsOr(original)) {
203        return SimplifyOr(original);
204      } else if (IsNot(original)) {
205        return SimplifyNot(original);
206      } else {
207        return SimplifyAny(original);
208      }
209    }
210
211
212    #region specific simplification routines
213    private SymbolicExpressionTreeNode SimplifyAny(SymbolicExpressionTreeNode original) {
214      // can't simplify this function but simplify all subtrees
215      List<SymbolicExpressionTreeNode> subTrees = new List<SymbolicExpressionTreeNode>(original.SubTrees);
216      while (original.SubTrees.Count > 0) original.RemoveSubTree(0);
217      var clone = (SymbolicExpressionTreeNode)original.Clone();
218      List<SymbolicExpressionTreeNode> simplifiedSubTrees = new List<SymbolicExpressionTreeNode>();
219      foreach (var subTree in subTrees) {
220        simplifiedSubTrees.Add(GetSimplifiedTree(subTree));
221        original.AddSubTree(subTree);
222      }
223      foreach (var simplifiedSubtree in simplifiedSubTrees) {
224        clone.AddSubTree(simplifiedSubtree);
225      }
226      if (simplifiedSubTrees.TrueForAll(t => IsConstant(t))) {
227        SimplifyConstantExpression(clone);
228      }
229      return clone;
230    }
231
232    private SymbolicExpressionTreeNode SimplifyConstantExpression(SymbolicExpressionTreeNode original) {
233      // not yet implemented
234      return original;
235    }
236
237    private SymbolicExpressionTreeNode SimplifyAverage(SymbolicExpressionTreeNode original) {
238      if (original.SubTrees.Count == 1) {
239        return GetSimplifiedTree(original.SubTrees[0]);
240      } else {
241        // simplify expressions x0..xn
242        // make sum(x0..xn) / n
243        Trace.Assert(original.SubTrees.Count > 1);
244        var sum = original.SubTrees
245          .Select(x => GetSimplifiedTree(x))
246          .Aggregate((a, b) => MakeSum(a, b));
247        return MakeFraction(sum, MakeConstant(original.SubTrees.Count));
248      }
249    }
250
251    private SymbolicExpressionTreeNode SimplifyDivision(SymbolicExpressionTreeNode original) {
252      if (original.SubTrees.Count == 1) {
253        return Invert(GetSimplifiedTree(original.SubTrees[0]));
254      } else {
255        // simplify expressions x0..xn
256        // make multiplication (x0 * 1/(x1 * x1 * .. * xn))
257        Trace.Assert(original.SubTrees.Count > 1);
258        var simplifiedTrees = original.SubTrees.Select(x => GetSimplifiedTree(x));
259        return
260          MakeProduct(simplifiedTrees.First(), Invert(simplifiedTrees.Skip(1).Aggregate((a, b) => MakeProduct(a, b))));
261      }
262    }
263
264    private SymbolicExpressionTreeNode SimplifyMultiplication(SymbolicExpressionTreeNode original) {
265      if (original.SubTrees.Count == 1) {
266        return GetSimplifiedTree(original.SubTrees[0]);
267      } else {
268        Trace.Assert(original.SubTrees.Count > 1);
269        return original.SubTrees
270          .Select(x => GetSimplifiedTree(x))
271          .Aggregate((a, b) => MakeProduct(a, b));
272      }
273    }
274
275    private SymbolicExpressionTreeNode SimplifySubtraction(SymbolicExpressionTreeNode original) {
276      if (original.SubTrees.Count == 1) {
277        return Negate(GetSimplifiedTree(original.SubTrees[0]));
278      } else {
279        // simplify expressions x0..xn
280        // make addition (x0,-x1..-xn)
281        Trace.Assert(original.SubTrees.Count > 1);
282        var simplifiedTrees = original.SubTrees.Select(x => GetSimplifiedTree(x));
283        return simplifiedTrees.Take(1)
284          .Concat(simplifiedTrees.Skip(1).Select(x => Negate(x)))
285          .Aggregate((a, b) => MakeSum(a, b));
286      }
287    }
288
289    private SymbolicExpressionTreeNode SimplifyAddition(SymbolicExpressionTreeNode original) {
290      if (original.SubTrees.Count == 1) {
291        return GetSimplifiedTree(original.SubTrees[0]);
292      } else {
293        // simplify expression x0..xn
294        // make addition (x0..xn)
295        Trace.Assert(original.SubTrees.Count > 1);
296        return original.SubTrees
297          .Select(x => GetSimplifiedTree(x))
298          .Aggregate((a, b) => MakeSum(a, b));
299      }
300    }
301
302    private SymbolicExpressionTreeNode SimplifyNot(SymbolicExpressionTreeNode original) {
303      return MakeNot(GetSimplifiedTree(original.SubTrees[0]));
304    }
305    private SymbolicExpressionTreeNode SimplifyOr(SymbolicExpressionTreeNode original) {
306      return original.SubTrees
307        .Select(x => GetSimplifiedTree(x))
308        .Aggregate((a, b) => MakeOr(a, b));
309    }
310    private SymbolicExpressionTreeNode SimplifyAnd(SymbolicExpressionTreeNode original) {
311      return original.SubTrees
312        .Select(x => GetSimplifiedTree(x))
313        .Aggregate((a, b) => MakeAnd(a, b));
314    }
315    private SymbolicExpressionTreeNode SimplifyLessThan(SymbolicExpressionTreeNode original) {
316      return MakeLessThan(GetSimplifiedTree(original.SubTrees[0]), GetSimplifiedTree(original.SubTrees[1]));
317    }
318    private SymbolicExpressionTreeNode SimplifyGreaterThan(SymbolicExpressionTreeNode original) {
319      return MakeGreaterThan(GetSimplifiedTree(original.SubTrees[0]), GetSimplifiedTree(original.SubTrees[1]));
320    }
321    private SymbolicExpressionTreeNode SimplifyIfThenElse(SymbolicExpressionTreeNode original) {
322      return MakeIfThenElse(GetSimplifiedTree(original.SubTrees[0]), GetSimplifiedTree(original.SubTrees[1]), GetSimplifiedTree(original.SubTrees[2]));
323    }
324    private SymbolicExpressionTreeNode SimplifyTangent(SymbolicExpressionTreeNode original) {
325      return MakeTangent(GetSimplifiedTree(original.SubTrees[0]));
326    }
327    private SymbolicExpressionTreeNode SimplifyCosine(SymbolicExpressionTreeNode original) {
328      return MakeCosine(GetSimplifiedTree(original.SubTrees[0]));
329    }
330    private SymbolicExpressionTreeNode SimplifySine(SymbolicExpressionTreeNode original) {
331      return MakeSine(GetSimplifiedTree(original.SubTrees[0]));
332    }
333    private SymbolicExpressionTreeNode SimplifyExp(SymbolicExpressionTreeNode original) {
334      return MakeExp(GetSimplifiedTree(original.SubTrees[0]));
335    }
336
337    private SymbolicExpressionTreeNode SimplifyLog(SymbolicExpressionTreeNode original) {
338      return MakeLog(GetSimplifiedTree(original.SubTrees[0]));
339    }
340
341    #endregion
342
343
344
345    #region low level tree restructuring
346    private SymbolicExpressionTreeNode MakeNot(SymbolicExpressionTreeNode t) {
347      return MakeProduct(t, MakeConstant(-1.0));
348    }
349
350    private SymbolicExpressionTreeNode MakeOr(SymbolicExpressionTreeNode a, SymbolicExpressionTreeNode b) {
351      if (IsConstant(a) && IsConstant(b)) {
352        var constA = a as ConstantTreeNode;
353        var constB = b as ConstantTreeNode;
354        if (constA.Value > 0.0 || constB.Value > 0.0) {
355          return MakeConstant(1.0);
356        } else {
357          return MakeConstant(-1.0);
358        }
359      } else if (IsConstant(a)) {
360        return MakeOr(b, a);
361      } else if (IsConstant(b)) {
362        var constT = b as ConstantTreeNode;
363        if (constT.Value > 0.0) {
364          // boolean expression is necessarily true
365          return MakeConstant(1.0);
366        } else {
367          // the constant value has no effect on the result of the boolean condition so we can drop the constant term
368          var orNode = orSymbol.CreateTreeNode();
369          orNode.AddSubTree(a);
370          return orNode;
371        }
372      } else {
373        var orNode = orSymbol.CreateTreeNode();
374        orNode.AddSubTree(a);
375        orNode.AddSubTree(b);
376        return orNode;
377      }
378    }
379    private SymbolicExpressionTreeNode MakeAnd(SymbolicExpressionTreeNode a, SymbolicExpressionTreeNode b) {
380      if (IsConstant(a) && IsConstant(b)) {
381        var constA = a as ConstantTreeNode;
382        var constB = b as ConstantTreeNode;
383        if (constA.Value > 0.0 && constB.Value > 0.0) {
384          return MakeConstant(1.0);
385        } else {
386          return MakeConstant(-1.0);
387        }
388      } else if (IsConstant(a)) {
389        return MakeAnd(b, a);
390      } else if (IsConstant(b)) {
391        var constB = b as ConstantTreeNode;
392        if (constB.Value > 0.0) {
393          // the constant value has no effect on the result of the boolean condition so we can drop the constant term
394          var andNode = andSymbol.CreateTreeNode();
395          andNode.AddSubTree(a);
396          return andNode;
397        } else {
398          // boolean expression is necessarily false
399          return MakeConstant(-1.0);
400        }
401      } else {
402        var andNode = andSymbol.CreateTreeNode();
403        andNode.AddSubTree(a);
404        andNode.AddSubTree(b);
405        return andNode;
406      }
407    }
408    private SymbolicExpressionTreeNode MakeLessThan(SymbolicExpressionTreeNode leftSide, SymbolicExpressionTreeNode rightSide) {
409      if (IsConstant(leftSide) && IsConstant(rightSide)) {
410        var lsConst = leftSide as ConstantTreeNode;
411        var rsConst = rightSide as ConstantTreeNode;
412        if (lsConst.Value < rsConst.Value) return MakeConstant(1.0);
413        else return MakeConstant(-1.0);
414      } else {
415        var ltNode = ltSymbol.CreateTreeNode();
416        ltNode.AddSubTree(leftSide);
417        ltNode.AddSubTree(rightSide);
418        return ltNode;
419      }
420    }
421    private SymbolicExpressionTreeNode MakeGreaterThan(SymbolicExpressionTreeNode leftSide, SymbolicExpressionTreeNode rightSide) {
422      if (IsConstant(leftSide) && IsConstant(rightSide)) {
423        var lsConst = leftSide as ConstantTreeNode;
424        var rsConst = rightSide as ConstantTreeNode;
425        if (lsConst.Value > rsConst.Value) return MakeConstant(1.0);
426        else return MakeConstant(-1.0);
427      } else {
428        var gtNode = gtSymbol.CreateTreeNode();
429        gtNode.AddSubTree(leftSide);
430        gtNode.AddSubTree(rightSide);
431        return gtNode;
432      }
433    }
434    private SymbolicExpressionTreeNode MakeIfThenElse(SymbolicExpressionTreeNode condition, SymbolicExpressionTreeNode trueBranch, SymbolicExpressionTreeNode falseBranch) {
435      if (IsConstant(condition)) {
436        var constT = condition as ConstantTreeNode;
437        if (constT.Value > 0.0) return trueBranch;
438        else return falseBranch;
439      } else {
440        var ifNode = ifThenElseSymbol.CreateTreeNode();
441        ifNode.AddSubTree(condition);
442        ifNode.AddSubTree(trueBranch);
443        ifNode.AddSubTree(falseBranch);
444        return ifNode;
445      }
446    }
447    private SymbolicExpressionTreeNode MakeSine(SymbolicExpressionTreeNode node) {
448      // todo implement more transformation rules
449      if (IsConstant(node)) {
450        var constT = node as ConstantTreeNode;
451        return MakeConstant(Math.Sin(constT.Value));
452      } else {
453        var sineNode = sineSymbol.CreateTreeNode();
454        sineNode.AddSubTree(node);
455        return sineNode;
456      }
457    }
458    private SymbolicExpressionTreeNode MakeTangent(SymbolicExpressionTreeNode node) {
459      // todo implement more transformation rules
460      if (IsConstant(node)) {
461        var constT = node as ConstantTreeNode;
462        return MakeConstant(Math.Tan(constT.Value));
463      } else {
464        var tanNode = tanSymbol.CreateTreeNode();
465        tanNode.AddSubTree(node);
466        return tanNode;
467      }
468    }
469    private SymbolicExpressionTreeNode MakeCosine(SymbolicExpressionTreeNode node) {
470      // todo implement more transformation rules
471      if (IsConstant(node)) {
472        var constT = node as ConstantTreeNode;
473        return MakeConstant(Math.Cos(constT.Value));
474      } else {
475        var cosNode = cosineSymbol.CreateTreeNode();
476        cosNode.AddSubTree(node);
477        return cosNode;
478      }
479    }
480    private SymbolicExpressionTreeNode MakeExp(SymbolicExpressionTreeNode node) {
481      // todo implement more transformation rules
482      if (IsConstant(node)) {
483        var constT = node as ConstantTreeNode;
484        return MakeConstant(Math.Exp(constT.Value));
485      } else {
486        var expNode = expSymbol.CreateTreeNode();
487        expNode.AddSubTree(node);
488        return expNode;
489      }
490    }
491    private SymbolicExpressionTreeNode MakeLog(SymbolicExpressionTreeNode node) {
492      // todo implement more transformation rules
493      if (IsConstant(node)) {
494        var constT = node as ConstantTreeNode;
495        return MakeConstant(Math.Log(constT.Value));
496      } else {
497        var logNode = logSymbol.CreateTreeNode();
498        logNode.AddSubTree(node);
499        return logNode;
500      }
501    }
502
503
504    // MakeFraction, MakeProduct and MakeSum take two already simplified trees and create a new simplified tree
505
506    private SymbolicExpressionTreeNode MakeFraction(SymbolicExpressionTreeNode a, SymbolicExpressionTreeNode b) {
507      if (IsConstant(a) && IsConstant(b)) {
508        // fold constants
509        return MakeConstant(((ConstantTreeNode)a).Value / ((ConstantTreeNode)b).Value);
510      } if (IsConstant(a) && !((ConstantTreeNode)a).Value.IsAlmost(1.0)) {
511        return MakeFraction(MakeConstant(1.0), MakeProduct(b, Invert(a)));
512      } else if (IsVariable(a) && IsConstant(b)) {
513        // merge constant values into variable weights
514        var constB = ((ConstantTreeNode)b).Value;
515        ((VariableTreeNode)a).Weight /= constB;
516        return a;
517      } else if (IsAddition(a) && IsConstant(b)) {
518        return a.SubTrees
519          .Select(x => GetSimplifiedTree(x))
520         .Select(x => MakeFraction(x, b))
521         .Aggregate((c, d) => MakeSum(c, d));
522      } else if (IsMultiplication(a) && IsConstant(b)) {
523        return MakeProduct(a, Invert(b));
524      } else if (IsDivision(a) && IsConstant(b)) {
525        // (a1 / a2) / c => (a1 / (a2 * c))
526        Trace.Assert(a.SubTrees.Count == 2);
527        return MakeFraction(a.SubTrees[0], MakeProduct(a.SubTrees[1], b));
528      } else if (IsDivision(a) && IsDivision(b)) {
529        // (a1 / a2) / (b1 / b2) =>
530        Trace.Assert(a.SubTrees.Count == 2);
531        Trace.Assert(b.SubTrees.Count == 2);
532        return MakeFraction(MakeProduct(a.SubTrees[0], b.SubTrees[1]), MakeProduct(a.SubTrees[1], b.SubTrees[0]));
533      } else if (IsDivision(a)) {
534        // (a1 / a2) / b => (a1 / (a2 * b))
535        Trace.Assert(a.SubTrees.Count == 2);
536        return MakeFraction(a.SubTrees[0], MakeProduct(a.SubTrees[1], b));
537      } else if (IsDivision(b)) {
538        // a / (b1 / b2) => (a * b2) / b1
539        Trace.Assert(b.SubTrees.Count == 2);
540        return MakeFraction(MakeProduct(a, b.SubTrees[1]), b.SubTrees[0]);
541      } else {
542        var div = divSymbol.CreateTreeNode();
543        div.AddSubTree(a);
544        div.AddSubTree(b);
545        return div;
546      }
547    }
548
549    private SymbolicExpressionTreeNode MakeSum(SymbolicExpressionTreeNode a, SymbolicExpressionTreeNode b) {
550      if (IsConstant(a) && IsConstant(b)) {
551        // fold constants
552        ((ConstantTreeNode)a).Value += ((ConstantTreeNode)b).Value;
553        return a;
554      } else if (IsConstant(a)) {
555        // c + x => x + c
556        // b is not constant => make sure constant is on the right
557        return MakeSum(b, a);
558      } else if (IsConstant(b) && ((ConstantTreeNode)b).Value.IsAlmost(0.0)) {
559        // x + 0 => x
560        return a;
561      } else if (IsAddition(a) && IsAddition(b)) {
562        // merge additions
563        var add = addSymbol.CreateTreeNode();
564        for (int i = 0; i < a.SubTrees.Count - 1; i++) add.AddSubTree(a.SubTrees[i]);
565        for (int i = 0; i < b.SubTrees.Count - 1; i++) add.AddSubTree(b.SubTrees[i]);
566        if (IsConstant(a.SubTrees.Last()) && IsConstant(b.SubTrees.Last())) {
567          add.AddSubTree(MakeSum(a.SubTrees.Last(), b.SubTrees.Last()));
568        } else if (IsConstant(a.SubTrees.Last())) {
569          add.AddSubTree(b.SubTrees.Last());
570          add.AddSubTree(a.SubTrees.Last());
571        } else {
572          add.AddSubTree(a.SubTrees.Last());
573          add.AddSubTree(b.SubTrees.Last());
574        }
575        MergeVariablesInSum(add);
576        return add;
577      } else if (IsAddition(b)) {
578        return MakeSum(b, a);
579      } else if (IsAddition(a) && IsConstant(b)) {
580        // a is an addition and b is a constant => append b to a and make sure the constants are merged
581        var add = addSymbol.CreateTreeNode();
582        for (int i = 0; i < a.SubTrees.Count - 1; i++) add.AddSubTree(a.SubTrees[i]);
583        if (IsConstant(a.SubTrees.Last()))
584          add.AddSubTree(MakeSum(a.SubTrees.Last(), b));
585        else {
586          add.AddSubTree(a.SubTrees.Last());
587          add.AddSubTree(b);
588        }
589        return add;
590      } else if (IsAddition(a)) {
591        // a is already an addition => append b
592        var add = addSymbol.CreateTreeNode();
593        add.AddSubTree(b);
594        foreach (var subTree in a.SubTrees) {
595          add.AddSubTree(subTree);
596        }
597        MergeVariablesInSum(add);
598        return add;
599      } else {
600        var add = addSymbol.CreateTreeNode();
601        add.AddSubTree(a);
602        add.AddSubTree(b);
603        MergeVariablesInSum(add);
604        return add;
605      }
606    }
607
608    // makes sure variable symbols in sums are combined
609    // possible improvment: combine sums of products where the products only reference the same variable
610    private void MergeVariablesInSum(SymbolicExpressionTreeNode sum) {
611      var subtrees = new List<SymbolicExpressionTreeNode>(sum.SubTrees);
612      while (sum.SubTrees.Count > 0) sum.RemoveSubTree(0);
613      var groupedVarNodes = from node in subtrees.OfType<VariableTreeNode>()
614                            let lag = (node is LaggedVariableTreeNode) ? ((LaggedVariableTreeNode)node).Lag : 0
615                            group node by node.VariableName + lag into g
616                            select g;
617      var unchangedSubTrees = subtrees.Where(t => !(t is VariableTreeNode));
618
619      foreach (var variableNodeGroup in groupedVarNodes) {
620        var weightSum = variableNodeGroup.Select(t => t.Weight).Sum();
621        var representative = variableNodeGroup.First();
622        representative.Weight = weightSum;
623        sum.AddSubTree(representative);
624      }
625      foreach (var unchangedSubtree in unchangedSubTrees)
626        sum.AddSubTree(unchangedSubtree);
627    }
628
629
630    private SymbolicExpressionTreeNode MakeProduct(SymbolicExpressionTreeNode a, SymbolicExpressionTreeNode b) {
631      if (IsConstant(a) && IsConstant(b)) {
632        // fold constants
633        ((ConstantTreeNode)a).Value *= ((ConstantTreeNode)b).Value;
634        return a;
635      } else if (IsConstant(a)) {
636        // a * $ => $ * a
637        return MakeProduct(b, a);
638      } else if (IsConstant(b) && ((ConstantTreeNode)b).Value.IsAlmost(1.0)) {
639        // $ * 1.0 => $
640        return a;
641      } else if (IsConstant(b) && IsVariable(a)) {
642        // multiply constants into variables weights
643        ((VariableTreeNode)a).Weight *= ((ConstantTreeNode)b).Value;
644        return a;
645      } else if (IsConstant(b) && IsAddition(a)) {
646        // multiply constants into additions
647        return a.SubTrees.Select(x => MakeProduct(x, b)).Aggregate((c, d) => MakeSum(c, d));
648      } else if (IsDivision(a) && IsDivision(b)) {
649        // (a1 / a2) * (b1 / b2) => (a1 * b1) / (a2 * b2)
650        Trace.Assert(a.SubTrees.Count == 2);
651        Trace.Assert(b.SubTrees.Count == 2);
652        return MakeFraction(MakeProduct(a.SubTrees[0], b.SubTrees[0]), MakeProduct(a.SubTrees[1], b.SubTrees[1]));
653      } else if (IsDivision(a)) {
654        // (a1 / a2) * b => (a1 * b) / a2
655        Trace.Assert(a.SubTrees.Count == 2);
656        return MakeFraction(MakeProduct(a.SubTrees[0], b), a.SubTrees[1]);
657      } else if (IsDivision(b)) {
658        // a * (b1 / b2) => (b1 * a) / b2
659        Trace.Assert(b.SubTrees.Count == 2);
660        return MakeFraction(MakeProduct(b.SubTrees[0], a), b.SubTrees[1]);
661      } else if (IsMultiplication(a) && IsMultiplication(b)) {
662        // merge multiplications (make sure constants are merged)
663        var mul = mulSymbol.CreateTreeNode();
664        for (int i = 0; i < a.SubTrees.Count; i++) mul.AddSubTree(a.SubTrees[i]);
665        for (int i = 0; i < b.SubTrees.Count; i++) mul.AddSubTree(b.SubTrees[i]);
666        MergeVariablesAndConstantsInProduct(mul);
667        return mul;
668      } else if (IsMultiplication(b)) {
669        return MakeProduct(b, a);
670      } else if (IsMultiplication(a)) {
671        // a is already an multiplication => append b
672        a.AddSubTree(b);
673        MergeVariablesAndConstantsInProduct(a);
674        return a;
675      } else {
676        var mul = mulSymbol.CreateTreeNode();
677        mul.SubTrees.Add(a);
678        mul.SubTrees.Add(b);
679        MergeVariablesAndConstantsInProduct(mul);
680        return mul;
681      }
682    }
683    #endregion
684
685    // helper to combine the constant factors in products and to combine variables (powers of 2, 3...)
686    private void MergeVariablesAndConstantsInProduct(SymbolicExpressionTreeNode prod) {
687      var subtrees = new List<SymbolicExpressionTreeNode>(prod.SubTrees);
688      while (prod.SubTrees.Count > 0) prod.RemoveSubTree(0);
689      var groupedVarNodes = from node in subtrees.OfType<VariableTreeNode>()
690                            let lag = (node is LaggedVariableTreeNode) ? ((LaggedVariableTreeNode)node).Lag : 0
691                            group node by node.VariableName + lag into g
692                            orderby g.Count()
693                            select g;
694      var constantProduct = (from node in subtrees.OfType<VariableTreeNode>()
695                             select node.Weight)
696                            .Concat(from node in subtrees.OfType<ConstantTreeNode>()
697                                    select node.Value)
698                            .DefaultIfEmpty(1.0)
699                            .Aggregate((c1, c2) => c1 * c2);
700
701      var unchangedSubTrees = from tree in subtrees
702                              where !(tree is VariableTreeNode)
703                              where !(tree is ConstantTreeNode)
704                              select tree;
705
706      foreach (var variableNodeGroup in groupedVarNodes) {
707        var representative = variableNodeGroup.First();
708        representative.Weight = 1.0;
709        if (variableNodeGroup.Count() > 1) {
710          var poly = mulSymbol.CreateTreeNode();
711          for (int p = 0; p < variableNodeGroup.Count(); p++) {
712            poly.AddSubTree((SymbolicExpressionTreeNode)representative.Clone());
713          }
714          prod.AddSubTree(poly);
715        } else {
716          prod.AddSubTree(representative);
717        }
718      }
719
720      foreach (var unchangedSubtree in unchangedSubTrees)
721        prod.AddSubTree(unchangedSubtree);
722
723      if (!constantProduct.IsAlmost(1.0)) {
724        prod.AddSubTree(MakeConstant(constantProduct));
725      }
726    }
727
728
729    #region helper functions
730    /// <summary>
731    /// x => x * -1
732    /// Doesn't create new trees and manipulates x
733    /// </summary>
734    /// <param name="x"></param>
735    /// <returns>-x</returns>
736    private SymbolicExpressionTreeNode Negate(SymbolicExpressionTreeNode x) {
737      if (IsConstant(x)) {
738        ((ConstantTreeNode)x).Value *= -1;
739      } else if (IsVariable(x)) {
740        var variableTree = (VariableTreeNode)x;
741        variableTree.Weight *= -1.0;
742      } else if (IsAddition(x)) {
743        // (x0 + x1 + .. + xn) * -1 => (-x0 + -x1 + .. + -xn)       
744        for (int i = 0; i < x.SubTrees.Count; i++)
745          x.SubTrees[i] = Negate(x.SubTrees[i]);
746      } else if (IsMultiplication(x) || IsDivision(x)) {
747        // x0 * x1 * .. * xn * -1 => x0 * x1 * .. * -xn
748        x.SubTrees[x.SubTrees.Count - 1] = Negate(x.SubTrees.Last()); // last is maybe a constant, prefer to negate the constant
749      } else {
750        // any other function
751        return MakeProduct(x, MakeConstant(-1));
752      }
753      return x;
754    }
755
756    /// <summary>
757    /// x => 1/x
758    /// Doesn't create new trees and manipulates x
759    /// </summary>
760    /// <param name="x"></param>
761    /// <returns></returns>
762    private SymbolicExpressionTreeNode Invert(SymbolicExpressionTreeNode x) {
763      if (IsConstant(x)) {
764        return MakeConstant(1.0 / ((ConstantTreeNode)x).Value);
765      } else if (IsDivision(x)) {
766        Trace.Assert(x.SubTrees.Count == 2);
767        return MakeFraction(x.SubTrees[1], x.SubTrees[0]);
768      } else {
769        // any other function
770        return MakeFraction(MakeConstant(1), x);
771      }
772    }
773
774    private SymbolicExpressionTreeNode MakeConstant(double value) {
775      ConstantTreeNode constantTreeNode = (ConstantTreeNode)(constSymbol.CreateTreeNode());
776      constantTreeNode.Value = value;
777      return (SymbolicExpressionTreeNode)constantTreeNode;
778    }
779
780    private SymbolicExpressionTreeNode MakeVariable(double weight, string name) {
781      var tree = (VariableTreeNode)varSymbol.CreateTreeNode();
782      tree.Weight = weight;
783      tree.VariableName = name;
784      return tree;
785    }
786    #endregion
787  }
788}
Note: See TracBrowser for help on using the repository browser.