পাইথন ডেকোরেটর: পর্ব - ১

পাইথন ডেকোরেটর: পর্ব - ১
২১ জুন, সোমবার, ২০২১

বেসিক পাইথন আমি মোটামুটি জানি। টুকটাক কাজও করেছি। কিন্তু পাইথনের এডভান্সড জিনিসপত্র শিখবো শিখবো করেও শেখা হচ্ছিল না। বেসিক পাইথনের আমি যতটুকু জানি, তার কমবেশি আমার "সহজ বাংলায় পাইথন" আর "সহজ বাংলায় পাইথনে ডেটা স্ট্রাকচার" ইউটিউব ভিডিও সিরিজের ভিডিওগুলোতে আলোচনা করেছি। এই ভিডিও গুলোর একটা সুবিধা হচ্ছে, অনেকেই অনেক সময় কমেন্ট করে নতুন কোনো টপিকের উপর ভিডিও বানানোর অনুরোধ করেন। সেইরকম একটা অনুরোধ ছিল এই পাইথন ডেকোরেটর। কাজেই বুঝতে পারছেন, আমি নিজে শিখে আজকে কিছু লেখার চেষ্টা করছি। কোত্থেকে শিখছি সেটার সম্পর্কেও একটু বলি। আমাদের ডিপার্টমেন্টের জুনিয়র, ফরহাদ নাঈমের কাছ থেকে পাইথনের উপর লুসিয়ানো রামালহো-র লেখা 'ফ্লুয়েন্ট পাইথন' বইটার নাম জেনেছিলাম। ফরহাদ খুবই কাজের একটা ছেলে, ওর টেকনোলজির উপর দখল অনেক ভালো। ওর কথাতেই বইটা একটু ঘাঁটাঘাঁটি করে দেখে আমি মুগ্ধ। খুবই ভালো বই। আজকের পুরো লেখাটাই এই বইয়ের 'Function Decorators and Closures' - চ্যাপ্টারের প্রথম অংশ থেকে নেয়া - নিজের মতো করে লেখার চেষ্টা করছি।    

পাইথন ডেকোরেটর বোঝার জন্য কয়েকটা জিনিস জানতে হবে: সবগুলোই এক এক করে উদাহরণ দিয়ে পরিষ্কার করার চেষ্ঠা করছি: 

• ১. পাইথন 'ফার্স্ট ক্লাস' ফাঙ্কশন সাপোর্ট করে  - অর্থাৎ, পাইথনে ফাঙ্কশন একটা অবজেক্ট। 

একটা ফাঙ্কশনকে কোনো ভ্যারিয়বলে -এ এসাইন করা, অন্য ফাঙ্কশনে প্যারামিটার হিসাবে পাস্ করা, অন্য ফাঙ্কশন থেকে রিটার্ন করা, কোনো ডেটা স্ট্রাকচার (যেমন, পাইথন লিস্ট, ডিকশনারী, সেট ইত্যাদি) -এ স্টোর করা যায়। নিচের ছবি ১ ও ২ খেয়াল করলে প্রথম দুইটা ব্যাপার পরিষ্কার হবে। 

ছবি ১: একটা ফাঙ্কশনকে অন্য ভেরিএবলে এসাইন করিয়ে, সেটা দিয়ে অন্য নামে কল করা যায় 

ছবি - ২ -, লাইন ১৪ তে  bar() ফাঙ্কশন foo ফাঙ্কশনকে প্যারামিটার হিসাবে নিলো, নিজে 'Inside bar  ...' প্রিন্ট করে তারপর foo ফাঙ্কশন কল করলো, যেটা 'Inside foo  ...' প্রিন্ট করলো।       

ছবি ২: একটা ফাঙ্কশন অন্য ফাঙ্কশনকে প্যারামিটার হিসাবে নিয়ে কল করতে পারে 

• ২. দুটো ফাঙ্কশন মাথায় রাখতে হবে, প্রথমটা হচ্ছে টার্গেট ফাঙ্কশন - যেটাকে ডেকোরেট (বা সাজানো) হবে, আর দ্বিতীয়টা হচ্ছে ডেকোরেটর ফাঙ্কশন, যেটা কিনা টার্গেট মেথডকে ডেকোরেট করবে বা সাজাবে।

আর এজন্য টার্গেট মেথডের শুরুতে '@' চিহ্ন ব্যবহার করে ডেকোরেটর মেথডের নাম লিখে দিতে হয়। এযেন টার্গেটের কানে দুল পরিয়ে সাজিয়ে দেয়া 😀। আসলে ডেকোরেটর মেথড টার্গেট মেথডকে প্যারামিটার হিসাবে নেয়। ডেকোরেটর মেথড নিজের মধ্যে অন্য কিছু করতে পারে, তারপর পাস্ হওয়া টার্গেট মেথড কল করতে পারে। সব কাজ শেষ হলে, রিটার্ন করতে পারে অরিজিনাল টার্গেট মেথড, অথবা অন্য inner মেথড (এ ব্যাপারে পরে বলছি)।   

