ग्राफ पुनर्लेखन

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

ग्राफ़ ट्रांसफ़ॉर्मेशन का उपयोग संगणना अमूर्त के रूप में किया जा सकता है। मूल विचार यह है कि यदि गणना की स्थिति को ग्राफ के रूप में प्रदर्शित किया जा सकता है, तो उस गणना में आगे के चरणों को उस ग्राफ पर परिवर्तन नियमों के रूप में प्रदर्शित किया जा सकता है। इस तरह के नियमों में एक मूल ग्राफ होता है, जिसे पूर्ण स्थिति में एक सबग्राफ से मिलान करना होता है, और एक प्रतिस्थापन ग्राफ, जो मिलान किए गए सबग्राफ को बदल देगा।

औपचारिक रूप से, एक ग्राफ़ पुनर्लेखन प्रणाली में आमतौर पर फ़ॉर्म के ग्राफ़ पुनर्लेखन नियमों का एक सेट होता है $L\rightarrow R$, साथ $L$ पैटर्न ग्राफ (या बायीं ओर) कहा जा रहा है और $R$ प्रतिस्थापन ग्राफ (या नियम के दाहिने हाथ की ओर) कहा जा रहा है। पैटर्न ग्राफ की घटना (पैटर्न मिलान, इस प्रकार सबग्राफ समरूपता समस्या को हल करना) की खोज करके और प्रतिस्थापन ग्राफ के एक उदाहरण द्वारा पाया गया घटना को बदलकर एक ग्राफ पुनर्लेखन नियम मेजबान ग्राफ पर लागू किया जाता है। स्ट्रिंग-विनियमित ग्राफ़ व्याकरण जैसे लेबल किए गए ग्राफ़ के मामले में पुनर्लेखन नियमों को और अधिक विनियमित किया जा सकता है।

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

ग्राफ़ पुनर्लेखन दृष्टिकोण

