Compute the Transitive Closure of a Graph

After doing a little reading, it appears that Warshall's method is the most common way of doing this in practice

  • 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(3) but it reduces storage by retaining only one bit for each matrix element (e.g. we can use bool data-type instead of int). The implementation

import pandas as pd

from scipy import sparse

graph = sparse.csr_matrix(
[
    [1,1,0,0],
    [1,1,0,0],
    [0,0,1,0],
    [0,0,0,1]
])

df = pd.DataFrame.sparse.from_spmatrix(graph)
df
0 1 2 3
0 1 1 0 0
1 1 1 0 0
2 0 0 1 0
3 0 0 0 1 
groups, labels = sparse.csgraph.connected_components(graph, directed=False)
groups

3