Changeset 10752

Timestamp:

04/15/14 17:08:35 (11 years ago)

Author:

bburlacu

Message:

#1772: Refactored subtree tracing functionality and moved it from the view into a separate static class. Shortened symbol names in the FragmentGraphView so that trees are displayed more nicely.

Location:

branches/HeuristicLab.EvolutionTracking

Files:

• HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.Views/3.4/SymbolicExpressionTreeTile.cs (modified) (2 diffs)
• HeuristicLab.Problems.DataAnalysis.Symbolic.Views/3.4/Tracking/FragmentGraphView.cs (modified) (4 diffs)
• HeuristicLab.Problems.DataAnalysis.Symbolic.Views/3.4/Tracking/SymboldDataAnalysisGenealogyView.cs (modified) (5 diffs)
• HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/HeuristicLab.Problems.DataAnalysis.Symbolic-3.4.csproj (modified) (1 diff)
• HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Tracking/SymbolicDataAnalysisExpressionAfterCrossoverOperator.cs (modified) (1 diff)
• HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Tracking/SymbolicDataAnalysisExpressionBeforeCrossoverOperator.cs (modified) (2 diffs)
• HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Tracking/SymbolicDataAnalysisExpressionTracing.cs (added)

branches/HeuristicLab.EvolutionTracking/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.Views/3.4/SymbolicExpressionTreeTile.cs

@@ -142 +142 @@
 
         RectangularPrimitiveBase rectangularPrimitive;
+        var label = ShortenLabel(node);
         if (node.SubtreeCount == 0) {
-          rectangularPrimitive = new Rectangle(Chart, lowerLeft, upperRight) { Font = font, Text = visualNode.Content.ToString() };
+          rectangularPrimitive = new Rectangle(Chart, lowerLeft, upperRight) { Font = font, Text = label };
         } else {
-          rectangularPrimitive = new Ellipse(Chart, lowerLeft, upperRight) { Font = font, Text = visualNode.Content.ToString() };
+          rectangularPrimitive = new Ellipse(Chart, lowerLeft, upperRight) { Font = font, Text = label };
         }
 
@@ -202 +203 @@
       base.Draw(graphics);
     }
+
+    private string ShortenLabel(ISymbolicExpressionTreeNode node) {
+      var term = node as SymbolicExpressionTreeTerminalNode;
+      if (term != null) {
+        var parts = term.ToString().Split(' '); // split by space
+        if (parts.Length == 1) {
+          return parts[0].Substring(0, 5);
+        } else {
+          return parts[0].Substring(0, 5) + parts[1];
+        }
+      }
+      return node.Symbol.ToString().Substring(0, 3);
+    }
   }
 }

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

@@ -93 +93 @@
         var aPos = aTile.Position;
 
-        // mark swapped fragment
-        if (node.Content.Index != 0) {
+        if (node.Content.Index > 0) {
           var subtree = node.Content.Root.NodeAt(node.Content.Index);
           foreach (var s in subtree.IterateNodesPrefix()) {
@@ -102 +101 @@
               if (rpb != null) {
                 rpb.Pen = new Pen(Color.RoyalBlue);
-              }
-            }
-          }
-        }
-
-        // mark the subtree that was replaced by the fragment
-        if (node.Children.Any() && node.Content.Index != 0) {
-          var child = node.Children.First();
-          {
-            var subtree = child.Content.Root.NodeAt(node.Content.Index);
-            var tile = tileDictionary[child].Tile;
-            foreach (var s in subtree.IterateNodesPrefix()) {
-              var primitive = tile.GetPrimitive(s);
-              if (primitive != null) {
-                var rpb = primitive as RectangularPrimitiveBase;
-                if (rpb != null) {
-                  rpb.Pen = new Pen(Color.DarkOrange);
-                }
               }
             }
@@ -133 +114 @@
           symbolicExpressionChartControl.Add(line);
 
-
+          if (child == node.Children.First()) {
+            if (node.Content.Index > 0) {
+              var subtree = child.Content.Root.NodeAt(node.Content.Index);
+              foreach (var s in subtree.IterateNodesPrefix()) {
+                var primitive = bTile.GetPrimitive(s);
+                if (primitive != null) {
+                  var rpb = primitive as RectangularPrimitiveBase;
+                  if (rpb != null) {
+                    rpb.Pen = new Pen(Color.DarkOrange);
+                  }
+                }
+              }
+            }
+          }
         }
       }
@@ -173 +167 @@
   }
 
