/*
 * Topology sort algorithm
 * textbook example 
*/

#include <stdio.h>

#define MAX 10

int adj[MAX][MAX];
int n = MAX;
int queue[MAX], front = -1, rear = -1;

void init();
void dag(int*);
void display();
void insert_queue(int);
int delete_queue(void);
int find_indegree(int);

int main(){
  int topsort[MAX], indeg[MAX];
  init();
  dag(&n);
  display();

  /*Find the in-degree of each node*/
  int i;
  for (i = 0; i < n; i++) {
    indeg[i] = find_indegree(i);
    if (indeg[i] == 0)
      insert_queue(i);
  }

  int j=0;
  int del_node;
  while (front <= rear) /*Continue loop until queue is empty */
  {
    del_node = delete_queue();
    topsort[j] = del_node; /*Add the deleted node to topsort*/
    j++;
    
    /*Delete the del_node edges */
    for (i = 0; i < n; i++) {
      if (adj[del_node][i] == 1) {
        adj[del_node][i] = 0;
        indeg[i] = indeg[i] - 1;
        if (indeg[i] == 0)
          insert_queue(i);
      }
    }
  }

  printf("The topological sorting can be given as:\n");
  for (i=0; i<j; i++) 
    printf("%d ", topsort[i]);

  return 0;
}

void dag(int* n) {
  adj[0][1] = 1;
  adj[0][2] = 1;
  adj[1][3] = 1;
  adj[1][4] = 1;
  adj[2][3] = 1;
  adj[2][4] = 1;
  *n = 5;
}

void init() {
  int i,j;
  for (i = 0; i < MAX; i++)
    for (j = 0; j < MAX; j++)
      adj[i][j] = 0;
}

void display() {
  int i, j;
  printf("   ");
  for (i = 0; i < n; i++)
    printf("%d ", i);
  printf("\n");
  for (i = 0; i < n; i++) {
    printf("%d ", i);
    for (j = 0; j < n; j++) {
      printf(" %d", adj[i][j]);
    }
    printf("\n");
  }
}

void insert_queue(int node) {
  if (rear == MAX)
    printf("\nOVERFLOW ");
  else {
    if (front == -1) /*If queue is initially empty */
      front = 0;
    queue[++rear] = node;
  }
}

int delete_queue() {
  int del_node;
  if (front == -1 || front > rear) {
    printf("\nUNDERFLOW %d %d", front, rear);
    return -1;
  } else {
    del_node = queue[front++];
    return del_node;
  }
}

int find_indegree(int node) {
  int i, in_deg = 0;
  for (i = 0; i < n; i++) {
    if (adj[i][node] == 1)
      in_deg++;
  }
  return in_deg;
}

/*
   0 1 2 3 4
0  0 1 1 0 0
1  0 0 0 1 1
2  0 0 0 1 1
3  0 0 0 0 0
4  0 0 0 0 0
The topological sorting can be given as:
0 1 2 3 4
 */