Найти все поддеревья в дереве, соответствующем заданному поддереву в Java

Question

Я пишу код на Java, который использует неупорядоченное корневое дерево, где каждый узел может иметь любое количество дочерних узлов. Учитывая дерево T и поддерево S, я хочу, чтобы найти все поддеревья в T, которые соответствуют S (это все поддеревья в T, которые изоморфны S).

Поддерево T изоморфна S, если S узлы могут быть сопоставлены с узлами Т таким образом, чтобы края карты S к краям в T.

A previous question было предложено на как найти, если дерево содержит другое поддерево, но я хочу, чтобы найти ВСЕ поддеревьях в T, которые соответствуют S. Кроме того, я хочу иметь возможность отображать от каждого узла в каждом матче в T к соответствующему узлу в S .

То есть, когда совпадение найдено, оно должно быть возвращено не просто как указатель на узел в T, где дерево коренится, которое соответствует S, но совпадение должно быть возвращено как somethi ng как список пар указателей на узлы [(T1, S1), (T2, S2), ... (Tn, Sn)] такие, что T1 является указателем на узел в T, который сопоставляется с узлом S1 в поддерево и т. д.

Альтернативно просто список пар значений может быть возвращен, поскольку каждый узел в дереве T и поддерево S имеет уникальный идентификатор целого числа, связанный с ним.

Например:

Учитывая дерево Т следующим образом:

a 
/\ 
    b c 
/\ 
d e 

и поддерево S как:

x 
/\ 
    y z 

следующий список совпадений должны быть возвращены:

[(a, x), (b, y), (c, z)] [(Ь, х), (д, у), (е, г)]

Уникальный матч определяется набором узлов в Т, не отображение между узлами в Т и С.

Так следующее соответствие:

[(а, х), (б, г ), (с, у)]

считается дубликатом

[(а, х), (б, у), (с, г)]

, потому что они имеют один и тот же набор узлов от T (a, b, c), поэтому нужно возвращать только одно из совпадений.

В качестве другого примера, данное дерево Т:

a 
    /|\ 
    b c d 

и поддерево S:

x 
/\ 
y z 

следующий список совпадений должны быть возвращены:

[(а, х), (b, y), (c, z)] [(a, x), (b, y), (d, z)] [(a, x), (c, y), (d , z)]

Может ли кто-нибудь привести пример кода, как это сделать?

Edit (в связи с комментарием Криса Каннон в):

Я думаю, вы хотите, чтобы кто-то код ответ для вас? Как далеко вы получили ? Какой код вы написали? - Крис Каннон 1 час назад

У меня есть следующий код, который при запуске, строит список (matchesList) указателей на узлы в дереве, где поддеревья укорененных, которые соответствуют заданному поддерево. Однако может быть несколько поддеревьев, внедренных в один и тот же узел, и в настоящее время каждый узел будет добавлен не более одного раза в matchList, независимо от того, сколько совпадений коренится там.

Кроме того, я не могу решить, как создать сопоставление, описанное выше между узлами в поддереве и узлах в совпадении, найденном в исходном дереве.

package Example; 

import java.util.LinkedList; 
import java.util.Vector; 

public class PartialTreeMatch { 
    public static void main(String[] args) { 
     NodeX testTree = createTestTree(); 
     NodeX searchTree = createSearchTree(); 

     System.out.println(testTree); 
     System.out.println(searchTree); 

     partialMatch(testTree, searchTree); 
    } 

    static LinkedList<NodeX> matchesList = new LinkedList<NodeX>(); 

    private static boolean partialMatch(NodeX tree, NodeX searchTree) { 
     findSubTreeInTree(tree, searchTree); 
     System.out.println(matchesList.size()); 
     for (NodeX n : matchesList) { 
      if (n != null) { 
       System.out.println("Found: " + n); 
      } 
     } 

     return false; 
    } 

    private static NodeX findSubTreeInTree(NodeX tree, NodeX node) { 
     if (tree.value == node.value) { 
      if (matchChildren(tree, node)) { 
       matchesList.add(tree); 

      } 
     } 

     NodeX result = null; 
     for (NodeX child : tree.children) { 
      result = findSubTreeInTree(child, node); 

      if (result != null) { 
       if (matchChildren(tree, result)) { 
        matchesList.add(result); 

       } 
      } 
     } 

     return result; 
    } 

