Changeset 16279
 Timestamp:
 11/06/18 15:41:13 (6 years ago)
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

trunk/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/TreeMatching/SymbolicExpressionTreeBottomUpSimilarityCalculator.cs
r16278 r16279 132 132 } 133 133 134 // at this point we know that v and w are isomorphic , however, the mapping cannot be done directly135 // (as in the paper) because the trees are unordered (subtree order might differ). the solution is136 // to sort subtrees from under commutative labels (this will work because the subtrees are isomorphic!)137 // while iterating over the two subtrees138 var vv = IterateBreadthOrdered(v, comparer);139 var ww = IterateBreadthOrdered(w, comparer);140 int len = Math.Min(vv.Count, ww.Count); 141 for (int j = 0; j < len; ++j) {142 var s = vv[j];143 var t = ww[j];134 // at this point we know that v and w are isomorphic (same length and depth) 135 // however, the mapping cannot be done directly (as in the paper) 136 // because the trees are unordered (subtree order might differ). 137 // the solution is to sort once again (this will work because the subtrees are isomorphic!) 138 var vv = v.IterateNodesPrefix().OrderBy(x => compactedGraph[x].Hash); 139 var ww = w.IterateNodesPrefix().OrderBy(x => compactedGraph[x].Hash); 140 141 foreach (var pair in vv.Zip(ww, Tuple.Create)) { 142 var s = pair.Item1; 143 var t = pair.Item2; 144 144 145 145 if (reverseMap.ContainsKey(t)) … … 152 152 153 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;168 154 } 169 155 … … 177 163 var nodeMap = new Dictionary<ISymbolicExpressionTreeNode, GraphNode>(); // K 178 164 var labelMap = new Dictionary<string, GraphNode>(); // L 179 var comparer = new SymbolicExpressionTreeNodeComparer();180 165 181 166 var nodes = n1.IterateNodesPostfix().Concat(n2.IterateNodesPostfix()); // the disjoint union F
Note: See TracChangeset
for help on using the changeset viewer.