Warshall algorithm - transitive closure helper

Need help with transitive closure of relation or graph? With this program/tool you can calculate the transitive closure of graph. It tells you stepp by stepp, if the step transforms the matrix, what it does. The relation is represented by an adjacency matrix. You can enter a matrix, max size of 10, with a 1 in cell [i,j] if the relation iRj exsist and a 0 if the relations doesnt exsist.

Warshall a theorem on boolean matrices

I have used the following algorithms (C# .NET):


                    private Boolean[][] WarshallsAlgorithm(Boolean[][] Matrix)
    {
        Boolean[][] adj = null;
        adj = new Boolean[N][];
        int i, j, k;
        for (i = 1; i <= N; i++)
        {
            adj[i] = new Boolean[N];
            for (j = 1; j <= N; j++)
            {
                adj[i][j] = Matrix[i][j];
            }
        }
        for (k = 1; k <= N; k++)
        {
            for (i = 1; i <= N; i++)
            {
                for (j = 1; j <= N; j++)
                {
                    adj[i][j] = (adj[i][j] || (adj[i][k] && adj[k][j]));
                }
            }
        }
        return adj;
    }

Sybren Roede (3 November 2009)

The Warshall Algorithm output

The start matrix of the Graph is

0	0	1	0
0	0	1	0
1	0	0	0
0	0	0	1
0	1	0	0

Algortihm

adj[i][j] = adj[3][2] = 1 && adj[j][k] = adj[2][4] = 1 --> adj[i][k] = adj[3][4] := 1

0	0	1	0
0	0	1	0
1	0	1	0
0	0	0	1
0	1	0	0

adj[i][j] = adj[5][3] = 1 && adj[j][k] = adj[3][2] = 1 --> adj[i][k] = adj[5][2] := 1
adj[i][j] = adj[5][3] = 1 && adj[j][k] = adj[3][4] = 1 --> adj[i][k] = adj[5][4] := 1

0	0	1	0
0	0	1	0
1	0	1	0
0	0	0	1
1	1	1	0

adj[i][j] = adj[1][4] = 1 && adj[j][k] = adj[4][5] = 1 --> adj[i][k] = adj[1][5] := 1

0	0	1	1
0	0	1	0
1	0	1	0
0	0	0	1
1	1	1	0

adj[i][j] = adj[2][4] = 1 && adj[j][k] = adj[4][5] = 1 --> adj[i][k] = adj[2][5] := 1

0	0	1	1
0	0	1	1
1	0	1	0
0	0	0	1
1	1	1	0

adj[i][j] = adj[3][4] = 1 && adj[j][k] = adj[4][5] = 1 --> adj[i][k] = adj[3][5] := 1

0	0	1	1
0	0	1	1
1	0	1	1
0	0	0	1
1	1	1	0

adj[i][j] = adj[5][4] = 1 && adj[j][k] = adj[4][5] = 1 --> adj[i][k] = adj[5][5] := 1

0	0	1	1
0	0	1	1
1	0	1	1
0	0	0	1
1	1	1	1

adj[i][j] = adj[1][5] = 1 && adj[j][k] = adj[5][2] = 1 --> adj[i][k] = adj[1][2] := 1
adj[i][j] = adj[1][5] = 1 && adj[j][k] = adj[5][3] = 1 --> adj[i][k] = adj[1][3] := 1

1	1	1	1
0	0	1	1
1	0	1	1
0	0	0	1
1	1	1	1

adj[i][j] = adj[2][5] = 1 && adj[j][k] = adj[5][2] = 1 --> adj[i][k] = adj[2][2] := 1
adj[i][j] = adj[2][5] = 1 && adj[j][k] = adj[5][3] = 1 --> adj[i][k] = adj[2][3] := 1

1	1	1	1
1	1	1	1
1	0	1	1
0	0	0	1
1	1	1	1

adj[i][j] = adj[3][5] = 1 && adj[j][k] = adj[5][3] = 1 --> adj[i][k] = adj[3][3] := 1

1	1	1	1
1	1	1	1
1	1	1	1
0	0	0	1
1	1	1	1

adj[i][j] = adj[4][5] = 1 && adj[j][k] = adj[5][2] = 1 --> adj[i][k] = adj[4][2] := 1
adj[i][j] = adj[4][5] = 1 && adj[j][k] = adj[5][3] = 1 --> adj[i][k] = adj[4][3] := 1
adj[i][j] = adj[4][5] = 1 && adj[j][k] = adj[5][4] = 1 --> adj[i][k] = adj[4][4] := 1

1	1	1	1
1	1	1	1
1	1	1	1
1	1	1	1
1	1	1	1

The Transitive matrix of the Graph is

1	1	1	1
1	1	1	1
1	1	1	1
1	1	1	1
1	1	1	1