গ্রাফ থিওরি (পর্ব ৬)
প্রোগ্রামিং — ১
গ্রাফের মধ্যে ঘুরাঘুরি (চলবে)
এখন আমরা গত পর্বের বাকি পড়াটুকু শেষ করে ফেলবো। BFS কিভাবে কাজ করে সেটা আমরা গত পর্বে দেখে এসেছি। প্রথমে BFS এর কোড দেখে নিয়ে পরে ব্যাখ্যায় যাচ্ছি।
এখানে উল্লেখ্য যে, উপরের গ্রাফকে ইনপুট হিসেবে নিচের কোডে ব্যবহার করা হয়েছে।
কোড ০০৬(ক) অংশে আমরা আগের মতোই গ্রাফকে adjacency matrices এর মাধ্যমে স্টোর করেছি।
লাইন ৫৭ — এখানে একটি ফাংশন ডিক্লেয়ার করা হয়েছে, এই ফাংশনের মধ্যেই আমরা BFS এর যাবতীয় কাজ করবো।
লাইন ৫৮ — BFS কিভাবে কাজ করে সেটা যখন ব্যাখ্যা করা হয়েছিল গত পর্বে, সেখানে আমরা দেখেছিলাম যেকোন একটি নির্দিষ্ট নোড থেকে যাত্রা আরম্ভ করা যায় এবং সেখান থেকে তার সাথে যাদের এজ আছে সেখানে সেখানে যাওয়া যায়। ধরি, আমি ১ নং নোড থেকে ২ নং নোডে গেলাম। তাহলে কার অবস্থান আগে? ১ নং নোডের। একে আমরা parent node বলবো। আর যেখানে যাচ্ছি (২ নং নোড) তাকে child node বলবো। আমরা ফাংশনের মধ্যে বের করে ফেলবো কোন্ নোড কোন্ নোডের parent বা child। এই লাইনে সেটাই প্রকাশ করা হয়েছে।
লাইন ৫৯ — ছবি ৪৭ এর গ্রাফে ১ নং নোড থেকে ৬ নং নোডের দূরত্ব দুটি এজ। যেহেতু এটা unweighted graph তাই প্রতিটি এজের value ধরা হয়েছে ১। এখন প্রশ্ন হচ্ছে যে, unweighted graph কি?
ছবি ৪৮ এ একটি weighted graph দেখানো হয়েছে। কোন গ্রাফের প্রতিটি এজের সাথে যদি একটি করে মান দেয়া থাকে তবে তাকে আমরা weighted graph বলবো। এই মান অনেককিছুই প্রকাশ করতে পারে, যেমন উপরের গ্রাফে এক শহর (শহরকে এখানে নোড হিসেবে দেখানো হয়েছে) থেকে অন্য শহরের (অন্য নোডের) দূরত্ব বুঝানো হয়েছে এজগুলোর মান দিয়ে। আবার অন্য কোন গ্রাফে দেখা যাচ্ছে এজগুলোর মান দিয়ে এক শহর থেকে অন্য শহরে যেতে কত সময় লাগে সেটাও বুঝাতে পারে। এভাবে অনেককিছুই প্রকাশ করা যেতে পারে এইসকল মান দিয়ে।
যাই হোক, আমরা যে গ্রাফকে ইনপুট হিসেবে নিয়েছি সেটা unweighted graph। কেননা এর এজগুলোতে কোন মান দেয়া নেই। unweighted graph এর ক্ষেত্রে এজগুলোর মান একই (এক্ষেত্রে আমরা ‘১’ ধরেছি) ধরে নেয়া হয়। তাহলে ৫৯ নং লাইনে durotto[6] এর মান হবে ২।
কোড ০০৬(খ) এ আমরা DFS এর মত কিছু প্রয়োজনীয় জিনিসপত্র নিয়ে রেখেছি।
৮ নং লাইন — প্যারামিটার হিসেবে যে নোড থেকে শুরু করতে চাই সেটা নিয়ে নিবো।
১০-১৫ নং লাইন — DFS এর মত প্রথমে সব নোডগুলোকে সাদা রঙে রাঙিয়ে নিলাম। তবে এখানে আরও কিছু কাজ করা হয়েছে, সবগুলো নোডের দূরত্ব (কোথা থেকে দূরত্ব? অবশ্যই যে নোড থেকে শুরু করবো সেখান থেকে।) প্রথমে খুবই ছোট সংখ্যা ( INT_MIN) ধরে নিলাম। INT_MIN নিয়ে পরে সুযোগ পেলে কথা বলবো, তবে আপাতত জেনে রাখো এটা দিয়ে খুবই ছোট সংখ্যা বোঝায়। ১৪ নং লাইনে সবগুলো নোডের parent ঋণাত্মক ধরা হয়েছে। এগুলো আমরা পরে আপডেট করবো। এখন শুধু উল্টাপাল্টা কিছু ধরে রাখলাম।
১৬ নং লাইন — যে নোড থেকে শুরু করবো সেটার দূরত্ব অবশ্যই শূন্য, কেননা দূরত্ব আমরা মাপছি শুরুর নোড থেকেই। তাহলে নিজের সাথেই দূরত্ব শূন্যই হবে।
১৭ নং লাইন — শুরুর নোডের কোন parent নাই, সেখান থেকেই তো পথ চলা শুরু। তাই এখানে উল্টাপাল্টা মান দিয়ে দেয়া হয়েছে।
১৯-৪৩ নং লাইনের কাজকর্ম বোঝার জন্য আমাদেরকে প্রথমে আরেকটি standard template library (STL) সম্পর্কে জেনে নিতে হবে, যার নাম হচ্ছে queue। তাহলে নিচের কোডটি খেয়াল করি,
৫ নং লাইন — queue ডিক্লেয়ার করার পদ্ধতি। এখানে ইন্টিজার টাইপের ‘লাইন’ নামের queue ডিক্লেয়ার করা হয়েছে।
৬-৯ নং লাইন — queue মানে লাইন। আমরা যখন কোন টিকিট কাউন্টারের সামনে লাইন হয়ে দাঁড়াই তখন যে মানুষটি সব প্রথমে লাইনে দাঁড়িয়েছিলেন তিনি প্রথমে টিকিট পেয়ে লাইন থেকে বের হয়ে যান। এই STL এর ক্ষেত্রেও তাই ঘটবে। অর্থাৎ ডিক্লেয়ার করার সময় queue খালি থাকবে যেমনটা সবপ্রথমে লাইন থাকেনা, ধীরে ধীরে মানুষ এলে লাইন তৈরি হয়।
১০ নং লাইন — line.empty() দিয়ে queue টি খালি কিনা তা দেখা হয়। এই লাইনে আমরা একটি ‘হোয়াইল লুপ’ ব্যবহার করেছি। যতক্ষণ না queue টি খালি হবে, ততক্ষণ লুপটি চলবে। line.empty() এর সামনে ‘!’ (চিহ্ন দিয়ে ‘না’ বা ঋণাত্মক কিছু বুঝানো হয়।) চিহ্ন দিয়ে বুঝানো হয়েছে যে, queue টি খালি না।
১২ নং লাইন — line.front() দিয়ে queue এর প্রথম উপাদানটিকে নির্দেশ করা হয়। এই লাইনে আমরা প্রথম উপাদানটি একটি চলক (variable) এর মধ্যে রাখছি এবং পরে তা প্রিন্ট করছি।
১৪ নং লাইন — line.pop() দিয়ে queue এর প্রথম উপাদানটিকে মুছে (delete) দেয়া হয়। তাহলে ছবি ৪৯ এর ক্ষেত্রে যদি আমরা একবার pop()ফাংশনটি ব্যবহার করি তাহলে queue থেকে ‘৫’ মুছে গিয়ে ‘৯’ প্রথম উপাদান হিসেবে জায়গা করে নিবে, যেমনটা মানুষের লাইনে হয়। এই কারণে এই STL কে FIFO (First In First Out) বলা হয়। যে প্রথমে ঢুকবে, সে প্রথমেই বের হয়ে যাবে।
আশা করছি queue সম্পর্কে মোটামুটি ধারণা তৈরি হয়েছে তোমাদের। এবার আমরা তাহলে কোড ০০৬(গ) এর ১৯-৪৩ নং লাইনের দিকে মনোযোগ দিতে পারি।
১৯ নং লাইন — q নামের একটি ইন্টিজার টাইপের queue ডিক্লেয়ার করা হয়েছে।
২০ নং লাইন — যে নোড থেকে আমরা গ্রাফে চলা শুরু করবো সেই নোডকে (startingNode) queue এর মধ্যে ঢুকিয়ে দিলাম, তাহলে ১৯ নং লাইনের ফাঁকা queue এখন আর ফাঁকা থাকলোনা, এর মধ্যে এখন উপাদান সংখ্যা একটি।
২১ নং লাইন — এখানে একটি ‘হোয়াইল লুপ’ ব্যবহার করা হয়েছে, যার শর্ত হচ্ছে যতক্ষণ queue টি ফাঁকা না হবে ততক্ষণ এটি কাজ করতে থাকবে। যেমনি queue টি ফাঁকা হয়ে যাবে ‘হোয়াইল লুপ’ এর কাজ শেষ হয়ে যাবে।
২৩-২৪ নং লাইন — queue এর প্রথম উপাদানটিকে গ্রহণ করার বন্দোবস্ত করা হয়েছে।
২৫ নং লাইন — প্রথম উপাদানটিকে বিদায় করে দেয়া হল। এখন কিন্তু আমাদের queue ফাঁকা হয়ে গেলো, কারণ ওই একটাই উপাদান ছিল আরকি। তাহলে কি এখনি ‘হোয়াইল লুপ’ কাজ করা বন্ধ করে দিবে? মোটেও না। লুপের শেষে গিয়ে কাজ করা বন্ধ করবে, যদি না এর মধ্যে আবার queue এ উপাদান ঢোকে।
২৬ নং লাইন — যেহেতু আমরা এবার ওই বিদায় করে দেয়া উপাদানের কাজ শুরু করবো, তাই একে সাদা থেকে ছাই রঙা করে দেয়া হল। পরের লাইনে একে প্রিন্ট করে দিলাম।
২৯-৪০ নং লাইন — এই লাইনগুলোর প্রধান কাজ হচ্ছে, যাকে নিয়ে কাজ শুরু হয়েছে তার সাথে কার কার এজ আছে সেটা বের করা। বের হলে, সেই নোডের রঙ সাদা আছে কিনা সেটা দেখা। যদি থাকে, তাহলে তাদের মধ্যে হিসাব করা হবে। ৩৫-৩৭ নং লাইনের কথা পরে বলছি।
৪১ নং লাইন — আমরা যেহেতু BFS পড়ছি, এক্ষেত্রে যে নোড দিয়ে শুরু করা হয় তার সবগুলোর প্রতিবেশী নোডেই ঘুরে আসা হয়। অর্থাৎ এই নোডের কাজ একেবারেই শেষ হয়ে যায়। তাই একে কালো করে দেয়া হয়েছে।
৩৫ নং লাইন — এক্ষেত্রে x হচ্ছে শুরুর নোড। এই x এর সাথে যে যে i এর সম্পর্ক আছে তারা x থেকেই বের হয়েছে। তাহলে x হচ্ছে parent এবং i গুলো হচ্ছে child।
৩৬ নং লাইন — শুরুর নোডটিকে ২০ নং লাইনে queue এর মধ্যে ঢুকিয়ে দিয়ে ওকে পরবর্তীতে x চলকের মধ্যে রেখে দিয়ে খুঁজে দেখলাম কার কার সাথে x এর সম্পর্ক আছে। এই লাইনে ওদেরকে (i) নতুন করে x এর মধ্যে ঢুকিয়ে নেয়া হল, এবার এরা আবার শুরুর নোড হিসেবে কাজ করবে।
৩৭ নং লাইন — parent তো আগে থাকে, তাইনা? তাহলে parent এর দূরত্বের সাথে ‘১’ যোগ করলে বাচ্চাকাচ্চার দূরত্ব পাওয়া যাবে, কেননা child পরে থাকে।
তাহলে আমাদের BFS ও পড়া শেষ হলো।
এবার তাহলে জনাব অয়লার সম্পর্কে আরেকটি তথ্য জেনে নেয়া যাক। অতিরিক্ত গবেষণার ও লেখালেখির কারণে বেশ অল্প বয়সেই অয়লার উনার ডানচোখের দৃষ্টিশক্তি হারিয়ে ফেলেন। কাজের চাপ অয়লারের জীবনে সবসময়ই ছিল। ৫৯ বছর বয়সে অয়লার তাঁর বাকি ভালো চোখটাও হারিয়ে ফেলে পুরো অন্ধ হয়ে যান।
