Program structure tree
একটি প্রোগ্রাম স্ট্রাকচার ট্রি (পি. এস. টি) একটি শ্রেণিবদ্ধ চিত্র যা একক-প্রবেশ একক-প্রস্থান (এস. ই. এস. ই) টুকরো/অঞ্চলের বাসা বাঁধার সম্পর্ক প্রদর্শন করে, যা একটি কম্পিউটার প্রোগ্রামের সংগঠনকে দেখায়। এই গাছের নোডগুলি প্রোগ্রামের এস. ই. এস. ই অঞ্চলগুলির প্রতিনিধিত্ব করে, যেখানে প্রান্তগুলি বাসা বাঁধার অঞ্চলগুলির প্রতিনিধিত্ব করে। পি. এস. টি সমস্ত নিয়ন্ত্রণ প্রবাহ গ্রাফের জন্য সংজ্ঞায়িত করা হয়। গ্রন্থপঞ্জিগত নোট এই নোটগুলি গুরুত্বপূর্ণ কাজগুলির তালিকা করে যা প্রোগ্রাম এবং/অথবা (কাজের) ফ্লো গ্রাফের বিশ্লেষণের উপর গবেষণাকে উজ্জীবিত করে (বিভাগ 3.5 ইঞ্চি থেকে অভিযোজিত)। সংযোগ বৈশিষ্ট্যগুলি গ্রাফের মৌলিক বৈশিষ্ট্য এবং একটি গ্রাফ সমতলীয় কিনা বা দুটি গ্রাফ সমরূপ কিনা তা নির্ধারণ করার সময় কার্যকর হয়। জন হপক্রফ্ট এবং রবার্ট এন্ড্রে টারজান (1973) একটি গ্রাফকে ত্রি-সংযুক্ত উপাদানগুলিতে বিভক্ত করার জন্য একটি সর্বোত্তম (একটি ধ্রুবক ফ্যাক্টরের মধ্যে) অ্যালগরিদম তৈরি করেছিলেন। অ্যালগরিদমটি গ্রাফের গভীরতা-প্রথম অনুসন্ধানের উপর ভিত্তি করে এবং শীর্ষ এবং প্রান্ত সহ একটি গ্রাফ পরীক্ষা করার জন্য সময় এবং স্থান প্রয়োজন। রবার্ট এন্ড্রে টারজান এবং জ্যাকোবো ভালদেস (1980) দ্বি-সংযুক্ত প্রবাহ গ্রাফের কাঠামোগত বিশ্লেষণের জন্য ত্রি-সংযুক্ত উপাদান ব্যবহার করেছিলেন। একটি প্রবাহ গ্রাফের অনির্দিষ্ট সংস্করণের ত্রি-সংযুক্ত উপাদানগুলি নির্দেশিত প্রবাহ গ্রাফের কাঠামোগত তথ্য আবিষ্কারের জন্য দরকারী বলে দেখানো হয়েছে। ত্রি-সংযুক্ত উপাদানগুলি দক্ষতার সাথে আবিষ্কার করা যেতে পারে এবং একটি প্রবাহ গ্রাফের এস. ই. এস. ই টুকরোগুলির একটি শ্রেণিবিন্যাস গঠন করতে পারে। জুসেপ্পে ডি বাটিস্টা এবং রবার্তো তামাসিয়া (1990) এস. পি. কিউ. আর-গাছ প্রবর্তন করেন-একটি তথ্য কাঠামো যা তার ত্রিবাহী সংযুক্ত উপাদানগুলির সাপেক্ষে একটি দ্বি-সংযুক্ত গ্রাফের পচনকে উপস্থাপন করে। মূলত, এস. পি. কিউ. আর-গাছ হল টারজান এবং ভালদেসের পার্স গাছ। লেখকরা বিভিন্ন অনলাইন গ্রাফ অ্যালগরিদমের জন্য এসপিকিউআর-গাছের উপযোগিতা দেখিয়েছেন, যেমন, ট্রানজিটিভ ক্লোজার, প্ল্যানারিটি টেস্টিং এবং ন্যূনতম স্প্যানিং ট্রি। বিশেষত, লেখকরা একটি গ্রাফের ট্রাইকানেক্টেড উপাদানগুলির অনলাইন রক্ষণাবেক্ষণের সমস্যার একটি কার্যকর সমাধানের প্রস্তাব দিয়েছেন। রিচার্ড সি জনসন এবং অন্যান্য। (1994) একটি প্রোগ্রাম স্ট্রাকচার ট্রি (পি. এস. টি) প্রস্তাব করেছিলেন, যা একক প্রান্তের প্রবেশ এবং একক প্রান্তের প্রস্থান অঞ্চলের উপর ভিত্তি করে প্রোগ্রাম কাঠামোর একটি শ্রেণিবদ্ধ উপস্থাপনা। একটি নির্বিচারে প্রবাহ গ্রাফের জন্য পি. এস. টি সময়মতো গণনা করা যেতে পারে, যেখানে গ্রাফের প্রান্তগুলির সেট রয়েছে। পি. এস. টি-র অসুবিধা হল এটি শুধুমাত্র প্রান্ত এন্ট্রি এবং প্রস্থানের উপর ভিত্তি করে একটি এস. ই. এস. ই খণ্ডের ধারণাকে কাজে লাগায়। সুতরাং, পি. এস. টি সেই এস. ই. এস. ই-এর টুকরোগুলি ধারণ করে না যা ভার্টেক্স এন্ট্রি এবং প্রস্থানের উপর ভিত্তি করে। কার্স্টেন গাটওয়েঞ্জার এবং পেট্রা মুতজেল (2001) দ্বি-সংযুক্ত গ্রাফের ত্রি-সংযুক্ত উপাদানগুলির রৈখিক সময় গণনার উপর তাদের ব্যবহারিক অভিজ্ঞতা ভাগ করে নিয়েছেন। তারা অ্যালগরিদমের ত্রুটিপূর্ণ অংশগুলি চিহ্নিত ও সংশোধন করেছে এবং এসপিকিউআর-গাছের গণনায় ফলস্বরূপ অ্যালগরিদম প্রয়োগ করেছে। বাস্তবায়ন সর্বজনীনভাবে উপলব্ধ। চুন ওয়ুয়াং এবং অন্যান্য। (2006-2009) বিপিএমএন চিত্রগুলিকে বিপিইএল প্রক্রিয়াগুলিতে অনুবাদ করতে পার্সিং ব্যবহার করে। একটি খণ্ডের ব্যবহৃত ধারণাটি একটি অঞ্চলের ধারণার অনুরূপ। যাইহোক, উন্নত পার্সিং অ্যালগরিদম অ-নির্ধারক, অর্থাৎ, পার্স ট্রি একটি প্রদত্ত চিত্রের জন্য অনন্য নয়। জুসি ভানহাতালো এবং অন্যান্য। (2008-2009) রিফাইন্ড প্রসেস স্ট্রাকচার ট্রি (আরপিএসটি) চালু করেছে। একটি ওয়ার্কফ্লো গ্রাফের পরিপ্রেক্ষিতে, আর. পি. এস. টি অনন্য, মডুলার, এবং অন্য যে কোনও পরিচিত পার্স গাছের তুলনায় সূক্ষ্ম দানাদার, অর্থাৎ, এটি অন্য যে কোনও কৌশলের তুলনায় বেশি এস. ই. এস. ই টুকরো আবিষ্কার করে। প্রকৃতপক্ষে, আর. পি. এস. টি একটি ওয়ার্কফ্লো গ্রাফের সমস্ত ক্যানোনিকাল টুকরোগুলি ধারণ করে যা ফলস্বরূপ, গ্রাফের সমস্ত এস. ই. এস. ই টুকরোগুলি উপস্থাপন করে। একটি নির্বিচারে প্রোগ্রাম/ওয়ার্কফ্লো গ্রাফের জন্য আর. পি. এস. টি গণনা করা যেতে পারে। আর্টেম পলিভিয়ানি, জুসি ভানহাতালো এবং হ্যাগেন ভোলজার (2010) আর. পি. এস. টি গণনার জন্য একটি সরলীকৃত অ্যালগরিদম প্রস্তাব করেছিলেন। এই সরলীকৃত অ্যালগরিদমটি একটি স্বেচ্ছাচারী প্রোগ্রাম/ওয়ার্কফ্লো গ্রাফের আর. পি. এস. টি গণনার জন্য একটি সাবরুটিন হিসাবে সহজবোধ্য উপায়ে নিযুক্ত করা যেতে পারে। মূল এবং সরলীকৃত উভয় অ্যালগরিদমই আর. পি. এস. টি-র একটি দক্ষ গণনার অনুমতি দেয়। যাইহোক, তারা ক্যানোনিকাল এসইএসই টুকরোগুলির বিভিন্ন কাঠামোগত বৈশিষ্ট্য প্রদান করে। বাহ্যিক লিঙ্কগুলি জে. বি. পি. টি লাইব্রেরিতে রিফাইন্ড প্রসেস স্ট্রাকচার ট্রি-র জাভা বাস্তবায়ন (জে. বি. পি. টি-ডেকো মডিউলে আর. পি. এস. টি ক্লাস দেখুন)। প্রয়োগটি রেফারেন্স প্রোগ্রামিং কনস্ট্রাকটস ট্রি (ডেটা স্ট্রাকচার)-এ বর্ণিত অ্যালগরিদম অনুসরণ করে।