Kaybolan veri tipinin izini sürmek

Eksik veri türünü ararken

• Grafikler, oklarla (kenarlar) birbirine bağlanan düğüm kümeleridir.
• Düğümler ve kenarlar veri içerebilir.
• Yazılım mühendisliğinde grafikler; paket bağımlılıkları, internet bağlantıları, yazılımın durum uzayı, ilişkisel veritabanları, bağlantılı listeler, ikili ağaçlar, hash tabloları gibi birçok biçimde karşımıza çıkar.
• İş mantığında da grafikler; alıntı referansları, ulaşım ağları, sosyal ağlar gibi alanlarda kullanılır.
• Yazılım geliştirme ile uzun süre uğraşırsanız, grafiklerle hemen her yerde karşılaşmanız muhtemeldir.

Grafik kullanımı üzerine düşünceler

• Grafikler faydalıdır, ancak gerçek kodda grafik kullanmak külfetli gelebilir.
• Çoğu ana akım dilde grafikler yerleşik tür olarak desteklenmez; standart kütüphanelerde de nadirdir ve sağlam üçüncü taraf kütüphaneler de çok yaygın değildir.
• Bu yüzden grafikleri çoğu zaman kendiniz uygulamanız gerekir.
• Yazılım mühendislerinin grafikleri kullanma sıklığı ile programlama ekosistemindeki destek arasında bir boşluk vardır.

Neden bir grafik tipi yok?

Tasarım seçeneği çok fazla

• Yönlü ve yönsüz grafikler, basit grafikler ve çoklu grafikler, hipergrafikler, ubergraph'lar gibi birçok grafik türü vardır.
• Her tür için düğümlere ve kenarlara kimlik verilip verilmeyeceği, hangi verilerin saklanacağı gibi kararlar gerekir.
• Tüm olasılıkları destekleyen kusursuz bir grafik kütüphanesi geliştirmek çok zaman ister.
• Grafik algoritmalarında performans önemlidir ve özel durumlar büyük fark yaratır.
• Grafik algoritmalarını doğru biçimde uygulamak zordur.

Uygulama seçeneği çok fazla

• Yalnızca basit yönlü grafikleri desteklediğinizi varsaysanız bile, bir grafiği dahili olarak temsil etmenin birçok yolu vardır.
• Kenar listesi, komşuluk listesi, komşuluk matrisi, struct kümeleri gibi çeşitli saklama biçimleri bulunur.
• Farklı grafik işlemleri, farklı gösterimlerde farklı performans özellikleri gösterir.
• Grafiğin seyrek ya da yoğun olmasına göre en uygun dahili temsil değişir.
• Düğüm verisi, kenar verisi ve farklı düğüm ile kenar türlerini uygulamak işi daha da karmaşıklaştırır.

Performans fazlasıyla önemli

• Birçok grafik algoritması NP-tamdır ya da daha da zordur.
• Grafikler çok büyük problemlere dönüşebilir; temsil biçimi ve algoritma uygulamasının ayrıntıları performansı ciddi biçimde etkiler.
• Veri gösterimi ve algoritmalar üzerinde yüksek düzeyde denetim gerekir.

Ortaya çıkan ortak görüş

• Grafik türlerinin, gösterimlerin ve algoritmaların çeşitliliği; performansa duyarlılık; büyük grafiklerde pahalı algoritmalar çalıştırma ihtiyacı gibi etkenler, grafik desteğinin yaygınlaşmamasının nedenleridir.
• Bu durum, dillerin neden standart kütüphanelerinde grafik desteği sunmadığını açıklar.
• Ayrıca programcıların neden üçüncü taraf grafik kütüphanelerinden kaçındığını da açıklar.
• Grafiklerle çalışmak zor olduğu için, aşırı gerekli olmadıkça insanların problemleri grafik olarak düşünmek istememesini de açıklar.

GN⁺ görüşü

• Bu yazı, grafiklerin neden programlama dilleri ve kütüphanelerinde temel bir veri türü hâline gelmediğine dair içgörü sunuyor.
• Grafik teorisi, bilgisayar biliminin önemli bir alanıdır ve algoritmalar, ağ analizi, veritabanları gibi birçok alanda uygulanır.
• Grafikleri etkili kullanmak için performans optimizasyonu ve uygun veri yapısı seçimi önemlidir.
• Üçüncü taraf kütüphaneler arasında NetworkX, Boost Graph Library ve Graph-tool yer alır; bunlar çeşitli grafik problemlerini çözmek için kullanılabilir.
• Grafik kullanırken, problemin niteliğine uygun grafik türünü ve algoritmayı seçmek kritik önemdedir; bu seçim sistem performansını doğrudan etkiler.

[GN⁺]

Hacker News görüşü