ছবি ৩: ডেকোরেটর  মেথড টার্গেট মেথডকে প্যারামিটার হিসাবে নেয় 

• ৩. ডেকোরেটর ফাঙ্কশন যে মডিউল-এ ডিফাইন করা আছে, সেই মডিউল লোড হওয়ার সময়ই, অর্থাৎ ইম্পোর্ট করার সময় (import time) ডেকোরেটর ফাঙ্কশন আপনা-আপনি 'কল' হয়ে যায়।

ছবি -৩ খেয়াল করলে দেখবেন, কেউ কিন্তু টার্গেট কিংবা ডেকোরেটর কোনো মেথডকেই কল করে নাই, কোনো কিছু প্রিন্ট করে নাই। কিন্তু তারপরও আউটপুট দেখলে দেখবেন 'Inside decorator  ...' প্রিন্ট হয়ে বসে আছে।  তার কারণ, কোড লোড হওয়া মাত্রই সব ডেকোরেটের মেথড আপনা-আপনি কল হয়ে যায়।  আর একারণেই আমরা দেখছি, 'Inside decorator ...' প্রিন্ট আছে।  

• ৪. পাইথন ডেকোরেটর আর কিছুই না, সূত্র আকারে মনে রাখতে চাইলে:  টার্গেট = ডেকোরেটর(টার্গেট). 

অর্থাৎ টার্গেট ফাঙ্কশনকে ডেকোরেটর ফাঙ্কশনের প্যারামিটার হিসাবে পাঠিয়ে দিয়ে, ডেকোরেটরের নিজস্ব কোড যোগ করে (অর্থাৎ সাজিয়ে নিয়ে) পরে ডেকোরেটর ফাঙ্কশন থেকে কিছু একটা রিটার্ন করিয়ে আবার টার্গেট ফাঙ্কশনের একই নামের ভ্যারিয়েবলে এসাইন করিয়ে দেয়া হয়। চাইলে একই টার্গেট ফাঙ্কশন বা অন্য একটা ইনার ফাঙ্কশন রেফারেন্স রিটার্ন করা যায়।  এতে করে যখন কেউ পরে আবার টার্গেট ফাঙ্কশন কল করবে, টার্গেট() - তখন ডেকোরেটর ফাঙ্কশন থেকে রিটার্ন করা ফাঙ্কশনটা রান করবে।  রামালহোর বইয়ের একটা স্ক্রিনশট না দিয়ে পারছি না :

রামালহোর বইয়ের স্ক্রিনশট: এক কথায় পাইথন ডেকোরেটরের ব্যাখ্যা  

ছবি ৪: ডেকোরেটর মেথডের মাধম্যে টার্গেট মেথড কল করা 

উপরের ছবি ৪ দেখে ব্যাপারটা আরেকটু বুঝিয়ে বলা যাক। খেয়াল করুন, লাইন ২৫ -এ যখন আমরা target() কল করছি, তার আগে কিন্তু 'target' ভ্যারিয়েবলে ডেকোরেটর মেথড থেকে রিটার্ন করা func রেফারেন্স করিয়ে নিচ্ছি। অর্থাৎ, target() কল করলেও আসলে কিন্তু func() ফাঙ্কশন কল হচ্ছে। আর এক্ষেত্রে দুটো একই 'target' ফাঙ্কশন হওয়ায় আউটপুট একই হবে, কিন্তু চাইলেই ডেকোরেটর মেথড থেকে আমরা অন্য inner মেথড রিটার্ন করিয়ে নিয়ে সম্পূর্ণ ভিন্ন কিছু আউটপুট দিতে পারতাম। যেমন নিচের ছবিতে (ছবি ৫), মূল টার্গেট মেথডকে সম্পূর্ণ সরিয়ে দিয়ে 'Inside inner  ...' প্রিন্ট করিয়ে নিচ্ছি:

  

ছবি ৫: টার্গেট মেথডের ব্যবহার (behavior) ডেকোরেটরের inner মেথড দিয়ে পাল্টিয়ে দিলাম 

আর লাইন ২৫ -এর এই কাজটা @ চিহ্ন দিয়ে ডেকোরেটর ফাঙ্কশনের নাম লিখে ব্যাকগ্রাউন্ডে করে ফেলা যায়। যেমন নিচের ছবিতে লাইন ২৫ মুছে দিয়েও একই আউটপুট পাওয়া যাচ্ছে। 

