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

#region License Information
/* HeuristicLab
 * Copyright (C) 2002-2014 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
 *
 * This file is part of HeuristicLab.
 *
 * HeuristicLab is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * HeuristicLab is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
 */
#endregion

using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using HeuristicLab.Core;
using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
using HeuristicLab.EvolutionTracking;

namespace HeuristicLab.Problems.DataAnalysis.Symbolic {
  public static class SymbolicDataAnalysisExpressionTracing {
    public static FragmentGraph TraceSubtree(IGenealogyGraphNode<ISymbolicExpressionTree> graphNode, int subtreeIndex) {
      var graph = new FragmentGraph();
      var vertices = Trace(graphNode, subtreeIndex).ToList();
      graph.AddVertices(vertices);
      return graph;
    }
    /// <summary>
    /// Traces a subtree in a genealogy of individuals, tracking down it's genetic components
    /// </summary>
    /// <param name="graphNode">The point in the genealogy where to start the tracing from</param>
    /// <param name="subtreeIndex">The traced subtree preorder index in the current tree</param>
    /// <param name="parentNode">The parent node in the fragment graph if there is any</param>
    /// <returns></returns>
    private static IEnumerable<FragmentNode> Trace(IGenealogyGraphNode<ISymbolicExpressionTree> graphNode, int subtreeIndex, FragmentNode parentNode = null) {
      var node = graphNode; // current node
      var index = subtreeIndex; // current index
      var parent = parentNode; // current parent

      IGenealogyGraphNode<ISymbolicExpressionTree> n1 = null;
      int i1 = -1;

      while (true) {
        if (node == n1 && index == i1)
          throw new InvalidOperationException("Infinite loop detected");

        n1 = node;
        i1 = index;

        if (!node.Parents.Any()) {
          // no tracing if there are no parents, return a fragment node representing the current trace
          var fragmentNode = new FragmentNode(node.Data) { SubtreeIndex = index };
          if (parent != null) {
            var arc = new GenealogyGraphArc(parent, fragmentNode);
            parent.AddArc(arc);
            fragmentNode.AddArc(arc);
          }
          yield return fragmentNode;
          break;
        }
        var parents = node.Parents.ToList();
        var fragment = (IFragment<ISymbolicExpressionTreeNode>)node.InArcs.Last().Data;

        if (fragment == null) {
          // the fragment can be null for two reasons:
          // 1) the individual is an elite
          // 2) the crossover/mutation made no changes to the root parent (or there is a bug in fragment identification)
          if (index >= parents[0].Data.Length) {
            throw new InvalidOperationException("Index exceeds tree length.");
          }
          node = parents[0];
          continue;
        }

        var fragmentLength = fragment.Root.GetLength();
        var tree = node.Data;
        var subtree = tree.NodeAt(index);
        var subtreeLength = subtree.GetLength();

        #region mutation tracing
        if (parents.Count == 1) {
          // we are tracing a mutation operation
          var fragmentNode = new FragmentNode(node.Data) {
            SubtreeIndex = index,
            FragmentIndex = fragment.Index1
          };
          if (parent != null) {
            var arc = new Arc(parent, fragmentNode);
            parent.AddArc(arc);
            fragmentNode.AddArc(arc);
          }
          if (node == parents[0])
            throw new InvalidOperationException("Node == parents[0]");

          node = parents[0];

          if (index == fragment.Index1) {
            // index stays the same
          } else if (fragment.Index1 < index) {
            if (index < fragment.Index1 + fragmentLength) {
              // in the case of mutation, the fragment could have been introduced via a node replacement
              // there is no guarantee the subtree exists above this level, therefore the index is set to the fragment index
              index = fragment.Index1;
            } else {
              // subtree outside of fragment
              index += node.Data.NodeAt(fragment.Index1).GetLength() - fragmentLength;
            }
          } else if (index < fragment.Index1) {
            if (fragment.Index1 < index + subtreeLength) {
              // subtree contains fragment
              index = fragment.Index1;
            } else {
              // index stays the same
            }
          }
          yield return fragmentNode;
          if (node == graphNode && index == subtreeIndex)
            throw new ArgumentException("Infinite recursion detected");
          var up = Trace(node, index, fragmentNode).ToList(); // force immediate query execution
          foreach (var v in up) { yield return v; }
          break;
        }
        #endregion

        #region crossover tracing
        if (parents.Count == 2) {
          if (node == parents[0])
            throw new InvalidOperationException("Node == parents[0]");
          if (node == parents[1])
            throw new InvalidOperationException("Node == parents[1]");
          // we are tracing a crossover operation
          if (fragment.Index1 == index) {
            node = parents[1]; // take second parent which contains the fragment
            index = fragment.Index2;
            continue;
          }

          if (fragment.Index1 < index) {
            if (fragment.Index1 + fragmentLength > index) {
              node = parents[1]; // 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 = parents[0]; // take first parent which contains the subtree
              index += node.Data.NodeAt(fragment.Index1).GetLength() - fragmentLength; // subtreeIndex must be adjusted according to swapped fragments sizes
            }
            continue;
          }

          if (fragment.Index1 > index) {
            if (fragment.Index1 < index + subtreeLength) {
              // subtree contains fragment => branching point in the fragment graph
              var fragmentNode = new FragmentNode(node.Data) {
                SubtreeIndex = index,
                FragmentIndex = fragment.Index1
              };
              if (parent != null) {
                var arc = new GenealogyGraphArc(parent, fragmentNode);
                parent.AddArc(arc);
                fragmentNode.AddArc(arc);
              }
              yield return fragmentNode;

              if (parents[1].Data.NodeAt(fragment.Index2).GetLength() != fragmentLength) {
                throw new Exception("Fragment lengths should match!");
              }
              // the two paths below ("left" and "right") correspond to the subtree and the fragment, respectively
              var left = Trace(parents[0], index, fragmentNode); // trace subtree
              var right = Trace(parents[1], fragment.Index2, fragmentNode); // trace fragment
              foreach (var v in left.Concat(right)) { yield return v; }
              break;
            } else {
              node = parents[0]; // fragment distinct from subtree: update node, index remains unchanged
            }
          }
        }
        #endregion
      }
    }

    private static string ViewAsText(this ISymbolicExpressionTreeNode root) {
      var writer = new StringWriter();
      SymbolicExpressionTreeHierarchicalFormatter.RenderNode(writer, root, string.Empty);
      return writer.ToString();
    }
  }
}