C++-এ গ্রাফ স্ট্রাকচার্ড স্ট্যাক বাস্তবায়ন

গ্রাফ স্ট্রাকচার্ড স্ট্যাক (Graph Structured Stack) একটি উন্নত ডেটা স্ট্রাকচার যা গ্রাফ ট্রাভার্সাল (বিশেষ করে টমসন কনস্ট্রাকশন বা পার্সিং-এ) একটি নোড থেকে অন্য নোডে পথ ট্র্যাক করতে ব্যবহৃত হয়। এটি একসাথে একাধিক স্ট্যাক ম্যানেজ করে যেখানে স্ট্যাকগুলো নোড শেয়ার করতে পারে।

এলগরিদম (সরলীকৃত)

শুরু
  Function graphStructuredStack(adjMat, source, bottomNode):
    অ্যাডজেসেন্সি ম্যাট্রিক্স কপি করুন
    সোর্স নোডকে mystack-এ পুশ করুন
    যতক্ষণ mystack খালি নয়:
      element = mystack.top()
      সব ডেস্টিনেশন d-এর জন্য:
        যদি adjMat[element][d] == 1:
          d কে mystack-এ পুশ করুন
          parent[d] = element
          adjMat[element][d] = 0  // ভিজিটেড মার্ক
          যদি d == bottomNode:
            stackFound = true
            ব্রেক
          element = d, d = 1, কন্টিনিউ
        d++
      যদি stackFound:
        bottomNode থেকে source পর্যন্ত parent ফলো করে istack বানান
        istack কে stackList-এ যোগ করুন
        stackFound = false
      mystack.pop()
    stackList-এর সব স্ট্যাক প্রিন্ট করুন
শেষ

উদাহরণ কোড

#include <iostream>
#include <cstdlib>
#include <stack>
#include <list>
using namespace std;

class GraphStructuredStack {
private:
    list< stack<int> > stackList;
    stack<int> mystack;
    int noOfNodes;
    int **adjMat;
    int *par;

public:
    GraphStructuredStack(int noOfNodes) {
        this->noOfNodes = noOfNodes;
        adjMat = new int*[noOfNodes + 1];
        par = new int[noOfNodes + 1];
        for (int i = 0; i <= noOfNodes; i++)
            adjMat[i] = new int[noOfNodes + 1];
    }

    void graphStructuredStack(int **adjMat, int s, int bNode) {
        bool stackFound = false;

        // অ্যাডজেসেন্সি ম্যাট্রিক্স কপি
        for (int sv = 1; sv <= noOfNodes; sv++)
            for (int dv = 1; dv <= noOfNodes; dv++)
                this->adjMat[sv][dv] = adjMat[sv][dv];

        mystack.push(s);
        int element, d;

        while (!mystack.empty()) {
            element = mystack.top();
            d = 1;

            while (d <= noOfNodes) {
                if (this->adjMat[element][d] == 1) {
                    mystack.push(d);
                    par[d] = element;
                    this->adjMat[element][d] = 0;

                    if (d == bNode) {
                        stackFound = true;
                        break;
                    }
                    element = d;
                    d = 1;
                    continue;
                }
                d++;
            }

            if (stackFound) {
                stack<int> istack;
                for (int node = bNode; node != s; node = par[node])
                    istack.push(node);
                istack.push(s);
                stackList.push_back(istack);
                stackFound = false;
            }
            mystack.pop();
        }

        // সব স্ট্যাক প্রিন্ট
        for (auto it = stackList.begin(); it != stackList.end(); ++it) {
            stack<int> st = *it;
            while (!st.empty()) {
                cout << st.top() << "\t";
                st.pop();
            }
            cout << endl;
        }
    }
};

int main() {
    int noofnodes;
    cout << "Enter number of nodes: ";
    cin >> noofnodes;

    GraphStructuredStack gss(noofnodes);
    int source, bottom;
    int **adjMatrix = new int*[noofnodes + 1];
    for (int i = 0; i <= noofnodes; i++)
        adjMatrix[i] = new int[noofnodes + 1];

    cout << "Enter the graph matrix:" << endl;
    for (int sv = 1; sv <= noofnodes; sv++)
        for (int dv = 1; dv <= noofnodes; dv++)
            cin >> adjMatrix[sv][dv];

    cout << "Enter the source node: ";
    cin >> source;
    cout << "Enter the bottom node: ";
    cin >> bottom;

    cout << "The stacks are:" << endl;
    gss.graphStructuredStack(adjMatrix, source, bottom);
    return 0;
}

নমুনা আউটপুট

Enter number of nodes: 4
Enter the graph matrix:
1 1 1 0
0 1 1 0
1 0 0 0
1 1 1 1
Enter the source node: 3
Enter the bottom node: 1
The stacks are:
3 1

ব্যবহার ক্ষেত্র: কম্পাইলার ডিজাইন (LR পার্সিং), গ্রাফ অ্যালগরিদম যেখানে শেয়ারড সাব-পাথ ট্র্যাক করা লাগে।