source: branches/HeuristicLab.EvolutionTracking/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Tracking/SymbolicDataAnalysisExpressionTracing.cs @ 10755

using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
using HeuristicLab.EvolutionTracking;
using FragmentNode = HeuristicLab.EvolutionTracking.GenealogyGraphNode<HeuristicLab.EvolutionTracking.IFragment<HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.ISymbolicExpressionTreeNode>>;
using IFragmentNode = HeuristicLab.EvolutionTracking.IGenealogyGraphNode<HeuristicLab.EvolutionTracking.IFragment<HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.ISymbolicExpressionTreeNode>>;
using IGraphNode = HeuristicLab.EvolutionTracking.IGenealogyGraphNode<HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.ISymbolicExpressionTree>;

namespace HeuristicLab.Problems.DataAnalysis.Symbolic.Views {
  public static class SymbolicDataAnalysisExpressionTracing {
    public static IGenealogyGraph<IFragment<ISymbolicExpressionTreeNode>> TraceSubtree(IGenealogyGraphNode<ISymbolicExpressionTree> graphNode, int subtreeIndex) {
      var graph = new GenealogyGraph<IFragment<ISymbolicExpressionTreeNode>>();
      var nodes = Trace(graphNode, subtreeIndex);
      foreach (var n in nodes) {
        graph.AddVertex(n);
      }
      return graph;
    }

    private static IEnumerable<IFragmentNode> Trace(IGraphNode graphNode, int subtreeIndex, FragmentNode parentNode = null) {
      var node = graphNode; // current node
      var index = subtreeIndex; // current index
      var parent = parentNode; // current parent

      while (true) {
        if (!node.Parents.Any()) {
          var fragmentNode = new FragmentNode {
            Content = new Fragment<ISymbolicExpressionTreeNode> { Root = node.Content.NodeAt(index) },
            Rank = node.Rank
          };
          if (parent != null) {
            var arc = new GenealogyGraphArc { Source = parent, Target = fragmentNode };
            parent.AddForwardArc(arc);
            //            fragmentNode.Content.Index1 = parent.Content.Index1;
          }
          yield return fragmentNode; // no tracing if there are no parents
          break;
        }

        if (node.IsElite) {
          node = node.Parents.First();
          continue;
        } // skip elite, go up the graph to original individual

        var tree = node.Content;
        var subtree = tree.NodeAt(index);
        var subtreeLength = subtree.GetLength();

        var fragment = (IFragment<ISymbolicExpressionTreeNode>)node.InArcs.Last().Data;
        if (fragment == null) break;
        var fragmentLength = fragment.Root.GetLength();

        if (fragment.Index1 == index) {
          node = node.Parents.Last(); // take second parent which contains the fragment
          index = fragment.Index2;
        } else if (fragment.Index1 < index) {
          if (fragment.Index1 + fragmentLength > index) {
            node = node.Parents.Last(); // fragment contains subtree, take second parent
            index += fragment.Index2 - fragment.Index1; // the subtree has the same index relative to the fragment
          } else {
            // fragment distinct from subtree
            node = node.Parents.First(); // take first parent which contains the subtree
            index += node.Content.NodeAt(fragment.Index1).GetLength() - fragmentLength; // subtreeIndex must be adjusted according to swapped fragments sizes
          }
        } else if (fragment.Index1 > index) {
          if (fragment.Index1 < index + subtreeLength) {
            // subtree contains fragment => bifurcation point in the fragment graph
            var fragmentNode = new FragmentNode {
              Content = new Fragment<ISymbolicExpressionTreeNode> { Root = subtree },
              Rank = node.Rank
            };
            if (parent != null) {
              var arc = new GenealogyGraphArc { Source = parent, Target = fragmentNode };
              parent.AddForwardArc(arc);
            }
            fragmentNode.Content.Index1 = fragment.Index1 - index;
            yield return fragmentNode;

            var left = Trace(node.Parents.First(), index, fragmentNode); // trace subtree

            if (node.Parents.Last().Content.NodeAt(fragment.Index2).GetLength() != fragmentLength) {
              throw new Exception("Fragment lengths should match!");
            }
            var right = Trace(node.Parents.Last(), fragment.Index2, fragmentNode); // trace fragment
            foreach (var v in left.Concat(right)) {
              yield return v;
            }
            break;
          } else {
            node = node.Parents.First(); // fragment distinct from subtree: update node, index remains unchanged
          }
        }
      }
    }

    private static string ViewAsText(this ISymbolicExpressionTreeNode root) {
      var writer = new StringWriter();
      SymbolicExpressionTreeHierarchicalFormatter.RenderNode(writer, root, string.Empty);
      return writer.ToString();
    }
    #region some helper methods for shortening the tracing code

    private static void AddChild(this IGenealogyGraphNode parent, IGenealogyGraphNode child) {
      parent.AddForwardArc(child);
      child.AddReverseArc(parent);
      child.Rank = parent.Rank - 1;
    }
    private static ISymbolicExpressionTreeNode NodeAt(this ISymbolicExpressionTree tree, int position) {
      return NodeAt(tree.Root, position);
    }
    private static ISymbolicExpressionTreeNode NodeAt(this ISymbolicExpressionTreeNode root, int position) {
      return root.IterateNodesPrefix().ElementAt(position);
    }
    private static int IndexOf(this ISymbolicExpressionTree tree, ISymbolicExpressionTreeNode node) {
      return IndexOf(tree.Root, node);
    }
    private static int IndexOf(this ISymbolicExpressionTreeNode root, ISymbolicExpressionTreeNode node) {
      int i = 0;
      foreach (var n in root.IterateNodesPrefix()) {
        if (n == node) return i;
        ++i;
      }
      return -1;
    }
    #endregion
  }
}