Topological sort of graph

Given a directed graph G (V,E), list all vertices such that for all edges (v,w), v is listed before w. This problem is called as topological sort on graph.

Simple example we can take is that of courses. Let’s say university provides four different courses, A, B, C and D. For taking B, A is prerequisite. Similarly for taking C, A and B are prerequisites. For D, C and B are prerequisite. If created a node for each course and have a directed edge from prerequisite course to other courses, we will get a graph to work with.

If somebody asks us to figure out in which order he/she must take these course, we just do the topological sorting of the graph, it will give us answer. Topological sort order will be A, B, C ,D

Topological sort algorithm

First we need to figure where to start. What do we understand from above example?
Yes, we should take course first which has no prerequisites. If a course has no prerequisites, then there will be no incoming edges to that course. In graph terminology, node would have zero in-degree.

OK, we got the first node. Now how to proceed. Lets go back to our example again. If we have taken a course, what we can do is remove edges from that course to all other courses for which it was prerequisite. Why? Because if we have taken this course we are eligible to take all courses which have this course as prerequisite. Correction : If this course was only prerequisite. So when we visit a node, what we do is we decrease the in-degree of all adjacent nodes.

Now again search for course, which has no prerequisite and process as above. In graph terminology, search for the node in update graph, which has zero in-degree and repeat above steps till we have no such node which has zero in-degree. If there are still some nodes which are not visited, it will be in case of cycles in graph,  topological sorting is not possible.

Let’s take an example and work it out.

Topological sort on graphs : Implementation

#include<stdio.h>
#include<stdlib.h>

#define NUM_NODE 7
#define true 1
#define false 0

#define INFINITE 1000

typedef struct node{
int value;
int wt;
struct node *next;
}Node;

Node *graph[NUM_NODE + 1];
int visited[NUM_NODE + 1];

int findNextNode(int indegree[]){
for( int i=0; i<= NUM_NODE; i++){
if(indegree[i] == 0 && visited[i] == 0){
return i;
}
}
return -1;
}
void topologicalSort(Node * graph[]){

int indegree[NUM_NODE+1];
int i;

Node * current = NULL;
Node * next = NULL;
for(i=1; i<=NUM_NODE; i++){
indegree[i] =0;
}
/* Find indegree of each node. go through all edges.
complexity : O(E) */

for(i=1; i<=NUM_NODE; i++){
current = graph[i];
if(current){
next = current->next;
while(next){
indegree[next->value]++;
next = next->next;
}
}
}

/* We will traverse each node */
for(i=1; i<=NUM_NODE; i++){
/* find a node with zero indegree */
int node  = findNextNode(indegree);
/* If there is no node with zero indegree,
topological sort not possible */
if(node != -1){
printf("%d ", node);
visited[node] = 1;
/* decrease in degree of each node adjacent
to node wih zero indegree */
current = graph[node];
if(current){
next = current->next;
while(next){
indegree[next->value]--;
next = next->next;
}
}
}
else{
printf("\n Topological sort no possible");
}
}
return ;
}

Node * createNode(int j, int wt){

Node * newNode = (Node *)malloc(sizeof(Node));
if(newNode){
newNode->value = j;
newNode->next = NULL;
newNode->wt = wt;
}
else{
printf("\n Node cannot be allocated");
}
return newNode;
}

void addEdge(int i, int j, int wt){

Node * currentNode = graph[i];
if(!currentNode){
graph[i] = createNode(j, wt);
}
else{
while(currentNode->next){
currentNode = currentNode->next;
}
currentNode->next = createNode(j, wt);
}
}

int main(){

for(int i=1; i<=NUM_NODE; i++){
graph[i] = createNode(i,0);
}

topologicalSort(graph);

return 0;
}

Complexity of topological sort algorithm is  O(V2 +E). For each vertex we find vertex with zero in-degree, hence the quadratic time.
Let’s think of something which can make this update and search less complex. Whenever we update in-degree of all adjacent node, we can store all vertices for which in-degree becomes zero in a queue. So, we don’t have to separately search for nodes with zero in-degree, we can take front of the queue.

Optimized implementation of topological sort

#include<stdio.h>
#include<stdlib.h>

#define NUM_NODE 7
#define true 1
#define false 0

typedef struct node{
int value;
int wt;
struct node *next;
}Node;

Node *graph[NUM_NODE + 1];
int visited[NUM_NODE + 1];

typedef struct Queue{
Node *front;
Node *rear;
}Queue;

int isEmpty(Queue *q){
if(!(q->front || q->rear) ) return true;

return false;
}

void enqueue(Queue *q, int value){

Node * newNode = (Node *)malloc(sizeof(Node));
newNode->value = value;

if(isEmpty(q)){
q->front = newNode;
q->rear  = newNode;
}
else{
if(q->rear){
q->rear->next = newNode;
q->rear 	  = newNode;
}
else{
printf("\n Error ");
}
}
}

int dequeue(Queue *q){
if(!isEmpty(q)){
int data = q->front->value;
Node * currentFront = q->front;
if(q->front == q->rear){
q->rear = NULL;
q->front = NULL;
}
else{
q->front = currentFront->next;
}
free(currentFront);
return data;
}
}
void initializeQueue(Queue **q){
*q = (Queue *)malloc(sizeof(Queue));
(*q)->front = NULL;
(*q)->rear = NULL;
}

void topologicalSort(Node * graph[]){

int indegree[NUM_NODE+1];
int i;

Queue *q = NULL;

initializeQueue(&q);

Node * current = NULL;
Node * next = NULL;
for(i=1; i<=NUM_NODE; i++){
indegree[i] =0;
}
/* Find indegree of each node. go through all edges.
complexity : O(E) */
for(i=1; i<=NUM_NODE; i++){
current = graph[i];
if(current){
next = current->next;
while(next){
indegree[next->value]++;
next = next->next;
}
}
}

for(i=1; i<=NUM_NODE; i++){
if(indegree[i] == 0){
enqueue(q, i);
indegree[i]--;
break;
}
}

while(!isEmpty(q)){
int node  = dequeue(q);
printf("%d ", node);
/* decrease in degree of each node adjacent to node wih zero indegree */
current = graph[node];
if(current){
next = current->next;
while(next){
indegree[next->value]--;
if(indegree[next->value] == 0){
/* If indegree of any node becomes zero, enqueue it in queue. */
enqueue(q,next->value);
indegree[next->value]--;
}
next = next->next;
}
}
}

for(i=1; i<=NUM_NODE; i++){
if(indegree[i] > 0){
printf("\n Topological sort not possible");
}
}
return;
}

Node * createNode(int j, int wt){

Node * newNode = (Node *)malloc(sizeof(Node));
if(newNode){
newNode->value = j;
newNode->next = NULL;
newNode->wt = wt;
}
else{
printf("\n Node cannot be allocated");
}
return newNode;
}

void addEdge(int i, int j, int wt){

Node * currentNode = graph[i];
if(!currentNode){
graph[i] = createNode(j, wt);
}
else{
while(currentNode->next){
currentNode = currentNode->next;
}
currentNode->next = createNode(j, wt);
}
}

int main(){

for(int i=1; i<=NUM_NODE; i++){
graph[i] = createNode(i,0);
}