2010-04-10

A Diatribe Against Constructors

I am now formally on record as being anti-constructor. Constructors are evil and should be avoided whenever possible (i.e. effectively always). An ideal language wouldn't have them at all. Fortunately while they obviously exist in Java, and indeed play a critical role in most code, the language does provide means of avoiding them and nearly completely abolishing them: the static factory method. Before describing those, and why they are good, I should obviously back up my claim that their cousins the constructors are, in fact, evil. That I will now proceed to do.

Firstly my main complaint isn't against the constructor in general... which is good because they obviously can't be entirely avoided in code... but against constructors with arguments specifically. I will argue that they tend to obfuscate code and limit the extendability of classes. I'll illustrate with an example.

Say I have a class called Circle which represents a circle on a plane (e.g. to be drawn on a display). Maybe I want to make this class sophisticated such that a programmer can be flexible in its construction. I might provide, for instance, a constructor that takes a center point and a radius and another that takes three points. Since a circle on a plane can be uniquely identified by its center and radius, or by three points on that plane, this sounds reasonable. So our constructor signatures might look like this:

public Circle(Point center, double radius)

public Circle(Point p1, Point p2, Point p3)

Looks good, at first... but wait! What are those three points? Are they three points on the circumference or a center point and two points on the circumference? Either case can uniquely construct a circle on a plane. How without (shudder the thought) reading the Javadoc is the poor programmer to know what the constructor is going to do? The reader might suggest that we could change the second constructor's arguments a bit to resolve this complication, say:

public Circle
(Point center, Point onCircumference1, Point onCircumference2)

This does resolve the ambiguity but also requires the programmer to have access to the constructor's signature. Using a modern IDE, say Eclipse, this is likely rarely a difficulty. They all have nice mechanisms for examining such details. But what if you're trying to read some code somewhere where your fancy IDE isn't available? Say on a Unix console in vi (some of us still need to do that from time to time, right?) or on somebodies poorly written blog? What if there's a line of code like:

Circle myCircle =
new Circle(new Point(10,10), new Point(25,25), new Point(50,50));

What kind of circle does that make? It's impossible to know without drilling down into the API, which seems like such a waste of time. Many (hopefully one day all) programmers have become accustomed to the concept that well chosen method names serve as implicit documentation and make code more readable. If method names are descriptive and methods are kept small then code readability skyrockets. Why are we making an exception in the critical area of object construction? Fortunately, there is an alternative. What if we ditch the constructor and add a new static method to the Circle class:

public static Circle makeCircleFromThreeCircumferencePoints
(Point p1, Point p2, Point p3) {
Circle newCircle = new Circle();
//Insert fancy math algorithm here
return newCircle;
}

Now what the method does is unambiguous: it makes a new Circle instance given three points on the circumference. Any programmer who can read English will see that quickly without any added documentation. What's more, with a good IDE simply typing Circle then a "." will bring up a list of static methods including this one from which you can choose. The programmer will quickly find what he's looking for without skipping a beat in his train of thought. How that would be accomplished with a constructor, and without a photographic memory, is hard to imagine. Some readers will, rightfully, object to the parameters having names like p1, p2, p3, preferring something like circumferencePoint1, etc. They're probably right, but since my method name is so descriptive that's somewhat redundant.

In case the reader remains unconvinced, being of the belief that self documenting code is overrated, there are more issues with constructors. They don't only make code hard to read, they limit what it can do. Specifically they make it inflexible. To illustrate, suppose in addition to creating circles given the center and radius we wish to be able to construct them given the center and circumference. How can we provide this functionality using constructors? If we need a constructor taking a point and a double for this purpose, and that is already taken to construct circles based on a center and a radius, what do we do? Create a new constructor with the arguments reversed? No doubt such abominations exist, but if one decides programmers are too lazy to divide by two and will want to also construct circles given a center and diameter? One is truly stuck.

So, to conclude, lets make our truly readable and flexible Circle class:

