source: branches/HeuristicLab.EvolutionaryTracking/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/SymbolicDataAnalysisExpressionTreeMatching.cs @ 9241

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

namespace HeuristicLab.Problems.DataAnalysis.Symbolic {
  [Item("SymbolicExpressionTreeNodeSimilarityComparer", "A comparison operator that checks node equality based on different similarity measures.")]
  [StorableClass]
  public class SymbolicExpressionTreeNodeSimilarityComparer : Item, ISymbolicExpressionTreeNodeComparer {
    [StorableConstructor]
    private SymbolicExpressionTreeNodeSimilarityComparer(bool deserializing) : base(deserializing) { }
    private SymbolicExpressionTreeNodeSimilarityComparer(SymbolicExpressionTreeNodeSimilarityComparer original, Cloner cloner)
      : base(original, cloner) {
      matchConstantValues = original.matchConstantValues;
      matchVariableNames = original.matchVariableNames;
      matchVariableWeights = original.matchVariableWeights;
    }
    public override IDeepCloneable Clone(Cloner cloner) { return new SymbolicExpressionTreeNodeSimilarityComparer(this, cloner); }

    // more flexible matching criteria 
    [Storable]
    private bool matchConstantValues;
    public bool MatchConstantValues {
      get { return matchConstantValues; }
      set { matchConstantValues = value; }
    }

    [Storable]
    private bool matchVariableNames;
    public bool MatchVariableNames {
      get { return matchVariableNames; }
      set { matchVariableNames = value; }
    }

    [Storable]
    private bool matchVariableWeights;
    public bool MatchVariableWeights {
      get { return matchVariableWeights; }
      set { matchVariableWeights = value; }
    }

    [StorableHook(HookType.AfterDeserialization)]
    private void AfterDeserialization() {
    }

    public SymbolicExpressionTreeNodeSimilarityComparer() {
      matchConstantValues = true;
      matchVariableNames = true;
      matchVariableWeights = true;
    }

    public int GetHashCode(ISymbolicExpressionTreeNode n) {
      return n.ToString().ToLower().GetHashCode();
    }

    public bool Equals(ISymbolicExpressionTreeNode a, ISymbolicExpressionTreeNode b) {
      if (!(a is SymbolicExpressionTreeTerminalNode))
        // if a and b are non terminal nodes, check equality of symbol names
        return !(b is SymbolicExpressionTreeTerminalNode) && a.Symbol.Name.Equals(b.Symbol.Name);
      var va = a as VariableTreeNode;
      if (va != null) {
        var vb = b as VariableTreeNode;
        if (vb == null) return false;

        return (!MatchVariableNames || va.VariableName.Equals(vb.VariableName)) && (!MatchVariableWeights || va.Weight.Equals(vb.Weight));
      }
      var ca = a as ConstantTreeNode;
      if (ca != null) {
        var cb = b as ConstantTreeNode;
        if (cb == null) return false;
        return (!MatchConstantValues || ca.Value.Equals(cb.Value));
      }
      return false;
    }
  }

  public class SymbolicExpressionTreeFragmentSimilarityComparer : IEqualityComparer<IFragment> {
    public SymbolicExpressionTreeNodeSimilarityComparer SimilarityComparer { get; set; }

    public bool Equals(IFragment x, IFragment y) {
      if (SimilarityComparer == null)
        throw new ArgumentNullException("SimilarityComparer needs to be initialized first.");
      return x.Length == y.Length &&
             SymbolicExpressionTreeMatching.Match(x.Root, y.Root, SimilarityComparer) == x.Length;
    }

    public int GetHashCode(IFragment fragment) {
      return fragment.Root.Symbol.Name.ToLower().GetHashCode();
    }
  }

  // this comparer considers that a < b if the type of a is "greater" than the type of b, for example:
  // - A function node is "greater" than a terminal node
  // - A variable terminal is "greater" than a constant terminal
  public class SymbolicExpressionTreeNodeComparer : IComparer<ISymbolicExpressionTreeNode> {
    public int Compare(ISymbolicExpressionTreeNode a, ISymbolicExpressionTreeNode b) {
      if (!(a is SymbolicExpressionTreeTerminalNode)) {
        if (b is SymbolicExpressionTreeTerminalNode) return -1;
        return string.Compare(a.Symbol.Name, b.Symbol.Name, StringComparison.Ordinal);
      }
      if (!(b is SymbolicExpressionTreeTerminalNode)) return 1;
      // at this point we know a and b are terminal nodes
      var va = a as VariableTreeNode;
      if (va != null) {
        if (b is ConstantTreeNode) return -1;
        var vb = (VariableTreeNode)b;
        return (va.VariableName.Equals(vb.VariableName)
                  ? va.Weight.CompareTo(vb.Weight)
                  : string.Compare(va.VariableName, vb.VariableName, StringComparison.Ordinal));
      }
      // at this point we know for sure that a is a constant tree node
      if (b is VariableTreeNode) return 1;
      var ca = (ConstantTreeNode)a;
      var cb = (ConstantTreeNode)b;
      return ca.Value.CompareTo(cb.Value);
    }
  }