ছবি ৬: ইন্ডিরেক্টলি বা ঘুরিয়ে ডেকোরেটর ফাঙ্কশন কল করা হচ্ছে 

আচ্ছা, কিন্তু এই ঘুরিয়ে কাজ করার দরকার বা উপকারিতাটা কি? ডেকোরেটরের পুরো শক্তি বা উপকারিতা একটা ব্লগ পোস্টে লিখে বোঝাতে গেলে লম্বা হয়ে যাবে। আজকের পোস্টে তাই inner ফাঙ্কশন ব্যবহার না করে, অর্থাৎ মূল টার্গেট মেথড ঠিক রেখে (ছবি ৩- এর মতো) কিভাবে ডেকোরেটর ব্যবহার করে একটা ডিজাইন প্রবলেম সল্ভ করা যায়, সেটা লিখছি। পরে কোনো একদিন বাকি গুলো নিয়ে লিখবো, ইনশাআল্লাহ। 

ধরা যাক ডিজাইন প্রবলেমটা অনেকটা এই রকম : আপনি একটা সুপার স্টোরের চেকআউট সিস্টেম ডিজাইন আর ইমপ্লিমেন্ট করবেন। আইডিয়া হচ্ছে, আপনার স্টোরে কাস্টমারেরা একটা শপিং কার্ট-এ বাজার করে চেকআউট কাউন্টারে আসবে। সব আইটেম স্ক্যান করা হয়ে গেলে আপনি মোট দামের উপর কিছু ডিসকাউন্ট দিতে চান।  যেমন: আপনার 'বান্ধা' বা রেগুলার  কোনো কাস্টমারের জন্য ৫% রিওয়ার্ড ডিসকাউন্ট দিতে চান; কোনো কাস্টমার একই আইটেম ২০ টার বেশি কিনলে সেগুলোর উপর ১০% ডিসকাউন্ট দিতে চান, ইত্যাদি। কিন্তু শর্ত হচ্ছে, একবারে শুধু একটা ডিসকাউন্ট প্রযোজ্য। দুইয়ের বেশি কুপন থাকলে সবচেয়ে বেশি ডিসকাউন্ট যেই কুপনে পাওয়া যাবে, শুধু সেইটাই মূল মূল্যের উপর ছাড় হিসাবে প্রয়োগ হবে। আর আপনি চান, খুব সহজেই পুরোনো কোনো 'অফার' বাদ দিয়ে অন্য নতুন 'অফার' যোগ করবেন (যেমন ঈদে বা পূজা কিংবা বড়দিনের সময় ১০% ছাড়)। এই কোডটা খুব সহজেই পাইথন ডেকোরেটর দিয়ে করে ফেলা যাবে।  

খুব বেশি ব্যাখ্যা না করে সরাসরি 'Cutomer', 'Item' আর 'Cart' ক্লাস গুলো নিচে দিয়ে দিচ্ছি। সাধারণ আইডিয়া, একজন কাস্টমারের নাম, রিওয়ার্ড পয়েন্ট, আর শপিং কার্ট -এর রেফারেন্স থাকবে 'Customer' ক্লাসে।  বাজারের আইটেম-এর ডেসক্রিপশন, দাম, আর সংখ্যা (ডিফল্ট ১ টা) থাকবে 'Item' ক্লাসে।  আর 'Cart' ক্লাসে আইটেমে অবজেক্টের  একটা লিস্ট থাকবে। কাস্টমার বাজার নিয়ে চেকআউট-এ আসলে তার কার্টে থাকা আইটেম গুলোর দাম আর সংখ্যা গুণ করে মোট দাম হিসাব করা হবে।  

ছবি ৭ : সবগুলো ক্লাস একটা পাইথন ফাইলে লিখে রেখেছি 

এইবার, আরেকটা পাইথন ফাইলে সবগুলো 'অফার' মেথড আকারে লিখে রাখবো। মেথডগুলোর কাজ হবে, কাস্টমারকে প্যারামিটার হিসাবে নিয়ে তার শপিং কার্টের আইটেম -র উপর ডিসকাউন্ট হিসাব করা। 

ছবি ৮: ডিসকাউন্ট অফার হিসাব করার ফাঙ্কশনগুলো 

