C++ Program to Implement Graph Structured Stack

«
»
This C++ Program demonstrates the implementation of Graph Structured Stack.

Here is source code of the C++ Program to demonstrate the implementation of Graph Structured Stack. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

  1. /*
  2.  * C++ Program to Implement Graph Structured Stack
  3.  */
  4. #include <iostream>
  5. #include <cstdlib>
  6. #include <stack>
  7. #include <list>
  8. using namespace std;
  9.  
  10. /*
  11.  * Class Graph Structured Stack
  12.  */
  13. class GraphStructuredStack
  14. {
  15.     private: 
  16.         list< stack<int> > stackList;
  17.         stack<int> mystack;
  18.         int numberOfNodes;
  19.         int **adjacencyMatrix;
  20.         int *parent;
  21.     public:
  22.         GraphStructuredStack(int numberOfNodes)
  23.         {
  24.             this->numberOfNodes = numberOfNodes;
  25.             adjacencyMatrix = new int* [numberOfNodes + 1];
  26.             this->parent = new int [numberOfNodes + 1];
  27.             for (int i = 0; i < numberOfNodes + 1; i++)
  28.                 adjacencyMatrix[i] = new int [numberOfNodes + 1];
  29.         }
  30.         /*
  31.          * Implement Graph Structured Stack
  32.          */        
  33.         void graphStructuredStack(int **adjacencyMatrix, int source,int bottomNode)
  34.         {
  35.             bool stackFound = false;
  36.             for (int sourceVertex = 1; sourceVertex <= numberOfNodes; sourceVertex++)
  37.             {
  38.                 for (int destinationVertex = 1; destinationVertex <= numberOfNodes; destinationVertex++)
  39.                 {
  40.                     this->adjacencyMatrix[sourceVertex][destinationVertex] 
  41.                           = adjacencyMatrix[sourceVertex][destinationVertex];
  42.                 }
  43.             }
  44.  
  45.             mystack.push(source);
  46.             int element, destination;
  47.             while (!mystack.empty())
  48.             {
  49.                 element = mystack.top();
  50.                 destination = 1;
  51.                 while (destination <= numberOfNodes)
  52.                 {
  53.                     if (this->adjacencyMatrix[element][destination] == 1)
  54.                     {
  55.                         mystack.push(destination);
  56.                         parent[destination] = element;
  57.                         this->adjacencyMatrix[element][destination] = 0;
  58.                         if (destination == bottomNode)
  59.                         {
  60.                             stackFound = true;
  61.                             break;
  62.                         }
  63.                         element = destination;
  64.                         destination = 1;
  65.                         continue;
  66.                     }
  67.                     destination++;
  68.                 }
  69.                 if (stackFound)
  70.                 {
  71.                     stack<int> istack;
  72.                     for (int node = bottomNode; node != source; node = parent[node])
  73.                     {
  74.                         istack.push(node);
  75.                     }
  76.                     istack.push(source);
  77.                     stackList.push_back(istack);
  78.                     stackFound = false;
  79.                 }
  80.                 mystack.pop();
  81.             }
  82.             list<stack<int> >::iterator iterator;
  83.             iterator = stackList.begin();
  84.             while (iterator != stackList.end())
  85.             {
  86.  
  87.                 stack <int> stack = *iterator;
  88.                 iterator++;
  89.                 while (!stack.empty())
  90.                 {
  91.                     cout<<stack.top()<<"\t";
  92.                     stack.pop();
  93.                 }
  94.                 cout<<endl;
  95.             }
  96.         }
  97. };
  98. /*
  99.  * Main
  100.  */
  101. int main()
  102. {
  103.     int numberofnodes;
  104.     cout<<"Enter number of nodes: ";
  105.     cin>>numberofnodes;
  106.     GraphStructuredStack gss(numberofnodes);
  107.     int source, bottom;
  108.     int **adjacencyMatrix;
  109.     adjacencyMatrix = new int* [numberofnodes + 1];
  110.     for (int i = 0; i < numberofnodes + 1; i++)
  111.         adjacencyMatrix[i] = new int [numberofnodes + 1];
  112.     cout<<"Enter the graph matrix: "<<endl;
  113.     for (int sourceVertex = 1; sourceVertex <= numberofnodes; sourceVertex++)
  114.     {
  115.         for (int destinationVertex = 1; destinationVertex <= numberofnodes; destinationVertex++)
  116.         {
  117.             cin>>adjacencyMatrix[sourceVertex][destinationVertex];
  118.         }
  119.     }
  120.     cout<<"Enter the source node: ";
  121.     cin>>source;
  122.     cout<<"Enter the bottom node: ";
  123.     cin>>bottom;
  124.     cout<<"The stacks are: "<<endl;
  125.     gss.graphStructuredStack(adjacencyMatrix, source, bottom);
  126.     return 0;
  127. }

advertisement
$ g++ graph_structured_stack.cpp
$ a.out
 
Enter number of nodes: 6
Enter the graph matrix:
0 0 0 0 0 0
1 0 0 0 0 0
1 0 0 0 0 0
0 1 1 0 0 0
0 0 0 1 0 0
0 0 0 0 1 0
Enter the source node: 6
Enter the bottom node: 1
The stacks are:
6       5       4       2       1
6       5       4       3       1
 
------------------
(program exited with code: 1)
Press return to continue

Sanfoundry Global Education & Learning Series – 1000 C++ Programs.

Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!
advertisement
advertisement
If you wish to look at all C++ Programming examples, go to C++ Programs.

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & technical discussions at Telegram SanfoundryClasses.