ডিসজয়েন্ট-সেট কি?
যদি কয়েকটা সেটের মধ্যে কোনো কমন এলিমেন্ট না থাকে, তাহলে সেই সেটগুলোকে ডিসজয়েন্ট-সেট বলা হয়। মানে,যদি A = {1, 2, 3} আর B = {4, 5} দুইটা সেট হয়, তাহলে এরা ডিসজয়েন্ট সেট, কারণ এদের মধ্যে কোনো কমন নাম্বার নেই। ডিসজয়েন্ট-সেট এর প্রত্যেকটা এলিমেন্টকে যদি একটা গ্রাফের ভার্টেক্স বা নোড ধরা হয়, তাহলে কানেক্টেড গ্রাফের অনেক সমস্যাই এই ডাটা স্ট্রাকচার দিয়ে ভালো পারফর্মেন্সে সমাধান করা সম্ভব। এটা দিয়ে সেটের পার্টিশনকে মডেল করা হয়, তাই কোনো নেটওয়ার্কের কানেক্টিভিটি বের করা যায়। ক্রুশকালের অ্যালগোরিদমে মিনিমান স্পানিং ট্রি বের করতেও এটি ব্যবহার হয়।
কিভাবে ইমপ্লিমেন্ট করা যেতে পারে ?
সরাসরি ইমপ্লিমেন্টেশনে যাবার আগে একটা উদাহরণ দেখা যাক। ধরে নেই, আমাদের কাছে কিছু নোড আছে। তাদের মধ্যে কে কার সাথে কানেক্টেড সেটাও বলা আছে।
Nodes = {a, b, c, d, e, f}
Connection = [
(a, b),
(a, c),
(c, d),
(e, f)
]এখানে a, b, c, d, e, f নামে ছয়টা নোড আছে। কানেকশন লিস্ট থেকে দেখা যাচ্ছে a এর সাথে b, c; c এর সাথে d, আর e এর সাথে f কানেক্টেড। তারমানে কোনো স্পেসিফিক ভাবে না ভেবেই আমরা যদি এদের কানেক্ট করি, আমরা এমন একটা গ্রাফ পাবো।
a - c - d
|
b
e - fএখানে নোডগুলো দুইটা ডিসজয়েন্ট সেটে ভাগ হয়েছে, {a, b, c, d} আর {e, f} । এখানে প্রথম গ্রাফের রুট a এবং দ্বিতীয় গ্রাফের রুট e, মানে ডিরেক্ট আর ইন্ডিরেক্ট কানেক্টিভিটি হিসাব করলে বাকি সব নোডের রুট এই দুই নোড। এখন, আমাদের কে যদি জিজ্ঞাসা করা হয় যে, a আর d কি কানেক্টেড? আমরা কিন্তু সহজেই বলে দিতে পারি, হ্যাঁ, কারণ এরা একই সেটে আছে বা এদের রুট একই! আমাদের লক্ষ্য হলো এমনই একটা স্ট্রাকচার তৈরি করা যেটা দিয়ে সহজেই কম্পিউটারও এটা বুঝতে পারে যে কারা কানেক্টেড/একই সেটে আছে কিনা।
টাইপস্ক্রিপ্ট দিয়ে ইমপ্লিমেন্টেশন
আচ্ছা, এবার আসা যাক টাইপস্ক্রিপ্ট দিয়ে ইমপ্লিমেন্টেশনে। আমরা নোডগুলোকে রাখবো একটা হ্যাশম্যাপে (যেটা আসলে একটা অবজেক্ট)। যদি আমাদের নোডগুলো শুধু নাম্বার হতো আমরা অ্যারে দিয়েও কাজটা করতে পারতাম । নোডগুলোকে ঠিকঠাক সাজিয়ে একটা গ্রাফ তৈরি করতে আমাদের লাগবে একটা unionNodes ফাংশন, আর সেই গ্রাফ থেকে নোডের রুটগুলো খুঁজে আনতে একটা findRootNode ফাংশন। এই unionNodes আর findRootNode এর উপরে আমাদের ডাটা স্ট্রাকচারের এফিসিয়েন্সি নির্ভর করবে।
ফাংশনগুলোতে যাবার আগে আমরা একটা স্ট্রাকচার ভেবে নেই, যেটা আমাদের নোডের ব্যাপারে কিছু তথ্য রাখতে পারবে। টাইপস্ক্রিপ্ট এ type তৈরি করে কাজটা করা যায়, যেমন এখানে আমরা রেখছি একটা নোডের রুট আর ওই নোডের র্যাংক, যাতে বুঝা যায় নোডটি তার সেটের রুটের কত কাছে আছে।
type Node = {
root: string;
rank: number;
};আমাদের ডিসজয়েন্ট-সেটের স্ট্রাকচারটা হবে এমন একটা ম্যাপ, যার key হচ্ছে ওই নোডের ভ্যালু, মানে, a, b, c এমন কিছু স্ট্রিং। key গুলোর ভ্যালু হিসাবে থাকবে এমন একেকটা নোড। আমরা শুরুতে প্রত্যেকটা নোড কে ডিসকানেক্টেড ধরবো, মানে নিজের রুট এরা নিজেই। আর র্যাংক শুরুতে সবার ১, যেহেতু নিজেরাই রুট! মানে, শুরুতে আমাদের ম্যাপটা হবে এমন,
[a:{a 1} b:{b 1} c:{c 1} d:{d 1} e:{e 1} f:{f 1}]findRootNode ফাংশনের ইমপ্লিমেন্টেশন
findRootNode এর নাম আর কাজ একই, কোনো একটা নোডের রুট খুঁজে বের করা। ফাংশনটার প্যারামিটারগুলো হল একটা ম্যাপ, যার মধ্যে আমাদের নোডগুলো আছে; একটা স্ট্রিং, যেটা কোনো একটা নোডের key, যেমন, a, b ইত্যাদি। আর ফাংশনটা রিটার্ণ করবে এমন একটা নোড যার key ওই স্ট্রিং এর সমান। তারমানে, ফাংশনটা হবে এমন,
function findRootNode(nodes: Record<string, Node>, x: string): Node {
return nodes[x];
}খুবই সহজ, তাইনা? কিন্তু এভাবে শুধু নোড পাঠিয়ে দেয়াটা এফিসিয়েন্ট না অতটা। তাহলে আমাদের unionNodes ফাংশনটা এমনভাবে লিখতে হবে যাতে কোনো দুইটা সেট কানেক্ট বা ইউনিয়ন করলে যে রুটকে আমার নতুন কম্বাইন্ড সেটের রুট করছি, প্রতিটা এলিমেন্টের জন্য সেটা আপডেট হয়ে যাবে। এখানে আমরা Path Compression এর ধারণা ব্যবহার করে একে আরো ফাস্ট করতে পারি। পাথ কমপ্রেশন যেটা করে তার হলো কোনো নোড এর রুট খোজার সময় যেসব নোড পায় তাদের রুটও আপডেট করতে করতে যায়। ফলে প্রথম কয়েকবার findRootNode কল করলে ম্যাপের নোডগুলো তাদের রুট দিয়ে আপডেট হয়ে যায়। শেষমেশ দেখা যায়, গ্রাফের যেসব নোডের সাথে রুট ডাইরেক্টলি বা ইন্ডারেক্টলি কানেক্টেড, সব নোডেরই রুট ওই গ্রাফের/সেটের রুট!
function findRootNode(nodes: Record<string, Node>, x: string): Node {
if (x === nodes[x].root) {
return nodes[x];
}
nodes[x] = findRootNode(nodes, nodes[x].root);
return nodes[x];
}একটা উদাহরণ দেখা যাক। ধরি আমাদের কাছে একটা গ্রাফ আছে এমন,
a - b - d - e
|
cএখানে যদি আমরা কে কার প্যারেন্ট সেটা যদি (প্যারেন্ট,চাইল্ড) হিসাবে দেখাই, (a, b) (a, c) (b, d) (d, e)
এখানে findRootNode এ আমরা রিকার্শন ব্যবহার করে প্রতিবার চাইল্ডের রুট নোড খুঁজে সেটা পালটে প্যারেন্টের রুট নোড করে দেবো। ফলে পরেরবার আর ইটারেট করতে হবে না। মানে আমাদের ম্যাপটা শেষে হবে এমন, (a, b) (a, c) (a, d) (a, e)। ভ্যালু কিভাবে চেঞ্জ হচ্ছে সেটা দেখার জন্য ফাংশনের মধ্যে আমরা রুটগুলো প্রিন্ট করেও দেখতে পারি।
unionNodes ফাংশনের ইমপ্লিমেন্টেশন
unionNodes ফাংশনটার কাজ হচ্ছে কিছু ডিসিশনের ভিত্তিতে দুইটা নোডকে কানেক্ট করা। ফলে গ্রাফ সমসময় এমনভাবে থাকে জেনো নোডগুলোর রুট আর র্যাংক এর সামঞ্জস্য থাকে। ফাংশনটার প্যারামিটারগুলো হলে একটা ম্যাপ, যার মধ্যে আমাদের নোডগুলো আছে; দুইটা নোডের ভ্যালু, যাদেরকে কানেক্ট করা লাগবে। তারমানে, ফাংশনটা হবে অনেকটা এমন,
function unionNodes(nodes: Record<string, Node>, x: string, y: string): void {
const nodeX = findRootNode(nodes, x);
const nodeY = findRootNode(nodes, y);
if (nodeX.root !== nodeY.root) {
nodeX.root = nodeY.root;
// Or nodeY.root = nodeX.root
}
}সহজ ইমপ্লিমেন্টেশন। আমরা দেখছি যে দুইটা নোড আমরা পেয়েছি প্যারামিটারে, তাদের রুট কারা। যদি রুট একই হয়, তাহলে তারা অলরেডি কানেক্টেড, নতুন করে কানেক্ট করার দরকার নেই। আর যদি তা না হয়, তাহলে দ্বিতীয় নোডের রুট কে প্রথম নোডেরও রুট করে দিচ্ছি। কিন্তু একটা কিন্তু আছে এখানে! এমন যদি হয় প্রতিবার আমরা আগের গ্রাফের সাথে নোড যোগ না করে, নোডের সাথে নতুন গ্রাফকে যোগ করছি? মানে, a-b-c গ্রাফের সাথে d যোগ করে a-b-c-d হওয়ার বদলে হচ্ছে d-a-b-c, তাহলে? এখানে যেহেতু, দুটোই কাজ করার কথা, আমরা যেকোনো টাই ব্যবহার করতে পারি। কিন্তু এভাবে টাইম কমপ্লেক্সিটি অনেক বেড়ে যায়! তাই, বুদ্ধিমানের মত কাজ হচ্ছে দেখা যে কোন গ্রাফ (বা নোডের সেট) টা বড় আর তার সাথে আমাদের ছোটটা কানেক্ট করে দেয়া।
function unionNodes(nodes: Record<string, Node>, x: string, y: string): void {
const nodeX = findRootNode(nodes, x);
const nodeY = findRootNode(nodes, y);
if (nodeX.root !== nodeY.root) {
if (nodeX.rank > nodeY.rank) {
nodes[nodeY.root].root = nodeX.root;
} else if (nodeX.rank < nodeY.rank) {
nodes[nodeX.root].root = nodeY.root;
} else {
nodes[nodeY.root].root = nodeX.root;
nodes[nodeX.root].rank += 1;
}
}
}শেষকথা
কোনো গ্রাফে দুইটা নোডের কানেক্টিভিটি বের করা খুবই কমন একটা সমস্যা, যা অনেকভাবেই সমাধান করা যায়। অপটিমাইজড ডিসজয়েন্ট-সেট ডাটা স্ট্রাকচার ব্যবহার করে খুব এফিসিয়েন্টলি এটা সমাধান করা সম্ভব, যেমন নিচের প্রবলেমটা!