package practice;

import java.io.File;
import java.io.FileNotFoundException;
import java.util.*;

class GraphTraversal{
 private int V;                      // No. of vertices
 private LinkedList<Integer> adj[];  //To store a adjacency list

/*
* Initialize a graph
*/
 GraphTraversal(int v) {
	 V = v;
	 adj = new LinkedList[V+1];

	 for (int i = 0; i <= V; i++) {
		 adj[i] = new LinkedList<Integer>();
	 }
 }

/*
* Add an edge into a graph
*/
void addEdge(int v, int w) {
	adj[v].add(w);
 }

/*
* This method is to calculate and show the shortest path from a given vertex
*/
 void shortestPath(int start) {
	 //  Create a queue for visited nodes
	 boolean visited[] = new boolean[V];

	 //  Create a queue for BFS
     LinkedList<Integer> queue = new LinkedList<Integer>();

     //  Mark the current node as visited and push it
     visited[start]=true;
     queue.push(start);

     int[] height = new int[V];

     //  Repeat until the BFS queue is empty (meaning we traversed all possible paths)
     while (queue.size() != 0) {
    	 int currentNode;
         // Dequeue a vertex from queue and print it
         currentNode = queue.poll();
         System.out.println("Distance from vertex " + start + " to vertex " + currentNode + " is: " + height[currentNode]);
         // Get all neighbors of the dequeued node
         // If a neighbor has not been visited, then mark it visited and push to the BFS queue
         Iterator<Integer> i = adj[currentNode].listIterator();
         while (i.hasNext())
         {
             int n = i.next();
             if (!visited[n])
             {
                 visited[n] = true;
                 queue.add(n);
             }
             height[n]++;
         }
     }
 }
}


/*
* This class is to read the inputQ2.txt text file.
* This class also calls the GraphTraversal class
* to find the distance from a vertex to all other
* vertices
*/
public class Test{

 public static void main(String args[]) {
	 File file = new File("C:\\Users\\iheal\\eclipse-workspace\\COSC222\\src\\lab8\\inputQ2.txt");  //File path
	 Scanner scan;
	 try {
		 scan = new Scanner(file);

	int nodes = scan.nextInt();
    int edges = scan.nextInt();

    GraphTraversal graph = new GraphTraversal(nodes);        //Initialize a graph

    for (int i = 0; i < edges; i++)
    graph.addEdge(scan.nextInt(), scan.nextInt());           //For loop to read the text file

    int startNode = scan.nextInt();
    graph.shortestPath(startNode);                            //To show the shortest path
    scan.close();

  } catch (FileNotFoundException e) {
	  e.printStackTrace();
	  }
	 }
}