Changeset 12929

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:

• HeuristicLab.Problems.DataAnalysis.Symbolic-3.4.csproj (modified) (2 diffs)
• Symbols/Wildcards (added)
• Symbols/Wildcards/AnyNode.cs (added)
• Symbols/Wildcards/AnyNodeSymbol.cs (added)
• Symbols/Wildcards/AnySubtree.cs (added)
• Symbols/Wildcards/AnySubtreeSymbol.cs (added)
• TreeMatching/QueryMatch.cs (added)
• TreeMatching/SymbolicExpressionTreeMatching.cs (modified) (1 diff)
• TreeMatching/SymbolicExpressionTreeNodeEqualityComparer.cs (modified) (1 diff)

branches/HeuristicLab.EvolutionTracking/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/HeuristicLab.Problems.DataAnalysis.Symbolic-3.4.csproj

@@ -184 +184 @@
     <Compile Include="Analyzers\SymbolicDataAnalysisBottomUpDiversityAnalyzer.cs" />
     <Compile Include="Analyzers\SymbolicDataAnalysisGeneticOperatorImprovementAnalyzer.cs" />
+    <Compile Include="Symbols\Wildcards\AnyNode.cs" />
+    <Compile Include="Symbols\Wildcards\AnySubtreeSymbol.cs" />
+    <Compile Include="Symbols\Wildcards\AnySubtree.cs" />
+    <Compile Include="Symbols\Wildcards\AnyNodeSymbol.cs" />
     <Compile Include="Analyzers\SymbolicDataAnalysisSingleObjectivePruningAnalyzer.cs" />
     <Compile Include="Analyzers\SymbolicDataAnalysisGenealogyAnalyzer.cs" />
@@ -318 +322 @@
     <Compile Include="Tracking\TraceCalculator.cs" />
     <Compile Include="TransformationToSymbolicTreeMapper.cs" />
+    <Compile Include="TreeMatching\QueryMatch.cs" />
     <Compile Include="TreeMatching\SymbolicExpressionTreeBottomUpSimilarityCalculator.cs" />
     <Compile Include="TreeMatching\SymbolicExpressionTreeCanonicalSorter.cs" />

branches/HeuristicLab.EvolutionTracking/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/TreeMatching/SymbolicExpressionTreeMatching.cs

@@ -54 +54 @@
     public static int Match(ISymbolicExpressionTreeNode a, ISymbolicExpressionTreeNode b, ISymbolicExpressionTreeNodeEqualityComparer comp) {
       if (!comp.Equals(a, b)) return 0;
+      // AnySubtree wildcards mach everything
+      if (a is AnySubtree)
+        return b.GetLength();
+      if (b is AnySubtree)
+        return a.GetLength();
+
       int m = a.SubtreeCount;
       int n = b.SubtreeCount;

branches/HeuristicLab.EvolutionTracking/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/TreeMatching/SymbolicExpressionTreeNodeEqualityComparer.cs

@@ -76 +76 @@
 
     public bool Equals(ISymbolicExpressionTreeNode a, ISymbolicExpressionTreeNode b) {
-      if (!(a is SymbolicExpressionTreeTerminalNode))
-        // if a and b are non terminal nodes, check equality of symbol names
-        return !(b is SymbolicExpressionTreeTerminalNode) && a.Symbol.Name.Equals(b.Symbol.Name);
-      var va = a as VariableTreeNode;
-      if (va != null) {
+      var sa = a as AnySubtree;
+      var sb = b as AnySubtree;
+
+      if (sa != null || sb != null)
+        return true;
+
+      if (a.SubtreeCount != b.SubtreeCount)
+        return false;
+
+      var na = a as AnyNode;
+      var nb = b as AnyNode;
+      if (na != null || nb != null)
+        return true;
+
+      var ta = a as SymbolicExpressionTreeTerminalNode;
+      var tb = b as SymbolicExpressionTreeTerminalNode;
+      if (ta != null && tb != null) {
+        var ca = a as ConstantTreeNode;
+        var cb = b as ConstantTreeNode;
+        if (ca != null && cb != null)
+          // both a and b are constants
+          return !MatchConstantValues || ca.Value.Equals(cb.Value);
+
+        var va = a as VariableTreeNode;
         var vb = b as VariableTreeNode;
-        if (vb == null) return false;
+        if (va != null && vb != null) {
+          // both a and b are variables
+          bool m1 = !MatchVariableNames || va.VariableName.Equals(vb.VariableName);
+          bool m2 = !MatchVariableWeights || va.Weight.IsAlmost(vb.Weight);
+          return m1 && m2;
+        }
+      }
+      if (ta == null && tb == null) {
+        // both a and b are non-terminal (function) nodes
+        return a.Symbol.Name.Equals(b.Symbol.Name);
+      }
 
-        return (!MatchVariableNames || va.VariableName.Equals(vb.VariableName)) && (!MatchVariableWeights || va.Weight.Equals(vb.Weight));
-      }
-      var ca = a as ConstantTreeNode;
-      if (ca != null) {
-        var cb = b as ConstantTreeNode;
-        if (cb == null) return false;
-        return (!MatchConstantValues || ca.Value.Equals(cb.Value));
-      }
+      // return false in all other cases
       return false;
     }