গ্রাফ থিওরি - ২ঃ ভেরিয়েবলে গ্রাফ ইনপুট নেওয়া

চিত্রে একটি আনওয়েটেড গ্রাফ দেখা যাচ্ছে। এই গ্রাফ নিয়ে প্রোগ্রামিং করতে হলে গ্রাফটাকে আগে ইনপুট নিতে হবে। কিন্তু প্রোগ্রামিং এ ইনপুট নিবো কিভাবে? সেখানে তো এরকম দাগ-টাগ টানা যায়না। এজও দেওয়া যায়না। তাইলে কেমনে কি :|

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

তো চিত্রে দেখে কি মনে হচ্ছে? ০ থেকে ১, ২, ৩ নাম্বার ঘরে যেতে পারি; ১ থেকে ০ এবং ২ এ যেতে পারি; ২ থেকে ১, ০, ৩, ৫ এ যেতে পারি; ৩ থেকে ০, ৫, ৪ এ সরাসরি যেতে পারি।

তো আমরা যদি ইনপুট এমনভাবে নিতে পারি যাতে এ সম্পর্কগুলো বজায় থাকে তবেই কাজ শেষ। তোমরা নিজেরা কিছুক্ষন চিন্তাভাবনা করো কোন পদ্ধতি খুঁজে পাও কিনা।

যদি কিছু খুঁজে না পাও এইদিকে আসো। উপরের সম্পর্কটাকে একটা লিস্ট আকারে সাজাই-
০-> ১, ২, ৩ //০ থেকে ১, ২, ৩ এ যাওয়া যায়
১-> ০, ২     //১ থেকে ০, ২ তে যাওয়া যায়। এভাবে সবগুলো
২-> ১, ০, ৩, ৫
৩-> ০, ৫, ৪
৪-> ৩, ৫
৫-> ২, ৩, ৪

উপরের লিস্ট টা দেখে তুমি আবার চিত্রটা ড্র করার চেষ্টা করো। যদি তুমি পেরে যাও তাহলে ধরে নাও তোমার অর্ধেক শেখা হয়ে গেছে।

তো এই কাজটা প্রোগ্রামিং এ করবো কিভাবে? তুমি চাইলে ২ডি অ্যারে ব্যাপারটা চেষ্টা করে দেখতে পারো। একটু হিন্ট দেই-

graph[0][1]  //০ থেকে ১ এ যাওয়া যায়
graph[0][2]  //০ থেকে ২ এ যাওয়া যায়
graph[0][3] //০ থেকে ৩ এ যাওয়া যায়
.
.
graph[5][2]
graph[5][3]
graph[5][4]

দেখোতো পারো কিনা! হবে কিনা আমিও শিওর না।  যদি এভাবে পেরে যাও আমাকে জানাবা। ট্রিট দিলেও দিতে পারি ;) (চোখ টিপের মানে হলো শর্ত প্রযোজ্য)

তো, তোমরা যারা জাভা পারো তারা এই কাজটাকে খুব সুন্দরভাবে করতে পারবে। ৬ টা অ্যারেলিস্ট নাও! প্রতিটা অ্যারে লিস্ট ভিতরে তার  সাথে কানেক্টেড নোডগুলোকে ঢুকিয়ে দিলেই ভেজাল শেষ।

ArrayList<Integer>[] graph = new ArrayList[6];  //৬ টা অ্যারেলিস্ট নিলাম। অ্যারেলিস্ট অব অ্যারে

graph[0] = new ArrayList<>();   //প্রথম অ্যারেলিস্ট এর যায়গা এলোকেট করলাম। জাভা জানলে এটা বুঝার কথা

graph[0].add(1);    //০ অ্যারেলিস্টের সাথে ১ কানেক্টেড
graph[0].add(2);
graph[0].add(3);

graph[1] = new ArrayList<>(); // ১ নাম্বার অ্যারেলিস্টের জন্য যায়গা এলোকেট করা
graph[1].add(0);
graph[1].add(2);

এভাবে আমরা কোন একটা অ্যারেলিস্ট দেখেই বলে দিতে পারবো তার সাথে কোন কোন নোড কানেক্টেড আছে। এখানে প্রতিটি অ্যারেলিস্ট এক একটা নোড হিসেবে কাজ করছে। উপরে গ্রাফ স্টোরের যে পদ্ধতি নিয়ে আলোচনা করলাম তার একটা নাম আছে আর তা হলো এডজেসেন্সি লিস্ট।

এই কাজটা সি প্লাস প্লাস এর ভেক্টর দিয়েও করা যায়। বলে রাখা ভালো ভেক্টর এবং অ্যারেলিস্টের কাজ একই। দুইটাই ডায়নামিক্যালি মেমরি এলোকেট করে ডেটা স্টোর করে। তোমাদের কাজ হলো পুরো গ্রাফটাকে স্টোর করা এবং একটা লুপ চালিয়ে কার সাথে কে কানেক্টেড তা প্রিন্ট করে দেখানো উপরের লিস্টের মত।

গ্রাফ স্টোর করার আরেকটা পদ্ধতি আছে তা হলো- এডজেসেন্সি ম্যাট্রিক্স। এই পদ্ধতিতে একটা ২ডি অ্যারেতে গ্রাপ ইনপুট নেওয়া হয়। গ্রাফে যতগুলো নোড আছে ২ডি অ্যারের সাইজ ঠিক ততটাই নিতে হয়। যেমন উপরের গ্রাফের ক্ষেত্রে হবে graph[6][6] !

