Changeset 7799 for branches/HeuristicLab.EvolutionaryTracking/HeuristicLab.EvolutionaryTracking

Timestamp:

05/11/12 17:29:55 (12 years ago)

Author:

bburlacu

Message:

#1772: Sanitized IGenealogyGraph interface, implemented new graph arc semantics (an arc signifies an interaction between the two nodes that it connects and has a data object containing specific information about the interaction).

Location:

branches/HeuristicLab.EvolutionaryTracking/HeuristicLab.EvolutionaryTracking/3.4

Files:

• Analyzers/SymbolicExpressionTreeFragmentsAnalyzer.cs (modified) (1 diff)
• Analyzers/SymbolicExpressionTreeGenealogyAnalyzer.cs (modified) (8 diffs)
• GenealogyGraph.cs (modified) (14 diffs)
• Interfaces/IGenealogyGraph.cs (modified) (1 diff)

branches/HeuristicLab.EvolutionaryTracking/HeuristicLab.EvolutionaryTracking/3.4/Analyzers/SymbolicExpressionTreeFragmentsAnalyzer.cs

@@ -236 +236 @@
           GlobalCloneMap.Clear();
           GlobalTraceMap.Clear();
-        }
-        GlobalFragmentMap.Clear();
+          GlobalFragmentMap.Clear();
+        }
       }
       return base.Apply();

branches/HeuristicLab.EvolutionaryTracking/HeuristicLab.EvolutionaryTracking/3.4/Analyzers/SymbolicExpressionTreeGenealogyAnalyzer.cs

@@ -21 +21 @@
 
 using System;
+using System.Collections.Generic;
 using System.Drawing;
 using System.Globalization;
@@ -57 +58 @@
     private const string GlobalTraceMapParameterName = "GlobalTraceMap";
     private const string GlobalCloneMapParameterName = "GlobalCloneMap";
+    private const string GlobalFragmentMapParameterName = "GlobalFragmentMap";
     private const string PopulationGraphResultParameterName = "PopulationGraph";
     private const string PopulationGraphResultParameterDescription = "Individual lineages";
@@ -105 +107 @@
       get { return (LookupParameter<CloneMapType>)Parameters[GlobalCloneMapParameterName]; }
     }
+    public LookupParameter<CloneMapType> GlobalFragmentMapParameter {
+      get { return (LookupParameter<CloneMapType>)Parameters[GlobalFragmentMapParameterName]; }
+    }
     #endregion
 
@@ -140 +145 @@
     public TraceMapType GlobalTraceMap {
       get { return GlobalTraceMapParameter.ActualValue; }
+    }
+    public CloneMapType GlobalFragmentMap {
+      get { return GlobalFragmentMapParameter.ActualValue; }
     }
     public SymbolicDataAnalysisExpressionTreeInterpreter SymbolicExpressionInterpreter {
@@ -173 +181 @@
       Parameters.Add(new LookupParameter<TraceMapType>(GlobalTraceMapParameterName, "A global cache containing the whole genealogy."));
       Parameters.Add(new LookupParameter<CloneMapType>(GlobalCloneMapParameterName, "A global map keeping track of trees and their clones (made during selection)."));
+      Parameters.Add(new LookupParameter<CloneMapType>(GlobalFragmentMapParameterName, "A global map keeping track of tree fragments received via crossover."));
       Parameters.Add(new ValueLookupParameter<ResultCollection>(ResultsParameterName, "The results collection where the analysis values should be stored."));
       Parameters.Add(new LookupParameter<SymbolicDataAnalysisExpressionTreeInterpreter>(SymbolicExpressionInterpreterParameterName, "Interpreter for symbolic expression trees"));
@@ -236 +245 @@
             var tree = qualities.ElementAt(i).Key;
             label = (i + 1).ToString(CultureInfo.InvariantCulture);
-            graph.AddNode(tree, qualities[tree], label, generation, i < Elites.Value);
+            var node = new GenealogyGraphNode(tree) { Quality = qualities[tree], Label = label, Rank = generation, IsElite = i < Elites.Value };
+            graph.AddNode(node);
           }
           return base.Apply();
@@ -245 +255 @@
           var child = qualities.ElementAt(i).Key;
           label = (generation * qualities.Count + i + 1).ToString(CultureInfo.InvariantCulture);
