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

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

परिभाषा

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

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

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

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

पहले से साधारण परिगणक को कल्पना करते हैं। समीकरण पद्धति "A=B; B=D+C; C=D+A; D=12;" इसमें A, B और C द्वारा गठित एक वत्तीय आश्रितता सम्मिलित है, क्योंकि B का मूल्यांकन A से पहले किया जाना चाहिए, C का मूल्यांकन B से पहले किया जाना चाहिए, और A का मूल्यांकन C से पहले किया जाना चाहिए |

मूल्यांकन अनुक्रम व्युत्पत्ति

एक सही मूल्यांकन अनुक्रम उन वस्तुओं का संख्यांकन $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; B = 5+D; C=4; D=2;" को देखते हुए, एक सही मूल्यांकन अनुक्रम (D, C, B, A) होता है। हालाँकि, (C, D, B, A) भी एक सही मूल्यांकन अनुक्रम है।

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

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

• एक समारोह $\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)