Graph Theory

I'm not sure what happened. I don't remember finding graph theory particularly interesting in university but over the past month I've had two occasions of simple pleasure while figuring out (pretty basic) directed graph algorithms.

The first was at our last Seaside sprint, where Lukas and I were working out how to modify his Package Dependency tool to mark cycles on Seaside 2.9's dependency graph in red, so we could immediately spot problems. It's not like there aren't already algorithms for this but it was fun just trying to work one out for ourselves.

The other was this Tuesday. I woke up wondering whether I couldn't make the graph a little easier to look at by removing direct edges when we have another indirect path to the same node. In other words, if package A depends on B and package B depends on C, we could omit a dependency from package A to package C because that dependency is already implied through transitivity anyway. I pictured this as the opposite of a Transitive Closure.

It turns out that this operation is called a Transitive Reduction and there are algorithms for it but they don't seem to be very well documented online. I ended up just working something out myself using depth-first searching and path-length tracking to prune shorter paths to objects. I don't know if there's a faster way but it doesn't really need to be that fast in this context anyway. I currently abort if the graph is cyclic but I'm pretty sure you could do something like pick an arbitrary root for the cycle, treat everything within the cycle as being distance zero from each other, and you would get a reasonable (albeit non-deterministic) answer. In our case, we don't want cycles in our graph so, realistically, you would fix the cycle and rerun the dependency checker anyway. Here's the result.

This got me thinking... is there a good implementation of graph theory algorithms in Smalltalk? I would love to be able to create a Graph of my model objects (maybe implement #edges on each one or something) and then call: "graph isCyclic", "graph transitiveReduction", or "graph topologicalSortFrom: aNode". So many things can map to directed graphs and, if you could work out domain-specific solutions by really easily layering generic graphing algorithms, that would be really cool.

Sometimes solving simple problems with definable right answers is so satisfying.