Program structure tree
પ્રોગ્રામ સ્ટ્રક્ચર ટ્રી (પી. એસ. ટી.) એ એક અધિક્રમિક આકૃતિ છે જે સિંગલ-એન્ટ્રી સિંગલ-એક્ઝિટ (એસ. ઇ. એસ. ઇ.) ટુકડાઓ/પ્રદેશોના માળાના સંબંધને દર્શાવે છે, જે કમ્પ્યુટર પ્રોગ્રામની સંસ્થાને દર્શાવે છે. આ વૃક્ષના ગાંઠો કાર્યક્રમના એસ. ઇ. એસ. ઇ. પ્રદેશોનું પ્રતિનિધિત્વ કરે છે, જ્યારે ધાર માળાના પ્રદેશોનું પ્રતિનિધિત્વ કરે છે. પી. એસ. ટી. તમામ નિયંત્રણ પ્રવાહ આલેખ માટે વ્યાખ્યાયિત થયેલ છે. ગ્રંથસૂચિ નોંધો આ નોંધો મહત્વપૂર્ણ કાર્યોની યાદી આપે છે જેણે કાર્યક્રમોના વિશ્લેષણ અને/અથવા (કાર્ય) પ્રવાહ આલેખ (વિભાગ 3.5 ઇંચમાંથી અનુકૂલિત) પર સંશોધનને પ્રોત્સાહન આપ્યું હતું. જોડાણ ગુણધર્મો આલેખના મૂળભૂત ગુણધર્મો છે અને આલેખ સમતલીય છે કે નહીં તે ચકાસતી વખતે અથવા બે આલેખ સમરૂપ છે કે નહીં તે નક્કી કરતી વખતે ઉપયોગી છે. જ્હોન હોપક્રોફ્ટ અને રોબર્ટ એન્ડ્રે ટાર્જન (1973) એ આલેખને ત્રિકોણીય ઘટકોમાં વિભાજિત કરવા માટે શ્રેષ્ઠ (સતત પરિબળની અંદર) અલ્ગોરિધમ વિકસાવ્યું હતું. અલ્ગોરિધમ આલેખની ઊંડાઈ-પ્રથમ શોધ પર આધારિત છે અને શિરોબિંદુઓ અને ધારવાળા આલેખની તપાસ કરવા માટે સમય અને જગ્યાની જરૂર પડે છે. રોબર્ટ એન્ડ્રે ટાર્જન અને જેકોબો વાલ્ડેસે (1980) દ્વિ-જોડાયેલા પ્રવાહ આલેખના માળખાકીય વિશ્લેષણ માટે ત્રિકોણીય જોડાયેલા ઘટકોનો ઉપયોગ કર્યો હતો. પ્રવાહ આલેખના દિશાહીન સંસ્કરણના ત્રિકોણીય જોડાયેલા ઘટકો નિર્દેશિત પ્રવાહ આલેખની માળખાકીય માહિતી શોધવા માટે ઉપયોગી હોવાનું દર્શાવવામાં આવ્યું છે. ત્રિકોણીય જોડાયેલા ઘટકોને અસરકારક રીતે શોધી શકાય છે અને પ્રવાહ આલેખના એસ. ઇ. એસ. ઇ. ટુકડાઓનો પદાનુક્રમ બનાવી શકાય છે. જિયુસેપ ડી બટ્ટિસ્ટા અને રોબર્ટો તામાસિયાએ (1990) એસ. પી. ક્યુ. આર.-વૃક્ષો રજૂ કર્યા-એક માહિતી માળખું જે તેના ત્રિકોણીય જોડાયેલા ઘટકોના સંદર્ભમાં દ્વિ-જોડાયેલા આલેખના વિઘટનને રજૂ કરે છે. અનિવાર્યપણે, એસ. પી. ક્યુ. આર.-વૃક્ષો ટાર્જન અને વાલ્ડેઝના પાર્સ વૃક્ષો છે. લેખકોએ વિવિધ ઓન-લાઇન ગ્રાફ અલ્ગોરિધમ્સ માટે એસ. પી. ક્યુ. આર.-વૃક્ષોની ઉપયોગીતા દર્શાવી હતી, દા. ત., સંક્રમક બંધ, પ્લેનેરિટી પરીક્ષણ અને લઘુત્તમ સ્પૅનિંગ ટ્રી. ખાસ કરીને, લેખકોએ આલેખના ત્રિકોણીય જોડાયેલા ઘટકોની ઓનલાઇન જાળવણીની સમસ્યાનું કાર્યક્ષમ સમાધાન સૂચવ્યું હતું. રિચાર્ડ સી. જોહ્ન્સન અને અન્ય. (1994) એ પ્રોગ્રામ સ્ટ્રક્ચર ટ્રી (પી. એસ. ટી.) ની દરખાસ્ત કરી હતી, જે સિંગલ એજ એન્ટ્રી અને સિંગલ એજ એક્ઝિટ પ્રદેશો પર આધારિત પ્રોગ્રામ સ્ટ્રક્ચરની અધિક્રમિક રજૂઆત છે. મનસ્વી પ્રવાહ આલેખ માટે પી. એસ. ટી. ની ગણતરી સમયસર કરી શકાય છે, જ્યાં આલેખમાં ધારોનો સમૂહ છે. પી. એસ. ટી. નો ગેરલાભ એ છે કે તે માત્ર ધાર એન્ટ્રીઓ અને બહાર નીકળવાના આધારે એસ. ઇ. એસ. ઇ. ટુકડાની કલ્પનાનો ઉપયોગ કરે છે. આમ, પી. એસ. ટી. તે એસ. ઇ. એસ. ઇ. ના ટુકડાઓ મેળવતું નથી જે શિરોબિંદુ પ્રવેશો અને બહાર નીકળવાના માર્ગો પર આધારિત હોય. કાર્સ્ટન ગુટવેન્જર અને પેટ્રા મુત્ઝેલ (2001) એ બાયકનેક્ટેડ ગ્રાફના ત્રિકોણીય જોડાયેલા ઘટકોની રેખીય સમય ગણતરી પર તેમના વ્યવહારુ અનુભવને શેર કર્યો. તેઓએ અલ્ગોરિધમનોના ખામીયુક્ત ભાગોને ઓળખી કાઢ્યા છે અને તેમાં સુધારો કર્યો છે અને પરિણામી અલ્ગોરિધમને એસ. પી. ક્યુ. આર.-વૃક્ષોની ગણતરીમાં લાગુ કર્યું છે. અમલીકરણ સાર્વજનિક રીતે ઉપલબ્ધ છે. ચુન ઓયુયાંગ એટ અલ. (2006-2009) બી. પી. એમ. એન. આકૃતિઓને બી. પી. ઈ. એલ. પ્રક્રિયાઓમાં અનુવાદિત કરવા માટે પદચ્છેદનનો ઉપયોગ કરે છે. ટુકડાની કાર્યરત કલ્પના એ પ્રદેશમાં એક પ્રદેશની કલ્પના જેવી જ છે. જો કે, વિકસિત પદચ્છેદન અલ્ગોરિધમ બિન-નિર્ધારિત છે, એટલે કે, પદચ્છેદન વૃક્ષ આપેલ આકૃતિ માટે અનન્ય નથી. જુસ્સી વન્હાતાલો એટ અલ. (2008-2009) એ રિફાઈન્ડ પ્રોસેસ સ્ટ્રક્ચર ટ્રી (RPST) રજૂ કર્યું. વર્કફ્લો ગ્રાફને જોતાં, આર. પી. એસ. ટી. અનન્ય, મોડ્યુલર છે, અને અન્ય કોઈપણ જાણીતા પાર્સ વૃક્ષ કરતાં વધુ સારી રીતે દાણાદાર છે, એટલે કે, તે અન્ય કોઈપણ તકનીક કરતાં વધુ એસ. ઇ. એસ. ઇ. ટુકડાઓ શોધે છે. હકીકતમાં, આર. પી. એસ. ટી. વર્કફ્લો ગ્રાફના તમામ કેનોનિકલ ટુકડાઓ મેળવે છે, જે બદલામાં, ગ્રાફના તમામ એસ. ઇ. એસ. ઇ. ટુકડાઓનું પ્રતિનિધિત્વ કરે છે. આર. પી. એસ. ટી. ની ગણતરી મનસ્વી પ્રોગ્રામ/વર્કફ્લો ગ્રાફ માટે કરી શકાય છે. આર્ટેમ પોલીવેની, જુસી વાનહાટાલો અને હેગન વોએલઝર (2010) એ આર. પી. એસ. ટી. ની ગણતરી માટે એક સરળ અલ્ગોરિધમનો પ્રસ્તાવ મૂક્યો હતો. આ સરળીકૃત અલ્ગોરિધમનો ઉપયોગ મનસ્વી પ્રોગ્રામ/વર્કફ્લો ગ્રાફના આર. પી. એસ. ટી. ની ગણતરી માટે સબરૂટિન તરીકે સીધી રીતે કરી શકાય છે. બંને એલ્ગોરિધમ્સ, મૂળ અને સરળ, આર. પી. એસ. ટી. ની કાર્યક્ષમ ગણતરી માટે પરવાનગી આપે છે. જો કે, તેઓ કેનોનિકલ એસ. ઇ. એસ. ઇ. ટુકડાઓની વિવિધ માળખાકીય લાક્ષણિકતાઓ પ્રદાન કરે છે. બાહ્ય કડીઓ જે. બી. પી. ટી. લાઈબ્રેરીમાં રિફાઈન્ડ પ્રોસેસ સ્ટ્રક્ચર ટ્રીનું જાવા અમલીકરણ (જે. બી. પી. ટી.-ડેકો મોડ્યુલમાં આર. પી. એસ. ટી. વર્ગ જુઓ). અમલીકરણ સંદર્ભ પ્રોગ્રામિંગ કન્સ્ટ્રક્ટ્સ ટ્રીઝ (ડેટા સ્ટ્રક્ચર્સ) માં વર્ણવેલ અલ્ગોરિધમનો અનુસરે છે.