matrix.transitive_closure

https://en.wikipedia.org/wiki/Transitive_closure#In_graph_theory https://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm

Functions

transitive_closure(→ list[list[int]])

Compute the transitive closure of a directed graph using the

Module Contents

matrix.transitive_closure.transitive_closure(graph: list[list[int]]) → list[list[int]]

Compute the transitive closure of a directed graph using the Floyd-Warshall algorithm.

Args:

graph: Adjacency matrix representation of the graph.

Returns:

Transitive closure matrix.

>>> graph = [
...     [0, 1, 1, 0],
...     [0, 0, 1, 0],
...     [1, 0, 0, 1],
...     [0, 0, 0, 0]
... ]
>>> transitive_closure(graph)
[[1, 1, 1, 1],
 [1, 1, 1, 1],
 [1, 1, 1, 1],
 [0, 0, 0, 1]]