ग्राफ़ (सार डेटा प्रकार): Difference between revisions

Revision as of 23:56, 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| के साथ, इनमें से प्रत्येक प्रतिनिधित्व के लिए, ग्राफ़ पर विभिन्न संचालन करने की समय जटिलता लागत देती है शीर्षों की संख्या एवं |ई| किनारों की संख्या आव्यूह अभ्यावेदन में, प्रविष्टियाँ शीर्ष का अनुसरण करने की लागत को एन्कोड करती हैं। जो किनारे सम्मिलित नहीं हैं उनकी लागत ∞ मानी जाती है।

	निकटवर्ती सूची	संलग्नता आव्यूह	घटना आव्यूह
स्टोर ग्राफ़	$O(\|V\|+\|E\|)$	$O(\|V\|^{2})$	$O(\|V\|\cdot \|E\|)$
शीर्ष जोड़ें	$O(1)$	$O(\|V\|^{2})$	$O(\|V\|\cdot \|E\|)$
किनारा जोड़ें	$O(1)$	$O(1)$	$O(\|V\|\cdot \|E\|)$
शीर्ष हटाएँ	$O(\|E\|)$	$O(\|V\|^{2})$	$O(\|V\|\cdot \|E\|)$
किनारा हटाओ	$O(\|V\|)$	$O(1)$	$O(\|V\|\cdot \|E\|)$
क्या शीर्ष x एवं y आसन्न हैं (यह मानते हुए कि उनकी भंडारण स्थिति ज्ञात है)?	$O(\|V\|)$	$O(1)$	$O(\|E\|)$
टिप्पणियां	शीर्षों एवं किनारों को हटाने में धीमी गति रखें, क्योंकि इसे सभी शीर्षों या किनारों को ढूंढने की आवश्यकता होती है	शीर्ष को जोड़ने या हटाने की गति धीमी है, क्योंकि मैट्रिक्स का आकार बदलना/कॉपी करना आवश्यक है	शीर्षों एवं किनारों को जोड़ने या हटाने में धीमी गति से, क्योंकि मैट्रिक्स का आकार कॉपी करना आवश्यक है

सामान्यतः विरल ग्राफ के प्रतिनिधित्व के लिए आसन्नता सूचियों को प्राथमिकता दी जाती है, अपितु ग्राफ़ सघन होने पर आसन्नता आव्यूह को प्राथमिकता दी जाती है; अर्थात् किनारों की संख्या |E| वर्ग शीर्षों की संख्या |V|² के समीप है, या यदि दो शीर्षों को जोड़ने वाला कोई किनारा है तो किसी को तुरंत देखने में सक्षम होना चाहिए।^[5]^[6]

समानान्तर निरूपण

ग्राफ समस्याओं के समानांतरीकरण में महत्वपूर्ण चुनौतियों डेटा-संचालित गणना, असंरचित समस्याएं, व्यर्थ स्थानीयता एवं गणना अनुपात तक उच्च डेटा पहुंच का सामना करना पड़ता है।^[7]^[8] समानांतर आर्किटेक्चर के लिए उपयोग किया जाने वाला ग्राफ़ प्रतिनिधित्व उन चुनौतियों का सामना करने में महत्वपूर्ण भूमिका निभाता है। व्यर्थ उपाय से चयन किए गए प्रतिनिधित्व एल्गोरिदम की संचार लागत को अनावश्यक रूप से बढ़ा सकते हैं, जिससे इसकी स्केलेबिलिटी कम हो जाती है। निम्नलिखित में, भाग एवं वितरित स्मृति आर्किटेक्चर पर विचार किया जाता है।

शेयर्ड स्मृति

शेयर्ड स्मृति प्रारूप के विषय में, समानांतर प्रसंस्करण के लिए उपयोग किए जाने वाले ग्राफ़ प्रतिनिधित्व अनुक्रमिक विषय के समान हैं,^[9] चूंकि ग्राफ़ प्रतिनिधित्व (उदाहरण के लिए आसन्न सूची) तक समानांतर पढ़ने-योग्य पहुंच शेयर्ड स्मृति में कुशल है।

वितरित स्मृति

