गायब डेटा टाइप की तलाश

छूटा हुआ डेटा टाइप खोजते हुए

• ग्राफ नोड्स के एक समूह से बना होता है, जो तीरों (edges) से जुड़े होते हैं.
• नोड्स और edges में डेटा शामिल किया जा सकता है.
• सॉफ़्टवेयर इंजीनियरिंग में ग्राफ कई रूपों में मौजूद होते हैं, जैसे package dependencies, internet links, software state space, relational databases, linked lists, binary trees, hash tables आदि.
• बिज़नेस लॉजिक में भी ग्राफ का उपयोग citation references, traffic networks, social networks आदि के रूप में होता है.
• अगर आप लंबे समय तक software development करते हैं, तो लगभग हर जगह ग्राफ से सामना होने की संभावना रहती है.

ग्राफ के उपयोग को लेकर दुविधा

• ग्राफ उपयोगी हैं, लेकिन वास्तविक कोड में ग्राफ का उपयोग करना बोझिल लग सकता है.
• ज़्यादातर मुख्यधारा की भाषाएँ ग्राफ को built-in type के रूप में support नहीं करतीं, standard library में भी यह कम मिलता है, और मज़बूत third-party libraries भी बहुत अधिक नहीं हैं.
• कई बार ग्राफ को सीधे खुद implement करना पड़ता है.
• सॉफ़्टवेयर इंजीनियर जिस आवृत्ति से ग्राफ का उपयोग कर सकते हैं और programming ecosystem में उपलब्ध support के बीच एक अंतर मौजूद है.

ग्राफ टाइप क्यों नहीं है

डिज़ाइन विकल्प बहुत ज़्यादा हैं

• directed graph और undirected graph, simple graph और multigraph, hypergraph, ubergraph जैसे कई प्रकार के ग्राफ मौजूद हैं.
• हर प्रकार के लिए यह तय करना पड़ता है कि नोड्स और edges को ID दी जाए या नहीं, और उनमें किस तरह का डेटा रखा जाए.
• सभी संभावनाओं को support करने वाली एक परिपूर्ण graph library बनाने में बहुत समय लगता है.
• graph algorithms का performance महत्वपूर्ण होता है, और विशेष case भी मायने रखते हैं.
• graph algorithms को सही ढंग से implement करना कठिन है.

implementation के विकल्प बहुत ज़्यादा हैं

• मान लें कि केवल एक साधारण directed graph को support करना है, तब भी ग्राफ को अंदरूनी रूप से represent करने के कई तरीके हैं.
• edge list, adjacency list, adjacency matrix, structs के collection जैसी कई storage विधियाँ मौजूद हैं.
• अलग-अलग graph operations की performance विशेषताएँ अलग-अलग representation में अलग होती हैं.
• ग्राफ sparse है या dense, इसके अनुसार सबसे उपयुक्त internal graph representation बदल जाता है.
• node data, edge data, और अलग-अलग प्रकार के nodes तथा edges को implement करना इसे और जटिल बनाता है.

performance बहुत महत्वपूर्ण है

• कई graph algorithms NP-complete समस्याएँ हैं, या उनसे भी कठिन हैं.
• ग्राफ बहुत बड़े problem बन सकते हैं, और representation तथा algorithm implementation की बारीकियों के अनुसार performance में बड़ा अंतर आ सकता है.
• data representation और algorithms पर काफी नियंत्रण की आवश्यकता होती है.

सहमति का निष्कर्ष

• ग्राफ के कई प्रकार, representation, algorithms, performance sensitivity, और बड़े ग्राफ पर महंगे algorithms चलाने जैसी बातें इस बात का कारण हैं कि graph support व्यापक नहीं हो पाया है.
• इससे यह समझ आता है कि भाषाएँ standard library में graph support क्यों नहीं देतीं.
• इससे यह भी समझ आता है कि programmer third-party graph libraries से क्यों बचते हैं.
• ग्राफ का उपयोग कठिन होने के कारण, बहुत चरम स्थिति न हो तो लोग समस्याओं को graph के रूप में सोचना भी नहीं चाहते.

