Program structure tree
प्रोग्राम स्ट्रक्चर ट्री (पी. एस. टी.) एक पदानुक्रमित आरेख है जो एकल-प्रविष्टि एकल-निकास (एस. ई. एस. ई.) टुकड़ों/क्षेत्रों के घोंसले के संबंध को प्रदर्शित करता है, जो एक कंप्यूटर प्रोग्राम के संगठन को दर्शाता है। इस पेड़ में नोड कार्यक्रम के एस. ई. एस. ई. क्षेत्रों का प्रतिनिधित्व करते हैं, जबकि किनारे घोंसले वाले क्षेत्रों का प्रतिनिधित्व करते हैं। पी. एस. टी. को सभी नियंत्रण प्रवाह ग्राफों के लिए परिभाषित किया गया है। ग्रंथसूचीगत टिप्पणियाँ इन टिप्पणियों में महत्वपूर्ण कार्यों को सूचीबद्ध किया गया है जो कार्यक्रमों और/या (कार्य) प्रवाह ग्राफ (खंड 3.5 इंच से अनुकूलित) के विश्लेषण पर अनुसंधान को बढ़ावा देते हैं। संपर्क गुण ग्राफ के मूल गुण हैं और यह परीक्षण करते समय उपयोगी होते हैं कि क्या ग्राफ समतल है या यह निर्धारित करते समय कि क्या दो ग्राफ समरूप हैं। जॉन हॉपक्राफ्ट और रॉबर्ट एंड्रे टार्जन (1973) ने एक ग्राफ को त्रिकोणीय घटकों में विभाजित करने के लिए एक इष्टतम (एक स्थिर कारक के भीतर) एल्गोरिथ्म विकसित किया। एल्गोरिथ्म ग्राफ की गहराई-पहली खोज पर आधारित है और शीर्ष और किनारों के साथ ग्राफ की जांच करने के लिए समय और स्थान की आवश्यकता होती है। रॉबर्ट एंड्रे टार्जन और जैकोबो वाल्डेस (1980) ने बाइकनेक्टेड फ्लो ग्राफ के संरचनात्मक विश्लेषण के लिए ट्राईकनेक्टेड घटकों का उपयोग किया। प्रवाह ग्राफ के दिशाहीन संस्करण के त्रिकोणीय घटकों को निर्देशित प्रवाह ग्राफ की संरचनात्मक जानकारी की खोज के लिए उपयोगी दिखाया गया है। ट्राइकनेक्टेड घटकों को कुशलता से खोजा जा सकता है और एक प्रवाह ग्राफ के एस. ई. एस. ई. टुकड़ों का एक पदानुक्रम बनाया जा सकता है। ग्यूसेप डी बतिस्ता और रॉबर्टो तामासिया (1990) ने एस. पी. क्यू. आर.-ट्री की शुरुआत की-एक डेटा संरचना जो अपने त्रिकोणीय घटकों के संबंध में एक द्विकोणीय ग्राफ के अपघटन का प्रतिनिधित्व करती है। अनिवार्य रूप से, एस. पी. क्यू. आर.-पेड़ टार्जन और वाल्डेस के पार्स पेड़ हैं। लेखकों ने विभिन्न ऑन-लाइन ग्राफ एल्गोरिदम के लिए एस. पी. क्यू. आर.-ट्री की उपयोगिता दिखाई, जैसे, ट्रांजिटिव क्लोजर, प्लेनेरिटी टेस्टिंग और मिनिमम स्पैनिंग ट्री। विशेष रूप से, लेखकों ने एक ग्राफ के त्रिकोणीय जुड़े घटकों के ऑनलाइन रखरखाव की समस्या का एक कुशल समाधान प्रस्तावित किया। रिचर्ड सी. जॉनसन और अन्य। (1994) ने एक प्रोग्राम स्ट्रक्चर ट्री (पी. एस. टी.) का प्रस्ताव रखा, जो एकल किनारे वाले प्रवेश और एकल किनारे वाले निकास क्षेत्रों पर आधारित प्रोग्राम संरचना का एक पदानुक्रमित प्रतिनिधित्व है। पी. एस. टी. की गणना एक मनमाने प्रवाह ग्राफ के लिए समय पर की जा सकती है, जहाँ ग्राफ में किनारों का सेट है। पी. एस. टी. का नुकसान यह है कि यह केवल धार प्रविष्टियों और निकास के आधार पर एस. ई. एस. ई. खंड की धारणा का फायदा उठाता है। इस प्रकार, पी. एस. टी. उन एस. ई. एस. ई. टुकड़ों को नहीं पकड़ता है जो शीर्ष प्रविष्टियों और निकास पर आधारित होते हैं। कार्स्टन गुटवेंगर और पेट्रा मुत्ज़ेल (2001) ने द्वि-संयोजित आलेखों के त्रिकोणीय घटकों की रैखिक समय गणना पर अपने व्यावहारिक अनुभव को साझा किया। उन्होंने एल्गोरिथ्म के दोषपूर्ण भागों की पहचान की है और उन्हें ठीक किया है और परिणामी एल्गोरिथ्म को एस. पी. क्यू. आर.-ट्री की गणना में लागू किया है। कार्यान्वयन सार्वजनिक रूप से उपलब्ध है। चुन ओयांग एट अल। (2006-2009) ने बी. पी. एम. एन. आरेखों को बी. पी. ई. एल. प्रक्रियाओं में अनुवादित करने के लिए पार्सिंग का उपयोग किया। एक टुकड़े की नियोजित धारणा एक क्षेत्र की धारणा के समान है। हालांकि, विकसित पार्सिंग एल्गोरिथ्म गैर-निर्धारक है, यानी, पार्स ट्री किसी दिए गए आरेख के लिए अद्वितीय नहीं है। जूसी वनहतालो एट अल। (2008-2009) ने परिष्कृत प्रक्रिया संरचना वृक्ष (RPST) की शुरुआत की। एक कार्यप्रवाह ग्राफ को देखते हुए, आर. पी. एस. टी. अद्वितीय, मॉड्यूलर है, और किसी भी अन्य ज्ञात पार्स ट्री की तुलना में महीन दानेदार है, यानी, यह किसी भी अन्य तकनीक की तुलना में अधिक एस. ई. एस. ई. टुकड़ों की खोज करता है। वास्तव में, आर. पी. एस. टी. एक कार्यप्रवाह ग्राफ के सभी विहित टुकड़ों को पकड़ता है, जो बदले में, ग्राफ के सभी एस. ई. एस. ई. टुकड़ों का प्रतिनिधित्व करता है। आर. पी. एस. टी. की गणना एक मनमाने कार्यक्रम/कार्यप्रवाह ग्राफ के लिए की जा सकती है। आर्टेम पॉलीवेनी, जूसी वानहाटालो और हेगन वोएलज़र (2010) ने आर. पी. एस. टी. की गणना के लिए एक सरलीकृत एल्गोरिथ्म का प्रस्ताव रखा। इस सरलीकृत एल्गोरिथ्म को एक मनमाने प्रोग्राम/वर्कफ़्लो ग्राफ़ के आर. पी. एस. टी. की गणना के लिए एक सबरूटीन के रूप में सीधे तरीके से नियोजित किया जा सकता है। दोनों एल्गोरिदम, मूल और सरलीकृत, आर. पी. एस. टी. की एक कुशल गणना की अनुमति देते हैं। हालाँकि, वे विहित एस. ई. एस. ई. टुकड़ों के विभिन्न संरचनात्मक लक्षण प्रदान करते हैं। बाहरी लिंक जे. बी. पी. टी. पुस्तकालय में परिष्कृत प्रक्रिया संरचना वृक्ष का जावा कार्यान्वयन (जे. बी. पी. टी.-डेको मॉड्यूल में आर. पी. एस. टी. वर्ग देखें)। कार्यान्वयन संदर्भ प्रोग्रामिंग निर्माण वृक्षों (डेटा संरचना) में वर्णित एल्गोरिदम का अनुसरण करता है।