Transitive Closure of a Graph - Warshall's Algorithm

Graphs->Transitive Closure

We have seen Adjacency Matrix, which tells you whose directly connected to whom, no! Remember, I left a special note there, saying that there can be many other paths which may exist and might not be visible from the Adjacency matrix, as these paths may have intermediate vertices. To find all such round about or via-paths there is a procedure to be followed, known as the transitive closure, which results in a matrix showing all those via-paths, if ever exist.

Before I give you the algorithm, I need to create some background for it, as its a little complicated one. The input to this algorithm is an adjacency matrix, which has 1s for any row-column pair if there exists an edge between them. What we'll be doing here is -- checking out for every vertex, the incoming and outgoing links. If there exist both incoming and outgoing links for a particular vertex, we will put a 1 for the row-column pair formed by them in the adjacency matrix. Let me explain this with the help of an example -

	A	B	C	D	E
A	0	0	0	1	0	(AD)
B	0	0	0	1	0	(BD)
C	0	1	0	0	0	(CB)
D	0	0	0	0	1	(DE)
E	0	0	1	0	0	(EC)

Directed Graph

Adjacency Matrix

Let's take the vertex E into consideration. You have an edge coming from D and you have an edge going to C; quite visible from the matrix. So, as I said, we'll put a 1 for the element DC in the matrix. Similarly, for the vertex C, we'll put 1 for the element EB. We'll do this for all the vertex in the graph and what you get at the end is the Transitive Closure of this graph. This way of finding the transitive closure was derived by Warshall and thus the name, Warshall's algorithm.

Algorithm:-
Step-1: Copy the Adjacency matrix into another matrix called the Path matrix
Step-2: Find in the Path matrix for every element in the Graph, the incoming and outgoing edges
Step-3: For every such pair of incoming and outgoing edges put a 1 in the Path matrix

C implementation:-
transclosure( int adjmat[max][max], int path[max][max])
{
for(i = 0; i < max; i++)
for(j = 0; j < max; j++)
      path[i][j] = adjmat[i][j];

for(i = 0;i <max; i++)
for(j = 0;j < max; j++)
   if(path[i][j] == 1)
    for(k = 0; k < max; k++)
      if(path[j][k] == 1)
        path[i][k] = 1;
}

Note:- Well, there are other ways to find the transitive closure but Warshall has actually simplified them and hence I have referred that only.

Index || Doubts / Clarifications || Related Topics || Web Links