source: branches/HeuristicLab.EvolutionaryTracking/HeuristicLab.EvolutionaryTracking/3.4/GenealogyGraph.cs @ 7479

using System;
using System.Collections.Generic;
using System.Drawing;
using System.Linq;
using HeuristicLab.Common;
using HeuristicLab.Core;
using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;

namespace HeuristicLab.EvolutionaryTracking {
  public class GenealogyGraph : NamedItem {
    private readonly Dictionary<ISymbolicExpressionTree, Node> _dictionary;
    public GenealogyGraph() {
      _dictionary = new Dictionary<ISymbolicExpressionTree, Node>();
    }

    public GenealogyGraph(GenealogyGraph g) {
      _dictionary = new Dictionary<ISymbolicExpressionTree, Node>(g._dictionary);
    }

    [StorableConstructor]
    private GenealogyGraph(bool serializing) : base(serializing) { }

    private GenealogyGraph(GenealogyGraph original, Cloner cloner)
      : base(original, cloner) {
      _dictionary = new Dictionary<ISymbolicExpressionTree, Node>(original._dictionary);
    }

    public bool HasNode(ISymbolicExpressionTree t) {
      return _dictionary.ContainsKey(t);
    }

    public Node GetNode(ISymbolicExpressionTree t) {
      return this.HasNode(t) ? _dictionary[t] : null;
    }

    public IEnumerable<ISymbolicExpressionTree> Keys {
      get { return _dictionary.Keys; }
    }

    public IEnumerable<Node> Values {
      get { return _dictionary.Values; }
    }

    public bool Any() {
      return _dictionary.Any();
    }

    public bool Any(Func<KeyValuePair<ISymbolicExpressionTree, Node>, bool> predicate) {
      return _dictionary.Any(predicate);
    }

    public void Clear() {
      _dictionary.Clear();
    }

    /// <summary>
    /// Adds a node representing an individual
    /// </summary>
    /// <param name="t">The symbolic expression tree</param>
    public void AddNode(ISymbolicExpressionTree t, double q = 0.0, string l = "", bool elite = false) {
      if (HasNode(t)) return;
      _dictionary[t] = new Node { Data = t, Quality = q, Label = l, IsElite = elite };
    }

    /// <summary>
    ///  more of a low level method to minimize memory usage when creating and returning subgraphs
    /// </summary>
    /// <param name="n"></param>
    public void AddNode(Node n) {
      var t = (ISymbolicExpressionTree)n.Data;
      if (HasNode(t))
        return;
      _dictionary[t] = n;
    }

    /// <summary>
    /// Remove a node from the graph along with edges associated with it
    /// </summary>
    /// <param name="t">The graph node</param>
    public void RemoveNode(ISymbolicExpressionTree t) {
      if (!_dictionary.ContainsKey(t))
        return;
      Node n = _dictionary[t];
      if (n.InEdges != null) {
        foreach (var e in n.InEdges.Where(e => e.Target.OutEdges != null)) {
          e.Target.OutEdges.RemoveAll(arc => arc.Target == n);
          if (!e.Target.OutEdges.Any())
            e.Target.OutEdges = null; // set to null to be a little more memory efficient
        }
        n.InEdges = null;
      }
      if (n.OutEdges != null) {
        foreach (var e in n.OutEdges.Where(e => e.Target.InEdges != null)) {
          e.Target.InEdges.RemoveAll(arc => arc.Target == n);
          if (!e.Target.OutEdges.Any())
            e.Target.InEdges = null; // set to null to be a little more memory efficient
        }
        n.OutEdges = null;
      }
      _dictionary.Remove(t);
    }

    public double AverageDegree {
      get { return Values.Average(x => x.Degree); }
    }

    /// <summary>
    /// Adds a graph arc from a to b
    /// </summary>
    /// <param name="a"></param>
    /// <param name="b"></param>
    /// <param name="label"></param>
    public void AddArc(ISymbolicExpressionTree a, ISymbolicExpressionTree b, string label) {
      Node src, dest;
      if (!HasNode(a)) {
        src = new Node { Data = a };
        _dictionary[a] = src;
      } else {
        src = _dictionary[a];
      }
      if (!HasNode(b)) {
        dest = new Node { Data = b };
        _dictionary[b] = dest;
      } else {
        dest = _dictionary[b];
      }
      // add forward and reverse arcs
      src.AddForwardArc(dest, label);
      dest.AddReverseArc(src, label);
    }

    public override IDeepCloneable Clone(Cloner cloner) {
      return new GenealogyGraph(this, cloner);
    }

    public override string ItemName {
      get { return "GenealogyGraph"; }
    }

    public override string ItemDescription {
      get { return "A graph describing the genealogies of all the individuals"; }
    }

    public new Version ItemVersion {
      get { return new Version(3, 3, 6); }
    }

    public new Image ItemImage {
      get { return Common.Resources.VSImageLibrary.Graph; }
    }
  }

  public class Node {
    public string Id { get; private set; }
    public string Label { get; set; }
    public bool IsElite { get; set; }
    public List<Arc> InEdges { get; set; }
    public List<Arc> OutEdges { get; set; }
    public object Data { get; set; }
    public double Quality { get; set; }

    public int Degree {
      get { return (InEdges == null ? 0 : InEdges.Count) + (OutEdges == null ? 0 : OutEdges.Count); }
    }

    public Node() {
      Id = Guid.NewGuid().ToString();
    }

    /// <summary>
    /// Returns a genealogical graph rooted in the current node, containing all ancestry information
    /// </summary>
    /// <returns></returns>
    public GenealogyGraph Genealogy() {
      var graph = new GenealogyGraph();
      graph.AddNode(this);
      foreach (var node in this.Ancestors())
        graph.AddNode(node);
      return graph;
    }

    /// <summary>
    /// Returns an enumerable of all the ancestors of the current node
    /// </summary>
    /// <returns></returns>
    public IEnumerable<Node> Ancestors() {
      var nodes = new HashSet<Node> { this };
      int offset = 0;
      int c0 = 1;
      while (offset != c0) {
        int c1 = c0;
        for (int i = offset; i != c1; ++i) {
          if (nodes.ElementAt(i).InEdges == null) continue;
          foreach (var p in nodes.ElementAt(i).InEdges.Select(e => e.Target)) {
            nodes.Add(p);
            yield return p;
          }
        }
        offset = c1;
        c0 = nodes.Count;
      }
    }

    public void AddForwardArc(Node target, string label) {
      var e = new Arc { Target = target, Label = label };
      if (OutEdges == null)
        OutEdges = new List<Arc> { e };
      else
        OutEdges.Add(e);
    }

    public void AddReverseArc(Node target, string label) {
      var e = new Arc { Target = target, Label = label };
      if (InEdges == null)
        InEdges = new List<Arc> { e };
      else
        InEdges.Add(e);
    }
  }

  /// <summary>
  /// An arc is an edge along with an orientation
  /// </summary>
  public class Arc {
    public Node Target { get; set; }
    public string Label { get; set; }
    public double Weight { get; set; }
    // other attributes
  }

  // an edge can be represented as a tuple<Node, Node> TODO: figure it out (might be useful for easier querying)
}