Changeset 8555

Timestamp:

09/03/12 14:58:39 (12 years ago)

Author:

bburlacu

Message:

#1772: Introduced more specific graph class for symbolic expression problems.

Location:

branches/HeuristicLab.EvolutionaryTracking/HeuristicLab.EvolutionaryTracking/3.4

Files:

• GenealogyGraph.cs (modified) (4 diffs)
• GenealogyGraphArc.cs (added)
• GenealogyGraphNode.cs (added)
• Interfaces/IGenealogyGraph.cs (modified) (1 diff)
• Interfaces/IGenealogyGraphNode.cs (added)
• Interfaces/ISymbolicExpressionTreeGenealogyGraph.cs (added)
• SymbolicExpressionTreeGenealogyGraph.cs (modified) (2 diffs)

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

@@ -31 +31 @@
   [Item("Genealogy graph", "Generic class for tracking the evolution of objects.")]
   [StorableClass]
-  public class GenealogyGraph<T> : NamedItem, IGenealogyGraph<T> where T : class {
-    [Storable]
-    private readonly Dictionary<T, GenealogyGraphNode> _nodes;
-    private readonly Dictionary<GenealogyGraphNode, List<double>> _nodeRanks;
+  public class GenealogyGraph<T> : NamedItem, IGenealogyGraph<T> where T : GenealogyGraphNode {
+    private readonly List<T> nodes; // graph will consist of a set of nodes of type T
+    public List<T> Nodes {
+      get { return nodes; }
+    }
 
     public GenealogyGraph() {
-      _nodes = new Dictionary<T, GenealogyGraphNode>();
-      _nodeRanks = new Dictionary<GenealogyGraphNode, List<double>>();
+      nodes = new List<T>();
     }
 
     public GenealogyGraph(GenealogyGraph<T> g) {
-      _nodes = new Dictionary<T, GenealogyGraphNode>(g._nodes);
-      _nodeRanks = new Dictionary<GenealogyGraphNode, List<double>>(g._nodeRanks);
+      nodes = new List<T>(g.Nodes);
     }
 
@@ -61 +60 @@
     protected GenealogyGraph(GenealogyGraph<T> original, Cloner cloner)
       : base(original, cloner) {
-      _nodes = new Dictionary<T, GenealogyGraphNode>(original._nodes);
+      nodes = new List<T>();
     }
 
-    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(); }
+    public virtual bool HasNode(T t) {
+      return nodes.Contains(t);
+    }
+
+    public virtual GenealogyGraphNode GetNode(T t) {
+      var node = Nodes.First(x => x == t);
+      return node;
+    }
+
+    public virtual bool IsEmpty {
+      get { return !nodes.Any(); }
+    }
+
+    public virtual bool Any(Func<T, bool> predicate) {
+      return nodes.Any(predicate);
+    }
+
+    public virtual void Clear() {
+      nodes.Clear();
+    }
 
     /// <summary>
     /// Adds a node representing an individual
     /// </summary>
-    /// <param name="tree">The data this node is supposed to represent in the graph</param>
-    public virtual void AddNode(T tree) {
-      if (HasNode(tree)) return;
-      _nodes[tree] = new GenealogyGraphNode(tree);
-    }
-
-    /// <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 virtual void AddNode(GenealogyGraphNode node) {
-      var t = (T)node.Data;
-      if (HasNode(t))
-        return;
-      _nodes[t] = node;
+    /// <param name="node">The node to add</param>
+    public virtual void AddNode(T node) {
+      Nodes.Add(node);
     }
 
@@ -96 +96 @@
     /// </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 virtual void RemoveNode(T t) {
+      Nodes.Remove(t);
     }
 
     public double AverageDegree {
-      get { return Values.Average(x => x.Degree); }
+      get { return Nodes.Average(x => x.Degree); }
     }
 
@@ -127 +109 @@
     /// <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 virtual void AddArc(T srcNode, T destNode, object data1 = null, object data2 = null) {
