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

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

परिभाषा

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