• Graphviz'in kendine özgü bir grafik kütüphanesi var ve bu başka projelerde kullanılmıyor. Bunun artıları ve eksileri var.

  • Bu deneyime dayanarak, kendi "ikinci sistem sendromu"larını yaşadılar.
  • Grafik kütüphanesinin modüler, tip güvenli ve verimli olması gerektiğine karar verdiler. Bu, "iyi, hızlı, ucuz - ikisini seç" sözünün bir varyasyonu olabilir.
  • Modülerden kastettikleri, bağımsız olarak geliştirilen ve derlenen bir grafik algoritmaları kütüphaneleri koleksiyonu yazmak istemeleriydi.
  • Tip güvenliden kastettikleri, programlama hatalarını derleme zamanında ya da en geç bağlama aşamasında tespit etmek istemeleriydi. Çalışma zamanı hataları istemiyorlardı.
  • Verimlilikten kastettikleri, grafiğin özelliklerine erişimin bir C struct alanına erişmek kadar ucuz olması gerektiğiydi.
  • Bu hedeflerin buna değip değmediği tartışmalı olabilir, ama istedikleri şey buydu. Ünlü C++ kurucuları laboratuvarlarındaydı, bu yüzden yardım alabileceklerini düşündüler ve C++'a bir kez daha şans vermeye karar verdiler.
  • Eski stajyer Gordon Woodhull, bu tür bir grafik kütüphanesini template C++ ile hayata geçiren olağanüstü bir programcıydı. Bu çalışma sourceforge üzerinden https://www.dynagraph.org/ adresinde yayımlandı.
  • Başkalarının kodun nasıl çalıştığını anlayıp anlayamayacağından emin olmadıkları için, ünlü C++ mucitleriyle kod incelemesi yaptılar. Karmaşıklık uçurumunun ötesine geçmiş olabileceklerini fark ettiler.
  • Bu Gordon'un hatası değildi; o çalışmalarını sürdürdü ve Microsoft OLE içinde dinamik grafik yerleşimi üzerine de başarılı işler yaptı. Geriye dönüp bakınca, bu kendi Project Xanadu'ları olmuş olabilir.
  • Onlar buna gömülmüşken, Gephi (Java) ile NetworkX ve NetworKit (Python) gibi pek çok şey ortaya çıktı.
  • Graphviz'in bazı bölümlerini yazan John Ellson, başlıca çabayı yeniden canlandıran son derece yetenekli bir yazılım mühendisidir.

• .NET'te kod yazıyorsanız, küçük ama özellik açısından zengin olmayan grafik kütüphanesi Arborescence'ı denemenizi öneririm.

  • Bu kütüphanenin soyutlamalar, algoritmalar ve veri yapıları arasında iyi bir ayrım sunduğuna inanıyorum.
  • Kullanıcılar kendi ID'lerine sahip edge'leri kullanabilir ya da anında genişleyen örtük grafikler kullanabilir.
  • Hem komşuluk (dışa giden komşular) hem de insidans (dışa giden edge + head) arayüzleri kullanılabilir.
  • Kütüphane bir edge tipi dayatmaz, ancak yardımcı araç olarak temel bir tail-head çift yapısı sağlar.

• Grafikler veri yapıları ya da veri tipleri değil, birer soyutlamadır.

  • Temelde bir grafiği tanımlamak için gereken tek şey bir tepe noktaları kümesi ve bir komşuluk fonksiyonudur.
  • Diğer her şey duruma özel kısıtlamalardır.
  • Hipergraph'lar dikkate alındığında, grafikler yalnızca özel bir durumdur.
  • Veritabanı perspektifinden bakarsanız, grafik bir sorgu optimizasyonu ve indeksleme problemidir.

• Programlama dillerinde yerleşik bir grafik veri tipi neden olmadığına dair çok soru aldım.

  • Artık insanları bunun gibi daha derin analizlere yönlendirebiliyor olmaktan memnunum.

• Merkezi engel şu:

  • Basit ve küçük grafik problemlerinde, vector of vectors komşuluk listesi kodlamak yeterince kolaydır.
  • Karmaşık ve devasa grafik problemlerinde, performans elde etmenin tek yolu probleme uygun bir grafik gerçekleştirimini özelleştirmektir.
  • Ne tür bir dil desteğinin yardımcı olacağı net değil.

• Bu yazı, programlama dillerinde grafik _algoritmaları_nın neden daha iyi desteklenmediği sorusunu büyük ölçüde yanıtlıyor.

  • Grafik desteğine genel olarak bakınca, OGM'nin neden ORM kadar popüler olmadığı, JSON'ın neden RDF'den daha yaygın kullanıldığı gibi daha geniş sorular da görülüyor.
  • Sonuçta, tarihsel nedenler ve grafiklerin karmaşıklığı yüzünden geliştiriciler arasında iyi ölçeklenmiyor.

• Grafik çizim araçları da çok hayal kırıklığı yaratıyor.

  • 500'den fazla düğüm içeren grafiklerde çıktı anlaşılması zor ya da aşırı karmaşık oluyor.
  • Grafikleri hiyerarşik yapılara otomatik olarak düzenleyen ve keşif için iyi bir arayüz sunan özellikler eksik.

• Bu yazı gerçekten harika.

  • "Uygulama seçeneği çok fazla" şeklindeki temel gözleme gelince, aslında öyle değil.
  • Gerçekte bir kütüphane, uygun olan tüm grafik gösterimlerini uygulayabilir.
  • Algoritmalar gösterime göre özelleştirilebilir ve bir gösterimden diğerine dönüştürülebilir.

• Electric Clojure, grafik yazım sözdizimi olarak Clojure'un kendisini (s-ifadeleri) kullanıyor.

  • Grafik yazımı DSL'i kapsam, kontrol akışı ve soyutlamayı ifade etmek zorundadır; bu da özünde bir programlama diliyle aynıdır.

• Tablolar gibi (veritabanındaki tablolar gibi) başka faydalı bir veri tipi daha var.

  • Derleyicinin veri yapısı gerçekleştirimini seçmesine izin vermek, programlama dillerinde ilerleme sağlayabilir.
  • Soyut yapılar (sequence, map, set, table, graph vb.) kullanılır ve program profilini temel alarak somut gerçekleştirimleri derleyici seçer.