Melacak Tipe Data yang Hilang

 (hillelwayne.com)
2 poin oleh GN⁺ 2024-03-05 | 1 komentar | Bagikan ke WhatsApp
  • Graf ada di berbagai bagian perangkat lunak, seperti dependensi, tautan web, ruang keadaan pada model checker, dan foreign key di basis data relasional, tetapi bahasa pemrograman arus utama hampir tidak memiliki tipe bawaan atau dukungan pustaka standar untuknya
  • Alasan pertama sulitnya membuat tipe graf bawaan adalah banyaknya jenis graf seperti directed/undirected, simple/multigraph, dan hypergraph, serta fakta bahwa sifat tertentu dapat sangat mengubah pilihan algoritme dan performa
  • Tiap cara representasi seperti edge list, adjacency list, adjacency matrix, dan struktur referensi memiliki karakteristik memori dan performa lookup yang berbeda, sehingga sulit memenuhi semua use case dengan satu representasi umum
  • Algoritme graf sulit diimplementasikan dan sering dijalankan pada input besar, sehingga seperti dalam kasus Nosey Parker dan Gecode, representasi dan traversal yang disesuaikan dengan masalah bisa menjadi lebih penting daripada pustaka umum
  • Graf jarang ada di pustaka standar karena trade-off tipe, representasi, algoritme, performa, dan beban pemeliharaan yang besar; pustaka pihak ketiga pun bisa terbatas atau lambat

Graf umum ditemukan, tetapi dukungan bahasa masih kurang

  • Graf terdiri dari node dan edge, dan node maupun edge dapat berisi data
  • Dalam software engineering, graf muncul dalam berbagai bentuk
    • Dependensi paket dan import modul membentuk directed graph
    • Internet adalah graf tautan antarhalaman web
    • Model checker menelusuri ruang keadaan dari semua konfigurasi yang mungkin; node adalah keadaan dan edge adalah transisi yang valid
    • Basis data relasional dapat dipandang sebagai record sebagai node dan foreign key sebagai edge
    • Graf dapat dipandang sebagai generalisasi dari linked list, binary tree, dan hash table
  • Dalam logika bisnis, graf juga sering muncul, seperti hubungan sitasi makalah, rute jaringan transportasi, dan koneksi social network
  • Graf sering dibutuhkan, tetapi sebagian besar bahasa arus utama tidak menyediakan graf sebagai tipe bawaan, dan jarang pula memasukkannya ke pustaka standar
  • Banyak ekosistem juga kekurangan pustaka graf pihak ketiga yang solid, sehingga sering kali graf harus diimplementasikan sendiri

Terlalu banyak pilihan dalam merancang tipe graf

  • Selain directed graph dan undirected graph, graf memiliki berbagai variasi lain
    • Simple graph, yang memiliki maksimal satu edge di antara dua node, dan multigraph, yang mengizinkan beberapa edge
    • Hypergraph, yaitu satu edge dapat menghubungkan tiga node atau lebih
    • Ubergraph, yaitu edge dapat menunjuk ke edge lain
  • Setiap variasi membawa keputusan desain tambahan
    • Harus diputuskan apakah edge juga diberi ID, atau hanya node yang diberi ID
    • Harus diputuskan pula data apa yang disimpan pada node dan edge
  • Semua graf bisa saja disediakan sebagai tipe umum seperti “directed hyper-uber-multigraph” lalu dibatasi oleh pengguna, tetapi dua masalah langsung muncul
    • Antarmuka berubah, misalnya apakah hasil operasi adalah satu nilai atau sebuah list
    • Jika sifat khusus graf tidak dimanfaatkan, performa algoritme memburuk
  • Misalnya, maximum weight matching dapat memakai algoritme cepat jika diketahui bahwa grafnya bipartite, tetapi untuk graf umum dibutuhkan algoritme yang lebih lambat dan lebih generik
  • Untuk suatu masalah P, graf G, serta algoritme A, B, C, muncul juga masalah algorithm dispatch: memilih algoritme mana yang harus dijalankan
  • Pustaka graf yang sempurna harus mendukung banyak jenis graf, tetapi akibatnya waktu untuk mengimplementasikan algoritme yang benar-benar diinginkan pengguna menjadi berkurang
  • Algoritme graf sulit diimplementasikan
    • Algoritme find_shortest_path yang ditulis oleh pencipta Python kemudian direvisi lima kali
    • Nicole mengatakan semua implementasi PageRank yang ia bandingkan keliru
    • NetworkX menyediakan sekitar 500 algoritme graf, dan kode algoritmenya saja hampir 60.000 baris
    • Seluruh pustaka standar Python memiliki sekitar 300 package dan kurang dari 600.000 baris
  • Pengelola pustaka standar harus memutuskan tipe graf apa, penanganan khusus topologi apa, dan algoritme apa yang akan disertakan, sehingga beban pemeliharaannya besar
  • Python pun dikenal sebagai “batteries included”, tetapi melalui PEP 594 sedang bergerak menghapus 20 modul pustaka standar

