source: branches/HeuristicLab.EvolutionaryTracking/HeuristicLab.EvolutionaryTracking.Views/3.4/GenealogyGraphChart.cs @ 8249

#region License Information
/* HeuristicLab
 * Copyright (C) 2002-2010 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.Drawing.Drawing2D;
using System.Linq;
using System.Windows.Forms;
using HeuristicLab.Common;
using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
using HeuristicLab.Visualization;

namespace HeuristicLab.EvolutionaryTracking.Views {
  public partial class GenealogyGraphChart : ChartControl {
    private Dictionary<GenealogyGraphNode, List<VisualGenealogyGraphNode>> _visualNodeMap;
    private Dictionary<Tuple<VisualGenealogyGraphNode, VisualGenealogyGraphNode>, VisualGenealogyGraphArc> _visualArcMap;
    private const int Diameter = 20; // node diameter
    private int x, y; // coordinates for positioning each node
    private const int Cx = 30, Cy = 30; // position increments
    private VisualGenealogyGraphNode _selectedGenealogyGraphNode;
    public VisualGenealogyGraphNode SelectedGenealogyGraphNode { get { return _selectedGenealogyGraphNode; } }
    private Visualization.Rectangle _targetRectangle; // provides a  rectangle mark of the currently selected genealogy graph node

    private SymbolicExpressionTreeGenealogyGraph _graph;
    public SymbolicExpressionTreeGenealogyGraph Graph {
      get { return _graph; }
      internal set {
        _graph = value;
        _visualNodeMap = new Dictionary<GenealogyGraphNode, List<VisualGenealogyGraphNode>>();
        _visualArcMap = new Dictionary<Tuple<VisualGenealogyGraphNode, VisualGenealogyGraphNode>, VisualGenealogyGraphArc>();
        DrawGraph();
      }
    }

    public event MouseEventHandler GenealogyGraphNodeClicked;
    private void OnGenealogyGraphNodeClicked(object sender, MouseEventArgs e) {
      var clicked = GenealogyGraphNodeClicked;
      if (clicked != null) clicked(sender, e);
    }

    public GenealogyGraphChart() {
      Chart = new Chart(0, 0, PreferredSize.Width, PreferredSize.Height);
      x = 0;
      y = PreferredSize.Height + Cx + 2 * Diameter;
    }

    public void DrawGraph() {
      if (_graph == null) return;
      Chart.UpdateEnabled = false;

      var genealogyGraphNodes = Graph.Values.ToList();
      var layers = genealogyGraphNodes.GroupBy(n => Graph[n].Ranks[0]).OrderBy(g => g.Key).Select(g => new { Rank = g.Key, Nodes = g.ToList() }).ToList();
      List<GenealogyGraphNode> currentLayer = null;
      List<GenealogyGraphNode> previousLayer = null;

      for (int i = 0; i != layers.Count(); ++i) {
        var layer = layers[i];
        double currentRank = layer.Rank;
        if (i > 0 && currentRank % 1 == 0) {
          previousLayer = currentLayer;
          currentLayer = layer.Nodes;
          int d = previousLayer.Count - currentLayer.Count;
          if (d > 0)
            currentLayer.AddRange(previousLayer.Take(d));
        } else {
          currentLayer = layer.Nodes;
        }
        currentLayer.Sort((b, a) => {
          if (Graph[a].Quality.Equals(Graph[b].Quality)) {
            if (Graph[a].IsElite) return 1;
            if (Graph[b].IsElite) return -1;
          }
          return Graph[a].Quality.CompareTo(Graph[b].Quality);
        }); // sort descending by quality (using comparison defined in GenealogyGraphNode class)

        x = 0; // reset horizontal coordinate
        // start laying out visual nodes
        foreach (var node in currentLayer) {
          var pen = new Pen(Color.LightGray);
          var nl = Environment.NewLine;
          var visualNode = new VisualGenealogyGraphNode(Chart, x, y, x + Diameter, y + Diameter, pen, null) {
            Data = node,
            ToolTipText = "Id: " + node.Label + nl +
                          "Ranks: " + string.Join(",", Graph[node].Ranks.Select(r => r.ToString())) + nl +
                          "Quality: " + String.Format("{0:0.0000}", Graph[node].Quality) + nl +
                          "IsElite: " + Graph[node].IsElite
          };
          Chart.Group.Add(visualNode);
          if (!_visualNodeMap.ContainsKey(node))
            _visualNodeMap[node] = new List<VisualGenealogyGraphNode>();
          _visualNodeMap[node].Add(visualNode);

          x += Cx; // increment horizontal coordinate
        }

        y -= Cy; // decrement vertical coordinate (because the origin is upside down)
      }
      // add arcs separately (to avoid some ordering problems)
      foreach (var node in _visualNodeMap.Keys) {
        var visualNode = _visualNodeMap[node][0];
        if (node.InEdges == null) continue;

        foreach (var arc in node.InEdges) {
          var visualParent = _visualNodeMap[arc.Target][0];
          var pen = new Pen(Color.Transparent);
          _visualArcMap[Tuple.Create(visualParent, visualNode)] = AddArc(Chart, visualParent, visualNode, pen);
        }
      }
      // connect visual nodes representing the same elite individual with a line
      foreach (var list in _visualNodeMap.Values.Where(l => l.Count > 1)) {
        for (int i = 1; i != list.Count; ++i) {
          var pen = new Pen(Color.LightGray);
          _visualArcMap[Tuple.Create(list[i - 1], list[i])] = AddArc(Chart, list[i - 1], list[i], pen);
        }
      }

      Chart.UpdateEnabled = true;
      Chart.EnforceUpdate();
    }

    // add an arc between the source and the target nodes, using the specified pen color
    // adds the arc to the arc lists of both nodes and to the primitive group of the chart
    private static VisualGenealogyGraphArc AddArc(IChart chart, VisualGenealogyGraphNode source, VisualGenealogyGraphNode target, Pen pen, Brush brush = null) {
      var arc = new VisualGenealogyGraphArc(chart, source, target, pen) { Brush = brush };
      arc.UpdatePosition();
      source.OutgoingArcs.Add(arc);
      target.IncomingArcs.Add(arc);
      chart.Group.Add(arc);
      return arc;
    }

    protected override void pictureBox_MouseUp(object sender, MouseEventArgs e) {
      if (Chart.Mode != ChartMode.Select)
        base.pictureBox_MouseUp(sender, e);
      else { // select mode
        // get selected node
        var visualNodes = Chart.GetAllPrimitives(e.Location).Where(p => p is VisualGenealogyGraphNode).ToList();
        if (visualNodes.Count > 0) {
          if (_selectedGenealogyGraphNode == visualNodes[0]) return;
          _selectedGenealogyGraphNode = visualNodes[0] as VisualGenealogyGraphNode;
          if (_selectedGenealogyGraphNode == null) return;
          // new node has been selected, clean up
          Chart.UpdateEnabled = false;
          // clear colors
          ClearAllNodes();
          // use a rectangle to highlight the currently selected genealogy graph node
          var center = _selectedGenealogyGraphNode.Center;
          var size = _selectedGenealogyGraphNode.Size;
          double x1 = center.X - size.Width / 2;
          double x2 = x1 + size.Width;
          double y1 = center.Y - size.Height / 2;
          double y2 = y1 + size.Height;
          if (_targetRectangle == null) {
            _targetRectangle = new Visualization.Rectangle(Chart, x1, y1, x2, y2, new Pen(Color.Black), null);
            Chart.Group.Add(_targetRectangle);
          } else {
            _targetRectangle.SetPosition(x1, y1, x2, y2);
          }
          var gNode = _selectedGenealogyGraphNode.Data; // genealogy graph node (representing an individual in the population) 
          double rank = Graph[gNode].Ranks[0];
          // ancestors
          var ancestors = gNode.Ancestors().Where(n => Graph[n].Ranks.Last() < rank).ToList();
          ancestors.Add(gNode);
          // descendants
          var descendants = gNode.Descendants().Where(n => Graph[n].Ranks.Last() > rank).ToList();
          descendants.Add(gNode);
          // highlight ancestors
          foreach (var node in ancestors.Select(n => _visualNodeMap[n][0])) {
            node.Brush = new SolidBrush(Graph[node.Data].GetColor());
            if (node.IncomingArcs != null)
              foreach (var arc in node.IncomingArcs) {
                // check if, in case of elites, the target node is the first visual representation of the elite
                // (for purposes of display consistency)
                bool isFirst = arc.Source == _visualNodeMap[arc.Source.Data][0];
                if (arc.Source.Data == arc.Target.Data || !isFirst) continue;
                var start = new Point((int)arc.Start.X, (int)arc.Start.Y);
                var end = new Point((int)arc.End.X, (int)arc.End.Y);
                arc.Pen.Brush = new LinearGradientBrush(start, end, Graph[arc.Source.Data].GetColor(), Graph[arc.Target.Data].GetColor());
              }
          }
          // highlight descendants
          foreach (var node in descendants.Select(n => _visualNodeMap[n][0])) {
            node.Brush = new SolidBrush(Graph[node.Data].GetColor());
            if (node.OutgoingArcs != null)
              foreach (var arc in node.OutgoingArcs) {
                // check if, in case of elites, the target node is the first visual representation of the elite
                // (for purposes of display consistency)
                bool isFirst = arc.Target == _visualNodeMap[arc.Target.Data][0];
                if (arc.Source.Data == arc.Target.Data || !isFirst) continue;
                var start = new Point((int)arc.Start.X, (int)arc.Start.Y);
                var end = new Point((int)arc.End.X, (int)arc.End.Y);
                arc.Pen.Brush = new LinearGradientBrush(start, end, Graph[arc.Source.Data].GetColor(), Graph[arc.Target.Data].GetColor());
              }
          }
        } else {
          _selectedGenealogyGraphNode = null;
        }
        // update
        Chart.UpdateEnabled = true;
        Chart.EnforceUpdate();
        if (_selectedGenealogyGraphNode != null)
          /* emit clicked event */
          OnGenealogyGraphNodeClicked(_selectedGenealogyGraphNode, e);
      }
    }

    public void ClearAllNodes() {
      foreach (var primitive in Chart.Group.Primitives) {
        primitive.Brush = null;
        if (primitive is VisualGenealogyGraphArc) {
          var arc = primitive as VisualGenealogyGraphArc;
          if (arc.Source.Data != arc.Target.Data && primitive.Pen.Brush != null)
            primitive.Pen.Brush = new SolidBrush(Color.Transparent);
        }
      }
    }

    public void HighlightLineage(IEnumerable<GenealogyGraphNode> nodes) {
      foreach (var node in nodes.SelectMany(n => _visualNodeMap[n])) {
        node.Brush = new SolidBrush(Graph[node.Data].GetColor());
        if (node.IncomingArcs == null || node != _visualNodeMap[node.Data][0]) continue;
        foreach (var arc in node.IncomingArcs) {
          if (arc.Source.Data == node.Data) continue;
          var start = new Point((int)arc.Start.X, (int)arc.Start.Y);
          var end = new Point((int)arc.End.X, (int)arc.End.Y);
          arc.Pen.Brush = new LinearGradientBrush(start, end, Graph[arc.Source.Data].GetColor(), Graph[arc.Target.Data].GetColor());
        }
      }
    }

    public void HighlightNodes(IEnumerable<ISymbolicExpressionTree> trees, Color color) {
      foreach (var visualNode in trees.Select(tree => _visualNodeMap[Graph.GetNode(tree)]).SelectMany(vList => vList))
        visualNode.Brush = new SolidBrush(color);
    }

    public void HighlightInDegree() {
      Chart.UpdateEnabled = false;
      ClearAllNodes();
      var graphNodes = Graph.Values.ToList();
      double min = graphNodes.Min(x => x.InEdges == null ? 0 : x.InEdges.Count);
      double max = graphNodes.Max(x => x.InEdges == null ? 0 : x.InEdges.Count);
      foreach (var graphNode in graphNodes) {
        var visualNode = _visualNodeMap[graphNode][0];
        double deg = graphNode.InEdges == null ? 0 : graphNode.InEdges.Count;
        var color = Color.FromArgb((int)(1 - deg / max) * 255, (int)(deg / max * 255), 100);
        visualNode.Brush = new SolidBrush(color);
      }
      Chart.UpdateEnabled = true;
      Chart.EnforceUpdate();
    }

    public void HighlightOutDegree() {
      Chart.UpdateEnabled = false;
      ClearAllNodes();
      var graphNodes = Graph.Values.ToList();
      double min = graphNodes.Min(x => x.OutEdges == null ? 0 : x.OutEdges.Count);
      double max = graphNodes.Max(x => x.OutEdges == null ? 0 : x.OutEdges.Count);
      foreach (var graphNode in graphNodes) {
        var visualNode = _visualNodeMap[graphNode][0];
        double deg = graphNode.OutEdges == null ? 0 : graphNode.OutEdges.Count;
        int index = (int)(deg / max * ColorGradient.Colors.Count) - 1;
        if (index < 0) index = 0;
        visualNode.Brush = new SolidBrush(ColorGradient.Colors[index]);
      }
      Chart.UpdateEnabled = true;
      Chart.EnforceUpdate();
    }
  }

  internal static class Util {
    public static Color GetColor(this NodeMetadata nm) {
      var colorIndex = (int)(nm.Quality * ColorGradient.Colors.Count);
      if (colorIndex >= ColorGradient.Colors.Count) --colorIndex;
      return ColorGradient.Colors[colorIndex];
    }
  }
}