Trouver tous les sous-arbres dans un arbre correspondant à une sous-arborescence donnée en Java

Question

Je suis en train d'écrire le code en Java qui utilise un non ordonnée, arbre enraciné où chaque nœud peut avoir un certain nombre de nœuds enfants. Étant donné un arbre T et un sous-arbre S, je veux être en mesure de trouver tous les sous-arbres en T qui correspondent à S (qui est tous les sous-arbres en T qui sont isomorphe à S).

Un sous-arbre de T est isomorphe à S, si les noeuds de S peuvent être mises en correspondance avec des noeuds de T de telle sorte que les bords de la carte S aux bords par T.

question précédente a été demandé sur la façon de trouver si un arbre contient un autre sous-arbre mais je veux être en mesure de trouver ALL T dans les sous-arbres qui correspondent S. en outre, je veux être en mesure de carte de chaque noeud dans chaque match en T au correspondant noeud S.

C'est, lorsqu'une correspondance est trouvée, il doit être retourné non pas simplement comme un pointeur vers le nœud T où un arbre est enraciné qui correspond à S, mais le match doit être retourné quelque chose comme une liste de paires de pointeurs à des noeuds [(T1, S1), (T2, S2), ... (Tn, Sn)] de sorte que T1 est un pointeur vers un noeud dans T qui mappe vers le noeud S1 dans le sous-arbre et ainsi de suite.

En variante simplement une liste de paires de valeurs peut être retourné comme chaque noeud d'arbre T et S sous-arbre a un identificateur entier unique qui lui est associé.

Par exemple:

Compte tenu de T comme arbre suit:

    a
   / \
  b   c
 / \  
d   e

et S en tant que sous-arbre:

    x
   / \
  y   z

la liste suivante des matchs doit être retourné:

  

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

Une correspondance est déterminée par l'ensemble des noeuds en T, pas le mappage entre les noeuds de T et S.

le match suivant:

  

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

est considéré comme double de

  

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

parce qu'ils ont le même ensemble de noeuds de T (a, b, c) si seulement l'un des matches doit être retourné.

Comme autre exemple, arbre donné T:

    a
   /|\
  b c d

et S sous-arbre:

  x
 / \  
y   z

la liste suivante des matchs doit être retourné:

  

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

Quelqu'un peut-il donner un exemple de code de la façon de le faire?

Modifier (par rapport au commentaire de Chris Kannon):

  

Je pense que vous voulez que quelqu'un coder   la réponse pour vous? Dans quelle mesure vous avez   obtenu? Quel code avez-vous écrit? -   Chris Kannon il y a 1 heure

Je le code suivant qui lorsqu'il est exécuté, construit une liste (matchesList) de pointeurs vers des noeuds dans l'arbre où sont les sous-arbres enracinés qui correspondent à la sous-arborescence donnée. Cependant, il peut y avoir plusieurs sous-arbres enracinés au même noeud et actuellement chaque noeud ne sera ajouté au plus une fois à matchesList quel que soit le nombre de matchs y sont enracinés.

De plus, je ne peux pas travailler sur la façon de construire la cartographie décrite ci-dessus entre les nœuds du sous-arbre et des noeuds dans le match trouvé dans l'arbre d'origine.

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

Le code ci-dessus essaie de trouver tous les sous-graphes dans:

  A
 /|\  
A A A
   / \
  A   A

quel match:

    A
   / \
  A   A

Le code détecte avec succès qu'il ya un match ancré un nœud supérieur en premier arbre et le 3ème enfant du premier arbre. Cependant, il y a en fait 3 matchs ancrés au nœud supérieur, pas seulement un. De plus, le code ne construit pas un mappage entre les nœuds dans l'arborescence et les nœuds du sous-arbre et je ne peux pas travailler sur la façon de le faire.

Quelqu'un peut-il offrir des conseils sur la façon de le faire?

Answer 1

Je pense que votre méthode récursive doit retourner une liste des correspondances partielles, au lieu d'un booléen. Cela contribuerait grandement à résoudre les deux vos problèmes (la nécessité de retourner la liste des correspondances, ainsi que de trouver des correspondances multiples).

pseudocode Java comme pour la fonction récursive pourrait ressembler à ceci:

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

Notez que cette fonction ne vérifie pas treeNode.value == searchNode.value, ou ajoutez ceci à la liste. L'appelant doit faire. Cette fonction doit être exécuté à chaque nœud de l'arbre.

Comme actuellement conçu, il utilise probablement trop de mémoire, mais qui pourraient être optimisés.

Answer 2

Cette peut être utile.