Warshall’s Algorithm to find Transitive Closure

What is the Transitive Closure of a Graph?

The transitive closure of a graph is a data structure that represents all the shortest paths between the nodes of the graph. More specifically, given a directed graph G = (V, E), the transitive closure is a new graph G' = (V, E'), where there is an edge (u, v) in E' if there is a path from u to v in G. In other words, the transitive closure of a graph is a compact representation of all the reachability information in the graph.

There are different methods to compute the transitive closure of a graph, including the Floyd-Warshall algorithm, the dynamic programming approach, and the matrix multiplication method. The choice of the method depends on the specific problem and the properties of the graph.

Real-World Examples of Transitive Closure

The concept of transitive closure can be applied to various real-world scenarios, such as:

Social Networks: In a social network like Facebook or LinkedIn, users are connected through friendships or professional connections. The transitive closure of the social network graph can be used to analyze the reachability between users and find the shortest path between them.

Web Crawling: Search engines like Google use web crawlers to index websites. The transitive closure of the web graph can be used to determine the reachability between different web pages and prioritize the crawling process.

Transportation Networks: In a transportation network, cities or stations are connected through roads, railways, or air routes. The transitive closure of the transportation network graph can be used to compute the shortest paths between cities or stations, which is essential for route planning and optimization.

Dependency Management: In software development, modules or packages often depend on other modules or packages. The transitive closure of the dependency graph can be used to determine the full set of dependencies for a given module or package, which is important for software building and distribution.

SOURCE CODE in C

/*This is a C Program to find Transitive Closure of a Digraph using Warshall’s Algorithm*/

#include<stdio.h>

#include<conio.h>

#include<math.h>

int max(int,int);

void warshal(int p[10][10],int n) {

    int i,j,k;

    for(k=1;k<=n;k++)

        for(i=1;i<=n;i++)

            for(j=1;j<=n;j++)

                p[i][j]=max(p[i][j],p[i][k]&&p[k][j]);

}

int max(int a,int b) {

    if(a>b)

        return(a);

    else

        return(b);

}

void main() {

    int p[10][10]={0},n,e,u,v,i,j;

    printf("****Transitive Closure of a Digraph using Warshall’s Algorithm*****\n\n");

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

    scanf("%d",&n);

    printf("Enter the number of edges:");

    scanf("%d",&e);

    for(i=1;i<=e;i++) {

        printf("Enter the end vertices of edge %d:",i);

        scanf("%d%d",&u,&v);

        p[u][v]=1;

    }

    printf("\n Adjacency Matrix of input data: \n");

    for(i=1;i<=n;i++) {

        for(j=1;j<=n;j++)

            printf("%d\t",p[i][j]);

        printf("\n");

    }

    

warshal(p,n);

    

    printf("\n Transitive closure: \n");

    for(i=1;i<=n;i++) {

        for(j=1;j<=n;j++)

            printf("%d\t",p[i][j]);

        printf("\n");

    }

}

 INPUT/ OUTPUT:

****Transitive Closure of a Digraph using WarshallÆs Algorithm*****

Enter the number of vertices:4

Enter the number of edges:4

Enter the end vertices of edge 1:1 2

Enter the end vertices of edge 2:2 4

Enter the end vertices of edge 3:4 1

Enter the end vertices of edge 4:4 3

 Adjacency Matrix of input data:

0       1       0       0

0       0       0       1

0       0       0       0

1       0       1       0

 Transitive closure:

1       1       1       1

1       1       1       1

0       0       0       0

1       1       1       1

--------------------------------

Process exited after 94.09 seconds with return value 4

Press any key to continue . . .