Free cookie consent management tool by TermsFeed Policy Generator

Changeset 12941


Ignore:
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:
1 edited

Legend:

Unmodified
Added
Removed

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

    r12933 r12941  
    2020#endregion
    2121
    22 using System;
    2322using System.Collections.Generic;
    2423using System.Linq;
    25 using System.Text;
    2624using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
    2725
    … …  
    3634    private QueryMatch() { }
    3735
    38     private readonly Stack<string> stack = new Stack<string>();
    39 
    40     public string Trace {
    41       get {
    42         var sb = new StringBuilder();
    43         while (stack.Count > 0)
    44           sb.Append(stack.Pop());
    45         return sb.ToString();
    46       }
    47     }
    48 
    4936    // whether matching nodes should also have matching parents
    5037    // in theory, this restricts the matching so that parent-child
    … …  
    5845
    5946    public bool Match(ISymbolicExpressionTreeNode data, ISymbolicExpressionTreeNode query) {
    60       stack.Clear();
     47      if (!comparer.Equals(data, query))
     48        return false;
     49
    6150      dNodes = InitializePostOrder(data);
    6251      qNodes = InitializePostOrder(query);
    … …  
    6857    }
    6958
    70     private List<NodeInfo> InitializePostOrder(ISymbolicExpressionTreeNode node) {
    71       var list = node.IterateNodesPostfix().Select((x, i) => new NodeInfo(x, i)).ToList();
    72       foreach (var l in list)
    73         l.Nodes = list;
    74 
    75       return list;
    76     }
    77 
    7859    private bool AreMatching(NodeInfo a, NodeInfo b) {
     60      // force the nodes to be on the same level
     61      if (a.Level != b.Level)
     62        return false;
     63
    7964      bool equals = comparer.Equals(a.Node, b.Node);
    8065
    8166      if (equals && MatchParents) {
    82         var pa = a.Parent();
    83         var pb = b.Parent();
     67        var pa = a.Parent;
     68        var pb = b.Parent;
     69        if (pa == null && pb == null)
     70          return true;
    8471        if (pa != null && pb != null)
    85           return comparer.Equals(pa.Node, pb.Node);
    86         if (!(pa == null && pb == null))
    87           return false;
     72          return pa.Level == pb.Level && comparer.Equals(pa.Node, pb.Node);
     73        return false;
    8874      }
    8975      return equals;
    … …  
    9177
    9278    private NodeInfo Tmatch(NodeInfo d, NodeInfo qFrom, NodeInfo qUntil, int tab = 0) {
    93 #if DEBUG
    94       var sb = new StringBuilder();
    95 #endif
    96       NodeInfo qBest = d.IsLeaf ? qFrom.Previous() : Hmatch(d.LastChild(), qFrom, qUntil, tab + 1);
    97 
    98       var next = qBest.Next();
     79      NodeInfo qBest = d.IsLeaf ? qFrom.Previous : Hmatch(d.LastChild, qFrom, qUntil, tab + 1);
     80      var next = qBest.Next;
    9981      if (next.Index <= qUntil.Index && AreMatching(d, next)) {
    10082        qBest = next;
    101         next = qBest.Next();
    102         var lastSibling = qBest.LastSibling();
    103         var result = next.Index <= lastSibling.Index ? Tmatch(d, next, lastSibling, tab + 1) : qBest;
    104 #if DEBUG
    105         for (int i = 0; i < tab; ++i)
    106           sb.Append("\t");
    107         sb.AppendLine(string.Format("TM(d{0}, q{1}, q{2}) => q{3}", d.Index, qFrom.Index, qUntil.Index, result.Index));
    108         stack.Push(sb.ToString());
    109 #endif
    110         return result;
    111       }
    112 #if DEBUG
    113       for (int i = 0; i < tab; ++i)
    114         sb.Append("\t");
    115       sb.AppendLine(string.Format("TM(d{0}, q{1}, q{2}) => q{3}", d.Index, qFrom.Index, qUntil.Index, qBest.Index));
    116       stack.Push(sb.ToString());
    117 #endif
     83        next = qBest.Next;
     84        var lastSibling = qBest.LastSibling;
     85        return next.Index <= lastSibling.Index ? Tmatch(d, next, lastSibling, tab + 1) : qBest;
     86      }
    11887      return qBest;
    11988    }
    12089
    12190    private NodeInfo Hmatch(NodeInfo d, NodeInfo qFrom, NodeInfo qUntil, int tab = 0) {
    122 #if DEBUG
    123       var sb = new StringBuilder();
    124 #endif
    125       if (d.IsFirstSibling) {
    126         var result = Tmatch(d, qFrom, qUntil, tab + 1);
    127 #if DEBUG
    128         for (int i = 0; i < tab; ++i)
    129           sb.Append("\t");
    130         sb.AppendLine(string.Format("HM(d{0}, q{1}, q{2}) => q{3}", d.Index, qFrom.Index, qUntil.Index, result.Index));
    131         stack.Push(sb.ToString());
    132 #endif
    133         return result;
    134       }
    135 
    136       var qHedge = Hmatch(d.PreviousSibling(), qFrom, qUntil, tab + 1);
     91      if (d.IsFirstSibling)
     92        return Tmatch(d, qFrom, qUntil, tab + 1);
     93
     94      var qHedge = Hmatch(d.PreviousSibling, qFrom, qUntil, tab + 1);
    13795      var qTree = Tmatch(d, qFrom, qUntil, tab + 1);
    13896
    13997      for (;;) {
    140         if (qHedge == qTree) {
    141 #if DEBUG
    142           for (int i = 0; i < tab; ++i)
    143             sb.Append("\t");
    144           sb.AppendLine(string.Format("HM(d{0}, q{1}, q{2}) => q{3}", d.Index, qFrom.Index, qUntil.Index, qHedge.Index));
    145           stack.Push(sb.ToString());
    146 #endif
     98        if (qHedge == qTree)
    14799          return qHedge;
    148         }
    149100        if (qTree.Index < qHedge.Index) {
    150           var rtop = Rtop(qTree.Next(), qHedge, tab);
    151           while (rtop.Index < qHedge.Next().Index && qHedge.Index < rtop.LastSibling().Index) {
    152             qTree = Tmatch(d, rtop.Next(), rtop.LastSibling(), tab + 1);
    153             rtop = Rtop(qTree.Next(), qHedge, tab);
     101          var rtop = Rtop(qTree.Next, qHedge, tab);
     102          while (rtop.Index < qHedge.Next.Index && qHedge.Index < rtop.LastSibling.Index) {
     103            qTree = Tmatch(d, rtop.Next, rtop.LastSibling, tab + 1);
     104            rtop = Rtop(qTree.Next, qHedge, tab);
    154105          }
    155           if (qTree.Index <= qHedge.Index) {
    156 #if DEBUG
    157             for (int i = 0; i < tab; ++i)
    158               sb.Append("\t");
    159             sb.AppendLine(string.Format("HM(d{0}, q{1}, q{2}) => q{3}", d.Index, qFrom.Index, qUntil.Index, qHedge.Index));
    160             stack.Push(sb.ToString());
    161 #endif
     106          if (qTree.Index <= qHedge.Index)
    162107            return qHedge;
     108        } else {
     109          var rtop = Rtop(qHedge.Next, qTree, tab);
     110          while (rtop.Index < qTree.Next.Index && qTree.Index < rtop.LastSibling.Index) {
     111            qHedge = Hmatch(d.PreviousSibling, rtop.Next, rtop.LastSibling, tab + 1);
     112            rtop = Rtop(qHedge.Next, qTree, tab);
    163113          }
    164         } else {
    165           var rtop = Rtop(qHedge.Next(), qTree, tab);
    166           while (rtop.Index < qTree.Next().Index && qTree.Index < rtop.LastSibling().Index) {
    167             qHedge = Hmatch(d.PreviousSibling(), rtop.Next(), rtop.LastSibling(), tab + 1);
    168             rtop = Rtop(qHedge.Next(), qTree, tab);
    169           }
    170           if (qHedge.Index <= qTree.Index) {
    171 #if DEBUG
    172             for (int i = 0; i < tab; ++i)
    173               sb.Append("\t");
    174             sb.AppendLine(string.Format("HM(d{0}, q{1}, q{2}) => q{3}", d.Index, qFrom.Index, qUntil.Index, qTree.Index));
    175             stack.Push(sb.ToString());
    176 #endif
     114          if (qHedge.Index <= qTree.Index)
    177115            return qTree;
    178           }
    179116        }
    180117      }
    … …  
    183120    // returns the rightmost node from the topmost nodes in the interval [hFrom, hUntil]
    184121    private NodeInfo Rtop(NodeInfo hFrom, NodeInfo hUntil, int tab = 0) {
    185 #if DEBUG
    186       var sb = new StringBuilder();
    187       for (int i = 0; i < tab; ++i)
    188         sb.Append("\t");
    189       sb.Append(string.Format("Rtop(q{0}, q{1})", hFrom.Index, hUntil.Index));
    190 #endif
    191 
    192       if (hFrom == hUntil) {
    193 #if DEBUG
    194         sb.AppendLine(string.Format(" => q{0}", hUntil.Index));
    195         stack.Push(sb.ToString());
    196 #endif
     122      if (hFrom == hUntil)
    197123        return hUntil;
    198       }
    199 
    200       if (hFrom.Nodes != hUntil.Nodes)
    201         throw new ArgumentException("hFrom and hUntil must belong to the same tree/hedge");
    202 
    203 
    204       NodeInfo rtop = null;
    205       if (hFrom.Index > hUntil.Index) {
    206         rtop = hFrom.Next(); // or return inf (inf is defined in the paper as the successor of the largest node in the hedge)
    207 #if DEBUG
    208         sb.AppendLine(string.Format(" => q{0}", rtop.Index));
    209         stack.Push(sb.ToString());
    210 #endif
    211         return rtop;
    212       }
    213 
     124      if (hFrom.Index > hUntil.Index)
     125        return hFrom.Next;
    214126      // let u be the highest ancestor of hUntil that has a previous sibling s such that s >= hFrom
    215127      // if no such u exists, then Rtop(hFrom, hUntil) = hUntil. Otherwise, rtop(hFrom, hUntil) = s
    216       var p = hUntil.Parent();
    217       if (p == null)
     128      if (hUntil.Parent == null)
    218129        return hUntil;
    219       List<NodeInfo> ancestors = hUntil.Ancestors().ToList();
     130
     131      NodeInfo rtop = null;
     132      List<NodeInfo> ancestors = hUntil.Ancestors.ToList();
    220133      // ancestors list is ordered in decreasing depth therefore we start from the end
    221134      for (int i = ancestors.Count - 1; i >= 0; --i) {
    222         var s = ancestors[i].PreviousSibling();
    223         if (s.Index >= hFrom.Index) {
     135        if (ancestors[i].Parent == null || ancestors[i].IsFirstSibling)
     136          continue;
     137        var s = ancestors[i].PreviousSibling;
     138        if (s != null && s.Index >= hFrom.Index) {
    224139          rtop = s;
    225140          break;
    226141        }
    227142      }
    228       if (rtop == null)
    229         rtop = hUntil;
    230 #if DEBUG
    231       sb.AppendLine(string.Format(" => q{0}", rtop.Index));
    232       stack.Push(sb.ToString());
    233 #endif
    234       return rtop;
     143      return rtop ?? hUntil;
     144    }
     145
     146    private List<NodeInfo> InitializePostOrder(ISymbolicExpressionTreeNode node) {
     147      var list = node.IterateNodesPostfix().ToList();
     148      var nodes = list.Select((x, i) => new NodeInfo { Node = x, Index = i, Level = node.GetBranchLevel(x) }).ToList();
     149      var map = Enumerable.Range(0, list.Count).ToDictionary(i => list[i], i => nodes[i]);
     150
     151      var inf = new NodeInfo { Node = null, Index = int.MaxValue, Previous = nodes.Last() };
     152      var nil = new NodeInfo { Node = null, Index = -1, Next = nodes.First() };
     153
     154      foreach (var n in nodes) {
     155        n.Parent = n.Node.Parent != null && map.ContainsKey(n.Node.Parent) ? map[n.Node.Parent] : null;
     156        n.Next = n == nodes.Last() ? inf : nodes[n.Index + 1];
     157        n.Previous = n == nodes.First() ? nil : nodes[n.Index - 1];
     158        if (n.Parent == null) {
     159          n.PreviousSibling = n.NextSibling = null;
     160          n.LastSibling = nil;
     161        } else {
     162          var parent = n.Parent.Node;
     163          int si = parent.IndexOfSubtree(n.Node);
     164          n.PreviousSibling = n.IsFirstSibling ? null : map[parent.GetSubtree(si - 1)];
     165          n.NextSibling = n.IsLastSibling ? null : map[parent.GetSubtree(si + 1)];
     166          n.LastSibling = map[parent.Subtrees.Last()];
     167        }
     168        n.LastChild = n.IsLeaf ? null : n.Previous;
     169      }
     170      return nodes;
    235171    }
    236172
    237173    private class NodeInfo {
    238       private NodeInfo() { }
    239 
    240       public NodeInfo(ISymbolicExpressionTreeNode n, int i) {
    241         Node = n;
    242         Index = i;
    243       }
    244 
    245       public List<NodeInfo> Nodes { get; set; }
    246       public ISymbolicExpressionTreeNode Node { get; }
    247       public int Index { get; }
     174      public ISymbolicExpressionTreeNode Node { get; set; }
     175      public int Index { get; set; }
     176      public int Level { get; set; }
     177      public NodeInfo Parent { get; set; }
     178      public NodeInfo Previous { get; set; }
     179      public NodeInfo PreviousSibling { get; set; }
     180      public NodeInfo Next { get; set; }
     181      public NodeInfo NextSibling { get; set; }
     182      public NodeInfo LastSibling { get; set; }
     183      public NodeInfo LastChild { get; set; }
    248184
    249185      public bool IsLeaf {
    … …  
    252188
    253189      public bool IsFirstSibling {
    254         get { return this.Node == this.Node.Parent.Subtrees.First(); }
    255       }
    256 
    257       public IEnumerable<NodeInfo> Ancestors() {
    258         var p = Parent();
    259         while (p != null) {
    260           yield return p;
    261           p = p.Parent();
    262         }
    263       }
    264 
    265       public NodeInfo Parent() {
    266         var p = Node.Parent;
    267         if (p == null || p.Symbol is StartSymbol)
    268           return null;
    269         var index = Index + 1;
    270         for (int i = p.SubtreeCount - 1; i >= 0; --i) {
    271           var subtree = p.GetSubtree(i);
    272           if (subtree == Node)
    273             break;
    274           index += subtree.GetLength();
    275         }
    276         return Nodes[index];
    277       }
    278 
    279       public NodeInfo Next() {
    280         if (this == Nodes.Last())
    281           return new NodeInfo(null, int.MaxValue) { Nodes = Nodes };
    282         return Nodes[Index + 1];
    283       }
    284 
    285       public NodeInfo NextSibling() {
    286         if (Node.Parent == null || Node == Node.Parent.Subtrees.Last())
    287           return new NodeInfo(null, -1);
    288 
    289         var s = Node.Parent.GetSubtree(Node.Parent.IndexOfSubtree(Node) + 1);
    290         var nextSibling = Nodes[Index + s.GetLength()];
    291         return nextSibling;
    292       }
    293 
    294       public NodeInfo LastSibling() {
    295         if (Node.Parent == null)
    296           return new NodeInfo(null, -1);
    297 
    298         var last = Node.Parent.Subtrees.Last();
    299         if (this.Node == last)
    300           return this;
    301 
    302         var n = this;
    303         while (n.Node != last)
    304           n = n.NextSibling();
    305         return n;
    306       }
    307 
    308       public NodeInfo Previous() {
    309         if (this == Nodes.First())
    310           return new NodeInfo(null, -1) { Nodes = Nodes }; // return nil
    311 
    312         return Nodes[Index - 1];
    313       }
    314 
    315       public NodeInfo PreviousSibling() {
    316         if (Node.Parent == null || Node == Node.Parent.Subtrees.First())
    317           return new NodeInfo(null, -1) { Nodes = Nodes };
    318         var previousSibling = Nodes[Index - Node.GetLength()];
    319         return previousSibling;
    320       }
    321 
    322       public NodeInfo LastChild() {
    323         var nil = new NodeInfo(null, -1);
    324         if (IsLeaf)
    325           return nil;
    326         return Previous();
     190        get { return Node.Parent != null && Node == Node.Parent.Subtrees.First(); }
     191      }
     192
     193      public bool IsLastSibling {
     194        get { return Node.Parent != null && Node == Node.Parent.Subtrees.Last(); }
     195      }
     196
     197      public IEnumerable<NodeInfo> Ancestors {
     198        get {
     199          var p = Parent;
     200          while (p != null) {
     201            yield return p;
     202            p = p.Parent;
     203          }
     204        }
    327205      }
    328206    }
    329207  }
    330208}
     209
Note: See TracChangeset for help on using the changeset viewer.