Changeset 12225

Timestamp:

03/19/15 01:10:21 (10 years ago)

Author:

bburlacu

Message:

#1772: Work in progress for calculating sampling counts for subtrees in the population: updated TraceCalculator to aggregate tracing statistics, updated SymbolicDataAnalysisGenealogyGraphView, added SymbolicDataAnalysisSubtreeSampleCountAnalyzer.

Location:

branches/HeuristicLab.EvolutionTracking

Files:

• HeuristicLab.EvolutionTracking.Views/3.4/GenealogyGraphView.cs (modified) (1 diff)
• HeuristicLab.Problems.DataAnalysis.Symbolic.Views/3.4/HeuristicLab.Problems.DataAnalysis.Symbolic.Views-3.4.csproj (modified) (1 diff)
• HeuristicLab.Problems.DataAnalysis.Symbolic.Views/3.4/Tracking/SymbolicDataAnalysisGenealogyGraphView.cs (modified) (9 diffs)
• HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/HeuristicLab.Problems.DataAnalysis.Symbolic-3.4.csproj (modified) (1 diff)
• HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Tracking/Analyzers/SymbolicDataAnalysisSubtreeSampleCountAnalyzer.cs (added)
• HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Tracking/TraceCalculator.cs (modified) (7 diffs)

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

@@ -35 +35 @@
     protected override void OnContentChanged() {
       base.OnContentChanged();
-      if (Content != null) { genealogyGraphChart.GenealogyGraph = Content; }
+      if (Content != null && Content != genealogyGraphChart.GenealogyGraph) { genealogyGraphChart.GenealogyGraph = Content; }
     }
     #endregion

branches/HeuristicLab.EvolutionTracking/HeuristicLab.Problems.DataAnalysis.Symbolic.Views/3.4/HeuristicLab.Problems.DataAnalysis.Symbolic.Views-3.4.csproj

@@ -368 +368 @@
       <SubType>Designer</SubType>
     </EmbeddedResource>
-    <EmbeddedResource Include="Tracking\SymbolicDataAnalysisGenealogyGraphView.resx">
-      <DependentUpon>SymbolicDataAnalysisGenealogyGraphView.cs</DependentUpon>
-    </EmbeddedResource>
   </ItemGroup>
   <Import Project="$(MSBuildToolsPath)\Microsoft.CSharp.targets" />

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

@@ -41 +41 @@
     private ISymbolicExpressionTreeNode selectedSubtree;
     private ISymbolicExpressionTreeNode SelectedSubtree {
-      get {
-        return selectedSubtree;
-      }
+      get { return selectedSubtree; }
       set {
-        if (selectedSubtree == value) return;
+        if (value == null || selectedSubtree == value) 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; }
+
+    // we use the symbolic expression tree chart to call the drawing routines
+    // and highlight relevant tree parts
+    public SymbolicExpressionTreeChart SymbolicExpressionTreeChart {
+      get {
+        var view = (GraphicalSymbolicExpressionTreeView)base.viewHost.ActiveView;
+        return view == null ? null : view.SymbolicExpressionTreeChart;
+      }
+    }
 
     public SymbolicDataAnalysisGenealogyGraphView() {
@@ -61 +69 @@
     protected override void OnContentChanged() {
       base.OnContentChanged();
-      if (Content != null) { genealogyGraphChart.GenealogyGraph = Content; }
-    }
-    #endregion
-
-    public SymbolicExpressionTreeChart SymbolicExpressionTreeChart {
-      get {
-        var view = (GraphicalSymbolicExpressionTreeView)base.viewHost.ActiveView;
-        return view == null ? null : view.SymbolicExpressionTreeChart;
-      }
-    }
-
-    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();
+      if (Content != null && Content != genealogyGraphChart.GenealogyGraph) {
+        genealogyGraphChart.GenealogyGraph = Content;
+      }
     }
 
@@ -110 +100 @@
         var fragment = data as IFragment<ISymbolicExpressionTreeNode>;
         var td = data as TraceData;
+        //        double max = Content.Vertices.SelectMany(x => x.Data.IterateNodesPrefix()).Max(x => x.NodeWeight);
+
         if (fragment != null) {
-          treeChart_HighlightSubtree(graphNode.Data.NodeAt(fragment.Index1));
+          //          treeChart_HighlightSubtree(graphNode.Data.NodeAt(fragment.Index1));
+          var nodes = graphNode.Data.IterateNodesPrefix().ToList();
+          int c = ColorGradient.Colors.Count - 1;
+          foreach (var n in nodes.Skip(1)) { // skip program root symbol 
+            //            var i = (int)Math.Round(n.NodeWeight / max * c);
+            //            const int alpha = 50;
+            //            var fillColor = Color.FromArgb(alpha, ColorGradient.Colors[i]);
+
+            //            treeChart_HighlightSubtree(n, null, fillColor);
+          }
         } else if (td != null) {
+
           var nodes = graphNode.Data.IterateNodesPrefix().ToList();
+          int c = ColorGradient.Colors.Count - 1;
+          foreach (var n in nodes.Skip(1)) { // skip program root symbol 
+            //            var i = (int)Math.Round(n.NodeWeight / max * c);
+            //            const int alpha = 50;
+            //            var fillColor = Color.FromArgb(alpha, ColorGradient.Colors[i]);
+
+            //            treeChart_HighlightSubtree(n, null, fillColor);
+          }
+
           treeChart_HighlightSubtree(nodes[td.LastSubtreeIndex], Color.Orange);
-          treeChart_HighlightSubtree(nodes[td.LastFragmentIndex], null, Color.PowderBlue);
+          treeChart_HighlightSubtree(nodes[td.LastFragmentIndex], Color.CornflowerBlue);
         }
       }
