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.

```
/*
```

 * C++ Program to Implement Graph Structured Stack

```
 */
```
```
#include <iostream>
```
```
#include <cstdlib>
```
```
#include <stack>
```
```
#include <list>
```
```
using namespace std;
```
```
 
```
```
/*
```
```
 * Class Graph Structured Stack
```
```
 */
```
```
class GraphStructuredStack
```
```
{
```
```
    private: 
```
```
        list< stack<int> > stackList;
```
```
        stack<int> mystack;
```
```
        int numberOfNodes;
```
```
        int **adjacencyMatrix;
```
```
        int *parent;
```
```
    public:
```

        GraphStructuredStack(int numberOfNodes)

```
        {
```

            this->numberOfNodes = numberOfNodes;

            adjacencyMatrix = new int* [numberOfNodes + 1];

            this->parent = new int [numberOfNodes + 1];

            for (int i = 0; i < numberOfNodes + 1; i++)

                adjacencyMatrix[i] = new int [numberOfNodes + 1];

```
        }
```
```
        /*
```

         * Implement Graph Structured Stack

```
         */        
```

        void graphStructuredStack(int **adjacencyMatrix, int source,int bottomNode)

```
        {
```
```
            bool stackFound = false;
```

            for (int sourceVertex = 1; sourceVertex <= numberOfNodes; sourceVertex++)

```
            {
```

                for (int destinationVertex = 1; destinationVertex <= numberOfNodes; destinationVertex++)

```
                {
```

                    this->adjacencyMatrix[sourceVertex][destinationVertex]

                          = adjacencyMatrix[sourceVertex][destinationVertex];

```
                }
```
```
            }
```
```
 
```
```
            mystack.push(source);
```
```
            int element, destination;
```
```
            while (!mystack.empty())
```
```
            {
```

                element = mystack.top();

```
                destination = 1;
```

                while (destination <= numberOfNodes)

```
                {
```

                    if (this->adjacencyMatrix[element][destination] == 1)

```
                    {
```

                        mystack.push(destination);

                        parent[destination] = element;

                        this->adjacencyMatrix[element][destination] = 0;

                        if (destination == bottomNode)

```
                        {
```

                            stackFound = true;

```
                            break;
```
```
                        }
```

                        element = destination;

                        destination = 1;

```
                        continue;
```
```
                    }
```
```
                    destination++;
```
```
                }
```
```
                if (stackFound)
```
```
                {
```
```
                    stack<int> istack;
```

                    for (int node = bottomNode; node != source; node = parent[node])

```
                    {
```

                        istack.push(node);

```
                    }
```

                    istack.push(source);

                    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;
```
```
            }
```
```
        }
```
```
};
```
```
/*
```
```
 * Main
```
```
 */
```
```
int main()
```
```
{
```
```
    int numberofnodes;
```
```
    cout<<"Enter number of nodes: ";
```
```
    cin>>numberofnodes;
```

    GraphStructuredStack gss(numberofnodes);

```
    int source, bottom;
```
```
    int **adjacencyMatrix;
```

    adjacencyMatrix = new int* [numberofnodes + 1];

    for (int i = 0; i < numberofnodes + 1; i++)

        adjacencyMatrix[i] = new int [numberofnodes + 1];

    cout<<"Enter the graph matrix: "<<endl;

    for (int sourceVertex = 1; sourceVertex <= numberofnodes; sourceVertex++)

```
    {
```

        for (int destinationVertex = 1; destinationVertex <= numberofnodes; destinationVertex++)

```
        {
```

            cin>>adjacencyMatrix[sourceVertex][destinationVertex];

```
        }
```
```
    }
```
```
    cout<<"Enter the source node: ";
```
```
    cin>>source;
```
```
    cout<<"Enter the bottom node: ";
```
```
    cin>>bottom;
```
```
    cout<<"The stacks are: "<<endl;
```

    gss.graphStructuredStack(adjacencyMatrix, source, bottom);

```
    return 0;
```
```
}
```

$ 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.

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

« Prev - C++ Program to Implement Vector

» Next - C++ Program to Check Cycle in a Graph using Graph Traversal

Related Posts:

Recommended Articles: