Changeset 11943 for stable


Ignore:
Timestamp:
02/06/15 14:08:47 (6 years ago)
Author:
jkarder
Message:

#2164: merged r10562, r10563, r11384 and r11392 into stable

Location:
stable
Files:
6 edited
3 copied

Legend:

Unmodified
Added
Removed
  • stable

  • stable/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding

  • stable/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding-3.4.csproj

    r11920 r11943  
    147147    <Compile Include="Interfaces\ISymbolicExpressionGrammarBase.cs" />
    148148    <Compile Include="Interfaces\ISymbolicExpressionTreeGrammar.cs" />
     149    <Compile Include="Interfaces\ISymbolicExpressionTreeNodeComparer.cs" />
     150    <Compile Include="Interfaces\ISymbolicExpressionTreeNodeSimilarityComparer.cs" />
    149151    <Compile Include="Interfaces\Operators\ISymbolicExpressionTreeArchitectureAlteringOperator.cs" />
    150152    <Compile Include="Interfaces\Operators\ISymbolicExpressionTreeGrammarBasedOperator.cs" />
  • stable/HeuristicLab.Problems.DataAnalysis.Symbolic

  • stable/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/HeuristicLab.Problems.DataAnalysis.Symbolic-3.4.csproj

    r11920 r11943  
    135135    <Compile Include="Importer\Token.cs" />
    136136    <Compile Include="Interfaces\IModelBacktransformator.cs" />
     137    <Compile Include="Matching\SymbolicExpressionTreeCanonicalSorter.cs" />
     138    <Compile Include="Matching\SymbolicExpressionTreeEqualityComparer.cs" />
     139    <Compile Include="Matching\SymbolicExpressionTreeMatching.cs" />
     140    <Compile Include="Matching\SymbolicExpressionTreeMaxCommonSequenceCalculator.cs" />
     141    <Compile Include="Matching\SymbolicExpressionTreeNodeComparer.cs" />
     142    <Compile Include="Matching\SymbolicExpressionTreeNodeSimilarityComparer.cs" />
    137143    <Compile Include="SymbolicExpressionTreeBacktransformator.cs" />
    138144    <Compile Include="SymbolicDataAnalysisExpressionPruningOperator.cs" />
  • stable/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Matching/SymbolicExpressionTreeMatching.cs

    r10562 r11943  
    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;
     
    4568      return matrix[m, n] + 1;
    4669    }
     70
     71    /// <summary>
     72    /// Calculates the difference between two symbolic expression trees.
     73    /// </summary>
     74    /// <param name="tree">The first symbolic expression tree</param>
     75    /// <param name="other">The second symbolic expression tree</param>
     76    /// <returns>Returns the root of the subtree (from T1) by which T1 differs from T2, or null if no difference is found.</returns>
     77    public static ISymbolicExpressionTreeNode Difference(this ISymbolicExpressionTree tree, ISymbolicExpressionTree other) {
     78      return Difference(tree.Root, other.Root);
     79    }
     80
     81    public static ISymbolicExpressionTreeNode Difference(this ISymbolicExpressionTreeNode node, ISymbolicExpressionTreeNode other) {
     82      var a = node.IterateNodesPrefix().ToList();
     83      var b = other.IterateNodesPrefix().ToList();
     84      var list = new List<ISymbolicExpressionTreeNode>();
     85      for (int i = 0, j = 0; i < a.Count && j < b.Count; ++i, ++j) {
     86        var s1 = a[i].ToString();
     87        var s2 = b[j].ToString();
     88        if (s1 == s2) continue;
     89        list.Add(a[i]);
     90        // skip subtrees since the parents are already different
     91        i += a[i].SubtreeCount;
     92        j += b[j].SubtreeCount;
     93      }
     94      ISymbolicExpressionTreeNode result = list.Count > 0 ? LowestCommonAncestor(node, list) : null;
     95      return result;
     96    }
     97
     98    private static ISymbolicExpressionTreeNode LowestCommonAncestor(ISymbolicExpressionTreeNode root, List<ISymbolicExpressionTreeNode> nodes) {
     99      if (nodes.Count == 0)
     100        throw new ArgumentException("The nodes list should contain at least one element.");
     101
     102      if (nodes.Count == 1)
     103        return nodes[0];
     104
     105      int minLevel = nodes.Min(x => root.GetBranchLevel(x));
     106
     107      // bring the nodes in the nodes to the same level (relative to the root)
     108      for (int i = 0; i < nodes.Count; ++i) {
     109        var node = nodes[i];
     110        var level = root.GetBranchLevel(node);
     111        for (int j = minLevel; j < level; ++j)
     112          node = node.Parent;
     113        nodes[i] = node;
     114      }
     115
     116      // while not all the elements in the nodes are equal, go one level up
     117      while (nodes.Any(x => x != nodes[0])) {
     118        for (int i = 0; i < nodes.Count; ++i)
     119          nodes[i] = nodes[i].Parent;
     120      }
     121
     122      return nodes[0];
     123    }
    47124  }
    48125}
Note: See TracChangeset for help on using the changeset viewer.