Changeset 12929 for branches/HeuristicLab.EvolutionTracking/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/TreeMatching

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/TreeMatching

Files:

• QueryMatch.cs (added)
• SymbolicExpressionTreeMatching.cs (modified) (1 diff)
• SymbolicExpressionTreeNodeEqualityComparer.cs (modified) (1 diff)

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;
     }