Changeset 11486 for branches/HeuristicLab.BottomUpTreeDistance/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/SimilarityCalculators/BottomUpSimilarityCalculator.cs
- Timestamp:
- 10/21/14 19:56:48 (10 years ago)
- File:
-
- 1 moved
Legend:
- Unmodified
- Added
- Removed
-
branches/HeuristicLab.BottomUpTreeDistance/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/SimilarityCalculators/BottomUpSimilarityCalculator.cs
r11482 r11486 22 22 using System; 23 23 using System.Collections.Generic; 24 using System.Diagnostics; 25 using System.Globalization; 24 26 using System.Linq; 25 27 using HeuristicLab.Common; … … 31 33 namespace HeuristicLab.Problems.DataAnalysis.Symbolic { 32 34 [StorableClass] 33 [Item("BottomUp TreeSimilarityCalculator", "A similarity calculator which uses the tree bottom-up distance as a similarity metric.")]34 public class BottomUp TreeSimilarityCalculator : SingleObjectiveSolutionSimilarityCalculator {35 private readonly HashSet<string> commutativeSymbols ;36 37 public BottomUpTreeSimilarityCalculator() {38 commutativeSymbols = new HashSet<string>(); 39 }40 41 p ublic BottomUpTreeSimilarityCalculator(IEnumerable<string> commutativeSymbols) {42 this.commutativeSymbols = new HashSet<string>(commutativeSymbols);35 [Item("BottomUpSimilarityCalculator", "A similarity calculator which uses the tree bottom-up distance as a similarity metric.")] 36 public class BottomUpSimilarityCalculator : SingleObjectiveSolutionSimilarityCalculator { 37 private readonly HashSet<string> commutativeSymbols = new HashSet<string> { "Addition", "Multiplication", "Average", "And", "Or", "Xor" }; 38 public bool MatchVariableWeights { get; set; } 39 public bool MatchConstantValues { get; set; } 40 41 public BottomUpSimilarityCalculator() { } 42 43 protected BottomUpSimilarityCalculator(BottomUpSimilarityCalculator original, Cloner cloner) 44 : base(original, cloner) { 43 45 } 44 46 45 47 public override IDeepCloneable Clone(Cloner cloner) { 46 return new BottomUpTreeSimilarityCalculator(this, cloner); 47 } 48 49 protected BottomUpTreeSimilarityCalculator(BottomUpTreeSimilarityCalculator original, Cloner cloner) 50 : base(original, cloner) { 48 return new BottomUpSimilarityCalculator(this, cloner); 49 } 50 51 public double CalculateSimilarity(ISymbolicExpressionTree t1, ISymbolicExpressionTree t2) { 52 if (t1 == t2) 53 return 1; 54 55 var map = ComputeBottomUpMapping(t1.Root, t2.Root); 56 return 2.0 * map.Count / (t1.Length + t2.Length); 51 57 } 52 58 … … 58 64 throw new ArgumentException("Cannot calculate similarity when one of the arguments is null."); 59 65 60 var similarity = CalculateS olutionSimilarity(t1, t2);66 var similarity = CalculateSimilarity(t1, t2); 61 67 if (similarity > 1.0) 62 68 throw new Exception("Similarity value cannot be greater than 1"); … … 65 71 } 66 72 67 public bool AddCommutativeSymbol(string symbolName) {68 return commutativeSymbols.Add(symbolName);69 }70 71 public bool RemoveCommutativeSymbol(string symbolName) {72 return commutativeSymbols.Remove(symbolName);73 }74 75 public double CalculateSolutionSimilarity(ISymbolicExpressionTree t1, ISymbolicExpressionTree t2) {76 if (t1 == t2)77 return 1;78 79 var map = ComputeBottomUpMapping(t1.Root, t2.Root);80 return 2.0 * map.Count / (t1.Length + t2.Length);81 }82 83 73 public Dictionary<ISymbolicExpressionTreeNode, ISymbolicExpressionTreeNode> ComputeBottomUpMapping(ISymbolicExpressionTreeNode n1, ISymbolicExpressionTreeNode n2) { 74 var comparer = new SymbolicExpressionTreeNodeComparer(); // use a node comparer because it's faster than calling node.ToString() (strings are expensive) and comparing strings 84 75 var compactedGraph = Compact(n1, n2); 85 76 … … 103 94 // at this point we know that v and w are isomorphic, however, the mapping cannot be done directly (as in the paper) because the trees are unordered (subtree order might differ) 104 95 // the solution is to sort subtrees by label using IterateBreadthOrdered (this will work because the subtrees are isomorphic!) and simultaneously iterate over the two subtrees 105 var eV = IterateBreadthOrdered(v ).GetEnumerator();106 var eW = IterateBreadthOrdered(w ).GetEnumerator();96 var eV = IterateBreadthOrdered(v, comparer).GetEnumerator(); 97 var eW = IterateBreadthOrdered(w, comparer).GetEnumerator(); 107 98 108 99 while (eV.MoveNext() && eW.MoveNext()) { … … 110 101 var t = eW.Current; 111 102 112 if (reverseMap.ContainsKey(t)) { 113 throw new Exception("A mapping to this node already exists."); 114 } 103 Debug.Assert(!reverseMap.ContainsKey(t)); 115 104 116 105 forwardMap[s] = t; … … 134 123 135 124 var nodes = n1.IterateNodesPostfix().Concat(n2.IterateNodesPostfix()); // the disjoint union F 136 var list = new List<GraphNode>(); 125 var list = new List<GraphNode>(); // preallocate size to avoid list resizing as it has a performance hit 137 126 var queue = new Queue<ISymbolicExpressionTreeNode>(); 138 127 139 128 foreach (var n in nodes) { 140 129 if (n.SubtreeCount == 0) { 141 var label = n.ToString();130 var label = Label(n); 142 131 if (!labelMap.ContainsKey(label)) { 143 132 var z = new GraphNode { SymbolicExpressionTreeNode = n, Label = label }; … … 161 150 bool sort = commutativeSymbols.Contains(label); 162 151 var nNodes = n.Subtrees.Select(x => nodeMap[x]).ToList(); 163 if (sort) nNodes.Sort((a, b) => String.Compare(a.Label, b.Label, StringComparison.Ordinal));152 if (sort) nNodes.Sort((a, b) => string.CompareOrdinal(a.Label, b.Label)); 164 153 165 154 for (int i = list.Count - 1; i >= 0; --i) { … … 172 161 var m = w.SymbolicExpressionTreeNode; 173 162 var mNodes = m.Subtrees.Select(x => nodeMap[x]).ToList(); 174 if (sort) mNodes.Sort((a, b) => String.Compare(a.Label, b.Label, StringComparison.Ordinal));163 if (sort) mNodes.Sort((a, b) => string.CompareOrdinal(a.Label, b.Label)); 175 164 176 165 if (nNodes.SequenceEqual(mNodes)) { … … 182 171 183 172 if (!found) { 184 var w = new GraphNode { SymbolicExpressionTreeNode = n, Label = label, Depth = depth , ChildrenCount = n.SubtreeCount};173 var w = new GraphNode { SymbolicExpressionTreeNode = n, Label = label, Depth = depth }; 185 174 list.Add(w); 186 175 nodeMap[n] = w; … … 188 177 } 189 178 179 if (n == n1 || n == n2) 180 continue; 181 190 182 var p = n.Parent; 191 183 if (p == null) … … 201 193 } 202 194 203 /// <summary> 204 /// This method iterates the nodes of a subtree in breadth order while also sorting the subtrees of commutative symbols based on their label. 205 /// This is necessary in order for the mapping to be realized correctly. 206 /// </summary> 207 /// <param name="node">The root of the subtree</param> 208 /// <returns>A list of nodes in breadth order (with children of commutative symbols sorted by label)</returns> 209 private IEnumerable<ISymbolicExpressionTreeNode> IterateBreadthOrdered(ISymbolicExpressionTreeNode node) { 195 private IEnumerable<ISymbolicExpressionTreeNode> IterateBreadthOrdered(ISymbolicExpressionTreeNode node, ISymbolicExpressionTreeNodeComparer comparer) { 210 196 var list = new List<ISymbolicExpressionTreeNode> { node }; 211 197 int i = 0; … … 213 199 var n = list[i]; 214 200 if (n.SubtreeCount > 0) { 215 var subtrees = commutativeSymbols.Contains(node.Symbol.Name) ? n.Subtrees.OrderBy(x => x .ToString(), StringComparer.Ordinal) : n.Subtrees;201 var subtrees = commutativeSymbols.Contains(node.Symbol.Name) ? n.Subtrees.OrderBy(x => x, comparer) : n.Subtrees; 216 202 list.AddRange(subtrees); 217 203 } … … 219 205 } 220 206 return list; 207 } 208 209 private string Label(ISymbolicExpressionTreeNode node) { 210 if (node.SubtreeCount > 0) 211 return node.Symbol.Name; 212 213 var constant = node as ConstantTreeNode; 214 if (constant != null) 215 return MatchConstantValues ? constant.Value.ToString(CultureInfo.InvariantCulture) : constant.Symbol.Name; 216 var variable = node as VariableTreeNode; 217 if (variable != null) { 218 return MatchVariableWeights ? variable.Weight + variable.VariableName : variable.VariableName; 219 } 220 221 return node.ToString(); 221 222 } 222 223 … … 225 226 public string Label; 226 227 public int Depth; 227 public int ChildrenCount ;228 public int ChildrenCount { get { return SymbolicExpressionTreeNode.SubtreeCount; } } 228 229 } 229 230 }
Note: See TracChangeset
for help on using the changeset viewer.