ग्राफ़ (सार डेटा प्रकार): Difference between revisions
No edit summary |
No edit summary |
||
| Line 76: | Line 76: | ||
==समानान्तर निरूपण== | ==समानान्तर निरूपण== | ||
ग्राफ समस्याओं के समानांतरीकरण में महत्वपूर्ण चुनौतियों | ग्राफ समस्याओं के समानांतरीकरण में महत्वपूर्ण चुनौतियों डेटा-संचालित गणना, असंरचित समस्याएं, व्यर्थ स्थानीयता एवं गणना अनुपात तक उच्च डेटा पहुंच का सामना करना पड़ता है।<ref name=Bader2013>{{cite book |last1=Bader |first1=David |last2=Meyerhenke |first2=Henning |last3=Sanders |first3=Peter |last4=Wagner |first4=Dorothea |date=January 2013 |title=ग्राफ़ विभाजन और ग्राफ़ क्लस्टरिंग|series=Contemporary Mathematics |publisher=American Mathematical Society |volume=588 |isbn=978-0-8218-9038-7 |doi=10.1090/conm/588/11709 |url=https://www.ams.org/conm/588/}}</ref><ref>{{cite journal |last1=Lumsdaine |first1=Andrew |last2=Gregor |first2=Douglas |last3=Hendrickson |first3=Bruce |last4=Berry |first4=Jonathan |date=March 2007 |title=समानांतर ग्राफ़ प्रसंस्करण में चुनौतियाँ|journal=Parallel Processing Letters |issn=0129-6264 |doi=10.1142/s0129626407002843 |volume=17 |issue=1 |pages=5–20}}</ref> समानांतर आर्किटेक्चर के लिए उपयोग किया जाने वाला ग्राफ़ प्रतिनिधित्व उन चुनौतियों का सामना करने में महत्वपूर्ण भूमिका निभाता है। व्यर्थ उपाय से चुने गए प्रतिनिधित्व एल्गोरिदम की संचार लागत को अनावश्यक रूप से बढ़ा सकते हैं, जिससे इसकी [[ scalability | स्केलेबिलिटी]] कम हो जाती है। निम्नलिखित में, भाग एवं वितरित स्मृति आर्किटेक्चर पर विचार किया जाता है। | ||
=== | === शेयर्ड स्मृति === | ||
शेयर्ड स्मृति प्रारूप के विषय में, समानांतर प्रसंस्करण के लिए उपयोग किए जाने वाले ग्राफ़ प्रतिनिधित्व अनुक्रमिक विषय के समान हैं,<ref name=Sanders2019>{{cite book |last1=Sanders |first1=Peter |last2=Mehlhorn |first2=Kurt |last3=Dietzfelbinger |first3=Martin |last4=Dementiev |first4=Roman |date=2019 |title=Sequential and Parallel Algorithms and Data Structures: The Basic Toolbox |publisher=Springer International Publishing |isbn=978-3-030-25208-3 |url=https://www.springer.com/gp/book/9783030252083}}</ref> चूंकि ग्राफ़ प्रतिनिधित्व (उदाहरण के लिए आसन्न सूची) तक समानांतर पढ़ने-योग्य पहुंच शेयर्ड स्मृति में कुशल है। | |||
=== [[वितरित स्मृति]] === | === [[वितरित स्मृति]] === | ||
वितरित | वितरित स्मृति प्रारूप में, सामान्य दृष्टिकोण शीर्ष सेट <math>V</math> के अंदर <math>p</math> सेट को <math>V_0, \dots, V_{p-1}</math> [[ग्राफ़ विभाजन]] करना है। यहाँ, <math>p</math> उपलब्ध प्रसंस्करण तत्वों (PE) की मात्रा है। शीर्ष सेट विभाजन को मिलान सूचकांक के साथ PE में, इसके अतिरिक्त संबंधित किनारों पर भी वितरित किया जाता है। प्रत्येक PE का स्वयं का [[सबग्राफ (ग्राफ सिद्धांत)|सबग्राफ]] प्रतिनिधित्व होता है, जहां दूसरे विभाजन में समापन बिंदु वाले किनारों पर विशेष ध्यान देने की आवश्यकता होती है। [[संदेश पासिंग इंटरफ़ेस]] जैसे मानक संचार इंटरफेस के लिए, अन्य समापन बिंदु के मालिक PE की आईडी पहचान योग्य होनी चाहिए। वितरित ग्राफ एल्गोरिदम में गणना के समय, इन किनारों के साथ जानकारी पारित करने से संचार का तात्पर्य होता है।<ref name=Sanders2019/> | ||
ग्राफ़ विभाजन को सावधानीपूर्वक करने की आवश्यकता है - कम संचार एवं समान आकार के विभाजन के मध्य समझौता है<ref>{{cite web |title=ग्राफ़ का समानांतर प्रसंस्करण|url=https://www.graphengine.io/downloads/papers/ParallelProcessingOfGraphs.pdf}}</ref> किन्तु ग्राफ़ को विभाजित करना एनपी-हार्ड समस्या है, इसलिए उनकी गणना करना संभव नहीं है। इसके | ग्राफ़ विभाजन को सावधानीपूर्वक करने की आवश्यकता है - कम संचार एवं समान आकार के विभाजन के मध्य समझौता है<ref>{{cite web |title=ग्राफ़ का समानांतर प्रसंस्करण|url=https://www.graphengine.io/downloads/papers/ParallelProcessingOfGraphs.pdf}}</ref> किन्तु ग्राफ़ को विभाजित करना एनपी-हार्ड समस्या है, इसलिए उनकी गणना करना संभव नहीं है। इसके अतिरिक्त, निम्नलिखित अनुमानों का उपयोग किया जाता है। | ||
1डी विभाजन: प्रत्येक प्रोसेसर को | 1डी विभाजन: प्रत्येक प्रोसेसर को <math>n/p</math> शीर्ष एवं संगत आउटगोइंग शीर्ष मिलता है। इसे आसन्न आव्यूह के पंक्ति-वार या स्तंभ-वार अपघटन के रूप में समझा जा सकता है। इस प्रतिनिधित्व पर काम करने वाले एल्गोरिदम के लिए, इसके लिए ऑल-टू-ऑल संचार चरण की भी आवश्यकता होती है <math>\mathcal{O}(m)</math> संदेश बफ़र आकार, क्योंकि प्रत्येक PE में संभावित रूप से हर दूसरे PE के लिए आउटगोइंग शीर्ष होते हैं।<ref name=Buluc2011>{{cite conference |last1=Buluç |first1=A. |last2=Madduri |first2=Kamesh |date=2011 |title=वितरित मेमोरी सिस्टम पर समानांतर चौड़ाई-पहली खोज|conference=2011 International Conference for High Performance Computing, Networking, Storage and Analysis |section=Applications |doi=10.1145/2063384.2063471 |s2cid=6540738 |number=65 |isbn=978-1-4503-0771-0}}</ref>2डी विभाजन: प्रत्येक प्रोसेसर को आसन्न आव्यूह का सबआव्यूह मिलता है। मान लें कि प्रोसेसर आयत <math>p = p_r \times p_c</math> में संरेखित हैं, कहाँ <math>p_r | ||
2डी विभाजन: प्रत्येक प्रोसेसर को आसन्न आव्यूह का सबआव्यूह मिलता है। मान लें कि प्रोसेसर आयत | |||
</math> एवं <math>p_c | </math> एवं <math>p_c | ||
</math> क्रमशः प्रत्येक पंक्ति एवं स्तंभ में प्रसंस्करण तत्वों की मात्रा है। फिर प्रत्येक प्रोसेसर को | </math> क्रमशः प्रत्येक पंक्ति एवं स्तंभ में प्रसंस्करण तत्वों की मात्रा है। फिर प्रत्येक प्रोसेसर को <math>(n/p_r)\times(n/p_c)</math> आयाम के आसन्न आव्यूह का [[सबमैट्रिक्स|सबआव्यूह]] मिलता है। इसे आव्यूह में [[ बिसात |बिसात]] पैटर्न के रूप में देखा जा सकता है।<ref name=Buluc2011/>इसलिए, प्रत्येक प्रसंस्करण इकाई में केवल ही पंक्ति एवं स्तंभ में PE के लिए आउटगोइंग शीर्ष हो सकते हैं। यह प्रत्येक PE के लिए संचार भागीदारों की <math>p_r + p_c - 1</math> से बाहर <math>p = p_r \times p_c</math> संभव वाले संख्या को सीमित करता है। | ||
==संकुचित अभ्यावेदन== | ==संकुचित अभ्यावेदन== | ||
[[ यंत्र अधिगम ]], सोशल नेटवर्क विश्लेषण एवं अन्य क्षेत्रों में खरबों किनारों वाले ग्राफ़ पाए जाते हैं। I/O एवं | [[ यंत्र अधिगम ]], सोशल नेटवर्क विश्लेषण एवं अन्य क्षेत्रों में खरबों किनारों वाले ग्राफ़ पाए जाते हैं। I/O एवं स्मृति आवश्यकताओं को कम करने के लिए डेटा संपीड़न ग्राफ़ प्रतिनिधित्व विकसित किया गया है। [[हफ़मैन कोडिंग]] जैसी सामान्य तकनीकें प्रस्तावित हैं, किन्तु दक्षता बढ़ाने के लिए आसन्न सूची या आसन्न आव्यूह को विशिष्ट तरीकों से संसाधित किया जा सकता है।<ref>{{cite arXiv |last1=Besta |first1=Maciej |last2=Hoefler |first2=Torsten |date=27 April 2019 |title=दोषरहित ग्राफ संपीड़न और अंतरिक्ष-कुशल ग्राफ प्रतिनिधित्व का सर्वेक्षण और वर्गीकरण|class=cs.DS |eprint=1806.01799}}</ref> | ||
| Line 103: | Line 102: | ||
=== गहराई पहली खोज === | === गहराई पहली खोज === | ||
गहराई-प्रथम खोज एल्गोरिदम के | गहराई-प्रथम खोज एल्गोरिदम के विषय में नए शीर्ष की खोज किसी भी बिंदु पर शुरू होती है। इस नए शीर्ष की जांच के बाद, चयनित शीर्ष की जांच जारी रहती है। जब सभी पहुंच योग्य शिखरों का गहन अन्वेषण कर लिया जाता है, तो खोज समाप्त हो जाती है। पुनरावर्ती उपाय से प्रस्तुत किए जाने पर यह खोज प्रक्रिया सबसे अच्छा काम करती है। डीएफएस ऐसी विधि का उपयोग करता है जो जब भी संभव हो ग्राफ़ का गहराई से अन्वेषण करता है। क्योंकि खोज कई स्रोतों से दोहराई जा सकती है, डीएफएस द्वारा बनाया गया पूर्ववर्ती सबग्राफ विभिन्न पेड़ों से बना हो सकता है। | ||
<ref name="Purti" /> | <ref name="Purti" /> | ||
Revision as of 23:22, 18 July 2023
कंप्यूटर विज्ञान में, ग्राफ अमूर्त डेटा प्रकार है जिसका उद्देश्य गणित के अंदर ग्राफ सिद्धांत के क्षेत्र से अप्रत्यक्ष ग्राफ एवं निर्देशित ग्राफ अवधारणाओं को प्रस्तावित करना है।
ग्राफ़ डेटा संरचना में शीर्षों का परिमित (एवं संभवतः परिवर्तनशील) सेट होता है, (जिसे नोड या बिंदु भी कहा जाता है) साथ में इन शीर्षों के अव्यवस्थित जोड़े का सेट होता है, साथ में अप्रत्यक्ष ग्राफ़ के लिए या निर्देशित ग्राफ़ के लिए क्रमित युग्मों का सेट है। इन जोड़ियों को किनारों के रूप में जाना जाता है (जिन्हें लिंक या लाइनें भी कहा जाता है) , एवं निर्देशित ग्राफ के लिए इन्हें किनारों के रूप में भी जाना जाता है, किन्तु कभी-कभी 'आर्क्स ' के रूप में भी जाना जाता है शीर्ष ग्राफ़ संरचना का भाग हो सकते हैं, या पूर्णांक सूचकांकों या संदर्भ (कंप्यूटर विज्ञान) द्वारा दर्शाई गई बाहरी इकाइयाँ हो सकती हैं।
ग्राफ़ डेटा संरचना प्रत्येक शीर्ष से कुछ शीर्ष मान को जैसे कि प्रतीकात्मक लेबल या संख्यात्मक विशेषता (लागत, क्षमता, लंबाई, आदि) भी जोड़ सकती है।
संचालन
ग्राफ़ डेटा संरचना G द्वारा प्रदान किए गए बुनियादी संचालन में सामान्यतः सम्मिलित हैं:[1]
- adjacent(G, x, y): परीक्षण करता है कि शीर्ष x से शीर्ष y तक कोई किनारा है या नहीं;
- neighbors(G, x): सभी शीर्षों y को इस प्रकार सूचीबद्ध करता है कि शीर्ष x से शीर्ष y तक किनारा हो;
- add_vertex(G, x): शीर्ष x जोड़ता है, यदि वह वहां नहीं है;
- remove_vertex(G, x): शीर्ष x को निकाल देता है, यदि वह वहां है;
- add_edge(G, x, y, z): शीर्ष x से शीर्ष y तक किनारा z जोड़ता है, यदि यह वहां नहीं है;
- remove_edge(G, x, y): शीर्ष को शीर्ष x से शीर्ष y तक निकाल देता है, यदि वह वहां है;
- get_vertex_value(G, x): शीर्ष x से संबद्ध मान लौटाता है;
- set_vertex_value(G, x, v): शीर्ष x से v तक संबद्ध मान सेट करता है।
संरचनाएं जो मूल्यों को किनारों से जोड़ती हैं, सामान्यतः यह भी प्रदान करती हैं:[1]* get_edge_value(G, x, y): शीर्ष (x, y) से जुड़ा मान लौटाता है;
- set_edge_value(G, x, y, v): शीर्ष (x, y) से जुड़े मान को v पर सेट करता है।
ग्राफ़ प्रतिनिधित्व के लिए सामान्य डेटा संरचनाएँ
- निकटवर्ती सूची[2]
- शीर्षों को रिकॉर्ड या ऑब्जेक्ट के रूप में संग्रहीत किया जाता है, एवं प्रत्येक शीर्ष आसन्न शीर्षों की सूची संग्रहीत करता है। यह डेटा संरचना शीर्षों पर अतिरिक्त डेटा के भंडारण की अनुमति देती है। यदि किनारों को ऑब्जेक्ट के रूप में भी संग्रहीत किया जाता है, तो अतिरिक्त डेटा संग्रहीत किया जा सकता है, इस स्थिति में प्रत्येक शीर्ष अपने घटना किनारों को संग्रहीत करता है एवं प्रत्येक किनारा अपने घटना शीर्षों को संग्रहीत करता है।
- सहखंडज आव्यूह[3]
- द्वि-आयामी आव्यूह, जिसमें पंक्तियाँ स्रोत शीर्षों का प्रतिनिधित्व करती हैं एवं स्तंभ गंतव्य शीर्षों का प्रतिनिधित्व करते हैं। किनारों एवं शीर्षों पर डेटा को बाहरी रूप से संग्रहीत किया जाना चाहिए। प्रत्येक जोड़ी शीर्षों के मध्य केवल शीर्ष की लागत संग्रहीत की जा सकती है।
- घटना आव्यूह[4]
- द्वि-आयामी आव्यूह, जिसमें पंक्तियाँ शीर्षों का प्रतिनिधित्व करती हैं एवं स्तंभ किनारों का प्रतिनिधित्व करते हैं। प्रविष्टियाँ पंक्ति में शीर्ष एवं स्तंभ में शीर्ष के मध्य घटना संबंध को प्रदर्शित करती हैं।
निम्न तालिका |V| के साथ, इनमें से प्रत्येक प्रतिनिधित्व के लिए, ग्राफ़ पर विभिन्न संचालन करने की समय जटिलता लागत देती है शीर्षों की संख्या एवं |ई| किनारों की संख्या आव्यूह अभ्यावेदन में, प्रविष्टियाँ शीर्ष का अनुसरण करने की लागत को एन्कोड करती हैं। जो किनारे सम्मिलित नहीं हैं उनकी लागत ∞ मानी जाती है।
| निकटवर्ती सूची | संलग्नता आव्यूह | घटना आव्यूह | |
|---|---|---|---|
| स्टोर ग्राफ़ | |||
| शीर्ष जोड़ें | |||
| किनारा जोड़ें | |||
| शीर्ष हटाएँ | |||
| किनारा हटाओ | |||
| क्या शीर्ष x एवं y आसन्न हैं (यह मानते हुए कि उनकी भंडारण स्थिति ज्ञात है)? | |||
| टिप्पणियां | शीर्षों एवं किनारों को हटाने में धीमी गति रखें, क्योंकि इसे सभी शीर्षों या किनारों को ढूंढने की आवश्यकता होती है | शीर्ष को जोड़ने या हटाने की गति धीमी है, क्योंकि मैट्रिक्स का आकार बदलना/कॉपी करना आवश्यक है | शीर्षों एवं किनारों को जोड़ने या हटाने में धीमी गति से, क्योंकि मैट्रिक्स का आकार कॉपी करना आवश्यक है |
सामान्यतः विरल ग्राफ के प्रतिनिधित्व के लिए आसन्नता सूचियों को प्राथमिकता दी जाती है, अपितु ग्राफ़ सघन होने पर आसन्नता आव्यूह को प्राथमिकता दी जाती है; अर्थात् किनारों की संख्या |E| वर्ग शीर्षों की संख्या |V|2 के समीप है, या यदि दो शीर्षों को जोड़ने वाला कोई किनारा है तो किसी को तुरंत देखने में सक्षम होना चाहिए।[5][6]
समानान्तर निरूपण
ग्राफ समस्याओं के समानांतरीकरण में महत्वपूर्ण चुनौतियों डेटा-संचालित गणना, असंरचित समस्याएं, व्यर्थ स्थानीयता एवं गणना अनुपात तक उच्च डेटा पहुंच का सामना करना पड़ता है।[7][8] समानांतर आर्किटेक्चर के लिए उपयोग किया जाने वाला ग्राफ़ प्रतिनिधित्व उन चुनौतियों का सामना करने में महत्वपूर्ण भूमिका निभाता है। व्यर्थ उपाय से चुने गए प्रतिनिधित्व एल्गोरिदम की संचार लागत को अनावश्यक रूप से बढ़ा सकते हैं, जिससे इसकी स्केलेबिलिटी कम हो जाती है। निम्नलिखित में, भाग एवं वितरित स्मृति आर्किटेक्चर पर विचार किया जाता है।
शेयर्ड स्मृति
शेयर्ड स्मृति प्रारूप के विषय में, समानांतर प्रसंस्करण के लिए उपयोग किए जाने वाले ग्राफ़ प्रतिनिधित्व अनुक्रमिक विषय के समान हैं,[9] चूंकि ग्राफ़ प्रतिनिधित्व (उदाहरण के लिए आसन्न सूची) तक समानांतर पढ़ने-योग्य पहुंच शेयर्ड स्मृति में कुशल है।
वितरित स्मृति
वितरित स्मृति प्रारूप में, सामान्य दृष्टिकोण शीर्ष सेट के अंदर सेट को ग्राफ़ विभाजन करना है। यहाँ, उपलब्ध प्रसंस्करण तत्वों (PE) की मात्रा है। शीर्ष सेट विभाजन को मिलान सूचकांक के साथ PE में, इसके अतिरिक्त संबंधित किनारों पर भी वितरित किया जाता है। प्रत्येक PE का स्वयं का सबग्राफ प्रतिनिधित्व होता है, जहां दूसरे विभाजन में समापन बिंदु वाले किनारों पर विशेष ध्यान देने की आवश्यकता होती है। संदेश पासिंग इंटरफ़ेस जैसे मानक संचार इंटरफेस के लिए, अन्य समापन बिंदु के मालिक PE की आईडी पहचान योग्य होनी चाहिए। वितरित ग्राफ एल्गोरिदम में गणना के समय, इन किनारों के साथ जानकारी पारित करने से संचार का तात्पर्य होता है।[9]
ग्राफ़ विभाजन को सावधानीपूर्वक करने की आवश्यकता है - कम संचार एवं समान आकार के विभाजन के मध्य समझौता है[10] किन्तु ग्राफ़ को विभाजित करना एनपी-हार्ड समस्या है, इसलिए उनकी गणना करना संभव नहीं है। इसके अतिरिक्त, निम्नलिखित अनुमानों का उपयोग किया जाता है।
1डी विभाजन: प्रत्येक प्रोसेसर को शीर्ष एवं संगत आउटगोइंग शीर्ष मिलता है। इसे आसन्न आव्यूह के पंक्ति-वार या स्तंभ-वार अपघटन के रूप में समझा जा सकता है। इस प्रतिनिधित्व पर काम करने वाले एल्गोरिदम के लिए, इसके लिए ऑल-टू-ऑल संचार चरण की भी आवश्यकता होती है संदेश बफ़र आकार, क्योंकि प्रत्येक PE में संभावित रूप से हर दूसरे PE के लिए आउटगोइंग शीर्ष होते हैं।[11]2डी विभाजन: प्रत्येक प्रोसेसर को आसन्न आव्यूह का सबआव्यूह मिलता है। मान लें कि प्रोसेसर आयत में संरेखित हैं, कहाँ एवं क्रमशः प्रत्येक पंक्ति एवं स्तंभ में प्रसंस्करण तत्वों की मात्रा है। फिर प्रत्येक प्रोसेसर को आयाम के आसन्न आव्यूह का सबआव्यूह मिलता है। इसे आव्यूह में बिसात पैटर्न के रूप में देखा जा सकता है।[11]इसलिए, प्रत्येक प्रसंस्करण इकाई में केवल ही पंक्ति एवं स्तंभ में PE के लिए आउटगोइंग शीर्ष हो सकते हैं। यह प्रत्येक PE के लिए संचार भागीदारों की से बाहर संभव वाले संख्या को सीमित करता है।
संकुचित अभ्यावेदन
यंत्र अधिगम , सोशल नेटवर्क विश्लेषण एवं अन्य क्षेत्रों में खरबों किनारों वाले ग्राफ़ पाए जाते हैं। I/O एवं स्मृति आवश्यकताओं को कम करने के लिए डेटा संपीड़न ग्राफ़ प्रतिनिधित्व विकसित किया गया है। हफ़मैन कोडिंग जैसी सामान्य तकनीकें प्रस्तावित हैं, किन्तु दक्षता बढ़ाने के लिए आसन्न सूची या आसन्न आव्यूह को विशिष्ट तरीकों से संसाधित किया जा सकता है।[12]
ग्राफ़ ट्रैवर्सल रणनीतियाँ
चौड़ाई पहली खोज
चौड़ाई-प्रथम खोज (बीएफएस) ट्रैवर्सल दृष्टिकोण है जिसका उपयोग किसी दिए गए ग्राफ़ में सभी नोड्स की खोज के लिए किया जाता है। यह ट्रैवर्सल तकनीक व्यक्तिगत नोड चुनती है, फिर समय में उसके प्रत्येक पड़ोसी का पता लगाती है। यह अतिरिक्त शीर्षों का निरीक्षण करना जारी रखता है एवं उन्हें पूरा करने के बाद आस-पास के सभी शीर्षों के लिए प्रक्रिया को दोहराता है।[13]
गहराई पहली खोज
गहराई-प्रथम खोज एल्गोरिदम के विषय में नए शीर्ष की खोज किसी भी बिंदु पर शुरू होती है। इस नए शीर्ष की जांच के बाद, चयनित शीर्ष की जांच जारी रहती है। जब सभी पहुंच योग्य शिखरों का गहन अन्वेषण कर लिया जाता है, तो खोज समाप्त हो जाती है। पुनरावर्ती उपाय से प्रस्तुत किए जाने पर यह खोज प्रक्रिया सबसे अच्छा काम करती है। डीएफएस ऐसी विधि का उपयोग करता है जो जब भी संभव हो ग्राफ़ का गहराई से अन्वेषण करता है। क्योंकि खोज कई स्रोतों से दोहराई जा सकती है, डीएफएस द्वारा बनाया गया पूर्ववर्ती सबग्राफ विभिन्न पेड़ों से बना हो सकता है।
[13]
यह भी देखें
- ग्राफ़ वॉकिंग रणनीतियों पर अधिक जानकारी के लिए ग्राफ ट्रैवर्सल
- ग्राफ़ (डेटा संरचना) दृढ़ता के लिए ग्राफ़ डेटाबेस
- ग्राफ़ के नियम आधारित परिवर्तनों के लिए ग्राफ़ पुनर्लेखन (ग्राफ़ डेटा संरचनाएं)
- ग्राफ़ खींचने के लिए सॉफ़्टवेयर, सिस्टम एवं सिस्टम प्रदाताओं के लिए ग्राफ पुनर्लेखन सॉफ़्टवेयर
संदर्भ
- ↑ 1.0 1.1 See, e.g. Goodrich & Tamassia (2015), Section 13.1.2: Operations on graphs, p. 360. For a more detailed set of operations, see Mehlhorn, K.; Näher, S. (1999). "Chapter 6: Graphs and their data structures". LEDA: A platform for combinatorial and geometric computing (PDF). Cambridge University Press. pp. 240–282.
- ↑ Cormen et al. (2001), pp. 528–529; Goodrich & Tamassia (2015), pp. 361-362.
- ↑ Cormen et al. (2001), pp. 529–530; Goodrich & Tamassia (2015), p. 363.
- ↑ Cormen et al. (2001), Exercise 22.1-7, p. 531.
- ↑ Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001). "Section 22.1: Representations of graphs". Introduction to Algorithms (Second ed.). MIT Press and McGraw-Hill. pp. 527–531. ISBN 0-262-03293-7.
- ↑ Goodrich, Michael T.; Tamassia, Roberto (2015). "Section 13.1: Graph terminology and representations". एल्गोरिथम डिज़ाइन और अनुप्रयोग. Wiley. pp. 355–364. ISBN 978-1-118-33591-8.
- ↑ Bader, David; Meyerhenke, Henning; Sanders, Peter; Wagner, Dorothea (January 2013). ग्राफ़ विभाजन और ग्राफ़ क्लस्टरिंग. Contemporary Mathematics. Vol. 588. American Mathematical Society. doi:10.1090/conm/588/11709. ISBN 978-0-8218-9038-7.
- ↑ Lumsdaine, Andrew; Gregor, Douglas; Hendrickson, Bruce; Berry, Jonathan (March 2007). "समानांतर ग्राफ़ प्रसंस्करण में चुनौतियाँ". Parallel Processing Letters. 17 (1): 5–20. doi:10.1142/s0129626407002843. ISSN 0129-6264.
- ↑ 9.0 9.1 Sanders, Peter; Mehlhorn, Kurt; Dietzfelbinger, Martin; Dementiev, Roman (2019). Sequential and Parallel Algorithms and Data Structures: The Basic Toolbox. Springer International Publishing. ISBN 978-3-030-25208-3.
- ↑ "ग्राफ़ का समानांतर प्रसंस्करण" (PDF).
- ↑ 11.0 11.1 Buluç, A.; Madduri, Kamesh (2011). "Applications". वितरित मेमोरी सिस्टम पर समानांतर चौड़ाई-पहली खोज. 2011 International Conference for High Performance Computing, Networking, Storage and Analysis. doi:10.1145/2063384.2063471. ISBN 978-1-4503-0771-0. S2CID 6540738.
- ↑ Besta, Maciej; Hoefler, Torsten (27 April 2019). "दोषरहित ग्राफ संपीड़न और अंतरिक्ष-कुशल ग्राफ प्रतिनिधित्व का सर्वेक्षण और वर्गीकरण". arXiv:1806.01799 [cs.DS].
- ↑ 13.0 13.1 Purti (July–September 2018). "ग्राफ ट्रैवर्सल और उसके अनुप्रयोग" (PDF). International Journal of Research and Analytical Reviews. 5 (3): 2.
बाहरी संबंध
- Boost Graph Library: a powerful C++ graph library s.a. Boost (C++ libraries)
- Networkx: a Python graph library
- GraphMatcher a java program to align directed/undirected graphs.
- GraphBLAS A specification for a library interface for operations on graphs, with a particular focus on sparse graphs.