GN⁺ की राय

• यह लेख इस बात पर उपयोगी अंतर्दृष्टि देता है कि programming languages और libraries में ग्राफ एक बुनियादी data type के रूप में क्यों स्थापित नहीं हो पाया.
• graph theory कंप्यूटर साइंस का एक महत्वपूर्ण क्षेत्र है, और इसका उपयोग algorithms, network analysis, databases जैसे कई क्षेत्रों में होता है.
• ग्राफ का प्रभावी उपयोग करने के लिए performance optimization और उचित data structure का चयन महत्वपूर्ण है.
• third-party libraries में NetworkX, Boost Graph Library, Graph-tool आदि शामिल हैं, जिनका उपयोग विभिन्न graph समस्याओं को हल करने में किया जा सकता है.
• ग्राफ का उपयोग करते समय समस्या की प्रकृति के अनुसार सही graph type और algorithm चुनना महत्वपूर्ण है, क्योंकि इसका सीधा संबंध system performance से होता है.

[GN⁺]

Hacker News राय

• Graphviz की अपनी ग्राफ लाइब्रेरी है, जिसका इस्तेमाल दूसरे प्रोजेक्ट्स में नहीं होता। इस लाइब्रेरी के अपने फायदे और नुकसान हैं।

  • इस अनुभव के आधार पर, उन्होंने अपना ही 'second-system syndrome' झेला।
  • उन्होंने तय किया कि ग्राफ लाइब्रेरी modular, type-safe, और efficient होनी चाहिए। यह शायद "अच्छा, तेज़, सस्ता — इनमें से दो चुनो" कहावत का एक रूपांतर है।
  • modular से उनका मतलब था कि वे ग्राफ algorithm libraries का ऐसा संग्रह बनाना चाहते थे जिन्हें स्वतंत्र रूप से विकसित और compile किया जा सके।
  • type-safe का मतलब था कि वे programming errors को compile time पर, या कम से कम link time पर पकड़ना चाहते थे। वे runtime errors नहीं चाहते थे।
  • efficiency का मतलब था कि ग्राफ की properties तक पहुंच C struct के fields जितनी सस्ती होनी चाहिए।
  • इन लक्ष्यों का मूल्य है या नहीं, इस पर बहस हो सकती है, लेकिन वे यही चाहते थे। उनकी लैब में C++ के प्रसिद्ध रचनाकार मौजूद थे, इसलिए उन्हें उम्मीद थी कि मदद मिल जाएगी, और उन्होंने C++ को एक और मौका देने का फैसला किया।
  • पूर्व इंटर्न Gordon Woodhull एक बेहतरीन programmer थे, जिन्होंने template C++ में इस तरह की ग्राफ लाइब्रेरी लागू की। इसे sourceforge के माध्यम से https://www.dynagraph.org/ पर जारी किया गया।
  • दूसरों को भरोसा नहीं था कि वे समझ पाएंगे कि कोड कैसे काम करता है, इसलिए उन्होंने प्रसिद्ध C++ आविष्कारकों के साथ code review किया। उन्हें पता चला कि शायद वे जटिलता की खाई पार कर चुके थे।
  • यह Gordon की गलती नहीं थी, और उन्होंने आगे भी काम जारी रखा तथा Microsoft OLE में dynamic graph layout पर सफल काम किया। पीछे मुड़कर देखें तो यह शायद उनका अपना Project Xanadu रहा हो।
  • जब तक वे इसमें डूबे रहे, तब तक Gephi(Java) और NetworkX तथा NetworKit(Python) जैसी कई चीजें सामने आ गईं।
  • John Ellson, जिन्होंने Graphviz का कुछ हिस्सा लिखा था, एक बेहद प्रतिभाशाली software engineer हैं, और उन्होंने मुख्य प्रयास को फिर से जीवित किया।

