import java.util.*;
public class COSC336Assignment7 {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		ArrayList<ArrayList<Integer>> graph = new ArrayList<ArrayList<Integer>>();
		// number of vertices
		int v = 7;
		// construction of the graph
		graph.get(0).add(1);
		graph.get(0).add(2);
		graph.get(0).add(3);
		graph.get(0).add(4);
		graph.get(0).add(5);
		graph.get(1).add(6);
		graph.get(2).add(6);
		graph.get(3).add(6);
		graph.get(4).add(6);
		graph.get(5).add(6);
		int starting = 0; //starting node
		int destination = 6; //ending node
		System.out.print("All paths from starting node ");
		System.out.print(starting);
		System.out.print(" to destination ");
		System.out.print(destination);
		System.out.print(" are:");
		System.out.println();
		// function for finding the paths
		getPaths(graph, starting, destination, v);
		System.out.print("\nShortest paths can be seen from the lengths.\n");


	}
	public static void getPaths(ArrayList<ArrayList<Integer>> g, int starting, int destination, int v) {
		Queue<ArrayList<Integer>> q = null;
		int length;
		ArrayList<Integer> path = null;
		path.add(starting);
		q.add(path);
		while(!q.isEmpty()) {
			path = q.peek();
			q.remove();
			int last = path.get(path.size()-1);
			length = path.size();
			if(last == destination) {
				System.out.println("Length of path " + length);
				displayPath(path);
			}
			for(int i = 0; i < g.get(last).size(); i++) {
				if(notVisited(g.get(last).get(i), path) != 0) {
					ArrayList<Integer> nPath = path;
					nPath.add(g.get(last).get(i));
					q.add(nPath);
				}
			}
		}
	}
	public static void displayPath(ArrayList<Integer> path) {
		int size = path.size();
		for(int i = 0; i < size; i++)
			System.out.println(path.get(i) + " ");
	}
	public static int notVisited(int x, ArrayList<Integer> path) {
		int size = path.size();
		for(int i = 0; i < size; i++) {
			if(path.get(i) == x)
				return 0;
		}
		return 1;
	}

}