Free cookie consent management tool by TermsFeed Policy Generator

source: stable/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Matching/SymbolicExpressionTreeMaxCommonSequenceCalculator.cs @ 11943

Last change on this file since 11943 was 10562, checked in by bburlacu, 9 years ago

#2164: Committed initial version of the tree matching functionality.

File size: 1.6 KB
Line 
1using System;
2using System.Collections.Generic;
3
4namespace HeuristicLab.Problems.DataAnalysis.Symbolic.Matching {
5  public class MaxCommonSequenceCalculator<T, U>
6    where T : class
7    where U : IEqualityComparer<T> {
8
9    public U Comparer { get; set; }
10    private int[,] matrix;
11    private List<T> sequence;
12
13    /// <summary>
14    /// Calculate the maximal common subsequence between arrays a and b and return it
15    /// </summary>
16    /// <param name="a"></param>
17    /// <param name="b"></param>
18    /// <returns></returns>
19    public IEnumerable<T> Calculate(T[] a, T[] b) {
20      int m = a.Length;
21      int n = b.Length;
22
23      if (m == 0 || n == 0) return null;
24      sequence = new List<T>();
25      matrix = new int[m + 1, n + 1];
26
27      for (int i = 0; i <= m; ++i) {
28        for (int j = 0; j <= n; ++j) {
29          if (i == 0 || j == 0) {
30            matrix[i, j] = 0;
31          } else if (Comparer.Equals(a[i - 1], b[j - 1])) {
32            matrix[i, j] = matrix[i - 1, j - 1] + 1;
33          } else {
34            matrix[i, j] = Math.Max(matrix[i - 1, j], matrix[i, j - 1]);
35          }
36        }
37      }
38      recon(a, b, n, m);
39      return sequence;
40    }
41
42    private void recon(T[] a, T[] b, int i, int j) {
43      while (true) {
44        if (i == 0 || j == 0) return;
45        if (Comparer.Equals(a[i - 1], b[j - 1])) {
46          recon(a, b, i - 1, j - 1);
47          sequence.Add(a[i - 1]);
48        } else if (matrix[i - 1, j] > matrix[i, j - 1]) {
49          i = i - 1;
50          continue;
51        } else {
52          j = j - 1;
53          continue;
54        }
55        break;
56      }
57    }
58  }
59}
Note: See TracBrowser for help on using the repository browser.