Changeset 13892

Timestamp:

06/12/16 22:34:22 (8 years ago)

Author:

bburlacu

Message:

#1772: Fix bug in tree matching with wildcards (used by the genealogy graph view instead of the query match) and improved subtree selection and matching functionality in the genealogy graph view.

Location:

branches/HeuristicLab.EvolutionTracking

Files:

• HeuristicLab.Problems.DataAnalysis.Symbolic.Views/3.4/Tracking/SymbolicDataAnalysisGenealogyGraphView.cs (modified) (12 diffs)
• HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/TreeMatching/SymbolicExpressionTreeMatching.cs (modified) (2 diffs)

branches/HeuristicLab.EvolutionTracking/HeuristicLab.Problems.DataAnalysis.Symbolic.Views/3.4/Tracking/SymbolicDataAnalysisGenealogyGraphView.cs

@@ -41 +41 @@
     private TraceData lastTd;
 
+    private ISymbolicExpressionTreeNode clonedSubtree;
+    private Dictionary<ISymbolicExpressionTreeNode, ISymbolicExpressionTreeNode> clonedMap;
+
     private ISymbolicExpressionTreeNode selectedSubtree;
     private ISymbolicExpressionTreeNode SelectedSubtree {
       get { return selectedSubtree; }
       set {
-        if (value == null || selectedSubtree == value) return;
+        if (value == null) return;
         selectedSubtree = value;
-        ClonedSubtree = (ISymbolicExpressionTreeNode)selectedSubtree.Clone();
-      }
-    }
-    // the clone is necessary in order to deselect parts of a tree (by removing subtrees) 
-    // and do "high level" matching of the remaining part
-    private ISymbolicExpressionTreeNode ClonedSubtree { get; set; }
+        // the code below enables a "shadow" copy of the selected subtree which is used for matching against the graph 
+        clonedSubtree = (ISymbolicExpressionTreeNode)selectedSubtree.Clone();
+        clonedMap = new Dictionary<ISymbolicExpressionTreeNode, ISymbolicExpressionTreeNode>();
+        var e1 = selectedSubtree.IterateNodesPrefix().GetEnumerator();
+        var e2 = clonedSubtree.IterateNodesPrefix().GetEnumerator();
+
+        while (e1.MoveNext() && e2.MoveNext()) {
+          clonedMap.Add(e1.Current, e2.Current);
+        }
+      }
+    }
 
     // we use the symbolic expression tree chart to call the drawing routines
@@ -74 +82 @@
         genealogyGraphChart.GenealogyGraph = Content;
       }
+    }
+
+    protected override void RegisterContentEvents() {
+      base.RegisterContentEvents();
+      if (SymbolicExpressionTreeChart != null)
+        SymbolicExpressionTreeChart.SymbolicExpressionTreeNodeClicked += treeChart_SymbolicExpressionTreeNodeClicked;
+    }
+
+    protected override void DeregisterContentEvents() {
+      if (SymbolicExpressionTreeChart != null)
+        SymbolicExpressionTreeChart.SymbolicExpressionTreeNodeClicked -= treeChart_SymbolicExpressionTreeNodeClicked;
+      base.DeregisterContentEvents();
     }
 
@@ -110 +130 @@
       var nodes = graphNode.Data.IterateNodesPrefix().ToList();
       // calculate max only in the current generation
-      var max = Content.Vertices.Max(x => ((IGenealogyGraphNode<ISymbolicExpressionTree>)x).Data.IterateNodesPrefix().Max(n => n.NodeWeight));
+      var max = Content.Vertices.Max(x => x.Data.IterateNodesPrefix().Max(n => n.NodeWeight));
       if (max.IsAlmost(0)) max = 1;
       // we skip the program root node because it's useless for display and it just takes space in the chart 
@@ -121 +141 @@
       }
 