+      if (srcNode == null || destNode == null) return;
+      srcNode.AddForwardArc(destNode, data1);
+      destNode.AddReverseArc(srcNode, data2);
     }
   }
-
-  public class GenealogyGraphNode {
-    public string Id { get; private set; }
-    public string Label { 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();
-      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() {
-      // for performance, we use a hashset for lookup and a list for iteration
-      var nodes = new HashSet<GenealogyGraphNode> { this };
-      var list = new List<GenealogyGraphNode> { this };
-      int i = 0;
-      while (i != list.Count) {
-        if (list[i].InEdges != null) {
-          foreach (var e in list[i].InEdges) {
-            if (nodes.Contains(e.Target)) continue;
-            nodes.Add(e.Target);
-            list.Add(e.Target);
-          }
-        }
-        ++i;
-      }
-      return list;
-    }
-
-    /// <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 };
-      var list = new List<GenealogyGraphNode> { this };
-      int i = 0;
-      while (i != list.Count) {
-        if (list[i].OutEdges != null) {
-          foreach (var e in list[i].OutEdges) {
-            if (nodes.Contains(e.Target)) continue;
-            nodes.Add(e.Target);
-            list.Add(e.Target);
-          }
-        }
-        ++i;
-      }
-      return list;
-    }
-
-    // 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);
-    }
-  }
-
-  /// <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; }
-  }
 }

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

@@ -21 +21 @@
 
 using System;
-using System.Collections.Generic;
 using HeuristicLab.Core;
 
 namespace HeuristicLab.EvolutionaryTracking {
   public interface IGenealogyGraph<T> : INamedItem where T : class {
-    // node/vertex operations
     bool HasNode(T t); // graph contains specific node?
-    bool Any(Func<KeyValuePair<T, GenealogyGraphNode>, bool> predicate); // graph contains any nodes matching the given predicate?
+    bool Any(Func<T, bool> predicate); // graph contains any nodes matching the given predicate?
     void Clear(); // clear graph
-    void AddNode(T t);
+    void AddNode(T nodeData);
     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
+    GenealogyGraphNode GetNode(T t); // return node corresponding to object nodeData, or null
     void AddArc(T source, T target, object sourceData = null, object targetData = null);
-    //void AddArcs(T[] a, T b);
   }
 }

branches/HeuristicLab.EvolutionaryTracking/HeuristicLab.EvolutionaryTracking/3.4/SymbolicExpressionTreeGenealogyGraph.cs

