গ্রাফ থিওরি (পর্ব ৭)
প্রোগ্রামিং — ১
প্রফেসর বামস্টিড সাহেবের সাজুগুজু
Thomas H. Cormen, Charles E. Leiserson, Ronald Rivest, Clifford Stein কর্তৃক রচিত Introduction to Algorithms বইটি সম্পর্কে প্রোগ্রামিং পথের সব পথিকেরা মোটামুটি জ্ঞাত। এই বইয়ের ‘গ্রাফ থিওরি’ অংশটি পড়ার সময় Henry Andrews Bumstead এর নামটি পেলাম। খানিকটা খোঁজাখুঁজির পর দেখলাম এই ভদ্রলোক ইয়েল বিশ্ববিদ্যালয়ের পদার্থবিজ্ঞানের প্রফেসর ছিলেন দীর্ঘদিন। জ্বী, ইয়েল বিশ্ববিদ্যালয়। বিশ্বের অন্যতম সেরা বিদ্যাপীঠ। উল্লেখিত বই থেকে একটি স্ক্রিনশট দিচ্ছি এখানে।
এই পর্যায়ে এসে আমার মনে প্রশ্ন জাগলো প্রফেসর বামস্টিডের সাথে এই বইয়ের লেখকদের কি সম্পর্ক। কিন্তু আমি জানতে পারলাম যে, একটা বিখ্যাত কার্টুন চরিত্র আছে যার নাম Dagwood Bumstead। এই চরিত্রটি প্রায় সবসময় স্যুটেড-ব্যুটেড অবস্থায় থাকে তাই লেখকেরা মজা করে উদাহরণ হিসেবে তাকে গ্রহণ করেছেন। উপরের উদাহরণের সাথে আসলে বাস্তবের প্রফেসর বামস্টিডের কোন যোগাযোগ নেই।
আচ্ছা বেশ খানিকটা গল্প হলো, এবার পড়াশোনায় মনোযোগ দেয়া যাক। উপরের ছবিটি ভালো করে খেয়াল করলে দেখা যাবে যে, এটি একটি directed graph। আমি আশা করছি তোমাদের directed graph কি, সেটা মনে আছে।
প্রশ্ন হচ্ছে যে, উপরের ছবিটির কাজ কি এখানে? সেটা বোঝার জন্য আমরা ধাপে ধাপে আগাবো। প্রথমেই আমরাকে directed acyclic graph (DAG) সম্পর্কে জেনে নিতে হবে এবং সেটার জন্য নিচের ছবিটি খেয়াল করা যেতে পারে,
ছবি ৫১ এর (১) নং গ্রাফটি খেয়াল করি, প্রতিটি এজের দিক নির্দেশ করা আছে অর্থাৎ এটি একটি directed graph। সাথে আরেকটি ব্যাপার, আমরা যদি a নোড থেকে যাত্রা আরম্ভ করে b নোডে যেয়ে c নোডের দিকে যেতে চাই, সেটা সম্ভব হবেনা। কারণ b থেকে c তে যাওয়ার উপায় নেই (তীরচিহ্নটি খেয়াল করো)। আবার যদি a নোড থেকে যাত্রা আরম্ভ করে c নোডে যেয়ে b নোডের দিকে যেতে চাই, সেটা সম্ভব। কিন্তু b থেকে a তে যাওয়া যাবেনা (তীরচিহ্ন উল্টাদিকে আছে)। তাহলে যা দেখা গেলো সেটা হচ্ছে যে, a নোড থেকে যাত্রা আরম্ভ করে আবার a নোডে ফিরে আসা যাচ্ছেনা। অর্থাৎ এখানে কোন cycle বা চক্র তৈরি হয়নি মানে এটি acyclic। তাহলে (১) নং গ্রাফটিকে বলা যায় এটি একটি DAG। ঠিক একই কারণে (২) নং গ্রাফটি DAG নয়।
তোমরা ছবি ৫০ এর গ্রাফটি (জ্বী, এটি অবশ্যই একটি গ্রাফ। জামা-কাপড়, জুতা-মোজা এগুলো নোড বুঝাচ্ছে এবং সাথে একগাদা এজ তো আছেই।) ভালোভাবে খেয়াল করলে দেখবে যে এটিও একটি DAG।
তোমাদের কি DFS এর কর্মপদ্ধতি মনে আছে? না মনে থাকলে চট করে পর্ব ৫ পড়ে আসো। সেখানে আমরা দেখেছি যে, একটি নির্দিষ্ট নোড থেকে যাত্রা আরম্ভ করে বিভিন্ন নোডে চলে যাওয়া যায়। যখন আমরা কোন “একটি নোড থেকে যাত্রা আরম্ভ করি” তার মানে কি? ওই নোডটিকে আমরা আবিষ্কার করলাম, ওই মুহূর্তটিকে বলা হয় আবিষ্কারের সময় বা discovery time। ওই নোডের কাজ শেষ হয়ে গেলে আমরা তার finishing time টাও লিখে রাখতে পারি। আমরা এখন ছবি ৫০ কে একটু পাল্টিয়ে (জামা-কাপড়ের নামের জায়গায় ১, ২, ৩ ইত্যাদি সংখ্যা লিখবো) প্রতিটি নোডের discovery time ও finishing time বের করার চেষ্টা করবো।
আমাদের ইচ্ছামত নোড থেকে শুরু করতে পারি হিসাব-নিকাশ। ছবি ৫০ এ ওরা shirt বা ৪ নং নোড থেকে যাত্রা শুরু করেছে। আমরা এখানে ছবি ৫২ এ ১ নং নোড থেকে শুরু করবো। তুমি ইচ্ছা করলে অন্য কোথাও থেকে শুরু করতে পারো। যাই হোক তাহলে শুরু করা যাক।
কিভাবে সময় (কখন আবিষ্কার করছি বা যাত্রা শেষ করছি তার সময়) হিসাব করবো সেটার নিয়ম বলে দিই। আমরা ১ নং নোড থেকে যাত্রা শুরু করছি, তাহলে ১ নং নোডের discovery time হচ্ছে ১ (মানে প্রথম সেকেন্ডেই [তুমি সময়ের যেকোন একক ব্যবহার করতে পারো] ১ নং নোড আবিষ্কার হয়েছে)। এর নিয়ম অনুযায়ী আমরা ১ নং নোডের সাথে যাদের সম্পর্ক আছে সেসব নোডে যাবো। মনে কর, ১ নং নোড থেকে গেলাম ২ নং নোডে (যদিও ৮ নং নোডেও যাওয়া যেত, ওইযে তোমার ইচ্ছা)। তাহলে ২ নং নোডও আবিষ্কার হয়ে গেলো। তাহলে ২ নং নোডের discovery time হচ্ছে ২। ২ নং নোড থেকে মনে কর গেলাম ৩ নং নোডে, তাহলে ৩ নং নোডের discovery time হচ্ছে ৩। এবার ৩ নং নোড থেকে গেলাম ৬ নং নোডে। তাহলে ৬ নং নোডের discovery time হচ্ছে ৪। এবার আমরা উপরের ছবিটি নতুন করে অঙ্কন করি।
ছবি ৫৩ এর (১) নং অংশে স্ল্যাশ চিহ্নের (/) বামপাশে আমরা discovery time উল্লেখ করেছি এবং ডানপাশটা finishing time এর জন্য ফাঁকা রেখে দিয়েছি।
আবার শুরু করা যাক, ৬ নং নোডে এসে কোন রাস্তা পাচ্ছিনা সামনের যাওয়ার। তাহলে এবার আমরাকে backtracking করে যেখান থেকে ৬ নং নোডে এসেছিলাম অর্থাৎ ৩ নং নোডে ফেরত যেতে হবে এবং সাথে সাথে ৬ নং নোডের কাজ শেষ হয়ে যাওয়ায়, এখানে finishing time হিসেবে ৫ লিখে দিতে হবে (ছবি ৫৩ এর (২) নং অংশ)।
৩ নং নোডেও এসে দেখা যাচ্ছে একই অবস্থা। কোন দিকে আগানো যাচ্ছেনা, তাহলে পেছনে সরে গিয়ে ২ নং নোডে যাবো এবং সাথে ৩ নং নোডের finishing time হিসেবে ৬ লিখে দিবো (সময় এক এক করে বাড়ছে আরকি!)। (ছবি ৫৩ এর (২) নং অংশ)
এবার ২ নং নোড থেকে ৮ নং নোডে যাওয়ার সুযোগ আছে দেখা যাচ্ছে। তাহলে যাই আমরা ৮ নং নোডে, এটা আবিষ্কার হয়ে গেলো। তাহলে ৮ নং নোডের discovery time হিসেবে ৭ লিখে দিয়ে আমরা দেখছি যে এখান থেকে আর কোন দিকে যাওয়া যাচ্ছেনা। তারমানে ৮ নং নোডেরও কাজ শেষ। তাহলে সাথে সাথে এর finishing time হিসেবে ৮ লিখে দেয়া যায়। এবার backtracking করে ২ নং নোডে এসেও একই অবস্থা, তাহলে ২ নং নোডের finishing time হবে ৯। ‘২’ থেকে ‘১’ এ এসে ১০ লিখা যায়। (চিত্র ৫৪ এর (১) নং অংশ)
আমাদের সময়ের এখন পর্যন্ত ১০ একক পর্যন্ত পৌঁছেছে। এবার যে সকল নোড এখনও ঘুরে দেখা হয়নি তাদের দিকে মনোযোগ দেয়া যেতে পারে। যেমন ৪ নং নোড। তাহলে ৪ নং নোড থেকে নতুন যাত্রা শুরু করলে এর discovery time হবে ১১। ‘৪’ থেকে ‘৫’ এ যাওয়া যায়, তাহলে এর ক্ষেত্রে discovery time হবে ১২। (ছবি ৫৪ এর (২) নং অংশ)
১২ নং নোড থেকে অন্য কোথাও যাওয়া যাচ্ছেনা অর্থাৎ এর কাজ শেষ। তাহলে এর finishing time হবে ১৩। এবার পেছনে ফিরে ‘৪’ এ এসে দেখা যাচ্ছে যে, এরও কাজ শেষ তাহলে ৪ নং নোডের finishing time হবে ১৪। (ছবি ৫৫ এর (১) নং অংশ)
একই নিয়ম মেনে ছবি ৫৫ এর (২) নং অংশে ৭ ও ৯ নং নোডেরও discovery time ও finishing time বসিয়ে দিয়েছি।
এবার আমরা সবগুলো নোডের finishing time গুলো দেখবো। যার finishing time যত বেশি সেই কাজ তত আগে করতে হবে। এখানে আমরা দেখতে পাচ্ছি যে, ৯ নং নোডের finishing time সবচেয়ে বেশি। তাহলে ৯ নং নোডকে সব আগে ঘুরে দেখতে হবে। তারপর? আচ্ছা সবার finishing time গুলো নিচে লিখে ফেলি।
নোড নম্বরের পাশে ব্র্যাকেটের মধ্যে finishing time দিয়ে লিখলে আমরা পাই,
৯(১৮) — ৭(১৬) — ৪(১৪) — ৫(১৩) — ১(১০) — ২ (৯) — ৮(৮) — ৩(৬) — ৬(৫)
এবার ছবি ৫০ এর সাথে তুলনা করলে আমরা পাই,
watch — socks — shirt — tie — undershorts — pants — shoes — belt — jacket
উপরের ক্রম অনুযায়ী Professor Bumstead বিভিন্ন উপকরণ দিয়ে সাজুগুজু করলে কোন সমস্যা নাই। কিন্তু উনি যদি মোজা পরার আগে জুতা পরতেন বা শার্ট পরার আগে টাই পরতেন তাহলে ঝামেলা হতো।
এ ধরনের ordering বা sorting কে topological sort বলে।
এখন সময় এসেছে এর প্রোগ্রাম লিখে বিশ্লেষণ করে ফেলার। আমরা ইতিমধ্যেই DFS এর প্রোগ্রাম দেখেছি। যেহেতু topological sort এর মূল চিন্তা ভাবনা DFS এর ওপর প্রতিষ্ঠিত তাই আমরা এর কোডকে একটু এদিক ওদিক করলেই topological sort এর প্রোগ্রাম পেয়ে যাবো।
তাহলে শুরু করা যাক।
এখানে শুধু ৬ নং লাইনটা নতুন, বাকি সবকিছু DFS এর কোডের অনুরূপ। ৭ নং লাইনে দুটো অ্যারে ও একটি ভ্যারিয়েবল ঘোষণা দেয়া হয়েছে আরকি। কোডের পরবর্তী অংশে এদের কাজ বোঝা যাবে।
উপরের অংশে (কোড ০০৮(খ)) শুধু ১৩ ও ২৩ নং লাইন নতুন। ১২ নং লাইনে যখন আমরা কোন নোডের মধ্যে যাত্রা শুরু করছি, সেটার starting time (discovery time) টা আমরা ১৩ নং লাইনে এসে লিখে দিচ্ছি। খেয়াল করে দেখো শেষে time++ করা হয়েছে অর্থাৎ পরবর্তীর জন্য সময়ের মান এক বাড়িয়ে দেয়া হয়েছে। ২২ নং লাইনে যখন উপরোক্ত নোডের কাজ শেষ হয়ে যাচ্ছে তখন ২৩ নং লাইনে তার finishing time লিখে রাখা হচ্ছে।
এই অংশে কোন পরিবর্তন নেই।
এটি directed graph তাই আগের মতো somporko[v2][v1]=1 লাইনটি আর নেই। ৪৭ নং লাইনে প্রিন্টের কাজ ছাড়া নতুন কিছু নেই।
লিওনার্দ অয়লার এর নামে একটি সংখ্যা আছে ক্যালকুলাসে, যাকে e দ্বারা প্রকাশ করা হয় এবং এর মান 2.71828 (প্রায়)।