Representasi graf juga sulit ditetapkan menjadi satu cara

  • Bahkan jika hanya memikirkan directed graph paling sederhana, ada berbagai kemungkinan representasi internal
    • Edge list: [[a, b], [b, c], [c, a], [c, b]]
    • Adjacency list: [[b], [c], [a, b]]
    • Adjacency matrix: [0 1 0; 0 0 1; 1 1 0]
    • Sekumpulan struct yang saling mereferensikan
  • Performa operasi berbeda tergantung cara representasinya
    • Jika graf dengan 100 node dan 200 edge direpresentasikan sebagai adjacency matrix, matriks 100×100 berisi 200 angka 1 dan 9.800 angka 0
    • Jika graf yang sama direpresentasikan sebagai edge list, hanya diperlukan 200 pasangan node
    • Tergantung bahasa dan tingkat optimasi, selisih memori bisa lebih dari 20 kali
  • Sebaliknya, pada graf dengan 100 node dan 8.000 edge, hasilnya berbeda saat mencari edge antara node 0 dan 93
    • Adjacency matrix memungkinkan lookup O(1) dengan graph[0][93]
    • Edge list harus menelusuri 8.000 edge, sehingga membutuhkan waktu O(|edge|)
  • Graf dengan sedikit edge disebut sparse graph, sedangkan graf dengan hampir semua edge disebut dense graph
  • Program yang membangun graf dari data eksternal bisa awalnya berupa sparse graph lalu kemudian menjadi dense graph, sehingga tidak ada “pilihan yang selalu baik” untuk representasi internal
  • Jika mendukung data node, data edge, serta berbagai jenis node dan edge, kompleksitas implementasi makin besar
  • Pustaka pihak ketiga umumnya memilih salah satu dari dua arah
    • Menyediakan satu tipe kaya yang mencakup semua use case, tetapi mengorbankan efisiensi
    • Menyediakan tipe graf terpisah untuk tiap cara representasi, dan menyerahkan pengelolaan data node/edge kepada pengguna

Trade-off yang ditunjukkan NetworkX dan Petgraph

  • NetworkX menyimpan graf sebagai struktur dict dari dict dari dict agar data arbitrer dapat dilekatkan ke node dan edge
  • NetworkX menyediakan fungsi untuk mengonversi ke representasi lain, tetapi tidak menyediakan cara bekerja langsung dengan representasi tersebut
  • Pustaka graf utama di Rust, Petgraph, menyediakan tipe berdasarkan use case seperti graph, graphmap, dan matrix_graph
  • Bradford menggunakan Petgraph dalam tool keamanan Nosey Parker untuk mencari secret di seluruh riwayat repositori git
    • Graf benchmark-nya adalah CPython, berisi 250.000 commit dan 1.300.000 object
    • Karena tiap node commit hanya memiliki beberapa edge, ia memilih adjacency list
  • Mendukung banyak representasi membuat biaya penambahan algoritme meningkat
    • Jika algoritme terpisah ditulis untuk tiap representasi, beban pemeliharaan meningkat 3–4 kali
    • Jika ditulis sebagai abstraksi generik di atas tipe polimorfik, performanya menurun
  • Seorang narasumber memperkirakan algoritme graf yang ia tulis sendiri bisa lebih dari 20 kali lebih cepat daripada algoritme generik

Batasan performa adalah masalah inti pustaka graf

  • Banyak algoritme graf mencakup masalah NP-complete atau yang lebih sulit
    • Dari 21 masalah canonical NP-complete milik Karp, 14 adalah masalah graf
  • Masalah graf dapat dijalankan pada input yang sangat besar, sehingga representasi dan detail implementasi menentukan apakah eksekusi layak dilakukan
  • Dalam Nosey Parker, Bradford harus menelusuri object graph untuk merekonstruksi snapshot filesystem pada tiap commit
    • Empat graph walker milik Petgraph tidak dapat diskalakan untuk use case tersebut
    • Ia merancang graph traversal algorithm yang “semi-novel” secara spontan, dan mengurangi penggunaan memori menjadi 1/1.000
  • Zayenz menyebut 15 puzzle sebagai contoh graf yang terlalu besar untuk ditangani secara keseluruhan
    • Pencarian solusi dilakukan dengan menjalankan A* search pada ruang keadaan
    • Ruang keadaan memiliki lebih dari 20 triliun keadaan
    • Jika semua node dibuat, prosesnya sudah berada dalam kondisi gagal
  • Dalam proyek riset penambahan graf pada solver constraint Gecode yang melibatkan Zayenz, tipe graf umum juga tidak mampu bersaing dengan pilihan representasi yang disesuaikan dengan masalah
  • Graph database juga dirancang untuk menjalankan algoritme graf yang kompleks, tetapi masalah performa tetap ada
    • Menurut Nicole, jika kedalaman tidak dibatasi saat traversal, seluruh graf akan dikunjungi
    • Pencarian kedalaman seperti “keluar 3 langkah dan jika ada jalur, temukan” pun akan mengunjungi banyak data
  • Dalam konsultasi performa kueri graf, Nicole terutama mengerjakan migrasi keluar dari graph database
    • Dalam satu proyek, hanya satu perhitungan yang dibiarkan apa adanya, sementara sisanya ditulis ulang sebagai prosedur MapReduce
    • Memang lebih sulit dipahami, tetapi benar-benar bisa selesai dalam semalam

