calculateEditDistance method

Implementation

int calculateEditDistance(IGraph<dynamic> other) {
  int subtreeEditDistance(Node? node1, Node? node2) {
    if (node1 == null && node2 == null) return 0;
    if (node1 == null) return 1; // нужно добавить узел
    if (node2 == null) return 1; // нужно удалить узел

    final children1 = getNodeEdges(node1).toList();
    final children2 = other.getNodeEdges(node2).toList();

    // Базовая стоимость - отличаются ли узлы
    final int cost = node1.key != node2.key ? 1 : 0;

    // Находим минимальную стоимость сопоставления детей
    final m = children1.length;
    final n = children2.length;
    final dp = List.generate(
      m + 1,
      (i) => List.generate(n + 1, (j) => 0),
    );

    // Инициализация
    for (int i = 0; i <= m; i++) {
      dp[i][0] = i;
    }
    for (int j = 0; j <= n; j++) {
      dp[0][j] = j;
    }

    // Заполняем динамику
    for (int i = 1; i <= m; i++) {
      for (int j = 1; j <= n; j++) {
        dp[i][j] = min(
          dp[i - 1][j] + 1, // удаление
          min(
            dp[i][j - 1] + 1, // вставка
            dp[i - 1][j - 1] +
                subtreeEditDistance(
                  children1[i - 1],
                  children2[j - 1],
                ), // замена или совпадение
          ),
        );
      }
    }

    return cost + dp[m][n];
  }

  return subtreeEditDistance(root, other.root);
}