The Joys of Java (not!)

Oh, the joys of Java (and most of its peers): You can't really separate theory from algorithm.

For example, if you want to use an idea from graph theory, you need to either go fetch a graph-algorithms library or cruft one up yourself. So, let's say you need the shortest path from one node to another. Well, maybe your graph library has an implementation of Dijkstra's Single-Source Shortest-Path (SSSP) algorithm. That's well and good, but now your library might give you the path with the fewest edges, or it might support a notion of edge costs, and now you can specify edge costs and then get SSSP as modified to take edge costs into account, and get the lowest-cost path from node A to node B. But maybe your library requires costs as double-precision floating point values, and maybe your application provides a cost function which depends (say) on the mode of transport, or even on the time of day at which you arrive at a node (which might reflect bus or train trip routing ideas). In that case, there's no fixed cost for any given edge, so the notion of providing a double-precision number to each edge is suddenly useless.

By the way, when you're running SSSP, you probably want to know what the actual path was and not just the cost to get there, so for the duration of the algorithm, you'll want to adorn each node with a reference to the previous node on the shortest path. But once you've read off your path, the adornments are just noise, and may be forgotten. Of course, your graph library could provide for a field in each node to reflect this adornment, and then just make sure to clear it in all nodes before running SSSP, which is fine in small graphs or if you want the shortest path to everywhere all the time (neither of which is usually true). Or, it could use the notion that each run of SSSP may be numbered, and, assuming you run it less that four billion times, it can use the predicate (this_run_number == node.SSSP_run_number) to decide if the node has been visited yet (and therefore if the back-pointer and path-cost fields contain valid data). (There's little point continuing a run when everything in the work queue is more costly than the best known cost to the intended target node. This means you won't visit every node every run, so it's more trouble than it's worth to clear a flag in every node. You could instead clear them all only when the run count wraps, but I digress from the main point.)

All this discounts the notion that you might be interested in running the A* algorithm instead, which uses a priority queue for which nodes to examine based on how close they are to the destination (and which therefore requires that your nodes have position in a metric space). See, the A* algorithm is a lot faster than SSSP because it tends to look only at nodes that are worth looking at. It is therefore much better for path-finding when the nodes represent points on a surface of some kind. But guess what? Your favorite graph library probably doesn't adorn nodes with XY position. And if it does, what if you need XYZ position? What if you're interested in city-block-distance instead of Euclidean distance?

I've said nothing yet of node labels, edge labels, graph colorings, directed vs. undirected edges, unique vs. non-unique edges, nodes with data records in them, finding connected components, finding convex hulls, or any of six dozen other interesting things you can do with ideas from graph theory.

Depending on what algorithms you want to run, your nodes will need different data in them. There's no universal answer: no matter what sort of node your graph library provides, there's some application for which it is inadequate.

One approach that came to mind is for all the algorithms to work by keeping a HashMap from the domain objects to the particular data created and maintained by the algorithm, and then require the client programmer to pass in an adapter from the domain to the information needed by the algorithm, similar to the way the Comparator interface works. And this may turn out OK in the specific case of widely-popular and generic graph algorithms, but:

• It creates a fairly significant cost in run time. Granted, it's (approximately) a constant multiplier, but it's still a pain.
• It's easy to do a bad job designing the interfaces involved.
• It still doesn't address the real problem, which is that data is kept around for different reasons, but it's all got to be declared in the same place.

A sufficiently well-designed notation for programming would let different parts of your program specify adornments to structures as needed for different purposes. A compiler for such a notation would then stitch all the adornments together into sensible run-time structures. The algorithm adapter idea is probably still a good one, but if it's integrated into the design of the language, then you won't have the clerical pain of writing a bunch of stuff like

new FavoriteAlgorithmAdapter() { 
    public double foo(DomainObject ob) { return ob.foo; }
    public int bar(DomainObject ob) { return ob.bar; }
    ... etc ...
}

most of which could be (and should be!) inferred from context.

So that's my rant for the day. I hope you like it.