बल-निर्देशित ग्राफ़ आरेखण: Difference between revisions

From Vigyanwiki
No edit summary
No edit summary
Line 1: Line 1:
{{Short description|Physical simulation to visualize graphs}}
{{Short description|Physical simulation to visualize graphs}}
[[File:SocialNetworkAnalysis.png|250px|right|thumb|बल-निर्देशित ग्राफ़ ड्राइंग एल्गोरिदम का उपयोग करके सामाजिक नेटवर्क विज़ुअलाइज़ेशन<ref>{{citation|first=Martin|last=Grandjean|contribution=Introduction à la visualisation de données, l'analyse de réseau en histoire|year=2015|title=Geschichte und Informatik 18/19|pages=109–128|url=http://www.martingrandjean.ch/wp-content/uploads/2015/09/Grandjean2015.pdf}}</ref>]][[Image:Visualization of wiki structure using prefuse visualization package.png|250px|right|thumb|बल-निर्देशित लेआउट का उपयोग करके विकी पर पृष्ठों के मध्य लिंक का विज़ुअलाइज़ेशन]]'''बल-निर्देशित''' [[ग्राफ ड्राइंग]] [[कलन विधि]] सौंदर्य-सुखदायक विधि से ग्राफ़ ड्राइंग के लिए एल्गोरिदम का वर्ग माना जाता है। उनका उद्देश्य ग्राफ़ (अलग-अलग गणित) के नोड्स को दो-आयामी या त्रि-आयामी अंतरिक्ष में स्थित करना होता है किंतु सभी किनारे कम या अधिक समान लंबाई के हों और जितना संभव हो उतना कम क्रॉसिंग किनारे हों, मध्य में बल निर्दिष्ट करके किनारों का समुच्चय और नोड्स का समुच्चय , उनकी सापेक्ष स्थिति के आधार पर, और फिर इन बलों का उपयोग या तो किनारों और नोड्स की गति को अनुकरण करने या उनकी ऊर्जा को कम करने के लिए किया जाता है।<ref>{{citation|first=Stephen G.|last=Kobourov|title=Spring Embedders and Force-Directed Graph Drawing Algorithms|year=2012|arxiv=1201.3011|bibcode=2012arXiv1201.3011K}}.</ref>
[[File:SocialNetworkAnalysis.png|250px|right|thumb|बल-निर्देशित ग्राफ़ ड्राइंग एल्गोरिदम का उपयोग करके सामाजिक नेटवर्क विज़ुअलाइज़ेशन<ref>{{citation|first=Martin|last=Grandjean|contribution=Introduction à la visualisation de données, l'analyse de réseau en histoire|year=2015|title=Geschichte und Informatik 18/19|pages=109–128|url=http://www.martingrandjean.ch/wp-content/uploads/2015/09/Grandjean2015.pdf}}</ref>]][[Image:Visualization of wiki structure using prefuse visualization package.png|250px|right|thumb|बल-निर्देशित लेआउट का उपयोग करके विकी पर पृष्ठों के मध्य लिंक का विज़ुअलाइज़ेशन]]'''बल-निर्देशित''' [[ग्राफ ड्राइंग]] [[कलन विधि]] सौंदर्य-सुखदायक विधि से ग्राफ़ ड्राइंग के लिए एल्गोरिदम का वर्ग माना जाता है। उनका उद्देश्य ग्राफ़ (अलग-अलग गणित) के नोड्स को दो-आयामी या त्रि-आयामी अंतरिक्ष में स्थित करना होता है किंतु सभी किनारे कम या अधिक समान लंबाई के हों और जितना संभव हो उतना कम क्रॉसिंग किनारे हों, मध्य में बल निर्दिष्ट करके किनारों का समुच्चय और नोड्स का समुच्चय , उनकी सापेक्ष स्थिति के आधार पर, और फिर इन बलों का उपयोग या तो किनारों और नोड्स की गति को अनुकरण करने या उनकी ऊर्जा को कम करने के लिए किया जाता है।<ref>{{citation|first=Stephen G.|last=Kobourov|title=Spring Embedders and Force-Directed Graph Drawing Algorithms|year=2012|arxiv=1201.3011|bibcode=2012arXiv1201.3011K}}.</ref>
इस प्रकार से जबकि ग्राफ़ बनाना कठिन समस्या हो सकती है, और बल-निर्देशित एल्गोरिदम, भौतिक सिमुलेशन होने के कारण, सामान्यतः ग्राफ़ सिद्धांत जैसे कि [[समतलीय ग्राफ]] के बारे में किसी विशेष ज्ञान की आवश्यकता नहीं होती है।
इस प्रकार से जबकि ग्राफ़ बनाना कठिन समस्या हो सकती है, और बल-निर्देशित एल्गोरिदम, भौतिक सिमुलेशन होने के कारण, सामान्यतः ग्राफ़ सिद्धांत जैसे कि [[समतलीय ग्राफ]] के बारे में किसी विशेष ज्ञान की आवश्यकता नहीं होती है।


==बल==
==बल==
बल-निर्देशित ग्राफ़ ड्राइंग एल्गोरिदम किनारों के समुच्चय और ग्राफ़ ड्राइंग के नोड्स के समुच्चय के मध्य बल निर्दिष्ट करते हैं। सामान्यतः , हुक के नियम पर आधारित [[वसंत (उपकरण)]]जैसे आकर्षक बलों का उपयोग ग्राफ के किनारों के अंतिम बिंदुओं के जोड़े को एक-दूसरे की ओर आकर्षित करने के लिए किया जाता है, जबकि साथ ही कूलम्ब के नियम के आधार पर विद्युत आवेश कणों जैसे प्रतिकारक बलों का उपयोग सभी जोड़े को अलग करने के लिए किया जाता है। नोड्स. बलों की इस प्रणाली के लिए [[यांत्रिक संतुलन]] में, किनारों की लंबाई समान होती है (स्प्रिंग बलों के कारण), और जो नोड्स किनारे से नहीं जुड़े होते हैं वे और अधिक दूर खींचे जाते हैं (विद्युत प्रतिकर्षण के कारण)। किनारे के आकर्षण और शीर्ष प्रतिकर्षण बलों को उन कार्यों का उपयोग करके परिभाषित किया जा सकता है जोकी स्प्रिंग्स और कणों के भौतिक व्यवहार पर आधारित नहीं होते हैं; इस प्रकार से उदाहरण के लिए, कुछ बल-निर्देशित प्रणालियाँ स्प्रिंग्स का उपयोग करती हैं जिनका आकर्षक बल रैखिक के अतिरिक्त लघुगणकीय होता है।
बल-निर्देशित ग्राफ़ ड्राइंग एल्गोरिदम किनारों के समुच्चय और ग्राफ़ ड्राइंग के नोड्स के समुच्चय के मध्य बल निर्दिष्ट करते हैं। सामान्यतः , हुक के नियम पर आधारित [[वसंत (उपकरण)]]जैसे आकर्षक बलों का उपयोग ग्राफ के किनारों के अंतिम बिंदुओं के जोड़े को एक-दूसरे की ओर आकर्षित करने के लिए किया जाता है, जबकि साथ ही कूलम्ब के नियम के आधार पर विद्युत आवेश कणों जैसे प्रतिकारक बलों का उपयोग सभी जोड़े को अलग करने के लिए किया जाता है। नोड्स. बलों की इस प्रणाली के लिए [[यांत्रिक संतुलन]] में, किनारों की लंबाई समान होती है (स्प्रिंग बलों के कारण), और जो नोड्स किनारे से नहीं जुड़े होते हैं वे और अधिक दूर खींचे जाते हैं (विद्युत प्रतिकर्षण के कारण)। किनारे के आकर्षण और शीर्ष प्रतिकर्षण बलों को उन कार्यों का उपयोग करके परिभाषित किया जा सकता है जोकी स्प्रिंग्स और कणों के भौतिक व्यवहार पर आधारित नहीं होते हैं; इस प्रकार से उदाहरण के लिए, कुछ बल-निर्देशित प्रणालियाँ स्प्रिंग्स का उपयोग करती हैं जिनका आकर्षक बल रैखिक के अतिरिक्त लघुगणकीय होता है।


इस प्रकार   वैकल्पिक मॉडल प्रत्येक जोड़ी नोड्स के लिए स्प्रिंग-जैसे बल <math>(i,j)</math> पर विचार करता है जहां <math>\delta_{ij}</math> आदर्श लंबाई है प्रत्येक स्प्रिंग का मान अलग प्रतिकारक बल का उपयोग किए बिना, नोड्स i और j के मध्य ग्राफ-सैद्धांतिक दूरी के समानुपाती होता है। [[यूक्लिडियन दूरी]] और नोड्स के मध्य आदर्श दूरी के मध्य अंतर (सामान्यतः वर्ग अंतर) को कम करना मीट्रिक [[बहुआयामी स्केलिंग]] समस्या के समान है।
इस प्रकार वैकल्पिक मॉडल प्रत्येक जोड़ी नोड्स के लिए स्प्रिंग-जैसे बल <math>(i,j)</math> पर विचार करता है जहां <math>\delta_{ij}</math> आदर्श लंबाई है प्रत्येक स्प्रिंग का मान अलग प्रतिकारक बल का उपयोग किए बिना, नोड्स i और j के मध्य ग्राफ-सैद्धांतिक दूरी के समानुपाती होता है। [[यूक्लिडियन दूरी]] और नोड्स के मध्य आदर्श दूरी के मध्य अंतर (सामान्यतः वर्ग अंतर) को कम करना मीट्रिक [[बहुआयामी स्केलिंग]] समस्या के समान है।


बल-निर्देशित ग्राफ़ में यांत्रिक स्प्रिंग्स और विद्युत प्रतिकर्षण के अलावा अन्य बल सम्मिलित हो सकते हैं। गुरुत्वाकर्षण के अनुरूप बल का उपयोग शीर्षों को ड्राइंग स्थान के निश्चित बिंदु की ओर खींचने के लिए किया जा सकता है; इसका उपयोग डिस्कनेक्ट किए गए ग्राफ़ के विभिन्न कनेक्टेड घटकों (ग्राफ़ सिद्धांत) को साथ खींचने के लिए किया जा सकता है, जो अन्यथा प्रतिकारक बलों के कारण एक-दूसरे से अलग हो जाते हैं, और ड्राइंग में अधिक केंद्रीय पदों पर अधिक केंद्रीयता वाले नोड्स खींचने के लिए उपयोग किया जा सकता है। ;<ref>{{citation|contribution=Force-directed graph drawing using social gravity and scaling|first1=M. J.|last1=Bannister|first2=D.|last2=Eppstein|author2-link=David Eppstein|first3=M. T.|last3=Goodrich|author3-link=Michael T. Goodrich|first4=L.|last4=Trott|arxiv=1209.0748|title=Proc. 20th Int. Symp. Graph Drawing|year=2012|bibcode=2012arXiv1209.0748B}}.</ref> यह घटक के अन्दर शीर्ष रिक्ति को भी प्रभावित कर सकता है। निर्देशित ग्राफ़ के लिए [[चुंबकीय क्षेत्र]] के एनालॉग्स का उपयोग किया जा सकता है। अंतिम ड्राइंग में ओवरलैप या निकट-ओवरलैप से बचने के लिए किनारों के साथ-साथ नोड्स पर भी प्रतिकारक बल लगाए जा सकते हैं। घुमावदार किनारों वाले रेखाचित्रों जैसे कि वृत्ताकार चाप या [[तख़्ता वक्र|स्प्प्लाईन]] में, इन वक्रों के नियंत्रण बिंदुओं पर बल भी लगाए जा सकते हैं, इस प्रकार से उदाहरण के लिए उनके कोणीय रिज़ॉल्यूशन (ग्राफ़ ड्राइंग) में सुधार करने के लिए किया जाता है ।<ref>{{citation|first1=R.|last1=Chernobelskiy|first2=K.|last2=Cunningham|first3=M. T.|last3=Goodrich|author3-link=Michael T. Goodrich|first4=S. G.|last4=Kobourov|first5=L.|last5=Trott|contribution=Force-directed Lombardi-style graph drawing|title=Proc. 19th Symposium on Graph Drawing|pages=78–90|year=2011|url=http://www.cs.arizona.edu/~kobourov/fdl.pdf}}.</ref>
बल-निर्देशित ग्राफ़ में यांत्रिक स्प्रिंग्स और विद्युत प्रतिकर्षण के अलावा अन्य बल सम्मिलित हो सकते हैं। गुरुत्वाकर्षण के अनुरूप बल का उपयोग शीर्षों को ड्राइंग स्थान के निश्चित बिंदु की ओर खींचने के लिए किया जा सकता है; इसका उपयोग डिस्कनेक्ट किए गए ग्राफ़ के विभिन्न कनेक्टेड घटकों (ग्राफ़ सिद्धांत) को साथ खींचने के लिए किया जा सकता है, जो अन्यथा प्रतिकारक बलों के कारण एक-दूसरे से अलग हो जाते हैं, और ड्राइंग में अधिक केंद्रीय पदों पर अधिक केंद्रीयता वाले नोड्स खींचने के लिए उपयोग किया जा सकता है। ;<ref>{{citation|contribution=Force-directed graph drawing using social gravity and scaling|first1=M. J.|last1=Bannister|first2=D.|last2=Eppstein|author2-link=David Eppstein|first3=M. T.|last3=Goodrich|author3-link=Michael T. Goodrich|first4=L.|last4=Trott|arxiv=1209.0748|title=Proc. 20th Int. Symp. Graph Drawing|year=2012|bibcode=2012arXiv1209.0748B}}.</ref> यह घटक के अन्दर शीर्ष रिक्ति को भी प्रभावित कर सकता है। निर्देशित ग्राफ़ के लिए [[चुंबकीय क्षेत्र]] के एनालॉग्स का उपयोग किया जा सकता है। अंतिम ड्राइंग में ओवरलैप या निकट-ओवरलैप से बचने के लिए किनारों के साथ-साथ नोड्स पर भी प्रतिकारक बल लगाए जा सकते हैं। घुमावदार किनारों वाले रेखाचित्रों जैसे कि वृत्ताकार चाप या [[तख़्ता वक्र|स्प्प्लाईन]] में, इन वक्रों के नियंत्रण बिंदुओं पर बल भी लगाए जा सकते हैं, इस प्रकार से उदाहरण के लिए उनके कोणीय रिज़ॉल्यूशन (ग्राफ़ ड्राइंग) में सुधार करने के लिए किया जाता है ।<ref>{{citation|first1=R.|last1=Chernobelskiy|first2=K.|last2=Cunningham|first3=M. T.|last3=Goodrich|author3-link=Michael T. Goodrich|first4=S. G.|last4=Kobourov|first5=L.|last5=Trott|contribution=Force-directed Lombardi-style graph drawing|title=Proc. 19th Symposium on Graph Drawing|pages=78–90|year=2011|url=http://www.cs.arizona.edu/~kobourov/fdl.pdf}}.</ref>
==विधि ==
==विधि ==
वर्तमान समय में ग्राफ़ के नोड्स और किनारों पर बलों को परिभाषित किया गया है, तो इन स्रोतों के तहत पूरे ग्राफ़ का व्यवहार तब अनुकरण किया जा सकता है जैसे कि यह भौतिक प्रणाली थी। इस प्रकार से   अनुकरण में, बलों को नोड्स पर प्रस्तुत किया जाता है, उन्हें अपनी ओर खींचा जाता है या उन्हें और दूर धकेल दिया जाता है। इसे तब तक दोहराया जाता है जब तक कि प्रणाली यांत्रिक संतुलन स्थिति में नहीं आ जाता; अर्थात , उनकी सापेक्ष स्थिति पुनरावृत्ति से दूसरी पुनरावृत्ति में नहीं परिवर्तित होती रहती है। इस संतुलन में नोड्स की स्थिति का उपयोग ग्राफ का चित्र बनाने के लिए किया जाता है।
वर्तमान समय में ग्राफ़ के नोड्स और किनारों पर बलों को परिभाषित किया गया है, तो इन स्रोतों के तहत पूरे ग्राफ़ का व्यवहार तब अनुकरण किया जा सकता है जैसे कि यह भौतिक प्रणाली थी। इस प्रकार से अनुकरण में, बलों को नोड्स पर प्रस्तुत किया जाता है, उन्हें अपनी ओर खींचा जाता है या उन्हें और दूर धकेल दिया जाता है। इसे तब तक दोहराया जाता है जब तक कि प्रणाली यांत्रिक संतुलन स्थिति में नहीं आ जाता; अर्थात , उनकी सापेक्ष स्थिति पुनरावृत्ति से दूसरी पुनरावृत्ति में नहीं परिवर्तित होती रहती है। इस संतुलन में नोड्स की स्थिति का उपयोग ग्राफ का चित्र बनाने के लिए किया जाता है।


इस प्रकार से स्प्रिंग्स से परिभाषित बलों के लिए जिनकी आदर्श लंबाई ग्राफ-सैद्धांतिक दूरी के समानुपाती होती है, तनाव प्रमुखता बहुत सही प्रकार से व्यवहार करती है (अर्थात , अनुक्रम की नीरस सीमा)<ref name="dl88">{{citation
इस प्रकार से स्प्रिंग्स से परिभाषित बलों के लिए जिनकी आदर्श लंबाई ग्राफ-सैद्धांतिक दूरी के समानुपाती होती है, तनाव प्रमुखता बहुत सही प्रकार से व्यवहार करती है (अर्थात , अनुक्रम की नीरस सीमा)<ref name="dl88">{{citation
   | last=de Leeuw | first=Jan
   | last=de Leeuw | first=Jan
   | title=Convergence of the majorization method for multidimensional scaling
   | title=Convergence of the majorization method for multidimensional scaling
Line 22: Line 22:
  }}.</ref> और इन अंतरों को अनुकूलित करने के लिए गणितीय रूप से सुंदर विधि (गणित) और, इसलिए, ग्राफ़ के लिए अच्छा लेआउट ढूंढें।
  }}.</ref> और इन अंतरों को अनुकूलित करने के लिए गणितीय रूप से सुंदर विधि (गणित) और, इसलिए, ग्राफ़ के लिए अच्छा लेआउट ढूंढें।


किंतु ऐसे तंत्रों को नियोजित करना भी संभव है जो भौतिक सिमुलेशन के अतिरिक्त या उसके संयोजन के साथ ऊर्जा मिनिमा के लिए अधिक सीधे खोज करते हैं। ऐसे तंत्र, जोकी सामान्य [[वैश्विक अनुकूलन]] विधियों के उदाहरण हैं, में [[ तैयार किए हुयी धातु पे पानी चढाने की कला |सिम्युलेटेड एनीलिंग]] और आनुवंशिक एल्गोरिदम सम्मिलित हैं।
किंतु ऐसे तंत्रों को नियोजित करना भी संभव है जो भौतिक सिमुलेशन के अतिरिक्त या उसके संयोजन के साथ ऊर्जा मिनिमा के लिए अधिक सीधे खोज करते हैं। ऐसे तंत्र, जोकी सामान्य [[वैश्विक अनुकूलन]] विधियों के उदाहरण हैं, में [[ तैयार किए हुयी धातु पे पानी चढाने की कला |सिम्युलेटेड एनीलिंग]] और आनुवंशिक एल्गोरिदम सम्मिलित हैं।


==लाभ==
==लाभ==
इस प्रकार से बल-निर्देशित एल्गोरिदम के सबसे महत्वपूर्ण लाभों में से निम्नलिखित होते हैं:
इस प्रकार से बल-निर्देशित एल्गोरिदम के सबसे महत्वपूर्ण लाभों में से निम्नलिखित होते हैं:
; उच्च गुणवत्ता वाले परिणाम: कम से कम मध्यम आकार (50-500 शीर्षों तक) के ग्राफ़ के लिए, प्राप्त परिणाम सामान्यतः निम्नलिखित मानदंडों के आधार पर अधिक उच्च परिणाम देते हैं: समान किनारे की लंबाई, समान शीर्ष वितरण और समरूपता दिखया जाता है । यह अंतिम मानदंड सबसे महत्वपूर्ण मानदंडों में से है और किसी अन्य प्रकार के एल्गोरिदम के साथ इसे प्राप्त करना कठिन है।
; उच्च गुणवत्ता वाले परिणाम: कम से कम मध्यम आकार (50-500 शीर्षों तक) के ग्राफ़ के लिए, प्राप्त परिणाम सामान्यतः निम्नलिखित मानदंडों के आधार पर अधिक उच्च परिणाम देते हैं: समान किनारे की लंबाई, समान शीर्ष वितरण और समरूपता दिखया जाता है । यह अंतिम मानदंड सबसे महत्वपूर्ण मानदंडों में से है और किसी अन्य प्रकार के एल्गोरिदम के साथ इसे प्राप्त करना कठिन है।
; लचीलापन: अतिरिक्त सौंदर्य मानदंडों को पूर्ण करने के लिए बल-निर्देशित एल्गोरिदम को सरलता से अनुकूलित और विस्तारित किया जा सकता है। यह उन्हें ग्राफ़ ड्राइंग एल्गोरिदम का सबसे बहुमुखी वर्ग बनाता है। इस प्रकार से उपस्तिथ एक्सटेंशन के उदाहरणों में निर्देशित ग्राफ़, 3डी ग्राफ़ ड्राइंग,<ref>{{cite web|last=Vose|first=Aaron|title=3D Phylogenetic Tree Viewer|url=http://aaronvose.net/phytree3d/|access-date=3 June 2012}}</ref> क्लस्टर ग्राफ़ ड्राइंग, विवश ग्राफ़ ड्राइंग, और गतिशील ग्राफ़ ड्राइंग आदि ।
; लचीलापन: अतिरिक्त सौंदर्य मानदंडों को पूर्ण करने के लिए बल-निर्देशित एल्गोरिदम को सरलता से अनुकूलित और विस्तारित किया जा सकता है। यह उन्हें ग्राफ़ ड्राइंग एल्गोरिदम का सबसे बहुमुखी वर्ग बनाता है। इस प्रकार से उपस्तिथ एक्सटेंशन के उदाहरणों में निर्देशित ग्राफ़, 3डी ग्राफ़ ड्राइंग,<ref>{{cite web|last=Vose|first=Aaron|title=3D Phylogenetic Tree Viewer|url=http://aaronvose.net/phytree3d/|access-date=3 June 2012}}</ref> क्लस्टर ग्राफ़ ड्राइंग, विवश ग्राफ़ ड्राइंग, और गतिशील ग्राफ़ ड्राइंग आदि ।
; सहज : चूंकि वे स्प्रिंग्स जैसी सामान्य वस्तुओं की भौतिक सादृश्यता पर आधारित होते हैं, इसलिए एल्गोरिदम के व्यवहार की भविष्यवाणी करना और समझना अपेक्षाकृत सरल होते है। अन्य प्रकार के ग्राफ़ ड्राइंग|ग्राफ़-ड्राइंग एल्गोरिदम के स्तिथि में ऐसा नहीं होता है।
; सहज : चूंकि वे स्प्रिंग्स जैसी सामान्य वस्तुओं की भौतिक सादृश्यता पर आधारित होते हैं, इसलिए एल्गोरिदम के व्यवहार की भविष्यवाणी करना और समझना अपेक्षाकृत सरल होते है। अन्य प्रकार के ग्राफ़ ड्राइंग|ग्राफ़-ड्राइंग एल्गोरिदम के स्तिथि में ऐसा नहीं होता है।
; सरलता: विशिष्ट बल-निर्देशित एल्गोरिदम सरल होते हैं और इन्हें कोड की कुछ पंक्तियों में प्रस्तुत किया जा सकता है। ग्राफ़-ड्राइंग एल्गोरिदम के अन्य वर्ग, जैसे ऑर्थोगोनल लेआउट के लिए, सामान्यतः बहुत अधिक सम्मिलित होते हैं।
; सरलता: विशिष्ट बल-निर्देशित एल्गोरिदम सरल होते हैं और इन्हें कोड की कुछ पंक्तियों में प्रस्तुत किया जा सकता है। ग्राफ़-ड्राइंग एल्गोरिदम के अन्य वर्ग, जैसे ऑर्थोगोनल लेआउट के लिए, सामान्यतः बहुत अधिक सम्मिलित होते हैं।
; अन्तरक्रियाशीलता: एल्गोरिदम के इस वर्ग का एक अन्य लाभ इंटरैक्टिव भाग है। ग्राफ़ के मध्यवर्ती चरणों को चित्रित करके, उपयोगकर्ता यह देख सकता है कि ग्राफ़ कैसे विकसित होता है, इसे एक उलझी हुई गड़बड़ी से एक अच्छे दिखने वाले कॉन्फ़िगरेशन में प्रकट होते हुए देख सकता है। कुछ इंटरैक्टिव ग्राफ़ ड्राइंग टूल में, उपयोगकर्ता एक या एक से अधिक नोड्स को उनकी संतुलन स्थिति से बाहर खींच सकता है और उन्हें वापस स्थिति में स्थानांतरित होते हुए देख सकता है। यह उन्हें गतिशील और [[ऑनलाइन एल्गोरिदम]] ग्राफ़-ड्राइंग प्रणाली के लिए मुख्य विकल्प बनाता है।
; अन्तरक्रियाशीलता: एल्गोरिदम के इस वर्ग का एक अन्य लाभ इंटरैक्टिव भाग है। ग्राफ़ के मध्यवर्ती चरणों को चित्रित करके, उपयोगकर्ता यह देख सकता है कि ग्राफ़ कैसे विकसित होता है, इसे एक उलझी हुई गड़बड़ी से एक अच्छे दिखने वाले कॉन्फ़िगरेशन में प्रकट होते हुए देख सकता है। कुछ इंटरैक्टिव ग्राफ़ ड्राइंग टूल में, उपयोगकर्ता एक या एक से अधिक नोड्स को उनकी संतुलन स्थिति से बाहर खींच सकता है और उन्हें वापस स्थिति में स्थानांतरित होते हुए देख सकता है। यह उन्हें गतिशील और [[ऑनलाइन एल्गोरिदम]] ग्राफ़-ड्राइंग प्रणाली के लिए मुख्य विकल्प बनाता है।
; कठोर सैद्धांतिक आधार: जबकि सरल तदर्थ बल-निर्देशित एल्गोरिदम अक्सर साहित्य और व्यवहार में दिखाई देते हैं (क्योंकि उन्हें समझना अपेक्षाकृत सरल है), अधिक तर्कसंगत दृष्टिकोण लोकप्रियता प्राप्त करना प्रारंभ कर रहे हैं। सांख्यिकीविद् 1930 के दशक से बहुआयामी स्केलिंग (एमडीएस) में समान समस्याओं को हल कर रहे हैं, और भौतिकविदों के पास संबंधित ए[[ एन शरीर | एन बॉडी]] समस्याओं के साथ काम करने का लंबा इतिहास भी है - इसलिए अधिक परिपक्व दृष्टिकोण उपस्तिथ हैं। उदाहरण के तौर पर, मीट्रिक एमडीएस के लिए तनाव प्रमुखीकरण दृष्टिकोण को ऊपर वर्णित अनुसार ग्राफ ड्राइंग पर प्रस्तुत किया जा सकता है। यह [[मोनोटोन अभिसरण प्रमेय]] से सिद्ध हो चुका है।<ref name="dl88"/> मोनोटोनिक अभिसरण, वह गुण जो एल्गोरिदम प्रत्येक पुनरावृत्ति पर लेआउट के तनाव या व्यय को कम करेगा, इस प्रकार से यह महत्वपूर्ण है क्योंकि यह प्रमाण देता है कि लेआउट अंततः स्थानीय न्यूनतम तक पहुंच जाएगा और रुक जाएगा। डंपिंग शेड्यूल के कारण एल्गोरिदम रुक जाता है, जिससे यह प्रत्याभूति नहीं दे सकता कि वास्तविक स्थानीय न्यूनतम तक पहुंच गया है।
; कठोर सैद्धांतिक आधार: जबकि सरल तदर्थ बल-निर्देशित एल्गोरिदम अक्सर साहित्य और व्यवहार में दिखाई देते हैं (क्योंकि उन्हें समझना अपेक्षाकृत सरल है), अधिक तर्कसंगत दृष्टिकोण लोकप्रियता प्राप्त करना प्रारंभ कर रहे हैं। सांख्यिकीविद् 1930 के दशक से बहुआयामी स्केलिंग (एमडीएस) में समान समस्याओं को हल कर रहे हैं, और भौतिकविदों के पास संबंधित ए[[ एन शरीर | एन बॉडी]] समस्याओं के साथ काम करने का लंबा इतिहास भी है - इसलिए अधिक परिपक्व दृष्टिकोण उपस्तिथ हैं। उदाहरण के तौर पर, मीट्रिक एमडीएस के लिए तनाव प्रमुखीकरण दृष्टिकोण को ऊपर वर्णित अनुसार ग्राफ ड्राइंग पर प्रस्तुत किया जा सकता है। यह [[मोनोटोन अभिसरण प्रमेय]] से सिद्ध हो चुका है।<ref name="dl88"/> मोनोटोनिक अभिसरण, वह गुण जो एल्गोरिदम प्रत्येक पुनरावृत्ति पर लेआउट के तनाव या व्यय को कम करेगा, इस प्रकार से यह महत्वपूर्ण है क्योंकि यह प्रमाण देता है कि लेआउट अंततः स्थानीय न्यूनतम तक पहुंच जाएगा और रुक जाएगा। डंपिंग शेड्यूल के कारण एल्गोरिदम रुक जाता है, जिससे यह प्रत्याभूति नहीं दे सकता कि वास्तविक स्थानीय न्यूनतम तक पहुंच गया है।


==हानि  ==
==हानि  ==
बल-निर्देशित एल्गोरिदम के मुख्य हानि में निम्नलिखित सम्मिलित होते हैं:
बल-निर्देशित एल्गोरिदम के मुख्य हानि में निम्नलिखित सम्मिलित होते हैं:
; उच्च समय जटिलता: विशिष्ट बल-निर्देशित एल्गोरिदम को सामान्यतः घन समय (<math>O(n^3)</math>), में चलने वाला माना जाता है जहाँ <math>n</math> इनपुट ग्राफ़ के नोड्स की संख्या है। ऐसा इसलिए है क्योंकि पुनरावृत्तियों की संख्या रैखिक होने का अनुमान (<math>O(n)</math>), है और प्रत्येक पुनरावृत्ति में, नोड्स के सभी जोड़े का दौरा करने और उनकी पारस्परिक प्रतिकारक शक्तियों की गणना करने की आवश्यकता होती है। यह भौतिकी में [[एन-बॉडी समस्या]] से संबंधित है। , चूँकि प्रतिकारक शक्तियाँ स्थानीय प्रकृति की होती हैं, इसलिए ग्राफ को इस प्रकार विभाजित किया जा सकता है कि केवल प्रतिवेशी शीर्षों पर ही विचार किया जाए। बड़े ग्राफ़ के लेआउट को निर्धारित करने के लिए एल्गोरिदम द्वारा उपयोग की जाने वाली सामान्य विधियों में उच्च-आयामी एम्बेडिंग सम्मिलित होते है,<ref>{{citation
; उच्च समय जटिलता: विशिष्ट बल-निर्देशित एल्गोरिदम को सामान्यतः घन समय (<math>O(n^3)</math>), में चलने वाला माना जाता है जहाँ <math>n</math> इनपुट ग्राफ़ के नोड्स की संख्या है। ऐसा इसलिए है क्योंकि पुनरावृत्तियों की संख्या रैखिक होने का अनुमान (<math>O(n)</math>), है और प्रत्येक पुनरावृत्ति में, नोड्स के सभी जोड़े का दौरा करने और उनकी पारस्परिक प्रतिकारक शक्तियों की गणना करने की आवश्यकता होती है। यह भौतिकी में [[एन-बॉडी समस्या]] से संबंधित है। , चूँकि प्रतिकारक शक्तियाँ स्थानीय प्रकृति की होती हैं, इसलिए ग्राफ को इस प्रकार विभाजित किया जा सकता है कि केवल प्रतिवेशी शीर्षों पर ही विचार किया जाए। बड़े ग्राफ़ के लेआउट को निर्धारित करने के लिए एल्गोरिदम द्वारा उपयोग की जाने वाली सामान्य विधियों में उच्च-आयामी एम्बेडिंग सम्मिलित होते है,<ref>{{citation
   | last1=Harel | first1=David | author1-link = David Harel
   | last1=Harel | first1=David | author1-link = David Harel
   | last2=Koren | first2=Yehuda
   | last2=Koren | first2=Yehuda
Line 42: Line 42:
   | title=Proceedings of the 9th International Symposium on Graph Drawing
   | title=Proceedings of the 9th International Symposium on Graph Drawing
   | pages=207&ndash;219
   | pages=207&ndash;219
   | isbn=3-540-00158-1| citeseerx=10.1.1.20.5390 }}</ref> मल्टी-लेयर ड्राइंग और [[एन-बॉडी सिमुलेशन]] से संबंधित अन्य विधियां। इस प्रकार से उदाहरण के लिए, बार्न्स-हट सिमुलेशन-आधारित विधि एफएडीई <ref name="quigley+eades">{{citation
   | isbn=3-540-00158-1| citeseerx=10.1.1.20.5390 }}</ref> मल्टी-लेयर ड्राइंग और [[एन-बॉडी सिमुलेशन]] से संबंधित अन्य विधियां। इस प्रकार से उदाहरण के लिए, बार्न्स-हट सिमुलेशन-आधारित विधि एफएडीई <ref name="quigley+eades">{{citation
  |last1        = Quigley
  |last1        = Quigley
  |first1      = Aaron
  |first1      = Aaron
Line 54: Line 54:
  |pages        = 197&ndash;210
  |pages        = 197&ndash;210
  |isbn        = 3-540-41554-8
  |isbn        = 3-540-41554-8
  }}.</ref> '''चलने के समय को रैखिक अंकीय बनाने में सुधार कर सकते हैं, या  प्रति पुनरावृत्ति.  मोटे मार्गदर्शक के रूप में, कुछ ही सेकंड में मानक के साथ अधिकतम 1,000 नोड्स खींचने की उम्मीद की जा सकती है <math>n^2</math> प्रति पुनरावृत्ति विधियों , और 100,000 के साथ <math>n\log(n)</math> प्रति पुनरावृत्ति विधियों .बल-निर्देशित एल्गोरिदम, जब ग्राफ़ क्लस्टरिंग दृष्टिकोण के साथ संयुक्त होते हैं, तो लाखों नोड्स के ग्राफ़ खींच सकते हैं।'''  :रनिंग टाइम को लीनियरिथ्मिक या प्रति पुनरावृत्ति <math>n\log(n)</math> में सुधार कर सकते हैं। एक जटिल मार्गदर्शक के रूप में, कुछ ही सेकंड में कोई मानक <math>n^2</math> प्रति पुनरावृत्ति विधियों के साथ अधिकतम 1,000 नोड्स और <math>n\log(n)</math> प्रति पुनरावृत्ति विधियों के साथ 100,000 नोड्स खींचने की उम्मीद कर सकता है। <ref name="quigley+eades" /> बल-निर्देशित एल्गोरिदम, जब ग्राफ क्लस्टरिंग दृष्टिकोण के साथ संयुक्त होते हैं, तो लाखों नोड्स के ग्राफ़ खींच सकते हैं।<ref>{{cite web|title=बड़े ग्राफ़ की एक गैलरी|url=http://yifanhu.net/GALLERY/GRAPHS/|access-date=22 Oct 2017}}</ref>
  }}.</ref> :रनिंग टाइम को लीनियरिथ्मिक या प्रति पुनरावृत्ति <math>n\log(n)</math> में सुधार कर सकते हैं। एक जटिल मार्गदर्शक के रूप में, कुछ ही सेकंड में कोई मानक <math>n^2</math> प्रति पुनरावृत्ति विधियों के साथ अधिकतम 1,000 नोड्स और <math>n\log(n)</math> प्रति पुनरावृत्ति विधियों के साथ 100,000 नोड्स खींचने की उम्मीद कर सकता है। <ref name="quigley+eades" /> बल-निर्देशित एल्गोरिदम, जब ग्राफ क्लस्टरिंग दृष्टिकोण के साथ संयुक्त होते हैं, तो लाखों नोड्स के ग्राफ़ खींच सकते हैं।<ref>{{cite web|title=बड़े ग्राफ़ की एक गैलरी|url=http://yifanhu.net/GALLERY/GRAPHS/|access-date=22 Oct 2017}}</ref>
; निकृष्ट [[स्थानीय न्यूनतम]]: यह देखना सरल होता है कि बल-निर्देशित एल्गोरिदम न्यूनतम ऊर्जा के साथ ग्राफ़ उत्पन्न करते हैं, विशेष रूप से जिसकी कुल ऊर्जा केवल स्थानीय न्यूनतम होती है। पाया गया स्थानीय न्यूनतम, कई स्तिथियों में, वैश्विक न्यूनतम से अधिक निकृष्ट हो सकता है, जो निम्न-गुणवत्ता वाली ड्राइंग में परिवर्तित हो जाता है। कई एल्गोरिदम के लिए, विशेष रूप से वे जो केवल शीर्ष से नीचे की ओर बढ़ने की अनुमति देते हैं, अंतिम परिणाम प्रारंभिक लेआउट से दृढ़ता से प्रभावित हो सकता है, जो कि अधिकतर स्तिथियों में यादृच्छिक रूप से उत्पन्न होता है। जैसे-जैसे ग्राफ़ के शीर्षों की संख्या बढ़ती है, निकृष्ट स्थानीय न्यूनतम की समस्या और अधिक महत्वपूर्ण हो जाती है। विभिन्न एल्गोरिदम का संयुक्त अनुप्रयोग इस समस्या को हल करने में सहायक है।<ref>{{citation
; निकृष्ट [[स्थानीय न्यूनतम]]: यह देखना सरल होता है कि बल-निर्देशित एल्गोरिदम न्यूनतम ऊर्जा के साथ ग्राफ़ उत्पन्न करते हैं, विशेष रूप से जिसकी कुल ऊर्जा केवल स्थानीय न्यूनतम होती है। पाया गया स्थानीय न्यूनतम, कई स्तिथियों में, वैश्विक न्यूनतम से अधिक निकृष्ट हो सकता है, जो निम्न-गुणवत्ता वाली ड्राइंग में परिवर्तित हो जाता है। कई एल्गोरिदम के लिए, विशेष रूप से वे जो केवल शीर्ष से नीचे की ओर बढ़ने की अनुमति देते हैं, अंतिम परिणाम प्रारंभिक लेआउट से दृढ़ता से प्रभावित हो सकता है, जो कि अधिकतर स्तिथियों में यादृच्छिक रूप से उत्पन्न होता है। जैसे-जैसे ग्राफ़ के शीर्षों की संख्या बढ़ती है, निकृष्ट स्थानीय न्यूनतम की समस्या और अधिक महत्वपूर्ण हो जाती है। विभिन्न एल्गोरिदम का संयुक्त अनुप्रयोग इस समस्या को हल करने में सहायक है।<ref>{{citation
  | last1 = Collberg | first1 = Christian
  | last1 = Collberg | first1 = Christian
  | last2 = Kobourov | first2 = Stephen
  | last2 = Kobourov | first2 = Stephen
Line 70: Line 70:
  | url = https://www.researchgate.net/publication/2851716
  | url = https://www.researchgate.net/publication/2851716
  | year = 2003| s2cid = 824991
  | year = 2003| s2cid = 824991
  |quote=To achieve an aesthetically pleasing layout of the graph it is also necessary to employ modified Fruchterman–Reingold forces, as the Kamada–Kawai method does not achieve satisfactory methods by itself but rather creates a good approximate layout so that the Fruchterman-Reingold calculations can quickly "tidy up" the layout.}}</ref> इस प्रकार से उदाहरण के लिए, कामदा-कवाई एल्गोरिदम का उपयोग किया जाता है <ref name="kk89" /> और शीघ्रता से उचित प्रारंभिक लेआउट और फिर फ्रूचटरमैन-रींगोल्ड एल्गोरिथम उत्पन्न करने के लिए<ref name="fr91" /> प्रतिवेशी नोड्स की स्थिति में सुधार करने के लिए किया जाता है । वैश्विक न्यूनतम प्राप्त करने की अन्य विधियों बहुस्तरीय दृष्टिकोण का उपयोग किया जाता है।<ref>http://jgaa.info/accepted/2003/Walshaw2003.7.3.pdf A Multilevel Algorithm for Force-Directed
  |quote=To achieve an aesthetically pleasing layout of the graph it is also necessary to employ modified Fruchterman–Reingold forces, as the Kamada–Kawai method does not achieve satisfactory methods by itself but rather creates a good approximate layout so that the Fruchterman-Reingold calculations can quickly "tidy up" the layout.}}</ref> इस प्रकार से उदाहरण के लिए, कामदा-कवाई एल्गोरिदम का उपयोग किया जाता है <ref name="kk89" /> और शीघ्रता से उचित प्रारंभिक लेआउट और फिर फ्रूचटरमैन-रींगोल्ड एल्गोरिथम उत्पन्न करने के लिए<ref name="fr91" /> प्रतिवेशी नोड्स की स्थिति में सुधार करने के लिए किया जाता है । वैश्विक न्यूनतम प्राप्त करने की अन्य विधियों बहुस्तरीय दृष्टिकोण का उपयोग किया जाता है।<ref>http://jgaa.info/accepted/2003/Walshaw2003.7.3.pdf A Multilevel Algorithm for Force-Directed
Graph-Drawing</ref>
Graph-Drawing</ref>
==इतिहास==
==इतिहास==
ग्राफ़ ड्राइंग में बल-निर्देशित विधियाँ {{harvtxt|टुटे|1963}}, में जिन्होंने दिखाया कि [[बहुफलकीय ग्राफ|पॉलीहेड्रल ग्राफ]] समतल में सभी फलकों के उत्तल होने के साथ खींचा जा सकता है, इसके अतिरिक्त ग्राफ के समतलीय फलक के बाहरी फलक के शीर्षों को [[उत्तल स्थिति]] में स्थापित करके, प्रत्येक किनारे पर स्प्रिंग जैसा आकर्षक बल लगाकर, और प्रणाली संतुलन में स्थापित हो जाता है।<ref>{{citation|first=W. T.|last=Tutte|author-link=W. T. Tutte|title=How to draw a graph|journal=Proceedings of the London Mathematical Society|volume=13|issue=52|pages=743–768|year=1963|doi=10.1112/plms/s3-13.1.743}}.</ref> इस स्तिथि में बलों की सरल प्रकृति के कारण, प्रणाली स्थानीय मिनिमा में फंस नहीं सकता है, किंतु अद्वितीय वैश्विक इष्टतम कॉन्फ़िगरेशन में परिवर्तित हो जाता है। इस कार्य के कारण, उत्तल फलकों वाले समतलीय ग्राफ़ों की एम्बेडिंग को कभी-कभी [[टुटे एम्बेडिंग]] कहा जाता है।
ग्राफ़ ड्राइंग में बल-निर्देशित विधियाँ {{harvtxt|टुटे|1963}}, में जिन्होंने दिखाया कि [[बहुफलकीय ग्राफ|पॉलीहेड्रल ग्राफ]] समतल में सभी फलकों के उत्तल होने के साथ खींचा जा सकता है, इसके अतिरिक्त ग्राफ के समतलीय फलक के बाहरी फलक के शीर्षों को [[उत्तल स्थिति]] में स्थापित करके, प्रत्येक किनारे पर स्प्रिंग जैसा आकर्षक बल लगाकर, और प्रणाली संतुलन में स्थापित हो जाता है।<ref>{{citation|first=W. T.|last=Tutte|author-link=W. T. Tutte|title=How to draw a graph|journal=Proceedings of the London Mathematical Society|volume=13|issue=52|pages=743–768|year=1963|doi=10.1112/plms/s3-13.1.743}}.</ref> इस स्तिथि में बलों की सरल प्रकृति के कारण, प्रणाली स्थानीय मिनिमा में फंस नहीं सकता है, किंतु अद्वितीय वैश्विक इष्टतम कॉन्फ़िगरेशन में परिवर्तित हो जाता है। इस कार्य के कारण, उत्तल फलकों वाले समतलीय ग्राफ़ों की एम्बेडिंग को कभी-कभी [[टुटे एम्बेडिंग]] कहा जाता है।


आसन्न शीर्षों पर आकर्षक बलों और सभी शीर्षों पर प्रतिकारक बलों के संयोजन का प्रयोग सर्वप्रथम किसके द्वारा किया गया था? {{harvtxt|ईड्स|1984}};<ref>{{citation
आसन्न शीर्षों पर आकर्षक बलों और सभी शीर्षों पर प्रतिकारक बलों के संयोजन का प्रयोग सर्वप्रथम किसके द्वारा किया गया था? {{harvtxt|ईड्स|1984}};<ref>{{citation
   | last=Eades | first=Peter | author-link = Peter Eades
   | last=Eades | first=Peter | author-link = Peter Eades
   | title=A Heuristic for Graph Drawing
   | title=A Heuristic for Graph Drawing
Line 99: Line 99:
   | doi=10.1016/0020-0190(89)90102-6}}.</ref>
   | doi=10.1016/0020-0190(89)90102-6}}.</ref>
==यह भी देखें==
==यह भी देखें==
*[[साइटोस्केप]], जैविक नेटवर्क को देखने के लिए सॉफ्टवेयर। बेस पैकेज में अंतर्निहित विधियों में से के रूप में बल-निर्देशित लेआउट सम्मिलित होते हैं।
*[[साइटोस्केप]], जैविक नेटवर्क को देखने के लिए सॉफ्टवेयर। बेस पैकेज में अंतर्निहित विधियों में से के रूप में बल-निर्देशित लेआउट सम्मिलित होते हैं।
*[[ कहाँ? | गेफी]], सभी प्रकार के नेटवर्क और जटिल प्रणालियों, गतिशील और श्रेणीबद्ध ग्राफ़ के लिए इंटरैक्टिव विज़ुअलाइज़ेशन और अन्वेषण मंच आदि ।
*[[ कहाँ? | गेफी]], सभी प्रकार के नेटवर्क और जटिल प्रणालियों, गतिशील और श्रेणीबद्ध ग्राफ़ के लिए इंटरैक्टिव विज़ुअलाइज़ेशन और अन्वेषण मंच आदि ।
*[[ग्रप्ह्वइज़|ग्राफविज़,]] सॉफ़्टवेयर जो बहुस्तरीय बल-निर्देशित लेआउट एल्गोरिदम प्रस्तुत करता है (कई अन्य के बीच) जो बहुत बड़े ग्राफ़ को संभालने में सक्षम है।
*[[ग्रप्ह्वइज़|ग्राफविज़,]] सॉफ़्टवेयर जो बहुस्तरीय बल-निर्देशित लेआउट एल्गोरिदम प्रस्तुत करता है (कई अन्य के बीच) जो बहुत बड़े ग्राफ़ को संभालने में सक्षम है।
*[[ट्यूलिप (सॉफ्टवेयर)]], जोकी अधिकांश बल-निर्देशित लेआउट एल्गोरिदम (जीईएम , एलजीएल, जीआरआईपी , एफएम³) को प्रस्तुत करता है।
*[[ट्यूलिप (सॉफ्टवेयर)]], जोकी अधिकांश बल-निर्देशित लेआउट एल्गोरिदम (जीईएम , एलजीएल, जीआरआईपी , एफएम³) को प्रस्तुत करता है।
*प्रस्तावना
*प्रस्तावना


==संदर्भ==
==संदर्भ==
{{Reflist|colwidth=30em}}
{{Reflist|colwidth=30em}}


==अग्रिम पठन==
==अग्रिम पठन==

Revision as of 19:07, 6 July 2023

बल-निर्देशित ग्राफ़ ड्राइंग एल्गोरिदम का उपयोग करके सामाजिक नेटवर्क विज़ुअलाइज़ेशन[1]
बल-निर्देशित लेआउट का उपयोग करके विकी पर पृष्ठों के मध्य लिंक का विज़ुअलाइज़ेशन

बल-निर्देशित ग्राफ ड्राइंग कलन विधि सौंदर्य-सुखदायक विधि से ग्राफ़ ड्राइंग के लिए एल्गोरिदम का वर्ग माना जाता है। उनका उद्देश्य ग्राफ़ (अलग-अलग गणित) के नोड्स को दो-आयामी या त्रि-आयामी अंतरिक्ष में स्थित करना होता है किंतु सभी किनारे कम या अधिक समान लंबाई के हों और जितना संभव हो उतना कम क्रॉसिंग किनारे हों, मध्य में बल निर्दिष्ट करके किनारों का समुच्चय और नोड्स का समुच्चय , उनकी सापेक्ष स्थिति के आधार पर, और फिर इन बलों का उपयोग या तो किनारों और नोड्स की गति को अनुकरण करने या उनकी ऊर्जा को कम करने के लिए किया जाता है।[2]

इस प्रकार से जबकि ग्राफ़ बनाना कठिन समस्या हो सकती है, और बल-निर्देशित एल्गोरिदम, भौतिक सिमुलेशन होने के कारण, सामान्यतः ग्राफ़ सिद्धांत जैसे कि समतलीय ग्राफ के बारे में किसी विशेष ज्ञान की आवश्यकता नहीं होती है।

बल

बल-निर्देशित ग्राफ़ ड्राइंग एल्गोरिदम किनारों के समुच्चय और ग्राफ़ ड्राइंग के नोड्स के समुच्चय के मध्य बल निर्दिष्ट करते हैं। सामान्यतः , हुक के नियम पर आधारित वसंत (उपकरण)जैसे आकर्षक बलों का उपयोग ग्राफ के किनारों के अंतिम बिंदुओं के जोड़े को एक-दूसरे की ओर आकर्षित करने के लिए किया जाता है, जबकि साथ ही कूलम्ब के नियम के आधार पर विद्युत आवेश कणों जैसे प्रतिकारक बलों का उपयोग सभी जोड़े को अलग करने के लिए किया जाता है। नोड्स. बलों की इस प्रणाली के लिए यांत्रिक संतुलन में, किनारों की लंबाई समान होती है (स्प्रिंग बलों के कारण), और जो नोड्स किनारे से नहीं जुड़े होते हैं वे और अधिक दूर खींचे जाते हैं (विद्युत प्रतिकर्षण के कारण)। किनारे के आकर्षण और शीर्ष प्रतिकर्षण बलों को उन कार्यों का उपयोग करके परिभाषित किया जा सकता है जोकी स्प्रिंग्स और कणों के भौतिक व्यवहार पर आधारित नहीं होते हैं; इस प्रकार से उदाहरण के लिए, कुछ बल-निर्देशित प्रणालियाँ स्प्रिंग्स का उपयोग करती हैं जिनका आकर्षक बल रैखिक के अतिरिक्त लघुगणकीय होता है।

इस प्रकार वैकल्पिक मॉडल प्रत्येक जोड़ी नोड्स के लिए स्प्रिंग-जैसे बल पर विचार करता है जहां आदर्श लंबाई है प्रत्येक स्प्रिंग का मान अलग प्रतिकारक बल का उपयोग किए बिना, नोड्स i और j के मध्य ग्राफ-सैद्धांतिक दूरी के समानुपाती होता है। यूक्लिडियन दूरी और नोड्स के मध्य आदर्श दूरी के मध्य अंतर (सामान्यतः वर्ग अंतर) को कम करना मीट्रिक बहुआयामी स्केलिंग समस्या के समान है।

बल-निर्देशित ग्राफ़ में यांत्रिक स्प्रिंग्स और विद्युत प्रतिकर्षण के अलावा अन्य बल सम्मिलित हो सकते हैं। गुरुत्वाकर्षण के अनुरूप बल का उपयोग शीर्षों को ड्राइंग स्थान के निश्चित बिंदु की ओर खींचने के लिए किया जा सकता है; इसका उपयोग डिस्कनेक्ट किए गए ग्राफ़ के विभिन्न कनेक्टेड घटकों (ग्राफ़ सिद्धांत) को साथ खींचने के लिए किया जा सकता है, जो अन्यथा प्रतिकारक बलों के कारण एक-दूसरे से अलग हो जाते हैं, और ड्राइंग में अधिक केंद्रीय पदों पर अधिक केंद्रीयता वाले नोड्स खींचने के लिए उपयोग किया जा सकता है। ;[3] यह घटक के अन्दर शीर्ष रिक्ति को भी प्रभावित कर सकता है। निर्देशित ग्राफ़ के लिए चुंबकीय क्षेत्र के एनालॉग्स का उपयोग किया जा सकता है। अंतिम ड्राइंग में ओवरलैप या निकट-ओवरलैप से बचने के लिए किनारों के साथ-साथ नोड्स पर भी प्रतिकारक बल लगाए जा सकते हैं। घुमावदार किनारों वाले रेखाचित्रों जैसे कि वृत्ताकार चाप या स्प्प्लाईन में, इन वक्रों के नियंत्रण बिंदुओं पर बल भी लगाए जा सकते हैं, इस प्रकार से उदाहरण के लिए उनके कोणीय रिज़ॉल्यूशन (ग्राफ़ ड्राइंग) में सुधार करने के लिए किया जाता है ।[4]

विधि

वर्तमान समय में ग्राफ़ के नोड्स और किनारों पर बलों को परिभाषित किया गया है, तो इन स्रोतों के तहत पूरे ग्राफ़ का व्यवहार तब अनुकरण किया जा सकता है जैसे कि यह भौतिक प्रणाली थी। इस प्रकार से अनुकरण में, बलों को नोड्स पर प्रस्तुत किया जाता है, उन्हें अपनी ओर खींचा जाता है या उन्हें और दूर धकेल दिया जाता है। इसे तब तक दोहराया जाता है जब तक कि प्रणाली यांत्रिक संतुलन स्थिति में नहीं आ जाता; अर्थात , उनकी सापेक्ष स्थिति पुनरावृत्ति से दूसरी पुनरावृत्ति में नहीं परिवर्तित होती रहती है। इस संतुलन में नोड्स की स्थिति का उपयोग ग्राफ का चित्र बनाने के लिए किया जाता है।

इस प्रकार से स्प्रिंग्स से परिभाषित बलों के लिए जिनकी आदर्श लंबाई ग्राफ-सैद्धांतिक दूरी के समानुपाती होती है, तनाव प्रमुखता बहुत सही प्रकार से व्यवहार करती है (अर्थात , अनुक्रम की नीरस सीमा)[5] और इन अंतरों को अनुकूलित करने के लिए गणितीय रूप से सुंदर विधि (गणित) और, इसलिए, ग्राफ़ के लिए अच्छा लेआउट ढूंढें।

किंतु ऐसे तंत्रों को नियोजित करना भी संभव है जो भौतिक सिमुलेशन के अतिरिक्त या उसके संयोजन के साथ ऊर्जा मिनिमा के लिए अधिक सीधे खोज करते हैं। ऐसे तंत्र, जोकी सामान्य वैश्विक अनुकूलन विधियों के उदाहरण हैं, में सिम्युलेटेड एनीलिंग और आनुवंशिक एल्गोरिदम सम्मिलित हैं।

लाभ

इस प्रकार से बल-निर्देशित एल्गोरिदम के सबसे महत्वपूर्ण लाभों में से निम्नलिखित होते हैं:

उच्च गुणवत्ता वाले परिणाम
कम से कम मध्यम आकार (50-500 शीर्षों तक) के ग्राफ़ के लिए, प्राप्त परिणाम सामान्यतः निम्नलिखित मानदंडों के आधार पर अधिक उच्च परिणाम देते हैं: समान किनारे की लंबाई, समान शीर्ष वितरण और समरूपता दिखया जाता है । यह अंतिम मानदंड सबसे महत्वपूर्ण मानदंडों में से है और किसी अन्य प्रकार के एल्गोरिदम के साथ इसे प्राप्त करना कठिन है।
लचीलापन
अतिरिक्त सौंदर्य मानदंडों को पूर्ण करने के लिए बल-निर्देशित एल्गोरिदम को सरलता से अनुकूलित और विस्तारित किया जा सकता है। यह उन्हें ग्राफ़ ड्राइंग एल्गोरिदम का सबसे बहुमुखी वर्ग बनाता है। इस प्रकार से उपस्तिथ एक्सटेंशन के उदाहरणों में निर्देशित ग्राफ़, 3डी ग्राफ़ ड्राइंग,[6] क्लस्टर ग्राफ़ ड्राइंग, विवश ग्राफ़ ड्राइंग, और गतिशील ग्राफ़ ड्राइंग आदि ।
सहज
चूंकि वे स्प्रिंग्स जैसी सामान्य वस्तुओं की भौतिक सादृश्यता पर आधारित होते हैं, इसलिए एल्गोरिदम के व्यवहार की भविष्यवाणी करना और समझना अपेक्षाकृत सरल होते है। अन्य प्रकार के ग्राफ़ ड्राइंग|ग्राफ़-ड्राइंग एल्गोरिदम के स्तिथि में ऐसा नहीं होता है।
सरलता
विशिष्ट बल-निर्देशित एल्गोरिदम सरल होते हैं और इन्हें कोड की कुछ पंक्तियों में प्रस्तुत किया जा सकता है। ग्राफ़-ड्राइंग एल्गोरिदम के अन्य वर्ग, जैसे ऑर्थोगोनल लेआउट के लिए, सामान्यतः बहुत अधिक सम्मिलित होते हैं।
अन्तरक्रियाशीलता
एल्गोरिदम के इस वर्ग का एक अन्य लाभ इंटरैक्टिव भाग है। ग्राफ़ के मध्यवर्ती चरणों को चित्रित करके, उपयोगकर्ता यह देख सकता है कि ग्राफ़ कैसे विकसित होता है, इसे एक उलझी हुई गड़बड़ी से एक अच्छे दिखने वाले कॉन्फ़िगरेशन में प्रकट होते हुए देख सकता है। कुछ इंटरैक्टिव ग्राफ़ ड्राइंग टूल में, उपयोगकर्ता एक या एक से अधिक नोड्स को उनकी संतुलन स्थिति से बाहर खींच सकता है और उन्हें वापस स्थिति में स्थानांतरित होते हुए देख सकता है। यह उन्हें गतिशील और ऑनलाइन एल्गोरिदम ग्राफ़-ड्राइंग प्रणाली के लिए मुख्य विकल्प बनाता है।
कठोर सैद्धांतिक आधार
जबकि सरल तदर्थ बल-निर्देशित एल्गोरिदम अक्सर साहित्य और व्यवहार में दिखाई देते हैं (क्योंकि उन्हें समझना अपेक्षाकृत सरल है), अधिक तर्कसंगत दृष्टिकोण लोकप्रियता प्राप्त करना प्रारंभ कर रहे हैं। सांख्यिकीविद् 1930 के दशक से बहुआयामी स्केलिंग (एमडीएस) में समान समस्याओं को हल कर रहे हैं, और भौतिकविदों के पास संबंधित ए एन बॉडी समस्याओं के साथ काम करने का लंबा इतिहास भी है - इसलिए अधिक परिपक्व दृष्टिकोण उपस्तिथ हैं। उदाहरण के तौर पर, मीट्रिक एमडीएस के लिए तनाव प्रमुखीकरण दृष्टिकोण को ऊपर वर्णित अनुसार ग्राफ ड्राइंग पर प्रस्तुत किया जा सकता है। यह मोनोटोन अभिसरण प्रमेय से सिद्ध हो चुका है।[5] मोनोटोनिक अभिसरण, वह गुण जो एल्गोरिदम प्रत्येक पुनरावृत्ति पर लेआउट के तनाव या व्यय को कम करेगा, इस प्रकार से यह महत्वपूर्ण है क्योंकि यह प्रमाण देता है कि लेआउट अंततः स्थानीय न्यूनतम तक पहुंच जाएगा और रुक जाएगा। डंपिंग शेड्यूल के कारण एल्गोरिदम रुक जाता है, जिससे यह प्रत्याभूति नहीं दे सकता कि वास्तविक स्थानीय न्यूनतम तक पहुंच गया है।

हानि

बल-निर्देशित एल्गोरिदम के मुख्य हानि में निम्नलिखित सम्मिलित होते हैं:

उच्च समय जटिलता
विशिष्ट बल-निर्देशित एल्गोरिदम को सामान्यतः घन समय (), में चलने वाला माना जाता है जहाँ इनपुट ग्राफ़ के नोड्स की संख्या है। ऐसा इसलिए है क्योंकि पुनरावृत्तियों की संख्या रैखिक होने का अनुमान (), है और प्रत्येक पुनरावृत्ति में, नोड्स के सभी जोड़े का दौरा करने और उनकी पारस्परिक प्रतिकारक शक्तियों की गणना करने की आवश्यकता होती है। यह भौतिकी में एन-बॉडी समस्या से संबंधित है। , चूँकि प्रतिकारक शक्तियाँ स्थानीय प्रकृति की होती हैं, इसलिए ग्राफ को इस प्रकार विभाजित किया जा सकता है कि केवल प्रतिवेशी शीर्षों पर ही विचार किया जाए। बड़े ग्राफ़ के लेआउट को निर्धारित करने के लिए एल्गोरिदम द्वारा उपयोग की जाने वाली सामान्य विधियों में उच्च-आयामी एम्बेडिंग सम्मिलित होते है,[7] मल्टी-लेयर ड्राइंग और एन-बॉडी सिमुलेशन से संबंधित अन्य विधियां। इस प्रकार से उदाहरण के लिए, बार्न्स-हट सिमुलेशन-आधारित विधि एफएडीई [8] :रनिंग टाइम को लीनियरिथ्मिक या प्रति पुनरावृत्ति में सुधार कर सकते हैं। एक जटिल मार्गदर्शक के रूप में, कुछ ही सेकंड में कोई मानक प्रति पुनरावृत्ति विधियों के साथ अधिकतम 1,000 नोड्स और प्रति पुनरावृत्ति विधियों के साथ 100,000 नोड्स खींचने की उम्मीद कर सकता है। [8] बल-निर्देशित एल्गोरिदम, जब ग्राफ क्लस्टरिंग दृष्टिकोण के साथ संयुक्त होते हैं, तो लाखों नोड्स के ग्राफ़ खींच सकते हैं।[9]
निकृष्ट स्थानीय न्यूनतम
यह देखना सरल होता है कि बल-निर्देशित एल्गोरिदम न्यूनतम ऊर्जा के साथ ग्राफ़ उत्पन्न करते हैं, विशेष रूप से जिसकी कुल ऊर्जा केवल स्थानीय न्यूनतम होती है। पाया गया स्थानीय न्यूनतम, कई स्तिथियों में, वैश्विक न्यूनतम से अधिक निकृष्ट हो सकता है, जो निम्न-गुणवत्ता वाली ड्राइंग में परिवर्तित हो जाता है। कई एल्गोरिदम के लिए, विशेष रूप से वे जो केवल शीर्ष से नीचे की ओर बढ़ने की अनुमति देते हैं, अंतिम परिणाम प्रारंभिक लेआउट से दृढ़ता से प्रभावित हो सकता है, जो कि अधिकतर स्तिथियों में यादृच्छिक रूप से उत्पन्न होता है। जैसे-जैसे ग्राफ़ के शीर्षों की संख्या बढ़ती है, निकृष्ट स्थानीय न्यूनतम की समस्या और अधिक महत्वपूर्ण हो जाती है। विभिन्न एल्गोरिदम का संयुक्त अनुप्रयोग इस समस्या को हल करने में सहायक है।[10] इस प्रकार से उदाहरण के लिए, कामदा-कवाई एल्गोरिदम का उपयोग किया जाता है [11] और शीघ्रता से उचित प्रारंभिक लेआउट और फिर फ्रूचटरमैन-रींगोल्ड एल्गोरिथम उत्पन्न करने के लिए[12] प्रतिवेशी नोड्स की स्थिति में सुधार करने के लिए किया जाता है । वैश्विक न्यूनतम प्राप्त करने की अन्य विधियों बहुस्तरीय दृष्टिकोण का उपयोग किया जाता है।[13]

इतिहास

ग्राफ़ ड्राइंग में बल-निर्देशित विधियाँ टुटे (1963), में जिन्होंने दिखाया कि पॉलीहेड्रल ग्राफ समतल में सभी फलकों के उत्तल होने के साथ खींचा जा सकता है, इसके अतिरिक्त ग्राफ के समतलीय फलक के बाहरी फलक के शीर्षों को उत्तल स्थिति में स्थापित करके, प्रत्येक किनारे पर स्प्रिंग जैसा आकर्षक बल लगाकर, और प्रणाली संतुलन में स्थापित हो जाता है।[14] इस स्तिथि में बलों की सरल प्रकृति के कारण, प्रणाली स्थानीय मिनिमा में फंस नहीं सकता है, किंतु अद्वितीय वैश्विक इष्टतम कॉन्फ़िगरेशन में परिवर्तित हो जाता है। इस कार्य के कारण, उत्तल फलकों वाले समतलीय ग्राफ़ों की एम्बेडिंग को कभी-कभी टुटे एम्बेडिंग कहा जाता है।

आसन्न शीर्षों पर आकर्षक बलों और सभी शीर्षों पर प्रतिकारक बलों के संयोजन का प्रयोग सर्वप्रथम किसके द्वारा किया गया था? ईड्स (1984);[15] इस प्रकार के बल-निर्देशित लेआउट पर अतिरिक्त अग्रणी कार्य किसके द्वारा किया गया था? फ्रूचरमैन & रींगोल्ड (1991).[12] शीर्षों के सभी युग्मों के मध्य केवल स्प्रिंग बलों का उपयोग करने का विचार, शीर्षों की ग्राफ-सैद्धांतिक दूरी के समान आदर्श स्प्रिंग लंबाई के साथ, से है कमादा & कवाई (1989).[11]

यह भी देखें

  • साइटोस्केप, जैविक नेटवर्क को देखने के लिए सॉफ्टवेयर। बेस पैकेज में अंतर्निहित विधियों में से के रूप में बल-निर्देशित लेआउट सम्मिलित होते हैं।
  • गेफी, सभी प्रकार के नेटवर्क और जटिल प्रणालियों, गतिशील और श्रेणीबद्ध ग्राफ़ के लिए इंटरैक्टिव विज़ुअलाइज़ेशन और अन्वेषण मंच आदि ।
  • ग्राफविज़, सॉफ़्टवेयर जो बहुस्तरीय बल-निर्देशित लेआउट एल्गोरिदम प्रस्तुत करता है (कई अन्य के बीच) जो बहुत बड़े ग्राफ़ को संभालने में सक्षम है।
  • ट्यूलिप (सॉफ्टवेयर), जोकी अधिकांश बल-निर्देशित लेआउट एल्गोरिदम (जीईएम , एलजीएल, जीआरआईपी , एफएम³) को प्रस्तुत करता है।
  • प्रस्तावना

संदर्भ

  1. Grandjean, Martin (2015), "Introduction à la visualisation de données, l'analyse de réseau en histoire", Geschichte und Informatik 18/19 (PDF), pp. 109–128
  2. Kobourov, Stephen G. (2012), Spring Embedders and Force-Directed Graph Drawing Algorithms, arXiv:1201.3011, Bibcode:2012arXiv1201.3011K.
  3. Bannister, M. J.; Eppstein, D.; Goodrich, M. T.; Trott, L. (2012), "Force-directed graph drawing using social gravity and scaling", Proc. 20th Int. Symp. Graph Drawing, arXiv:1209.0748, Bibcode:2012arXiv1209.0748B.
  4. Chernobelskiy, R.; Cunningham, K.; Goodrich, M. T.; Kobourov, S. G.; Trott, L. (2011), "Force-directed Lombardi-style graph drawing", Proc. 19th Symposium on Graph Drawing (PDF), pp. 78–90.
  5. 5.0 5.1 de Leeuw, Jan (1988), "Convergence of the majorization method for multidimensional scaling", Journal of Classification, Springer, 5 (2): 163–180, doi:10.1007/BF01897162, S2CID 122413124.
  6. Vose, Aaron. "3D Phylogenetic Tree Viewer". Retrieved 3 June 2012.
  7. Harel, David; Koren, Yehuda (2002), "Graph drawing by high-dimensional embedding", Proceedings of the 9th International Symposium on Graph Drawing, pp. 207–219, CiteSeerX 10.1.1.20.5390, ISBN 3-540-00158-1
  8. 8.0 8.1 Quigley, Aaron; Eades, Peter (2001), "FADE: Graph Drawing, Clustering, and Visual Abstraction", Proceedings of the 8th International Symposium on Graph Drawing (PDF), pp. 197–210, ISBN 3-540-41554-8.
  9. "बड़े ग्राफ़ की एक गैलरी". Retrieved 22 Oct 2017.
  10. Collberg, Christian; Kobourov, Stephen; Nagra, Jasvir; Pitts, Jacob; Wampler, Kevin (2003), "A System for Graph-based Visualization of the Evolution of Software", Proceedings of the 2003 ACM Symposium on Software Visualization (SoftVis '03), New York, NY, USA: ACM, pp. 77–86, figures on p. 212, doi:10.1145/774833.774844, ISBN 1-58113-642-0, S2CID 824991, To achieve an aesthetically pleasing layout of the graph it is also necessary to employ modified Fruchterman–Reingold forces, as the Kamada–Kawai method does not achieve satisfactory methods by itself but rather creates a good approximate layout so that the Fruchterman-Reingold calculations can quickly "tidy up" the layout.
  11. 11.0 11.1 Kamada, Tomihisa; Kawai, Satoru (1989), "An algorithm for drawing general undirected graphs", Information Processing Letters, Elsevier, 31 (1): 7–15, doi:10.1016/0020-0190(89)90102-6.
  12. 12.0 12.1 Fruchterman, Thomas M. J.; Reingold, Edward M. (1991), "Graph Drawing by Force-Directed Placement", Software: Practice and Experience, Wiley, 21 (11): 1129–1164, doi:10.1002/spe.4380211102, S2CID 31468174.
  13. http://jgaa.info/accepted/2003/Walshaw2003.7.3.pdf A Multilevel Algorithm for Force-Directed Graph-Drawing
  14. Tutte, W. T. (1963), "How to draw a graph", Proceedings of the London Mathematical Society, 13 (52): 743–768, doi:10.1112/plms/s3-13.1.743.
  15. Eades, Peter (1984), "A Heuristic for Graph Drawing", Congressus Numerantium, 42 (11): 149–160.

अग्रिम पठन

बाहरी संबंध