Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
What does a graph's transitive closure mean?
3.
Floyd Warshall Algorithm
4.
Finding Transitive Closure Implementation
4.1.
Output
5.
Complexity
5.1.
Time Complexity
5.2.
Space complexity
6.
Frequently Asked Questions
6.1.
What does "transitive closure" mean?
6.2.
What factors determine that a directed graph is transitive?
6.3.
Give an example of reflexive closure?
6.4.
Is the Floyd-Warshall algorithm greedy?
6.5.
Is programming using the Floyd-Warshall method dynamic?
7.
Conclusion
Last Updated: Mar 27, 2024
Medium

Transitive closure of a Graph

Master Power BI using Netflix Data
Speaker
Ashwin Goyal
Product @
18 Jun, 2024 @ 01:30 PM

Introduction

We will study the transitive closure of the graph in this article. Transitive Close the reachability matrix to connect a graph's vertex u to vertex v. Given a graph, we must determine every vertex combination for which a vertex v can be reached from a vertex u.

Introduction

graph is a visual representation of a collection of things where some object pairs are linked together. Vertices are the points used to depict related items, while edges are the connections between them.

What does a graph's transitive closure mean?

Let's use node I as the starting point in any Directed Graph and node j as the finishing point. The reachability factor is used to create a transitive closure matrix for all (i,j) pairs in a graph. If j is reachable from I (i.e., there is a path connecting I and j), we can set the matrix element to 1; otherwise, if there is no connection, we can set it to 0.

Imagine receiving the Directed Graph shown below:

Directed Graph

The graph's reachability matrix can then be determined via,

graph's reachability matrix

The availability of a path from I to j for each (i,j) in the matrix is shown by the number "1" in this matrix, which is also known as the transitive closure matrix.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Floyd Warshall Algorithm

The stages that make up this algorithm are as follows:
 

  • The input neighbouring matrix of the graph is used to initialise the solution matrix in the first phase. Give it the name "shortest path".
     
  • The next step is to treat each node in the range of 0–n as a strating vertex when we iterate over them one by one. The nodes 1, 2,..., n are iterated over once again while taking the terminating vertex into account.
     
  • The next iteration for the shortest path must range from 1, 2,..., k-1, where vertex k has been chosen as an intermediate vertex.
     
  • There are two potential outcomes for each pair of the starting and finishing vertices I j), respectively.
     
  • Shortest path[i][j] > shortest path[i][k] + shortest path[k][j] 
shortest path
  • New path path[i][j]
     
  • The loop continues if k is not an intermediate vertex since then nothing is changed.
     

For improved idea clarity, Floyd Warshall's sample demonstration is provided below.

/// utility function for the Floyd Warshall Algorithm demonstration
void Floyd_Warshall (int** edges, int numNodes) 
/// Where numNodes represents the number of nodes.
{  
    int shortest_path[numNodes][numNodes];  

    /// Initialising the neighbouring matrix to the solution matrix in step one
    for (int i = 0; i < numNodes; i++)  
        for (int j = 0; j < numNodes; j++)  
            shortest_path[i][j] = edges[i][j];  

    /// k is a middle vertex.
    for (int k = 0; k < numNodes; k++)  
    {  
        /// I = beginning vertex
        for (int i = 0; i < numNodes; i++)  
        {  
            /// j = end vertex
            for (int j = 0; j < numNodes; j++)  
            {  
                /// the quickest path being updated
                if (shortest_path[i][k] + shortest_path[k][j] < shortest_path[i][j])  
                    shortest_path[i][j] = shortest_path[i][k] + shortest_path[k][j];  
            }  
        }  
    } 

    /// program to print the graph of the shortest path
    print_graph(shortest_path);  
}

Finding Transitive Closure Implementation

#include <iostream>
#include <vector>
#include <cstring>
#include <iomanip>
using namespace std;
 
// An edge-storing data structure for graphs
struct Edge {
    int src, dest;
};
 
// a class for graph objects
class Graph
{
public:
    //an adjacency list represented as a vector of vectors
    vector<vector<int>> adjList;
 
    Graph(vector<Edge> const &edges, int n)
    {
        adjList.resize(n);
 
        // A directed graph with edges
        for (Edge edge: edges)
        {
            int src = edge.src;
            int dest = edge.dest;
 
            adjList[src].push_back(dest);
        }
    }
};
 