@@ -125 +136 @@
       // highlight the selected subtree inside the displayed tree on the right hand side
       treeChart_ClearColors();
-      treeChart_HighlightSubtree(subtree);
+      treeChart_HighlightSubtree(subtree, Color.Black, Color.RoyalBlue);
 
       bool trace = genealogyGraphChart.TraceFragments; // check whether we are in 'trace' or 'match' mode
@@ -136 +147 @@
             var graphNode = (IGenealogyGraphNode<ISymbolicExpressionTree>)genealogyGraphChart.SelectedGraphNode;
             var subtreeIndex = graphNode.Data.IterateNodesPrefix().ToList().IndexOf(subtree);
-            var traceGraph = TraceCalculator.TraceSubtree(graphNode, subtreeIndex);
+            var traceGraph = TraceCalculator.TraceSubtree(graphNode, subtreeIndex, updateVertexWeights: true, updateSubtreeWeights: true, cacheTraceNodes: true);
             if (traceGraph.Vertices.Any()) {
               genealogyGraphChart.UpdateEnabled = false;
-              genealogyGraphChart.ClearArcs();
-              var genealogyNodes = traceGraph.Vertices.Select(v => Content.GetByContent(v.Data));
-              genealogyGraphChart.HighlightNodes(genealogyNodes, Color.Black, false);
+              genealogyGraphChart.ClearPrimitives();
+              var traceVertices = traceGraph.Vertices.ToList();
+              var genealogyNodes = traceVertices.Select(v => Content.GetByContent(v.Data)).ToList();
+              // color graph vertices according to their weight
+              double max = traceGraph.Vertices.Max(x => x.Data.IterateNodesPrefix().Max(n => x.Weight));
+              for (int i = 0; i < genealogyNodes.Count; ++i) {
+                var g = genealogyNodes[i];
+                g.Weight = traceVertices[i].Weight;
+                var v = genealogyGraphChart.GetMappedNode(g);
+                if (v != null) {
+                  v.Brush = new SolidBrush(ColorGradient.Colors[(int)Math.Round(g.Weight * (ColorGradient.Colors.Count - 1) / max)]);
+                }
+              }
+
               genealogyGraphChart.UpdateEnabled = true;
               genealogyGraphChart.EnforceUpdate();
+
               if (openNew_CheckBox.Checked)
                 MainFormManager.MainForm.ShowContent(traceGraph); // display the fragment graph on the screen
-
-              var max = traceGraph.Vertices.Max(x => x.Weight);
-
-              genealogyGraphChart.UpdateEnabled = false;
-              foreach (var traceNode in traceGraph.Vertices) {
-                var g = Content.GetByContent(traceNode.Data);
-                g.Weight = traceNode.Weight;
-                var v = genealogyGraphChart.GetMappedNode(g);
-                if (v != null) {
-                  int i = (int)Math.Round(g.Weight * (ColorGradient.Colors.Count - 1) / max);
-
-                  v.Brush = new SolidBrush(ColorGradient.Colors[i]);
-                }
-              }
-              genealogyGraphChart.UpdateEnabled = true;
-              genealogyGraphChart.EnforceUpdate();
             }
           } else {
@@ -188 +195 @@
           break;
       }
+    }
+    #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();
     }
 