-      if (!graphNode.InArcs.Any()) return;
+      if (!graphNode.InArcs.Any())
+        return;
       var data = graphNode.InArcs.Last().Data;
       var fragment = data as IFragment<ISymbolicExpressionTreeNode>;
@@ -133 +154 @@
       } else if (td != null) {
         // highlight traced subtree and fragment
-        treeChart_HighlightSubtree(nodes[td.SubtreeIndex], Color.Orange);
-        treeChart_HighlightSubtree(nodes[td.FragmentIndex], Color.CornflowerBlue);
+        if (td.SubtreeIndex == td.FragmentIndex) {
+          treeChart_HighlightSubtree(nodes[td.SubtreeIndex], Color.Purple);
+        } else if (td.SubtreeIndex < td.FragmentIndex) {
+          treeChart_HighlightSubtree(nodes[td.SubtreeIndex], Color.Orange);
+          treeChart_HighlightSubtree(nodes[td.FragmentIndex], Color.CornflowerBlue);
+        } else {
+          treeChart_HighlightSubtree(nodes[td.FragmentIndex], Color.CornflowerBlue);
+          treeChart_HighlightSubtree(nodes[td.SubtreeIndex], Color.Orange);
+        }
       }
     }
@@ -149 +177 @@
         var subtreeIndex = graphNode.Data.IterateNodesPrefix().ToList().IndexOf(node);
         var traceGraph = TraceCalculator.TraceSubtree(graphNode, subtreeIndex, updateVertexWeights: false, updateSubtreeWeights: false, cacheTraceNodes: true);
+
+        if (!traceGraph.Vertices.Any())
+          return;
+
         genealogyGraphChart.SuspendRendering();
         genealogyGraphChart.ClearPrimitives(); // clear everything
         var rankMaximums = new Dictionary<double, double>();
+
+        if (openNew_CheckBox.Checked) {
+          MainFormManager.MainForm.ShowContent(traceGraph);
+        } else {
+        }
         // fill each vertex in the graph with a grayscale color according to average subtree weight
 
