source: branches/2915-AbsoluteSymbol/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/TreeMatching/SymbolicExpressionTreeBottomUpSimilarityCalculator.cs @ 16304

Last change on this file since 16304 was 16304, checked in by lkammere, 2 years ago

#2915: Merge changes in the trunk to current HEAD into the branch.

File size: 10.1 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2018 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
4 *
5 * This file is part of HeuristicLab.
6 *
7 * HeuristicLab is free software: you can redistribute it and/or modify
8 * it under the terms of the GNU General Public License as published by
9 * the Free Software Foundation, either version 3 of the License, or
10 * (at your option) any later version.
11 *
12 * HeuristicLab is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15 * GNU General Public License for more details.
16 *
17 * You should have received a copy of the GNU General Public License
18 * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
19 */
20#endregion
21
22using System;
23using System.Collections.Generic;
24using System.Globalization;
25using System.Linq;
26using HeuristicLab.Common;
27using HeuristicLab.Core;
28using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
29using HeuristicLab.Optimization.Operators;
30using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
31
32using NodeMap = System.Collections.Generic.Dictionary<HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.ISymbolicExpressionTreeNode, HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.ISymbolicExpressionTreeNode>;
33
34namespace HeuristicLab.Problems.DataAnalysis.Symbolic {
35  [StorableClass]
36  [Item("SymbolicExpressionTreeBottomUpSimilarityCalculator", "A similarity calculator which uses the tree bottom-up distance as a similarity metric.")]
37  public class SymbolicExpressionTreeBottomUpSimilarityCalculator : SolutionSimilarityCalculator {
38    private readonly HashSet<string> commutativeSymbols = new HashSet<string> { "Addition", "Multiplication", "Average", "And", "Or", "Xor" };
39
40    public SymbolicExpressionTreeBottomUpSimilarityCalculator() { }
41    protected override bool IsCommutative { get { return true; } }
42
43    public bool MatchConstantValues { get; set; }
44    public bool MatchVariableWeights { get; set; }
45
46    [StorableConstructor]
47    protected SymbolicExpressionTreeBottomUpSimilarityCalculator(bool deserializing)
48      : base(deserializing) {
49    }
50
51    protected SymbolicExpressionTreeBottomUpSimilarityCalculator(SymbolicExpressionTreeBottomUpSimilarityCalculator original, Cloner cloner)
52      : base(original, cloner) {
53    }
54
55    public override IDeepCloneable Clone(Cloner cloner) {
56      return new SymbolicExpressionTreeBottomUpSimilarityCalculator(this, cloner);
57    }
58
59    #region static methods
60    private static ISymbolicExpressionTreeNode ActualRoot(ISymbolicExpressionTree tree) {
61      return tree.Root.GetSubtree(0).GetSubtree(0);
62    }
63
64    public static double CalculateSimilarity(ISymbolicExpressionTree t1, ISymbolicExpressionTree t2, bool strict = false) {
65      return CalculateSimilarity(ActualRoot(t1), ActualRoot(t2), strict);
66    }
67
68    public static double CalculateSimilarity(ISymbolicExpressionTreeNode n1, ISymbolicExpressionTreeNode n2, bool strict = false) {
69      var calculator = new SymbolicExpressionTreeBottomUpSimilarityCalculator { MatchConstantValues = strict, MatchVariableWeights = strict };
70      return CalculateSimilarity(n1, n2, strict);
71    }
72
73    public static Dictionary<ISymbolicExpressionTreeNode, ISymbolicExpressionTreeNode> ComputeBottomUpMapping(ISymbolicExpressionTree t1, ISymbolicExpressionTree t2, bool strict = false) {
74      return ComputeBottomUpMapping(ActualRoot(t1), ActualRoot(t2), strict);
75    }
76
77    public static Dictionary<ISymbolicExpressionTreeNode, ISymbolicExpressionTreeNode> ComputeBottomUpMapping(ISymbolicExpressionTreeNode n1, ISymbolicExpressionTreeNode n2, bool strict = false) {
78      var calculator = new SymbolicExpressionTreeBottomUpSimilarityCalculator { MatchConstantValues = strict, MatchVariableWeights = strict };
79      return calculator.ComputeBottomUpMapping(n1, n2);
80    }
81    #endregion
82
83    public double CalculateSimilarity(ISymbolicExpressionTree t1, ISymbolicExpressionTree t2) {
84      return CalculateSimilarity(t1, t2, out Dictionary<ISymbolicExpressionTreeNode, ISymbolicExpressionTreeNode> map);
85    }
86
87    public double CalculateSimilarity(ISymbolicExpressionTree t1, ISymbolicExpressionTree t2, out NodeMap map) {
88      if (t1 == t2) {
89        map = null;
90        return 1;
91      }
92      map = ComputeBottomUpMapping(t1, t2);
93      return 2.0 * map.Count / (t1.Length + t2.Length - 4); // -4 for skipping root and start symbols in the two trees
94    }
95
96    public override double CalculateSolutionSimilarity(IScope leftSolution, IScope rightSolution) {
97      if (leftSolution == rightSolution)
98        return 1.0;
99
100      var t1 = leftSolution.Variables[SolutionVariableName].Value as ISymbolicExpressionTree;
101      var t2 = rightSolution.Variables[SolutionVariableName].Value as ISymbolicExpressionTree;
102
103      if (t1 == null || t2 == null)
104        throw new ArgumentException("Cannot calculate similarity when one of the arguments is null.");
105
106      var similarity = CalculateSimilarity(t1, t2);
107      if (similarity > 1.0)
108        throw new Exception("Similarity value cannot be greater than 1");
109
110      return similarity;
111    }
112
113    public Dictionary<ISymbolicExpressionTreeNode, ISymbolicExpressionTreeNode> ComputeBottomUpMapping(ISymbolicExpressionTree t1, ISymbolicExpressionTree t2) {
114      return ComputeBottomUpMapping(t1.Root.GetSubtree(0).GetSubtree(0), t2.Root.GetSubtree(0).GetSubtree(0));
115    }
116
117    public Dictionary<ISymbolicExpressionTreeNode, ISymbolicExpressionTreeNode> ComputeBottomUpMapping(ISymbolicExpressionTreeNode n1, ISymbolicExpressionTreeNode n2) {
118      var compactedGraph = Compact(n1, n2);
119
120      IEnumerable<ISymbolicExpressionTreeNode> Subtrees(ISymbolicExpressionTreeNode node, bool commutative) {
121        var subtrees = node.IterateNodesPrefix();
122        return commutative ? subtrees.OrderBy(x => compactedGraph[x].Hash) : subtrees;
123      }
124
125      var nodes1 = n1.IterateNodesPostfix().OrderByDescending(x => x.GetLength()); // by descending length so that largest subtrees are mapped first
126      var nodes2 = (List<ISymbolicExpressionTreeNode>)n2.IterateNodesPostfix();
127
128      var forward = new NodeMap();
129      var reverse = new NodeMap();
130
131      foreach (ISymbolicExpressionTreeNode v in nodes1) {
132        if (forward.ContainsKey(v))
133          continue;
134
135        var kv = compactedGraph[v];
136        var commutative = v.SubtreeCount > 1 && commutativeSymbols.Contains(kv.Label);
137
138        foreach (ISymbolicExpressionTreeNode w in nodes2) {
139          if (w.GetLength() != kv.Length || w.GetDepth() != kv.Depth || reverse.ContainsKey(w) || compactedGraph[w] != kv)
140            continue;
141
142          // map one whole subtree to the other
143          foreach (var t in Subtrees(v, commutative).Zip(Subtrees(w, commutative), Tuple.Create)) {
144            forward[t.Item1] = t.Item2;
145            reverse[t.Item2] = t.Item1;
146          }
147
148          break;
149        }
150      }
151
152      return forward;
153    }
154
155    /// <summary>
156    /// Creates a compact representation of the two trees as a directed acyclic graph
157    /// </summary>
158    /// <param name="n1">The root of the first tree</param>
159    /// <param name="n2">The root of the second tree</param>
160    /// <returns>The compacted DAG representing the two trees</returns>
161    private Dictionary<ISymbolicExpressionTreeNode, GraphNode> Compact(ISymbolicExpressionTreeNode n1, ISymbolicExpressionTreeNode n2) {
162      var nodeMap = new Dictionary<ISymbolicExpressionTreeNode, GraphNode>(); // K
163      var labelMap = new Dictionary<string, GraphNode>(); // L
164
165      var nodes = n1.IterateNodesPostfix().Concat(n2.IterateNodesPostfix()); // the disjoint union F
166      var graph = new List<GraphNode>();
167
168      IEnumerable<GraphNode> Subtrees(GraphNode g, bool commutative) {
169        var subtrees = g.SymbolicExpressionTreeNode.Subtrees.Select(x => nodeMap[x]);
170        return commutative ? subtrees.OrderBy(x => x.Hash) : subtrees;
171      }
172
173      foreach (var node in nodes) {
174        var label = GetLabel(node);
175
176        if (node.SubtreeCount == 0) {
177          if (!labelMap.ContainsKey(label)) {
178            labelMap[label] = new GraphNode(node, label);
179          }
180          nodeMap[node] = labelMap[label];
181        } else {
182          var v = new GraphNode(node, label);
183          bool found = false;
184          var commutative = node.SubtreeCount > 1 && commutativeSymbols.Contains(label);
185
186          var vv = Subtrees(v, commutative);
187
188          foreach (var w in graph) {
189            if (v.Depth != w.Depth || v.SubtreeCount != w.SubtreeCount || v.Length != w.Length || v.Label != w.Label) {
190              continue;
191            }
192
193            var ww = Subtrees(w, commutative);
194            found = vv.SequenceEqual(ww);
195
196            if (found) {
197              nodeMap[node] = w;
198              break;
199            }
200          }
201          if (!found) {
202            nodeMap[node] = v;
203            graph.Add(v);
204          }
205        }
206      }
207      return nodeMap;
208    }
209
210    private string GetLabel(ISymbolicExpressionTreeNode node) {
211      if (node.SubtreeCount > 0)
212        return node.Symbol.Name;
213
214      if (node is ConstantTreeNode constant)
215        return MatchConstantValues ? constant.Value.ToString(CultureInfo.InvariantCulture) : constant.Symbol.Name;
216
217      if (node is VariableTreeNode variable)
218        return MatchVariableWeights ? variable.Weight + variable.VariableName : variable.VariableName;
219
220      return node.ToString();
221    }
222
223    private class GraphNode {
224      private GraphNode() { }
225
226      public GraphNode(ISymbolicExpressionTreeNode node, string label) {
227        SymbolicExpressionTreeNode = node;
228        Label = label;
229        Hash = GetHashCode();
230        Depth = node.GetDepth();
231        Length = node.GetLength();
232      }
233
234      public int Hash { get; }
235      public ISymbolicExpressionTreeNode SymbolicExpressionTreeNode { get; }
236      public string Label { get; }
237      public int Depth { get; }
238      public int SubtreeCount { get { return SymbolicExpressionTreeNode.SubtreeCount; } }
239      public int Length { get; }
240    }
241  }
242}
Note: See TracBrowser for help on using the repository browser.