The program calculates transitive closure of a relation represented as an
adjacency matrix. Element (i,j) in the matrix is equal to 1 if the pair
(i,j) is in the relation. Otherwise, it is equal to 0.
For calculating transitive closure it uses Warshall's algorithm.
Algorithm Warshall
Input: The adjacency matrix of a relation R on a set with n elements.
Output: The adjacency matrix T of the transitive closure of R.
Procedure:
Start with T=A.
For each j from 1 to n
For each i from 1 to n
If T(i,j)=1, then form the Boolean or of row i and row j
and replace row i by it.
Go on to the next i-value.
Once you have processed each i-value, go on to the next j-value.
The above description of the algorithm and proof of its correctness
may be found in "Discrete Mathematics" by Kenneth P. Bogart.
The program allows to specify the number of elements in the relation (from 1 to 20). (Upper bound is set to 20 for the sake of nice graphics.) Pressing the button "New matrix" will result in creating a new matrix of a specified size. Elements with value 0 are represented as empty cells, elements with values 1 are represented as cells containing "1". Clicking on an empty cell will change its value to 1. Clicking on a cell with "1" will change its value back to an empty cell.
After you have specified the relation press "Find transitive closure" button to see its transitive closure.
Press the button to see the program.