Trova tutte le sottostrutture in un albero che corrispondono a un determinato sottostruttura in Java

Question

Sto scrivendo il codice in Java che utilizza un non ordinato, albero radicato in cui ogni nodo può avere un numero illimitato di nodi figlio. Dato un albero T e una sottostruttura S, voglio essere in grado di trovare tutte le sottostrutture in T che corrispondono S (cioè tutte le sottostrutture in T che sono isomorfi a S).

Una struttura secondaria di T è isomorfo a S, se i nodi di S possono essere mappati a nodi di T in modo tale che i bordi di S mappa a bordi T.

Un domanda precedente è stato chiesto su come se trovo un albero contiene un altro sottostruttura però io voglio essere in grado di trovare tutti sottostrutture in T che corrispondono S. Oltre voglio essere in grado di mappare da ogni nodo in ogni partita in T al corrispondente nodo S.

Cioè, quando viene trovata una corrispondenza, dovrebbe essere restituito non semplicemente come un puntatore al nodo T dove è radicato un albero che corrisponde S, ma la partita deve essere restituito come qualcosa di simile a una lista di coppie di puntatori a nodi [(T1, S1), (T2, S2), ... (Tn, Sn)] tali che T1 è un puntatore a un nodo in T che associa al nodo S1 nella sottostruttura e così via.

In alternativa semplicemente una lista di coppie di valori potrebbe essere restituito come ciascun nodo albero T e sottostruttura S ha un identificatore unico intero ad esso associato.

Ad esempio:

albero Dato T come segue:

    a
   / \
  b   c
 / \  
d   e

e sottostruttura S come:

    x
   / \
  y   z

il seguente elenco di partite deve essere restituito:

  

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

Un incontro unico nel suo genere è determinata dal set di nodi in T, non il mapping tra i nodi in T e S.

Quindi, la seguente partita:

  

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

è considerato duplicato

  

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

perché hanno lo stesso insieme di nodi da T (a, b, c), in modo che solo una delle partite deve essere restituito.

Come altro esempio, dato albero T:

    a
   /|\
  b c d

e sottostruttura S:

  x
 / \  
y   z

il seguente elenco di partite deve essere restituito:

  

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

Qualcuno può dare alcun codice esempio di come fare questo?

Modifica (in relazione al commento di Chris Kannon):

  

Sto pensando si desidera che qualcuno codificare   la risposta per voi? Fino a che punto averti   ottenuto? Quale codice hai scritto? -   Chris Kannon 1 giorno fa

Ho il seguente codice che quando viene eseguito, si accumula una lista (matchesList) di puntatori ai nodi nella struttura in cui sono radicati sottostrutture che corrisponde alla struttura ad albero secondaria. Tuttavia vi possono essere più sottostrutture radicati allo stesso nodo e attualmente ogni nodo verrà aggiunto al massimo una volta al matchesList indipendentemente dal numero di partite sono radicati lì.

Inoltre, non riesco a capire come costruire la mappatura di cui sopra tra i nodi del sottoalbero e nodi in corrispondenza trovata nella struttura originale.

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

Il codice sopra cerca di trovare tutte le sottografi in:

  A
 /|\  
A A A
   / \
  A   A

che partita:

    A
   / \
  A   A

Il codice rileva correttamente che c'è una corrispondenza radicato un nodo principale nel primo albero e il 3 ° figlio del primo albero. Tuttavia, ci sono in realtà 3 partite radicati al nodo superiore, non solo uno. Inoltre, il codice non costruire una mappatura tra i nodi dell'albero ei nodi nella sottostruttura e non riesco a capire come fare questo.

Chiunque può offrire qualche consiglio su come fare questo?

Answer 1

Credo che il vostro metodo ricorsivo ha bisogno di restituire un elenco di parole parziali, invece di un valore booleano. Che sarebbe andare un lungo cammino per risolvere sia i vostri problemi (la necessità di restituire l'elenco di partite, oltre a trovare più corrispondenze).

pseudocodice Java-like per la funzione ricorsiva potrebbe essere simile a questo:

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

Si noti che questa funzione non prova treeNode.value == searchNode.value, o aggiungere questo alla lista. Il chiamante ha bisogno di farlo. Questa funzione deve essere eseguito ad ogni nodo della struttura.

Come attualmente concepito, probabilmente utilizza troppa memoria, ma che potrebbe essere ottimizzato.

Answer 2

Questo può essere utile.