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.

advertisement
If you wish to look at all C++ Programming examples, go to C++ Programs.

advertisement
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He is Linux Kernel Developer & SAN Architect and is passionate about competency developments in these areas. He lives in Bangalore and delivers focused training sessions to IT professionals in Linux Kernel, Linux Debugging, Linux Device Drivers, Linux Networking, Linux Storage, Advanced C Programming, SAN Storage Technologies, SCSI Internals & Storage Protocols such as iSCSI & Fiber Channel. Stay connected with him @ LinkedIn