Changeset 7779 for branches/HeuristicLab.EvolutionaryTracking/HeuristicLab.EvolutionaryTracking/3.4/GenealogyGraph.cs

Timestamp:

05/03/12 12:26:11 (12 years ago)

Author:

bburlacu

Message:

#1772: Implemented new View, improved functionality (tracking of fragments and operators)

File:

• branches/HeuristicLab.EvolutionaryTracking/HeuristicLab.EvolutionaryTracking/3.4/GenealogyGraph.cs (modified) (12 diffs)

branches/HeuristicLab.EvolutionaryTracking/HeuristicLab.EvolutionaryTracking/3.4/GenealogyGraph.cs

@@ -1 @@
-using System;
+#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;
@@ -8 +29 @@
 
 namespace HeuristicLab.EvolutionaryTracking {
-  public class GenealogyGraph : NamedItem {
-    private readonly Dictionary<object, Node> _dictionary;
+  [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> _dictionary;
 
     public GenealogyGraph() {
-      _dictionary = new Dictionary<object, Node>();
-    }
-
-    public GenealogyGraph(GenealogyGraph g) {
-      _dictionary = new Dictionary<object, Node>(g._dictionary);
+      _dictionary = new Dictionary<T, GenealogyGraphNode>();
+    }
+
+    public GenealogyGraph(GenealogyGraph<T> g) {
+      _dictionary = new Dictionary<T, GenealogyGraphNode>(g._dictionary);
     }
 
     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 {
+      return new GenealogyGraph<T>(this, cloner);
+    }
+
+    public override Image ItemImage {
       get { return Common.Resources.VSImageLibrary.Graph; }
     }
@@ -44 +54 @@
     }
 
-    private GenealogyGraph(GenealogyGraph original, Cloner cloner)
+    private GenealogyGraph(GenealogyGraph<T> original, Cloner cloner)
       : base(original, cloner) {
-      _dictionary = new Dictionary<object, Node>(original._dictionary);
-    }
-
-    public bool HasNode(object t) {
+      _dictionary = new Dictionary<T, GenealogyGraphNode>(original._dictionary);
+    }
+
+    public bool HasNode(T t) {
       return _dictionary.ContainsKey(t);
     }
 
-    public Node GetNode(object t) {
-      return this.HasNode(t) ? _dictionary[t] : null;
-    }
-
-    public IEnumerable<object> Keys {
+    public GenealogyGraphNode GetNode(T t) {
+      return HasNode(t) ? _dictionary[t] : null;
+    }
+
+    public IEnumerable<T> Keys {
       get { return _dictionary.Keys; }
     }
 
-    public IEnumerable<Node> Values {
+    public IEnumerable<GenealogyGraphNode> Values {
       get { return _dictionary.Values; }
     }
 
-    public bool Any() {
-      return _dictionary.Any();
-    }
-
-    public bool Any(Func<KeyValuePair<object, Node>, bool> predicate) {
+    public bool IsEmpty {
+      get { return !_dictionary.Any(); }
+    }
+
+    public bool Any(Func<KeyValuePair<T, GenealogyGraphNode>, bool> predicate) {
       return _dictionary.Any(predicate);
     }
@@ -81 +91 @@
     /// </summary>
     /// <param name="t">The symbolic expression tree</param>
-    /// <param name="q">The quality value </param>
-    /// <param name="l">The node label</param>
+    /// <param name="quality">The quality value </param>
+    /// <param name="label">The node label</param>
+    /// <param name="rank">The node rank</param>
     /// <param name="elite">Specifies if this node is an elite</param>
-    public void AddNode(object t, double q = 0.0, string l = "", double g = 0, bool elite = false) {
+    public void AddNode(T t, double quality = 0.0, string label = "", double rank = 0, bool elite = false, int cutIndex = -1) {
       if (HasNode(t)) return;
-      var color = new Color { R = (byte)(255 - 255 * q), G = (byte)(255 * q), B = 50 };
-      _dictionary[t] = new Node { Data = t, Quality = q, Label = l, IsElite = elite, Rank = g, Color = color };
+      _dictionary[t] = new GenealogyGraphNode { Data = t, Quality = quality, Label = label, IsElite = elite, Rank = rank, CutpointIndex = cutIndex };
     }
 
@@ -93 +103 @@
     ///  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 = n.Data;
-      if (HasNode(t))
-        return;
+    /// <param name="n">The node to be added</param>
+    public void AddNode(GenealogyGraphNode n) {
+      var t = (T)n.Data;
+      if (HasNode(t)) return;
       _dictionary[t] = n;
     }
@@ -105 +114 @@
     /// </summary>
     /// <param name="t">The graph node</param>
-    public void RemoveNode(object t) {
-      if (!_dictionary.ContainsKey(t))
-        return;
-      Node n = _dictionary[t];
+    public void RemoveNode(T t) {
+      if (!_dictionary.ContainsKey(t)) return;
+      GenealogyGraphNode n = _dictionary[t];
       if (n.InEdges != null) {
         foreach (var e in n.InEdges.Where(e => e.Target.OutEdges != null)) {
@@ -138 +146 @@
     /// <param name="b"></param>
     /// <param name="label"></param>
-    public void AddArc(object a, object b, string label = "") {
-      Node src, dest;
+    public void AddArc(T a, T b, int opType = 0) {
+      GenealogyGraphNode src, dest;
       if (!HasNode(a)) {
-        src = new Node { Data = a };
+        src = new GenealogyGraphNode { Data = a };
         _dictionary[a] = src;
       } else {
@@ -147 +155 @@
       }
       if (!HasNode(b)) {
-        dest = new Node { Data = b };
+        dest = new GenealogyGraphNode { Data = b };
         _dictionary[b] = dest;
       } else {
@@ -153 +161 @@
       }
       // add forward and reverse arcs
-      src.AddForwardArc(dest, label);
-      dest.AddReverseArc(src, label);
-    }
-
-    public void AddArcs(object[] a, object b, string label) {
-      Node src, dest;
+      src.AddForwardArc(dest, opType);
+      dest.AddReverseArc(src, opType);
+    }
+
+    public void AddArcs(T[] a, T b, int opType = 0) {
+      GenealogyGraphNode src, dest;
       if (!HasNode(b)) {
-        dest = new Node { Data = b };
+        dest = new GenealogyGraphNode { Data = b };
         _dictionary[b] = dest;
       } else {
@@ -167 +175 @@
       foreach (var o in a) {
         if (!HasNode(o)) {
-          src = new Node { Data = o };
+          src = new GenealogyGraphNode { Data = o };
           _dictionary[o] = src;
         } else {
           src = _dictionary[o];
         }
-        src.AddForwardArc(dest, label);
-        dest.AddReverseArc(src, label);
+        src.AddForwardArc(dest, opType);
+        dest.AddReverseArc(src, opType);
       }
     }
   }
 
-  public class Node {
+  public class GenealogyGraphNode : IComparable {
     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 double Rank { get; set; }
-    public Color Color { get; set; }
-
-    public int Degree {
-      get { return (InEdges == null ? 0 : InEdges.Count) + (OutEdges == null ? 0 : OutEdges.Count); }
-    }
-
-    public Node() {
+    public int CutpointIndex { get; set; }
+    public List<GenealogyGraphArc> InEdges { get; set; }
+    public List<GenealogyGraphArc> OutEdges { get; set; }
+
+    public int Degree { get { return (InEdges == null ? 0 : InEdges.Count) + (OutEdges == null ? 0 : OutEdges.Count); } }
+
+    public GenealogyGraphNode() { Id = Guid.NewGuid().ToString(); }
+
+    public GenealogyGraphNode(GenealogyGraphNode node) {
       Id = Guid.NewGuid().ToString();
-    }
-
-    /// <summary>
-    /// Returns a genealogical graph rooted in the current node, containing all ancestry information
+      Rank = node.Rank;
+      Quality = node.Quality;
+      IsElite = node.IsElite;
+      Label = node.Label;
+      Data = node.Data;
+      InEdges = node.InEdges;
+      OutEdges = node.OutEdges;
+      CutpointIndex = node.CutpointIndex;
+    }
+
+    /// <summary>
+    /// Returns all the ancestors of the current node
     /// </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 };
+    public IEnumerable<GenealogyGraphNode> Ancestors() {
+      var nodes = new HashSet<GenealogyGraphNode> { this };
       int offset = 0;
       int c0 = 1;
@@ -231 +235 @@
     }
 
-    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>
+    /// Returns all the descendants of the current node (identical to above method except for using the OutEdges)
+    /// </summary>
+    /// <returns></returns>
+    public IEnumerable<GenealogyGraphNode> Descendants() {
+      var nodes = new HashSet<GenealogyGraphNode> { this };
+      int offset = 0;
+      int c0 = 1;
+      while (offset != c0) {
+        int c1 = c0;
+        for (int i = offset; i != c1; ++i) {
+          if (nodes.ElementAt(i).OutEdges == null) continue;
+          foreach (var p in nodes.ElementAt(i).OutEdges.Select(e => e.Target)) {
+            nodes.Add(p);
+            yield return p;
+          }
+        }
+        offset = c1;
+        c0 = nodes.Count;
+      }
+    }
+
+    public void AddForwardArc(GenealogyGraphNode target, int opType) {
+      var e = new GenealogyGraphArc { Target = target, OperatorType = opType };
+      if (OutEdges == null) OutEdges = new List<GenealogyGraphArc> { e };
+      else OutEdges.Add(e);
+    }
+
+    public void AddReverseArc(GenealogyGraphNode target, int opType) {
+      var e = new GenealogyGraphArc { Target = target, OperatorType = opType };
+      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);
     }
   }
@@ -251 +287 @@
   /// 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)
-
-  public struct Color {
-    public byte R { get; set; }
-    public byte G { get; set; }
-    public byte B { get; set; }
+  public class GenealogyGraphArc {
+    public GenealogyGraphNode Target { get; set; }
+    // OperationType is an identifier for the genetic operation (mutation, crossover) that a graph arc will represent 
+    // So basically it describes which operator was applied to an individual/graph node (the one emitting the arc), 
+    // while Target represents the end result of that operator (node ==GeneticOperation==> Target)
+    public int OperatorType { 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
   }
 }