Free cookie consent management tool by TermsFeed Policy Generator

Ignore:
Timestamp:
04/16/14 17:15:33 (11 years ago)
Author:
bburlacu
Message:

#1772: Simplified genealogy graph and fragment graph creation:

  • the genealogy graph now has a 1-1 mapping between content and vertices (as opposed to 1-n as it was previously, to account for elites); this required changes to the directed graph implementation
  • the fragment graph only contains bifurcation points (where the subtree contains the fragment so tracing must be done both ways (in the root parent AND in the other parent). in the other cases, tracing is restarted from the parent genealogy graph node.
Location:
branches/HeuristicLab.EvolutionTracking
Files:
14 edited

Legend:

Unmodified
Added
Removed

  • branches/HeuristicLab.EvolutionTracking/HeuristicLab.EvolutionTracking/3.4/Analyzers/GenealogyAnalyzer.cs

    r10677 r10755  
    191191        instrumentedManipulator.AfterExecutionOperators.Clear();
    192192        instrumentedManipulator.BeforeExecutionOperators.Clear();
    193         if (EnableManipulatorTracking.Value && Manipulator != null) {
     193
     194        if (EnableManipulatorTracking.Value) {
    194195          if (BeforeManipulatorOperator != null) {
    195196            BeforeManipulatorOperator.ChildParameter.ActualName = ManipulatorChildParameterName;
    … …  
    222223        if (elite != null) {
    223224          var vertex = new GenealogyGraphNode<T> {
    224             Content = elite,
     225            Content = (T)elite.Clone(),
    225226            Rank = Generations.Value,
    226227            IsElite = true
    227228          };
    228           var previousVertex = (IGenealogyGraphNode<T>)GenealogyGraph[elite].Last();
     229          var previousVertex = (IGenealogyGraphNode<T>)GenealogyGraph[elite];
    229230          GenealogyGraph.AddVertex(vertex);
    230231          previousVertex.AddForwardArc(vertex);
    231232          vertex.AddReverseArc(previousVertex);
    232233          vertex.Id = previousVertex.Id; // another way would be to introduce the vertex.Id into the scope of the elite
     234          vertex.Quality = previousVertex.Quality;
     235
    233236          if (previousVertex.InArcs.Any()) {
    234237            vertex.InArcs.Last().Data = previousVertex.InArcs.Last().Data; // save the fragment in case there is one
    … …  
    238241      // update qualities
    239242      for (int i = 0; i < population.Count; ++i) {
    240         var individual = population[i];
    241         foreach (var vertex in GenealogyGraph[individual].Cast<IGenealogyGraphNode<T>>()) {
    242           vertex.Quality = qualities[i].Value;
    243         }
     243        var vertex = (IGenealogyGraphNode)GenealogyGraph[population[i]];
     244        vertex.Quality = qualities[i].Value;
    244245      }
    245246

  • branches/HeuristicLab.EvolutionTracking/HeuristicLab.EvolutionTracking/3.4/DirectedGraph/DirectedGraph.cs

    r10677 r10755  
    3838    }
    3939    [Storable]
    40     private readonly Dictionary<object, List<IVertex>> contentMap;
     40    private readonly Dictionary<object, IVertex> contentMap;
    4141    public DirectedGraph() {
    4242      nodes = new List<IVertex>();
    43       contentMap = new Dictionary<object, List<IVertex>>();
     43      contentMap = new Dictionary<object, IVertex>();
    4444    }
    4545    [StorableConstructor]
    … …  
    5050      : base(original, cloner) {
    5151      nodes = new List<IVertex>(original.Nodes);
    52       contentMap = new Dictionary<object, List<IVertex>>(original.contentMap);
     52      contentMap = new Dictionary<object, IVertex>(original.contentMap);
    5353    }
    5454    public override IDeepCloneable Clone(Cloner cloner) {
    … …  
    6262      return contentMap.ContainsKey(content);
    6363    }
    64     public List<IVertex> this[object key] {
     64    public IVertex this[object key] {
    6565      get {
    66         List<IVertex> result;
     66        IVertex result;
    6767        contentMap.TryGetValue(key, out result);
    6868        return result;
    … …  
    8080    }
    8181    public virtual void AddVertex(IVertex vertex) {
     82      if (contentMap.ContainsKey(vertex.Content)) {
     83        throw new Exception("Content already exists in the graph.");
     84      }
     85      contentMap[vertex.Content] = vertex;
    8286      Nodes.Add(vertex);
    83       if (!contentMap.ContainsKey(vertex.Content))
    84         contentMap[vertex.Content] = new List<IVertex>();
    85       contentMap[vertex.Content].Add(vertex);
    8687    }
    8788

  • branches/HeuristicLab.EvolutionTracking/HeuristicLab.EvolutionTracking/3.4/DirectedGraph/Interfaces/IDirectedGraph.cs

    r10300 r10755  
    3232    void RemoveVertex(IVertex vertex);
    3333    List<IVertex> Nodes { get; }
    34     List<IVertex> this[object content] { get; }
     34    IVertex this[object content] { get; }
    3535    bool Contains(object content);
    3636  }

  • branches/HeuristicLab.EvolutionTracking/HeuristicLab.EvolutionTracking/3.4/Fragment.cs

    r10650 r10755  
    88  public class Fragment : Item, IFragment {
    99    [Storable]
    10     public int Index { get; set; }
     10    public int Index1 { get; set; }
    1111
    1212    [Storable]
    13     public int OldIndex { get; set; }
     13    public int Index2 { get; set; }
    1414
    1515    [Storable]
    … …  
    2323      : base(original, cloner) {
    2424      Root = original.Root;
    25       Index = original.Index;
    26       OldIndex = original.OldIndex;
     25      Index1 = original.Index1;
     26      Index2 = original.Index2;
    2727    }
    2828    public override IDeepCloneable Clone(Cloner cloner) {

  • branches/HeuristicLab.EvolutionTracking/HeuristicLab.EvolutionTracking/3.4/GenealogyGraph/GenealogyGraph.cs

    r10677 r10755  
    7171    }
    7272
    73     public new List<IGenealogyGraphNode> this[object content] {
     73    public new IGenealogyGraphNode this[object content] {
    7474      get {
    7575        var result = base[content];
    76         return result != null ? result.Cast<IGenealogyGraphNode>().ToList() : null;
     76        return result == null ? null : (IGenealogyGraphNode)result;
    7777      }
    7878    }
    … …  
    112112    public override void AddVertex(IVertex vertex) {
    113113      var node = (IGenealogyGraphNode<T>)vertex;
    114       if (!Ranks.ContainsKey(node.Rank))
     114      if (!Ranks.ContainsKey(node.Rank)) {
    115115        Ranks[node.Rank] = new LinkedList<IGenealogyGraphNode>();
     116      }
    116117      Ranks[node.Rank].AddLast(node);
    117118      base.AddVertex(vertex);
    … …  
    134135      if (updated != null) updated(sender, args);
    135136    }
    136     public new List<IGenealogyGraphNode<T>> this[object content] {
     137    public new IGenealogyGraphNode<T> this[object content] {
    137138      get {
    138139        var result = base[content];
    139         return result != null ? result.Cast<IGenealogyGraphNode<T>>().ToList() : null;
     140        return result == null ? null : (IGenealogyGraphNode<T>)result;
    140141      }
    141142    }

  • branches/HeuristicLab.EvolutionTracking/HeuristicLab.EvolutionTracking/3.4/Interfaces/IFragment.cs

    r10650 r10755  
    2525  public interface IFragment : IItem {
    2626    object Root { get; set; }
    27     int Index { get; set; }
    28     int OldIndex { get; set; }
     27    int Index1 { get; set; }
     28    int Index2 { get; set; }
    2929  }
    3030

  • branches/HeuristicLab.EvolutionTracking/HeuristicLab.EvolutionTracking/3.4/Operators/BeforeManipulatorOperator.cs

    r10677 r10755  
    4949    public override IOperation Apply() {
    5050      if (GenealogyGraph.Contains(ChildParameter.ActualValue)) {
     51        // if the graph already contains a vertex representing the child, it means that the child is a product of crossover
     52        // when mutation follows after crossover, some changes need to be made
    5153        var child = ChildParameter.ActualValue;
    5254        var clone = (T)child.Clone();
    53         var vChild = (IGenealogyGraphNode<T>)GenealogyGraph[child].Last();
     55        var vChild = (IGenealogyGraphNode<T>)GenealogyGraph[child];
    5456        var vClone = new GenealogyGraphNode<T> { Content = clone, Rank = vChild.Rank - 0.5 };
    5557        GenealogyGraph.AddVertex(vClone);
    5658        // adjust parent-child(clone) relationship in the graph
    57         var parents = vChild.InArcs.Select(a => a.Source);
     59        var parents = vChild.Parents;
     60        // if there's a fragment, save it
     61        IFragment fragment = null;
     62        if (vChild.InArcs.Last().Data != null) {
     63          fragment = (IFragment<T>)vChild.InArcs.Last().Data;
     64        }
    5865        vChild.InArcs = new List<IGenealogyGraphArc>();
    5966        foreach (var p in parents) {
    60           foreach (var a in p.OutArcs) {
    61             if (a.Target == vChild)
    62               a.Target = vClone;
     67          foreach (var a in p.OutArcs.Where(a => a.Target == vChild)) {
     68            a.Target = vClone;
    6369          }
    6470          vClone.AddReverseArc(p);
    … …  
    6672        vChild.AddReverseArc(vClone);
    6773        vClone.AddForwardArc(vChild);
     74        vClone.InArcs.Last().Data = fragment;
    6875      } else { // this needs to be checked
    6976        var vChild = new GenealogyGraphNode<T> { Content = ChildParameter.ActualValue, Rank = Generations.Value };

  • branches/HeuristicLab.EvolutionTracking/HeuristicLab.Problems.DataAnalysis.Symbolic.Views/3.4/Tracking/FragmentGraphView.cs

    r10752 r10755  
    22using System.Drawing;
    33using System.Linq;
     4using HeuristicLab.Common;
    45using HeuristicLab.Core.Views;
    56using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
    … …  
    9394        var aPos = aTile.Position;
    9495
    95         if (node.Content.Index > 0) {
    96           var subtree = node.Content.Root.NodeAt(node.Content.Index);
    97           foreach (var s in subtree.IterateNodesPrefix()) {
     96        if (node.Rank.IsAlmost(0)) {
     97          foreach (var s in node.Content.Root.IterateNodesPrefix()) {
    9898            var primitive = aTile.GetPrimitive(s);
    9999            if (primitive != null) {
    100100              var rpb = primitive as RectangularPrimitiveBase;
    101101              if (rpb != null) {
    102                 rpb.Pen = new Pen(Color.RoyalBlue);
     102                rpb.Pen = new Pen(Color.ForestGreen);
     103              }
     104            }
     105          }
     106        } else {
     107
     108          if (node.Content.Index1 > 0) {
     109            var subtree = node.Content.Root.NodeAt(node.Content.Index1);
     110            foreach (var s in subtree.IterateNodesPrefix()) {
     111              var primitive = aTile.GetPrimitive(s);
     112              if (primitive != null) {
     113                var rpb = primitive as RectangularPrimitiveBase;
     114                if (rpb != null) {
     115                  rpb.Pen = new Pen(Color.RoyalBlue);
     116                }
    103117              }
    104118            }
    … …  
    115129
    116130          if (child == node.Children.First()) {
    117             if (node.Content.Index > 0) {
    118               var subtree = child.Content.Root.NodeAt(node.Content.Index);
     131            if (node.Content.Index1 > 0) {
     132              var subtree = child.Content.Root.NodeAt(node.Content.Index1);
    119133              foreach (var s in subtree.IterateNodesPrefix()) {
    120134                var primitive = bTile.GetPrimitive(s);

  • branches/HeuristicLab.EvolutionTracking/HeuristicLab.Problems.DataAnalysis.Symbolic.Views/3.4/Tracking/SymboldDataAnalysisGenealogyView.cs

    r10752 r10755  
    8181        var fragment = (IFragment<ISymbolicExpressionTreeNode>)graphNode.InArcs.Last().Data;
    8282        if (fragment != null) {
    83           treeChart_HighlightSubtree(fragment.Root);
     83          treeChart_HighlightSubtree(graphNode.Content.NodeAt(fragment.Index1));
    8484        }
    8585      }
    … …  
    101101        var subtreeIndex = graphNode.Content.IterateNodesPrefix().ToList().IndexOf(subtree);
    102102        var fragmentGraph = SymbolicDataAnalysisExpressionTracing.TraceSubtree(graphNode, subtreeIndex);
    103         MainFormManager.MainForm.ShowContent(fragmentGraph); // display the fragment graph on the screen
     103        if (fragmentGraph.Nodes.Any()) {
     104          MainFormManager.MainForm.ShowContent(fragmentGraph); // display the fragment graph on the screen
     105        }
    104106      } else {
    105107        // perform matching like it was done before
    … …  
    108110        var matchingTrees = trees.Where(x => x.Root.ContainsSubtree(subtree, comparer));
    109111
    110         var matchingVertices = matchingTrees.SelectMany(x => Content[x]).Cast<IGenealogyGraphNode<ISymbolicExpressionTree>>();
     112        var matchingVertices = matchingTrees.Select(x => Content[x]).Cast<IGenealogyGraphNode<ISymbolicExpressionTree>>();
    111113        graphChart_highlightMatchingVertices(matchingVertices);
    112114      }

  • branches/HeuristicLab.EvolutionTracking/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Tracking/SymbolicDataAnalysisExpressionAfterCrossoverOperator.cs

    r10752 r10755  
    1010    public override IOperation Apply() {
    1111      var child = ChildParameter.ActualValue;
    12       var childVertex = (IGenealogyGraphNode)GenealogyGraph[child].Last();
     12      var childVertex = (IGenealogyGraphNode)GenealogyGraph[child];
    1313      var arcs = childVertex.InArcs.ToList();
    1414      var nodes0 = (List<ISymbolicExpressionTreeNode>)arcs[0].Data;
    … …  
    2020        fragment = new Fragment<ISymbolicExpressionTreeNode> {
    2121          Root = childNodes[i],
    22           Index = i,
     22          Index1 = i,
    2323        };
    24         fragment.OldIndex = nodes1.IndexOf(fragment.Root);
     24        fragment.Index2 = nodes1.IndexOf(fragment.Root);
    2525        break;
    2626      }

  • branches/HeuristicLab.EvolutionTracking/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Tracking/SymbolicDataAnalysisExpressionAfterManipulatorOperator.cs

    r10677 r10755  
    77
    88namespace HeuristicLab.Problems.DataAnalysis.Symbolic {
    9   public class SymbolicDataAnalysisExpressionAfterManipulatorOperator : BeforeManipulatorOperator<ISymbolicExpressionTree> {
     9  public class SymbolicDataAnalysisExpressionAfterManipulatorOperator : AfterManipulatorOperator<ISymbolicExpressionTree> {
    1010    private readonly SymbolicExpressionTreeNodeSimilarityComparer comparer;
    1111
    … …  
    1919
    2020    public override IOperation Apply() {
    21       var vChild = (IGenealogyGraphNode<ISymbolicExpressionTree>)GenealogyGraph[ChildParameter.ActualValue].First();
     21      var vChild = (IGenealogyGraphNode<ISymbolicExpressionTree>)GenealogyGraph[ChildParameter.ActualValue];
    2222      var nodesBefore = (List<ISymbolicExpressionTreeNode>)vChild.InArcs.First().Data;
    23       var nodesAfter = ChildParameter.ActualValue.IterateNodesBreadth().ToList();
     23      var nodesAfter = ChildParameter.ActualValue.IterateNodesPrefix().ToList();
    2424      IFragment<ISymbolicExpressionTreeNode> fragment = null;
    2525
    2626      for (int i = 0; i < Math.Min(nodesAfter.Count, nodesBefore.Count); ++i) {
    27         if (comparer.Equals(nodesAfter[i], nodesBefore[i])) continue;
     27        var a = nodesAfter[i];
     28        var b = nodesBefore[i];
     29        if (ReferenceEquals(a, b) && comparer.Equals(a, b)) continue;
    2830        fragment = new Fragment<ISymbolicExpressionTreeNode> {
    29           Root = nodesAfter[i],
    30           Index = i
     31          Root = a,
     32          Index1 = i
    3133        };
    3234      }

  • branches/HeuristicLab.EvolutionTracking/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Tracking/SymbolicDataAnalysisExpressionBeforeCrossoverOperator.cs

    r10752 r10755  
    3131      var result = base.Apply(); // the base operator will add the child to the graph before the actual crossover operation takes place
    3232      var parents = ParentsParameter.ActualValue.ToList();
    33       var childVertex = (IGenealogyGraphNode<ISymbolicExpressionTree>)GenealogyGraph[parents[0]].Last(); // use the parent since it is actually the child before crossover (and the ChildParameter doesn't have a value yet)
     33      var childVertex = (IGenealogyGraphNode<ISymbolicExpressionTree>)GenealogyGraph[parents[0]]; // use the parent since it is actually the child before crossover (and the ChildParameter doesn't have a value yet)
    3434      var arcs = childVertex.InArcs.ToList();
    3535

  • branches/HeuristicLab.EvolutionTracking/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Tracking/SymbolicDataAnalysisExpressionBeforeManipulatorOperator.cs

    r10677 r10755  
    77  public class SymbolicDataAnalysisExpressionBeforeManipulatorOperator : BeforeManipulatorOperator<ISymbolicExpressionTree> {
    88    public override IOperation Apply() {
    9       var result = base.Apply();
     9      var result = base.Apply(); // add the vertex in the genealogy graph
    1010
    11       var vChild = (IGenealogyGraphNode<ISymbolicExpressionTree>)GenealogyGraph[ChildParameter.ActualValue].Last();
    12       vChild.InArcs.First().Data = vChild.Content.IterateNodesBreadth().ToList();
     11      var vChild = (IGenealogyGraphNode<ISymbolicExpressionTree>)GenealogyGraph[ChildParameter.ActualValue];
     12      vChild.InArcs.First().Data = vChild.Content.IterateNodesPrefix().ToList();
    1313
    1414      return result;

  • branches/HeuristicLab.EvolutionTracking/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Tracking/SymbolicDataAnalysisExpressionTracing.cs

    r10752 r10755  
    11
     2using System;
    23using System.Collections.Generic;
    34using System.IO;
    … …  
    2425      var index = subtreeIndex; // current index
    2526      var parent = parentNode; // current parent
     27
    2628      while (true) {
     29        if (!node.Parents.Any()) {
     30          var fragmentNode = new FragmentNode {
     31            Content = new Fragment<ISymbolicExpressionTreeNode> { Root = node.Content.NodeAt(index) },
     32            Rank = node.Rank
     33          };
     34          if (parent != null) {
     35            var arc = new GenealogyGraphArc { Source = parent, Target = fragmentNode };
     36            parent.AddForwardArc(arc);
     37            //            fragmentNode.Content.Index1 = parent.Content.Index1;
     38          }
     39          yield return fragmentNode; // no tracing if there are no parents
     40          break;
     41        }
     42
     43        if (node.IsElite) {
     44          node = node.Parents.First();
     45          continue;
     46        } // skip elite, go up the graph to original individual
     47
    2748        var tree = node.Content;
    2849        var subtree = tree.NodeAt(index);
    2950        var subtreeLength = subtree.GetLength();
    30         var fragmentNode = new FragmentNode {
    31           Content = new Fragment<ISymbolicExpressionTreeNode> { Root = subtree },
    32           Rank = node.Rank
    33         };
    34         if (parent != null) {
    35           var arc = new GenealogyGraphArc { Source = parent, Target = fragmentNode };
    36           parent.AddForwardArc(arc);
    37         }
    38         parent = fragmentNode;
    39         yield return fragmentNode;
    40         if (!node.Parents.Any()) break;
    41         if (node.IsElite) {
    42           node = node.Parents.First();
    43           continue;
    44         }
     51
    4552        var fragment = (IFragment<ISymbolicExpressionTreeNode>)node.InArcs.Last().Data;
    4653        if (fragment == null) break;
    4754        var fragmentLength = fragment.Root.GetLength();
    48         if (fragment.Index == index) {
     55
     56        if (fragment.Index1 == index) {
    4957          node = node.Parents.Last(); // take second parent which contains the fragment
    50           index = fragment.OldIndex;
    51         } else if (fragment.Index < index) {
    52           if (fragment.Index + fragmentLength > index) { // fragment contains subtree
    53             node = node.Parents.Last(); // take second parent
    54             index += fragment.OldIndex - fragment.Index;
    55           } else { // fragment distinct from subtree
     58          index = fragment.Index2;
     59        } else if (fragment.Index1 < index) {
     60          if (fragment.Index1 + fragmentLength > index) {
     61            node = node.Parents.Last(); // fragment contains subtree, take second parent
     62            index += fragment.Index2 - fragment.Index1; // the subtree has the same index relative to the fragment
     63          } else {
     64            // fragment distinct from subtree
    5665            node = node.Parents.First(); // take first parent which contains the subtree
    57             index += node.Content.NodeAt(fragment.Index).GetLength() - fragmentLength; // subtreeIndex must be adjusted according to swapped fragments sizes
     66            index += node.Content.NodeAt(fragment.Index1).GetLength() - fragmentLength; // subtreeIndex must be adjusted according to swapped fragments sizes
    5867          }
    59         } else if (fragment.Index > index) {
    60           if (fragment.Index < index + subtreeLength) { // subtree contains fragment => bifurcation point in the fragment graph
    61             fragmentNode.Content.Index = fragment.Index - index;
     68        } else if (fragment.Index1 > index) {
     69          if (fragment.Index1 < index + subtreeLength) {
     70            // subtree contains fragment => bifurcation point in the fragment graph
     71            var fragmentNode = new FragmentNode {
     72              Content = new Fragment<ISymbolicExpressionTreeNode> { Root = subtree },
     73              Rank = node.Rank
     74            };
     75            if (parent != null) {
     76              var arc = new GenealogyGraphArc { Source = parent, Target = fragmentNode };
     77              parent.AddForwardArc(arc);
     78            }
     79            fragmentNode.Content.Index1 = fragment.Index1 - index;
     80            yield return fragmentNode;
     81
    6282            var left = Trace(node.Parents.First(), index, fragmentNode); // trace subtree
    63             var right = Trace(node.Parents.Last(), fragment.OldIndex, fragmentNode); // trace fragment
    64             foreach (var v in left.Concat(right)) { yield return v; }
     83
     84            if (node.Parents.Last().Content.NodeAt(fragment.Index2).GetLength() != fragmentLength) {
     85              throw new Exception("Fragment lengths should match!");
     86            }
     87            var right = Trace(node.Parents.Last(), fragment.Index2, fragmentNode); // trace fragment
     88            foreach (var v in left.Concat(right)) {
     89              yield return v;
     90            }
    6591            break;
     92          } else {
     93            node = node.Parents.First(); // fragment distinct from subtree: update node, index remains unchanged
    6694          }
    67           node = node.Parents.First(); // fragment distinct from subtree: update node, index remains unchanged
    6895        }
    6996      }
Note: See TracChangeset for help on using the changeset viewer.