Necesito un editor que permita ingresar a un árbol, cada nodo del cual puede contener varios subnodos.
La parte de entrada es fácil. Puedo usar solo un editor de texto y una lista jerárquica como
* a ** b ** c *** d
Pero también necesito comparar dos árboles (encontrar si hay alguna diferencia y si hay diferencias, informarlas).
El orden de los nodos no importa. Entonces el árbol anterior se considera equivalente a
* a ** c *** d ** b
Estoy usando Ubuntu Linux, y el software debería venir sin dinero pagado.
Mejor que nada respuesta parcial. Este método puede devolver un falso positivo (ver notas al final), pero no un falso negativo ( es decir , los resultados negativos son confiables).
tsortes una utilidad útil que realiza la clasificación topológica a partir de la entrada estándar. tsortrequiere entrada emparejada de nodos, de modo que esto:
* a
** b
** c
*** d
Primero debe ser reformateado para tsortque se vea así:
a b
a c
c d
Canaliza eso a través de tsort:
printf '%s %s\n' a b a c c d | sort | tsort
Producción:
a
c
b
d
Usando bashy diff, los dos árboles en la pregunta se pueden comparar así:
diff <(printf '%s %s\n' a c c d a b | sort | tsort) \
<(printf '%s %s\n' a b a c c d | sort | tsort)
La salida es nada, ya que los dos árboles son iguales.
Notas:
los tsortdocumentos necesitan mejorar.
Los resultados negativos (los árboles son diferentes) son fiables. Los resultados positivos (los árboles son los mismos) pueden no serlo. Algunos gráficos (todos los árboles son gráficos) que son diferentes aún pueden tener el mismo resultado de clasificación. Pero si diffdevuelve algo, los árboles no son absolutamente iguales.
Ejemplo de falso positivo, considere los dos árboles:
+---+
| a |
+---+
|
|
v
+---+
| b |
+---+
|
|
v
+---+
| c |
+---+
y:
+---+ +---+
| c | <-- | a |
+---+ +---+
|
|
v
+---+
| b |
+---+
Pon esos árboles en tsort:
paste <(printf '%s %s\n' a b a c | sort | tsort) \
<(printf '%s %s\n' a c c b | sort | tsort)
Producción:
a a
c c
b b