1  using System;


2  using System.Collections.Generic;


3  using System.Linq;


4  using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;


5  //using HeuristicLab.EvolutionTracking;


6 


7  namespace HeuristicLab.Problems.DataAnalysis.Symbolic {


8  public static class SymbolicExpressionTreeMatching {


9  public static bool ContainsSubtree(this ISymbolicExpressionTreeNode root, ISymbolicExpressionTreeNode subtree, SymbolicExpressionTreeNodeSimilarityComparer comparer) {


10  return FindMatches(root, subtree, comparer).Any();


11  }


12  public static IEnumerable<ISymbolicExpressionTreeNode> FindMatches(ISymbolicExpressionTree tree, ISymbolicExpressionTreeNode subtree, SymbolicExpressionTreeNodeSimilarityComparer comparer) {


13  return FindMatches(tree.Root, subtree, comparer);


14  }


15 


16  public static IEnumerable<ISymbolicExpressionTreeNode> FindMatches(ISymbolicExpressionTreeNode root, ISymbolicExpressionTreeNode subtree, SymbolicExpressionTreeNodeSimilarityComparer comp) {


17  var fragmentLength = subtree.GetLength();


18  // below, we use ">=" for Match(n, subtree, comp) >= fragmentLength because in case of relaxed conditions,


19  // we can have multiple matches of the same node


20 


21  return root.IterateNodesBreadth().Where(n => n.GetLength() >= fragmentLength && Match(n, subtree, comp) == fragmentLength);


22  }


23 


24  ///<summary>


25  /// Finds the longest common subsequence in quadratic time and linear space


26  /// Variant of:


27  /// D. S. Hirschberg. A linear space algorithm for or computing maximal common subsequences. 1975.


28  /// http://dl.acm.org/citation.cfm?id=360861


29  /// </summary>


30  /// <returns>Number of pairs that were matched</returns>


31  public static int Match(ISymbolicExpressionTreeNode a, ISymbolicExpressionTreeNode b, SymbolicExpressionTreeNodeSimilarityComparer comp) {


32  if (!comp.Equals(a, b)) return 0;


33  int m = a.SubtreeCount;


34  int n = b.SubtreeCount;


35  if (m == 0  n == 0) return 1;


36  var matrix = new int[m + 1, n + 1];


37  for (int i = 1; i <= m; ++i) {


38  var ai = a.GetSubtree(i  1);


39  for (int j = 1; j <= n; ++j) {


40  var bj = b.GetSubtree(j  1);


41  int match = Match(ai, bj, comp);


42  matrix[i, j] = Math.Max(Math.Max(matrix[i, j  1], matrix[i  1, j]), matrix[i  1, j  1] + match);


43  }


44  }


45  return matrix[m, n] + 1;


46  }


47  }


48  }

