C Program to Create a Random Linear Extension for a DAG

«
»
This is a C Program to find topological sorting of a graph. For example:a1 < a0, a1 < a2 < a3. The problem is to determine a list of order, in which if ai < aj then ai will come before aj in the final sorted list. For example, our list could be : a1, a0, a2, a3 or a1, a2, a0, a3 or a1, a2, a3, a0 Any partial ordered list can be sorted topological. For a graph, a topological sort of a directed graph refers to an ordering of the vertices, that for every edge u,v, u comes before v in the ordering. Here is source code of the C Program to Create a Random Linear Extension for a DAG. The C program is successfully compiled and run on a Linux system. The program output is also shown below.
  1. #include<stdio.h>
  2. #include<math.h>
  3. int main() {
  4.     int i, j, k, n, a[10][10], indeg[10], flag[10], count = 0;
  5.     printf("Enter the no of vertices:");
  6.     scanf("%d", &n);
  7.     printf("Enter the incidence matrix:");
  8.     for (i = 0; i < n; i++)
  9.         for (j = 0; j < n; j++)
  10.             scanf("%d", &a[i][j]);
  11.  
  12.     for (i = 0; i < n; i++) {
  13.         indeg[i] = 0;
  14.         flag[i] = 0;
  15.     }
  16.     for (i = 0; i < n; i++)
  17.         for (j = 0; j < n; j++)
  18.             indeg[i] = indeg[i] + a[j][i];
  19.     printf("The topological order is:");
  20.     while (count < n) {
  21.         for (k = 0; k < n; k++) {
  22.             if ((indeg[k] == 0) && (flag[k] == 0)) {
  23.                 printf("%d ", (k + 1));
  24.                 flag[k] = 1;
  25.             }
  26.             for (i = 0; i < n; i++) {
  27.                 if (a[i][k] == 1)
  28.                     indeg[k]--;
  29.             }
  30.         }
  31.         count++;
  32.     }
  33.     return 0;
  34. }

Output:

$ gcc LinearExtensionOfDAG.c
$ ./a.out
 
Enter the no of vertices:6
Enter the incidence matrix:
0 1 0 0 0 0
0 0 1 1 0 0 
0 0 0 0 0 0
0 0 0 0 1 1
0 0 0 0 0 1
0 0 1 1 0 0
The topological order is:
1 2 3 4 5 6

Sanfoundry Global Education & Learning Series – 1000 C Programs.

Here’s the list of Best Books in C Programming, Data Structures and Algorithms.

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & technical discussions at Telegram SanfoundryClasses.