-        int colorCount = ColorGradient.GrayscaledColors.Count - 1;
-        var colorGradient = ColorGradient.GrayscaledColors;
-        foreach (var r in Content.Ranks) {
-          var vertices = r.Value.Cast<IGenealogyGraphNode<ISymbolicExpressionTree>>().ToList();
-          var averages = vertices.Select(x => x.Data.IterateNodesPrefix().Average(n => n.NodeWeight)).ToList();
-          var max = averages.Max();
-          rankMaximums.Add(r.Key, max);
-          if (max.IsAlmost(0.0)) continue;
-          for (int i = 0; i < vertices.Count; ++i) {
-            var color = colorGradient[(int)Math.Round(averages[i] / max * colorCount)];
-            var vNode = genealogyGraphChart.GetMappedNode(vertices[i]);
-            vNode.Brush = new SolidBrush(color);
-          }
-        }
-        // fill vertices that are part of the trace with a rgb color according to average subtree weight
-        if (traceGraph.Vertices.Any()) {
-          var ranks = traceGraph.Vertices.Select(x => Content.GetByContent(x.Data)).GroupBy(x => x.Rank);
-          foreach (var g in ranks) {
-            var vertices = g.ToList();
-            var averages = vertices.Select(x => x.Data.IterateNodesPrefix().Average(n => n.NodeWeight)).ToList();
-            double max = rankMaximums[g.Key];
-            if (max.IsAlmost(0.0)) continue;
-            for (int i = 0; i < vertices.Count; ++i) {
-              var vNode = genealogyGraphChart.GetMappedNode(vertices[i]);
-              // use a grayscale gradient
-              var color = colorGradient[(int)Math.Round(averages[i] / max * colorCount)];
-              vNode.Brush = new SolidBrush(color);
-            }
-          }
-
-          if (openNew_CheckBox.Checked) {
-            MainFormManager.MainForm.ShowContent(traceGraph); // display the fragment graph on the screen
-          }
-        }
+        /*
+                var colorGradient = ColorGradient.GrayscaledColors;
+                var colorCount = colorGradient.Count - 1;
+                foreach (var r in Content.Ranks) {
+                  var vertices = r.Value.Cast<IGenealogyGraphNode<ISymbolicExpressionTree>>().ToList();
+                  var averages = vertices.Select(x => x.Data.IterateNodesPrefix().Average(n => n.NodeWeight)).ToList();
+                  var max = averages.Max();
+                  rankMaximums.Add(r.Key, max);
+                  if (max.IsAlmost(0.0)) continue;
+                  for (int i = 0; i < vertices.Count; ++i) {
+                    var color = colorGradient[(int)Math.Round(averages[i] / max * colorCount)];
+                    var vNode = genealogyGraphChart.GetMappedNode(vertices[i]);
+                    vNode.Brush = new SolidBrush(color);
+                  }
+                }
+                // fill vertices that are part of the trace with a rgb color according to average subtree weight
+                if (traceGraph.Vertices.Any()) {
+                  var ranks = traceGraph.Vertices.Select(x => Content.GetByContent(x.Data)).GroupBy(x => x.Rank);
+                  foreach (var g in ranks) {
+                    var vertices = g.ToList();
+                    var averages = vertices.Select(x => x.Data.IterateNodesPrefix().Average(n => n.NodeWeight)).ToList();
+                    double max = rankMaximums[g.Key];
+                    if (max.IsAlmost(0.0)) continue;
+                    for (int i = 0; i < vertices.Count; ++i) {
+                      var vNode = genealogyGraphChart.GetMappedNode(vertices[i]);
+                      // use a grayscale gradient
+                      var color = colorGradient[(int)Math.Round(averages[i] / max * colorCount)];
+                      vNode.Brush = new SolidBrush(color);
+                    }
+                  }
+                  */
+
+        //          if (openNew_CheckBox.Checked) {
+        //            MainFormManager.MainForm.ShowContent(traceGraph); // display the fragment graph on the screen
+        //          }
+        //        }
         genealogyGraphChart.ResumeRendering();
       } else {
@@ -203 +242 @@
 
     private void OnTreeNodeMiddleClicked(ISymbolicExpressionTreeNode node) {
-      var index = SelectedSubtree.IterateNodesPrefix().ToList().IndexOf(node);
-      if (index > 0) {
-        var s = ClonedSubtree.NodeAt(index);
-        s.Parent.RemoveSubtree(s.Parent.IndexOfSubtree(s));
-
-        var trees = Content.Vertices.Select(x => x.Data);
-        comparer.MatchVariableWeights = matchingModeButton.Checked;
-        comparer.MatchConstantValues = matchingModeButton.Checked;
-        var matchingTrees = trees.Where(x => x.Root.ContainsSubtree(ClonedSubtree, comparer));
-
-        var matchingVertices = matchingTrees.Select(x => Content.GetByContent(x));
-        treeChart_HighlightSubtree(node, Color.Black, Color.White);
-        graphChart_HighlightMatchingVertices(matchingVertices);
-      }
+      ISymbolicExpressionTreeNode clone;
+      if (!clonedMap.TryGetValue(node, out clone)) return;
+      if (clone.Parent == null) return;
+      var cloneParent = clone.Parent;
+      var cloneIndex = cloneParent.IndexOfSubtree(clone);
+      cloneParent.RemoveSubtree(cloneIndex);
+      cloneParent.InsertSubtree(cloneIndex, new AnySubtreeSymbol().CreateTreeNode());
+
+      var trees = Content.Vertices.Select(x => x.Data);
+      comparer.MatchVariableWeights = comparer.MatchConstantValues = matchingModeButton.Checked;
+      var matchingTrees = trees.Where(x => x.Root.ContainsSubtree(clonedSubtree, comparer));
+
+      var matchingVertices = matchingTrees.Select(x => Content.GetByContent(x));
+      treeChart_HighlightSubtree(node, Color.Black, Color.White);
+      graphChart_HighlightMatchingVertices(matchingVertices);
     }
     #endregion
@@ -223 +263 @@
       var visualNode = (VisualTreeNode<ISymbolicExpressionTreeNode>)sender;
       var subtree = visualNode.Content;
-      // highlight the selected subtree inside the displayed tree on the right hand side
-      treeChart_ClearColors();
-      treeChart_HighlightSubtree(subtree, Color.Black, Color.RoyalBlue);
 
       switch (args.Button) {
         case MouseButtons.Left: {
+            // highlight the selected subtree inside the displayed tree on the right hand side
+            treeChart_ClearColors();
+            treeChart_HighlightSubtree(subtree, Color.Black, Color.RoyalBlue);
+
             OnTreeNodeLeftClicked(subtree);
             break;
@@ -240 +281 @@
     #endregion
 
-    protected override void RegisterContentEvents() {
-      base.RegisterContentEvents();
-      if (SymbolicExpressionTreeChart != null)
-        SymbolicExpressionTreeChart.SymbolicExpressionTreeNodeClicked += treeChart_SymbolicExpressionTreeNodeClicked;
-    }
-
-    protected override void DeregisterContentEvents() {
-      if (SymbolicExpressionTreeChart != null)
-        SymbolicExpressionTreeChart.SymbolicExpressionTreeNodeClicked -= treeChart_SymbolicExpressionTreeNodeClicked;
-      base.DeregisterContentEvents();
-    }
+
 
     private void graphChart_HighlightMatchingVertices(IEnumerable<IGenealogyGraphNode> vertices) {
@@ -304 +335 @@
       }
 
+      var comp = new SymbolicExpressionTreeNodeEqualityComparer();
+
       if (lastTd != null && graphNode.InDegree > 1) {
-        var c = graphNode.Data;
-        var s = c.NodeAt(lastTd.SubtreeIndex);
-        var f = c.NodeAt(lastTd.FragmentIndex);
-        arc = graphNode.InArcs.FirstOrDefault(
-          a => {
-            var td = a.Data as TraceData;
-            if (td == null) return false;
-            var p = (ISymbolicExpressionTree)a.Source.Data;
-            var d = s.Difference(p.NodeAt(td.SubtreeIndex));
-            if (d == null) return true;
-            return f.IterateNodesPrefix().Any(x => x.IsIsomorphicWith(d));
-          });
+        var descendant = graphNode.Data;
+        // going left (in the direction of the traced subtree): 
+        // the ancestor shares the same structure with the descendant, with the exception of the fragment
+        // thus we identify the right ancestor by comparing the remaining nodes
+        //var descendantNodes = descendant.Root.IterateNodesPrefix(lastTd.FragmentIndex);
+        // calculate the relative fragment preorder index. it will always be > 0 due to the way the trace graph is constructed
+        var relativeFragmentIndex = lastTd.FragmentIndex - lastTd.SubtreeIndex;
+        var descendantNodes = descendant.NodeAt(lastTd.SubtreeIndex).IterateNodesPrefix(relativeFragmentIndex);
+
+        var filteredArcs = graphNode.InArcs.Where(a => {
+          var td = a.Data as TraceData;
+          if (td == null)
+            return false;
+          if (!(td.LastSubtreeIndex == lastTd.SubtreeIndex && td.LastFragmentIndex == lastTd.FragmentIndex))
+            return false;
+          return true;
+        }).ToList();
+
+        if (filteredArcs.Count == 0)
+          return;
+
+        if (filteredArcs.Count == 1) {
+          arc = filteredArcs[0];
+        } else {
+          arc = filteredArcs.FirstOrDefault(
+         a => {
+           var ancestor = (ISymbolicExpressionTree)a.Source.Data;
+           var td = a.Data as TraceData;
+           if (td == null)
+             return false;
+           var ancestorNodes = ancestor.NodeAt(td.SubtreeIndex).IterateNodesPrefix(skipIndex: relativeFragmentIndex);
+           return descendantNodes.SequenceEqual(ancestorNodes, comp);
+         });
+        }
+
+
       }
       if (arc == null) return;
@@ -338 +395 @@
 
       if (lastTd != null && graphNode.InDegree > 1) {
-        var c = graphNode.Data;
-        var f = c.NodeAt(lastTd.FragmentIndex);
-        arc = graphNode.InArcs.FirstOrDefault(
-          a => {
-            var td = a.Data as TraceData;
-            var p = (ISymbolicExpressionTree)a.Source.Data;
-            return td != null && p.NodeAt(td.SubtreeIndex).Difference(f) == null;
-          });
+        var descendant = graphNode.Data;
+        // going right (in the direction of the fragment): 
+        // 1) fragment was swapped by crossover
+        // 2) fragment was introduced by mutation 
+        // in some cases mutation changes things completely so we do not know which way to go
+
+        var f = descendant.NodeAt(lastTd.FragmentIndex);
+        arc = graphNode.InArcs.FirstOrDefault(a => {
+          var td = a.Data as TraceData;
+          if (td == null) return false;
+          var ancestor = (ISymbolicExpressionTree)a.Source.Data;
+          return f.Difference(ancestor.NodeAt(td.SubtreeIndex)) == null;
+        });
       }
       if (arc == null) return;
@@ -364 +426 @@
     return NodeAt(tree.Root, position);
   }
+
   internal static ISymbolicExpressionTreeNode NodeAt(this ISymbolicExpressionTreeNode root, int position) {
     return root.IterateNodesPrefix().ElementAt(position);
   }
+
   internal static bool IsIsomorphicWith(this ISymbolicExpressionTreeNode a, ISymbolicExpressionTreeNode b) {
     return a.Difference(b) == null;
   }
+
+  internal static IEnumerable<ISymbolicExpressionTreeNode> IterateNodesPrefix(this ISymbolicExpressionTreeNode node, int skipIndex) {
+    var e = node.IterateNodesPrefix().GetEnumerator();
+    var i = 0;
+    while (e.MoveNext()) {
+      var n = e.Current;
+      if (i == skipIndex) {
+        var len = n.GetLength();
+        while (--len >= 0 && e.MoveNext()) ;
+        n = e.Current;
+      }
+      if (n != null)
+        yield return n;
+      ++i;
+    }
+  }
+
+  internal static IEnumerable<ISymbolicExpressionTreeNode> IterateNodesPrefix(this ISymbolicExpressionTreeNode node, ISymbolicExpressionTreeNode skipNode) {
+    var e = node.IterateNodesPrefix().GetEnumerator();
+    while (e.MoveNext()) {
+      var n = e.Current;
+      if (n == skipNode) {
+        int len = n.GetLength();
+        while (--len >= 0 && e.MoveNext()) ;
+        n = e.Current;
+      }
+      if (n != null)
+        yield return n;
+    }
+  }
 }
 #endregion

branches/HeuristicLab.EvolutionTracking/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/TreeMatching/SymbolicExpressionTreeMatching.cs

@@ -42 +42 @@
       // we can have multiple matches of the same node
 
-      return root.IterateNodesBreadth().Where(n => n.GetLength() >= fragmentLength && Match(n, subtree, comp) == fragmentLength);
+      return root.IterateNodesBreadth().Where(n => n.GetLength() >= fragmentLength && Match(n, subtree, comp) >= fragmentLength);
     }
 
@@ -56 +56 @@
       // AnySubtree wildcards mach everything
       if (a is AnySubtree)
-        return b.GetLength();
+        return 1;
       if (b is AnySubtree)
-        return a.GetLength();
+        return 1;
 
       int m = a.SubtreeCount;