Visualisasi Grafik Ketergantungan

22

Tujuan dari tantangan ini adalah untuk menulis sebuah program yang memvisualisasikan grafik ketergantungan dalam bentuk pohon. Sementara "grafik dependensi" dalam konteks ini tidak lebih dari grafik yang diarahkan, metode visualisasi yang dijelaskan di sini berfungsi paling baik untuk grafik yang menggambarkan beberapa hubungan dependensi (sebagai latihan, setelah Anda membaca tantangannya, cobalah untuk membalikkan arah salah satu grafik). contoh grafik, dan lihat apakah hasilnya bermanfaat.)

The masukan untuk program ini terdiri dari satu atau lebih sasaran definisi , yang garis dalam bentuk

Target DirectDependency1 DirectDependency2 ...

, menentukan target , dan dependensi langsung terkait , jika ada. Target dan ketergantungannya secara kolektif disebut objek . Jika suatu objek hanya muncul sebagai dependensi, dan bukan sebagai target, ia tidak memiliki dependensi. Himpunan semua objek yang muncul dalam input disebut Γ . (Lihat bagian Input dan Output untuk detail lebih lanjut tentang format input.)

Untuk setiap pasangan objek, A dan B , kita mengatakan bahwa:

  • A tergantung pada B (ekuivalen, B diperlukan oleh A ), jika A secara langsung bergantung pada B , atau jika A secara langsung bergantung pada B ' , dan B' tergantung pada B , untuk beberapa objek B ' ;
  • Sebuah benar tergantung pada B (ekuivalen, B benar dibutuhkan oleh A ), jika A tergantung pada B , dan B tidak tergantung pada A .

Kami mendefinisikan objek yang dibuat, ʀooᴛ , bukan di Γ, sehingga ʀooᴛ tidak secara langsung diperlukan oleh objek apa pun, dan sedemikian rupa sehingga, untuk semua objek A , ʀooᴛ secara langsung bergantung pada A jika dan hanya jika A ada di Γ, dan A tidak diperlukan dengan benar oleh objek apa pun di Γ (dengan kata lain, ʀooᴛ langsung bergantung pada A jika tidak ada objek lain bergantung pada A , atau jika semua objek yang bergantung pada A juga diperlukan oleh A. )

Pohon Keluaran

Kami membangun pohon , yang simpul akar-nya adalah ʀooᴛ, dan sedemikian rupa sehingga anak-anak dari setiap simpul adalah dependensi langsungnya. Misalnya diberi input

Bread Dough Yeast
Dough Flour Water
Butter Milk

, pohon yang dihasilkan adalah

Contoh Pohon Keluaran

, atau, dalam bentuk ASCII,

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

. Output program adalah pohon yang didefinisikan di atas, dicetak tanpa simpul ʀooᴛ. Jadi, misalnya, output yang sesuai untuk input di atas adalah

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

. Penjelasan rinci tentang tata letak pohon output diberikan nanti.

Pesanan Node

Node anak dari node induk yang diberikan, P , harus diurutkan , sehingga, untuk semua node anak A dan B dari P , A muncul sebelum B jika dan hanya jika

  • ada simpul anak C dari P , sehingga A diharuskan oleh C , dan C mendahului, atau sama dengan, B , menurut urutan yang sama; atau ,
  • Sebuah abjad mendahului B (lebih preceisely, A mendahului B menggunakan ASCII pemeriksaan,) dan terdapat ada node anak C dari P , sehingga B benar dibutuhkan oleh C , dan C mendahului, atau setara, A , sesuai dengan urutan yang sama .

(Orang-orang yang mencari tantangan matematika mungkin ingin menunjukkan bahwa hubungan ini didefinisikan dengan baik, dan itu, pada kenyataannya, urutan total yang ketat. Jangan lupa bahwa Γ terbatas!)

Misalnya diberi input

X D C B A
B D
C A

, hasilnya harus

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

. Amuncul sebelumnya B, dan Bmuncul sebelumnya C, karena urutan abjad mereka; Dmuncul sebelumnya B, karena diharuskan olehnya, dan sesudahnya A, karena mengikutinya secara abjad; Bdan Ctidak muncul sebelumnya D, meskipun mereka mendahului secara alfabetis, karena ada simpul, yaitu B, yang membutuhkan dengan benar D, dan yang sama dengan B(yaitu, itu sendiri), dan prekursor C, sesuai dengan aturan yang sama.

Pengulangan

