गायब डेटा टाइप की तलाश में एक पड़ताल

 (hillelwayne.com)
2 पॉइंट द्वारा GN⁺ 2024-03-05 | 1 टिप्पणियां | WhatsApp पर शेयर करें
  • ग्राफ़ dependency, web link, model checker के state space, relational DB की foreign key जैसी चीज़ों के रूप में software में हर जगह मौजूद हैं, लेकिन mainstream programming languages में इनके लिए built-in type या standard library support लगभग नहीं है
  • built-in graph type बनाना कठिन होने की पहली वजह यह है कि directed/undirected, simple/multi, hypergraph जैसी graph की किस्में बहुत हैं, और किसी खास property से algorithm चयन और performance बहुत बदल जाते हैं
  • edge list, adjacency list, adjacency matrix, reference struct जैसी representation methods में memory और lookup performance अलग-अलग होती है, इसलिए एक ही generic representation से सभी use cases को संतुष्ट करना कठिन है
  • graph algorithms implement करना कठिन होता है और वे अक्सर बड़े inputs पर चलते हैं, इसलिए Nosey Parker और Gecode जैसे मामलों में problem-specific representation और traversal generic library से ज़्यादा महत्वपूर्ण हो सकते हैं
  • standard library में graph कम मिलने की वजह type, representation, algorithm और performance trade-off के साथ-साथ maintenance burden का बड़ा होना है; third-party libraries भी सीमित या धीमी हो सकती हैं

ग्राफ़ आम हैं, लेकिन language support कम है

  • graph nodes और edges से बनता है, और nodes व edges में data हो सकता है
  • software engineering में graph कई रूपों में दिखते हैं
    • package dependencies और module imports directed graph बनाते हैं
    • internet, web pages के बीच links का graph है
    • model checker सभी संभव configurations के state space को explore करता है; nodes states होते हैं और edges valid transitions होते हैं
    • relational database को records को nodes और foreign keys को edges मानकर देखा जा सकता है
    • graph को linked list, binary tree और hash table का generalization माना जा सकता है
  • business logic में भी paper citation relationships, transport network routes, social network connections जैसे graph अक्सर आते हैं
  • graph की ज़रूरत अक्सर पड़ती है, लेकिन ज़्यादातर mainstream languages graph को built-in type के रूप में नहीं देतीं और standard library में भी इसे शामिल करना दुर्लभ है
  • कई ecosystems में मजबूत third-party graph libraries भी नहीं होतीं, इसलिए अक्सर खुद implement करना पड़ता है

graph type design में बहुत अधिक विकल्प हैं

  • graph में directed graph और undirected graph के अलावा भी कई variants हैं
    • simple graph, जिसमें दो nodes के बीच अधिकतम एक edge होता है, और multigraph, जो कई edges की अनुमति देता है
    • hypergraph, जिसमें एक edge 3 या अधिक nodes को जोड़ता है
    • ubergraph, जिसमें edges दूसरे edges की ओर point कर सकते हैं
  • हर variant के साथ अतिरिक्त design decisions जुड़ते हैं
    • edges को भी ID देना है या सिर्फ nodes को, यह तय करना पड़ता है
    • nodes और edges में कौन-सा data store करना है, यह भी तय करना पड़ता है
  • सभी graphs को “directed hyper-uber-multigraph” जैसे generic type के रूप में देकर user से constraints लगवाए जा सकते हैं, लेकिन तुरंत दो समस्याएं पैदा होती हैं
    • operation का result single value होगा या list, इस तरह interface बदल जाता है
    • खास graph properties का फायदा न उठा पाने पर algorithm performance खराब हो जाती है
  • उदाहरण के लिए maximum weight matching में अगर पता हो कि graph bipartite graph है, तो fast algorithm इस्तेमाल किया जा सकता है, लेकिन general graph के लिए धीमा और generic algorithm चाहिए
  • किसी problem P, graph G, और algorithms A·B·C के लिए कौन-सा algorithm चलाना है, यह चुनने की algorithm dispatch समस्या भी पैदा होती है
  • perfect graph library को graph की कई किस्मों को support करना होगा, लेकिन इससे असल users को चाहिए algorithms implement करने के लिए उपलब्ध समय घट जाता है
  • graph algorithms implement करना कठिन है
    • Python के creator द्वारा लिखा गया find_shortest_path algorithm बाद में पांच बार संशोधित हुआ
    • Nicole कहती हैं कि उन्होंने जिन PageRank implementations की तुलना की, वे सभी गलत थीं
    • NetworkX करीब 500 graph algorithms देता है, और सिर्फ algorithm code ही लगभग 60,000 lines का है
    • पूरी Python standard library में करीब 300 packages हैं और 600,000 lines से कम code है
  • standard library maintainers को तय करना पड़ता है कि कौन-से graph types, कौन-सी topology-specific handling और कौन-से algorithms शामिल किए जाएं, इसलिए maintenance burden बड़ा है
  • Python भी “batteries included” के लिए जाना जाता है, लेकिन PEP 594 के जरिए 20 standard library modules हटाने की दिशा में है

