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 Floyd-Warshall algorithm to update the transitive closure matrix. After running the code, the matrix will contain 1s where a path exists between nodes and 0s where it doesn’t.