C++でグラフ構造化スタック（Graph Structured Stack）を実装する方法

この記事では、C++を用いてグラフ構造化スタック（Graph Structured Stack）を実装する方法を解説します。グラフ構造化スタックは、複数のスタックの状態を有向グラフとして管理できるデータ構造であり、GLR構文解析などのパースアルゴリズムで利用されることで知られています。本プログラムでは、隣接行列で表現されたグラフ上を探索し、始点ノードからボトムノードに至る経路を複数のスタックとして検出・出力します。

アルゴリズムの手順

開始
    関数 graphStructuredStack(int **adjMat, int s, int bNode):
    隣接行列 adjMat、始点 s、ボトムノード bNode を受け取る
    stackFound = false で初期化する
    sVertex = 1 から noOfNodes まで繰り返す
        dVertex = 1 から noOfNodes まで繰り返す
            this->adjMat[sVertex][dVertex] = adjMat[sVertex][dVertex]
        繰り返し終了
    繰り返し終了
    始点 s を mystack にプッシュする
    while (!mystack.empty())
        element = mystack.top()
        d = 1 で初期化する
        while (d <= noOfNodes)
            if (this->adjMat[element][d] == 1)
                行き先 d を mystack にプッシュする
                par[d] = element（親ノードを記録）
                this->adjMat[element][d] = 0（辺を使用済みにする）
                if (d == bNode)
                    stackFound = true を設定して break
                終了
                element = d
                d = 1
                continue
            終了
            d をインクリメント
        繰り返し終了
        if (stackFound)
            node = bNode から node != s の間
                node を istack にプッシュ
            s を istack にプッシュ
            stackList.push_back(istack)
            stackFound = false に戻す
        終了
        mystack から要素をポップ
    繰り返し終了
    iterator = stackList.begin()
    while (iterator != stackList.end())
        イテレータを進める
        while (!stack.empty())
            スタックの先頭要素を出力
            スタックから要素をポップ
        繰り返し終了
    繰り返し終了
終了。

サンプルコード

#include <iostream>
#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];
      this->par = new int [noOfNodes + 1];
      for (int i = 0; i < noOfNodes + 1; i++)
         adjMat[i] = new int [noOfNodes + 1];
   }
   void graphStructuredStack(int **adjMat, int s, int bNode) {
      bool stackFound = false;
      for (int sVertex = 1; sVertex <= noOfNodes; sVertex++) {
         for (int dVertex = 1; dVertex <= noOfNodes; dVertex++) {
            this->adjMat[sVertex][dVertex] = adjMat[sVertex][dVertex];
         }
      }
      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();
      }
      list<stack<int> >::iterator iterator;
      iterator = stackList.begin();
      while (iterator != stackList.end()) {
         stack <int> stack = *iterator;
         iterator++;
         while (!stack.empty()) {
            cout<<stack.top()<<"\t";
            stack.pop();
         }
         cout<<endl;
      }
   }
};
int main() {
   int noofnodes;
   cout<<"Enter number of nodes: ";
   cin>>noofnodes;
   GraphStructuredStack gss(noofnodes);
   int source, bottom;
   int **adjMatrix;
   adjMatrix = new int* [noofnodes + 1];
   for (int i = 0; i < noofnodes + 1; i++)
      adjMatrix[i] = new int [noofnodes + 1];
   cout<<"Enter the graph matrix: "<<endl;
   for (int sVertex = 1; sVertex <= noofnodes; sVertex++) {
      for (int dVertex = 1; dVertex <= noofnodes; dVertex++) {
         cin>>adjMatrix[sVertex][dVertex];
      }
   }
   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:
31

このように、ノード3を始点としノード1をボトムノードとした場合、「3 → 1」という経路がスタックとして検出されています。グラフの形状によっては、複数の異なる経路（複数のスタック）が一度に出力されることもあります。