graph representation को भी एक तरीके पर तय करना कठिन है

  • सिर्फ सबसे सरल directed graph के बारे में सोचें, तो भी internal representation के कई तरीके हो सकते हैं
    • 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]
    • एक-दूसरे को reference करने वाले structs का set
  • representation method के हिसाब से operation performance बदलती है
    • 100 nodes और 200 edges वाले graph को adjacency matrix से represent करने पर 100×100 matrix में 200 ones और 9,800 zeros होते हैं
    • वही graph edge list से represent करने पर केवल 200 node pairs चाहिए
    • language और optimization level के हिसाब से memory difference 20 गुना से अधिक हो सकता है
  • उल्टा, 100 nodes और 8,000 edges वाले graph में node 0 और 93 के बीच edge खोजने पर नतीजा अलग होता है
    • adjacency matrix में graph[0][93] से O(1) lookup संभव है
    • edge list में 8,000 edges से होकर गुजरना पड़ता है, इसलिए O(|edge|) time लगता है
  • कम edges वाला graph sparse graph है, और लगभग सभी possible edges वाला graph dense graph है
  • external data से graph बनाने वाला program शुरुआत में sparse graph हो सकता है और बाद में dense graph बन सकता है, इसलिए internal representation में कोई “हमेशा अच्छा choice” नहीं होता
  • node data, edge data, और कई तरह के nodes व edges support करने पर implementation complexity और बढ़ती है
  • third-party libraries आमतौर पर दो दिशाओं में से एक चुनती हैं
    • सभी use cases को cover करने वाला rich single type देती हैं, लेकिन efficiency की कीमत पर
    • representation method के हिसाब से अलग graph types देती हैं, और node/edge data management user पर छोड़ती हैं

NetworkX और Petgraph जो trade-offs दिखाते हैं

  • NetworkX graph को dict के dict के dict structure में store करता है ताकि nodes और edges पर arbitrary data लगाया जा सके
  • यह दूसरे representations में convert करने के functions देता है, लेकिन उन representations पर सीधे काम करने का तरीका नहीं देता
  • Rust की प्रमुख graph library Petgraph graph, graphmap, matrix_graph जैसे use-case-specific types देती है
  • Bradford ने git repository के पूरे history में secrets खोजने वाले security tool Nosey Parker में Petgraph का इस्तेमाल किया
    • benchmark graph CPython है, जिसमें 250,000 commits और 1,300,000 objects शामिल हैं
    • हर commit node पर edges कुछ ही हैं, इसलिए adjacency list चुनी गई
  • कई representations support करने पर algorithm जोड़ने की cost बढ़ती है
    • हर representation के लिए अलग algorithm लिखने पर maintenance burden 3–4 गुना बढ़ जाता है
    • polymorphic type पर generic abstraction से लिखने पर performance घट जाती है
  • एक interviewee ने अनुमान लगाया कि खुद लिखा गया graph algorithm generic algorithm से 20 गुना से अधिक तेज़ हो सकता है

performance constraints graph libraries की मूल समस्या हैं

  • graph algorithms में कई problems NP-complete या उससे भी कठिन हैं
    • Karp की 21 canonical NP-complete problems में से 14 graph problems हैं
  • graph problems बहुत बड़े inputs पर चल सकती हैं, इसलिए representation method और implementation details तय करते हैं कि वे practically चल पाएंगी या नहीं
  • Bradford को Nosey Parker में हर commit के लिए filesystem snapshot reconstruct करने के लिए object graph traverse करना पड़ा
    • Petgraph के चार graph walkers उस use case के लिए scale नहीं हुए
    • उन्होंने मौके पर “semi-novel” graph traversal algorithm design किया और memory usage को 1,000वें हिस्से तक घटा दिया
  • Zayenz ने ऐसे case के तौर पर 15 puzzle का ज़िक्र किया, जहां graph इतना बड़ा है कि पूरे graph से निपटना संभव नहीं
    • solution search, state space में A* search चलाने का तरीका है
    • state space में 20 trillion से अधिक states हैं
    • सभी nodes generate करते ही काम fail हो चुका होगा
  • Zayenz से जुड़े Gecode constraint solver के graph addition research project में भी generic graph type, problem-specific representation choice से मुकाबला नहीं कर सका
  • graph databases भी complex graph algorithms चलाने के लिए design किए गए हैं, लेकिन performance issues बाकी हैं
    • Nicole के अनुसार, traversal में depth limit न लगाएं तो पूरा graph visit हो जाता है
    • “3 steps बाहर जाकर path हो तो खोजो” जैसी depth search भी बहुत data visit करती है
  • Nicole graph query performance consulting में ज़्यादातर graph database से migration का काम करती हैं
    • एक project में एक calculation को जस का तस छोड़ा और बाकी को MapReduce procedure के रूप में फिर से लिखा
    • समझना ज्यादा कठिन था, लेकिन वह सच में रात भर में complete हो सकता था