+  internal static class Util {
+    internal static ISymbolicExpressionTreeNode NodeAt(this ISymbolicExpressionTree tree, int position) {
+      return NodeAt(tree.Root, position);
+    }
+    internal static ISymbolicExpressionTreeNode NodeAt(this ISymbolicExpressionTreeNode root, int position) {
+      return root.IterateNodesPrefix().ElementAt(position);
+    }
+  }
+
   internal class TileLayoutNode {
     public SymbolicExpressionTreeTile Tile { get; set; }

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

@@ -20 +20 @@
 #endregion
 
-using System;
 using System.Collections.Generic;
 using System.Drawing;
-using System.IO;
 using System.Linq;
 using System.Windows.Forms;
@@ -33 +31 @@
 using HeuristicLab.MainForm;
 
-using FragmentGraph = HeuristicLab.EvolutionTracking.IGenealogyGraph<HeuristicLab.EvolutionTracking.IFragment<HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.ISymbolicExpressionTreeNode>>;
-using FragmentNode = HeuristicLab.EvolutionTracking.GenealogyGraphNode<HeuristicLab.EvolutionTracking.IFragment<HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.ISymbolicExpressionTreeNode>>;
 
 namespace HeuristicLab.Problems.DataAnalysis.Symbolic.Views {
@@ -84 +80 @@
       if (graphNode.InArcs.Any()) {
         var fragment = (IFragment<ISymbolicExpressionTreeNode>)graphNode.InArcs.Last().Data;
-        treeChart_HighlightSubtree(fragment.Root);
+        if (fragment != null) {
+          treeChart_HighlightSubtree(fragment.Root);
+        }
       }
     }
@@ -100 +98 @@
       if (trace) {
         // perform fragment tracing
-        var fragmentGraph = TraceSubtree(subtree);
+        var graphNode = (IGenealogyGraphNode<ISymbolicExpressionTree>)genealogyGraphChart.SelectedGraphNode;
+        var subtreeIndex = graphNode.Content.IterateNodesPrefix().ToList().IndexOf(subtree);
+        var fragmentGraph = SymbolicDataAnalysisExpressionTracing.TraceSubtree(graphNode, subtreeIndex);
         MainFormManager.MainForm.ShowContent(fragmentGraph); // display the fragment graph on the screen
       } else {
@@ -159 +159 @@
     }
     #endregion
-
-    #region fragment tracing
-    private FragmentGraph TraceSubtree(ISymbolicExpressionTreeNode subtree) {
-      var graphNode = (IGenealogyGraphNode<ISymbolicExpressionTree>)genealogyGraphChart.SelectedGraphNode;
-      var graph = new GenealogyGraph<IFragment<ISymbolicExpressionTreeNode>>();
-      Trace(graphNode, subtree, graph);
-      return graph;
-    }
-
-    private static void Trace(IGenealogyGraphNode<ISymbolicExpressionTree> graphNode, ISymbolicExpressionTreeNode subtree, FragmentGraph fragmentGraph, FragmentNode parentNode = null) {
-      while (true) {
-        if (!graphNode.InArcs.Any()) return;
-
-        var parentVertices = graphNode.Parents.ToList();
-        // the subtree must belong to the currently displayed tree which in turn must belong to the currently selected graph node
-        var tree = graphNode.Content;
-        var subtreeIndex = tree.IndexOf(subtree);
-        var subtreeLength = subtree.GetLength();
-
-        var fragment = (IFragment<ISymbolicExpressionTreeNode>)graphNode.InArcs.Last().Data;
-        if (fragment == null) return;
-        var fragmentLength = fragment.Root.GetLength();
-
-        var fragmentNode = new FragmentNode {
-          Content = new Fragment<ISymbolicExpressionTreeNode> {
-            Root = subtree,
-          },
-          Rank = graphNode.Rank
-        };
-
-        if (parentNode != null) {
-          if (parentNode == fragmentNode) {
-            throw new Exception("Node cannot be a child of itself!");
-          }
-          var arc = new GenealogyGraphArc { Source = parentNode, Target = fragmentNode };
-          parentNode.AddForwardArc(arc);
-        }
-        fragmentGraph.AddVertex(fragmentNode);
-
-        parentNode = fragmentNode;
-
-        // if the selected subtree is the actual fragment
-        if (fragment.Index == subtreeIndex) {
-          if (fragmentLength != subtreeLength) throw new Exception("Fragment and subtree lengths should be the same!");
-          graphNode = parentVertices.Last();
-          tree = graphNode.Content;
-          subtree = tree.NodeAt(fragment.OldIndex);
-          continue;
-        }
-        // if the fragment contains the selected subtree => track fragment, then track subtree
-        if (fragment.Index < subtreeIndex && subtreeIndex < fragment.Index + fragmentLength) {
-          if (subtreeLength >= fragmentLength) throw new Exception("Fragment contains subtree, so subtree length should be less than the fragment length.");
-
-          graphNode = parentVertices.Last();
-          tree = graphNode.Content;
-          var i = fragment.Root.IndexOf(subtree); // get the index of the selected subtree, relative to the fragment root
-          subtree = tree.NodeAt(fragment.OldIndex + i);
-          continue;
-        }
-        // if the selected subtree contains the fragment => track fragment and subtree
-        if (subtreeIndex < fragment.Index && fragment.Index < subtreeIndex + subtreeLength) {
-          if (fragmentLength >= subtreeLength) throw new Exception("Subtree contains fragment, so fragment length should be less than the subtree length.");
-          fragmentNode.Content.Index = fragment.Index - subtreeIndex;
-          graphNode = parentVertices[0];
-          // debug check
-          tree = graphNode.Content;
-          subtree = tree.NodeAt(subtreeIndex);
-          if (subtree.GetLength() <= fragmentNode.Content.Index) {
-            throw new Exception("Index exceeds subtree length.");
-          }
-          // track subtree
-          Trace(graphNode, subtree, fragmentGraph, fragmentNode);
-
-          // track fragment
-          if (parentVertices.Count > 1) {
-            // save the index of the current fragment in the tree where it was swapped
-            graphNode = parentVertices[1];
-            tree = graphNode.Content;
-            subtree = tree.NodeAt(fragment.OldIndex);
-            continue;
-          }
-        } else {
-          // fragment and subtree are completely distinct => we only track the subtree (contained by the root parent)
-          // if the subtree comes AFTER the fragment in the prefix iteration of nodes, 
-          // then its index is affected by the difference in fragment size between current tree and parent
-          graphNode = parentVertices[0];
-          tree = graphNode.Content;
-          if (subtreeIndex > fragment.Index) {
-            var diff = tree.NodeAt(fragment.Index).GetLength() - fragmentLength;
-            subtreeIndex += diff;
-          }
-          subtree = tree.NodeAt(subtreeIndex);
-          continue;
-        }
-        break;
-      }
-    }
-    #endregion
-  }
-
-  internal static class Util {
-    private static string ViewAsText(this ISymbolicExpressionTreeNode root) {
-      var writer = new StringWriter();
-      SymbolicExpressionTreeHierarchicalFormatter.RenderNode(writer, root, string.Empty);
-      return writer.ToString();
-    }
-    #region some helper methods for shortening the tracing code
-
-    internal static void AddChild(this IGenealogyGraphNode parent, IGenealogyGraphNode child) {
-      parent.AddForwardArc(child);
-      child.AddReverseArc(parent);
-      child.Rank = parent.Rank - 1;
-    }
-    internal static ISymbolicExpressionTreeNode NodeAt(this ISymbolicExpressionTree tree, int position) {
-      return NodeAt(tree.Root, position);
-    }
-    internal static ISymbolicExpressionTreeNode NodeAt(this ISymbolicExpressionTreeNode root, int position) {
-      return root.IterateNodesPrefix().ElementAt(position);
-    }
-    internal static int IndexOf(this ISymbolicExpressionTree tree, ISymbolicExpressionTreeNode node) {
-      return IndexOf(tree.Root, node);
-    }
-    internal static int IndexOf(this ISymbolicExpressionTreeNode root, ISymbolicExpressionTreeNode node) {
-      int i = 0;
-      foreach (var n in root.IterateNodesPrefix()) {
-        if (n == node) return i;
-        ++i;
-      }
-      return -1;
-    }
-    #endregion
   }
 }

