Transitive closure of a graph - GeeksforGeeks

Transitive closure of a graph - GeeksforGeeks
Given a directed graph, find out if a vertex j is reachable from another vertex i for all vertex pairs (i, j) in the given graph. Here reachable mean that there is a path from vertex i to j. The reach-ability matrix is called transitive closure of a graph.

Transitive closure of above graphs is 
     1 1 1 1 
     1 1 1 1 
     1 1 1 1 
     0 0 0 1 

Floyd Warshall Algorithm can be used, we can calculate the distance matrix dist[V][V] using Floyd Warshall, if dist[i][j] is infinite, then j is not reachable from i, otherwise j is reachable and value of dist[i][j] will be less than V.
Instead of directly using Floyd Warshall, we can optimize it in terms of space and time, for this particular problem. Following are the optimizations:

1) Instead of integer resultant matrix (dist[V][V] in floyd warshall), we can create a boolean reach-ability matrix reach[V][V] (we save space). The value reach[i][j] will be 1 if j is reachable from i, otherwise 0.

2) Instead of using arithmetic operations, we can use logical operations. For arithmetic operation ‘+’, logical and ‘&&’ is used, and for min, logical or ‘||’ is used. (We save time by a constant factor. Time complexity is same though)

    final static int V = 4; //Number of vertices in a graph

 

    // Prints transitive closure of graph[][] using Floyd

    // Warshall algorithm

    void transitiveClosure(int graph[][])

    {

        /* reach[][] will be the output matrix that will finally

           have the shortest  distances between every pair of

           vertices */

        int reach[][] = new int[V][V];

        int  i, j, k;

 

        /* Initialize the solution matrix same as input graph

           matrix. Or  we can say the initial values of shortest

           distances are based  on shortest paths considering

           no intermediate vertex. */

        for (i = 0; i < V; i++)

            for (j = 0; j < V; j++)

                reach[i][j] = graph[i][j];

 

        /* Add all vertices one by one to the set of intermediate

           vertices.

          ---> Before start of a iteration, we have reachability

               values for all  pairs of vertices such that the

               reachability values consider only the vertices in

               set {0, 1, 2, .. k-1} as intermediate vertices.

          ----> After the end of a iteration, vertex no. k is

                added to the set of intermediate vertices and the

                set becomes {0, 1, 2, .. k} */

        for (k = 0; k < V; k++)

        {

            // Pick all vertices as source one by one

            for (i = 0; i < V; i++)

            {

                // Pick all vertices as destination for the

                // above picked source

                for (j = 0; j < V; j++)

                {

                    // If vertex k is on a path from i to j,

                    // then make sure that the value of reach[i][j] is 1

                    reach[i][j] = (reach[i][j]!=0) ||

                             ((reach[i][k]!=0) && (reach[k][j]!=0))?1:0;

                }

            }

        }

 

        // Print the shortest distance matrix

        printSolution(reach);

    }

Read full article from Transitive closure of a graph - GeeksforGeeks