Melacak Tipe Data yang Hilang

Mencari tipe data yang hilang

• Graf adalah himpunan node yang terhubung oleh panah (edge).
• Node dan edge dapat memuat data.
• Dalam rekayasa perangkat lunak, graf hadir dalam berbagai bentuk seperti dependensi paket, tautan internet, ruang status perangkat lunak, basis data relasional, linked list, binary tree, hash table, dan lain-lain.
• Dalam logika bisnis juga, graf dimanfaatkan untuk referensi kutipan, jaringan transportasi, jejaring sosial, dan sebagainya.
• Jika cukup lama mengembangkan perangkat lunak, besar kemungkinan Anda akan menjumpai graf di mana-mana.

Pergulatan dalam menggunakan graf

• Graf memang berguna, tetapi menggunakan graf di kode nyata terasa membebani.
• Di sebagian besar bahasa pemrograman arus utama, graf tidak didukung sebagai tipe bawaan, jarang ada di pustaka standar, dan pustaka pihak ketiga yang kokoh juga tidak banyak.
• Dalam banyak kasus, kita harus mengimplementasikan graf sendiri.
• Ada kesenjangan antara seberapa sering insinyur perangkat lunak perlu menggunakan graf dan dukungan yang tersedia di ekosistem pemrograman.

Mengapa tidak ada tipe graf

Terlalu banyak pilihan desain

• Ada berbagai jenis graf: graf berarah dan tak berarah, graf sederhana dan multigraf, hipergraf, ubergraph, dan lainnya.
• Untuk tiap jenis, perlu diputuskan apakah node dan edge akan diberi ID, data seperti apa yang akan disimpan, dan sebagainya.
• Pustaka graf sempurna yang mendukung semua kemungkinan akan membutuhkan waktu yang sangat lama untuk dibuat.
• Kinerja algoritme graf itu penting, dan kasus-kasus khusus juga penting.
• Algoritme graf sulit diimplementasikan dengan benar.

Terlalu banyak pilihan implementasi

• Bahkan jika diasumsikan hanya mendukung graf berarah sederhana, tetap ada banyak cara untuk merepresentasikan graf secara internal.
• Ada berbagai cara penyimpanan seperti edge list, adjacency list, adjacency matrix, kumpulan struct, dan lain-lain.
• Operasi graf yang berbeda memiliki karakteristik kinerja yang berbeda pada representasi yang berbeda.
• Bergantung pada apakah graf jarang atau padat, representasi internal graf yang optimal juga berbeda.
• Mengimplementasikan data node, data edge, serta berbagai jenis node dan edge membuatnya makin rumit.

Kinerja terlalu penting

• Banyak algoritme graf adalah masalah NP-lengkap atau bahkan lebih sulit.
• Graf bisa menjadi masalah yang sangat besar, dan kinerja dapat sangat berbeda tergantung detail representasi dan implementasi algoritmenya.
• Diperlukan banyak kendali atas representasi data dan algoritme.

Konsensus yang terbentuk

• Beragamnya jenis graf, representasi, algoritme, sensitivitas terhadap kinerja, serta mahalnya menjalankan algoritme pada graf besar adalah alasan mengapa dukungan graf tidak tersebar luas.
• Ini menjelaskan mengapa bahasa pemrograman tidak mendukung graf di pustaka standarnya.
• Ini juga menjelaskan mengapa programmer menghindari pustaka graf pihak ketiga.
• Karena menggunakan graf itu sulit, ini menjelaskan mengapa orang enggan memikirkan masalah sebagai graf kecuali dalam situasi yang ekstrem.

Opini GN⁺

• Artikel ini memberikan wawasan tentang mengapa graf belum menjadi tipe data dasar di bahasa pemrograman dan pustakanya.
• Teori graf adalah bidang penting dalam ilmu komputer dan diterapkan di berbagai area seperti algoritme, analisis jaringan, basis data, dan lain-lain.
• Untuk menggunakan graf secara efektif, optimasi kinerja dan pemilihan struktur data yang tepat sangat penting.
• Pustaka pihak ketiga seperti NetworkX, Boost Graph Library, dan Graph-tool dapat digunakan untuk menyelesaikan berbagai masalah graf.
• Saat menggunakan graf, penting untuk memilih jenis graf dan algoritme yang sesuai dengan karakteristik masalah, karena hal ini berkaitan langsung dengan kinerja sistem.

[GN⁺]

Komentar Hacker News

