Calculator
Enter a graph as a 0/1 adjacency matrix. You can type values or paste a matrix.
Example data
A 4-vertex directed cycle. Each vertex can reach every other vertex.
| V1 | V2 | V3 | V4 | |
|---|---|---|---|---|
| V1 | 0 | 1 | 0 | 0 |
| V2 | 0 | 0 | 1 | 0 |
| V3 | 0 | 0 | 0 | 1 |
| V4 | 1 | 0 | 0 | 0 |
| V1 | V2 | V3 | V4 | |
|---|---|---|---|---|
| V1 | 1 | 1 | 1 | 1 |
| V2 | 1 | 1 | 1 | 1 |
| V3 | 1 | 1 | 1 | 1 |
| V4 | 1 | 1 | 1 | 1 |
Formula used
Warshall’s recurrence updates reachability by allowing one more intermediate vertex each round:
- R is a 0/1 reachability matrix.
- k loops from 1 to n, adding new intermediates.
- If diagonal forcing is enabled, R[i][i]=1.
How to use this calculator
- Set the number of vertices, then choose graph options.
- Enter the adjacency matrix using the grid, or paste it.
- Click Compute to get the transitive closure.
- Enable steps to see the matrix after each k iteration.
- Use the download buttons to export CSV or PDF.
FAQs
1) What does the transitive closure represent?
It shows reachability. A value of 1 at (i, j) means there exists a path from vertex i to vertex j using one or more edges, depending on whether the diagonal is forced to 1.
2) Is this the same as Floyd–Warshall?
Warshall targets reachability with boolean logic. Floyd–Warshall is a related dynamic programming method that computes shortest paths by replacing OR/AND with min/+ over weighted distances.
3) Can I use this for undirected graphs?
Yes. Uncheck “Directed graph.” The tool symmetrizes the matrix, so if an edge exists between i and j, both (i, j) and (j, i) become 1 before the closure runs.
4) What does “Force diagonal to 1” do?
It sets every (i, i) entry to 1, meaning each vertex is reachable from itself. This is common for reachability definitions, and it often makes results easier to interpret.
5) How large can the matrix be?
This page supports 2 to 12 vertices to keep input readable. The algorithm itself is O(n³), so larger n increases compute time and step displays can become very long.
6) Why are only 0 and 1 accepted?
Warshall’s closure uses boolean values. Any input that is not exactly 1 is treated as 0 to prevent accidental non-binary entries from changing the meaning of reachability.
7) What is shown in the step-by-step output?
Each step shows the matrix after allowing vertex k as an intermediate node. You can watch reachability expand as k increases, matching the recurrence used by the algorithm.
8) Do downloads include the step matrices?
Downloads include the final closure matrix. Step tables are designed for on-screen learning, because exporting every intermediate matrix can create large files and reduce readability.