isIsomorphicTo method

bool isIsomorphicTo(
  1. IGraph other
)

Проверяет, изоморфны ли два графа Два графа изоморфны, если они имеют одинаковую структуру, независимо от порядка потомков

Implementation

bool isIsomorphicTo(IGraph<dynamic> other) {
  bool areSubtreesIsomorphic(Node node1, Node node2) {
    final children1 = getNodeEdges(node1);
    final children2 = other.getNodeEdges(node2);

    if (children1.length != children2.length) return false;
    if (children1.isEmpty) return true;

    // Для каждого ребенка из первого графа
    // должен найтись изоморфный из второго
    final used = <Node>{};
    for (final child1 in children1) {
      bool foundMatch = false;

      for (final child2 in children2) {
        if (!used.contains(child2) && areSubtreesIsomorphic(child1, child2)) {
          used.add(child2);
          foundMatch = true;
          break;
        }
      }

      if (!foundMatch) return false;
    }

    return true;
  }

  return areSubtreesIsomorphic(root, other.root);
}