Abhängigkeitsdiagramm-Visualisierung

22

Ziel dieser Herausforderung ist es, ein Programm zu schreiben , das einen Abhängigkeitsgraphen in Form eines Baums visualisiert. Während "Abhängigkeitsgraph" in diesem Kontext nichts anderes als ein gerichteter Graph bedeutet, funktioniert die hier beschriebene Visualisierungsmethode am besten für Graphen, die eine Abhängigkeitsrelation beschreiben (als Übung versuchen Sie, nach dem Lesen der Herausforderung die Richtung einer der Graphen umzukehren die Beispielgrafiken und sehen, ob das Ergebnis so nützlich ist.)

Die Eingabe in das Programm besteht aus einer oder mehreren Zieldefinitionen , die Zeilen des Formulars sind

Target DirectDependency1 DirectDependency2 ...

Definieren eines Ziels und der damit verbundenen direkten Abhängigkeiten , falls vorhanden. Ziele und ihre Abhängigkeiten werden gemeinsam als Objekte bezeichnet . Wenn ein Objekt nur als Abhängigkeit und nicht als Ziel angezeigt wird, hat es keine Abhängigkeiten. Die Menge aller Objekte, die in der Eingabe erscheinen, heißt Γ . (Weitere Informationen zum Eingabeformat finden Sie im Abschnitt Eingabe und Ausgabe.)

Für jedes Paar von Objekten, A und B , sagen wir Folgendes:

  • A hängt von B (äquivalent B wird durch erforderlich A ), falls A hängt direkt von B , oder wenn A hängt direkt von B ‚ und B‘ hängt von B , für einen Gegenstand B‘ ;
  • A hängt richtig von B ab (äquivalent dazu wird B von A richtig benötigt ), wenn A von B abhängtund B nicht von A abhängt.

Wir definieren ein erfundenes Objekt, ʀooʀ , nicht in Γ, so dass ʀooʀ von keinem Objekt direkt benötigt wird und dass ʀooʀ für alle Objekte A genau dann von A abhängt, wenn A in Γ ist, und A nicht Ordnungsgemäß von einem Objekt in Γ angefordert (mit anderen Worten, ʀooᴛ hängt direkt von A ab, wenn kein anderes Objekt von A abhängt oder wenn alle Objekte, die von A abhängen, auch von A angefordert werden .)

Ausgabebaum

Wir konstruieren einen Baum , dessen Wurzelknoten "100" ist, und zwar so, dass die Kinder jedes Knotens seine direkten Abhängigkeiten sind. Zum Beispiel angesichts der Eingabe

Bread Dough Yeast
Dough Flour Water
Butter Milk

Der resultierende Baum ist

Beispiel für einen Ausgabebaum

oder in ASCII-Form

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

. Die Ausgabe des Programms ist der oben definierte Baum, der ohne den Knoten ʀooʀ gedruckt wird . So ist zum Beispiel der entsprechende Ausgang für den obigen Eingang

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

. Eine detaillierte Beschreibung des Layouts des Ausgabebaums wird später gegeben.

Knotenreihenfolge

Die untergeordneten Knoten eines gegebenen Elternknoten, P , werden sortiert , so dass für alle untergeordneten Knoten A und B von P , A erscheint vor B , wenn und nur wenn

  • es gibt einen Kindknoten C von P , so dass A von C ordnungsgemäß benötigt wird und C B entsprechend derselben Reihenfolge vorausgeht oder gleich B ist; oder ,
  • A steht alphabetisch vor B (genauer gesagt, A steht unter Verwendung der ASCII- Kollatierung vor B ), und es gibt keinen untergeordneten Knoten C von P , sodass B ordnungsgemäß von C benötigt wird und C A entsprechend derselben Reihenfolge vorausgeht oder gleich A ist .

(Leute, die nach einer mathematischen Herausforderung suchen, möchten vielleicht zeigen, dass diese Beziehung gut definiert ist und dass es sich tatsächlich um eine strenge Gesamtordnung handelt. Vergessen Sie nicht, dass Γ endlich ist!)

Zum Beispiel angesichts der Eingabe

X D C B A
B D
C A

sollte die Ausgabe sein

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

. Aerscheint vor Bund Berscheint vor C, aufgrund ihrer alphabetischen Reihenfolge; Derscheint davor B, da es von ihm richtig verlangt wird, und danach A, da es alphabetisch danach folgt; Bund Cerscheinen nicht davor D, obwohl sie alphabetisch vorangestellt sind , da es einen Knoten gibt, nämlich den, Bder ordnungsgemäß benötigt Dund der B(dh sich selbst) entspricht und Cnach denselben Regeln vorangeht .

Wiederholungen

Das gleiche Objekt A kann in der Ausgabe mehrmals vorkommen, wenn es beispielsweise von mehr als einem Objekt benötigt wird. Wenn A keine eigenen Abhängigkeiten hat, ist in diesem Fall keine besondere Behandlung erforderlich. Andernfalls werden die Abhängigkeiten von A nur beim ersten Auftreten aufgelistet, für das keiner der Vorfahren Geschwister eines anderen A- Knotens sind , um die Ausführlichkeit der Ausgabe zu minimieren und eine unendliche Rekursion aufgrund von zirkulären Abhängigkeiten zu vermeiden . Jedes andere Vorkommen von A sollte keine untergeordneten Elemente enthalten und von einem Leerzeichen und einer Ellipse gefolgt sein, wie in .A...

Zum Beispiel angesichts der Eingabe

IP Ethernet
TCP IP
UDP IP
WebRTC TCP UDP

sollte die Ausgabe sein

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

. Als weiteres Beispiel, das sowohl zirkuläre Abhängigkeiten als auch Überlegungen zur Abstammung enthält,

Rock Scissors
Paper Rock
Scissors Paper

sollte ergeben

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

. Beachten Sie, dass beispielsweise beim ersten Auftreten von Rockdie Abhängigkeiten nicht aufgelistet werden, da das übergeordnete Element Paperein Geschwister eines anderen RockKnotens ist. Das übergeordnete RockElement des zweiten Knotens, "100" (das nicht in der Ausgabe angezeigt wird), hat kein gleichrangiges Element Rock, daher werden die Abhängigkeiten von Rockauf diesem Knoten aufgelistet.

Ausgabebaumlayout

Ich bin mir sicher, Sie wissen, wie der Baum als ASCII-Grafik dargestellt werden soll (und Sie können diesen Abschnitt auch überspringen, wenn Sie dies haben), aber der Vollständigkeit halber ...

Die untergeordneten Knoten von ʀooʀ werden der Reihe nach in separaten Zeilen ohne Einrückung gedruckt. Jedem Knoten folgen unmittelbar die Kinder (falls vorhanden), die in derselben Weise rekursiv gedruckt und von zwei Zeichen rechts eingerückt werden. Für jeden Knoten mit untergeordneten Knoten verläuft eine vertikale Linie, die aus |(Pipe-) Zeichen besteht, vom Zeichen direkt unter dem ersten Zeichen des Knotens bis zur Zeile seines letzten untergeordneten Knotens, wobei die untergeordneten Knoten des letzten untergeordneten Knotens nicht berücksichtigt werden. Wenn der Einzug eines Knotens ungleich Null ist, wird ihm +-(auf derselben Einzugsebene wie dem übergeordneten Knoten ) das Überschreiben der oben beschriebenen vertikalen Linie vorangestellt .

Ein- und Ausgang

Sie können die Eingabe über STDIN oder eine gleichwertige Methode lesen . Sie können davon ausgehen, dass keine leeren Zeilen vorhanden sind , und Sie müssen möglicherweise festlegen, dass die letzte Zeile in einem Zeilenumbruchzeichen endet oder nicht endet. Sie können davon ausgehen, dass Objektnamen aus druckbaren ASCII-Zeichen bestehen (ohne Leerzeichen). Sie können davon ausgehen, dass Objekte in einer Zieldefinition durch ein einzelnes Leerzeichen getrennt sind und keine führenden oder nachfolgenden Leerzeichen vorhanden sind . Sie können davon ausgehen, dass jedes Ziel höchstens einmal definiert wurde und die Abhängigkeitsliste keine Wiederholungen enthält .

Sie können die Ausgabe in STDOUT schreiben oder eine äquivalente Methode verwenden . Alle Ausgabezeilen, mit Ausnahme der längsten, können nachgestellte Leerzeichen enthalten. Die letzte Ausgabezeile kann mit einem Zeilenumbruchzeichen enden oder auch nicht.

Ergebnis

Das ist Code-Golf . Die kürzeste Antwort in Bytes gewinnt.

Testfälle

Ihr Programm sollte jeden der folgenden Testfälle in angemessener Zeit verarbeiten.

Eingang

Depender Dependee
Independent

Ausgabe

Depender
+-Dependee
Independent

Eingang

Earth Turtle
Turtle Turtle

Ausgabe

Earth
+-Turtle
  +-Turtle ...

Eingang

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

Ausgabe

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

Civilization V-Technologiebaum

Eingang

Code-Snippet anzeigen

Ausgabe

Code-Snippet anzeigen

Cygwin syslog-ng Paketabhängigkeitsdiagramm

Eingang

Code-Snippet anzeigen

Ausgabe

Code-Snippet anzeigen

GNU grep regex.cCall Graph

Eingang

Code-Snippet anzeigen

Ausgabe (Hoppla! Für SE zu lang.)

code-golf ascii-art graph-theory Ell
quelle
5
Gut spezifiziert!
Nicht dass Charles
Die Selbstreferenz im Abschnitt zur Knotenreihenfolge lässt meinen Kopf schmerzen.
rekursiver

Antworten:

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

Laufen Sie online bei Ideone

Anders Kaseorg
quelle
Glückwunsch. Sehr schön!
Ell