शीर्ष: उदाहरण ग्राफ पुनर्लेखन नियम (कंपाइलर निर्माण से प्रोग्राम ऑप्टिमाइज़ेशन # असेंबली स्तर: 2 के साथ गुणा को जोड़कर)। नीचे: y=x*2 को y=x+x में अनुकूलित करने के लिए नियम का अनुप्रयोग।

बीजगणितीय दृष्टिकोण

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

डीपीओ दृष्टिकोण के दृष्टिकोण से एक ग्राफ़ पुनर्लेखन नियम ग्राफ़ की श्रेणी में morphisms की एक जोड़ी है और उनके बीच ग्राफ़ समरूपता है: $r=(L\leftarrow K\rightarrow R)$, लिखा भी है $L\supseteq K\subseteq R$, कहाँ $K\rightarrow L$ इंजेक्शन है। ग्राफ K को अपरिवर्तनीय या कभी-कभी ग्लूइंग ग्राफ कहा जाता है। एक पुनर्लेखन कदम या एक मेजबान ग्राफ जी के नियम आर के आवेदन को दो पुशआउट (श्रेणी सिद्धांत) आरेखों द्वारा परिभाषित किया गया है जो दोनों एक ही आकारिकी में उत्पन्न होते हैं। $k\colon K\rightarrow D$, जहां डी एक संदर्भ ग्राफ है (यह वह जगह है जहां नाम डबल-पुशआउट आता है)। एक और ग्राफ रूपवाद $m\colon L\rightarrow G$ जी में एल की घटना को मॉडल करता है और इसे पैटर्न मिलान कहा जाता है। इसकी व्यावहारिक समझ यह है $L$ एक सबग्राफ है जिससे मिलान किया जाता है $G$ (सबग्राफ समरूपता समस्या देखें), और एक मैच मिलने के बाद, $L$ से प्रतिस्थापित किया जाता है $R$ मेजबान ग्राफ में $G$ कहाँ $K$ एक इंटरफ़ेस के रूप में कार्य करता है, जिसमें नियम लागू करते समय संरक्षित नोड्स और किनारे होते हैं। लेखाचित्र $K$ पैटर्न को इसके संदर्भ से मिलान करने के लिए संलग्न करने की आवश्यकता है: यदि यह खाली है, तो मैच केवल ग्राफ के पूरे जुड़े हुए घटक को निर्दिष्ट कर सकता है $G$.

इसके विपरीत एसपीओ दृष्टिकोण का एक ग्राफ पुनर्लेखन नियम लेबल किए गए मल्टीग्राफ और आंशिक मैपिंग की श्रेणी में एक एकल आकारिकी है जो मल्टीग्राफ संरचना को संरक्षित करता है: $r\colon L\rightarrow R$. इस प्रकार एक पुनर्लेखन चरण को एकल पुशआउट (श्रेणी सिद्धांत) आरेख द्वारा परिभाषित किया गया है। इसकी व्यावहारिक समझ डीपीओ दृष्टिकोण के समान है। अंतर यह है कि पुनर्लेखन चरण का परिणाम होने के कारण मेजबान ग्राफ G और ग्राफ G' के बीच कोई इंटरफ़ेस नहीं है।

व्यावहारिक दृष्टिकोण से, डीपीओ और एसपीओ के बीच मुख्य अंतर यह है कि वे आसन्न किनारों के साथ नोड्स को हटाने से कैसे निपटते हैं, विशेष रूप से, वे कैसे बचते हैं कि इस तरह के विलोपन लटकते किनारों को पीछे छोड़ सकते हैं। डीपीओ दृष्टिकोण केवल एक नोड को हटाता है जब नियम सभी आसन्न किनारों को भी हटाने को निर्दिष्ट करता है (किसी दिए गए मैच के लिए इस झूलने की स्थिति की जाँच की जा सकती है), जबकि एसपीओ दृष्टिकोण स्पष्ट विनिर्देश की आवश्यकता के बिना, आसन्न किनारों का निपटान करता है।

मुख्य रूप से बूलियन बीजगणित और मैट्रिसेस के बीजगणित पर आधारित ग्राफ पुनर्लेखन के लिए एक अन्य बीजगणितीय दृष्टिकोण भी है, जिसे मैट्रिक्स ग्राफ व्याकरण कहा जाता है।

निर्धारित ग्राफ पुनर्लेखन

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

टर्म ग्राफ पुनर्लेखन

ग्राफ़ पुनर्लेखन के लिए एक अन्य दृष्टिकोण शब्द ग्राफ़ पुनर्लेखन है, जिसमें सिंटैक्टिक पुनर्लेखन नियमों के एक सेट द्वारा शब्द ग्राफ़ (जिसे सार सिमेंटिक ग्राफ़ के रूप में भी जाना जाता है) का प्रसंस्करण या रूपांतरण शामिल है।

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

टर्मग्राफ सम्मेलन पूरी तरह से टर्म ग्राफ पुनर्लेखन और इसके अनुप्रयोगों में अनुसंधान पर केंद्रित है।

ग्राफ व्याकरण और ग्राफ पुनर्लेखन प्रणाली की कक्षाएं

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

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

कार्यान्वयन और अनुप्रयोग

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

• उपकरण जो अनुप्रयोग डोमेन तटस्थ हैं:
  • AGG, जिम्मेदार ग्राफ व्याकरण प्रणाली (जावा (प्रोग्रामिंग भाषा) )
  • GP 2 ग्राफ़ परिवर्तन नियमों के निर्देशित अनुप्रयोग द्वारा ग्राफ़ पर गणना करने के लिए एक प्रोग्रामिंग भाषा है।
  • GMTE, ग्राफ मिलान और परिवर्तन के लिए ग्राफ मिलान और परिवर्तन इंजन। यह सी ++ का उपयोग कर मेस्मर के एल्गोरिदम के विस्तार का कार्यान्वयन है।
  • GrGen|GrGen.NET, ग्राफ़ पुनर्लेखन जनरेटर, C Sharp (प्रोग्रामिंग भाषा) उत्सर्जित करने वाला एक ग्राफ़ रूपांतरण उपकरण|C#-कोड या .NET-असेंबली
  • GROOVE, ग्राफ़ और ग्राफ़ ट्रांसफ़ॉर्मेशन नियमों के संपादन के लिए एक जावा-आधारित टूल सेट, ग्राफ़ व्याकरण के स्टेट स्पेस की खोज, और उन स्टेट स्पेस की मॉडल जाँच; ग्राफ परिवर्तन इंजन के रूप में भी इस्तेमाल किया जा सकता है।
  • Verigraph, ग्राफ पुनर्लेखन (हास्केल (प्रोग्रामिंग भाषा)) पर आधारित एक सॉफ्टवेयर विनिर्देश और सत्यापन प्रणाली।
• उपकरण जो ग्राफ पुनर्लेखन के साथ सॉफ्टवेयर इंजीनियरिंग कार्यों (मुख्य रूप से मॉडल संचालित वास्तुकला) को हल करते हैं:
  • [1], कहानी-संचालित मॉडलिंग|स्टोरी-ड्रिवन मॉडलिंग और ट्रिपल ग्राफ ग्रामर के समर्थन के साथ एक EMF-संगत मॉडल-परिवर्तन उपकरण
  • EMorF ग्रहण मॉडलिंग फ्रेमवर्क पर आधारित एक ग्राफ रीराइटिंग सिस्टम, इन-प्लेस और मॉडल-टू-मॉडल मॉडल परिवर्तन का समर्थन करता है
  • Fujaba कहानी चालित मॉडलिंग का उपयोग करता है, PROGRES पर आधारित एक ग्राफ पुनर्लेखन भाषा
  • ग्राफ डेटाबेस अक्सर ग्राफ़ के गतिशील पुनर्लेखन का समर्थन करता है
  • महान
  • Gremlin, एक ग्राफ़-आधारित प्रोग्रामिंग भाषा (देखें ग्राफ़ पुनर्लेखन)
  • Henshin, एक्लिप्स मॉडलिंग फ्रेमवर्क पर आधारित एक ग्राफ रीराइटिंग सिस्टम, इन-प्लेस और मॉडल-टू-मॉडल मॉडल ट्रांसफॉर्मेशन, महत्वपूर्ण जोड़ी (तर्क)लॉजिक) और मॉडल की जाँच को सपोर्ट करता है।
  • PROGRES, प्रोग्राम्ड ग्राफ़ रीराइटिंग सिस्टम के लिए एक एकीकृत वातावरण और बहुत उच्च स्तरीय भाषा
  • हवाओं
