Instantly share code, notes, and snippets.

# farooqkz/warshall_for.py

Last active May 10, 2021 15:16
Show Gist options
• Save farooqkz/a6d6ac3cacdf06af1907952888acc5c2 to your computer and use it in GitHub Desktop.
Warshall algorithm calculating transitive closure
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 """ 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: