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

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

परिभाषा

वस्तुओं के एक समुच्चय को देखते हुए 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)