Free cookie consent management tool by TermsFeed Policy Generator

source: branches/HeuristicLab.EvolutionTracking/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/TreeMatching/QueryMatch.cs @ 12941

Last change on this file since 12941 was 12941, checked in by bburlacu, 9 years ago

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

File size: 7.9 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2015 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
4 *
5 * This file is part of HeuristicLab.
6 *
7 * HeuristicLab is free software: you can redistribute it and/or modify
8 * it under the terms of the GNU General Public License as published by
9 * the Free Software Foundation, either version 3 of the License, or
10 * (at your option) any later version.
11 *
12 * HeuristicLab is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15 * GNU General Public License for more details.
16 *
17 * You should have received a copy of the GNU General Public License
18 * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
19 */
20#endregion
21
22using System.Collections.Generic;
23using System.Linq;
24using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
25
26namespace HeuristicLab.Problems.DataAnalysis.Symbolic {
27  // this class implements the decision version of the tree pattern query matching algorithm
28  // by M. Götz, C. Koch and W. Martens in http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.182.5440
29  public class QueryMatch {
30    private List<NodeInfo> dNodes;
31    private List<NodeInfo> qNodes;
32    private readonly ISymbolicExpressionTreeNodeEqualityComparer comparer;
33
34    private QueryMatch() { }
35
36    // whether matching nodes should also have matching parents
37    // in theory, this restricts the matching so that parent-child
38    // pairs in the query tree are matched by parent-child pairs in
39    // the data tree (and not ancestor-descendant pairs)
40    public bool MatchParents { get; set; }
41
42    public QueryMatch(ISymbolicExpressionTreeNodeEqualityComparer comparer) {
43      this.comparer = comparer;
44    }
45
46    public bool Match(ISymbolicExpressionTreeNode data, ISymbolicExpressionTreeNode query) {
47      if (!comparer.Equals(data, query))
48        return false;
49
50      dNodes = InitializePostOrder(data);
51      qNodes = InitializePostOrder(query);
52
53      var dRoot = dNodes.Last();
54      var qRoot = qNodes.Last();
55      var result = Tmatch(dRoot, qNodes.First(), qNodes.Last());
56      return result == qRoot;
57    }
58
59    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
64      bool equals = comparer.Equals(a.Node, b.Node);
65
66      if (equals && MatchParents) {
67        var pa = a.Parent;
68        var pb = b.Parent;
69        if (pa == null && pb == null)
70          return true;
71        if (pa != null && pb != null)
72          return pa.Level == pb.Level && comparer.Equals(pa.Node, pb.Node);
73        return false;
74      }
75      return equals;
76    }
77
78    private NodeInfo Tmatch(NodeInfo d, NodeInfo qFrom, NodeInfo qUntil, int tab = 0) {
79      NodeInfo qBest = d.IsLeaf ? qFrom.Previous : Hmatch(d.LastChild, qFrom, qUntil, tab + 1);
80      var next = qBest.Next;
81      if (next.Index <= qUntil.Index && AreMatching(d, next)) {
82        qBest = next;
83        next = qBest.Next;
84        var lastSibling = qBest.LastSibling;
85        return next.Index <= lastSibling.Index ? Tmatch(d, next, lastSibling, tab + 1) : qBest;
86      }
87      return qBest;
88    }
89
90    private NodeInfo Hmatch(NodeInfo d, NodeInfo qFrom, NodeInfo qUntil, int tab = 0) {
91      if (d.IsFirstSibling)
92        return Tmatch(d, qFrom, qUntil, tab + 1);
93
94      var qHedge = Hmatch(d.PreviousSibling, qFrom, qUntil, tab + 1);
95      var qTree = Tmatch(d, qFrom, qUntil, tab + 1);
96
97      for (;;) {
98        if (qHedge == qTree)
99          return qHedge;
100        if (qTree.Index < qHedge.Index) {
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);
105          }
106          if (qTree.Index <= qHedge.Index)
107            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);
113          }
114          if (qHedge.Index <= qTree.Index)
115            return qTree;
116        }
117      }
118    }
119
120    // returns the rightmost node from the topmost nodes in the interval [hFrom, hUntil]
121    private NodeInfo Rtop(NodeInfo hFrom, NodeInfo hUntil, int tab = 0) {
122      if (hFrom == hUntil)
123        return hUntil;
124      if (hFrom.Index > hUntil.Index)
125        return hFrom.Next;
126      // let u be the highest ancestor of hUntil that has a previous sibling s such that s >= hFrom
127      // if no such u exists, then Rtop(hFrom, hUntil) = hUntil. Otherwise, rtop(hFrom, hUntil) = s
128      if (hUntil.Parent == null)
129        return hUntil;
130
131      NodeInfo rtop = null;
132      List<NodeInfo> ancestors = hUntil.Ancestors.ToList();
133      // ancestors list is ordered in decreasing depth therefore we start from the end
134      for (int i = ancestors.Count - 1; i >= 0; --i) {
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) {
139          rtop = s;
140          break;
141        }
142      }
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;
171    }
172
173    private class NodeInfo {
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; }
184
185      public bool IsLeaf {
186        get { return Node.SubtreeCount == 0; }
187      }
188
189      public bool IsFirstSibling {
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        }
205      }
206    }
207  }
208}
209
Note: See TracBrowser for help on using the repository browser.