Changeset 12941 for branches/HeuristicLab.EvolutionTracking

Timestamp:

09/06/15 22:11:26 (9 years ago)

Author:

bburlacu

Message:

#1772: Refactored the tree query match code and removed debugging code (as the same information can be obtained with IntelliTrace).

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

@@ -20 +20 @@
 #endregion
 
-using System;
 using System.Collections.Generic;
 using System.Linq;
-using System.Text;
 using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
 
@@ -36 +34 @@
     private QueryMatch() { }
 
-    private readonly Stack<string> stack = new Stack<string>();
-
-    public string Trace {
-      get {
-        var sb = new StringBuilder();
-        while (stack.Count > 0)
-          sb.Append(stack.Pop());
-        return sb.ToString();
-      }
-    }
-
     // whether matching nodes should also have matching parents
     // in theory, this restricts the matching so that parent-child
@@ -58 +45 @@
 
     public bool Match(ISymbolicExpressionTreeNode data, ISymbolicExpressionTreeNode query) {
-      stack.Clear();
+      if (!comparer.Equals(data, query))
+        return false;
+
       dNodes = InitializePostOrder(data);
       qNodes = InitializePostOrder(query);
@@ -68 +57 @@
     }
 
-    private List<NodeInfo> InitializePostOrder(ISymbolicExpressionTreeNode node) {
-      var list = node.IterateNodesPostfix().Select((x, i) => new NodeInfo(x, i)).ToList();
-      foreach (var l in list)
-        l.Nodes = list;
-
-      return list;
-    }
-
     private bool AreMatching(NodeInfo a, NodeInfo b) {
+      // force the nodes to be on the same level
+      if (a.Level != b.Level)
+        return false;
+
       bool equals = comparer.Equals(a.Node, b.Node);
 
       if (equals && MatchParents) {
-        var pa = a.Parent();
-        var pb = b.Parent();
+        var pa = a.Parent;
+        var pb = b.Parent;
+        if (pa == null && pb == null)
+          return true;
         if (pa != null && pb != null)
-          return comparer.Equals(pa.Node, pb.Node);
-        if (!(pa == null && pb == null))
-          return false;
+          return pa.Level == pb.Level && comparer.Equals(pa.Node, pb.Node);
+        return false;
       }
       return equals;
@@ -91 +77 @@
 
     private NodeInfo Tmatch(NodeInfo d, NodeInfo qFrom, NodeInfo qUntil, int tab = 0) {
-#if DEBUG
-      var sb = new StringBuilder();
-#endif
-      NodeInfo qBest = d.IsLeaf ? qFrom.Previous() : Hmatch(d.LastChild(), qFrom, qUntil, tab + 1);
-
-      var next = qBest.Next();
+      NodeInfo qBest = d.IsLeaf ? qFrom.Previous : Hmatch(d.LastChild, qFrom, qUntil, tab + 1);
+      var next = qBest.Next;
       if (next.Index <= qUntil.Index && AreMatching(d, next)) {
         qBest = next;
-        next = qBest.Next();
-        var lastSibling = qBest.LastSibling();
-        var result = next.Index <= lastSibling.Index ? Tmatch(d, next, lastSibling, tab + 1) : qBest;
-#if DEBUG
-        for (int i = 0; i < tab; ++i)
-          sb.Append("\t");
-        sb.AppendLine(string.Format("TM(d{0}, q{1}, q{2}) => q{3}", d.Index, qFrom.Index, qUntil.Index, result.Index));
-        stack.Push(sb.ToString());
-#endif
-        return result;
-      }
-#if DEBUG
-      for (int i = 0; i < tab; ++i)
-        sb.Append("\t");
-      sb.AppendLine(string.Format("TM(d{0}, q{1}, q{2}) => q{3}", d.Index, qFrom.Index, qUntil.Index, qBest.Index));
-      stack.Push(sb.ToString());
-#endif
+        next = qBest.Next;
+        var lastSibling = qBest.LastSibling;
+        return next.Index <= lastSibling.Index ? Tmatch(d, next, lastSibling, tab + 1) : qBest;
+      }
       return qBest;
     }
 
     private NodeInfo Hmatch(NodeInfo d, NodeInfo qFrom, NodeInfo qUntil, int tab = 0) {
-#if DEBUG
-      var sb = new StringBuilder();
-#endif
-      if (d.IsFirstSibling) {
-        var result = Tmatch(d, qFrom, qUntil, tab + 1);
-#if DEBUG
-        for (int i = 0; i < tab; ++i)
-          sb.Append("\t");
-        sb.AppendLine(string.Format("HM(d{0}, q{1}, q{2}) => q{3}", d.Index, qFrom.Index, qUntil.Index, result.Index));
-        stack.Push(sb.ToString());
-#endif
-        return result;
-      }
-
-      var qHedge = Hmatch(d.PreviousSibling(), qFrom, qUntil, tab + 1);
+      if (d.IsFirstSibling)
+        return Tmatch(d, qFrom, qUntil, tab + 1);
+
+      var qHedge = Hmatch(d.PreviousSibling, qFrom, qUntil, tab + 1);
       var qTree = Tmatch(d, qFrom, qUntil, tab + 1);
 
       for (;;) {
-        if (qHedge == qTree) {
-#if DEBUG
-          for (int i = 0; i < tab; ++i)
-            sb.Append("\t");
-          sb.AppendLine(string.Format("HM(d{0}, q{1}, q{2}) => q{3}", d.Index, qFrom.Index, qUntil.Index, qHedge.Index));
-          stack.Push(sb.ToString());
-#endif
+        if (qHedge == qTree)
           return qHedge;
-        }
         if (qTree.Index < qHedge.Index) {
-          var rtop = Rtop(qTree.Next(), qHedge, tab);
-          while (rtop.Index < qHedge.Next().Index && qHedge.Index < rtop.LastSibling().Index) {
-            qTree = Tmatch(d, rtop.Next(), rtop.LastSibling(), tab + 1);
-            rtop = Rtop(qTree.Next(), qHedge, tab);
+          var rtop = Rtop(qTree.Next, qHedge, tab);
+          while (rtop.Index < qHedge.Next.Index && qHedge.Index < rtop.LastSibling.Index) {
+            qTree = Tmatch(d, rtop.Next, rtop.LastSibling, tab + 1);
+            rtop = Rtop(qTree.Next, qHedge, tab);
           }
-          if (qTree.Index <= qHedge.Index) {
-#if DEBUG
-            for (int i = 0; i < tab; ++i)
-              sb.Append("\t");
-            sb.AppendLine(string.Format("HM(d{0}, q{1}, q{2}) => q{3}", d.Index, qFrom.Index, qUntil.Index, qHedge.Index));
-            stack.Push(sb.ToString());
-#endif
+          if (qTree.Index <= qHedge.Index)
             return qHedge;
+        } else {
+          var rtop = Rtop(qHedge.Next, qTree, tab);
+          while (rtop.Index < qTree.Next.Index && qTree.Index < rtop.LastSibling.Index) {
+            qHedge = Hmatch(d.PreviousSibling, rtop.Next, rtop.LastSibling, tab + 1);
+            rtop = Rtop(qHedge.Next, qTree, tab);
           }
-        } else {
-          var rtop = Rtop(qHedge.Next(), qTree, tab);
-          while (rtop.Index < qTree.Next().Index && qTree.Index < rtop.LastSibling().Index) {
-            qHedge = Hmatch(d.PreviousSibling(), rtop.Next(), rtop.LastSibling(), tab + 1);
-            rtop = Rtop(qHedge.Next(), qTree, tab);
-          }
-          if (qHedge.Index <= qTree.Index) {
-#if DEBUG
-            for (int i = 0; i < tab; ++i)
-              sb.Append("\t");
-            sb.AppendLine(string.Format("HM(d{0}, q{1}, q{2}) => q{3}", d.Index, qFrom.Index, qUntil.Index, qTree.Index));
-            stack.Push(sb.ToString());
-#endif
+          if (qHedge.Index <= qTree.Index)
             return qTree;
-          }
         }
       }
@@ -183 +120 @@
     // returns the rightmost node from the topmost nodes in the interval [hFrom, hUntil]
     private NodeInfo Rtop(NodeInfo hFrom, NodeInfo hUntil, int tab = 0) {
-#if DEBUG
-      var sb = new StringBuilder();
-      for (int i = 0; i < tab; ++i)
-        sb.Append("\t");
-      sb.Append(string.Format("Rtop(q{0}, q{1})", hFrom.Index, hUntil.Index));
-#endif
-
-      if (hFrom == hUntil) {
-#if DEBUG
-        sb.AppendLine(string.Format(" => q{0}", hUntil.Index));
-        stack.Push(sb.ToString());
-#endif
+      if (hFrom == hUntil)
         return hUntil;
-      }
-
-      if (hFrom.Nodes != hUntil.Nodes)
-        throw new ArgumentException("hFrom and hUntil must belong to the same tree/hedge");
-
-
-      NodeInfo rtop = null;
-      if (hFrom.Index > hUntil.Index) {
-        rtop = hFrom.Next(); // or return inf (inf is defined in the paper as the successor of the largest node in the hedge)
-#if DEBUG
-        sb.AppendLine(string.Format(" => q{0}", rtop.Index));
-        stack.Push(sb.ToString());
-#endif
-        return rtop;
-      }
-
+      if (hFrom.Index > hUntil.Index)
+        return hFrom.Next;
       // let u be the highest ancestor of hUntil that has a previous sibling s such that s >= hFrom
       // if no such u exists, then Rtop(hFrom, hUntil) = hUntil. Otherwise, rtop(hFrom, hUntil) = s
-      var p = hUntil.Parent();
-      if (p == null)
+      if (hUntil.Parent == null)
         return hUntil;
-      List<NodeInfo> ancestors = hUntil.Ancestors().ToList();
+
+      NodeInfo rtop = null;
+      List<NodeInfo> ancestors = hUntil.Ancestors.ToList();
       // ancestors list is ordered in decreasing depth therefore we start from the end
       for (int i = ancestors.Count - 1; i >= 0; --i) {
-        var s = ancestors[i].PreviousSibling();
-        if (s.Index >= hFrom.Index) {
+        if (ancestors[i].Parent == null || ancestors[i].IsFirstSibling)
+          continue;
+        var s = ancestors[i].PreviousSibling;
+        if (s != null && s.Index >= hFrom.Index) {
           rtop = s;
           break;
         }
       }
-      if (rtop == null)
-        rtop = hUntil;
-#if DEBUG
-      sb.AppendLine(string.Format(" => q{0}", rtop.Index));
-      stack.Push(sb.ToString());
-#endif
-      return rtop;
+      return rtop ?? hUntil;
+    }
+
+    private 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();
+      var map = Enumerable.Range(0, list.Count).ToDictionary(i => list[i], i => nodes[i]);
+
+      var inf = new NodeInfo { Node = null, Index = int.MaxValue, Previous = nodes.Last() };
+      var nil = new NodeInfo { Node = null, Index = -1, Next = nodes.First() };
+
+      foreach (var n in nodes) {
+        n.Parent = n.Node.Parent != null && map.ContainsKey(n.Node.Parent) ? map[n.Node.Parent] : null;
+        n.Next = n == nodes.Last() ? inf : nodes[n.Index + 1];
+        n.Previous = n == nodes.First() ? nil : nodes[n.Index - 1];
+        if (n.Parent == null) {
+          n.PreviousSibling = n.NextSibling = null;
+          n.LastSibling = nil;
+        } else {
+          var parent = n.Parent.Node;
+          int si = parent.IndexOfSubtree(n.Node);
+          n.PreviousSibling = n.IsFirstSibling ? null : map[parent.GetSubtree(si - 1)];
+          n.NextSibling = n.IsLastSibling ? null : map[parent.GetSubtree(si + 1)];
+          n.LastSibling = map[parent.Subtrees.Last()];
+        }
+        n.LastChild = n.IsLeaf ? null : n.Previous;
+      }
+      return nodes;
     }
 
     private class NodeInfo {
-      private NodeInfo() { }
-
-      public NodeInfo(ISymbolicExpressionTreeNode n, int i) {
-        Node = n;
-        Index = i;
-      }
-
-      public List<NodeInfo> Nodes { get; set; }
-      public ISymbolicExpressionTreeNode Node { get; }
-      public int Index { get; }
+      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 {
@@ -252 +188 @@
 
       public bool IsFirstSibling {
-        get { return this.Node == this.Node.Parent.Subtrees.First(); }
-      }
-
-      public IEnumerable<NodeInfo> Ancestors() {
-        var p = Parent();
-        while (p != null) {
-          yield return p;
-          p = p.Parent();
-        }
-      }
-
-      public NodeInfo Parent() {
-        var p = Node.Parent;
-        if (p == null || p.Symbol is StartSymbol)
-          return null;
-        var index = Index + 1;
-        for (int i = p.SubtreeCount - 1; i >= 0; --i) {
-          var subtree = p.GetSubtree(i);
-          if (subtree == Node)
-            break;
-          index += subtree.GetLength();
-        }
-        return Nodes[index];
-      }
-
-      public NodeInfo Next() {
-        if (this == Nodes.Last())
-          return new NodeInfo(null, int.MaxValue) { Nodes = Nodes };
-        return Nodes[Index + 1];
-      }
-
-      public NodeInfo NextSibling() {
-        if (Node.Parent == null || Node == Node.Parent.Subtrees.Last())
-          return new NodeInfo(null, -1);
-
-        var s = Node.Parent.GetSubtree(Node.Parent.IndexOfSubtree(Node) + 1);
-        var nextSibling = Nodes[Index + s.GetLength()];
-        return nextSibling;
-      }
-
-      public NodeInfo LastSibling() {
-        if (Node.Parent == null)
-          return new NodeInfo(null, -1);
-
-        var last = Node.Parent.Subtrees.Last();
-        if (this.Node == last)
-          return this;
-
-        var n = this;
-        while (n.Node != last)
-          n = n.NextSibling();
-        return n;
-      }
-
-      public NodeInfo Previous() {
-        if (this == Nodes.First())
-          return new NodeInfo(null, -1) { Nodes = Nodes }; // return nil
-
-        return Nodes[Index - 1];
-      }
-
-      public NodeInfo PreviousSibling() {
-        if (Node.Parent == null || Node == Node.Parent.Subtrees.First())
-          return new NodeInfo(null, -1) { Nodes = Nodes };
-        var previousSibling = Nodes[Index - Node.GetLength()];
-        return previousSibling;
-      }
-
-      public NodeInfo LastChild() {
-        var nil = new NodeInfo(null, -1);
-        if (IsLeaf)
-          return nil;
-        return Previous();
+        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;
+          }
+        }
       }
     }
   }
 }
+