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

Last change on this file since 13892 was 13892, checked in by bburlacu, 4 years ago

#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.

File size: 20.3 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      nodeQualityLabel.Text = string.Format("{0:0.000}", graphNode.Quality);
106      nodeRankLabel.Text = string.Format("{0:0.0}", graphNode.Rank);
107      nodeDegreeLabel.Text = string.Format("{0} / {1}", graphNode.InDegree, graphNode.OutDegree);
108      nodeWeightLabel.Text = string.Format("{0:0.00}", graphNode.Weight);
109
110      // update the righthand side tree view when another genealogy graph node is selected
111      UpdateTreeChart(graphNode);
112
113      if (!graphNode.InArcs.Any()) return; // node has no ancestors, nothing to do
114
115      if (openNew_CheckBox.Checked) {
116        // get the ancestors into a new view
117        var cloner = new Cloner();
118        // clone arcs and vertices and use them to create a new graph
119        // that will include just the individual and its ancestors
120        var graph = new GenealogyGraph<ISymbolicExpressionTree>();
121        var ancestors = new[] { graphNode }.Concat(graphNode.Ancestors).ToList();
122        graph.AddVertices(ancestors.Select(cloner.Clone));
123        graph.AddArcs(ancestors.SelectMany(x => x.InArcs).Select(cloner.Clone));
124        MainFormManager.MainForm.ShowContent(graph);
125      }
126    }
127
128    private void UpdateTreeChart(IGenealogyGraphNode<ISymbolicExpressionTree> graphNode) {
129      SymbolicExpressionTreeChart.Tree = graphNode.Data;
130      var nodes = graphNode.Data.IterateNodesPrefix().ToList();
131      // calculate max only in the current generation
132      var max = Content.Vertices.Max(x => x.Data.IterateNodesPrefix().Max(n => n.NodeWeight));
133      if (max.IsAlmost(0)) max = 1;
134      // we skip the program root node because it's useless for display and it just takes space in the chart
135      foreach (var n in nodes.Skip(1)) {
136        var visualSymbolicExpressionTreeNode = SymbolicExpressionTreeChart.GetVisualSymbolicExpressionTreeNode(n);
137        visualSymbolicExpressionTreeNode.ToolTip += Environment.NewLine + string.Format("Weight: {0:0}", n.NodeWeight);
138        var i = (int)Math.Round(n.NodeWeight / max * 255);
139        var fillColor = Color.FromArgb(i, Color.Red);
140        treeChart_HighlightSubtree(n, null, fillColor);
141      }
142
143      if (!graphNode.InArcs.Any())
144        return;
145      var data = graphNode.InArcs.Last().Data;
146      var fragment = data as IFragment<ISymbolicExpressionTreeNode>;
147      var td = lastTd;
148
149      if (fragment != null) {
150        // highlight the fragment with a blue line color
151        foreach (var n in graphNode.Data.NodeAt(fragment.Index1).IterateNodesPrefix()) {
152          treeChart_HighlightSubtree(n, Color.CornflowerBlue);
153        }
154      } else if (td != null) {
155        // highlight traced subtree and fragment
156        if (td.SubtreeIndex == td.FragmentIndex) {
157          treeChart_HighlightSubtree(nodes[td.SubtreeIndex], Color.Purple);
158        } else if (td.SubtreeIndex < td.FragmentIndex) {
159          treeChart_HighlightSubtree(nodes[td.SubtreeIndex], Color.Orange);
160          treeChart_HighlightSubtree(nodes[td.FragmentIndex], Color.CornflowerBlue);
161        } else {
162          treeChart_HighlightSubtree(nodes[td.FragmentIndex], Color.CornflowerBlue);
163          treeChart_HighlightSubtree(nodes[td.SubtreeIndex], Color.Orange);
164        }
165      }
166    }
167
168    #region specific symbolic expression tree node click actions
169    private void OnTreeNodeLeftClicked(ISymbolicExpressionTreeNode node) {
170      SelectedSubtree = node;
171      bool trace = genealogyGraphChart.TraceFragments;
172
173      // check whether we are in 'trace' or 'match' mode
174      if (trace) {
175        // perform fragment tracing
176        var graphNode = (IGenealogyGraphNode<ISymbolicExpressionTree>)genealogyGraphChart.SelectedGraphNode;
177        var subtreeIndex = graphNode.Data.IterateNodesPrefix().ToList().IndexOf(node);
178        var traceGraph = TraceCalculator.TraceSubtree(graphNode, subtreeIndex, updateVertexWeights: false, updateSubtreeWeights: false, cacheTraceNodes: true);
179
180        if (!traceGraph.Vertices.Any())
181          return;
182
183        genealogyGraphChart.SuspendRendering();
184        genealogyGraphChart.ClearPrimitives(); // clear everything
185        var rankMaximums = new Dictionary<double, double>();
186
187        if (openNew_CheckBox.Checked) {
188          MainFormManager.MainForm.ShowContent(traceGraph);
189        } else {
190        }
191        // fill each vertex in the graph with a grayscale color according to average subtree weight
192
193        /*
194                var colorGradient = ColorGradient.GrayscaledColors;
195                var colorCount = colorGradient.Count - 1;
196                foreach (var r in Content.Ranks) {
197                  var vertices = r.Value.Cast<IGenealogyGraphNode<ISymbolicExpressionTree>>().ToList();
198                  var averages = vertices.Select(x => x.Data.IterateNodesPrefix().Average(n => n.NodeWeight)).ToList();
199                  var max = averages.Max();
200                  rankMaximums.Add(r.Key, max);
201                  if (max.IsAlmost(0.0)) continue;
202                  for (int i = 0; i < vertices.Count; ++i) {
203                    var color = colorGradient[(int)Math.Round(averages[i] / max * colorCount)];
204                    var vNode = genealogyGraphChart.GetMappedNode(vertices[i]);
205                    vNode.Brush = new SolidBrush(color);
206                  }
207                }
208                // fill vertices that are part of the trace with a rgb color according to average subtree weight
209                if (traceGraph.Vertices.Any()) {
210                  var ranks = traceGraph.Vertices.Select(x => Content.GetByContent(x.Data)).GroupBy(x => x.Rank);
211                  foreach (var g in ranks) {
212                    var vertices = g.ToList();
213                    var averages = vertices.Select(x => x.Data.IterateNodesPrefix().Average(n => n.NodeWeight)).ToList();
214                    double max = rankMaximums[g.Key];
215                    if (max.IsAlmost(0.0)) continue;
216                    for (int i = 0; i < vertices.Count; ++i) {
217                      var vNode = genealogyGraphChart.GetMappedNode(vertices[i]);
218                      // use a grayscale gradient
219                      var color = colorGradient[(int)Math.Round(averages[i] / max * colorCount)];
220                      vNode.Brush = new SolidBrush(color);
221                    }
222                  }
223                  */
224
225        //          if (openNew_CheckBox.Checked) {
226        //            MainFormManager.MainForm.ShowContent(traceGraph); // display the fragment graph on the screen
227        //          }
228        //        }
229        genealogyGraphChart.ResumeRendering();
230      } else {
231        // perform matching like it was done before
232        // currently there is no possibility to specify the subtree matching criteria
233        var trees = Content.Vertices.Select(x => x.Data);
234        comparer.MatchVariableWeights = matchingModeButton.Checked;
235        comparer.MatchConstantValues = matchingModeButton.Checked;
236        var matchingTrees = trees.Where(x => x.Root.ContainsSubtree(node, comparer));
237
238        var matchingVertices = matchingTrees.Select(x => Content.GetByContent(x));
239        graphChart_HighlightMatchingVertices(matchingVertices);
240      }
241    }
242
243    private void OnTreeNodeMiddleClicked(ISymbolicExpressionTreeNode node) {
244      ISymbolicExpressionTreeNode clone;
245      if (!clonedMap.TryGetValue(node, out clone)) return;
246      if (clone.Parent == null) return;
247      var cloneParent = clone.Parent;
248      var cloneIndex = cloneParent.IndexOfSubtree(clone);
249      cloneParent.RemoveSubtree(cloneIndex);
250      cloneParent.InsertSubtree(cloneIndex, new AnySubtreeSymbol().CreateTreeNode());
251
252      var trees = Content.Vertices.Select(x => x.Data);
253      comparer.MatchVariableWeights = comparer.MatchConstantValues = matchingModeButton.Checked;
254      var matchingTrees = trees.Where(x => x.Root.ContainsSubtree(clonedSubtree, comparer));
255
256      var matchingVertices = matchingTrees.Select(x => Content.GetByContent(x));
257      treeChart_HighlightSubtree(node, Color.Black, Color.White);
258      graphChart_HighlightMatchingVertices(matchingVertices);
259    }
260    #endregion
261
262    public void treeChart_SymbolicExpressionTreeNodeClicked(object sender, MouseEventArgs args) {
263      var visualNode = (VisualTreeNode<ISymbolicExpressionTreeNode>)sender;
264      var subtree = visualNode.Content;
265
266      switch (args.Button) {
267        case MouseButtons.Left: {
268            // highlight the selected subtree inside the displayed tree on the right hand side
269            treeChart_ClearColors();
270            treeChart_HighlightSubtree(subtree, Color.Black, Color.RoyalBlue);
271
272            OnTreeNodeLeftClicked(subtree);
273            break;
274          }
275        case MouseButtons.Middle: {
276            OnTreeNodeMiddleClicked(subtree);
277            break;
278          }
279      }
280    }
281    #endregion
282
283
284
285    private void graphChart_HighlightMatchingVertices(IEnumerable<IGenealogyGraphNode> vertices) {
286      genealogyGraphChart.SuspendRendering();
287      genealogyGraphChart.ClearPrimitives();
288      genealogyGraphChart.HighlightNodes(vertices);
289      genealogyGraphChart.ResumeRendering();
290    }
291
292    private void treeChart_ClearColors() {
293      foreach (var node in SymbolicExpressionTreeChart.Tree.IterateNodesPrefix()) {
294        var visualNode = SymbolicExpressionTreeChart.GetVisualSymbolicExpressionTreeNode(node);
295        if (visualNode != null) {
296          visualNode.LineColor = Color.Black;
297          visualNode.FillColor = Color.Transparent;
298        }
299      }
300      SymbolicExpressionTreeChart.RepaintNodes();
301    }
302
303    private void treeChart_HighlightSubtree(ISymbolicExpressionTreeNode subtree, Color? lineColor = null, Color? fillColor = null) {
304      if (lineColor == null && fillColor == null)
305        return;
306
307      foreach (var s in subtree.IterateNodesPrefix()) {
308        var visualNode = SymbolicExpressionTreeChart.GetVisualSymbolicExpressionTreeNode(s);
309        if (lineColor != null) {
310          visualNode.LineColor = (Color)lineColor;
311          foreach (var c in s.Subtrees) {
312            var visualArc = SymbolicExpressionTreeChart.GetVisualSymbolicExpressionTreeNodeConnection(s, c);
313            visualArc.LineColor = (Color)lineColor;
314          }
315        }
316        if (fillColor != null)
317          visualNode.FillColor = (Color)fillColor;
318      }
319      SymbolicExpressionTreeChart.RepaintNodes();
320    }
321
322    #region navigate the genealogy / trace graph
323    private void navigateLeftButton_Click(object sender, EventArgs e) {
324      var graphNode = (IGenealogyGraphNode<ISymbolicExpressionTree>)genealogyGraphChart.SelectedGraphNode;
325      if (!graphNode.InArcs.Any()) return;
326
327      // check if the arc contains fragment data
328      var arc = graphNode.InArcs.First();
329      var fragment = arc.Data as IFragment<ISymbolicExpressionTreeNode>;
330
331      if (fragment != null) {
332        genealogyGraphChart.SelectedGraphNode = arc.Source;
333        UpdateTreeChart((IGenealogyGraphNode<ISymbolicExpressionTree>)arc.Source);
334        return;
335      }
336
337      var comp = new SymbolicExpressionTreeNodeEqualityComparer();
338
339      if (lastTd != null && graphNode.InDegree > 1) {
340        var descendant = graphNode.Data;
341        // going left (in the direction of the traced subtree):
342        // the ancestor shares the same structure with the descendant, with the exception of the fragment
343        // thus we identify the right ancestor by comparing the remaining nodes
344        //var descendantNodes = descendant.Root.IterateNodesPrefix(lastTd.FragmentIndex);
345        // calculate the relative fragment preorder index. it will always be > 0 due to the way the trace graph is constructed
346        var relativeFragmentIndex = lastTd.FragmentIndex - lastTd.SubtreeIndex;
347        var descendantNodes = descendant.NodeAt(lastTd.SubtreeIndex).IterateNodesPrefix(relativeFragmentIndex);
348
349        var filteredArcs = graphNode.InArcs.Where(a => {
350          var td = a.Data as TraceData;
351          if (td == null)
352            return false;
353          if (!(td.LastSubtreeIndex == lastTd.SubtreeIndex && td.LastFragmentIndex == lastTd.FragmentIndex))
354            return false;
355          return true;
356        }).ToList();
357
358        if (filteredArcs.Count == 0)
359          return;
360
361        if (filteredArcs.Count == 1) {
362          arc = filteredArcs[0];
363        } else {
364          arc = filteredArcs.FirstOrDefault(
365         a => {
366           var ancestor = (ISymbolicExpressionTree)a.Source.Data;
367           var td = a.Data as TraceData;
368           if (td == null)
369             return false;
370           var ancestorNodes = ancestor.NodeAt(td.SubtreeIndex).IterateNodesPrefix(skipIndex: relativeFragmentIndex);
371           return descendantNodes.SequenceEqual(ancestorNodes, comp);
372         });
373        }
374
375
376      }
377      if (arc == null) return;
378      lastTd = arc.Data as TraceData;
379      genealogyGraphChart.SelectedGraphNode = arc.Source;
380      UpdateTreeChart((IGenealogyGraphNode<ISymbolicExpressionTree>)arc.Source);
381    }
382
383    private void navigateRightButton_Click(object sender, EventArgs e) {
384      var graphNode = (IGenealogyGraphNode<ISymbolicExpressionTree>)genealogyGraphChart.SelectedGraphNode;
385      if (!graphNode.InArcs.Any()) return;
386
387      // check if the arc contains fragment data
388      var arc = graphNode.InArcs.Last();
389      var fragment = arc.Data as IFragment<ISymbolicExpressionTreeNode>;
390      if (fragment != null) {
391        genealogyGraphChart.SelectedGraphNode = arc.Source;
392        UpdateTreeChart((IGenealogyGraphNode<ISymbolicExpressionTree>)arc.Source);
393        return;
394      }
395
396      if (lastTd != null && graphNode.InDegree > 1) {
397        var descendant = graphNode.Data;
398        // going right (in the direction of the fragment):
399        // 1) fragment was swapped by crossover
400        // 2) fragment was introduced by mutation
401        // in some cases mutation changes things completely so we do not know which way to go
402
403        var f = descendant.NodeAt(lastTd.FragmentIndex);
404        arc = graphNode.InArcs.FirstOrDefault(a => {
405          var td = a.Data as TraceData;
406          if (td == null) return false;
407          var ancestor = (ISymbolicExpressionTree)a.Source.Data;
408          return f.Difference(ancestor.NodeAt(td.SubtreeIndex)) == null;
409        });
410      }
411      if (arc == null) return;
412      lastTd = arc.Data as TraceData;
413      genealogyGraphChart.SelectedGraphNode = arc.Source;
414      UpdateTreeChart((IGenealogyGraphNode<ISymbolicExpressionTree>)arc.Source);
415    }
416  }
417  #endregion
418}
419
420// bogus class needed in order to be able to "design" the view
421public class SymbolicDataAnalysisGenealogyGraphViewDesignable : GenealogyGraphView<ISymbolicExpressionTree> { }
422
423#region helper methods
424internal static class Util {
425  internal static ISymbolicExpressionTreeNode NodeAt(this ISymbolicExpressionTree tree, int position) {
426    return NodeAt(tree.Root, position);
427  }
428
429  internal static ISymbolicExpressionTreeNode NodeAt(this ISymbolicExpressionTreeNode root, int position) {
430    return root.IterateNodesPrefix().ElementAt(position);
431  }
432
433  internal static bool IsIsomorphicWith(this ISymbolicExpressionTreeNode a, ISymbolicExpressionTreeNode b) {
434    return a.Difference(b) == null;
435  }
436
437  internal static IEnumerable<ISymbolicExpressionTreeNode> IterateNodesPrefix(this ISymbolicExpressionTreeNode node, int skipIndex) {
438    var e = node.IterateNodesPrefix().GetEnumerator();
439    var i = 0;
440    while (e.MoveNext()) {
441      var n = e.Current;
442      if (i == skipIndex) {
443        var len = n.GetLength();
444        while (--len >= 0 && e.MoveNext()) ;
445        n = e.Current;
446      }
447      if (n != null)
448        yield return n;
449      ++i;
450    }
451  }
452
453  internal static IEnumerable<ISymbolicExpressionTreeNode> IterateNodesPrefix(this ISymbolicExpressionTreeNode node, ISymbolicExpressionTreeNode skipNode) {
454    var e = node.IterateNodesPrefix().GetEnumerator();
455    while (e.MoveNext()) {
456      var n = e.Current;
457      if (n == skipNode) {
458        int len = n.GetLength();
459        while (--len >= 0 && e.MoveNext()) ;
460        n = e.Current;
461      }
462      if (n != null)
463        yield return n;
464    }
465  }
466}
467#endregion
Note: See TracBrowser for help on using the repository browser.