Changeset 14326
 Timestamp:
 10/07/16 00:04:21 (8 years ago)
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

branches/HeuristicLab.EvolutionTracking/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/TreeMatching/QueryMatch.cs
r13877 r14326 20 20 #endregion 21 21 22 using System; 22 23 using System.Collections.Generic; 23 24 using System.Linq; … … 28 29 // by M. Götz, C. Koch and W. Martens in http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.182.5440 29 30 public class QueryMatch { 30 public ISymbolicExpressionTreeNodeEqualityComparer Comparer { get; } 31 public ISymbolicExpressionTreeNodeEqualityComparer Comparer { get; private set; } 32 private readonly NodeInfo Inf = new NodeInfo { Index = int.MaxValue }; 33 private readonly NodeInfo Nil = new NodeInfo { Index = 1 }; 31 34 32 35 private QueryMatch() { } … … 39 42 40 43 public QueryMatch(ISymbolicExpressionTreeNodeEqualityComparer comparer) { 41 this.Comparer = comparer;44 Comparer = comparer; 42 45 } 43 46 … … 93 96 94 97 private NodeInfo Tmatch(NodeInfo d, NodeInfo qFrom, NodeInfo qUntil) { 95 NodeInfoqBest = d.IsLeaf ? qFrom.Previous : Hmatch(d.LastChild, qFrom, qUntil);98 var qBest = d.IsLeaf ? qFrom.Previous : Hmatch(d.LastChild, qFrom, qUntil); 96 99 var next = qBest.Next; 97 if (next .Index <= qUntil.Index&& AreMatching(d, next)) {100 if (next <= qUntil && AreMatching(d, next)) { 98 101 qBest = next; 99 102 next = qBest.Next; 100 103 var lastSibling = qBest.LastSibling; 101 return next .Index <= lastSibling.Index? Tmatch(d, next, lastSibling) : qBest;104 return next <= lastSibling ? Tmatch(d, next, lastSibling) : qBest; 102 105 } 103 106 return qBest; … … 114 117 if (qHedge == qTree) 115 118 return qHedge; 116 if (qTree .Index < qHedge.Index) {119 if (qTree < qHedge) { 117 120 var rtop = Rtop(qTree.Next, qHedge); 118 while (rtop .Index < int.MaxValue && qHedge.Index < rtop.LastSibling.Index) {121 while (rtop < Inf && qHedge < rtop.LastSibling) { 119 122 qTree = Tmatch(d, rtop.Next, rtop.LastSibling); 120 123 rtop = Rtop(qTree.Next, qHedge); 121 124 } 122 if (qTree .Index <= qHedge.Index)125 if (qTree <= qHedge) 123 126 return qHedge; 124 127 } else { 125 128 var rtop = Rtop(qHedge.Next, qTree); 126 while (rtop .Index < int.MaxValue && qTree.Index < rtop.LastSibling.Index) {129 while (rtop < Inf && qTree < rtop.LastSibling) { 127 130 qHedge = Hmatch(d.PreviousSibling, rtop.Next, rtop.LastSibling); 128 131 rtop = Rtop(qHedge.Next, qTree); 129 132 } 130 if (qHedge .Index <= qTree.Index)133 if (qHedge <= qTree) 131 134 return qTree; 132 135 } … … 134 137 } 135 138 136 // returns the rightmost node from the topmost nodes in the interval [hFrom, hUntil] 139 /// <summary> 140 /// Description from Götz et al.  Efficient Algorithms for Descendantonly Tree Pattern Queries, 2009: 141 /// Given two nodes hFrom and hUntil, returns the rightmost node among the topmost nodes in the interval [hFrom, hUntil] 142 /// More formally, Rtop(hFrom,hUntil) is the node u such that depth(u) is minimal and u is larger than every other node v 143 /// in [hFrom, hUntil] with depth(u)==depth(v). 144 /// </summary> 145 /// <param name="hFrom">The interval start</param> 146 /// <param name="hUntil">The interval end</param> 147 /// <returns>The rightmost node from the topmost nodes in the interval [hFrom, hUntil]</returns> 137 148 private NodeInfo Rtop(NodeInfo hFrom, NodeInfo hUntil) { 138 149 if (hFrom == hUntil) 139 150 return hUntil; 140 151 if (hFrom.Index > hUntil.Index) 141 return new NodeInfo { Node = null, Index = int.MaxValue };152 return Inf; 142 153 // let u be the highest ancestor of hUntil that has a previous sibling s such that s >= hFrom 143 154 // if no such u exists, then Rtop(hFrom, hUntil) = hUntil. Otherwise, rtop(hFrom, hUntil) = s 144 NodeInfo rtop = null; 145 List<NodeInfo> ancestors = hUntil.Ancestors.ToList(); 146 // ancestors list is ordered in decreasing depth therefore we start from the end 147 for (int i = ancestors.Count  1; i >= 0; i) { 148 if (ancestors[i].Parent == null  ancestors[i].IsFirstSibling) 149 continue; 150 var s = ancestors[i].PreviousSibling; 151 if (s != null && s.Index >= hFrom.Index) { 152 rtop = s; 153 break; 154 } 155 } 155 var rtop = hUntil.Ancestors.OrderBy(x => x.Level).Select(x => x.PreviousSibling).FirstOrDefault(x => x != null && x >= hFrom); 156 156 return rtop ?? hUntil; 157 157 } 158 158 159 159 internal static List<NodeInfo> InitializePostOrder(ISymbolicExpressionTreeNode node) { 160 // levels will be computed below 160 161 var nodes = node.IterateNodesPostfix().Select((x, i) => new NodeInfo { Node = x, Index = i, Level = 0 }).ToList(); 161 162 var map = nodes.ToDictionary(x => x.Node, x => x); 162 163 var inf = new NodeInfo { Node = null, Index = int.MaxValue, Previous = nodes.Last() }; 164 var nil = new NodeInfo { Node = null, Index = 1, Next = nodes.First() }; 165 163 nodes.First().Previous = new NodeInfo { Node = null, Index = 1, Next = nodes.First() }; 164 nodes.Last().Next = new NodeInfo { Node = null, Index = int.MaxValue, Previous = nodes.Last() }; 166 165 for (int i = nodes.Count  1; i >= 0; i) { 167 166 var n = nodes[i]; 168 n.Parent = n.Node.Parent != null && map.ContainsKey(n.Node.Parent) ? map[n.Node.Parent] : null; 169 n.Level = n.Parent?.Level + 1 ?? 1; 170 n.Next = n == nodes.Last() ? inf : nodes[n.Index + 1]; 171 n.Previous = n == nodes.First() ? nil : nodes[n.Index  1]; 167 if (n != nodes.Last()) n.Next = nodes[n.Index + 1]; 168 if (n != nodes.First()) n.Previous = nodes[n.Index  1]; 169 NodeInfo parentInfo; 170 map.TryGetValue(n.Node.Parent, out parentInfo); 171 n.Parent = parentInfo; 172 172 if (n.Parent == null) { 173 n.PreviousSibling = n.NextSibling = null; 174 n.LastSibling = nil; 173 n.PreviousSibling = n.NextSibling = n.LastSibling = null; 175 174 } else { 176 175 var parent = n.Parent.Node; … … 179 178 n.NextSibling = n.IsLastSibling ? null : map[parent.GetSubtree(si + 1)]; 180 179 n.LastSibling = map[parent.Subtrees.Last()]; 180 n.Level = n.Parent.Level + 1; 181 181 } 182 182 n.LastChild = n.IsLeaf ? null : n.Previous; … … 186 186 } 187 187 188 internal class NodeInfo { 188 /// <summary> 189 /// NodeInfo objects are useful for keeping sibling, parent, index and depth information for tree nodes 190 /// </summary> 191 internal class NodeInfo : IComparable<NodeInfo> { 189 192 public ISymbolicExpressionTreeNode Node { get; set; } 190 193 public int Index { get; set; } … … 219 222 } 220 223 } 224 225 public int CompareTo(NodeInfo other) { 226 return other == null ? 1 : Index.CompareTo(other.Index); 227 } 228 229 public static bool operator <(NodeInfo lsh, NodeInfo rhs) { 230 return lsh.CompareTo(rhs) == 1; 231 } 232 233 public static bool operator >(NodeInfo lhs, NodeInfo rhs) { 234 return lhs.CompareTo(rhs) == 1; 235 } 236 237 public static bool operator <=(NodeInfo lhs, NodeInfo rhs) { 238 return lhs.CompareTo(rhs) <= 0; 239 } 240 241 public static bool operator >=(NodeInfo lhs, NodeInfo rhs) { 242 return lhs.CompareTo(rhs) >= 0; 243 } 221 244 } 222 245 }
Note: See TracChangeset
for help on using the changeset viewer.