Free cookie consent management tool by TermsFeed Policy Generator

Changeset 12929


Ignore:
Timestamp:
09/02/15 01:21:49 (9 years ago)
Author:
bburlacu
Message:

#1772: Initial implementation of tree pattern matching algorithm by Götz et al. (http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.182.5440). Added wildcard symbols and nodes and updated the matching code accordingly.

Location:
branches/HeuristicLab.EvolutionTracking/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4
Files:
6 added
3 edited

Legend:

Unmodified
Added
Removed
  • branches/HeuristicLab.EvolutionTracking/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/HeuristicLab.Problems.DataAnalysis.Symbolic-3.4.csproj

    r12892 r12929  
    184184    <Compile Include="Analyzers\SymbolicDataAnalysisBottomUpDiversityAnalyzer.cs" />
    185185    <Compile Include="Analyzers\SymbolicDataAnalysisGeneticOperatorImprovementAnalyzer.cs" />
     186    <Compile Include="Symbols\Wildcards\AnyNode.cs" />
     187    <Compile Include="Symbols\Wildcards\AnySubtreeSymbol.cs" />
     188    <Compile Include="Symbols\Wildcards\AnySubtree.cs" />
     189    <Compile Include="Symbols\Wildcards\AnyNodeSymbol.cs" />
    186190    <Compile Include="Analyzers\SymbolicDataAnalysisSingleObjectivePruningAnalyzer.cs" />
    187191    <Compile Include="Analyzers\SymbolicDataAnalysisGenealogyAnalyzer.cs" />
     
    318322    <Compile Include="Tracking\TraceCalculator.cs" />
    319323    <Compile Include="TransformationToSymbolicTreeMapper.cs" />
     324    <Compile Include="TreeMatching\QueryMatch.cs" />
    320325    <Compile Include="TreeMatching\SymbolicExpressionTreeBottomUpSimilarityCalculator.cs" />
    321326    <Compile Include="TreeMatching\SymbolicExpressionTreeCanonicalSorter.cs" />
  • branches/HeuristicLab.EvolutionTracking/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/TreeMatching/SymbolicExpressionTreeMatching.cs

    r12155 r12929  
    5454    public static int Match(ISymbolicExpressionTreeNode a, ISymbolicExpressionTreeNode b, ISymbolicExpressionTreeNodeEqualityComparer comp) {
    5555      if (!comp.Equals(a, b)) return 0;
     56      // AnySubtree wildcards mach everything
     57      if (a is AnySubtree)
     58        return b.GetLength();
     59      if (b is AnySubtree)
     60        return a.GetLength();
     61
    5662      int m = a.SubtreeCount;
    5763      int n = b.SubtreeCount;
  • branches/HeuristicLab.EvolutionTracking/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/TreeMatching/SymbolicExpressionTreeNodeEqualityComparer.cs

    r12155 r12929  
    7676
    7777    public bool Equals(ISymbolicExpressionTreeNode a, ISymbolicExpressionTreeNode b) {
    78       if (!(a is SymbolicExpressionTreeTerminalNode))
    79         // if a and b are non terminal nodes, check equality of symbol names
    80         return !(b is SymbolicExpressionTreeTerminalNode) && a.Symbol.Name.Equals(b.Symbol.Name);
    81       var va = a as VariableTreeNode;
    82       if (va != null) {
     78      var sa = a as AnySubtree;
     79      var sb = b as AnySubtree;
     80
     81      if (sa != null || sb != null)
     82        return true;
     83
     84      if (a.SubtreeCount != b.SubtreeCount)
     85        return false;
     86
     87      var na = a as AnyNode;
     88      var nb = b as AnyNode;
     89      if (na != null || nb != null)
     90        return true;
     91
     92      var ta = a as SymbolicExpressionTreeTerminalNode;
     93      var tb = b as SymbolicExpressionTreeTerminalNode;
     94      if (ta != null && tb != null) {
     95        var ca = a as ConstantTreeNode;
     96        var cb = b as ConstantTreeNode;
     97        if (ca != null && cb != null)
     98          // both a and b are constants
     99          return !MatchConstantValues || ca.Value.Equals(cb.Value);
     100
     101        var va = a as VariableTreeNode;
    83102        var vb = b as VariableTreeNode;
    84         if (vb == null) return false;
     103        if (va != null && vb != null) {
     104          // both a and b are variables
     105          bool m1 = !MatchVariableNames || va.VariableName.Equals(vb.VariableName);
     106          bool m2 = !MatchVariableWeights || va.Weight.IsAlmost(vb.Weight);
     107          return m1 && m2;
     108        }
     109      }
     110      if (ta == null && tb == null) {
     111        // both a and b are non-terminal (function) nodes
     112        return a.Symbol.Name.Equals(b.Symbol.Name);
     113      }
    85114
    86         return (!MatchVariableNames || va.VariableName.Equals(vb.VariableName)) && (!MatchVariableWeights || va.Weight.Equals(vb.Weight));
    87       }
    88       var ca = a as ConstantTreeNode;
    89       if (ca != null) {
    90         var cb = b as ConstantTreeNode;
    91         if (cb == null) return false;
    92         return (!MatchConstantValues || ca.Value.Equals(cb.Value));
    93       }
     115      // return false in all other cases
    94116      return false;
    95117    }
Note: See TracChangeset for help on using the changeset viewer.