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

#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.Linq;
using HeuristicLab.Common;
using HeuristicLab.Core;
using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;

namespace HeuristicLab.EvolutionaryTracking {
  [Item("Genealogy graph", "Generic class for tracking the evolution of objects.")]
  public class GenealogyGraph<T> : NamedItem, IGenealogyGraph<T> where T : class {
    private readonly Dictionary<T, GenealogyGraphNode> _nodes;

    public GenealogyGraph() {
      _nodes = new Dictionary<T, GenealogyGraphNode>();
    }

    public GenealogyGraph(GenealogyGraph<T> g) {
      _nodes = new Dictionary<T, GenealogyGraphNode>(g._nodes);
    }

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

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

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

    private GenealogyGraph(GenealogyGraph<T> original, Cloner cloner)
      : base(original, cloner) {
      _nodes = new Dictionary<T, GenealogyGraphNode>(original._nodes);
    }

    public bool HasNode(T t) { return _nodes.ContainsKey(t); }
    public GenealogyGraphNode GetNode(T t) { return HasNode(t) ? _nodes[t] : null; }
    public IEnumerable<T> Keys { get { return _nodes.Keys; } }
    public IEnumerable<GenealogyGraphNode> Values { get { return _nodes.Values; } }
    public bool IsEmpty { get { return !_nodes.Any(); } }
    public bool Any(Func<KeyValuePair<T, GenealogyGraphNode>, bool> predicate) { return _nodes.Any(predicate); }
    public void Clear() { _nodes.Clear(); }

    /// <summary>
    /// Adds a node representing an individual
    /// </summary>
    /// <param name="t">The data this node is supposed to represent in the graph</param>
    public void AddNode(T t) {
      if (HasNode(t)) return;
      _nodes[t] = new GenealogyGraphNode(t) { Quality = 0.0, Label = "", IsElite = false, Rank = 0.0 };
    }

    /// <summary>
    ///  more of a low level method to minimize memory usage when creating and returning subgraphs
    /// </summary>
    /// <param name="node">The node to be added</param>
    public void AddNode(GenealogyGraphNode node) {
      var t = (T)node.Data;
      if (HasNode(t)) return;
      _nodes[t] = node;
    }

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

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

    /// <summary>
    /// Adds a graph arc from a to b
    /// </summary>
    /// <param name="obj1"></param>
    /// <param name="obj2"></param>
    public void AddArc(T obj1, T obj2, object data1 = null, object data2 = null) {
      GenealogyGraphNode src, dest;
      if (!HasNode(obj1)) {
        src = new GenealogyGraphNode(obj1);
        _nodes[obj1] = src;
      } else {
        src = _nodes[obj1];
      }
      if (!HasNode(obj2)) {
        dest = new GenealogyGraphNode(obj2);
        _nodes[obj2] = dest;
      } else {
        dest = _nodes[obj2];
      }
      // add forward and reverse arcs
      src.AddForwardArc(dest, data1);
      dest.AddReverseArc(src, data2);
    }

    //public void AddArcs(T[] a, T b) {
    //  GenealogyGraphNode src, dest;
    //  if (!HasNode(b)) {
    //    dest = new GenealogyGraphNode(b);
    //    _nodes[b] = dest;
    //  } else {
    //    dest = _nodes[b];
    //  }
    //  foreach (var o in a) {
    //    if (!HasNode(o)) {
    //      src = new GenealogyGraphNode(o);
    //      _nodes[o] = src;
    //    } else {
    //      src = _nodes[o];
    //    }
    //    src.AddForwardArc(dest);
    //    dest.AddReverseArc(src);
    //  }
    //}
  }

