Changeset 11023

Timestamp:

06/17/14 10:30:25 (11 years ago)

Author:

bburlacu

Message:

#1772: Small cosmetic changes in BottomUpDistanceCalculator.cs

File:

• branches/HeuristicLab.EvolutionTracking/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/TreeDistance/BottomUpDistanceCalculator.cs (modified) (8 diffs)

branches/HeuristicLab.EvolutionTracking/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/TreeDistance/BottomUpDistanceCalculator.cs

@@ -1 +1 @@
 #region License Information
 /* HeuristicLab
- * Copyright (C) 2002-2013 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
+ * Copyright (C) 2002-2014 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
  *
  * This file is part of HeuristicLab.
@@ -31 +31 @@
 
 namespace HeuristicLab.Problems.DataAnalysis.Symbolic {
+  /// <summary>
+  /// This class implements the bottom-up tree distance described in the following paper: 
+  /// G. Valiente, "An Efficient Bottom-up Distance Between Trees", http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.102.7958
+  /// </summary>
   public static class BottomUpDistanceCalculator {
     private static Dictionary<ISymbolicExpressionTreeNode, IVertex> Compact(ISymbolicExpressionTree t1, ISymbolicExpressionTree t2) {
@@ -41 +45 @@
       var nodes = F.Nodes.ToList();
 
+      // for all leaf labels l in F
       foreach (var l in nodes.Where(x => x.SubtreeCount == 0)) {
         var label = Label(l);
@@ -49 +54 @@
 
       var Q = new Queue<ISymbolicExpressionTreeNode>();
+
+      // for all nodes
       foreach (var v in nodes) {
         Children[v] = v.SubtreeCount;
@@ -62 +69 @@
         } else {
           bool found = false;
-
+          // for all nodes w in G in reverse order
           foreach (var w in G.Vertices.Reverse()) {
-            if (Height(v) != Height(w))
+            if (Height(v) != Height(w) || v.SubtreeCount != w.OutDegree || Label(v) != w.Label)
               break;
-            if (v.SubtreeCount != w.OutDegree)
-              break;
-            if (Label(v) != w.Label)
-              break;
-
+
+            // sort V and W because we are dealing with unordered trees
             var V = v.Subtrees.Select(s => K[s]).OrderBy(x => x.Label);
             var W = w.OutArcs.Select(x => x.Target).OrderBy(x => x.Label);
@@ -91 +95 @@
         } // 42: end if
 
-        if (v.Parent == null) continue;
-        var p = v.Parent;
-        Children[p]--;
-        if (Children[p] == 0)
-          Q.Enqueue(p);
+        if (v.Parent != null) {
+          var p = v.Parent;
+          Children[p]--;
+          if (Children[p] == 0)
+            Q.Enqueue(p);
+        }
       };
 
@@ -118 +123 @@
             if (!M_.ContainsKey(u)) {
               w = u;
+              // commented out test below since we are dealing with unordered trees
               //              if (plist2.IndexOf(u) < pw) {
               //                w = u;
@@ -183 +189 @@
     }
 
-    // draw the mapping between t1 and t2
+    // draw the mapping between t1 and t2 as a tikz picture
     private static string FormatMapping(ISymbolicExpressionTree t1, ISymbolicExpressionTree t2, Dictionary<ISymbolicExpressionTreeNode, ISymbolicExpressionTreeNode> map) {
       var formatter = new SymbolicExpressionTreeLatexFormatter();