Transitive Closure

Transitive Closure it the reach-ability matrix to reach from vertex u to vertex v of a graph. One graph is given, we have to find a vertex v which is reachable from another vertex u, for all vertex pairs (u, v).

The final matrix is the Boolean type. When there is a value 1 for vertex u to vertex v, it means that there is at least one path from u to v.

Input and Output

Input:
1 1 0 1
0 1 1 0
0 0 1 1
0 0 0 1

Output:
The matrix of transitive closure
1 1 1 1
0 1 1 1
0 0 1 1
0 0 0 1

Algorithm

transColsure(graph)

Input: The given graph.
Output: Transitive Closure matrix.

Begin
   copy the adjacency matrix into another matrix named transMat
   for any vertex k in the graph, do
      for each vertex i in the graph, do
         for each vertex j in the graph, do
            transMat[i, j] := transMat[i, j] OR (transMat[i, k]) AND transMat[k, j])
         done
      done
   done
   Display the transMat
End