Changeset 16278
 Timestamp:
 11/06/18 14:24:43 (16 months ago)
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

trunk/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/TreeMatching/SymbolicExpressionTreeBottomUpSimilarityCalculator.cs
r15583 r16278 22 22 using System; 23 23 using System.Collections.Generic; 24 using System.Diagnostics;25 24 using System.Globalization; 26 25 using System.Linq; … … 40 39 protected override bool IsCommutative { get { return true; } } 41 40 41 public bool MatchConstantValues { get; set; } 42 public bool MatchVariableWeights { get; set; } 43 42 44 [StorableConstructor] 43 45 protected SymbolicExpressionTreeBottomUpSimilarityCalculator(bool deserializing) … … 57 59 return 1; 58 60 59 var map = ComputeBottomUpMapping(t1.Root, t2.Root); 60 return 2.0 * map.Count / (t1.Length + t2.Length); 61 var actualRoot1 = t1.Root.GetSubtree(0).GetSubtree(0); // skip root and start symbols 62 var actualRoot2 = t2.Root.GetSubtree(0).GetSubtree(0); // skip root and start symbols 63 var map = ComputeBottomUpMapping(actualRoot1, actualRoot2); 64 return 2.0 * map.Count / (t1.Length + t2.Length  4); // 4 for skipping root and start symbols in the two trees 65 } 66 67 public double CalculateSimilarity(ISymbolicExpressionTree t1, ISymbolicExpressionTree t2, out Dictionary<ISymbolicExpressionTreeNode, ISymbolicExpressionTreeNode> map) { 68 if (t1 == t2) { 69 map = null; 70 return 1; 71 } 72 73 var actualRoot1 = t1.Root.GetSubtree(0).GetSubtree(0); // skip root and start symbols 74 var actualRoot2 = t2.Root.GetSubtree(0).GetSubtree(0); // skip root and start symbols 75 map = ComputeBottomUpMapping(actualRoot1, actualRoot2); 76 77 return 2.0 * map.Count / (t1.Length + t2.Length  4); // 4 for skipping root and start symbols in the two trees 61 78 } 62 79 … … 86 103 87 104 // visit nodes in order of decreasing height to ensure correct mapping 88 var nodes1 = n1.IterateNodesPrefix().OrderByDescending(x => x.GetDepth()).ToList();89 var nodes2 = n2.IterateNodesPrefix().ToList();90 for (int i = 0; i < nodes1.Count; ++i) { 91 var v = nodes1[i];92 if (forwardMap.ContainsKey(v)) 105 var nodes1 = (List<ISymbolicExpressionTreeNode>)n1.IterateNodesPrefix(); 106 var nodes2 = (List<ISymbolicExpressionTreeNode>)n2.IterateNodesPrefix(); 107 108 foreach (var v in nodes1) { 109 if (forwardMap.ContainsKey(v)) { 93 110 continue; 111 } 112 94 113 var kv = compactedGraph[v]; 95 ISymbolicExpressionTreeNode w = null; 114 115 var w = nodes2.Last(); 116 int k = nodes2.Count  1; 117 96 118 for (int j = 0; j < nodes2.Count; ++j) { 97 119 var t = nodes2[j]; 98 if (reverseMap.ContainsKey(t)  compactedGraph[t] != kv) 120 121 if (reverseMap.ContainsKey(t)  kv != compactedGraph[t]) 99 122 continue; 100 w = t; 101 break; 102 } 103 if (w == null) continue; 123 124 if (j < k) { 125 w = t; 126 k = j; 127 } 128 } 129 130 if (kv != compactedGraph[w]) { 131 continue; 132 } 104 133 105 134 // at this point we know that v and w are isomorphic, however, the mapping cannot be done directly … … 107 136 // to sort subtrees from under commutative labels (this will work because the subtrees are isomorphic!) 108 137 // while iterating over the two subtrees 109 var vv = IterateBreadthOrdered(v, comparer) .ToList();110 var ww = IterateBreadthOrdered(w, comparer) .ToList();138 var vv = IterateBreadthOrdered(v, comparer); 139 var ww = IterateBreadthOrdered(w, comparer); 111 140 int len = Math.Min(vv.Count, ww.Count); 112 141 for (int j = 0; j < len; ++j) { 113 142 var s = vv[j]; 114 143 var t = ww[j]; 115 Debug.Assert(!reverseMap.ContainsKey(t)); 144 145 if (reverseMap.ContainsKey(t)) 146 continue; 116 147 117 148 forwardMap[s] = t; … … 121 152 122 153 return forwardMap; 154 } 155 156 private List<ISymbolicExpressionTreeNode> IterateBreadthOrdered(ISymbolicExpressionTreeNode node, ISymbolicExpressionTreeNodeComparer comparer) { 157 var list = new List<ISymbolicExpressionTreeNode> { node }; 158 int i = 0; 159 while (i < list.Count) { 160 var n = list[i]; 161 if (n.SubtreeCount > 0) { 162 var subtrees = commutativeSymbols.Contains(node.Symbol.Name) ? n.Subtrees.OrderBy(x => x, comparer) : n.Subtrees; 163 list.AddRange(subtrees); 164 } 165 i++; 166 } 167 return list; 123 168 } 124 169 … … 132 177 var nodeMap = new Dictionary<ISymbolicExpressionTreeNode, GraphNode>(); // K 133 178 var labelMap = new Dictionary<string, GraphNode>(); // L 134 var c hildrenCount = new Dictionary<ISymbolicExpressionTreeNode, int>(); // Children179 var comparer = new SymbolicExpressionTreeNodeComparer(); 135 180 136 181 var nodes = n1.IterateNodesPostfix().Concat(n2.IterateNodesPostfix()); // the disjoint union F 137 var list= new List<GraphNode>();138 var queue = new Queue<ISymbolicExpressionTreeNode>(); 139 140 foreach (var n in nodes) {141 if (n.SubtreeCount == 0) { 142 var label = GetLabel(n);182 var graph = new List<GraphNode>(); 183 184 foreach (var node in nodes) { 185 var label = GetLabel(node); 186 187 if (node.SubtreeCount == 0) { 143 188 if (!labelMap.ContainsKey(label)) { 144 var z = new GraphNode { SymbolicExpressionTreeNode = n, Label = label };145 labelMap[z.Label] = z;146 }147 nodeMap[n] = labelMap[label];148 queue.Enqueue(n);189 var g = new GraphNode(node, label); 190 graph.Add(g); 191 labelMap[label] = g; 192 } 193 nodeMap[node] = labelMap[label]; 149 194 } else { 150 childrenCount[n] = n.SubtreeCount; 151 } 152 } 153 while (queue.Any()) { 154 var n = queue.Dequeue(); 155 if (n.SubtreeCount > 0) { 195 var v = new GraphNode(node, label); 156 196 bool found = false; 157 var label = n.Symbol.Name; 158 var depth = n.GetDepth(); 159 160 bool sort = n.SubtreeCount > 1 && commutativeSymbols.Contains(label); 161 var nSubtrees = n.Subtrees.Select(x => nodeMap[x]).ToList(); 162 if (sort) nSubtrees.Sort((a, b) => string.CompareOrdinal(a.Label, b.Label)); 163 164 for (int i = list.Count  1; i >= 0; i) { 165 var w = list[i]; 166 if (!(n.SubtreeCount == w.SubtreeCount && label == w.Label && depth == w.Depth)) 197 var commutative = node.SubtreeCount > 1 && commutativeSymbols.Contains(label); 198 199 IEnumerable<GraphNode> vv, ww; 200 201 for (int i = graph.Count  1; i >= 0; i) { 202 var w = graph[i]; 203 204 if (v.Depth != w.Depth  v.SubtreeCount != w.SubtreeCount  v.Length != w.Length  v.Label != w.Label) { 167 205 continue; 168 169 // sort V and W when the symbol is commutative because we are dealing with unordered trees 170 var m = w.SymbolicExpressionTreeNode; 171 var mSubtrees = m.Subtrees.Select(x => nodeMap[x]).ToList(); 172 if (sort) mSubtrees.Sort((a, b) => string.CompareOrdinal(a.Label, b.Label)); 173 174 found = nSubtrees.SequenceEqual(mSubtrees); 206 } 207 208 vv = commutative ? v.SymbolicExpressionTreeNode.Subtrees.Select(x => nodeMap[x]).OrderBy(x => x.Hash) : v.SymbolicExpressionTreeNode.Subtrees.Select(x => nodeMap[x]); 209 ww = commutative ? w.SymbolicExpressionTreeNode.Subtrees.Select(x => nodeMap[x]).OrderBy(x => x.Hash) : w.SymbolicExpressionTreeNode.Subtrees.Select(x => nodeMap[x]); 210 found = vv.SequenceEqual(ww); 211 175 212 if (found) { 176 nodeMap[n ] = w;213 nodeMap[node] = w; 177 214 break; 178 215 } 179 216 } 180 181 217 if (!found) { 182 var w = new GraphNode { SymbolicExpressionTreeNode = n, Label = label, Depth = depth }; 183 list.Add(w); 184 nodeMap[n] = w; 185 } 186 } 187 188 if (n == n1  n == n2) 189 continue; 190 191 var p = n.Parent; 192 if (p == null) 193 continue; 194 195 childrenCount[p]; 196 197 if (childrenCount[p] == 0) 198 queue.Enqueue(p); 199 } 200 218 nodeMap[node] = v; 219 graph.Add(v); 220 } 221 } 222 } 201 223 return nodeMap; 202 224 } 203 225 204 private IEnumerable<ISymbolicExpressionTreeNode> IterateBreadthOrdered(ISymbolicExpressionTreeNode node, ISymbolicExpressionTreeNodeComparer comparer) { 205 var list = new List<ISymbolicExpressionTreeNode> { node }; 206 int i = 0; 207 while (i < list.Count) { 208 var n = list[i]; 209 if (n.SubtreeCount > 0) { 210 var subtrees = commutativeSymbols.Contains(node.Symbol.Name) ? n.Subtrees.OrderBy(x => x, comparer) : n.Subtrees; 211 list.AddRange(subtrees); 212 } 213 i++; 214 } 215 return list; 216 } 217 218 private static string GetLabel(ISymbolicExpressionTreeNode node) { 226 private string GetLabel(ISymbolicExpressionTreeNode node) { 219 227 if (node.SubtreeCount > 0) 220 228 return node.Symbol.Name; 221 229 222 var constant = node as ConstantTreeNode; 223 if (constant != null) 224 return constant.Value.ToString(CultureInfo.InvariantCulture); 225 226 var variable = node as VariableTreeNode; 227 if (variable != null) 228 return variable.Weight + variable.VariableName; 230 if (node is ConstantTreeNode constant) 231 return MatchConstantValues ? constant.Value.ToString(CultureInfo.InvariantCulture) : constant.Symbol.Name; 232 233 if (node is VariableTreeNode variable) 234 return MatchVariableWeights ? variable.Weight + variable.VariableName : variable.VariableName; 229 235 230 236 return node.ToString(); … … 232 238 233 239 private class GraphNode { 234 public ISymbolicExpressionTreeNode SymbolicExpressionTreeNode; 235 public string Label; 236 public int Depth; 240 private GraphNode() { } 241 242 public GraphNode(ISymbolicExpressionTreeNode node, string label) { 243 SymbolicExpressionTreeNode = node; 244 Label = label; 245 Hash = GetHashCode(); 246 Depth = node.GetDepth(); 247 Length = node.GetLength(); 248 } 249 250 public int Hash { get; } 251 252 public ISymbolicExpressionTreeNode SymbolicExpressionTreeNode { get; } 253 254 public string Label { get; } 255 256 public int Depth { get; } 257 237 258 public int SubtreeCount { get { return SymbolicExpressionTreeNode.SubtreeCount; } } 259 260 public int Length { get; } 238 261 } 239 262 }
Note: See TracChangeset
for help on using the changeset viewer.