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)
File:
1 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)) {
Note: See TracChangeset for help on using the changeset viewer.