Changeset 16278


Ignore:
Timestamp:
11/06/18 14:24:43 (16 months ago)
Author:
bburlacu
Message:

#2959: Address the issues described in the ticket.

File:
1 edited

Legend:

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

    r15583 r16278  
    2222using System;
    2323using System.Collections.Generic;
    24 using System.Diagnostics;
    2524using System.Globalization;
    2625using System.Linq;
     
    4039    protected override bool IsCommutative { get { return true; } }
    4140
     41    public bool MatchConstantValues { get; set; }
     42    public bool MatchVariableWeights { get; set; }
     43
    4244    [StorableConstructor]
    4345    protected SymbolicExpressionTreeBottomUpSimilarityCalculator(bool deserializing)
     
    5759        return 1;
    5860
    59       var map = ComputeBottomUpMapping(t1.Root, t2.Root);
    60       return 2.0 * map.Count / (t1.Length + t2.Length);
     61      var actualRoot1 = t1.Root.GetSubtree(0).GetSubtree(0); // skip root and start symbols
     62      var actualRoot2 = t2.Root.GetSubtree(0).GetSubtree(0); // skip root and start symbols
     63      var map = ComputeBottomUpMapping(actualRoot1, actualRoot2);
     64      return 2.0 * map.Count / (t1.Length + t2.Length - 4); // -4 for skipping root and start symbols in the two trees
     65    }
     66
     67    public double CalculateSimilarity(ISymbolicExpressionTree t1, ISymbolicExpressionTree t2, out Dictionary<ISymbolicExpressionTreeNode, ISymbolicExpressionTreeNode> map) {
     68      if (t1 == t2) {
     69        map = null;
     70        return 1;
     71      }
     72
     73      var actualRoot1 = t1.Root.GetSubtree(0).GetSubtree(0); // skip root and start symbols
     74      var actualRoot2 = t2.Root.GetSubtree(0).GetSubtree(0); // skip root and start symbols
     75      map = ComputeBottomUpMapping(actualRoot1, actualRoot2);
     76
     77      return 2.0 * map.Count / (t1.Length + t2.Length - 4); // -4 for skipping root and start symbols in the two trees
    6178    }
    6279
     
    86103
    87104      // visit nodes in order of decreasing height to ensure correct mapping
    88       var nodes1 = n1.IterateNodesPrefix().OrderByDescending(x => x.GetDepth()).ToList();
    89       var nodes2 = n2.IterateNodesPrefix().ToList();
    90       for (int i = 0; i < nodes1.Count; ++i) {
    91         var v = nodes1[i];
    92         if (forwardMap.ContainsKey(v))
     105      var nodes1 = (List<ISymbolicExpressionTreeNode>)n1.IterateNodesPrefix();
     106      var nodes2 = (List<ISymbolicExpressionTreeNode>)n2.IterateNodesPrefix();
     107
     108      foreach (var v in nodes1) {
     109        if (forwardMap.ContainsKey(v)) {
    93110          continue;
     111        }
     112
    94113        var kv = compactedGraph[v];
    95         ISymbolicExpressionTreeNode w = null;
     114
     115        var w = nodes2.Last();
     116        int k = nodes2.Count - 1;
     117
    96118        for (int j = 0; j < nodes2.Count; ++j) {
    97119          var t = nodes2[j];
    98           if (reverseMap.ContainsKey(t) || compactedGraph[t] != kv)
     120
     121          if (reverseMap.ContainsKey(t) || kv != compactedGraph[t])
    99122            continue;
    100           w = t;
    101           break;
    102         }
    103         if (w == null) continue;
     123
     124          if (j < k) {
     125            w = t;
     126            k = j;
     127          }
     128        }
     129
     130        if (kv != compactedGraph[w]) {
     131          continue;
     132        }
    104133
    105134        // at this point we know that v and w are isomorphic, however, the mapping cannot be done directly
     
    107136        // to sort subtrees from under commutative labels (this will work because the subtrees are isomorphic!)
    108137        // while iterating over the two subtrees
    109         var vv = IterateBreadthOrdered(v, comparer).ToList();
    110         var ww = IterateBreadthOrdered(w, comparer).ToList();
     138        var vv = IterateBreadthOrdered(v, comparer);
     139        var ww = IterateBreadthOrdered(w, comparer);
    111140        int len = Math.Min(vv.Count, ww.Count);
    112141        for (int j = 0; j < len; ++j) {
    113142          var s = vv[j];
    114143          var t = ww[j];
    115           Debug.Assert(!reverseMap.ContainsKey(t));
     144
     145          if (reverseMap.ContainsKey(t))
     146            continue;
    116147
    117148          forwardMap[s] = t;
     
    121152
    122153      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;
    123168    }
    124169
     
    132177      var nodeMap = new Dictionary<ISymbolicExpressionTreeNode, GraphNode>(); // K
    133178      var labelMap = new Dictionary<string, GraphNode>(); // L
    134       var childrenCount = new Dictionary<ISymbolicExpressionTreeNode, int>(); // Children
     179      var comparer = new SymbolicExpressionTreeNodeComparer();
    135180
    136181      var nodes = n1.IterateNodesPostfix().Concat(n2.IterateNodesPostfix()); // the disjoint union F
    137       var list = new List<GraphNode>();
    138       var queue = new Queue<ISymbolicExpressionTreeNode>();
    139 
    140       foreach (var n in nodes) {
    141         if (n.SubtreeCount == 0) {
    142           var label = GetLabel(n);
     182      var graph = new List<GraphNode>();
     183
     184      foreach (var node in nodes) {
     185        var label = GetLabel(node);
     186
     187        if (node.SubtreeCount == 0) {
    143188          if (!labelMap.ContainsKey(label)) {
    144             var z = new GraphNode { SymbolicExpressionTreeNode = n, Label = label };
    145             labelMap[z.Label] = z;
    146           }
    147           nodeMap[n] = labelMap[label];
    148           queue.Enqueue(n);
     189            var g = new GraphNode(node, label);
     190            graph.Add(g);
     191            labelMap[label] = g;
     192          }
     193          nodeMap[node] = labelMap[label];
    149194        } else {
    150           childrenCount[n] = n.SubtreeCount;
    151         }
    152       }
    153       while (queue.Any()) {
    154         var n = queue.Dequeue();
    155         if (n.SubtreeCount > 0) {
     195          var v = new GraphNode(node, label);
    156196          bool found = false;
    157           var label = n.Symbol.Name;
    158           var depth = n.GetDepth();
    159 
    160           bool sort = n.SubtreeCount > 1 && commutativeSymbols.Contains(label);
    161           var nSubtrees = n.Subtrees.Select(x => nodeMap[x]).ToList();
    162           if (sort) nSubtrees.Sort((a, b) => string.CompareOrdinal(a.Label, b.Label));
    163 
    164           for (int i = list.Count - 1; i >= 0; --i) {
    165             var w = list[i];
    166             if (!(n.SubtreeCount == w.SubtreeCount && label == w.Label && depth == w.Depth))
     197          var commutative = node.SubtreeCount > 1 && commutativeSymbols.Contains(label);
     198
     199          IEnumerable<GraphNode> vv, ww;
     200
     201          for (int i = graph.Count - 1; i >= 0; --i) {
     202            var w = graph[i];
     203
     204            if (v.Depth != w.Depth || v.SubtreeCount != w.SubtreeCount || v.Length != w.Length || v.Label != w.Label) {
    167205              continue;
    168 
    169             // sort V and W when the symbol is commutative because we are dealing with unordered trees
    170             var m = w.SymbolicExpressionTreeNode;
    171             var mSubtrees = m.Subtrees.Select(x => nodeMap[x]).ToList();
    172             if (sort) mSubtrees.Sort((a, b) => string.CompareOrdinal(a.Label, b.Label));
    173 
    174             found = nSubtrees.SequenceEqual(mSubtrees);
     206            }
     207
     208            vv = commutative ? v.SymbolicExpressionTreeNode.Subtrees.Select(x => nodeMap[x]).OrderBy(x => x.Hash) : v.SymbolicExpressionTreeNode.Subtrees.Select(x => nodeMap[x]);
     209            ww = commutative ? w.SymbolicExpressionTreeNode.Subtrees.Select(x => nodeMap[x]).OrderBy(x => x.Hash) : w.SymbolicExpressionTreeNode.Subtrees.Select(x => nodeMap[x]);
     210            found = vv.SequenceEqual(ww);
     211
    175212            if (found) {
    176               nodeMap[n] = w;
     213              nodeMap[node] = w;
    177214              break;
    178215            }
    179216          }
    180 
    181217          if (!found) {
    182             var w = new GraphNode { SymbolicExpressionTreeNode = n, Label = label, Depth = depth };
    183             list.Add(w);
    184             nodeMap[n] = w;
    185           }
    186         }
    187 
    188         if (n == n1 || n == n2)
    189           continue;
    190 
    191         var p = n.Parent;
    192         if (p == null)
    193           continue;
    194 
    195         childrenCount[p]--;
    196 
    197         if (childrenCount[p] == 0)
    198           queue.Enqueue(p);
    199       }
    200 
     218            nodeMap[node] = v;
     219            graph.Add(v);
     220          }
     221        }
     222      }
    201223      return nodeMap;
    202224    }
    203225
    204     private IEnumerable<ISymbolicExpressionTreeNode> IterateBreadthOrdered(ISymbolicExpressionTreeNode node, ISymbolicExpressionTreeNodeComparer comparer) {
    205       var list = new List<ISymbolicExpressionTreeNode> { node };
    206       int i = 0;
    207       while (i < list.Count) {
    208         var n = list[i];
    209         if (n.SubtreeCount > 0) {
    210           var subtrees = commutativeSymbols.Contains(node.Symbol.Name) ? n.Subtrees.OrderBy(x => x, comparer) : n.Subtrees;
    211           list.AddRange(subtrees);
    212         }
    213         i++;
    214       }
    215       return list;
    216     }
    217 
    218     private static string GetLabel(ISymbolicExpressionTreeNode node) {
     226    private string GetLabel(ISymbolicExpressionTreeNode node) {
    219227      if (node.SubtreeCount > 0)
    220228        return node.Symbol.Name;
    221229
    222       var constant = node as ConstantTreeNode;
    223       if (constant != null)
    224         return constant.Value.ToString(CultureInfo.InvariantCulture);
    225 
    226       var variable = node as VariableTreeNode;
    227       if (variable != null)
    228         return variable.Weight + variable.VariableName;
     230      if (node is ConstantTreeNode constant)
     231        return MatchConstantValues ? constant.Value.ToString(CultureInfo.InvariantCulture) : constant.Symbol.Name;
     232
     233      if (node is VariableTreeNode variable)
     234        return MatchVariableWeights ? variable.Weight + variable.VariableName : variable.VariableName;
    229235
    230236      return node.ToString();
     
    232238
    233239    private class GraphNode {
    234       public ISymbolicExpressionTreeNode SymbolicExpressionTreeNode;
    235       public string Label;
    236       public int Depth;
     240      private GraphNode() { }
     241
     242      public GraphNode(ISymbolicExpressionTreeNode node, string label) {
     243        SymbolicExpressionTreeNode = node;
     244        Label = label;
     245        Hash = GetHashCode();
     246        Depth = node.GetDepth();
     247        Length = node.GetLength();
     248      }
     249
     250      public int Hash { get; }
     251
     252      public ISymbolicExpressionTreeNode SymbolicExpressionTreeNode { get; }
     253
     254      public string Label { get; }
     255
     256      public int Depth { get; }
     257
    237258      public int SubtreeCount { get { return SymbolicExpressionTreeNode.SubtreeCount; } }
     259
     260      public int Length { get; }
    238261    }
    239262  }
Note: See TracChangeset for help on using the changeset viewer.