-          if (!graph.HasNode(child))
-            graph.AddNode(child, qualities[child], label, generation, i < Elites.Value);
+          if (!graph.HasNode(child)) {
+            var node = new GenealogyGraphNode(child) { Quality = qualities[child], Label = label, Rank = generation, IsElite = i < Elites.Value };
+            graph.AddNode(node);
+          }
           if (!GlobalTraceMap.ContainsKey(child)) continue;
-          var parents = GlobalTraceMap[child];
+          var parents = GlobalTraceMap[child].Cast<ISymbolicExpressionTree>();
 
           foreach (var parent in parents) {
+            object data;
             if (GlobalTraceMap.ContainsKey(parent)) {
-              double quality = Evaluate((ISymbolicExpressionTree)parent);
-              graph.AddNode((ISymbolicExpressionTree)parent, quality, "", generation - 0.5);
-              var pp = GlobalTraceMap[parent];
+              double quality = Evaluate(parent);
+              var node = new GenealogyGraphNode(parent) { Quality = quality, Label = "", Rank = generation - 0.5 };
+              graph.AddNode(node);
+              var pp = GlobalTraceMap[parent].Cast<ISymbolicExpressionTree>();
               foreach (var p in pp) {
-                graph.AddArc((ISymbolicExpressionTree)p, (ISymbolicExpressionTree)parent);
+                data = ((List<ISymbolicExpressionTreeNode>)parent.IterateNodesBreadth())[((IntValue)GlobalFragmentMap[parent]).Value];
+                graph.AddArc(p, parent, data);
               }
             }
-            graph.AddArc((ISymbolicExpressionTree)parent, child);
+            data = ((List<ISymbolicExpressionTreeNode>)child.IterateNodesBreadth())[((IntValue)GlobalFragmentMap[child]).Value];
+            graph.AddArc(parent, child, data);
           }
         }
@@ -267 +283 @@
           GlobalTraceMap.Clear();
           GlobalCloneMap.Clear();
+          GlobalFragmentMap.Clear();
         }
 

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

@@ -31 +31 @@
   [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;
+    private readonly Dictionary<T, GenealogyGraphNode> _nodes;
 
     public GenealogyGraph() {
-      _dictionary = new Dictionary<T, GenealogyGraphNode>();
+      _nodes = new Dictionary<T, GenealogyGraphNode>();
     }
 
     public GenealogyGraph(GenealogyGraph<T> g) {
-      _dictionary = new Dictionary<T, GenealogyGraphNode>(g._dictionary);
+      _nodes = new Dictionary<T, GenealogyGraphNode>(g._nodes);
     }
 
@@ -56 +56 @@
     private GenealogyGraph(GenealogyGraph<T> original, Cloner cloner)
       : base(original, cloner) {
-      _dictionary = new Dictionary<T, GenealogyGraphNode>(original._dictionary);
-    }
-
-    public bool HasNode(T t) {
-      return _dictionary.ContainsKey(t);
-    }
-
-    public GenealogyGraphNode GetNode(T t) {
-      return HasNode(t) ? _dictionary[t] : null;
-    }
-
-    public IEnumerable<T> Keys {
-      get { return _dictionary.Keys; }
-    }
-
-    public IEnumerable<GenealogyGraphNode> Values {
-      get { return _dictionary.Values; }
-    }
-
-    public bool IsEmpty {
-      get { return !_dictionary.Any(); }
-    }
-
-    public bool Any(Func<KeyValuePair<T, GenealogyGraphNode>, bool> predicate) {
-      return _dictionary.Any(predicate);
-    }
-
-    public void Clear() {
-      _dictionary.Clear();
-    }
+      _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 symbolic expression tree</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(T t, double quality = 0.0, string label = "", double rank = 0, bool elite = false) {
+    /// <param name="t">The data this node is supposed to represent in the graph</param>
+    public void AddNode(T t) {
       if (HasNode(t)) return;
-      _dictionary[t] = new GenealogyGraphNode { Data = t, Quality = quality, Label = label, IsElite = elite, Rank = rank };
+      _nodes[t] = new GenealogyGraphNode(t) { Quality = 0.0, Label = "", IsElite = false, Rank = 0.0 };
     }
 
@@ -107 +83 @@
       var t = (T)node.Data;
       if (HasNode(t)) return;
-      _dictionary[t] = node;
+      _nodes[t] = node;
     }
 
@@ -115 +91 @@
     /// <param name="t">The graph node</param>
     public void RemoveNode(T t) {
-      if (!_dictionary.ContainsKey(t)) return;
-      var node = _dictionary[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.Any())
+          if (e.Target.OutEdges.Count == 0)
             e.Target.OutEdges = null; // set to null to be a little more memory efficient
         }
@@ -128 +104 @@
         foreach (var e in node.OutEdges.Where(e => e.Target.InEdges != null)) {
           e.Target.InEdges.RemoveAll(arc => arc.Target == node);
-          if (!e.Target.InEdges.Any())
+          if (e.Target.InEdges.Count == 0)
             e.Target.InEdges = null; // set to null to be a little more memory efficient
         }
         node.OutEdges = null;
       }