public class Circle{

private Circle() {
//We don't want anybody constructing un-configured Circles.
}

public static Circle makeCircleFromThreeCircumferencePoints
(Point p1, Point p2, Point p3) {
Circle newCircle = new Circle()
//Insert fancy math algorithm here
return newCircle;
}

public static Circle makeCircleFromCenterPointAndRadius
(Point center, double radius) {
Circle newCircle = new Circle()
//Insert fancy math algorithm here
return newCircle;
}

public static Circle makeCircleFromCenterPointAndCircumference
(Point center, double circumference) {
Circle newCircle = new Circle()
//Insert fancy math algorithm here
return newCircle;
}

}

So that's it... easy to read, easy to use and easy to extend. If I need new ways to build circles I add new static factories, not needing to worry that I've made the API hard to understand or needing to concoct fancy ways around already used argument type lists. Note the private constructor. This makes it so that the only way to create new Circle instances is via the static factories. The only place a Circle constructor is used is in the factory methods themselves (there's to way around that). What if we actually wanted to give the ability to generate unconfigured Circles, for configuration later? Rather than making the noarg constructor public I would still recommend creating a no argument factory, say makeUnconfiguredCircle. That way the point is explicit and the API consistent.

Finally, should one ever let classes have public constructors? While I will agree that there are cases where it is harmless to leave classes with, say, single noarg constructors I would personally discourage it. Firstly, if one is going to use static factories for classes that need to be initialized configured then using static factories in all cases will keep the API consistent. Secondly, maybe a class starts out simple, needing only a single constructor for example, but can one guarantee that it will stay that way? Our circle may have started out only needing center and radius construction, but needs expanded as the project evolved, as always. Now one either needs to refactor all the code already building Circles or mix and match constructors with static factories... not a disaster, perhaps, but at least a little ugly.

So hopefully I've convinced somebody and there will be a few less constructors littering the APIs of the future.

2009-05-06

Thoughts on SDLC

I've been reading a great deal lately on testing and development methodologies. Certainly all the rage these days are such buzzwords as Test Driven Development (TDD) and agile/RAD programming. Exactly what these terms mean have varied interpretations and I think there are few development shops that implement them precisely as any given description (except, perhaps, their own) presents it. Anyway, in reading blogs, books, Wikipedia posts, etc. I have tried to assimilate, filter and aggregate in order to come up with my own development methodology, admitting that I can't claim to be an expert in the field given that many others have spent a great deal more time thinking about the subject. Still, I feel entitled to an opinion so here goes.

First of all I want to say that I do in principle agree with the one week SDLC cycle emphasized in Agile and RAD methods. It's my experience that the waterfall SDLC concept is generally not effective. Insisting on a set of rigorous and complete requirements up front I feel is a near guarantee of project failure. Requirements change constantly, at least on every project I've been on. More to the point, we learn about the requirements in the process of trying to implement them. Things we thought up front sounded like great ideas just don't look so good as implementations. So a continuous analyze/prototype/evaluate cycle makes sense. Get ideas, see if they work and if they do make those the requirements. I think this is efficient and effective, and given the popularity of Agile methods so, apparently, do many others.

I do think that it is important to ensure that the rapid Agile cycles don't become excuses for cutting corners, though. One thing, for instance, that I keep reading in descriptions of Agile methods is "involves less documentation". I don't buy that. Why, just because we have quick cycles, do we get away with less documentation? This just sounds like a ploy by developers, famous for not wanting to document to get away with it. I feel that every week the team should be spending time keeping running documentation up to date. If they can design and program as they go, they can document as they go.

Basically the way I see it is that in Agile, one shouldn't be abandoning the steps in traditional Waterfall SDLC. One should just be compressing them all into a single week. So, planning/analysis/design/coding/testing/implementation/maintenance (well, replace implementation with prototyping, that may become implementation) gets done every week. No cutting corners in any of these steps should be allowed. The only difference is that the project is broken into bite sized steps that can be accomplished in weekly cycles. I think this is doable and practical.

The "less documentation" paradigm is especially odd given the emphasis on testing in Agile methods, specifically unit testing. Testing is another area notoriously neglected by software developers and Agile testing methods were specifically proposed to address this deficiency. Still, I'm concerned that simply declaring that every method, and ideally every logical input type to the method, needs to be tested does not guarantee good, effective tests. It's easy to toss together a quick test for a method and accomplish little more than not testing at all.

So, here's my proposal. I think that there should be some kind of guidelines such that for every unit of time spent programming, the thing must of us programmers enjoy doing most and would do all day if we were allowed, there should be some proportional unit of time devoted to these less popular activities, testing and documentation. I'm going to, as an initial estimate, propose 2:2:1. So for every 2 units (say 2 hours) of programming there should be an equal 2 units of testing and 1 unit of documentation. One might make the objection that such rigid rules are unreasonable, that every day is different and requires adjustments to the times on different tasks. So projects might have complex programming requirements but not need as much testing and documentation. I don't buy that. If a programming task was complex then it logically requires proportional testing to validate that complexity and proportional documentation to understand it. That seems reasonable to me so I'm sticking to my guns on that.

The proportions themselves I will leave negotiable since I would need to try to put it into practice and reevaluate. They seem reasonable to me on the surface but I believe in empirical evidence so I'm keeping an open mind. The testing requirement I feel pretty confident in since it seems very natural that the complexity of the testing can't be less than the complexity of the coding. In fact, maybe the testing time should be higher. Testing, let's face it, is hard, involved work. I don't think that developers should spend the same amount of time documenting as on these other two tasks, though. The primary job of a developer is not writing documentation, although it is a critical aspect of their job. Besides, even 2:1 between coding and documentation is much more than is typical (e.g. 0). A team could get very nice documents out of such an effort, I think. I doubt it should be much less, though. While not the primary role of the developer, we don't want to de-emphasize the importance of the task.

So, there's my proposal in a nutshell. I hope to think, and write, more about the subject as time goes by. Maybe I'll completely change my mind. These are admittedly initial thoughts. I definitely plan to focus on this area more in this blog, though. After all, algorithms are fun, but this is what really matters in real life software development.

2009-05-05

Horspool's Algorithm

Today, another algorithm. Admittedly this one is not likely to be of much use to many programmers as an actual implementation. Horspool's algorithm, the subject of today's post, is nothing more than a pretty efficient way to search a string for a pattern. Obviously unless your project is to write a new programming language API then you already have such facilities ready at hand. In fact I'd be willing to bet that whatever API you're using has an algorithm similar to this to do the job.

The point here is that the purpose of these exercises are not to reinvent the wheel. They are to understand how things work, under the hood so to speak. I, for one, like that. I feel that it is the sign of a good programmer to have that sort of curiosity, to not just know how to do things but how things work. For my own selfish reasons, I find that I never really understand something until I write about it. So, acknowledging that this post might not have a huge audience, at least I'll get something out of it.

Anyway, about Horspool's algorithm. Obviously the simplest way to do a string pattern search is just to start at the beginning of both string and pattern and do a character by character comparison. Then, if a mismatch is found in any character, shift the pattern one position forward in the string and do the comparison again. Really, this is probably efficient enough for most purposes, should a programmer actually need to implement such an algorithm for some reason. For large searches through many large strings something better might be worth it, though.

Obviously (hopefully) I'm not going to be so foolish as to post such a trivial algorithm as the simple version described above, so there is an optimization, Horspool's that is. (One day I'll have an algorithm named after me.) Firstly, Horspool's starts by aligning the string and pattern as described above. Then it does it's comparison starting at the end of the pattern instead of the start. Now, the key insight is that if a mismatch is found the pattern can be shifted more than a single character. For instance if the final character, the first checked, does not match and also is not contained anywhere in the pattern then the pattern can be shifted the whole length of the pattern forward in the string. If, on the other hand, there is a mismatch but the character does exist elsewhere in the pattern then the pattern can be shifted forward the distance necessary to align that character in the pattern with the string character just checked. Furthermore this is true of any character mismatch anywhere in the string. The exact same shifting rule applies.

The algorithm will continue in this way until either all characters are found to match or the start position of the pattern within the string is such that the end of the pattern would be beyond the end of the string. in that case a "no match" indicator is returned (-1 in my version).

Note that an algorithm like this would not be worth it in code that just does low frequency single character comparisons. The simple algorithm is plenty good enough for that. In fact the computation of the shift table might erase any potential efficiency gain. For large comparisons, though, say a grep on a set of large files this algorithm could make a substantial difference. Note that the shift table is calculated only once and so can be amortized across multiple searches. Of course, as I mentioned before, in the real world we already have grep at our disposal but I'm sure whatever greppers one uses have a similar implementation to this (or maybe even more efficient versions, which exist, although those are quite a bit more complex and might be considered not worth it even for api vendors. Evidence of this is that Horpool published his algorithm after the more efficient, but similar, version. Apparently he saw a need for a simplification).

Anyway, here is my Ruby implementation. I tried to include a good many comments to make the logic easy to follow. Hopefully I succeeded. Enjoy.
class Horspool
def findIn(str, pattern)
@shiftTable=Hash.new(nil) #will contain shift amounts for all valid chars
@pattern=pattern
calcShift #buld the shift table
i=0 #pos in str
j=pattern.size-1 #pos in pattern
shift=pattern.size #initialize shift to maximum posible
while i+pattern.size-1<str.size #Pattern doesn't extend past end of str
#Use shift table lookup to shift the precomputed amount minus dist from
#end of pattern (which is (pattern.size-1)-j), if that's less then
#previously computed shift make it the current shift
newShift=@shiftTable[str[i+j,1]]-((pattern.size-1)-j)
(newShift<shift)?shift=newShift:nil
if str[i+j]==pattern[j] #str/pattern char match
j-=1 #moving backward through pattern
if j<0 #Made it all the way through pattern, must match
return i
end
else
i+=shift #Start comparing at new post in str
j=pattern.size-1 #reset j to end of pattern
shift=pattern.size
end
end
return -1 #No match
end

private

def calcShift
#Precompute to shift whole pattern length for chars not in pattern
for i in 'a'..'z'
@shiftTable[i]=@pattern.size
end
#Shift distance from end of pattern-1 for chars in pattern
for i in 0... @pattern.size-1
@shiftTable[@pattern[i,1]]=(@pattern.size-i)-1
end
end
end

if __FILE__ == $0
print Horspool.new.findIn("ericzetterbaum","zett")
end

2009-05-03

Java/Tomcat Web Services

I've decided I want to have my Java algorithms library available as a web services API. This post will describe how I set about to accomplish that.

First of all, I must give credit where it is due. Most of the information on how to do this for Tomcat (my container of choice right now) came from this document by Peter Yeung. Mostly the steps laid out in that document were sufficient for my project, although there were a few gotchas that took me some time to work out. I think he was using an older version of the Java Web Services Developer Pack. It looks like there have been a few changes, including the introduction of bugs!

So, to start, I downloaded the above mentioned JWSDP as noted above. This definitely makes the job of creating the web service infrastructure easier. It has utilities to generate the WSDL and a bunch of SOAP utility classes, stuff for serialization and such. Who would want to deal with all that? Not me! (Indeed, one could create highly functional web services without ever knowing WSDL using this an other similar utilities out there.)

The actual programming steps are then quite simple. First, one needs to create an interface to define the functionality of web service. For my Warshall algorithm, it looks like this:

package algorithms.server;
import java.rmi.Remote;
import java.rmi.RemoteException;

public interface Warshall extends Remote{
public PathMatrix getPathMatrix(byte[][] adjacencyMatrix)
throws RemoteException;
}


Then I created a WarshallImpl class that implements that interface (I won't bother posting it here since it's just a POJO, basically the Warshall.java I posted earlier, but I will make the whole project available to download.) Also I created the PathMatrix class rather than just returning the matrix as an array since I want to be able to send a status back to the client, like if it made an unreasonable request.

Now, you need two XML files. One is a JaxRPC web service description file that the JWSDP deploy utility will use to get its necessary information. It should be named jaxrpc-ri.xml. It looks like this:
<?xml version="1.0" encoding="UTF-8"?>
<!-- configuration file for JWSDP wsdeploy tool -->
<webServices xmlns="http://java.sun.com/xml/ns/jax-rpc/ri/dd" version="1.0"
targetNamespaceBase="http://com.test/wsdl"
typeNamespaceBase="http://com.test/types"
>
<!-- the endpoint name becomes the service name in the WSDL -->
<endpoint name="warshallService"
interface="algorithms.Warshall"
implementation="algorithms.WarshallImpl"/>
<endpointMapping endpointName="warshallService" urlPattern="/warshallService"/>
</webServices>


Then you need a deployment descriptor. This was the first gotcha from Peter Yeung's instructions. He said to make an empty web.xml, i.e. just web-app tags with no content. This doesn't work. The utility will generate some kind of null pointer exception. After some Googling, I came up with this solution:
<?xml version="1.0" encoding="UTF-8"?>
<web-app>
<session-config>
<session-timeout>60</session-timeout>
</session-config>
</web-app>


Put both the web.xml and raxrpc-ri.xml in a config directory under your project root, and put the java source in a src directory. Also make a build directory, a dist directory and a web directory. One might choose to simplify this by keeping the configuration files in the web/WEB-INF directory, and building straight to to web/WEB-INF/classes. Or, just make a nice ant script to automate it all. I'm in the process of doing the latter, which I'll include with my project when I upload it. This will make it all very easy. In the meantime, after building the project I have to copy the conf and build contents into the web/WEB-INF and web/WEB-INF/classes directories.

Now we get to the magic parts. First, made a war file from the web directory:

jar -cvf build/myWEB-INF.war -C web/ .

Then I ran
%JWSDP_HOME%/jaxrpc/bin/wsdeploy.bat -verbose -o dist/algorithms.war build/myWEB-INF.war assuming that %JWSDP_HOME% is the install directory of JWSDP. This makes a new war file that is the web service app itself, that can then be deployed to Tomcat. Just dump this war file in the Tomcat webapps folder and the web service is deployed. That's it, done. Oh, do make sure you put the needed .jar files from the JWSDP distribution into the Tomcat lib. This is %JWSDP_HOME%\jaxrpc\lib, %JWSDP_HOME%\saaj\lib, %JWSDP_HOME%\jwsdp-shared\lib and %JWSDP_HOME%\jaxp\lib\endorsed.

OK, so now we have a functional web service. We can check that it works like so: http://localhost:8082/algorithms/warshallService?WSDL. That shows us our WSDL, which we didn't have to bother to write.

Now, how about a client? JWSDP also contains an automatic client maker. Nice! It generates all the client stub classes for us. All that's needed is another simple XML configuration file to give it instructions. For my client, it looks like this:

<?xml version="1.0"?>
<configuration xmlns="http://java.sun.com/xml/ns/jax-rpc/ri/config">
<!-- WSDL URL and generated package name -->
<wsdl location="http://localhost:8082/algorithms/warshallService?WSDL" packageName="clientStub"></wsdl>
</configuration>

I named it /config/wscompile_config.xml under the project root.

Then I ran:

%JWSDP_HOME%/jaxrpc/bin/wscompile -d build -gen:client -keep config/wscompile_config.xml

That generates all the client stub classes. Finally, make a jar of it:

jar -cvf lib/wsstub.jar -C build clientStub/

OK, now we're good to go... mostly. This was the other big gotcha. To actually use this we will need the necessary jars from the JWSDP distribution. The one's we need are from: jwsdp-shared\lib, \fastinfoset\lib and \jaxrpc\lib. Now I come to the biggest gotcha of this project You also need the saaj jars, but the ones included with the JWSDP dist DIDN'T WORK. It seems like there is some kind of incompatibility with some of the other jars, or maybe something. But I kept getting a class cast exception, specifically:

java.lang.ClassCastException: com.sun.xml.internal.messaging.saaj.soap.ver1_1.Message1_1Impl cannot be cast to com.sun.xml.messaging.saaj.soap.MessageImpl

This one drove me crazy. Finally I solved it by downloading the lib files directly from the SAAJ (SOAP with Attachments API for Java) project, https://saaj.dev.java.net/. That indeed solved the problem. And I was done with my client. My source, the part I had to write myself, looks like this:
package algorithms.client;
import java.rmi.RemoteException;
import java.util.Random;

import javax.xml.rpc.ServiceException;

import clientStub.*;

public class WarshallClient {
public static void main (String[] args) {
WarshallService warshallService = new WarshallService_Impl();
Warshall warshall = null;
try {
warshall = warshallService.getWarshallPort();
} catch (ServiceException e) {
e.printStackTrace();
}
try {
PathMatrix pm = warshall.getPathMatrix(new byte[][]{{0,0,0,1},{1,0,1,1},{1,0,0,1},{1,0,1,0}});
System.out.println();
System.out.printf("Status=%s\n",pm.getStatus());
System.out.print("Path matrix:");
for(int i=0;i<pm.getPathMatrix().length;i++) {
System.out.println();
for(int j=0;j<pm.getPathMatrix().length;j++) {
System.out.print(pm.getPathMatrix()[i][j] + ",");
}
}
} catch (RemoteException e) {
e.printStackTrace();
}
}
}

WarshallService, WarshallService_Impl and Warshall were all generated automatically by the wscompile utiltiy. Warshall.java is just a stub for the actual web service. The rest is just to test that it's actually working. And it does! Now, making web services is about as easy as making the POJOs. Nice! Now I can add my algorithms API to the cloud! I'm sure thousands of programmers are waiting anxiously. :)

Anyway, I'll post the whole source as soon as I have a chance to clean it up a little. In the meantime, I hope my experience proves useful to others.

2009-05-01

Java Interview Questions

Here are a few of the more notable Java programming questions I've had at interviews lately.

Q: How do sets and lists differ in handling multiple nulls?

A: In a Set, there will have be single null, while in a List there will be as many nulls as were inserted. This is because sets consolidate equal inputs into a single entry (no duplicates) while lists allow multiples of the same value. BTW, this comes from the mathematical definition of sets and lists.

Q: Given the following: Set s = new HashSet<String>(); what is the behavior of this set? For instance what happens if I add, say, an Integer?

A: The Set will contain the Integer. No compiler or runtime errors will occur. Whether or not a collection is a generic depends on the declaration type, not the assignment type.

Q: In an HttpSession, if one adds a HashMap as a session attribute in a request, then in another request retrieves the HashMap and adds another entry: is it necessary to set the attribute again for yet another request to retrieve the new HashMap entry?

A: Yes. If you don't then the HashMap will appear to the subsequent request as if you haven't updated the HashMap. In other words, if one modifies the object in a session attribute, the attribute needs to be re-set with the object.

Q: Are there memory leaks in Java?

A: Not in the traditional sense as they are understood in C programming, for instance. By that I mean that one doesn't need to worry about explicitly freeing memory after allocating it. The garbage collector takes care of that. There are programming habits that lead to effective memory leakage, however. For example one might have a private instance variable that is initialized in, say, a constructor. That variable might not be referenced anywhere else in the class but as long as an application retains a reference to the class object itself the variable can't be garbage collected. Now this is probably really an example of the bad programming technique of using instance variables when a local variable will do but, still, it illustrates how allocated memory can stay allocated even though it is not reachable. In a more complex example it might not be as obvious as in this simplified version.

2009-04-25

Floyd's Algorithm (Ruby)

I've got another algorithm post today. My latest is Floyd's algorithm, again in Ruby. My ultimate goal is to publish a large library of algorithms in Java, Ruby and C. Gonna have to really get moving on that project. I'll have the Java version of this guy shortly.

Floyd's algorithm is very closely related to Warshall's (as I previously presented here and here). Indeed it's sometimes called the Floyd-Warshall algorithm since Floyd apparently got the idea for it from Warshall's algorithm. It's also often called the all-pairs shortest-paths problem which is the descriptive version.

Floyd's algorithm is more commonly seen in the literature (a Google on Warshall is in fact brings this algorithm higher that Warshall's own). The reason for this is that it's useful in more applications. One often wants to know how far it is to something, say a network resource, rather than just whether or not one can get there.

