Buscar todos los subárboles en un árbol que coincida con un subárbol dado en Java

Question

Estoy escribiendo código en Java que usa un árbol rooteado y desordenado donde cada nodo puede tener cualquier número de nodos secundarios. Dado un árbol T y un subárbol S, quiero ser capaz de encontrar todos los subárboles en T que coinciden con S (que son todos los subárboles en T que son isomorfos a S).

un subárbol de T es isomorfo a S, si los nodos de S se pueden asignar a nodos de T de tal manera que los bordes de S mapa a bordes en T.

A previous question se ha pedido en cómo encontrar si un árbol contiene otro subárbol, sin embargo, quiero poder encontrar TODOS subárboles en T que coincidan con S. Además, quiero poder mapear desde cada nodo en cada coincidencia en T hasta el nodo correspondiente en S

Es decir, cuando se encuentra una coincidencia, se debe devolver no simplemente como un puntero al nodo en T donde se enraiza un árbol que coincide con S, pero la coincidencia se debe devolver como algo ng como una lista de pares de punteros a nodos [(T1, S1), (T2, S2), ... (Tn, Sn)] tal que T1 es un puntero a un nodo en T que se mapea al nodo S1 en el subárbol y así sucesivamente.

Alternativamente, simplemente se podría devolver una lista de pares de valores ya que cada nodo en el árbol T y el subárbol S tiene un identificador entero único asociado.

Por ejemplo:

árbol T de la forma siguiente:

a 
/\ 
    b c 
/\ 
d e 

y subárbol S como:

x 
/\ 
    y z 

debe devolverse la siguiente lista de coincidencias:

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

Un partido único se determina por el conjunto de nodos en T, no la asignación entre los nodos en T y S.

Así que el siguiente partido:

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

se considera que es duplicado de

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

porque tienen el mismo conjunto de nodos de T (a, b, c) por lo que solo se debe devolver una de las coincidencias.

Como otro ejemplo, árbol T dado:

a 
    /|\ 
    b c d 

y subárbol S:

x 
/\ 
y z 

la siguiente lista de coincidencias debe ser devuelto:

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

¿Alguien puede dar un código de ejemplo de cómo hacer esto?

Editar (en relación con el comentario de Chris Kannon):

Estoy pensando en usted quiere que alguien codificar la respuesta para usted? ¿Cuánto has conseguido ? ¿Qué código has escrito? - Chris Kannon Hace 1 día

tengo el siguiente código, que cuando se ejecuta, se acumula una lista (matchesList) de punteros a nodos en el árbol donde se arraigan subárboles que coincidan con el subárbol dado. Sin embargo, puede haber varios subárboles enraizados en el mismo nodo y, actualmente, cada nodo solo se agregará como máximo una vez a la Lista de coincidencias, independientemente de cuántas coincidencias haya allí.

Además, no puedo encontrar la manera de construir el mapeo descrito anteriormente entre los nodos en el subárbol y nodos en el partido que se encuentra en el árbol 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(); 
    } 
} 

El código anterior trata de encontrar todos los subgrafos en:

A 
/|\ 
A A A 
/\ 
    A A 

cual de los ajustes:

A 
/\ 
    A A 

El código detecta con éxito que hay un partido arraigado un nodo superior en primer árbol y el tercer hijo del primer árbol. Sin embargo, en realidad hay 3 coincidencias enraizadas en el nodo superior, no solo una. Además, el código no crea una asignación entre los nodos en el árbol y los nodos en el subárbol y no puedo encontrar la manera de hacerlo.

¿Alguien puede ofrecer algún consejo sobre cómo hacer esto?

Answer 1

Creo que su método recursivo necesita devolver una lista de coincidencias parciales, en lugar de un valor lógico. Eso sería un gran paso para resolver ambos problemas (la necesidad de devolver la lista de coincidencias, así como encontrar varias coincidencias).

pseudocódigo similar a Java para la función recursiva podría ser algo como esto:

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

Tenga en cuenta que esta función no prueba treeNode.value == searchNode.value, o añadir esto a la lista. La persona que llama debe hacer eso. Esta función debe ejecutarse en cada nodo del árbol.

Como actualmente diseñada, es probable que utiliza demasiada memoria, pero que podría ser optimizado.

Answer 2

This puede ser útil.