-      _dictionary.Remove(t);
+      _nodes.Remove(t);
     }
 
@@ -143 +119 @@
     /// Adds a graph arc from a to b
     /// </summary>
-    /// <param name="a"></param>
-    /// <param name="b"></param>
-    public void AddArc(T a, T b) {
+    /// <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(a)) {
-        src = new GenealogyGraphNode { Data = a };
-        _dictionary[a] = src;
+      if (!HasNode(obj1)) {
+        src = new GenealogyGraphNode(obj1);
+        _nodes[obj1] = src;
       } else {
-        src = _dictionary[a];
-      }
-      if (!HasNode(b)) {
-        dest = new GenealogyGraphNode { Data = b };
-        _dictionary[b] = dest;
+        src = _nodes[obj1];
+      }
+      if (!HasNode(obj2)) {
+        dest = new GenealogyGraphNode(obj2);
+        _nodes[obj2] = dest;
       } else {
-        dest = _dictionary[b];
+        dest = _nodes[obj2];
       }
       // add forward and reverse arcs
@@ -164 +140 @@
     }
 
-    public void AddArcs(T[] a, T b) {
-      GenealogyGraphNode src, dest;
-      if (!HasNode(b)) {
-        dest = new GenealogyGraphNode { Data = b };
-        _dictionary[b] = dest;
-      } else {
-        dest = _dictionary[b];
-      }
-      foreach (var o in a) {
-        if (!HasNode(o)) {
-          src = new GenealogyGraphNode { Data = o };
-          _dictionary[o] = src;
-        } else {
-          src = _dictionary[o];
-        }
-        src.AddForwardArc(dest);
-        dest.AddReverseArc(src);
-      }
-    }
+    //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);
+    //  }
+    //}
   }
 
@@ -189 +165 @@
     public string Label { get; set; }
     public bool IsElite { get; set; }
-    public object Data { 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() { Id = Guid.NewGuid().ToString(); }
+    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) {
@@ -206 +198 @@
       Label = node.Label;
       Data = node.Data;
-      InEdges = node.InEdges;
-      OutEdges = node.OutEdges;
+      InEdges = new List<GenealogyGraphArc>(node.InEdges);
+      OutEdges = new List<GenealogyGraphArc>(node.OutEdges);
     }
 
@@ -216 +208 @@
     public IEnumerable<GenealogyGraphNode> Ancestors() {
       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).InEdges == null) continue;
+      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);
@@ -227 +216 @@
           }
         }
-        offset = c1;
-        c0 = nodes.Count;
+        ++i;
       }
     }
@@ -238 +226 @@
     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;
+      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);
@@ -249 +234 @@
           }
         }
-        offset = c1;
-        c0 = nodes.Count;
-      }
-    }
-
-    public void AddForwardArc(GenealogyGraphNode target) {
-      var e = new GenealogyGraphArc { Target = target };
+        ++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) {
-      var e = new GenealogyGraphArc { Target = target };
+    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);
@@ -289 +276 @@
     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; }
   }
 }

branches/HeuristicLab.EvolutionaryTracking/HeuristicLab.EvolutionaryTracking/3.4/Interfaces/IGenealogyGraph.cs

@@ -30 +30 @@
     bool Any(Func<KeyValuePair<T, GenealogyGraphNode>, bool> predicate); // graph contains any nodes matching the given predicate?
     void Clear(); // clear graph
-    void AddNode(T t, double quality = 0.0, string label = "", double rank = 0, bool elite = false);
+    void AddNode(T t);
     void RemoveNode(T t); // remove node if contained in the graph
     GenealogyGraphNode GetNode(T t); // return node corresponding to object t, or null
     // arc operation
-    void AddArc(T source, T target);
-    void AddArcs(T[] a, T b);
+    void AddArc(T source, T target, object sourceData = null, object targetData = null);
+    //void AddArcs(T[] a, T b);
   }
 }