এবার আসল মজা! পাইথন যেহেতু 'ফার্স্ট ক্লাস' মেথড সাপোর্ট করে, সব গুলো ডিসকাউন্ট মেথড গুলোকে একটা লিস্টের মধ্যে নিয়ে রেখে দিয়ে, তারপর কাস্টমারের বাজার করা শেষে এক এক করে এপ্লাই করে সবচেয়ে বেশি বা ম্যাক্সিমাম ডিসকাউন্ট যেটাতে পাওয়া যায়, সেটা প্রয়োগ করলেই হয়! যদি নতুন কোনো 'ডিসকাউন্ট অফার' যোগ করতে হয়, তাহলে, আরেকটা মেথড লিখে ওই লিস্টে অ্যাড করলে হয়ে যাবে। কিন্তু পুরোনো 'ডিসকাউন্ট অফার' বাদ দিবো কিভাবে? 

দুটো কাজই আসলে ডেকোরেটর দিয়ে করা যায়। একটা ডেকোরেটর ফাঙ্কশন ইমপ্লিমেন্ট করা যায়, যার কাজ হবে ফাঙ্কশনগুলোকে একটা লিস্টে অ্যাড করা।  আর প্রতিটি 'ডিসকাউন্ট' মেথডের শুরুতে @ চিহ্ন দিয়ে ওই ডেকোরেটরের নাম দিয়ে দিলেই হবে। মডিউল ইম্পোর্ট করার সময় (import time) আপনা-আপনি সবগুলো ডেকরেটর মেথড লিস্টে অ্যাড হয়ে যাবে। আর কোনো একটা 'অফার' বাদ দিতে চাইলে শুরুর @ চিহ্ন কমেন্ট আউট (comment out) করে দিলেই চলবে। তখন সেই অফার মেথড আর লিস্টে অ্যাড হবে না।  নিচের কোডে (ছবি ৯) খেয়াল করুন, যেহেতু ডেকোরেটর মেথড টার্গেট মেথড কল করছে না, শুধু রিটার্ন করছে, তাই টার্গেট মেথডের বিহেভিয়ার বা ব্যবহার বদলাচ্ছে না।   

ছবি ৯: ডেকোরেটর ব্যবহার করে promos লিস্টে ডিসকাউন্ট অফার মেথডগুলো যোগ করা হচ্ছে 

খেয়াল করুন, লাইন ২৬ - এ discount মেথড promos লিস্টে থাকা এক একটা ডিসকাউন্ট মেথড কল করবে আর শেষে সর্বোচ্চ ডিসকাউন্ট এমাউন্ট রিটার্ন করবে।  

এইবার, একটা ক্লায়েন্ট কোড লিখে কোডটা রান করা যাক। নিচের ছবি ১০-এ আমরা কয়েকটা আইটেম অবজেক্ট তৈরি করে নিলাম। তারপর একটা Cart অবজেক্ট তৈরি করে আইটেম গুলো অ্যাড করে নিচ্ছি।  এইবার লাইন ১২-তে একজন কাস্টমার 'জসিম' তৈরী করলাম, ধরে নেই উনার রিওয়ার্ড পয়েন্ট ১০০। এবার ডিসকাউন্ট বাদে মূল্য বের করলাম তারপর ডিসকাউন্ট এপ্লাই করলাম।   

ছবি ১০: ডেকোরেটর ব্যবহার করে সর্বোচ্চ ডিসকাউন্ট প্রয়োগ 

খেয়াল করুন, কোড রান করার শুরুতেই ডেকোরেটর গুলো আপনা-আপনি রান হয়ে যাচ্ছে, আর ডিসকাউন্ট প্রমোশন গুলো লিস্টে অ্যাড হয়ে যাচ্ছে।  সবশেষে, লাইন ১৭-তে যখন 'discount()' মেথড কল হচ্ছে, তখন সর্বোচ্চ যেই ডিসকাউন্ট সেটা প্রয়োগ হয়ে দাম দেখাচ্ছে। ব্যস, হয়ে গেলো!!

যাই হোক, আশা করি বুঝতে পেরেছেন। পুরো কোডের Repl.it লিংক নিচে দিয়ে দিচ্ছি।  কোড গুলো ক্লোন করে নিয়ে নিজেরা রান করলে আশাকরি আরো ভালোভাবে বুঝতে পারবেন।  

'ফার্স্ট ক্লাস' ফাঙ্কশন কনসেপ্ট -এর কোড: এই লিংকে 

ডিজাইন প্রবলেম -এর পুরো সল্যুশন কোড : এই লিংকে 

সবাইকে ধন্যবাদ !

ডাইক্স্ট্রা এলগোরিদম: ইমপ্লিমেন্ট করতে গিয়ে যা যা শিখলাম!

 ডাইক্স্ট্রা এলগোরিদম: ইমপ্লিমেন্ট করতে গিয়ে যা যা শিখলাম 
১১ মে, ২০২১, মঙ্গলবার 

