Changeset 11225


Ignore:
Timestamp:
07/24/14 23:44:39 (8 years ago)
Author:
bburlacu
Message:

#2215: Fixed a couple of bugs in the BottomUpSimilarityCalculator:

  • the child sequences of matching nodes were not sorted in the same way (one was using StringComparison.Ordinal, the other the default)
  • when creating the mapping it is necessary to walk the nodes of the first tree in decreasing height order (not level-order as the author claims)
Location:
branches/HeuristicLab.BottomUpTreeDistance
Files:
2 edited

Legend:

Unmodified
Added
Removed
  • branches/HeuristicLab.BottomUpTreeDistance/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/SimilarityCalculators/BottomUpSimilarityCalculator.cs

    r11224 r11225  
    7777      var reverseMap = new Dictionary<ISymbolicExpressionTreeNode, ISymbolicExpressionTreeNode>(); // nodes of t2 => nodes of t1
    7878
    79       foreach (var v in IterateBreadthOrdered(n1)) {
    80         if (forwardMap.ContainsKey(v)) continue;
     79      // visit nodes in order of decreasing height to ensure correct mapping
     80      foreach (var v in n1.IterateNodesPrefix().OrderByDescending(x => compactedGraph[x].Weight)) {
     81        if (forwardMap.ContainsKey(v))
     82          continue;
    8183        var kv = compactedGraph[v];
    8284        ISymbolicExpressionTreeNode w = null;
    83         foreach (var t in IterateBreadthOrdered(n2)) {
    84           if (reverseMap.ContainsKey(t) || compactedGraph[t] != kv) continue;
     85        foreach (var t in n2.IterateNodesPrefix()) {
     86          if (reverseMap.ContainsKey(t) || compactedGraph[t] != kv)
     87            continue;
    8588          w = t;
    8689          break;
     
    9699          var s = eV.Current;
    97100          var t = eW.Current;
    98           if (reverseMap.ContainsKey(t))
    99             throw new Exception("Mapping already present");
     101
     102          if (reverseMap.ContainsKey(t)) {
     103            throw new Exception("A mapping to this node already exists.");
     104          }
     105
    100106          forwardMap[s] = t;
    101107          reverseMap[t] = s;
     
    124130        if (n.SubtreeCount == 0) {
    125131          var label = n.ToString();
    126           var z = new Vertex { Content = n, Label = label };
    127           labelsToVertices[z.Label] = z;
    128           vertices.Add(z);
     132          if (!labelsToVertices.ContainsKey(label)) {
     133            var z = new Vertex { Content = n, Label = label };
     134            labelsToVertices[z.Label] = z;
     135            vertices.Add(z);
     136          }
     137          nodesToVertices[n] = labelsToVertices[label];
    129138          queue.Enqueue(n);
    130139        } else {
     
    135144      while (queue.Any()) {
    136145        var v = queue.Dequeue();
    137         string label;
    138         if (v.SubtreeCount == 0) {
    139           label = v.ToString();
    140           nodesToVertices[v] = labelsToVertices[label]; // 18
    141         } else {
    142           label = v.Symbol.Name;
     146
     147        if (v.SubtreeCount > 0) {
     148          var label = v.Symbol.Name;
    143149          bool found = false;
    144150          var height = v.GetDepth();
     
    152158            var w = vertices[i];
    153159            var n = (ISymbolicExpressionTreeNode)w.Content;
    154             if (n.SubtreeCount == 0) continue; // v is a function node so w will have to be a function node as well
    155             if (height != (int)w.Weight || v.SubtreeCount != n.SubtreeCount || label != w.Label)
     160            if (v.SubtreeCount != n.SubtreeCount || label != w.Label || height != (int)w.Weight)
    156161              continue;
    157162
    158163            // sort V and W when the symbol is commutative because we are dealing with unordered trees
    159             var wSubtrees = sort ? w.OutArcs.Select(x => x.Target).OrderBy(x => x.Label)
    160                                  : w.OutArcs.Select(x => x.Target);
     164            var wSubtrees = n.Subtrees.Select(x => nodesToVertices[x]).ToList();
     165            if (sort) wSubtrees.Sort((a, b) => String.Compare(a.Label, b.Label, StringComparison.Ordinal));
    161166
    162167            if (vSubtrees.SequenceEqual(wSubtrees)) {
  • branches/HeuristicLab.BottomUpTreeDistance/HeuristicLab.Tests/BottomUpSimilarityCalculatorTest.cs

    r11221 r11225  
    4646      TestMatchedNodes("(+ (exp 2.1033) (/ -4.3072 (variable 2.4691 X7)))", "(/ 1 (+ (/ -4.3072 (variable 2.4691 X7)) (exp 2.1033)))", 6);
    4747      TestMatchedNodes("(+ (exp 2.1033) (/ -4.3072 (variable 2.4691 X7)))", "(/ 1 (+ (/ (variable 2.4691 X7) -4.3072) (exp 2.1033)))", 4);
     48
     49      var expr1 = "(* (- 1.2175e+1 (+ (/ (exp -1.4134e+1) (exp 9.2013)) (exp (log (exp (/ (exp (- (* -4.2461 (variable 2.2634 X5)) (- -9.6267e-1 3.3243))) (- (/ (/ (variable 1.0883 X1) (variable 6.9620e-1 X2)) (log 1.3011e+1)) (variable -4.3098e-1 X7)))))))) (log 1.3011e+1))";
     50      var expr2 = "(* (- 1.2175e+1 (+ (/ (/ (+ (variable 3.0140 X9) (variable 1.3430 X8)) -1.0864e+1) (exp 9.2013)) (exp (log (exp (/ (exp (- (* -4.2461 (variable 2.2634 X5)) (- -9.6267e-1 3.3243))) (- (/ (/ (variable 1.0883 X1) (variable 6.9620e-1 X2)) (log 1.3011e+1)) (variable -4.3098e-1 X7)))))))) (exp (variable 4.0899e-1 X7)))";
     51
     52      TestMatchedNodes(expr1, expr2, 23);
     53
    4854    }
    4955
Note: See TracChangeset for help on using the changeset viewer.