Changeset 8555


Ignore:
Timestamp:
09/03/12 14:58:39 (7 years ago)
Author:
bburlacu
Message:

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

Location:
branches/HeuristicLab.EvolutionaryTracking/HeuristicLab.EvolutionaryTracking/3.4
Files:
4 added
3 edited

Legend:

Unmodified
Added
Removed
  • branches/HeuristicLab.EvolutionaryTracking/HeuristicLab.EvolutionaryTracking/3.4/GenealogyGraph.cs

    r8248 r8555  
    3131  [Item("Genealogy graph", "Generic class for tracking the evolution of objects.")]
    3232  [StorableClass]
    33   public class GenealogyGraph<T> : NamedItem, IGenealogyGraph<T> where T : class {
    34     [Storable]
    35     private readonly Dictionary<T, GenealogyGraphNode> _nodes;
    36     private readonly Dictionary<GenealogyGraphNode, List<double>> _nodeRanks;
     33  public class GenealogyGraph<T> : NamedItem, IGenealogyGraph<T> where T : GenealogyGraphNode {
     34    private readonly List<T> nodes; // graph will consist of a set of nodes of type T
     35    public List<T> Nodes {
     36      get { return nodes; }
     37    }
    3738
    3839    public GenealogyGraph() {
    39       _nodes = new Dictionary<T, GenealogyGraphNode>();
    40       _nodeRanks = new Dictionary<GenealogyGraphNode, List<double>>();
     40      nodes = new List<T>();
    4141    }
    4242
    4343    public GenealogyGraph(GenealogyGraph<T> g) {
    44       _nodes = new Dictionary<T, GenealogyGraphNode>(g._nodes);
    45       _nodeRanks = new Dictionary<GenealogyGraphNode, List<double>>(g._nodeRanks);
     44      nodes = new List<T>(g.Nodes);
    4645    }
    4746
     
    6160    protected GenealogyGraph(GenealogyGraph<T> original, Cloner cloner)
    6261      : base(original, cloner) {
    63       _nodes = new Dictionary<T, GenealogyGraphNode>(original._nodes);
     62      nodes = new List<T>();
    6463    }
    6564
    66     public bool HasNode(T t) { return _nodes.ContainsKey(t); }
    67     public GenealogyGraphNode GetNode(T t) { return HasNode(t) ? _nodes[t] : null; }
    68     public IEnumerable<T> Keys { get { return _nodes.Keys; } }
    69     public IEnumerable<GenealogyGraphNode> Values { get { return _nodes.Values; } }
    70     public bool IsEmpty { get { return !_nodes.Any(); } }
    71     public bool Any(Func<KeyValuePair<T, GenealogyGraphNode>, bool> predicate) { return _nodes.Any(predicate); }
    72     public void Clear() { _nodes.Clear(); }
     65    public virtual bool HasNode(T t) {
     66      return nodes.Contains(t);
     67    }
     68
     69    public virtual GenealogyGraphNode GetNode(T t) {
     70      var node = Nodes.First(x => x == t);
     71      return node;
     72    }
     73
     74    public virtual bool IsEmpty {
     75      get { return !nodes.Any(); }
     76    }
     77
     78    public virtual bool Any(Func<T, bool> predicate) {
     79      return nodes.Any(predicate);
     80    }
     81
     82    public virtual void Clear() {
     83      nodes.Clear();
     84    }
    7385
    7486    /// <summary>
    7587    /// Adds a node representing an individual
    7688    /// </summary>
    77     /// <param name="tree">The data this node is supposed to represent in the graph</param>
    78     public virtual void AddNode(T tree) {
    79       if (HasNode(tree)) return;
    80       _nodes[tree] = new GenealogyGraphNode(tree);
    81     }
    82 
    83     /// <summary>
    84     ///  more of a low level method to minimize memory usage when creating and returning subgraphs
    85     /// </summary>
    86     /// <param name="node">The node to be added</param>
    87     public virtual void AddNode(GenealogyGraphNode node) {
    88       var t = (T)node.Data;
    89       if (HasNode(t))
    90         return;
    91       _nodes[t] = node;
     89    /// <param name="node">The node to add</param>
     90    public virtual void AddNode(T node) {
     91      Nodes.Add(node);
    9292    }
    9393
     
    9696    /// </summary>
    9797    /// <param name="t">The graph node</param>
    98     public void RemoveNode(T t) {
    99       if (!_nodes.ContainsKey(t)) return;
    100       var node = _nodes[t];
    101       if (node.InEdges != null) {
    102         foreach (var e in node.InEdges.Where(e => e.Target.OutEdges != null)) {
    103           e.Target.OutEdges.RemoveAll(arc => arc.Target == node);
    104           if (e.Target.OutEdges.Count == 0)
    105             e.Target.OutEdges = null; // set to null to be a little more memory efficient
    106         }
    107         node.InEdges = null;
    108       }
    109       if (node.OutEdges != null) {
    110         foreach (var e in node.OutEdges.Where(e => e.Target.InEdges != null)) {
    111           e.Target.InEdges.RemoveAll(arc => arc.Target == node);
    112           if (e.Target.InEdges.Count == 0)
    113             e.Target.InEdges = null; // set to null to be a little more memory efficient
    114         }
    115         node.OutEdges = null;
    116       }
    117       _nodes.Remove(t);
     98    public virtual void RemoveNode(T t) {
     99      Nodes.Remove(t);
    118100    }
    119101
    120102    public double AverageDegree {
    121       get { return Values.Average(x => x.Degree); }
     103      get { return Nodes.Average(x => x.Degree); }
    122104    }
    123105
     
    127109    /// <param name="obj1"></param>
    128110    /// <param name="obj2"></param>
    129     public void AddArc(T obj1, T obj2, object data1 = null, object data2 = null) {
    130       GenealogyGraphNode src, dest;
    131       if (!HasNode(obj1)) {
    132         src = new GenealogyGraphNode(obj1);
    133         _nodes[obj1] = src;
    134       } else {
    135         src = _nodes[obj1];
    136       }
    137       if (!HasNode(obj2)) {
    138         dest = new GenealogyGraphNode(obj2);
    139         _nodes[obj2] = dest;
    140       } else {
    141         dest = _nodes[obj2];
    142       }
    143       // add forward and reverse arcs
    144       src.AddForwardArc(dest, data1);
    145       dest.AddReverseArc(src, data2);
     111    public virtual void AddArc(T srcNode, T destNode, object data1 = null, object data2 = null) {
     112      if (srcNode == null || destNode == null) return;
     113      srcNode.AddForwardArc(destNode, data1);
     114      destNode.AddReverseArc(srcNode, data2);
    146115    }
    147116  }
    148 
    149   public class GenealogyGraphNode {
    150     public string Id { get; private set; }
    151     public string Label { get; set; }
    152     public List<GenealogyGraphArc> InEdges { get; set; }
    153     public List<GenealogyGraphArc> OutEdges { get; set; }
    154     private object _data;
    155     public object Data {
    156       get { return _data; }
    157       set {
    158         if (value == null)
    159           throw new ArgumentException("Node data cannot be null.");
    160         else {
    161           _data = value; // data must be of type T
    162         }
    163       }
    164     }
    165 
    166     public int Degree { get { return (InEdges == null ? 0 : InEdges.Count) + (OutEdges == null ? 0 : OutEdges.Count); } }
    167 
    168     public GenealogyGraphNode(object data) {
    169       if (data == null) {
    170         throw new ArgumentException("Node data cannot be null");
    171       }
    172       Id = Guid.NewGuid().ToString();
    173       Data = data;
    174     }
    175 
    176     public GenealogyGraphNode(GenealogyGraphNode node) {
    177       Id = Guid.NewGuid().ToString();
    178       Label = node.Label;
    179       Data = node.Data;
    180       InEdges = new List<GenealogyGraphArc>(node.InEdges);
    181       OutEdges = new List<GenealogyGraphArc>(node.OutEdges);
    182     }
    183 
    184     /// <summary>
    185     /// Performs an upward-breath-traversal of the genealogy graph using the nodes InEdges
    186     /// </summary>
    187     /// <returns>All the ancestors of the current node</returns>
    188     public IEnumerable<GenealogyGraphNode> Ancestors() {
    189       // for performance, we use a hashset for lookup and a list for iteration
    190       var nodes = new HashSet<GenealogyGraphNode> { this };
    191       var list = new List<GenealogyGraphNode> { this };
    192       int i = 0;
    193       while (i != list.Count) {
    194         if (list[i].InEdges != null) {
    195           foreach (var e in list[i].InEdges) {
    196             if (nodes.Contains(e.Target)) continue;
    197             nodes.Add(e.Target);
    198             list.Add(e.Target);
    199           }
    200         }
    201         ++i;
    202       }
    203       return list;
    204     }
    205 
    206     /// <summary>
    207     /// Performs a downward-breath-traversal of the genealogy graph using the nodes OutEdges
    208     /// </summary>
    209     /// <returns>All the descendants of the current node</returns>
    210     public IEnumerable<GenealogyGraphNode> Descendants() {
    211       var nodes = new HashSet<GenealogyGraphNode> { this };
    212       var list = new List<GenealogyGraphNode> { this };
    213       int i = 0;
    214       while (i != list.Count) {
    215         if (list[i].OutEdges != null) {
    216           foreach (var e in list[i].OutEdges) {
    217             if (nodes.Contains(e.Target)) continue;
    218             nodes.Add(e.Target);
    219             list.Add(e.Target);
    220           }
    221         }
    222         ++i;
    223       }
    224       return list;
    225     }
    226 
    227     // this method can be used to add arcs towards targets that are not visible in the graph
    228     // (they do not appear in the _nodes Dictionary). It is the programmers responsibility to
    229     // enforce the correct and desired behavior.
    230     public void AddForwardArc(GenealogyGraphNode target, object data = null) {
    231       var e = new GenealogyGraphArc { Target = target, Data = data };
    232       if (OutEdges == null) OutEdges = new List<GenealogyGraphArc> { e };
    233       else OutEdges.Add(e);
    234     }
    235 
    236     public void AddReverseArc(GenealogyGraphNode target, object data = null) {
    237       var e = new GenealogyGraphArc { Target = target, Data = data };
    238       if (InEdges == null) InEdges = new List<GenealogyGraphArc> { e };
    239       else InEdges.Add(e);
    240     }
    241   }
    242 
    243   /// <summary>
    244   /// An arc is an edge along with an orientation
    245   /// </summary>
    246   public class GenealogyGraphArc {
    247     public GenealogyGraphNode Target { get; set; }
    248     // these two fields are not used, but they might be useful later
    249     public string Label { get; set; } // might be useful later
    250     public double Weight { get; set; } // might be useful later
    251     // object used to embed information about node interactions into the arc that connects them (therefore a graph arc will encode a relationship/interaction)
    252     public object Data { get; set; }
    253   }
    254117}
  • branches/HeuristicLab.EvolutionaryTracking/HeuristicLab.EvolutionaryTracking/3.4/Interfaces/IGenealogyGraph.cs

    r7799 r8555  
    2121
    2222using System;
    23 using System.Collections.Generic;
    2423using HeuristicLab.Core;
    2524
    2625namespace HeuristicLab.EvolutionaryTracking {
    2726  public interface IGenealogyGraph<T> : INamedItem where T : class {
    28     // node/vertex operations
    2927    bool HasNode(T t); // graph contains specific node?
    30     bool Any(Func<KeyValuePair<T, GenealogyGraphNode>, bool> predicate); // graph contains any nodes matching the given predicate?
     28    bool Any(Func<T, bool> predicate); // graph contains any nodes matching the given predicate?
    3129    void Clear(); // clear graph
    32     void AddNode(T t);
     30    void AddNode(T nodeData);
    3331    void RemoveNode(T t); // remove node if contained in the graph
    34     GenealogyGraphNode GetNode(T t); // return node corresponding to object t, or null
    35     // arc operation
     32    GenealogyGraphNode GetNode(T t); // return node corresponding to object nodeData, or null
    3633    void AddArc(T source, T target, object sourceData = null, object targetData = null);
    37     //void AddArcs(T[] a, T b);
    3834  }
    3935}
  • branches/HeuristicLab.EvolutionaryTracking/HeuristicLab.EvolutionaryTracking/3.4/SymbolicExpressionTreeGenealogyGraph.cs

    r8248 r8555  
    1 using System.Collections.Generic;
     1#region License Information
     2/* HeuristicLab
     3 * Copyright (C) 2002-2012 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
     4 *
     5 * This file is part of HeuristicLab.
     6 *
     7 * HeuristicLab is free software: you can redistribute it and/or modify
     8 * it under the terms of the GNU General Public License as published by
     9 * the Free Software Foundation, either version 3 of the License, or
     10 * (at your option) any later version.
     11 *
     12 * HeuristicLab is distributed in the hope that it will be useful,
     13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
     14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
     15 * GNU General Public License for more details.
     16 *
     17 * You should have received a copy of the GNU General Public License
     18 * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
     19 */
     20#endregion
     21
     22using System.Collections.Generic;
    223using System.Linq;
    324using HeuristicLab.Common;
     
    1031  [Item("SymbolicExpressionTreeGenealogyGraph", "A genealogy graph for symbolic expression trees")]
    1132  [StorableClass]
    12   public class SymbolicExpressionTreeGenealogyGraph : GenealogyGraph<ISymbolicExpressionTree> {
     33  public class SymbolicExpressionTreeGenealogyGraph : GenealogyGraph<SymbolicExpressionGenealogyGraphNode>, ISymbolicExpressionTreeGenealogyGraph {
     34    [Storable]
     35    private readonly Dictionary<ISymbolicExpressionTree, List<SymbolicExpressionGenealogyGraphNode>> nodeMap =
     36      new Dictionary<ISymbolicExpressionTree, List<SymbolicExpressionGenealogyGraphNode>>();
    1337
    14     [Storable]
    15     private readonly Dictionary<GenealogyGraphNode, NodeMetadata> _nodeInfo = new Dictionary<GenealogyGraphNode, NodeMetadata>();
    16 
    17     public SymbolicExpressionTreeGenealogyGraph() {
    18     }
     38    public SymbolicExpressionTreeGenealogyGraph() { }
    1939
    2040    [StorableConstructor]
    21     public SymbolicExpressionTreeGenealogyGraph(bool serializing)
    22       : base(serializing) {
    23     }
     41    public SymbolicExpressionTreeGenealogyGraph(bool serializing) : base(serializing) { }
    2442
    25     public override IDeepCloneable Clone(Cloner cloner) {
    26       return new SymbolicExpressionTreeGenealogyGraph(this, cloner);
    27     }
     43    public override IDeepCloneable Clone(Cloner cloner) { return new SymbolicExpressionTreeGenealogyGraph(this, cloner); }
    2844
    29     protected SymbolicExpressionTreeGenealogyGraph(SymbolicExpressionTreeGenealogyGraph original, Cloner cloner)
    30       : base(original, cloner) {
    31     }
     45    protected SymbolicExpressionTreeGenealogyGraph(SymbolicExpressionTreeGenealogyGraph original, Cloner cloner) : base(original, cloner) { }
    3246
    33     public override void AddNode(ISymbolicExpressionTree tree) {
    34       if (HasNode(tree)) return;
    35       var node = new GenealogyGraphNode(tree);
    36       _nodeInfo[node] = new NodeMetadata();
     47    public override void AddNode(SymbolicExpressionGenealogyGraphNode node) {
     48      if (!nodeMap.ContainsKey(node.SymbolicExpressionTree))
     49        nodeMap[node.SymbolicExpressionTree] = new List<SymbolicExpressionGenealogyGraphNode> { node };
     50      else
     51        nodeMap[node.SymbolicExpressionTree].Add(node);
    3752      base.AddNode(node);
    3853    }
    3954
    40     public override void AddNode(GenealogyGraphNode node) {
    41       var tree = (ISymbolicExpressionTree)node.Data;
    42       if (HasNode(tree)) return;
    43       _nodeInfo[node] = new NodeMetadata();
    44       base.AddNode(node);
     55    public List<SymbolicExpressionGenealogyGraphNode> GetGraphNodes(ISymbolicExpressionTree tree) {
     56      return nodeMap.ContainsKey(tree) ? nodeMap[tree] : null;
    4557    }
    4658
    47     public NodeMetadata this[GenealogyGraphNode node] {
    48       get {
    49         NodeMetadata value;
    50         _nodeInfo.TryGetValue(node, out value);
    51         return value;
     59    public bool HasNode(SymbolicExpressionTree tree) {
     60      return Nodes.Any(x => x.SymbolicExpressionTree == tree);
     61    }
     62
     63    public int Compare(GenealogyGraphNode a, GenealogyGraphNode b) {
     64      return Compare(a as SymbolicExpressionGenealogyGraphNode, b as SymbolicExpressionGenealogyGraphNode);
     65    }
     66
     67    // TODO: make sure a and b are valid and the info exists for both
     68    public int Compare(SymbolicExpressionGenealogyGraphNode a, SymbolicExpressionGenealogyGraphNode b) {
     69      if (a.Quality.Equals(b.Quality)) {
     70        if (a.IsElite) return +1;
     71        if (b.IsElite) return -1;
    5272      }
    53       set {
    54         _nodeInfo[node] = value;
    55       }
     73      return a.Quality.CompareTo(b.Quality);
    5674    }
    5775
    5876    #region Fragment tracing
    59     public IEnumerable<ISymbolicExpressionTree> TraceFragment(ISymbolicExpressionTreeNode fragment, int mode = 0) {
    60       return Keys.Where(tree => tree.ContainsFragment(fragment, mode));
     77    public IEnumerable<ISymbolicExpressionTree> TraceFragment(ISymbolicExpressionTreeNode fragment, SimilarityLevel similarity = SimilarityLevel.Exact) {
     78      return Nodes.Where(x => x.SymbolicExpressionTree.ContainsFragment(fragment, similarity)).Select(x => x.SymbolicExpressionTree).ToList();
    6179    }
    6280    #endregion
    6381  }
    6482
    65   public class NodeMetadata {
     83  public class SymbolicExpressionGenealogyGraphNode : GenealogyGraphNode {
     84    public ISymbolicExpressionTree SymbolicExpressionTree { get; set; }
    6685    public double Quality { get; set; }
     86    public bool IsElite { get; set; }
    6787    public List<double> Ranks { get; set; }
    68     public bool IsElite { get; set; }
    6988
    70     public NodeMetadata() {
     89    public SymbolicExpressionGenealogyGraphNode() {
     90      Ranks = new List<double>();
     91    }
     92
     93    public SymbolicExpressionGenealogyGraphNode(object content) {
     94      Content = content;
    7195      Ranks = new List<double>();
    7296    }
Note: See TracChangeset for help on using the changeset viewer.