ডিসজয়েন্ট-সেট বা ইউনিয়ন-ফাইন্ড, পারস্পারিক বিচ্ছিন্ন সেটের বিভিন্ন সমস্যা সমাধানে খুবই পরিচিত একটা ডাটা স্ট্রাকচার। আজকে আমি জানানোর চেষ্টা করবো কিভাবে Go দিয়ে এটা ইমপ্লিমেন্ট করা যায়।

টুকটাক থিউরি

ডিসজয়েন্ট-সেট কি?

যদি কয়েকটা সেটের মধ্যে কোনো কমন এলিমেন্ট না থাকে, তাহলে সেই সেটগুলোকে ডিসজয়েন্ট-সেট বলা হয়। মানে,যদি 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 কি কানেক্টেড? আমরা কিন্তু সহজেই বলে দিতে পারি, হ্যাঁ, কারণ এরা একই সেটে আছে বা এদের রুট একই! আমাদের লক্ষ্য হলো এমনই একটা স্ট্রাকচার তৈরি করা যেটা দিয়ে সহজেই কম্পিউটারও এটা বুঝতে পারে যে কারা কানেক্টেড/একই সেটে আছে কিনা।

ইমপ্লিমেন্টেশন

আচ্ছা, এবার আসা যাক Go দিয়ে ইমপ্লিমেন্টেশনে। আমরা নোডগুলোকে রাখবো একটা ম্যাপে (অনেক সময় হ্যাশম্যাপ ও বলে)। যদি আমাদের নোডগুলো শুধু নাম্বার হতো আমরা স্লাইস দিয়েও করতে পারতাম । নোডগুলোকে ঠিকঠাক সাজিয়ে একটা গ্রাফ তৈরি করতে আমাদের লাগবে একটা UnionNodes ফাংশন, আর সেই গ্রাফ থেকে নোডের রুটগুলো খুঁজে আনতে একটা FindRootNode ফাংশন। এই UnionNodes আর FindRootNode এর উপরে আমাদের ডাটা স্ট্রাকচারের এফিসিয়েন্সি নির্ভর করবে।

ফাংশনগুলোতে যাবার আগে আমরা একটা স্ট্রাকচার ভেবে নেই, যেটা আমাদের নোডের ব্যাপারে কিছু তথ্য রাখতে পারবে। Go তে struct বলে একটা কালেকশন টাইপ আছে, যাতে আমরা বিভিন্ন টাইপের কয়েকটা ডাটা রাখতে পারি। যেমন এখানে আমরা রেখছি একটা নোডের রুট আর ওই নোডের র‍্যাংক, যাতে বুঝা যায় নোডটি তার সেটের রুটের কত কাছে আছে।

type Node struct {
  root string
  rank int
}

আমাদের ডিসজয়েন্ট-সেটের স্ট্রাকচারটা হবে এমন একটা ম্যাপ, যার 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 ওই স্ট্রিং এর সমান। তারমানে, ফাংশনটা হবে অনেকটা এমন,

func FindRootNode(nodes map[string]Node, x string) Node {
  return nodes[x]
}

খুবই সহজ, তাইনা? কিন্তু এভাবে শুধু নোড পাঠিয়ে দেয়াটা এফিসিয়েন্ট না অতটা। কারণ, তাহলে আমাদের UnionNodes ফাংশনটা এমনভাবে লিখতে হবে যাতে কোনো দুইটা সেট কানেক্ট বা ইউনিয়ন করলে যে রুটকে আমার নতুন কম্বাইন্ড সেটের রুট করছি, প্রতিটা এলিমেন্টের জন্য সেটা আপডেট হয়ে যাবে। এখানে আমরা Path Compression এর ধারণা ব্যবহার করে একে আরো ফাস্ট করতে পারি। পাথ কমপ্রেশন যেটা করে তার হলো কোনো নোড এর রুট খোজার সময় পথে যেসব নোড পায় তাদের রুটও আপডেট করতে করতে যায়। ফলে প্রথম কয়েকবার FindRootNode কল করলে ম্যাপের নোডগুলো তাদের রুট দিয়ে আপডেট হয়ে যায়। শেষমেশ দেখা যায়, গ্রাফের যেসব নোডের সাথে রুট ডাইরেক্টলি বা ইন্ডারেক্টলি কানেক্টেড, সব নোডেরই রুট ওই গ্রাফের/সেটের রুট!

func FindRootNode(nodes map[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 ফাংশনটার কাজ হচ্ছে কিছু ডিসিশনের ভিত্তিতে দুইটা নোডকে কানেক্ট করা। ফলে গ্রাফ সমসময় এমনভাবে থাকে জেনো নোডগুলোর রুট আর র‍্যাংক এর সামঞ্জস্য থাকে। ফাংশনটার প্যারামিটারগুলো হলে একটা ম্যাপ, যার মধ্যে আমাদের নোডগুলো আছে; দুইটা নোডের ভ্যালু, যাদেরকে কানেক্ট করা লাগবে। তারমানে, ফাংশনটা হবে অনেকটা এমন,

func UnionNodes(nodes map[string]Node, x, y string) {
  nodeX := FindRootNode(nodes, x)
  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, তাহলে? এখানে যেহেতু, দুটোই কাজ করার কথা, আমরা যেকোনো টাই ব্যবহার করতে পারি। কিন্তু এভাবে টাইম কমপ্লেক্সিটি অনেক বেড়ে যায়! তাই, বুদ্ধিমানের মত কাজ হচ্ছে দেখা যে কোন গ্রাফ (বা নোডের সেট) টা বড় আর তার সাথে আমাদের ছোটটা কানেক্ট করে দেয়া।

func UnionNodes(nodes map[string]Node, x, y string) {
  nodeX := FindRootNode(nodes, x)
  nodeY := FindRootNode(nodes, y)

  if nodeX.root != nodeY.root {
    if nodeX.rank > nodeY.rank {
      nodeY.root = nodeX.root
    } else if nodeX.rank < nodeY.rank {
      nodeX.root = nodeY.root
    } else {
      nodeY.root = nodeX.root
      nodeX.rank += 1
    }
    nodes[x] = nodeX
    nodes[y] = nodeY
  }
}

এখানে আমরা র‍্যাঙ্ক দিয়ে গ্রাফের হাইট বা উচ্চতা মাপছি। প্রতিবার রুট চেঞ্জ হলে, নতুন রুটের হাইট বাড়ে। ফলে কোনো রুটের র‍্যাংক দেখে সহজেই বোঝা যায় গ্রাফটা কত বড়! নিচের দুইটা লাইনের কারণ হচ্ছে, গো তে স্ট্রাক্ট ম্যাপের ভ্যালু সরাসরি চেঞ্জ করা যায় না।

nodes[x] = nodeX
nodes[y] = nodeY

শেষকথা

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

বোনাস

নিচের প্রবলেমটা ডিসজয়েন্ট-সেট ইউনিয়ন দিয়ে সমাধান করা যায়। চেষ্টা করে দেখতে পারেন। https://leetcode.com/problems/number-of-provinces/