The way Floyd's algorithm works is so. We start with a weight matrix of a directed graph, which is like the adjacency matrix except that it contains "weights" of edges representing distances between nodes. As with Warshall's algorithm one then iterates through intermediate nodes, call them k, to find the distance of the path between each node i,j through k. If it is smaller than the distance already calculated through a previous k, and smaller than the weight (distance) of any edge connected i to j, then the current distance in the distance matrix is replaced with the new, shorter, distance. Note that in my version I initialize the distance matrix with the weight matrix so we always compare the distance paths with, at least, the direct distance between the nodes. We might call this k=0 (or maybe k=-1 would be better given my 0 indexed arrays).

One thing I didn't note in my discussion of Warshall's algorithm is that both these algorithms are examples of dynamic programming. In dynamic programming one builds a final result from intermediate results. I this case each intermediate result is the intermediate node, k. Since we iterate through each k we build up successively all possible paths from all nodes using all possible intermediate nodes thus comparing all paths between all nodes to find the smallest.

OK, so here's the algorithm. Enjoy. (Oh, I included a randomized again, so its easy to generate lots of examples.)
class Floyd #aka all-pairs shortest paths algorithm
def initialize(weightMatrix=nil,oo=256) #256?
@weightMatrix=weightMatrix
@oo=oo #needed to set a weight considered "infinite"
end

