How do you implement Knuth's Toposort in C?

Question

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.

Answer 1

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

Answer 2

If you read Knuth's TAOCP (The Art of Computer Programming) Volume 1, Section 2.2.3 in the 3rd Edn, you'll find Knuth's "Algorithm T (Topological sort)" and also the comment:

A topological sorting technique similar to Algorithm T (but without the important feature of the queue links) was first published by A. B. Kahn, CACM 5 (1962), 558-562.

This indicates that Knuth's Algorithm T is different from Kahn's algorithm.

Answer 3

I think the problem is that there are multiple versions of Knuth's algorithms for topological sorting. The first one published in 1968 was the same as the Kahn algorithm (published in 1962). An algorithm to generate all possible solutions for a topological sort was published in 1964 by Donald Knuth (it uses a deque D which acts as a counter array for the sort).

http://www.cs.iit.edu/~cs560/fall_2012/Research_Paper_Topological_sorting/Topological%20sorting.pdf

Answer 4

There is a C implementation of Knuth's topological sort algorithm from TAOCP at https://github.com/theartofcomputerprogramming/programs/blob/main/vol_1_fundamental_algorithms_chap_2_information_structures/sec_2.2.3_linked_allocation/algorithm_t_topological_sort.c

The C code is annotated with each step of Algorithm T (Topological sort) from section 2.2.3 Linked Allocation of TAOCP

Knuth's algorithm is remarkably fast and compact due to the queue links that differentiate it from Kahn's algorithm. The C code contains an explanation of how the queue works at the top of the file.

It's noteworthy Knuth introduces this algorithm very early in Volume 1 of TAOCP well before trees or graphs are covered in later volumes.

The program takes binary input and outputs binary data for compatibility with Program T (Topological sort) from section 2.2.3 Linked Allocation of The MMIX Supplement companion to TAOCP. It may be considered a port of the MMIX implementation and can be used to view the expected output from Knuth's algorithm.

There is sample binary data for testing in the data subdirectory along with text representations to examine - I've added the data from the example in the question to in.2.le.dat (source in.2.txt)

Binary data may be generated with this tool in the repo - https://github.com/theartofcomputerprogramming/programs/blob/main/tools/texttobinary.sh

I tested the program with gcc 11.2 and vc++ 2022 version 17.1

A caveat for building on Windows - use an external build directory because the path to the source in the repo is pretty long and breaks cmake path limits - cmake configure can fail with cryptic errors about No CMAKE_C_COMPILER could be found and No CMAKE_CXX_COMPILER could be found

Here's how to run the program on a little-endian system like x64

$ algorithm_t_topological_sort -h

usage: algorithm_t_topological_sort <in.dat >out.dat

Implements Algorithm T (Topological sort) from 2.2.3 Linked Allocation, The Art of Computer Programming Volume 1, Fundamental Algorithms by Donald Knuth
Input and output is binary compatible with Program T (Topological sort) from 2.2.3 Linked Allocation, The MMIX Supplement by Martin Ruckert

Reads sequence of pairs of binary uint32_t values on stdin
Each pair is a dependency relation between objects
First of each pair is predecessor, second is successor
First pair is special: first value is 0, second is objects count
Last pair is special: both values are 0
Output on stdout is binary uint32_t values in topologically sorted order

Examples:
algorithm_t_topological_sort <in.0.le.dat | od -An -td4 -w4 -v

$ cat in.2.le.dat | od -An -td4 -w4 -v | paste -d ' ' - - | tr -s ' ' | sed 's/ //'

0 15
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

The result is a different sorted order than those seen in the question and comments - note tsort on Linux also implements Knuth's algorithm

$ algorithm_t_topological_sort <in.2.le.dat | od -An -td4 -w4 -v | tr -s '\n' ' ' | sed 's/ //'

8 7 4 5 6 12 1 13 10 2 9 14 11 3 15 0