@@ -210 +230 @@
 
     private void treeChart_HighlightSubtree(ISymbolicExpressionTreeNode subtree, Color? lineColor = null, Color? fillColor = null) {
-      var lc = lineColor ?? Color.RoyalBlue;
-      var fc = fillColor ?? Color.White;
+      if (lineColor == null && fillColor == null)
+        return;
+
       foreach (var s in subtree.IterateNodesPrefix()) {
         var visualNode = SymbolicExpressionTreeChart.GetVisualSymbolicExpressionTreeNode(s);
-        visualNode.LineColor = lc;
-        visualNode.FillColor = fc;
-
-        foreach (var c in s.Subtrees) {
-          var visualArc = SymbolicExpressionTreeChart.GetVisualSymbolicExpressionTreeNodeConnection(s, c);
-          visualArc.LineColor = lc;
+        if (lineColor != null) {
+          visualNode.LineColor = (Color)lineColor;
+          foreach (var c in s.Subtrees) {
+            var visualArc = SymbolicExpressionTreeChart.GetVisualSymbolicExpressionTreeNodeConnection(s, c);
+            visualArc.LineColor = (Color)lineColor;
+          }
         }
+        if (fillColor != null)
+          visualNode.FillColor = (Color)fillColor;
       }
       SymbolicExpressionTreeChart.RepaintNodes();
     }
 
+    #region navigate the genealogy / trace graph
     private void navigateLeftButton_Click(object sender, EventArgs e) {
       var graphNode = (IGenealogyGraphNode<ISymbolicExpressionTree>)genealogyGraphChart.SelectedGraphNode;
@@ -267 +291 @@
       }
     }
+    #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) {
@@ -278 +306 @@
     }
   }
+  #endregion
 }

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

@@ -309 +309 @@
     <Compile Include="Symbols\VariableTreeNode.cs" />
     <Compile Include="Tracking\Analyzers\SymbolicDataAnalysisFragmentLengthAnalyzer.cs" />
+    <Compile Include="Tracking\Analyzers\SymbolicDataAnalysisSubtreeSampleCountAnalyzer.cs" />
     <Compile Include="Tracking\Analyzers\SymbolicDataAnalysisTraceOverlapAnalyzer.cs" />
     <Compile Include="Tracking\SymbolicDataAnalysisExpressionAfterCrossoverOperator.cs" />

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

@@ -39 +39 @@
     public IGenealogyGraph<ISymbolicExpressionTree> TraceGraph { get; private set; }
 
+    public bool UpdateVertexWeights { get; set; }
+    public bool UpdateSubtreeWeights { get; set; }
+    public bool CacheTraceNodes { get; set; }
+
     public TraceCalculator() {
+      ResetState();
+    }
+
+    protected TraceCalculator(TraceCalculator original, Cloner cloner)
+      : base(original, cloner) {
+    }
+
+    public override IDeepCloneable Clone(Cloner cloner) {
+      return new TraceCalculator(this, cloner);
+    }
+
+    public void ResetState() {
       TraceGraph = new GenealogyGraph<ISymbolicExpressionTree>();
       traceMap = new Dictionary<IGenealogyGraphNode<ISymbolicExpressionTree>, TraceData>();
@@ -46 +62 @@
     }
 
