Visualización del gráfico de dependencia

22

El objetivo de este desafío es escribir un programa que visualice un gráfico de dependencia en forma de árbol. Mientras que "gráfico de dependencia" en este contexto no significa más que un gráfico dirigido, el método de visualización descrito aquí funciona mejor para gráficos que describen alguna relación de dependencia (como ejercicio, después de haber leído el desafío, intente invertir la dirección de uno de los gráficos de muestra y vea si el resultado es tan útil).

La entrada al programa consta de una o más definiciones de destino , que son líneas del formulario

Target DirectDependency1 DirectDependency2 ...

, definiendo un objetivo y sus dependencias directas asociadas , si las hay. Los objetivos y sus dependencias se denominan colectivamente objetos . Si un objeto aparece solo como una dependencia, y no como un objetivo, no tiene dependencias. El conjunto de todos los objetos que aparecen en la entrada se llama Γ . (Consulte la sección Entrada y Salida para obtener más detalles sobre el formato de entrada).

Para cualquier par de objetos, A y B , decimos que:

  • A depende de B (de manera equivalente, B es requerido por A ), si A depende directamente de B , o si A depende directamente de B ' , y B' depende de B , para algún objeto B ' ;
  • Un depende correctamente en B (que es equivalente, B está debidamente requerido por A ), si A depende de B , y B no depende de una .

Definimos un objeto artificial, ʀooᴛ , no en Γ, de modo que thatooᴛ no sea requerido directamente por ningún objeto, y de tal manera que, para todos los objetos A , ʀooᴛ dependa directamente de A si y solo si A está en Γ, y A no está debidamente requerido por cualquier objeto en Γ (en otras palabras, ʀooᴛ depende directamente de a si no hay otro objeto depende de a , o si todos los objetos que dependen de a también están obligados por una .)

Árbol de salida

Construimos un árbol , cuyo nodo raíz es ʀooᴛ, y tal que los hijos de cada nodo son sus dependencias directas. Por ejemplo, dada la entrada

Bread Dough Yeast
Dough Flour Water
Butter Milk

, el árbol resultante es

Ejemplo de árbol de salida

o, en forma ASCII,

ʀooᴛ
+-Bread
| +-Dough
| | +-Flour
| | +-Water
| +-Yeast
+-Butter
  +-Milk

. La salida del programa es el árbol definido anteriormente, impreso sin el nodo ʀooᴛ. Entonces, por ejemplo, la salida correspondiente para la entrada anterior es

Bread
+-Dough
| +-Flour
| +-Water
+-Yeast
Butter
+-Milk

. Más adelante se proporciona una descripción detallada del diseño del árbol de salida.

Orden de nodos

Los nodos hijos de un nodo padre dado, P , deben ordenarse , de modo que, para todos los nodos hijos A y B de P , A aparezca antes que B si y solo si

  • existe un nodo hijo C de P , de modo que A es requerido adecuadamente por C , y C precede, o es igual a, B , de acuerdo con el mismo orden; o ,
  • A alfabéticamente precede a B (más específicamente, A precede a B usando la intercalación ASCII) y no existe ningún nodo hijo C de P , de modo que B sea ​​requerido adecuadamente por C , y C preceda, o sea igual a, A , de acuerdo con el mismo orden .

(Las personas que buscan un desafío matemático pueden querer mostrar que esta relación está bien definida y que, de hecho, es un orden total estricto. ¡No olviden que Γ es finito!)

Por ejemplo, dada la entrada

X D C B A
B D
C A

, la salida debe ser

X
+-A
+-D
+-B
| +-D
+-C
  +-A

. Aaparece antes B, y Baparece antes C, debido a su orden alfabético; Daparece antes B, ya que lo requiere adecuadamente, y después A, ya que lo sigue alfabéticamente; By Cno aparecen antes D, a pesar de que lo preceden alfabéticamente, ya que existe un nodo, es decir, Bque requiere adecuadamente D, y que es igual a B(es decir, a sí mismo), y precede C, de acuerdo con las mismas reglas.

Repeticiones

El mismo objeto, A , puede aparecer más de una vez en la salida, si, por ejemplo, es requerido por más de un objeto. Si A no tiene dependencias propias, no se requiere un manejo especial en este caso. De lo contrario, para minimizar la verbosidad de la salida y evitar una recursión infinita debido a dependencias circulares, las dependencias de A se enumeran solo en su primera aparición para la que ninguno de los antepasados ​​son hermanos de otro nodo A ; cualquier otra aparición de A no debería tener hijos, y debería aparecer seguida de un espacio y puntos suspensivos, como en .A...

Por ejemplo, dada la entrada

IP Ethernet
TCP IP
UDP IP
WebRTC TCP UDP

, la salida debe ser

WebRTC
+-TCP
| +-IP
|   +-Ethernet
+-UDP
  +-IP ...

