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

Timestamp:

03/19/15 01:10:21 (9 years ago)

Author:

bburlacu

Message:

#1772: Work in progress for calculating sampling counts for subtrees in the population: updated TraceCalculator to aggregate tracing statistics, updated SymbolicDataAnalysisGenealogyGraphView, added SymbolicDataAnalysisSubtreeSampleCountAnalyzer.

File:

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

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

@@ -39 +39 @@
     public IGenealogyGraph<ISymbolicExpressionTree> TraceGraph { get; private set; }
 
+    public bool UpdateVertexWeights { get; set; }
+    public bool UpdateSubtreeWeights { get; set; }
+    public bool CacheTraceNodes { get; set; }
+
     public TraceCalculator() {
+      ResetState();
+    }
+
+    protected TraceCalculator(TraceCalculator original, Cloner cloner)
+      : base(original, cloner) {
+    }
+
+    public override IDeepCloneable Clone(Cloner cloner) {
+      return new TraceCalculator(this, cloner);
+    }
+
+    public void ResetState() {
       TraceGraph = new GenealogyGraph<ISymbolicExpressionTree>();
       traceMap = new Dictionary<IGenealogyGraphNode<ISymbolicExpressionTree>, TraceData>();
@@ -46 +62 @@
     }
 
-    protected TraceCalculator(TraceCalculator original, Cloner cloner)
-      : base(original, cloner) {
-    }
-
-    public override IDeepCloneable Clone(Cloner cloner) {
-      return new TraceCalculator(this, cloner);
-    }
-
-    public static IGenealogyGraph<ISymbolicExpressionTree> TraceSubtree(
-      IGenealogyGraphNode<ISymbolicExpressionTree> node, int subtreeIndex) {
-      var tc = new TraceCalculator();
+    public static IGenealogyGraph<ISymbolicExpressionTree> TraceSubtree(IGenealogyGraphNode<ISymbolicExpressionTree> node, int subtreeIndex, bool updateVertexWeights = false, bool updateSubtreeWeights = false, bool cacheTraceNodes = true) {
+      var tc = new TraceCalculator {
+        UpdateVertexWeights = updateSubtreeWeights,
+        UpdateSubtreeWeights = updateSubtreeWeights,
+        CacheTraceNodes = cacheTraceNodes
+      };
       tc.Trace(node, subtreeIndex);
       return tc.TraceGraph;
     }
 
-    public IGenealogyGraph<ISymbolicExpressionTree> Trace(IGenealogyGraphNode<ISymbolicExpressionTree> node, int subtreeIndex) {
-      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>>();
+    public IGenealogyGraph<ISymbolicExpressionTree> Trace(IGenealogyGraphNode<ISymbolicExpressionTree> node, int subtreeIndex, bool resetState = true) {
+      if (resetState) ResetState();
       TraceRecursive(node, subtreeIndex);
       return TraceGraph;
@@ -90 +98 @@
     /// <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) {
+    private void TraceRecursive(IGenealogyGraphNode<ISymbolicExpressionTree> node, int subtreeIndex, IGenealogyGraphNode<ISymbolicExpressionTree> last = null) {
       var g = node;
       int si = subtreeIndex; // subtree index
       int fi = 0; // fragment index
       while (((List<IArc>)((IVertex)g).InArcs).Count > 0) {
-        //      while (g.Parents.Any()) {
         Debug.Assert(si < g.Data.Length);
         var inArcs = (List<IArc>)((IVertex)g).InArcs;
@@ -138 +144 @@
               var n = AddTraceNode(g, si, fi); // current node becomes "last" as we restart tracing from the parent
               var t0 = new Tuple<IGenealogyGraphNode<ISymbolicExpressionTree>, IGenealogyGraphNode<ISymbolicExpressionTree>, int>(parent0, n, si);
-              if (!traceCache.Contains(t0)) {
+              if (!(CacheTraceNodes && traceCache.Contains(t0))) {
                 TraceRecursive(parent0, si, n);
                 traceCache.Add(t0);
-              } else {
+              }
+              if (UpdateVertexWeights)
                 n.Weight++;
-              }
               var t1 = new Tuple<IGenealogyGraphNode<ISymbolicExpressionTree>, IGenealogyGraphNode<ISymbolicExpressionTree>, int>(parent1, n, fragment.Index2);
-              if (!traceCache.Contains(t1)) {
+              if (!(CacheTraceNodes && traceCache.Contains(t1))) {
                 TraceRecursive(parent1, fragment.Index2, n);
                 traceCache.Add(t1);
-              } else {
+              }
+              // gather statistics about sampled individuals and sampled subtrees
+              if (UpdateVertexWeights)
                 n.Weight++;
+              if (UpdateSubtreeWeights) {
+                var arcs = (List<IArc>)((IVertex)n).InArcs; // at this moment n will have been added as a child to the next trace node
+                for (int i = 0; i < arcs.Count; ++i) {
+                  var td = (TraceData)((IArc<IDeepCloneable>)arcs[i]).Data;
+                  var p = (IGenealogyGraphNode<ISymbolicExpressionTree>)arcs[i].Source;
+                  // TODO: the first part of the check below represents a necessary but not sufficient condition
+                  // TODO: therefore, a Difference check is also performed, it would be nice to make this code more ellegant
+                  if (td.LastFragmentIndex == td.SubtreeIndex && fragment.Root.Difference(NodeAt(p.Data, td.SubtreeIndex)) == null) {
+                    arcs[i].Weight++;
+                    break;
+                  }
+                }
               }
               break;
@@ -171 +191 @@
             int i = si < fi ? si : fi;
             var t = new Tuple<IGenealogyGraphNode<ISymbolicExpressionTree>, IGenealogyGraphNode<ISymbolicExpressionTree>, int>(parent0, n, i);
-            if (!traceCache.Contains(t)) {
+            if (!(CacheTraceNodes && traceCache.Contains(t))) {
               TraceRecursive(parent0, i, n);
               traceCache.Add(t);
-            } else {
+            }
+            if (UpdateVertexWeights)
               n.Weight++;
-            }
             break;
           } else {
@@ -204 +224 @@
     /// <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, int si, int fi) {
       var n = TraceGraph.GetByContent(g.Data);
       if (n == null) {
@@ -239 +258 @@
       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)
+      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
       // using the inArcs seems to be slightly more efficient than using the outArcs