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

#region License Information
/* HeuristicLab
 * Copyright (C) 2002-2016 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
 *
 * This file is part of HeuristicLab.
 *
 * HeuristicLab is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * HeuristicLab is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
 */
#endregion

using System;
using System.Collections.Generic;
using System.Drawing;
using System.Linq;
using System.Windows.Forms;
using HeuristicLab.Common;
using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.Views;
using HeuristicLab.EvolutionTracking;
using HeuristicLab.EvolutionTracking.Views;
using HeuristicLab.MainForm;
using HeuristicLab.Problems.DataAnalysis.Symbolic;

namespace HeuristicLab.Problems.DataAnalysis.Symbolic.Views {
  [View("SymbolicDataAnalysisGenealogyGraphView")]
  [Content(typeof(IGenealogyGraph<ISymbolicExpressionTree>), IsDefaultView = true)]
  public partial class SymbolicDataAnalysisGenealogyGraphView : SymbolicDataAnalysisGenealogyGraphViewDesignable {
    private readonly ISymbolicExpressionTreeNodeEqualityComparer comparer;

    private TraceData lastTd;

    private ISymbolicExpressionTreeNode clonedSubtree;
    private Dictionary<ISymbolicExpressionTreeNode, ISymbolicExpressionTreeNode> clonedMap;

    private ISymbolicExpressionTreeNode selectedSubtree;
    private ISymbolicExpressionTreeNode SelectedSubtree {
      get { return selectedSubtree; }
      set {
        if (value == null) return;
        selectedSubtree = value;
        // 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
    // and highlight relevant tree parts
    public SymbolicExpressionTreeChart SymbolicExpressionTreeChart {
      get {
        var view = (GraphicalSymbolicExpressionTreeView)base.viewHost.ActiveView;
        return view == null ? null : view.SymbolicExpressionTreeChart;
      }
    }

    public SymbolicDataAnalysisGenealogyGraphView() {
      InitializeComponent();
      comparer = new SymbolicExpressionTreeNodeEqualityComparer();
      viewHost.ViewType = typeof(GraphicalSymbolicExpressionTreeView);
    }
    #region event handlers
    protected override void OnContentChanged() {
      base.OnContentChanged();
      if (Content != null && Content != genealogyGraphChart.GenealogyGraph) {
        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();
    }

    public override void graphChart_GenealogyGraphNodeClicked(object sender, MouseEventArgs args) {
      base.graphChart_GenealogyGraphNodeClicked(sender, args);
      var visualNode = (VisualGenealogyGraphNode)sender;
      var graphNode = (IGenealogyGraphNode<ISymbolicExpressionTree>)visualNode.Data;

      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) {
        // get the ancestors into a new view
        var cloner = new Cloner();
        // clone arcs and vertices and use them to create a new graph 
        // that will include just the individual and its ancestors
        var graph = new GenealogyGraph<ISymbolicExpressionTree>();
        var ancestors = new[] { graphNode }.Concat(graphNode.Ancestors).ToList();
        graph.AddVertices(ancestors.Select(cloner.Clone));
        graph.AddArcs(ancestors.SelectMany(x => x.InArcs).Select(cloner.Clone));
        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 => 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 = lastTd;

      if (fragment != null) {
        // highlight the fragment with a blue line color
        foreach (var n in graphNode.Data.NodeAt(fragment.Index1).IterateNodesPrefix()) {
          treeChart_HighlightSubtree(n, Color.CornflowerBlue);
        }
      } else if (td != null) {
        // highlight traced subtree and fragment
        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);
        }
      }
    }

    #region specific symbolic expression tree node click actions
    private void OnTreeNodeLeftClicked(ISymbolicExpressionTreeNode node) {
      SelectedSubtree = node;
      bool trace = genealogyGraphChart.TraceFragments;

      // check whether we are in 'trace' or 'match' mode
      if (trace) {
        // perform fragment tracing
        var graphNode = (IGenealogyGraphNode<ISymbolicExpressionTree>)genealogyGraphChart.SelectedGraphNode;
        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

        /*
                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 {
        // perform matching like it was done before
        // currently there is no possibility to specify the subtree matching criteria
        var trees = Content.Vertices.Select(x => x.Data);
        comparer.MatchVariableWeights = matchingModeButton.Checked;
        comparer.MatchConstantValues = matchingModeButton.Checked;
        var matchingTrees = trees.Where(x => x.Root.ContainsSubtree(node, comparer));

        var matchingVertices = matchingTrees.Select(x => Content.GetByContent(x));
        graphChart_HighlightMatchingVertices(matchingVertices);
      }
    }

    private void OnTreeNodeMiddleClicked(ISymbolicExpressionTreeNode node) {
      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

    public void treeChart_SymbolicExpressionTreeNodeClicked(object sender, MouseEventArgs args) {
      var visualNode = (VisualTreeNode<ISymbolicExpressionTreeNode>)sender;
      var subtree = visualNode.Content;

      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;
          }
        case MouseButtons.Middle: {
            OnTreeNodeMiddleClicked(subtree);
            break;
          }
      }
    }
    #endregion



    private void graphChart_HighlightMatchingVertices(IEnumerable<IGenealogyGraphNode> vertices) {
      genealogyGraphChart.SuspendRendering();
      genealogyGraphChart.ClearPrimitives();
      genealogyGraphChart.HighlightNodes(vertices);
      genealogyGraphChart.ResumeRendering();
    }

    private void treeChart_ClearColors() {
      foreach (var node in SymbolicExpressionTreeChart.Tree.IterateNodesPrefix()) {
        var visualNode = SymbolicExpressionTreeChart.GetVisualSymbolicExpressionTreeNode(node);
        if (visualNode != null) {
          visualNode.LineColor = Color.Black;
          visualNode.FillColor = Color.Transparent;
        }
      }
      SymbolicExpressionTreeChart.RepaintNodes();
    }

    private void treeChart_HighlightSubtree(ISymbolicExpressionTreeNode subtree, Color? lineColor = null, Color? fillColor = null) {
      if (lineColor == null && fillColor == null)
        return;

      foreach (var s in subtree.IterateNodesPrefix()) {
        var visualNode = SymbolicExpressionTreeChart.GetVisualSymbolicExpressionTreeNode(s);
        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;
      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;
      }

      var comp = new SymbolicExpressionTreeNodeEqualityComparer();

      if (lastTd != null && graphNode.InDegree > 1) {
        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;
      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;
      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 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;
      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;
  }

  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