Given a digraph G, the transitive closure is a digraph G’ such that (i, j) is an edge in G’ if there is a directed path from i to j in G. The resultant digraph G’ representation in form of adjacency matrix is called the connectivity matrix.

**For example, consider below directed graph –**

**Its connectivity matrix C is – **

1 0 1 0

1 1 1 0

0 0 1 0

1 1 1 1

The value of C[i][j] is 1 only if a directed path exists from vertex i to vertex j.

**Method 1:**

As discussed in previous post, the Floyd–Warshall algorithm can be used to for finding the **transitive closure** of a graph in O(V^{3}) time. The algorithm returns the shortest paths between every of vertices in graph. We can easily modify the algorithm to return 1/0 depending upon path exists between pair of vertices or not. The implementation can be seen here.

**Method 2: (Commonly used)**

**Warshall’s algorithm** is commonly used to construct transitive closures. It is very identical to Floyd’s all-pairs-shortest-path algorithm. The main idea behind Warshall’s algorithm is that a path exists between two pair of vertices i, j if and only if there is an edge from i to j or any of the below condition is true.

- there is a path from i to j going through vertex 1
- there is a path from i to j going through vertex 1 and/or 2
- there is a path from i to j going through vertex 1, 2, and/or 3
- there is a path from i to j going through any of the other vertices

The time complexity of this algorithm is same as that of Floyd–Warshall algorithm i.e. O(V^{3}) but it reduce storage by retaining only one bit for each matrix element (e.g. we can use bool data-type instead of int). The implementation can be seen here.

**Method 3: (For dense graphs)**

We know that all pairs of vertices are reachable from each other in each strongly connected component of a graph. We also know that the strongly connected components of graph can be computed in linear time. The idea is to exploit this fact to compute transitive closure of the graph. Further, if (x,y) is an edge between two vertices in different strongly connected components, every vertex in y’s component is reachable from each vertex in x’s component. Thus the problem reduces to finding the transitive closure on a graph of strongly connected components, which should have considerably fewer edges and vertices than given graph. We will discuss this approach soon in separate post.

**Method 4: (For sparse graphs)**

We know that we can find all vertices reachable from a vertex v by calling DFS on vertex v. If we do the same for all vertices present in the graph and store the path information in a matrix, we will get transitive closure of the graph. Also, the total time complexity will reduce to O(V(V+E)) which is equal O(V^{3}) only if graph is dense (remember E = V^{2} for a dense graph). We can also use BFS instead of DFS.

**C++ implementation –**

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 |
#include <bits/stdc++.h> using namespace std; // Number of vertices in the graph #define N 4 // data structure to store graph edges struct Edge { int src, dest; }; // class to represent a graph object class Graph { public: // A array of vectors to represent adjacency list vector<int> adjList[N]; // Constructor Graph(vector<Edge> edges) { // add edges to the directed graph for (int i = 0; i < edges.size(); i++) { int src = edges[i].src; int dest = edges[i].dest; adjList[src].push_back(dest); } } }; // C is connectivity matrix and stores transitive closure of graph // root is the topmost node in DFS tree(it is starting vertex of DFS) // descendent is current vertex to be explored in DFS // Invariant: A path already exists from root -> descendent in graph void DFS(Graph const& graph, bool C[N][N], int root, int descendent) { for (int child : graph.adjList[descendent]) { // if child is a adjacent vertex of descendent, we have // found a path from root->child if (!C[root][child]) { C[root][child] = true; DFS(graph, C, root, child); } } } // main function int main() { // array of graph edges as per above diagram vector<Edge> edges = { { 0, 2 }, { 1, 0 }, { 3, 1 } }; // create a graph from edges Graph graph(edges); // C is connectivity matrix and stores the transitive closure // of the graph. The value of C[i][j] is 1 only if a directed // path exists from vertex i to vertex j. bool C[N][N]; memset(C, false, sizeof C); // consider each vertex and start DFS from it for (int v = 0; v < N; v++) { C[v][v] = true; DFS(graph, C, v, v); // print path info for vertex v 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

Transitive closure is used to answer reachability queries (can we get to x from y?) efficiently in constant time after preprocessing of constructing the transitive closure.

**Transitive Reduction**

Transitive reduction (also known as minimum equivalent digraph) is reducing the number of edges while maintaining identical reachability properties i.e the transitive closure of G is identical to the transitive closure of the transitive reduction of *G*. The primary application of transitive reduction is space minimization, by eliminating redundant edges from G that do not effect reachability. We will try to cover transitive reduction in detail in future posts. So stay tuned and thank you for reading. 🙂

**References:**

https://www8.cs.umu.se/kurser/TDBA77/VT06/algorithms/BOOK/BOOK4/NODE163.HTM

http://cs.winona.edu/lin/cs440/ch08-2.pdf

Please use ideone or C++ Shell or any other online compiler link to post code in comments.

Like us? Please spread the word and help us grow. Happy coding 🙂

## Leave a Reply