Changeset 7779


Ignore:
Timestamp:
05/03/12 12:26:11 (8 years ago)
Author:
bburlacu
Message:

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

Location:
branches/HeuristicLab.EvolutionaryTracking
Files:
56 added
7 edited

Legend:

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

    r7522 r7779  
    2626
    2727namespace HeuristicLab.Encodings.SymbolicExpressionTreeEncoding {
    28   [Plugin("HeuristicLab.Encodings.SymbolicExpressionTreeEncoding","Provides operators and related classes for the symbolic expression tree encoding.", "3.4.2.7514")]
     28  [Plugin("HeuristicLab.Encodings.SymbolicExpressionTreeEncoding","Provides operators and related classes for the symbolic expression tree encoding.", "3.4.2.7522")]
    2929  [PluginFile("HeuristicLab.Encodings.SymbolicExpressionTreeEncoding-3.4.dll", PluginFileType.Assembly)]
    3030  [PluginDependency("HeuristicLab.Analysis", "3.3")]
  • branches/HeuristicLab.EvolutionaryTracking/HeuristicLab.EvolutionaryTracking/3.4/Analyzers/SymbolicExpressionTreeGenealogyAnalyzer.cs

    r7522 r7779  
    2222using System;
    2323using System.Collections.Generic;
     24using System.Drawing;
    2425using System.Globalization;
    2526using System.Linq;
     
    3637using HeuristicLab.Problems.DataAnalysis;
    3738using HeuristicLab.Problems.DataAnalysis.Symbolic;
    38 using HeuristicLab.Problems.DataAnalysis.Symbolic.Regression;
    3939using CloneMapType = HeuristicLab.Core.ItemDictionary<HeuristicLab.Core.IItem, HeuristicLab.Core.IItem>;
    4040using TraceMapType = HeuristicLab.Core.ItemDictionary<HeuristicLab.Core.IItem, HeuristicLab.Core.IItemList<HeuristicLab.Core.IItem>>;
     
    4747  [StorableClass]
    4848  public sealed class SymbolicExpressionTreeGenealogyAnalyzer : SingleSuccessorOperator, IAnalyzer {
     49    public enum GeneticOperator { Crossover, Mutation }
     50
    4951    private const string UpdateIntervalParameterName = "UpdateInterval";
    5052    private const string UpdateCounterParameterName = "UpdateCounter";
     
    213215        var gScope = ExecutionContext.Scope;
    214216        while (gScope.Parent != null) gScope = gScope.Parent;
    215         GenealogyGraph graph;
     217        SymbolicExpressionTreeGenealogyGraph graph;
    216218        if (!Results.ContainsKey(PopulationGraphResultParameterName)) {
    217           graph = new GenealogyGraph();
     219          graph = new SymbolicExpressionTreeGenealogyGraph();
    218220          Results.Add(new Result(PopulationGraphResultParameterName, PopulationGraphResultParameterDescription, graph));
    219221        } else {
    220           graph = (GenealogyGraph)Results[PopulationGraphResultParameterName].Value;
     222          graph = (SymbolicExpressionTreeGenealogyGraph)Results[PopulationGraphResultParameterName].Value;
    221223        }
    222224        // get tree quality values
     
    225227                         let quality = (DoubleValue)s.Variables["Quality"].Value
    226228                         orderby quality.Value descending
    227                          select new Tuple<IItem, double>(individual, quality.Value)).ToDictionary(t => t.Item1, t => t.Item2);
     229                         select new Tuple<ISymbolicExpressionTree, double>((ISymbolicExpressionTree)individual, quality.Value)).ToDictionary(t => t.Item1, t => t.Item2);
    228230
    229231        // add all individuals to the evolutionary graph
     
    232234
    233235        if (generation == 0) {
    234           // at generation 0 no trace map is present (since no reproduction has taken place yet),
    235           // so we only add the initial trees as nodes in the genealogy graph
     236          // at generation 0 no trace map is present (since no reproduction has taken place yet), so we only add the initial trees as nodes in the genealogy graph
    236237          for (int i = 0; i != qualities.Count; ++i) {
    237238            var tree = qualities.ElementAt(i).Key;
     
    242243        }
    243244
     245        // add nodes to genealogy graph
    244246        for (int i = 0; i != qualities.Count; ++i) {
    245247          var child = qualities.ElementAt(i).Key;
    246248          label = (generation * qualities.Count + i + 1).ToString(CultureInfo.InvariantCulture);
    247           if (i < Elites.Value) {
    248             if (graph.HasNode(child))
    249               graph.GetNode(child).Label += "\\n" + label;
    250             else
    251               graph.AddNode(child, qualities[child], label, generation, true);
    252           } else
    253             graph.AddNode(child, qualities[child], label, generation);
     249          if (!graph.HasNode(child)) graph.AddNode(child, qualities[child], label, generation, i < Elites.Value);
    254250          if (!GlobalTraceMap.ContainsKey(child)) continue;
    255251          var parents = GlobalTraceMap[child];
     252
    256253          foreach (var parent in parents) {
     254            int opType;
    257255            if (GlobalTraceMap.ContainsKey(parent)) {
    258256              double quality = Evaluate((ISymbolicExpressionTree)parent);
    259               graph.AddNode(parent, quality, "", generation - 0.5);
    260               foreach (var p in GlobalTraceMap[parent])
    261                 graph.AddArc(p, parent);
     257              graph.AddNode((ISymbolicExpressionTree)parent, quality, "", generation - 0.5);
     258              var pp = GlobalTraceMap[parent];
     259              foreach (var p in pp) {
     260                opType = pp.Count == 2 ? (int)GeneticOperator.Crossover : (int)GeneticOperator.Mutation;
     261                graph.AddArc((ISymbolicExpressionTree)p, (ISymbolicExpressionTree)parent, opType);
     262              }
    262263            }
    263             graph.AddArc(parent, child);
     264            opType = parents.Count == 2 ? (int)GeneticOperator.Crossover : (int)GeneticOperator.Mutation;
     265            graph.AddArc((ISymbolicExpressionTree)parent, child, opType);
    264266          }
    265267        }
    266268
     269        // clear trace and clone maps in preparation for the next generation
    267270        GlobalTraceMap.Clear();
    268271        GlobalCloneMap.Clear();
    269272
    270         #region end of the run
    271         bool maxGenerationsReached = (Generations.Value == MaximumGenerations.Value);
    272         bool isOsga = (SelectionPressure != null && MaximumSelectionPressure != null);
    273         bool maxSelectionPressureReached = isOsga && (SelectionPressure.Value >= MaximumSelectionPressure.Value);
    274         if (maxGenerationsReached || maxSelectionPressureReached) {
    275           var path = Environment.GetFolderPath(Environment.SpecialFolder.UserProfile);
    276 
    277           // write whole graph to a dot file
    278           WriteDot(path + @"\lineage.dot", graph);
    279 
    280           // get genealogy of the best solution
    281           var bestSolution = (ISymbolicExpressionTree)qualities.First().Key;
    282           var genealogy = graph.GetNode(bestSolution).Genealogy();
    283           WriteDot(path + @"\bestlineage.dot", genealogy);
    284 
    285           // write the direct root lineage of the best solution (is it useful?)
    286 
    287           // calculate impact values of nodes in the best solution, attempt to trace those with high impact to their origins
    288           var calculator = new SymbolicRegressionSolutionValuesCalculator();
    289           var impactValues = calculator.CalculateImpactValues(bestSolution, SymbolicExpressionInterpreter, SymbolicRegressionProblemData, 0, 0);
    290           foreach (var pair in impactValues.Where(pair => !(pair.Key is ConstantTreeNode || pair.Key is VariableTreeNode) && pair.Value > 0.9)) {
    291             var node = pair.Key;
    292 
    293             foreach (var ancestor in genealogy.Keys) {
    294               graph.GetNode(ancestor).Color = ContainsSubtree(ancestor as ISymbolicExpressionTree, node) ? new Color { R = 0, G = 0, B = 150 } : new Color { R = 255, G = 255, B = 255 };
    295             }
    296           }
    297           WriteDot(path + @"\impactancestry.dot", genealogy);
    298 
    299           // trim the graph
    300           // exclude the individuals of the last generation
    301           var individuals = graph.Keys.Except(qualities.Select(x => x.Key)).ToList();
    302           bool done = false;
    303           while (!done) {
    304             done = true;
    305             foreach (var ind in individuals) {
    306               // if node has no outgoing connections (absence of offspring), remove it from the graph
    307               var node = graph.GetNode(ind);
    308               if (node == null) continue;
    309               if (node.OutEdges == null) {
    310                 done = false; // we still have "dead" nodes
    311                 graph.RemoveNode(ind);
    312               }
    313             }
    314           }
    315           WriteDot(path + @"\trimmedlineage.dot", graph);
    316         }
     273        #region end of the run (code for writing results to dot files)
     274        //bool maxGenerationsReached = (Generations.Value == MaximumGenerations.Value);
     275        //bool isOsga = (SelectionPressure != null && MaximumSelectionPressure != null);
     276        //bool maxSelectionPressureReached = isOsga && (SelectionPressure.Value >= MaximumSelectionPressure.Value);
     277        //if (maxGenerationsReached || maxSelectionPressureReached) {
     278        //  var path = Environment.GetFolderPath(Environment.SpecialFolder.UserProfile);
     279
     280        //  // write whole graph to a dot file
     281        //  WriteDot(path + @"\lineage.dot", graph);
     282
     283        //  // get genealogy of the best solution
     284        //  var bestSolution = (ISymbolicExpressionTree)qualities.First().Key;
     285        //  var genealogy = graph.GetNode(bestSolution).Ancestors();
     286        //  //WriteDot(path + @"\bestlineage.dot", genealogy);
     287
     288        //  // write the direct root lineage of the best solution (is it useful?)
     289
     290        //  // calculate impact values of nodes in the best solution, attempt to trace those with high impact to their origins
     291        //  var calculator = new SymbolicRegressionSolutionValuesCalculator();
     292        //  var impactValues = calculator.CalculateImpactValues(bestSolution, SymbolicExpressionInterpreter, SymbolicRegressionProblemData, 0, 0);
     293        //  foreach (var pair in impactValues.Where(pair => !(pair.Key is ConstantTreeNode || pair.Key is VariableTreeNode)).OrderByDescending(pair => pair.Value).Take(2)) {
     294        //    var node = pair.Key;
     295        //  }
     296        //  //WriteDot(path + @"\impactancestry.dot", genealogy);
     297
     298        //  // trim the graph
     299        //  // exclude the individuals of the last generation
     300        //  var individuals = graph.Keys.Except(qualities.Select(x => x.Key)).ToList();
     301        //  bool done = false;
     302        //  while (!done) {
     303        //    done = true;
     304        //    foreach (var ind in individuals) {
     305        //      // if node has no outgoing connections (absence of offspring), remove it from the graph
     306        //      var node = graph.GetNode(ind);
     307        //      if (node == null) continue;
     308        //      if (node.OutEdges == null) {
     309        //        done = false; // we still have "dead" nodes
     310        //        graph.RemoveNode(ind);
     311        //      }
     312        //    }
     313        //  }
     314        //  WriteDot(path + @"\trimmedlineage.dot", graph);
     315        //}
    317316        #endregion
    318317      }
     
    336335
    337336    #region Export to dot file
    338     private static void WriteDot(string path, GenealogyGraph graph) {
     337    private static void WriteDot(string path, SymbolicExpressionTreeGenealogyGraph graph) {
    339338      using (var file = new System.IO.StreamWriter(path)) {
    340339        string nl = Environment.NewLine;
    341         file.WriteLine("digraph \"lineage " + graph.AverageDegree.ToString(CultureInfo.InvariantCulture) + "\" {" + nl +
    342                        "ratio=auto;" + nl +
    343                        "mincross=2.0");
     340        file.WriteLine("digraph \"lineage " + graph.AverageDegree.ToString(CultureInfo.InvariantCulture) + "\" {" + nl + "ratio=auto;" + nl + "mincross=2.0");
    344341        file.WriteLine("\tnode [shape=circle,label=\"\",style=filled]");
    345342
    346343        foreach (var node in graph.Values) {
    347           string fillColor = String.Format("#{0:x2}{1:x2}{2:x2}", node.Color.R, node.Color.G, node.Color.B);
     344          var color = Color.FromArgb((int)((1 - node.Quality) * 255), (int)(node.Quality * 255), 0);
     345          string fillColor = String.Format("#{0:x2}{1:x2}{2:x2}", color.R, color.G, color.B);
    348346          string shape = "circle";
    349347          if (node.IsElite)
     
    353351            continue;
    354352          foreach (var edge in node.InEdges) {
    355             var edgeStyle = node.InEdges.Count == 1 ? "dashed" : String.Empty;
     353            //var edgeStyle = node.InEdges.Count == 1 ? "dashed" : String.Empty;
     354            var edgeStyle = String.Empty;
    356355            file.WriteLine("\t\"" + edge.Target.Id + "\" -> \"" + node.Id + "\" [arrowsize=.5, color=\"" + fillColor + "\", style=\"" + edgeStyle + "\"];");
    357356          }
     
    370369    #endregion
    371370
    372     #region Allele tracking
    373     private bool ContainsSubtree(ISymbolicExpressionTree tree, ISymbolicExpressionTreeNode node) {
    374       return tree.IterateNodesPostfix().Where(n => n.Symbol == node.Symbol && n.GetLength() == node.GetLength())
    375                                        .Where(n => n.Subtrees.Any() && node.Subtrees.Any())
    376                                        .Any(n => n.Subtrees.First().Symbol == node.Subtrees.First().Symbol);
    377     }
    378     #endregion
    379 
    380371    #region Extra / not really needed
     372    // method of iterating tree nodes in a breadth-wise manner
    381373    private IEnumerable<ISymbolicExpressionTreeNode> IterateNodes(ISymbolicExpressionTree tree) {
    382374      return IterateNodes(tree.Root);
  • branches/HeuristicLab.EvolutionaryTracking/HeuristicLab.EvolutionaryTracking/3.4/GenealogyGraph.cs

    r7522 r7779  
    1 using System;
     1#region License Information
     2/* HeuristicLab
     3 * Copyright (C) 2002-2010 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;
    223using System.Collections.Generic;
    324using System.Drawing;
     
    829
    930namespace HeuristicLab.EvolutionaryTracking {
    10   public class GenealogyGraph : NamedItem {
    11     private readonly Dictionary<object, Node> _dictionary;
     31  [Item("Genealogy graph", "Generic class for tracking the evolution of objects.")]
     32  public class GenealogyGraph<T> : NamedItem, IGenealogyGraph<T> where T : class {
     33    private readonly Dictionary<T, GenealogyGraphNode> _dictionary;
    1234
    1335    public GenealogyGraph() {
    14       _dictionary = new Dictionary<object, Node>();
    15     }
    16 
    17     public GenealogyGraph(GenealogyGraph g) {
    18       _dictionary = new Dictionary<object, Node>(g._dictionary);
     36      _dictionary = new Dictionary<T, GenealogyGraphNode>();
     37    }
     38
     39    public GenealogyGraph(GenealogyGraph<T> g) {
     40      _dictionary = new Dictionary<T, GenealogyGraphNode>(g._dictionary);
    1941    }
    2042
    2143    public override IDeepCloneable Clone(Cloner cloner) {
    22       return new GenealogyGraph(this, cloner);
    23     }
    24 
    25     public override string ItemName {
    26       get { return "GenealogyGraph"; }
    27     }
    28 
    29     public override string ItemDescription {
    30       get { return "A graph describing the genealogies of all the individuals"; }
    31     }
    32 
    33     public new Version ItemVersion {
    34       get { return new Version(3, 3, 6); }
    35     }
    36 
    37     public new Image ItemImage {
     44      return new GenealogyGraph<T>(this, cloner);
     45    }
     46
     47    public override Image ItemImage {
    3848      get { return Common.Resources.VSImageLibrary.Graph; }
    3949    }
     
    4454    }
    4555
    46     private GenealogyGraph(GenealogyGraph original, Cloner cloner)
     56    private GenealogyGraph(GenealogyGraph<T> original, Cloner cloner)
    4757      : base(original, cloner) {
    48       _dictionary = new Dictionary<object, Node>(original._dictionary);
    49     }
    50 
    51     public bool HasNode(object t) {
     58      _dictionary = new Dictionary<T, GenealogyGraphNode>(original._dictionary);
     59    }
     60
     61    public bool HasNode(T t) {
    5262      return _dictionary.ContainsKey(t);
    5363    }
    5464
    55     public Node GetNode(object t) {
    56       return this.HasNode(t) ? _dictionary[t] : null;
    57     }
    58 
    59     public IEnumerable<object> Keys {
     65    public GenealogyGraphNode GetNode(T t) {
     66      return HasNode(t) ? _dictionary[t] : null;
     67    }
     68
     69    public IEnumerable<T> Keys {
    6070      get { return _dictionary.Keys; }
    6171    }
    6272
    63     public IEnumerable<Node> Values {
     73    public IEnumerable<GenealogyGraphNode> Values {
    6474      get { return _dictionary.Values; }
    6575    }
    6676
    67     public bool Any() {
    68       return _dictionary.Any();
    69     }
    70 
    71     public bool Any(Func<KeyValuePair<object, Node>, bool> predicate) {
     77    public bool IsEmpty {
     78      get { return !_dictionary.Any(); }
     79    }
     80
     81    public bool Any(Func<KeyValuePair<T, GenealogyGraphNode>, bool> predicate) {
    7282      return _dictionary.Any(predicate);
    7383    }
     
    8191    /// </summary>
    8292    /// <param name="t">The symbolic expression tree</param>
    83     /// <param name="q">The quality value </param>
    84     /// <param name="l">The node label</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>
    8596    /// <param name="elite">Specifies if this node is an elite</param>
    86     public void AddNode(object t, double q = 0.0, string l = "", double g = 0, bool elite = false) {
     97    public void AddNode(T t, double quality = 0.0, string label = "", double rank = 0, bool elite = false, int cutIndex = -1) {
    8798      if (HasNode(t)) return;
    88       var color = new Color { R = (byte)(255 - 255 * q), G = (byte)(255 * q), B = 50 };
    89       _dictionary[t] = new Node { Data = t, Quality = q, Label = l, IsElite = elite, Rank = g, Color = color };
     99      _dictionary[t] = new GenealogyGraphNode { Data = t, Quality = quality, Label = label, IsElite = elite, Rank = rank, CutpointIndex = cutIndex };
    90100    }
    91101
     
    93103    ///  more of a low level method to minimize memory usage when creating and returning subgraphs
    94104    /// </summary>
    95     /// <param name="n"></param>
    96     public void AddNode(Node n) {
    97       var t = n.Data;
    98       if (HasNode(t))
    99         return;
     105    /// <param name="n">The node to be added</param>
     106    public void AddNode(GenealogyGraphNode n) {
     107      var t = (T)n.Data;
     108      if (HasNode(t)) return;
    100109      _dictionary[t] = n;
    101110    }
     
    105114    /// </summary>
    106115    /// <param name="t">The graph node</param>
    107     public void RemoveNode(object t) {
    108       if (!_dictionary.ContainsKey(t))
    109         return;
    110       Node n = _dictionary[t];
     116    public void RemoveNode(T t) {
     117      if (!_dictionary.ContainsKey(t)) return;
     118      GenealogyGraphNode n = _dictionary[t];
    111119      if (n.InEdges != null) {
    112120        foreach (var e in n.InEdges.Where(e => e.Target.OutEdges != null)) {
     
    138146    /// <param name="b"></param>
    139147    /// <param name="label"></param>
    140     public void AddArc(object a, object b, string label = "") {
    141       Node src, dest;
     148    public void AddArc(T a, T b, int opType = 0) {
     149      GenealogyGraphNode src, dest;
    142150      if (!HasNode(a)) {
    143         src = new Node { Data = a };
     151        src = new GenealogyGraphNode { Data = a };
    144152        _dictionary[a] = src;
    145153      } else {
     
    147155      }
    148156      if (!HasNode(b)) {
    149         dest = new Node { Data = b };
     157        dest = new GenealogyGraphNode { Data = b };
    150158        _dictionary[b] = dest;
    151159      } else {
     
    153161      }
    154162      // add forward and reverse arcs
    155       src.AddForwardArc(dest, label);
    156       dest.AddReverseArc(src, label);
    157     }
    158 
    159     public void AddArcs(object[] a, object b, string label) {
    160       Node src, dest;
     163      src.AddForwardArc(dest, opType);
     164      dest.AddReverseArc(src, opType);
     165    }
     166
     167    public void AddArcs(T[] a, T b, int opType = 0) {
     168      GenealogyGraphNode src, dest;
    161169      if (!HasNode(b)) {
    162         dest = new Node { Data = b };
     170        dest = new GenealogyGraphNode { Data = b };
    163171        _dictionary[b] = dest;
    164172      } else {
     
    167175      foreach (var o in a) {
    168176        if (!HasNode(o)) {
    169           src = new Node { Data = o };
     177          src = new GenealogyGraphNode { Data = o };
    170178          _dictionary[o] = src;
    171179        } else {
    172180          src = _dictionary[o];
    173181        }
    174         src.AddForwardArc(dest, label);
    175         dest.AddReverseArc(src, label);
     182        src.AddForwardArc(dest, opType);
     183        dest.AddReverseArc(src, opType);
    176184      }
    177185    }
    178186  }
    179187
    180   public class Node {
     188  public class GenealogyGraphNode : IComparable {
    181189    public string Id { get; private set; }
    182190    public string Label { get; set; }
    183191    public bool IsElite { get; set; }
    184     public List<Arc> InEdges { get; set; }
    185     public List<Arc> OutEdges { get; set; }
    186192    public object Data { get; set; }
    187193    public double Quality { get; set; }
    188194    public double Rank { get; set; }
    189     public Color Color { get; set; }
    190 
    191     public int Degree {
    192       get { return (InEdges == null ? 0 : InEdges.Count) + (OutEdges == null ? 0 : OutEdges.Count); }
    193     }
    194 
    195     public Node() {
     195    public int CutpointIndex { get; set; }
     196    public List<GenealogyGraphArc> InEdges { get; set; }
     197    public List<GenealogyGraphArc> OutEdges { get; set; }
     198
     199    public int Degree { get { return (InEdges == null ? 0 : InEdges.Count) + (OutEdges == null ? 0 : OutEdges.Count); } }
     200
     201    public GenealogyGraphNode() { Id = Guid.NewGuid().ToString(); }
     202
     203    public GenealogyGraphNode(GenealogyGraphNode node) {
    196204      Id = Guid.NewGuid().ToString();
    197     }
    198 
    199     /// <summary>
    200     /// Returns a genealogical graph rooted in the current node, containing all ancestry information
     205      Rank = node.Rank;
     206      Quality = node.Quality;
     207      IsElite = node.IsElite;
     208      Label = node.Label;
     209      Data = node.Data;
     210      InEdges = node.InEdges;
     211      OutEdges = node.OutEdges;
     212      CutpointIndex = node.CutpointIndex;
     213    }
     214
     215    /// <summary>
     216    /// Returns all the ancestors of the current node
    201217    /// </summary>
    202218    /// <returns></returns>
    203     public GenealogyGraph Genealogy() {
    204       var graph = new GenealogyGraph();
    205       graph.AddNode(this);
    206       foreach (var node in this.Ancestors())
    207         graph.AddNode(node);
    208       return graph;
    209     }
    210 
    211     /// <summary>
    212     /// Returns an enumerable of all the ancestors of the current node
    213     /// </summary>
    214     /// <returns></returns>
    215     public IEnumerable<Node> Ancestors() {
    216       var nodes = new HashSet<Node> { this };
     219    public IEnumerable<GenealogyGraphNode> Ancestors() {
     220      var nodes = new HashSet<GenealogyGraphNode> { this };
    217221      int offset = 0;
    218222      int c0 = 1;
     
    231235    }
    232236
    233     public void AddForwardArc(Node target, string label) {
    234       var e = new Arc { Target = target, Label = label };
    235       if (OutEdges == null)
    236         OutEdges = new List<Arc> { e };
    237       else
    238         OutEdges.Add(e);
    239     }
    240 
    241     public void AddReverseArc(Node target, string label) {
    242       var e = new Arc { Target = target, Label = label };
    243       if (InEdges == null)
    244         InEdges = new List<Arc> { e };
    245       else
    246         InEdges.Add(e);
     237    /// <summary>
     238    /// Returns all the descendants of the current node (identical to above method except for using the OutEdges)
     239    /// </summary>
     240    /// <returns></returns>
     241    public IEnumerable<GenealogyGraphNode> Descendants() {
     242      var nodes = new HashSet<GenealogyGraphNode> { this };
     243      int offset = 0;
     244      int c0 = 1;
     245      while (offset != c0) {
     246        int c1 = c0;
     247        for (int i = offset; i != c1; ++i) {
     248          if (nodes.ElementAt(i).OutEdges == null) continue;
     249          foreach (var p in nodes.ElementAt(i).OutEdges.Select(e => e.Target)) {
     250            nodes.Add(p);
     251            yield return p;
     252          }
     253        }
     254        offset = c1;
     255        c0 = nodes.Count;
     256      }
     257    }
     258
     259    public void AddForwardArc(GenealogyGraphNode target, int opType) {
     260      var e = new GenealogyGraphArc { Target = target, OperatorType = opType };
     261      if (OutEdges == null) OutEdges = new List<GenealogyGraphArc> { e };
     262      else OutEdges.Add(e);
     263    }
     264
     265    public void AddReverseArc(GenealogyGraphNode target, int opType) {
     266      var e = new GenealogyGraphArc { Target = target, OperatorType = opType };
     267      if (InEdges == null) InEdges = new List<GenealogyGraphArc> { e };
     268      else InEdges.Add(e);
     269    }
     270
     271    // comparable
     272    // may seem weird, it is actually implemented so higher quality means "less than" in terms of ordering
     273    // if quality is equal, the elite node takes precedence
     274    public int CompareTo(object obj) {
     275      if (obj == null) return 1;
     276      var other = obj as GenealogyGraphNode;
     277      if (other == null) return 1;
     278      if (Quality.Equals(other.Quality)) {
     279        if (IsElite) return -1;
     280        return other.IsElite ? 1 : -1;
     281      }
     282      return other.Quality.CompareTo(Quality);
    247283    }
    248284  }
     
    251287  /// An arc is an edge along with an orientation
    252288  /// </summary>
    253   public class Arc {
    254     public Node Target { get; set; }
    255     public string Label { get; set; }
    256     public double Weight { get; set; }
    257     // other attributes
    258   }
    259   // an edge can be represented as a tuple<Node, Node> TODO: figure it out (might be useful for easier querying)
    260 
    261   public struct Color {
    262     public byte R { get; set; }
    263     public byte G { get; set; }
    264     public byte B { get; set; }
     289  public class GenealogyGraphArc {
     290    public GenealogyGraphNode Target { get; set; }
     291    // OperationType is an identifier for the genetic operation (mutation, crossover) that a graph arc will represent
     292    // So basically it describes which operator was applied to an individual/graph node (the one emitting the arc),
     293    // while Target represents the end result of that operator (node ==GeneticOperation==> Target)
     294    public int OperatorType { get; set; }
     295    // these two fields are not used, but they might be useful later
     296    public string Label { get; set; } // might be useful later
     297    public double Weight { get; set; } // might be useful later
    265298  }
    266299}
  • branches/HeuristicLab.EvolutionaryTracking/HeuristicLab.EvolutionaryTracking/3.4/HeuristicLab.EvolutionaryTracking-3.4.csproj

    r7522 r7779  
    7272    <Reference Include="HeuristicLab.Problems.DataAnalysis.Symbolic.Regression.Views-3.4, Version=3.4.0.0, Culture=neutral, PublicKeyToken=ba48961d6f65dcec, processorArchitecture=MSIL" />
    7373    <Reference Include="HeuristicLab.Problems.DataAnalysis.Symbolic.Views-3.4, Version=3.4.0.0, Culture=neutral, PublicKeyToken=ba48961d6f65dcec, processorArchitecture=MSIL" />
    74     <Reference Include="Microsoft.GLEE">
    75       <HintPath>..\..\..\..\..\..\..\..\Program Files\Microsoft Research\GLEE\bin\Microsoft.GLEE.dll</HintPath>
    76     </Reference>
    77     <Reference Include="Microsoft.GLEE.Drawing">
    78       <HintPath>..\..\..\..\..\..\..\..\Program Files\Microsoft Research\GLEE\bin\Microsoft.GLEE.Drawing.dll</HintPath>
    79     </Reference>
    80     <Reference Include="Microsoft.GLEE.GraphViewerGDI">
    81       <HintPath>..\..\..\..\..\..\..\..\Program Files\Microsoft Research\GLEE\bin\Microsoft.GLEE.GraphViewerGDI.dll</HintPath>
    82     </Reference>
    8374    <Reference Include="System" />
    8475    <Reference Include="System.Core" />
     
    9485    <Compile Include="Analyzers\SymbolicExpressionTreeGenealogyAnalyzer.cs" />
    9586    <Compile Include="GenealogyGraph.cs" />
    96     <Compile Include="GenealogyGraphView.cs">
    97       <SubType>UserControl</SubType>
    98     </Compile>
    99     <Compile Include="GenealogyGraphView.Designer.cs">
    100       <DependentUpon>GenealogyGraphView.cs</DependentUpon>
    101     </Compile>
     87    <Compile Include="Interfaces\IGenealogyGraph.cs" />
    10288    <Compile Include="Plugin.cs" />
    10389    <Compile Include="Properties\AssemblyInfo.cs" />
     90    <Compile Include="SymbolicExpressionTreeGenealogyGraph.cs" />
    10491  </ItemGroup>
    105   <ItemGroup>
    106     <Folder Include="Interfaces\" />
    107   </ItemGroup>
     92  <ItemGroup />
    10893  <ItemGroup>
    10994    <ProjectReference Include="..\..\HeuristicLab.Encodings.SymbolicExpressionTreeEncoding\3.4\HeuristicLab.Encodings.SymbolicExpressionTreeEncoding-3.4.csproj">
  • branches/HeuristicLab.EvolutionaryTracking/HeuristicLab.Tracking.sln

    r7479 r7779  
    1313EndProject
    1414Project("{FAE04EC0-301F-11D3-BF4B-00C04F79EFBC}") = "HeuristicLab.EvolutionaryTracking-3.4", "HeuristicLab.EvolutionaryTracking\3.4\HeuristicLab.EvolutionaryTracking-3.4.csproj", "{1F75CEA3-464F-4A6F-B2F0-04B9841EBC16}"
     15EndProject
     16Project("{FAE04EC0-301F-11D3-BF4B-00C04F79EFBC}") = "HeuristicLab.EvolutionaryTracking.Views-3.4", "HeuristicLab.EvolutionaryTracking.Views\3.4\HeuristicLab.EvolutionaryTracking.Views-3.4.csproj", "{318DFE8C-CA23-4F1B-A4AC-62B425060241}"
    1517EndProject
    1618Global
     
    7072    {1F75CEA3-464F-4A6F-B2F0-04B9841EBC16}.Release|x64.ActiveCfg = Release|Any CPU
    7173    {1F75CEA3-464F-4A6F-B2F0-04B9841EBC16}.Release|x86.ActiveCfg = Release|Any CPU
     74    {318DFE8C-CA23-4F1B-A4AC-62B425060241}.Debug|Any CPU.ActiveCfg = Debug|Any CPU
     75    {318DFE8C-CA23-4F1B-A4AC-62B425060241}.Debug|Any CPU.Build.0 = Debug|Any CPU
     76    {318DFE8C-CA23-4F1B-A4AC-62B425060241}.Debug|Mixed Platforms.ActiveCfg = Debug|Any CPU
     77    {318DFE8C-CA23-4F1B-A4AC-62B425060241}.Debug|Mixed Platforms.Build.0 = Debug|Any CPU
     78    {318DFE8C-CA23-4F1B-A4AC-62B425060241}.Debug|x64.ActiveCfg = Debug|Any CPU
     79    {318DFE8C-CA23-4F1B-A4AC-62B425060241}.Debug|x86.ActiveCfg = Debug|Any CPU
     80    {318DFE8C-CA23-4F1B-A4AC-62B425060241}.Release|Any CPU.ActiveCfg = Release|Any CPU
     81    {318DFE8C-CA23-4F1B-A4AC-62B425060241}.Release|Any CPU.Build.0 = Release|Any CPU
     82    {318DFE8C-CA23-4F1B-A4AC-62B425060241}.Release|Mixed Platforms.ActiveCfg = Release|Any CPU
     83    {318DFE8C-CA23-4F1B-A4AC-62B425060241}.Release|Mixed Platforms.Build.0 = Release|Any CPU
     84    {318DFE8C-CA23-4F1B-A4AC-62B425060241}.Release|x64.ActiveCfg = Release|Any CPU
     85    {318DFE8C-CA23-4F1B-A4AC-62B425060241}.Release|x86.ActiveCfg = Release|Any CPU
    7286  EndGlobalSection
    7387  GlobalSection(SolutionProperties) = preSolution
Note: See TracChangeset for help on using the changeset viewer.