-    protected TraceCalculator(TraceCalculator original, Cloner cloner)
-      : base(original, cloner) {
-    }
-
-    public override IDeepCloneable Clone(Cloner cloner) {
-      return new TraceCalculator(this, cloner);
-    }
-
-    public static IGenealogyGraph<ISymbolicExpressionTree> TraceSubtree(
-      IGenealogyGraphNode<ISymbolicExpressionTree> node, int subtreeIndex) {
-      var tc = new TraceCalculator();
+    public static IGenealogyGraph<ISymbolicExpressionTree> TraceSubtree(IGenealogyGraphNode<ISymbolicExpressionTree> node, int subtreeIndex, bool updateVertexWeights = false, bool updateSubtreeWeights = false, bool cacheTraceNodes = true) {
+      var tc = new TraceCalculator {
+        UpdateVertexWeights = updateSubtreeWeights,
+        UpdateSubtreeWeights = updateSubtreeWeights,
+        CacheTraceNodes = cacheTraceNodes
+      };
       tc.Trace(node, subtreeIndex);
       return tc.TraceGraph;
     }
 
-    public IGenealogyGraph<ISymbolicExpressionTree> Trace(IGenealogyGraphNode<ISymbolicExpressionTree> node, int subtreeIndex) {
-      TraceGraph = new GenealogyGraph<ISymbolicExpressionTree>();
-      traceMap = new Dictionary<IGenealogyGraphNode<ISymbolicExpressionTree>, TraceData>();
-      nodeListCache = new Dictionary<ISymbolicExpressionTree, List<ISymbolicExpressionTreeNode>>();
-      traceCache = new HashSet<Tuple<IGenealogyGraphNode<ISymbolicExpressionTree>, IGenealogyGraphNode<ISymbolicExpressionTree>, int>>();
+    public IGenealogyGraph<ISymbolicExpressionTree> Trace(IGenealogyGraphNode<ISymbolicExpressionTree> node, int subtreeIndex, bool resetState = true) {
+      if (resetState) ResetState();
       TraceRecursive(node, subtreeIndex);
       return TraceGraph;
@@ -90 +98 @@
     /// <param name="subtreeIndex">The index of the traced subtree</param>
     /// <param name="last">The last added node in the trace graph</param>
-    private void TraceRecursive(IGenealogyGraphNode<ISymbolicExpressionTree> node, int subtreeIndex,
-      IGenealogyGraphNode<ISymbolicExpressionTree> last = null) {
+    private void TraceRecursive(IGenealogyGraphNode<ISymbolicExpressionTree> node, int subtreeIndex, IGenealogyGraphNode<ISymbolicExpressionTree> last = null) {
       var g = node;
       int si = subtreeIndex; // subtree index
       int fi = 0; // fragment index
       while (((List<IArc>)((IVertex)g).InArcs).Count > 0) {
-        //      while (g.Parents.Any()) {
         Debug.Assert(si < g.Data.Length);
         var inArcs = (List<IArc>)((IVertex)g).InArcs;
@@ -138 +144 @@
               var n = AddTraceNode(g, si, fi); // current node becomes "last" as we restart tracing from the parent
               var t0 = new Tuple<IGenealogyGraphNode<ISymbolicExpressionTree>, IGenealogyGraphNode<ISymbolicExpressionTree>, int>(parent0, n, si);
-              if (!traceCache.Contains(t0)) {
+              if (!(CacheTraceNodes && traceCache.Contains(t0))) {
                 TraceRecursive(parent0, si, n);
                 traceCache.Add(t0);
-              } else {
+              }
+              if (UpdateVertexWeights)
                 n.Weight++;
-              }
               var t1 = new Tuple<IGenealogyGraphNode<ISymbolicExpressionTree>, IGenealogyGraphNode<ISymbolicExpressionTree>, int>(parent1, n, fragment.Index2);
-              if (!traceCache.Contains(t1)) {
+              if (!(CacheTraceNodes && traceCache.Contains(t1))) {
                 TraceRecursive(parent1, fragment.Index2, n);
                 traceCache.Add(t1);
-              } else {
+              }
+              // gather statistics about sampled individuals and sampled subtrees
+              if (UpdateVertexWeights)
                 n.Weight++;
+              if (UpdateSubtreeWeights) {
+                var arcs = (List<IArc>)((IVertex)n).InArcs; // at this moment n will have been added as a child to the next trace node
+                for (int i = 0; i < arcs.Count; ++i) {
+                  var td = (TraceData)((IArc<IDeepCloneable>)arcs[i]).Data;
+                  var p = (IGenealogyGraphNode<ISymbolicExpressionTree>)arcs[i].Source;
+                  // TODO: the first part of the check below represents a necessary but not sufficient condition
+                  // TODO: therefore, a Difference check is also performed, it would be nice to make this code more ellegant
+                  if (td.LastFragmentIndex == td.SubtreeIndex && fragment.Root.Difference(NodeAt(p.Data, td.SubtreeIndex)) == null) {
+                    arcs[i].Weight++;
+                    break;
+                  }
+                }
               }
               break;
@@ -171 +191 @@
             int i = si < fi ? si : fi;
             var t = new Tuple<IGenealogyGraphNode<ISymbolicExpressionTree>, IGenealogyGraphNode<ISymbolicExpressionTree>, int>(parent0, n, i);
-            if (!traceCache.Contains(t)) {
+            if (!(CacheTraceNodes && traceCache.Contains(t))) {
               TraceRecursive(parent0, i, n);
               traceCache.Add(t);
-            } else {
+            }
+            if (UpdateVertexWeights)
               n.Weight++;
-            }
             break;
           } else {
@@ -204 +224 @@
     /// <param name="fi">The fragment index</param>
     /// <returns></returns>
-    private IGenealogyGraphNode<ISymbolicExpressionTree> AddTraceNode(IGenealogyGraphNode<ISymbolicExpressionTree> g,
-      int si, int fi) {
+    private IGenealogyGraphNode<ISymbolicExpressionTree> AddTraceNode(IGenealogyGraphNode<ISymbolicExpressionTree> g, int si, int fi) {
       var n = TraceGraph.GetByContent(g.Data);
       if (n == null) {
@@ -239 +258 @@
       IGenealogyGraphNode<ISymbolicExpressionTree> last, int si, int fi) {
       var lastTraceData = traceMap[last];
-      int lastSi = lastTraceData.SubtreeIndex;
-      // last subtree index (index of the traced subtree in the previous trace node)
-      int lastFi = lastTraceData.FragmentIndex;
-      // last fragment index (index of the fragment in the previous trace node)
+      int lastSi = lastTraceData.SubtreeIndex; // last subtree index (index of the traced subtree in the previous trace node)
+      int lastFi = lastTraceData.FragmentIndex; // last fragment index (index of the fragment in the previous trace node)
       var td = new TraceData(si, fi, lastSi, lastFi); // trace data
       // using the inArcs seems to be slightly more efficient than using the outArcs