Changeset 10654

Timestamp:

03/24/14 23:50:17 (10 years ago)

Author:

bburlacu

Message:

#1772: Some progress on tracking fragments and building blocks, still incomplete.

Location:

branches/HeuristicLab.EvolutionTracking

Files:

• HeuristicLab.Problems.DataAnalysis.Symbolic.Views/3.4/SymboldDataAnalysisGenealogyView.cs (modified) (4 diffs)
• HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Tracking/SymbolicDataAnalysisExpressionAfterCrossoverOperator.cs (modified) (1 diff)
• HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Tracking/SymbolicDataAnalysisExpressionBeforeCrossoverOperator.cs (modified) (1 diff)

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

@@ -20 +20 @@
 #endregion
 
+using System;
 using System.Collections.Generic;
 using System.Drawing;
@@ -110 +111 @@
         graphChart_highlightMatchingVertices(vertices);
       } else {
-        // perform matching like before
+        // perform matching like it was done before
+        // currently there is no possibility to specify the subtree matching criteria
         var trees = Content.Nodes.Select(x => (ISymbolicExpressionTree)x.Content);
         var matchingTrees = trees.Where(x => x.Root.ContainsSubtree(subtree, comparer));
@@ -174 +176 @@
     }
 
-    private void Trace(IGenealogyGraphNode<ISymbolicExpressionTree> graphNode, ISymbolicExpressionTreeNode subtree, FragmentGraph fragmentGraph, FragmentNode fragmentNode = null) {
-      // add the subtree as a vertex in the fragment graph
-      var fn = new FragmentNode { Content = new Fragment<ISymbolicExpressionTreeNode> { Root = subtree }, Rank = graphNode.Rank };
-      fragmentGraph.AddVertex(fn);
-
-      // maybe we reached the end of the genealogy
+    private void Trace(IGenealogyGraphNode<ISymbolicExpressionTree> graphNode, ISymbolicExpressionTreeNode subtree, FragmentGraph fragmentGraph, FragmentNode parentNode = null) {
       if (graphNode.InArcs == null) return;
-
       // the subtree must belong to the currently displayed tree which in turn must belong to the currently selected graph node
       var tree = graphNode.Content;
@@ -190 +186 @@
       var fragmentLength = fragment.Root.GetLength();
 
-      if (fragment.Index <= index && index < fragment.Index + fragmentLength) {
-        // the selected subtree is contained by the fragment
-        var fn1 = new FragmentNode { Content = fragment };
-        if (fragmentNode != null) {
-          AddChild(fragmentNode, fn1);
-        }
-        fragmentGraph.AddVertex(fn1);
+      if (fragment.Index == index) {
+        // the selected subtree is the actual fragment
+        if (fragmentLength != length) throw new Exception("Fragment and subtree lengths should be the same!");
+
+        var node = new FragmentNode { Content = fragment, Rank = graphNode.Rank };
+
+        if (parentNode != null) {
+          AddChild(parentNode, node);
+        }
+
+        fragmentGraph.AddVertex(node);
+
         graphNode = (IGenealogyGraphNode<ISymbolicExpressionTree>)graphNode.InArcs.Last().Source;
         subtree = graphNode.Content.IterateNodesPrefix().ToList()[fragment.OldIndex];
-        Trace(graphNode, subtree, fragmentGraph, fn1);
-      } else if (fragment.Index > index && fragment.Index < index + length) {
+        Trace(graphNode, subtree, fragmentGraph, node);
+      } else if (fragment.Index < index && index < fragment.Index + fragmentLength) {
+        // the fragment contains the selected subtree 
+        if (length >= fragmentLength) throw new Exception("Fragment contains subtree, so subtree length should be less than the fragment length.");
+
+        var node = new FragmentNode { Content = fragment, Rank = graphNode.Rank };
+        if (parentNode != null) {
+          AddChild(parentNode, node);
+        }
+
+        fragmentGraph.AddVertex(node);
+
+        graphNode = (IGenealogyGraphNode<ISymbolicExpressionTree>)graphNode.InArcs.Last().Source;
+        var i = fragment.Root.IterateNodesPrefix().ToList().IndexOf(subtree);
+        subtree = graphNode.Content.IterateNodesPrefix().ToList()[fragment.OldIndex + i];
+        Trace(graphNode, subtree, fragmentGraph, node);
+
+      } else if (index < fragment.Index && fragment.Index < index + length) {
         // the selected subtree contains the fragment
-        // first trace the fragment, then trace the subtree
-        graphNode = (IGenealogyGraphNode<ISymbolicExpressionTree>)graphNode.InArcs.Last().Source;
-        subtree = graphNode.Content.IterateNodesPrefix().ToList()[fragment.OldIndex];
-
-        var fn0 = new FragmentNode { Content = new Fragment<ISymbolicExpressionTreeNode> { Root = subtree } };
-        var fn1 = new FragmentNode { Content = fragment };
-
-        if (fragmentNode != null) {
-          AddChild(fragmentNode, fn0);
-          AddChild(fragmentNode, fn1);
-        }
-        fragmentGraph.AddVertex(fn0);
-        fragmentGraph.AddVertex(fn1);
+        if (fragmentLength >= length) throw new Exception("Subtree contains fragment, so fragment length should be less than the subtree length.");
+
+        var node = new FragmentNode { Content = new Fragment<ISymbolicExpressionTreeNode> { Root = subtree }, Rank = graphNode.Rank };
+
+        if (parentNode != null) {
+          AddChild(parentNode, node);
+        }
+        fragmentGraph.AddVertex(node);
 
         var graphNode0 = (IGenealogyGraphNode<ISymbolicExpressionTree>)graphNode.InArcs[0].Source;
         var subtree0 = graphNode0.Content.IterateNodesPrefix().ToList()[index];
-        Trace(graphNode0, subtree0, fragmentGraph, fn0);
-
-        var graphNode1 = (IGenealogyGraphNode<ISymbolicExpressionTree>)graphNode.InArcs.Last().Source;
-        var subtree1 = graphNode1.Content.IterateNodesPrefix().ToList()[fragment.OldIndex];
-        Trace(graphNode1, subtree1, fragmentGraph, fn1);
-      } else {
-        // the fragment is not contained by the selected subtree, so we go one level up
-        graphNode = (IGenealogyGraphNode<ISymbolicExpressionTree>)graphNode.InArcs[0].Source;
-        subtree = graphNode.Content.IterateNodesPrefix().ToList()[index];
-        fragmentGraph.Clear(); // restart the trace one level up
-        Trace(graphNode, subtree, fragmentGraph);
+        Trace(graphNode0, subtree0, fragmentGraph, node);
+
+        if (graphNode.InArcs.Count > 1) {
+          var graphNode1 = (IGenealogyGraphNode<ISymbolicExpressionTree>)graphNode.InArcs[1].Source;
+          var subtree1 = graphNode1.Content.IterateNodesPrefix().ToList()[fragment.OldIndex];
+          Trace(graphNode1, subtree1, fragmentGraph, node);
+        }
       }
     }

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

@@ -9 +9 @@
   public class SymbolicDataAnalysisExpressionAfterCrossoverOperator : AfterCrossoverOperator<ISymbolicExpressionTree> {
     public override IOperation Apply() {
-      var childVertex = GenealogyGraph[ChildParameter.ActualValue].Last();
+      var child = ChildParameter.ActualValue;
+      var childVertex = GenealogyGraph[child].Last();
       var arc0 = (IGenealogyGraphArc)childVertex.InArcs[0];
       var arc1 = (IGenealogyGraphArc)childVertex.InArcs[1];
       var nodes0 = (List<ISymbolicExpressionTreeNode>)arc0.Data;
       var nodes1 = (List<ISymbolicExpressionTreeNode>)arc1.Data;
-      var childNodes = ChildParameter.ActualValue.IterateNodesBreadth().ToList();
+      var childNodes = child.IterateNodesPrefix().ToList();
       IFragment<ISymbolicExpressionTreeNode> fragment = null;
-
       for (int i = 0; i < Math.Min(nodes0.Count, childNodes.Count); ++i) {
         if (nodes0[i] == childNodes[i]) continue;
         fragment = new Fragment<ISymbolicExpressionTreeNode> {
           Root = childNodes[i],
-          Index = i
+          Index = i,
         };
+        fragment.OldIndex = nodes1.IndexOf(fragment.Root);
+        break;
       }
       if (fragment == null) throw new Exception("Could not determine fragment!");
-
-      for (int i = 0; i < nodes1.Count; ++i) {
-        if (nodes1[i] != fragment.Root) continue;
-        fragment.OldIndex = i;
-      }
 
       arc0.Data = null;

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

@@ -7 +7 @@
   public class SymbolicDataAnalysisExpressionBeforeCrossoverOperator : BeforeCrossoverOperator<ISymbolicExpressionTree> {
     public override IOperation Apply() {
-      var result = base.Apply();
+      var result = base.Apply(); // the child will be added to the graph before the crossover
       var parents = ParentsParameter.ActualValue.ToList();
       var childVertex = GenealogyGraph[parents[0]].Last(); // use the parent since it is actually the child before crossover (and the ChildParameter doesn't have a value yet)
       //      var parentVertices = ExecutionContext.Scope.SubScopes.Select(s => CurrentGeneration[int.Parse(s.Name)]).ToList();
 
+      // we add the breadth list of nodes of each parent as the data element of the arc from the parent to the child
       for (int i = 0; i < parents.Count; ++i) {
-        var nodes = parents[i].IterateNodesBreadth().ToList();
+        var nodes = parents[i].IterateNodesPrefix().ToList();
         var arc = (IGenealogyGraphArc)childVertex.InArcs[i];
         arc.Data = nodes;