Warshall algorithm in Graph in Java.

In directed graph if we starts from a vertex we may not be able to reach some vertices. For example consider below graph, if we start from vertex D we can only reach C other vertices are unreachable from D. In some graph applications we need to know which vertices we can reach if we starts from a particular vertex.

Fig 1

Using Warshall algorithm we can modify adjacency matrix of graph to generate transistive closure of graph using which we can know what all vertices are reachable from a particular vertex. For finding transistive closure using warshall algorithm we modify adjacency matrix whenever we find transitive property between vertices for connections. For example in above graph there is an edge from A to D and another edge from D to C, so there is path from A to C and we modify entry for row A and column C in adjacency matrix to indicate connection.

Consider below directed graph. Using below java code for warshall algorithm we will find transistve closure for below graph.

Fig 2

Java code:

001 /*Warshall Algorithm to find Transistive Closure  002  * of a Directed Graph. 003  * @author Anuj 004  * */ 005 public class Warshall { 006         private Graph graph; 007          008         /* 009          * Adding vertices and Edges to  010          * graph. 011          * */ 012         private void setGraph(){ 013                 graph = new Graph(5); 014                 graph.addVertex('A'); 015                 graph.addVertex('B'); 016                 graph.addVertex('C'); 017                 graph.addVertex('D'); 018                 graph.addVertex('E'); 019                  020                 graph.addEdge(0, 1); 021                 graph.addEdge(1, 2); 022                 graph.addEdge(2, 4); 023                 graph.addEdge(3, 1); 024                 graph.addEdge(3, 4); 025         } 026          027         /* 028          * In this method warshall algorithm runs. 029          *Adjacency Matrix of a directed graph is modified to  030          *generate transistive closure of graph.  031          * */ 032         private void warshallAlgo(){ 033                 int numVerts = graph.numVerts; 034                  035                 for (int k = 0; k < numVerts; k++) { 036                         for (int i = 0; i < numVerts; i++) { 037                                 if(graph.adjMatrix[i][k]==0){ 038                                         continue; 039                                 } 040                                 for (int j = 0; j < numVerts; j++) { 041                                         if(graph.adjMatrix[k][j]==1){ 042                                                 graph.adjMatrix[i][j] = 1; 043                                         } 044                                 } 045                         } 046                 } 047         } 048  049         public static void main(String[] args) { 050                 Warshall warshall = new Warshall(); 051                 warshall.setGraph(); 052                 System.out.println("Adjacency matrix of Graph is:"); 053                 warshall.graph.displayMatrx(warshall.graph.adjMatrix); 054                 System.out.println(); 055                 warshall.warshallAlgo(); 056                 //Adjacency matrix is modified to generate transistive closure  057                 //in method warshallAlgo(). 058                 System.out.println("Transistive Closure of Graph is:"); 059                 warshall.graph.displayMatrx(warshall.graph.adjMatrix); 060         } 061 } 062  063  064 class Graph{ 065      int maxVertsNum; 066          int numVerts; 067          Vertex [] vertexList; 068          int [][] adjMatrix; 069          070         public Graph(int maxVerts){ 071                 maxVertsNum = maxVerts; 072                 numVerts = 0; 073                 vertexList = new Vertex[maxVertsNum]; 074                 adjMatrix = new int[maxVertsNum][maxVertsNum]; 075                 //Initializing all entries to zero. 076                 for (int i = 0; i < maxVertsNum; i++) { 077                         for (int j = 0; j < maxVertsNum; j++) { 078                                 adjMatrix[i][j] = 0; 079                         } 080                 } 081         } 082          083         public void addVertex(char label){ 084                 if(numVerts < maxVertsNum){ 085                         vertexList[numVerts++] = new Vertex(label); 086                 } 087         } 088          089         /* 090          * Adding an edge to a directed graph. 091          * */ 092         public void addEdge(int start, int end){ 093                 if(start < numVerts && end < numVerts){ 094                         adjMatrix[start][end] = 1; 095                 } 096         } 097          098         public void display(int idx){ 099                 System.out.print(vertexList[idx].label); 100         } 101          102         /* 103          * Method to display 2-D array in row  104          * and column form with labels of vertices in  105          * row and column. 106          * */ 107         public void displayMatrx(int [][] array){ 108                 System.out.print("  "); 109                 for (int i = 0; i < numVerts; i++) { 110                         System.out.print(vertexList[i].label+" "); 111                 } 112                 System.out.println(); 113                 for (int i = 0; i < numVerts; i++) { 114                         System.out.print(vertexList[i].label+" "); 115                         for (int j = 0; j < numVerts; j++) { 116                                 System.out.print(array[i][j]+" "); 117                         } 118                         System.out.println(); 119                 } 120         } 121 } 122  123 class Vertex{ 124         char label; 125          126         public Vertex(char label){ 127                 this.label = label; 128         } 129 }

Java2html

Output: 

Adjacency matrix of Graph is:
  A B C D E 
A 0 1 0 0 0 
B 0 0 1 0 0 
C 0 0 0 0 1 
D 0 1 0 0 1 
E 0 0 0 0 0 

Transistive Closure of Graph is:
  A B C D E 
A 0 1 1 0 1 
B 0 0 1 0 1 
C 0 0 0 0 1 
D 0 1 1 0 1 
E 0 0 0 0 0 

Explanation:
In warshall algorithm for finding transitive closure of graph we modify adjacency matrix of graph. For example in Fig 2 graph if there is an edge from A to B and another edge from B to C then A and C are connected and we modify entry in adjacency matrix to enter 1 for row A and column C. In above code method warshallAlgo contains logic for warshall algorithm. There are 3 for loops used in warshall algorithm. Vertex represented by outermost for loop using int variable k acts as intermediate vertex like B in example I just mentioned above that is connected with 2 different vertex. In 1st inner for loop with i as loop variable we check for all vertices if there is an edge to vertices represented by outermost loop i.e. an edge from i to k, if there is no edge we do not go to 2nd inner for loop and continue with next iteration of 1st inner for loop. 2nd inner loop having j as loop variable is entered only when there is an edge from i to k. In 2nd for loop we check if there is an edge from vertices of outermost for loop to in the direction of vertices of 2nd inner for loop i.e. an edge from k to j. If there an edge from k to j thats mean i to j is a connected path and we modify adjacency matrix entry for row i and column j.
Warshall algorithm has time complexity of O(N^3). But after transistive closure has been generated it will take only O(1) time to find if a vertex is reachable from a particular vertex.