In this post, we will see about Topological Sorting in the graph.
Topological Sorting is ordering of vertices or nodes such if there is an edge between (u,v) then u should come before v in topological sorting. Topological sort is possible only for Directed Acyclic Graph(DAG). If there is a cycle in graph, then there won’t be any possibility for Topological Sort.
Table of Contents
Topological Sort example
Let’s understand with the help of an example.
You might have used maven as build tool. If you have multiple modules in the maven, maven build projects on the basis of dependencies.
Let’s say you have 4 maven modules.
- maven-model
- maven-business-logic
- mavan-util
- maven-ui
Now you need to build maven-model before maven-business-logic because maven-business-logic uses code from maven-model.
Similiarly, maven-model ,maven-business-logic and maven-util should be built before maven-ui as maven-ui depends on all three modules.
So, in this scenario, we can compute Topological sorting , so that maven can build them in the correct order.
Topological Sort Algorithm
Please note that there can be more than one solution for topological sort.
Let’s pick up node 30 here.
- Node 30 depends on node 20 and node 10.
- Node 10 depends on node 20 and node 40.
- Node 20 depends on node 40.
Hence node 10, node 20 and node 40 should come before node 30 in topological sorting.
This algorithm is a variant of Depth-first search. In depth first search, we first print the vertex and then go to its neighbours but in case of topological sort, we don’t print vertex immediately instead we push it to the Stack.
In topological sorting, we will have a temporary stack. We are not going to print the vertex immediately, we first recursively call topological sorting for all its neighbour vertices, then push it to a stack. We will print stack once we are done with recursive topolgical sorting.
Why it works?
It works because when you push any node to stack, you have already pushed its neighbours(and their neighbours and so on),so node which does not have any dependency will be on the top of stack. In our case, we will have 40 on top of the stack.
Java program to implement topological sorting
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 |
package org.arpit.java2blog; import java.util.ArrayList; import java.util.List; import java.util.Stack; public class TopologicalSort { Stack<Node> stack; public TopologicalSort() { stack=new Stack<>(); } static class Node { int data; boolean visited; List<Node> neighbours; Node(int data) { this.data=data; this.neighbours=new ArrayList<>(); } public void addneighbours(Node neighbourNode) { this.neighbours.add(neighbourNode); } public List<Node> getNeighbours() { return neighbours; } public void setNeighbours(List<Node> neighbours) { this.neighbours = neighbours; } public String toString() { return ""+data; } } // Recursive toplogical Sort public void toplogicalSort(Node node) { List<Node> neighbours=node.getNeighbours(); for (int i = 0; i < neighbours.size(); i++) { Node n=neighbours.get(i); if(n!=null && !n.visited) { toplogicalSort(n); n.visited=true; } } stack.push(node); } public static void main(String arg[]) { TopologicalSort topological = new TopologicalSort(); Node node40 =new Node(40); Node node10 =new Node(10); Node node20 =new Node(20); Node node30 =new Node(30); Node node60 =new Node(60); Node node50 =new Node(50); Node node70 =new Node(70); node40.addneighbours(node10); node40.addneighbours(node20); node10.addneighbours(node30); node20.addneighbours(node10); node20.addneighbours(node30); node20.addneighbours(node60); node20.addneighbours(node50); node30.addneighbours(node60); node60.addneighbours(node70); node50.addneighbours(node70); System.out.println("Topological Sorting Order:"); topological.toplogicalSort(node40); // Print contents of stack Stack<Node> resultStack=topological.stack; while (resultStack.empty()==false) System.out.print(resultStack.pop() + " "); } } |
When you run above program, you will get below output:
40 20 50 10 30 60 70
Time Complexity
It is very much similar to Depth-first search with just an extra stack. So its time complexity is O(V+E)
.That’s all about Topological Sort in java.
