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`for a dense graph). We can also use BFS instead of DFS.

^{2}## C++

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 83 84 |
#include <iostream> #include <vector> #include <cstring> #include <iomanip> 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: // An array of vectors to represent adjacency list vector<int> adjList[N]; // Constructor Graph(vector<Edge> const &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) // descendant is current vertex to be explored in DFS // Invariant: A path already exists from root -> descendant in graph void DFS(Graph const& graph, bool C[N][N], int root, int descendant) { for (int child : graph.adjList[descendant]) { // if child is a adjacent vertex of descendant, 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; } |

## Java

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 83 84 85 86 87 88 89 |
import java.util.*; // Data structure to store graph edges class Edge { int source, dest; public Edge(int source, int dest) { this.source = source; this.dest = dest; } }; // Class to represent a graph object class Graph { // An array of Lists to represent adjacency list List<List<Integer>> adjList = null; // Constructor Graph(List<Edge> edges, int N) { adjList = new ArrayList<>(N); for (int i = 0; i < N; i++) { adjList.add(i, new ArrayList<>()); } // add edges to the undirected graph for (int i = 0; i < edges.size(); i++) { int src = edges.get(i).source; int dest = edges.get(i).dest; adjList.get(src).add(dest); } } } class TransitiveClosure { // C is connectivity matrix and stores transitive closure of graph // root is the topmost node in DFS tree(it is starting vertex of DFS) // descendant is current vertex to be explored in DFS // Invariant: A path already exists from root -> descendant in graph public static void DFS(Graph graph, byte[][] C, int root, int descendant) { for (int child : graph.adjList.get(descendant)) { // if child is a adjacent vertex of descendant, we have // found a path from root->child if (C[root][child] == 0) { C[root][child] = 1; DFS(graph, C, root, child); } } } public static void main(String[] args) { // vector of graph edges as per above diagram List<Edge> edges = Arrays.asList( new Edge(0, 2), new Edge(1, 0), new Edge(3, 1) ); // Set number of vertices in the graph final int N = 4; // create a graph from edges Graph graph = new Graph(edges, N); // 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. byte C[][] = new byte[N][N]; // consider each vertex and start DFS from it for (int v = 0; v < N; v++) { C[v][v] = 1; DFS(graph, C, v, v); // print path info for vertex v for (int u = 0; u < N; u++) System.out.print(C[v][u] + " "); System.out.println(); } } } |

`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 pre-processing 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:**

**Thanks for reading.**

Please use our online compiler to post code in comments.

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

## Leave a Reply

Don’t think the example above is right. Based on the diagram, the adjacency matrix will look like below:

Original graph

0 0 1 01 0 0 0

0 0 0 0

0 1 0 0

And the transitive closure should look like below.

Transitive closure of the graph

0 0 1 01 0 1 0

0 0 0 0

1 1 1 0

Thanks Faiz for sharing your concerns. You’re right but ignoring the fact that there exists a path from every vertex to itself. Hence all diagonal elements in the square connectivity matrix are also 1. Hope you’re clear now.

why the complexity is O(V + E) but not O(E) for dfs? Since in each dfs we only iterate over the adjlist. Thanks!

Thanks Emily for sharing your concerns. Consider a disconnected graph with n vertices and 0 edges. In this case, DFS routine would run in

O(n)time.Hope you’re clear now. Happy coding 🙂