वितरित स्मृति प्रारूप में, सामान्य दृष्टिकोण शीर्ष सेट $V$ के अंदर $p$ सेट को $V_{0},\dots ,V_{p-1}$ ग्राफ़ विभाजन करना है। यहाँ, $p$ उपलब्ध प्रसंस्करण तत्वों (PE) की मात्रा है। शीर्ष सेट विभाजन को मिलान सूचकांक के साथ PE में, इसके अतिरिक्त संबंधित किनारों पर भी वितरित किया जाता है। प्रत्येक PE का स्वयं का सबग्राफ प्रतिनिधित्व होता है, जहां दूसरे विभाजन में समापन बिंदु वाले किनारों पर विशेष ध्यान देने की आवश्यकता होती है। संदेश पासिंग इंटरफ़ेस जैसे मानक संचार इंटरफेस के लिए, अन्य समापन बिंदु के मालिक PE की आईडी पहचान योग्य होनी चाहिए। वितरित ग्राफ एल्गोरिदम में गणना के समय, इन किनारों के साथ जानकारी पारित करने से संचार का तात्पर्य होता है।^[9]

ग्राफ़ विभाजन को सावधानीपूर्वक करने की आवश्यकता है - कम संचार एवं समान आकार के विभाजन के मध्य समझौता है^[10] किन्तु ग्राफ़ को विभाजित करना एनपी-हार्ड समस्या है, इसलिए उनकी गणना करना संभव नहीं है। इसके अतिरिक्त, निम्नलिखित अनुमानों का उपयोग किया जाता है।

1डी विभाजन: प्रत्येक प्रोसेसर को $n/p$ शीर्ष एवं संगत आउटगोइंग शीर्ष मिलता है। इसे आसन्न आव्यूह के पंक्ति-वार या स्तंभ-वार अपघटन के रूप में समझा जा सकता है। इस प्रतिनिधित्व पर कार्य करने वाले एल्गोरिदम के लिए, इसके लिए ऑल-टू-ऑल संचार चरण की भी आवश्यकता होती है ${\mathcal {O}}(m)$ संदेश बफ़र आकार, क्योंकि प्रत्येक PE में संभावित रूप से हर दूसरे PE के लिए आउटगोइंग शीर्ष होते हैं।^[11]2डी विभाजन: प्रत्येक प्रोसेसर को आसन्न आव्यूह का सबआव्यूह मिलता है। मान लें कि प्रोसेसर आयत $p=p_{r}\times p_{c}$ में संरेखित हैं, जहाँ $p_{r}$ एवं $p_{c}$ क्रमशः प्रत्येक पंक्ति एवं स्तंभ में प्रसंस्करण तत्वों की मात्रा है। फिर प्रत्येक प्रोसेसर को $(n/p_{r})\times (n/p_{c})$ आयाम के आसन्न आव्यूह का सबआव्यूह मिलता है। इसे आव्यूह में बिसात पैटर्न के रूप में देखा जा सकता है।^[11]इसलिए, प्रत्येक प्रसंस्करण इकाई में केवल ही पंक्ति एवं स्तंभ में PE के लिए आउटगोइंग शीर्ष हो सकते हैं। यह प्रत्येक PE के लिए संचार भागीदारों की $p_{r}+p_{c}-1$ से बाहर $p=p_{r}\times p_{c}$ संभव वाले संख्या को सीमित करता है।

संकुचित अभ्यावेदन

यंत्र अधिगम, सोशल नेटवर्क विश्लेषण एवं अन्य क्षेत्रों में खरबों किनारों वाले ग्राफ़ पाए जाते हैं। 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.

[gt-ops-1] 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.

[2] Cormen et al. (2001), pp. 528–529; Goodrich & Tamassia (2015), pp. 361-362.

[3] Cormen et al. (2001), pp. 529–530; Goodrich & Tamassia (2015), p. 363.

[4] Cormen et al. (2001), Exercise 22.1-7, p. 531.

[clrs-5] 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.

[gt-6] Goodrich, Michael T.; Tamassia, Roberto (2015). "Section 13.1: Graph terminology and representations". एल्गोरिथम डिज़ाइन और अनुप्रयोग. Wiley. pp. 355–364. ISBN 978-1-118-33591-8.

