Changeset 13424


Ignore:
Timestamp:
12/01/15 00:10:20 (5 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:
1 edited

Legend:

Unmodified
Added
Removed
  • branches/HeuristicLab.EvolutionTracking/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Tracking/TraceCalculator.cs

    r12966 r13424  
    3434  [StorableClass]
    3535  public class TraceCalculator : Item {
    36     private Dictionary<IGenealogyGraphNode<ISymbolicExpressionTree>, TraceData> traceMap;
    3736    private Dictionary<ISymbolicExpressionTree, List<ISymbolicExpressionTreeNode>> nodeListCache;
    3837    private HashSet<Tuple<IGenealogyGraphNode<ISymbolicExpressionTree>, IGenealogyGraphNode<ISymbolicExpressionTree>, int>> traceCache;
     
    6059    public void ResetState() {
    6160      TraceGraph = new GenealogyGraph<ISymbolicExpressionTree>();
    62       traceMap = new Dictionary<IGenealogyGraphNode<ISymbolicExpressionTree>, TraceData>();
    6361      nodeListCache = new Dictionary<ISymbolicExpressionTree, List<ISymbolicExpressionTreeNode>>();
    6462      traceCache = new HashSet<Tuple<IGenealogyGraphNode<ISymbolicExpressionTree>, IGenealogyGraphNode<ISymbolicExpressionTree>, int>>();
     
    10199    /// <param name="subtreeIndex">The index of the traced subtree</param>
    102100    /// <param name="last">The last added node in the trace graph</param>
    103     private void TraceRecursive(IGenealogyGraphNode<ISymbolicExpressionTree> node, int subtreeIndex, IGenealogyGraphNode<ISymbolicExpressionTree> last = null) {
     101    /// <param name="lastSi">The subtree index in the last added individual</param>
     102    /// <param name="lastFi">The fragment index in the last added individual</param>
     103    private void TraceRecursive(IGenealogyGraphNode<ISymbolicExpressionTree> node, int subtreeIndex, IGenealogyGraphNode<ISymbolicExpressionTree> last = null, int lastSi = -1, int lastFi = -1) {
    104104      var g = node;
    105105      int si = subtreeIndex; // subtree index
    106106      int fi = 0; // fragment index
    107107      while (((List<IArc>)((IVertex)g).InArcs).Count > 0) {
    108         Debug.Assert(si < g.Data.Length);
     108        if (!(si < g.Data.Length)) throw new ArgumentOutOfRangeException("The subtree index exceeds the size of the tree.");
    109109        var inArcs = (List<IArc>)((IVertex)g).InArcs;
    110110        var fragment = (IFragment<ISymbolicExpressionTreeNode>)((IGenealogyGraphArc)inArcs.Last()).Data;
     
    144144            if (fi < si + sl) {
    145145              // subtree contains fragment => branching point in the fragment graph
    146               var n = AddTraceNode(g, si, fi); // current node becomes "last" as we restart tracing from the parent
     146              var n = AddTraceNode(g); // current node becomes "last" as we restart tracing from the parent
    147147              var t0 = new Tuple<IGenealogyGraphNode<ISymbolicExpressionTree>, IGenealogyGraphNode<ISymbolicExpressionTree>, int>(parent0, n, si);
    148148              if (!(CacheTraceNodes && traceCache.Contains(t0))) {
    149                 TraceRecursive(parent0, si, n);
     149                TraceRecursive(parent0, si, n, si, fi);
    150150                traceCache.Add(t0);
    151151              }
    152152              var t1 = new Tuple<IGenealogyGraphNode<ISymbolicExpressionTree>, IGenealogyGraphNode<ISymbolicExpressionTree>, int>(parent1, n, fragment.Index2);
    153153              if (!(CacheTraceNodes && traceCache.Contains(t1))) {
    154                 TraceRecursive(parent1, fragment.Index2, n);
     154                TraceRecursive(parent1, fragment.Index2, n, si, fi);
    155155                traceCache.Add(t1);
    156156              }
     
    172172          // check if the subtree and the fragment overlap => branch out
    173173          if ((si == fi) || (si < fi && fi < si + sl) || (fi < si && si < fi + fl)) {
    174             var n = AddTraceNode(g, si, fi); // current node becomes "last" as we restart tracing from the parent
     174            var n = AddTraceNode(g); // current node becomes "last" as we restart tracing from the parent
    175175            int i = si < fi ? si : fi;
    176176            var t = new Tuple<IGenealogyGraphNode<ISymbolicExpressionTree>, IGenealogyGraphNode<ISymbolicExpressionTree>, int>(parent0, n, i);
    177177            if (!(CacheTraceNodes && traceCache.Contains(t))) {
    178               TraceRecursive(parent0, i, n);
     178              TraceRecursive(parent0, i, n, si, fi);
    179179              traceCache.Add(t);
    180180            }
     
    193193      // when we are out of the while the last vertex must be connected with the current one
    194194      // if there is no last vertex, it means the tracing reached the top of the genealogy graph
    195       var current = AddTraceNode(g, si, fi);
    196       if (last != null)
    197         ConnectLast(current, last, si, fi);
     195      if (last != null) {
     196        var current = AddTraceNode(g);
     197        if (current.Rank.IsAlmost(0)) fi = -1; // if current is part of the initial population there will be no fragment
     198        var td = new TraceData(si, fi, lastSi, lastFi);
     199#if DEBUG
     200        var currentLength = current.Data.Length;
     201        var lastLength = last.Data.Length;
     202
     203        if (!(si < currentLength))
     204          throw new ArgumentOutOfRangeException(string.Format("Subtree index {0} exceeds tree length ({1}", si, currentLength));
     205
     206        if (!(fi < currentLength))
     207          throw new ArgumentOutOfRangeException(string.Format("Fragment index {0} exceeds tree length ({1}", fi, currentLength));
     208
     209        if (!(lastSi < lastLength))
     210          throw new ArgumentOutOfRangeException(string.Format("Last subtree index {0} exceeds tree length ({1}", lastSi, lastLength));
     211
     212        if (!(lastFi < lastLength))
     213          throw new ArgumentOutOfRangeException(string.Format("Last fragment index {0} exceeds tree length ({1}", lastFi, lastLength));
     214#endif
     215        ConnectLast(current, last, td);
     216      }
    198217    }
    199218
     
    206225    /// <param name="fi">The fragment index</param>
    207226    /// <returns></returns>
    208     private IGenealogyGraphNode<ISymbolicExpressionTree> AddTraceNode(IGenealogyGraphNode<ISymbolicExpressionTree> g, int si, int fi) {
     227    private IGenealogyGraphNode<ISymbolicExpressionTree> AddTraceNode(IGenealogyGraphNode<ISymbolicExpressionTree> g) {
    209228      var n = TraceGraph.GetByContent(g.Data);
    210229      if (n == null) {
    211230        n = g.Copy();
    212231        TraceGraph.AddVertex(n);
    213         Debug.Assert(!traceMap.ContainsKey(n));
    214         traceMap[n] = new TraceData(si, fi, -1, -1); // only the first two fields are needed
    215232      }
    216233      return n;
     
    234251    /// </summary>
    235252    /// <param name="current">The current node in the genealogy graph</param>
    236     /// <param name="last">The last added node in the trace graph</param>   
    237     /// <param name="si">The index of the traced subtree</param>
    238     /// <param name="fi">The index of the fragment</param>
    239     private void ConnectLast(IGenealogyGraphNode<ISymbolicExpressionTree> current, IGenealogyGraphNode<ISymbolicExpressionTree> last, int si, int fi) {
    240       var lastTraceData = traceMap[last];
    241       int lastSi = lastTraceData.SubtreeIndex; // last subtree index (index of the traced subtree in the previous trace node)
    242       int lastFi = lastTraceData.FragmentIndex; // last fragment index (index of the fragment in the previous trace node)
    243       var td = new TraceData(si, fi, lastSi, lastFi); // trace data
    244 
     253    /// <param name="last">The last added node in the trace graph</param>
     254    /// <param name="td">The trace data specifying the preorder indices of the subtree and fragment in the @current and @last vertices</param>   
     255    private void ConnectLast(IGenealogyGraphNode<ISymbolicExpressionTree> current, IGenealogyGraphNode<ISymbolicExpressionTree> last, TraceData td) {
    245256      // TODO: more testing
    246257      var inArcs = (List<IArc>)((IVertex)last).InArcs; // using the InArcs seems to be slightly more efficient than using the OutArcs
Note: See TracChangeset for help on using the changeset viewer.