branches/HeuristicLab.EvolutionTracking/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/HeuristicLab.Problems.DataAnalysis.Symbolic-3.4.csproj

@@ -304 +304 @@
     <Compile Include="Tracking\SymbolicDataAnalysisExpressionAfterManipulatorOperator.cs" />
     <Compile Include="Tracking\SymbolicDataAnalysisExpressionBeforeManipulatorOperator.cs" />
+    <Compile Include="Tracking\SymbolicDataAnalysisExpressionTracing.cs" />
     <None Include="HeuristicLab.snk" />
     <None Include="Plugin.cs.frame" />

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

@@ -25 +25 @@
         break;
       }
-      if (fragment == null) throw new Exception("Could not determine fragment!");
+      // if the fragment is null then it means crossover did not do anything
+      //      if (fragment == null) throw new Exception("Could not determine fragment!");
 
       arcs[0].Data = null;

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

@@ -29 +29 @@
   public class SymbolicDataAnalysisExpressionBeforeCrossoverOperator : BeforeCrossoverOperator<ISymbolicExpressionTree> {
     public override IOperation Apply() {
-      var result = base.Apply(); // the child will be added to the graph before the crossover
+      var result = base.Apply(); // the base operator will add the child to the graph before the actual crossover operation takes place
       var parents = ParentsParameter.ActualValue.ToList();
       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)
@@ -38 +38 @@
         arcs[i].Data = nodes;
       }
-      var parentVertices = childVertex.InArcs.Select(x => (IGenealogyGraphNode<ISymbolicExpressionTree>)x.Source).ToList();
+      var parentVertices = childVertex.Parents.ToList();
       if (parents[0].Length != parentVertices[0].Content.Length || parents[1].Length != parentVertices[1].Content.Length) {
         throw new Exception("Inconsistency detected in GenealogyGraph.");