source: branches/HeuristicLab.EvolutionTracking/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Tracking/TraceCalculator.cs @ 11473

using System;
using System.Collections.Generic;
using System.Linq;
using HeuristicLab.Common;
using HeuristicLab.Core;
using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
using HeuristicLab.EvolutionTracking;
using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;

namespace HeuristicLab.Problems.DataAnalysis.Symbolic {
  [Item("TraceCalculator", "Walks a genealogy graph and produces a trace of the specified subtree")]
  [StorableClass]
  public class TraceCalculator : Item {
    private readonly IGenealogyGraph<ISymbolicExpressionTree> traceGraph;
    private readonly Dictionary<IGenealogyGraphNode<ISymbolicExpressionTree>, Tuple<int, int>> traceMap;

    public IGenealogyGraph<ISymbolicExpressionTree> TraceGraph { get { return traceGraph; } }

    public TraceCalculator() {
      traceGraph = new GenealogyGraph<ISymbolicExpressionTree>();
      traceMap = new Dictionary<IGenealogyGraphNode<ISymbolicExpressionTree>, Tuple<int, int>>();
    }

    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();
      tc.Trace(node, subtreeIndex);
      return tc.TraceGraph;
    }

    /// <summary>
    /// This method starts from a given vertex in the genealogy graph and works its way 
    /// up the ancestry trying to track the structure of the subtree given by subtreeIndex.
    /// This method will skip genealogy graph nodes that did not have an influence on the 
    /// structure of the tracked subtree. 
    /// 
    /// Only genealogy nodes which did have an influence are added (as copies) to the trace 
    /// and are consequently called 'trace nodes'. 
    /// 
    /// The arcs connecting trace nodes hold information about the locations of the subtrees
    /// and fragments that have been swapped in the form of a tuple (si, fi, lastSi, lastFi),
    /// where:
    /// - si is the subtree index in the current trace node
    /// - fi is the fragment index in the current trace node
    /// - lastSi is the subtree index in the previous trace node
    /// - lastFi is the subtree index in the previous trace node
    /// </summary>
    /// <param name="g">The current node in the genealogy graph</param>
    /// <param name="si">The index of the traced subtree</param>
    /// <param name="last">The last added node in the trace graph</param>
    public void Trace(IGenealogyGraphNode<ISymbolicExpressionTree> g, int si, IGenealogyGraphNode<ISymbolicExpressionTree> last = null) {
      while (g.Parents.Any()) {
        var parents = g.Parents.ToList();
        var fragment = (IFragment<ISymbolicExpressionTreeNode>)g.InArcs.Last().Data;
        if (fragment == null) {
          // the node is either an elite node or (in rare cases) no fragment was transferred
          g = parents[0];
          continue;
        }

        int fragmentLength = fragment.Root.GetLength();
        int subtreeLength = g.Data.NodeAt(si).GetLength();

        #region trace crossover
        if (parents.Count == 2) {
          if (fragment.Index1 == si) {
            g = parents[1];
            si = fragment.Index2;
            continue;
          }
          if (fragment.Index1 < si) {
            if (fragment.Index1 + fragmentLength > si) {
              // fragment contains subtree
              g = parents[1];
              si += fragment.Index2 - fragment.Index1;
            } else {
              // fragment distinct from subtree
              g = parents[0];
              si += g.Data.NodeAt(fragment.Index1).GetLength() - fragmentLength;
            }
            continue;
          }
          if (fragment.Index1 > si) {
            if (fragment.Index1 < si + subtreeLength) {
              // subtree contains fragment => branching point in the fragment graph
              var n = traceGraph.GetByContent(g.Data);
              if (n == null) {
                n = g.Copy();
                traceGraph.AddVertex(n);
                traceMap[n] = new Tuple<int, int>(si, fragment.Index1);
              }

              Trace(parents[0], si, n);
              Trace(parents[1], fragment.Index2, n);
              break;
            } else {
              // subtree and fragment are distinct. 
              g = parents[0];
              continue;
            }
          }
        }
        #endregion
        #region trace mutation
        if (parents.Count == 1) {
          if (si == fragment.Index1) {
            // fragment and subtree coincide
            // since mutation can potentially alter trees quite drastically, we branch here,
            // in order not to miss any changes
            var n = traceGraph.GetByContent(g.Data);
            if (n == null) {
              n = g.Copy();
              traceGraph.AddVertex(n);
              traceMap[n] = new Tuple<int, int>(si, fragment.Index1);
            }
            Trace(parents[0], si, n);
            break;
          }
          if (fragment.Index1 < si) {
            if (si < fragment.Index1 + fragmentLength) {
              // fragment contains subtree
              g = parents[0];
              si = fragment.Index2;
            } else {
              // fragment and subtree are distinct
              // since the fragment occurs before the subtree in the prefix node ordering
              // the subtree index must be adjusted according to the fragment length
              g = parents[0];
              si += g.Data.NodeAt(fragment.Index1).GetLength() - fragmentLength;
            }
            continue;
          }
          if (si < fragment.Index1) {
            // subtree occurs before fragment in the prefix node ordering
            if (fragment.Index1 < si + subtreeLength) {
              // subtree contains fragment, we are interested to see what the subtree looked like before
              // but we also want to keep track of what it looks like now, therefore we branch here
              var n = traceGraph.GetByContent(g.Data);
              if (n == null) {
                n = g.Copy();
                traceGraph.AddVertex(n);
                traceMap[n] = new Tuple<int, int>(si, fragment.Index1);
              }
              Trace(parents[0], si, n);
              break;
            } else {
              // fragment and subtree are distinct, subtree index stays the same
              // since the subtree comes before the fragment in the prefix node ordering
              g = parents[0];
              continue;
            }
          }
        }
        #endregion
        throw new InvalidOperationException("A node cannot have more than two parents");
      }
      // when we are out of the while the last vertex must be connected with the current one
      ConnectLast(g, si, last);
    }