বহু বছর পর, দেশের বাইরে এই সেমিস্টারে প্রথমবারের মতো এলগোরিদম কোর্স পড়ালাম। কোনো কিছু পড়াতে গেলেই  যে সবচেয়ে ভালো শেখা হয় - এই কথাটা যে কী ভীষণ সত্যি সেটা না হয় আর নাই বললাম, কিন্তু এলগোরিদম পড়া আর কোডে ইমপ্লিমেন্ট করাতেও যে অনেক তফাৎ থাকতে পারে - সেই গল্পটাই আজকে বলছি।

ডাইক্স্ট্রা এলগোরিদম (Dijkstra Algorithm) - এলগোরিদম কোর্সে খুবই কমন একটা টপিক। গ্রাফে একটা নোড থেকে বাকি সব নোডে যাওয়ার সবচেয়ে ছোট (বা শর্টেস্ট) পথ খুঁজে বের করাই এই এলগোরিদমের কাজ। এর কিছু সীমাবদ্ধতা আছে (যেমন, নেগেটিভ এজ সামলাতে পারে না) - এসব বাদ দিলে খুবই কার্যকরী একটা এলগোরিদম।  'লোভী পদ্ধতির' বা 'Greedy Strategy' এলগোরিদম বোঝার জন্যও ডাইক্স্ট্রা এলগোরিদম উদাহরণ হিসাবে শেখা উচিত। যদিও আমি নিচে ব্যাখ্যা করছি, তবুও আপনার জানা না থাকলে, কিংবা এই মুহুর্তে ডাইক্স্ট্রা এলগোরিদমটা মনে না থাকলে চট করে শাফায়াত আশরাফের বাংলা ব্লগ পড়ে নিতে পারেন। শাফায়াত আমাদের ডিপার্টমেন্টের জুনিয়র। ওর সাথে আমার কোনোদিন দেখা হয় নাই। কিন্তু ওর সাথে ওর এই ব্লগের কল্যানেই যোগাযোগ আছে। ওর গ্রাফের উপর বাংলা বইটাও খুবই চমৎকার। আমি ক্লাসের প্রিপারেশন নেয়ার জন্য ওর বইটা ব্যবহার করেছি। মায়ের ভাষায় কোনো কিছু পড়লে অনেক সহজবোধ্য হয়।  কিন্তু শাফায়াতের এলগোরিদম আর গ্রাফের উপর জ্ঞান আর লেখার হাত দুটো ভালো বলেই বইটা আরো ভালো হয়েছে।  

যাই হোক, খুব সংক্ষেপে ডাইক্স্ট্রা এলগোরিদম মূল আইডিয়াটা লেখার চেষ্টা করছি। Breadth First Search বা BFS হচ্ছে এর মূল ইঞ্জিন। BFS আবার কি? একটা গ্রাফের একটা নোড থেকে তার সবগুলো প্রতিবেশী নোডকে এক এক করে visit বা ঘুরে তারপর অন্য নোডে যাওয়াটাই BFS। নতুন কোনো নোডে যাওয়া মাত্রই তাকে একটা চিহ্ন বা দাগ দিয়ে দিতে হয় (রং gray বা ছাই করে দিয়ে), যাতে পরবর্তীতে আর ভিসিট করা না লাগে। আর একটা নোডের সবগুলো প্রতিবেশী নোড দেখা শেষ হয়ে গেলে আরেকটা চিহ্ন (রং কালো করে দিয়ে) 'complete' করে দিতে হয়।  আর এই পুরা কাজটা একটা কিউ (Queue) ডাটা স্ট্রাকচার দিয়ে ইমপ্লিমেন্ট করা হয়।  নিচে কোরমানের বইয়ের আলগোরিদমের ছবি দিয়ে দিচ্ছি (এইখানে d হচ্ছে মূল বা সোর্স নোড থেকে দূরত্ব/ধাপ আর 'পাই' আগের নোডের হিসাব রাখে):

      

ছবি ১: কোরমানের বই থেকে নেয়া [১]: BFS এলগোরিদম 

প্রথম যেটা খেয়াল করতে হবে, BFS এলগোরিদমে গ্রাফের প্রতিবেশী নোডগুলোর মধ্যে দূরত্ব ধরা হয় ১, অর্থাৎ এজের weight বা দূরত্ব সমান। এলগোরিদম রান করা শেষে একটা নোড থেকে বাকি নোড গুলো কত 'ধাপ' দূরে আর প্রতি নোডে যেতে কোন পথে যেতে হবে সেটা বের হয়।  কিন্তু ডাইক্স্ট্রা এলগোরিদম-এ গ্রাফের প্রতিটা নোডের সাথে তার প্রতিবেশী নোড শুধু সংযুক্তই না, ভিন্ন weight বা দূরত্বও দেয়া থাকে। সবচেয়ে কম দূরত্বে (বা Shortest Path) কিভাবে যাওয়া যায় সেটাই এই এলগোরিদম বের করে।  