. Como otro ejemplo, con consideraciones de dependencia circular y ascendencia,

Rock Scissors
Paper Rock
Scissors Paper

, debería resultar en

Paper
+-Rock ...
Rock
+-Scissors ...
Scissors
+-Paper ...

. Tenga en cuenta que, por ejemplo, la primera aparición de Rockno enumera sus dependencias, ya que su padre Paperes un hermano de otro Rocknodo. El padre del segundo Rocknodo, ʀooᴛ (que no aparece en la salida), no tiene Rockcomo hermano, por lo que las dependencias de Rockse enumeran en este nodo.

Diseño del árbol de salida

Estoy seguro de que entendió cómo se debe representar el árbol como arte ASCII (y siéntase libre de omitir esta sección si lo tiene), pero en aras de la integridad ...

Los nodos secundarios de ʀooᴛ se imprimen en líneas separadas, sin sangría, en orden. Cada nodo es seguido inmediatamente por sus hijos, si los hay, impresos de la misma manera, recursivamente, sangrados por dos caracteres a la derecha. Para cada nodo que tiene elementos secundarios, una línea vertical, que consta de caracteres |(canalización), se extiende desde el carácter directamente debajo del primer carácter del nodo, hasta la fila de su último nodo secundario, sin incluir los elementos secundarios del último nodo secundario. Si la sangría de un nodo no es cero, está precedida por +-(en el mismo nivel de sangría que su padre), sobrescribiendo la línea vertical descrita anteriormente.

Entrada y salida

Puede leer la entrada a través de STDIN , o utilizando un método equivalente . Puede suponer que no hay líneas vacías y puede requerir que la última línea termine, o no termine, en un carácter de nueva línea. Puede suponer que los nombres de los objetos consisten en caracteres ASCII imprimibles (sin incluir el espacio). Puede suponer que los objetos en una definición de destino están separados por un solo carácter de espacio , y que no hay espacios iniciales o finales . Puede suponer que cada objetivo se define como máximo una vez y que no hay repeticiones en su lista de dependencias.

Puede escribir la salida en STDOUT o usar un método equivalente . Todas las líneas de salida, excepto la más larga, pueden incluir espacios finales. La última línea de salida puede, o no, terminar en un carácter de nueva línea.

Puntuación

Este es el código de golf . La respuesta más corta , en bytes, gana.

Casos de prueba

Su programa debe procesar cada uno de los siguientes casos de prueba en un tiempo razonable.

Entrada

Depender Dependee
Independent

Salida

Depender
+-Dependee
Independent

Entrada

Earth Turtle
Turtle Turtle

Salida

Earth
+-Turtle
  +-Turtle ...

Entrada

F A C B D I
A B
B A C
D E H
C
G F
J H G C E I
E D
H D
I G

Salida

J
+-C
+-E
| +-D
|   +-E ...
|   +-H ...
+-H
| +-D ...
+-G
| +-F
|   +-C
|   +-A
|   | +-B ...
|   +-B
|   | +-C
|   | +-A ...
|   +-D ...
|   +-I ...
+-I
  +-G ...

Civilization V Technology Tree

Entrada

Mostrar fragmento de código

Salida

Mostrar fragmento de código

Gráfico de dependencia del paquete Cygwin syslog-ng

Entrada

Mostrar fragmento de código

Salida

Mostrar fragmento de código

GNU grep regex.cCall Graph

Entrada

Mostrar fragmento de código

Salida (¡Vaya! Demasiado tiempo para que SE la maneje).

code-golf ascii-art graph-theory Ana
fuente
55
Bien especificado!
No es que Charles
La autorreferencia en la sección Orden de nodo me duele la cabeza.
recursivo

Respuestas:

5

Haskell, 512 bytes

import Data.List
r=reverse
n j|let(w,s)#p|let a?b=or[q!b<GT|(q,r)<-i,a==r,elem q(h p)>elem(a,q)i];a!b|a==b=EQ|a?b||(a<b)>b?a=LT;_!_=GT;l=nub.sortBy(!)$h p;m(v,s)q|h q==[]=(v,[q]:s)|elem q w=(v,[q++" ..."]:s)|(w,x:y)<-(v,[])#q=(w,(q:(u"| "=<<r y)++u"  "x):s)=foldl m(l++w,[])l;c(p,q)=z$p:q:h q;y=z=<<j;i=iterate(nub.sort.(c=<<))y!!length j;h""=[p|p<-id=<<j,and[elem(p,r)i|(r,q)<-i,p==q]];h p=[r|(q,r)<-y,p==q]=unlines=<<r(snd$mempty#"")
u s(x:y)=("+-"++x):map(s++)y
z(x:y)=(,)x<$>y
main=interact$n.map words.lines

Corre en línea en Ideone

Anders Kaseorg
fuente
Felicidades ¡Muy agradable!
Ell