C++-এ DAG-এর জন্য র‍্যান্ডম লিনিয়ার এক্সটেনশন (Random Linear Extension) তৈরি করা

এখানে আমরা ডirected অ্যাসাইক্লিক গ্রাফ (DAG - Directed Acyclic Graph) এর জন্য র‍্যান্ডম লিনিয়ার এক্সটেনশন (Random Linear Extension) তৈরি করার পদ্ধতি দেখব। লিনিয়ার এক্সটেনশন মূলত DAG-এর টপোলজিক্যাল সর্টিং (topological sorting)।

গ্রাফ নিচের মত হওয়ার কথা:

একটি ডirected অ্যাসাইক্লিক গ্রাফের টপোলজিক্যাল সর্টিং হলো ভার্টেক্সগুলোর লিনিয়ার অর্ডারিং। প্রতিটি এজ u-v-এর জন্য, ভার্টেক্স u, ভার্টেক্স v-র আগে অর্ডারিং-এ আসবে।

যেহেতু সোর্স ভার্টেক্স ডেস্টিনেশন ভার্টেক্সের পরে আসে, তাই আমাদের পূর্বের এলিমেন্টগুলো সংরক্ষণ করার জন্য একটি স্ট্যাক (stack) ব্যবহার করতে হবে। সব নোড কমপ্লিট হলে, স্ট্যাক থেকে সেগুলো সহজে ডিসপ্লে করা যাবে।

ইনপুট

আউটপুট

টপোলজিক্যালি সর্ট করা নোডের ক্রম - 5 4 2 3 1 0

অ্যালগরিদম

topoSort(u, visited, stack)

ইনপুট - শুরুর ভার্টেক্স u, ভিজিটেড ট্র্যাক করার অ্যারে, নোড সংরক্ষণের স্ট্যাক।

আউটপুট - স্টকে টপোলজিক্যাল সিকোয়েন্সে ভার্টেক্স সর্টিং।

শুরু
  u কে ভিজিটেড চিহ্নিত করুন
  u-র সাথে এডজেসেন্ট সব ভার্টেক্স v এর জন্য, করুন
    যদি v ভিজিটেড না হয়, তবে
      topoSort(v, visited, stack)
    শেষ করুন
  u কে স্টকে পুশ করুন
শেষ

performTopologicalSorting(Graph)

ইনপুট - দেওয়া ডirected অ্যাসাইক্লিক গ্রাফ।

আউটপুট - নোডের সিকোয়েন্স।

শুরু
  প্রাথমিকভাবে সব নোডকে আনভিজিটেড চিহ্নিত করুন
  গ্রাফের সব নোড v এর জন্য, করুন
    যদি v ভিজিটেড না হয়, তবে
      topoSort(v, visited, stack)
    শেষ করুন
  স্ট্যাক থেকে সব এলিমেন্ট পপ ও প্রিন্ট করুন
শেষ

উদাহরণ কোড

#include <iostream>
#include <stack>
#define NODE 6
using namespace std;

int graph[NODE][NODE] = {
    {0, 0, 0, 0, 0, 0},
    {0, 0, 0, 0, 0, 0},
    {0, 0, 0, 1, 0, 0},
    {0, 1, 0, 0, 0, 0},
    {1, 1, 0, 0, 0, 0},
    {1, 0, 1, 0, 0, 0}
};

void topoSort(int u, bool visited[], stack<int> &stk) {
    visited[u] = true; // নোড v কে ভিজিটেড সেট করুন
    for (int v = 0; v < NODE; v++) {
        if (graph[u][v]) { // u-র সাথে এডজেসেন্ট সব ভার্টেক্স v
            if (!visited[v])
                topoSort(v, visited, stk);
        }
    }
    stk.push(u); // শুরুর ভার্টেক্স স্টকে পুশ
}

void performTopologicalSort() {
    stack<int> stk;
    bool vis[NODE];
    for (int i = 0; i < NODE; i++)
        vis[i] = false; // প্রাথমিকভাবে সব নোড আনভিজিটেড
    for (int i = 0; i < NODE; i++)
        if (!vis[i]) // নোড ভিজিটেড না হলে
            topoSort(i, vis, stk);
    while (!stk.empty()) {
        cout << stk.top() << " ";
        stk.pop();
    }
}

int main() {
    cout << "Nodes after topological sorted order: ";
    performTopologicalSort();
    return 0;
}

আউটপুট

Nodes after topological sorted order: 5 4 2 3 1 0