I am trying to implement Knuth's topological sorting algorithm in C. When I search for online resources, all I see are implementations of Kahn's Algorithm and this kind of confuses me. Are they both the same? Or are they different? Here is my implementation based on what I have researched.
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define MAX 1000
void create_graph();
void add(int vertex);
int del();
int isEmpty();
int find_indegree_of_vertex(int vertex);
int total_vertices;
int adjacent_matrix[MAX][MAX];
int queue[MAX];
int front = -1;
int rear = -1;
int main()
{
int i, vertex, count, topological_sort[MAX], indegree[MAX];
create_graph();
for(i = 1; i <= total_vertices; i++)
{
indegree[i] = find_indegree_of_vertex(i);
if(indegree[i] == 0)
{
add(i);
}
}
count = 0;
while(!isEmpty() && count < total_vertices)
{
vertex = del();
topological_sort[++count] = vertex;
for(i = 1; i <= total_vertices; i++)
{
if(adjacent_matrix[vertex][i] == 1)
{
adjacent_matrix[vertex][i] = 0;
indegree[i] = indegree[i] - 1;
if(indegree[i] == 0)
{
add(i);
}
}
}
}
for(i = 1; i <= count; i++)
{
printf("%d ", topological_sort[i]);
}
printf("\n");
return 0;
}
void add(int vertex)
{
if(!(rear == MAX - 1))
{
if(front == -1)
{
front = 0;
}
rear = rear + 1;
queue[rear] = vertex ;
}
}
int isEmpty()
{
if(front == -1 || front > rear)
{
return 1;
}
else
{
return 0;
}
}
int del()
{
int element;
if(front == -1 || front > rear)
{
exit(1);
}
else
{
element = queue[front];
front = front + 1;
return element;
}
}
int find_indegree_of_vertex(int vertex)
{
int count, total_indegree = 0;
for(count = 0; count < total_vertices; count++)
{
if(adjacent_matrix[count][vertex] == 1)
{
total_indegree++;
}
}
return total_indegree;
}
void create_graph()
{
int count, maximum_edges, origin_vertex, destination_vertex;
char v1[1000], v2[1000];
char temp[10];
scanf("%d\n", &total_vertices);
maximum_edges = total_vertices * (total_vertices - 1);
for(count = 1; count <= maximum_edges; count++)
{
fgets(temp, sizeof(temp), stdin);;
char * splitter;
splitter = strtok(temp, " ");
strncpy(v1, splitter, strlen(splitter)+1);
splitter = strtok(NULL, " ");
strncpy(v2, splitter, strlen(splitter)+1);
origin_vertex = atoi(v1);
destination_vertex = atoi(v2);
if((origin_vertex == 0) && (destination_vertex == 0))
{
break;
}
else
adjacent_matrix[origin_vertex][destination_vertex] = 1;
}
}
Sample Input:
15 (Number of vertices)
1 2
2 3
4 5
5 1
5 12
5 6
7 6
8 9
10 11
12 10
12 13
13 14
13 9
14 15
0 0 (End of entries, not a part of the adjacency matrix.)
Output:
4 7 8 5 1 6 12 2 10 13 3 11 9 14 15
Expected Output (From our class activity):
4 7 8 5 6 12 1 13 10 2 9 14 11 3 15 (Notice the difference!)
My code accepts inputs of pairs and returns the order after application of toposort. For simplicity, I am assuming the entry is a valid graph for toposort.
It can be implemented like this:
#include <stdio.h>
#define MAX 200
int n,adj[MAX][MAX];
int front = -1,rear = -1,queue[MAX];
void main() {
int i,j = 0,k;
int topsort[MAX],indeg[MAX];
create_graph();
print("The adjacency matrix is:\n");
display();
for (i=1;i<+n;i++) {
indeg[i]=indegree(i);
if(indeg[i]==0)
insert_queue(i);
}
while(front<=rear) {
k=delete_queue();
topsort[j++]=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);
}
}
}
printf("Nodes after topological sorting are:\n");
for (i=0;i<=n;i++)
{
printf("%d",topsort[i]);
printf("\n");
}
}
create_graph()
{
int i,max_edges,origin,destin;
printf("\n Enter number of vertices:");
scanf("%d",&n);
max_edges = n * (n - 1);
for (i = 1; i <= max_edges; i++)
{
printf("\n Enter edge %d (00 to quit):",i);
scanf("%d%d",&origin,&destin);
if ((origin == 0) && (destin == 0)) {
printf("Invalid edge!!\n");
i–;
}
else
adj[origin][destin] = 1;
}
return;
}
display()
{
int i,j;
for (i = 0;i <= n;i++) {
for (j = 1;jrear) {
printf("Queue Underflow");
return;
} else {
del_item = queue[front];
front = front + 1;
return del_item;
}
}
}
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;
}