    private static boolean matchChildren(NodeX tree, NodeX searchTree) { 
     if (tree.value != searchTree.value) { 
      return false; 
     } 

     if (tree.children.size() < searchTree.children.size()) { 
      return false; 
     } 

     boolean result = true; 
     int treeChildrenIndex = 0; 

     for (int searchChildrenIndex = 0; searchChildrenIndex < searchTree.children 
       .size(); searchChildrenIndex++) { 

      // Skip non-matching children in the tree. 
      while (treeChildrenIndex < tree.children.size() 
        && !(result = matchChildren(tree.children 
          .get(treeChildrenIndex), searchTree.children 
          .get(searchChildrenIndex)))) { 
       treeChildrenIndex++; 
      } 

      if (!result) { 
       return result; 
      } 
     } 

     return result; 
    } 

    private static NodeX createTestTree() { 

     NodeX subTree2 = new NodeX('A'); 
     subTree2.children.add(new NodeX('A')); 
     subTree2.children.add(new NodeX('A')); 

     NodeX subTree = new NodeX('A'); 
     subTree.children.add(new NodeX('A')); 
     subTree.children.add(new NodeX('A')); 
     subTree.children.add(subTree2); 

     return subTree; 
    } 

    private static NodeX createSearchTree() { 
     NodeX root = new NodeX('A'); 
     root.children.add(new NodeX('A')); 
     root.children.add(new NodeX('A')); 

     return root; 
    } 
} 

class NodeX { 
    char value; 
    Vector<NodeX> children; 

    public NodeX(char val) { 
     value = val; 
     children = new Vector<NodeX>(); 
    } 

    public String toString() { 
     StringBuilder sb = new StringBuilder(); 

     sb.append('('); 
     sb.append(value); 

     for (NodeX child : children) { 
      sb.append(' '); 
      sb.append(child.toString()); 
     } 

     sb.append(')'); 

     return sb.toString(); 
    } 
} 

Код выше пытается найти все подграфы в:

A 
/|\ 
A A A 
/\ 
    A A 

который матч:

A 
/\ 
    A A 

код успешно обнаруживает, что существует соответствие коренится верхний узел первое дерево и третий ребенок первого дерева. Тем не менее, на самом верхнем узле есть 3 спички, а не один. Кроме того, код не создает сопоставление между узлами в дереве и узлами в поддереве, и я не могу понять, как это сделать.

Может кто-нибудь предложить какие-либо советы о том, как это сделать?

Answer 1

Я думаю, что ваш рекурсивный метод должен возвращать список частичных совпадений, а не просто логическое. Это проделало бы долгий путь для решения ваших проблем (необходимость вернуть список совпадений, а также найти несколько совпадений).

Java-подобный псевдокод для рекурсивной функции может выглядеть примерно так:

findMatches(treeNode, searchNode) { 
    if searchNode has no children { 
     // search successful 
     pairs = [] // empty list 
     return [pairs] // list of lists 
    } 
    else { 
     matches = [] // empty list 
     searchChild = first child node of searchNode 
     searchNode2 = searchNode with searchChild removed 
     // NOTE: searchNode2 is created by doing a shallow copy of just the node 
     // (not it's children) and then removing searchChild from the child list. 

     for each treeChild in treeNode.children { 
      if treeChild.value == searchChild.value { 
       treeNode2 = treeNode with treeChild removed // also a shallow copy 
       childMatches = findMatches(searchChild, treeChild) 
       nodeMatches = findMatches(treeNode2, searchNode2) 

       // cross-product 
       for each nodeMatchPairs in nodeMatches { 
        for each childMatchPairs in childMatches { 
         fullMatchPairs = [(searchChild, treeChild)] 
          + childMatchPairs + nodeMatchPairs // concatenate lists 
         add fullMatchPairs to matches 
        } 
       } 
      } 
     } 

     return matches 
    } 
} 

Обратите внимание, что эта функция не проверяет treeNode.value == searchNode.value, или добавьте к этому списку. Вызывающий должен это сделать. Эта функция должна выполняться на каждом узле дерева.

В настоящее время он, вероятно, использует слишком много памяти, но это может быть оптимизировано.

Answer 2

This может быть полезно.