source: branches/HeuristicLab.EvolutionTracking/HeuristicLab.Problems.DataAnalysis.Symbolic.Views/3.4/Tracking/SymbolicDataAnalysisGenealogyGraphView.cs @ 15561

Last change on this file since 15561 was 15561, checked in by bburlacu, 5 years ago

#1772: Refactor SymbolicDataAnalysisGenealogyGraphView

File size: 20.1 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2016 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
4 *
5 * This file is part of HeuristicLab.
6 *
7 * HeuristicLab is free software: you can redistribute it and/or modify
8 * it under the terms of the GNU General Public License as published by
9 * the Free Software Foundation, either version 3 of the License, or
10 * (at your option) any later version.
11 *
12 * HeuristicLab is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15 * GNU General Public License for more details.
16 *
17 * You should have received a copy of the GNU General Public License
18 * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
19 */
20#endregion
21
22using System;
23using System.Collections.Generic;
24using System.Drawing;
25using System.Linq;
26using System.Windows.Forms;
27using HeuristicLab.Common;
28using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
29using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.Views;
30using HeuristicLab.EvolutionTracking;
31using HeuristicLab.EvolutionTracking.Views;
32using HeuristicLab.MainForm;
33using HeuristicLab.Problems.DataAnalysis.Symbolic;
34
35namespace HeuristicLab.Problems.DataAnalysis.Symbolic.Views {
36  [View("SymbolicDataAnalysisGenealogyGraphView")]
37  [Content(typeof(IGenealogyGraph<ISymbolicExpressionTree>), IsDefaultView = true)]
38  public partial class SymbolicDataAnalysisGenealogyGraphView : SymbolicDataAnalysisGenealogyGraphViewDesignable {
39    private readonly ISymbolicExpressionTreeNodeEqualityComparer comparer;
40
41    private TraceData lastTd;
42
43    private ISymbolicExpressionTreeNode clonedSubtree;
44    private Dictionary<ISymbolicExpressionTreeNode, ISymbolicExpressionTreeNode> clonedMap;
45
46    private ISymbolicExpressionTreeNode selectedSubtree;
47    private ISymbolicExpressionTreeNode SelectedSubtree {
48      get { return selectedSubtree; }
49      set {
50        if (value == null) return;
51        selectedSubtree = value;
52        // the code below enables a "shadow" copy of the selected subtree which is used for matching against the graph
53        clonedSubtree = (ISymbolicExpressionTreeNode)selectedSubtree.Clone();
54        clonedMap = new Dictionary<ISymbolicExpressionTreeNode, ISymbolicExpressionTreeNode>();
55        var e1 = selectedSubtree.IterateNodesPrefix().GetEnumerator();
56        var e2 = clonedSubtree.IterateNodesPrefix().GetEnumerator();
57
58        while (e1.MoveNext() && e2.MoveNext()) {
59          clonedMap.Add(e1.Current, e2.Current);
60        }
61      }
62    }
63
64    // we use the symbolic expression tree chart to call the drawing routines
65    // and highlight relevant tree parts
66    public SymbolicExpressionTreeChart SymbolicExpressionTreeChart {
67      get {
68        var view = (GraphicalSymbolicExpressionTreeView)base.viewHost.ActiveView;
69        return view == null ? null : view.SymbolicExpressionTreeChart;
70      }
71    }
72
73    public SymbolicDataAnalysisGenealogyGraphView() {
74      InitializeComponent();
75      comparer = new SymbolicExpressionTreeNodeEqualityComparer();
76      viewHost.ViewType = typeof(GraphicalSymbolicExpressionTreeView);
77    }
78    #region event handlers
79    protected override void OnContentChanged() {
80      base.OnContentChanged();
81      if (Content != null && Content != genealogyGraphChart.GenealogyGraph) {
82        genealogyGraphChart.GenealogyGraph = Content;
83      }
84    }
85
86    protected override void RegisterContentEvents() {
87      base.RegisterContentEvents();
88      if (SymbolicExpressionTreeChart != null)
89        SymbolicExpressionTreeChart.SymbolicExpressionTreeNodeClicked += treeChart_SymbolicExpressionTreeNodeClicked;
90    }
91
92    protected override void DeregisterContentEvents() {
93      if (SymbolicExpressionTreeChart != null)
94        SymbolicExpressionTreeChart.SymbolicExpressionTreeNodeClicked -= treeChart_SymbolicExpressionTreeNodeClicked;
95      base.DeregisterContentEvents();
96    }
97
98    public override void graphChart_GenealogyGraphNodeClicked(object sender, MouseEventArgs args) {
99      base.graphChart_GenealogyGraphNodeClicked(sender, args);
100      var visualNode = (VisualGenealogyGraphNode)sender;
101      var graphNode = (IGenealogyGraphNode<ISymbolicExpressionTree>)visualNode.Data;
102
103      lastTd = null;
104
105      selectedNodeStatusStrip.Text = string.Format("Quality: {0:0.00}, Rank: {1:0.0}, Degree: {2}/{3}, Weight: {4:0.00}",
106        graphNode.Quality, graphNode.Rank, graphNode.InDegree, graphNode.OutDegree, graphNode.Weight);
107
108      // update the righthand side tree view when another genealogy graph node is selected
109      UpdateTreeChart(graphNode);
110
111      if (!graphNode.InArcs.Any()) return; // node has no ancestors, nothing to do
112
113      if (createNewViewCheckBox.Checked) {
114        // get the ancestors into a new view
115        var cloner = new Cloner();
116        // clone arcs and vertices and use them to create a new graph
117        // that will include just the individual and its ancestors
118        var graph = new GenealogyGraph<ISymbolicExpressionTree>();
119        var ancestors = new[] { graphNode }.Concat(graphNode.Ancestors).ToList();
120        graph.AddVertices(ancestors.Select(cloner.Clone));
121        graph.AddArcs(ancestors.SelectMany(x => x.InArcs).Select(cloner.Clone));
122        MainFormManager.MainForm.ShowContent(graph);
123      }
124    }
125
126    private void UpdateTreeChart(IGenealogyGraphNode<ISymbolicExpressionTree> graphNode) {
127      SymbolicExpressionTreeChart.Tree = graphNode.Data;
128      var nodes = graphNode.Data.IterateNodesPrefix().ToList();
129      // calculate max only in the current generation
130      var max = Content.Vertices.Max(x => x.Data.IterateNodesPrefix().Max(n => n.NodeWeight));
131      if (max.IsAlmost(0)) max = 1;
132      // we skip the program root node because it's useless for display and it just takes space in the chart
133      foreach (var n in nodes.Skip(1)) {
134        var visualSymbolicExpressionTreeNode = SymbolicExpressionTreeChart.GetVisualSymbolicExpressionTreeNode(n);
135        visualSymbolicExpressionTreeNode.ToolTip += Environment.NewLine + string.Format("Weight: {0:0}", n.NodeWeight);
136        var i = (int)Math.Round(n.NodeWeight / max * 255);
137        var fillColor = Color.FromArgb(i, Color.Red);
138        treeChart_HighlightSubtree(n, null, fillColor);
139      }
140
141      if (!graphNode.InArcs.Any())
142        return;
143      var data = graphNode.InArcs.Last().Data;
144      var fragment = data as IFragment<ISymbolicExpressionTreeNode>;
145      var td = lastTd;
146
147      if (fragment != null) {
148        // highlight the fragment with a blue line color
149        foreach (var n in graphNode.Data.NodeAt(fragment.Index1).IterateNodesPrefix()) {
150          treeChart_HighlightSubtree(n, Color.CornflowerBlue);
151        }
152      } else if (td != null) {
153        // highlight traced subtree and fragment
154        if (td.SubtreeIndex == td.FragmentIndex) {
155          treeChart_HighlightSubtree(nodes[td.SubtreeIndex], Color.Purple);
156        } else if (td.SubtreeIndex < td.FragmentIndex) {
157          treeChart_HighlightSubtree(nodes[td.SubtreeIndex], Color.Orange);
158          treeChart_HighlightSubtree(nodes[td.FragmentIndex], Color.CornflowerBlue);
159        } else {
160          treeChart_HighlightSubtree(nodes[td.FragmentIndex], Color.CornflowerBlue);
161          treeChart_HighlightSubtree(nodes[td.SubtreeIndex], Color.Orange);
162        }
163      }
164    }
165
166    #region specific symbolic expression tree node click actions
167    private void OnTreeNodeLeftClicked(ISymbolicExpressionTreeNode node) {
168      SelectedSubtree = node;
169      bool trace = traceCheckBox.Checked;
170
171      // check whether we are in 'trace' or 'match' mode
172      if (trace) {
173        // perform fragment tracing
174        var graphNode = (IGenealogyGraphNode<ISymbolicExpressionTree>)genealogyGraphChart.SelectedGraphNode;
175        var subtreeIndex = graphNode.Data.IterateNodesPrefix().ToList().IndexOf(node);
176        var traceGraph = TraceCalculator.TraceSubtree(graphNode, subtreeIndex, updateVertexWeights: false, updateSubtreeWeights: false, cacheTraceNodes: true);
177
178        if (!traceGraph.Vertices.Any())
179          return;
180
181        genealogyGraphChart.SuspendRendering();
182        genealogyGraphChart.ClearPrimitives(); // clear everything
183        bool newView = createNewViewCheckBox.Checked;
184        if (newView) {
185          MainFormManager.MainForm.ShowContent(traceGraph);
186        } else {
187          genealogyGraphChart.SuspendRendering();
188          genealogyGraphChart.HighlightNodes(traceGraph.Vertices);
189          genealogyGraphChart.ResumeRendering();
190        }
191      } else {
192        // perform matching like it was done before
193        // currently there is no possibility to specify the subtree matching criteria
194        var trees = Content.Vertices.Select(x => x.Data);
195        //comparer.MatchVariableWeights = matchingModeButton.Checked;
196        //comparer.MatchConstantValues = matchingModeButton.Checked;
197        var matchingTrees = trees.Where(x => x.Root.ContainsSubtree(node, comparer));
198
199        var matchingVertices = matchingTrees.Select(x => Content.GetByContent(x));
200        graphChart_HighlightMatchingVertices(matchingVertices);
201      }
202    }
203
204    private void OnTreeNodeMiddleClicked(ISymbolicExpressionTreeNode node) {
205      ISymbolicExpressionTreeNode clone;
206      if (!clonedMap.TryGetValue(node, out clone)) return;
207      if (clone.Parent == null) return;
208      var cloneParent = clone.Parent;
209      var cloneIndex = cloneParent.IndexOfSubtree(clone);
210      cloneParent.RemoveSubtree(cloneIndex);
211      cloneParent.InsertSubtree(cloneIndex, new AnySubtreeSymbol().CreateTreeNode());
212
213      var trees = Content.Vertices.Select(x => x.Data);
214      //comparer.MatchVariableWeights = comparer.MatchConstantValues = matchingModeButton.Checked;
215      var matchingTrees = trees.Where(x => x.Root.ContainsSubtree(clonedSubtree, comparer));
216
217      var matchingVertices = matchingTrees.Select(x => Content.GetByContent(x));
218      treeChart_HighlightSubtree(node, Color.Black, Color.White);
219      graphChart_HighlightMatchingVertices(matchingVertices);
220    }
221    #endregion
222
223    public void treeChart_SymbolicExpressionTreeNodeClicked(object sender, MouseEventArgs args) {
224      var visualNode = (VisualTreeNode<ISymbolicExpressionTreeNode>)sender;
225      var subtree = visualNode.Content;
226
227      switch (args.Button) {
228        case MouseButtons.Left: {
229            // highlight the selected subtree inside the displayed tree on the right hand side
230            treeChart_ClearColors();
231            treeChart_HighlightSubtree(subtree, Color.Black, Color.RoyalBlue);
232
233            OnTreeNodeLeftClicked(subtree);
234            break;
235          }
236        case MouseButtons.Middle: {
237            OnTreeNodeMiddleClicked(subtree);
238            break;
239          }
240      }
241    }
242    #endregion
243
244    private void graphChart_HighlightMatchingVertices(IEnumerable<IGenealogyGraphNode> vertices) {
245      genealogyGraphChart.SuspendRendering();
246      genealogyGraphChart.ClearPrimitives();
247      genealogyGraphChart.HighlightNodes(vertices);
248      genealogyGraphChart.ResumeRendering();
249    }
250
251    #region treechart methods
252    private void treeChart_ClearColors() {
253      foreach (var node in SymbolicExpressionTreeChart.Tree.IterateNodesPrefix()) {
254        var visualNode = SymbolicExpressionTreeChart.GetVisualSymbolicExpressionTreeNode(node);
255        if (visualNode != null) {
256          visualNode.LineColor = Color.Black;
257          visualNode.FillColor = Color.Transparent;
258        }
259      }
260      SymbolicExpressionTreeChart.RepaintNodes();
261    }
262
263    private void treeChart_HighlightSubtree(ISymbolicExpressionTreeNode subtree, Color? lineColor = null, Color? fillColor = null) {
264      if (lineColor == null && fillColor == null)
265        return;
266
267      foreach (var s in subtree.IterateNodesPrefix()) {
268        var visualNode = SymbolicExpressionTreeChart.GetVisualSymbolicExpressionTreeNode(s);
269        if (lineColor != null) {
270          visualNode.LineColor = (Color)lineColor;
271          foreach (var c in s.Subtrees) {
272            var visualArc = SymbolicExpressionTreeChart.GetVisualSymbolicExpressionTreeNodeConnection(s, c);
273            visualArc.LineColor = (Color)lineColor;
274          }
275        }
276        if (fillColor != null)
277          visualNode.FillColor = (Color)fillColor;
278      }
279      SymbolicExpressionTreeChart.RepaintNodes();
280    }
281    #endregion
282
283    #region navigate the genealogy / trace graph
284    private void navigateLeftButton_Click(object sender, EventArgs e) {
285      var graphNode = (IGenealogyGraphNode<ISymbolicExpressionTree>)genealogyGraphChart.SelectedGraphNode;
286      if (!graphNode.InArcs.Any()) return;
287
288      // check if the arc contains fragment data
289      var arc = graphNode.InArcs.First();
290      var fragment = arc.Data as IFragment<ISymbolicExpressionTreeNode>;
291
292      if (fragment != null) {
293        genealogyGraphChart.SelectedGraphNode = arc.Source;
294        UpdateTreeChart((IGenealogyGraphNode<ISymbolicExpressionTree>)arc.Source);
295        return;
296      }
297
298      var comp = new SymbolicExpressionTreeNodeEqualityComparer();
299
300      if (lastTd != null && graphNode.InDegree > 1) {
301        var descendant = graphNode.Data;
302        // going left (in the direction of the traced subtree):
303        // the ancestor shares the same structure with the descendant, with the exception of the fragment
304        // thus we identify the right ancestor by comparing the remaining nodes
305        //var descendantNodes = descendant.Root.IterateNodesPrefix(lastTd.FragmentIndex);
306        // calculate the relative fragment preorder index. it will always be > 0 due to the way the trace graph is constructed
307        var relativeFragmentIndex = lastTd.FragmentIndex - lastTd.SubtreeIndex;
308        var descendantNodes = descendant.NodeAt(lastTd.SubtreeIndex).IterateNodesPrefix(relativeFragmentIndex);
309
310        var filteredArcs = graphNode.InArcs.Where(a => {
311          var td = a.Data as TraceData;
312          if (td == null)
313            return false;
314          if (!(td.LastSubtreeIndex == lastTd.SubtreeIndex && td.LastFragmentIndex == lastTd.FragmentIndex))
315            return false;
316          return true;
317        }).ToList();
318
319        if (filteredArcs.Count == 0)
320          return;
321
322        if (filteredArcs.Count == 1) {
323          arc = filteredArcs[0];
324        } else {
325          arc = filteredArcs.FirstOrDefault(
326         a => {
327           var ancestor = (ISymbolicExpressionTree)a.Source.Data;
328           var td = a.Data as TraceData;
329           if (td == null)
330             return false;
331           var ancestorNodes = ancestor.NodeAt(td.SubtreeIndex).IterateNodesPrefix(skipIndex: relativeFragmentIndex);
332           return descendantNodes.SequenceEqual(ancestorNodes, comp);
333         });
334        }
335      }
336      if (arc == null) return;
337      lastTd = arc.Data as TraceData;
338      genealogyGraphChart.SelectedGraphNode = arc.Source;
339      graphNode = (IGenealogyGraphNode<ISymbolicExpressionTree>)arc.Source;
340      UpdateTreeChart(graphNode);
341
342      var inDegreeDistinct = graphNode.InArcs.Select(x => x.Source).Distinct().Count();
343      var outDegreeDistinct = graphNode.OutArcs.Select(x => x.Target).Distinct().Count();
344
345      selectedNodeStatusStrip.Text = string.Format("Quality: {0:0.00}, Rank: {1:0.0}, Degree: {2}/{3}, Weight: {4:0.00}",
346        graphNode.Quality, graphNode.Rank, inDegreeDistinct, outDegreeDistinct, graphNode.Weight);
347    }
348
349    private void navigateRightButton_Click(object sender, EventArgs e) {
350      var graphNode = (IGenealogyGraphNode<ISymbolicExpressionTree>)genealogyGraphChart.SelectedGraphNode;
351      if (!graphNode.InArcs.Any()) return;
352
353      // check if the arc contains fragment data
354      var arc = graphNode.InArcs.Last();
355      var fragment = arc.Data as IFragment<ISymbolicExpressionTreeNode>;
356      if (fragment != null) {
357        genealogyGraphChart.SelectedGraphNode = arc.Source;
358        UpdateTreeChart((IGenealogyGraphNode<ISymbolicExpressionTree>)arc.Source);
359        return;
360      }
361
362      if (lastTd != null && graphNode.InDegree > 1) {
363        var descendant = graphNode.Data;
364        // going right (in the direction of the fragment):
365        // 1) fragment was swapped by crossover
366        // 2) fragment was introduced by mutation
367        // in some cases mutation changes things completely so we do not know which way to go
368
369        var f = descendant.NodeAt(lastTd.FragmentIndex);
370        arc = graphNode.InArcs.FirstOrDefault(a => {
371          var td = a.Data as TraceData;
372          if (td == null) return false;
373          var ancestor = (ISymbolicExpressionTree)a.Source.Data;
374          return f.Difference(ancestor.NodeAt(td.SubtreeIndex)) == null;
375        });
376      }
377      if (arc == null) return;
378      lastTd = arc.Data as TraceData;
379      genealogyGraphChart.SelectedGraphNode = arc.Source;
380      graphNode = (IGenealogyGraphNode<ISymbolicExpressionTree>)arc.Source;
381      UpdateTreeChart(graphNode);
382
383      var inDegreeDistinct = graphNode.InArcs.Select(x => x.Source).Distinct().Count();
384      var outDegreeDistinct = graphNode.OutArcs.Select(x => x.Target).Distinct().Count();
385
386      selectedNodeStatusStrip.Text = string.Format("Quality: {0:0.00}, Rank: {1:0.0}, Degree: {2}/{3}, Weight: {4:0.00}",
387        graphNode.Quality, graphNode.Rank, inDegreeDistinct, outDegreeDistinct, graphNode.Weight);
388    }
389
390    private void nodeColorsComboBox_SelectedIndexChanged(object sender, EventArgs e) {
391      switch (nodeColorsComboBox.SelectedIndex) {
392        case 0: // color by quality
393          genealogyGraphChart.ColorSelector = node => ColorGradient.Colors[(int)Math.Round(node.Quality * 255)];
394          genealogyGraphChart.SuspendRendering();
395          genealogyGraphChart.HighlightAll();
396          genealogyGraphChart.ResumeRendering();
397          break;
398        case 1: // color by weight
399          var weights = Content.Vertices.ToDictionary(v => (IGenealogyGraphNode)v, v => v.Data.IterateNodesPrefix().Average(x => x.NodeWeight));
400          var max = weights.Values.Max();
401          genealogyGraphChart.ColorSelector = node => ColorGradient.GrayscaledColors[(int)Math.Round(weights[node] / max * 255)];
402          genealogyGraphChart.SuspendRendering();
403          genealogyGraphChart.HighlightAll();
404          genealogyGraphChart.ResumeRendering();
405          break;
406        default:
407          break;
408      }
409    }
410
411    private void lockCheckBox_CheckedChanged(object sender, EventArgs e) {
412      genealogyGraphChart.LockGenealogy = lockCheckBox.Checked;
413    }
414  }
415  #endregion
416}
417
418// bogus class needed in order to be able to "design" the view
419public class SymbolicDataAnalysisGenealogyGraphViewDesignable : GenealogyGraphView<ISymbolicExpressionTree> { }
420
421#region helper methods
422internal static class Util {
423  internal static ISymbolicExpressionTreeNode NodeAt(this ISymbolicExpressionTree tree, int position) {
424    return NodeAt(tree.Root, position);
425  }
426
427  internal static ISymbolicExpressionTreeNode NodeAt(this ISymbolicExpressionTreeNode root, int position) {
428    return root.IterateNodesPrefix().ElementAt(position);
429  }
430
431  internal static bool IsIsomorphicWith(this ISymbolicExpressionTreeNode a, ISymbolicExpressionTreeNode b) {
432    return a.Difference(b) == null;
433  }
434
435  internal static IEnumerable<ISymbolicExpressionTreeNode> IterateNodesPrefix(this ISymbolicExpressionTreeNode node, int skipIndex) {
436    var e = node.IterateNodesPrefix().GetEnumerator();
437    var i = 0;
438    while (e.MoveNext()) {
439      var n = e.Current;
440      if (i == skipIndex) {
441        var len = n.GetLength();
442        while (--len >= 0 && e.MoveNext()) ;
443        n = e.Current;
444      }
445      if (n != null)
446        yield return n;
447      ++i;
448    }
449  }
450
451  internal static IEnumerable<ISymbolicExpressionTreeNode> IterateNodesPrefix(this ISymbolicExpressionTreeNode node, ISymbolicExpressionTreeNode skipNode) {
452    var e = node.IterateNodesPrefix().GetEnumerator();
453    while (e.MoveNext()) {
454      var n = e.Current;
455      if (n == skipNode) {
456        int len = n.GetLength();
457        while (--len >= 0 && e.MoveNext()) ;
458        n = e.Current;
459      }
460      if (n != null)
461        yield return n;
462    }
463  }
464}
465#endregion
Note: See TracBrowser for help on using the repository browser.