1  #region License Information


2  /* HeuristicLab


3  * Copyright (C) 20022019 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 


22  using System;


23  using System.Collections.Generic;


24  using System.Globalization;


25  using System.Linq;


26  using HeuristicLab.Common;


27  using HeuristicLab.Core;


28  using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;


29  using HeuristicLab.Optimization.Operators;


30  using HEAL.Attic;


31 


32  using NodeMap = System.Collections.Generic.Dictionary<HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.ISymbolicExpressionTreeNode, HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.ISymbolicExpressionTreeNode>;


33 


34  namespace HeuristicLab.Problems.DataAnalysis.Symbolic {


35  [StorableType("63ACB7A4137F468FBE42A4CA6B62C63B")]


36  [Item("SymbolicExpressionTreeBottomUpSimilarityCalculator", "A similarity calculator which uses the tree bottomup 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(StorableConstructorFlag _) : base(_) {


48  }


49 


50  protected SymbolicExpressionTreeBottomUpSimilarityCalculator(SymbolicExpressionTreeBottomUpSimilarityCalculator original, Cloner cloner)


51  : base(original, cloner) {


52  }


53 


54  public override IDeepCloneable Clone(Cloner cloner) {


55  return new SymbolicExpressionTreeBottomUpSimilarityCalculator(this, cloner);


56  }


57 


58  #region static methods


59  private static ISymbolicExpressionTreeNode ActualRoot(ISymbolicExpressionTree tree) {


60  return tree.Root.GetSubtree(0).GetSubtree(0);


61  }


62 


63  public static double CalculateSimilarity(ISymbolicExpressionTree t1, ISymbolicExpressionTree t2, bool strict = false) {


64  return CalculateSimilarity(ActualRoot(t1), ActualRoot(t2), strict);


65  }


66 


67  public static double CalculateSimilarity(ISymbolicExpressionTreeNode n1, ISymbolicExpressionTreeNode n2, bool strict = false) {


68  var calculator = new SymbolicExpressionTreeBottomUpSimilarityCalculator { MatchConstantValues = strict, MatchVariableWeights = strict };


69  return CalculateSimilarity(n1, n2, strict);


70  }


71 


72  public static Dictionary<ISymbolicExpressionTreeNode, ISymbolicExpressionTreeNode> ComputeBottomUpMapping(ISymbolicExpressionTree t1, ISymbolicExpressionTree t2, bool strict = false) {


73  return ComputeBottomUpMapping(ActualRoot(t1), ActualRoot(t2), strict);


74  }


75 


76  public static Dictionary<ISymbolicExpressionTreeNode, ISymbolicExpressionTreeNode> ComputeBottomUpMapping(ISymbolicExpressionTreeNode n1, ISymbolicExpressionTreeNode n2, bool strict = false) {


77  var calculator = new SymbolicExpressionTreeBottomUpSimilarityCalculator { MatchConstantValues = strict, MatchVariableWeights = strict };


78  return calculator.ComputeBottomUpMapping(n1, n2);


79  }


80  #endregion


81 


82  public double CalculateSimilarity(ISymbolicExpressionTree t1, ISymbolicExpressionTree t2) {


83  return CalculateSimilarity(t1, t2, out Dictionary<ISymbolicExpressionTreeNode, ISymbolicExpressionTreeNode> map);


84  }


85 


86  public double CalculateSimilarity(ISymbolicExpressionTree t1, ISymbolicExpressionTree t2, out NodeMap map) {


87  if (t1 == t2) {


88  map = null;


89  return 1;


90  }


91  map = ComputeBottomUpMapping(t1, t2);


92  return 2.0 * map.Count / (t1.Length + t2.Length  4); // 4 for skipping root and start symbols in the two trees


93  }


94 


95  public override double CalculateSolutionSimilarity(IScope leftSolution, IScope rightSolution) {


96  if (leftSolution == rightSolution)


97  return 1.0;


98 


99  var t1 = leftSolution.Variables[SolutionVariableName].Value as ISymbolicExpressionTree;


100  var t2 = rightSolution.Variables[SolutionVariableName].Value as ISymbolicExpressionTree;


101 


102  if (t1 == null  t2 == null)


103  throw new ArgumentException("Cannot calculate similarity when one of the arguments is null.");


104 


105  var similarity = CalculateSimilarity(t1, t2);


106  if (similarity > 1.0)


107  throw new Exception("Similarity value cannot be greater than 1");


108 


109  return similarity;


110  }


111 


112  public Dictionary<ISymbolicExpressionTreeNode, ISymbolicExpressionTreeNode> ComputeBottomUpMapping(ISymbolicExpressionTree t1, ISymbolicExpressionTree t2) {


113  return ComputeBottomUpMapping(ActualRoot(t1), ActualRoot(t2));


114  }


115 


116  public Dictionary<ISymbolicExpressionTreeNode, ISymbolicExpressionTreeNode> ComputeBottomUpMapping(ISymbolicExpressionTreeNode n1, ISymbolicExpressionTreeNode n2) {


117  var compactedGraph = Compact(n1, n2);


118 


119  IEnumerable<ISymbolicExpressionTreeNode> Subtrees(ISymbolicExpressionTreeNode node, bool commutative) {


120  var subtrees = node.IterateNodesPrefix();


121  return commutative ? subtrees.OrderBy(x => compactedGraph[x].Hash) : subtrees;


122  }


123 


124  var nodes1 = n1.IterateNodesPostfix().OrderByDescending(x => x.GetLength()); // by descending length so that largest subtrees are mapped first


125  var nodes2 = (List<ISymbolicExpressionTreeNode>)n2.IterateNodesPostfix();


126 


127  var forward = new NodeMap();


128  var reverse = new NodeMap();


129 


130  foreach (ISymbolicExpressionTreeNode v in nodes1) {


131  if (forward.ContainsKey(v))


132  continue;


133 


134  var kv = compactedGraph[v];


135  var commutative = v.SubtreeCount > 1 && commutativeSymbols.Contains(kv.Label);


136 


137  foreach (ISymbolicExpressionTreeNode w in nodes2) {


138  if (w.GetLength() != kv.Length  w.GetDepth() != kv.Depth  reverse.ContainsKey(w)  compactedGraph[w] != kv)


139  continue;


140 


141  // map one whole subtree to the other


142  foreach (var t in Subtrees(v, commutative).Zip(Subtrees(w, commutative), Tuple.Create)) {


143  forward[t.Item1] = t.Item2;


144  reverse[t.Item2] = t.Item1;


145  }


146 


147  break;


148  }


149  }


150 


151  return forward;


152  }


153 


154  /// <summary>


155  /// Creates a compact representation of the two trees as a directed acyclic graph


156  /// </summary>


157  /// <param name="n1">The root of the first tree</param>


158  /// <param name="n2">The root of the second tree</param>


159  /// <returns>The compacted DAG representing the two trees</returns>


160  private Dictionary<ISymbolicExpressionTreeNode, GraphNode> Compact(ISymbolicExpressionTreeNode n1, ISymbolicExpressionTreeNode n2) {


161  var nodeMap = new Dictionary<ISymbolicExpressionTreeNode, GraphNode>(); // K


162  var labelMap = new Dictionary<string, GraphNode>(); // L


163 


164  var nodes = n1.IterateNodesPostfix().Concat(n2.IterateNodesPostfix()); // the disjoint union F


165  var graph = new List<GraphNode>();


166 


167  IEnumerable<GraphNode> Subtrees(GraphNode g, bool commutative) {


168  var subtrees = g.SymbolicExpressionTreeNode.Subtrees.Select(x => nodeMap[x]);


169  return commutative ? subtrees.OrderBy(x => x.Hash) : subtrees;


170  }


171 


172  foreach (var node in nodes) {


173  var label = GetLabel(node);


174 


175  if (node.SubtreeCount == 0) {


176  if (!labelMap.ContainsKey(label)) {


177  labelMap[label] = new GraphNode(node, label);


178  }


179  nodeMap[node] = labelMap[label];


180  } else {


181  var v = new GraphNode(node, label);


182  bool found = false;


183  var commutative = node.SubtreeCount > 1 && commutativeSymbols.Contains(label);


184 


185  var vv = Subtrees(v, commutative);


186 


187  foreach (var w in graph) {


188  if (v.Depth != w.Depth  v.SubtreeCount != w.SubtreeCount  v.Length != w.Length  v.Label != w.Label) {


189  continue;


190  }


191 


192  var ww = Subtrees(w, commutative);


193  found = vv.SequenceEqual(ww);


194 


195  if (found) {


196  nodeMap[node] = w;


197  break;


198  }


199  }


200  if (!found) {


201  nodeMap[node] = v;


202  graph.Add(v);


203  }


204  }


205  }


206  return nodeMap;


207  }


208 


209  private string GetLabel(ISymbolicExpressionTreeNode node) {


210  if (node.SubtreeCount > 0)


211  return node.Symbol.Name;


212 


213  if (node is ConstantTreeNode constant)


214  return MatchConstantValues ? constant.Value.ToString(CultureInfo.InvariantCulture) : constant.Symbol.Name;


215 


216  if (node is VariableTreeNode variable)


217  return MatchVariableWeights ? variable.Weight + variable.VariableName : variable.VariableName;


218 


219  return node.ToString();


220  }


221 


222  private class GraphNode {


223  private GraphNode() { }


224 


225  public GraphNode(ISymbolicExpressionTreeNode node, string label) {


226  SymbolicExpressionTreeNode = node;


227  Label = label;


228  Hash = GetHashCode();


229  Depth = node.GetDepth();


230  Length = node.GetLength();


231  }


232 


233  public int Hash { get; }


234  public ISymbolicExpressionTreeNode SymbolicExpressionTreeNode { get; }


235  public string Label { get; }


236  public int Depth { get; }


237  public int SubtreeCount { get { return SymbolicExpressionTreeNode.SubtreeCount; } }


238  public int Length { get; }


239  }


240  }


241  }