// A graph's transitive closure is stored in a connection matrix called "C."
// The DFS tree's "root" node is at the very top (it is the starting vertex of DFS)
// The current vertex being investigated in DFS is "descendant."
// The graph already has a route from "root" to "descendant," which is an invariant.
void DFS(Graph const &graph, vector<vector<bool>> &C, int root, int descendant)
{
    for (int child: graph.adjList[descendant])
    {
        // If "child" is a descendant's neighbouring vertex, we have
        // identified a root-to-child path
        if (!C[root][child])
        {
            C[root][child] = true;
            DFS(graph, C, root, child);
        }
    }
}
 
int main()
{
    // a collection of graph edges, as seen in the picture above.
    vector<Edge> edges = {
        {0, 2}, {1, 0}, {3, 1}
    };
 
    // number of nodes in the network as a whole (labelled from 0 to 3)
    int n = 4;
 
    // create a graph using the provided edges.
    Graph graph(edges, n);
 
    // The transitive closure is stored in the connection matrix "C."
    // that graph. C[i][j] only has a value of 1 if a directed
    // From vertex I to vertex "j," a route exists.
    vector<vector<bool>> C(n, vector<bool>(n, false));
 
    // Take into account each vertex and begin DFS from it.
    for (int v = 0; v < n; v++)
    {
        C[v][v] = true;
        DFS(graph, C, v, v);
 
        // print vertex 'v' path information
        for (int u = 0; u < n; u++) {
            cout << left << setw(4) << C[v][u];
        }
        cout << endl;
    }
 
    return 0;
}

Output

1   0   1   0   
1   1   1   0   
0   0   1   0   
1   1   1   1  

Complexity

Time Complexity

O(V^3): where V is the number of vertexes.

Reason: For the main iteration, three loops are layered inside of one another. Each loop iterates for V times, and this number changes depending on the input V. As a result, our temporal complexity is O(V^3).

Space complexity

O(V^2): where n is the array's size.

Reason: We allocate a single two-dimensional matrix with a total number of rows and columns equal to the number of vertices V in each at the start of the process. As V rises, the program's space requirements grow. Therefore, that depends on V. Thus, the complexity of space is O(V^2).

Frequently Asked Questions

What does "transitive closure" mean?

The smallest relation on X that contains R and is transitive is known as the transitive closure of a binary relation R on a set X. In terms of finite sets, the term "smallest" can be interpreted as meaning that there are the fewest related pairs; in terms of infinite sets, it refers to the one and only minimum transitive superset of R.

What factors determine that a directed graph is transitive?

An undirected graph has a transitive orientation if its edges may be orientated in such a way that if the resultant directed graph has two edges (x, y), and two edges (y, z), then the resulting directed graph also has an edge (x, z).

Give an example of reflexive closure?

The smallest reflexive relation on X that includes a binary relation R on a set X is known as the reflexive closure of R. For instance, if X is a collection of distinct integers and x R y signifies "x is less than y," then the relation "x is less than or equal to y" is the reflexive closure of R.

Is the Floyd-Warshall algorithm greedy?

While the greedy algorithm evaluates each node that is passed to pick the shortest route (Local Optimum) so that the time needed for searching is shorter, the Floyd-Warshall algorithm considers all potential routes so that some routes are presented. So it is considered a greedy algorithm.

Is programming using the Floyd-Warshall method dynamic?

Floyd-Warshall algorithm is an illustration of dynamic programming. It divides the issue into more manageable subproblems, and then integrates the solutions to those subproblems to address the larger issue at hand.

Conclusion

We have gone through the Transitive closure of a Graph. After calling the utility function to output the matrix, our algorithm is complete.

You should now fully understand how to use the Floyd Warshall Algorithm to discover the transitive closure of a graph after reading this article from Coding Ninja.

Check Out these articles mentioned below.

If you face any doubt, please comment, and we will love to answer your questions.

Want expertise in Python for your next web development project? Check out our course.
Nevertheless, you may consider our paid courses to give your career an edge over others!

Do upvote our blogs if you find them helpful and engaging!

Happy Learning!

Previous article
Implementation of Push Relabel Algorithm
Next article
Transitive Closure Of a Graph Using Recursion
Live masterclass