Free cookie consent management tool by TermsFeed Policy Generator

Changeset 7799


Ignore:
Timestamp:
05/11/12 17:29:55 (11 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
Files:
9 edited

Legend:

Unmodified
Added
Removed
  • branches/HeuristicLab.EvolutionaryTracking/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/Plugin.cs

    r7792 r7799  
    2626
    2727namespace HeuristicLab.Encodings.SymbolicExpressionTreeEncoding {
    28   [Plugin("HeuristicLab.Encodings.SymbolicExpressionTreeEncoding","Provides operators and related classes for the symbolic expression tree encoding.", "3.4.2.7788")]
     28  [Plugin("HeuristicLab.Encodings.SymbolicExpressionTreeEncoding","Provides operators and related classes for the symbolic expression tree encoding.", "3.4.2.7792")]
    2929  [PluginFile("HeuristicLab.Encodings.SymbolicExpressionTreeEncoding-3.4.dll", PluginFileType.Assembly)]
    3030  [PluginDependency("HeuristicLab.Analysis", "3.3")]
  • branches/HeuristicLab.EvolutionaryTracking/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/SymbolicExpressionTreeNode.cs

    r7792 r7799  
    173173
    174174    public IEnumerable<ISymbolicExpressionTreeNode> IterateNodesBreadth() {
    175       var list = new List<ISymbolicExpressionTreeNode>(GetLength()) { this };
    176       int offset = 0, count = 1;
    177       while (offset != count) {
    178         var c = count;
    179         for (int i = offset; i != count; ++i)
    180           if (list[i].SubtreeCount > 0)
    181             list.AddRange(list[i].Subtrees);
    182         offset = c;
    183         count = list.Count;
     175      var list = new List<ISymbolicExpressionTreeNode>() { this };
     176      int i = 0;
     177      while (i != list.Count) {
     178        for (int j = 0; j != list[i].SubtreeCount; ++j)
     179          list.Add(list[i].GetSubtree(j));
     180        ++i;
    184181      }
    185182      return list;
  • branches/HeuristicLab.EvolutionaryTracking/HeuristicLab.EvolutionaryTracking.Views/3.4/GenealogyGraphView.cs

    r7792 r7799  
    9999          _selectedVisualSymbolicExpressionTreeNode = symbolicExpressionTreeChart.GetVisualSymbolicExpressionTreeNode(nodes[index + fragments.Count - 1]);
    100100          var subtree = _selectedVisualSymbolicExpressionTreeNode.SymbolicExpressionTreeNode;
    101           foreach (var visualNode in subtree.IterateNodesPostfix().Select(node => symbolicExpressionTreeChart.GetVisualSymbolicExpressionTreeNode(node))) {
     101          foreach (var visualNode in subtree.IterateNodesBreadth().Select(node => symbolicExpressionTreeChart.GetVisualSymbolicExpressionTreeNode(node))) {
    102102            visualNode.FillColor = Color.LightBlue;
    103103          }
    104104          symbolicExpressionTreeChart.Repaint();
     105        }
     106      }
     107      var tree = symbolicExpressionTreeChart.Tree;
     108      var graphNode = Content.GetNode(tree);
     109      if (graphNode.InEdges != null) {
     110        var arc = graphNode.InEdges.Find(a => a.Data != null);
     111        if (arc != null) {
     112          var fragment = arc.Data as ISymbolicExpressionTreeNode;
     113          foreach (var node in fragment.IterateNodesBreadth()) {
     114            var visualNode = symbolicExpressionTreeChart.GetVisualSymbolicExpressionTreeNode(node);
     115            visualNode.FillColor = Color.LightGreen;
     116          }
    105117        }
    106118      }
  • branches/HeuristicLab.EvolutionaryTracking/HeuristicLab.EvolutionaryTracking/3.4/Analyzers/SymbolicExpressionTreeFragmentsAnalyzer.cs

    r7792 r7799  
    236236          GlobalCloneMap.Clear();
    237237          GlobalTraceMap.Clear();
    238         }
    239         GlobalFragmentMap.Clear();
     238          GlobalFragmentMap.Clear();
     239        }
    240240      }
    241241      return base.Apply();
  • branches/HeuristicLab.EvolutionaryTracking/HeuristicLab.EvolutionaryTracking/3.4/Analyzers/SymbolicExpressionTreeGenealogyAnalyzer.cs

    r7792 r7799  
    2121
    2222using System;
     23using System.Collections.Generic;
    2324using System.Drawing;
    2425using System.Globalization;
     
    5758    private const string GlobalTraceMapParameterName = "GlobalTraceMap";
    5859    private const string GlobalCloneMapParameterName = "GlobalCloneMap";
     60    private const string GlobalFragmentMapParameterName = "GlobalFragmentMap";
    5961    private const string PopulationGraphResultParameterName = "PopulationGraph";
    6062    private const string PopulationGraphResultParameterDescription = "Individual lineages";
     
    105107      get { return (LookupParameter<CloneMapType>)Parameters[GlobalCloneMapParameterName]; }
    106108    }
     109    public LookupParameter<CloneMapType> GlobalFragmentMapParameter {
     110      get { return (LookupParameter<CloneMapType>)Parameters[GlobalFragmentMapParameterName]; }
     111    }
    107112    #endregion
    108113
     
    140145    public TraceMapType GlobalTraceMap {
    141146      get { return GlobalTraceMapParameter.ActualValue; }
     147    }
     148    public CloneMapType GlobalFragmentMap {
     149      get { return GlobalFragmentMapParameter.ActualValue; }
    142150    }
    143151    public SymbolicDataAnalysisExpressionTreeInterpreter SymbolicExpressionInterpreter {
     
    173181      Parameters.Add(new LookupParameter<TraceMapType>(GlobalTraceMapParameterName, "A global cache containing the whole genealogy."));
    174182      Parameters.Add(new LookupParameter<CloneMapType>(GlobalCloneMapParameterName, "A global map keeping track of trees and their clones (made during selection)."));
     183      Parameters.Add(new LookupParameter<CloneMapType>(GlobalFragmentMapParameterName, "A global map keeping track of tree fragments received via crossover."));
    175184      Parameters.Add(new ValueLookupParameter<ResultCollection>(ResultsParameterName, "The results collection where the analysis values should be stored."));
    176185      Parameters.Add(new LookupParameter<SymbolicDataAnalysisExpressionTreeInterpreter>(SymbolicExpressionInterpreterParameterName, "Interpreter for symbolic expression trees"));
     
    236245            var tree = qualities.ElementAt(i).Key;
    237246            label = (i + 1).ToString(CultureInfo.InvariantCulture);
    238             graph.AddNode(tree, qualities[tree], label, generation, i < Elites.Value);
     247            var node = new GenealogyGraphNode(tree) { Quality = qualities[tree], Label = label, Rank = generation, IsElite = i < Elites.Value };
     248            graph.AddNode(node);
    239249          }
    240250          return base.Apply();
     
    245255          var child = qualities.ElementAt(i).Key;
    246256          label = (generation * qualities.Count + i + 1).ToString(CultureInfo.InvariantCulture);
    247           if (!graph.HasNode(child))
    248             graph.AddNode(child, qualities[child], label, generation, i < Elites.Value);
     257          if (!graph.HasNode(child)) {
     258            var node = new GenealogyGraphNode(child) { Quality = qualities[child], Label = label, Rank = generation, IsElite = i < Elites.Value };
     259            graph.AddNode(node);
     260          }
    249261          if (!GlobalTraceMap.ContainsKey(child)) continue;
    250           var parents = GlobalTraceMap[child];
     262          var parents = GlobalTraceMap[child].Cast<ISymbolicExpressionTree>();
    251263
    252264          foreach (var parent in parents) {
     265            object data;
    253266            if (GlobalTraceMap.ContainsKey(parent)) {
    254               double quality = Evaluate((ISymbolicExpressionTree)parent);
    255               graph.AddNode((ISymbolicExpressionTree)parent, quality, "", generation - 0.5);
    256               var pp = GlobalTraceMap[parent];
     267              double quality = Evaluate(parent);
     268              var node = new GenealogyGraphNode(parent) { Quality = quality, Label = "", Rank = generation - 0.5 };
     269              graph.AddNode(node);
     270              var pp = GlobalTraceMap[parent].Cast<ISymbolicExpressionTree>();
    257271              foreach (var p in pp) {
    258                 graph.AddArc((ISymbolicExpressionTree)p, (ISymbolicExpressionTree)parent);
     272                data = ((List<ISymbolicExpressionTreeNode>)parent.IterateNodesBreadth())[((IntValue)GlobalFragmentMap[parent]).Value];
     273                graph.AddArc(p, parent, data);
    259274              }
    260275            }
    261             graph.AddArc((ISymbolicExpressionTree)parent, child);
     276            data = ((List<ISymbolicExpressionTreeNode>)child.IterateNodesBreadth())[((IntValue)GlobalFragmentMap[child]).Value];
     277            graph.AddArc(parent, child, data);
    262278          }
    263279        }
     
    267283          GlobalTraceMap.Clear();
    268284          GlobalCloneMap.Clear();
     285          GlobalFragmentMap.Clear();
    269286        }
    270287
  • branches/HeuristicLab.EvolutionaryTracking/HeuristicLab.EvolutionaryTracking/3.4/GenealogyGraph.cs

    r7792 r7799  
    3131  [Item("Genealogy graph", "Generic class for tracking the evolution of objects.")]
    3232  public class GenealogyGraph<T> : NamedItem, IGenealogyGraph<T> where T : class {
    33     private readonly Dictionary<T, GenealogyGraphNode> _dictionary;
     33    private readonly Dictionary<T, GenealogyGraphNode> _nodes;
    3434
    3535    public GenealogyGraph() {
    36       _dictionary = new Dictionary<T, GenealogyGraphNode>();
     36      _nodes = new Dictionary<T, GenealogyGraphNode>();
    3737    }
    3838
    3939    public GenealogyGraph(GenealogyGraph<T> g) {
    40       _dictionary = new Dictionary<T, GenealogyGraphNode>(g._dictionary);
     40      _nodes = new Dictionary<T, GenealogyGraphNode>(g._nodes);
    4141    }
    4242
     
    5656    private GenealogyGraph(GenealogyGraph<T> original, Cloner cloner)
    5757      : base(original, cloner) {
    58       _dictionary = new Dictionary<T, GenealogyGraphNode>(original._dictionary);
    59     }
    60 
    61     public bool HasNode(T t) {
    62       return _dictionary.ContainsKey(t);
    63     }
    64 
    65     public GenealogyGraphNode GetNode(T t) {
    66       return HasNode(t) ? _dictionary[t] : null;
    67     }
    68 
    69     public IEnumerable<T> Keys {
    70       get { return _dictionary.Keys; }
    71     }
    72 
    73     public IEnumerable<GenealogyGraphNode> Values {
    74       get { return _dictionary.Values; }
    75     }
    76 
    77     public bool IsEmpty {
    78       get { return !_dictionary.Any(); }
    79     }
    80 
    81     public bool Any(Func<KeyValuePair<T, GenealogyGraphNode>, bool> predicate) {
    82       return _dictionary.Any(predicate);
    83     }
    84 
    85     public void Clear() {
    86       _dictionary.Clear();
    87     }
     58      _nodes = new Dictionary<T, GenealogyGraphNode>(original._nodes);
     59    }
     60
     61    public bool HasNode(T t) { return _nodes.ContainsKey(t); }
     62    public GenealogyGraphNode GetNode(T t) { return HasNode(t) ? _nodes[t] : null; }
     63    public IEnumerable<T> Keys { get { return _nodes.Keys; } }
     64    public IEnumerable<GenealogyGraphNode> Values { get { return _nodes.Values; } }
     65    public bool IsEmpty { get { return !_nodes.Any(); } }
     66    public bool Any(Func<KeyValuePair<T, GenealogyGraphNode>, bool> predicate) { return _nodes.Any(predicate); }
     67    public void Clear() { _nodes.Clear(); }
    8868
    8969    /// <summary>
    9070    /// Adds a node representing an individual
    9171    /// </summary>
    92     /// <param name="t">The symbolic expression tree</param>
    93     /// <param name="quality">The quality value </param>
    94     /// <param name="label">The node label</param>
    95     /// <param name="rank">The node rank</param>
    96     /// <param name="elite">Specifies if this node is an elite</param>
    97     public void AddNode(T t, double quality = 0.0, string label = "", double rank = 0, bool elite = false) {
     72    /// <param name="t">The data this node is supposed to represent in the graph</param>
     73    public void AddNode(T t) {
    9874      if (HasNode(t)) return;
    99       _dictionary[t] = new GenealogyGraphNode { Data = t, Quality = quality, Label = label, IsElite = elite, Rank = rank };
     75      _nodes[t] = new GenealogyGraphNode(t) { Quality = 0.0, Label = "", IsElite = false, Rank = 0.0 };
    10076    }
    10177
     
    10783      var t = (T)node.Data;
    10884      if (HasNode(t)) return;
    109       _dictionary[t] = node;
     85      _nodes[t] = node;
    11086    }
    11187
     
    11591    /// <param name="t">The graph node</param>
    11692    public void RemoveNode(T t) {
    117       if (!_dictionary.ContainsKey(t)) return;
    118       var node = _dictionary[t];
     93      if (!_nodes.ContainsKey(t)) return;
     94      var node = _nodes[t];
    11995      if (node.InEdges != null) {
    12096        foreach (var e in node.InEdges.Where(e => e.Target.OutEdges != null)) {
    12197          e.Target.OutEdges.RemoveAll(arc => arc.Target == node);
    122           if (!e.Target.OutEdges.Any())
     98          if (e.Target.OutEdges.Count == 0)
    12399            e.Target.OutEdges = null; // set to null to be a little more memory efficient
    124100        }
     
    128104        foreach (var e in node.OutEdges.Where(e => e.Target.InEdges != null)) {
    129105          e.Target.InEdges.RemoveAll(arc => arc.Target == node);
    130           if (!e.Target.InEdges.Any())
     106          if (e.Target.InEdges.Count == 0)
    131107            e.Target.InEdges = null; // set to null to be a little more memory efficient
    132108        }
    133109        node.OutEdges = null;
    134110      }
    135       _dictionary.Remove(t);
     111      _nodes.Remove(t);
    136112    }
    137113
     
    143119    /// Adds a graph arc from a to b
    144120    /// </summary>
    145     /// <param name="a"></param>
    146     /// <param name="b"></param>
    147     public void AddArc(T a, T b) {
     121    /// <param name="obj1"></param>
     122    /// <param name="obj2"></param>
     123    public void AddArc(T obj1, T obj2, object data1 = null, object data2 = null) {
    148124      GenealogyGraphNode src, dest;
    149       if (!HasNode(a)) {
    150         src = new GenealogyGraphNode { Data = a };
    151         _dictionary[a] = src;
     125      if (!HasNode(obj1)) {
     126        src = new GenealogyGraphNode(obj1);
     127        _nodes[obj1] = src;
    152128      } else {
    153         src = _dictionary[a];
    154       }
    155       if (!HasNode(b)) {
    156         dest = new GenealogyGraphNode { Data = b };
    157         _dictionary[b] = dest;
     129        src = _nodes[obj1];
     130      }
     131      if (!HasNode(obj2)) {
     132        dest = new GenealogyGraphNode(obj2);
     133        _nodes[obj2] = dest;
    158134      } else {
    159         dest = _dictionary[b];
     135        dest = _nodes[obj2];
    160136      }
    161137      // add forward and reverse arcs
     
    164140    }
    165141
    166     public void AddArcs(T[] a, T b) {
    167       GenealogyGraphNode src, dest;
    168       if (!HasNode(b)) {
    169         dest = new GenealogyGraphNode { Data = b };
    170         _dictionary[b] = dest;
    171       } else {
    172         dest = _dictionary[b];
    173       }
    174       foreach (var o in a) {
    175         if (!HasNode(o)) {
    176           src = new GenealogyGraphNode { Data = o };
    177           _dictionary[o] = src;
    178         } else {
    179           src = _dictionary[o];
    180         }
    181         src.AddForwardArc(dest);
    182         dest.AddReverseArc(src);
    183       }
    184     }
     142    //public void AddArcs(T[] a, T b) {
     143    //  GenealogyGraphNode src, dest;
     144    //  if (!HasNode(b)) {
     145    //    dest = new GenealogyGraphNode(b);
     146    //    _nodes[b] = dest;
     147    //  } else {
     148    //    dest = _nodes[b];
     149    //  }
     150    //  foreach (var o in a) {
     151    //    if (!HasNode(o)) {
     152    //      src = new GenealogyGraphNode(o);
     153    //      _nodes[o] = src;
     154    //    } else {
     155    //      src = _nodes[o];
     156    //    }
     157    //    src.AddForwardArc(dest);
     158    //    dest.AddReverseArc(src);
     159    //  }
     160    //}
    185161  }
    186162
     
    189165    public string Label { get; set; }
    190166    public bool IsElite { get; set; }
    191     public object Data { get; set; }
    192167    public double Quality { get; set; }
    193168    public double Rank { get; set; }
    194169    public List<GenealogyGraphArc> InEdges { get; set; }
    195170    public List<GenealogyGraphArc> OutEdges { get; set; }
     171    private object _data;
     172    public object Data {
     173      get { return _data; }
     174      set {
     175        if (value == null)
     176          throw new ArgumentException("Node data cannot be null.");
     177        else {
     178          _data = value; // data must be of type T
     179        }
     180      }
     181    }
    196182
    197183    public int Degree { get { return (InEdges == null ? 0 : InEdges.Count) + (OutEdges == null ? 0 : OutEdges.Count); } }
    198184
    199     public GenealogyGraphNode() { Id = Guid.NewGuid().ToString(); }
     185    public GenealogyGraphNode(object data) {
     186      if (data == null) {
     187        throw new ArgumentException("Node data cannot be null");
     188      }
     189      Id = Guid.NewGuid().ToString();
     190      Data = data;
     191    }
    200192
    201193    public GenealogyGraphNode(GenealogyGraphNode node) {
     
    206198      Label = node.Label;
    207199      Data = node.Data;
    208       InEdges = node.InEdges;
    209       OutEdges = node.OutEdges;
     200      InEdges = new List<GenealogyGraphArc>(node.InEdges);
     201      OutEdges = new List<GenealogyGraphArc>(node.OutEdges);
    210202    }
    211203
     
    216208    public IEnumerable<GenealogyGraphNode> Ancestors() {
    217209      var nodes = new HashSet<GenealogyGraphNode> { this };
    218       int offset = 0;
    219       int c0 = 1;
    220       while (offset != c0) {
    221         int c1 = c0;
    222         for (int i = offset; i != c1; ++i) {
    223           if (nodes.ElementAt(i).InEdges == null) continue;
     210      int i = 0;
     211      while (i != nodes.Count) {
     212        if (nodes.ElementAt(i).InEdges != null) {
    224213          foreach (var p in nodes.ElementAt(i).InEdges.Select(e => e.Target)) {
    225214            nodes.Add(p);
     
    227216          }
    228217        }
    229         offset = c1;
    230         c0 = nodes.Count;
     218        ++i;
    231219      }
    232220    }
     
    238226    public IEnumerable<GenealogyGraphNode> Descendants() {
    239227      var nodes = new HashSet<GenealogyGraphNode> { this };
    240       int offset = 0;
    241       int c0 = 1;
    242       while (offset != c0) {
    243         int c1 = c0;
    244         for (int i = offset; i != c1; ++i) {
    245           if (nodes.ElementAt(i).OutEdges == null) continue;
     228      int i = 0;
     229      while (i != nodes.Count) {
     230        if (nodes.ElementAt(i).OutEdges != null) {
    246231          foreach (var p in nodes.ElementAt(i).OutEdges.Select(e => e.Target)) {
    247232            nodes.Add(p);
     
    249234          }
    250235        }
    251         offset = c1;
    252         c0 = nodes.Count;
    253       }
    254     }
    255 
    256     public void AddForwardArc(GenealogyGraphNode target) {
    257       var e = new GenealogyGraphArc { Target = target };
     236        ++i;
     237      }
     238    }
     239
     240    // this method can be used to add arcs towards targets that are not visible in the graph
     241    // (they do not appear in the _nodes Dictionary). It is the programmers responsibility to
     242    // enforce the correct and desired behavior.
     243    public void AddForwardArc(GenealogyGraphNode target, object data = null) {
     244      var e = new GenealogyGraphArc { Target = target, Data = data };
    258245      if (OutEdges == null) OutEdges = new List<GenealogyGraphArc> { e };
    259246      else OutEdges.Add(e);
    260247    }
    261248
    262     public void AddReverseArc(GenealogyGraphNode target) {
    263       var e = new GenealogyGraphArc { Target = target };
     249    public void AddReverseArc(GenealogyGraphNode target, object data = null) {
     250      var e = new GenealogyGraphArc { Target = target, Data = data };
    264251      if (InEdges == null) InEdges = new List<GenealogyGraphArc> { e };
    265252      else InEdges.Add(e);
     
    289276    public string Label { get; set; } // might be useful later
    290277    public double Weight { get; set; } // might be useful later
     278    // object used to embed information about node interactions into the arc that connects them (therefore a graph arc will encode a relationship/interaction)
     279    public object Data { get; set; }
    291280  }
    292281}
  • branches/HeuristicLab.EvolutionaryTracking/HeuristicLab.EvolutionaryTracking/3.4/Interfaces/IGenealogyGraph.cs

    r7792 r7799  
    3030    bool Any(Func<KeyValuePair<T, GenealogyGraphNode>, bool> predicate); // graph contains any nodes matching the given predicate?
    3131    void Clear(); // clear graph
    32     void AddNode(T t, double quality = 0.0, string label = "", double rank = 0, bool elite = false);
     32    void AddNode(T t);
    3333    void RemoveNode(T t); // remove node if contained in the graph
    3434    GenealogyGraphNode GetNode(T t); // return node corresponding to object t, or null
    3535    // arc operation
    36     void AddArc(T source, T target);
    37     void AddArcs(T[] a, T b);
     36    void AddArc(T source, T target, object sourceData = null, object targetData = null);
     37    //void AddArcs(T[] a, T b);
    3838  }
    3939}
  • branches/HeuristicLab.EvolutionaryTracking/HeuristicLab.Selection/3.3/Plugin.cs

    r7792 r7799  
    2626  /// Plugin class for HeuristicLab.Selection plugin.
    2727  /// </summary>
    28   [Plugin("HeuristicLab.Selection", "3.3.6.7788")]
     28  [Plugin("HeuristicLab.Selection", "3.3.6.7792")]
    2929  [PluginFile("HeuristicLab.Selection-3.3.dll", PluginFileType.Assembly)]
    3030  [PluginDependency("HeuristicLab.Collections", "3.3")]
Note: See TracChangeset for help on using the changeset viewer.