Visualisation du graphique des dépendances

22

Le but de ce défi est d'écrire un programme qui visualise un graphe de dépendance sous la forme d'un arbre. Alors que "graphique de dépendance" dans ce contexte ne signifie rien de plus qu'un graphique dirigé, la méthode de visualisation décrite ici fonctionne mieux pour les graphiques décrivant une relation de dépendance (comme exercice, après avoir lu le défi, essayez d'inverser la direction de l'un des les exemples de graphiques et voyez si le résultat est aussi utile.)

L' entrée du programme consiste en une ou plusieurs définitions cibles , qui sont des lignes du formulaire

Target DirectDependency1 DirectDependency2 ...

, définissant une cible et ses dépendances directes associées , le cas échéant. Les cibles et leurs dépendances sont appelées collectivement objets . Si un objet n'apparaît qu'en tant que dépendance et non en tant que cible, il n'a pas de dépendances. L'ensemble de tous les objets qui apparaissent dans l'entrée est appelé Γ . (Voir la section Entrée et sortie pour plus de détails sur le format d'entrée.)

Pour toute paire d'objets, A et B , nous disons que:

  • A dépend de B (de manière équivalente, B est requis par A ), si A dépend directement de B , ou si A dépend directement de B ' , et B' dépend de B , pour un objet B ' ;
  • A , dependant B (équivalent, B est bien nécessaire par A ), si A dépend de B et B ne dépend pas de A .

Nous définissons un objet artificiel, ʀooᴛ , pas dans Γ, de telle sorte que ʀooᴛ ne soit directement requis par aucun objet, et tel que, pour tous les objets A , ʀooᴛ dépend directement de A si et seulement si A est dans Γ, et A n'est pas correctement requis par tout objet dans Γ (en d'autres termes, ʀooᴛ dépend directement de A si aucun autre objet ne dépend de A , ou si tous les objets qui dépendent de A sont également requis par A. )

Arbre de sortie

Nous construisons un arbre , dont le nœud racine est ʀooᴛ, et tel que les enfants de chaque nœud sont ses dépendances directes. Par exemple, étant donné l'entrée

Bread Dough Yeast
Dough Flour Water
Butter Milk

, l'arbre résultant est

Exemple d'arbre de sortie

, ou, sous forme ASCII,

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

. La sortie du programme est l'arborescence définie ci-dessus, imprimée sans le nœud ʀooᴛ. Ainsi, par exemple, la sortie correspondante pour l'entrée ci-dessus est

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

. Une description détaillée de la disposition de l'arborescence de sortie est donnée plus loin.

Ordre des nœuds

Les nœuds enfants d'un nœud parent donné, P , doivent être triés de telle sorte que, pour tous les nœuds enfants A et B de P , A apparaît avant B si et seulement si

  • il existe un nœud enfant C de P , tel que A est correctement requis par C , et C précède, ou est égal à, B , selon le même ordre; ou ,
  • A précède alphabétiquement B (plus précisément, A précède B en utilisant le classement ASCII) et il n'existe pas de nœud enfant C de P , tel que B est correctement requis par C , et C précède ou est égal à A , selon le même ordre .

