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

Timestamp:

10/02/15 01:08:30 (9 years ago)

Author:

bburlacu

Message:

#1772:

• added parameters to the SchemaCreator for calculating things in parallel
• added parallel code to the SchemaEvaluator
• implemented quality calculation and saving of estimated values in the scope in the UpdateEstimatedValuesOperator
• small refactoring of QueryMatch (added some useful methods and made NodeInfo internal)
• updated query match unit test

File:

• branches/HeuristicLab.EvolutionTracking/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/TreeMatching/QueryMatch.cs (modified) (7 diffs)

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

@@ -28 +28 @@
   // by M. Götz, C. Koch and W. Martens in http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.182.5440
   public class QueryMatch {
-    private List<NodeInfo> dNodes;
-    private List<NodeInfo> qNodes;
-    private readonly ISymbolicExpressionTreeNodeEqualityComparer comparer;
+    public ISymbolicExpressionTreeNodeEqualityComparer Comparer { get; }
 
     private QueryMatch() { }
@@ -41 +39 @@
 
     public QueryMatch(ISymbolicExpressionTreeNodeEqualityComparer comparer) {
-      this.comparer = comparer;
+      this.Comparer = comparer;
+    }
+
+    internal bool Match(List<NodeInfo> data, List<NodeInfo> query) {
+      var dRoot = data.Last();
+      var qRoot = query.Last();
+
+      var result = Tmatch(dRoot, query.First(), qRoot);
+      return result == qRoot;
     }
 
@@ -49 +55 @@
 
     public bool Match(ISymbolicExpressionTreeNode data, ISymbolicExpressionTreeNode query) {
-      if (!comparer.Equals(data, query))
+      if (!Comparer.Equals(data, query))
         return false;
 
-      dNodes = InitializePostOrder(data);
-      qNodes = InitializePostOrder(query);
+      var dNodes = InitializePostOrder(data);
+      var qNodes = InitializePostOrder(query);
 
       var dRoot = dNodes.Last();
       var qRoot = qNodes.Last();
-      var result = Tmatch(dRoot, qNodes.First(), qNodes.Last());
+      var result = Tmatch(dRoot, qNodes.First(), qRoot);
       return result == qRoot;
+    }
+
+    public IEnumerable<ISymbolicExpressionTree> GetMatchingTrees(IEnumerable<ISymbolicExpressionTree> data, ISymbolicExpressionTree query) {
+      var qRoot = query.Root.GetSubtree(0).GetSubtree(0);
+      var filtered = data.Where(x => x.Length >= query.Length && Comparer.Equals(x.Root.GetSubtree(0).GetSubtree(0), qRoot));
+      var qNodes = InitializePostOrder(query.Root.GetSubtree(0).GetSubtree(0));
+      return from d in filtered let dNodes = InitializePostOrder(d.Root.GetSubtree(0).GetSubtree(0)) where Match(dNodes, qNodes) select d;
     }
 
@@ -66 +79 @@
         return false;
 
-      bool equals = comparer.Equals(a.Node, b.Node);
+      bool equals = Comparer.Equals(a.Node, b.Node);
 
       if (equals && MatchParents) {
@@ -74 +87 @@
           return true;
         if (pa != null && pb != null)
-          return pa.Level == pb.Level && comparer.Equals(pa.Node, pb.Node);
+          return pa.Level == pb.Level && Comparer.Equals(pa.Node, pb.Node);
         return false;
       }
@@ -145 +158 @@
     }
 
-    private List<NodeInfo> InitializePostOrder(ISymbolicExpressionTreeNode node) {
+    internal static List<NodeInfo> InitializePostOrder(ISymbolicExpressionTreeNode node) {
       var list = node.IterateNodesPostfix().ToList();
       var nodes = list.Select((x, i) => new NodeInfo { Node = x, Index = i, Level = node.GetBranchLevel(x) }).ToList();
@@ -171 +184 @@
       return nodes;
     }
-
-    private class NodeInfo {
-      public ISymbolicExpressionTreeNode Node { get; set; }
-      public int Index { get; set; }
-      public int Level { get; set; }
-      public NodeInfo Parent { get; set; }
-      public NodeInfo Previous { get; set; }
-      public NodeInfo PreviousSibling { get; set; }
-      public NodeInfo Next { get; set; }
-      public NodeInfo NextSibling { get; set; }
-      public NodeInfo LastSibling { get; set; }
-      public NodeInfo LastChild { get; set; }
-
-      public bool IsLeaf {
-        get { return Node.SubtreeCount == 0; }
-      }
-
-      public bool IsFirstSibling {
-        get { return Node.Parent != null && Node == Node.Parent.Subtrees.First(); }
-      }
-
-      public bool IsLastSibling {
-        get { return Node.Parent != null && Node == Node.Parent.Subtrees.Last(); }
-      }
-
-      public IEnumerable<NodeInfo> Ancestors {
-        get {
-          var p = Parent;
-          while (p != null) {
-            yield return p;
-            p = p.Parent;
-          }
+  }
+
+  internal class NodeInfo {
+    public ISymbolicExpressionTreeNode Node { get; set; }
+    public int Index { get; set; }
+    public int Level { get; set; }
+    public NodeInfo Parent { get; set; }
+    public NodeInfo Previous { get; set; }
+    public NodeInfo PreviousSibling { get; set; }
+    public NodeInfo Next { get; set; }
+    public NodeInfo NextSibling { get; set; }
+    public NodeInfo LastSibling { get; set; }
+    public NodeInfo LastChild { get; set; }
+
+    public bool IsLeaf {
+      get { return Node.SubtreeCount == 0; }
+    }
+
+    public bool IsFirstSibling {
+      get { return Node.Parent != null && Node == Node.Parent.Subtrees.First(); }
+    }
+
+    public bool IsLastSibling {
+      get { return Node.Parent != null && Node == Node.Parent.Subtrees.Last(); }
+    }
+
+    public IEnumerable<NodeInfo> Ancestors {
+      get {
+        var p = Parent;
+        while (p != null) {
+          yield return p;
+          p = p.Parent;
         }
       }