Topological sorting using source-removal algorithm result not showing

Question

I'm currently coding a topological sorting algorithm using source-removal algorithm.

I first identified a vertex with no incoming edges in remaining digraph and deleted it along with all the edges outgoing from it. And the order in which the vertices are deleted yields a solution to the topological sorting problem.

The input is number of vertices that I want to sort, and I used adjacency matrix to show the direction and existence of the edges.

The problem is that somewhere in the code makes an infinite loop and as a result my code does not show a result.

My input is

number of vertices: 4
Enter row 1 
0 1 1 0

Enter row 2
0 0 0 1

Enter row 3
0 0 0 1

Enter row 4
0 0 0 0

And I expected this output:

1 2 3 4

But what I got is an endless loop (result not showing at all)

I guess something's wrong here:

while(count<n-1){
        for(k=0;k<n;k++){

            if((indeg[k]==0 && flag[k] ==0))        // zero incoming edges && not sorted yet
            {
                printf("%d ", k+1);
                flag[k]=1;      //checked

                for(i=0;i<n;i++){
                    if(a[k][i]==1){  // if there is an outgoing edge
                        a[k][i]=0;     // delete the outgoing edge
                        indeg[k]--;   // decrease the indeg sing the outgoing edge is deleted
                    }
                }

                count++;
            }
        }
    }

... but can't find what's wrong with it. And I have no idea why even the first vertex does not get printed out.

Here's the full code in case:

# include <stdio.h>
# include <stdlib.h>


int main(void){

    int i, j;
    int k, n;
    int a[10][10];      // adjacency matrix

    int indeg[10] = {0};        // number of incoming edges
    int flag[10] = {0};         // checked or not

    int count=0;                // count value for sorting vertices


    printf("Enter the no of vertices: ");
    scanf("%d",&n);

    printf("Enter the adjacency matrix:\n");
    for(i=0;i<n;i++){
        printf("Enter row %d\n",i+1);
        for(j=0;j<n;j++)
            scanf("%d",&a[i][j]);       // enter the adjacency matrix
    }


    for(i=0;i<n;i++)
        for(j=0;j<n;j++)
            indeg[i]+=a[j][i];      // number of incoming edges updated



    printf("\nThe topological order is:");



    while(count<n-1){
        for(k=0;k<n;k++){

            if((indeg[k]==0) && (flag[k] ==0))      // zero incoming edges && not sorted yet
            {
                printf("%d ", k+1);
                flag[k]=1;      //checked

                for(i=0;i<n;i++){
                    if(a[k][i]==1){
                        a[k][i]=0;              // delete the sorted vertice's outgoing edges 
                        indeg[k]--;             // subtract indeg since the outgoind edge is deleted
                    }
                }

                count++;                        // update the iteration count
                break;                          // break the for loop and start a new one
            }
        }
    }

}

I used this page to code my algorithm (although the code there is also wrong in the while loop that I uploaded) https://www.thecrazyprogrammer.com/2017/05/topological-sort.html

Answer 1

I spot two bugs:

• indeg[k]--; should be indeg[i]--; because k is the current node (we already established that indeg[k]==0 just to get to this location in the code) and i is the neighbor who we're deleting the incoming edge for (outgoing from k).
• while(count<n-1) should be while(count<n) or we won't print the last node.

---

A few suggestions:

• A good way to debug a program like this is to print the data to inspect its values on each iteration. Printing indeg[k] reveals that the value drops below 0, which should make the problem clear.
• Temporarily hardcoding your input data saves the time of typing it in repeatedly, reducing errors and making the problem easily reproducible for others.
• Using clear variable names and consistent spacing throughout your code helps reduce bugs and makes it easier to track them down when they do arise.
• It's a good idea to separate algorithm logic from input logic to avoid side effects. Breaking the code into functions is a good way to do this. This eases debugging considerably and makes code extensible and reusable.
• This code is vulnerable to a buffer overflow attack because of the hardcoded array size. Dynamic memory allocation is a good solution, or at least adding a conditional to prevent the user from specifying n > 10.

Here's an initial re-write that only implements some of the above suggestions (compile with gcc topological_sort.c -Wall -std=c99):

#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main() {
    int n = 4;
    int adjacency_matrix[][4] = {
        {0, 1, 1, 0},   //   0-->1-->3
        {0, 0, 0, 1},   //   |       ^
        {0, 0, 0, 1},   //   v       |
        {0, 0, 0, 0}    //   2-------+
    };
    int indegrees[n];
    bool visited[n];
    memset(&indegrees, 0, sizeof(*indegrees) * n);
    memset(&visited, false, sizeof(*visited) * n);

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            indegrees[i] += adjacency_matrix[j][i];
        }
    }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (!indegrees[j] && !visited[j]) {
                visited[j] = true;
                printf("%d ", j + 1);

                for (int k = 0; k < n; k++) {
                    if (adjacency_matrix[j][k]) {
                        adjacency_matrix[j][k] = 0;
                        indegrees[k]--;
                    }
                }

                break;
            }
        }
    }

    return 0;
}