[FIXED] How do you implement Knuth's Toposort in C?

Issue

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.

Solution

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;
}

Answered By - Vikhyat

Answer Checked By - Mildred Charles (PHPFixing Admin)