• अगर आप .NET में coding करते हैं, तो मैं चाहूंगा कि आप छोटी और बहुत अधिक feature-rich न होने वाली ग्राफ लाइब्रेरी Arborescence को आज़माएं।

  • मेरा मानना है कि यह abstraction, algorithms, और data structures के बीच अच्छा विभाजन देती है।
  • उपयोगकर्ता अपनी खुद की ID वाले edges का इस्तेमाल कर सकते हैं, या ऐसे implicit graphs का जो ज़रूरत पड़ने पर तुरंत विस्तृत हो जाते हैं।
  • adjacency (बाहर जाने वाले neighbors) और incidence (बाहर जाने वाले edges + head) दोनों interfaces उपलब्ध हैं।
  • लाइब्रेरी edge type को enforce नहीं करती, लेकिन utility के रूप में एक बुनियादी tail-head pair structure देती है।

• ग्राफ कोई data structure या data type नहीं, बल्कि एक abstraction है।

  • मूल रूप से, ग्राफ को परिभाषित करने के लिए सिर्फ vertex set और neighbor function की ज़रूरत होती है।
  • बाकी सब चीजें case-by-case constraints हैं।
  • अगर hypergraph को देखें, तो graph सिर्फ एक special case है।
  • database के नजरिये से सोचें, तो graph query optimization और indexing की समस्या है।

• मुझसे अक्सर पूछा गया है कि programming languages में built-in graph data type क्यों नहीं होता।

  • अब मैं खुशी से इस लेख जैसी अधिक गहरी analysis की ओर इशारा कर सकता हूँ।

• केंद्रीय बाधा यह है:

  • सरल और छोटे graph problems के लिए, vectors की vector adjacency list कोड करना काफी आसान है।
  • जटिल और बहुत बड़े graph problems के लिए, performance पाने का कोई तरीका नहीं है सिवाय इसके कि समस्या के अनुसार graph implementation को customize किया जाए।
  • यह स्पष्ट नहीं है कि किस तरह का language support मददगार होगा।

• यह लेख काफी हद तक इस सवाल का जवाब देता है कि programming languages में graph algorithms के लिए बेहतर support क्यों नहीं है।

  • अगर सामान्य रूप से graph support को देखें, तो इससे बड़े सवाल भी दिखते हैं, जैसे OGM, ORM जितना लोकप्रिय क्यों नहीं है, JSON, RDF से अधिक व्यापक क्यों है, आदि।
  • अंततः, ऐतिहासिक कारणों और graph की जटिलता के कारण यह developers के बीच अच्छी तरह scale नहीं करता।

• graph drawing tools भी बेहद निराशाजनक हैं।

  • 500 से अधिक nodes वाले graph में output समझना मुश्किल या अत्यधिक जटिल हो जाता है।
  • graph को hierarchical structure में अपने-आप व्यवस्थित करने और उसे explore करने के लिए अच्छा interface देने वाली सुविधाओं की कमी है।

• यह लेख सचमुच शानदार है।

  • "implementation options बहुत ज़्यादा हैं" वाली मुख्य बात पर, वास्तव में ऐसा नहीं है।
  • असल में, libraries सभी उपयुक्त graph representations को implement कर सकती हैं।
  • algorithms को representation के अनुसार customize किया जा सकता है, और एक representation से दूसरे में बदला जा सकता है।

• Electric Clojure, graph authoring syntax के रूप में Clojure खुद (s-expressions) का उपयोग करता है।

  • graph authoring DSL को scope, control flow, और abstraction को व्यक्त करना पड़ता है, और यह मूलतः programming language जैसा ही है।

• tables (जैसे database के अंदर की tables) जैसा एक और उपयोगी data type भी है।

  • अगर compiler को data structures की implementation चुनने दी जाए, तो programming languages में प्रगति हो सकती है।
  • abstract structures (sequence, map, set, table, graph आदि) का उपयोग करें, और compiler को program profile के आधार पर concrete implementation चुनने दें।