এখন এইটার ভিতর আমাদের গ্রাফটা ঢুকাবো কেমনে? সেই পুরান কাহিনী। কইলেই বুইঝা ফেলবা

graph[0][0] = 0 //০ এর সাথে ০ এর কানেকশ নাই
graph[0][1] = 1 //০ এর সাথে ১ এর কানেকশন
graph[0][2] = 1 //০ এর সাথে ২ এর কানেকশন
graph[0][3] = 1 //০ এর সাথে ৩ এর কানেকশন
graph[0][4] = 0 //০ এর সাথে ৪ এর কানেকশন নাই
graph[0][5] = 0 //০ এর সাথে ৫ কানেকশন নাই

বুঝতেই পারতেছো কি করছি। যার সাথে যার কানেকশন আছে তার ঘরে ১ বসায়া দিচ্ছি আর যার সাথে যার কানেকশন নাই তার ঘরে বসায়া দিছি শুন্য। এভাবে বাকি নোডগুলোর ক্ষেত্রেও কিন্তু একই কেইস।

graph[1][0]--------------------graph[1][5] // ১ এর সাথে যার যার কানেকশন আছে সেই ঘরে ১ নাহলে ০
graph[2][0]--------------------graph[2][5]
.
.
graph[5][0]--------------------graph[5][5]

যারা বুঝতেছোনা কি ঘটছে তারা নীচের টেবিলটার দিকে তাকাও। নিজের প্র্যাক্টিস করার খাতার ছবিই দিয়ে দিলাম। লিখতে আলসেমি লাগতেছে। যাকগে আমার হাতের লেখার দিকে তাকালে মাইর খাবা :|

অ্যাডজেসেন্সি ম্যাট্রিক্স

এভাবে বাকিগুলো। তারপর আমরা ছোট্ট একটা লুপ চালিয়ে এদের ভিতরে ভেলু চেক করে খুব সহজেই বলে দিতে পারবো কার সাথে কার কানেকশন। তো তোমরা এই কাজটাও কইরালাও এবং লুপ চালায়া প্রিন্ট করো কার সাথে কার প্রেম বালুবাসা!

আমিও ইমপ্লিমেন্ট করছি তোমরা নিজেরা করে তারপর দেইখা নিতে পারো। আমি অ্যাডজেন্সি লিস্ট সি প্লাস প্লাস এর ভেক্টর দিয়ে করছি। তোমরা অন্য যেকোন ল্যাংগুয়েজ বা অ্যারেলিস্ট/লিংক লিস্ট হেন তেন ব্যবহার করতে পারো।

ক্ষ্যাতমার্কা কোডিং করছি এইটারে স্মার্ট করার দায়িত্ব তোমাদের। এই ধরো-
১। অ্যাডজেসেন্সি ম্যাট্রিক্স
২। অ্যাডজেন্সি লিস্ট

টাইম কমপ্লেক্সিটিঃ তো গ্রাফ স্টোরের দুইটা পদ্ধতি দেখলাম। এই দুইটার মধ্যে কোনটা ভালা? তুমি যেহেতু এই পোস্টটা পড়তেছো আমি ধরে নিচ্ছি তুমি টাইম কমপ্লেক্সিটির/মেমরি কমপ্লেক্সিটির কিচ্ছাকাহিনী গেবনে একবার হলেও শুনছো।

অ্যাডজেন্সি ম্যাট্রিক্স এর কথাই আগে কই। একটা গ্রাফে যতগুলো এজ থাকুকনা কেন ডেটা রাখার জন্য তোমাকে n*n সাইজের অ্যারে ডিক্লেয়ার করা লাগবে। উপরের গ্রাফে মোট এজ আছে ৯টা কিন্তু আমরা ইউজ করছি মোট 6*6 = 36 টা ইন্টেজার। মানে এডজেন্সি ম্যাট্রিক্স এর মেমরি কমপ্লেক্সিটি n^2। তবে অ্যাডজেন্সি ম্যাট্রিক্স এর একটা সুবিধা হলো কোন নোডের সাথে কোন নোড কানেক্টেড তা আমরা O(1) কমপ্লেক্সিটিতেই পেয়ে যাবো। যদি বলি ০ এর সাথে ৩ এর কানেকশন আছে কিনা আমরা সিমপ্লি graph[0][3] চেক করলেই বুঝে যাবো। তবে বড় সাইজের কোন গ্রাফের ক্ষেত্রে অ্যাডজেন্সি লিস্ট ইউজ না করাই ভালো। এতে হিতে বিপরীত হতে পারে।


এইবার আসি অ্যাডজেন্সি লিস্টের কথা। অ্যাডজেন্সি ম্যাট্রিক্স এর সমস্যা বুঝতে পারছো সে কেন বেশী মেমরি খায়? আমরা সেখানে কানেক্টেড এবং নন কানেক্টেড সবগুলো নোডেরই ট্র্যাক রাখতেছি। কিন্তু কেন ভাই? যার অস্তিত্বই নাই তার ট্র্যাক রাখার কেন দরকার। অ্যাডজেসেন্সি লিস্ট ঠিক এই কাজটাই করছে। তার সাথে যার কানেকশন শুধু তারে তার দলে রাখছে। এভাবে সবগুলো নোডই এই কাজটা করছে। এতে মেমরি কনজাম্পশন কমে আসছে। এটার মেমরি কমপ্লেক্সিটি কত এবং আর একটা নোডের কানেক্টেড সব নোড খুঁজে বের করতে কি পরিমান সময় লাগবে? এইটা খুঁজে বের করা তোমার কাজ।  আজ এই পর্যন্তই! টা  টু