Mengapa graf jarang ada di pustaka standar

  • Dukungan graf yang luas jarang ditemukan karena beberapa faktor saling bertumpuk
    • Ada banyak jenis graf
    • Tiap jenis graf memiliki banyak cara representasi
    • Ada banyak jenis algoritme graf
    • Performa algoritme sensitif terhadap representasi dan detail implementasi
    • Orang menjalankan algoritme yang sangat mahal pada graf yang sangat besar
  • Pustaka standar bahasa harus menanggung terlalu banyak keputusan desain, trade-off, dan beban pemeliharaan
  • Ada juga alasan mengapa programmer menghindari pustaka graf pihak ketiga
    • Pustakanya bisa terlalu terbatas
    • Pustaka generik mungkin tidak memenuhi kebutuhan performa
  • Graf berguna untuk analisis sistem, tetapi pada tahap implementasi sering kali representasi data dan pilihan algoritme harus dikendalikan langsung

Lampiran: bahasa yang menyediakan tipe graf dan tool terkait

  • Graph query language (GQL) berperan seperti SQL pada graph database
    • Belum ada standar yang digunakan luas, tetapi contoh utamanya adalah SPARQL dan Cypher dari Neo4j
    • GQL di sini tidak boleh disamakan dengan bahasa standar GQL yang sedang dikembangkan
  • GraphQL bukan graph query language; namanya berasal dari kaitannya dengan Facebook Graph Search
  • Perbedaan utama antara GQL dan SQL adalah relasi, yaitu “join”, menjadi entitas kelas satu
    • Dalam dataset film dan orang, SQL mengimplementasikan relasi “pemeran”, “sutradara”, dan “produser” masing-masing sebagai tabel many-to-many
    • Dalam SPARQL, relasi adalah edge, sehingga mudah melakukan query “orang yang memegang peran apa pun dalam film Y, beserta perannya”
  • GQL juga dapat mendukung manipulasi edge seperti pembalikan edge, komposisi, dan transitive closure
    • SPARQL tidak menyediakan panjang jalur atau komputasi di dalam jalur, misalnya mengumpulkan rantai film yang menghubungkan dua aktor
    • GQL yang mendukung hal ini menjadi jauh lebih kompleks
  • Bahasa spesifikasi formal Alloy memiliki primitive traversal graf yang berguna pada tipe data relation, sehingga representasi graf lebih mudah ditangani dibandingkan dalam bahasa pemrograman umum
    • Namun primitive ini berbasis edge berlabel dan mungkin tidak cocok untuk representasi graf lain
  • Python menambahkan graphlib pada 2020
    • Tidak ada method selain TopologicalSorter
    • Graf hanya diterima sebagai dict node
    • Graf a -> b direpresentasikan sebagai dict arah terbalik seperti {b: [a]}
  • Per 2023, graphlib tidak digunakan secara internal di CPython
    • Di GitHub, file yang merujuk graphlib kurang dari 900
    • zoneinfo yang ditambahkan pada tahun yang sama muncul di lebih dari 6.000 file
    • Ekspresi def topological_sort( muncul di 4.000 file
    • Implementasi topological sort yang dibuat sendiri sering memakai representasi graf yang berbeda dari graphlib, sehingga sulit dikonversi
  • Contoh lain bahasa dengan tipe graf di pustaka standar adalah Erlang dan SWI-Prolog
  • Ada juga bahasa pemrograman yang “semuanya adalah graf”
    • Contohnya GP2 dan Grape
    • Saat ini ini masih merupakan ranah yang sangat akademis
  • Bahasa perangkat lunak matematika seperti Mathematica, MATLAB, dan Maple juga memiliki pustaka graf dalam bentuk tertentu
  • Pembaruan 18 Maret 2024: sebagian komentar tentang tulisan ini dikumpulkan di halaman terpisah

Bacaan terkait

1 komentar

 
GN⁺ 2024-03-05
Komentar Hacker News

  • Graphviz memiliki library graf dasar sendiri yang tidak dipakai proyek lain, dan ada kelebihan maupun kekurangannya
    Berdasarkan pengalaman itu, kami juga mengalami sindrom sistem kedua yang klasik. Kami ingin membuat library graf yang modular, aman tipe, dan efisien, tetapi pada akhirnya itu mungkin hanya variasi dari “bagus, cepat, murah — pilih dua saja”
    Modular berarti kami ingin sekumpulan library algoritme graf bisa dikembangkan dan dikompilasi secara independen, sementara aman tipe berarti kami ingin menangkap kesalahan pemrograman seperti “node tidak memiliki properti color” saat kompilasi, atau paling lambat saat linking, alih-alih sebagai error runtime
    Efisien berarti biaya mengakses properti graf harus semurah mengakses field pada struct C, dan kami tidak ingin membawa-bawa tabel hash eksternal atau melakukan banyak konversi string
    Apakah tujuan-tujuan ini masuk akal dan sepadan dengan biayanya bisa diperdebatkan, tetapi itulah yang kami inginkan saat itu. Di lab ada para pencipta C++ terkenal, dan kami juga sempat berpikir untuk memberi C++ kesempatan lagi
    Gordon Woodhull, yang awalnya magang lalu terus bekerja bersama kami, adalah programmer hebat, dan ia menulis implementasi library graf seperti ini dengan template C++. Sourcenya juga tersedia di https://www.dynagraph.org/
    Kami yang lain tidak yakin apakah pada akhirnya kami bisa memahami cara kerja kode itu, jadi kami melakukan code review bersama para penemu C++ terkenal, dan setelah banyak layar kode serta keheningan, kesimpulannya adalah “mungkin akan berfungsi”. Saat itu kami sudah sadar bahwa kami mungkin telah melewati tebing kompleksitas
    Error template pada compile time membuat satu error memenuhi seluruh layar dan menumpahkan detail yang mungkin hanya dicintai oleh penemu C++. Kesalahannya ada pada kami, dan Gordon terus maju hingga membuat layout graf dinamis itu berjalan juga di Microsoft OLE
    Jika dipikir kembali, itu semacam Project Xanadu versi kami sendiri, dan saat kami tersesat di sana, muncullah hal-hal seperti Gephi (Java), NetworkX, dan NetworKit (Python). John Ellson, software engineer brilian yang menulis sebagian Graphviz, menghidupkan kembali pekerjaan arus utamanya

    • Sintaks dot Graphviz bisa diparse dengan NetworkX untuk menyusun rencana eksekusi tool yang mahal, dan berkat struktur grafnya dapat diparalelkan secara otomatis

  • Sebagai orang yang sudah banyak mengerjakan graf, saya sudah tak terhitung menerima pertanyaan “mengapa bahasa pemrograman tidak punya tipe data graf bawaan?”
    Sekarang saya senang karena tidak perlu hanya meminta orang percaya ketika saya berkata “membuatnya dengan baik itu benar-benar sulit”, melainkan bisa menunjuk ke analisis yang lebih mendalam seperti artikel ini

    • Hal yang agak lucu dari pertanyaan itu adalah mereka biasanya melewatkan fakta bahwa sebagian besar bahasa bahkan tidak punya struktur data tree
      Yang disediakan sebagian besar bahasa sebagai tipe struktural hanyalah array statis, array dinamis, dan linked list. Hal seperti binary search tree atau hash table adalah abstraksi semantik yang menyembunyikan sebagian kemampuan struktur dasarnya, bukan representasi struktural murni
    • Graf adalah struktur data yang luas, yang cara representasinya sangat berubah tergantung kebutuhan, jadi saya dulu berpikir lebih masuk akal untuk mengimplementasikannya di level domain
      Bagian artikel tentang “terlalu banyak pilihan implementasi” juga mengatakan hal yang sama. Lalu saya melihat Petgraph [0] dan untuk pertama kalinya meninjau library graf serbaguna dengan serius; itu cukup menarik, tetapi saya tetap mengimplementasikan graf di level domain
      [0] https://github.com/petgraph/petgraph
    • Saya juga pernah mengalami kebalikannya. Saat pertama kali mengerjakan graf di Tcl, saya tentu saja mengira tidak akan ada algoritme graf di standard library, tetapi ternyata ada, dan berkat itu saya tidak perlu menciptakan ulang roda
      https://core.tcl-lang.org/tcllib/doc/trunk/embedded/md/tclli...
    • Yang lebih penting daripada “membuatnya dengan baik itu benar-benar sulit” adalah banyaknya trade-off
      Hampir semua bahasa menyediakan hash map, dan walaupun dalam situasi tertentu implementasi sendiri bisa dibuat lebih cepat, implementasi default umumnya bekerja dengan baik. Untuk graf, hal seperti itu sulit dilakukan, dan jika memungkinkan mungkin perlu menyediakan beberapa tipe graf
      Sebagai tambahan, HashMap di Java agak unik karena, berbeda dari kebanyakan bahasa lain, load factor-nya bisa disesuaikan
    • Mungkin ini pemikiran yang sangat naif, tetapi saya melihat pointer pada dasarnya sebagai tipe graf native
      Yang diinginkan orang sebenarnya bukan tipe graf itu sendiri, melainkan lebih dekat ke alat untuk menelusuri graf

  • Saya menganggap graf lebih sebagai abstraksi daripada struktur data atau tipe data
    Pada dasarnya, yang diperlukan untuk mendefinisikan graf hanyalah himpunan vertex v \in V dan fungsi Neighbors(v), dan untuk sebagian besar algoritme graf dasar, itu benar-benar sudah cukup
    Sisanya adalah batasan per kasus. Apakah A->B berarti B->A, apakah himpunan node dapat dipartisi di bawah batasan tertentu, apakah ada warna atau label, dan sebagainya
    Jika digeneralisasi lebih jauh, kita bisa sampai ke hypergraph, dan dalam hal ini yang diperlukan hanyalah himpunan vertex dan himpunan dari himpunan vertex. Bergantung pada kepentingannya, ini bisa direpresentasikan dengan banyak cara, dan graf biasa hanyalah kasus khususnya
    Dari sudut pandang database, ini juga bisa dilihat sebagai masalah optimisasi query dan indexing. Cara representasi yang bisa menjawab lebih baik bergantung pada pertanyaan apa yang ingin diajukan ke graf. Sama seperti abstraksi “tabel” tidak hanya punya satu cara representasi, “graf” juga tidak selesai dengan satu cara saja

    • Alasan graf ada di mana-mana adalah karena ia begitu abstrak
      Ia berada pada level abstraksi yang sama seperti bilangan murni. Kita bisa mengatakan ada library “numerik” yang berguna sebagaimana ada library “grafis/graf” yang berguna, tetapi hampir tidak ada library “bilangan” atau library “graf”. Konsep seperti itu terlalu abstrak untuk dijadikan API
    • Himpunan vertex dan Neighbors(v) saja sudah cukup membatasi. Karena itu tidak mengizinkan multi-edge menuju tetangga yang sama
    • Jika hypergraph adalah himpunan vertex dan himpunan dari himpunan vertex, kedengarannya agak mirip dengan file system
      File adalah vertex, dan direktori adalah himpunan vertex yang dapat bersarang

  • Ada dua hambatan utama
    Untuk masalah graf yang sederhana dan kecil, cukup mudah membuat sendiri adjacency list dengan vektor berisi vektor; sedangkan untuk masalah graf yang kompleks dan sangat besar, performa baru muncul jika implementasi graf dibuat khusus sesuai detail masalah yang ingin diselesaikan
    Karena itu tidak jelas dukungan bahasa seperti apa yang akan membantu. Sulit, kecuali ada compiler supercerdas yang menganalisis kode lalu menentukan mana yang optimal: adjacency list, matriks, array 3 dimensi, dan sebagainya. Optimisasi seperti itu tampaknya masih sulit ditemukan di compiler untuk sementara waktu
    Ini contoh lain dari fenomena yang dilihat Stroustrup. Kita cukup baik dalam berbagi kode untuk hal kecil seperti vektor dan hal besar seperti sistem operasi, tetapi tidak pandai berbagi untuk masalah berukuran menengah

    • Bahkan untuk hal kecil pun sulit dibilang benar-benar dibagikan dengan baik, karena tiap bahasa pemrograman punya implementasi vektornya sendiri
      Dalam satu ekosistem bahasa, API vektor kecil, sehingga tampaknya mudah dibagikan. Sistem operasi punya API yang relatif kecil dibanding kompleksitas internalnya, begitu juga pustaka komputasi numerik, sehingga keduanya mudah dibagikan
      Sebaliknya, makin sesuatu ingin dikustomisasi—seperti struktur data yang kompleks—API-nya makin rumit dan makin sulit dibagikan. Pada akhirnya, kemungkinan untuk berbagi tampaknya bergantung pada luas permukaan dari sesuatu yang dibagikan, yaitu ukuran relatif API-nya
    • Melihat algoritma yang ditulis untuk tipe graf abstrak, lalu mengisi implementasinya agar sesuai dengan algoritma tertentu dan mengoptimalkannya, tampaknya cukup cocok untuk ranah LLM spesialisasi kode

  • Electric Clojure memakai s-expression Clojure sendiri sebagai sintaks penulisan graf, dan dengan makro mewujudkan aliran data sistem klien/server reaktif
    Di sini kasus pemakaiannya adalah antarmuka pengguna full-stack, tetapi idenya bisa digeneralisasi. https://github.com/hyperfiddle/electric Saya pendirinya
    Menurut saya, jawaban atas “ke mana perginya semua tipe graf?” adalah bahwa DSL untuk menulis graf harus mengekspresikan scope, control flow, dan abstraksi; jika demikian, pada dasarnya ia menjadi isomorfik dengan bahasa pemrograman yang dibebaskan dari model evaluasi. Di Python dan TypeScript, menyisipkan bahasa pemrograman penuh cukup sulit
    Tulisan blog “Four problems preventing visual flowchart programming from expressing web applications” juga layak dirujuk
    https://www.dustingetz.com/#/page/four%20problems%20preventi...

  • Tulisan ini terutama menjawab “mengapa bahasa pemrograman tidak mendukung algoritma graf dengan lebih baik”, dan tampaknya lebih berfokus pada pemrosesan graf “big data” daripada dukungan graf secara umum
    Jika melihat dukungan graf secara keseluruhan, ada juga pertanyaan yang lebih luas seperti “mengapa OGM (Object Graph Mapper) tidak sepopuler ORM” dan “mengapa JSON dipakai luas, sedangkan RDF atau serialisasi graf tingkat rendah lain tidak”
    Pada akhirnya saya pikir alasan historis berperan besar. RDF muncul sedikit terlalu awal, tidak berevolusi dengan baik, dan malah membangun ekosistem standar akademis serta implementasi yang buruk. Selain itu, graf pada dasarnya sedikit lebih kompleks dalam implementasi dan kurva belajar, sehingga tidak mudah diskalakan ke banyak developer
    Saya tidak akan memberi terlalu banyak bobot pada bagian “Graph Querying Language” dalam tulisan itu. Ada bagian yang terbaca seperti copy marketing yang ditulis oleh pengguna fanatik Neo4J atau SPARQL tanpa benar-benar pernah membangun produk
    Dikatakan bahwa “perbedaan utama semua GQL dan SQL adalah join, yaitu relasi merupakan entitas kelas satu”, tetapi di SQL pun join adalah entitas kelas satu. Bahkan ada keyword JOIN
    Jika turun ke lapisan yang lebih rendah dari bahasa kueri graf dan melihat query planning, tidak banyak perbedaan bermakna dengan kueri berbasis SQL. Fakta bahwa standardisasi GQL[0] berjalan sebagai ekstensi SQL menjadi buktinya
    SPARQL memang mudah saat perlu traversal jalur yang tepat, tetapi begitu mencoba melakukan hal yang sedikit lebih kompleks seperti yang lazim di backend webapp, kita cepat menabrak jebakan seperti join dengan nilai yang tidak terikat, yang tanpa sengaja bisa menghapus seluruh result set
    [0]: https://en.wikipedia.org/wiki/Graph_Query_Language

    • Justru adanya keyword tersendiri lebih mendekati bukti kuat bahwa sesuatu bukan objek kelas satu
      Misalnya, type class di Haskell bukan kelas satu, dan di sebagian besar bahasa pemrograman, control flow juga bukan kelas satu
    • JOIN, khususnya join pada kueri RECURSIVE, adalah inti dari database graf, sehingga database relasional SQL pada umumnya juga menanganinya dengan baik
      Hanya saja tidak ada jalan pintas sintaksis, dan bahasa kueri graf pada dasarnya berfokus menambahkan jalan pintas itu

  • Alat untuk menggambar grafik juga cukup mengecewakan. Pada grafik kecil, alat ini bekerja dengan baik, tetapi begitu jumlah node melewati sekitar 500, output-nya menjadi sama sekali tidak dapat dipahami atau sangat sulit dilihat
    Kemampuannya kurang untuk menata grafik secara otomatis ke dalam struktur hierarkis dan menyediakan antarmuka yang enak untuk dijelajahi. Mengingat kita terbiasa melihat hampir semua hal di sekitar kita sebagai struktur hierarkis sampai taraf tertentu, tampaknya jenis masalah yang sama juga perlu dipecahkan saat membuat tipe data grafik serbaguna
    Hal seperti ini mungkin perlu diimplementasikan di tingkat compiler, sehingga algoritma grafik serbaguna harus beradaptasi dengan hierarki struktur yang dihasilkan. Jika ditambah theorem prover untuk memastikan bahwa subgraf tertentu selalu memiliki struktur tertentu, prosedur untuk bagian itu bisa dibuat secara statis, sementara untuk sisa grafik tingkat atas bisa dibuat secara dinamis saat runtime
    Karena itu, siapa pun yang memecahkan masalah penggambaran grafik serbaguna kemungkinan juga akan memiliki kemampuan atau wawasan untuk mengimplementasikan hal ini

    • Menggambar grafik itu sulit
      Ini adalah library penggambaran grafik serbaguna sejenis Graphviz, dengan lebih banyak opsi dan kontrol
      https://eclipse.dev/elk/
      Eksperimen yang dilakukan tim pengembang ELK di Kiel University
      https://github.com/kieler/KLighD
      Wiki proyek Kieler
      https://rtsys.informatik.uni-kiel.de/confluence/display/KIEL...
      Library penggambaran grafik berbasis constraint
      https://www.adaptagrams.org/
      Implementasi JavaScript
      https://ialab.it.monash.edu/webcola/
      Materi menarik: HOLA: Human-like Orthogonal Network Layout
      https://ialab.it.monash.edu/~dwyer/papers/hola2015.pdf
      Demo Confluent Graphs membuat edge lebih mudah dibaca
      https://www.aviz.fr/~bbach/confluentgraphs/
      Stress-Minimizing Orthogonal Layout of Data Flow Diagrams with Ports
      https://arxiv.org/pdf/1408.4626.pdf
      Improved Optimal and Approximate Power Graph Compression for Clearer Visualisation of Dense Graphs
      https://arxiv.org/pdf/1311.6996v1.pdf
    • Beberapa algoritma menangani masalah ini dengan lebih baik, tetapi dalam kasus umum, “buatlah diagram yang bagus dari sebuah grafik” nyaris merupakan masalah AI-complete
      Bahkan untuk grafik yang secara struktur sama, dua orang bisa merendernya dengan cara yang sama sekali berbeda karena ingin menonjolkan aspek data yang berbeda. Ini juga mirip dengan masalah “algoritma grafik serbaguna” dan “struktur data grafik serbaguna”
      Grafik berada di perbatasan antara kode dan data. Misalnya, program apa pun memiliki call graph, jadi dalam arti tertentu “algoritma grafik serbaguna” adalah komputasi itu sendiri
    • Hal-hal ideal biasanya tampak seperti tree, tetapi struktur dunia nyata, meski tertata rapi, biasanya berupa directed acyclic graph
      Begitu jumlah node melewati beberapa puluh saja, biasanya sulit membuatnya planar, atau membuatnya tampak hampir planar dengan sedikit crossing dan pengelompokan node terkait yang baik
    • Menurut saya masalah yang lebih besar adalah kita terbiasa dengan ilusi bahwa segala sesuatu bersifat hierarkis
      Pada kenyataannya, graph drawing harus mendamaikan hal-hal yang hampir tidak hierarkis, dan sulit menarik garis yang ketat secara matematis tentang sejauh mana sesuatu bisa dianggap sebagai hierarki. Semakin sedikit asumsi tentang struktur grafik underlying—seperti konektivitas, ada/tidaknya siklus, atau sparsity—semakin buruk masalah ini
      Dalam praktiknya, saat membuat UI yang berinteraksi dengan grafik, biasanya kita bisa menetapkan atau memaksakan satu-dua tingkat meta-hierarki untuk melakukan clustering. Dengan begitu, dampak node hairball yang merusak layout dapat dikurangi, jumlah node juga berkurang, sehingga performa rendering membaik. Untuk layout, fCOSE bisa digunakan, dan ada juga implementasi Cytoscape.js
    • Gambar neural network menunjukkan dengan jelas betapa visualisasi grafik skala besar bisa menjadi sepenuhnya sulit dipahami

  • Saya rasa pengamatan inti bahwa “ada terlalu banyak pilihan implementasi” tidak sepenuhnya tepat
    Pada praktiknya, sebuah library bisa mengimplementasikan semua representasi graf yang sesuai, menyediakan algoritme dengan performa terbaik untuk tiap representasi, serta menyediakan konversi antarrepresentasi. Konversi ini sebanding dengan jumlah representasi, dan baik implementasi maupun penggunaannya sederhana, sehingga menjadi beban yang cukup masuk akal bagi pemelihara maupun pengguna
    Sebagai bonus, library juga bisa menyediakan konversi impor/ekspor dari tipe data dan idiom standard library. Biaya memori dan konversi itu murah, dan untuk 99% use case kemungkinan besar overhead konversi data dapat diabaikan, baik dari sisi RAM maupun CPU
    Saya juga teringat ungkapan, “kebenaran pahit bekerja di Google adalah pada akhirnya Anda hanya memindahkan protobuf dari satu tempat ke tempat lain”
    https://news.ycombinator.com/item?id=20132880

    • Kalau begitu, sepertinya akan menjadi library yang sangat besar, dan saya tidak yakin akan memakainya dalam pekerjaan saya. Saya banyak memakai graf, tetapi pengalaman saya mirip dengan orang-orang yang diwawancarai penulis
      Pada akhirnya kami selalu mengimplementasikan ulang graf. Performa penting, dan library graf siap pakai yang pernah saya lihat tidak bisa memanfaatkan keteraturan dataset kami. Misalnya, kami memakai DAG append-only, di mana hampir semua node hanya punya satu edge yang menunjuk ke item yang terakhir ditambahkan, sehingga secara internal bisa memakai run-length encoding
      Saya juga belum pernah melihat library graf umum yang mendukung query yang kami perlukan. Yang terutama besar adalah fungsi diff subgraf
      Selain itu, implementasi khusus tidak terlalu banyak pekerjaannya. Graf jauh lebih mudah diimplementasikan ulang daripada B-tree, dan implementasi sederhana bisa dibuat dalam beberapa puluh baris. Bahkan library kami yang sangat dioptimalkan, termasuk algoritme yang didukungnya, hanya sekitar beberapa ratus baris
      Akan praktis jika ada cara mengekspor data ke format standar, tetapi untuk use case kami, menarik sebuah library tampaknya akan menambah lebih banyak masalah daripada menyelesaikannya

  • Aplikasi yang sering saya bayangkan hilang adalah Excel untuk graf
    Seperti Excel untuk data tabular, alat ini menangani data berukuran cukup untuk masuk ke RAM—skala yang membutuhkan komputer tetapi belum sampai membutuhkan datacenter—mengimplementasikan banyak algoritme dan visualisasi dengan “cukup baik”, serta bisa digunakan tanpa pengetahuan pemrograman
    Seperti yang dikatakan tulisan itu, banyak masalah nyata adalah masalah graf, jadi mengapa hanya programmer yang harus punya alat untuk menyelesaikannya

    • Rasanya tulisan itu terlalu cepat mengambil kesimpulan. Banyak masalah lain pun bisa dibuat serumit dan sesulit apa pun jika kita menambahkan requirement
      Namun tetap ada struktur data dan standard library yang cukup cocok untuk sebagian besar use case, dan jika ada kebutuhan yang sangat tajam, kita bisa membuat solusi khusus
      Tulisan itu mengatakan graf sering kali terlalu besar, tetapi jika bertanya kepada orang yang memang bekerja dengan algoritme graf, wajar kalau mereka sering mengalami hal itu. Sebagian besar programmer dan pengguna mungkin hanya menangani graf yang benar-benar kecil
    • Saya rasa hanya programmer dan matematikawan yang memodelkan masalah seperti ini sebagai graf
      Saya tidak berpikir pengguna umum melihat graf dalam masalah dunia nyata yang acak. Hal yang saya pelajari saat bekerja di perusahaan besar adalah, jika berusaha cukup keras, segala sesuatu bisa menjadi spreadsheet Excel
    • Ini tidak persis seperti yang diminta, tetapi https://gephi.org/ mengimplementasikan banyak algoritme visualisasi graf
      https://strlen.com/treesheets/ lebih dekat ke Excel untuk data tree
    • Tulisan itu tidak benar-benar mendukung poin bahwa “banyak masalah dunia nyata adalah masalah graf”
      Misalnya dikatakan internet bisa dimodelkan sebagai graf, dan meskipun itu benar, tidak jelas lalu apa artinya. Internet bisa direpresentasikan dengan banyak cara, dan tidak jelas bahwa merepresentasikannya sebagai graf secara umum memiliki implikasi rekayasa yang berguna
      Representasi ideal untuk memperoleh informasi berguna bisa sama meyakinkannya jika disebut fungsi encoding matriks black-box yang memetakan input arbitrer ke output konsisten, yaitu jaringan saraf
      Bagi tempat seperti Google, itu mungkin ide bernilai miliaran dolar, tetapi seluruh internet bukanlah masalah graf bagi banyak orang, dan merepresentasikannya sebagai graf tidak menyelesaikan banyak hal
      Jarang ada orang yang menyelesaikan masalah nyata di atas kertas dengan graf. Tabel selalu dipakai. Graf memang umum, tetapi masalah graf tidak umum
    • Menurut saya kuncinya di sini adalah VR
      Komentar lain juga mengatakan visualisasi graf itu sulit, tetapi antarmuka 3D memberi ruang yang jauh lebih besar. Ketika gelombang VR mulai, saya berpikir “apa Excel-nya VR?” dan jawaban Microsoft adalah “spreadsheet 2D yang melayang di ruang 3D”. Menurut saya itu tidak masuk akal. Saya pikir jawabannya adalah graf
      Jika ada yang ingin mengeksplorasi bersama, silakan kirim email ke nama pengguna saya at gmail.com

  • Tipe graf sudah ada sejak cukup lama
    Erlang memiliki https://www.erlang.org/doc/man/digraph.html dan https://www.erlang.org/doc/man/digraph_utils, dan jika ingin melakukan operasi berbasis teori himpunan, ada juga https://www.erlang.org/doc/man/sofs.html

    • Erlang dibahas singkat di bagian akhir tulisan
      Isinya kira-kira: “Saya menemukan dua bahasa lain yang memiliki tipe graf, yaitu Erlang dan SWI-Prolog. Karena saya tidak begitu mengenal keduanya, saya tidak bisa mengatakan kapan itu ditambahkan, tetapi Erlang setidaknya sudah memilikinya sebelum 2008. Saya menghubungi seseorang di komite bahasa inti Erlang, tetapi tidak mendapat jawaban”
    • Elixir juga punya library graf yang cukup bagus: https://hexdocs.pm/libgraph/api-reference.html
      Saya pernah menggunakannya untuk dependency resolution dalam menentukan urutan pekerjaan
    • Saya penasaran seberapa fleksibel dan baik performanya dalam berbagai situasi