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.

```
#include<stdio.h>
```
```
#include<math.h>
```
```
int main() {
```

    int i, j, k, n, a[10][10], indeg[10], flag[10], count = 0;

    printf("Enter the no of vertices:");

```
    scanf("%d", &n);
```

    printf("Enter the incidence matrix:");

```
    for (i = 0; i < n; i++)
```
```
        for (j = 0; j < n; j++)
```
```
            scanf("%d", &a[i][j]);
```
```
 
```
```
    for (i = 0; i < n; i++) {
```
```
        indeg[i] = 0;
```
```
        flag[i] = 0;
```
```
    }
```
```
    for (i = 0; i < n; i++)
```
```
        for (j = 0; j < n; j++)
```

            indeg[i] = indeg[i] + a[j][i];

    printf("The topological order is:");

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

            if ((indeg[k] == 0) && (flag[k] == 0)) {

```
                printf("%d ", (k + 1));
```
```
                flag[k] = 1;
```
```
            }
```
```
            for (i = 0; i < n; i++) {
```
```
                if (a[i][k] == 1)
```
```
                    indeg[k]--;
```
```
            }
```
```
        }
```
```
        count++;
```
```
    }
```
```
    return 0;
```
```
}
```

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.

If you find any mistake above, kindly email to [email protected]

« Prev - C Program to Generate All Possible Subsets using Binary Counting Method

» Next - C Program to Find K Closest Median Elements

Related Posts:

Recommended Articles: