/* Program for topological sorting */
#include<stdio.h>
#define MAX 20
int n,adj[MAX][MAX];
int front=-1,rear=-1,queue[MAX];
main()
{
int i,j=0,k;
int topsort[MAX],indeg[MAX];
create_graph();
printf("The adjacency matrix is :\n");
display();
/*Find the indegree of each node*/
for(i=1;i<=n;i++)
{
indeg[i]=indegree(i);
if( indeg[i]==0 )
insert_queue(i);
}
while(front<=rear) /*Loop till queue is not empty */
{
k=delete_queue();
topsort[j++]=k; /*Add node k to topsort array*/
/*Delete all edges going fron node k */
for(i=1;i<=n;i++)
{
if( adj[k][i]==1 )
{
adj[k][i]=0;
indeg[i]=indeg[i]-1;
if(indeg[i]==0)
insert_queue(i);
}
}/*End of for*/
}/*End of while*/
printf("Nodes after topological sorting are :\n");
for(i=0;i<j;i++)
printf( "%d ",topsort[i] );
printf("\n");
}/*End of main()*/
create_graph()
{
int i,max_edges,origin,destin;
printf("Enter number of vertices : ");
scanf("%d",&n);
max_edges=n*(n-1);
for(i=1;i<=max_edges;i++)
{
printf("Enter edge %d(0 0 to quit): ",i);
scanf("%d %d",&origin,&destin);
if((origin==0) && (destin==0))
break;
if( origin > n || destin > n || origin<=0 || destin<=0)
{
printf("Invalid edge!\n");
i--;
}
else
adj[origin][destin]=1;
}/*End of for*/
}/*End of create_graph()*/
display()
{
int i,j;
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
printf("%3d",adj[i][j]);
printf("\n");
}
}/*End of display()*/
insert_queue(int node)
{
if (rear==MAX-1)
printf("Queue Overflow\n");
else
{
if (front==-1) /*If queue is initially empty */
front=0;
rear=rear+1;
queue[rear] = node ;
}
}/*End of insert_queue()*/
delete_queue()
{
int del_item;
if (front == -1 || front > rear)
{
printf("Queue Underflow\n");
return ;
}
else
{
del_item=queue[front];
front=front+1;
return del_item;
}
}/*End of delete_queue() */
int indegree(int node)
{
int i,in_deg=0;
for(i=1;i<=n;i++)
if( adj[i][node] == 1 )
in_deg++;
return in_deg;
}/*End of indegree() */