@@ -1 @@
-using System.Collections.Generic;
+#region License Information
+/* HeuristicLab
+ * Copyright (C) 2002-2012 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.Collections.Generic;
 using System.Linq;
 using HeuristicLab.Common;
@@ -10 +31 @@
   [Item("SymbolicExpressionTreeGenealogyGraph", "A genealogy graph for symbolic expression trees")]
   [StorableClass]
-  public class SymbolicExpressionTreeGenealogyGraph : GenealogyGraph<ISymbolicExpressionTree> {
+  public class SymbolicExpressionTreeGenealogyGraph : GenealogyGraph<SymbolicExpressionGenealogyGraphNode>, ISymbolicExpressionTreeGenealogyGraph {
+    [Storable]
+    private readonly Dictionary<ISymbolicExpressionTree, List<SymbolicExpressionGenealogyGraphNode>> nodeMap =
+      new Dictionary<ISymbolicExpressionTree, List<SymbolicExpressionGenealogyGraphNode>>();
 
-    [Storable]
-    private readonly Dictionary<GenealogyGraphNode, NodeMetadata> _nodeInfo = new Dictionary<GenealogyGraphNode, NodeMetadata>();
-
-    public SymbolicExpressionTreeGenealogyGraph() {
-    }
+    public SymbolicExpressionTreeGenealogyGraph() { }
 
     [StorableConstructor]
-    public SymbolicExpressionTreeGenealogyGraph(bool serializing)
-      : base(serializing) {
-    }
+    public SymbolicExpressionTreeGenealogyGraph(bool serializing) : base(serializing) { }
 
-    public override IDeepCloneable Clone(Cloner cloner) {
-      return new SymbolicExpressionTreeGenealogyGraph(this, cloner);
-    }
+    public override IDeepCloneable Clone(Cloner cloner) { return new SymbolicExpressionTreeGenealogyGraph(this, cloner); }
 
-    protected SymbolicExpressionTreeGenealogyGraph(SymbolicExpressionTreeGenealogyGraph original, Cloner cloner)
-      : base(original, cloner) {
-    }
+    protected SymbolicExpressionTreeGenealogyGraph(SymbolicExpressionTreeGenealogyGraph original, Cloner cloner) : base(original, cloner) { }
 
-    public override void AddNode(ISymbolicExpressionTree tree) {
-      if (HasNode(tree)) return;
-      var node = new GenealogyGraphNode(tree);
-      _nodeInfo[node] = new NodeMetadata();
+    public override void AddNode(SymbolicExpressionGenealogyGraphNode node) {
+      if (!nodeMap.ContainsKey(node.SymbolicExpressionTree))
+        nodeMap[node.SymbolicExpressionTree] = new List<SymbolicExpressionGenealogyGraphNode> { node };
+      else
+        nodeMap[node.SymbolicExpressionTree].Add(node);
       base.AddNode(node);
     }
 
-    public override void AddNode(GenealogyGraphNode node) {
-      var tree = (ISymbolicExpressionTree)node.Data;
-      if (HasNode(tree)) return;
-      _nodeInfo[node] = new NodeMetadata();
-      base.AddNode(node);
+    public List<SymbolicExpressionGenealogyGraphNode> GetGraphNodes(ISymbolicExpressionTree tree) {
+      return nodeMap.ContainsKey(tree) ? nodeMap[tree] : null;
     }
 
-    public NodeMetadata this[GenealogyGraphNode node] {
-      get {
-        NodeMetadata value;
-        _nodeInfo.TryGetValue(node, out value);
-        return value;
+    public bool HasNode(SymbolicExpressionTree tree) {
+      return Nodes.Any(x => x.SymbolicExpressionTree == tree);
+    }
+
+    public int Compare(GenealogyGraphNode a, GenealogyGraphNode b) {
+      return Compare(a as SymbolicExpressionGenealogyGraphNode, b as SymbolicExpressionGenealogyGraphNode);
+    }
+
+    // TODO: make sure a and b are valid and the info exists for both
+    public int Compare(SymbolicExpressionGenealogyGraphNode a, SymbolicExpressionGenealogyGraphNode b) {
+      if (a.Quality.Equals(b.Quality)) {
+        if (a.IsElite) return +1;
+        if (b.IsElite) return -1;
       }
-      set {
-        _nodeInfo[node] = value;
-      }
+      return a.Quality.CompareTo(b.Quality);
     }
 
     #region Fragment tracing
-    public IEnumerable<ISymbolicExpressionTree> TraceFragment(ISymbolicExpressionTreeNode fragment, int mode = 0) {
-      return Keys.Where(tree => tree.ContainsFragment(fragment, mode));
+    public IEnumerable<ISymbolicExpressionTree> TraceFragment(ISymbolicExpressionTreeNode fragment, SimilarityLevel similarity = SimilarityLevel.Exact) {
+      return Nodes.Where(x => x.SymbolicExpressionTree.ContainsFragment(fragment, similarity)).Select(x => x.SymbolicExpressionTree).ToList();
     }
     #endregion
   }
 
-  public class NodeMetadata {
+  public class SymbolicExpressionGenealogyGraphNode : GenealogyGraphNode {
+    public ISymbolicExpressionTree SymbolicExpressionTree { get; set; }
     public double Quality { get; set; }
+    public bool IsElite { get; set; }
     public List<double> Ranks { get; set; }
-    public bool IsElite { get; set; }
 
-    public NodeMetadata() {
+    public SymbolicExpressionGenealogyGraphNode() {
+      Ranks = new List<double>();
+    }
+
+    public SymbolicExpressionGenealogyGraphNode(object content) {
+      Content = content;
       Ranks = new List<double>();
     }