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+" ");
        }
    }
}