# Graph Topological Sorting - Build System Order Example

November 20, 2020

## Graph Topological Sorting

This is a well known problem in graph world. Topological sort is to put vertices in order and output a list of vertices in such an order that vertices are in order of dependencies. i.e. The vertices comes first is the independent one, then list the one which are dependent on those.

In above Directed Graph, following can be possible topological sort order:

``````A B C D E F G H
OR
A C B E G D F H
OR
B E G A D C F H``````

## Build System Example

The usage of this sort is in the Build system. A build system is where there are different projects or modules are to built. And, it is to decide which module to build first so that updated module can be integrated in the dependent project or module.

## Code

``````class Node {
//to represent a Vertex
public String name;
public List<Node> connectedNodes;
//...some other data
return this.connectedNodes;
}
}
class Graph {
private List<Node> nodes;
public List<Node> nodes() {
return this.nodes;
}

}

public Stack<Node> topological(Graph g) {
//assumming Graph has method nodes() which gives list of all nodes.
List<Node> nodes = g.nodes();

//Set to keep track of visited nodes
Set<Node> visited = new HashSet();

//For keeping nodes in order
Stack<Node> stack = new Stack();

for (Node node : nodes) {
helper(node, visited, stack);
}
}

private void helper(Node node, Set visited, Stack stack) {
if (visited.contains(node)) {
continue;
}
//mark node visited

//visit all attached nodes with this vertices
//Assumming there is a method adj() which gives connected nodes to a vertex
for (Node n : node.adj()) {
//recursively visit each node's connected vertices
helper(n, visited, stack);
}

//all connected vertices are exhausted.
//Lets add this to our order list
}

//main
Stack<Node> stack = topological(graph);
//print stack
``````

## Complexity

Its `O(n)`

## Similar Posts

### Rotate Array - Leet Code Solution

Problem Statement Given an array, rotate the array to the right by k steps…

System design interview is pretty common these days, specially if you are having…

### Reverse String - Leet Code Solution

Problem Statement Write a function that reverses a string. The input string is…

### Check whether number is palindrome or not - Leet Code Solution

Problem Statement Determine whether an integer is a palindrome. An integer is a…

### Counting Inversions Coding Problem

** Inversion There is an array(a) and two indexes i and j. Inversion is the…

### What FAANG companies expect in their interview from candidates

Its every software engineer’s dream to work with the big FAANG companies…

## Latest Posts

### Jenkins Pipeline with Jenkinsfile - How To Schedule Job on Cron and Not on Code Commit

Introduction In this post we will see following: How to schedule a job on cron…

### How to Git Clone Another Repository from Jenkin Pipeline in Jenkinsfile

Introduction There are some cases, where I need another git repository while…

### How to Fetch Multiple Credentials and Expose them in Environment using Jenkinsfile pipeline

Introduction In this post, we will see how to fetch multiple credentials and…

### Jenkins Pipeline - How to run Automation on Different Environment (Dev/Stage/Prod), with Credentials

Introduction I have an automation script, that I want to run on different…

### Jenkinsfile - How to Create UI Form Text fields, Drop-down and Run for Different Conditions

Introduction I had to write a CICD system for one of our project. I had to…

### Java Log4j Logger - Programmatically Initialize JSON logger with customized keys in json logs

Introduction Java log4j has many ways to initialize and append the desired…