• Graphviz memiliki pustaka graf miliknya sendiri, yang tidak digunakan oleh proyek lain. Pustaka ini punya kelebihan dan kekurangan.

  • Berdasarkan pengalaman ini, mereka mengalami versi mereka sendiri dari 'second-system syndrome'.
  • Mereka memutuskan bahwa pustaka graf harus modular, type-safe, dan efisien. Ini mungkin merupakan variasi dari ungkapan "baik, cepat, murah — pilih dua".
  • Modular berarti mereka ingin menulis kumpulan pustaka algoritme graf yang dapat dikembangkan dan dikompilasi secara independen.
  • Type-safe berarti mereka ingin mendeteksi kesalahan pemrograman saat kompilasi, atau setidaknya saat linking. Mereka tidak menginginkan kesalahan saat runtime.
  • Efisiensi berarti mengakses properti graf harus semurah mengakses field pada struct C.
  • Apakah tujuan-tujuan ini layak dikejar masih bisa diperdebatkan, tetapi itulah yang mereka inginkan. Karena para pencipta C++ terkenal ada di lab mereka, mereka berharap bisa mendapat bantuan, dan memutuskan memberi C++ satu kesempatan lagi.
  • Gordon Woodhull, mantan intern yang merupakan programmer luar biasa, mengimplementasikan pustaka graf semacam ini dalam template C++. Ini dirilis melalui sourceforge di https://www.dynagraph.org/.
  • Karena mereka tidak yakin orang lain akan bisa memahami cara kerja kode itu, mereka melakukan code review dengan para penemu C++ yang terkenal. Mereka menyadari bahwa mereka mungkin sudah melewati tebing kompleksitas.
  • Ini bukan salah Gordon, dan ia terus maju serta berhasil mengerjakan layout graf dinamis bahkan dalam Microsoft OLE. Jika dipikir kembali, ini mungkin adalah Project Xanadu versi mereka sendiri.
  • Sementara mereka tenggelam dalam hal ini, banyak hal lain muncul, seperti Gephi (Java) dan NetworkX serta NetworKit (Python).
  • John Ellson adalah software engineer yang sangat berbakat yang menulis sebagian dari Graphviz, dan ia menghidupkan kembali upaya utamanya.

• Jika Anda menulis kode di .NET, Anda mungkin ingin mencoba Arborescence, pustaka graf kecil yang tidak terlalu kaya fitur.

  • Saya percaya pustaka ini menawarkan pemisahan yang baik antara abstraksi, algoritme, dan struktur data.
  • Pengguna dapat memakai edge dengan ID mereka sendiri, atau menggunakan graf implisit yang diekspansi saat dibutuhkan.
  • Tersedia antarmuka adjacency (tetangga keluar) dan incidence (edge keluar + head).
  • Pustaka ini tidak memaksakan tipe edge, tetapi menyediakan struktur dasar pasangan tail-head sebagai utilitas.

• Graf bukanlah struktur data atau tipe data, melainkan sebuah abstraksi.

  • Pada dasarnya, yang diperlukan untuk mendefinisikan graf hanyalah himpunan vertex dan fungsi tetangga.
  • Semua hal lainnya adalah batasan kasus per kasus.
  • Jika mempertimbangkan hypergraph, graf hanyalah kasus khusus.
  • Jika dipandang dari perspektif basis data, graf adalah masalah optimasi kueri dan pengindeksan.

• Saya sering mendapat pertanyaan mengapa tidak ada tipe data graf yang tertanam dalam bahasa pemrograman.

  • Sekarang saya senang bisa menunjuk ke analisis yang lebih mendalam seperti tulisan ini.

• Hambatan utamanya adalah sebagai berikut:

  • Untuk masalah graf yang sederhana dan kecil, cukup mudah menulis adjacency list sebagai vector of vectors.
  • Untuk masalah graf yang kompleks dan sangat besar, tidak ada cara mendapatkan performa selain menyesuaikan implementasi graf dengan masalahnya.
  • Tidak jelas bentuk dukungan bahasa seperti apa yang akan membantu.

• Tulisan ini sebagian besar menjawab pertanyaan mengapa algoritme graf tidak didukung lebih baik dalam bahasa pemrograman.

  • Jika melihat dukungan graf secara umum, muncul pertanyaan yang lebih luas, seperti mengapa OGM tidak sepopuler ORM, atau mengapa JSON lebih luas digunakan daripada RDF.
  • Pada akhirnya, karena alasan historis dan kompleksitas graf, hal ini tidak berkembang dengan baik di kalangan developer.

• Alat visualisasi graf juga sangat mengecewakan.

  • Pada graf dengan lebih dari 500 node, hasil keluarannya menjadi sulit dipahami atau terlalu rumit.
  • Masih kurang fitur yang dapat otomatis menyusun graf ke dalam struktur hierarkis dan menyediakan antarmuka yang baik untuk menelusurinya.

• Tulisan ini benar-benar keren.

  • Mengenai pengamatan inti bahwa "ada terlalu banyak pilihan implementasi", sebenarnya tidak demikian.
  • Pada praktiknya, pustaka dapat mengimplementasikan semua representasi graf yang sesuai.
  • Algoritme dapat disesuaikan dengan representasi, dan dapat mengonversi dari satu representasi ke representasi lain.

• Electric Clojure menggunakan Clojure itu sendiri (s-expression) sebagai sintaks authoring graf.

  • DSL authoring graf harus dapat mengekspresikan scope, control flow, dan abstraksi, yang pada dasarnya sama dengan bahasa pemrograman.

• Ada tipe data berguna lain seperti tabel (misalnya tabel di dalam basis data).

  • Akan ada kemajuan dalam bahasa pemrograman jika kompiler dibiarkan memilih implementasi struktur data.
  • Gunakan struktur abstrak (sequence, map, set, table, graph, dan sebagainya), lalu biarkan kompiler memilih implementasi konkret berdasarkan profil program.