Free cookie consent management tool by TermsFeed Policy Generator

Ignore:
Timestamp:
10/16/14 15:52:41 (10 years ago)
Author:
bburlacu
Message:

#1772: Finished the TraceCalculator, added tracing for mutation operations.

File:
1 edited

Legend:

Unmodified
Added
Removed

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

    r11458 r11473  
    99
    1010namespace HeuristicLab.Problems.DataAnalysis.Symbolic {
    11 
    12 
    1311  [Item("TraceCalculator", "Walks a genealogy graph and produces a trace of the specified subtree")]
    1412  [StorableClass]
    1513  public class TraceCalculator : Item {
    16     private IGenealogyGraphNode<ISymbolicExpressionTree> lastVisited;
    1714    private readonly IGenealogyGraph<ISymbolicExpressionTree> traceGraph;
    1815    private readonly Dictionary<IGenealogyGraphNode<ISymbolicExpressionTree>, Tuple<int, int>> traceMap;
    … …  
    3936    }
    4037
    41     public void Trace(IGenealogyGraphNode<ISymbolicExpressionTree> node, int subtreeIndex) {
    42       while (true) {
    43         if (!node.Parents.Any()) {
    44           if (node.Rank.IsAlmost(0) && lastVisited != null) {
    45             var n = traceGraph.GetByContent(node.Data);
    46             if (n == null) {
    47               n = node.Copy();
    48               traceGraph.AddVertex(n);
    49             }
    50             if (n.InArcs.All(x => x.Source != lastVisited)) {
    51               traceGraph.AddArc(lastVisited, n);
    52             }
    53           }
    54           return;
    55         }
    56 
    57         var parents = node.Parents.ToList();
    58 
    59         var fragment = (IFragment<ISymbolicExpressionTreeNode>)node.InArcs.Last().Data;
     38    /// <summary>
     39    /// This method starts from a given vertex in the genealogy graph and works its way
     40    /// up the ancestry trying to track the structure of the subtree given by subtreeIndex.
     41    /// This method will skip genealogy graph nodes that did not have an influence on the
     42    /// structure of the tracked subtree.
     43    ///
     44    /// Only genealogy nodes which did have an influence are added (as copies) to the trace
     45    /// and are consequently called 'trace nodes'.
     46    ///
     47    /// The arcs connecting trace nodes hold information about the locations of the subtrees
     48    /// and fragments that have been swapped in the form of a tuple (si, fi, lastSi, lastFi),
     49    /// where:
     50    /// - si is the subtree index in the current trace node
     51    /// - fi is the fragment index in the current trace node
     52    /// - lastSi is the subtree index in the previous trace node
     53    /// - lastFi is the subtree index in the previous trace node
     54    /// </summary>
     55    /// <param name="g">The current node in the genealogy graph</param>
     56    /// <param name="si">The index of the traced subtree</param>
     57    /// <param name="last">The last added node in the trace graph</param>
     58    public void Trace(IGenealogyGraphNode<ISymbolicExpressionTree> g, int si, IGenealogyGraphNode<ISymbolicExpressionTree> last = null) {
     59      while (g.Parents.Any()) {
     60        var parents = g.Parents.ToList();
     61        var fragment = (IFragment<ISymbolicExpressionTreeNode>)g.InArcs.Last().Data;
    6062        if (fragment == null) {
    6163          // the node is either an elite node or (in rare cases) no fragment was transferred
    62           node = parents[0];
     64          g = parents[0];
    6365          continue;
    6466        }
    6567
    6668        int fragmentLength = fragment.Root.GetLength();
    67         int subtreeLength = node.Data.NodeAt(subtreeIndex).GetLength();
     69        int subtreeLength = g.Data.NodeAt(si).GetLength();
    6870
    6971        #region trace crossover
    7072        if (parents.Count == 2) {
    71           if (fragment.Index1 == subtreeIndex) {
    72             node = parents[1];
    73             subtreeIndex = fragment.Index2;
     73          if (fragment.Index1 == si) {
     74            g = parents[1];
     75            si = fragment.Index2;
    7476            continue;
    7577          }
    76           if (fragment.Index1 < subtreeIndex) {
    77             if (fragment.Index1 + fragmentLength > subtreeIndex) {
     78          if (fragment.Index1 < si) {
     79            if (fragment.Index1 + fragmentLength > si) {
    7880              // fragment contains subtree
    79               node = parents[1];
    80               subtreeIndex += fragment.Index2 - fragment.Index1;
     81              g = parents[1];
     82              si += fragment.Index2 - fragment.Index1;
    8183            } else {
    8284              // fragment distinct from subtree
    83               node = parents[0];
    84               subtreeIndex += node.Data.NodeAt(fragment.Index1).GetLength() - fragmentLength;
     85              g = parents[0];
     86              si += g.Data.NodeAt(fragment.Index1).GetLength() - fragmentLength;
    8587            }
    8688            continue;
    8789          }
    88           if (fragment.Index1 > subtreeIndex) {
    89             if (fragment.Index1 < subtreeIndex + subtreeLength) {
     90          if (fragment.Index1 > si) {
     91            if (fragment.Index1 < si + subtreeLength) {
    9092              // subtree contains fragment => branching point in the fragment graph
    91               var n = traceGraph.GetByContent(node.Data);
     93              var n = traceGraph.GetByContent(g.Data);
    9294              if (n == null) {
    93                 n = node.Copy();
     95                n = g.Copy();
    9496                traceGraph.AddVertex(n);
    95                 traceMap[n] = new Tuple<int, int>(subtreeIndex, fragment.Index1);
     97                traceMap[n] = new Tuple<int, int>(si, fragment.Index1);
    9698              }
    9799
    98               if (lastVisited != null) {
    99                 var lastTraceData = traceMap[lastVisited];
    100                 int lastSi = lastTraceData.Item1;
    101                 int lastFi = lastTraceData.Item2;
    102                 var traceData = new Tuple<int, int, int, int>(lastSi, lastFi, subtreeIndex, fragment.Index1);
    103                 if (!n.InArcs.Any(a => a.Source == lastVisited && a.Data.Equals(traceData))) {
    104                   var arc = traceGraph.AddArc(lastVisited, n);
    105                   arc.Data = traceData;
    106                 }
    107               }
    108 
    109               lastVisited = n;
    110               Trace(parents[0], subtreeIndex);
    111               lastVisited = n;
    112               Trace(parents[1], fragment.Index2);
     100              Trace(parents[0], si, n);
     101              Trace(parents[1], fragment.Index2, n);
    113102              break;
    114103            } else {
    115104              // subtree and fragment are distinct.
    116               node = parents[0];
     105              g = parents[0];
    117106              continue;
    118107            }
    … …  
    122111        #region trace mutation
    123112        if (parents.Count == 1) {
    124           if (subtreeIndex == fragment.Index1) {
    125             //            node = parents[0];
    126             var n = traceGraph.GetByContent(node.Data);
     113          if (si == fragment.Index1) {
     114            // fragment and subtree coincide
     115            // since mutation can potentially alter trees quite drastically, we branch here,
     116            // in order not to miss any changes
     117            var n = traceGraph.GetByContent(g.Data);
    127118            if (n == null) {
    128               n = node.Copy();
     119              n = g.Copy();
    129120              traceGraph.AddVertex(n);
    130             }
    131 
    132             if (lastVisited != null) {
    133               var arc = traceGraph.AddArc(lastVisited, n);
    134               var lastTraceData = traceMap[lastVisited];
    135               int lastSi = lastTraceData.Item1;
    136               int lastFi = lastTraceData.Item2;
    137               var td = new Tuple<int, int, int, int>(lastSi, lastFi, subtreeIndex, fragment.Index1);
    138             }
    139           }
     121              traceMap[n] = new Tuple<int, int>(si, fragment.Index1);
     122            }
     123            Trace(parents[0], si, n);
     124            break;
     125          }
     126          if (fragment.Index1 < si) {
     127            if (si < fragment.Index1 + fragmentLength) {
     128              // fragment contains subtree
     129              g = parents[0];
     130              si = fragment.Index2;
     131            } else {
     132              // fragment and subtree are distinct
     133              // since the fragment occurs before the subtree in the prefix node ordering
     134              // the subtree index must be adjusted according to the fragment length
     135              g = parents[0];
     136              si += g.Data.NodeAt(fragment.Index1).GetLength() - fragmentLength;
     137            }
     138            continue;
     139          }
     140          if (si < fragment.Index1) {
     141            // subtree occurs before fragment in the prefix node ordering
     142            if (fragment.Index1 < si + subtreeLength) {
     143              // subtree contains fragment, we are interested to see what the subtree looked like before
     144              // but we also want to keep track of what it looks like now, therefore we branch here
     145              var n = traceGraph.GetByContent(g.Data);
     146              if (n == null) {
     147                n = g.Copy();
     148                traceGraph.AddVertex(n);
     149                traceMap[n] = new Tuple<int, int>(si, fragment.Index1);
     150              }
     151              Trace(parents[0], si, n);
     152              break;
     153            } else {
     154              // fragment and subtree are distinct, subtree index stays the same
     155              // since the subtree comes before the fragment in the prefix node ordering
     156              g = parents[0];
     157              continue;
     158            }
     159          }
     160        }
    140161        #endregion
    141         } else {
    142           throw new InvalidOperationException("A node cannot have more than two parents");
    143         }
     162        throw new InvalidOperationException("A node cannot have more than two parents");
    144163      }
     164      // when we are out of the while the last vertex must be connected with the current one
     165      ConnectLast(g, si, last);
     166    }
     167
     168    /// <summary>
     169    /// Connect the current node of the trace graph with the node that was previously added (@last). The current node of the trace graph is determined by the content
     170    /// of the genealogy graph node @g. 
     171    /// </summary>
     172    /// <param name="g">The current node in the genealogy graph</param>
     173    /// <param name="si">The index of the traced subtree</param>
     174    /// <param name="last">The last added node in the trace graph</param>
     175    private void ConnectLast(IGenealogyGraphNode<ISymbolicExpressionTree> g, int si, IGenealogyGraphNode<ISymbolicExpressionTree> last) {
     176      IFragment<ISymbolicExpressionTreeNode> fragment = g.Parents.Any() ? (IFragment<ISymbolicExpressionTreeNode>)g.InArcs.Last().Data : null;
     177      var n = traceGraph.GetByContent(g.Data);
     178      if (n == null) {
     179        n = g.Copy();
     180        traceGraph.AddVertex(n);
     181      }
     182      int fi = fragment == null ? 0 : fragment.Index1; // fragment index
     183      traceMap[n] = new Tuple<int, int>(si, fi);
     184      if (last == null)
     185        return;
     186      var lastTraceData = traceMap[last];
     187      int lastSi = lastTraceData.Item1; // last subtree index
     188      int lastFi = lastTraceData.Item2; // last fragment index
     189      var td = new Tuple<int, int, int, int>(si, fi, lastSi, lastFi); // trace data
     190      var arc = n.InArcs.SingleOrDefault(a => a.Source == last && a.Data.Equals(td));
     191      if (arc != null)
     192        return;
     193      arc = new GenealogyGraphArc(last, n);
     194      arc.Data = td;
     195      traceGraph.AddArc(arc);
    145196    }
    146197  }
    147198
    148199  internal static class Util {
    149     // shallow copy which does not clone the data and completely ignores arcs
     200    // shallow node copy (does not clone the data or the arcs)
    150201    public static IGenealogyGraphNode<ISymbolicExpressionTree> Copy(this IGenealogyGraphNode<ISymbolicExpressionTree> node) {
    151202      return new GenealogyGraphNode<ISymbolicExpressionTree>(node.Data) { Rank = node.Rank, Quality = node.Quality };
Note: See TracChangeset for help on using the changeset viewer.