Encontre todas as subáridas em uma árvore que combine uma determinada subárvore em java

Question

Estou escrevendo código em Java que usa uma árvore não ordenada e enraizada, onde cada nó pode ter qualquer número de nós filhos. Dada uma árvore t e uma subárvore, eu quero poder encontrar todas as subáridas em T que correspondem S (que são todas as subáridas em T que são isomórficas a S).

Uma subárvore de T é isomórfica para S, se os nós de S puderem ser mapeados para nós de t de tal maneira que as bordas do s mapa nas bordas em T.

UMA pergunta anterior foi questionado sobre como encontrar se uma árvore contém outra subárvore, mas quero poder encontrar TUDO Subáridas em T que correspondem S. Além disso, eu quero ser capaz de mapear de cada nó em cada partida em t para o nó correspondente em S.

Ou seja, quando uma partida é encontrada, ela deve ser devolvida não apenas como um ponteiro para o nó em T, onde uma árvore está enraizada que corresponde S, mas a partida deve ser devolvida como algo como uma lista de pares de ponteiros para nós [ (T1, S1), (T2, S2), ... (TN, SN)] De modo que T1 seja um ponteiro de um nó em T que mapeia para o nó S1 na subárvore e assim por diante.

Como alternativa, simplesmente uma lista de pares de valores pode ser retornada, pois cada nó na árvore t e a subárvore s possui um identificador inteiro exclusivo associado a ele.

Por exemplo:

Dada a árvore t da seguinte forma:

    a
   / \
  b   c
 / \  
d   e

e subárvore s como:

    x
   / \
  y   z

A lista a seguir de correspondências deve ser devolvida:

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

Uma correspondência única é determinada pelo conjunto de nós em t, não o mapeamento entre os nós em T e S.

Então, a seguinte partida:

(a, x), (b,z), (c,y)]

é considerado duplicado de

(a, x), (b,y), (c,z)]

Porque eles têm o mesmo conjunto de nós de t (a, b, c) para que apenas uma das partidas deve ser devolvida.

Como outro exemplo, dada a árvore t:

    a
   /|\
  b c d

e subárvore s:

  x
 / \  
y   z

A lista a seguir de correspondências deve ser devolvida:

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

Alguém pode dar algum exemplo de código de como fazer isso?

Editar (em relação ao comentário de Chris Kannon):

Estou pensando que você quer que alguém codifique a resposta para você? Quão longe você chegou? Que código você escreveu? - Chris Kannon 1 hora atrás

Eu tenho o seguinte código que, quando executado, cria uma lista (Matcheslist) de ponteiros para nós na árvore, onde as subáridas estão enraizadas que correspondem à subárvore fornecida. No entanto, pode haver várias subárvores enraizadas no mesmo nó e, atualmente, cada nó só será adicionado no máximo uma vez para a lista de correspondências, independentemente de quantas correspondências estão enraizadas lá.

Além disso, não posso descobrir como construir o mapeamento descrito acima entre nós na subárvore e os nós na partida encontrada na árvore original.

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();
    }
}

O Código acima tenta encontrar todos os subgrafos em:

  A
 /|\  
A A A
   / \
  A   A

Qual correspondência:

    A
   / \
  A   A

O código detecta com sucesso que há uma partida enraizada no nó superior na primeira árvore e no 3º filho da primeira árvore. No entanto, na verdade existem três partidas enraizadas no nó superior, não apenas uma. Além disso, o código não cria um mapeamento entre nós na árvore e nós na subárvore e não consigo descobrir como fazer isso.

Alguém pode oferecer algum conselho sobre como fazer isso?

Answer 1

Eu acho que seu método recursivo precisa retornar uma lista de correspondências parciais, em vez de apenas um booleano. Isso ajudaria bastante a resolver seus problemas (a necessidade de retornar a lista de correspondências, além de encontrar várias correspondências).

O pseudocódigo semelhante a java para a função recursiva pode parecer algo assim:

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
    }
}

Observe que esta função não testar Treenode.Value == SearchNode.Value ou adicione -a à lista. O chamador precisa fazer isso. Esta função precisa ser executada em todos os nó da árvore.

Conforme projetado atualmente, provavelmente usa muita memória, mas isso pode ser otimizado.

Answer 2

este pode ser útil.