Free cookie consent management tool by TermsFeed Policy Generator

Ignore:
Timestamp:
09/23/14 16:59:16 (10 years ago)
Author:
bburlacu
Message:

#1772: Merged changes to SymbolicExpressionTreeMatching.cs from trunk.

File:
1 edited

Legend:

Unmodified
Added
Removed
  • branches/HeuristicLab.EvolutionTracking/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Matching/SymbolicExpressionTreeMatching.cs

    r10746 r11385  
    1 using System;
     1#region License Information
     2
     3/* HeuristicLab
     4 * Copyright (C) 2002-2014 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;
    225using System.Collections.Generic;
    326using System.Linq;
     
    4265      return matrix[m, n] + 1;
    4366    }
     67
     68    /// <summary>
     69    /// Calculates the difference between two symbolic expression trees.
     70    /// </summary>
     71    /// <param name="tree">The first symbolic expression tree</param>
     72    /// <param name="other">The second symbolic expression tree</param>
     73    /// <returns>Returns the root of the subtree (from T1) by which T1 differs from T2, or null if no difference is found.</returns>
     74    public static ISymbolicExpressionTreeNode Difference(this ISymbolicExpressionTree tree, ISymbolicExpressionTree other) {
     75      return Difference(tree.Root, other.Root);
     76    }
     77
     78    public static ISymbolicExpressionTreeNode Difference(this ISymbolicExpressionTreeNode node, ISymbolicExpressionTreeNode other) {
     79      var these = node.IterateNodesPrefix().ToList();
     80      var others = other.IterateNodesPrefix().ToList();
     81
     82      var minCount = Math.Min(these.Count, others.Count);
     83      var list = new List<ISymbolicExpressionTreeNode>();
     84
     85      for (int i = 0; i < minCount; ++i) {
     86        if (these[i].ToString() != others[i].ToString())
     87          list.Add(these[i]);
     88      }
     89
     90      return list.Count > 0 ? LowestCommonAncestor(node, list) : null;
     91    }
     92
     93    private static ISymbolicExpressionTreeNode LowestCommonAncestor(ISymbolicExpressionTreeNode root, List<ISymbolicExpressionTreeNode> nodes) {
     94      if (nodes.Count == 0)
     95        throw new ArgumentException("The nodes list should contain at least one element.");
     96
     97      if (nodes.Count == 1)
     98        return nodes[0];
     99
     100      int lowestLevel = nodes.Min(x => root.GetBranchLevel(x));
     101
     102      // bring the nodes in the nodes to the same level (relative to the root)
     103      for (int i = 0; i < nodes.Count; ++i) {
     104        var node = nodes[i];
     105        var level = root.GetBranchLevel(node);
     106        for (int j = lowestLevel; j < level; ++j)
     107          node = node.Parent;
     108        nodes[i] = node;
     109      }
     110
     111      // while not all the elements in the nodes are equal, go one level up
     112      while (nodes.Any(x => x != nodes[0])) {
     113        for (int i = 0; i < nodes.Count; ++i)
     114          nodes[i] = nodes[i].Parent;
     115      }
     116
     117      return nodes[0];
     118    }
    44119  }
    45120}
Note: See TracChangeset for help on using the changeset viewer.