  public class GenealogyGraphNode : IComparable {
    public string Id { get; private set; }
    public string Label { get; set; }
    public bool IsElite { get; set; }
    public double Quality { get; set; }
    public double Rank { get; set; }
    public List<GenealogyGraphArc> InEdges { get; set; }
    public List<GenealogyGraphArc> OutEdges { get; set; }
    private object _data;
    public object Data {
      get { return _data; }
      set {
        if (value == null)
          throw new ArgumentException("Node data cannot be null.");
        else {
          _data = value; // data must be of type T
        }
      }
    }

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

    public GenealogyGraphNode(object data) {
      if (data == null) {
        throw new ArgumentException("Node data cannot be null");
      }
      Id = Guid.NewGuid().ToString();
      Data = data;
    }

    public GenealogyGraphNode(GenealogyGraphNode node) {
      Id = Guid.NewGuid().ToString();
      Rank = node.Rank;
      Quality = node.Quality;
      IsElite = node.IsElite;
      Label = node.Label;
      Data = node.Data;
      InEdges = new List<GenealogyGraphArc>(node.InEdges);
      OutEdges = new List<GenealogyGraphArc>(node.OutEdges);
    }

    /// <summary>
    /// Performs an upward-breath-traversal of the genealogy graph using the nodes InEdges
    /// </summary>
    /// <returns>All the ancestors of the current node</returns>
    public IEnumerable<GenealogyGraphNode> Ancestors() {
      var nodes = new HashSet<GenealogyGraphNode> { this };
      int i = 0;
      while (i != nodes.Count) {
        if (nodes.ElementAt(i).InEdges != null) {
          foreach (var p in nodes.ElementAt(i).InEdges.Select(e => e.Target)) {
            nodes.Add(p);
            yield return p;
          }
        }
        ++i;
      }
    }

    /// <summary>
    /// Performs a downward-breath-traversal of the genealogy graph using the nodes OutEdges
    /// </summary>
    /// <returns>All the descendants of the current node</returns>
    public IEnumerable<GenealogyGraphNode> Descendants() {
      var nodes = new HashSet<GenealogyGraphNode> { this };
      int i = 0;
      while (i != nodes.Count) {
        if (nodes.ElementAt(i).OutEdges != null) {
          foreach (var p in nodes.ElementAt(i).OutEdges.Select(e => e.Target)) {
            nodes.Add(p);
            yield return p;
          }
        }
        ++i;
      }
    }

    // this method can be used to add arcs towards targets that are not visible in the graph 
    // (they do not appear in the _nodes Dictionary). It is the programmers responsibility to 
    // enforce the correct and desired behavior.
    public void AddForwardArc(GenealogyGraphNode target, object data = null) {
      var e = new GenealogyGraphArc { Target = target, Data = data };
      if (OutEdges == null) OutEdges = new List<GenealogyGraphArc> { e };
      else OutEdges.Add(e);
    }

    public void AddReverseArc(GenealogyGraphNode target, object data = null) {
      var e = new GenealogyGraphArc { Target = target, Data = data };
      if (InEdges == null) InEdges = new List<GenealogyGraphArc> { e };
      else InEdges.Add(e);
    }

    // comparable
    // may seem weird, it is actually implemented so higher quality means "less than" in terms of ordering
    // if quality is equal, the elite node takes precedence
    public int CompareTo(object obj) {
      if (obj == null) return 1;
      var other = obj as GenealogyGraphNode;
      if (other == null) return 1;
      if (Quality.Equals(other.Quality)) {
        if (IsElite) return -1;
        return other.IsElite ? 1 : -1;
      }
      return other.Quality.CompareTo(Quality);
    }
  }

  /// <summary>
  /// An arc is an edge along with an orientation
  /// </summary>
  public class GenealogyGraphArc {
    public GenealogyGraphNode Target { get; set; }
    // these two fields are not used, but they might be useful later 
    public string Label { get; set; } // might be useful later
    public double Weight { get; set; } // might be useful later
    // object used to embed information about node interactions into the arc that connects them (therefore a graph arc will encode a relationship/interaction)
    public object Data { get; set; }
  }
}