Transitive Closure of a Directed Graph
The transitive closure of a directed graph G = (V, E) is a graph G’ = (V, E’) such that E’ contains an edge (u, v) if and only if there is a path from u to v in G. Intuitively, it makes reachability explicit.
Algorithms like Warshall’s can compute transitive closure in O(V^3) time.
Java example:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
 boolean[][] transitiveClosure(boolean[][] graph) {
int V = graph.length;
boolean[][] tc = new boolean[V][V];
for (int i = 0; i < V; i++) {
for (int j = 0; j < V; j++) {
if (graph[i][j]) {
tc[i][j] = true;
}
}
}
for (int k = 0; k < V; k++) {
for (int i = 0; i < V; i++) {
for (int j = 0; j < V; j++) {
tc[i][j] = tc[i][j]  (tc[i][k] && tc[k][j]);
}
}
}
return tc;
}

C++ example:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
 vector<vector<bool>> transitiveClosure(vector<vector<bool>> graph) {
int V = graph.size();
vector<vector<bool>> tc(V, vector<bool>(V, false));
for (int i = 0; i < V; i++) {
for (int j = 0; j < V; j++) {
if (graph[i][j]) {
tc[i][j] = true;
}
}
}
for (int k = 0; k < V; k++) {
for (int i = 0; i < V; i++) {
for (int j = 0; j < V; j++) {
tc[i][j] = tc[i][j]  (tc[i][k] && tc[k][j]);
}
}
}
return tc;
}

Python example:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
 def transitive_closure(graph):
V = len(graph)
tc = [[False] * V for _ in range(V)]
for i in range(V):
for j in range(V):
if graph[i][j]:
tc[i][j] = True
for k in range(V):
for i in range(V):
for j in range(V):
tc[i][j] = tc[i][k] and tc[k][j]
return tc

Finding the transitive closure allows querying reachability between all vertex pairs in O(1) time.
The transitive closure of a directed graph is a matrix representation that allows you to determine if there’s a path between any two nodes in the graph. If there’s a path from node i
to node j
, then the matrix cell (i, j)
will contain a 1
, otherwise it will contain a 0
.
For example, if you have a graph with nodes A, B, and C where A > B and B > C, then the transitive closure would indicate that you can also travel from A to C.
Code Examples
Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
 public class TransitiveClosure {
public static int[][] getTransitiveClosure(int[][] graph) {
int n = graph.length;
int[][] closure = new int[n][n];
for(int i=0; i<n; i++) {
for(int j=0; j<n; j++) {
closure[i][j] = graph[i][j];
}
}
for(int k=0; k<n; k++) {
for(int i=0; i<n; i++) {
for(int j=0; j<n; j++) {
closure[i][j] = closure[i][j] == 1  (closure[i][k] == 1 && closure[k][j] == 1) ? 1 : 0;
}
}
}
return closure;
}
}

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
 #include <iostream>
#include <vector>
using namespace std;
vector<vector<int>> getTransitiveClosure(vector<vector<int>> graph) {
int n = graph.size();
vector<vector<int>> closure(n, vector<int>(n));
for(int i=0; i<n; ++i) {
for(int j=0; j<n; ++j) {
closure[i][j] = graph[i][j];
}
}
for(int k=0; k<n; ++k) {
for(int i=0; i<n; ++i) {
for(int j=0; j<n; ++j) {
closure[i][j] = closure[i][j]  (closure[i][k] && closure[k][j]);
}
}
}
return closure;
}

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
 def get_transitive_closure(graph):
n = len(graph)
closure = [[0]*n for _ in range(n)]
for i in range(n):
for j in range(n):
closure[i][j] = graph[i][j]
for k in range(n):
for i in range(n):
for j in range(n):
closure[i][j] = closure[i][j] or (closure[i][k] and closure[k][j])
return closure

These code snippets implement the transitive closure of a directed graph. They use the FloydWarshall algorithm to update the transitive closure matrix. After running the code, the matrix will contain 1
s where a path exists between nodes and 0
s where it doesn’t.