(Les personnes à la recherche d'un défi mathématique voudront peut-être montrer que cette relation est bien définie et qu'il s'agit en fait d'un ordre total strict. N'oubliez pas que Γ est fini!)

Par exemple, étant donné l'entrée

X D C B A
B D
C A

, la sortie doit être

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

. Aapparaît avant Bet Bapparaît avant C, en raison de leur ordre alphabétique; Dapparaît avant B, puisqu'il lui est convenablement demandé, et après A, puisqu'il le suit alphabétiquement; Bet Cn'apparaissent pas avant D, même s'ils le précèdent par ordre alphabétique, car il existe un nœud, à savoir, Bqui nécessite correctement D, et qui est égal à B(c'est- à -dire lui-même), et précède C, selon les mêmes règles.

Répétitions

Le même objet, A , peut apparaître plusieurs fois dans la sortie, si, par exemple, il est requis par plusieurs objets. Si A n'a pas de dépendances propres, aucune manipulation spéciale n'est requise dans ce cas. Sinon, afin de minimiser la verbosité de la sortie et d'éviter la récursion infinie due aux dépendances circulaires, les dépendances de A ne sont répertoriées que lors de sa première occurrence pour laquelle aucun des ancêtres n'est le frère d'un autre nœud A ; toute autre occurrence de A ne doit pas avoir d'enfants et doit apparaître suivie d'un espace et d'une ellipse, comme dans .A...

Par exemple, étant donné l'entrée

IP Ethernet
TCP IP
UDP IP
WebRTC TCP UDP

, la sortie doit être

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

. Comme autre exemple, présentant à la fois des considérations de dépendance circulaire et d'ascendance,

Rock Scissors
Paper Rock
Scissors Paper

, devrait entraîner

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

. Notez que, par exemple, la première occurrence de Rockne répertorie pas ses dépendances, car son parent Paper, est le frère d'un autre Rocknœud. Le parent du deuxième Rocknœud, ʀooᴛ (qui n'apparaît pas dans la sortie), n'a pas Rockde frère, donc les dépendances de Rocksont répertoriées sur ce nœud.

Disposition de l'arborescence de sortie

Je suis sûr que vous avez compris comment l'arbre devrait être représenté en tant qu'art ASCII (et n'hésitez pas à ignorer cette section si vous l'avez), mais par souci d'exhaustivité ...

Les nœuds enfants de ʀooᴛ sont imprimés sur des lignes distinctes, sans indentation, dans l'ordre. Chaque nœud est immédiatement suivi de ses enfants, le cas échéant, imprimés de la même manière, récursivement, en retrait de deux caractères à droite. Pour chaque nœud qui a des enfants, une ligne verticale, composée de caractères |(pipe), descend du caractère directement sous le premier caractère du nœud, jusqu'à la ligne de son dernier nœud enfant, sans inclure les enfants du dernier nœud enfant. Si l'indentation d'un nœud est différente de zéro, elle est précédée de +-(au même niveau d'indentation que son parent), écrasant la ligne verticale décrite ci-dessus.

Entrée et sortie

Vous pouvez lire l'entrée via STDIN ou en utilisant une méthode équivalente . Vous pouvez supposer qu'il n'y a pas de lignes vides et vous pouvez exiger que la dernière ligne se termine ou ne se termine pas par un caractère de nouvelle ligne. Vous pouvez supposer que les noms d'objet sont constitués de caractères ASCII imprimables (hors espace). Vous pouvez supposer que les objets d'une définition cible sont séparés par un seul caractère espace et qu'il n'y a pas d'espaces de début ou de fin . Vous pouvez supposer que chaque cible est définie au plus une fois et qu'il n'y a pas de répétitions dans sa liste de dépendances.

Vous pouvez écrire la sortie dans STDOUT ou utiliser une méthode équivalente . Toutes les lignes de sortie, à l'exception des plus longues, peuvent inclure des espaces de fin. La dernière ligne de sortie peut se terminer ou non par un caractère de nouvelle ligne.

But

C'est du code-golf . La réponse la plus courte , en octets, gagne.

Cas de test

Votre programme doit traiter chacun des cas de test suivants dans un délai raisonnable.

Contribution

Depender Dependee
Independent

Sortie

Depender
+-Dependee
Independent

Contribution

Earth Turtle
Turtle Turtle

Sortie

Earth
+-Turtle
  +-Turtle ...

Contribution

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

Sortie

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

Arbre technologique de Civilization V

Contribution

Afficher l'extrait de code

Sortie

Afficher l'extrait de code

Graphique de dépendance des packages Cygwin syslog-ng

Contribution

Afficher l'extrait de code

Sortie

Afficher l'extrait de code

regex.cGraphique d'appel GNU grep

Contribution

Afficher l'extrait de code

Sortie (Oups! Trop de temps pour que SE puisse gérer.)

code-golf ascii-art graph-theory Aune
la source
5
Bien spécifié!
Pas que Charles
L'auto-référence dans la section Ordre des nœuds me fait mal à la tête.
récursif

Réponses:

5

Haskell, 512 octets

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

Courez en ligne sur Ideone

Anders Kaseorg
la source
Félicitations. Très agréable!
Ell