A topological sort of a directed acyclic graph (in short DAG) is a linear ordering of vertices such that if DAG contains a directed edge (u,v), then u appears always before v in the ordering. For example in below directed acyclic graph one of possible topological order is c a d b. Topological sort is not possible if a directed graph contains a cycle. if a directed graph contains a cycle then it is impossible to preserve the property of topological ordering.

Topological Sorting

Some real word applications which uses topological sorting.

Ubuntu Linux/OS package manager ( synaptic, apt-get).

It uses topological sorting to obtain the best possible order in which a set of Debian packages can be installed/removed.

 Maven Build system

Maven is a popular open source build tool for enterprise Java project.

Note: Topological sorting is used to solve classing scheduling and maximum flow problem in computer science.

Now let us an algorithm known as Kahn’s algorithm for topological sorting.

Kahn’s algorithm

  1. Determine the in-degree of each vertex of directed acyclic graph.
  2. Find the zero in-degree node and print it. After printing remove the vertex and all its outgoing edges from the graph. if there is no zero in-degree vertex in graph,the graph is cyclic and no topological sort possible.
  3. Continue to step 1 (recalculate the in-degree of remaining vertices of the DAG) and step 2, until the graph becomes empty.

Let us see below example graph and apply above algorithm on it. The below figure shows adjacency matrix and adjacency list representation of graph, on its left side.

Topological SortingIf we represent the graph nodes a as 0 , b as 1, c as 2 and d as 3 . The one of topological order  would be 0 2 3 1. Let us see the below implementation for topological order of above graph. To remove the 0 in-degree node (u) from the graph, we decrease the in-degree of each connected vertex from (u) by 1.

#include<iostream>
#include<list>
#include<queue>
using namespace std;

// number of vertex
#define V 4

// Adjacency matrix of graph
//a b c d
int g[V][V] = { {0, 1, 0, 1}, //a
{0, 0, 0, 0}, //b
{0, 1, 0, 1}, //c
{0, 1, 0, 0}}; //d

void calculateInDegree (int indegree[V]);

int main ()
{

queue < int >Q;
list < int >order;
// for storing in degree of each vertex
int indegree[V];
// calculate indegree of each vertex
calculateInDegree (indegree);

// enqueue 0 indegree vertex
int i = 0;
for (i = 0; i < V; i++)
{
if (indegree[i] == 0)
Q.push (i);
}

// check Q is empty or not empty
// if it is empty , it means there is
// no zero in-degree vertex in graph
// hence graph is cyclic, no topological sort possible
if( Q.empty() ){
cout<<"Graph contains dircted cycle,no topological sort\n";
}
while (!Q.empty ())
{
int u = Q.front ();
order.push_back (u);
Q.pop ();
int v = -1;
for (v = 0; v < V; v++)
{
if (g[u][v])
{
// if there is incomming edge from u to v
// dcrease the indegree of v
indegree[v]--;
if (indegree[v] == 0)
Q.push (v);
}
}
}
// print order

list < int >::iterator li;
for (li = order.begin (); li != order.end (); li++)
cout << *li << " ";
cout << endl;
return 0;
}

void calculateInDegree (int indegree[V])
{
// init in degree of each vertex 0
int i = 0;
int j = 0;
for (i = 0; i < V; i++)
indegree[i] = 0;

/***************************************/
/** calculate in degree of each vertex */
/***************************************/
for (i = 0; i < V; i++)
{
for (j = 0; j < V; j++)
{
// if there is edge from i to j
if (g[i][j])
{
indegree[j]++;
}
}
}
}

Ref: http://cs.anu.edu.au/~Alistair.Rendell/Teaching/apac_comp3600/module4/basic_graph_algorithms.xhtml




Related Contents to follow