    /// <summary>
    /// 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
    /// of the genealogy graph node @g.  
    /// </summary>
    /// <param name="g">The current node in the genealogy graph</param>
    /// <param name="si">The index of the traced subtree</param>
    /// <param name="last">The last added node in the trace graph</param>
    private void ConnectLast(IGenealogyGraphNode<ISymbolicExpressionTree> g, int si, IGenealogyGraphNode<ISymbolicExpressionTree> last) {
      IFragment<ISymbolicExpressionTreeNode> fragment = g.Parents.Any() ? (IFragment<ISymbolicExpressionTreeNode>)g.InArcs.Last().Data : null;
      var n = traceGraph.GetByContent(g.Data);
      if (n == null) {
        n = g.Copy();
        traceGraph.AddVertex(n);
      }
      int fi = fragment == null ? 0 : fragment.Index1; // fragment index
      traceMap[n] = new Tuple<int, int>(si, fi);
      if (last == null)
        return;
      var lastTraceData = traceMap[last];
      int lastSi = lastTraceData.Item1; // last subtree index
      int lastFi = lastTraceData.Item2; // last fragment index
      var td = new Tuple<int, int, int, int>(si, fi, lastSi, lastFi); // trace data
      var arc = n.InArcs.SingleOrDefault(a => a.Source == last && a.Data.Equals(td));
      if (arc != null)
        return;
      arc = new GenealogyGraphArc(last, n);
      arc.Data = td;
      traceGraph.AddArc(arc);
    }
  }

  internal static class Util {
    // shallow node copy (does not clone the data or the arcs)
    public static IGenealogyGraphNode<ISymbolicExpressionTree> Copy(this IGenealogyGraphNode<ISymbolicExpressionTree> node) {
      return new GenealogyGraphNode<ISymbolicExpressionTree>(node.Data) { Rank = node.Rank, Quality = node.Quality };
    }
    #region some helper methods for shortening the tracing code
    public static ISymbolicExpressionTreeNode NodeAt(this ISymbolicExpressionTree tree, int index) {
      return NodeAt(tree.Root, index);
    }
    public static ISymbolicExpressionTreeNode NodeAt(this ISymbolicExpressionTreeNode root, int index) {
      return root.IterateNodesPrefix().ElementAt(index);
    }
    #endregion
  }
}