Warshall algorithm calculating transitive closure

warshall_for.py

"""
Warshall algorithm
This calculates transitive closure for a given binary matrix
Author: Farooq Karimi Zadeh
Code is under CC0 1.0
"""

from pprint import pprint

def pretty_print_matrix(matrix):
    pprint(matrix, width=len(matrix[0]) * 3 + 2)


n = int(3e5)  # calculate n times
bin_matrix = [[0, 1, 0, 0], [1, 0, 1, 0], [0, 0, 0, 1], [0, 0, 0, 0]]
for dummy in range(n):
    for k, _ in enumerate(bin_matrix):
        for i, row in enumerate(bin_matrix):
            for j, value in enumerate(row):
                if not value:
                    bin_matrix[i][j] = bin_matrix[i][k] and bin_matrix[k][j]

if n == 1:
    pretty_print_matrix(bin_matrix)
else:
    pass  # then we are benchmarking

[22:27:04]:~/py$ time python3 warshall_for.py 

real	0m5.438s
user	0m5.430s
sys	0m0.008s
[22:27:15]:~/py$ time pypy3 warshall_for.py 

real	0m0.563s
user	0m0.491s
sys	0m0.025s

See these too:

• The same algorithm using functional programming it might not be Pythonic.
• The same algorithm in Rust