Java Program to Implement Graph Structured Stack

Code:

import java.util.ArrayList;
import java.util.Iterator;
import java.util.Scanner;
import java.util.Stack;

public class GraphStructuredStack
{
    private ArrayList> stackList;
    private Stack stack;
    private int numberOfNodes;
    private int adjacencyMatrix[][];
    private int[] parent;

    public GraphStructuredStack()
    {
        stackList = new ArrayList>();
        stack  = new Stack();
    }

    public void graphStructuredStack(int adjacencyMatrix[][],int source,int bottomNode)
    {
        boolean stackFound = false;
        this.numberOfNodes = adjacencyMatrix[source].length - 1;
        this.adjacencyMatrix = new int[numberOfNodes + 1][numberOfNodes +1];
        this.parent = new int[numberOfNodes+ 1];

        for (int sourceVertex = 1; sourceVertex <= numberOfNodes; sourceVertex++)
        {
            for (int destinationVertex = 1; destinationVertex <= numberOfNodes; destinationVertex++)
            {
                this.adjacencyMatrix[sourceVertex][destinationVertex] 
                      = adjacencyMatrix[sourceVertex][destinationVertex];
            }
        }
        stack.push(source);
        int element, destination;
        while (!stack.isEmpty())
        {
            element = stack.peek();
            destination = 1;
            while (destination <= numberOfNodes)
            {
                if (this.adjacencyMatrix[element][destination] == 1)
                {
                    stack.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 istack = new Stack();
                for (int node = bottomNode; node != source; node = parent[node])
                {
                    istack.push(node);
                }
                istack.push(source);
                stackList.add(istack);
                stackFound = false;
            }
            stack.pop();
        }

        Iterator> iterator = stackList.iterator();
        while (iterator.hasNext())
        {
            Stack stack = iterator.next();
            Iterator stckitr = stack.iterator();
            while (stckitr.hasNext())
            {
                System.out.print(stckitr.next() +"\t");
            }
            System.out.println();
        }
    }

    public static void main(String...arg)
    {
        int adjacencyMatrix[][];
        int numberofnodes;
        int source, bottom;

        Scanner scanner = new Scanner(System.in);
        System.out.println("enter the number of nodes");
        numberofnodes = scanner.nextInt();
        adjacencyMatrix = new int[numberofnodes + 1] [numberofnodes + 1];

        System.out.println("enter the graph matrix");
        for (int sourceVertex = 1; sourceVertex <= numberofnodes; sourceVertex++)
        {
            for (int destinationVertex = 1; destinationVertex <= numberofnodes; destinationVertex++)
            {
                adjacencyMatrix[sourceVertex][destinationVertex] = scanner.nextInt();
            }
        }

        System.out.println("enter the source node");
        source = scanner.nextInt();

        System.out.println("enter the bottom node");
        bottom = scanner.nextInt();

        System.out.println("the stacks are");
        GraphStructuredStack graphStructuredStack = new GraphStructuredStack();
        graphStructuredStack.graphStructuredStack(adjacencyMatrix, source, bottom);
        scanner.close();
    }
}


Output:

enter the 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
1 2 4 5 6
1 3 4 5 6


More Java Programs: