Data Modelling & AI Data Structure & Algorithm

Transitive closure of a graph

31 July 2024

3

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 the transitive closure of a graph.

For example, consider below graph

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

The graph is given in the form of adjacency matrix say ‘graph[V][V]’ where graph[i][j] is 1 if there is an edge from vertex i to vertex j or i is equal to j, otherwise graph[i][j] is 0.
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 the 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:

Instead of an 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.

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

Below is the implementation of the above approach:

C++

// Program for transitive closure
// using Floyd Warshall Algorithm
#include<stdio.h>
 
// Number of vertices in the graph
#define V 4
 
// A function to print the solution matrix
void printSolution(int reach[][V]);
 
// Prints transitive closure of graph[][]
// using Floyd Warshall algorithm
void transitiveClosure(int graph[][V])
{
    /* reach[][] will be the output matrix
    // that will finally have the 
       shortest distances between 
       every pair of vertices */
    int reach[V][V], 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, .. 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] || 
                  (reach[i][k] && reach[k][j]);
            }
        }
    }
 
    // Print the shortest distance matrix
    printSolution(reach);
}
 
/* A utility function to print solution */
void printSolution(int reach[][V])
{
    printf ("Following matrix is transitive");
    printf("closure of the given graph\n");
    for (int i = 0; i < V; i++)
    {
        for (int j = 0; j < V; j++)
        {
              /* because "i==j means same vertex"
               and we can reach same vertex 
               from same vertex. So, we print 1....
               and we have not considered this in 
               Floyd Warshall Algo. so we need to 
               make this true by ourself
               while printing transitive closure.*/
              if(i == j)
                printf("1 "); 
              else
                printf ("%d ", reach[i][j]);
        }
        printf("\n");
    }
}
 
// Driver Code
int main()
{
    /* Let us create the following weighted graph
            10
       (0)------->(3)
        |         /|\
      5 |          |
        |          | 1
       \|/         |
       (1)------->(2)
            3           */
    int graph[V][V] = { {1, 1, 0, 1},
                        {0, 1, 1, 0},
                        {0, 0, 1, 1},
                        {0, 0, 0, 1}
                      };
 
    // Print the solution
    transitiveClosure(graph);
    return 0;
}

Java

// Program for transitive closure
// using Floyd Warshall Algorithm
import java.util.*;
import java.lang.*;
import java.io.*;
 
class GraphClosure
{
    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);
    }
 
    /* A utility function to print solution */
    void printSolution(int reach[][])
    {
        System.out.println("Following matrix is transitive closure"+
                           " of the given graph");
        for (int i = 0; i < V; i++)
        {
            for (int j = 0; j < V; j++) {
                if ( i == j)
                  System.out.print("1 ");
                else
                  System.out.print(reach[i][j]+" ");
            }
            System.out.println();
        }
    }
 
    // Driver Code
    public static void main (String[] args)
    {
        /* Let us create the following weighted graph
           10
        (0)------->(3)
        |         /|\
      5 |          |
        |          | 1
        \|/        |
        (1)------->(2)
           3           */
 
        /* Let us create the following weighted graph
 
              10
         (0)------->(3)
          |         /|\
        5 |          |
          |          | 1
         \|/         |
         (1)------->(2)
            3           */
         int graph[][] = new int[][]{ {1, 1, 0, 1},
                                      {0, 1, 1, 0},
                                      {0, 0, 1, 1},
                                      {0, 0, 0, 1}
                                    };
 
         // Print the solution
         GraphClosure g = new GraphClosure();
         g.transitiveClosure(graph);
    }
}
// This code is contributed by Aakash Hasija

Python3

# Python program for transitive closure using Floyd Warshall Algorithm 
#Complexity : O(V^3)
 
from collections import defaultdict
 
#Class to represent a graph
class Graph:
 
    def __init__(self, vertices):
        self.V = vertices
 
    # A utility function to print the solution
    def printSolution(self, reach):
        print ("Following matrix transitive closure of the given graph ")    
        for i in range(self.V):
            for j in range(self.V):
                if (i == j):
                  print ("%7d\t" % (1),end=" ")
                else:
                  print ("%7d\t" %(reach[i][j]),end=" ")
            print()
     
     
    # Prints transitive closure of graph[][] using Floyd Warshall algorithm
    def transitiveClosure(self,graph):
        '''reach[][] will be the output matrix that will finally
        have reachability values.
        Initialize the solution matrix same as input graph matrix'''
        reach =[i[:] for i in graph]
        '''Add all vertices one by one to the set of intermediate
        vertices.
         ---> Before start of a iteration, we have reachability value
         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 an iteration, vertex no. k is
         added to the set of intermediate vertices and the 
        set becomes {0, 1, 2, .. k}'''
        for k in range(self.V):
             
            # Pick all vertices as source one by one
            for i in range(self.V):
                 
                # Pick all vertices as destination for the
                # above picked source
                for j in range(self.V):
                     
                    # 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] or (reach[i][k] and reach[k][j])
 
        self.printSolution(reach)
         
