Cómo comprimir y verificar la igualdad de objetos con referencias circulares

Question

Tengo cíclico estructura de tipo gráfico representada por Nodo objetos. A El nodo es un valor escalar (hoja) o una lista de n> = 1 Nodos (nodo interno).

Debido a las posibles referencias circulares, no puedo simplemente usar una función recursiva HashCode(), que combina el HashCode() de todos los nodos secundarios: terminaría en una recursión infinita.

Mientras que la parte HashCode() parece al menos ser factible al marcar e ignorar los nodos visitados, tengo algunos problemas para pensar en un algoritmo eficiente y eficiente para Equals().

Para mi sorpresa, no encontré ninguna información útil sobre esto, pero estoy seguro de que muchas personas inteligentes han pensado en buenas maneras de resolver estos problemas ... ¿no?

Ejemplo (pitón):

A = [ 1, 2, None ]; A[2] = A 
B = [ 1, 2, None ]; B[2] = B 

A es igual a B, ya que representa exactamente la misma gráfica.

BTW. Esta pregunta no está dirigida a ningún lenguaje específico, pero la implementación de hashCode() y equals() para el objeto descrito Node en Java sería un buen ejemplo práctico.

Answer 1

Si piensa en esto como un gráfico, un nodo hoja es un nodo que tiene una sola conexión y un nodo complejo es uno con al menos 2. Entonces uno lo consiguió de esa manera, implementa un algoritmo BFS simple que aplica el función hash para cada nodo que pasa y luego descarta el resultado. De esta forma, se asegura de que no caerá en celdas ni atravesará ningún nodo más de una vez.

La implementación podría ser muy sencilla. Lea sobre esto here.

Answer 2

Tienes que recorrer los gráficos.

Aquí hay una pregunta: ¿estos gráficos son iguales?

A = [1,2,None]; A[2] = A 
B = [1,2,[1,2,None]]; B[2][2] = B 

Si es así, necesita un conjunto de (Node, Node) tuplas. Use este conjunto para atrapar bucles, y devuelva 'verdadero' cuando atrape un bucle.

De lo contrario, puede ser un poco más eficiente y usar un mapa de Nodo a Nodo. Luego, cuando recorra los gráficos, construya un conjunto de correspondencias. (En el caso anterior, A correspondería con B, A [2] correspondería con B [2], & c.) Luego, cuando visite un par de nodos, asegúrese de que el par exacto esté en el mapa; si no es así, el gráfico no coincide.

Answer 3

Me gustaría saber una buena respuesta también. Hasta ahora utilizo una solución basada en el conjunto visitado.

Al calcular el hash, atravieso la estructura del gráfico y guardo un conjunto de nodos visitados. No entro al mismo nodo dos veces. Cuando toco un nodo ya visitado, el hash devuelve un número sin recurrencia.

Esto funciona incluso para la comparación de igualdad. Comparo datos de nodo e invoco recursivamente en los niños. Cuando toco un nodo ya visitado, la comparación devuelve verdadero sin recurrencia.