Free cookie consent management tool by TermsFeed Policy Generator

Changeset 16279

Ignore:
Timestamp:
11/06/18 15:41:13 (6 years ago)
Message:

#2959: Simplify code, improve performance, fix another potential bug in relation with 3).

File:
1 edited

Unmodified
Added
Removed
• trunk/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/TreeMatching/SymbolicExpressionTreeBottomUpSimilarityCalculator.cs

 r16278 } // at this point we know that v and w are isomorphic, however, the mapping cannot be done directly // (as in the paper) because the trees are unordered (subtree order might differ). the solution is // to sort subtrees from under commutative labels (this will work because the subtrees are isomorphic!) // while iterating over the two subtrees var vv = IterateBreadthOrdered(v, comparer); var ww = IterateBreadthOrdered(w, comparer); int len = Math.Min(vv.Count, ww.Count); for (int j = 0; j < len; ++j) { var s = vv[j]; var t = ww[j]; // at this point we know that v and w are isomorphic (same length and depth) // however, the mapping cannot be done directly (as in the paper) // because the trees are unordered (subtree order might differ). // the solution is to sort once again (this will work because the subtrees are isomorphic!) var vv = v.IterateNodesPrefix().OrderBy(x => compactedGraph[x].Hash); var ww = w.IterateNodesPrefix().OrderBy(x => compactedGraph[x].Hash); foreach (var pair in vv.Zip(ww, Tuple.Create)) { var s = pair.Item1; var t = pair.Item2; if (reverseMap.ContainsKey(t)) return forwardMap; } private List IterateBreadthOrdered(ISymbolicExpressionTreeNode node, ISymbolicExpressionTreeNodeComparer comparer) { var list = new List { node }; int i = 0; while (i < list.Count) { var n = list[i]; if (n.SubtreeCount > 0) { var subtrees = commutativeSymbols.Contains(node.Symbol.Name) ? n.Subtrees.OrderBy(x => x, comparer) : n.Subtrees; list.AddRange(subtrees); } i++; } return list; } var nodeMap = new Dictionary(); // K var labelMap = new Dictionary(); // L var comparer = new SymbolicExpressionTreeNodeComparer(); var nodes = n1.IterateNodesPostfix().Concat(n2.IterateNodesPostfix()); // the disjoint union F
Note: See TracChangeset for help on using the changeset viewer.