Changeset 11221 for branches/HeuristicLab.BottomUpTreeDistance

Timestamp:

07/23/14 22:49:51 (10 years ago)

Author:

bburlacu

Message:

#2215: Fixed incorrect namespace of the BottomUpSimilarityCalculator. Changed signature of ComputeBottomMapping method to take tree nodes as arguments rather than trees, because we should be able to compute the bottom-up distance for any two subtrees. Added internal diversity calculator based on the bottom-up distance, which computes the average diversity of all the nodes inside a tree individual.

Location:

branches/HeuristicLab.BottomUpTreeDistance

Files:

• HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Analyzers/SymbolicDataAnalysisInternalDiversityAnalyzer.cs (added)
• HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/HeuristicLab.Problems.DataAnalysis.Symbolic-3.4.csproj (modified) (1 diff)
• HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/SimilarityCalculators/BottomUpSimilarityCalculator.cs (modified) (4 diffs)
• HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/SimilarityCalculators/MaxCommonSubtreeSimilarityCalculator.cs (modified) (1 diff)
• HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/SymbolicDataAnalysisProblem.cs (modified) (1 diff)
• HeuristicLab.Tests/BottomUpSimilarityCalculatorTest.cs (modified) (3 diffs)

branches/HeuristicLab.BottomUpTreeDistance/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/HeuristicLab.Problems.DataAnalysis.Symbolic-3.4.csproj

@@ -197 +197 @@
   </ItemGroup>
   <ItemGroup>
+    <Compile Include="Analyzers\SymbolicDataAnalysisInternalDiversityAnalyzer.cs" />
     <Compile Include="Analyzers\SymbolicDataAnalysisSingleObjectivePruningAnalyzer.cs" />
     <Compile Include="Analyzers\SymbolicDataAnalysisSingleObjectiveValidationParetoBestSolutionAnalyzer.cs" />

branches/HeuristicLab.BottomUpTreeDistance/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/SimilarityCalculators/BottomUpSimilarityCalculator.cs

@@ -29 +29 @@
 using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
 
-namespace HeuristicLab.Problems.DataAnalysis.Symbolic.SimilarityCalculators {
+namespace HeuristicLab.Problems.DataAnalysis.Symbolic {
   [StorableClass]
   [Item("BottomUpSimilarityCalculator", "A similarity calculator which uses the tree bottom-up distance as a similarity metric.")]
@@ -59 +59 @@
         return 1;
 
-      var map = ComputeBottomUpMapping(t1, t2);
+      var map = ComputeBottomUpMapping(t1.Root, t2.Root);
       return 2.0 * map.Count / (t1.Length + t2.Length);
     }
 
-
-    public Dictionary<ISymbolicExpressionTreeNode, ISymbolicExpressionTreeNode> ComputeBottomUpMapping(ISymbolicExpressionTree t1, ISymbolicExpressionTree t2) {
-      var compactedGraph = Compact(t1, t2);
+    public Dictionary<ISymbolicExpressionTreeNode, ISymbolicExpressionTreeNode> ComputeBottomUpMapping(ISymbolicExpressionTreeNode n1, ISymbolicExpressionTreeNode n2) {
+      var compactedGraph = Compact(n1, n2);
 
       var forwardMap = new Dictionary<ISymbolicExpressionTreeNode, ISymbolicExpressionTreeNode>(); // nodes of t1 => nodes of t2
       var reverseMap = new Dictionary<ISymbolicExpressionTreeNode, ISymbolicExpressionTreeNode>(); // nodes of t2 => nodes of t1
 
-      foreach (var v in t1.IterateNodesBreadth()) {
+      foreach (var v in n1.IterateNodesBreadth()) {
         if (forwardMap.ContainsKey(v)) continue;
         var kv = compactedGraph[v];
         ISymbolicExpressionTreeNode w = null;
-        foreach (var t in t2.IterateNodesBreadth()) {
+        foreach (var t in n2.IterateNodesBreadth()) {
           if (reverseMap.ContainsKey(t) || compactedGraph[t] != kv) continue;
           w = t;
@@ -103 +102 @@
     /// <param name="t2">The second tree</param>
     /// <returns>The compacted DAG representing the two trees</returns>
-    private Dictionary<ISymbolicExpressionTreeNode, IVertex> Compact(ISymbolicExpressionTree t1, ISymbolicExpressionTree t2) {
+    private Dictionary<ISymbolicExpressionTreeNode, IVertex> Compact(ISymbolicExpressionTreeNode n1, ISymbolicExpressionTreeNode n2) {
       var nodesToVertices = new Dictionary<ISymbolicExpressionTreeNode, IVertex>(); // K
       var labelsToVertices = new Dictionary<string, IVertex>(); // L
@@ -109 +108 @@
       var vertices = new List<IVertex>(); // G
 
-      var nodes = t1.IterateNodesPostfix().Concat(t2.IterateNodesPostfix()); // the disjoint union F
+      var nodes = n1.IterateNodesPostfix().Concat(n2.IterateNodesPostfix()); // the disjoint union F
       var queue = new Queue<ISymbolicExpressionTreeNode>();
 

branches/HeuristicLab.BottomUpTreeDistance/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/SimilarityCalculators/MaxCommonSubtreeSimilarityCalculator.cs

@@ -27 +27 @@
 using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
 
-namespace HeuristicLab.Problems.DataAnalysis.Symbolic.SimilarityCalculators {
+namespace HeuristicLab.Problems.DataAnalysis.Symbolic {
   [StorableClass]
   [Item("MaxCommonSubtreeSimilarityCalculator", "A similarity calculator based on the size of the maximum common subtree between two trees")]

branches/HeuristicLab.BottomUpTreeDistance/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/SymbolicDataAnalysisProblem.cs

@@ -34 +34 @@
 using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
 using HeuristicLab.PluginInfrastructure;
-using HeuristicLab.Problems.DataAnalysis.Symbolic.SimilarityCalculators;
 using HeuristicLab.Problems.Instances;
 

branches/HeuristicLab.BottomUpTreeDistance/HeuristicLab.Tests/BottomUpSimilarityCalculatorTest.cs

@@ -8 +8 @@
 using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
 using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.Views;
-using HeuristicLab.Problems.DataAnalysis.Symbolic.SimilarityCalculators;
 using HeuristicLab.Random;
 using Microsoft.VisualStudio.TestTools.UnitTesting;
@@ -33 +32 @@
       TestMatchedNodes("(+ 1 2)", "(+ 2 1)", 5);
       TestMatchedNodes("(- 2 1)", "(- 1 2)", 2);
+      TestMatchedNodes("(* (variable 1 X1) (variable 1 X2))", "(* (+ (variable 1 X1) 1) (+ (variable 1 X2) 1))", 2);
 
       TestMatchedNodes("(* (variable 1 X1) (variable 1 X2))", "(* (+ (variable 1 X1) 1) (variable 1 X2))", 2);
@@ -52 +52 @@
       var t2 = importer.Import(expr2);
 
-      var mapping = busCalculator.ComputeBottomUpMapping(t1, t2);
+      var mapping = busCalculator.ComputeBottomUpMapping(t1.Root, t2.Root);
       var c = mapping.Count;