g= Graph(4)
 
graph = [[1, 1, 0, 1],
         [0, 1, 1, 0],
         [0, 0, 1, 1],
         [0, 0, 0, 1]]
 
#Print the solution
g.transitiveClosure(graph)
 
#This code is contributed by Neelam Yadav

C#

// C# Program for transitive closure 
// using Floyd Warshall Algorithm 
using System;
 
class GFG 
{ 
    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); 
    } 
 
    /* A utility function to print solution */
    void printSolution(int [,]reach) 
    { 
        Console.WriteLine("Following matrix is transitive" + 
                          " closure of the given graph"); 
        for (int i = 0; i < V; i++) 
        { 
            for (int j = 0; j < V; j++){
                if (i == j)
                  Console.Write("1 ");
                else
                  Console.Write(reach[i, j] + " ");
            }
            Console.WriteLine(); 
        } 
    } 
 
    // Driver Code
    public static void Main (String[] args) 
    { 
        /* Let us create the following weighted graph 
        10 
        (0)------->(3) 
        |     /|\ 
    5 |     | 
        |     | 1 
        \|/ | 
        (1)------->(2) 
        3     */
 
        /* Let us create the following weighted graph 
 
            10 
        (0)------->(3) 
        |     /|\ 
        5 |     | 
        |     | 1 
        \|/     | 
        (1)------->(2) 
            3     */
        int [,]graph = new int[,]{{1, 1, 0, 1}, 
                                  {0, 1, 1, 0}, 
                                  {0, 0, 1, 1}, 
                                  {0, 0, 0, 1}}; 
 
        // Print the solution 
        GFG g = new GFG(); 
        g.transitiveClosure(graph); 
    } 
} 
 
// This code is contributed by 29AjayKumar

Javascript

<script>
      // JavaScript Program for transitive closure
      // using Floyd Warshall Algorithm
      var V = 4; // Number of vertices in a graph
 
      // Prints transitive closure of graph[,]
      // using Floyd Warshall algorithm
      function transitiveClosure(graph) {
        /* reach[,] will be the output matrix that
        will finally have the shortest distances
        between every pair of vertices */
        var reach = Array.from(Array(V), () => new Array(V));
        var 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);
      }
 
      /* A utility function to print solution */
      function printSolution(reach) {
        document.write(
          "Following matrix is transitive" + " closure of the given graph <br>"
        );
        for (var i = 0; i < V; i++) {
          for (var j = 0; j < V; j++) {
            if (i == j) document.write("1 ");
            else document.write(reach[i][j] + " ");
          }
          document.write("<br>");
        }
      }
 
      // Driver Code
      /* Let us create the following weighted graph
        10
        (0)------->(3)
        |     /|\
    5 |     |
        |     | 1
        \|/ |
        (1)------->(2)
        3     */
 
      /* Let us create the following weighted graph
 
            10
        (0)------->(3)
        |     /|\
        5 |     |
        |     | 1
        \|/     |
        (1)------->(2)
            3     */
      var graph = [
        [1, 1, 0, 1],
        [0, 1, 1, 0],
        [0, 0, 1, 1],
        [0, 0, 0, 1],
      ];
 
      // Print the solution
 
      transitiveClosure(graph);
       
      // This code is contributed by rdtank.
    </script>

Output

Following matrix is transitiveclosure of the given graph
1 1 1 1 
0 1 1 1 
0 0 1 1 
0 0 0 1

Time Complexity: O(V³) where V is number of vertices in the given graph.

See below post for a O(V²) solution.

Transitive Closure of a Graph using DFS

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!

Transitive closure of a graph

C++

Java

Python3

C#

Javascript

Run Local AWS Cloud Stack using LocalStack on Linux

Learn Terraform Automation in 3 days using Video Courses

How To Expose Ansible AWX Service using Nginx Ingress

LEAVE A REPLY Cancel reply

Most Popular

One UI 7: Everything you need to know

Review: The Ulefone Armor Mini 20T Pro makes other rugged phones seem flimsy

Best midrange Android phones in 2024

I tried a Xiaomi mid-ranger for the first time in years, and I’m glad the Pixel 8a exists in the US

Recent Comments

EDITOR PICKS

One UI 7: Everything you need to know

Review: The Ulefone Armor Mini 20T Pro makes other rugged phones seem flimsy

Best midrange Android phones in 2024

POPULAR POSTS

One UI 7: Everything you need to know

Review: The Ulefone Armor Mini 20T Pro makes other rugged phones seem flimsy

Best midrange Android phones in 2024

POPULAR CATEGORY

ABOUT US

FOLLOW US