উপরের এলগোরিদমে লাইন ১৩-র মতো 'একটা নোড ইতিমধ্যেই দেখা বা visit করা শেষ (রং সাদা না), তাই আর ঘাঁটানোর দরকার নাই '  - এই আইডিয়া বাদ দিয়ে ডাইক্স্ট্রা এলগোরিদম আরেকটু কৌতুহলী হয়। একটা নোডে যদি আরো কম খরচে (দরকার হলে অন্য আরেকটা নোড ঘুরে, কম দূরত্বে) পৌঁছানো যায়, তখন সেইটাই ভালো পথ - মূলত এই আইডিয়াটাই ডাইক্স্ট্রা এলগোরিদম। এই আপডেটটা নিচের 'Relax' মেথডটা করে থাকে:

ছবি ২: কোরমানের বই থেকে নেয়া[১]: সোর্স থেকে কোনো নোডের দূরত্ব (v.d) যদি অন্য আরেকটা নোড (u) ঘুরে কম দূরত্বে পৌঁছানো যায়, তাহলে সেইটাই ভালো পথ। w(u, v) নোড দুটোর দূরত্ব দেয়।  

আরেকটা কাজ ডাইক্স্ট্রা এলগোরিদম করে থাকে, সাধারণ কিউ (regular queue) ব্যবহার না করে প্রায়োরিটি কিউ ব্যবহার করে। কারণ যেহেতু আমরা শর্টেস্ট বা সবচেয়ে কম দূরত্বে পৌঁছাতে চাই, তাই সোর্স নোড থেকে কম দূরত্বের ভিত্তিতে একটা প্রায়োরিটি কিউ বা মিন-হিপ ব্যবহার করে কাজ করলে একই নোড বার বার ভিসিট বা ঘুরে দেখতে হয় না। আরেকটু বুঝিয়ে বলি: নিজের নোডে পৌঁছাতে যেহেতু কোনো দূরত্ব যাওয়া লাগে না, তাই শুরুতে সোর্স নোডের দূরত্ব শূন্য করে দিয়ে বাকি সব গুলো নোডের দূরত্ব অসীম করে দিয়ে প্রায়োরিটি কিউ বা মিন-হিপ তৈরী করা হয়।  এখন প্রায়োরিটি কিউ তে যতক্ষণ নোড আছে, প্রতিবার সবচেয়ে কম দূরত্বে পৌঁছানো যায় এমন নোড বের করে নিয়ে (Extract-Min ) (শুরুতে সোর্স নোড নিজেই থাকবে) সবগুলো প্রতিবেশীকে 'Relax' করিয়ে নিলেই হলো - সব সময় কম দূরত্বের নোডই অগ্রাধিকার পাবে, আর তা একবারই পাবে। আর এভাবে 'লোভী' হয়ে সব সময় কম দূরত্বের নোডকে নিয়ে চলতে থাকলে একসময় সব গুলো নোডে পৌঁছানোর শর্টেস্ট বা সবচেয়ে কমদূরত্বের পথ বের করে ফেলা যাবে। ব্যস, এইটাই ডাইক্স্ট্রা এলগোরিদম। নিচে এলগোরিদমটা দিয়ে দিচ্ছি:

ছবি ৩: কোরমানের বই থেকে নেয়া[১]: প্রায়োরিটি কিউ (বা মিন-হিপ) আর relax ফাঙ্কশন ব্যবহার করে ডাইক্স্ট্রা এলগোরিদম  

যাই হোক, আশা করি আপনি এখন পর্যন্ত সাথেই আছেন আর এই লাইনটা পড়ছেন। এইবার বলি এলগোরিদম ইমপ্লিমেন্ট করতে ঝামেলাটা কোথায় হলো। প্রথম সমস্যা হচ্ছে, কোডে গ্রাফ তৈরি করাটা একটু কঠিন। বেশ অনেকখানি সাপোর্টিং কোড লিখে তারপর ডাইক্স্ট্রা এলগোরিদম ইমপ্লিমেন্ট করতে হয়। একটু চিন্তা করে দেখুন, প্রতিটা নোডের প্রতিবেশী নোড গুলার লিস্ট রাখতে হবে,  সোর্স নোড থেকে দূরত্ব রাখতে হবে, সোর্স থেকে পথ বের করার জন্য আগের নোড কে সেটা রাখতে হবে ইত্যাদি।  নিচের কোড একটা নোড ক্লাস তৈরি করে:

ছবি ৪: নোড অথবা ভারটেক্স ক্লাস 

