Free cookie consent management tool by TermsFeed Policy Generator

Ignore:
Timestamp:
11/06/18 15:41:13 (5 years ago)
Author:
bburlacu
Message:

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

File:
1 edited

Legend:

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

    r16278 r16279  
    132132        }
    133133
    134         // at this point we know that v and w are isomorphic, however, the mapping cannot be done directly
    135         // (as in the paper) because the trees are unordered (subtree order might differ). the solution is
    136         // to sort subtrees from under commutative labels (this will work because the subtrees are isomorphic!)
    137         // while iterating over the two subtrees
    138         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;
    144144
    145145          if (reverseMap.ContainsKey(t))
     
    152152
    153153      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;
    168154    }
    169155
     
    177163      var nodeMap = new Dictionary<ISymbolicExpressionTreeNode, GraphNode>(); // K
    178164      var labelMap = new Dictionary<string, GraphNode>(); // L
    179       var comparer = new SymbolicExpressionTreeNodeComparer();
    180165
    181166      var nodes = n1.IterateNodesPostfix().Concat(n2.IterateNodesPostfix()); // the disjoint union F
Note: See TracChangeset for help on using the changeset viewer.