• मैकेनिकल इंजीनियरिंग उपकरण
  • GraphSynth अप्रतिबंधित ग्राफ व्याकरण बनाने के साथ-साथ परिणामी भाषा संस्करण का परीक्षण और खोज करने के लिए एक दुभाषिया और UI वातावरण है। यह ग्राफ़ और ग्राफ़ व्याकरण के नियमों को XML फ़ाइलों के रूप में सहेजता है और C Sharp (प्रोग्रामिंग भाषा) | C# में लिखा जाता है।
  • सोले स्टूडियो, ग्राफ परिवर्तन प्रणालियों के लिए एक एकीकृत विकास वातावरण है। इसका मुख्य अनुप्रयोग फोकस इंजीनियरिंग के क्षेत्र में डेटा एनालिटिक्स है।
• जीव विज्ञान अनुप्रयोग
  • एक ग्राफ व्याकरण आधारित भाषा के साथ कार्यात्मक-संरचनात्मक संयंत्र मॉडलिंग
  • स्ट्रिंग-विनियमित ग्राफ व्याकरण के साथ बहुकोशिकीय विकास मॉडलिंग
• आर्टिफिशियल इंटेलिजेंस / प्राकृतिक भाषा प्रसंस्करण
  • OpenCog एक बुनियादी पैटर्न मैचर (hypergraph पर) प्रदान करता है जिसका उपयोग विभिन्न AI एल्गोरिदम को लागू करने के लिए किया जाता है।
  • RelEx एक अंग्रेजी-भाषा पार्सर है जो एक लिंक व्याकरण को निर्भरता व्याकरण में बदलने के लिए ग्राफ री-राइटिंग को नियोजित करता है।
• कंप्यूटर प्रोग्रामिंग भाषा
  • ग्राफ़ पुनर्लेखन का उपयोग करके स्वच्छ प्रोग्रामिंग भाषा लागू की जाती है।

यह भी देखें

• ग्राफ सिद्धांत
• आकार व्याकरण
• औपचारिक व्याकरण
• सार पुनर्लेखन - ग्राफ पुनर्लेखन का एक सामान्यीकरण

संदर्भ

स्रोत

• Rozenberg, Grzegorz (1997), Handbook of Graph Grammars and Computing by Graph Transformations, vol. 1–3, World Scientific Publishing, ISBN 9810228848.
• Perez, P.P. (2009), Matrix Graph Grammars: An Algebraic Approach to Graph Dynamics, VDM Verlag, ISBN 978-3-639-21255-6.
• हेकेल, आर. (2006). संक्षेप में ग्राफ परिवर्तन। सैद्धांतिक कंप्यूटर विज्ञान में इलेक्ट्रॉनिक नोट्स 148 (1 विनिर्देश आईएसएस।), पीपी। 187-198।
• कोनिग, बारबरा (2004)। गतिशील रूप से विकसित संरचना के साथ प्रणालियों का विश्लेषण और सत्यापन। Habilitation thesis, Universität Stuttgart, पीपी. 65–180।
• Lobo, Daniel; Vico, Francisco J.; Dassow, Jürgen (2011-10-01). "स्ट्रिंग-विनियमित पुनर्लेखन के साथ ग्राफ़ व्याकरण". Theoretical Computer Science. 412 (43): 6101–6111. doi:10.1016/j.tcs.2011.07.004. ISSN 0304-3975.
• Grzegorz Rozenberg, ed. (Feb 1997). नींव. Handbook of Graph Grammars and Computing by Graph Transformation. Vol. 1. World Scientific. doi:10.1142/3303. ISBN 978-981-02-2884-2.
• Hartmut Ehrig; Gregor Engels; Hans-Jörg Kreowski; Grzegorz Rozenberg, eds. (Oct 1999). अनुप्रयोग, भाषाएँ और उपकरण. Handbook of Graph Grammars and Computing by Graph Transformation. Vol. 2. World Scientific. doi:10.1142/4180. ISBN 978-981-02-4020-2.
• Hartmut Ehrig; Hans-Jörg Kreowski; Ugo Montanari; Grzegorz Rozenberg, eds. (Aug 1999). संगामिति, समानता और वितरण. Handbook of Graph Grammars and Computing by Graph Transformation. Vol. 3. World Scientific. doi:10.1142/4181. ISBN 978-981-02-4021-9.

श्रेणी:ग्राफ़ पुनर्लेखन