Transitive closure of a Graph

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] 

• 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.

• Graph
   
• Learn Graphs
   
• Learn Trees
   
• Binary Tree
   
• Learn Trees (Hinglish).
   

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!