Topological Sort.

/*
     PRE-CONDITION
     =============
     Graph should be Acyclic and Directed (DAG).

     APPLICATIONS
     ============
•     Ordering of formula cell evaluation when recomputing formula values in spreadsheets,
•     Logic synthesis.
•      Determining the order of compilation tasks to perform in makefiles.
•     Data serialization
•     Resolving symbol dependencies in linkers. 
•     It is also used to decide in which order to load tables with foreign keys in databases.

     ALGORITHM
     =========
1.     Put all the vertices in unexplored set.
2.     While unexplored set is not empty, Repeat step 3 to 5
3.     Select a vertex from unexplored set and perform DFS taking this as source,
4.     Remove vertex in DFS path from unexplored set and put them in explored set.
5.     Print the last node in DFS exploration (sink node).
*/

public void printSinkNodeDFS(Vertex source, boolean visited[]) {
     //Move the vertex to explored set.
     visited[source.vertexId] = true;
     for(int i=0; i<source.edges.size(); i++) {
          
          //Get all the vertices reachable from current vertex and present in unexplored set.
          Vertex target = source.edges.get(i).Target;
          if(!visited[target.vertexId])
               printSinkNodeDFS(target, visited);
     }
     //When there are no more unexplored vertices reachable from current node.
     //Process the current node which is now the sink node.
     System.out.print("  " + source.vertexId);
}
     

public void topologicalSort() {
     System.out.println("nnTopological Sort");
     int i;
     
     //Initially each vertex is in unexplored set.
     boolean visited[] = new boolean[totalVertices];
     for(i=0; i<totalVertices; i++) 
          visited[i] = false;
     
     //Scan all vertices in unexplored set and perform DFS with first unscanned vertex as source.
     //Move vertices from unexplored to explored set.
     //Repeat until no vertex is present in unexplored set.
     for(i=0; i<totalVertices; i++) {
          if(!visited[i]) {
               printSinkNodeDFS(vertices[i],visited);
          }
     }
}