standard libraries में graph दुर्लभ क्यों हैं

  • व्यापक graph support दुर्लभ होने की वजह कई factors का साथ आना है
    • graph की कई किस्में हैं
    • हर graph type के लिए कई representation methods हैं
    • graph algorithms की कई किस्में हैं
    • algorithm performance representation और implementation details के प्रति sensitive है
    • लोग बहुत बड़े graphs पर बहुत महंगे algorithms चलाते हैं
  • language standard libraries को बहुत ज्यादा design decisions, trade-offs और maintenance burden उठाना पड़ता है
  • programmers के third-party graph libraries से बचने की भी वजहें हैं
    • library बहुत सीमित हो सकती है
    • generic library performance requirements पूरी नहीं कर सकती
  • graph system analysis में उपयोगी हैं, लेकिन implementation stage में data representation और algorithm choice को अक्सर खुद control करना पड़ता है

परिशिष्ट: graph type देने वाली languages और संबंधित tools

  • graph query language (GQL) graph databases में SQL जैसी भूमिका निभाती है
    • व्यापक रूप से इस्तेमाल होने वाला standard नहीं है, लेकिन प्रमुख examples में SPARQL और Neo4j का Cypher शामिल हैं
    • यहां GQL को development में मौजूद GQL standard language से confuse नहीं करना चाहिए
  • GraphQL graph query language नहीं है; इसका नाम Facebook Graph Search से connection से आया है
  • GQL और SQL का मुख्य अंतर यह है कि relationships, यानी “join”, first-class entities होते हैं
    • movies और people dataset में SQL “acting”, “directing”, “production” relationships को अलग-अलग many-to-many tables के रूप में implement करता है
    • SPARQL में relationships edges होते हैं, इसलिए “movie Y में कोई भी role निभाने वाले लोग और उनका role” आसानी से query किया जा सकता है
  • GQL edge reversal, composition, transitive closure जैसी edge operations भी support कर सकता है
    • SPARQL path length या path के दौरान calculations, जैसे दो actors को जोड़ने वाली movie chain collect करना, provide नहीं कर पाता
    • इसे support करने वाला GQL कहीं ज्यादा complex हो जाता है
  • formal specification language Alloy में relation data type के लिए उपयोगी graph traversal primitives हैं, इसलिए graph representation संभालना general programming languages की तुलना में आसान है
    • हालांकि ये primitives labeled edges पर आधारित हैं और दूसरे graph representations के लिए उपयुक्त नहीं हो सकते
  • Python ने 2020 में graphlib जोड़ा
    • TopologicalSorter के अलावा कोई method नहीं है
    • graph केवल node dict के रूप में लिया जाता है
    • a -> b graph को {b: [a]} जैसे reverse direction dict में represent करता है
  • 2023 तक CPython internals में graphlib का इस्तेमाल नहीं होता
    • GitHub पर graphlib को reference करने वाली files 900 से कम हैं
    • उसी साल जोड़ा गया zoneinfo 6,000 से अधिक files में दिखता है
    • def topological_sort( expression 4,000 files में दिखता है
    • खुद implement किए गए topological sorts अक्सर graphlib से अलग graph representations इस्तेमाल करते हैं, इसलिए convert करना कठिन होता है
  • standard library में graph type होने के अन्य examples Erlang और SWI-Prolog हैं
  • कुछ programming languages में “सब कुछ graph” होता है
    • उदाहरण के लिए GP2 और Grape हैं
    • फिलहाल यह बहुत academic क्षेत्र है
  • Mathematica, MATLAB, Maple जैसी mathematical software languages में भी किसी न किसी रूप में graph libraries होती हैं
  • 18 मार्च 2024 के update में, लेख पर कुछ comments अलग page पर इकट्ठा किए गए

संबंधित पढ़ाई

1 टिप्पणियां

 
GN⁺ 2024-03-05
Hacker News की राय

  • Graphviz के पास अपनी बुनियादी ग्राफ लाइब्रेरी है, जिसे दूसरे प्रोजेक्ट इस्तेमाल नहीं करते, और इसके फायदे-नुकसान दोनों हैं
    उसी अनुभव के आधार पर हम भी क्लासिक second system syndrome से गुज़रे। हम एक modular, type-safe और efficient ग्राफ लाइब्रेरी बनाना चाहते थे, लेकिन अंत में यह शायद “अच्छा, तेज़ और सस्ता — इनमें से सिर्फ़ दो चुनें” का ही एक रूप था
    modular होने का मतलब था कि हम ग्राफ algorithm libraries के समूह को स्वतंत्र रूप से develop और compile कर सकें; और type-safe होने का मतलब था कि “नोड में color attribute नहीं है” जैसी runtime errors के बजाय programming errors को compile time पर, या कम से कम link time तक, पकड़ना चाहते थे
    efficient होने का मतलब था कि graph properties तक access की लागत C struct field access जितनी सस्ती होनी चाहिए, और हम external hash tables ढोने या बहुत सारे string conversions करने वाला तरीका नहीं चाहते थे
    ये लक्ष्य अपनी कीमत के लायक थे या समझ में आते थे, इस पर बहस हो सकती है, लेकिन उस समय हम यही चाहते थे। लैब में C++ के प्रसिद्ध creators थे और हम C++ को फिर से एक मौका देने के बारे में भी सोच रहे थे
    Gordon Woodhull, जो intern था और फिर हमारे साथ काम करता रहा, एक बेहतरीन programmer था, और उसने template C++ में ऐसी graph library implementation लिखी। source भी https://www.dynagraph.org/ पर उपलब्ध है
    बाकी लोगों को भरोसा नहीं था कि हम कभी समझ पाएंगे कि वह code कैसे काम करता है, इसलिए हमने प्रसिद्ध C++ inventors के साथ code review किया, और code की अनगिनत screens और लंबी चुप्पी के बाद निष्कर्ष निकला कि “शायद यह काम करेगा।” उसी समय हमें लगा कि शायद हम complexity की cliff पार कर चुके थे
    compile-time template errors में एक error पूरी screen भर देता था और ऐसे details उगलता था जिन्हें शायद सिर्फ़ C++ inventor ही प्यार कर सकता था। गलती हमारी थी, और Gordon आगे बढ़ता रहा और dynamic graph layout को Microsoft OLE में भी चलने लायक बना दिया
    पीछे मुड़कर देखें तो यह हमारा अपना Project Xanadu था, और जब हम उसमें भटक रहे थे, तब Gephi(Java), NetworkX, NetworKit(Python) जैसी चीज़ें आ गईं। Graphviz के कुछ हिस्से लिखने वाले उत्कृष्ट software engineer John Ellson ने मुख्यधारा का काम फिर से जिंदा किया

    • Graphviz dot syntax को NetworkX से parse करके महंगे tools का execution plan बनाया जा सकता है, और graph structure की वजह से automatic parallelization संभव हो जाता है

  • ग्राफ पर काफी काम कर चुके व्यक्ति के रूप में मुझसे अनगिनत बार पूछा गया है, “programming languages में built-in graph data type क्यों नहीं होता?”
    अब खुशी है कि सिर्फ़ “इसे अच्छी तरह बनाना सचमुच मुश्किल है” कहकर भरोसा करने को कहने के बजाय, इस लेख जैसी गहरी analysis की ओर इशारा कर सकता हूं

    • उस सवाल में थोड़ा मज़ेदार पहलू यह है कि लोग यह बात छोड़ देते हैं कि ज़्यादातर languages में tree data structure तक नहीं होता
      ज़्यादातर languages structural types के रूप में static arrays, dynamic arrays और linked lists ही देती हैं। binary search tree या hash table जैसी चीज़ें semantic abstractions हैं, जो underlying structure की कुछ क्षमताओं को छिपाती हैं; वे शुद्ध structural representation नहीं हैं
    • ग्राफ एक व्यापक data structure है जिसकी representation requirements के हिसाब से बहुत बदलती है, इसलिए मुझे लगता था कि इसे domain level पर implement करना ज़्यादा उचित है
      लेख का “implementation choices बहुत ज़्यादा हैं” वाला हिस्सा भी यही बात कहता है। फिर Petgraph [0] देखकर पहली बार मैंने एक general-purpose graph library को ठीक से देखा और यह काफ़ी दिलचस्प लगी, लेकिन फिर भी मैं graphs को domain level पर ही implement करता आया हूं
      [0] https://github.com/petgraph/petgraph
    • उलटा अनुभव भी हुआ। Tcl में पहली बार graph work करते समय मैंने स्वाभाविक रूप से मान लिया था कि standard library में graph algorithms नहीं होंगे, लेकिन पता चला कि थे, और उसकी वजह से wheel को फिर से invent नहीं करना पड़ा
      https://core.tcl-lang.org/tcllib/doc/trunk/embedded/md/tclli...
    • “इसे अच्छी तरह बनाना सचमुच मुश्किल है” से भी ज़्यादा महत्वपूर्ण बात यह है कि trade-offs बहुत हैं
      लगभग हर language hash map देती है, और किसी खास स्थिति में खुद implement करने पर उसे तेज़ बनाया जा सकता है, फिर भी default implementation आम तौर पर अच्छी तरह काम करती है। graphs के साथ ऐसा करना मुश्किल है, और अगर संभव भी हो तो शायद कई graph types देने पड़ें
      साथ ही, Java का HashMap थोड़ा अलग है क्योंकि अधिकांश दूसरी languages के विपरीत इसमें load factor adjust किया जा सकता है
    • यह बहुत भोला विचार हो सकता है, लेकिन मुझे लगता है कि pointers असल में native graph type हैं
      लोग graph type खुद नहीं, बल्कि graph traverse करने वाले tools चाहते हैं

  • मुझे लगता है कि graph कोई data structure या data type नहीं, बल्कि एक abstraction है
    मूल रूप से graph को define करने के लिए सिर्फ़ vertex set v \in V और function Neighbors(v) चाहिए, और बुनियादी graph algorithms में से ज़्यादातर के लिए सच में इतना ही काफी है
    बाकी सब case-by-case constraints हैं। जैसे A->B का मतलब B->A भी है या नहीं, node set को किसी खास constraint के तहत partition किया जा सकता है या नहीं, colors या labels हैं या नहीं
    और generalize करें तो hypergraph तक जा सकते हैं, जहां सिर्फ़ vertex set और vertex sets का set चाहिए। रुचि के आधार पर इसे बहुत तरीकों से represent किया जा सकता है, और सामान्य graph बस उसका एक special case है
    database के नजरिए से इसे query optimization और indexing की समस्या भी माना जा सकता है। आप graph से किस तरह के सवाल पूछना चाहते हैं, उसके आधार पर वह representation बदलती है जो बेहतर जवाब दे सके। जैसे “table” abstraction को represent करने का एक ही तरीका नहीं है, वैसे ही “graph” भी एक तरीके पर खत्म नहीं होता

    • graphs हर जगह इसलिए हैं क्योंकि वे इतने abstract हैं
      वे pure numbers जैसी abstraction level पर हैं। जैसे उपयोगी “numeric” libraries होती हैं, वैसे उपयोगी “graph-like” libraries भी कही जा सकती हैं, लेकिन “number” library या “graph” library बहुत कम होती हैं। ऐसे concepts API बनाने के लिए बहुत ज़्यादा abstract हैं
    • सिर्फ़ vertex set और Neighbors(v) भी पहले से ही काफी restrictive हैं, क्योंकि वे उसी neighbor तक जाने वाली multiple edges की अनुमति नहीं देते
    • अगर hypergraph vertex set और vertex sets का set है, तो यह थोड़ा file system जैसा भी लगता है
      files vertices हैं, और directories ऐसे vertex sets हैं जिन्हें nest किया जा सकता है

  • मुख्य बाधाएँ दो हैं
    सरल और छोटे graph problems में vectors के vector से बनी adjacency list को खुद लिखना भी काफी आसान होता है, और जटिल व बहुत बड़े graph problems में performance तभी मिलती है जब graph implementation को हल की जा रही समस्या की बारीकियों के हिसाब से custom बनाया जाए
    इसलिए यह साफ नहीं दिखता कि भाषा-स्तर का कौन-सा support मददगार होगा। जब तक कोई बेहद smart compiler code को analyze करके यह तय न कर सके कि adjacency list, matrix, 3D array आदि में से क्या optimal है, यह मुश्किल है। ऐसी optimization कुछ समय तक compilers में दिखना कठिन होगा
    यह Stroustrup द्वारा देखी गई phenomenon का एक और उदाहरण है। हम vector जैसी छोटी चीजों और operating system जैसी बड़ी चीजों में code sharing अच्छी तरह करते हैं, लेकिन मध्यम आकार की समस्याएँ अच्छी तरह share नहीं कर पाते

    • छोटे स्तर पर भी हम सचमुच बहुत अच्छी sharing करते हैं, ऐसा कहना मुश्किल है। क्योंकि हर programming language में vector implementation अलग होती है
      किसी एक language ecosystem के भीतर vector API छोटी होती है, इसलिए sharing आसान लगती है। Operating system की API भी उसकी internal complexity की तुलना में अपेक्षाकृत छोटी होती है, और numerical computing libraries के साथ भी यही है, इसलिए sharing अच्छी होती है
      इसके उलट, जटिल data structures जैसी चीजों को जितना ज्यादा customize करना चाहेंगे, API उतनी जटिल होगी और sharing उतनी कठिन हो जाएगी। आखिरकार shareability शायद share की जाने वाली चीज के surface area, यानी API के relative size पर निर्भर करती है
    • abstract graph type के लिए लिखे गए algorithms को देखकर, किसी खास algorithm के अनुरूप implementation भरकर optimize करना code-specialized LLM के क्षेत्र में काफी अच्छी तरह फिट होता दिखता है

  • Electric Clojure, Clojure की अपनी s-expressions को graph authoring syntax के रूप में इस्तेमाल करता है, और macros के जरिए reactive client/server system के data flow को concrete बनाता है
    यहाँ use case full-stack user interface है, लेकिन idea को generalize किया जा सकता है। https://github.com/hyperfiddle/electric का founder हूँ
    “graph types आखिर कहाँ चले गए?” का जवाब मुझे यह लगता है कि graph authoring DSL को scope, control flow और abstraction को express करना पड़ता है, और तब वह असल में evaluation model से मुक्त programming language के साथ isomorphic हो जाता है। Python और TypeScript में पूरी programming language को embed करना काफी कठिन है
    ब्लॉग पोस्ट “Four problems preventing visual flowchart programming from expressing web applications” भी देखने लायक है
    https://www.dustingetz.com/#/page/four%20problems%20preventi...

  • यह लेख मुख्य रूप से “programming languages graph algorithms को बेहतर support क्यों नहीं करतीं” का जवाब देता है, और सामान्य graph support की तुलना में “big data” graph processing पर ज्यादा केंद्रित लगता है
    graph support को व्यापक रूप से देखें तो इसमें “OGM(Object Graph Mapper) ORM जितना लोकप्रिय क्यों नहीं है”, “JSON व्यापक रूप से इस्तेमाल होता है, पर RDF या दूसरे low-level graph serialization क्यों नहीं” जैसे बड़े सवाल भी शामिल हैं
    आखिरकार मुझे लगता है कि historical कारण बड़े हैं। RDF थोड़ा बहुत जल्दी आ गया, सही ढंग से evolve नहीं हो पाया, और उसने भयानक academic standards व implementation ecosystem बना लिया। इसके ऊपर, graphs implementation और learning curve में स्वाभाविक रूप से थोड़े ज्यादा जटिल हैं, इसलिए वे कई developers के लिए अच्छी तरह scale नहीं करते
    लेख के “Graph Querying Language” हिस्से को मैं बहुत ज्यादा महत्व नहीं दूँगा। कुछ जगहें ऐसी लगती हैं जैसे Neo4J या SPARQL का कोई उत्साही user, जिसने सच में product नहीं बनाए, marketing copy लिख रहा हो
    यह कहा गया है कि “सभी GQL और SQL के बीच मुख्य अंतर join है, यानी relationship first-class entity है”, लेकिन SQL में भी joins first-class entities हैं। यहाँ तक कि JOIN नाम का keyword भी है
    अगर graph query language की lower layer में जाकर query plans देखें, तो SQL-based queries से कोई खास meaningful फर्क नहीं दिखता। GQL[0] standardization का SQL extension के रूप में आगे बढ़ना इसका प्रमाण है
    SPARQL तब आसान है जब exact path traversal चाहिए, लेकिन web app backend में किए जाने लायक थोड़ा और जटिल काम करने की कोशिश करें तो unbound values के साथ join जैसी pitfalls से जल्दी सामना हो जाता है, जहाँ आप गलती से पूरा result set उड़ा सकते हैं
    [0]: https://en.wikipedia.org/wiki/Graph_Query_Language

    • किसी चीज का अपना keyword होना उलटे इस बात का मजबूत प्रमाण है कि वह first-class object नहीं है
      उदाहरण के लिए Haskell की type classes first-class नहीं हैं, और ज्यादातर programming languages में control flow भी first-class नहीं होता
    • JOIN, खासकर RECURSIVE queries में joins, graph databases का core हैं, इसलिए SQL relational databases भी आम तौर पर इन्हें अच्छी तरह handle करते हैं
      बस syntactic shortcut नहीं होता, और graph query languages मूलतः वही shortcut जोड़ने पर केंद्रित होती हैं

  • ग्राफ़ बनाने वाले टूल भी काफ़ी निराशाजनक हैं। छोटे ग्राफ़ में वे ठीक काम करते हैं, लेकिन जैसे ही node लगभग 500 से ज़्यादा हो जाते हैं, output पूरी तरह समझ से बाहर या देखने में बहुत मुश्किल हो जाता है
    ग्राफ़ को अपने-आप hierarchical structure में व्यवस्थित करने और उसे explore करने के लिए अच्छा interface देने की क्षमता कम है। यह देखते हुए कि हम अपने आसपास की लगभग हर चीज़ को कुछ हद तक hierarchical structure के रूप में देखने के आदी हैं, लगता है कि general-purpose graph data type बनाते समय भी इसी तरह की समस्या हल करनी होगी
    ऐसा काम compiler level पर implement करना पड़ सकता है, ताकि general-purpose graph algorithms generated structure hierarchy के हिसाब से adapt हो सकें। अगर इसमें theorem prover जोड़कर यह verify किया जा सके कि कोई specific subgraph हमेशा कोई specific structure रखता है, तो उस procedure को statically generate किया जा सकता है, और बाकी upper graph के लिए runtime पर dynamically generate किया जा सकता है
    इसलिए general-purpose graph drawing की समस्या हल करने वाले व्यक्ति के पास इस समस्या को implement करने की क्षमता या insight भी होगी

    • ग्राफ़ drawing कठिन है
      Graphviz-जैसी general-purpose graph drawing library, जो ज़्यादा options और control देती है
      https://eclipse.dev/elk/
      Kiel University में ELK development team द्वारा किया गया experiment
      https://github.com/kieler/KLighD
      Kieler project wiki
      https://rtsys.informatik.uni-kiel.de/confluence/display/KIEL...
      constraint-based graph drawing library
      https://www.adaptagrams.org/
      JavaScript implementation
      https://ialab.it.monash.edu/webcola/
      एक दिलचस्प resource: HOLA: Human-like Orthogonal Network Layout
      https://ialab.it.monash.edu/~dwyer/papers/hola2015.pdf
      Confluent Graphs demo edges को ज़्यादा readable बनाता है
      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
    • कुछ algorithms इस समस्या को बेहतर संभालते हैं, लेकिन general case में “ग्राफ़ का अच्छा diagram बनाओ” कहना लगभग AI-complete problem जैसा है
      संरचनात्मक रूप से एक जैसे graph को भी दो लोग data के अलग-अलग पहलुओं पर ज़ोर देने के लिए बिल्कुल अलग तरह से render कर सकते हैं। यह “general-purpose graph algorithm” और “general-purpose graph data structure” की समस्याओं जैसा भी है
      graph code और data की सीमा पर स्थित होते हैं। उदाहरण के लिए, किसी भी program का call graph होता है, इसलिए एक अर्थ में “general-purpose graph algorithm” computation खुद ही है
    • आदर्श चीज़ें अक्सर tree जैसी दिखती हैं, लेकिन वास्तविक दुनिया की संरचना, भले ही अच्छी तरह व्यवस्थित हो, आम तौर पर directed acyclic graph होती है
      कुछ दर्जन nodes से ऊपर जाते ही उसे planar बनाना, या crossings कम करके संबंधित nodes को अच्छी तरह group कर लगभग planar जैसा दिखाना आमतौर पर कठिन होता है
    • मुझे लगता है बड़ी समस्या यह है कि हम इस भ्रम के आदी हैं कि हर चीज़ hierarchical है
      असल में जो चीज़ें मुश्किल से ही hierarchical होती हैं, graph drawing को उन्हें reconcile करना पड़ता है, और कहाँ तक hierarchy माना जाए, इसकी गणितीय रूप से सटीक रेखा खींचना कठिन है। underlying graph structure के बारे में connectivity, acyclicity, sparsity जैसी assumptions जितनी कम हों, यह समस्या उतनी ही खराब होती जाती है
      practice में graph के साथ interact करने वाला UI बनाते समय आम तौर पर metadata hierarchy के एक-दो स्तर तय या enforce किए जा सकते हैं, जिससे clustering हो सकती है; इससे hairball nodes द्वारा layout बिगाड़ने का असर कम होता है और nodes की संख्या घटकर rendering performance भी बेहतर होती है। layout के लिए fCOSE इस्तेमाल किया जा सकता है, और इसका Cytoscape.js implementation भी है
    • neural network diagrams देखने पर साफ़ दिखता है कि large-scale graph visualization कितना पूरी तरह समझ से बाहर हो सकता है

  • मुख्य observation कि “implementation के विकल्प बहुत ज़्यादा हैं” मुझे पूरी तरह सही नहीं लगती
    असल में library सभी उपयुक्त graph representations implement कर सकती है, हर representation के लिए सबसे अच्छा performance देने वाले algorithms दे सकती है, और representations के बीच conversion भी दे सकती है। यह conversion representations की संख्या के अनुपात में होता है, implement और use करना भी simple है, इसलिए maintainers और users दोनों के लिए यह काफी reasonable burden है
    बोनस के तौर पर standard library data types और idioms से import/export conversions भी दिए जा सकते हैं। memory और conversion cost सस्ती है, और 99% use cases में RAM और CPU दोनों तरफ data conversion overhead को ignore किया जा सकने की संभावना है
    यह बात भी याद आती है कि “Google में काम करने की कठोर सच्चाई यह है कि आखिरकार आप protobuf को एक जगह से दूसरी जगह ले जा रहे होते हैं”
    https://news.ycombinator.com/item?id=20132880

    • ऐसा करने पर लगता है कि library बहुत विशाल हो जाएगी, और मुझे यकीन नहीं कि मेरे काम में उसका use होगा। मैं graphs बहुत use करता हूं, लेकिन मेरा अनुभव लेखक द्वारा interview किए गए लोगों जैसा ही है
      आखिर में graph को हमेशा फिर से implement करना पड़ता है। performance important है, और जो ready-made graph libraries मैंने देखीं, वे हमारे dataset की regularity का फायदा नहीं उठा सकीं। उदाहरण के लिए हम append-only DAG use करते हैं, जिसमें लगभग हर node में सिर्फ एक edge होती है जो आखिरी में जोड़े गए item की ओर point करती है, इसलिए internally run-length encoding संभव है
      मैंने ऐसी general-purpose graph library भी नहीं देखी जो जरूरी queries support करती हो। खासकर बड़ी चीज subgraph diff function है
      इसके अलावा custom implementation इतना बड़ा काम नहीं है। graph को B-tree की तुलना में फिर से implement करना बहुत आसान है, और simple implementation कुछ दर्जन lines में हो जाता है। supported algorithms सहित हमारी highly optimized library भी बस कुछ सौ lines की है
      data को standard format में export करने का तरीका हो तो सुविधाजनक होगा, लेकिन हमारे use case में library लाना शायद समाधान से ज्यादा समस्याएं बढ़ा देगा

  • जो missing application मुझे अक्सर याद आती है, वह graphs के लिए Excel है
    tabular data के लिए Excel की तरह, यह ऐसा tool हो जो RAM में fit होने लायक data—यानी ऐसा scale जहां computer चाहिए लेकिन datacenter नहीं—handle करे, कई algorithms और visualizations को “काफी अच्छा” implement करे, और programming knowledge के बिना भी use किया जा सके
    जैसा लेख कहता है, real world की कई problems graph problems हैं, तो उन्हें solve करने के tools सिर्फ programmers के पास ही क्यों हों

    • लगता है लेख ने conclusion बहुत जल्दी निकाल लिया। कई दूसरी problems भी requirements जोड़ने पर जितनी चाहें complex और difficult बनाई जा सकती हैं
      फिर भी ज्यादातर use cases के लिए पर्याप्त data structures और standard libraries मौजूद हैं, और अगर कोई खास तौर पर तीखी requirement हो तो custom solution बनाया जा सकता है
      लेख कहता है कि graphs अक्सर बहुत बड़े होते हैं, लेकिन graph algorithms के साथ असल में काम करने वालों से पूछें तो ऐसा अनुभव होना आसान है। ज्यादातर programmers और users शायद सच में बहुत छोटे graphs ही handle करेंगे
    • मुझे लगता है कि सिर्फ programmers और mathematicians ही ऐसी problems को graph के रूप में model करते हैं
      मुझे नहीं लगता कि आम users किसी random real-world problem में graph देखते हैं। बड़ी कंपनियों में काम करते हुए मैंने यह सीखा कि पर्याप्त कोशिश की जाए तो हर चीज Excel spreadsheet बन सकती है
    • ठीक वही नहीं जो मांगा गया था, लेकिन https://gephi.org/ कई graph visualization algorithms implement करता है
      https://strlen.com/treesheets/ tree data के लिए Excel के ज्यादा करीब है
    • लेख “कई real-world problems graph problems हैं” इस बात को ठीक से support नहीं करता
      उदाहरण के लिए, यह कहा जा सकता है कि internet को graph के रूप में model किया जा सकता है, लेकिन यह सही होने पर भी इससे क्या होता है, यह अस्पष्ट है। internet को कई तरीकों से represent किया जा सकता है, और graph representation के आम तौर पर useful engineering implications होते हैं, यह स्पष्ट नहीं है
      useful information पाने के लिए ideal representation इसके बजाय arbitrary inputs को consistent outputs में map करने वाला black-box matrix encoding function, यानी neural network, कहा जाए तो भी लगभग उतना ही convincing लगेगा
      Google जैसी जगहों के लिए यह अरबों dollar का idea हो सकता है, लेकिन पूरा internet बहुत से लोगों के लिए graph problem नहीं है, और graph के रूप में represent करने से बहुत कुछ solve नहीं हो जाता
      real-world problems को कागज पर graph बनाकर solve करने वाले लोग दुर्लभ हैं। tables हमेशा use होते हैं। graphs आम हैं, लेकिन graph problems आम नहीं हैं
    • मुझे लगता है यहां key VR है
      दूसरे comments में भी कहा गया कि graph visualization मुश्किल है, लेकिन 3D interface कहीं ज्यादा space देता है। जब VR boom शुरू हुआ तो मैंने सोचा था, “VR का Excel क्या होगा?” Microsoft का जवाब था “3D space में तैरती 2D spreadsheet”। मुझे यह बेतुका लगता है। मेरे हिसाब से जवाब graph है
      अगर कोई साथ में explore करना चाहता हो तो मेरे username at gmail.com पर email कर सकता है

  • graph type काफी समय से मौजूद है
    Erlang में https://www.erlang.org/doc/man/digraph.html और https://www.erlang.org/doc/man/digraph_utils हैं, और अगर set-theoretic काम करना हो तो https://www.erlang.org/doc/man/sofs.html भी है

    • लेख के आखिर में Erlang का संक्षेप में जिक्र है
      “graph type वाली दो और languages के रूप में मुझे Erlang और SWI-Prolog मिले। दोनों के बारे में अच्छी तरह नहीं जानता, इसलिए यह नहीं कह सकता कि वे कब add हुए, लेकिन Erlang में यह कम से कम 2008 से पहले था। मैंने Erlang core language committee के एक व्यक्ति से संपर्क किया, लेकिन जवाब नहीं मिला” यही बात है
    • Elixir में भी एक काफी अच्छी graph library है: https://hexdocs.pm/libgraph/api-reference.html
      मैंने इसे कामों का order तय करने के लिए dependency resolution में use किया है
    • जिज्ञासा है कि वह अलग-अलग situations में कितनी flexible और performant है