Warshall's Algorithm in Ruby

Among my current projects is to learn Ruby. Although my background is almost entirely in statically typed languages I feel that to be a complete programmer I also need to be comfortable in a dynamically typed language. Ruby is definitely interesting. I'm not sure I'm sold on the value of dynamic typing. It seems to deny one the opportunity of letting the language itself help with the programming task, not to mention being much less amenable to static analysis and the such. Still, one might make the case that most of the problems static typing are designed to prevent are one's good programmers shouldn't make very often anyway and that one can simply code faster in statically typed languages since one doesn't need to worry about such minor issues as... knowing the type at design time. Ruby definitely allows one to be very terse with the syntax, do complex things simply and hence program fast. And we all want to program fast, I'm sure.

Anyway this post wasn't really meant to be a discussion of the relative merits of static vs. dynamic typing, or even on why Ruby is cool (although my example below does illustrate the terseness of Ruby relative to Java). It was meant to present my first program in Ruby, a translation of my Java Warshall's algorithm implementation. Actually it's not a direct translation since I added a small optimization. I realized that one doesn't need to bother with the j loop if (i,k)=0. If you can't get from i to k at all you definitely can't get form i to j through k. This needs to be added to the Java implementation, which I'll get around to eventually. Note that this improvement changes the algorithm's best case (a completely unconnected graph) time complexity to Θ(n)=n². Average and worst cases remain Θ(n)=n³.

I don't have a test case for this since I haven't yet learned how to do test cases in Ruby. OK, I'm sure I could rig one up myself, but I don't see the point. Instead I just have a script at the bottom that displays the path matrix for various adjacency matrix. I also added a little random adjacency matrix generator so that one can see more examples of the algorithm at work. One of the interesting parts of that was to choose reasonable edge densities to get a nice number of paths (using n/2 as the randomizer's cutoff seems to work well).

So, here's the algorithm:

class Warshall
 def initialize(adjacencyMatrix)
  @adjacencyMatrix=adjacencyMatrix
 end
 
 def getPathMatrix
  numNodes=@adjacencyMatrix[0].length
  pathMatrix=Array.new(@adjacencyMatrix)
  for k in 0...numNodes
   for i in 0...numNodes
    #Optimization: if no path from i to k, no need to test k to j
    if pathMatrix[i][k]==1 then 
     for j in 0...numNodes
      if pathMatrix[k][j]==1 then
       pathMatrix[i][j]=1
      end
     end
    end
   end
  end
  return pathMatrix
 end

 def showPathMatrix
  puts "adjacency"
  @adjacencyMatrix.each{|c| print c,"\n"}
  puts "path"
  getPathMatrix.each{|c| print c,"\n"}
 end 

end
#tests:
if __FILE__ == $0
 adjMatrix = [[0,1],[1,0]]
 Warshall.new(adjMatrix).showPathMatrix
 adjMatrix = [[0,1,0],[0,0,1],[0,0,0]]
 Warshall.new(adjMatrix).showPathMatrix
 adjMatrix = [[0,0,0,1],[1,0,1,1],[1,0,0,1],[1,0,1,0]]
 Warshall.new(adjMatrix).showPathMatrix
 dim=10 #randomize out a big graph
 adjMatrix=Array.new(dim){Array.new(dim)}
 for i in 0...dim do
  for j in 0...dim do
   if rand(dim/2)==0 then
    adjMatrix[i][j]=1
   else
    adjMatrix[i][j]=0
   end
  end
 end
 Warshall.new(adjMatrix).showPathMatrix
end #tests