attr_accessor :oo

attr_accessor :weightMatrix

def getDistanceMatrix
numNodes=@weightMatrix[0].length
distanceMatrix=Array.new(@weightMatrix)

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 distanceMatrix[i][k]<@oo then
for j in 0...numNodes
distance = distanceMatrix[i][k] + distanceMatrix[k][j]
if distance<distanceMatrix[i][j] then
distanceMatrix[i][j]=distance
end
end
end
end
end
distanceMatrix
end

def showDistanceMatrix
puts "weight"
@weightMatrix.each{|c| print c.to_s.gsub(@oo.to_s,"oo"),"\n"}
puts "distance"
getDistanceMatrix.each{|c| print c.to_s.gsub(@oo.to_s,"oo"),"\n"}
end

end

#tests:
if __FILE__ == $0
floyd=Floyd.new
oo=floyd.oo
floyd.weightMatrix=[[0,oo,3,oo],[2,0,oo,oo],[oo,7,0,1],[6,oo,oo,0]]
floyd.showDistanceMatrix
dim=10 #randomize out a big graph
weightMatrix=Array.new(dim){Array.new(dim)}
for i in 0...dim do
for j in 0...dim do
if i==j then
weightMatrix[i][j]=0
elsif rand(dim/2)==0 then
weightMatrix[i][j]=rand(9)+1
else
weightMatrix[i][j]=oo
end
end
end
floyd.weightMatrix=weightMatrix
floyd.showDistanceMatrix
end

2009-04-19

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)=n2. Average and worst cases remain Θ(n)=n3.

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