  // tree equality
  public class SymbolicExpressionTreeEqualityComparer : IEqualityComparer<ISymbolicExpressionTree> {
    public SymbolicExpressionTreeNodeSimilarityComparer SimilarityComparer { get; set; }

    public bool Equals(ISymbolicExpressionTree a, ISymbolicExpressionTree b) {
      if (SimilarityComparer == null) throw new ArgumentNullException("SimilarityComparer needs to be initialized first.");
      return SymbolicExpressionTreeMatching.Match(a.Root, b.Root, SimilarityComparer) == Math.Min(a.Length, b.Length);
    }

    public int GetHashCode(ISymbolicExpressionTree tree) {
      return (tree.Length << 8) % 12345;
    }
  }

  public class SymbolicExpressionTreeCanonicalSorter {
    private readonly HashSet<Type> nonSymmetricSymbols = new HashSet<Type> { typeof(Subtraction), typeof(Division) };

    public void SortSubtrees(ISymbolicExpressionTree tree) {
      SortSubtrees(tree.Root);
    }

    public void SortSubtrees(ISymbolicExpressionTreeNode node) {
      if (node.SubtreeCount == 0) return;
      var subtrees = node.Subtrees as List<ISymbolicExpressionTreeNode> ?? node.Subtrees.ToList();
      if (IsSymmetric(node.Symbol)) {
        var comparer = new SymbolicExpressionTreeNodeComparer();
        subtrees.Sort(comparer);
      }
      foreach (var s in subtrees)
        SortSubtrees(s);
    }

    private bool IsSymmetric(ISymbol s) {
      return !nonSymmetricSymbols.Contains(s.GetType());
    }
  }
}

public static class SymbolicExpressionTreeMatching {
  public static bool IsSimilarTo(this ISymbolicExpressionTree t1, ISymbolicExpressionTree t2, SymbolicExpressionTreeNodeSimilarityComparer comparer) {
    return t1.Root.IsSimilarTo(t2.Root, comparer);
  }
  public static bool IsSimilarTo(this ISymbolicExpressionTreeNode t1, ISymbolicExpressionTreeNode t2, SymbolicExpressionTreeNodeSimilarityComparer comparer) {
    return Match(t1, t2, comparer) == Math.Min(t1.GetLength(), t2.GetLength());
  }
  public static bool ContainsFragment(this ISymbolicExpressionTreeNode root, IFragment fragment, SymbolicExpressionTreeNodeSimilarityComparer comparer) {
    return FindMatches(root, fragment.Root, comparer).Any();
  }
  public static IEnumerable<ISymbolicExpressionTreeNode> FindMatches(ISymbolicExpressionTree tree, ISymbolicExpressionTreeNode fragment, SymbolicExpressionTreeNodeSimilarityComparer comparer) {
    return FindMatches(tree.Root, fragment, comparer);
  }

  public static IEnumerable<ISymbolicExpressionTreeNode>
    FindMatches(ISymbolicExpressionTreeNode root, ISymbolicExpressionTreeNode fragment, SymbolicExpressionTreeNodeSimilarityComparer comp) {
    var fragmentLength = fragment.GetLength();
    // below, we use ">=" for Match(n, fragment, comp) >= fragmentLength because in case of relaxed conditions, 
    // we can have multiple matches of the same node
    return root.IterateNodesBreadth().Where(n => n.GetLength() >= fragmentLength && Match(n, fragment, comp) == fragmentLength);
  }

  ///<summary>
  /// Finds the longest common subsequence in quadratic time and linear space
  /// Variant of:
  /// D. S. Hirschberg. A linear space algorithm for or computing maximal common subsequences. 1975.
  /// http://dl.acm.org/citation.cfm?id=360861
  /// </summary>
  /// <returns>Number of pairs that were matched</returns>
  public static int Match(ISymbolicExpressionTreeNode a, ISymbolicExpressionTreeNode b, SymbolicExpressionTreeNodeSimilarityComparer comp) {
    if (!comp.Equals(a, b)) return 0;
    int m = a.SubtreeCount;
    int n = b.SubtreeCount;
    if (m == 0 || n == 0) return 1;
    var matrix = new int[m + 1, n + 1];
    for (int i = 1; i <= m; ++i) {
      var ai = a.GetSubtree(i - 1);
      for (int j = 1; j <= n; ++j) {
        var bj = b.GetSubtree(j - 1);
        int match = Match(ai, bj, comp);
        matrix[i, j] = Math.Max(Math.Max(matrix[i, j - 1], matrix[i - 1, j]), matrix[i - 1, j - 1] + match);
      }
    }
    return matrix[m, n] + 1;
  }
}