source: branches/HeuristicLab.EvolutionTracking/HeuristicLab.Problems.DataAnalysis.Symbolic.Views/3.4/Tracking/SymboldDataAnalysisGenealogyView.cs @ 10746

#region License Information
/* HeuristicLab
 * Copyright (C) 2002-2014 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.IO;
using System.Linq;
using System.Windows.Forms;
using HeuristicLab.Core.Views;
using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.Views;
using HeuristicLab.EvolutionTracking;
using HeuristicLab.EvolutionTracking.Views;
using HeuristicLab.MainForm;

using FragmentGraph = HeuristicLab.EvolutionTracking.IGenealogyGraph<HeuristicLab.EvolutionTracking.IFragment<HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.ISymbolicExpressionTreeNode>>;
using FragmentNode = HeuristicLab.EvolutionTracking.GenealogyGraphNode<HeuristicLab.EvolutionTracking.IFragment<HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.ISymbolicExpressionTreeNode>>;

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

    public SymboldDataAnalysisGenealogyView() {
      InitializeComponent();

      comparer = new SymbolicExpressionTreeNodeSimilarityComparer();
    }

    public new IGenealogyGraph<ISymbolicExpressionTree> Content {
      get { return (IGenealogyGraph<ISymbolicExpressionTree>)base.Content; }
      set { base.Content = value; }
    }

    #region event handlers

    protected override void OnContentChanged() {
      base.OnContentChanged();
      if (Content != null) {
        genealogyGraphChart.GenealogyGraph = Content;
      }
    }

    #endregion

    protected override void RegisterContentEvents() {
      genealogyGraphChart.GenealogyGraphNodeClicked += graphChart_GenealogyGraphNodeClicked;
      symbolicExpressionTreeChart.SymbolicExpressionTreeNodeClicked += treeChart_SymbolicExpressionNodeClicked;
      base.RegisterContentEvents();
    }

    protected override void DeregisterContentEvents() {
      base.DeregisterContentEvents();
      genealogyGraphChart.GenealogyGraphNodeClicked -= graphChart_GenealogyGraphNodeClicked;
      symbolicExpressionTreeChart.SymbolicExpressionTreeNodeClicked -= treeChart_SymbolicExpressionNodeClicked;
    }

    public void graphChart_GenealogyGraphNodeClicked(object sender, MouseEventArgs args) {
      var visualNode = (VisualGenealogyGraphNode)sender;
      var graphNode = (IGenealogyGraphNode<ISymbolicExpressionTree>)visualNode.Data;
      var tree = graphNode.Content;
      symbolicExpressionTreeChart.Tree = tree;

      if (graphNode.InArcs.Any()) {
        var fragment = (IFragment<ISymbolicExpressionTreeNode>)graphNode.InArcs.Last().Data;
        treeChart_HighlightSubtree(fragment.Root);
      }
    }

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

      // highlight the selected subtree inside the displayed tree on the right hand side
      treeChart_ClearColors();
      treeChart_HighlightSubtree(subtree);

      bool trace = genealogyGraphChart.TraceFragments; // check whether the mode is 'trace' or 'match'

      if (trace) {
        // perform fragment tracing
        var fragmentGraph = TraceSubtree(subtree);
        MainFormManager.MainForm.ShowContent(fragmentGraph); // display the fragment graph on the screen
      } else {
        // perform matching like it was done before
        // currently there is no possibility to specify the subtree matching criteria
        var trees = Content.Nodes.Select(x => x.Content);
        var matchingTrees = trees.Where(x => x.Root.ContainsSubtree(subtree, comparer));

        var matchingVertices = matchingTrees.SelectMany(x => Content[x]).Cast<IGenealogyGraphNode<ISymbolicExpressionTree>>();
        graphChart_highlightMatchingVertices(matchingVertices);
      }
    }

    private void graphChart_highlightMatchingVertices(IEnumerable<IGenealogyGraphNode> vertices) {
      genealogyGraphChart.Chart.UpdateEnabled = false;
      genealogyGraphChart.ClearPrimitives();
      genealogyGraphChart.HighlightNodes(vertices);
      genealogyGraphChart.Chart.UpdateEnabled = true;
      genealogyGraphChart.Chart.EnforceUpdate();
    }

    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) {
      foreach (var s in subtree.IterateNodesPrefix()) {
        var visualNode = symbolicExpressionTreeChart.GetVisualSymbolicExpressionTreeNode(s);
        visualNode.LineColor = Color.RoyalBlue;
        visualNode.FillColor = Color.LightBlue;

        foreach (var c in s.Subtrees) {
          var visualArc = symbolicExpressionTreeChart.GetVisualSymbolicExpressionTreeNodeConnection(s, c);
          visualArc.LineColor = Color.RoyalBlue;
        }
      }
      symbolicExpressionTreeChart.RepaintNodes();
    }

    #region events for configuring the behavior of the genealogy chart (trace/match, simple lineages, etc)
    private void trace_checkBox_CheckedChanged(object sender, System.EventArgs e) {
      genealogyGraphChart.TraceFragments = trace_checkBox.Checked;
    }

    private void simpleLineages_checkBox_CheckedChanged(object sender, System.EventArgs e) {
      genealogyGraphChart.SimpleLineages = simpleLineages_checkBox.Checked;
    }

    private void lockGraph_checkBox_CheckedChanged(object sender, System.EventArgs e) {
      genealogyGraphChart.LockGenealogy = lockGraph_checkBox.Checked;
    }
    #endregion

    #region fragment tracing
    private FragmentGraph TraceSubtree(ISymbolicExpressionTreeNode subtree) {
      var graphNode = (IGenealogyGraphNode<ISymbolicExpressionTree>)genealogyGraphChart.SelectedGraphNode;
      var graph = new GenealogyGraph<IFragment<ISymbolicExpressionTreeNode>>();
      Trace(graphNode, subtree, graph);
      return graph;
    }

    private static void Trace(IGenealogyGraphNode<ISymbolicExpressionTree> graphNode, ISymbolicExpressionTreeNode subtree, FragmentGraph fragmentGraph, FragmentNode parentNode = null) {
      while (true) {
        if (!graphNode.InArcs.Any()) return;

        var parentVertices = graphNode.Parents.ToList();
        // the subtree must belong to the currently displayed tree which in turn must belong to the currently selected graph node
        var tree = graphNode.Content;
        var subtreeIndex = tree.IndexOf(subtree);
        var subtreeLength = subtree.GetLength();

        var fragment = (IFragment<ISymbolicExpressionTreeNode>)graphNode.InArcs.Last().Data;
        if (fragment == null) return;
        var fragmentLength = fragment.Root.GetLength();

        var fragmentNode = new FragmentNode {
          Content = new Fragment<ISymbolicExpressionTreeNode> {
            Root = subtree,
          },
          Rank = graphNode.Rank
        };

        if (parentNode != null) {
          if (parentNode == fragmentNode) {
            throw new Exception("Node cannot be a child of itself!");
          }
          var arc = new GenealogyGraphArc { Source = parentNode, Target = fragmentNode };
          parentNode.AddForwardArc(arc);
        }
        fragmentGraph.AddVertex(fragmentNode);

        parentNode = fragmentNode;

        // if the selected subtree is the actual fragment
        if (fragment.Index == subtreeIndex) {
          if (fragmentLength != subtreeLength) throw new Exception("Fragment and subtree lengths should be the same!");
          graphNode = parentVertices.Last();
          tree = graphNode.Content;
          subtree = tree.NodeAt(fragment.OldIndex);
          continue;
        }
        // if the fragment contains the selected subtree => track fragment, then track subtree
        if (fragment.Index < subtreeIndex && subtreeIndex < fragment.Index + fragmentLength) {
          if (subtreeLength >= fragmentLength) throw new Exception("Fragment contains subtree, so subtree length should be less than the fragment length.");

          graphNode = parentVertices.Last();
          tree = graphNode.Content;
          var i = fragment.Root.IndexOf(subtree); // get the index of the selected subtree, relative to the fragment root
          subtree = tree.NodeAt(fragment.OldIndex + i);
          continue;
        }
        // if the selected subtree contains the fragment => track fragment and subtree
        if (subtreeIndex < fragment.Index && fragment.Index < subtreeIndex + subtreeLength) {
          if (fragmentLength >= subtreeLength) throw new Exception("Subtree contains fragment, so fragment length should be less than the subtree length.");
          fragmentNode.Content.Index = fragment.Index - subtreeIndex;
          graphNode = parentVertices[0];
          // debug check
          tree = graphNode.Content;
          subtree = tree.NodeAt(subtreeIndex);
          if (subtree.GetLength() <= fragmentNode.Content.Index) {
            throw new Exception("Index exceeds subtree length.");
          }
          // track subtree
          Trace(graphNode, subtree, fragmentGraph, fragmentNode);

          // track fragment
          if (parentVertices.Count > 1) {
            // save the index of the current fragment in the tree where it was swapped
            graphNode = parentVertices[1];
            tree = graphNode.Content;
            subtree = tree.NodeAt(fragment.OldIndex);
            continue;
          }
        } else {
          // fragment and subtree are completely distinct => we only track the subtree (contained by the root parent)
          // if the subtree comes AFTER the fragment in the prefix iteration of nodes, 
          // then its index is affected by the difference in fragment size between current tree and parent
          graphNode = parentVertices[0];
          tree = graphNode.Content;
          if (subtreeIndex > fragment.Index) {
            var diff = tree.NodeAt(fragment.Index).GetLength() - fragmentLength;
            subtreeIndex += diff;
          }
          subtree = tree.NodeAt(subtreeIndex);
          continue;
        }
        break;
      }
    }
    #endregion
  }

  internal static class Util {
    private static string ViewAsText(this ISymbolicExpressionTreeNode root) {
      var writer = new StringWriter();
      SymbolicExpressionTreeHierarchicalFormatter.RenderNode(writer, root, string.Empty);
      return writer.ToString();
    }
    #region some helper methods for shortening the tracing code

    internal static void AddChild(this IGenealogyGraphNode parent, IGenealogyGraphNode child) {
      parent.AddForwardArc(child);
      child.AddReverseArc(parent);
      child.Rank = parent.Rank - 1;
    }
    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 int IndexOf(this ISymbolicExpressionTree tree, ISymbolicExpressionTreeNode node) {
      return IndexOf(tree.Root, node);
    }
    internal static int IndexOf(this ISymbolicExpressionTreeNode root, ISymbolicExpressionTreeNode node) {
      int i = 0;
      foreach (var n in root.IterateNodesPrefix()) {
        if (n == node) return i;
        ++i;
      }
      return -1;
    }
    #endregion
  }
}