Skip to content

Instantly share code, notes, and snippets.

@farooqkz
Last active May 10, 2021 15:16
Show Gist options
  • Save farooqkz/a6d6ac3cacdf06af1907952888acc5c2 to your computer and use it in GitHub Desktop.
Save farooqkz/a6d6ac3cacdf06af1907952888acc5c2 to your computer and use it in GitHub Desktop.
Warshall algorithm calculating transitive closure
"""
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
@farooqkz
Copy link
Author

farooqkz commented May 6, 2021

[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:

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment