Wizualizacja wykresu zależności

22

Celem tego wyzwania jest napisanie programu, który wizualizuje wykres zależności w postaci drzewa. Podczas gdy „wykres zależności” w tym kontekście oznacza nic więcej niż wykres ukierunkowany, opisana tutaj metoda wizualizacji działa najlepiej w przypadku wykresów opisujących pewną zależność zależności (jako ćwiczenie, po przeczytaniu wyzwania, spróbuj odwrócić kierunek jednego z przykładowe wykresy i sprawdź, czy wynik jest tak przydatny).

Dane wejściowe do programu składają się z jednej lub większej liczby definicji docelowych , które są wierszami formularza

Target DirectDependency1 DirectDependency2 ...

, definiowanie celu i powiązanych z nim bezpośrednich zależności , jeśli takie istnieją. Cele i ich zależności są wspólnie nazywane obiektami . Jeśli obiekt pojawia się tylko jako zależność, a nie jako cel, nie ma żadnych zależności. Zestaw wszystkich obiektów pojawiających się na wejściu nazywa się Γ . (Więcej informacji na temat formatu wejściowego znajduje się w sekcji Dane wejściowe i wyjściowe).

Dla dowolnej pary obiektów, A i B , mówimy, że:

  • A zależy od B (równoważnie, B jest wymagane przez A ), jeśli A zależy bezpośrednio od B lub jeśli A zależy bezpośrednio od B ' , a B' zależy od B , dla niektórych obiektów B ' ;
  • Odpowiednio w zależności od B (równoważnie B jest odpowiednio wymaganych A ), o ilezależy od B , a B nie zależy A .

Definiujemy wymyślony obiekt „ ʀoo” , a nie „ such” w taki sposób, że ʀoo required nie jest bezpośrednio wymagany przez żaden obiekt, i tak, że dla wszystkich obiektów A ʀooᴛ zależy bezpośrednio od A tylko wtedy, gdy A jest w Γ, a A nie jest poprawnie wymagane przez dowolny obiekt w Γ (innymi słowy, „oo ”zależy bezpośrednio od A, jeśli żaden inny obiekt nie zależy od A lub jeśli wszystkie obiekty zależne od A są również wymagane przez A. )

Drzewo wyjściowe

Konstruujemy drzewo , którego węzłem głównym jest „oo ”, i tak, że potomkami każdego węzła są jego bezpośrednie zależności. Na przykład biorąc pod uwagę dane wejściowe

Bread Dough Yeast
Dough Flour Water
Butter Milk

, powstałe drzewo to

Przykład drzewa wyjściowego

lub w formie ASCII

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

. Wyjście programu to zdefiniowane powyżej drzewo, drukowane bez węzła „ooo”. Na przykład odpowiadające wyjście dla powyższego wejścia to

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

. Szczegółowy opis układu drzewa wyjściowego podano później.

Zamówienie węzła

Węzły potomne danego węzła macierzystego, P , powinny być posortowane w taki sposób, aby dla wszystkich węzłów potomnych A i B z P , A pojawiało się przed B wtedy i tylko wtedy, gdy

  • istnieje węzeł potomny C z P , taki że A jest odpowiednio wymagany przez C , a C poprzedza lub równa się B , zgodnie z tą samą kolejnością; lub ,
  • Alfabetycznie poprzedza B (więcej preceisely, A poprzedza B za pomocą ASCII sortowania,) i istnieje nie węzła potomnego C w P tak, że B jest odpowiednio wymaganych C i C poprzedza lub równa, A , według tej samej kolejności .

(Ludzie szukający matematycznego wyzwania mogą chcieć pokazać, że relacja ta jest dobrze zdefiniowana i że w rzeczywistości jest to ścisły porządek całkowity. Nie zapominaj, że Γ jest skończone!)

Na przykład biorąc pod uwagę dane wejściowe

X D C B A
B D
C A

, wyjście powinno być

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

. Apojawia się przed Bi Bpojawia się przed C, ze względu na ich kolejność alfabetyczną; Dpojawia się przed nim B, ponieważ jest odpowiednio przez niego wymagany, a następnie A, ponieważ alfabetycznie następuje; Bi Cnie pojawiają się wcześniej D, mimo że poprzedzają go alfabetycznie, ponieważ istnieje węzeł, a mianowicie, Bktóry odpowiednio wymaga Di który jest równy B(tj. samemu sobie) i poprzedza C, zgodnie z tymi samymi regułami.

Powtórzenia

Ten sam obiekt, A , może pojawić się więcej niż jeden raz w danych wyjściowych, jeśli na przykład jest wymagany przez więcej niż jeden obiekt. Jeśli A nie ma własnych zależności, w tym przypadku nie jest wymagane specjalne postępowanie. W przeciwnym razie, w celu zminimalizowania szczegółowości danych wyjściowych i uniknięcia nieskończonej rekurencji z powodu zależności cyklicznych, zależności A są wymienione tylko przy pierwszym wystąpieniu, dla którego żaden z przodków nie jest rodzeństwem innego węzła A ; każde inne wystąpienie A nie powinno mieć dzieci i powinno pojawić się po nim spacja i elipsa, jak w .A...

Na przykład biorąc pod uwagę dane wejściowe

IP Ethernet
TCP IP
UDP IP
WebRTC TCP UDP

, wyjście powinno być

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

. Jako kolejny przykład, uwzględniający zarówno zależności cykliczne, jak i pochodzenie,

Rock Scissors
Paper Rock
Scissors Paper

, powinno skutkować

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

. Zauważ, że na przykład pierwsze wystąpienie Rocknie wyświetla jego zależności, ponieważ jego rodzic Paperjest rodzeństwem innego Rockwęzła. Element nadrzędny drugiego Rockwęzła, „oo ”(który nie pojawia się w danych wyjściowych), nie ma Rockjako rodzeństwo, więc zależności Rocksą wymienione w tym węźle.

Układ drzewa wyjściowego

Jestem pewien, że wiesz, jak drzewo powinno być przedstawiane jako sztuka ASCII (i możesz pominąć tę sekcję, jeśli masz), ale ze względu na kompletność ...

Węzły potomne „oo ”są drukowane w osobnych wierszach, bez wcięć, w kolejności. Po każdym węźle natychmiast pojawiają się jego dzieci, jeśli takie istnieją, drukowane w ten sam sposób, rekurencyjnie, wcięte dwoma znakami po prawej stronie. Dla każdego węzła, który ma dzieci, linia pionowa, składająca się ze |znaków (potoku), rozciąga się w dół od znaku bezpośrednio poniżej pierwszego znaku węzła, aż do rzędu jego ostatniego węzła potomnego, nie licząc dzieci ostatniego węzła potomnego. Jeśli wcięcie węzła jest niezerowe, poprzedza je +-(na tym samym poziomie wcięcia co jego element nadrzędny), zastępując linię pionową opisaną powyżej.

Wejście i wyjście

Możesz odczytać dane wejściowe poprzez STDIN lub za pomocą równoważnej metody . Możesz założyć, że nie ma żadnych pustych linii i możesz wymagać, aby ostatnia linia kończyła się lub nie kończyła znakiem nowej linii. Możesz założyć, że nazwy obiektów składają się z drukowalnych znaków ASCII (bez spacji). Możesz założyć, że obiekty w definicji celu są oddzielone pojedynczym znakiem spacji i że nie ma spacji wiodących ani końcowych . Możesz założyć, że każdy cel jest zdefiniowany najwyżej raz i że na jego liście zależności nie ma powtórzeń .

Możesz zapisać dane wyjściowe do STDOUT lub użyć równoważnej metody . Wszystkie linie wyjściowe, z wyjątkiem najdłuższej, mogą zawierać spacje końcowe. Ostatni wiersz wyjściowy może, ale nie musi, kończyć się znakiem nowej linii.

Wynik

To jest golf golfowy . Najkrótsza odpowiedź w bajtach, wygrywa.

Przypadki testowe

Twój program powinien przetworzyć każdy z poniższych przypadków testowych w rozsądnym czasie.

Wkład

Depender Dependee
Independent

Wydajność

Depender
+-Dependee
Independent

Wkład

Earth Turtle
Turtle Turtle

Wydajność

Earth
+-Turtle
  +-Turtle ...

Wkład

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

Wydajność

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

Drzewo technologii Civilization V.

Wkład

Pokaż fragment kodu

Wydajność

Pokaż fragment kodu

Cygwin syslog-ng Wykres zależności pakietu

Wkład

Pokaż fragment kodu

Wydajność

Pokaż fragment kodu

regex.cWykres połączeń GNU grep

Wkład

Pokaż fragment kodu

Wyjście (Ups! Zbyt długo, aby SE mógł sobie z tym poradzić.)

code-golf ascii-art graph-theory Łokieć
źródło
5
Dobrze określone!
Nie to, że Charles
Odsyłacze do siebie w sekcji Kolejność węzłów powodują ból głowy.
rekurencyjny

Odpowiedzi:

5

Haskell, 512 bajtów

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

Uruchom online w Ideone

Anders Kaseorg
źródło
Gratulacje. Bardzo dobrze!
Ell