এবার যেহেতু প্রতিটা এজের weight  বা দূরত্ব হিসাবে নিতে হবে, তার জন্য একটা টেবিল তৈরী করতে হবে।  ধরা যাক, আমরা নোড u  আর v - এর মধ্যে এজ, u - v  এজের জন্য 'uv' স্ট্রিং কী (Key) আর weight বা দূরত্ব ইন্টিজার (Value)  হিসাবে হ্যাশ ম্যাপ -এ রাখলাম।  নিচের কোড গ্রাফের নোড গুলো কে একটা ArrayList -এ রাখবে, কিছু সাপোর্টিং ফাঙ্কশন থাকবে যেগুলো দিয়ে নোড গুলোর মধ্যে এজ আর weight যোগ করা যায়।  বলে রাখা ভালো, নোড গুলোকে নাম্বার দিয়ে নাম দিয়ে রাখছি, অর্থাৎ 'u', 'v' ইত্যাদি না বলে 1, 2 ইত্যাদি হিসাবে রাখছি।   

ছবি ৫: গ্রাফ ইমপ্লিমেন্টেশন

এবার গ্রাফ তৈরি করার জন্য সব কোড রেডি। যতগুলো নোডের গ্রাফ তৈরী করতে চাই, ধরা যাক, ৫ নোডের গ্রাফ, তাহলে main মেথডে Graph(5) কল করে প্রথমে নোডগুলো তৈরী করে নিয়ে, তারপর ম্যানুয়ালি বা ধরে ধরে এজ আর এজের weight যোগ করে দেয়া যাবে।    

এবার আসি, ডাইক্স্ট্রা এলগোরিদম ইম্প্লিমেন্টেশনে। প্রথমে relax ফাঙ্কশন। ছবি ২ -এর এলগোরিদম নিচের কোডে ইমপ্লিমেন্ট করলাম। Relax করলে true আর নাইলে false রিটার্ন করবে। কেন? একটু পরে বুঝিয়ে বলছি।  

ছবি ৬: Graph ক্লাসের ভেতরে প্রাইভেট relax ফাঙ্কশন 

 

এরপর ছবি ৩-এর ডাইক্স্ট্রা এলগোরিদম ইমপ্লিমেন্ট করার জন্য আমাদের প্রায়োরিটি কিউ (মিন-হিপ) লাগবে। গুগলে একটু ঘাঁটাঘাঁটি করে পেলাম যে জাভাতে util লাইব্রেরিতে প্রায়োরিটি কিউ (মিন-হিপ) আগে থেকেই ইমপ্লিমেন্ট করা আছে। কিন্তু যেহেতু আমাদের সোর্স নোড থেকে অন্য নোডের দূরত্বের ভিত্তিতে প্রায়োরিটি কিউ বানাতে হবে, তাই এই ব্যাপারটা একটু বলে দিতে হবে। আর এই কাজটা একটা ক্লাস যেটা Comparator ইন্টারফেস ইমপ্লিমেন্ট করে সেটা লিখে করতে হয়। এর পর শুধু প্রায়োরিটি কিউ-এর প্যারামিটার হিসাবে সেই ক্লাস তা পাস্ করে দিলে হয়ে যায়।  নিচের কোড:

ছবি ৭: Graph ক্লাসের ভেতরে Comparator ইন্টারফেস ইমপ্লিমেন্ট করা inner ক্লাস 

এবার শেষমেষ ডাইক্স্ট্রা এলগোরিদম ইমপ্লিমেন্টেশনের পালা। ছবি ৩ -এর কোড ধরে কোডটা ইমপ্লিমেন্ট করে দিলাম। খেয়াল করবেন, প্রায়োরিটি কিউ প্যারামিটার হিসাবে আমাদের Comparator ক্লাস নিচ্ছে। 

ছবি ৮: Graph ক্লাসের ভেতরে ডাইক্স্ট্রা মেথড। 

ব্যস, হয়ে গেছে তাই না? টেস্ট করার জন্য কিছু কোড লিখে, একটা টেস্ট গ্রাফের উপর রান করলাম, ডিবাগ করে দেখলাম, সেটাও (সৌভাগ্য কিংবা দুর্ভাগ্য বশতঃ?) কাজ করলো! কিন্তু যেই না স্টুডেন্টদের কোড দিয়ে অন্য টেস্ট কেস রান করতে বললাম, এরর খাওয়া শুরু হলো।  কোড বার বার চেক করেও বের করতে পারছিলাম না কেন কাজ করছে না। কোড তো এলগোরিদম হিসাবে ঠিক ভাবেই ইমপ্লিমেন্ট করলাম। কি একটা বেইজ্জতির ব্যাপার! শেষমেষ না পেরে বললাম, আজকে থাক, আমি পরে কোড চেক করে বের করার চেষ্টা করবো কেন কাজ করছে না।  

