Apakah ada algoritma yang cocok untuk menggambar campuran konstituensi / ketergantungan grafik dalam sistem koordinat?

9

Saya mencari algoritme untuk menggambar grafik gabungan / ketergantungan (untuk aplikasi linguistik). Grafik seperti itu akan memiliki dua jenis simpul yang berbeda (token, node), dan dua jenis tepi yang berbeda (hierarkis, non-hierarkis).

Saya baru mengenal teori grafik dan algoritma secara umum, dan saya harap pertanyaan ini tidak berbenturan misalnya dengan persyaratan tingkat penelitian situs ini. Namun umumnya harus dalam lingkup cerita .

Grafik harus ditarik dari bawah ke atas (saya pikir), karena semua token harus ditampilkan dengan koordinat y yang sama, dan koordinat y dari token pengelompokan node dan / atau simpul ke dalam konstituen harus dihitung secara dinamis, misalnya, melalui jalur terpanjang mereka ke token.

Tepi hierarkis (digunakan untuk mengelompokkan token / node ke dalam konstituen) harus memiliki jumlah titik bend minimum (idealnya 0), tetapi juga harus ada jumlah penyeberangan minimum, menimpa persyaratan sebelumnya jika perlu.

Tepi non-hierarkis (digunakan untuk dependensi) harus memiliki jumlah penyeberangan minimum, dan digambarkan sebagai kurva Bézier.

Hal terbaik berikutnya yang saya temui adalah algoritma yang dijelaskan oleh Buchheim et al. , meningkatkan algoritme Walker untuk berjalan dalam waktu linier.

Tolong beri tahu saya jika ada kebutuhan untuk meningkatkan pertanyaan saya, dan terima kasih banyak sebelumnya untuk petunjuk apa pun.

EDIT:

Seperti yang ditunjukkan dalam komentar, saya harus menyebutkan bahwa pada dasarnya saya ingin tata letak grafik default dengan suatu algoritma, yang saya - dalam jangka panjang - ingin mengedit dan merevisi dalam kemungkinan GEF Eclipse . Saya sebelumnya telah melihat opsi untuk membuat Graphviz bekerja dengan GEF, tetapi sepertinya tidak ada solusi yang berfungsi yang menjaga semua fungsi pengeditan yang diwarisi dari GEF.

ds.algorithms graph-algorithms cg.comp-geom graph-drawing sd
sumber
Apakah Anda memerlukan algoritme atau alat yang ada? Graphviz ( graphviz.org ) dapat melakukan ini. Anda menentukan grafik, mungkin beberapa opsi pemformatan (untuk berbagai jenis node dan tepi) dan alat akan menghasilkan grafik yang diberikan secara wajar.
Dave Clarke
@DaveClarke: Terima kasih. Saya menyadari Graphviz dapat melakukan ini. Sayangnya sepertinya tidak ada kemungkinan di luar sana untuk menggunakan Graphviz dengan editor berdasarkan [Eclipse Graphical Editing Framework] (www.eclipse.org/gef). Karenanya saya mencari algoritma yang sebenarnya. Kecuali ada yang tahu cara pasang / port Graphviz ke GEF tentu :)
sd
Kedengarannya seperti OP sedang mencari algoritma (atau perumusan masalah yang menangkap spesifikasi)
Suresh Venkat
@ SureshVenkat: Ya, terima kasih telah menjelaskan.
sd
1
Q tidak menyebutkan penyuntingan & tetapi dalam komentar Anda menolak graphviz & sepertinya mengindikasikan Anda ingin mengeditnya dengan GEF. GEF adalah kerangka kerja penyuntingan visual umum / API tempat "plugin" lain dapat dibangun. Anda tampaknya menginginkan tata letak grafik default dengan suatu algoritma yang kemudian dapat Anda revisi. sarankan Anda mengedit pertanyaan Anda untuk mencerminkan hal itu. by the way percaya graphviz dapat digunakan untuk menghasilkan koordinat yang kemudian dapat dimasukkan ke dalam editor grafik. sedang mengedit grafik GEF lihat misalnya tata letak grafik profesional untuk GEF
vzn

Jawaban:

1

Anda sepertinya menginginkan yang berikut ini

  • algoritma tata letak grafik. banyak algoritma std biasanya menggunakan metode berbasis gaya di mana node dihubungkan oleh "pegas" yang menarik / menarik dan keseimbangan / keadaan energi rendah diperoleh melalui beberapa iterasi (dari persamaan diferensial terkait kekuatan yang dibangun secara global). output dari algoritma adalah satu set koordinat 2-d atau 3-d untuk node dan (biasanya) edge.
  • kemampuan untuk secara manual memodifikasi hasil dari algoritma tersebut. biasanya disebut "editor grafik". ini dimulai dengan koordinat dari algoritma tata letak dan memungkinkan penyesuaian.

re (1) perangkat lunak terdepan tampaknya graphviz . re (2) lihat misalnya pertanyaan ini "apa editor grafik terbaik" di mathoverflow .

menelusuri galeri graphviz, berikut adalah dua jenis grafik yang mirip dengan yang Anda inginkan.

Diagram ER dan lampu lalu lintas .

Anda mengatakan Anda memiliki dua jenis tepi. cara sederhana adalah dengan mengarahkan tepi "ke atau jauh" seperti pada contoh lampu lalu lintas. atau ujung-ujungnya dapat dilabeli dengan dua cara seperti pada diagram ER. kedua contoh menunjukkan dua tipe simpul yang berbeda menggunakan bentuk atau label yang berbeda, atau naungan dll. pendekatan lain adalah menggunakan pewarnaan.

sebagai mathoverflow T / As menunjukkan ada banyak editor grafik. yang pertama dengan graphviz adalah "dotty". lihat misalnya pdf "pengeditan grafik dengan dotty " oleh Koutsofious.

teknik lain untuk grafik, mungkin grafik besar, adalah dengan melihat komposisi struktural misalnya dekomposisi klik.

vzn
sumber