Objek yang sama, A , dapat muncul lebih dari sekali dalam output, jika, misalnya, diperlukan oleh lebih dari satu objek. Jika A tidak memiliki dependensi sendiri, tidak diperlukan penanganan khusus dalam kasus ini. Kalau tidak, untuk meminimalkan verbositas output, dan untuk menghindari rekursi tak terbatas karena dependensi melingkar, dependensi A hanya didaftar pada kemunculan pertamanya di mana tidak ada nenek moyang yang merupakan saudara kandung dari simpul A lainnya ; setiap kejadian lain dari A tidak boleh memiliki anak, dan harus muncul diikuti oleh spasi dan elipsis, seperti pada .A...

Misalnya diberi input

IP Ethernet
TCP IP
UDP IP
WebRTC TCP UDP

, hasilnya harus

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

. Sebagai contoh lain, menampilkan ketergantungan sirkular dan pertimbangan keturunan,

Rock Scissors
Paper Rock
Scissors Paper

, harus menghasilkan

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

. Perhatikan bahwa, misalnya, kemunculan pertama Rocktidak mencantumkan dependensinya, karena induknya Paper,, adalah saudara kandung dari Rocksimpul lain . Induk dari Rocksimpul kedua , ʀooᴛ (yang tidak muncul dalam output), tidak memiliki Rocksebagai saudara kandung, sehingga dependensi Rockterdaftar di simpul ini.

Tata Letak Pohon Keluaran

Saya yakin Anda memahami bagaimana pohon harus diwakili sebagai seni ASCII (dan jangan ragu untuk melewati bagian ini jika Anda punya), tetapi demi kelengkapan ...

Simpul turunan ʀooᴛ dicetak pada baris terpisah, tanpa lekukan apa pun, secara berurutan. Setiap simpul segera diikuti oleh anak-anaknya, jika ada, dicetak dengan cara yang sama, secara rekursif, di-indentasi oleh dua karakter ke kanan. Untuk setiap simpul yang memiliki anak, garis vertikal, yang terdiri dari |karakter (pipa), membentang turun dari karakter langsung di bawah karakter pertama dari simpul, hingga baris simpul anak terakhir, tidak termasuk anak-anak simpul anak terakhir. Jika lekukan sebuah node bukan nol, itu didahului oleh +-(pada tingkat indentasi yang sama dengan induknya), menimpa garis vertikal yang dijelaskan di atas.

Masukan dan keluaran

Anda dapat membaca input melalui STDIN , atau menggunakan metode yang setara . Anda dapat berasumsi bahwa tidak ada baris kosong , dan Anda mungkin mengharuskan baris terakhir berakhir, atau tidak berakhir, dalam karakter baris baru. Anda dapat mengasumsikan bahwa nama objek terdiri dari karakter ASCII yang dapat dicetak (tidak termasuk spasi). Anda dapat mengasumsikan bahwa objek dalam definisi target dipisahkan oleh karakter spasi tunggal , dan bahwa tidak ada spasi awal atau spasi tambahan . Anda dapat mengasumsikan bahwa setiap target didefinisikan paling banyak satu kali , dan bahwa tidak ada pengulangan dalam daftar ketergantungannya.

Anda dapat menulis output ke STDOUT , atau menggunakan metode yang setara . Semua jalur keluaran, kecuali yang terpanjang, dapat menyertakan spasi tambahan. Baris keluaran terakhir mungkin, atau mungkin tidak, berakhir pada karakter baris baru.

Skor

Ini adalah kode-golf . The jawaban terpendek , dalam byte, menang.

Uji Kasus

Program Anda harus memproses masing-masing kasus uji berikut dalam jumlah waktu yang wajar.

Memasukkan

Depender Dependee
Independent

Keluaran

Depender
+-Dependee
Independent

Memasukkan

Earth Turtle
Turtle Turtle

Keluaran

Earth
+-Turtle
  +-Turtle ...

Memasukkan

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

Keluaran

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

Pohon Teknologi Peradaban V

Memasukkan

Tampilkan cuplikan kode

Keluaran

Tampilkan cuplikan kode

Paket Ketergantungan Paket Cygwin syslog-ng

Memasukkan

Tampilkan cuplikan kode

Keluaran

Tampilkan cuplikan kode

GNU grep regex.cCall Graph

Memasukkan

Tampilkan cuplikan kode

Output (Whoops! Terlalu lama untuk ditangani SE).

code-golf ascii-art graph-theory Elo
sumber
5
Ditentukan dengan baik!
Bukan karena Charles
Referensi-diri di bagian Urutan Node membuat kepala saya sakit.
rekursif

Jawaban:

5

Haskell, 512 byte

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

Jalankan online di Ideone

Anders Kaseorg
sumber
Selamat. Sangat bagus!
Ell