Changeset 13877

Timestamp:

06/06/16 19:39:43 (8 years ago)

Author:

bburlacu

Message:

#1772: Improve SymbolicDataAnalysisGenealogyGraphView by using a better coloring scheme for frequent subtrees. Fix bug when reaching the end of the genealogy. Minor refactorings.

Location:

branches/HeuristicLab.EvolutionTracking

Files:

• HeuristicLab.EvolutionTracking.Views/3.4/GenealogyGraphChart.cs (modified) (5 diffs)
• HeuristicLab.Problems.DataAnalysis.Symbolic.Views/3.4/Tracking/SymbolicDataAnalysisGenealogyGraphView.cs (modified) (12 diffs)
• HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Tracking/TraceCalculator.cs (modified) (2 diffs)
• HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/TreeMatching/QueryMatch.cs (modified) (1 diff)

branches/HeuristicLab.EvolutionTracking/HeuristicLab.EvolutionTracking.Views/3.4/GenealogyGraphChart.cs

@@ -1 +1 @@
 #region License Information
 /* HeuristicLab
- * Copyright (C) 2002-2014 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
+ * Copyright (C) 2002-2016 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
  *
  * This file is part of HeuristicLab.
@@ -67 +67 @@
           return;
         SelectedVisualNode = GetMappedNode(value);
-        UpdateSelectedVisualNode();
-      }
-    }
-
+        RedrawLineages();
+      }
+    }
     private void Clear() {
       nodeMap = new Dictionary<IGenealogyGraphNode, VisualGenealogyGraphNode>();
@@ -179 +178 @@
         if (primitive != null && primitive != SelectedVisualNode) {
           SelectedVisualNode = (VisualGenealogyGraphNode)primitive;
-          UpdateSelectedVisualNode(); // redraw ancestries, mark node etc.
+          RedrawLineages(); // redraw ancestries, mark node etc.
+
+          if (SelectedVisualNode != null)
+            OnGenealogyGraphNodeClicked(SelectedVisualNode, null); // emit clicked event
         }
       }
@@ -185 +187 @@
     }
 
-    private void UpdateSelectedVisualNode() {
+    private void RedrawLineages() {
       if (!LockGenealogy) {
         // new node has been selected, clean up
@@ -206 +208 @@
       // update
       ResumeRendering();
-
-      if (SelectedVisualNode != null)
-        OnGenealogyGraphNodeClicked(SelectedVisualNode, null); // emit clicked event
     }
     #endregion

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

@@ -1 +1 @@
 #region License Information
 /* HeuristicLab
- * Copyright (C) 2002-2015 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
+ * Copyright (C) 2002-2016 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
  *
  * This file is part of HeuristicLab.
@@ -26 +26 @@
 using System.Windows.Forms;
 using HeuristicLab.Common;
-using HeuristicLab.Core;
 using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
 using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.Views;
@@ -32 +31 @@
 using HeuristicLab.EvolutionTracking.Views;
 using HeuristicLab.MainForm;
+using HeuristicLab.Problems.DataAnalysis.Symbolic;
 
 namespace HeuristicLab.Problems.DataAnalysis.Symbolic.Views {
@@ -38 +38 @@
   public partial class SymbolicDataAnalysisGenealogyGraphView : SymbolicDataAnalysisGenealogyGraphViewDesignable {
     private readonly ISymbolicExpressionTreeNodeEqualityComparer comparer;
+
+    private TraceData lastTd;
 
     private ISymbolicExpressionTreeNode selectedSubtree;
@@ -79 +81 @@
       var graphNode = (IGenealogyGraphNode<ISymbolicExpressionTree>)visualNode.Data;
 
-      nodeQualityLabel.Text = String.Format("{0:0.000}", graphNode.Quality);
-      nodeRankLabel.Text = String.Format("{0:0.0}", graphNode.Rank);
-      nodeDegreeLabel.Text = String.Format("{0} / {1}", graphNode.InDegree, graphNode.OutDegree);
-      nodeWeightLabel.Text = String.Format("{0:0.00}", graphNode.Weight);
-
-      int colorCount = ColorGradient.Colors.Count - 1;
-      const int alpha = 100;
-      // calculate max only in the current generation
-      var nodes = graphNode.Data.IterateNodesPrefix().Skip(1).ToList();
-      var max = Content.GetByRank(graphNode.Rank).Max(x => ((IGenealogyGraphNode<ISymbolicExpressionTree>)x).Data.IterateNodesPrefix().Max(n => n.NodeWeight));
-      if (max.IsAlmost(0)) max = 1;
-      foreach (var n in nodes) {
-        var visualSymbolicExpressionTreeNode = SymbolicExpressionTreeChart.GetVisualSymbolicExpressionTreeNode(n);
-        visualSymbolicExpressionTreeNode.ToolTip += Environment.NewLine + String.Format("Weight: {0:0}", n.NodeWeight);
-        var i = (int)Math.Round(n.NodeWeight / max * colorCount);
-        var fillColor = Color.FromArgb(alpha, ColorGradient.Colors[i]);
-        treeChart_HighlightSubtree(n, null, fillColor);
-      }
-
-      if (!graphNode.InArcs.Any()) return;
+      lastTd = null;
+
+      nodeQualityLabel.Text = string.Format("{0:0.000}", graphNode.Quality);
+      nodeRankLabel.Text = string.Format("{0:0.0}", graphNode.Rank);
+      nodeDegreeLabel.Text = string.Format("{0} / {1}", graphNode.InDegree, graphNode.OutDegree);
+      nodeWeightLabel.Text = string.Format("{0:0.00}", graphNode.Weight);
+
+      // update the righthand side tree view when another genealogy graph node is selected
+      UpdateTreeChart(graphNode);
+
+      if (!graphNode.InArcs.Any()) return; // node has no ancestors, nothing to do
 
       if (openNew_CheckBox.Checked) {
@@ -111 +104 @@
         MainFormManager.MainForm.ShowContent(graph);
       }
-
+    }
+
+    private void UpdateTreeChart(IGenealogyGraphNode<ISymbolicExpressionTree> graphNode) {
+      SymbolicExpressionTreeChart.Tree = graphNode.Data;
+      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));
+      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 
+      foreach (var n in nodes.Skip(1)) {
+        var visualSymbolicExpressionTreeNode = SymbolicExpressionTreeChart.GetVisualSymbolicExpressionTreeNode(n);
+        visualSymbolicExpressionTreeNode.ToolTip += Environment.NewLine + string.Format("Weight: {0:0}", n.NodeWeight);
+        var i = (int)Math.Round(n.NodeWeight / max * 255);
+        var fillColor = Color.FromArgb(i, Color.Red);
+        treeChart_HighlightSubtree(n, null, fillColor);
+      }
+
+      if (!graphNode.InArcs.Any()) return;
       var data = graphNode.InArcs.Last().Data;
       var fragment = data as IFragment<ISymbolicExpressionTreeNode>;
-      var td = data as TraceData;
+      var td = lastTd;
 
       if (fragment != null) {
@@ -123 +133 @@
       } else if (td != null) {
         // highlight traced subtree and fragment
-        treeChart_HighlightSubtree(nodes[td.LastSubtreeIndex], Color.Orange);
-        treeChart_HighlightSubtree(nodes[td.LastFragmentIndex], Color.CornflowerBlue);
+        treeChart_HighlightSubtree(nodes[td.SubtreeIndex], Color.Orange);
+        treeChart_HighlightSubtree(nodes[td.FragmentIndex], Color.CornflowerBlue);
       }
     }
@@ -143 +153 @@
         var rankMaximums = new Dictionary<double, double>();
         // 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();
@@ -149 +162 @@
           rankMaximums.Add(r.Key, max);
           if (max.IsAlmost(0.0)) continue;
-          int colorCount = ColorGradient.GrayscaledColors.Count - 1;
           for (int i = 0; i < vertices.Count; ++i) {
-            var color = ColorGradient.GrayscaledColors[(int)Math.Round(averages[i] / max * colorCount)];
+            var color = colorGradient[(int)Math.Round(averages[i] / max * colorCount)];
             var vNode = genealogyGraphChart.GetMappedNode(vertices[i]);
             vNode.Brush = new SolidBrush(color);
@@ -159 +171 @@
         if (traceGraph.Vertices.Any()) {
           var ranks = traceGraph.Vertices.Select(x => Content.GetByContent(x.Data)).GroupBy(x => x.Rank);
-          int colorCount = ColorGradient.Colors.Count - 1;
           foreach (var g in ranks) {
             var vertices = g.ToList();
@@ -168 +179 @@
               var vNode = genealogyGraphChart.GetMappedNode(vertices[i]);
               // use a grayscale gradient
-              var color = ColorGradient.Colors[(int)Math.Round(averages[i] / max * colorCount)];
+              var color = colorGradient[(int)Math.Round(averages[i] / max * colorCount)];
               vNode.Brush = new SolidBrush(color);
             }
@@ -281 +292 @@
     private void navigateLeftButton_Click(object sender, EventArgs e) {
       var graphNode = (IGenealogyGraphNode<ISymbolicExpressionTree>)genealogyGraphChart.SelectedGraphNode;
-      var inArcs = (List<IArc>)((IVertex)graphNode).InArcs;
-      if (inArcs.Count > 0) {
-        genealogyGraphChart.SelectedGraphNode = (IGenealogyGraphNode<ISymbolicExpressionTree>)inArcs[0].Source;
-      }
+      if (!graphNode.InArcs.Any()) return;
+
+      // check if the arc contains fragment data
+      var arc = graphNode.InArcs.First();
+      var fragment = arc.Data as IFragment<ISymbolicExpressionTreeNode>;
+
+      if (fragment != null) {
+        genealogyGraphChart.SelectedGraphNode = arc.Source;
+        UpdateTreeChart((IGenealogyGraphNode<ISymbolicExpressionTree>)arc.Source);
+        return;
+      }
+
+      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));
+          });
+      }
+      if (arc == null) return;
+      lastTd = arc.Data as TraceData;
+      genealogyGraphChart.SelectedGraphNode = arc.Source;
+      UpdateTreeChart((IGenealogyGraphNode<ISymbolicExpressionTree>)arc.Source);
     }
 
     private void navigateRightButton_Click(object sender, EventArgs e) {
       var graphNode = (IGenealogyGraphNode<ISymbolicExpressionTree>)genealogyGraphChart.SelectedGraphNode;
-      var inArcs = (List<IArc>)((IVertex)graphNode).InArcs;
-      if (inArcs.Count > 0) {
-        if (inArcs.Count == 1) {
-          genealogyGraphChart.SelectedGraphNode = (IGenealogyGraphNode<ISymbolicExpressionTree>)inArcs[0].Source;
-          return;
-        }
-        IGenealogyGraphNode<ISymbolicExpressionTree> source = null;
-        var fragment = ((IArc<IDeepCloneable>)inArcs.Last()).Data as IFragment<ISymbolicExpressionTreeNode>;
-        var traceData = ((IArc<IDeepCloneable>)inArcs[0]).Data as TraceData;
-        if (fragment != null) {
-          source = (IGenealogyGraphNode<ISymbolicExpressionTree>)inArcs.Last().Source;
-        }
-        if (traceData != null) {
-          var f = graphNode.Data.NodeAt(traceData.LastFragmentIndex);
-          var selected = inArcs.Skip(1).First(x => {
-            var td = (TraceData)((IArc<IDeepCloneable>)x).Data;
-            var s = (IGenealogyGraphNode<ISymbolicExpressionTree>)x.Source;
-            return f.Difference(s.Data.NodeAt(td.SubtreeIndex)) == null;
+      if (!graphNode.InArcs.Any()) return;
+
+      // check if the arc contains fragment data
+      var arc = graphNode.InArcs.Last();
+      var fragment = arc.Data as IFragment<ISymbolicExpressionTreeNode>;
+      if (fragment != null) {
+        genealogyGraphChart.SelectedGraphNode = arc.Source;
+        UpdateTreeChart((IGenealogyGraphNode<ISymbolicExpressionTree>)arc.Source);
+        return;
+      }
+
+      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;
           });
-          source = (IGenealogyGraphNode<ISymbolicExpressionTree>)selected.Source;
-        }
-        if (source != null)
-          genealogyGraphChart.SelectedGraphNode = source;
-      }
-    }
-    #endregion
-  }
-
-  // bogus class needed in order to be able to "design" the view
-  public class SymbolicDataAnalysisGenealogyGraphViewDesignable : GenealogyGraphView<ISymbolicExpressionTree> { }
-
-  #region helper methods
-  internal static class Util {
-    internal static ISymbolicExpressionTreeNode NodeAt(this ISymbolicExpressionTree tree, int position) {
-      return NodeAt(tree.Root, position);
-    }
-    internal static ISymbolicExpressionTreeNode NodeAt(this ISymbolicExpressionTreeNode root, int position) {
-      return root.IterateNodesPrefix().ElementAt(position);
+      }
+      if (arc == null) return;
+      lastTd = arc.Data as TraceData;
+      genealogyGraphChart.SelectedGraphNode = arc.Source;
+      UpdateTreeChart((IGenealogyGraphNode<ISymbolicExpressionTree>)arc.Source);
     }
   }
   #endregion
 }
+
+// bogus class needed in order to be able to "design" the view
+public class SymbolicDataAnalysisGenealogyGraphViewDesignable : GenealogyGraphView<ISymbolicExpressionTree> { }
+
+#region helper methods
+internal static class Util {
+  internal static ISymbolicExpressionTreeNode NodeAt(this ISymbolicExpressionTree tree, int position) {
+    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;
+  }
+}
+#endregion

branches/HeuristicLab.EvolutionTracking/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Tracking/TraceCalculator.cs

@@ -1 +1 @@
 #region License Information
 /* HeuristicLab
- * Copyright (C) 2002-2015 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
+ * Copyright (C) 2002-2016 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
  *
  * This file is part of HeuristicLab.
@@ -233 +233 @@
     /// </summary>
     /// <param name="g">The genealogy graph node</param>
-    /// <param name="si">The subtree index</param>
-    /// <param name="fi">The fragment index</param>
     /// <returns></returns>
     private IGenealogyGraphNode<ISymbolicExpressionTree> AddTraceNode(IGenealogyGraphNode<ISymbolicExpressionTree> g) {

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

@@ -203 +203 @@
 
     public bool IsFirstSibling {
-      get { return Node.Parent != null && Node == Node.Parent.Subtrees.First(); }
+      get { return Parent != null && Node == Node.Parent.Subtrees.First(); }
     }
 
     public bool IsLastSibling {
-      get { return Node.Parent != null && Node == Node.Parent.Subtrees.Last(); }
+      get { return Parent != null && Node == Node.Parent.Subtrees.Last(); }
     }