# Topological Sorting

*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.
*

*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 *

*Kahn’s algorithm*

*Determine the in-degree of each vertex of directed acyclic graph.**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.*

*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.*

*If 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.*

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 92 |
#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

## Leave a Reply