প্রিরিকুইজিট: গ্রাফ থিউরি, গ্রাফ ট্র্যাভার্সাল

কম্পিউটারে গ্রাফ রিপ্রেজেন্ট করার জন্যে ইনপুট সাইজ খুবই গুরুত্বপূর্ণ। আর প্রোগ্রামিং কন্টেস্টে সাধারণত বিভিন্ন ইনপুট সাইজের উপর ভিত্তি করে দুই রকম রিপ্রেজেন্টেশন ব্যবহার করা হয় – অ্যাডজেসেন্সি মেট্রিক্স আর অ্যাডজেসেন্সি লিস্ট। ছোট গ্রাফের জন্যে মেট্রিক্স রিপ্রেজেন্টেশন সুবিধাজনক হলেও বড় গ্রাফের জন্যে এটা মেমরি এফিশিয়েন্ট না। C++ এ STL (বা অন্য ল্যাঙ্গুয়েজে এই ধরণের কন্টেইনার) ব্যবহার করে অ্যাডজেসেন্সি লিস্ট ইমপ্লিমেন্ট করা যায়, আর করাও খুব সহজ। তবে আজকে আমরা সেটা দেখব না, দেখব আরেকটা সহজ উপায়ে অ্যাডজেসেন্সি লিস্ট কিভাবে ইমপ্লিমেন্ট করা যায়।

ধরা যাক, গ্রাফের সবগুলো নোড আর এজের একটা লিস্ট (এজ এর অ্যারে) আছে । স্পেস কমপ্লেক্সিটি এখানে O(এজ সংখ্যা + নোড সংখ্যা)। গ্রাফটা ট্র্যাভার্স করতে গেলে কি করতে হবে?

একটা নোডে যেয়ে ওই নোড থেকে যে যে এজগুলো বের হয় সেগুলো পাওয়া লাগবে। এজ লিস্ট থেকে খুঁজে খুঁজে বের করতে গেলে (একটা একটা করে এজ দেখে) প্রতি নোডে পুরো এজ লিস্ট টাই দেখে ফেলা লাগবে। তাই খুব একটা টাইম এফিশিয়েন্ট না।

এফিশিয়েন্ট করার জন্যে যেটা করা যায় সেটা হল – কোন নোড থেকে বের হওয়া কোন একটা এজ এর পরের এজটা যেটা, এজ লিস্টে সেটার ইন্ডেক্সটা যদি কোন ভাবে রেখে দেওয়া যায়। এটা কিন্তু করা যায় গ্রাফটা তৈরি করবার সময়ই। যখনই আমরা একটা এজ (a,b) যোগ করব ওই এজটা হবে a এর সবচেয়ে নতুন যোগ হওয়া এজ। আমরা যদি a নোড এর সবচেয়ে নতুন এজ (a, b) এর ইন্ডেক্সটা রেখে দিতে পারি,তাহলে এইমাত্র যোগ হওয়া এজ (a,b) এর মধ্যে a নোডে যোগ হওয়া ঠিক তার আগের এজটার ইন্ডেক্সটা রেখে দিতে পারবো। একই নোডের এজগুলোর মাঝে এই যোগসূত্র থাকায় এজগুলো ভিজিট করার সময় কখনই অন্য নোডের এজে যাবে না। কোড দেখলে পুরো ব্যাপারটা আরো পরিষ্কার হবে।

এজ লিস্টের জন্যে একটা স্ট্রাকচার বানাই:

struct Edge {
  int to; // বর্তমান এজটা যে নোডে যাচ্ছে
  int prevEdge; // পূর্ববর্তী এজের ইন্ডেক্স, বলে রাখা ভালো ট্রাভার্সিংয়ের সময় এজগুলো উলটো অর্ডারে ভিজিট হবে
  // এজ এর অন্যান্য তথ্য যেমন Weight, Capacity
} edgeList[NO_OF_EDGES]; // NO_OF_EDGES = এজ সংখ্যা
 
int lastEdge[NO_OF_NODES]; // lastEdge[v] = কোন একটা নোড v তে যোগ হওয়া সর্বশেষ এজের ইন্ডেক্স, শুরুতেই -1 দিয়ে ইনিশিয়ালাইজ করে নিতে হবে।  NO_OF_NODES = নোড সংখ্যা
int numEdges; // গ্রাফে এ পর্যন্ত যে কটা এজ যোগ করা হয়েছে তার সংখ্যা, শুরুতে 0 দিয়ে ইনিশিয়ালাইজ হবে

একটা এজ যোগ করা যাবে এভাবে:

void addEdge(int u, int v) {
  edgeList[numEdges].to = v;
  edgeList[numEdges].prevEdge = lastEdge[u];
  lastEdge[u] = numEdges;
  numEdges++;
}

আর এভাবে ট্রাভার্স করা যাবে:

bool seen[NO_OF_NODES]; // ভিজিট ফ্ল্যাগ, শুরুতেই false দিয়ে ইনিশিয়ালাইজ করা
void dfs(int u) {
  seen[u] = true;
  for (int e = lastEdge[u]; e != -1; e = edgeList[e].prevEdge) {
    int v = edgeList[e].to;
    if (!seen[v]) {
      dfs(v);
    }
  }
}

ফ্লো-নেটওয়ার্কের ক্ষেত্রেও এই টেকনিকটা কাজে লাগানো যায়। আমরা যদি প্রতিটা আর্ক আর তার রিভার্স আর্কটা লিস্টে পরপর রাখি তাহলে আর্কের এজ ইন্ডেক্স হবে $2i$ আর রিভার্সটার হবে $2i+1$ ($0$-বেইসড ইন্ডেক্সিং)। $2i$ কে $1$ দিয়ে XOR করলে $2i+1$ পাওয়া যায়। আবার $2i+1$ কে একইভাবে $1$ দিয়ে XOR করলে $2i$ পাওয়া যায়। এভাবে খুব সহজেই কোন আর্কের রিভার্স আর্ক পাওয়া যাবে।

(এই ট্রিকটা আমি প্রথম শিখি টপকোডারের anastasov.bg এর কাছে, Anastasov কে ধন্যবাদ!)