Ignore:
Timestamp:
08/16/10 09:54:22 (11 years ago)
Author:
gkronber
Message:

Added better support for simplification of fractions and products and cleaned code a little bit. #1026

Location:
branches/DataAnalysis/HeuristicLab.Problems.DataAnalysis/3.3/Symbolic
Files:
2 edited

Legend:

Unmodified
Added
Removed
  • branches/DataAnalysis/HeuristicLab.Problems.DataAnalysis/3.3/Symbolic/SymbolicSimplifier.cs

    r4068 r4220  
    3232  /// <summary>
    3333  /// Simplistic simplifier for arithmetic expressions
    34   /// Rules:
    35   ///  * Constants are always the last argument to any function
    36   ///  * f(c1, c2) => c3 (constant expression folding)
    3734  /// </summary>
    3835  public class SymbolicSimplifier {
     
    8582    }
    8683
     84
     85    #region symbol predicates
     86    private bool IsDivision(SymbolicExpressionTreeNode original) {
     87      return original.Symbol is Division;
     88    }
     89
     90    private bool IsMultiplication(SymbolicExpressionTreeNode original) {
     91      return original.Symbol is Multiplication;
     92    }
     93
     94    private bool IsSubtraction(SymbolicExpressionTreeNode original) {
     95      return original.Symbol is Subtraction;
     96    }
     97
     98    private bool IsAddition(SymbolicExpressionTreeNode original) {
     99      return original.Symbol is Addition;
     100    }
     101
     102    private bool IsVariable(SymbolicExpressionTreeNode original) {
     103      return original.Symbol is Variable;
     104    }
     105
     106    private bool IsConstant(SymbolicExpressionTreeNode original) {
     107      return original.Symbol is Constant;
     108    }
     109
     110    private bool IsAverage(SymbolicExpressionTreeNode original) {
     111      return original.Symbol is Average;
     112    }
     113    private bool IsLog(SymbolicExpressionTreeNode original) {
     114      return original.Symbol is Logarithm;
     115    }
     116    #endregion
     117
    87118    /// <summary>
    88119    /// Creates a new simplified tree
     
    94125        return (SymbolicExpressionTreeNode)original.Clone();
    95126      } else if (IsAddition(original)) {
    96         if (original.SubTrees.Count == 1) {
    97           return GetSimplifiedTree(original.SubTrees[0]);
     127        return SimplifyAddition(original);
     128      } else if (IsSubtraction(original)) {
     129        return SimplifySubtraction(original);
     130      } else if (IsMultiplication(original)) {
     131        return SimplifyMultiplication(original);
     132      } else if (IsDivision(original)) {
     133        return SimplifyDivision(original);
     134      } else if (IsAverage(original)) {
     135        return SimplifyAverage(original);
     136      } else if (IsLog(original)) {
     137        // TODO simplify logarditm
     138        return SimplifyAny(original);
     139      } else if (IsAverage(original)) {
     140        return SimplifyAverage(original);
     141      } else {
     142        return SimplifyAny(original);
     143      }
     144    }
     145
     146    #region specific simplification routines
     147    private SymbolicExpressionTreeNode SimplifyAny(SymbolicExpressionTreeNode original) {
     148      // can't simplify this function but simplify all subtrees
     149      List<SymbolicExpressionTreeNode> subTrees = new List<SymbolicExpressionTreeNode>(original.SubTrees);
     150      while (original.SubTrees.Count > 0) original.RemoveSubTree(0);
     151      var clone = (SymbolicExpressionTreeNode)original.Clone();
     152      List<SymbolicExpressionTreeNode> simplifiedSubTrees = new List<SymbolicExpressionTreeNode>();
     153      foreach (var subTree in subTrees) {
     154        simplifiedSubTrees.Add(GetSimplifiedTree(subTree));
     155        original.AddSubTree(subTree);
     156      }
     157      foreach (var simplifiedSubtree in simplifiedSubTrees) {
     158        clone.AddSubTree(simplifiedSubtree);
     159      }
     160      if (simplifiedSubTrees.TrueForAll(t => IsConstant(t))) {
     161        SimplifyConstantExpression(clone);
     162      }
     163      return clone;
     164    }
     165
     166    private SymbolicExpressionTreeNode SimplifyConstantExpression(SymbolicExpressionTreeNode original) {
     167      // not yet implemented
     168      return original;
     169    }
     170
     171    private SymbolicExpressionTreeNode SimplifyAverage(SymbolicExpressionTreeNode original) {
     172      if (original.SubTrees.Count == 1) {
     173        return GetSimplifiedTree(original.SubTrees[0]);
     174      } else {
     175        // simplify expressions x0..xn
     176        // make sum(x0..xn) / n
     177        Trace.Assert(original.SubTrees.Count > 1);
     178        var sum = original.SubTrees
     179          .Select(x => GetSimplifiedTree(x))
     180          .Aggregate((a, b) => MakeSum(a, b));
     181        return MakeFraction(sum, MakeConstant(original.SubTrees.Count));
     182      }
     183    }
     184
     185    private SymbolicExpressionTreeNode SimplifyDivision(SymbolicExpressionTreeNode original) {
     186      if (original.SubTrees.Count == 1) {
     187        return Invert(GetSimplifiedTree(original.SubTrees[0]));
     188      } else {
     189        // simplify expressions x0..xn
     190        // make multiplication (x0 * 1/(x1 * x1 * .. * xn))
     191        Trace.Assert(original.SubTrees.Count > 1);
     192        var simplifiedTrees = original.SubTrees.Select(x => GetSimplifiedTree(x));
     193        return
     194          MakeProduct(simplifiedTrees.First(), Invert(simplifiedTrees.Skip(1).Aggregate((a, b) => MakeProduct(a, b))));
     195      }
     196    }
     197
     198    private SymbolicExpressionTreeNode SimplifyMultiplication(SymbolicExpressionTreeNode original) {
     199      if (original.SubTrees.Count == 1) {
     200        return GetSimplifiedTree(original.SubTrees[0]);
     201      } else {
     202        Trace.Assert(original.SubTrees.Count > 1);
     203        return original.SubTrees
     204          .Select(x => GetSimplifiedTree(x))
     205          .Aggregate((a, b) => MakeProduct(a, b));
     206      }
     207    }
     208
     209    private SymbolicExpressionTreeNode SimplifySubtraction(SymbolicExpressionTreeNode original) {
     210      if (original.SubTrees.Count == 1) {
     211        return Negate(GetSimplifiedTree(original.SubTrees[0]));
     212      } else {
     213        // simplify expressions x0..xn
     214        // make addition (x0,-x1..-xn)
     215        Trace.Assert(original.SubTrees.Count > 1);
     216        var simplifiedTrees = original.SubTrees.Select(x => GetSimplifiedTree(x));
     217        return simplifiedTrees.Take(1)
     218          .Concat(simplifiedTrees.Skip(1).Select(x => Negate(x)))
     219          .Aggregate((a, b) => MakeSum(a, b));
     220      }
     221    }
     222
     223    private SymbolicExpressionTreeNode SimplifyAddition(SymbolicExpressionTreeNode original) {
     224      if (original.SubTrees.Count == 1) {
     225        return GetSimplifiedTree(original.SubTrees[0]);
     226      } else {
     227        // simplify expression x0..xn
     228        // make addition (x0..xn)
     229        Trace.Assert(original.SubTrees.Count > 1);
     230        return original.SubTrees
     231          .Select(x => GetSimplifiedTree(x))
     232          .Aggregate((a, b) => MakeSum(a, b));
     233      }
     234    }
     235    #endregion
     236
     237
     238
     239    #region low level tree restructuring
     240    // each make* method must return a simplified tree
     241
     242    private SymbolicExpressionTreeNode MakeFraction(SymbolicExpressionTreeNode a, SymbolicExpressionTreeNode b) {
     243      if (IsConstant(a) && IsConstant(b)) {
     244        // fold constants
     245        return MakeConstant(((ConstantTreeNode)a).Value / ((ConstantTreeNode)b).Value);
     246      } if (IsConstant(a) && !((ConstantTreeNode)a).Value.IsAlmost(1.0)) {
     247        return MakeFraction(MakeConstant(1.0), MakeProduct(b, Invert(a)));
     248      } else if (IsVariable(a) && IsConstant(b)) {
     249        // merge constant values into variable weights
     250        var constB = ((ConstantTreeNode)b).Value;
     251        ((VariableTreeNode)a).Weight /= constB;
     252        return a;
     253      } else if (IsAddition(a) && IsConstant(b)) {
     254        return a.SubTrees
     255         .Select(x => MakeFraction(x, b))
     256         .Aggregate((c, d) => MakeSum(c, d));
     257      } else if (IsMultiplication(a) && IsConstant(b)) {
     258        return MakeProduct(a, Invert(b));
     259      } else if (IsDivision(a) && IsConstant(b)) {
     260        // (a1 / a2) / c => (a1 / (a2 * c))
     261        Trace.Assert(a.SubTrees.Count == 2);
     262        return MakeFraction(a.SubTrees[0], MakeProduct(a.SubTrees[1], b));
     263      } else if (IsDivision(a) && IsDivision(b)) {
     264        // (a1 / a2) / (b1 / b2) =>
     265        Trace.Assert(a.SubTrees.Count == 2);
     266        Trace.Assert(b.SubTrees.Count == 2);
     267        return MakeFraction(MakeProduct(a.SubTrees[0], b.SubTrees[1]), MakeProduct(a.SubTrees[1], b.SubTrees[0]));
     268      } else if (IsDivision(a)) {
     269        // (a1 / a2) / b => (a1 / (a2 * b))
     270        Trace.Assert(a.SubTrees.Count == 2);
     271        return MakeFraction(a.SubTrees[0], MakeProduct(a.SubTrees[1], b));
     272      } else if (IsDivision(b)) {
     273        // a / (b1 / b2) => (a * b2) / b1
     274        Trace.Assert(b.SubTrees.Count == 2);
     275        return MakeFraction(MakeProduct(a, b.SubTrees[1]), b.SubTrees[0]);
     276      } else {
     277        var div = divSymbol.CreateTreeNode();
     278        div.AddSubTree(a);
     279        div.AddSubTree(b);
     280        return div;
     281      }
     282    }
     283
     284    private SymbolicExpressionTreeNode MakeSum(SymbolicExpressionTreeNode a, SymbolicExpressionTreeNode b) {
     285      if (IsConstant(a) && IsConstant(b)) {
     286        // fold constants
     287        ((ConstantTreeNode)a).Value += ((ConstantTreeNode)b).Value;
     288        return a;
     289      } else if (IsConstant(a)) {
     290        // c + x => x + c
     291        // b is not constant => make sure constant is on the right
     292        return MakeSum(b, a);
     293      } else if (IsConstant(b) && ((ConstantTreeNode)b).Value.IsAlmost(0.0)) {
     294        // x + 0 => x
     295        return a;
     296      } else if (IsAddition(a) && IsAddition(b)) {
     297        // merge additions
     298        var add = addSymbol.CreateTreeNode();
     299        for (int i = 0; i < a.SubTrees.Count - 1; i++) add.AddSubTree(a.SubTrees[i]);
     300        for (int i = 0; i < b.SubTrees.Count - 1; i++) add.AddSubTree(b.SubTrees[i]);
     301        if (IsConstant(a.SubTrees.Last()) && IsConstant(b.SubTrees.Last())) {
     302          add.AddSubTree(MakeSum(a.SubTrees.Last(), b.SubTrees.Last()));
     303        } else if (IsConstant(a.SubTrees.Last())) {
     304          add.AddSubTree(b.SubTrees.Last());
     305          add.AddSubTree(a.SubTrees.Last());
    98306        } else {
    99           // simplify expression x0..xn
    100           // make addition (x0..xn)
    101           Trace.Assert(original.SubTrees.Count > 1);
    102           return original.SubTrees
    103             .Select(x => GetSimplifiedTree(x))
    104             .Aggregate((a, b) => MakeAddition(a, b));
    105         }
    106       } else if (IsSubtraction(original)) {
    107         if (original.SubTrees.Count == 1) {
    108           return Negate(GetSimplifiedTree(original.SubTrees[0]));
     307          add.AddSubTree(a.SubTrees.Last());
     308          add.AddSubTree(b.SubTrees.Last());
     309        }
     310        MergeVariablesInSum(add);
     311        return add;
     312      } else if (IsAddition(b)) {
     313        return MakeSum(b, a);
     314      } else if (IsAddition(a) && IsConstant(b)) {
     315        // a is an addition and b is a constant => append b to a and make sure the constants are merged
     316        var add = addSymbol.CreateTreeNode();
     317        for (int i = 0; i < a.SubTrees.Count - 1; i++) add.AddSubTree(a.SubTrees[i]);
     318        if (IsConstant(a.SubTrees.Last()))
     319          add.AddSubTree(MakeSum(a.SubTrees.Last(), b));
     320        else {
     321          add.AddSubTree(a.SubTrees.Last());
     322          add.AddSubTree(b);
     323        }
     324        return add;
     325      } else if (IsAddition(a)) {
     326        // a is already an addition => append b
     327        var add = addSymbol.CreateTreeNode();
     328        add.AddSubTree(b);
     329        foreach (var subTree in a.SubTrees) {
     330          add.AddSubTree(subTree);
     331        }
     332        MergeVariablesInSum(add);
     333        return add;
     334      } else {
     335        var add = addSymbol.CreateTreeNode();
     336        add.AddSubTree(a);
     337        add.AddSubTree(b);
     338        MergeVariablesInSum(add);
     339        return add;
     340      }
     341    }
     342
     343    private void MergeVariablesInSum(SymbolicExpressionTreeNode sum) {
     344      var subtrees = new List<SymbolicExpressionTreeNode>(sum.SubTrees);
     345      while (sum.SubTrees.Count > 0) sum.RemoveSubTree(0);
     346      var groupedVarNodes = from node in subtrees.OfType<VariableTreeNode>()
     347                            group node by node.VariableName into g
     348                            select g;
     349      var unchangedSubTrees = subtrees.Where(t => !(t is VariableTreeNode));
     350
     351      foreach (var variableNodeGroup in groupedVarNodes) {
     352        var weightSum = variableNodeGroup.Select(t => t.Weight).Sum();
     353        var representative = variableNodeGroup.First();
     354        representative.Weight = weightSum;
     355        sum.AddSubTree(representative);
     356      }
     357      foreach (var unchangedSubtree in unchangedSubTrees)
     358        sum.AddSubTree(unchangedSubtree);
     359    }
     360
     361
     362    private SymbolicExpressionTreeNode MakeProduct(SymbolicExpressionTreeNode a, SymbolicExpressionTreeNode b) {
     363      if (IsConstant(a) && IsConstant(b)) {
     364        // fold constants
     365        ((ConstantTreeNode)a).Value *= ((ConstantTreeNode)b).Value;
     366        return a;
     367      } else if (IsConstant(a)) {
     368        // a * $ => $ * a
     369        return MakeProduct(b, a);
     370      } else if (IsConstant(b) && ((ConstantTreeNode)b).Value.IsAlmost(1.0)) {
     371        // $ * 1.0 => $
     372        return a;
     373      } else if (IsConstant(b) && IsVariable(a)) {
     374        // multiply constants into variables weights
     375        ((VariableTreeNode)a).Weight *= ((ConstantTreeNode)b).Value;
     376        return a;
     377      } else if (IsConstant(b) && IsAddition(a)) {
     378        // multiply constants into additions
     379        return a.SubTrees.Select(x => MakeProduct(x, b)).Aggregate((c, d) => MakeSum(c, d));
     380      } else if (IsDivision(a) && IsDivision(b)) {
     381        // (a1 / a2) * (b1 / b2) => (a1 * b1) / (a2 * b2)
     382        Trace.Assert(a.SubTrees.Count == 2);
     383        Trace.Assert(b.SubTrees.Count == 2);
     384        return MakeFraction(MakeProduct(a.SubTrees[0], b.SubTrees[0]), MakeProduct(a.SubTrees[1], b.SubTrees[1]));
     385      } else if (IsDivision(a)) {
     386        // (a1 / a2) * b => (a1 * b) / a2
     387        Trace.Assert(a.SubTrees.Count == 2);
     388        return MakeFraction(MakeProduct(a.SubTrees[0], b), a.SubTrees[1]);
     389      } else if (IsDivision(b)) {
     390        // a * (b1 / b2) => (b1 * a) / b2
     391        Trace.Assert(b.SubTrees.Count == 2);
     392        return MakeFraction(MakeProduct(b.SubTrees[0], a), b.SubTrees[1]);
     393      } else if (IsMultiplication(a) && IsMultiplication(b)) {
     394        // merge multiplications (make sure constants are merged)
     395        var mul = mulSymbol.CreateTreeNode();
     396        for (int i = 0; i < a.SubTrees.Count; i++) mul.AddSubTree(a.SubTrees[i]);
     397        for (int i = 0; i < b.SubTrees.Count; i++) mul.AddSubTree(b.SubTrees[i]);
     398        MergeVariablesAndConstantsInProduct(mul);
     399        return mul;
     400      } else if (IsMultiplication(b)) {
     401        return MakeProduct(b, a);
     402      } else if (IsMultiplication(a)) {
     403        // a is already an multiplication => append b
     404        a.AddSubTree(b);
     405        MergeVariablesAndConstantsInProduct(a);
     406        return a;
     407      } else {
     408        var mul = mulSymbol.CreateTreeNode();
     409        mul.SubTrees.Add(a);
     410        mul.SubTrees.Add(b);
     411        MergeVariablesAndConstantsInProduct(mul);
     412        return mul;
     413      }
     414    }
     415    #endregion
     416
     417    private void MergeVariablesAndConstantsInProduct(SymbolicExpressionTreeNode prod) {
     418      var subtrees = new List<SymbolicExpressionTreeNode>(prod.SubTrees);
     419      while (prod.SubTrees.Count > 0) prod.RemoveSubTree(0);
     420      var groupedVarNodes = from node in subtrees.OfType<VariableTreeNode>()
     421                            group node by node.VariableName into g
     422                            orderby g.Count()
     423                            select g;
     424      var constantProduct = (from node in subtrees.OfType<VariableTreeNode>()
     425                             select node.Weight)
     426                            .Concat(from node in subtrees.OfType<ConstantTreeNode>()
     427                                    select node.Value)
     428                            .DefaultIfEmpty(1.0)
     429                            .Aggregate((c1, c2) => c1 * c2);
     430
     431      var unchangedSubTrees = from tree in subtrees
     432                              where !(tree is VariableTreeNode)
     433                              where !(tree is ConstantTreeNode)
     434                              select tree;
     435
     436      foreach (var variableNodeGroup in groupedVarNodes) {
     437        var representative = variableNodeGroup.First();
     438        representative.Weight = 1.0;
     439        if (variableNodeGroup.Count() > 1) {
     440          var poly = mulSymbol.CreateTreeNode();
     441          for (int p = 0; p < variableNodeGroup.Count(); p++) {
     442            poly.AddSubTree((SymbolicExpressionTreeNode)representative.Clone());
     443          }
     444          prod.AddSubTree(poly);
    109445        } else {
    110           // simplify expressions x0..xn
    111           // make addition (x0,-x1..-xn)
    112           Trace.Assert(original.SubTrees.Count > 1);
    113           var simplifiedTrees = original.SubTrees.Select(x => GetSimplifiedTree(x));
    114           return simplifiedTrees.Take(1)
    115             .Concat(simplifiedTrees.Skip(1).Select(x => Negate(x)))
    116             .Aggregate((a, b) => MakeAddition(a, b));
    117         }
    118       } else if (IsMultiplication(original)) {
    119         if (original.SubTrees.Count == 1) {
    120           return GetSimplifiedTree(original.SubTrees[0]);
    121         } else {
    122           Trace.Assert(original.SubTrees.Count > 1);
    123           return original.SubTrees
    124             .Select(x => GetSimplifiedTree(x))
    125             .Aggregate((a, b) => MakeMultiplication(a, b));
    126         }
    127       } else if (IsDivision(original)) {
    128         if (original.SubTrees.Count == 1) {
    129           return Invert(GetSimplifiedTree(original.SubTrees[0]));
    130         } else {
    131           // simplify expressions x0..xn
    132           // make multiplication (x0 * 1/(x1 * x1 * .. * xn))
    133           Trace.Assert(original.SubTrees.Count > 1);
    134           var simplifiedTrees = original.SubTrees.Select(x => GetSimplifiedTree(x));
    135           return
    136             MakeMultiplication(simplifiedTrees.First(), Invert(simplifiedTrees.Skip(1).Aggregate((a, b) => MakeMultiplication(a, b))));
    137         }
    138       } else if (IsAverage(original)) {
    139         if (original.SubTrees.Count == 1) {
    140           return GetSimplifiedTree(original.SubTrees[0]);
    141         } else {
    142           // simpliy expressions x0..xn
    143           // make sum(x0..xn) / n
    144           Trace.Assert(original.SubTrees.Count > 1);
    145           var sum = original.SubTrees
    146             .Select(x => GetSimplifiedTree(x))
    147             .Aggregate((a, b) => MakeAddition(a, b));
    148           return MakeDivision(sum, MakeConstant(original.SubTrees.Count));
    149         }
    150       } else {
    151         // can't simplify this function but simplify all subtrees
    152         // TODO evaluate the function if original is a constant expression
    153         List<SymbolicExpressionTreeNode> subTrees = new List<SymbolicExpressionTreeNode>(original.SubTrees);
    154         while (original.SubTrees.Count > 0) original.RemoveSubTree(0);
    155         var clone = (SymbolicExpressionTreeNode)original.Clone();
    156         foreach (var subTree in subTrees) {
    157           clone.AddSubTree(GetSimplifiedTree(subTree));
    158           original.AddSubTree(subTree);
    159         }
    160         return clone;
    161       }
    162     }
    163 
     446          prod.AddSubTree(representative);
     447        }
     448      }
     449
     450      foreach (var unchangedSubtree in unchangedSubTrees)
     451        prod.AddSubTree(unchangedSubtree);
     452
     453      if (!constantProduct.IsAlmost(1.0)) {
     454        prod.AddSubTree(MakeConstant(constantProduct));
     455      }
     456    }
     457
     458
     459    #region helper functions
    164460    /// <summary>
    165461    /// x => x * -1
     
    184480      } else {
    185481        // any other function
    186         return MakeMultiplication(x, MakeConstant(-1));
     482        return MakeProduct(x, MakeConstant(-1));
    187483      }
    188484      return x;
     
    198494      if (IsConstant(x)) {
    199495        ((ConstantTreeNode)x).Value = 1.0 / ((ConstantTreeNode)x).Value;
     496      } else if (IsDivision(x)) {
     497        Trace.Assert(x.SubTrees.Count == 2);
     498        return MakeFraction(x.SubTrees[1], x.SubTrees[0]);
    200499      } else {
    201500        // any other function
    202         return MakeDivision(MakeConstant(1), x);
     501        return MakeFraction(MakeConstant(1), x);
    203502      }
    204503      return x;
    205504    }
    206 
    207     private SymbolicExpressionTreeNode MakeDivision(SymbolicExpressionTreeNode a, SymbolicExpressionTreeNode b) {
    208       if (IsConstant(a) && IsConstant(b)) {
    209         return MakeConstant(((ConstantTreeNode)a).Value / ((ConstantTreeNode)b).Value);
    210       } else if (IsVariable(a) && IsConstant(b)) {
    211         var constB = ((ConstantTreeNode)b).Value;
    212         ((VariableTreeNode)a).Weight /= constB;
    213         return a;
    214       } else {
    215         var div = divSymbol.CreateTreeNode();
    216         div.AddSubTree(a);
    217         div.AddSubTree(b);
    218         return div;
    219       }
    220     }
    221 
    222     private SymbolicExpressionTreeNode MakeAddition(SymbolicExpressionTreeNode a, SymbolicExpressionTreeNode b) {
    223       if (IsConstant(a) && IsConstant(b)) {
    224         // merge constants
    225         ((ConstantTreeNode)a).Value += ((ConstantTreeNode)b).Value;
    226         return a;
    227       } else if (IsConstant(a)) {
    228         // c + x => x + c
    229         // b is not constant => make sure constant is on the right
    230         return MakeAddition(b, a);
    231       } else if (IsConstant(b) && ((ConstantTreeNode)b).Value.IsAlmost(0.0)) {
    232         // x + 0 => x
    233         return a;
    234       } else if (IsAddition(a) && IsAddition(b)) {
    235         // merge additions
    236         var add = addSymbol.CreateTreeNode();
    237         for (int i = 0; i < a.SubTrees.Count - 1; i++) add.AddSubTree(a.SubTrees[i]);
    238         for (int i = 0; i < b.SubTrees.Count - 1; i++) add.AddSubTree(b.SubTrees[i]);
    239         if (IsConstant(a.SubTrees.Last()) && IsConstant(b.SubTrees.Last())) {
    240           add.AddSubTree(MakeAddition(a.SubTrees.Last(), b.SubTrees.Last()));
    241         } else if (IsConstant(a.SubTrees.Last())) {
    242           add.AddSubTree(b.SubTrees.Last());
    243           add.AddSubTree(a.SubTrees.Last());
    244         } else {
    245           add.AddSubTree(a.SubTrees.Last());
    246           add.AddSubTree(b.SubTrees.Last());
    247         }
    248         MergeVariables(add);
    249         return add;
    250       } else if (IsAddition(b)) {
    251         return MakeAddition(b, a);
    252       } else if (IsAddition(a) && IsConstant(b)) {
    253         var add = addSymbol.CreateTreeNode();
    254         for (int i = 0; i < a.SubTrees.Count - 1; i++) add.AddSubTree(a.SubTrees[i]);
    255         if (IsConstant(a.SubTrees.Last()))
    256           add.AddSubTree(MakeAddition(a.SubTrees.Last(), b));
    257         else {
    258           add.AddSubTree(a.SubTrees.Last());
    259           add.AddSubTree(b);
    260         }
    261         return add;
    262       } else if (IsAddition(a)) {
    263         var add = addSymbol.CreateTreeNode();
    264         add.AddSubTree(b);
    265         foreach (var subTree in a.SubTrees) {
    266           add.AddSubTree(subTree);
    267         }
    268         MergeVariables(add);
    269         return add;
    270       } else {
    271         var add = addSymbol.CreateTreeNode();
    272         add.AddSubTree(a);
    273         add.AddSubTree(b);
    274         MergeVariables(add);
    275         return add;
    276       }
    277     }
    278 
    279     private void MergeVariables(SymbolicExpressionTreeNode add) {
    280       var subtrees = new List<SymbolicExpressionTreeNode>(add.SubTrees);
    281       while (add.SubTrees.Count > 0) add.RemoveSubTree(0);
    282       var groupedVarNodes = from node in subtrees.OfType<VariableTreeNode>()
    283                             group node by node.VariableName into g
    284                             select g;
    285       var unchangedSubTrees = subtrees.Where(t => !(t is VariableTreeNode));
    286 
    287       foreach (var variableNodeGroup in groupedVarNodes) {
    288         var weightSum = variableNodeGroup.Select(t => t.Weight).Sum();
    289         var representative = variableNodeGroup.First();
    290         representative.Weight = weightSum;
    291         add.AddSubTree(representative);
    292       }
    293       foreach (var unchangedSubtree in unchangedSubTrees)
    294         add.AddSubTree(unchangedSubtree);
    295     }
    296 
    297     private SymbolicExpressionTreeNode MakeMultiplication(SymbolicExpressionTreeNode a, SymbolicExpressionTreeNode b) {
    298       if (IsConstant(a) && IsConstant(b)) {
    299         ((ConstantTreeNode)a).Value *= ((ConstantTreeNode)b).Value;
    300         return a;
    301       } else if (IsConstant(a)) {
    302         return MakeMultiplication(b, a);
    303       } else if (IsConstant(b) && ((ConstantTreeNode)b).Value.IsAlmost(1.0)) {
    304         return a;
    305       } else if (IsConstant(b) && IsVariable(a)) {
    306         ((VariableTreeNode)a).Weight *= ((ConstantTreeNode)b).Value;
    307         return a;
    308       } else if (IsConstant(b) && IsAddition(a)) {
    309         return a.SubTrees.Select(x => MakeMultiplication(x, b)).Aggregate((c, d) => MakeAddition(c, d));
    310       } else if (IsDivision(a) && IsDivision(b)) {
    311         return MakeDivision(MakeMultiplication(a.SubTrees[0], b.SubTrees[0]), MakeMultiplication(a.SubTrees[1], b.SubTrees[1]));
    312       } else if (IsDivision(a)) {
    313         Trace.Assert(a.SubTrees.Count == 2);
    314         return MakeDivision(MakeMultiplication(a.SubTrees[0], b), a.SubTrees[1]);
    315       } else if (IsDivision(b)) {
    316         Trace.Assert(b.SubTrees.Count == 2);
    317         return MakeDivision(MakeMultiplication(b.SubTrees[0], a), b.SubTrees[1]);
    318       } else if (IsMultiplication(a) && IsMultiplication(b)) {
    319         var mul = mulSymbol.CreateTreeNode();
    320         for (int i = 0; i < a.SubTrees.Count - 1; i++) mul.AddSubTree(a.SubTrees[i]);
    321         for (int i = 0; i < b.SubTrees.Count - 1; i++) mul.AddSubTree(b.SubTrees[i]);
    322         mul.AddSubTree(MakeMultiplication(a.SubTrees.Last(), b.SubTrees.Last()));
    323         return mul;
    324       } else if (IsMultiplication(a)) {
    325         var mul = mulSymbol.CreateTreeNode();
    326         for (int i = 0; i < a.SubTrees.Count - 1; i++) mul.AddSubTree(a.SubTrees[i]);
    327         mul.AddSubTree(MakeMultiplication(a.SubTrees.Last(), b));
    328         return mul;
    329       } else if (IsMultiplication(b)) {
    330         var mul = mulSymbol.CreateTreeNode();
    331         for (int i = 0; i < b.SubTrees.Count - 1; i++) mul.AddSubTree(b.SubTrees[i]);
    332         mul.AddSubTree(MakeMultiplication(b.SubTrees.Last(), a));
    333         return mul;
    334       } else {
    335         var mul = mulSymbol.CreateTreeNode();
    336         mul.SubTrees.Add(a);
    337         mul.SubTrees.Add(b);
    338         return mul;
    339       }
    340     }
    341 
    342     #region is symbol ?
    343     private bool IsDivision(SymbolicExpressionTreeNode original) {
    344       return original.Symbol is Division;
    345     }
    346 
    347     private bool IsMultiplication(SymbolicExpressionTreeNode original) {
    348       return original.Symbol is Multiplication;
    349     }
    350 
    351     private bool IsSubtraction(SymbolicExpressionTreeNode original) {
    352       return original.Symbol is Subtraction;
    353     }
    354 
    355     private bool IsAddition(SymbolicExpressionTreeNode original) {
    356       return original.Symbol is Addition;
    357     }
    358 
    359     private bool IsVariable(SymbolicExpressionTreeNode original) {
    360       return original.Symbol is Variable;
    361     }
    362 
    363     private bool IsConstant(SymbolicExpressionTreeNode original) {
    364       return original.Symbol is Constant;
    365     }
    366 
    367     private bool IsAverage(SymbolicExpressionTreeNode original) {
    368       return original.Symbol is Average;
    369     }
    370     #endregion
    371505
    372506    private SymbolicExpressionTreeNode MakeConstant(double value) {
     
    382516      return tree;
    383517    }
     518    #endregion
    384519  }
    385520}
  • branches/DataAnalysis/HeuristicLab.Problems.DataAnalysis/3.3/Symbolic/Symbols/VariableTreeNode.cs

    r4068 r4220  
    2121
    2222using HeuristicLab.Core;
     23using HeuristicLab.Common;
    2324using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
    2425using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
     
    8081
    8182    public override string ToString() {
    82       return weight.ToString("E4") + " " + variableName;
     83      if (weight.IsAlmost(1.0)) return variableName;
     84      else return weight.ToString("E4") + " " + variableName;
    8385    }
    8486  }
Note: See TracChangeset for help on using the changeset viewer.