ঐদিন ক্লাস শেষে বেশ কিছুক্ষন ডিবাগ করে, ডকুমেন্টস, StackOverflow ঘেঁটে পরে বাগটা ধরতে পারলাম। আপনারা একটু চেষ্টা করে দেখবেন নাকি ধরতে পারেন কিনা? 

যাই হোক, এতক্ষন ধরে আসলে কনটেক্সট দেয়ার চেষ্টা করলাম। এইবার মূল ব্যাপারটা বলি। বাগটা হচ্ছে প্রায়োরিটি কিউ ব্যবহার করায়। কোনো প্রায়োরিটি কিউ তার প্রপার্টি -- আমাদের ক্ষেত্রে সোর্স নোড থেকে সবচেয়ে কম দূরত্বে থাকা নোড রুটে (root) থাকবে - এই ব্যাপারটা মেইনটেইন করবে কেবল শুরুতে যখন প্রায়োরিটি কিউ তৈরী করা হয় আর যখন কোনো অপারেশন করা হয়, যেমন poll (extract) কিংবা add ইত্যাদি কল করার পর। 

আমরা যখন ছবি ৬ -এ, 'relax' মেথড কল করে নোডের ভেতরে 'distance' বা দূরত্ব আপডেট করে দিচ্ছি, তখন ধরে নিচ্ছিলাম যে প্রায়োরিটি কিউ নিজে থেকে আপডেট হয়ে, স্ট্রাকচার বা কাঠামো বদলে সবচেয়ে কম দূরত্বের নোড কে উপরে বা রুটে (root) নিয়ে আসবে। এটা সম্পূর্ণ ভুল ধারণা। প্রায়োরিটি কিউ -এর ডকুমেন্টেশনে কোথাও সেটা বলা নাই।  

তাহলে উপায়? StackOverflow ঘেঁটে সল্যুশন বের করলাম। যখন 'relax' মেথড নোডের distance আপডেট করে true রিটার্ন করবে তখন ম্যানুয়ালি প্রায়োরিটি কিউতে একটা অপারেশন চালিয়ে - যেমন poll করে রুট বের করে নিয়ে আবার সেই একই রুট নোড add করে দিয়ে আমাদের প্রপার্টি 'force update' করে নিতে হবে, তবেই কাজ হবে। নিচে পরিবর্তিত কোড, হাইলাইট করে দিচ্ছি :

    

ছবি ৯: বাগ ফিক্স করা পরিবর্তিত ডাইক্স্ট্রা এলগোরিদম ইমপ্লিমেন্টেশন 

এখন আশা করি বুঝতে পারছেন, ছবি ৬ - এ কেন relax মেথডে true/false রিটার্ন করা জরুরি ছিল। আমি ভাবছিলাম এই ছোট কিন্তু খুব জরুরি বিষয়টা কেন পরিস্কারভাবে বলা হলো না? পরে আরেকটু ভালো করে পড়ার পর পেলাম কোরমানের বইয়ে 'relax' -এর সাথে Decrease-Key ফাঙ্কশনের সম্পর্ক বলা আছে - যেটা কিনা প্রায়োরিটি কিউয়ের নোডের key (আমাদের ক্ষেত্রে distance-ই key) কমিয়ে দিয়ে কিউ আপডেট করে। 

ছবি ১০: কোরমানের বই থেকে নেয়া[১]। ঘুরিয়ে বলা হয়েছে যে relax পরোক্ষভাবে অন্য ফাঙ্কশন কল করে প্রায়োরিটি কিউয়ের প্রপার্টি মেইনটেইন করবে   

যাই হোক, ঝানু প্রোগ্রামাররা হয়তো শুরুতেই ব্যাপারটা ধরতে পেরেছেন। কিন্তু আমার মতো দুর্বল প্রোগ্রামাররা হয়তো কত ঘন্টা এই বাগের পেছনে সময় ব্যয় করেছেন কে জানে? দিন শেষে শিক্ষা: যখনই কোনো এলগোরিদম শিখবো, কোডে ইমপ্লিমেন্ট করে তবেই থামতে হবে; কোডে কোনো লাইব্রেরি ব্যবহার করলে তার ডকুমেন্টেশন ভালো করে পড়ে নিতে হবে, শুধু চট করে ফাঙ্কশন কল করে কোনো কিছু হয়ে যাবে  ধরে নেয়া ঠিক না; কোড বেশি বেশি টেস্ট করার কোনো বিকল্প নাই।  

সবাইকে ধন্যবাদ!

--ইশতিয়াক 

রেফারেন্স: 

[১] 'Introduction to Algorithms' by Thomas H. Cormen and others.