[Bader2013-7] 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.

[8] Lumsdaine, Andrew; Gregor, Douglas; Hendrickson, Bruce; Berry, Jonathan (March 2007). "समानांतर ग्राफ़ प्रसंस्करण में चुनौतियाँ". Parallel Processing Letters. 17 (1): 5–20. doi:10.1142/s0129626407002843. ISSN 0129-6264.

[Sanders2019-9] 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.

[10] "ग्राफ़ का समानांतर प्रसंस्करण" (PDF).

[Buluc2011-11] 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.

[12] Besta, Maciej; Hoefler, Torsten (27 April 2019). "दोषरहित ग्राफ संपीड़न और अंतरिक्ष-कुशल ग्राफ प्रतिनिधित्व का सर्वेक्षण और वर्गीकरण". arXiv:1806.01799 [cs.DS].

[Purti-13] 13.0 ^13.1 Purti (July–September 2018). "ग्राफ ट्रैवर्सल और उसके अनुप्रयोग" (PDF). International Journal of Research and Analytical Reviews. 5 (3): 2.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

@@ 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=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 | स्केलेबिलिटी]] कम हो जाती है। निम्नलिखित में, भाग एवं वितरित स्मृति आर्किटेक्चर पर विचार किया जाता है।
 === शेयर्ड स्मृति ===
@@ Line 86: / Line 86: @@
 ग्राफ़ विभाजन को सावधानीपूर्वक करने की आवश्यकता है - कम संचार एवं समान आकार के विभाजन के मध्य समझौता है<ref>{{cite web |title=ग्राफ़ का समानांतर प्रसंस्करण|url=https://www.graphengine.io/downloads/papers/ParallelProcessingOfGraphs.pdf}}</ref>  किन्तु ग्राफ़ को विभाजित करना एनपी-हार्ड समस्या है, इसलिए उनकी गणना करना संभव नहीं है। इसके अतिरिक्त, निम्नलिखित अनुमानों का उपयोग किया जाता है।
-डी विभाजन: प्रत्येक प्रोसेसर को <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
+डी विभाजन: प्रत्येक प्रोसेसर को <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
 </math> एवं <math>p_c
 </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> संभव वाले संख्या को सीमित करता है।
@@ Line 92: / Line 92: @@
 ==संकुचित अभ्यावेदन==
-[[ यंत्र अधिगम ]], सोशल नेटवर्क विश्लेषण एवं अन्य क्षेत्रों में खरबों किनारों वाले ग्राफ़ पाए जाते हैं। 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>
+[[ यंत्र अधिगम | यंत्र अधिगम]], सोशल नेटवर्क विश्लेषण एवं अन्य क्षेत्रों में खरबों किनारों वाले ग्राफ़ पाए जाते हैं। 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>
 == ग्राफ़ ट्रैवर्सल रणनीतियाँ ==
-=== चौड़ाई पहली खोज ===
+=== पहले चौड़ाई शोधो ===
-चौड़ाई-प्रथम खोज (बीएफएस) ट्रैवर्सल दृष्टिकोण है जिसका उपयोग किसी दिए गए ग्राफ़ में सभी नोड्स की खोज के लिए किया जाता है। यह ट्रैवर्सल तकनीक व्यक्तिगत नोड चुनती है, फिर समय में उसके प्रत्येक पड़ोसी का पता लगाती है। यह अतिरिक्त शीर्षों का निरीक्षण करना जारी रखता है एवं उन्हें पूरा करने के बाद आस-पास के सभी शीर्षों के लिए प्रक्रिया को दोहराता है।<ref name="Purti">{{cite journal |author=Purti |date=July–September 2018 |title=ग्राफ ट्रैवर्सल और उसके अनुप्रयोग|journal=International Journal of Research and Analytical Reviews |volume=5 |issue=3 |page=2 |url=http://ijrar.com/upload_issue/ijrar_issue_1836.pdf}}</ref>
+चौड़ाई-प्रथम शोध (बीएफएस) ट्रैवर्सल दृष्टिकोण है जिसका उपयोग किसी दिए गए ग्राफ़ में सभी नोड्स की शोध के लिए किया जाता है। यह ट्रैवर्सल तकनीक व्यक्तिगत नोड चुनती है, फिर समय में उसके प्रत्येक पड़ोसी का को ज्ञात करती है। यह अतिरिक्त शीर्षों का निरीक्षण करना निरंतर रखता है एवं उन्हें पूर्ण करने के पश्चात निकटवर्ती शीर्षों के लिए प्रक्रिया को दोहराता है।<ref name="Purti">{{cite journal |author=Purti |date=July–September 2018 |title=ग्राफ ट्रैवर्सल और उसके अनुप्रयोग|journal=International Journal of Research and Analytical Reviews |volume=5 |issue=3 |page=2 |url=http://ijrar.com/upload_issue/ijrar_issue_1836.pdf}}</ref>
-=== गहराई पहली खोज ===
+=== गहराई पहली शोध ===
-गहराई-प्रथम खोज एल्गोरिदम के विषय में नए शीर्ष की खोज किसी भी बिंदु पर शुरू होती है। इस नए शीर्ष की जांच के बाद, चयनित शीर्ष की जांच जारी रहती है। जब सभी पहुंच योग्य शिखरों का गहन अन्वेषण कर लिया जाता है, तो खोज समाप्त हो जाती है। पुनरावर्ती उपाय से प्रस्तुत किए जाने पर यह खोज प्रक्रिया सबसे अच्छा काम करती है। डीएफएस ऐसी विधि का उपयोग करता है जो जब भी संभव हो ग्राफ़ का गहराई से अन्वेषण करता है। क्योंकि खोज कई स्रोतों से दोहराई जा सकती है, डीएफएस द्वारा बनाया गया पूर्ववर्ती सबग्राफ विभिन्न पेड़ों से बना हो सकता है।
+गहराई-प्रथम शोध एल्गोरिदम के विषय में नए शीर्ष की शोध किसी भी बिंदु पर प्रारम्भ होती है। इस नए शीर्ष की शोध के पश्चात, चयनित शीर्ष की शोध निरंतर रहती है। जब सभी पहुंच योग्य शिखरों का गहन अन्वेषण कर लिया जाता है, तो शोध समाप्त हो जाती है। पुनरावर्ती उपाय से प्रस्तुत किए जाने पर यह शोध प्रक्रिया उत्तम कार्य करती है। डीएफएस ऐसी विधि का उपयोग करता है जो जब भी संभव हो ग्राफ़ का गहराई से अन्वेषण करता है। क्योंकि शोध कई स्रोतों से दोहराई जा सकती है, डीएफएस द्वारा बनाया गया पूर्ववर्ती सबग्राफ विभिन्न पेड़ों से बना हो सकता है।
   <ref name="Purti" />

v t e Graph representations
Data structures	Graph (abstract data type) Adjacency list Edge list Adjacency matrix Incidence matrix
XML-based formats	DGML DotML GEXF GraphML GXL XGMML
Text-based formats	DOT Graph Modelling Language (GML) LCF notation for cubic Hamiltonian graphs Newick format for trees Trivial Graph Format
Related concepts	Graph database Graph drawing Linked data

v t e Well-known data structures
Types	Collection Container
Abstract	Associative array Multimap Retrieval Data Structure List Stack Queue Double-ended queue Priority queue Double-ended priority queue Set Multiset Disjoint-set
Arrays	Bit array Circular buffer Dynamic array Hash table Hashed array tree Sparse matrix
Linked	Association list Linked list Skip list Unrolled linked list XOR linked list
Trees	B-tree Binary search tree AA tree AVL tree Red–black tree Self-balancing tree Splay tree Heap Binary heap Binomial heap Fibonacci heap R-tree R* tree R+ tree Hilbert R-tree Trie Hash tree
Graphs	Binary decision diagram Directed acyclic graph Directed acyclic word graph
List of data structures

Anonymous

Search

ग्राफ़ (सार डेटा प्रकार): Difference between revisions

Namespaces

More

Page actions

Revision as of 23:56, 18 July 2023

Contents

संचालन

ग्राफ़ प्रतिनिधित्व के लिए सामान्य डेटा संरचनाएँ