Before I present it, I suppose I should explain a little bit about what Warshall's algorithm does, in case there some readers who have never heard of it (like me less that a year ago). I'm not going to go deep, it being a well established and easily Googleable subject. For instance, this page does a better job than I'm likely to do in any case.
Here it is in a nutshell. Given a directed graph find out which nodes have paths between them. This is also known as the transitive closure of the graph for those who prefer the more impressive sounding mathematical terminology. For Warshall's algorithm one starts with the adjacency matrix of the graph, which is a matrix in which all nodes with direct connections (edges) between them are identified with a 1, and all other pairs of nodes with a 0. Warshall's algorithm generates from this data a new matrix with a 1 for all nodes that are connected by a path, 0 for all others. By "path" I mean that by traveling from node to adjacent node (those with an edge between them) one can arrive at the other node in a pair of nodes. Since this is a directed graph one must follow the direction of the edge in question. Think of it as a game of catch where each player only throws to certain other players. The adjacency matrix would identify which players throw to specific other players; a 1 row 1 column 2 if player 1 throws to player 2, a 0 otherwise. It's quite possible, based on this scenario, that some players never get the ball thrown to them. A fair PE teacher could implement Warshall's algorithm to identify that situation. If only more PE teachers understood algorithms the world would be a more equitable place. (One interesting side note, row 1 column 1 will always be 0 in the adjacency matrix since a player never throws the ball to himself, but it could be 1 in the path matrix since hopefully the player can get the ball back... or maybe not!)
The way Warshall's algorithm works is like this. Enumerating through each node numbered by k, starting with k=0 (i.e. node #0), decide which node pairs i,j have paths through node k. This can be determined by evaluating wither or not a path from i to k and from k to j already exists on the path matrix, which was initialized as the adjacency matrix. If it does, then the path from i to j can be added to the path matrix. Our paths will thus grow organically as we iterate through k. When we done we will have every path identified in our matrix since every path with every intermediate node will have been identified.
Anyway, now that I've probably confused everybody (Google "directed graph" to become un-befuddled) here's the Java code. I've also included a test case class which I think helps to understand it. So, without further ado:
package com.blogspot.ezetter.algorithms;And the test case:
public class Warshall {
public byte[][] getPathMatrix(byte [][] adjacencyMatrix) {
int numberOfNodes=adjacencyMatrix[0].length;
byte [][] pathMatrix = new byte[numberOfNodes][numberOfNodes];
System.arraycopy(adjacencyMatrix,0,pathMatrix,0,numberOfNodes);
for(int k=0;k<numberOfNodes; k++) {
for(int i=0;i<numberOfNodes; i++) {
if (pathMatrix[i][k]==0){
continue;
}
for(int j=0;j<numberOfNodes; j++) {
if(pathMatrix[i][k]==1 &&
pathMatrix[k][j]==1) {
pathMatrix[i][j]=1;
}
}
}
}
return pathMatrix;
}
}
package com.blogspot.ezetter.algorithms;
import junit.framework.TestCase;
public class WarshallTests extends TestCase {
private byte[][] adjacencyMatrix =
{{0,0,0,1},{1,0,1,1},{1,0,0,1},{1,0,1,0}};
private byte[][] expectedPathMatrix =
{{1,0,1,1},{1,0,1,1},{1,0,1,1},{1,0,1,1}};
private byte[][] adjacencyMatrix2 =
{{0,1,0},{0,0,1},{0,0,0}};
private byte[][] expectedPathMatrix2 =
{{0,1,1},{0,0,1},{0,0,0}};
public void testGetPathMatrix() {
byte[][] pathMatrix = new Warshall().getPathMatrix(adjacencyMatrix);
for(int i=0;i<adjacencyMatrix.length;i++) {
for(int j=0;j<adjacencyMatrix.length;j++) {
assertEquals("Path matrix at i=" + i + ", j=" + j + ":",
expectedPathMatrix[i][j],pathMatrix[i][j]);
}
}
pathMatrix = new Warshall().getPathMatrix(adjacencyMatrix2);
for(int i=0;i<adjacencyMatrix2.length;i++) {
for(int j=0;j<adjacencyMatrix2.length;j++) {
assertEquals("Path matrix at i=" + i + ", j=" + j + ":",
expectedPathMatrix2[i][j],pathMatrix[i][j]);
}
}
}
