গ্রাফ থিওরি (পর্ব ৮)
প্রোগ্রামিং — ১
মজবুত সম্পর্কের গ্রাফ
Undirected graph এর ক্ষেত্রে আমরা জানি যে, ১ নং নোড থেকে ২ নং নোডে যদি যাওয়া যায় তাহলে ২ নং থেকে ১ নং এ যাওয়া যাবে। কিন্তু directed graph এর ক্ষেত্রে বিষয়টি সেরকম নাও হতে পারে। নিচের ছবিটি খেয়াল করি,
(১) নং গ্রাফটি undirected তাই আবুল যেমন বাবুলের বন্ধু, ঠিক তেমনি বাবুলও আবুলের বন্ধু। আবুল মনে মনে সখিনাকে খুব ভালোবাসে কিন্তু সখিনা আবুলকে পাত্তা দেয়না। তাহলে আবুলের দিক থেকে সখিনার সাথে সম্পর্ক থাকলেও, সখিনার দিক থেকে নেই। ছবির (২) নং অংশে directed graph দ্বারা এই বিষয়টি বুঝানো হয়েছে। তাহলে বলা যায় যে, আবুল ও সখিনার মধ্যে মজবুত সম্পর্ক নাই। এক হাতে তালি বাজছে আরকি।
তাহলে সম্পর্ক তখনই মজবুত হবে যখন দুই পক্ষ থেকেই সম্পর্ক থাকবে। নিচের ছবিটি দেখা যাক,
(১) নং গ্রাফে, খুলনা থেকে সিলেট যাওয়া যায় আবার সিলেট থেকে খুলনাও যাওয়া যায়। এদের মধ্যে মজবুত সম্পর্ক আছে দেখা যাচ্ছে। (২) নং গ্রাফে ঢাকা থেকে খুলনা যাওয়া যায়, আবার ঢাকা থেকে খুলনা হয়ে সিলেট যাওয়া যায়। খুলনা থেকে সিলেট যাওয়া যায়, আবার খুলনা থেকে সিলেট হয়ে ঢাকা যাওয়া যায়। সবার সাথে সবার খুব ভালো সম্পর্ক। (৩) নং গ্রাফেও তাই। যদি কোন গ্রাফে এরকম সম্পর্ক পাওয়া যায় তবে তাদেরকে আমরা strongly connected বলবো।
পর্ব ৪ এ আমরা disconnected graph এর component সংখ্যা নিয়ে কথা বলেছি। নিচের ছবিটি খেয়াল করি,
(১) নং গ্রাফটি undirected ও disconnected, এর component সংখ্যা হচ্ছে ২। (২) নং গ্রাফটি directed ও connected। কিন্তু ঢাকা, খুলনা, সিলেট থেকে সব জায়গায় যাওয়া গেলেও টোকিও থেকে কোথাও যাওয়া যাচ্ছেনা। তাই বলা যায়, ঢাকা, খুলনা, সিলেট এর মধ্যে সম্পর্ক মজবুত কিন্তু টোকিওর সাথে অন্যদের সম্পর্ক মজবুত নয়। তাহলে ঢাকা, খুলনা, সিলেট মিলে একটা অংশ এবং টোকিও নিজে একটা অংশ। ঢাকা, খুলনা, সিলেট strongly connected এবং টোকিও থেকে যেহেতু টোকিও যাওয়া যায় তাই এটা নিজে নিজে strongly connected। তাহলে (২) নং গ্রাফে strongly connected component কয়টা? ২টা।
গ্রাফের গল্প থেকে একটু বিরতি নিয়ে তোমাদের সাথে ভারতে জন্ম নেয়া এক ভদ্রলোকের সাথে পরিচয় করিয়ে দেই। পৃথিবীর সেরা ১৫ টি বিশ্ববিদ্যালয়ের একটি হচ্ছে জন হপকিন্স বিশ্ববিদ্যালয়। এই বিশ্ববিদ্যালয়ের কম্পিউটার বিজ্ঞানের একজন প্রফেসর হচ্ছেন Sambasiva Rao Kosaraju। ৭৬ বছর বয়স্ক এই প্রফেসর বর্তমানে যুক্তরাষ্ট্রের ন্যাশনাল সায়েন্স ফাউন্ডেশনের একটি বিভাগের পরিচালক হিসেবে দায়িত্ব পালন করছেন।
এই Kosaraju সাহেব, কোন একটা গ্রাফে কয়টি strongly connected component (SCC) আছে সেটা বের করার জন্য একটি বিখ্যাত অ্যালগরিদম তৈরি করেন ৪১ বছর আগে। উনার নামেই এই অ্যালগরিদমের নাম হচ্ছে Kosaraju’s algorithm।
আমরা এই পর্বে উল্লেখিত অ্যালগরিদমটি কিভাবে কাজ করে এবং তার প্রোগ্রাম দেখবো। তাহলে কাজ শুরু করা যাক।
প্রথমে অ্যালগরিদমটি ব্যাখ্যা করার জন্য আমরা একটি গ্রাফ নিয়ে নিই। নিচের ছবিটি খেয়াল করি,
ছবি ৫৮ থেকে যে ধারণা পাওয়া গেছে তা ব্যবহার করে ছবি ৫৯ এর SCC বের করার চেষ্টা করে দেখতে পারো।
এখন আমরা অ্যালগরিদমটি ব্যাখ্যা করবো।
১ম ধাপ — প্রথমে প্রদত্ত গ্রাফের সবগুলো নোডের finishing time বের করে ফেলতে হবে। আমি আশা করছি তোমরা পর্ব ৭ থেকে discovery time ও finishing time এর ধারণা নিয়ে এসেছো। তাহলে সেই ধারণা প্রয়োগ করে আমরা নিচের ছবিটি তৈরি করে ফেলতে পারি। যদি আমরা ১ নং নোড থেকে যাত্রা আরম্ভ করি তাহলে,
সবচেয়ে বেশি finishing time থেকে সবচেয়ে কম হিসেবে সাজালে আমরা পাই,
১ — ২ — ৪ — ৫ — ৩ — ৬ — ৮ — ৭ — ১০ — ৯ — ১১ — ১২
২য় ধাপ — ছবি ৫৯ এর গ্রাফের সবগুলো এজের দিক আমরা এখন উল্টিয়ে দিবো। তাহলে যে গ্রাফটি পাওয়া যাবে তাকে বলা হবে মূল গ্রাফের ট্রান্সপোজ গ্রাফ (Transpose graph)। যদি মূল গ্রাফটি (ছবি ৫৯) G হয়, তাহলে এর ট্রান্সপোজ গ্রাফকে (ছবি ৬১) Gᵀ দ্বারা প্রকাশ করা হয়।
৩য় ধাপ — ছবি ৬১ এর গ্রাফের নোডগুলোর finishing time আবার বের করবো আমরা। তবে ইচ্ছামতো নোড থেকে শুরু করবোনা। ছবি ৬০ থেকে যে ধারাটা পেয়েছিলাম অর্থাৎ ১ — ২ — ৪ — ৫ — ৩ — ৬ — ৮ — ৭ — ১০ — ৯ — ১১ — ১২ অনুযায়ী আমরা finishing time বের করবো।
শুরু করা যাক ১ নং নোড থেকে। দেখা যাচ্ছে যে এখান থেকে কোথাও যাওয়া যাচ্ছেনা। তাহলে এটি একটি SCC। (ছবি ৬২)
(১) — ২ — ৪ — ৫ — ৩ — ৬ — ৮ — ৭ — ১০ — ৯ — ১১ — ১২ ধারা থেকে ১ নং নোডের কাজ শেষ (তাই একে প্রথম বন্ধনীর মধ্যে দেখানো হল)। এবার তাহলে ২ নং নোড থেকে শুরু হবে। ‘২’ থেকে শুরু করে ‘৫’ ও ৪ নং নোড ঘুরে আবার ‘২’ এ ফেরত এসে দেখা যাচ্ছে আর কোথাও যাওয়া যাচ্ছেনা। তাহলে নোড ২, ৫, ৪ মিলে একটি SCC। (ছবি ৬৩)
(১) — (২ — ৪ — ৫) — ৩ — ৬ — ৮ — ৭ — ১০ — ৯ — ১১ — ১২ ধারা থেকে আমরা এবার ৩ নং নোড দিয়ে শুরু করবো। একইরকমভাবে ৩ ও ৬ নং নোড দিয়ে আরেকটি SCC তৈরি হচ্ছে কেননা ৩ নং নোড থেকে যাত্রা শুরু করে ৬ নং নোডে এসে আর কোথাও যাওয়া যাচ্ছেনা। তাই ৩ নং নোডে ফেরত গিয়ে দেখা যাচ্ছে সেখান থেকেও অন্য কোথাও যাওয়া যাচ্ছেনা। (ছবি ৬৪)
(১) — (২ — ৪ — ৫) — (৩ — ৬) — ৮ — ৭ — ১০ — ৯ — ১১ — ১২ ধারা থেকে আমরা এবার ৮ নং নোড দিয়ে শুরু করবো। আগের মতো করেই হিসাব করলে আমরা দেখতে পাবো যে, ৮, ৭, ১০, ৯, ১১ ও ১২ নং নোড মিলে আরেকটি SCC তৈরি করেছে। এটার জন্য আর finishing time দেখালাম না।
তাহলে দেখা যাচ্ছে যে, আমাদের আলোচ্য গ্রাফটিতে ৪টি strongly connected component পাওয়া যাচ্ছে। এখানে আমরা ইচ্ছাকৃত একটা ভুল করেছি, সেটা হচ্ছে SCC গুলো ট্রান্সপোজ গ্রাফে দেখিয়েছি। এটা করা হয়েছে একান্তই আলোচনার সুবিধার জন্য। SCC দেখাতে হয় সবসময় মূল গ্রাফে। (ছবি ৬৫)
এই ছিল Kosaraju’s algorithm ব্যবহার করে কোন directed graph এর strongly connected component বের করার পদ্ধতি। এবার আমরা এর প্রোগ্রাম দেখবো, তবে তার আগে কিছু আলোচনা সেরে নেয়া ভালো হবে।
যারা ১ম পর্ব থেকে এ পর্যন্ত সব লেখা পড়ে ফেলেছো তাদের অভিনন্দন, কারণ Introduction to Algorithms বইয়ের ২২ নং অধ্যায়ে যেসব বিষয় আছে সেগুলো আমাদের আলোচনা করা শেষ। অর্থাৎ ২২ নং অধ্যায় পড়া শেষ!
এ পর্যন্ত আলোচ্য বিষয়ের মধ্যে ছিল, গ্রাফের সাথে পরিচয়, গ্রাফকে কিভাবে কম্পিউটারে স্টোর করা যায়, DFS, BFS, Topological Sorting এবং এই পর্বে SCC। বাস্তব জীবনে এগুলো কোন্ কোন্ কাজে লাগে সে সম্পর্কে ধারণা থাকলে পড়াশোনা করে মজা পাওয়া যায়। এখন আমরা এ সম্পর্কিত সংক্ষিপ্ত কিছু আলোচনা করে ফেলি।
DFS — কোন গ্রাফে cycle বা চক্র আছে কিনা সেটা বের করার জন্য আমরা ডিএফএস ব্যবহার করে থাকি। Topological Sorting এবং SCC বের করার জন্য যে আমরা ডিএফএস ব্যবহার করেছি সেটাতো মনে আছেই। আরও অনেক গুরুত্বপূর্ণ ব্যবহারের মধ্যে একটা হচ্ছে কোন একটা গ্রাফ Bipartite কিনা সেটা বের করার জন্যও ডিএফএস ব্যবহার করা হয়। আমি আশা করছি তোমাদের নিশ্চয়ই মনে আছে, Bipartite গ্রাফের কথা।
BFS — বিভিন্ন ধরনের নেটওয়ার্ক তৈরিতে বা নেটওয়ার্কের যোগাযোগ (connection) পরীক্ষা করতে বিএফএস ব্যবহার করা হয়।
এবার প্রোগ্রাম দেখার পালা।
**কিছুদিন পর SCC এর প্রোগ্রাম এখানে যুক্ত করা হবে।
