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

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 IGenealogyGraphNode<ISymbolicExpressionTree> lastVisited;
    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;
    }

    public void Trace(IGenealogyGraphNode<ISymbolicExpressionTree> node, int subtreeIndex) {
      while (true) {
        if (!node.Parents.Any()) {
          if (node.Rank.IsAlmost(0) && lastVisited != null) {
            var n = traceGraph.GetByContent(node.Data);
            if (n == null) {
              n = node.Copy();
              traceGraph.AddVertex(n);
            }
            if (n.InArcs.All(x => x.Source != lastVisited)) {
              traceGraph.AddArc(lastVisited, n);
            }
          }
          return;
        }

        var parents = node.Parents.ToList();

        var fragment = (IFragment<ISymbolicExpressionTreeNode>)node.InArcs.Last().Data;
        if (fragment == null) {
          // the node is either an elite node or (in rare cases) no fragment was transferred
          node = parents[0];
          continue;
        }

        int fragmentLength = fragment.Root.GetLength();
        int subtreeLength = node.Data.NodeAt(subtreeIndex).GetLength();

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

              if (lastVisited != null) {
                var lastTraceData = traceMap[lastVisited];
                int lastSi = lastTraceData.Item1;
                int lastFi = lastTraceData.Item2;
                var traceData = new Tuple<int, int, int, int>(lastSi, lastFi, subtreeIndex, fragment.Index1);
                if (!n.InArcs.Any(a => a.Source == lastVisited && a.Data.Equals(traceData))) {
                  var arc = traceGraph.AddArc(lastVisited, n);
                  arc.Data = traceData;
                }
              }

              lastVisited = n;
              Trace(parents[0], subtreeIndex);
              lastVisited = n;
              Trace(parents[1], fragment.Index2);
              break;
            } else {
              // subtree and fragment are distinct. 
              node = parents[0];
              continue;
            }
          }
        }
        #endregion
        #region trace mutation
        if (parents.Count == 1) {
          if (subtreeIndex == fragment.Index1) {
            //            node = parents[0];
            var n = traceGraph.GetByContent(node.Data);
            if (n == null) {
              n = node.Copy();
              traceGraph.AddVertex(n);
            }

            if (lastVisited != null) {
              var arc = traceGraph.AddArc(lastVisited, n);
              var lastTraceData = traceMap[lastVisited];
              int lastSi = lastTraceData.Item1;
              int lastFi = lastTraceData.Item2;
              var td = new Tuple<int, int, int, int>(lastSi, lastFi, subtreeIndex, fragment.Index1);
            }
          }
        #endregion
        } else {
          throw new InvalidOperationException("A node cannot have more than two parents");
        }
      }
    }
  }

  internal static class Util {
    // shallow copy which does not clone the data and completely ignores 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
  }
}