package DataStructures.Graphs;

import java.util.ArrayList;

import java.util.Map;

import java.util.LinkedHashMap;

import java.util.HashMap;

import java.util.Set;

import java.util.Queue;

import java.util.LinkedList;

/**

* An algorithm that sorts a graph in toplogical order.

*/

/**

* A class that represents the adjaceny list of a graph

*/

class AdjacencyList<E extends Comparable<E>>{

Map<E,ArrayList<E>> adj;

AdjacencyList(){

adj = new LinkedHashMap<E,ArrayList<E>>();

}

/**

* This function adds an Edge to the adjaceny list

* @param from , the vertex the edge is from

* @param to, the vertex the edge is going to

*/

void addEdge(E from, E to){

try{

adj.get(from).add(to);

}

catch(Exception E){

adj.put(from,new ArrayList<E>());

adj.get(from).add(to);

}

if(!adj.containsKey(to)){

adj.put(to, new ArrayList<E>());

}

}

/**

* @param v, A vertex in a graph

* @return returns an ArrayList of all the adjacents of vertex v

*/

ArrayList<E> getAdjacents(E v){

return adj.get(v);

}

/**

* @return returns a set of all vertices in the graph

*/

Set<E> getVertices(){

return adj.keySet();

}

/**

* Prints the adjacency list

*/

void printGraph(){

for(E vertex: adj.keySet()){

System.out.print(vertex+" : ");

for(E adjacent: adj.get(vertex)){

System.out.print(adjacent+" ");

}

System.out.println();

}

}

}

class TopologicalSort<E extends Comparable<E>>{

AdjacencyList<E> graph;

Map<E,Integer> inDegree;

TopologicalSort(AdjacencyList<E> graph){

this.graph = graph;

}

/**

* Calculates the in degree of all vertices

*/

void calculateInDegree(){

inDegree = new HashMap<>();

for(E vertex: graph.getVertices()){

if(!inDegree.containsKey(vertex)){

inDegree.put(vertex,0);

}

for(E adjacent: graph.getAdjacents(vertex)){

try{

inDegree.put(adjacent,inDegree.get(adjacent) + 1);

}

catch(Exception e){

inDegree.put(adjacent,1);

}

}

}

}

/**

* Returns an ArrayList with vertices arranged in topological order

*/

ArrayList<E> topSortOrder(){

calculateInDegree();

Queue<E> q = new LinkedList<E>();

for(E vertex: inDegree.keySet()){

if(inDegree.get(vertex) == 0){

q.add(vertex);

}

}

ArrayList<E> answer = new ArrayList<>();

while(!q.isEmpty()){

E current = q.poll();

answer.add(current);

for(E adjacent: graph.getAdjacents(current)){

inDegree.put(adjacent,inDegree.get(adjacent)-1);

if(inDegree.get(adjacent) == 0){

q.add(adjacent);

}

}

}

return answer;

}

}

/**

* A driver class that sorts a given graph in topological order.

*/

public class KahnsAlgorithm{

public static void main(String[] args){

//Graph definition and initialization

AdjacencyList<String> graph = new AdjacencyList<>();

graph.addEdge("a","b");

graph.addEdge("c","a");

graph.addEdge("a","d");

graph.addEdge("b","d");

graph.addEdge("c","u");

graph.addEdge("u","b");

TopologicalSort<String> topSort = new TopologicalSort<>(graph);

//Printing the order

for(String s: topSort.topSortOrder()){

System.out.print(s+" ");

}

}

}