आश्रितता ग्राफ

गणित, कंप्यूटर विज्ञान और डिजिटल इलेक्ट्रॉनिक्स में, निर्भरता ग्राफ़ एक निर्देशित ग्राफ़ है जो एक दूसरे के प्रति कई वस्तुओं की निर्भरता का प्रतिनिधित्व करता है। मूल्यांकन आदेश प्राप्त करना या मूल्यांकन आदेश की अनुपस्थिति संभव है जो निर्भरता ग्राफ से दी गई निर्भरता का सम्मान करती है।

परिभाषा

वस्तुओं का एक सेट दिया गया $S$ और एक सकर्मक संबंध $R\subseteq S\times S$ साथ $(a,b)\in R$ निर्भरता का मॉडलिंग a, b पर निर्भर करता है (a को पहले b का मूल्यांकन करने की आवश्यकता है), निर्भरता ग्राफ एक ग्राफ है $G=(S,T)$ साथ $T\subseteq R$ आर की सकर्मक कमी

उदाहरण के लिए, एक साधारण कैलकुलेटर मान लें। यह कैलकुलेटर वेरिएबल्स के लिए स्थिर मानों को निर्दिष्ट करने और तीसरे वेरिएबल को ठीक दो वेरिएबल्स का योग निर्दिष्ट करने का समर्थन करता है। A = B+C जैसे कई समीकरण दिए गए हैं; बी = 5+डी; सी=4; डी=2; , तब $S=\{A,B,C,D\}$ और $R=\{(A,B),(A,C),(B,D)\}$. आप इस संबंध को सीधे प्राप्त कर सकते हैं: A, B और C पर निर्भर करता है, क्योंकि आप दो चर जोड़ सकते हैं यदि और केवल तभी जब आप दोनों चर के मान जानते हों। इस प्रकार, A की गणना करने से पहले B की गणना की जानी चाहिए। हालाँकि, C और D के मान तुरंत ज्ञात हो जाते हैं, क्योंकि वे संख्या शाब्दिक हैं।

असंभव मूल्यांकन को पहचानना

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

पहले से सरल कैलकुलेटर मान लें। समीकरण प्रणाली A=B; बी=डी+सी; सी=डी+ए; डी=12; ए, बी और सी द्वारा बनाई गई एक गोलाकार निर्भरता शामिल है, क्योंकि बी का मूल्यांकन ए से पहले किया जाना चाहिए, सी का मूल्यांकन से पहले किया जाना चाहिए 'बी', और 'ए' का मूल्यांकन 'सी' से पहले किया जाना चाहिए।

मूल्यांकन आदेश निकालना

एक सही मूल्यांकन क्रम एक क्रमांकन है $n:S\rightarrow \mathbb {N}$ वे वस्तुएँ जो निर्भरता ग्राफ़ के नोड्स बनाती हैं ताकि निम्नलिखित समीकरण कायम रहे: $n(a)<n(b)\Rightarrow (a,b)\notin R$ साथ $a,b\in S$. इसका मतलब है, यदि क्रमांकन दो तत्वों का आदेश देता है $a$ और $b$ ताकि $a$ पहले मूल्यांकन किया जाएगा $b$, तब $a$ पर निर्भर नहीं रहना चाहिए $b$.

एक से अधिक सही मूल्यांकन क्रम हो सकते हैं। वास्तव में, एक सही नंबरिंग एक टोपोलॉजिकल सॉर्टिंग है, और कोई भी टोपोलॉजिकल ऑर्डर एक सही नंबरिंग है। इस प्रकार, कोई भी एल्गोरिदम जो एक सही टोपोलॉजिकल ऑर्डर प्राप्त करता है, एक सही मूल्यांकन क्रम प्राप्त करता है।

ऊपर दिए गए सरल कैलकुलेटर को एक बार फिर से मान लें। समीकरण प्रणाली A = B+C दिया गया है; बी = 5+डी; सी=4; डी=2; , एक सही मूल्यांकन क्रम होगा (डी, सी, बी, ए)। हालाँकि, (सी, डी, बी, ए) भी एक सही मूल्यांकन क्रम है।

मोनोइड संरचना

एक एसाइक्लिक निर्भरता ग्राफ एक ट्रेस मोनॉइड के ट्रेस से इस प्रकार मेल खाता है:

• एक समारोह $\phi :S\to \Sigma$ प्रत्येक शीर्ष को वर्णमाला के एक प्रतीक के साथ लेबल करें $\Sigma$
• एक किनारा है $a\to b$ या $b\to a$ अगर और केवल अगर $(\phi (a),\phi (b))$ निर्भरता संबंध में है $D$.
• दो ग्राफ़ समान माने जाते हैं यदि उनके लेबल और किनारे मेल खाते हों।

फिर एक सही मूल्यांकन क्रम द्वारा क्रमित शीर्ष लेबल वाली स्ट्रिंग एक ट्रेस की एक स्ट्रिंग से मेल खाती है।

मोनोइडल ऑपरेशन $(S_{12},R_{12})=(S_{1},R_{1})\bullet (S_{2},R_{2})$ असंयुक्त संघ लेता है $S_{12}=S_{1}\sqcup S_{2}$ दो ग्राफ़ के शीर्ष सेटों में से, प्रत्येक ग्राफ़ में मौजूदा किनारों को संरक्षित करता है, और पहले से दूसरे तक नए किनारों को खींचता है जहां निर्भरता संबंध अनुमति देता है,

$R_{12}=R_{1}\sqcup R_{2}\sqcup \{(a,b)\mid a\in S_{1}\land b\in S_{2}\land (\phi (a),\phi (b))\in D\}$

पहचान खाली ग्राफ है.

उदाहरण

निर्भरता ग्राफ़ का उपयोग इसमें किया जाता है:

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

निर्भरता ग्राफ़ इसका एक पहलू है:

• बाधाओं का सिद्धांत#पौधे के प्रकार: कच्चे माल को कई निर्भर चरणों के माध्यम से उत्पादों में संसाधित किया जाता है।
• जॉब शॉप शेड्यूलिंग: कंप्यूटर विज्ञान में संबंधित सैद्धांतिक समस्याओं का संग्रह।

यह भी देखें

• कॉल ग्राफ़
• टोपोलॉजिकल सॉर्ट
• डेटा निर्भरता

संदर्भ

• Balmas, Francoise (2001) Displaying dependence graphs: a hierarchical approach, [1] wcre, p. 261, Eighth Working Conference on Reverse Engineering (WCRE'01)