โปรแกรม C++ สำหรับการใช้งาน Graph Structured Stack

ในโปรแกรม C++ นี้ เราใช้งาน Graph Structured Stack (GSS) ซึ่งเป็นโครงสร้างข้อมูลที่ใช้ในการแยกวิเคราะห์ (parsing) โดยเฉพาะ Tomita's algorithm สำหรับ Generalized LR parsing GSS แทนสแต็กหลายตัวที่แบ่งก้อน (fork) และรวมกัน (merge) ได้

อัลกอริธึม (Graph Structured Stack)

1. รับ adjacency matrix, source node, bottom node
2. คัดลอก adjacency matrix
3. Push source ลง stack หลัก (mystack)
4. While mystack ไม่ว่าง:
   • Pop element (current node)
   • สำหรับแต่ละ destination node d:
     • ถ้ามี edge (element, d): push d, บันทึก parent, ลบ edge
     • ถ้า d == bottom node: พบ path → สร้าง stack ใหม่จาก parent chain
5. พิมพ์ทุก stack ที่พบ (แต่ละ stack = path จาก source ถึง bottom)

โค้ดตัวอย่าง

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

class GraphStructuredStack {
private:
    list< stack<int> > stackList; // เก็บ path ทั้งหมดที่พบ
    stack<int> mystack;            // stack สำหรับ DFS
    int noOfNodes;
    vector<vector<int>> adjMat;  // ใช้ vector แทน int** เพื่อความปลอดภัย
    vector<int> par;              // parent array

public:
    GraphStructuredStack(int noOfNodes) : noOfNodes(noOfNodes) {
        adjMat.assign(noOfNodes + 1, vector<int>(noOfNodes + 1, 0));
        par.assign(noOfNodes + 1, -1);
    }

    void graphStructuredStack(vector<vector<int>> &adjMat, int s, int bNode) {
        this->adjMat = adjMat;
        bool stackFound = false;

        mystack.push(s);

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

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

                    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();
        }

        // พิมพ์ทุก path (stack)
        for (auto &st : stackList) {
            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);
    vector<vector<int>> adjMatrix(noofnodes + 1, vector<int>(noofnodes + 1, 0));

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

    int source, bottom;
    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

หมายเหตุ: โค้ดต้นฉบับใช้ int** และ new/delete แบบ manual โค้ดด้านบนปรับใช้ vector เพื่อความปลอดภัยและอ่านง่ายขึ้น GSS ใช้จริงใน parser generator เช่น Bison (GLR) หรือ Earley parser