Changeset 13424

Timestamp:

12/01/15 00:10:20 (9 years ago)

Author:

bburlacu

Message:

#1772: Fixed bug due to incorrect caching in the traceMap where in some cases trace graph arcs could contain incorrect trace data (this does not affect or invalidate any previous tracing results as arc information is only being used for visualization). Simplified code by removing the traceMap completely and passing the indices directly to the trace method.

File:

• branches/HeuristicLab.EvolutionTracking/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Tracking/TraceCalculator.cs (modified) (8 diffs)

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

@@ -34 +34 @@
   [StorableClass]
   public class TraceCalculator : Item {
-    private Dictionary<IGenealogyGraphNode<ISymbolicExpressionTree>, TraceData> traceMap;
     private Dictionary<ISymbolicExpressionTree, List<ISymbolicExpressionTreeNode>> nodeListCache;
     private HashSet<Tuple<IGenealogyGraphNode<ISymbolicExpressionTree>, IGenealogyGraphNode<ISymbolicExpressionTree>, int>> traceCache;
@@ -60 +59 @@
     public void ResetState() {
       TraceGraph = new GenealogyGraph<ISymbolicExpressionTree>();
-      traceMap = new Dictionary<IGenealogyGraphNode<ISymbolicExpressionTree>, TraceData>();
       nodeListCache = new Dictionary<ISymbolicExpressionTree, List<ISymbolicExpressionTreeNode>>();
       traceCache = new HashSet<Tuple<IGenealogyGraphNode<ISymbolicExpressionTree>, IGenealogyGraphNode<ISymbolicExpressionTree>, int>>();
@@ -101 +99 @@
     /// <param name="subtreeIndex">The index of the traced subtree</param>
     /// <param name="last">The last added node in the trace graph</param>
-    private void TraceRecursive(IGenealogyGraphNode<ISymbolicExpressionTree> node, int subtreeIndex, IGenealogyGraphNode<ISymbolicExpressionTree> last = null) {
+    /// <param name="lastSi">The subtree index in the last added individual</param>
+    /// <param name="lastFi">The fragment index in the last added individual</param>
+    private void TraceRecursive(IGenealogyGraphNode<ISymbolicExpressionTree> node, int subtreeIndex, IGenealogyGraphNode<ISymbolicExpressionTree> last = null, int lastSi = -1, int lastFi = -1) {
       var g = node;
       int si = subtreeIndex; // subtree index
       int fi = 0; // fragment index
       while (((List<IArc>)((IVertex)g).InArcs).Count > 0) {
-        Debug.Assert(si < g.Data.Length);
+        if (!(si < g.Data.Length)) throw new ArgumentOutOfRangeException("The subtree index exceeds the size of the tree.");
         var inArcs = (List<IArc>)((IVertex)g).InArcs;
         var fragment = (IFragment<ISymbolicExpressionTreeNode>)((IGenealogyGraphArc)inArcs.Last()).Data;
@@ -144 +144 @@
             if (fi < si + sl) {
               // subtree contains fragment => branching point in the fragment graph
-              var n = AddTraceNode(g, si, fi); // current node becomes "last" as we restart tracing from the parent
+              var n = AddTraceNode(g); // current node becomes "last" as we restart tracing from the parent
               var t0 = new Tuple<IGenealogyGraphNode<ISymbolicExpressionTree>, IGenealogyGraphNode<ISymbolicExpressionTree>, int>(parent0, n, si);
               if (!(CacheTraceNodes && traceCache.Contains(t0))) {
-                TraceRecursive(parent0, si, n);
+                TraceRecursive(parent0, si, n, si, fi);
                 traceCache.Add(t0);
               }
               var t1 = new Tuple<IGenealogyGraphNode<ISymbolicExpressionTree>, IGenealogyGraphNode<ISymbolicExpressionTree>, int>(parent1, n, fragment.Index2);
               if (!(CacheTraceNodes && traceCache.Contains(t1))) {
-                TraceRecursive(parent1, fragment.Index2, n);
+                TraceRecursive(parent1, fragment.Index2, n, si, fi);
                 traceCache.Add(t1);
               }
@@ -172 +172 @@
           // check if the subtree and the fragment overlap => branch out
           if ((si == fi) || (si < fi && fi < si + sl) || (fi < si && si < fi + fl)) {
-            var n = AddTraceNode(g, si, fi); // current node becomes "last" as we restart tracing from the parent
+            var n = AddTraceNode(g); // current node becomes "last" as we restart tracing from the parent
             int i = si < fi ? si : fi;
             var t = new Tuple<IGenealogyGraphNode<ISymbolicExpressionTree>, IGenealogyGraphNode<ISymbolicExpressionTree>, int>(parent0, n, i);
             if (!(CacheTraceNodes && traceCache.Contains(t))) {
-              TraceRecursive(parent0, i, n);
+              TraceRecursive(parent0, i, n, si, fi);
               traceCache.Add(t);
             }
@@ -193 +193 @@
       // when we are out of the while the last vertex must be connected with the current one
       // if there is no last vertex, it means the tracing reached the top of the genealogy graph
-      var current = AddTraceNode(g, si, fi);
-      if (last != null)
-        ConnectLast(current, last, si, fi);
+      if (last != null) {
+        var current = AddTraceNode(g);
+        if (current.Rank.IsAlmost(0)) fi = -1; // if current is part of the initial population there will be no fragment
+        var td = new TraceData(si, fi, lastSi, lastFi);
+#if DEBUG
+        var currentLength = current.Data.Length;
+        var lastLength = last.Data.Length;
+
+        if (!(si < currentLength))
+          throw new ArgumentOutOfRangeException(string.Format("Subtree index {0} exceeds tree length ({1}", si, currentLength));
+
+        if (!(fi < currentLength))
+          throw new ArgumentOutOfRangeException(string.Format("Fragment index {0} exceeds tree length ({1}", fi, currentLength));
+
+        if (!(lastSi < lastLength))
+          throw new ArgumentOutOfRangeException(string.Format("Last subtree index {0} exceeds tree length ({1}", lastSi, lastLength));
+
+        if (!(lastFi < lastLength))
+          throw new ArgumentOutOfRangeException(string.Format("Last fragment index {0} exceeds tree length ({1}", lastFi, lastLength));
+#endif
+        ConnectLast(current, last, td);
+      }
     }
 
@@ -206 +225 @@
     /// <param name="fi">The fragment index</param>
     /// <returns></returns>
-    private IGenealogyGraphNode<ISymbolicExpressionTree> AddTraceNode(IGenealogyGraphNode<ISymbolicExpressionTree> g, int si, int fi) {
+    private IGenealogyGraphNode<ISymbolicExpressionTree> AddTraceNode(IGenealogyGraphNode<ISymbolicExpressionTree> g) {
       var n = TraceGraph.GetByContent(g.Data);
       if (n == null) {
         n = g.Copy();
         TraceGraph.AddVertex(n);
-        Debug.Assert(!traceMap.ContainsKey(n));
-        traceMap[n] = new TraceData(si, fi, -1, -1); // only the first two fields are needed
       }
       return n;
@@ -234 +251 @@
     /// </summary>
     /// <param name="current">The current node in the genealogy graph</param>
-    /// <param name="last">The last added node in the trace graph</param>   
-    /// <param name="si">The index of the traced subtree</param>
-    /// <param name="fi">The index of the fragment</param>
-    private void ConnectLast(IGenealogyGraphNode<ISymbolicExpressionTree> current, IGenealogyGraphNode<ISymbolicExpressionTree> last, int si, int fi) {
-      var lastTraceData = traceMap[last];
-      int lastSi = lastTraceData.SubtreeIndex; // last subtree index (index of the traced subtree in the previous trace node)
-      int lastFi = lastTraceData.FragmentIndex; // last fragment index (index of the fragment in the previous trace node)
-      var td = new TraceData(si, fi, lastSi, lastFi); // trace data
-
+    /// <param name="last">The last added node in the trace graph</param>
+    /// <param name="td">The trace data specifying the preorder indices of the subtree and fragment in the @current and @last vertices</param>   
+    private void ConnectLast(IGenealogyGraphNode<ISymbolicExpressionTree> current, IGenealogyGraphNode<ISymbolicExpressionTree> last, TraceData td) {
       // TODO: more testing
       var inArcs = (List<IArc>)((IVertex)last).InArcs; // using the InArcs seems to be slightly more efficient than using the OutArcs